Skip to content

Commit b41ec6a

Browse files
authored
[feature](Nereids): Pushdown LimitDistinct Through Join (#25113)
Push down limit-distinct through left/right outer join or cross join. such as select t1.c1 from t1 left join t2 on t1.c1 = t2.c1 order by t1.c1 limit 1;
1 parent 5a55e47 commit b41ec6a

10 files changed

Lines changed: 443 additions & 17 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -91,6 +91,7 @@
9191
import org.apache.doris.nereids.rules.rewrite.PushProjectThroughUnion;
9292
import org.apache.doris.nereids.rules.rewrite.PushdownFilterThroughProject;
9393
import org.apache.doris.nereids.rules.rewrite.PushdownLimit;
94+
import org.apache.doris.nereids.rules.rewrite.PushdownLimitDistinctThroughJoin;
9495
import org.apache.doris.nereids.rules.rewrite.PushdownTopNThroughJoin;
9596
import org.apache.doris.nereids.rules.rewrite.PushdownTopNThroughWindow;
9697
import org.apache.doris.nereids.rules.rewrite.ReorderJoin;
@@ -280,6 +281,7 @@ public class Rewriter extends AbstractBatchJobExecutor {
280281
new SplitLimit(),
281282
new PushdownLimit(),
282283
new PushdownTopNThroughJoin(),
284+
new PushdownLimitDistinctThroughJoin(),
283285
new PushdownTopNThroughWindow(),
284286
new CreatePartitionTopNFromWindow()
285287
)

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

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -252,6 +252,9 @@ public enum RuleType {
252252
PUSH_TOP_N_THROUGH_PROJECT_JOIN(RuleTypeClass.REWRITE),
253253
PUSH_TOP_N_THROUGH_PROJECT_WINDOW(RuleTypeClass.REWRITE),
254254
PUSH_TOP_N_THROUGH_WINDOW(RuleTypeClass.REWRITE),
255+
// limit distinct push down
256+
PUSH_LIMIT_DISTINCT_THROUGH_JOIN(RuleTypeClass.REWRITE),
257+
PUSH_LIMIT_DISTINCT_THROUGH_PROJECT_JOIN(RuleTypeClass.REWRITE),
255258
// adjust nullable
256259
ADJUST_NULLABLE(RuleTypeClass.REWRITE),
257260
ADJUST_CONJUNCTS_RETURN_TYPE(RuleTypeClass.REWRITE),
Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
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.nereids.rules.Rule;
21+
import org.apache.doris.nereids.rules.RuleType;
22+
import org.apache.doris.nereids.trees.expressions.Slot;
23+
import org.apache.doris.nereids.trees.plans.Plan;
24+
import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate;
25+
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
26+
import org.apache.doris.nereids.trees.plans.logical.LogicalLimit;
27+
import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
28+
29+
import com.google.common.collect.ImmutableList;
30+
31+
import java.util.List;
32+
import java.util.stream.Collectors;
33+
34+
/**
35+
* Same with PushdownLimit
36+
*/
37+
public class PushdownLimitDistinctThroughJoin implements RewriteRuleFactory {
38+
39+
@Override
40+
public List<Rule> buildRules() {
41+
return ImmutableList.of(
42+
// limit -> distinct -> join
43+
logicalLimit(logicalAggregate(logicalJoin())
44+
.when(LogicalAggregate::isDistinct))
45+
.then(limit -> {
46+
LogicalAggregate<LogicalJoin<Plan, Plan>> agg = limit.child();
47+
LogicalJoin<Plan, Plan> join = agg.child();
48+
49+
Plan newJoin = pushLimitThroughJoin(limit, join);
50+
if (newJoin == null || join.children().equals(newJoin.children())) {
51+
return null;
52+
}
53+
return limit.withChildren(agg.withChildren(newJoin));
54+
})
55+
.toRule(RuleType.PUSH_LIMIT_DISTINCT_THROUGH_JOIN),
56+
57+
// limit -> distinct -> project -> join
58+
logicalLimit(logicalAggregate(logicalProject(logicalJoin()).when(LogicalProject::isAllSlots))
59+
.when(LogicalAggregate::isDistinct))
60+
.then(limit -> {
61+
LogicalAggregate<LogicalProject<LogicalJoin<Plan, Plan>>> agg = limit.child();
62+
LogicalProject<LogicalJoin<Plan, Plan>> project = agg.child();
63+
LogicalJoin<Plan, Plan> join = project.child();
64+
65+
Plan newJoin = pushLimitThroughJoin(limit, join);
66+
if (newJoin == null || join.children().equals(newJoin.children())) {
67+
return null;
68+
}
69+
return limit.withChildren(agg.withChildren(project.withChildren(newJoin)));
70+
}).toRule(RuleType.PUSH_LIMIT_DISTINCT_THROUGH_JOIN)
71+
);
72+
}
73+
74+
private Plan pushLimitThroughJoin(LogicalLimit<?> limit, LogicalJoin<Plan, Plan> join) {
75+
LogicalAggregate<?> agg = (LogicalAggregate<?>) limit.child();
76+
List<Slot> groupBySlots = agg.getGroupByExpressions().stream()
77+
.flatMap(e -> e.getInputSlots().stream()).collect(Collectors.toList());
78+
switch (join.getJoinType()) {
79+
case LEFT_OUTER_JOIN:
80+
if (join.left().getOutputSet().containsAll(groupBySlots)
81+
&& join.left().getOutputSet().equals(agg.getOutputSet())) {
82+
return join.withChildren(limit.withLimitChild(limit.getLimit() + limit.getOffset(), 0,
83+
agg.withChildren(join.left())), join.right());
84+
}
85+
return null;
86+
case RIGHT_OUTER_JOIN:
87+
if (join.right().getOutputSet().containsAll(groupBySlots)
88+
&& join.right().getOutputSet().equals(agg.getOutputSet())) {
89+
return join.withChildren(join.left(), limit.withLimitChild(limit.getLimit() + limit.getOffset(), 0,
90+
agg.withChildren(join.right())));
91+
}
92+
return null;
93+
case CROSS_JOIN:
94+
if (join.left().getOutputSet().containsAll(groupBySlots)
95+
&& join.left().getOutputSet().equals(agg.getOutputSet())) {
96+
return join.withChildren(limit.withLimitChild(limit.getLimit() + limit.getOffset(), 0,
97+
agg.withChildren(join.left())), join.right());
98+
} else if (join.right().getOutputSet().containsAll(groupBySlots)
99+
&& join.right().getOutputSet().equals(agg.getOutputSet())) {
100+
return join.withChildren(join.left(), limit.withLimitChild(limit.getLimit() + limit.getOffset(), 0,
101+
agg.withChildren(join.right())));
102+
} else {
103+
return null;
104+
}
105+
default:
106+
return null;
107+
}
108+
}
109+
}

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

Lines changed: 19 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -25,12 +25,10 @@
2525
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
2626
import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
2727
import org.apache.doris.nereids.trees.plans.logical.LogicalTopN;
28-
import org.apache.doris.nereids.util.Utils;
2928

3029
import com.google.common.collect.ImmutableList;
3130

3231
import java.util.List;
33-
import java.util.Set;
3432
import java.util.stream.Collectors;
3533

3634
/**
@@ -75,28 +73,33 @@ public List<Rule> buildRules() {
7573
}
7674

7775
private Plan pushLimitThroughJoin(LogicalTopN<? extends Plan> topN, LogicalJoin<Plan, Plan> join) {
76+
List<Slot> orderbySlots = topN.getOrderKeys().stream().map(OrderKey::getExpr)
77+
.flatMap(e -> e.getInputSlots().stream()).collect(Collectors.toList());
7878
switch (join.getJoinType()) {
7979
case LEFT_OUTER_JOIN:
80-
Set<Slot> rightOutputSet = join.right().getOutputSet();
81-
if (topN.getOrderKeys().stream().map(OrderKey::getExpr)
82-
.anyMatch(e -> Utils.isIntersecting(rightOutputSet, e.getInputSlots()))) {
83-
return null;
80+
if (join.left().getOutputSet().containsAll(orderbySlots)) {
81+
return join.withChildren(
82+
topN.withLimitChild(topN.getLimit() + topN.getOffset(), 0, join.left()),
83+
join.right());
8484
}
85-
return join.withChildren(topN.withChildren(join.left()), join.right());
85+
return null;
8686
case RIGHT_OUTER_JOIN:
87-
Set<Slot> leftOutputSet = join.left().getOutputSet();
88-
if (topN.getOrderKeys().stream().map(OrderKey::getExpr)
89-
.anyMatch(e -> Utils.isIntersecting(leftOutputSet, e.getInputSlots()))) {
90-
return null;
87+
if (join.right().getOutputSet().containsAll(orderbySlots)) {
88+
return join.withChildren(
89+
join.left(),
90+
topN.withLimitChild(topN.getLimit() + topN.getOffset(), 0, join.right()));
9191
}
92-
return join.withChildren(join.left(), topN.withChildren(join.right()));
92+
return null;
9393
case CROSS_JOIN:
94-
List<Slot> orderbySlots = topN.getOrderKeys().stream().map(OrderKey::getExpr)
95-
.flatMap(e -> e.getInputSlots().stream()).collect(Collectors.toList());
94+
9695
if (join.left().getOutputSet().containsAll(orderbySlots)) {
97-
return join.withChildren(topN.withChildren(join.left()), join.right());
96+
return join.withChildren(
97+
topN.withLimitChild(topN.getLimit() + topN.getOffset(), 0, join.left()),
98+
join.right());
9899
} else if (join.right().getOutputSet().containsAll(orderbySlots)) {
99-
return join.withChildren(join.left(), topN.withChildren(join.right()));
100+
return join.withChildren(
101+
join.left(),
102+
topN.withLimitChild(topN.getLimit() + topN.getOffset(), 0, join.right()));
100103
} else {
101104
return null;
102105
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalAggregate.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -161,7 +161,8 @@ public Optional<LogicalRepeat<?>> getSourceRepeat() {
161161
}
162162

163163
public boolean isDistinct() {
164-
return outputExpressions.equals(groupByExpressions);
164+
return outputExpressions.stream().allMatch(e -> e instanceof Slot)
165+
&& groupByExpressions.stream().allMatch(e -> e instanceof Slot);
165166
}
166167

167168
public boolean isGenerated() {

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalLimit.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,12 @@ public List<? extends Expression> getExpressions() {
117117
return ImmutableList.of();
118118
}
119119

120+
public LogicalLimit<Plan> withLimitChild(long limit, long offset, Plan child) {
121+
Preconditions.checkArgument(children.size() == 1,
122+
"LogicalTopN should have 1 child, but input is %s", children.size());
123+
return new LogicalLimit<>(limit, offset, phase, child);
124+
}
125+
120126
@Override
121127
public Plan withGroupExpression(Optional<GroupExpression> groupExpression) {
122128
return new LogicalLimit<>(limit, offset, phase, groupExpression, Optional.of(getLogicalProperties()), child());

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,13 @@ public LogicalTopN<Plan> withOrderKeys(List<OrderKey> orderKeys) {
122122
Optional.empty(), Optional.of(getLogicalProperties()), child());
123123
}
124124

125+
public LogicalTopN<Plan> withLimitChild(long limit, long offset, Plan child) {
126+
Preconditions.checkArgument(children.size() == 1,
127+
"LogicalTopN should have 1 child, but input is %s", children.size());
128+
return new LogicalTopN<>(orderKeys, limit, offset,
129+
Optional.empty(), Optional.of(getLogicalProperties()), child);
130+
}
131+
125132
@Override
126133
public LogicalTopN<Plan> withChildren(List<Plan> children) {
127134
Preconditions.checkArgument(children.size() == 1,

0 commit comments

Comments
 (0)