You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "jimczi (via GitHub)" <gi...@apache.org> on 2026/06/03 07:07:07 UTC
[PR] Use a single two-phase strategy for doc-values range queries [lucene]
jimczi opened a new pull request, #16177:
URL: https://github.com/apache/lucene/pull/16177
### Why
Doc-values queries (numeric ranges, set membership) are naturally **two-phase**: a
`SkipBlockRangeIterator` approximation that rides the skip index, plus a `matches()` that
checks the value. That is the form the rest of Lucene drives, two-phase confirmation,
leap-frog conjunctions, `DenseConjunctionBulkScorer`, disjunction approximations.
To evaluate dense ranges in bulk (load matches into a bit set, vectorize the value check),
#16050 added a *second* strategy for the same predicate: `BatchDocValuesRangeIterator`, a
plain `DocIdSetIterator` with its own `intoBitSet`, selected by a fork inside
`SortedNumericDocValuesRangeQuery`. So today a doc-values range is a two-phase iterator in
some code paths and a plain DISI in others — two implementations of one predicate, with
different contracts, kept in lockstep by hand. An optimization applied to one (SIMD,
multi-valued support, …) carries no signal that it diverges from, or regresses, the other.
**The goal of this PR is a single strategy: a doc-values query is always a two-phase query.**
Bulk evaluation should be something the two-phase iterator can do — not a reason to leave the
two-phase form or to depend on a specific bulk scorer.
### What
Make bulk evaluation a capability of the two-phase iterator itself:
- **`TwoPhaseIterator.intoBitSet(upTo, bitSet, offset)`** — default confirms `matches()` per
doc (behavior-preserving); a subclass may override it to load matches in bulk.
`DocValuesRangeIterator` does the vectorized, `upTo`-bounded block walk, and fully-matching
runs collect as ranges via `docIDRunEnd`.
- **`DenseConjunctionBulkScorer`** drives every two-phase clause through this single bit-set
path (the parallel leap-frog path is removed); a survivor-aware step confirms only surviving
bits when an intersection turns sparse, so dense conjunctions don't regress.
- `SortedNumericDocValuesRangeQuery` drops its fork and returns the two-phase
`DocValuesRangeIterator`; `BatchDocValuesRangeIterator` is removed.
One representation, one predicate. Bulk evaluation is an override on the natural two-phase
object, reachable by the standard scorers — not a second iterator type bound to a specific
bulk scorer.
### Benchmarks
The cleanup also wins where it matters. `MultiFieldDocValuesRangeBenchmark`, 1M docs,
conjunction of N range clauses (throughput, ops/s), shown against two references: the
two-phase form *before* #16050 turned single-valued ranges into a plain `DocIdSetIterator`,
and current `main` (with #16050).
| pattern (N=3 / N=5) | two-phase (pre-#16050) | `main` | this PR | vs two-phase | vs `main` |
| ---------------------------- | ---------------------- | ------------- | ------------- | ----------------- | ----------- |
| random (selective) | 82 / 60 | 76 / 74 | 145 / 135 | **+76% / +124%** | +89% / +83% |
| dense (~70%) | 59 / 43 | 113 / 70 | 118 / 71 | **+98% / +64%** | +4% / +2% |
| clustered (disjoint, ~empty) | 22.8k / 17.0k | 90.4k / 85.4k | 56.1k / 54.2k | **+146% / +220%** | −38% / −37% |
Against the two-phase form — what every other doc-values query uses — this is a uniform win
(+64–220%). The one cell trailing `main` is the synthetic disjoint-`clustered` case, whose
intersection is essentially empty; there #16050's plain DISI is faster, but even there this
PR is +146–220% over the two-phase baseline.
Single range, phrase conjunctions, and sparse non-skip ranges are neutral (±4%); a sparse
single skip-indexed range is +41%.
### Notes
- Single-clause and phrase paths are covered by tests and benchmarks; unaffected or improved.
- A guard rejects a wrapped two-phase passed as a plain iterator (so it can never be silently
consumed as a plain DISI); a test asserts two-phase runs reach `collectRange`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use a single two-phase strategy for doc-values range queries [lucene]
Posted by "jimczi (via GitHub)" <gi...@apache.org>.
jimczi commented on code in PR #16177:
URL: https://github.com/apache/lucene/pull/16177#discussion_r3347412639
##########
lucene/CHANGES.txt:
##########
@@ -141,6 +141,11 @@ Improvements
Optimizations
---------------------
+* GITHUB#16177: Doc-values range queries are now always two-phase iterators. Bulk evaluation is
Review Comment:
Done in 7a38cc12c13 — moved to 10.5 and folded into the `GITHUB#16050` entry.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use a single two-phase strategy for doc-values range queries [lucene]
Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on code in PR #16177:
URL: https://github.com/apache/lucene/pull/16177#discussion_r3346669926
##########
lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java:
##########
@@ -287,6 +315,41 @@ public int docIDRunEnd() throws IOException {
return blockIterator.docIDRunEnd();
}
+ @Override
+ public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+ if (numericValues == null) {
+ // Generic doc values: confirm each candidate one doc at a time (the TwoPhaseIterator
+ // default). Only single-valued numeric fields can be range-evaluated block at a time.
+ super.intoBitSet(upTo, bitSet, offset);
+ return;
+ }
+ while (blockIterator.docID() < upTo) {
+ int blockStart = blockIterator.docID();
+ SkipBlockRangeIterator.Match match = blockIterator.getMatch();
+ // For MAYBE blocks docIDRunEnd() is conservative (doc+1), so use the full block boundary to
+ // evaluate the whole block at once.
+ int blockEnd =
+ match == SkipBlockRangeIterator.Match.MAYBE
+ ? Math.min(upTo, blockIterator.blockEnd())
+ : Math.min(upTo, blockIterator.docIDRunEnd());
+ switch (match) {
+ case YES -> bitSet.set(blockStart - offset, blockEnd - offset);
+ case YES_IF_PRESENT -> {
+ // All present values are in range, but the field is sparse: only a presence check.
+ for (int d = blockStart; d < blockEnd; d++) {
Review Comment:
Can we use numericValues.intoBitSet() here?
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/PhraseScorerBenchmark.java:
##########
@@ -105,6 +114,56 @@ public void tearDown() throws IOException {
dir.close();
}
+ // A constant-score conjunction with a phrase FILTER clause routes through
+ // DenseConjunctionBulkScorer
+ // (the phrase is a two-phase clause whose approximation matches ~50% but whose phrase matches
+ // ~0.1%), so this exercises the unified two-phase bit-set/survivor path. MatchAllDocsQuery forces
+ // a
+ // 2-clause conjunction so it isn't rewritten to the bare phrase.
Review Comment:
I'm not sure this is correct, MatchAllDocsQuery filters get removed at rewrite time
##########
lucene/CHANGES.txt:
##########
@@ -141,6 +141,11 @@ Improvements
Optimizations
---------------------
+* GITHUB#16177: Doc-values range queries are now always two-phase iterators. Bulk evaluation is
Review Comment:
Let's put this in 10.5?
Also I think BatchDocValuesRangeIterator hasn't actually been released, so maybe combine that CHANGES entry here?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use a single two-phase strategy for doc-values range queries [lucene]
Posted by "jimczi (via GitHub)" <gi...@apache.org>.
jimczi commented on code in PR #16177:
URL: https://github.com/apache/lucene/pull/16177#discussion_r3347411298
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/PhraseScorerBenchmark.java:
##########
@@ -105,6 +114,56 @@ public void tearDown() throws IOException {
dir.close();
}
+ // A constant-score conjunction with a phrase FILTER clause routes through
+ // DenseConjunctionBulkScorer
+ // (the phrase is a two-phase clause whose approximation matches ~50% but whose phrase matches
+ // ~0.1%), so this exercises the unified two-phase bit-set/survivor path. MatchAllDocsQuery forces
+ // a
+ // 2-clause conjunction so it isn't rewritten to the bare phrase.
Review Comment:
Good catch — `MatchAllDocsQuery` gets stripped from the multi-clause FILTER at rewrite. Fixed in 7a38cc12c13: using a real all-matching `TermQuery` as the dense lead clause instead.
##########
lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java:
##########
@@ -287,6 +315,41 @@ public int docIDRunEnd() throws IOException {
return blockIterator.docIDRunEnd();
}
+ @Override
+ public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+ if (numericValues == null) {
+ // Generic doc values: confirm each candidate one doc at a time (the TwoPhaseIterator
+ // default). Only single-valued numeric fields can be range-evaluated block at a time.
+ super.intoBitSet(upTo, bitSet, offset);
+ return;
+ }
+ while (blockIterator.docID() < upTo) {
+ int blockStart = blockIterator.docID();
+ SkipBlockRangeIterator.Match match = blockIterator.getMatch();
+ // For MAYBE blocks docIDRunEnd() is conservative (doc+1), so use the full block boundary to
+ // evaluate the whole block at once.
+ int blockEnd =
+ match == SkipBlockRangeIterator.Match.MAYBE
+ ? Math.min(upTo, blockIterator.blockEnd())
+ : Math.min(upTo, blockIterator.docIDRunEnd());
+ switch (match) {
+ case YES -> bitSet.set(blockStart - offset, blockEnd - offset);
+ case YES_IF_PRESENT -> {
+ // All present values are in range, but the field is sparse: only a presence check.
+ for (int d = blockStart; d < blockEnd; d++) {
Review Comment:
Done in 7a38cc12c13.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use a single two-phase strategy for doc-values range queries [lucene]
Posted by "jimczi (via GitHub)" <gi...@apache.org>.
jimczi merged PR #16177:
URL: https://github.com/apache/lucene/pull/16177
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org