You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2026/05/18 14:07:34 UTC
(lucene) branch main updated: Implement LeafCollector#collectRange in the collectors used in LRUCache (#16081)
This is an automated email from the ASF dual-hosted git repository.
iverase pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 33d6115c384 Implement LeafCollector#collectRange in the collectors used in LRUCache (#16081)
33d6115c384 is described below
commit 33d6115c3840a77f29de0e76e9ac507a790eb365
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Mon May 18 15:07:28 2026 +0100
Implement LeafCollector#collectRange in the collectors used in LRUCache (#16081)
---
lucene/CHANGES.txt | 2 +
.../org/apache/lucene/search/LRUQueryCache.java | 23 +++++--
.../org/apache/lucene/util/RoaringDocIdSet.java | 76 ++++++++++++++++++++-
.../apache/lucene/search/TestLRUQueryCache.java | 30 ++++++++
.../apache/lucene/util/TestRoaringDocIdSet.java | 79 ++++++++++++++++++++++
5 files changed, 202 insertions(+), 8 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 52748a51f9f..3d51b6fbb78 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -390,6 +390,8 @@ Optimizations
* GITHUB#16080: Add a BulkScrer implementation spcialized for filters that match dense ranges. (Ignacio Vera)
+* GITHUB#16081: Implement LeafCollector#collectRange in the collectors used in LRUCache. (Ignacio Vera)
+
Bug Fixes
---------------------
* GITHUB#15754: Fix HTMLStripCharFilter to prevent tags from incorrectly consuming subsequent
diff --git a/lucene/core/src/java/org/apache/lucene/search/LRUQueryCache.java b/lucene/core/src/java/org/apache/lucene/search/LRUQueryCache.java
index 0344ccadcdf..bc87550837e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/LRUQueryCache.java
+++ b/lucene/core/src/java/org/apache/lucene/search/LRUQueryCache.java
@@ -610,16 +610,22 @@ public class LRUQueryCache implements QueryCache, Accountable, Closeable {
private int[] buffer;
@Override
- public void setScorer(Scorable scorer) throws IOException {}
+ public void setScorer(Scorable scorer) {}
@Override
- public void collect(int doc) throws IOException {
+ public void collect(int doc) {
count[0]++;
bitSet.set(doc);
}
@Override
- public void collect(DocIdStream stream) throws IOException {
+ public void collectRange(int min, int max) {
+ count[0] += max - min;
+ bitSet.set(min, max);
+ }
+
+ @Override
+ public void collect(DocIdStream stream) {
if (buffer == null) {
buffer = new int[128];
}
@@ -646,15 +652,20 @@ public class LRUQueryCache implements QueryCache, Accountable, Closeable {
private int[] buffer = null;
@Override
- public void setScorer(Scorable scorer) throws IOException {}
+ public void setScorer(Scorable scorer) {}
@Override
- public void collect(int doc) throws IOException {
+ public void collect(int doc) {
builder.add(doc);
}
@Override
- public void collect(DocIdStream stream) throws IOException {
+ public void collectRange(int min, int max) {
+ builder.add(min, max);
+ }
+
+ @Override
+ public void collect(DocIdStream stream) {
if (buffer == null) {
buffer = new int[128];
}
diff --git a/lucene/core/src/java/org/apache/lucene/util/RoaringDocIdSet.java b/lucene/core/src/java/org/apache/lucene/util/RoaringDocIdSet.java
index 1eed8c1c0d9..38a7aa00915 100644
--- a/lucene/core/src/java/org/apache/lucene/util/RoaringDocIdSet.java
+++ b/lucene/core/src/java/org/apache/lucene/util/RoaringDocIdSet.java
@@ -116,6 +116,54 @@ public class RoaringDocIdSet extends DocIdSet {
currentBlock = block;
}
+ appendDocInCurrentBlock(docId, block);
+ return this;
+ }
+
+ /**
+ * Add a contiguous half-open range {@code [min, max)} of doc ids. Doc ids must remain in
+ * non-decreasing order relative to prior {@link #add(int)} calls; {@code min} must be strictly
+ * greater than the last document added (if any). Equivalent to calling {@link #add(int)} for
+ * each {@code min <= doc < max}, but uses a more efficient implementation for dense ranges.
+ *
+ * @param min inclusive lower bound (must be {@code >= 0})
+ * @param max exclusive upper bound
+ * @throws IllegalArgumentException if {@code min > max}, if {@code min <= lastDocId}, or if
+ * {@code max} exceeds {@link #Builder(int) maxDoc}
+ */
+ public Builder add(int min, int max) {
+ if (min > max) {
+ throw new IllegalArgumentException("min must be <= max, got min=" + min + " max=" + max);
+ }
+ if (min == max) {
+ return this;
+ }
+ if (min <= lastDocId) {
+ throw new IllegalArgumentException(
+ "Doc ids must be added in-order, got range starting at "
+ + min
+ + " which is <= lastDocID="
+ + lastDocId);
+ }
+ if (max > maxDoc) {
+ throw new IllegalArgumentException(
+ "max must be <= maxDoc (" + maxDoc + "), got max=" + max);
+ }
+ int doc = min;
+ while (doc < max) {
+ final int block = doc >>> 16;
+ final int blockEnd = Math.min(max, (block + 1) << 16);
+ if (block != currentBlock) {
+ flush();
+ currentBlock = block;
+ }
+ appendRangeInCurrentBlock(doc, blockEnd, block);
+ doc = blockEnd;
+ }
+ return this;
+ }
+
+ private void appendDocInCurrentBlock(int docId, int block) {
if (currentBlockCardinality < MAX_ARRAY_LENGTH) {
buffer[currentBlockCardinality] = (short) docId;
} else {
@@ -127,12 +175,36 @@ public class RoaringDocIdSet extends DocIdSet {
denseBuffer.set(doc & 0xFFFF);
}
}
- denseBuffer.set(docId & 0xFFFF);
+ denseBuffer.set(docId - (block << 16));
}
lastDocId = docId;
currentBlockCardinality += 1;
- return this;
+ }
+
+ private void appendRangeInCurrentBlock(int fromDoc, int toDocExclusive, int block) {
+ assert (fromDoc >>> 16) == block;
+ assert (toDocExclusive >>> 16) == block || toDocExclusive == (block + 1) << 16;
+ assert fromDoc < toDocExclusive;
+ final int span = toDocExclusive - fromDoc;
+ if (currentBlockCardinality + span < MAX_ARRAY_LENGTH) {
+ for (int d = fromDoc; d < toDocExclusive; d++) {
+ buffer[currentBlockCardinality++] = (short) d;
+ }
+ lastDocId = toDocExclusive - 1;
+ } else {
+ int offset = block << 16;
+ if (denseBuffer == null) {
+ final int numBits = Math.min(1 << 16, maxDoc - offset);
+ denseBuffer = new FixedBitSet(numBits);
+ for (int i = 0; i < currentBlockCardinality; i++) {
+ denseBuffer.set(buffer[i] & 0xFFFF);
+ }
+ }
+ denseBuffer.set(fromDoc - offset, toDocExclusive - offset);
+ lastDocId = toDocExclusive - 1;
+ currentBlockCardinality += span;
+ }
}
/** Add the content of the provided {@link DocIdSetIterator}. */
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestLRUQueryCache.java b/lucene/core/src/test/org/apache/lucene/search/TestLRUQueryCache.java
index d3c8989525e..47aa02cea70 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestLRUQueryCache.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestLRUQueryCache.java
@@ -1117,6 +1117,36 @@ public class TestLRUQueryCache extends LuceneTestCase {
queryCache.close();
}
+ public void testCachePopulationUsesLeafCollectorCollectRange() throws IOException {
+ final LRUQueryCache queryCache =
+ new LRUQueryCache(1_000_000, Long.MAX_VALUE, _ -> true, Float.POSITIVE_INFINITY);
+ final int maxDoc = random().nextInt(100, 1_000_000);
+ final int minDocId = random().nextInt(0, maxDoc - 1);
+ final int maxDocId = random().nextInt(minDocId + 1, maxDoc);
+ LRUQueryCache.CacheAndCount cacheAndCount =
+ queryCache.cacheImpl(
+ new BulkScorer() {
+ @Override
+ public int score(LeafCollector collector, Bits acceptDocs, int min, int max)
+ throws IOException {
+ collector.collectRange(minDocId, maxDocId);
+ return max;
+ }
+
+ @Override
+ public long cost() {
+ return maxDocId - minDocId;
+ }
+ },
+ 1_000_000);
+ assertEquals(maxDocId - minDocId, cacheAndCount.count());
+ DocIdSetIterator iterator = cacheAndCount.iterator();
+ assertEquals(minDocId, iterator.advance(0));
+ assertEquals(maxDocId, iterator.docIDRunEnd());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, iterator.advance(maxDocId));
+ queryCache.close();
+ }
+
public void testQuerySizeBytesAreCached() throws IOException {
try (Directory dir = newDirectory();
RandomIndexWriter w = new RandomIndexWriter(random(), dir)) {
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestRoaringDocIdSet.java b/lucene/core/src/test/org/apache/lucene/util/TestRoaringDocIdSet.java
index 3eb3555d442..a0193c0e5bf 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestRoaringDocIdSet.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestRoaringDocIdSet.java
@@ -121,4 +121,83 @@ public class TestRoaringDocIdSet extends BaseDocIdSetTestCase<RoaringDocIdSet> {
assertEquals(expectedDocIDRunEnd(bs, maxDoc, doc), it.docIDRunEnd());
}
}
+
+ public void testAddRangeSmall() throws IOException {
+ int maxDoc = 100;
+ BitSet expected = new BitSet(maxDoc);
+ expected.set(10, 80);
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(maxDoc);
+ b.add(10, 80);
+ assertEquals(maxDoc, expected, b.build());
+ }
+
+ public void testAddRangeDenseBlockUsesBitSetEncoding() throws IOException {
+ int maxDoc = 50_000;
+ BitSet expected = new BitSet(maxDoc);
+ expected.set(7, 43_000);
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(maxDoc);
+ b.add(7, 43_000);
+ assertEquals(maxDoc, expected, b.build());
+ }
+
+ public void testAddRangeCrossesBlockBoundary() throws IOException {
+ int maxDoc = 70_000;
+ BitSet expected = new BitSet(maxDoc);
+ expected.set(65_530, 65_545);
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(maxDoc);
+ b.add(65_530, 65_545);
+ assertEquals(maxDoc, expected, b.build());
+ }
+
+ public void testAddRangeAfterSingletonAdd() throws IOException {
+ int maxDoc = 1_000;
+ BitSet expected = new BitSet(maxDoc);
+ expected.set(5);
+ expected.set(100, 200);
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(maxDoc);
+ b.add(5);
+ b.add(100, 200);
+ assertEquals(maxDoc, expected, b.build());
+ }
+
+ public void testAddRangeEmptyNoOp() throws IOException {
+ int maxDoc = 100;
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(maxDoc);
+ b.add(10, 10);
+ b.add(0, 100);
+ BitSet expected = new BitSet(maxDoc);
+ expected.set(0, 100);
+ assertEquals(maxDoc, expected, b.build());
+ }
+
+ public void testAddRandomRange() throws IOException {
+ int maxDoc = random().nextInt(10, 250_000);
+ BitSet expected = new BitSet(maxDoc);
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(maxDoc);
+ int index = 0;
+ int iters = 0;
+ while (index + 1 < maxDoc && iters++ < 10) {
+ int end = random().nextInt(index + 1, maxDoc);
+ expected.set(index, end);
+ b.add(index, end);
+ index = end;
+ }
+ assertEquals(maxDoc, expected, b.build());
+ }
+
+ public void testAddRangeOutOfOrderThrows() {
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(100);
+ b.add(5);
+ expectThrows(IllegalArgumentException.class, () -> b.add(3, 10));
+ }
+
+ public void testAddRangeExceedsMaxDocThrows() {
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(100);
+ expectThrows(IllegalArgumentException.class, () -> b.add(0, 101));
+ }
+
+ public void testAddRangeMinGreaterThanMaxThrows() {
+ RoaringDocIdSet.Builder b = new RoaringDocIdSet.Builder(100);
+ expectThrows(IllegalArgumentException.class, () -> b.add(10, 5));
+ }
}