github-actions[bot] commented on code in PR #66482: URL: https://github.com/apache/doris/pull/66482#discussion_r3764664509
########## fe/fe-core/src/test/java/org/apache/doris/nereids/util/InferMarkSlotNotNullMapTest.java: ########## @@ -0,0 +1,338 @@ +// 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.doris.nereids.util; + +import org.apache.doris.common.Pair; +import org.apache.doris.nereids.rules.expression.ExpressionRewriteTestHelper; +import org.apache.doris.nereids.trees.expressions.And; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.IsNull; +import org.apache.doris.nereids.trees.expressions.MarkJoinSlotReference; +import org.apache.doris.nereids.trees.expressions.Not; +import org.apache.doris.nereids.trees.expressions.Or; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.expressions.functions.scalar.AssertTrue; +import org.apache.doris.nereids.trees.expressions.functions.scalar.Nvl; +import org.apache.doris.nereids.trees.expressions.literal.BooleanLiteral; +import org.apache.doris.nereids.trees.expressions.literal.NullLiteral; +import org.apache.doris.nereids.trees.expressions.literal.VarcharLiteral; +import org.apache.doris.nereids.types.BooleanType; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Lists; +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.Test; + +import java.util.List; +import java.util.Map; + +/** + * InferMarkSlotNotNullMapTest. + */ +public class InferMarkSlotNotNullMapTest extends ExpressionRewriteTestHelper { + + @Test + public void testSingleMarkSlotAndOr() { + MarkJoinSlotReference markSlot1 = new MarkJoinSlotReference("markSlot1"); + + // pair.first is based on the simplified predicate (non-mark-slot children in And/Or + // are replaced by true/false): true when it taking false or null always evaluates + // to false or null; pair.second is based on the original predicate: true when it + // taking false or null always evaluates to false or null + assertMarkSlotPair(new And(BooleanLiteral.FALSE, markSlot1), markSlot1, true, true); + assertMarkSlotPair(new And(BooleanLiteral.TRUE, markSlot1), markSlot1, true, true); + assertMarkSlotPair(new And(NullLiteral.INSTANCE, markSlot1), markSlot1, true, true); + // or(true, markSlot1): after simplification the child true is replaced by false, so + // the simplified predicate or(false, markSlot1) taking false or null evaluates to + // false or null, making pair.first true; the original or(true, markSlot1) taking + // false evaluates to true, making pair.second false + assertMarkSlotPair(new Or(BooleanLiteral.TRUE, markSlot1), markSlot1, true, false); + assertMarkSlotPair(new Or(BooleanLiteral.FALSE, markSlot1), markSlot1, true, true); + assertMarkSlotPair(new Or(NullLiteral.INSTANCE, markSlot1), markSlot1, true, true); + } + + @Test + public void testSingleMarkSlotIsNullIsNotNull() { + MarkJoinSlotReference markSlot1 = new MarkJoinSlotReference("markSlot1"); + + // is null: taking false returns false while taking null returns true, which is + // neither false nor null, and taking true returns false, so both fields are false + assertMarkSlotPair(new IsNull(markSlot1), markSlot1, false, false); + // is not null: taking false returns true, which is neither false nor null, so + // pair.first is false; the original predicate taking false also evaluates to + // true, so pair.second is false too + assertMarkSlotPair(new Not(new IsNull(markSlot1)), markSlot1, false, false); + // markSlot1 and is not null(markSlot1): the predicate is equivalent to + // markSlot1 being true + assertMarkSlotPair(new And(markSlot1, new Not(new IsNull(markSlot1))), + markSlot1, true, true); + } + + @Test + public void testSingleMarkSlotNvl() { + MarkJoinSlotReference markSlot1 = new MarkJoinSlotReference("markSlot1"); + + // nvl(markSlot1, false) is equivalent to markSlot1 being true + assertMarkSlotPair(new Nvl(markSlot1, BooleanLiteral.FALSE), markSlot1, true, true); + // nvl(markSlot1, true): taking null returns true, which is neither false nor null, + // so both pair.first and pair.second are false + assertMarkSlotPair(new Nvl(markSlot1, BooleanLiteral.TRUE), markSlot1, false, false); + // nvl(markSlot1, null): taking null returns null, which is treated as same as false, + // and taking true returns true, so both fields are true + assertMarkSlotPair(new Nvl(markSlot1, NullLiteral.INSTANCE), markSlot1, true, true); + } + + @Test + public void testMultiMarkSlot() { + MarkJoinSlotReference markSlot1 = new MarkJoinSlotReference("markSlot1"); + MarkJoinSlotReference markSlot2 = new MarkJoinSlotReference("markSlot2"); + + // or(markSlot1, markSlot2): when the other mark slot is true, the target slot taking + // false or null evaluates to true, which is neither false nor null, so both + // pair.first and pair.second are false + assertMarkSlotPair(new Or(markSlot1, markSlot2), markSlot1, false, false); + assertMarkSlotPair(new Or(markSlot1, markSlot2), markSlot2, false, false); + // and(markSlot1, markSlot2): the target slot taking false or null always evaluates + // to false or null in both the simplified and the original predicate + assertMarkSlotPair(new And(markSlot1, markSlot2), markSlot1, true, true); + assertMarkSlotPair(new And(markSlot1, markSlot2), markSlot2, true, true); + + // and(or(markSlot1, markSlot2), false): after simplification the non-mark-slot child + // false is replaced by true, so the simplified predicate taking false can evaluate + // to true when the other mark slot is true, making pair.first false; the original + // predicate always evaluates to false or null, making pair.second true + assertMarkSlotPair(new And(new Or(markSlot1, markSlot2), BooleanLiteral.FALSE), + markSlot1, false, true); + assertMarkSlotPair(new And(new Or(markSlot1, markSlot2), BooleanLiteral.FALSE), + markSlot2, false, true); + + // markSlot1 taking false or null always evaluates to false or null in both the + // simplified and the original predicate, while markSlot2 taking false evaluates + // to true when markSlot1 is true, so for markSlot2 both pair.first and pair.second + // are false + Expression predicate = new And(new Nvl(markSlot1, BooleanLiteral.FALSE), + new Or(markSlot1, markSlot2)); + Map<MarkJoinSlotReference, Pair<Boolean, Boolean>> result = + ExpressionUtils.inferMarkSlotNotNullMap(predicate, context); + Assertions.assertEquals(2, result.size()); + Assertions.assertEquals(Pair.of(Boolean.TRUE, Boolean.TRUE), result.get(markSlot1)); + Assertions.assertEquals(Pair.of(Boolean.FALSE, Boolean.FALSE), result.get(markSlot2)); + } + + @Test + public void testLaterTupleAssignmentMatters() { Review Comment: [P2] Make the NULL base-3 digit mutation-sensitive These new continuation/carry cases are all decided by another mark becoming FALSE: codes 1, 3, and 9. Replacing `otherLiterals`' NULL entry with FALSE still leaves every committed oracle passing, so the third base-3 value remains untested after the earlier later-tuple request. A direct discriminator is `(M1 AND FALSE) OR IS NULL(M2)` for target M1: M2=TRUE/FALSE keeps the candidate pair apparently `(true,true)`, and only M2=NULL forces the correct `(false,false)`. Please add that oracle plus carry variants such as `(M1 AND FALSE) OR (M2 AND IS NULL(M3))` and the four-mark analogue, whose deciding NULL assignments occur after carries. ########## regression-test/suites/query_p0/subquery/subquery_unnesting.groovy: ########## @@ -145,4 +146,171 @@ suite ("subquery_unnesting") { FROM (SELECT 1 AS x) t WHERE 1 NOT IN (SELECT CAST(NULL AS INT)); """ + + // ===================================================================== + // mark join elimination in the join ON condition. + // + // inferMarkSlotNotNullMap returns a pair for each mark join slot: + // Pair.first : the null and false values of the mark slot are + // indistinguishable, so the mark slot can be treated as a + // non-nullable boolean (null is computed as false when + // producing the mark value). this never changes the number + // of output rows, so it's safe for all join types. + // Pair.second: the original mark join can be directly eliminated and + // turned into a plain semi join. a plain semi join only + // outputs the matched rows, while a mark join keeps all + // original rows plus the mark column, so eliminating the + // mark join is only safe for inner, cross and semi joins + // where dropping the unmatched rows is already part of the + // join semantics. + // + // take the query below as an example: + // select t1.* from t1 left join t2 on t1.k2 = t2.k3 + // and t1.k1 in (select t3.k1 from t3 where t1.k2 = t3.k2) + // for the outer join the mark join must be kept: the unmatched left rows + // (mark = false/null) must be preserved with null columns of t2, while a + // plain semi join would drop them. so the analyzed plan must keep + // isMarkJoin=true and only infer the non-nullable mark + // (isMarkJoinSlotNotNull=true). for inner/cross/semi join the unmatched + // rows are dropped anyway, so the mark join can be safely eliminated + // (isMarkJoin=false and the mark slot is replaced by the true literal). + // + // note: anti join also keeps the mark join for the null-aware semantics + // of NOT IN, but executing an anti join with a subquery in its ON + // condition is a pre-existing unsupported path in physical planning, so + // only the analyzed plan is checked here. asof join's ON clause only + // allows equal conjuncts, so a subquery can never appear in it and the + // asof branch in the code is defensive only. + // ===================================================================== + + // inner join: the mark join is eliminated (isMarkJoin=false, MarkJoinSlotReference=empty) + explain { + sql("""analyzed plan select t1.* from t1 inner join t2 on t1.k2 = t2.k3 + and t1.k1 in (select t3.k1 from t3 where t1.k2 = t3.k2) order by t1.k1, t1.k2;""") + contains("isMarkJoin=false") + contains("MarkJoinSlotReference=empty") + } + // semi join: the mark join is eliminated too + explain { + sql("""analyzed plan select t1.* from t1 left semi join t2 on t1.k2 = t2.k3 + and t1.k1 in (select t3.k1 from t3 where t1.k2 = t3.k2) order by t1.k1, t1.k2;""") + contains("isMarkJoin=false") + contains("MarkJoinSlotReference=empty") + } + // outer join: the mark join must be kept, and the mark slot's null/false + // equivalence (isMarkJoinSlotNotNull=true) is still inferred + explain { + sql("""analyzed plan select t1.* from t1 left join t2 on t1.k2 = t2.k3 + and t1.k1 in (select t3.k1 from t3 where t1.k2 = t3.k2) order by t1.k1, t1.k2;""") + contains("isMarkJoin=true") + contains("isMarkJoinSlotNotNull=true") + } + // anti join: the mark join must be kept for the null-aware semantics of NOT IN + explain { + sql("""analyzed plan select t1.* from t1 left anti join t2 on t1.k2 = t2.k3 + and t1.k1 not in (select t3.k1 from t3 where t1.k2 = t3.k2) order by t1.k1, t1.k2;""") + contains("isMarkJoin=true") + contains("isMarkJoinSlotNotNull=true") + } + + // result checks: the mark join elimination must not change the query results. + // (the outer join results with subquery in the ON condition are already + // covered by qt_select37 / qt_select43, the mark join is kept there) + // inner join with IN subquery in the ON condition (mark join eliminated) + qt_select66 """select t1.* from t1 inner join t2 on t1.k2 = t2.k3 and t1.k1 in (select t3.k1 from t3 where t1.k2 = t3.k2) order by t1.k1, t1.k2;""" + // inner join with NOT IN subquery in the ON condition (mark join eliminated) + qt_select67 """select t1.* from t1 inner join t2 on t1.k2 = t2.k3 and t1.k1 not in (select t3.k1 from t3 where t1.k2 = t3.k2) order by t1.k1, t1.k2;""" + // left semi join with IN subquery in the ON condition (mark join eliminated) + qt_select68 """select t1.* from t1 left semi join t2 on t1.k2 = t2.k3 and t1.k1 in (select t3.k1 from t3 where t1.k2 = t3.k2) order by t1.k1, t1.k2;""" + + // error-behavior regression: the mark join must NOT be eliminated when the filter + // contains assert_true (a NoneMovableFunction). although M = false and M = null both + // fold the predicate to false (the row-truth proof), eliminating the mark join changes + // which rows reach assert_true: the semi join prunes the unmatched rows before the + // filter, so assert_true is no longer evaluated on them and its error is suppressed. + // with the mark join kept, all rows reach the filter and assert_true throws on the + // unmatched guard = false rows. + // data: M = assert_t.k1 in (assert_s.k1 where assert_s.k2 = assert_t.k2), so only + // row (2,2) matches; guard = assert_t.k2 = 2 is false exactly on the unmatched rows + // (1,1) and (3,3) + sql "drop table if exists assert_t" + sql "drop table if exists assert_s" + sql """create table assert_t (k1 bigint, k2 bigint) DUPLICATE KEY(k1) + DISTRIBUTED BY HASH(k2) BUCKETS 1 PROPERTIES('replication_num'='1');""" + sql """create table assert_s (k1 bigint, k2 bigint) DUPLICATE KEY(k1) + DISTRIBUTED BY HASH(k2) BUCKETS 1 PROPERTIES('replication_num'='1');""" + sql """insert into assert_t values (1,1),(2,2),(3,3);""" + sql """insert into assert_s values (2,2);""" + test { + sql """select assert_t.k1 from assert_t + where ifnull( + ifnull(assert_t.k1 in (select assert_s.k1 from assert_s + where assert_s.k2 = assert_t.k2), false) + and assert_true(assert_t.k2 = 2, 'assert failed'), + false);""" + exception "assert failed" + } + + // error-behavior regressions for the "complete evaluation domain" fence: the mark join + // must not be eliminated when a NoneMovableFunction (assert_true) exists anywhere in the + // affected evaluation domain, even if it is NOT inside the mark conjunct itself. + sql "drop table if exists assert_u" + sql """create table assert_u (k1 bigint, k2 bigint) DUPLICATE KEY(k1) + DISTRIBUTED BY HASH(k2) BUCKETS 1 PROPERTIES('replication_num'='1');""" + sql """insert into assert_u values (1,1),(2,2),(3,3);""" + + // sibling conjunct: assert_true is a SIBLING conjunct of the eliminable mark conjunct. + // the mark conjunct is `k1 NOT IN (...)` = NOT M, which keeps the unmatched rows (1,1) + // and (3,3) and prunes the matched row (2,2); assert_true(guard) throws exactly on the + // kept unmatched rows. the mark conjunct alone infers pair.second = true, so the mark + // join would be eliminated into a semi join that only outputs the matched row and + // assert_true would never run on the unmatched rows. with the complete evaluation + // domain fence the mark join is kept, all rows reach the filter and assert_true throws + // on the unmatched guard = false rows. + test { + sql """select assert_t.k1 from assert_t Review Comment: [P2] Make this sibling-fence regression reach a mark Apply This bare `NOT IN` is itself a top-level `SubqueryExpr`, so `shouldOutputMarkJoinSlot` returns false and `visitInSubquery` replaces it with TRUE without creating a marker. The test therefore never exercises the new inference/domain fence. Its correlated non-mark `NOT IN` becomes a left anti join, which still emits the unmatched `(1,1)` and `(3,3)` rows where `assert_true(k2 = 2)` fails, so deleting the complete-domain fence leaves this test green. Please use a marker-requiring positive form such as `ifnull(k1 IN (...), false) AND assert_true(...)`: without the fence its semi join prunes the failing unmatched rows, while the retained mark Apply preserves the required error. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java: ########## @@ -503,6 +535,82 @@ private Pair<LogicalPlan, Optional<Expression>> addApply(SubqueryExpr subquery, return Pair.of(logicalProject, newCorrelatedOuterExpr); } + /** + * simplify the conjunct that contains mark join slots and infer the behavior of each + * mark join slot, return the rewritten conjunct together with the mark slots info. + * + * for each mark slot, the pair in the returned map has: + * Pair.first: whether the null and false values of the mark slot are indistinguishable, + * i.e. the mark slot can be treated as a non-nullable boolean. it only affects + * how the mark value is computed (treating null as false) and never changes the + * number of output rows, so it's safe for every join type and the filter. + * Pair.second: whether the original mark join can be directly eliminated and turned into a + * plain semi join. a plain semi join only outputs the matched rows, while a + * mark join keeps all original rows and adds a mark column, so eliminating the + * mark join is only safe when discarding the unmatched rows is already part of + * the containing join's semantics (inner, cross and semi joins). + * + * when Pair.second is true, the mark slot is replaced by the true literal in the returned + * conjunct, and the caller can drop the mark join slot to turn the mark join into a plain + * semi join. + */ + private Pair<Expression, Map<MarkJoinSlotReference, Pair<Boolean, Boolean>>> simplifyConjunctWithMarkJoinSlot( + Expression conjunct, Plan plan, CascadesContext cascadesContext) { + ExpressionRewriteContext rewriteContext = new ExpressionRewriteContext(plan, cascadesContext); + Map<MarkJoinSlotReference, Pair<Boolean, Boolean>> markSlotsInfo; + if (conjunct.containsType(MarkJoinSlotReference.class)) { + markSlotsInfo = ExpressionUtils.inferMarkSlotNotNullMap( + conjunct, rewriteContext, collectEvaluationDomain(plan)); + } else { + markSlotsInfo = Maps.newHashMap(); + } + Map<MarkJoinSlotReference, BooleanLiteral> replaceMap = Maps.newHashMap(); + for (Map.Entry<MarkJoinSlotReference, Pair<Boolean, Boolean>> entry : markSlotsInfo.entrySet()) { + if (entry.getValue().second) { + replaceMap.put(entry.getKey(), BooleanLiteral.TRUE); + } + } + if (!replaceMap.isEmpty()) { + conjunct = ExpressionUtils.replace(conjunct, replaceMap); + } + return Pair.of(conjunct, markSlotsInfo); + } + + /* + * collect the complete evaluation domain of the mark slot inference: the containing + * conjunct set of the filter/join, plus all the expressions inside the correlated + * subquery plans. a sensitive expression (e.g. assert_true) does not need to be inside + * the current conjunct: it may be a sibling conjunct of the same filter/join, or live in + * a later subquery plan whose input rows are pruned together with the outer rows when an + * earlier mark join is eliminated. pair.second is only safe when every such expression + * is still evaluated on the same rows after the elimination, so they all belong to the + * evaluation domain that the pair.second proof must be validated against. + */ + private List<Expression> collectEvaluationDomain(Plan plan) { + List<Expression> evaluationDomain = new ArrayList<>(); + if (plan instanceof LogicalFilter) { + evaluationDomain.addAll(((LogicalFilter<? extends Plan>) plan).getConjuncts()); + } else if (plan instanceof LogicalJoin) { + evaluationDomain.addAll(((LogicalJoin<?, ?>) plan).getExpressions()); + } + List<Expression> subqueryPlanExpressions = new ArrayList<>(); + for (Expression expression : evaluationDomain) { + Set<SubqueryExpr> subqueries = expression.collect(SubqueryExpr.class::isInstance); + for (SubqueryExpr subquery : subqueries) { + collectPlanExpressions(subquery.getQueryPlan(), subqueryPlanExpressions); Review Comment: [P1] Fence elimination across generated correlated-scalar assertions This collector only sees expressions already present in the original filter and subquery plans, but a later `addApply` synthesizes the correlated-scalar `Count`/`AssertTrue(count <= 1)` after collection. For source-ordered `ifnull(o.k IN (...), false) AND o.x = (SELECT u.x ... WHERE u.g = o.g)`, Pair.second drops the first marker and that Apply becomes a left semi join before the scalar Apply is added: ```text Filter(TRUE, o.x = any_value(u.x)) Project(..., assert_true(count <= 1)) ScalarApply(correlate o.g) LeftSemiJoin(o.k = i.k AND o.g = i.g) Scan(o) Scan(i) ``` With outer rows `(1,10,7)` and `(2,20,9)`, IN side `(1,10)`, and scalar side `(10,7),(20,9),(20,10)`, the semi join removes the only group with two scalar rows and suppresses `correlate scalar subquery must return only 1 row`. The retained-mark plan sends that row to the generated `AssertTrue` and raises. This is distinct from the existing later-subquery thread: that sensitive expression already exists in an original subquery plan, whereas this assertion is synthesized only after this traversal. Please fence a preceding Apply when a later correlated scalar needs this generated check (or build/collect the check before deciding Pair.second) and add the expected-error regression. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
