This is an automated email from the ASF dual-hosted git repository.
JingsongLi pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/paimon.git
The following commit(s) were added to refs/heads/master by this push:
new 8aeeb15997 [common] Add support for btree global prefix range scan
(#8339)
8aeeb15997 is described below
commit 8aeeb15997eba0f5c7ea897883da47eb00bb86ee
Author: Arnav Balyan <[email protected]>
AuthorDate: Tue Jun 23 18:22:47 2026 -0700
[common] Add support for btree global prefix range scan (#8339)
- StartsWith on a btree global index returns every non null row today,
so a prefix query like col like 'abc%' reads the whole segment and the
lower level filters afterwards.
- The index keys are sorted, so a prefix is a contiguous range and can
be checked with the min and max values of the keys, similar to bitmap
global index.
- Add support for btree level pushdown which checks the min/max keys and
prunes startwith values based on the btree values.
### Benchmark (Before vs After):
High cardinality keys were generated, and query selects single prefix
using the startswith. Performance was measured against a highly
selective query (defined by the % match illustrated in the workload
column).
| Workload | Before | After | Speedup |
| --- | --- | --- | --- |
| 50K rows, 1% match | 2.73 ms | 0.085 ms | 32x |
| 1M rows, 1% match | 42.8 ms | 0.857 ms | 50x |
| 1M rows, 0.1% match | 42.2 ms | 0.061 ms | 697x |
---
.../paimon/globalindex/SortedFileMetaSelector.java | 2 +-
.../paimon/globalindex/btree/BTreeIndexReader.java | 19 ++++++++++++-
.../globalindex/btree/AbstractIndexReaderTest.java | 32 ++++++++++++++++++++++
3 files changed, 51 insertions(+), 2 deletions(-)
diff --git
a/paimon-common/src/main/java/org/apache/paimon/globalindex/SortedFileMetaSelector.java
b/paimon-common/src/main/java/org/apache/paimon/globalindex/SortedFileMetaSelector.java
index 047f7b17a5..144b3195d1 100644
---
a/paimon-common/src/main/java/org/apache/paimon/globalindex/SortedFileMetaSelector.java
+++
b/paimon-common/src/main/java/org/apache/paimon/globalindex/SortedFileMetaSelector.java
@@ -276,7 +276,7 @@ public class SortedFileMetaSelector implements
FunctionVisitor<Optional<List<Glo
.collect(Collectors.toList());
}
- protected static byte[] prefixUpperBound(byte[] prefix) {
+ public static byte[] prefixUpperBound(byte[] prefix) {
for (int i = prefix.length - 1; i >= 0; i--) {
int unsignedByte = prefix[i] & 0xFF;
if (unsignedByte != 0xFF) {
diff --git
a/paimon-common/src/main/java/org/apache/paimon/globalindex/btree/BTreeIndexReader.java
b/paimon-common/src/main/java/org/apache/paimon/globalindex/btree/BTreeIndexReader.java
index 92816e909e..e9cb833a68 100644
---
a/paimon-common/src/main/java/org/apache/paimon/globalindex/btree/BTreeIndexReader.java
+++
b/paimon-common/src/main/java/org/apache/paimon/globalindex/btree/BTreeIndexReader.java
@@ -23,6 +23,7 @@ import org.apache.paimon.fs.SeekableInputStream;
import org.apache.paimon.globalindex.GlobalIndexIOMeta;
import org.apache.paimon.globalindex.GlobalIndexResult;
import org.apache.paimon.globalindex.KeySerializer;
+import org.apache.paimon.globalindex.SortedFileMetaSelector;
import org.apache.paimon.globalindex.SortedIndexFileMeta;
import org.apache.paimon.globalindex.io.GlobalIndexFileReader;
import org.apache.paimon.io.cache.CacheManager;
@@ -250,7 +251,23 @@ public class BTreeIndexReader implements Closeable {
}
public Optional<GlobalIndexResult> visitStartsWith(Object literal) {
- return createResult(this::allNonNullRows);
+ return createResult(
+ () -> {
+ if (minKey == null) {
+ return new RoaringNavigableMap64();
+ }
+ byte[] upperBound =
+ SortedFileMetaSelector.prefixUpperBound(
+ keySerializer.serialize(literal));
+ if (upperBound == null) {
+ return rangeQuery(literal, maxKey, true, true);
+ }
+ return rangeQuery(
+ literal,
+
keySerializer.deserialize(MemorySlice.wrap(upperBound)),
+ true,
+ false);
+ });
}
public Optional<GlobalIndexResult> visitEndsWith(Object literal) {
diff --git
a/paimon-common/src/test/java/org/apache/paimon/globalindex/btree/AbstractIndexReaderTest.java
b/paimon-common/src/test/java/org/apache/paimon/globalindex/btree/AbstractIndexReaderTest.java
index b2d0fa2d7f..d2c280f1e1 100644
---
a/paimon-common/src/test/java/org/apache/paimon/globalindex/btree/AbstractIndexReaderTest.java
+++
b/paimon-common/src/test/java/org/apache/paimon/globalindex/btree/AbstractIndexReaderTest.java
@@ -44,6 +44,7 @@ import org.apache.paimon.types.CharType;
import org.apache.paimon.types.DataField;
import org.apache.paimon.types.DataType;
import org.apache.paimon.types.DataTypeDefaultVisitor;
+import org.apache.paimon.types.DataTypeFamily;
import org.apache.paimon.types.DateType;
import org.apache.paimon.types.DecimalType;
import org.apache.paimon.types.DoubleType;
@@ -275,6 +276,37 @@ public abstract class AbstractIndexReaderTest {
}
}
+ @TestTemplate
+ public void testStartsWith() throws Exception {
+ if (!dataType.is(DataTypeFamily.CHARACTER_STRING)) {
+ return;
+ }
+
+ FieldRef ref = new FieldRef(1, "testField", dataType);
+ try (GlobalIndexReader reader = prepareDataAndCreateReader()) {
+ Random random = new Random();
+ for (int i = 0; i < 5; i++) {
+ String value =
+ ((BinaryString)
data.get(random.nextInt(dataNum)).getKey()).toString();
+ String prefix = value.substring(0, 1 +
random.nextInt(value.length()));
+ GlobalIndexResult result =
+ reader.visitStartsWith(ref,
BinaryString.fromString(prefix)).join().get();
+ assertResult(
+ result, filter(obj -> ((BinaryString)
obj).toString().startsWith(prefix)));
+ }
+
+ GlobalIndexResult all =
+ reader.visitStartsWith(ref,
BinaryString.fromString("")).join().get();
+ assertResult(all, filter(Objects::nonNull));
+
+ GlobalIndexResult none =
+ reader.visitStartsWith(ref,
BinaryString.fromString("zzz_no_such_prefix"))
+ .join()
+ .get();
+ Assertions.assertTrue(none.results().isEmpty());
+ }
+ }
+
protected abstract GlobalIndexReader prepareDataAndCreateReader() throws
Exception;
protected GlobalIndexIOMeta writeData(List<Pair<Object, Long>> data)
throws IOException {
