Skip to content

Commit af525d5

Browse files
authored
[fix](rbo) Guard partial TopN pushdown through joins (#67796)
### What problem does this PR solve? For a `SELECT DISTINCT` over an outer or cross join, a mixed `ORDER BY` can begin with columns from one join child and continue with columns from the other child. The TopN pushdown rule used to keep only that child's leading order-key prefix and apply a hard `LIMIT` before the join. If the prefix contains ties, the remaining order keys decide which rows belong to the final TopN. Applying the limit to an arbitrary subset of tied child rows can therefore remove the true result before the join and return a wrong row. For example, with multiple left rows sharing the same `k`, this shape is unsafe: ```sql SELECT DISTINCT l.id, l.k, r.score FROM left_table l LEFT JOIN right_table r ON l.id = r.id ORDER BY l.k, r.score LIMIT 1; ``` ### What is changed and how does it work? The rule now applies a partial order-key prefix only when that prefix is provably unique after the child-side `DISTINCT`. The proof accepts a prefix that: - covers all output columns of the child; - contains a non-null unique key; or - functionally determines every remaining child output column. An order-key sequence that comes entirely from one child remains eligible for pushdown. A mixed sequence without a uniqueness proof is kept above the join only. The change adds focused unit coverage for rejected non-unique prefixes and accepted complete, full-output, and functionally determining prefixes. It also adds result regressions for tied prefixes, mixed-side ordering, descending ordering, and offsets.
1 parent c4dee4b commit af525d5

7 files changed

Lines changed: 294 additions & 8 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/nereids/properties/DataTrait.java‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -73,8 +73,7 @@ public boolean isEmpty() {
7373
}
7474

7575
public boolean isDependent(Set<Slot> dominate, Set<Slot> dependency) {
76-
return fdDg.findValidFuncDeps(Sets.union(dependency, dominate))
77-
.isFuncDeps(dominate, dependency);
76+
return fdDg.isDependent(dominate, dependency);
7877
}
7978

8079
public boolean isUnique(Slot slot) {

‎fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDepsDG.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@
2424
import com.google.common.collect.ImmutableMap;
2525
import com.google.common.collect.ImmutableSet;
2626

27+
import java.util.ArrayDeque;
2728
import java.util.ArrayList;
2829
import java.util.HashMap;
2930
import java.util.HashSet;
@@ -97,6 +98,58 @@ public boolean isEmpty() {
9798
return dgItems.isEmpty();
9899
}
99100

101+
/**
102+
* Checks whether the determinant closure contains every dependency slot.
103+
*
104+
* <p>Nodes are indexed by each slot that they are still waiting for. When a dependency edge adds a slot to
105+
* the closure, only nodes waiting for that slot are revisited. Each node and edge is expanded at most once,
106+
* avoiding construction of the graph's full transitive FD relation.</p>
107+
*/
108+
public boolean isDependent(Set<Slot> determinants, Set<Slot> dependencies) {
109+
Set<Slot> closure = new HashSet<>(determinants);
110+
if (closure.containsAll(dependencies)) {
111+
return true;
112+
}
113+
114+
int[] missingSlotCounts = new int[dgItems.size()];
115+
Map<Slot, List<Integer>> waitingNodes = new HashMap<>();
116+
ArrayDeque<Integer> readyNodes = new ArrayDeque<>();
117+
for (DGItem item : dgItems) {
118+
for (Slot slot : item.slots) {
119+
if (!closure.contains(slot)) {
120+
missingSlotCounts[item.index]++;
121+
waitingNodes.computeIfAbsent(slot, key -> new ArrayList<>()).add(item.index);
122+
}
123+
}
124+
if (missingSlotCounts[item.index] == 0) {
125+
readyNodes.add(item.index);
126+
}
127+
}
128+
129+
while (!readyNodes.isEmpty()) {
130+
DGItem item = dgItems.get(readyNodes.remove());
131+
for (int childIndex : item.children) {
132+
for (Slot slot : dgItems.get(childIndex).slots) {
133+
if (closure.add(slot)) {
134+
List<Integer> nodes = waitingNodes.get(slot);
135+
if (nodes != null) {
136+
for (int nodeIndex : nodes) {
137+
missingSlotCounts[nodeIndex]--;
138+
if (missingSlotCounts[nodeIndex] == 0) {
139+
readyNodes.add(nodeIndex);
140+
}
141+
}
142+
}
143+
}
144+
}
145+
if (closure.containsAll(dependencies)) {
146+
return true;
147+
}
148+
}
149+
}
150+
return false;
151+
}
152+
100153
/**
101154
* Finds all functional dependencies that are applicable to a given set of valid slots.
102155
*/

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PushDownTopNDistinctThroughJoin.java‎

Lines changed: 36 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717

1818
package org.apache.doris.nereids.rules.rewrite;
1919

20+
import org.apache.doris.nereids.properties.DataTrait;
2021
import org.apache.doris.nereids.properties.OrderKey;
2122
import org.apache.doris.nereids.rules.Rule;
2223
import org.apache.doris.nereids.rules.RuleType;
@@ -33,6 +34,7 @@
3334

3435
import com.google.common.collect.ImmutableList;
3536

37+
import java.util.HashSet;
3638
import java.util.List;
3739
import java.util.Set;
3840
import java.util.stream.Collectors;
@@ -114,7 +116,7 @@ private Plan pushTopNThroughJoin(LogicalTopN<? extends Plan> topN, LogicalJoin<P
114116
return null;
115117
}
116118
List<OrderKey> pushedOrderKeys = getPushedOrderKeys(groupBySlots,
117-
join.left().getOutputSet(), topN.getOrderKeys());
119+
join.left(), topN.getOrderKeys());
118120
if (!pushedOrderKeys.isEmpty()) {
119121
LogicalTopN<Plan> left = topN.withLimitOrderKeyAndChild(
120122
childLimit, 0, pushedOrderKeys,
@@ -129,7 +131,7 @@ private Plan pushTopNThroughJoin(LogicalTopN<? extends Plan> topN, LogicalJoin<P
129131
return null;
130132
}
131133
List<OrderKey> pushedOrderKeys = getPushedOrderKeys(groupBySlots,
132-
join.right().getOutputSet(), topN.getOrderKeys());
134+
join.right(), topN.getOrderKeys());
133135
if (!pushedOrderKeys.isEmpty()) {
134136
LogicalTopN<Plan> right = topN.withLimitOrderKeyAndChild(
135137
childLimit, 0, pushedOrderKeys,
@@ -142,14 +144,14 @@ private Plan pushTopNThroughJoin(LogicalTopN<? extends Plan> topN, LogicalJoin<P
142144
Plan leftChild = join.left();
143145
Plan rightChild = join.right();
144146
List<OrderKey> leftPushedOrderKeys = getPushedOrderKeys(groupBySlots,
145-
join.left().getOutputSet(), topN.getOrderKeys());
147+
join.left(), topN.getOrderKeys());
146148
if (!(join.left() instanceof TopN) && !leftPushedOrderKeys.isEmpty()) {
147149
leftChild = topN.withLimitOrderKeyAndChild(
148150
childLimit, 0, leftPushedOrderKeys,
149151
PlanUtils.distinct(join.left()));
150152
}
151153
List<OrderKey> rightPushedOrderKeys = getPushedOrderKeys(groupBySlots,
152-
join.right().getOutputSet(), topN.getOrderKeys());
154+
join.right(), topN.getOrderKeys());
153155
if (!(join.right() instanceof TopN) && !rightPushedOrderKeys.isEmpty()) {
154156
rightChild = topN.withLimitOrderKeyAndChild(
155157
childLimit, 0, rightPushedOrderKeys,
@@ -170,8 +172,9 @@ private Plan pushTopNThroughJoin(LogicalTopN<? extends Plan> topN, LogicalJoin<P
170172
/**
171173
* return pushed order-keys. If top-n distinct cannot be pushed, return empty list.
172174
*/
173-
private List<OrderKey> getPushedOrderKeys(Set<Slot> groupBySlots, Set<Slot> joinChildSlot,
175+
private List<OrderKey> getPushedOrderKeys(Set<Slot> groupBySlots, Plan joinChild,
174176
List<OrderKey> orderKeys) {
177+
Set<Slot> joinChildSlot = joinChild.getOutputSet();
175178
// NOTICE: Currently, we have implemented strict restrictions to ensure that the distinct columns is
176179
// a superset of the output from the corresponding child of the join operator. In the future, we can relax
177180
// this restriction and only require that there is overlap between the output of the corresponding child of
@@ -197,6 +200,33 @@ private List<OrderKey> getPushedOrderKeys(Set<Slot> groupBySlots, Set<Slot> join
197200
notFound = true;
198201
}
199202
}
200-
return pushedOrderKeys.build();
203+
List<OrderKey> pushedOrderKeyList = pushedOrderKeys.build();
204+
if (pushedOrderKeyList.size() == orderKeys.size()
205+
|| isOrderKeyPrefixUniqueAfterDistinct(joinChild, pushedOrderKeyList)) {
206+
return pushedOrderKeyList;
207+
}
208+
return ImmutableList.of();
209+
}
210+
211+
/**
212+
* A partial order-key prefix is safe for a hard limit only when it uniquely orders the rows produced by
213+
* {@link PlanUtils#distinct(Plan)}. This is true when a leading part of the prefix either is already a
214+
* non-null unique key, covers every child output, or functionally determines every remaining child output.
215+
*/
216+
private boolean isOrderKeyPrefixUniqueAfterDistinct(Plan joinChild, List<OrderKey> orderKeyPrefix) {
217+
if (orderKeyPrefix.isEmpty()) {
218+
return false;
219+
}
220+
Set<Slot> childOutput = joinChild.getOutputSet();
221+
Set<Slot> prefixSlots = new HashSet<>();
222+
for (OrderKey orderKey : orderKeyPrefix) {
223+
prefixSlots.add((Slot) orderKey.getExpr());
224+
}
225+
if (prefixSlots.containsAll(childOutput)) {
226+
return true;
227+
}
228+
DataTrait childTrait = joinChild.getLogicalProperties().getTrait();
229+
return childTrait.isUniqueAndNotNull(prefixSlots)
230+
|| childTrait.isDependent(prefixSlots, childOutput);
201231
}
202232
}

‎fe/fe-core/src/test/java/org/apache/doris/nereids/properties/FuncDepsDGTest.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,21 @@ void testTrans() {
5252
Assertions.assertEquals(1, res.size());
5353
}
5454

55+
@Test
56+
void testDependencyClosure() {
57+
FuncDepsDG.Builder dg = new FuncDepsDG.Builder();
58+
Slot s1 = new SlotReference("s1", IntegerType.INSTANCE);
59+
Slot s2 = new SlotReference("s2", IntegerType.INSTANCE);
60+
Slot s3 = new SlotReference("s3", IntegerType.INSTANCE);
61+
Slot s4 = new SlotReference("s4", IntegerType.INSTANCE);
62+
dg.addDeps(Sets.newHashSet(s1), Sets.newHashSet(s2));
63+
dg.addDeps(Sets.newHashSet(s2, s3), Sets.newHashSet(s4));
64+
65+
FuncDepsDG funcDeps = dg.build();
66+
Assertions.assertTrue(funcDeps.isDependent(Sets.newHashSet(s1, s3), Sets.newHashSet(s2, s4)));
67+
Assertions.assertFalse(funcDeps.isDependent(Sets.newHashSet(s1), Sets.newHashSet(s4)));
68+
}
69+
5570
@Test
5671
void testCircle() {
5772
FuncDepsDG.Builder dg = new FuncDepsDG.Builder();
Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
package org.apache.doris.nereids.rules.rewrite;
19+
20+
import org.apache.doris.catalog.KeysType;
21+
import org.apache.doris.catalog.OlapTable;
22+
import org.apache.doris.common.Pair;
23+
import org.apache.doris.nereids.trees.expressions.Add;
24+
import org.apache.doris.nereids.trees.expressions.Alias;
25+
import org.apache.doris.nereids.trees.expressions.NamedExpression;
26+
import org.apache.doris.nereids.trees.expressions.literal.IntegerLiteral;
27+
import org.apache.doris.nereids.trees.plans.JoinType;
28+
import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
29+
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
30+
import org.apache.doris.nereids.util.LogicalPlanBuilder;
31+
import org.apache.doris.nereids.util.MemoPatternMatchSupported;
32+
import org.apache.doris.nereids.util.PlanChecker;
33+
import org.apache.doris.nereids.util.PlanConstructor;
34+
import org.apache.doris.qe.ConnectContext;
35+
36+
import com.google.common.collect.ImmutableList;
37+
import org.junit.jupiter.api.AfterEach;
38+
import org.junit.jupiter.api.BeforeEach;
39+
import org.junit.jupiter.api.Test;
40+
41+
class PushDownTopNDistinctThroughJoinTest implements MemoPatternMatchSupported {
42+
private static final PushDownTopNDistinctThroughJoin RULE = new PushDownTopNDistinctThroughJoin();
43+
private static final LogicalOlapScan LEFT_SCAN = PlanConstructor.newLogicalOlapScan(0, "t1", 0);
44+
private static final LogicalOlapScan RIGHT_SCAN = PlanConstructor.newLogicalOlapScan(1, "t2", 0);
45+
private ConnectContext connectContext;
46+
47+
@BeforeEach
48+
void setUp() {
49+
connectContext = new ConnectContext();
50+
connectContext.setThreadLocalInfo();
51+
}
52+
53+
@AfterEach
54+
void tearDown() {
55+
ConnectContext.remove();
56+
}
57+
58+
@Test
59+
void pushDirectShapeWhenAccumulatedPrefixDeterminesChildOutput() {
60+
NamedExpression id = LEFT_SCAN.getOutput().get(0);
61+
LogicalPlan left = new LogicalPlanBuilder(LEFT_SCAN)
62+
.projectExprs(ImmutableList.of(id, LEFT_SCAN.getOutput().get(1),
63+
new Alias(new Add(id, new IntegerLiteral(1)), "id_plus_one")))
64+
.build();
65+
LogicalPlan plan = new LogicalPlanBuilder(left)
66+
.join(RIGHT_SCAN, JoinType.LEFT_OUTER_JOIN, Pair.of(0, 0))
67+
.distinct(ImmutableList.of(0, 1, 2, 3, 4))
68+
.topN(10, 0, ImmutableList.of(0, 1, 3))
69+
.build();
70+
71+
PlanChecker.from(connectContext, plan)
72+
.applyTopDown(RULE)
73+
.matchesFromRoot(
74+
logicalTopN(
75+
logicalAggregate(
76+
logicalJoin(
77+
logicalTopN(logicalAggregate(logicalProject(logicalOlapScan())))
78+
.when(topN -> topN.getLimit() == 10),
79+
logicalOlapScan()
80+
)
81+
)
82+
)
83+
);
84+
}
85+
86+
@Test
87+
void pushAllSlotsProjectShapeForNonNullUniquePrefix() {
88+
LogicalOlapScan uniqueScan = newUniqueScan(2, "unique_not_null", false);
89+
LogicalPlan join = new LogicalPlanBuilder(uniqueScan)
90+
.join(RIGHT_SCAN, JoinType.LEFT_OUTER_JOIN, Pair.of(0, 0))
91+
.build();
92+
LogicalPlan plan = new LogicalPlanBuilder(join)
93+
.projectExprs(ImmutableList.<NamedExpression>builder().addAll(join.getOutput()).build())
94+
.distinct(ImmutableList.of(0, 1, 2, 3))
95+
.topN(10, 0, ImmutableList.of(0, 2))
96+
.build();
97+
98+
PlanChecker.from(connectContext, plan)
99+
.applyTopDown(RULE)
100+
.matchesFromRoot(
101+
logicalTopN(
102+
logicalProject(
103+
logicalAggregate(
104+
logicalJoin(
105+
logicalTopN(logicalAggregate(logicalOlapScan()))
106+
.when(topN -> topN.getLimit() == 10),
107+
logicalOlapScan()
108+
)
109+
)
110+
)
111+
)
112+
);
113+
}
114+
115+
@Test
116+
void rejectNullableUniquePrefix() {
117+
LogicalOlapScan nullableUniqueScan = newUniqueScan(3, "unique_nullable", true);
118+
LogicalPlan plan = new LogicalPlanBuilder(nullableUniqueScan)
119+
.join(RIGHT_SCAN, JoinType.LEFT_OUTER_JOIN, Pair.of(0, 0))
120+
.distinct(ImmutableList.of(0, 1, 2, 3))
121+
.topN(10, 0, ImmutableList.of(0, 2))
122+
.build();
123+
124+
PlanChecker.from(connectContext, plan)
125+
.applyTopDown(RULE)
126+
.matchesFromRoot(
127+
logicalTopN(
128+
logicalAggregate(
129+
logicalJoin(logicalOlapScan(), logicalOlapScan())
130+
)
131+
)
132+
);
133+
}
134+
135+
private LogicalOlapScan newUniqueScan(long tableId, String tableName, boolean keyNullable) {
136+
OlapTable table = PlanConstructor.newOlapTable(tableId, tableName, 0, KeysType.UNIQUE_KEYS);
137+
table.getFullSchema().get(0).setIsAllowNull(keyNullable);
138+
table.getFullSchema().get(1).setIsKey(false);
139+
return new LogicalOlapScan(PlanConstructor.getNextRelationId(), table, ImmutableList.of("db"));
140+
}
141+
}

‎regression-test/data/nereids_rules_p0/push_down_top_n/push_down_top_n_distinct_through_join.out‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,3 +45,10 @@ PhysicalResultSink
4545
6
4646
7
4747

48+
-- !partial_prefix_asc --
49+
1 0 10
50+
51+
-- !partial_prefix_desc_offset --
52+
6 0 60
53+
7 0 70
54+

‎regression-test/suites/nereids_rules_p0/push_down_top_n/push_down_top_n_distinct_through_join.groovy‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,4 +67,45 @@ suite("push_down_top_n_distinct_through_join") {
6767
qt_push_down_topn_through_join_data """
6868
select distinct * from (select t1.id from table_join t1 cross join table_join t2) t order by id limit 10;
6969
"""
70+
71+
sql "DROP TABLE IF EXISTS topn_distinct_left"
72+
sql "DROP TABLE IF EXISTS topn_distinct_right"
73+
sql """
74+
CREATE TABLE topn_distinct_left (
75+
k INT NOT NULL,
76+
id INT NOT NULL
77+
) DUPLICATE KEY(k, id)
78+
DISTRIBUTED BY HASH(id) BUCKETS 1
79+
PROPERTIES("replication_num" = "1")
80+
"""
81+
sql """
82+
CREATE TABLE topn_distinct_right (
83+
id INT NOT NULL,
84+
s INT NOT NULL
85+
) DUPLICATE KEY(id)
86+
DISTRIBUTED BY HASH(id) BUCKETS 1
87+
PROPERTIES("replication_num" = "1")
88+
"""
89+
sql """
90+
INSERT INTO topn_distinct_left VALUES
91+
(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)
92+
"""
93+
sql """
94+
INSERT INTO topn_distinct_right VALUES
95+
(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60), (7, 70), (8, 80)
96+
"""
97+
98+
order_qt_partial_prefix_asc """
99+
SELECT DISTINCT l.id, l.k, r.s
100+
FROM topn_distinct_left l LEFT JOIN topn_distinct_right r ON l.id = r.id
101+
ORDER BY l.k ASC, r.s ASC
102+
LIMIT 1
103+
"""
104+
105+
order_qt_partial_prefix_desc_offset """
106+
SELECT DISTINCT l.id, l.k, r.s
107+
FROM topn_distinct_left l LEFT JOIN topn_distinct_right r ON l.id = r.id
108+
ORDER BY l.k ASC, r.s DESC
109+
LIMIT 2 OFFSET 1
110+
"""
70111
}

0 commit comments

Comments
 (0)