foxtail463 commented on code in PR #59013:
URL: https://github.com/apache/doris/pull/59013#discussion_r2656121063
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/Predicates.java:
##########
@@ -129,167 +131,239 @@ public static Map<Expression, ExpressionInfo>
compensateCouldNotPullUpPredicates
}
/**
- * compensate equivalence predicates
+ * Compensate equivalence predicates based on equivalence classes.
+ * Collects uncovered equivalence predicates into uncoveredEquals for
residual compensation.
*/
public static Map<Expression, ExpressionInfo>
compensateEquivalence(StructInfo queryStructInfo,
StructInfo viewStructInfo,
SlotMapping viewToQuerySlotMapping,
- ComparisonResult comparisonResult) {
+ ComparisonResult comparisonResult,
+ Set<Expression> uncoveredEquals) {
EquivalenceClass queryEquivalenceClass =
queryStructInfo.getEquivalenceClass();
EquivalenceClass viewEquivalenceClass =
viewStructInfo.getEquivalenceClass();
Map<SlotReference, SlotReference> viewToQuerySlotMap =
viewToQuerySlotMapping.toSlotReferenceMap();
EquivalenceClass viewEquivalenceClassQueryBased =
viewEquivalenceClass.permute(viewToQuerySlotMap);
if (viewEquivalenceClassQueryBased == null) {
return null;
}
- final Map<Expression, ExpressionInfo> equalCompensateConjunctions =
new HashMap<>();
if (queryEquivalenceClass.isEmpty() && viewEquivalenceClass.isEmpty())
{
return ImmutableMap.of();
}
- if (queryEquivalenceClass.isEmpty() &&
!viewEquivalenceClass.isEmpty()) {
- return null;
- }
EquivalenceClassMapping queryToViewEquivalenceMapping =
EquivalenceClassMapping.generate(queryEquivalenceClass,
viewEquivalenceClassQueryBased);
- // can not map all target equivalence class, can not compensate
if (queryToViewEquivalenceMapping.getEquivalenceClassSetMap().size()
< viewEquivalenceClass.getEquivalenceSetList().size()) {
return null;
}
- // do equal compensate
+ Map<Expression, ExpressionInfo> compensations = new HashMap<>();
Set<List<SlotReference>> mappedQueryEquivalenceSet =
queryToViewEquivalenceMapping.getEquivalenceClassSetMap().keySet();
for (List<SlotReference> queryEquivalenceSet :
queryEquivalenceClass.getEquivalenceSetList()) {
- // compensate the equivalence in query but not in view
if (!mappedQueryEquivalenceSet.contains(queryEquivalenceSet)) {
- Iterator<SlotReference> iterator =
queryEquivalenceSet.iterator();
- SlotReference first = iterator.next();
- while (iterator.hasNext()) {
- Expression equals = new EqualTo(first, iterator.next());
- if (equals.anyMatch(AggregateFunction.class::isInstance)) {
- return null;
- }
- equalCompensateConjunctions.put(equals,
ExpressionInfo.EMPTY);
+ SlotReference first = queryEquivalenceSet.get(0);
+ for (int i = 1; i < queryEquivalenceSet.size(); i++) {
+ uncoveredEquals.add(new EqualTo(first,
queryEquivalenceSet.get(i)));
}
} else {
- // compensate the equivalence both in query and view, but
query has more equivalence
List<SlotReference> viewEquivalenceSet =
queryToViewEquivalenceMapping.getEquivalenceClassSetMap().get(queryEquivalenceSet);
- List<SlotReference> copiedQueryEquivalenceSet = new
ArrayList<>(queryEquivalenceSet);
- copiedQueryEquivalenceSet.removeAll(viewEquivalenceSet);
- SlotReference first = viewEquivalenceSet.iterator().next();
- for (SlotReference slotReference : copiedQueryEquivalenceSet) {
- Expression equals = new EqualTo(first, slotReference);
+ List<SlotReference> queryExtraSlots = new
ArrayList<>(queryEquivalenceSet);
+ queryExtraSlots.removeAll(viewEquivalenceSet);
+
+ SlotReference firstViewSlot = viewEquivalenceSet.get(0);
+ for (SlotReference extraSlot : queryExtraSlots) {
+ Expression equals = new EqualTo(firstViewSlot, extraSlot);
if (equals.anyMatch(AggregateFunction.class::isInstance)) {
return null;
}
- equalCompensateConjunctions.put(equals,
ExpressionInfo.EMPTY);
+ compensations.put(equals, ExpressionInfo.EMPTY);
}
}
}
- return equalCompensateConjunctions;
+ return compensations;
}
/**
- * compensate range predicates
+ * Compensate range predicates.
+ * Collects uncovered range predicates into uncoveredRanges for residual
compensation.
*/
public static Map<Expression, ExpressionInfo>
compensateRangePredicate(StructInfo queryStructInfo,
StructInfo viewStructInfo,
SlotMapping viewToQuerySlotMapping,
ComparisonResult comparisonResult,
- CascadesContext cascadesContext) {
+ CascadesContext cascadesContext,
+ Set<Expression> uncoveredRanges) {
SplitPredicate querySplitPredicate =
queryStructInfo.getSplitPredicate();
SplitPredicate viewSplitPredicate = viewStructInfo.getSplitPredicate();
- Set<Expression> viewRangeQueryBasedSet = new HashSet<>();
- for (Expression viewExpression :
viewSplitPredicate.getRangePredicateMap().keySet()) {
- viewRangeQueryBasedSet.add(
- ExpressionUtils.replace(viewExpression,
viewToQuerySlotMapping.toSlotReferenceMap()));
- }
- viewRangeQueryBasedSet.remove(BooleanLiteral.TRUE);
+ Set<Expression> viewRangeQueryBasedSet = mapExpressionsToQueryContext(
+ viewSplitPredicate.getRangePredicateMap().keySet(),
viewToQuerySlotMapping);
+ Set<Expression> queryRangeSet = new
HashSet<>(querySplitPredicate.getRangePredicateMap().keySet());
- Set<Expression> queryRangeSet =
querySplitPredicate.getRangePredicateMap().keySet();
- queryRangeSet.remove(BooleanLiteral.TRUE);
+ // TODO: Seems already normalized. Is further normalization necessary?
+ Set<Expression> normalizedViewRange =
normalizeExpressionSet(viewRangeQueryBasedSet, cascadesContext);
+ Set<Expression> normalizedQueryRange =
normalizeExpressionSet(queryRangeSet, cascadesContext);
- Set<Expression> differentExpressions = new HashSet<>();
- Sets.difference(queryRangeSet,
viewRangeQueryBasedSet).copyInto(differentExpressions);
- Sets.difference(viewRangeQueryBasedSet,
queryRangeSet).copyInto(differentExpressions);
- // the range predicate in query and view is same, don't need to
compensate
- if (differentExpressions.isEmpty()) {
- return ImmutableMap.of();
- }
- // try to normalize the different expressions
- Set<Expression> normalizedExpressions =
- normalizeExpression(ExpressionUtils.and(differentExpressions),
cascadesContext);
- if (!queryRangeSet.containsAll(normalizedExpressions)) {
- // normalized expressions is not in query, can not compensate
+ Set<Expression> mvExtraRange = Sets.difference(normalizedViewRange,
normalizedQueryRange);
+ if (!mvExtraRange.isEmpty()) {
return null;
}
- Map<Expression, ExpressionInfo> normalizedExpressionsWithLiteral = new
HashMap<>();
- for (Expression expression : normalizedExpressions) {
- Set<Literal> literalSet = expression.collect(expressionTreeNode ->
expressionTreeNode instanceof Literal);
- if (!(expression instanceof ComparisonPredicate)
- || (expression instanceof GreaterThan || expression
instanceof LessThanEqual)
- || literalSet.size() != 1) {
- if (expression.anyMatch(AggregateFunction.class::isInstance)) {
- return null;
- }
- normalizedExpressionsWithLiteral.put(expression,
ExpressionInfo.EMPTY);
- continue;
- }
- if (expression.anyMatch(AggregateFunction.class::isInstance)) {
- return null;
- }
- normalizedExpressionsWithLiteral.put(expression, new
ExpressionInfo(literalSet.iterator().next()));
- }
- return normalizedExpressionsWithLiteral;
- }
- private static Set<Expression> normalizeExpression(Expression expression,
CascadesContext cascadesContext) {
- ExpressionNormalization expressionNormalization = new
ExpressionNormalization();
- ExpressionOptimization expressionOptimization = new
ExpressionOptimization();
- ExpressionRewriteContext context = new
ExpressionRewriteContext(cascadesContext);
- expression = expressionNormalization.rewrite(expression, context);
- expression = expressionOptimization.rewrite(expression, context);
- return ExpressionUtils.extractConjunctionToSet(expression);
+ uncoveredRanges.addAll(Sets.difference(normalizedQueryRange,
normalizedViewRange));
+ return ImmutableMap.of();
}
/**
- * compensate residual predicates
+ * Compensate residual predicates with extra query residuals (uncovered
equal/range predicates).
+ * Supports OR branch matching. For example, if MV has predicate (id = 5
OR id > 10)
+ * and query has (id = 5), the query matches one branch of MV's OR
predicate.
+ * Compensation NOT(id > 10) is generated to exclude the extra MV branch.
*/
public static Map<Expression, ExpressionInfo>
compensateResidualPredicate(StructInfo queryStructInfo,
StructInfo viewStructInfo,
SlotMapping viewToQuerySlotMapping,
- ComparisonResult comparisonResult) {
- // TODO Residual predicates compensate, simplify implementation
currently.
+ ComparisonResult comparisonResult,
+ Set<Expression> extraQueryResiduals) {
SplitPredicate querySplitPredicate =
queryStructInfo.getSplitPredicate();
SplitPredicate viewSplitPredicate = viewStructInfo.getSplitPredicate();
- Set<Expression> viewResidualQueryBasedSet = new HashSet<>();
- for (Expression viewExpression :
viewSplitPredicate.getResidualPredicateMap().keySet()) {
- viewResidualQueryBasedSet.add(
- ExpressionUtils.replace(viewExpression,
viewToQuerySlotMapping.toSlotReferenceMap()));
+ Set<Expression> viewResidualQueryBasedSet =
mapExpressionsToQueryContext(
+ viewSplitPredicate.getResidualPredicateMap().keySet(),
viewToQuerySlotMapping);
+ Set<Expression> queryResidualSet = new
HashSet<>(querySplitPredicate.getResidualPredicateMap().keySet());
+ if (extraQueryResiduals != null) {
+ queryResidualSet.addAll(extraQueryResiduals);
}
- viewResidualQueryBasedSet.remove(BooleanLiteral.TRUE);
-
- Set<Expression> queryResidualSet =
querySplitPredicate.getResidualPredicateMap().keySet();
- // remove unnecessary literal BooleanLiteral.TRUE
- queryResidualSet.remove(BooleanLiteral.TRUE);
- // query residual predicate can not contain all view residual
predicate when view have residual predicate,
- // bail out
- if (!queryResidualSet.containsAll(viewResidualQueryBasedSet)) {
+
+ Set<Expression> compensations =
coverResidualSets(viewResidualQueryBasedSet, queryResidualSet);
+ if (compensations == null) {
return null;
}
- queryResidualSet.removeAll(viewResidualQueryBasedSet);
- Map<Expression, ExpressionInfo> expressionExpressionInfoMap = new
HashMap<>();
- for (Expression needCompensate : queryResidualSet) {
- if (needCompensate.anyMatch(AggregateFunction.class::isInstance)) {
+
+ Map<Expression, ExpressionInfo> compensationMap = new HashMap<>();
+ for (Expression compensation : compensations) {
+ if (compensation.anyMatch(AggregateFunction.class::isInstance)) {
+ return null;
+ }
+ Set<Literal> literalSet = compensation.collect(expressionTreeNode
-> expressionTreeNode instanceof Literal);
+ ExpressionInfo exprInfo;
+ if (compensation instanceof ComparisonPredicate
+ && !(compensation instanceof GreaterThan || compensation
instanceof LessThanEqual)
+ && literalSet.size() == 1) {
+ exprInfo = new ExpressionInfo(literalSet.iterator().next());
+ } else {
+ exprInfo = ExpressionInfo.EMPTY;
+ }
+ compensationMap.put(compensation, exprInfo);
+ }
+ return compensationMap;
+ }
+
+ /**
+ * Check if MV residual predicates can cover query residual predicates,
return compensation expressions.
+ * <p>
+ * Example:
+ * MV residuals: [(id = 5 OR id > 10)]
+ * Query residuals: [(id = 5), (score = 1)]
+ * <p>
+ * Process:
+ * 1. (id = 5 OR id > 10) matches (id = 5) → compensation: NOT(id > 10)
Review Comment:
E.g.
MV: id = 5 or id = 2 or id > 10
query: id = 5 or id = 2
then we should compensate (not id>10)
or
id=5 or id=2
the closer the materialized view is to the query in form, the less "not
compensation" is required, and it can be predicted that the query is not much
different from the materialized view.
--
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]
