github-actions[bot] commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3780780922
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java:
##########
@@ -462,6 +507,18 @@ private Pair<LogicalPlan, Optional<Expression>>
addApply(SubqueryExpr subquery,
} else {
throw new AnalysisException(String.format("Unsupported subquery :
%s", subquery.toString()));
}
+ boolean isMarkJoinSlotNotNull = false;
+ if (markJoinSlot.isPresent() &&
markSlotsInfo.containsKey(markJoinSlot.get())) {
+ Pair<Boolean, Boolean> info =
markSlotsInfo.get(markJoinSlot.get());
+ // 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
+ isMarkJoinSlotNotNull = info.first;
+ // Pair.second: the mark join can be directly eliminated into a
plain semi join
+ // that only outputs the matched rows, so drop the mark join slot
here
+ if (info.second) {
+ markJoinSlot = Optional.empty();
Review Comment:
[P1] Preserve null-aware NOT IN after marker removal
A marker-requiring NOT IN can keep stale correlation slots after its
correlation predicate folds away. For example, `ifnull(o.k not in (select s.v
from s where s.g = o.g or true), false)` records `o.g` during analysis, then
normalization removes the effective correlation. Pair.second clears the marker
here; `InApplyToJoin` builds only `o.k = s.v`, but still selects
`LEFT_ANTI_JOIN` because `apply.isCorrelated()` remains true. If nullable `s.v`
contains NULL, that ordinary anti join emits `o`, whereas NOT IN is NULL and
the `ifnull` predicate must reject it. Please base null-aware anti selection on
the effective correlation (or clear stale slots) and add a NULL-build
regression.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java:
##########
@@ -503,6 +560,267 @@ 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.
+ *
+ * extraEvaluationDomain extends the evaluation domain with expressions
that are not yet
+ * part of the plan but will be evaluated on the same rows later, e.g. the
generated
+ * assert_true(count(*) <= 1) that addApply synthesizes for a later
correlated scalar
+ * subquery; see collectGeneratedAssertionsOfLaterConjuncts.
+ *
+ * subqueryToMarkJoinSlot maps every subquery of the conjunct to its
(optional) mark slot,
+ * and currentConjunctSubqueryOrder lists them in the order
subqueryToApply stacks the
+ * applies (first = lowest). currentIndex is the conjunct being processed,
subqueryExprsList
+ * the subqueries of every conjunct, and relatedInfoList (null in the
filter path) the join
+ * side of every conjunct's apply. the evaluation domain is resolved PER
TARGET mark slot
+ * and only includes the subquery plans that are actually downstream of
the target: later
+ * applies on the filter chain or on the same join child, plus the higher
same-conjunct
+ * applies and their generated assertions; the target and already-lower
applies and
+ * opposite-side join applies are excluded; see
collectTargetEvaluationDomain.
+ */
+ private Pair<Expression, Map<MarkJoinSlotReference, Pair<Boolean,
Boolean>>> simplifyConjunctWithMarkJoinSlot(
+ Expression conjunct, Plan plan, CascadesContext cascadesContext,
+ int currentIndex,
+ List<Set<SubqueryExpr>> subqueryExprsList,
+ List<RelatedInfo> relatedInfoList,
+ Map<SubqueryExpr, Optional<MarkJoinSlotReference>>
subqueryToMarkJoinSlot,
+ List<SubqueryExpr> currentConjunctSubqueryOrder,
+ List<Expression> extraEvaluationDomain) {
+ ExpressionRewriteContext rewriteContext = new
ExpressionRewriteContext(plan, cascadesContext);
+ Map<MarkJoinSlotReference, Pair<Boolean, Boolean>> markSlotsInfo;
+ if (conjunct.containsType(MarkJoinSlotReference.class)) {
+ markSlotsInfo = ExpressionUtils.inferMarkSlotNotNullMap(conjunct,
rewriteContext,
+ target -> collectTargetEvaluationDomain(plan, target,
currentIndex, subqueryExprsList,
+ relatedInfoList, subqueryToMarkJoinSlot,
currentConjunctSubqueryOrder,
+ extraEvaluationDomain));
+ } 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 base evaluation domain of the mark slot inference: the
containing conjunct
+ * set of the filter/join (always in the domain, since every conjunct
expression is
+ * evaluated above all the stacked applies), plus the expressions inside
the subquery
+ * plans that are DOWNSTREAM of the target. only those downstream plans
can have their
+ * sensitive expressions skipped by the target's elimination: an earlier
filter apply is
+ * already below the target, and an opposite-side join apply is in an
independent subtree,
+ * so neither is affected and collecting them would only lose valid
eliminations.
+ */
+ private List<Expression> collectEvaluationDomain(Plan plan,
Collection<SubqueryExpr> downstreamSubqueries) {
+ 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 (SubqueryExpr subquery : downstreamSubqueries) {
+ collectPlanExpressions(subquery.getQueryPlan(),
subqueryPlanExpressions);
+ }
+ evaluationDomain.addAll(subqueryPlanExpressions);
+ return evaluationDomain;
+ }
+
+ private void collectPlanExpressions(Plan plan, List<Expression>
expressions) {
+ expressions.addAll(plan.getExpressions());
+ if (plan instanceof LogicalApply) {
+ // LogicalApply.getExpressions() exposes only the correlation
slots/filter and omits
+ // the runtime compareExpr and typeCoercionExpr, but the executed
apply (e.g.
+ // InApplyToJoin) reads compareExpr to build the run-time
equality, so a
+ // NoneMovableFunction/volatile there (such as a nested
`assert_true(x) IN (...)`
+ // compare expression) must be part of the sensitivity walk too
+ LogicalApply<?, ?> apply = (LogicalApply<?, ?>) plan;
+ apply.getCompareExpr().ifPresent(expressions::add);
+ apply.getTypeCoercionExpr().ifPresent(expressions::add);
+ }
+ for (Plan child : plan.children()) {
+ collectPlanExpressions(child, expressions);
+ }
+ }
+
+ /*
+ * whether addApply will synthesize the runtime assert_true(count(*) <= 1)
for the
+ * subquery: a correlated scalar subquery without a top-level scalar agg
that is not
+ * limit-one-eliminated. a top-level scalar agg returns at most one row
and a
+ * limit-one-eliminated subquery is guaranteed to produce at most one row,
so no check
+ * is generated for them. the check references a count slot that only
exists after
+ * addApply, so it is invisible to collectEvaluationDomain and a preceding
mark join
+ * whose elimination prunes the rows reaching the check must be fenced.
+ */
+ private static boolean isCorrelatedScalarNeedingRuntimeCheck(SubqueryExpr
subquery) {
+ if (!(subquery instanceof ScalarSubquery)) {
+ return false;
+ }
+ ScalarSubquery scalar = (ScalarSubquery) subquery;
+ return !scalar.getCorrelateSlots().isEmpty()
+ && !scalar.hasTopLevelScalarAgg()
+ && !scalar.limitOneIsEliminated();
+ }
+
+ /*
+ * the representative assert_true(count(*) <= 1) that addApply synthesizes
for a
+ * correlated scalar subquery whose output is used in the outer
expression: only the
+ * sensitive-function type matters for the inference fence, so a fresh
count slot is
+ * enough.
+ */
+ private static Expression generatedCorrelatedScalarAssertion() {
+ Slot countSlot = new Alias(new Count()).toSlot();
+ return new AssertTrue(
+ ExpressionUtils.or(new IsNull(countSlot),
+ new LessThanEqual(countSlot, new BigIntLiteral(1))),
+ new VarcharLiteral("correlate scalar subquery must return only
1 row"));
+ }
+
+ /*
+ * resolve the evaluation domain for ONE target mark slot. an eliminated
apply prunes
+ * rows BEFORE the applies built after it evaluate, so the domain of a
target must contain
+ * exactly the subquery plans that are DOWNSTREAM of it:
+ * - the higher same-conjunct applies (positions after the target in
+ * currentConjunctSubqueryOrder, first = lowest)
+ * - the later conjuncts on the same reachability: later applies on the
filter chain
+ * (relatedInfoList == null) or later applies on the same join child
+ * and must NOT contain the target's own plan, the already-lower applies,
or the
Review Comment:
[P1] Keep an empty higher EXISTS from erasing lower checks
The claim that already-lower Applies cannot be skipped fails for `nvl(o.x =
(select s.x from s) AND exists(select 1 where false), false)`: preorder puts
the scalar Apply below the EXISTS. The scalar lowers to `CrossJoin(o,
LogicalAssertNumRows(s))`, then dropping the higher EXISTS marker creates a
non-mark CROSS join with an empty right side. `EliminateEmptyRelation` replaces
that whole join with empty and deletes the lower cardinality check. With the
marker retained, its `!join.isMarkJoin()` guard preserves the subtree and the
multi-row scalar raises. Please fence this subtree-elimination case (or
preserve an evaluation barrier) and add an expected-error regression.
##########
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/EliminateMarkJoinTest.java:
##########
@@ -0,0 +1,137 @@
+// 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.rules.rewrite;
+
+import org.apache.doris.nereids.trees.plans.JoinType;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.MemoPatternMatchSupported;
+import org.apache.doris.nereids.util.PlanChecker;
+import org.apache.doris.utframe.TestWithFeService;
+
+import org.junit.jupiter.api.Test;
+
+class EliminateMarkJoinTest extends TestWithFeService implements
MemoPatternMatchSupported {
+
+ @Override
+ protected void runBeforeAll() throws Exception {
+ createDatabase("test");
+
+ connectContext.setDatabase("test");
+ // tables are empty in the ut env, keep the scans from collapsing to
empty relations
+
connectContext.getSessionVariable().setDisableNereidsRules("PRUNE_EMPTY_PARTITION");
+
+ createTable("CREATE TABLE t1 (id int not null, score int null)\n"
+ + "DISTRIBUTED BY HASH(id) BUCKETS 1\n"
+ + "PROPERTIES(\"replication_num\"=\"1\");");
+ createTable("CREATE TABLE t2 (id int not null)\n"
+ + "DISTRIBUTED BY HASH(id) BUCKETS 1\n"
+ + "PROPERTIES(\"replication_num\"=\"1\");");
+ createTable("CREATE TABLE t3 (id int not null, score int null)\n"
+ + "DISTRIBUTED BY HASH(id) BUCKETS 1\n"
+ + "PROPERTIES(\"replication_num\"=\"1\");");
+ }
+
+ @Test
+ void inSubqueryInJoinOnCondition() {
+ // the IN subquery sits in the join ON clause, so unnesting produces a
mark join;
+ // the mark slot ends up consumed by a bare filter conjunct and must
be eliminated
+ String sql = "select t1.id from t1 join t2 on t1.id = t2.id"
+ + " and t1.id in (select id from t3)";
+
+ PlanChecker.from(connectContext)
+ .analyze(sql)
+ .rewrite()
+ .nonMatch(logicalJoin().when(LogicalJoin::isMarkJoin))
+ .matches(logicalJoin().when(join ->
+ join.getJoinType() == JoinType.LEFT_SEMI_JOIN &&
!join.isMarkJoin()));
+ }
+
+ @Test
+ void inSubqueryInJoinOnConditionNullableColumn() {
+ // nullable compare column: the mark conjuncts may stay separate from
the hash
+ // conjuncts, the rule must fold them into the plain semi join as well
+ String sql = "select t1.id from t1 join t2 on t1.id = t2.id"
+ + " and t1.score in (select score from t3)";
+
+ PlanChecker.from(connectContext)
+ .analyze(sql)
+ .rewrite()
+ .nonMatch(logicalJoin().when(LogicalJoin::isMarkJoin))
+ .matches(logicalJoin().when(join ->
+ join.getJoinType() == JoinType.LEFT_SEMI_JOIN &&
!join.isMarkJoin()));
+ }
+
+ @Test
+ void markSlotProjectedToOutput() {
+ // the mark slot is the query output, not a filter conjunct: must keep
the mark join
+ String sql = "select t1.id, t1.id in (select id from t3) as flag from
t1";
+
+ PlanChecker.from(connectContext)
+ .analyze(sql)
+ .rewrite()
+ .matches(logicalJoin().when(LogicalJoin::isMarkJoin));
+ }
+
+ @Test
+ void markSlotInNullDistinguishingPredicate() {
+ // the consumer keeps rows whose mark is NULL, so three-valued mark
semantics is
+ // observable and the mark join must stay as it is
+ String sql = "select t1.id from t1"
+ + " where (t1.score in (select score from t3) and t1.id > 0)
is null";
+
+ PlanChecker.from(connectContext)
+ .analyze(sql)
+ .rewrite()
+ .matches(logicalJoin().when(LogicalJoin::isMarkJoin));
+
+ String bareIsNull = "select t1.id from t1"
+ + " where (t1.score in (select score from t3)) is null";
+
+ PlanChecker.from(connectContext)
+ .analyze(bareIsNull)
+ .rewrite()
+ .matches(logicalJoin().when(LogicalJoin::isMarkJoin));
+ }
+
+ @Test
+ void markSlotInDisjunction() {
+ // FALSE and NULL marks are distinguishable inside OR: must keep the
mark join
+ String sql = "select t1.id from t1 where t1.id = 1"
+ + " or t1.score in (select score from t3)";
+
+ PlanChecker.from(connectContext)
+ .analyze(sql)
+ .rewrite()
+ .matches(logicalJoin().when(LogicalJoin::isMarkJoin));
+ }
+
+ @Test
+ void notInSubqueryInJoinOnCondition() {
+ // NOT IN unnests to a null-aware anti join; the bare mark slot
conjunct is
+ // equivalent to the mark being true, so the mark slot is eliminated
and the
+ // result is a plain (non-mark) null-aware anti join
+ String sql = "select t1.id from t1 join t2 on t1.id = t2.id"
+ + " and t1.score not in (select score from t3)";
+
+ PlanChecker.from(connectContext)
+ .analyze(sql)
+ .rewrite()
+ .matches(logicalJoin().when(join -> !join.isMarkJoin()
+ && join.getJoinType() ==
JoinType.NULL_AWARE_LEFT_ANTI_JOIN));
+ }
Review Comment:
[P2] Cover clean EXISTS marker elimination
The new positive-elimination tests stop at `IN`/`NOT IN`, but this change
also sends marker-producing `EXISTS`/`NOT EXISTS` through Pair.second:
`visitExists` creates the marker, `addApply` can now drop it, and
`ExistsApplyToJoin` lowers the marker-free Apply. Both added EXISTS scenarios
instead require the marker to remain, so an EXISTS-only regression that
disables elimination leaves every changed oracle green. Please add clean
correlated and uncorrelated EXISTS/NOT EXISTS cases (including empty/non-empty
inputs) that assert the target marker is absent and verify the result.
--
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]
