github-actions[bot] commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3765650583
##########
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;
+ }
+ }
+ /*
+ * 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, the evaluation domain matters: 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 in this
+ * case so that the mark join is never eliminated across such
expressions.
+ *
+ * pair.first is not safe either, even when the mark join is kept.
treating the mark
+ * slot as non-nullable (isMarkJoinSlotNotNull) turns a null mark
value into false,
+ * and for a sensitive expression in the evaluation domain null and
false are
+ * observably different: 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. fence
pair.first to
+ * false as well in this case.
+ *
+ * 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 both fields are
validated against the
+ * complete evaluation domain (the containing conjunct set and all
affected subquery
+ * plans) instead of the current conjunct alone.
+ */
+ if (containsNoneMovableOrVolatile(evaluationDomain)) {
Review Comment:
[P2] Preserve Pair.first for sensitivity outside this predicate
This full-domain guard clears both fields, but only Pair.second changes
which rows reach sibling/later expressions. Pair.first keeps the Apply and only
maps this generated marker's NULL to FALSE; after a clean consumer such as
`ifnull(M,false)` proves that substitution safe, a sibling assertion or later
subquery cannot observe M. For an uncorrelated nullable positive IN, clearing
Pair.first leaves its equality solely in `markConjuncts`; with no correlation
hash conjunct, `JoinUtils.couldShuffle` returns false and planning is forced to
broadcast. Keeping Pair.first moves the equality into join conjuncts and
preserves the shuffle alternative. Please apply the current-predicate sensitive
fence to Pair.first, but the complete evaluation-domain fence only to
Pair.second, and add an uncorrelated nullable-IN plan regression.
--
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]
