starocean999 commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3780624670
##########
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:
fix SemiJoinSemiJoinTransposeProject rule in other pr
--
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]
