github-actions[bot] commented on code in PR #66482:
URL: https://github.com/apache/doris/pull/66482#discussion_r3755449431
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/SubqueryToApply.java:
##########
@@ -118,20 +118,15 @@ public List<Rule> buildRules() {
ctx.statementContext,
shouldOutputMarkJoinSlot.get(i));
SubqueryContext context = new
SubqueryContext(subqueryExprs);
Expression conjunct =
replaceSubquery.replace(oldConjuncts.get(i), context);
- // TODO: The way to optimize null aware mark join is
not right.
- // remove it temporary until we refactor it.
- // ExpressionRewriteContext rewriteContext = new
ExpressionRewriteContext(ctx.cascadesContext);
- // boolean isMarkSlotNotNull =
conjunct.containsType(MarkJoinSlotReference.class)
- // ?
ExpressionUtils.canInferNotNullForMarkSlot(
- //
TrySimplifyPredicateWithMarkJoinSlot.INSTANCE.rewrite(conjunct,
- // rewriteContext),
rewriteContext)
- // : false;
- boolean isMarkSlotNotNull = false;
+ Pair<Expression, Map<MarkJoinSlotReference,
Pair<Boolean, Boolean>>> simplifyResult =
+ simplifyConjunctWithMarkJoinSlot(conjunct,
filter, ctx.cascadesContext);
Review Comment:
[P1] Fence elimination against the complete evaluation domain
Inference receives only the current marker-replaced conjunct. For `WHERE
ifnull(k IN (SELECT v FROM s), FALSE) AND assert_true(guard,'bad')`, top-level
conjunction extraction puts the assertion in a sibling expression, so the first
conjunct alone yields Pair.second=true. The resulting semi join prunes an
unmatched `guard=FALSE` row before the filter, whereas a mixed match/nonmatch
block from the retained mark Apply still evaluates the sibling assertion and
raises. A second blind spot occurs when the sensitive expression is inside a
later subquery plan: marker replacement erases that plan before this call, so
an earlier eliminable Apply can prune its input. The existing same-expression
fence cannot see either case. Please validate Pair.second against the complete
containing conjunct set and all affected subquery plans, with sibling-conjunct
and ordered multi-Apply regressions.
##########
fe/fe-core/src/test/java/org/apache/doris/nereids/util/InferMarkSlotNotNullMapTest.java:
##########
@@ -0,0 +1,230 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.util;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.rules.expression.ExpressionRewriteTestHelper;
+import org.apache.doris.nereids.trees.expressions.And;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.IsNull;
+import org.apache.doris.nereids.trees.expressions.MarkJoinSlotReference;
+import org.apache.doris.nereids.trees.expressions.Not;
+import org.apache.doris.nereids.trees.expressions.Or;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.expressions.functions.scalar.AssertTrue;
+import org.apache.doris.nereids.trees.expressions.functions.scalar.Nvl;
+import org.apache.doris.nereids.trees.expressions.literal.BooleanLiteral;
+import org.apache.doris.nereids.trees.expressions.literal.NullLiteral;
+import org.apache.doris.nereids.trees.expressions.literal.VarcharLiteral;
+import org.apache.doris.nereids.types.BooleanType;
+
+import com.google.common.collect.Lists;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.List;
+import java.util.Map;
+
+/**
+ * InferMarkSlotNotNullMapTest.
+ */
+public class InferMarkSlotNotNullMapTest extends ExpressionRewriteTestHelper {
+
+ @Test
+ public void testSingleMarkSlotAndOr() {
+ MarkJoinSlotReference markSlot1 = new
MarkJoinSlotReference("markSlot1");
+
+ // pair.first is based on the simplified predicate (non-mark-slot
children in And/Or
+ // are replaced by true/false): true when it taking false or null
always evaluates
+ // to false or null; pair.second is based on the original predicate:
true when it
+ // taking false or null always evaluates to false or null
+ assertMarkSlotPair(new And(BooleanLiteral.FALSE, markSlot1),
markSlot1, true, true);
+ assertMarkSlotPair(new And(BooleanLiteral.TRUE, markSlot1), markSlot1,
true, true);
+ assertMarkSlotPair(new And(NullLiteral.INSTANCE, markSlot1),
markSlot1, true, true);
+ // or(true, markSlot1): after simplification the child true is
replaced by false, so
+ // the simplified predicate or(false, markSlot1) taking false or null
evaluates to
+ // false or null, making pair.first true; the original or(true,
markSlot1) taking
+ // false evaluates to true, making pair.second false
+ assertMarkSlotPair(new Or(BooleanLiteral.TRUE, markSlot1), markSlot1,
true, false);
+ assertMarkSlotPair(new Or(BooleanLiteral.FALSE, markSlot1), markSlot1,
true, true);
+ assertMarkSlotPair(new Or(NullLiteral.INSTANCE, markSlot1), markSlot1,
true, true);
+ }
+
+ @Test
+ public void testSingleMarkSlotIsNullIsNotNull() {
+ MarkJoinSlotReference markSlot1 = new
MarkJoinSlotReference("markSlot1");
+
+ // is null: taking false returns false while taking null returns true,
which is
+ // neither false nor null, and taking true returns false, so both
fields are false
+ assertMarkSlotPair(new IsNull(markSlot1), markSlot1, false, false);
+ // is not null: taking false returns true, which is neither false nor
null, so
+ // pair.first is false; the original predicate taking false also
evaluates to
+ // true, so pair.second is false too
+ assertMarkSlotPair(new Not(new IsNull(markSlot1)), markSlot1, false,
false);
+ // markSlot1 and is not null(markSlot1): the predicate is equivalent to
+ // markSlot1 being true
+ assertMarkSlotPair(new And(markSlot1, new Not(new IsNull(markSlot1))),
+ markSlot1, true, true);
+ }
+
+ @Test
+ public void testSingleMarkSlotNvl() {
+ MarkJoinSlotReference markSlot1 = new
MarkJoinSlotReference("markSlot1");
+
+ // nvl(markSlot1, false) is equivalent to markSlot1 being true
+ assertMarkSlotPair(new Nvl(markSlot1, BooleanLiteral.FALSE),
markSlot1, true, true);
+ // nvl(markSlot1, true): taking null returns true, which is neither
false nor null,
+ // so both pair.first and pair.second are false
+ assertMarkSlotPair(new Nvl(markSlot1, BooleanLiteral.TRUE), markSlot1,
false, false);
+ // nvl(markSlot1, null): taking null returns null, which is treated as
same as false,
+ // and taking true returns true, so both fields are true
+ assertMarkSlotPair(new Nvl(markSlot1, NullLiteral.INSTANCE),
markSlot1, true, true);
+ }
+
+ @Test
+ public void testMultiMarkSlot() {
+ MarkJoinSlotReference markSlot1 = new
MarkJoinSlotReference("markSlot1");
+ MarkJoinSlotReference markSlot2 = new
MarkJoinSlotReference("markSlot2");
+
+ // or(markSlot1, markSlot2): when the other mark slot is true, the
target slot taking
+ // false or null evaluates to true, which is neither false nor null,
so both
+ // pair.first and pair.second are false
+ assertMarkSlotPair(new Or(markSlot1, markSlot2), markSlot1, false,
false);
Review Comment:
[P2] Exercise a later base-3 assignment
Every current multi-slot oracle is decided by tuple zero, where the other
mark is TRUE; the four-slot OR also exits on that all-TRUE tuple and asserts
only map size. Consequently, changing the implementation to `loopCount = 1`
still passes this suite. A mutation-sensitive case is `P = (M1 AND FALSE) OR
NOT(M2)` for target `M1`: `M2=TRUE` appears to allow `(true,true)`, but the
later `M2=FALSE` assignment makes both predicates TRUE and forces the correct
`(false,false)`. Please add this later-tuple case plus three-/four-slot carry
cases so the new enumeration logic is actually covered.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -680,72 +685,139 @@ 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) {
+ 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));
+ }
+ }
+ 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();
/*
- * 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;
}
- return true;
}
- return false;
+ /*
+ * 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 predicate. 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.
+ */
+ if (predicate.containsType(NoneMovableFunction.class)
+ || predicate.containsVolatileExpression()) {
+ sameResultForFalseAndNull = false;
Review Comment:
[P1] Fence Pair.first across evaluation-sensitive expressions
This guard clears only `sameResultForFalseAndNull` (Pair.second), leaving
`simplifiedForFalseAndNull` (Pair.first) true. For `((M AND
assert_true(guard,'bad')) OR flag)`, the simplifier produces `(M AND TRUE) OR
FALSE`, so Pair.first marks `M` non-null even though Pair.second correctly
keeps the mark Apply. With an unmatched positive-IN probe against a
NULL-containing build side, `InApplyToJoin` then changes `M` from NULL to
FALSE. Vectorized AND evaluates its RHS for the nullable NULL input but can
return before the RHS for an all-FALSE/non-null input, suppressing the required
`assert_true` error. This is distinct from the existing Pair.second issue
because the Apply and its row domain remain intact. Please fence Pair.first
(and the volatile analogue) here too, and add a NULL-producing error regression
for this retained-mark path.
--
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]
