morrySnow commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3765894910
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -680,72 +685,183 @@ 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.
+ */
+ public static Map<MarkJoinSlotReference, Pair<Boolean, Boolean>>
inferMarkSlotNotNullMap(
+ Expression predicate, ExpressionRewriteContext ctx,
Collection<Expression> evaluationDomain) {
+ 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) {
+ for (int targetIdx = 0; targetIdx < markSlotSize; ++targetIdx) {
+ result.put(markJoinSlotReferenceList.get(targetIdx),
+ inferMarkSlotNotNullForTargetMarkSlot(
+ predicate, simplifiedPredicate,
markJoinSlotReferenceList, targetIdx, ctx,
+ evaluationDomain));
+ }
+ }
+ 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,
+ Collection<Expression> evaluationDomain) {
+ 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);
+ Map<Expression, Expression> replaceMap = Maps.newHashMap();
+ boolean sameResultForFalseAndNull = true;
+ boolean simplifiedForFalseAndNull = true;
+ for (int i = 0; i < loopCount; ++i) {
+ 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();
- /*
- * replace each mark slot with null or false
- * literals.get(0) -> NullLiteral(BooleanType.INSTANCE)
- * literals.get(1) -> BooleanLiteral.FALSE
- */
- for (int j = 0; j < markSlotSize; ++j) {
- replaceMap.put(markJoinSlotReferenceList.get(j),
literals.get((i >> j) & 1));
+ int code = i;
+ for (int j = 0; j < markSlotSize; ++j) {
+ if (j == targetIdx) {
+ continue;
}
- Expression evalResult = FoldConstantRule.evaluate(
- ExpressionUtils.replace(predicate, replaceMap),
- ctx);
+ replaceMap.put(markJoinSlotReferenceList.get(j),
otherLiterals.get(code % 3));
+ code /= 3;
+ }
+ // 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 simplified predicate with target slot taking false
+ Expression simplifiedEvalResultWithFalse =
FoldConstantRule.evaluate(
+ ExpressionUtils.replace(simplifiedPredicate, 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);
+ // evaluate the simplified predicate with target slot taking null
+ Expression simplifiedEvalResultWithNull =
FoldConstantRule.evaluate(
+ ExpressionUtils.replace(simplifiedPredicate, replaceMap),
ctx);
+ /*
+ * 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
+ */
+ if (!isFalseOrNull(evalResultWithFalse) ||
!isFalseOrNull(evalResultWithNull)) {
+ sameResultForFalseAndNull = false;
+ }
- 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 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;
+ }
+
+ if (!sameResultForFalseAndNull && !simplifiedForFalseAndNull) {
+ break;
+ }
+ }
+ /*
Review Comment:
Scope caveat: the fence only covers NoneMovableFunction (AssertTrue is the
only implementation in Doris today) and volatile expressions. Other
error-raising expressions in the same evaluation domain are not fenced: with
strict division-by-zero enabled (`enable_strict_division_by_zero`) or on cast
errors, a sibling conjunct such as `ifnull(k in (...), false) and 1/(x) > 0`
raises an error in the original plan (the division is evaluated on the rows the
filter discards) but is silently skipped after the elimination prunes those
rows inside the semi join — the query then returns a result instead of failing.
The same applies to the current conjunct when Pair.first replaces a null mark
by false. If the intent is to preserve error behavior strictly, the fence
should cover this class too; otherwise it is worth documenting that only
NoneMovableFunction/volatile semantics are guaranteed.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java:
##########
@@ -503,6 +537,137 @@ 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.
+ */
+ private Pair<Expression, Map<MarkJoinSlotReference, Pair<Boolean,
Boolean>>> simplifyConjunctWithMarkJoinSlot(
+ Expression conjunct, Plan plan, CascadesContext cascadesContext,
+ List<Expression> extraEvaluationDomain) {
+ ExpressionRewriteContext rewriteContext = new
ExpressionRewriteContext(plan, cascadesContext);
+ Map<MarkJoinSlotReference, Pair<Boolean, Boolean>> markSlotsInfo;
+ if (conjunct.containsType(MarkJoinSlotReference.class)) {
+ List<Expression> evaluationDomain = collectEvaluationDomain(plan);
+ evaluationDomain.addAll(extraEvaluationDomain);
+ markSlotsInfo = ExpressionUtils.inferMarkSlotNotNullMap(conjunct,
rewriteContext, evaluationDomain);
+ } 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.
a generated
+ * assert_true(count(*) <= 1) for a later correlated scalar subquery is
not visible here
+ * (it is synthesized by addApply after the collection), so the callers
add it separately
+ * via collectGeneratedAssertionsOfLaterConjuncts.
+ */
+ 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);
+ }
+ }
+ 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();
+ }
+
+ /*
+ * collect a representative of the runtime assert_true(count(*) <= 1) that
addApply
+ * will synthesize for every correlated scalar subquery in the conjuncts
after
+ * currentIndex: those applies are built above the current conjunct's
apply, so
+ * eliminating the current conjunct's mark join would prune the rows that
reach the
+ * generated assertion and suppress its error. only the sensitive-function
type
+ * matters for the inference fence, so a representative assertion with a
fresh count
+ * slot is enough to fence the elimination.
+ */
+ private List<Expression> collectGeneratedAssertionsOfLaterConjuncts(
Review Comment:
`collectGeneratedAssertionsOfLaterConjuncts` over-fences in two cases,
losing valid eliminations:
1. It fences all later conjuncts regardless of which side their apply is
built on. In the join path the applies of later conjuncts on the opposite side
of the join are independent subtrees — eliminating the current mark join does
not change the rows reaching them — but they are fenced anyway. (In the filter
path all applies are stacked on one chain, so fencing later conjuncts there is
correct.)
2. `isCorrelatedScalarNeedingRuntimeCheck` does not check
`needAddScalarSubqueryOutputToProjects`
(`isScalarSubqueryOutputUsedInOuterScope`). addApply only synthesizes the
`assert_true(count(*) <= 1)` when the scalar's output is actually used in the
outer expression — e.g. a correlated scalar subquery nested inside another
subquery has its output used inside the inner plan, not in the current
conjunct, so no assert is generated — yet the fence still fires and blocks the
elimination.
Since the fence here is only a safety net, the over-fencing is safe but
misses real optimization opportunities; checking the actual assert-generation
condition and the apply side would make it precise.
--
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]
