morrySnow commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3733188026
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -680,72 +681,124 @@ 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) {
+ ExpressionRewriteContext rewriteContext = new
ExpressionRewriteContext(ctx.cascadesContext);
+ Expression simplifiedPredicate =
TrySimplifyPredicateWithMarkJoinSlot.INSTANCE.rewrite(predicate,
+ rewriteContext);
+ 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;
+ for (int targetIdx = 0; targetIdx < markSlotSize; ++targetIdx) {
+ result.put(markJoinSlotReferenceList.get(targetIdx),
+ inferMarkSlotNotNullForTargetMarkSlot(
+ predicate, simplifiedPredicate,
markJoinSlotReferenceList, targetIdx, ctx));
+ }
+ }
+ 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) {
+ 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();
Review Comment:
**Optimization: missing early exit when both booleans are already `false`.**
Once both `sameResultForFalseAndNull` and `simplifiedForFalseAndNull` have
been set to `false`, no further iteration can flip them back to `true`. Adding
`if (!sameResultForFalseAndNull && !simplifiedForFalseAndNull) break;` (or
`return Pair.of(false, false)`) would short-circuit the remaining loop
iterations.
In the worst case (4 mark slots → 27 inner iterations), the current code
always runs all 27 iterations per target slot (108 iterations total for 4
targets), doing 4 `FoldConstantRule.evaluate` + 4 `ExpressionUtils.replace`
calls per iteration (432 evaluations total). In many practical predicates both
flags will be set to `false` by the first few iterations. An early exit could
significantly reduce this.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -680,72 +681,124 @@ 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) {
+ ExpressionRewriteContext rewriteContext = new
ExpressionRewriteContext(ctx.cascadesContext);
+ Expression simplifiedPredicate =
TrySimplifyPredicateWithMarkJoinSlot.INSTANCE.rewrite(predicate,
Review Comment:
**Minor: the `ExpressionRewriteContext` created here discards the plan from
the caller's context.**
```java
ExpressionRewriteContext rewriteContext = new
ExpressionRewriteContext(ctx.cascadesContext);
Expression simplifiedPredicate =
TrySimplifyPredicateWithMarkJoinSlot.INSTANCE.rewrite(predicate,
rewriteContext);
```
The passed-in `ctx` may have been constructed with a `Plan` (see
`simplifyConjunctWithMarkJoinSlot` at `SubqueryToApply.java` line 157-158:
`plan == null ? new ExpressionRewriteContext(cascadesContext) : new
ExpressionRewriteContext(plan, cascadesContext)`). Here a fresh context is
created from just `cascadesContext`, discarding the plan. While
`TrySimplifyPredicateWithMarkJoinSlot` is a purely structural rewrite that
doesn't depend on plan state today, the plan-less context is then also what
flows into the fold-constant evaluation (via the original `ctx`). The
two-context pattern is confusing — consider either reusing the caller's context
directly for the simplify step, or adding a comment explaining why a fresh
plan-less context is intentionally used here.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java:
##########
@@ -237,28 +232,21 @@ public List<Rule> buildRules() {
ReplaceSubquery replaceSubquery = new
ReplaceSubquery(ctx.statementContext, true);
SubqueryContext context = new
SubqueryContext(subqueryExprs);
Expression conjunct =
replaceSubquery.replace(subqueryConjuncts.get(i), context);
- /*
- * 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
- * we pass this info to LogicalApply. And in
InApplyToJoin rule
- * if it's semi join with non-null mark slot
- * we can safely change the mark conjunct to hash
conjunct
- */
- ExpressionRewriteContext rewriteContext
- = new ExpressionRewriteContext(join,
ctx.cascadesContext);
- boolean isMarkSlotNotNull =
conjunct.containsType(MarkJoinSlotReference.class)
- ? ExpressionUtils.canInferNotNullForMarkSlot(
-
TrySimplifyPredicateWithMarkJoinSlot.INSTANCE.rewrite(conjunct, rewriteContext),
- rewriteContext)
- : false;
+ Map<MarkJoinSlotReference, Pair<Boolean, Boolean>>
markSlotsInfo;
+ if (join.getJoinType().isInnerOrCrossJoin() ||
join.getJoinType().isSemiJoin()) {
+ Pair<Expression, Map<MarkJoinSlotReference,
Pair<Boolean, Boolean>>> simplifyResult =
Review Comment:
**Question: why are outer/anti/asof joins excluded from mark-slot
simplification?**
The condition `join.getJoinType().isInnerOrCrossJoin() ||
join.getJoinType().isSemiJoin()` excludes LEFT/RIGHT OUTER, ANTI, and ASOF
joins from the `simplifyConjunctWithMarkJoinSlot` call, falling back to an
empty `markSlotsInfo` map. This means mark join elimination (`info.second`) and
non-nullable mark inference (`info.first`) are both skipped for those join
types.
For ANTI joins: the `buildRules` filter path (line 30-43) does call
`simplifyConjunctWithMarkJoinSlot` unconditionally. But in the join-ON path, a
NOT IN subquery in an ANTI join's ON clause would skip the simplification
entirely. While this is conservative and correct, a brief comment explaining
*why* these join types can't be simplified would help future readers (e.g.,
"outer joins preserve NULLs from the nullable side, making mark slot
three-valued semantics observable").
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -680,72 +681,124 @@ 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) {
+ ExpressionRewriteContext rewriteContext = new
ExpressionRewriteContext(ctx.cascadesContext);
+ Expression simplifiedPredicate =
TrySimplifyPredicateWithMarkJoinSlot.INSTANCE.rewrite(predicate,
+ rewriteContext);
+ 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)
Review Comment:
**Style: `maxMarkSlotCount = 4` should be a `private static final`
class-level constant.**
As a local variable inside `inferMarkSlotNotNullMap`, the rationale for the
limit (performance guard against 3^k combinatorial explosion) and the specific
value 4 are harder to discover. Extracting it to a named constant at the class
level, e.g. `private static final int MAX_MARK_SLOT_COUNT_FOR_INFERENCE = 4`,
with a brief comment explaining the 3^k scaling, would make the performance
contract explicit.
--
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]
