This is an automated email from the ASF dual-hosted git repository.
Jackie-Jiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/pinot.git
The following commit(s) were added to refs/heads/master by this push:
new 201e18c8cd7 Avoid per-comparison ByteBuffer allocation in dictionary
UTF-8 compare (#18732)
201e18c8cd7 is described below
commit 201e18c8cd7c48cef607ac018bc9e5fa665ddb78
Author: Praveen <[email protected]>
AuthorDate: Tue Aug 4 16:30:28 2026 -0700
Avoid per-comparison ByteBuffer allocation in dictionary UTF-8 compare
(#18732)
---
.../pinot/perf/BenchmarkStringInListLookup.java | 164 +++++++++++++++++++++
.../local/io/util/ValueReaderComparisons.java | 49 +++---
2 files changed, 189 insertions(+), 24 deletions(-)
diff --git
a/pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkStringInListLookup.java
b/pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkStringInListLookup.java
new file mode 100644
index 00000000000..dce972bdd6f
--- /dev/null
+++
b/pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkStringInListLookup.java
@@ -0,0 +1,164 @@
+/**
+ * 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.pinot.perf;
+
+import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
+import it.unimi.dsi.fastutil.ints.IntSet;
+import java.io.File;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import java.util.concurrent.TimeUnit;
+import org.apache.commons.io.FileUtils;
+import
org.apache.pinot.segment.local.segment.creator.impl.SegmentDictionaryCreator;
+import org.apache.pinot.segment.local.segment.index.readers.StringDictionary;
+import org.apache.pinot.segment.spi.V1Constants;
+import org.apache.pinot.segment.spi.index.reader.Dictionary;
+import org.apache.pinot.segment.spi.memory.PinotDataBuffer;
+import org.apache.pinot.spi.data.DimensionFieldSpec;
+import org.apache.pinot.spi.data.FieldSpec.DataType;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+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.runner.Runner;
+import org.openjdk.jmh.runner.options.ChainedOptionsBuilder;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+import org.openjdk.jmh.runner.options.TimeValue;
+
+
+/**
+ * Micro-benchmark for resolving a large {@code IN} list against a
high-cardinality STRING dictionary whose values are
+ * bare signed 64-bit integers stored as strings (e.g. {@code
"-7930618564724103528"}) with no shared prefix. This
+ * mirrors the production hot path
+ * {@code PredicateUtils.getDictIdSet ->
BaseImmutableDictionary.getDictIdsDivideBinarySearch ->
+ * FixedByteValueReaderWriter.compareUtf8Bytes ->
ValueReaderComparisons.mismatch}.
+ *
+ * Run the same benchmark on the baseline tree and on the patched tree to
compare throughput and, with
+ * {@code -prof gc}, the per-probe allocation rate.
+ */
+@State(Scope.Benchmark)
+public class BenchmarkStringInListLookup {
+ private static final File INDEX_DIR = new File(FileUtils.getTempDirectory(),
"BenchmarkStringInListLookup");
+ private static final String COLUMN_NAME = "column";
+ private static final long SEED = 42L;
+
+ @Param({"100000", "1000000"})
+ private int _cardinality;
+
+ @Param({"100", "500"})
+ private int _inListSize;
+
+ private StringDictionary _dictionary;
+ // Sorted (lexicographically) IN-list mixing values present and absent in
the dictionary, matching the input shape
+ // that PredicateUtils hands to getDictIds(..., DIVIDE_BINARY_SEARCH).
+ private List<String> _inList;
+
+ @Setup
+ public void setUp()
+ throws IOException {
+ FileUtils.deleteDirectory(INDEX_DIR);
+ Random random = new Random(SEED);
+
+ // Generate `_cardinality` unique bare-numeric strings (full signed-long
range -> no shared prefix).
+ Set<Long> uniqueLongs = new HashSet<>(_cardinality * 2);
+ while (uniqueLongs.size() < _cardinality) {
+ uniqueLongs.add(random.nextLong());
+ }
+ String[] sortedValues = new String[_cardinality];
+ int idx = 0;
+ for (long value : uniqueLongs) {
+ sortedValues[idx++] = Long.toString(value);
+ }
+ // The dictionary stores values sorted lexicographically, so sort the same
way here.
+ Arrays.sort(sortedValues);
+
+ int maxLength;
+ try (SegmentDictionaryCreator creator = new SegmentDictionaryCreator(
+ new DimensionFieldSpec(COLUMN_NAME, DataType.STRING, true), INDEX_DIR,
false)) {
+ creator.build(sortedValues);
+ maxLength = creator.getNumBytesPerEntry();
+ }
+ _dictionary = new StringDictionary(
+ PinotDataBuffer.mapReadOnlyBigEndianFile(new File(INDEX_DIR,
COLUMN_NAME + V1Constants.Dict.FILE_EXTENSION)),
+ _cardinality, maxLength);
+
+ // Build an IN-list: ~half present (sampled from the dictionary), ~half
absent (random longs not in the dictionary).
+ List<String> inList = new ArrayList<>(_inListSize);
+ int numPresent = _inListSize / 2;
+ for (int i = 0; i < numPresent; i++) {
+ inList.add(sortedValues[random.nextInt(_cardinality)]);
+ }
+ while (inList.size() < _inListSize) {
+ long candidate = random.nextLong();
+ if (!uniqueLongs.contains(candidate)) {
+ inList.add(Long.toString(candidate));
+ }
+ }
+ inList.sort(null);
+ _inList = inList;
+ }
+
+ @TearDown
+ public void tearDown()
+ throws Exception {
+ FileUtils.deleteDirectory(INDEX_DIR);
+ }
+
+ /** End-to-end IN-list resolution as used by the IN predicate evaluator. */
+ @Benchmark
+ @BenchmarkMode(Mode.Throughput)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkDivideBinarySearch() {
+ IntSet dictIds = new IntOpenHashSet();
+ _dictionary.getDictIds(_inList, dictIds,
Dictionary.SortedBatchLookupAlgorithm.DIVIDE_BINARY_SEARCH);
+ return dictIds.size();
+ }
+
+ /** Isolates the comparison primitive: one independent binary search per
value via indexOf. */
+ @Benchmark
+ @BenchmarkMode(Mode.Throughput)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkIndexOf() {
+ int sum = 0;
+ List<String> inList = _inList;
+ for (int i = 0, n = inList.size(); i < n; i++) {
+ sum += _dictionary.indexOf(inList.get(i));
+ }
+ return sum;
+ }
+
+ public static void main(String[] args)
+ throws Exception {
+ ChainedOptionsBuilder opt =
+ new
OptionsBuilder().include(BenchmarkStringInListLookup.class.getSimpleName()).warmupTime(TimeValue.seconds(3))
+
.warmupIterations(3).measurementTime(TimeValue.seconds(5)).measurementIterations(5).forks(1)
+ .addProfiler("gc");
+ new Runner(opt.build()).run();
+ }
+}
diff --git
a/pinot-segment-local/src/main/java/org/apache/pinot/segment/local/io/util/ValueReaderComparisons.java
b/pinot-segment-local/src/main/java/org/apache/pinot/segment/local/io/util/ValueReaderComparisons.java
index a6025b673a8..f774b46aa1f 100644
---
a/pinot-segment-local/src/main/java/org/apache/pinot/segment/local/io/util/ValueReaderComparisons.java
+++
b/pinot-segment-local/src/main/java/org/apache/pinot/segment/local/io/util/ValueReaderComparisons.java
@@ -18,26 +18,32 @@
*/
package org.apache.pinot.segment.local.io.util;
-import java.nio.ByteBuffer;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
import java.nio.ByteOrder;
import org.apache.pinot.segment.spi.memory.PinotDataBuffer;
public class ValueReaderComparisons {
+ // Read 8 bytes at a time straight from the query byte[] instead of wrapping
it in a ByteBuffer on every comparison.
+ // The byte order is matched to the data buffer's order so the longs are
directly comparable (see mismatch()).
+ private static final VarHandle LONG_VIEW_LITTLE_ENDIAN =
+ MethodHandles.byteArrayViewVarHandle(long[].class,
ByteOrder.LITTLE_ENDIAN);
+ private static final VarHandle LONG_VIEW_BIG_ENDIAN =
+ MethodHandles.byteArrayViewVarHandle(long[].class, ByteOrder.BIG_ENDIAN);
+
private ValueReaderComparisons() {
}
- private static int mismatch(PinotDataBuffer dataBuffer, long startOffset,
int length, ByteBuffer buffer) {
+ private static int mismatch(PinotDataBuffer dataBuffer, long startOffset,
int length, byte[] bytes) {
boolean littleEndian = dataBuffer.order() == ByteOrder.LITTLE_ENDIAN;
- if (littleEndian) {
- buffer.order(ByteOrder.LITTLE_ENDIAN);
- }
- int limit = Math.min(length, buffer.limit());
+ VarHandle longView = littleEndian ? LONG_VIEW_LITTLE_ENDIAN :
LONG_VIEW_BIG_ENDIAN;
+ int limit = Math.min(length, bytes.length);
int loopBound = limit & ~0x7;
int i = 0;
for (; i < loopBound; i += 8) {
long ours = dataBuffer.getLong(startOffset + i);
- long theirs = buffer.getLong(i);
+ long theirs = (long) longView.get(bytes, i);
if (ours != theirs) {
long difference = ours ^ theirs;
return i + ((littleEndian ? Long.numberOfTrailingZeros(difference) :
Long.numberOfLeadingZeros(difference))
@@ -46,7 +52,7 @@ public class ValueReaderComparisons {
}
for (; i < limit; i++) {
byte ours = dataBuffer.getByte(startOffset + i);
- byte theirs = buffer.get(i);
+ byte theirs = bytes[i];
if (ours != theirs) {
return i;
}
@@ -55,20 +61,15 @@ public class ValueReaderComparisons {
}
static int compareBytes(PinotDataBuffer dataBuffer, long startOffset, int
length, byte[] bytes) {
- // can use MethodHandles.byteArrayViewVarHandle here after dropping JDK8
- ByteBuffer buffer = ByteBuffer.wrap(bytes);
- int mismatchPosition = mismatch(dataBuffer, startOffset, length, buffer);
+ int mismatchPosition = mismatch(dataBuffer, startOffset, length, bytes);
if (mismatchPosition == -1) {
return length - bytes.length;
}
- // can use Byte.compareUnsigned here after dropping JDK8
- return (dataBuffer.getByte(startOffset + mismatchPosition) & 0xFF) -
(bytes[mismatchPosition] & 0xFF);
+ return Byte.compareUnsigned(dataBuffer.getByte(startOffset +
mismatchPosition), bytes[mismatchPosition]);
}
static int compareUtf8Bytes(PinotDataBuffer dataBuffer, long startOffset,
int length, boolean padded, byte[] bytes) {
- // can use MethodHandles.byteArrayViewVarHandle here after dropping JDK8
- ByteBuffer buffer = ByteBuffer.wrap(bytes);
- int mismatchPosition = mismatch(dataBuffer, startOffset, length, buffer);
+ int mismatchPosition = mismatch(dataBuffer, startOffset, length, bytes);
if (mismatchPosition == -1) {
if (padded && bytes.length < length) {
// check if the stored string continues beyond the length of the
parameter
@@ -80,10 +81,10 @@ public class ValueReaderComparisons {
}
// we know the position of the mismatch but need to do utf8 decoding
before comparison
// to respect collation rules
- return compareUtf8(dataBuffer, startOffset, buffer, mismatchPosition);
+ return compareUtf8(dataBuffer, startOffset, bytes, mismatchPosition);
}
- private static int compareUtf8(PinotDataBuffer ourBuffer, long
ourStartOffset, ByteBuffer theirBuffer,
+ private static int compareUtf8(PinotDataBuffer ourBuffer, long
ourStartOffset, byte[] theirBytes,
int mismatchPosition) {
char ours1 = '\ufffd';
char ours2 = '\ufffd';
@@ -93,7 +94,7 @@ public class ValueReaderComparisons {
// 1. seek backwards from mismatch position to find start of each utf8
sequence
// assuming we have valid UTF-8 and knowing that the content before
mismatchPosition is
// identical, we will go back the same distance in each buffer
- while (mismatchPosition > 0 &&
isUtf8Continuation(theirBuffer.get(mismatchPosition))) {
+ while (mismatchPosition > 0 &&
isUtf8Continuation(theirBytes[mismatchPosition])) {
mismatchPosition--;
}
// 2. decode to get the 1 or 2 characters containing where the mismatch
lies
@@ -117,17 +118,17 @@ public class ValueReaderComparisons {
}
}
{
- byte first = theirBuffer.get(mismatchPosition);
+ byte first = theirBytes[mismatchPosition];
int control = first & 0xF0;
if (first >= 0) {
theirs1 = (char) (first & 0xFF);
} else if (control < 0xE0) {
- theirs1 = decode(first, theirBuffer.get(mismatchPosition + 1));
+ theirs1 = decode(first, theirBytes[mismatchPosition + 1]);
} else if (control == 0xE0) {
- theirs1 = decode(first, theirBuffer.get(mismatchPosition + 1),
theirBuffer.get(mismatchPosition + 2));
+ theirs1 = decode(first, theirBytes[mismatchPosition + 1],
theirBytes[mismatchPosition + 2]);
} else {
- int codepoint = decode(first, theirBuffer.get(mismatchPosition + 1),
theirBuffer.get(mismatchPosition + 2),
- theirBuffer.get(mismatchPosition + 3));
+ int codepoint = decode(first, theirBytes[mismatchPosition + 1],
theirBytes[mismatchPosition + 2],
+ theirBytes[mismatchPosition + 3]);
if (Character.isValidCodePoint(codepoint)) {
theirs1 = Character.highSurrogate(codepoint);
theirs2 = Character.lowSurrogate(codepoint);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
