github-actions[bot] commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3775118211
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java:
##########
@@ -503,6 +560,257 @@ 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());
Review Comment:
[P1] Include nested Apply runtime fields in the sensitivity walk
A downstream query plan can still contain this reduced tree after nested
analysis:
```text
Higher EXISTS Apply
Project
Filter(TRUE)
Nested IN Apply(compareExpr=assert_true(...))
U V
```
`collectPlanExpressions` reaches the nested Apply, but
`LogicalApply.getExpressions()` exposes only correlation slots/filter and omits
`compareExpr` and `typeCoercionExpr`. The bare IN occurrence has already become
TRUE in its filter, while `InApplyToJoin` later reads `compareExpr` to build
the executed equality. Consequently an earlier target marker can be removed as
if this downstream domain were clean, and its plain semi join can prune the bad
outer row before the nested `assert_true`/volatile comparison runs. Please
inventory all runtime Apply fields (at least both omitted expressions), or use
an exhaustive evaluation-expression visitor, and add a nested-IN expected-error
regression. This is distinct from the prior reachability comment: the correct
downstream plan is reached here, but its executed expression is missing.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -680,72 +689,262 @@ public static boolean hasNullLiteral(List<Expression>
children) {
}
/**
- * canInferNotNullForMarkSlot
+ * infer the null and false behavior of each mark join slot in the
predicate.
+ * the predicate is first simplified by
TrySimplifyPredicateWithMarkJoinSlot, which
+ * replaces the conjuncts without any mark slot in And with true and in Or
with false,
+ * then both the original predicate and the simplified predicate are
evaluated.
+ * return a map from mark join slot to a pair:
+ * Pair.first: whether the simplified predicate taking false or null always
+ * evaluates to a value that is either false or null, i.e. the
+ * target mark slot's null value can be replaced by false
+ * Pair.second: whether the original predicate taking false or null always
+ * evaluates to a value that is either false or null, i.e. the
+ * false and null values of the target mark slot are
+ * indistinguishable in the original predicate
*/
- public static boolean canInferNotNullForMarkSlot(Expression predicate,
ExpressionRewriteContext ctx) {
- /*
- * assume predicate is from LogicalFilter
- * the idea is replacing each mark join slot with null and false
literal then run FoldConstant rule
- * if the evaluate result are:
- * 1. all true
- * 2. all null and false (in logicalFilter, we discard both null and
false values)
- * the mark slot can be non-nullable boolean
- * and in semi join, we can safely change the mark conjunct to hash
conjunct
- */
- ImmutableList<Literal> literals =
ImmutableList.of(NullLiteral.BOOLEAN_INSTANCE, BooleanLiteral.FALSE);
+ public static Map<MarkJoinSlotReference, Pair<Boolean, Boolean>>
inferMarkSlotNotNullMap(
+ Expression predicate, ExpressionRewriteContext ctx) {
+ // the evaluation domain defaults to the predicate itself for callers
that only
+ // have the single conjunct at hand
+ return inferMarkSlotNotNullMap(predicate, ctx,
ImmutableList.of(predicate));
+ }
+
+ /**
+ * infer the null and false behavior of the mark slots in the given
predicate
+ * the evaluationDomain is the complete set of expressions that are
evaluated together
+ * with the predicate: 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 predicate, it may
be a sibling
+ * conjunct or live in a later subquery plan whose input rows are pruned
when the mark
+ * join is eliminated, so pair.second must be validated against the whole
evaluation
+ * domain. the same domain is used for every target mark slot here.
+ */
+ public static Map<MarkJoinSlotReference, Pair<Boolean, Boolean>>
inferMarkSlotNotNullMap(
+ Expression predicate, ExpressionRewriteContext ctx,
Collection<Expression> evaluationDomain) {
+ return inferMarkSlotNotNullMap(predicate, ctx, ignored ->
evaluationDomain);
+ }
+
+ /**
+ * same as inferMarkSlotNotNullMap(predicate, ctx, Collection), but the
evaluation domain
+ * is resolved PER TARGET MARK SLOT through the provider. when a conjunct
contains several
+ * subqueries, subqueryToApply stacks their applies, and eliminating a
mark join only
+ * prunes the rows below the applies built after it: the target's own and
already-lower
+ * applies are evaluated identically or before the target, while the
subsequent (higher)
+ * same-conjunct applies and their generated assertions are evaluated
above it and CAN be
+ * suppressed by the elimination. the provider lets the caller give each
target exactly the
+ * domain that can observe the elimination.
+ */
+ public static Map<MarkJoinSlotReference, Pair<Boolean, Boolean>>
inferMarkSlotNotNullMap(
+ Expression predicate, ExpressionRewriteContext ctx,
+ Function<MarkJoinSlotReference, Collection<Expression>>
evaluationDomainProvider) {
+ Expression simplifiedPredicate =
TrySimplifyPredicateWithMarkJoinSlot.INSTANCE.rewrite(predicate, ctx);
+ Map<MarkJoinSlotReference, Pair<Boolean, Boolean>> result =
Maps.newLinkedHashMap();
List<MarkJoinSlotReference> markJoinSlotReferenceList = new
ArrayList<>(
(predicate.collect(MarkJoinSlotReference.class::isInstance)));
int markSlotSize = markJoinSlotReferenceList.size();
- int maxMarkSlotCount = 4;
// if the conjunct has mark slot, and maximum 4 mark slots(for
performance)
- if (markSlotSize > 0 && markSlotSize <= maxMarkSlotCount) {
- Map<Expression, Expression> replaceMap = Maps.newHashMap();
- boolean meetTrue = false;
- boolean meetNullOrFalse = false;
+ if (markSlotSize > 0 && markSlotSize <= MAX_MARK_SLOT_COUNT) {
+ // predicateSensitive is per-conjunct (the same predicate for
every target); the
+ // evaluation-domain sensitivity is per-target and resolved
through the provider
+ boolean predicateSensitive =
containsNoneMovableOrVolatile(ImmutableList.of(predicate));
+ for (int targetIdx = 0; targetIdx < markSlotSize; ++targetIdx) {
+ MarkJoinSlotReference target =
markJoinSlotReferenceList.get(targetIdx);
+ boolean evaluationDomainSensitive =
+
containsNoneMovableOrVolatile(evaluationDomainProvider.apply(target));
+ result.put(target, inferMarkSlotNotNullForTargetMarkSlot(
+ predicate, simplifiedPredicate,
markJoinSlotReferenceList, targetIdx, ctx,
+ predicateSensitive,
evaluationDomainSensitive));
+ }
+ }
+ return result;
+ }
+
+ /**
+ * infer the null and false behavior of the target mark slot
+ * replace the target slot with false and null, and replace other mark
slots with
+ * true, false and null, and evaluate both the original predicate and the
simplified
+ * predicate for every combination of other mark slots' values
+ * return a pair:
+ * Pair.first: whether the simplified predicate taking false or null
always evaluates to
+ * a value that is either false or null
+ * Pair.second: whether the original predicate taking false or null always
evaluates to
+ * a value that is either false or null
+ */
+ private static Pair<Boolean, Boolean>
inferMarkSlotNotNullForTargetMarkSlot(Expression predicate,
+ Expression simplifiedPredicate,
+ List<MarkJoinSlotReference> markJoinSlotReferenceList, int
targetIdx, ExpressionRewriteContext ctx,
+ boolean predicateSensitive, boolean evaluationDomainSensitive) {
+ int markSlotSize = markJoinSlotReferenceList.size();
+ /*
+ * target slot enumerates false and null, other mark slots enumerate
true, false and null
+ * markSlotSize = 1 -> otherMarkSlotCount = 0 -> loopCount = 1
+ * markSlotSize = 2 -> otherMarkSlotCount = 1 -> loopCount = 3
+ * markSlotSize = 3 -> otherMarkSlotCount = 2 -> loopCount = 9
+ * markSlotSize = 4 -> otherMarkSlotCount = 3 -> loopCount = 27
+ */
+ int otherMarkSlotCount = markSlotSize - 1;
+ int loopCount = 1;
+ for (int i = 0; i < otherMarkSlotCount; ++i) {
+ loopCount *= 3;
+ }
+ ImmutableList<Literal> otherLiterals = ImmutableList.of(
+ BooleanLiteral.TRUE, BooleanLiteral.FALSE,
NullLiteral.BOOLEAN_INSTANCE);
+ /*
+ * pair.second is a row-truth proof: it only proves that the filter
treats the target
+ * mark slot taking false or null identically. dropping the mark join
(turning the
+ * Apply into a plain semi join) also changes which rows reach the
other expressions
+ * in the filter. for a NoneMovableFunction (e.g. assert_true) or a
volatile
+ * expression in the evaluation domain, the semi join prunes the
unmatched rows before
+ * the filter, so these expressions may no longer be evaluated on the
same rows, which
+ * changes error behavior or results. fence pair.second to false so
that the mark join
+ * is never eliminated across such expressions.
+ *
+ * pair.first is only fenced by the CURRENT predicate's sensitive
expressions. treating
+ * the mark slot as non-nullable (isMarkJoinSlotNotNull) turns a null
mark value into
+ * false, and a sensitive expression inside the current predicate can
observe that
+ * null-vs-false distinction: the vectorized AND must evaluate its
right operand for a
+ * nullable null input (NULL AND x depends on x), but can return early
when the left
+ * operand is an all-false non-null column, so converting the mark's
null to false may
+ * skip evaluating e.g. assert_true and suppress its error. a
sensitive expression in a
+ * sibling conjunct or a later subquery plan cannot observe this
distinction: pair.first
+ * keeps the apply (all rows are preserved) and those expressions do
not reference the
+ * generated marker, so the complete evaluation domain fences
pair.second only.
+ *
+ * this split also fixes an over-conservative fence: before it, any
sensitive expression
+ * in the complete evaluation domain fenced BOTH fields, so a join ON
condition such as
+ * `t1.k in (select c from t3) and assert_true(t1.k > 0, 'bad')`
(clean current
+ * predicate, sensitive sibling) lost isMarkJoinSlotNotNull: the
nullable IN equality
+ * stayed in the markConjuncts of a standalone mark join and, with no
hash conjunct,
+ * JoinUtils.couldShuffle returned false, forcing the join to
broadcast. keeping
+ * pair.first (isMarkJoinSlotNotNull=true) moves the equality into the
hash conjuncts,
+ * which preserves the shuffle alternative.
+ *
+ * the sensitive expression is not necessarily 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 also pruned when the mark join is eliminated. those
expressions are
+ * invisible to the single-conjunct inference, so pair.second is
validated against the
+ * complete evaluation domain (the containing conjunct set and all
affected subquery
+ * plans) instead of the current conjunct alone.
+ *
+ * the current conjunct's OWN subquery plans are deliberately not part
of the
+ * evaluation domain: the apply and the resulting semi/anti join both
evaluate the
+ * inner plan (per outer row for correlated, once for uncorrelated),
only the output
+ * row set differs, so a sensitive expression inside them cannot be
affected by the
+ * elimination. the caller (collectEvaluationDomain) excludes them
when building the
+ * domain.
+ *
+ * scope caveat: the fence covers exactly the classes detected by
+ * containsNoneMovableOrVolatile, i.e. NoneMovableFunction
(assert_true is the only
+ * implementation in Doris today) and volatile expressions. other
error-raising
+ * expressions in the evaluation domain are deliberately NOT fenced:
e.g. with
+ * enable_strict_division_by_zero or on cast errors, a sibling
conjunct such as
+ * `ifnull(k in (...), false) and 1/(x) > 0` raises in the retained
plan (the division
+ * is evaluated on the rows the filter later discards) but is silently
skipped after
+ * the elimination prunes those rows inside the semi join, so the
query returns a
+ * result instead of failing. the same holds for the current conjunct
when pair.first
+ * turns a null mark into false. only NoneMovableFunction/volatile
error semantics are
+ * guaranteed to survive an elimination; other error behaviors are
best-effort.
+ */
+ if (predicateSensitive) {
+ // a sensitive expression inside the current predicate can observe
the marker's
+ // null-vs-false distinction, so both fields are fenced and the
base-3 enumeration
+ // below would be discarded entirely; skip it to avoid the
exponential
+ // N * 3^(N-1) * 4 fold cost for every such conjunct
+ return Pair.of(false, false);
+ }
+ Map<Expression, Expression> replaceMap = Maps.newHashMap();
+ boolean sameResultForFalseAndNull = true;
+ boolean simplifiedForFalseAndNull = true;
+ for (int i = 0; i < loopCount; ++i) {
+ if (!sameResultForFalseAndNull && !simplifiedForFalseAndNull) {
+ // both fields are monotonic: they start true and only become
false, never
+ // back to true, so once both are false no remaining tuple can
change the
+ // result and the rest of the enumeration can be skipped
+ break;
+ }
+ replaceMap.clear();
/*
- * markSlotSize = 1 -> loopCount = 2 ---- 0, 1
- * markSlotSize = 2 -> loopCount = 4 ---- 00, 01, 10, 11
- * markSlotSize = 3 -> loopCount = 8 ---- 000, 001, 010, 011, 100,
101, 110, 111
- * markSlotSize = 4 -> loopCount = 16 ---- 0000, 0001, ... 1111
+ * replace other mark slots with true, false or null
+ * otherLiterals.get(0) -> BooleanLiteral.TRUE
+ * otherLiterals.get(1) -> BooleanLiteral.FALSE
+ * otherLiterals.get(2) -> NullLiteral(BooleanType.INSTANCE)
*/
- int loopCount = 1 << markSlotSize;
- for (int i = 0; i < loopCount; ++i) {
- replaceMap.clear();
+ int code = i;
+ for (int j = 0; j < markSlotSize; ++j) {
+ if (j == targetIdx) {
+ continue;
+ }
+ replaceMap.put(markJoinSlotReferenceList.get(j),
otherLiterals.get(code % 3));
+ code /= 3;
+ }
+ // a field is monotonic, so once it is false its folds are only
used to flip it
+ // from true to false and can be skipped for the rest of the
enumeration
+ if (sameResultForFalseAndNull) {
+ // evaluate the original predicate with target slot taking
false
+ replaceMap.put(markJoinSlotReferenceList.get(targetIdx),
BooleanLiteral.FALSE);
+ Expression evalResultWithFalse = FoldConstantRule.evaluate(
+ ExpressionUtils.replace(predicate, replaceMap), ctx);
+ // evaluate the original predicate with target slot taking null
+ replaceMap.put(markJoinSlotReferenceList.get(targetIdx),
NullLiteral.BOOLEAN_INSTANCE);
+ Expression evalResultWithNull = FoldConstantRule.evaluate(
+ ExpressionUtils.replace(predicate, replaceMap), ctx);
/*
- * replace each mark slot with null or false
- * literals.get(0) -> NullLiteral(BooleanType.INSTANCE)
- * literals.get(1) -> BooleanLiteral.FALSE
+ * if the original predicate taking false or null evaluates to
a value other than
+ * false or null, the false and null values of the target mark
slot are
+ * distinguishable in the original predicate
*/
- for (int j = 0; j < markSlotSize; ++j) {
- replaceMap.put(markJoinSlotReferenceList.get(j),
literals.get((i >> j) & 1));
+ if (!isFalseOrNull(evalResultWithFalse) ||
!isFalseOrNull(evalResultWithNull)) {
+ sameResultForFalseAndNull = false;
}
- Expression evalResult = FoldConstantRule.evaluate(
- ExpressionUtils.replace(predicate, replaceMap),
- ctx);
-
- if (evalResult.equals(BooleanLiteral.TRUE)) {
- if (meetNullOrFalse) {
- return false;
- } else {
- meetTrue = true;
- }
- } else if ((isNullOrFalse(evalResult))) {
- if (meetTrue) {
- return false;
- } else {
- meetNullOrFalse = true;
- }
- } else {
- return false;
+ }
+ if (simplifiedForFalseAndNull) {
+ // evaluate the simplified predicate with target slot taking
false
+ replaceMap.put(markJoinSlotReferenceList.get(targetIdx),
BooleanLiteral.FALSE);
+ Expression simplifiedEvalResultWithFalse =
FoldConstantRule.evaluate(
+ ExpressionUtils.replace(simplifiedPredicate,
replaceMap), ctx);
+ // evaluate the simplified predicate with target slot taking
null
+ replaceMap.put(markJoinSlotReferenceList.get(targetIdx),
NullLiteral.BOOLEAN_INSTANCE);
+ Expression simplifiedEvalResultWithNull =
FoldConstantRule.evaluate(
+ ExpressionUtils.replace(simplifiedPredicate,
replaceMap), ctx);
+ /*
+ * if the simplified predicate taking false or null evaluates
to a value other than
+ * false or null, the target slot's null value cannot be
replaced by false
+ */
+ if (!isFalseOrNull(simplifiedEvalResultWithFalse)
+ || !isFalseOrNull(simplifiedEvalResultWithNull)) {
+ simplifiedForFalseAndNull = false;
}
}
- return true;
+ }
+ // complete evaluation-domain fence: a sensitive expression anywhere
in the evaluation
+ // domain must fence pair.second (the elimination prunes the unmatched
rows before the
+ // sibling conjuncts and later subquery expressions), while pair.first
is left as
+ // inferred (the apply is kept and sibling/later expressions cannot
observe the marker's
+ // null-vs-false mapping)
+ if (evaluationDomainSensitive) {
+ sameResultForFalseAndNull = false;
+ }
+ return Pair.of(simplifiedForFalseAndNull, sameResultForFalseAndNull);
+ }
+
+ /*
+ * whether any expression in the evaluation domain is sensitive for mark
join elimination:
+ * a NoneMovableFunction (assert_true is the only implementation today) or
a volatile
+ * expression. other error-raising expressions (strict division-by-zero,
cast errors) are
+ * deliberately not covered here, so only the NoneMovableFunction/volatile
error semantics
+ * are guaranteed to survive a mark join elimination.
+ */
+ private static boolean
containsNoneMovableOrVolatile(Collection<Expression> expressions) {
+ for (Expression expression : expressions) {
+ if (expression.containsVolatileExpression() ||
expression.containsType(NoneMovableFunction.class)) {
Review Comment:
[P2] Add mutation-sensitive coverage for the volatile fence
This is an independent safety arm, but every new sensitivity oracle uses
`AssertTrue`/`NoneMovableFunction`; none constructs a `Random`, `Uuid`, or
other `VolatileExpression`. Deleting only
`expression.containsVolatileExpression() ||` therefore leaves all changed tests
green while reopening both paths this branch protects: a volatile current
predicate can retain unsafe Pair.first/Pair.second, and a volatile
target-specific downstream domain can retain unsafe Pair.second. Please add
focused unit cases using an actual volatile Nereids expression: the
current-predicate case should produce `(false, false)`, while a clean target
with a volatile supplied domain should produce `(true, false)`.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java:
##########
@@ -503,6 +560,257 @@ 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());
+ 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
+ * applies on the opposite physical join child (evaluated identically /
before /
+ * independently, so the elimination cannot skip their sensitive
expressions). the higher
+ * same-conjunct output-used correlated scalars additionally contribute
their generated
+ * assert_true(count(*) <= 1), and the later conjuncts contribute
extraEvaluationDomain.
+ */
+ private List<Expression> collectTargetEvaluationDomain(Plan plan,
+ MarkJoinSlotReference target,
+ int currentIndex,
+ List<Set<SubqueryExpr>> subqueryExprsList,
+ List<RelatedInfo> relatedInfoList,
+ Map<SubqueryExpr, Optional<MarkJoinSlotReference>>
subqueryToMarkJoinSlot,
+ List<SubqueryExpr> currentConjunctSubqueryOrder,
+ List<Expression> extraEvaluationDomain) {
+ // the position of the target's subquery in the apply-stacking order
+ int targetPos = -1;
+ for (int k = 0; k < currentConjunctSubqueryOrder.size(); ++k) {
+ Optional<MarkJoinSlotReference> markSlot =
+
subqueryToMarkJoinSlot.get(currentConjunctSubqueryOrder.get(k));
+ if (markSlot.isPresent() && markSlot.get().equals(target)) {
+ targetPos = k;
+ break;
+ }
+ }
+ // the subquery plans that are actually downstream of the target
+ Set<SubqueryExpr> downstreamSubqueries = new HashSet<>();
+ // higher same-conjunct applies (built after the target, so above it)
+ for (int k = targetPos + 1; k < currentConjunctSubqueryOrder.size();
++k) {
Review Comment:
[P1] Account for post-lowering transposes of lower evaluations
The "already-lower Apply" premise holds only for the initial stack. A
reduced input is:
```text
Project
IN Apply M2 (target)
Project(all A slots, M1)
EXISTS Apply M1 (condition includes assert_true)
A B
C
```
Pair.second can drop M2 because the EXISTS plan precedes `targetPos`;
lowering then creates a plain `SemiIN` above the mark `SemiExists`. The
registered `SemiJoinSemiJoinTransposeProject` accepts this `(LEFT_SEMI,
LEFT_SEMI)` all-slot shape and can produce:
```text
MarkSemiExists(assert_true)
Project
SemiIN(A, C)
B
```
An A row absent from C is now removed before `assert_true`, suppressing its
required error; retaining M2 keeps a mark join and preserves that row. The same
root issue exists for the non-mark-only semi/aggregate transpose family, which
can move an eliminated target below a sensitive aggregate. Please fence all
legal post-lowering crossings (or preserve an evaluation barrier), rather than
relying only on Apply position, and add expected-error coverage for these
transpose shapes. This is distinct from the prior over-fence comment: that
comment assumes the initial lower position remains fixed, while these
registered rules invalidate that assumption after marker removal.
--
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]
