You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@paimon.apache.org by "discivigour (via GitHub)" <gi...@apache.org> on 2026/08/03 01:43:09 UTC
[PR] [core] Support TopN pushdown for BTree global indexes [paimon]
discivigour opened a new pull request, #8991:
URL: https://github.com/apache/paimon/pull/8991
## What changed
- add a TopN result type that keeps sortable keys and merges candidates globally across BTree readers
- support forward and reverse BTree iteration for ascending and descending TopN, including null ordering
- prune dominated BTree index files before lookup while retaining the complete file set for coverage calculation
- group candidate row IDs by key and pass the resulting row ranges into data-evolution scans
- add unit and table-level coverage for result merging, iterator direction, file selection, cross-file candidates, diagnostics, and fallback behavior
## Why
BTree global indexes could evaluate predicates, but TopN planning could not use the index ordering to reduce index and data reads. Evaluating each file independently is insufficient because the final candidates must be compared globally, and coverage handling must not treat intentionally pruned index files as unindexed data.
This change computes a conservative global candidate set for supported single-column TopN queries. The execution engine still retains the final sort and limit, so the pushdown remains a pruning optimization rather than the source of final result ordering.
## Impact
Data-evolution tables with a compatible BTree global index can reduce index-file opens, index-entry scans, and downstream row reads for ascending or descending TopN queries. Unsupported shapes and incomplete metadata continue to fall back conservatively.
## Validation
```bash
mvn -pl paimon-core -am \
-Dmaven.repo.local=/opt/homebrew/opt/maven/repository \
-DwildcardSuites=none \
-DfailIfNoTests=false \
-Dtest=GlobalIndexEvaluatorTest,TopNGlobalIndexResultTest,BTreeIndexReaderTest,LazyFilteredBTreeIndexReaderTest,BlockIteratorTest,BTreeTopNIndexFileSelectorTest,BtreeGlobalIndexTableTest \
test
```
- paimon-common: 229 tests passed
- paimon-core: 27 tests passed
- Checkstyle, Spotless, and Maven Enforcer passed
- `git diff --check` passed
--
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] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "leaves12138 (via GitHub)" <gi...@apache.org>.
leaves12138 commented on code in PR #8991:
URL: https://github.com/apache/paimon/pull/8991#discussion_r3700948458
##########
paimon-core/src/main/java/org/apache/paimon/globalindex/BTreeTopNIndexFileSelector.java:
##########
@@ -0,0 +1,174 @@
+/*
+ * 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;
+
+import org.apache.paimon.index.GlobalIndexMeta;
+import org.apache.paimon.index.IndexFileMeta;
+import org.apache.paimon.memory.MemorySlice;
+import org.apache.paimon.predicate.SortValue;
+import org.apache.paimon.predicate.TopN;
+import org.apache.paimon.types.DataField;
+
+import javax.annotation.Nullable;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * Selects BTree index files which may contain a single-column TopN result.
+ *
+ * <p>Files without usable sorted metadata are always retained. For files with usable metadata,
+ * retaining the first {@code N} files ordered by their best value is safe because every non-empty
+ * BTree file contributes at least one row at that value. Fewer files can be retained when one file
+ * alone contains at least {@code N} rows and its worst value is not worse than the best value of
+ * every remaining file.
+ */
+class BTreeTopNIndexFileSelector {
+
+ private final KeySerializer keySerializer;
+ private final Comparator<Object> keyComparator;
+ private final boolean ascending;
+ private final boolean nullsFirst;
+
+ private BTreeTopNIndexFileSelector(DataField field, TopN topN) {
+ this.keySerializer = KeySerializer.create(field.type());
+ this.keyComparator = keySerializer.createComparator();
+ this.ascending = topN.orders().get(0).direction() == SortValue.SortDirection.ASCENDING;
+ this.nullsFirst = topN.orders().get(0).nullOrdering() == SortValue.NullOrdering.NULLS_FIRST;
+ }
+
+ static List<IndexFileMeta> select(List<IndexFileMeta> files, DataField field, TopN topN) {
+ int limit = topN.limit();
+ if (limit == 0) {
+ return new ArrayList<>();
+ }
+
+ BTreeTopNIndexFileSelector selector = new BTreeTopNIndexFileSelector(field, topN);
+ List<IndexFileMeta> selected = new ArrayList<>();
+ List<RankedIndexFile> rankedFiles = new ArrayList<>();
+ for (IndexFileMeta file : files) {
+ RankedIndexFile rankedFile = selector.tryRank(file);
+ if (rankedFile == null) {
+ // Match TopNDataSplitEvaluator: unknown sources cannot be pruned.
+ selected.add(file);
Review Comment:
[P1] Fall back instead of retaining unreadable metadata
returns not only for an unrankable file, but also when is null or throws. Retaining such a file does not provide conservative TopN behavior: later unconditionally deserializes the same metadata in its constructor, so planning fails with an NPE/corruption exception instead of falling back to the normal TopN path. Please make return unsupported when any required file lacks valid sorted metadata, or add a reader path that can actually read it without this metadata.
##########
paimon-common/src/main/java/org/apache/paimon/globalindex/btree/LazyFilteredBTreeReader.java:
##########
@@ -147,6 +149,11 @@ protected RoaringNavigableMap64 greaterThan(BTreeIndexReader reader, Object lite
return bitmap(reader.visitGreaterThan(literal));
}
+ @Override
+ public CompletableFuture<Optional<GlobalIndexResult>> visitTopN(TopN topN) {
+ return visitAllFiles(reader -> reader.visitTopN(topN));
Review Comment:
[P1] Bound the cross-file TopN work
This invokes a local for every selected file. The selector can retain up to ranked files (plus all unknown files), and queues a future for every one. Each reader eagerly loads its footer/index block, materializes up to row IDs, and remains in until the scan closes. The resulting work and peak memory are , not ; for example, 557 files with limit 10,000 can retain 5.57 million candidates, potentially with millions of objects. only bounds concurrently running tasks, not total opened readers or retained results, and unlike split-level TopN there is no limit threshold. Please add a configurable max-limit fallback at minimum, and preferably use lazy file opening plus a global heap/merge with early stopping.
--
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] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8991:
URL: https://github.com/apache/paimon/pull/8991#issuecomment-5165166269
Please disable global-index TopN for incremental scan domains.
--
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] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "leaves12138 (via GitHub)" <gi...@apache.org>.
leaves12138 commented on code in PR #8991:
URL: https://github.com/apache/paimon/pull/8991#discussion_r3700948458
##########
paimon-core/src/main/java/org/apache/paimon/globalindex/BTreeTopNIndexFileSelector.java:
##########
@@ -0,0 +1,174 @@
+/*
+ * 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;
+
+import org.apache.paimon.index.GlobalIndexMeta;
+import org.apache.paimon.index.IndexFileMeta;
+import org.apache.paimon.memory.MemorySlice;
+import org.apache.paimon.predicate.SortValue;
+import org.apache.paimon.predicate.TopN;
+import org.apache.paimon.types.DataField;
+
+import javax.annotation.Nullable;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * Selects BTree index files which may contain a single-column TopN result.
+ *
+ * <p>Files without usable sorted metadata are always retained. For files with usable metadata,
+ * retaining the first {@code N} files ordered by their best value is safe because every non-empty
+ * BTree file contributes at least one row at that value. Fewer files can be retained when one file
+ * alone contains at least {@code N} rows and its worst value is not worse than the best value of
+ * every remaining file.
+ */
+class BTreeTopNIndexFileSelector {
+
+ private final KeySerializer keySerializer;
+ private final Comparator<Object> keyComparator;
+ private final boolean ascending;
+ private final boolean nullsFirst;
+
+ private BTreeTopNIndexFileSelector(DataField field, TopN topN) {
+ this.keySerializer = KeySerializer.create(field.type());
+ this.keyComparator = keySerializer.createComparator();
+ this.ascending = topN.orders().get(0).direction() == SortValue.SortDirection.ASCENDING;
+ this.nullsFirst = topN.orders().get(0).nullOrdering() == SortValue.NullOrdering.NULLS_FIRST;
+ }
+
+ static List<IndexFileMeta> select(List<IndexFileMeta> files, DataField field, TopN topN) {
+ int limit = topN.limit();
+ if (limit == 0) {
+ return new ArrayList<>();
+ }
+
+ BTreeTopNIndexFileSelector selector = new BTreeTopNIndexFileSelector(field, topN);
+ List<IndexFileMeta> selected = new ArrayList<>();
+ List<RankedIndexFile> rankedFiles = new ArrayList<>();
+ for (IndexFileMeta file : files) {
+ RankedIndexFile rankedFile = selector.tryRank(file);
+ if (rankedFile == null) {
+ // Match TopNDataSplitEvaluator: unknown sources cannot be pruned.
+ selected.add(file);
Review Comment:
[P1] Fall back instead of retaining unreadable metadata
`tryRank` returns `null` not only for an unrankable file, but also when `indexMeta()` is null or `SortedIndexFileMeta.deserialize` throws. Retaining such a file does not provide conservative TopN behavior: `BTreeIndexReader` later unconditionally deserializes the same metadata in its constructor, so planning fails with an NPE/corruption exception instead of falling back to the normal TopN path. Please make `createForTopN` return unsupported when any required file lacks valid sorted metadata, or add a reader path that can actually read it without this metadata.
##########
paimon-common/src/main/java/org/apache/paimon/globalindex/btree/LazyFilteredBTreeReader.java:
##########
@@ -147,6 +149,11 @@ protected RoaringNavigableMap64 greaterThan(BTreeIndexReader reader, Object lite
return bitmap(reader.visitGreaterThan(literal));
}
+ @Override
+ public CompletableFuture<Optional<GlobalIndexResult>> visitTopN(TopN topN) {
+ return visitAllFiles(reader -> reader.visitTopN(topN));
Review Comment:
[P1] Bound the cross-file TopN work
This invokes a local `visitTopN(limit)` for every selected file. The selector can retain up to `min(limit, fileCount)` ranked files (plus all unknown files), and `visitAllFiles` queues a future for every one. Each reader eagerly loads its footer/index block, materializes up to `limit` row IDs, and remains in `readerCache` until the scan closes. The resulting work and peak memory are `O(selectedFiles * limit)`, not `O(limit)`; for example, 557 files with limit 10,000 can retain 5.57 million candidates, potentially with millions of `KeyRowIds` objects. `global-index.thread-num` only bounds concurrently running tasks, not total opened readers or retained results, and unlike split-level TopN there is no limit threshold. Please add a configurable max-limit fallback at minimum, and preferably use lazy file opening plus a global heap/merge with early stopping.
--
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] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "discivigour (via GitHub)" <gi...@apache.org>.
discivigour commented on PR #8991:
URL: https://github.com/apache/paimon/pull/8991#issuecomment-5166494179
> Can you add tests for Spark SQL?
Added.
--
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] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #8991:
URL: https://github.com/apache/paimon/pull/8991#issuecomment-5178690075
+1
--
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] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "discivigour (via GitHub)" <gi...@apache.org>.
discivigour commented on PR #8991:
URL: https://github.com/apache/paimon/pull/8991#issuecomment-5166505255
> Please disable global-index TopN for incremental scan domains.
Thanks, I will change 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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "leaves12138 (via GitHub)" <gi...@apache.org>.
leaves12138 commented on code in PR #8991:
URL: https://github.com/apache/paimon/pull/8991#discussion_r3700948458
##########
paimon-core/src/main/java/org/apache/paimon/globalindex/BTreeTopNIndexFileSelector.java:
##########
@@ -0,0 +1,174 @@
+/*
+ * 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;
+
+import org.apache.paimon.index.GlobalIndexMeta;
+import org.apache.paimon.index.IndexFileMeta;
+import org.apache.paimon.memory.MemorySlice;
+import org.apache.paimon.predicate.SortValue;
+import org.apache.paimon.predicate.TopN;
+import org.apache.paimon.types.DataField;
+
+import javax.annotation.Nullable;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * Selects BTree index files which may contain a single-column TopN result.
+ *
+ * <p>Files without usable sorted metadata are always retained. For files with usable metadata,
+ * retaining the first {@code N} files ordered by their best value is safe because every non-empty
+ * BTree file contributes at least one row at that value. Fewer files can be retained when one file
+ * alone contains at least {@code N} rows and its worst value is not worse than the best value of
+ * every remaining file.
+ */
+class BTreeTopNIndexFileSelector {
+
+ private final KeySerializer keySerializer;
+ private final Comparator<Object> keyComparator;
+ private final boolean ascending;
+ private final boolean nullsFirst;
+
+ private BTreeTopNIndexFileSelector(DataField field, TopN topN) {
+ this.keySerializer = KeySerializer.create(field.type());
+ this.keyComparator = keySerializer.createComparator();
+ this.ascending = topN.orders().get(0).direction() == SortValue.SortDirection.ASCENDING;
+ this.nullsFirst = topN.orders().get(0).nullOrdering() == SortValue.NullOrdering.NULLS_FIRST;
+ }
+
+ static List<IndexFileMeta> select(List<IndexFileMeta> files, DataField field, TopN topN) {
+ int limit = topN.limit();
+ if (limit == 0) {
+ return new ArrayList<>();
+ }
+
+ BTreeTopNIndexFileSelector selector = new BTreeTopNIndexFileSelector(field, topN);
+ List<IndexFileMeta> selected = new ArrayList<>();
+ List<RankedIndexFile> rankedFiles = new ArrayList<>();
+ for (IndexFileMeta file : files) {
+ RankedIndexFile rankedFile = selector.tryRank(file);
+ if (rankedFile == null) {
+ // Match TopNDataSplitEvaluator: unknown sources cannot be pruned.
+ selected.add(file);
Review Comment:
[P1] Fall back instead of retaining unreadable metadata
`tryRank` returns `null` not only for an unrankable file, but also when `indexMeta()` is null or `SortedIndexFileMeta.deserialize` throws. Retaining such a file does not provide conservative TopN behavior: `BTreeIndexReader` later unconditionally deserializes the same metadata in its constructor, so planning fails with an NPE/corruption exception instead of falling back to the normal TopN path. Please make `createForTopN` return unsupported when any required file lacks valid sorted metadata, or add a reader path that can actually read it without this metadata.
##########
paimon-common/src/main/java/org/apache/paimon/globalindex/btree/LazyFilteredBTreeReader.java:
##########
@@ -147,6 +149,11 @@ protected RoaringNavigableMap64 greaterThan(BTreeIndexReader reader, Object lite
return bitmap(reader.visitGreaterThan(literal));
}
+ @Override
+ public CompletableFuture<Optional<GlobalIndexResult>> visitTopN(TopN topN) {
+ return visitAllFiles(reader -> reader.visitTopN(topN));
Review Comment:
[P1] Bound the cross-file TopN work
This invokes a local `visitTopN(limit)` for every selected file. The selector can retain up to `min(limit, fileCount)` ranked files (plus all unknown files), and `visitAllFiles` queues a future for every one. Each reader eagerly loads its footer/index block, materializes up to `limit` row IDs, and remains in `readerCache` until the scan closes. The resulting work and peak memory are `O(selectedFiles * limit)`, not `O(limit)`; for example, 557 files with limit 10,000 can retain 5.57 million candidates, potentially with millions of `KeyRowIds` objects. `global-index.thread-num` only bounds concurrently running tasks, not total opened readers or retained results, and unlike split-level TopN there is no limit threshold. Please add a configurable max-limit fallback at minimum, and preferably use lazy file opening plus a global heap/merge with early stopping.
--
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] [core] Support TopN pushdown for BTree global indexes [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi merged PR #8991:
URL: https://github.com/apache/paimon/pull/8991
--
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