Skip to content

Commit 17b1108

Browse files
authored
[fix](nereids)support uncorrelated subquery in join condition (#26672)
sql select * from t1 a join t1 b on b.id in (select 1) and a.id = b.id; will report an error. This pr support uncorrelated subquery in join condition to fix it
1 parent a78e0f8 commit 17b1108

5 files changed

Lines changed: 183 additions & 29 deletions

File tree

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

Lines changed: 95 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,6 @@
2323
import org.apache.doris.nereids.rules.RuleType;
2424
import org.apache.doris.nereids.trees.expressions.Alias;
2525
import org.apache.doris.nereids.trees.expressions.BinaryOperator;
26-
import org.apache.doris.nereids.trees.expressions.ComparisonPredicate;
2726
import org.apache.doris.nereids.trees.expressions.Exists;
2827
import org.apache.doris.nereids.trees.expressions.Expression;
2928
import org.apache.doris.nereids.trees.expressions.InSubquery;
@@ -45,6 +44,7 @@
4544
import org.apache.doris.nereids.trees.plans.logical.LogicalOneRowRelation;
4645
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
4746
import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
47+
import org.apache.doris.nereids.trees.plans.logical.LogicalSort;
4848

4949
import com.google.common.collect.ImmutableList;
5050
import com.google.common.collect.ImmutableSet;
@@ -180,16 +180,23 @@ public List<Rule> buildRules() {
180180
Collectors.toList()));
181181
List<Expression> subqueryConjuncts = joinConjuncts.get(true);
182182
if (subqueryConjuncts == null || subqueryConjuncts.stream()
183-
.anyMatch(expr -> !isValidSubqueryConjunct(expr, join.left()))) {
183+
.anyMatch(expr -> !isValidSubqueryConjunct(expr))) {
184+
return join;
185+
}
186+
187+
List<RelatedInfo> relatedInfoList = collectRelatedInfo(
188+
subqueryConjuncts, join.left(), join.right());
189+
if (relatedInfoList.stream().anyMatch(info -> info == RelatedInfo.UnSupported)) {
184190
return join;
185191
}
186192

187193
ImmutableList<Set<SubqueryExpr>> subqueryExprsList = subqueryConjuncts.stream()
188194
.<Set<SubqueryExpr>>map(e -> e.collect(SubqueryExpr.class::isInstance))
189195
.collect(ImmutableList.toImmutableList());
190196
ImmutableList.Builder<Expression> newConjuncts = new ImmutableList.Builder<>();
191-
LogicalPlan applyPlan = null;
197+
LogicalPlan applyPlan;
192198
LogicalPlan leftChildPlan = (LogicalPlan) join.left();
199+
LogicalPlan rightChildPlan = (LogicalPlan) join.right();
193200

194201
// Subquery traversal with the conjunct of and as the granularity.
195202
for (int i = 0; i < subqueryExprsList.size(); ++i) {
@@ -207,44 +214,97 @@ public List<Rule> buildRules() {
207214

208215
applyPlan = subqueryToApply(
209216
subqueryExprs.stream().collect(ImmutableList.toImmutableList()),
210-
leftChildPlan, context.getSubqueryToMarkJoinSlot(),
217+
relatedInfoList.get(i) == RelatedInfo.RelatedToLeft ? leftChildPlan : rightChildPlan,
218+
context.getSubqueryToMarkJoinSlot(),
211219
ctx.cascadesContext, Optional.of(conjunct), false);
212-
leftChildPlan = applyPlan;
220+
if (relatedInfoList.get(i) == RelatedInfo.RelatedToLeft) {
221+
leftChildPlan = applyPlan;
222+
} else {
223+
rightChildPlan = applyPlan;
224+
}
213225
newConjuncts.add(conjunct);
214226
}
215227
List<Expression> simpleConjuncts = joinConjuncts.get(false);
216228
if (simpleConjuncts != null) {
217229
newConjuncts.addAll(simpleConjuncts);
218230
}
219231
Plan newJoin = join.withConjunctsChildren(join.getHashJoinConjuncts(),
220-
newConjuncts.build(), applyPlan, join.right());
232+
newConjuncts.build(), leftChildPlan, rightChildPlan);
221233
return newJoin;
222234
}))
223235
);
224236
}
225237

