You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "costin (via GitHub)" <gi...@apache.org> on 2026/06/25 21:21:40 UTC
[PR] Use LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
costin opened a new pull request, #16297:
URL: https://github.com/apache/lucene/pull/16297
Replace LongBitSet with LongHashSet in buildOrdinalSet() so memory scales with the number of matching terms rather than the total ordinal count of the segment.
This is an issue since DocValuesRangeIterator.buildOrdinalSet() builds a set of matching ordinals for MultiTermQuery rewrites which fires for prefix, wildcard, and regexp queries on doc-values-only fields.
The current implementation allocates, per query, a `LongBitSet(ordCount)` where `ordCount` is the total number of unique values in the segment. This means a wildcard query matching 10 terms against a 10M-cardinality field allocates 1.2 MB per segment of mostly-zero bits.
This PR replaces LongBitSet with LongHashSet, which allocates proportionally to matching terms (~32 bytes/entry). Contiguous ordinal sets skip the hash set allocation entirely, ords are collected into a temporary long[] and contiguity is detected from the sorted stream.
| Scenario | Old | New |
|----------|-----|-----|
| Contiguous (range query) | LongBitSet(ordCount) allocated, populated, **discarded** | long[matchCount] temp array only ; **no set allocated** |
| Non-contiguous (wildcard) | LongBitSet(ordCount) allocated, kept for per-doc lookup | long[matchCount] temp + LongHashSet(matchCount) |
| Empty (no matching terms) | returns null | returns null (unchanged) |
## Memory per _query_ instance per _segment_
| matchCount | ordCount | Old (`LongBitSet`) | New (`LongHashSet`) | Saved | Extra time/1M docs |
|-----------|----------|-------------------:|--------------------:|------:|-------------------:|
| 10 | 1K | 128 B | 320 B | -192 B | +1.4 ms |
| 10 | 100K | 12.2 KB | 320 B | 38x | +1.4 ms |
| 10 | 10M | 1.2 MB | 320 B | 3,906x | +2.1 ms |
| 100 | 1K | 128 B | 2.5 KB | -2.4 KB | +1.2 ms |
| 100 | 100K | 12.2 KB | 2.5 KB | 5x | +1.2 ms |
| 100 | 10M | 1.2 MB | 2.5 KB | 500x | +1.1 ms |
| 1000 | 1K | 128 B | 25 KB | -24.9 KB | +0.5 ms |
| 1000 | 100K | 12.2 KB | 25 KB | -12.8 KB | +1.5 ms |
| 1000 | 10M | 1.2 MB | 25 KB | 50x | +1.6 ms |
--
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 LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on code in PR #16297:
URL: https://github.com/apache/lucene/pull/16297#discussion_r3805367351
##########
lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java:
##########
@@ -145,27 +148,37 @@ boolean disjoint(DocValuesSkipper skipper) {
}
}
- private static OrdinalSet buildOrdinalSet(TermsEnum termsEnum, long ordCount) throws IOException {
+ private static OrdinalSet buildOrdinalSet(TermsEnum termsEnum) throws IOException {
if (termsEnum.next() == null) {
return null;
}
- // TODO can we be more memory efficient here? eg LongHashSet
- LongBitSet ords = new LongBitSet(ordCount);
long min = termsEnum.ord();
- ords.set(min);
long max = min;
- // Count distinct ords via getAndSet so a TermsEnum that yields a duplicate ord doesn't fool
- // the contiguity check below. The first set bit (min) is always new on a fresh bitset.
+ long[] collected = new long[] {min};
+ int count = 1;
+ long prev = min;
long distinctCount = 1;
while (termsEnum.next() != null) {
- max = termsEnum.ord();
- if (ords.getAndSet(max) == false) {
+ long ord = termsEnum.ord();
Review Comment:
Maybe worth preserving the comment (suitably reworded) about possible duplicate ords coming from a TermsEnum 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 LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on PR #16297:
URL: https://github.com/apache/lucene/pull/16297#issuecomment-5495679881
Thanks @costin! One more thing - following a suggestion from @sgup432 elsewhere - I think we can remove the benchmark? It's useful to give a motivation for a particular change, but it's not especially helpful to have in the repository longer term.
--
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 LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on PR #16297:
URL: https://github.com/apache/lucene/pull/16297#issuecomment-5523302728
Thanks @costin!
--
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 LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
Posted by "costin (via GitHub)" <gi...@apache.org>.
costin commented on PR #16297:
URL: https://github.com/apache/lucene/pull/16297#issuecomment-5499816934
@romseygeek done!
--
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 LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
Posted by "costin (via GitHub)" <gi...@apache.org>.
costin commented on code in PR #16297:
URL: https://github.com/apache/lucene/pull/16297#discussion_r3832920654
##########
lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java:
##########
@@ -145,27 +148,37 @@ boolean disjoint(DocValuesSkipper skipper) {
}
}
- private static OrdinalSet buildOrdinalSet(TermsEnum termsEnum, long ordCount) throws IOException {
+ private static OrdinalSet buildOrdinalSet(TermsEnum termsEnum) throws IOException {
if (termsEnum.next() == null) {
return null;
}
- // TODO can we be more memory efficient here? eg LongHashSet
- LongBitSet ords = new LongBitSet(ordCount);
long min = termsEnum.ord();
- ords.set(min);
long max = min;
- // Count distinct ords via getAndSet so a TermsEnum that yields a duplicate ord doesn't fool
- // the contiguity check below. The first set bit (min) is always new on a fresh bitset.
+ long[] collected = new long[] {min};
+ int count = 1;
+ long prev = min;
long distinctCount = 1;
while (termsEnum.next() != null) {
- max = termsEnum.ord();
- if (ords.getAndSet(max) == false) {
+ long ord = termsEnum.ord();
Review Comment:
Added comment about possible duplicate ords from TermsEnum.
--
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 LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek merged PR #16297:
URL: https://github.com/apache/lucene/pull/16297
--
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 LongHashSet for sparse ordinal sets in DocValuesRangeIterator [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #16297:
URL: https://github.com/apache/lucene/pull/16297#issuecomment-5075894227
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!
--
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