salvatore-campagna commented on code in PR #16160:
URL: https://github.com/apache/lucene/pull/16160#discussion_r3389968668
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java:
##########
@@ -480,6 +480,59 @@ static void rangeIntoBitSet(
values, fromDoc, toDoc, minValue, maxValue, bitSet, offset);
}
+ private static void rangeGcdDeltaIntoBitSet(
+ LongValues values,
+ int fromDoc,
+ int toDoc,
+ long minValue,
+ long maxValue,
+ long mul,
+ long delta,
+ FixedBitSet bitSet,
+ int offset) {
+ long encodedMin;
+ long encodedMax;
+ try {
+ encodedMin = Math.subtractExact(minValue, delta);
+ encodedMax = Math.subtractExact(maxValue, delta);
+ if (mul != 1) {
+ encodedMin = ceilDiv(encodedMin, mul);
Review Comment:
We already use `Math.floorDiv` for the upper bound. Is there a reason we use
`ceilDiv` instead of `Math.ceilDiv` for the lower one? With `mul > 0`
`Math.ceilDiv` is documented to never overflow, so the `Math.addExact` in
the positive branch looks redundant. Symmetriccally `Math.ceilDiv` /
`Math.floorDiv` would also read more naturally side by side.
##########
lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java:
##########
@@ -598,4 +599,108 @@ public void testRangeIntoBitSetMatchesPerDocEvaluation()
throws Exception {
}
}
}
+
Review Comment:
Should we add a case like query `[delta - 50, delta + 100]` where
`subtractExact` succeeds but `encodedMin` returns a negative result? This way
we would exercise also `Math.max(0, encodedMin)` which in my understanding is
not covered. Am I missing something?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java:
##########
@@ -480,6 +480,59 @@ static void rangeIntoBitSet(
values, fromDoc, toDoc, minValue, maxValue, bitSet, offset);
}
+ private static void rangeGcdDeltaIntoBitSet(
+ LongValues values,
+ int fromDoc,
+ int toDoc,
+ long minValue,
+ long maxValue,
+ long mul,
+ long delta,
+ FixedBitSet bitSet,
+ int offset) {
+ long encodedMin;
Review Comment:
Should we also assert `mul > 0`. It would also future-proof against a caller
that wires this up without going through `entry.gcd`.
##########
lucene/CHANGES.txt:
##########
@@ -156,6 +156,8 @@ Optimizations
* GITHUB#15597, GITHUB#15777: Reduce memory usage of NeighborArray (Viliam
Durina)
+* GITHUB# 16160: Improve numeric doc values range query performance for dense
fields that use GCD or delta encoding. (Costin Leau)
Review Comment:
I see other issues do not have a space after the `#` symbol. But does not
seem to fail any check. SHould we just align the format to be coherent?
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/GcdDeltaRangeIntoBitSetBenchmark.java:
##########
@@ -0,0 +1,206 @@
+/*
+ * 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.NumericDocValuesField;
+import org.apache.lucene.document.SortedNumericDocValuesField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.search.BooleanClause.Occur;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.MatchAllDocsQuery;
+import org.apache.lucene.search.Query;
+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 dense numeric doc values encoded as raw,
delta, GCD, or both. */
+@State(Scope.Thread)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.SECONDS)
+@Warmup(iterations = 3, time = 3)
+@Measurement(iterations = 5, time = 5)
+public class GcdDeltaRangeIntoBitSetBenchmark {
+
+ private static final String FIELD = "val";
+ private static final String NONE = "none";
+ private static final String DELTA_ONLY = "delta_only";
+ private static final String GCD_1000 = "gcd_1000";
+ private static final String GCD_100_DELTA = "gcd_100_delta";
+ 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({NONE, DELTA_ONLY, GCD_1000, GCD_100_DELTA})
+ public String encoding;
+
+ @Param({"0.01", "0.1", "0.5"})
+ public double selectivity;
+
+ @Setup(Level.Trial)
+ public void setup() throws Exception {
+ path = Files.createTempDirectory("gcdDeltaRangeIntoBitSet");
+ 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();
+ doc.add(NumericDocValuesField.indexedField(FIELD,
valueForDoc(encoding, i, random)));
+ writer.addDocument(doc);
+ }
+ writer.forceMerge(1);
+ }
+
+ reader = DirectoryReader.open(dir);
+ searcher = new IndexSearcher(reader);
+ query = rangeQuery(encoding, selectivity);
+ }
+
+ private static long valueForDoc(String encoding, int doc, Random random) {
+ if (doc == 0) {
+ return minimumValue(encoding);
+ } else if (doc == 1 && encoding.equals(GCD_100_DELTA)) {
Review Comment:
Could you explain why we need this specific condition?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java:
##########
@@ -480,6 +480,59 @@ static void rangeIntoBitSet(
values, fromDoc, toDoc, minValue, maxValue, bitSet, offset);
}
+ private static void rangeGcdDeltaIntoBitSet(
Review Comment:
Even though other helpers like `applyGcdDelta` and
`bulkDecodeByteAlignedValues` don't have Javadoc, maybe the bound
transformation here is non-obvious enough that a short comment would help.
Something like:
// Map the raw query bounds into the encoded domain so the SIMD kernel
// in DocValuesRangeSupport can run directly on packed values:
// [encodedMin, encodedMax] = [ceil((min - delta) / mul), floor((max -
delta) / mul)]
// On overflow during the transformation we fall back to the per-doc decoded
loop.
##########
lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java:
##########
@@ -598,4 +599,108 @@ public void testRangeIntoBitSetMatchesPerDocEvaluation()
throws Exception {
}
}
}
+
+ public void testRangeIntoBitSetMatchesPerDocEvaluationWithDeltaEncoding()
throws Exception {
+ long delta = 1_000_000L;
+ long[] values = rangeValues(DOC_COUNT, doc -> delta + doc);
+ assertRangeIntoBitSetMatchesPerDocEvaluation(
+ "delta-only encoded range must match decoded evaluation",
+ values,
+ delta + 127,
+ delta + 4097);
+ }
+
+ public void testRangeIntoBitSetMatchesPerDocEvaluationWithGcdEncoding()
throws Exception {
+ long[] values = rangeValues(DOC_COUNT, doc -> doc * 1_000L);
+ assertRangeIntoBitSetMatchesPerDocEvaluation(
+ "gcd encoded range must match decoded evaluation", values, 123_456L,
4_567_890L);
+ }
+
+ public void
testRangeIntoBitSetMatchesPerDocEvaluationWithGcdAndDeltaEncoding() throws
Exception {
+ long delta = 1_000_000L;
+ long[] values = rangeValues(DOC_COUNT, doc -> delta + doc * 100L);
+ assertRangeIntoBitSetMatchesPerDocEvaluation(
+ "gcd+delta encoded range must match decoded evaluation",
+ values,
+ delta + 123,
+ delta + 456_789);
+ }
+
+ public void
testRangeIntoBitSetMatchesPerDocEvaluationWhenGcdRangeFallsBetweenValues()
+ throws Exception {
+ long[] values = rangeValues(DOC_COUNT, doc -> 10L + doc * 5L);
+ assertRangeIntoBitSetMatchesPerDocEvaluation(
+ "gcd encoded gap range must match no docs", values, 11, 14);
+ }
+
+ public void testRangeIntoBitSetMatchesPerDocEvaluationWithOverflowFallback()
throws Exception {
+ long delta = 1_000_000L;
+ long[] values = rangeValues(DOC_COUNT, doc -> delta + doc);
+ assertRangeIntoBitSetMatchesPerDocEvaluation(
+ "overflowing transformed lower bound must fall back to decoded
evaluation",
+ values,
+ Long.MIN_VALUE,
+ delta + 127);
+ }
+
+ public void
testRangeIntoBitSetMatchesPerDocEvaluationWithFullGcdDeltaRange() throws
Exception {
+ long delta = 1_000_000L;
+ long[] values = rangeValues(DOC_COUNT, doc -> delta + doc * 100L);
+ assertRangeIntoBitSetMatchesPerDocEvaluation(
+ "full gcd+delta encoded range must match all docs",
+ values,
+ delta,
+ delta + (DOC_COUNT - 1L) * 100L);
+ }
+
+ public void
testRangeIntoBitSetMatchesPerDocEvaluationWithSingleGcdDeltaValue() throws
Exception {
+ long delta = 1_000_000L;
+ long value = delta + 123L * 100L;
+ long[] values = rangeValues(DOC_COUNT, doc -> delta + doc * 100L);
+ assertRangeIntoBitSetMatchesPerDocEvaluation(
+ "single gcd+delta encoded value range must match one doc", values,
value, value);
+ }
+
+ private static long[] rangeValues(int numDocs, LongUnaryOperator
valueFunction) {
+ long[] values = new long[numDocs];
+ for (int i = 0; i < numDocs; i++) {
+ values[i] = valueFunction.applyAsLong(i);
+ }
+ return values;
+ }
+
+ private void assertRangeIntoBitSetMatchesPerDocEvaluation(
+ String message, long[] values, long rangeMin, long rangeMax) throws
Exception {
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig iwc = new IndexWriterConfig().setCodec(new
Lucene104Codec());
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (long value : values) {
+ Document doc = new Document();
+ doc.add(NumericDocValuesField.indexedField("val", value));
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ }
+
+ try (DirectoryReader reader = DirectoryReader.open(dir)) {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ FixedBitSet expected = new FixedBitSet(values.length);
+ NumericDocValues slowDv = ctx.reader().getNumericDocValues("val");
+ for (int d = 0; d < values.length; d++) {
+ if (slowDv.advanceExact(d)) {
+ long value = slowDv.longValue();
+ if (value >= rangeMin && value <= rangeMax) {
+ expected.set(d);
+ }
+ }
+ }
+
+ FixedBitSet actual = new FixedBitSet(values.length);
+ NumericDocValues fastDv = ctx.reader().getNumericDocValues("val");
+ fastDv.rangeIntoBitSet(0, values.length, rangeMin, rangeMax, actual,
0);
+
+ assertEquals(message, expected, actual);
+ }
+ }
+ }
Review Comment:
Do we want a test for a query whose whole range falls below the stored
minimum? That exercises the `encodedMin > encodedMax` condition which seems not
covered by these tests. Am I missing it?
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