226-
private static boolean isValidSubqueryConjunct(Expression expression, Plan leftChild) {
227-
// the subquery must be uncorrelated subquery or only correlated to the left child
228-
// currently only support the following 4 simple scenarios
229-
// 1. col ComparisonPredicate subquery
230-
// 2. col in (subquery)
231-
// 3. exists (subquery)
232-
// 4. col1 ComparisonPredicate subquery or xxx (no more subquery)
233-
List<Slot> slots = leftChild.getOutput();
234-
if (expression instanceof ComparisonPredicate && expression.child(1) instanceof ScalarSubquery) {
235-
ScalarSubquery subquery = (ScalarSubquery) expression.child(1);
236-
return slots.containsAll(subquery.getCorrelateSlots());
237-
} else if (expression instanceof InSubquery) {
238-
return slots.containsAll(((InSubquery) expression).getCorrelateSlots());
239-
} else if (expression instanceof Exists) {
240-
return slots.containsAll(((Exists) expression).getCorrelateSlots());
241-
} else {
238+
private static boolean isValidSubqueryConjunct(Expression expression) {
239+
// only support 1 subquery expr in the expression
240+
// don't support expression like subquery1 or subquery2
241+
return expression.collectToList(SubqueryExpr.class::isInstance).size() == 1;
242+
}
243+
244+
private enum RelatedInfo {
245+
// both subquery and its output don't related to any child. like (select sum(t.a) from t) > 1
246+
Unrelated,
247+
// either subquery or its output only related to left child. like bellow:
248+
// tableLeft.a in (select t.a from t)
249+
// 3 in (select t.b from t where t.a = tableLeft.a)
250+
// tableLeft.a > (select sum(t.a) from t where tableLeft.b = t.b)
251+
RelatedToLeft,
252+
// like above, but related to right child
253+
RelatedToRight,
254+
// subquery related to both left and child is not supported:
255+
// tableLeft.a > (select sum(t.a) from t where t.b = tableRight.b)
256+
UnSupported
257+
}
258+
259+
private ImmutableList<RelatedInfo> collectRelatedInfo(List<Expression> subqueryConjuncts,
260+
Plan leftChild, Plan rightChild) {
261+
int size = subqueryConjuncts.size();
262+
ImmutableList.Builder<RelatedInfo> correlatedInfoList = new ImmutableList.Builder<>();
263+
Set<Slot> leftOutputSlots = leftChild.getOutputSet();
264+
Set<Slot> rightOutputSlots = rightChild.getOutputSet();
265+
for (int i = 0; i < size; ++i) {
266+
Expression expression = subqueryConjuncts.get(i);
242267
List<SubqueryExpr> subqueryExprs = expression.collectToList(SubqueryExpr.class::isInstance);
268+
RelatedInfo relatedInfo = RelatedInfo.UnSupported;
243269
if (subqueryExprs.size() == 1) {
244-
return slots.containsAll(subqueryExprs.get(0).getCorrelateSlots());
270+
SubqueryExpr subqueryExpr = subqueryExprs.get(0);
271+
List<Slot> correlatedSlots = subqueryExpr.getCorrelateSlots();
272+
if (subqueryExpr instanceof ScalarSubquery) {
273+
Set<Slot> inputSlots = expression.getInputSlots();
274+
if (correlatedSlots.isEmpty() && inputSlots.isEmpty()) {
275+
relatedInfo = RelatedInfo.Unrelated;
276+
} else if (leftOutputSlots.containsAll(inputSlots)
277+
&& leftOutputSlots.containsAll(correlatedSlots)) {
278+
relatedInfo = RelatedInfo.RelatedToLeft;
279+
} else if (rightOutputSlots.containsAll(inputSlots)
280+
&& rightOutputSlots.containsAll(correlatedSlots)) {
281+
relatedInfo = RelatedInfo.RelatedToRight;
282+
}
283+
} else if (subqueryExpr instanceof InSubquery) {
284+
InSubquery inSubquery = (InSubquery) subqueryExpr;
285+
Set<Slot> compareSlots = inSubquery.getCompareExpr().getInputSlots();
286+
if (compareSlots.isEmpty()) {
287+
relatedInfo = RelatedInfo.UnSupported;
288+
} else if (leftOutputSlots.containsAll(compareSlots)
289+
&& leftOutputSlots.containsAll(correlatedSlots)) {
290+
relatedInfo = RelatedInfo.RelatedToLeft;
291+
} else if (rightOutputSlots.containsAll(compareSlots)
292+
&& rightOutputSlots.containsAll(correlatedSlots)) {
293+
relatedInfo = RelatedInfo.RelatedToRight;
294+
}
295+
} else if (subqueryExpr instanceof Exists) {
296+
if (correlatedSlots.isEmpty()) {
297+
relatedInfo = RelatedInfo.Unrelated;
298+
} else if (leftOutputSlots.containsAll(correlatedSlots)) {
299+
relatedInfo = RelatedInfo.RelatedToLeft;
300+
} else if (rightOutputSlots.containsAll(correlatedSlots)) {
301+
relatedInfo = RelatedInfo.RelatedToRight;
302+
}
303+
}
245304
}
305+
correlatedInfoList.add(relatedInfo);
246306
}
247-
return false;
307+
return correlatedInfoList.build();
248308
}
249309

250310
private LogicalPlan subqueryToApply(List<SubqueryExpr> subqueryExprs, LogicalPlan childPlan,
@@ -270,10 +330,17 @@ private LogicalPlan subqueryToApply(List<SubqueryExpr> subqueryExprs, LogicalPla
270330
private boolean nonMarkJoinExistsWithAgg(SubqueryExpr exists,
271331
Map<SubqueryExpr, Optional<MarkJoinSlotReference>> subqueryToMarkJoinSlot) {
272332
return exists instanceof Exists
273-
&& exists.getQueryPlan()
274-
.anyMatch(planTreeNode -> planTreeNode instanceof LogicalAggregate
275-
&& ((LogicalAggregate<?>) planTreeNode).getGroupByExpressions().isEmpty())
276-
&& !subqueryToMarkJoinSlot.get(exists).isPresent();
333+
&& !subqueryToMarkJoinSlot.get(exists).isPresent()
334+
&& hasTopLevelAggWithoutGroupBy(exists.getQueryPlan());
335+
}
336+
337+
private boolean hasTopLevelAggWithoutGroupBy(Plan plan) {
338+
if (plan instanceof LogicalAggregate) {
339+
return ((LogicalAggregate) plan).getGroupByExpressions().isEmpty();
340+
} else if (plan instanceof LogicalProject || plan instanceof LogicalSort) {
341+
return hasTopLevelAggWithoutGroupBy(plan.child(0));
342+
}
343+
return false;
277344
}
278345

279346
private LogicalPlan addApply(SubqueryExpr subquery, LogicalPlan childPlan,

‎regression-test/data/nereids_syntax_p0/sub_query_correlated.out‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -486,3 +486,6 @@ true
486486
-- !cir_5218_exists_ok_6 --
487487
0
488488

489+
-- !doris_7643 --
490+
3 3
491+

‎regression-test/suites/nereids_p0/subquery/test_subquery.groovy‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,62 @@ suite("test_subquery") {
6565
select * from nereids_test_query_db.baseall where k1 = (select k1 from nereids_test_query_db.baseall order by k1 desc limit 1)
6666
"""
6767

68+
sql """DROP TABLE IF EXISTS table_1000_undef_undef"""
69+
sql """DROP TABLE IF EXISTS table_1000_undef_undef2"""
70+
sql """CREATE TABLE `table_1000_undef_undef` (
71+
`pk` int(11) NULL,
72+
`col_bigint_undef_signed` bigint(20) NULL,
73+
`col_bigint_undef_signed2` bigint(20) NULL
74+
) ENGINE=OLAP
75+
DUPLICATE KEY(`pk`, `col_bigint_undef_signed`, `col_bigint_undef_signed2`)
76+
COMMENT 'OLAP'
77+
DISTRIBUTED BY HASH(`pk`) BUCKETS 10
78+
PROPERTIES (
79+
"replication_allocation" = "tag.location.default: 1",
80+
"is_being_synced" = "false",
81+
"storage_format" = "V2",
82+
"light_schema_change" = "true",
83+
"disable_auto_compaction" = "false",
84+
"enable_single_replica_compaction" = "false"
85+
); """
86+
87+
sql """ CREATE TABLE `table_1000_undef_undef2` (
88+
`pk` int(11) NULL,
89+
`col_bigint_undef_signed` bigint(20) NULL,
90+
`col_bigint_undef_signed2` bigint(20) NULL
91+
) ENGINE=OLAP
92+
DUPLICATE KEY(`pk`, `col_bigint_undef_signed`, `col_bigint_undef_signed2`)
93+
COMMENT 'OLAP'
94+
DISTRIBUTED BY HASH(`pk`) BUCKETS 10
95+
PROPERTIES (
96+
"replication_allocation" = "tag.location.default: 1",
97+
"is_being_synced" = "false",
98+
"storage_format" = "V2",
99+
"light_schema_change" = "true",
100+
"disable_auto_compaction" = "false",
101+
"enable_single_replica_compaction" = "false"
102+
);"""
103+
explain {
104+
sql """
105+
SELECT `col_bigint_undef_signed` '00:39:36' , `col_bigint_undef_signed` '11:19:45', `col_bigint_undef_signed` '11:55:37', `col_bigint_undef_signed2` '19:01:23'
106+
FROM table_1000_undef_undef2
107+
WHERE EXISTS
108+
(SELECT `col_bigint_undef_signed` '17:38:13' , `col_bigint_undef_signed2` '17:36:21'
109+
FROM table_1000_undef_undef2
110+
WHERE `col_bigint_undef_signed2` NOT IN
111+
(SELECT `col_bigint_undef_signed`
112+
FROM table_1000_undef_undef2
113+
WHERE `col_bigint_undef_signed2` <
114+
(SELECT AVG(`col_bigint_undef_signed`)
115+
FROM table_1000_undef_undef2
116+
WHERE `col_bigint_undef_signed2` < 2)) ) ;
117+
"""
118+
contains("VAGGREGATE")
119+
}
120+
121+
sql """DROP TABLE IF EXISTS table_1000_undef_undef"""
122+
sql """DROP TABLE IF EXISTS table_1000_undef_undef2"""
123+
68124
sql """drop table if exists test_one_row_relation;"""
69125
sql """
70126
CREATE TABLE `test_one_row_relation` (

‎regression-test/suites/nereids_syntax_p0/sub_query_correlated.groovy‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -648,6 +648,34 @@ suite ("sub_query_correlated") {
648648
exception "Unsupported correlated subquery with grouping and/or aggregation";
649649
}
650650

651+
qt_doris_7643 """
652+
SELECT sub_query_correlated_subquery6.*
653+
FROM sub_query_correlated_subquery6
654+
JOIN sub_query_correlated_subquery7
655+
ON sub_query_correlated_subquery6.k2 = sub_query_correlated_subquery7.k3
656+
AND EXISTS
657+
(SELECT sub_query_correlated_subquery8.k1
658+
FROM sub_query_correlated_subquery8 )
659+
AND sub_query_correlated_subquery6.k2 IN
660+
(SELECT sub_query_correlated_subquery8.k2
661+
FROM sub_query_correlated_subquery8 )
662+
AND sub_query_correlated_subquery6.k1 IN
663+
(SELECT sub_query_correlated_subquery8.k2
664+
FROM sub_query_correlated_subquery8
665+
WHERE sub_query_correlated_subquery6.k2 = sub_query_correlated_subquery8.k2 )
666+
AND sub_query_correlated_subquery7.k3 IN
667+
(SELECT sub_query_correlated_subquery8.k1
668+
FROM sub_query_correlated_subquery8 )
669+
AND 10 >
670+
(SELECT min(sub_query_correlated_subquery8.k2)
671+
FROM sub_query_correlated_subquery8 )
672+
AND sub_query_correlated_subquery7.k3 IN
673+
(SELECT sub_query_correlated_subquery8.k2
674+
FROM sub_query_correlated_subquery8
675+
WHERE sub_query_correlated_subquery7.v1 = sub_query_correlated_subquery8.k2 )
676+
ORDER BY sub_query_correlated_subquery6.k1, sub_query_correlated_subquery6.k2;
677+
"""
678+
651679
// order_qt_doris_6937_2 """
652680
// select * from sub_query_correlated_subquery1 where sub_query_correlated_subquery1.k1 not in (select sub_query_correlated_subquery3.k3 from sub_query_correlated_subquery3 where sub_query_correlated_subquery3.v2 > sub_query_correlated_subquery1.k2) or k1 < 10 order by k1, k2;
653681
// """

‎regression-test/suites/query_p0/join/test_join.groovy‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1107,7 +1107,7 @@ suite("test_join", "query,p0") {
11071107
qt_join_on_predicate7"""SELECT t2.k1,t2.k2,t3.k1,t3.k2 FROM baseall t2 LEFT JOIN test t3 ON t2.k2=t3.k2 WHERE t2.k1 = 4 OR (t2.k1 > 4 AND t3.k1 IS NULL) order by 1, 2, 3, 4"""
11081108

11091109
test {
1110-
sql "select a.k1 from baseall a join test b on b.k2 in (select 49) and a.k1 = b.k1 order by k1;"
1110+
sql "select /*+ SET_VAR(enable_nereids_planner=false) */ a.k1 from baseall a join test b on b.k2 in (select 49) and a.k1 = b.k1 order by k1;"
11111111
exception "Not support OnClause contain Subquery"
11121112
}
11131113

0 commit comments

Comments
 (0)