morrySnow commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3765893505
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -126,6 +128,9 @@ public class ExpressionUtils {
private static final int MAX_INFER_NOT_NULL_EXPR_WIDTH = 256;
private static final int MAX_INFER_NOT_NULL_EXPR_DEPTH = 64;
private static final int MAX_INFER_NOT_NULL_INPUT_SLOTS = 32;
+ // The inferMarkSlotNotNullMap function needs at most
3^MAX_MARK_SLOT_COUNT loops to compute results.
+ // We restrict MAX_MARK_SLOT_COUNT to 4 to avoid long computation time.
+ private static final int MAX_MARK_SLOT_COUNT = 4;
Review Comment:
The complexity bound stated here ("at most 3^MAX_MARK_SLOT_COUNT loops")
understates the actual cost. Per target mark slot the loop runs 3^(N-1)
iterations with 4 FoldConstantRule evaluations each (original+simplified x
false+null), and the loop is repeated for every one of the N mark slots in the
predicate: worst case N * 3^(N-1) * 4 = 432 full `ExpressionUtils.replace` +
`FoldConstantRule.evaluate` passes over the whole conjunct (vs 2^N = 16 folds
in the old code). Each pass rebuilds the expression tree and folds it. For a
wide conjunct containing 4 mark slots this is ~27x the old analysis cost per
conjunct; it runs again for every filter/join conjunct. The bound comment
should reflect the actual N*3^(N-1)*4, and it may be worth keeping a flag to
skip the whole inference when the fold is trivially decidable by the first
tuple (the current break only helps when both fields turn false early).
##########
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:
This fence is over-conservative in two ways, both of which lose valid
eliminations:
1. The evaluation domain includes the current conjunct's own subquery plan
expressions (`collectEvaluationDomain` collects the plans of every subquery in
the conjunct set). But those inner plans are evaluated identically whether the
mark join is kept or eliminated: the apply and the resulting semi/anti join
both evaluate the inner plan per outer row (or once for uncorrelated), only the
output row set differs. So a `NoneMovableFunction`/volatile inside the current
conjunct's own subquery cannot be affected by the elimination, and fencing
pair.second on it is unnecessary.
2. Pair.first (treating the mark's null as false) is fenced by the same full
domain, but the null->false conversion is only observable by expressions that
consume the mark column, i.e. the conjunct set of the same filter/join.
Expressions inside any subquery plan never see the converted mark value, so
fencing pair.first with subquery plan expressions loses the non-nullable
inference for no safety gain.
Also, `containsNoneMovableOrVolatile(evaluationDomain)` is recomputed for
every target mark slot (up to 4x per conjunct) — it could be hoisted out of
`inferMarkSlotNotNullForTargetMarkSlot`.
--
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]
