This is an automated email from the ASF dual-hosted git repository.
morrySnow pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 4b8573234e0 [fix](fe) Merge TopN with child prefix order keys (#64685)
4b8573234e0 is described below
commit 4b8573234e00f29c5062a8d24a62c63c579c79da
Author: morrySnow <[email protected]>
AuthorDate: Tue Jun 23 14:59:10 2026 +0800
[fix](fe) Merge TopN with child prefix order keys (#64685)
### What problem does this PR solve?
Problem Summary: Consecutive TopN nodes were merged only when the child
order key list was a prefix of the parent order key list. When the
parent order key list was shorter and was instead a prefix of the child
list, the rule kept both TopN nodes even though the child ordering can
serve as a deterministic tie-breaker for the parent ordering. This
change allows that prefix direction, keeps the longer order key list in
the merged TopN, and adjusts LogicalTopN.withOrderKeys typing so callers
preserve their child type.
---
.../doris/nereids/rules/rewrite/MergeTopNs.java | 15 ++++--
.../rules/rewrite/PullUpProjectUnderTopN.java | 2 +-
.../nereids/trees/plans/logical/LogicalTopN.java | 2 +-
.../nereids/rules/rewrite/MergeTopNsTest.java | 21 ++++++++
.../limit_push_down/merge_topn_prefix_key.out | 11 ++++
.../limit_push_down/merge_topn_prefix_key.groovy | 63 ++++++++++++++++++++++
6 files changed, 109 insertions(+), 5 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeTopNs.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeTopNs.java
index 3614434459d..27ef659118a 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeTopNs.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeTopNs.java
@@ -29,7 +29,8 @@ import java.util.List;
* this rule aims to merge consecutive topN
* <p>
* topN - child topN
- * If child topN orderby list is prefix subList of topN =>
+ * If one TopN orderby list is a prefix of the other =>
+ * merged TopN uses the longer orderby list, with
* topN with limit = min(topN.limit, max(childTopN.limit - topN.offset, 0)),
* offset = topN.offset + childTopN.offset
*/
@@ -41,8 +42,16 @@ public class MergeTopNs extends OneRewriteRuleFactory {
LogicalTopN<Plan> childTopN = topN.child();
List<OrderKey> orderKeys = topN.getOrderKeys();
List<OrderKey> childOrderKeys = childTopN.getOrderKeys();
- if (!orderKeys.subList(0,
childOrderKeys.size()).equals(childOrderKeys)) {
- return null;
+ int shortKeyLength = Math.min(orderKeys.size(),
childOrderKeys.size());
+ if (orderKeys.size() < childOrderKeys.size()) {
+ if (!childOrderKeys.subList(0,
shortKeyLength).equals(orderKeys)) {
+ return null;
+ }
+ topN = topN.withOrderKeys(childOrderKeys);
+ } else {
+ if (!orderKeys.subList(0,
childOrderKeys.size()).equals(childOrderKeys)) {
+ return null;
+ }
}
long offset = topN.getOffset();
long limit = topN.getLimit();
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectUnderTopN.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectUnderTopN.java
index 88482d948b6..7d12de12b74 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectUnderTopN.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectUnderTopN.java
@@ -73,7 +73,7 @@ public class PullUpProjectUnderTopN extends
OneRewriteRuleFactory {
if (!outputSet.containsAll(allUsedSlots)) {
return null;
}
- LogicalTopN<Plan> newTopN =
topN.withOrderKeys(newOrderKeys);
+ LogicalTopN<?> newTopN = topN.withOrderKeys(newOrderKeys);
if (outputSet.size() == allUsedSlots.size()) {
Preconditions.checkState(outputSet.equals(allUsedSlots));
return
project.withChildren(newTopN.withChildren(project.child()));
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
index 903f58dfbc4..bc685158b57 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
@@ -128,7 +128,7 @@ public class LogicalTopN<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TYP
return expressions.get();
}
- public LogicalTopN<Plan> withOrderKeys(List<OrderKey> orderKeys) {
+ public LogicalTopN<CHILD_TYPE> withOrderKeys(List<OrderKey> orderKeys) {
return AbstractPlan.copyWithSameId(this, () ->
new LogicalTopN<>(orderKeys, limit, offset,
Optional.empty(), Optional.of(getLogicalProperties()),
child()));
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/MergeTopNsTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/MergeTopNsTest.java
index 63b2c97ac31..35ced912045 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/MergeTopNsTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/MergeTopNsTest.java
@@ -27,6 +27,7 @@ import org.apache.doris.nereids.util.PlanChecker;
import org.apache.doris.nereids.util.PlanConstructor;
import com.google.common.collect.ImmutableList;
+import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
/**
@@ -61,6 +62,26 @@ class MergeTopNsTest implements MemoPatternMatchSupported {
);
}
+ @Test
+ void testMergeChildMoreOrderKeys() {
+ LogicalPlan plan = new LogicalPlanBuilder(score)
+ .topN(20, 0, ImmutableList.of(0, 1))
+ .topN(10, 0, ImmutableList.of(0))
+ .build();
+ PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
+ .applyTopDown(new MergeTopNs())
+ .matches(
+ logicalTopN(logicalOlapScan()).when(topN -> {
+ Assertions.assertEquals(10, topN.getLimit());
+ Assertions.assertEquals(0, topN.getOffset());
+ Assertions.assertEquals(2,
topN.getOrderKeys().size());
+ Assertions.assertEquals(score.getOutput().get(0),
topN.getOrderKeys().get(0).getExpr());
+ Assertions.assertEquals(score.getOutput().get(1),
topN.getOrderKeys().get(1).getExpr());
+ return true;
+ })
+ );
+ }
+
@Test
void testOffset() {
LogicalPlan plan = new LogicalPlanBuilder(score)
diff --git
a/regression-test/data/nereids_rules_p0/limit_push_down/merge_topn_prefix_key.out
b/regression-test/data/nereids_rules_p0/limit_push_down/merge_topn_prefix_key.out
new file mode 100644
index 00000000000..7055064bf13
--- /dev/null
+++
b/regression-test/data/nereids_rules_p0/limit_push_down/merge_topn_prefix_key.out
@@ -0,0 +1,11 @@
+-- This file is automatically generated. You should know what you did if you
want to edit this
+-- !merge_child_more_order_keys_shape --
+PhysicalResultSink
+--PhysicalTopN[MERGE_SORT]
+----PhysicalDistribute[DistributionSpecGather]
+------PhysicalTopN[LOCAL_SORT]
+--------PhysicalOlapScan[merge_topn_prefix_key]
+
+-- !merge_child_more_order_keys --
+12 1 2
+13 1 3
diff --git
a/regression-test/suites/nereids_rules_p0/limit_push_down/merge_topn_prefix_key.groovy
b/regression-test/suites/nereids_rules_p0/limit_push_down/merge_topn_prefix_key.groovy
new file mode 100644
index 00000000000..8f80d381a14
--- /dev/null
+++
b/regression-test/suites/nereids_rules_p0/limit_push_down/merge_topn_prefix_key.groovy
@@ -0,0 +1,63 @@
+// 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.
+
+suite("merge_topn_prefix_key") {
+ sql "SET enable_nereids_planner=true"
+ sql "SET enable_fallback_to_original_planner=false"
+ sql "SET runtime_filter_mode=OFF"
+ sql "SET topn_lazy_materialization_threshold=-1"
+
+ sql "DROP TABLE IF EXISTS merge_topn_prefix_key"
+
+ sql """
+ CREATE TABLE merge_topn_prefix_key (
+ id INT,
+ a INT,
+ b INT
+ )
+ DUPLICATE KEY(id)
+ DISTRIBUTED BY HASH(id) BUCKETS 1
+ PROPERTIES (
+ "replication_allocation" = "tag.location.default: 1"
+ )
+ """
+
+ sql """
+ INSERT INTO merge_topn_prefix_key VALUES
+ (11, 1, 1),
+ (12, 1, 2),
+ (13, 1, 3),
+ (21, 2, 1),
+ (22, 2, 2),
+ (31, 3, 1)
+ """
+
+ qt_merge_child_more_order_keys_shape """
+ EXPLAIN SHAPE PLAN
+ SELECT id, a, b FROM (
+ SELECT id, a, b FROM merge_topn_prefix_key ORDER BY a, b LIMIT 4
+ ) t ORDER BY a LIMIT 2 OFFSET 1
+ """
+
+ qt_merge_child_more_order_keys """
+ SELECT * FROM (
+ SELECT id, a, b FROM (
+ SELECT id, a, b FROM merge_topn_prefix_key ORDER BY a, b LIMIT
4
+ ) t ORDER BY a LIMIT 2 OFFSET 1
+ ) r ORDER BY a, b, id
+ """
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
