You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@paimon.apache.org by "ArnavBalyan (via GitHub)" <gi...@apache.org> on 2026/06/28 00:41:50 UTC

[PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

ArnavBalyan opened a new pull request, #8371:
URL: https://github.com/apache/paimon/pull/8371

   ### Purpose:
    - Add a reverse btree global index that stores keys byte reversed (ReversedKeySerializer), converting a suffix query into a prefix scan since value.endsWith(s) reverse(value).startsWith(reverse(s)).
    - ReverseLazyFilteredBTreeReader routes endsWith and LIKE '%abc' through the existing prefix scan, and uses min/max pruning instead of full scan.
    - Reuses the existing btree file format (only key bytes are reversed). In the future more complex like clauses can be offloaded in combination with the straight btree index.
   
   ### Tests
    - Unit Tests


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5083439866

   Hi @JingsongLi thanks for the review, have converted to draft while this is being finalized. Will update once it's ready for re-review ty! :) 


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5083434142

   CI fail


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5003415954

   Thanks for the reviews @JingsongLi, have updated all comments can you PTAL


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5092129954

   cc @JingsongLi (all comments addressed and CI is green, there is an unrelated failure). Could you please take a look when possible thanks!


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-4954123075

   The reverse btree factory accepts all supported types such as INT, but Spark builds indexes that are hard coded as UDF1<String, byte []>and calls Binary String. from String; Non character string index creation will result in type conversion failure during Spark execution phase
   


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5216405100

   cc @JingsongLi gentle reminder thanks!


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-4823773485

   cc @JingsongLi @leaves12138 thanks! :) 


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi closed pull request #8371: [common] Introduce reverse btree global index for Paimon
URL: https://github.com/apache/paimon/pull/8371


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5264912026

   cc @JingsongLi @leaves12138 gentle reminder when you get a chance thanks!


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on code in PR #8371:
URL: https://github.com/apache/paimon/pull/8371#discussion_r3489455611


