You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ro...@apache.org on 2026/07/13 08:41:24 UTC
(lucene) branch main updated: Apply GCD bound transform to sorted numeric rangeIntoBitSet (#16285)
This is an automated email from the ASF dual-hosted git repository.
romseygeek 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 263c3a4765f Apply GCD bound transform to sorted numeric rangeIntoBitSet (#16285)
263c3a4765f is described below
commit 263c3a4765f031c41eab7395473b7cf677eb4d67
Author: Costin Leau <co...@users.noreply.github.com>
AuthorDate: Mon Jul 13 01:41:17 2026 -0700
Apply GCD bound transform to sorted numeric rangeIntoBitSet (#16285)
GCD- and delta-encoded multi-value SortedNumericDocValues decode
every packed value during range evaluation. This transforms query
bounds into the encoded domain and compares raw values directly,
matching the recipe used for single-value NumericDocValues.
---
lucene/CHANGES.txt | 15 +-
.../SortedNumericGcdRangeIntoBitSetBenchmark.java | 194 ++++++++++++++++
.../codecs/lucene90/Lucene90DocValuesProducer.java | 103 +++++++--
...TestSkipBlockRangeIteratorBitSetOperations.java | 244 +++++++++++++++++++++
4 files changed, 527 insertions(+), 29 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 26729df9979..b01c7b3003c 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -341,6 +341,9 @@ Optimizations
* GITHUB#16352: Better cost() estimation for SkipBlockRangeIterator. (Alan Woodward)
+* GITHUB#16285: Apply GCD bound transform to sorted numeric rangeIntoBitSet, comparing raw
+ encoded values directly instead of decoding every packed value. (Costin Leau)
+
* GITHUB#16307: ReqExclBulkScorer now skips runs of excluded docs via
TwoPhaseIterator#docIDRunEnd for two-phase excluded clauses (e.g. a doc-values
not-equals filter), instead of advancing one doc at a time. (Jim Ferenczi)
@@ -358,18 +361,16 @@ Bug Fixes
---------------------
* GITHUB#16350: Disable bulk-scoring in monitor queries. (Alan Woodward)
-* GITHUB#16295: SingletonSortedNumericDocValues now delegates rangeIntoBitSet
- to the wrapped NumericDocValues, enabling optimized range evaluation for
- single-valued sorted numeric fields. (Costin Leau)
-
-<<<<<<< join_util_scores
* GITHUB#16378: Accumulate join Total/Avg scores in double precision in
TermsWithScoreCollector and JoinUtil's numeric point join, fixing
intermittent failures caused by non-associative float addition. (Luca Cavanna)
-=======
+
* GITHUB#16296: Fix missing null check in RamUsageEstimator.sizeOf(Accountable)
to be consistent with sizeOf(String) and sizeOf(Accountable[]). (Tim Grein)
->>>>>>> main
+
+* GITHUB#16295: SingletonSortedNumericDocValues now delegates rangeIntoBitSet
+ to the wrapped NumericDocValues, enabling optimized range evaluation for
+ single-valued sorted numeric fields. (Costin Leau)
Other
---------------------
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedNumericGcdRangeIntoBitSetBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedNumericGcdRangeIntoBitSetBenchmark.java
new file mode 100644
index 00000000000..1d47067937c
--- /dev/null
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedNumericGcdRangeIntoBitSetBenchmark.java
@@ -0,0 +1,194 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.Comparator;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.Stream;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.SortedNumericDocValuesField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.BooleanClause.Occur;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.TermQuery;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.MMapDirectory;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.TearDown;
+import org.openjdk.jmh.annotations.Warmup;
+
+/**
+ * Benchmarks range queries over GCD/delta-encoded sorted numeric doc values with multiple values
+ * per doc.
+ */
+@State(Scope.Thread)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.SECONDS)
+@Warmup(iterations = 3, time = 3)
+@Measurement(iterations = 5, time = 5)
+public class SortedNumericGcdRangeIntoBitSetBenchmark {
+
+ private static final String FIELD = "val";
+ private static final String LEAD_FIELD = "lead";
+ private static final String LEAD_VALUE = "yes";
+ private static final long DOMAIN = 10_000_000L;
+ private static final long DELTA = 1_700_000_000_000L;
+
+ private Directory dir;
+ private DirectoryReader reader;
+ private IndexSearcher searcher;
+ private Path path;
+ private Query query;
+
+ @Param({"1000000"})
+ public int numDocs;
+
+ @Param({"delta_only", "gcd_1000", "gcd_100_delta"})
+ public String encoding;
+
+ @Param({"1", "3", "5"})
+ public int cardinality;
+
+ @Param({"0.01", "0.1", "0.5"})
+ public double selectivity;
+
+ @Setup(Level.Trial)
+ public void setup() throws Exception {
+ path = Files.createTempDirectory("sortedNumericGcdRange");
+ dir = MMapDirectory.open(path);
+
+ Random random = new Random(0);
+ try (IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig())) {
+ for (int i = 0; i < numDocs; i++) {
+ Document doc = new Document();
+ long base = valueForDoc(i, random);
+ for (int c = 0; c < cardinality; c++) {
+ doc.add(SortedNumericDocValuesField.indexedField(FIELD, base + c * step()));
+ }
+ doc.add(new StringField(LEAD_FIELD, LEAD_VALUE, Field.Store.NO));
+ writer.addDocument(doc);
+ }
+ writer.forceMerge(1);
+ }
+
+ reader = DirectoryReader.open(dir);
+ searcher = new IndexSearcher(reader);
+ query = rangeQuery();
+ }
+
+ private long valueForDoc(int doc, Random random) {
+ long value = random.nextLong(0, DOMAIN);
+ return switch (encoding) {
+ case "delta_only" -> DELTA + value;
+ case "gcd_1000" -> value * 1_000L;
+ case "gcd_100_delta" -> DELTA + value * 100L;
+ default -> throw new IllegalArgumentException("Unknown encoding: " + encoding);
+ };
+ }
+
+ private long step() {
+ return switch (encoding) {
+ case "delta_only" -> 1;
+ case "gcd_1000" -> 1_000L;
+ case "gcd_100_delta" -> 100L;
+ default -> throw new IllegalArgumentException("Unknown encoding: " + encoding);
+ };
+ }
+
+ private Query rangeQuery() {
+ long range = Math.max(1, (long) (DOMAIN * selectivity));
+ long min = (DOMAIN - range) / 2;
+ long max = min + range;
+ long actualMin = actualValue(min);
+ long actualMax = actualValue(max);
+ Query rangeQuery = SortedNumericDocValuesField.newSlowRangeQuery(FIELD, actualMin, actualMax);
+ return new BooleanQuery.Builder()
+ .add(new TermQuery(new Term(LEAD_FIELD, LEAD_VALUE)), Occur.FILTER)
+ .add(rangeQuery, Occur.FILTER)
+ .build();
+ }
+
+ private long actualValue(long value) {
+ return switch (encoding) {
+ case "delta_only" -> DELTA + value;
+ case "gcd_1000" -> value * 1_000L;
+ case "gcd_100_delta" -> DELTA + value * 100L;
+ default -> throw new IllegalArgumentException("Unknown encoding: " + encoding);
+ };
+ }
+
+ @TearDown(Level.Trial)
+ public void tearDown() throws Exception {
+ reader.close();
+ dir.close();
+ if (Files.exists(path)) {
+ try (Stream<Path> walk = Files.walk(path)) {
+ walk.sorted(Comparator.reverseOrder())
+ .forEach(
+ p -> {
+ try {
+ Files.delete(p);
+ } catch (IOException _) {
+ }
+ });
+ }
+ }
+ }
+
+ @Benchmark
+ @Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx2g", "-Xms2g", "-XX:+AlwaysPreTouch"})
+ public int rangeQueryDefaultProvider() throws IOException {
+ return searcher.count(query);
+ }
+
+ @Benchmark
+ @Fork(
+ value = 1,
+ jvmArgsAppend = {
+ "--add-modules",
+ "jdk.incubator.vector",
+ "-Xmx2g",
+ "-Xms2g",
+ "-XX:+AlwaysPreTouch"
+ })
+ public int rangeQueryPanamaProvider() throws IOException {
+ return searcher.count(query);
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java
index f3599924c32..fcb1dad93d3 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java
@@ -482,12 +482,28 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
}
/**
- * Maps the raw query bounds {@code [minValue, maxValue]} into the encoded domain so the SIMD
- * kernel in {@link org.apache.lucene.internal.vectorization.DocValuesRangeSupport} can run
- * directly on packed values: {@code [encodedMin, encodedMax] = [ceil((min - delta) / mul),
- * floor((max - delta) / mul)]}. Open bounds (e.g. {@code Long.MIN_VALUE} or {@code
- * Long.MAX_VALUE}) are saturated to the encoded domain so they keep the SIMD path even when
- * {@code min - delta} or {@code max - delta} would overflow.
+ * Transforms query bounds {@code [minValue, maxValue]} into the encoded domain where stored
+ * values satisfy {@code stored = raw * mul + delta}. Returns {@code {encodedMin, encodedMax}} or
+ * {@code null} if the range is empty (no raw value can match).
+ */
+ private static long[] transformGcdBounds(long minValue, long maxValue, long mul, long delta) {
+ assert mul > 0;
+ long encodedMin = saturatingShiftLower(minValue, delta);
+ long encodedMax = saturatingShiftUpper(maxValue, delta);
+ if (mul != 1) {
+ encodedMin = Math.ceilDiv(encodedMin, mul);
+ encodedMax = Math.floorDiv(encodedMax, mul);
+ }
+ encodedMin = Math.max(0, encodedMin);
+ if (encodedMin > encodedMax) {
+ return null;
+ }
+ return new long[] {encodedMin, encodedMax};
+ }
+
+ /**
+ * Maps the raw query bounds {@code [minValue, maxValue]} into the encoded domain and runs the
+ * SIMD range scan directly on packed values.
*/
private static void rangeGcdDeltaIntoBitSet(
LongValues values,
@@ -499,18 +515,9 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
long delta,
FixedBitSet bitSet,
int offset) {
- assert mul > 0;
- long encodedMin = saturatingShiftLower(minValue, delta);
- long encodedMax = saturatingShiftUpper(maxValue, delta);
- if (mul != 1) {
- // Math.ceilDiv / Math.floorDiv never overflow for mul > 0 (only Long.MIN_VALUE / -1 does),
- // so the SIMD path is always taken; no fallback to the per-doc decoded loop is required.
- encodedMin = Math.ceilDiv(encodedMin, mul);
- encodedMax = Math.floorDiv(encodedMax, mul);
- }
- encodedMin = Math.max(0, encodedMin);
- if (encodedMin <= encodedMax) {
- rangeIntoBitSet(values, fromDoc, toDoc, encodedMin, encodedMax, bitSet, offset);
+ long[] bounds = transformGcdBounds(minValue, maxValue, mul, delta);
+ if (bounds != null) {
+ rangeIntoBitSet(values, fromDoc, toDoc, bounds[0], bounds[1], bitSet, offset);
}
}
@@ -1933,6 +1940,12 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
final LongValues values = getNumericValues(entry);
final int denseFixedCardinality = fixedCardinality(entry, skipperEntry);
+ final boolean hasGcdEncoding =
+ entry.bitsPerValue > 0
+ && entry.blockShift < 0
+ && entry.table == null
+ && (entry.gcd != 1 || entry.minValue != 0);
+
if (entry.docsWithFieldOffset == -1) {
// dense
return new SortedNumericDocValues() {
@@ -1940,6 +1953,7 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
int doc = -1;
long start, end;
int count;
+ LongValues rawValues;
@Override
public int nextDoc() throws IOException {
@@ -1988,7 +2002,8 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
@Override
public void rangeIntoBitSet(
- int fromDoc, int toDoc, long minValue, long maxValue, FixedBitSet bitSet, int offset) {
+ int fromDoc, int toDoc, long minValue, long maxValue, FixedBitSet bitSet, int offset)
+ throws IOException {
int endDoc = Math.min(toDoc, maxDoc);
if (fromDoc >= endDoc) {
return;
@@ -1999,16 +2014,37 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
}
return;
}
+ LongValues v;
+ long lo, hi;
+ if (hasGcdEncoding) {
+ long[] bounds = transformGcdBounds(minValue, maxValue, entry.gcd, entry.minValue);
+ if (bounds == null) {
+ return;
+ }
+ if (rawValues == null) {
+ RandomAccessInput rawSlice =
+ data.randomAccessSlice(entry.valuesOffset, entry.valuesLength);
+ rawValues =
+ getDirectReaderInstance(rawSlice, entry.bitsPerValue, 0L, entry.numValues);
+ }
+ v = rawValues;
+ lo = bounds[0];
+ hi = bounds[1];
+ } else {
+ v = values;
+ lo = minValue;
+ hi = maxValue;
+ }
int cardinality = denseFixedCardinality;
if (cardinality > 1) {
DOC_VALUES_RANGE_SUPPORT.sortedNumericRangeIntoBitSet(
- values, fromDoc, endDoc, cardinality, minValue, maxValue, bitSet, offset);
+ v, fromDoc, endDoc, cardinality, lo, hi, bitSet, offset);
return;
}
for (int currentDoc = fromDoc; currentDoc < endDoc; currentDoc++) {
long startOffset = addresses.get(currentDoc);
long endOffset = addresses.get(currentDoc + 1L);
- if (sortedNumericMatchesRange(values, startOffset, endOffset, minValue, maxValue)) {
+ if (sortedNumericMatchesRange(v, startOffset, endOffset, lo, hi)) {
bitSet.set(currentDoc - offset);
}
}
@@ -2044,6 +2080,7 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
boolean set;
long start, end;
int count;
+ LongValues rawValues;
@Override
public int nextDoc() throws IOException {
@@ -2108,11 +2145,33 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
set = false;
return;
}
+ LongValues v;
+ long lo, hi;
+ if (hasGcdEncoding) {
+ long[] bounds = transformGcdBounds(minValue, maxValue, entry.gcd, entry.minValue);
+ if (bounds == null) {
+ set = false;
+ return;
+ }
+ if (rawValues == null) {
+ RandomAccessInput rawSlice =
+ data.randomAccessSlice(entry.valuesOffset, entry.valuesLength);
+ rawValues =
+ getDirectReaderInstance(rawSlice, entry.bitsPerValue, 0L, entry.numValues);
+ }
+ v = rawValues;
+ lo = bounds[0];
+ hi = bounds[1];
+ } else {
+ v = values;
+ lo = minValue;
+ hi = maxValue;
+ }
for (; currentDoc < endDoc; currentDoc = disi.nextDoc()) {
int index = disi.index();
long startOffset = addresses.get(index);
long endOffset = addresses.get(index + 1L);
- if (sortedNumericMatchesRange(values, startOffset, endOffset, minValue, maxValue)) {
+ if (sortedNumericMatchesRange(v, startOffset, endOffset, lo, hi)) {
bitSet.set(currentDoc - offset);
}
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorBitSetOperations.java b/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorBitSetOperations.java
index 01c22552921..3dffd2efe75 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorBitSetOperations.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorBitSetOperations.java
@@ -1355,6 +1355,250 @@ public class TestSkipBlockRangeIteratorBitSetOperations extends BaseDocValuesSki
assertTrue("Expected some bits set", bitSet.cardinality() > 0);
}
+ /** Tests rangeIntoBitSet on GCD-encoded sorted numeric doc values with fixed cardinality. */
+ public void testSortedNumericGcdEncodedRangeIntoBitSet() throws Exception {
+ doTestSortedNumericGcdRangeIntoBitSet(true, 3, 7, 1_000_000L);
+ }
+
+ /** Tests rangeIntoBitSet on delta-only encoded sorted numeric doc values. */
+ public void testSortedNumericDeltaOnlyRangeIntoBitSet() throws Exception {
+ doTestSortedNumericGcdRangeIntoBitSet(true, 2, 1, 1_700_000_000_000L);
+ }
+
+ /** Tests rangeIntoBitSet on GCD-encoded sparse sorted numeric doc values. */
+ public void testSortedNumericGcdEncodedSparseRangeIntoBitSet() throws Exception {
+ doTestSortedNumericGcdRangeIntoBitSet(false, 4, 100, 500_000L);
+ }
+
+ /** Tests rangeIntoBitSet with negative values to exercise saturating shift overflow paths. */
+ public void testSortedNumericGcdNegativeValuesRangeIntoBitSet() throws Exception {
+ doTestSortedNumericGcdRangeIntoBitSet(true, 3, 7, -1_000_000_000L);
+ }
+
+ /**
+ * Tests rangeIntoBitSet on GCD-encoded sorted numeric with variable cardinality. Exercises the
+ * per-doc fallback loop (rawValues != null, denseFixedCardinality == -1) rather than the
+ * fixed-cardinality scalar fast path.
+ */
+ public void testSortedNumericGcdVariableCardinalityRangeIntoBitSet() throws Exception {
+ int numDocs = 4096 * 2;
+ long gcd = 100;
+ long offset = 500_000L;
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig iwc = new IndexWriterConfig().setCodec(new Lucene104Codec());
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (int docID = 0; docID < numDocs; docID++) {
+ Document doc = new Document();
+ long base = ((docID * 13L) % 100) * gcd + offset;
+ int cardinality = (docID % 3) + 1;
+ for (int i = 0; i < cardinality; i++) {
+ doc.add(SortedNumericDocValuesField.indexedField("sn", base + i * gcd));
+ }
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ }
+
+ try (DirectoryReader reader = DirectoryReader.open(dir)) {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ long queryMin = 20 * gcd + offset;
+ long queryMax = 40 * gcd + offset;
+
+ FixedBitSet expected = new FixedBitSet(numDocs);
+ var expectedValues = ctx.reader().getSortedNumericDocValues("sn");
+ for (int docID = 0; docID < numDocs; docID++) {
+ if (expectedValues.advanceExact(docID)) {
+ for (int i = 0, count = expectedValues.docValueCount(); i < count; i++) {
+ long value = expectedValues.nextValue();
+ if (value >= queryMin) {
+ if (value <= queryMax) {
+ expected.set(docID);
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ FixedBitSet actual = new FixedBitSet(numDocs);
+ ctx.reader()
+ .getSortedNumericDocValues("sn")
+ .rangeIntoBitSet(0, numDocs, queryMin, queryMax, actual, 0);
+ assertEquals("GCD sorted numeric variable cardinality", expected, actual);
+ }
+ }
+ }
+
+ /**
+ * Tests that rangeIntoBitSet correctly handles query bounds that fall between GCD multiples,
+ * exercising the {@code transformGcdBounds} null early-exit (no raw value can match).
+ */
+ public void testSortedNumericGcdBoundsBetweenMultiplesRangeIntoBitSet() throws Exception {
+ int numDocs = 4096 * 2;
+ long gcd = 1000;
+ long offset = 500_000L;
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig iwc = new IndexWriterConfig().setCodec(new Lucene104Codec());
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (int docID = 0; docID < numDocs; docID++) {
+ Document doc = new Document();
+ long base = ((docID * 13L) % 100) * gcd + offset;
+ for (int i = 0; i < 3; i++) {
+ doc.add(SortedNumericDocValuesField.indexedField("sn", base + i * gcd));
+ }
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ }
+
+ try (DirectoryReader reader = DirectoryReader.open(dir)) {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ long queryMin = 20 * gcd + offset + 1;
+ long queryMax = 21 * gcd + offset - 1;
+
+ FixedBitSet actual = new FixedBitSet(numDocs);
+ ctx.reader()
+ .getSortedNumericDocValues("sn")
+ .rangeIntoBitSet(0, numDocs, queryMin, queryMax, actual, 0);
+ assertEquals(
+ "GCD bounds between multiples should match zero docs", 0, actual.cardinality());
+ }
+ }
+ }
+
+ private void doTestSortedNumericGcdRangeIntoBitSet(
+ boolean dense, int cardinality, long gcd, long offset) throws Exception {
+ int numDocs = 4096 * 2;
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig iwc = new IndexWriterConfig().setCodec(new Lucene104Codec());
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (int docID = 0; docID < numDocs; docID++) {
+ Document doc = new Document();
+ if (dense || docID % 3 != 0) {
+ long base = ((docID * 13L) % 100) * gcd + offset;
+ for (int i = 0; i < cardinality; i++) {
+ doc.add(SortedNumericDocValuesField.indexedField("sn", base + i * gcd));
+ }
+ }
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ }
+
+ try (DirectoryReader reader = DirectoryReader.open(dir)) {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ long queryMin = 20 * gcd + offset;
+ long queryMax = 40 * gcd + offset;
+
+ FixedBitSet expected = new FixedBitSet(numDocs);
+ var expectedValues = ctx.reader().getSortedNumericDocValues("sn");
+ for (int docID = 0; docID < numDocs; docID++) {
+ if (expectedValues.advanceExact(docID)) {
+ for (int i = 0, count = expectedValues.docValueCount(); i < count; i++) {
+ long value = expectedValues.nextValue();
+ if (value >= queryMin) {
+ if (value <= queryMax) {
+ expected.set(docID);
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ FixedBitSet actual = new FixedBitSet(numDocs);
+ ctx.reader()
+ .getSortedNumericDocValues("sn")
+ .rangeIntoBitSet(0, numDocs, queryMin, queryMax, actual, 0);
+ assertEquals(
+ "GCD sorted numeric (dense="
+ + dense
+ + ", card="
+ + cardinality
+ + ", gcd="
+ + gcd
+ + ", offset="
+ + offset
+ + ")",
+ expected,
+ actual);
+ }
+ }
+ }
+
+ public void testSortedNumericGcdRangeIntoBitSetRandomized() throws Exception {
+ Random rng = random();
+ for (int iter = 0; iter < 10; iter++) {
+ boolean dense = rng.nextBoolean();
+ boolean variableCardinality = rng.nextBoolean();
+ int cardinality = rng.nextInt(1, 6);
+ long gcd = rng.nextLong(2, 1000);
+ long offset = rng.nextLong(0, 1_000_000_000L);
+ int numDocs = rng.nextInt(4096, 4096 * 3);
+
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig iwc = new IndexWriterConfig().setCodec(new Lucene104Codec());
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (int docID = 0; docID < numDocs; docID++) {
+ Document doc = new Document();
+ if (dense || docID % 3 != 0) {
+ long base = rng.nextLong(0, 100) * gcd + offset;
+ int docCardinality = variableCardinality ? rng.nextInt(1, 6) : cardinality;
+ for (int i = 0; i < docCardinality; i++) {
+ doc.add(SortedNumericDocValuesField.indexedField("sn", base + i * gcd));
+ }
+ }
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ }
+
+ try (DirectoryReader reader = DirectoryReader.open(dir)) {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ long queryMin = rng.nextLong(0, 50) * gcd + offset;
+ long queryMax = rng.nextLong(50, 100) * gcd + offset;
+ if (rng.nextBoolean()) {
+ queryMin += rng.nextLong(1, gcd);
+ queryMax -= rng.nextLong(1, gcd);
+ }
+
+ FixedBitSet expected = new FixedBitSet(numDocs);
+ var expectedValues = ctx.reader().getSortedNumericDocValues("sn");
+ for (int docID = 0; docID < numDocs; docID++) {
+ if (expectedValues.advanceExact(docID)) {
+ for (int i = 0, count = expectedValues.docValueCount(); i < count; i++) {
+ long value = expectedValues.nextValue();
+ if (value >= queryMin) {
+ if (value <= queryMax) {
+ expected.set(docID);
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ FixedBitSet actual = new FixedBitSet(numDocs);
+ ctx.reader()
+ .getSortedNumericDocValues("sn")
+ .rangeIntoBitSet(0, numDocs, queryMin, queryMax, actual, 0);
+ assertEquals(
+ "GCD sorted numeric randomized (dense="
+ + dense
+ + ", card="
+ + cardinality
+ + ", gcd="
+ + gcd
+ + ", offset="
+ + offset
+ + ")",
+ expected,
+ actual);
+ }
+ }
+ }
+ }
+
private static long[] rangeValues(int numDocs, LongUnaryOperator valueFunction) {
long[] values = new long[numDocs];
for (int i = 0; i < numDocs; i++) {