##########
paimon-common/src/test/java/org/apache/paimon/globalindex/btree/ReverseBTreeEndsWithTest.java:
##########
@@ -0,0 +1,190 @@
+/*
+ * 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.paimon.globalindex.btree;
+
+import org.apache.paimon.data.BinaryString;
+import org.apache.paimon.fs.FileIO;
+import org.apache.paimon.fs.Path;
+import org.apache.paimon.fs.PositionOutputStream;
+import org.apache.paimon.fs.local.LocalFileIO;
+import org.apache.paimon.globalindex.GlobalIndexIOMeta;
+import org.apache.paimon.globalindex.GlobalIndexReader;
+import org.apache.paimon.globalindex.GlobalIndexResult;
+import org.apache.paimon.globalindex.GlobalIndexSingleColumnWriter;
+import org.apache.paimon.globalindex.KeySerializer;
+import org.apache.paimon.globalindex.ResultEntry;
+import org.apache.paimon.globalindex.ReversedKeySerializer;
+import org.apache.paimon.globalindex.io.GlobalIndexFileReader;
+import org.apache.paimon.globalindex.io.GlobalIndexFileWriter;
+import org.apache.paimon.options.MemorySize;
+import org.apache.paimon.options.Options;
+import org.apache.paimon.predicate.FieldRef;
+import org.apache.paimon.types.DataField;
+import org.apache.paimon.types.DataType;
+import org.apache.paimon.types.VarCharType;
+import org.apache.paimon.utils.Pair;
+
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.api.io.TempDir;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Optional;
+import java.util.Random;
+import java.util.stream.Collectors;
+
+import static org.apache.paimon.shade.guava30.com.google.common.util.concurrent.MoreExecutors.newDirectExecutorService;
+import static org.assertj.core.api.Assertions.assertThat;
+
+/** Tests for {@link ReverseBTreeGlobalIndexer}. */
+public class ReverseBTreeEndsWithTest {
+
+    private static final DataType TYPE = new VarCharType(VarCharType.MAX_LENGTH);
+    private static final FieldRef REF = new FieldRef(1, "f", TYPE);
+
+    @TempDir java.nio.file.Path tempPath;
+
+    private List<Pair<Object, Long>> data;
+
+    @Test
+    public void testEndsWithAndLikeAreAccelerated() throws Exception {
+        String[] suffixes = {"red", "green", "blue", "gold"};
+        ReversedKeySerializer reversed = new ReversedKeySerializer(KeySerializer.create(TYPE));
+
+        try (GlobalIndexReader reader = buildIndex(reversed, suffixes)) {
+            for (String suffix : suffixes) {
+                List<Long> expected = idsEndingWith(suffix);
+
+                GlobalIndexResult endsWith =
+                        reader.visitEndsWith(REF, BinaryString.fromString(suffix)).join().get();
+                assertThat(rowIds(endsWith)).containsExactlyInAnyOrderElementsOf(expected);
+
+                GlobalIndexResult like =
+                        reader.visitLike(REF, BinaryString.fromString("%" + suffix)).join().get();
+                assertThat(rowIds(like)).containsExactlyInAnyOrderElementsOf(expected);
+            }
+
+            Optional<GlobalIndexResult> none =
+                    reader.visitEndsWith(REF, BinaryString.fromString("nosuchsuffix")).join();
+            assertThat(none).isPresent();
+            assertThat(none.get().results().isEmpty()).isTrue();
+        }
+    }
+
+    @Test
+    public void testOrderDependentPredicatesDecline() throws Exception {
+        String[] suffixes = {"red", "green", "blue", "gold"};
+        ReversedKeySerializer reversed = new ReversedKeySerializer(KeySerializer.create(TYPE));
+
+        try (GlobalIndexReader reader = buildIndex(reversed, suffixes)) {
+            BinaryString probe = BinaryString.fromString("row5");
+            assertThat(reader.visitStartsWith(REF, probe).join()).isEmpty();
+            assertThat(reader.visitLessThan(REF, probe).join()).isEmpty();
+            assertThat(reader.visitGreaterThan(REF, probe).join()).isEmpty();
+            assertThat(reader.visitLessOrEqual(REF, probe).join()).isEmpty();
+            assertThat(reader.visitGreaterOrEqual(REF, probe).join()).isEmpty();
+            assertThat(reader.visitBetween(REF, probe, BinaryString.fromString("row9")).join())
+                    .isEmpty();
+        }
+    }
+
+    @Test
+    public void testEqualityStillWorksOnReversedIndex() throws Exception {
+        String[] suffixes = {"red", "green", "blue", "gold"};
+        ReversedKeySerializer reversed = new ReversedKeySerializer(KeySerializer.create(TYPE));
+
+        try (GlobalIndexReader reader = buildIndex(reversed, suffixes)) {
+            BinaryString exact = (BinaryString) data.get(0).getKey();
+            List<Long> expected =
+                    data.stream()
+                            .filter(p -> p.getKey().equals(exact))
+                            .map(Pair::getValue)
+                            .collect(Collectors.toList());
+            GlobalIndexResult equal = reader.visitEqual(REF, exact).join().get();
+            assertThat(rowIds(equal)).containsExactlyInAnyOrderElementsOf(expected);
+        }
+    }
+
+    private GlobalIndexReader buildIndex(ReversedKeySerializer reversed, String[] suffixes)
+            throws IOException {
+        FileIO fileIO = LocalFileIO.create();
+        GlobalIndexFileWriter fileWriter =
+                new GlobalIndexFileWriter() {
+                    @Override
+                    public String newFileName(String prefix) {
+                        return "reverse-btree-" + prefix;
+                    }
+
+                    @Override
+                    public PositionOutputStream newOutputStream(String fileName)
+                            throws IOException {
+                        return fileIO.newOutputStream(
+                                new Path(new Path(tempPath.toUri()), fileName), true);
+                    }
+                };
+        GlobalIndexFileReader fileReader =
+                meta ->
+                        fileIO.newInputStream(
+                                new Path(new Path(tempPath.toUri()), meta.filePath()));
+
+        Options options = new Options();
+        options.set(BTreeIndexOptions.BTREE_INDEX_CACHE_SIZE, MemorySize.ofMebiBytes(8));
+        ReverseBTreeGlobalIndexer indexer =
+                new ReverseBTreeGlobalIndexer(new DataField(1, "f", TYPE), options);
+        Comparator<Object> cmp = reversed.createComparator();
+
+        Random rnd = new Random(7);
+        data = new ArrayList<>();
+        for (int i = 0; i < 20000; i++) {
+            String v = "row" + rnd.nextInt(1_000_000) + suffixes[rnd.nextInt(suffixes.length)];
+            data.add(Pair.of(BinaryString.fromString(v), (long) i));
+        }
+        data.sort((a, b) -> cmp.compare(a.getKey(), b.getKey()));

Review Comment:
   [P1] Please cover the production build path before registering this index type. This test writes a valid reverse-btree only because it sorts with the reversed-key comparator here. The real create_global_index paths do not do that: reverse-btree is not in the Spark/Flink SortedIndexTopoBuilder support lists, so it falls through to the default/generic builders, and those pass rows to BTreeIndexWriter in scan order; even SortedGlobalIndexBuilder sorts by the original index field, not the reversed bytes. Since SstFileWriter/BTreeIndexWriter require keys to be monotonically increasing in the writer comparator, an index built through the normal procedure can produce an incorrectly ordered SST and wrong suffix lookups. Please wire reverse-btree into a builder that sorts by ReversedKeySerializer ordering and add an integration test for the procedure path.



-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5158508170

   > * Flink’s `SortedIndexTopoBuilder` uses signed bytes to sort the encoded keys, but `ReversedKeySerializer` uses unsigned bytes for comparison.
   > * Non-ASCII characters in UTF-8 result in reverse order, such as `a` and `é`.
   > * This may cause the `BTreeIndexWriter`’s monotonicity check to fail or generate a reverse B-tree with incorrect ordering.
   > * Existing tests only cover ASCII characters; it is recommended to add tests for non-ASCII keys and use a comparator consistent with the serializer.
   
   Hi @JingsongLi thanks a lot for the detailed review! I have added tests for the non ascii keys. 
   I double checked the code path, looks like Flink bytes is resolving to SortUtil.compareBinary using unsigned comparator. I followed with the existing btree which uses unsigned. Have added the non ascii UT to ensure it also produces correct sort stream thanks!
   Let me know if you see any other concerns!


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5350142769

   I still need to give some more thought to whether it's necessary to add an index solely for `endsWith`.


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5010090637

   Please fix CI


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5292664008

   Fixed merge conflicts 


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5523289991

   We have already supported fm index, this is more useful for string.


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5083446488

   And you should modify the PR title and description. Should be something like `introduce reverse-btree`.


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Accelerate endsWith and like '%x' with reverse btree global index [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5083450481

   Thanks I'll update this shortly!


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5132475273

      - Flink’s `SortedIndexTopoBuilder` uses signed bytes to sort the encoded keys, but `ReversedKeySerializer` uses unsigned bytes for comparison.
      - Non-ASCII characters in UTF-8 result in reverse order, such as `a` and `é`.
      - This may cause the `BTreeIndexWriter`’s monotonicity check to fail or generate a reverse B-tree with incorrect ordering.
      - Existing tests only cover ASCII characters; it is recommended to add tests for non-ASCII keys and use a comparator consistent with the serializer.


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [common] Introduce reverse btree global index for Paimon [paimon]

Posted by "ArnavBalyan (via GitHub)" <gi...@apache.org>.
ArnavBalyan commented on PR #8371:
URL: https://github.com/apache/paimon/pull/8371#issuecomment-5369268876

   Hi @JingsongLi that makes sense, let me know if we want to reopen it for the future, I suppose this may help for string search cases, thanks!


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org