seawinde commented on code in PR #61345:
URL: https://github.com/apache/doris/pull/61345#discussion_r3050998076
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/Predicates.java:
##########
@@ -255,40 +258,257 @@ private static Set<Expression>
normalizeExpression(Expression expression, Cascad
}
/**
- * compensate residual predicates
+ * collect all predicate compensation candidates before residual
finalization.
*/
- public static Map<Expression, ExpressionInfo>
compensateResidualPredicate(StructInfo queryStructInfo,
+ public static PredicateCompensation collectCompensationCandidates(
+ StructInfo queryStructInfo,
StructInfo viewStructInfo,
SlotMapping viewToQuerySlotMapping,
- ComparisonResult comparisonResult) {
- // TODO Residual predicates compensate, simplify implementation
currently.
- SplitPredicate querySplitPredicate =
queryStructInfo.getSplitPredicate();
- SplitPredicate viewSplitPredicate = viewStructInfo.getSplitPredicate();
+ ComparisonResult comparisonResult,
+ CascadesContext cascadesContext) {
+ Map<Expression, ExpressionInfo> equalCandidates =
collectEquivalenceCandidates(
+ queryStructInfo, viewStructInfo, viewToQuerySlotMapping,
comparisonResult);
+ Map<Expression, ExpressionInfo> rangeCandidates =
collectRangeCandidates(
+ queryStructInfo, viewStructInfo, viewToQuerySlotMapping,
comparisonResult, cascadesContext);
+ Map<Expression, ExpressionInfo> residualCandidates =
collectResidualCandidates(queryStructInfo);
+ if (equalCandidates == null || rangeCandidates == null ||
residualCandidates == null) {
+ return null;
+ }
+ return new PredicateCompensation(equalCandidates, rangeCandidates,
residualCandidates);
+ }
- Set<Expression> viewResidualQueryBasedSet = new HashSet<>();
- for (Expression viewExpression :
viewSplitPredicate.getResidualPredicateMap().keySet()) {
- viewResidualQueryBasedSet.add(
- ExpressionUtils.replace(viewExpression,
viewToQuerySlotMapping.toSlotReferenceMap()));
+ /**
+ * compensate predicates in one step.
+ */
+ public static PredicateCompensation compensatePredicates(
+ StructInfo queryStructInfo,
+ StructInfo viewStructInfo,
+ SlotMapping viewToQuerySlotMapping,
+ ComparisonResult comparisonResult,
+ CascadesContext cascadesContext) {
+ PredicateCompensation compensationCandidates =
collectCompensationCandidates(
+ queryStructInfo, viewStructInfo, viewToQuerySlotMapping,
comparisonResult, cascadesContext);
+ if (compensationCandidates == null) {
+ return null;
}
- viewResidualQueryBasedSet.remove(BooleanLiteral.TRUE);
+ return compensateCandidatesByViewResidual(viewStructInfo,
viewToQuerySlotMapping,
+ compensationCandidates);
+ }
- 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)) {
+ /**
+ * Build the final predicate compensation from collected candidates.
+ *
+ * This step uses query-based view residual predicates to:
+ * 1) validate compensation safety (candidates must imply view residual),
and
+ * 2) remove candidate predicates already covered by view residual.
+ *
+ * Returns null when compensation is unsafe or cannot be proven within DNF
guard limits.
+ */
+ public static PredicateCompensation compensateCandidatesByViewResidual(
+ StructInfo viewStructInfo,
+ SlotMapping viewToQuerySlotMapping,
+ PredicateCompensation compensationCandidates) {
+ try {
+ return doCompensateCandidatesByViewResidual(viewStructInfo,
viewToQuerySlotMapping,
+ compensationCandidates);
+ } catch (DnfBranchOverflowException e) {
+ // DNF branch expansion may explode exponentially; fail
compensation conservatively.
return null;
}
- queryResidualSet.removeAll(viewResidualQueryBasedSet);
- Map<Expression, ExpressionInfo> expressionExpressionInfoMap = new
HashMap<>();
- for (Expression needCompensate : queryResidualSet) {
- if (needCompensate.anyMatch(AggregateFunction.class::isInstance)) {
+ }
+
+ private static PredicateCompensation doCompensateCandidatesByViewResidual(
+ StructInfo viewStructInfo,
+ SlotMapping viewToQuerySlotMapping,
+ PredicateCompensation compensationCandidates) {
+ Set<Expression> queryBasedViewResidualPredicates =
+ collectViewResidualPredicates(viewStructInfo,
viewToQuerySlotMapping);
+ Expression combinedQueryBasedViewResidual =
buildCombinedPredicate(queryBasedViewResidualPredicates);
+
+ if (!validateCompensationByViewResidual(combinedQueryBasedViewResidual,
+ compensationCandidates)) {
+ return null;
+ }
+
+ return new PredicateCompensation(
+ removePredicatesImpliedByViewResidual(
+ compensationCandidates.getEquals(),
combinedQueryBasedViewResidual),
+ removePredicatesImpliedByViewResidual(
+ compensationCandidates.getRanges(),
combinedQueryBasedViewResidual),
+ removePredicatesImpliedByViewResidual(
+ compensationCandidates.getResiduals(),
combinedQueryBasedViewResidual));
+ }
+
+ private static Set<Expression> collectViewResidualPredicates(StructInfo
viewStructInfo,
+ SlotMapping viewToQuerySlotMapping) {
+ return collectNonInferredQueryBasedExpressions(
+
viewStructInfo.getSplitPredicate().getResidualPredicateMap().keySet(),
viewToQuerySlotMapping);
+ }
+
+ private static Map<Expression, ExpressionInfo>
collectResidualCandidates(StructInfo queryStructInfo) {
+ Set<Expression> expressions = collectNonInferredExpressions(
+
queryStructInfo.getSplitPredicate().getResidualPredicateMap().keySet());
+ Map<Expression, ExpressionInfo> residualCandidates = new
LinkedHashMap<>();
+ for (Expression expression : expressions) {
+ if (expression.anyMatch(AggregateFunction.class::isInstance)) {
+ // Aggregate functions in residual predicates are not safe for
detail-MV compensation.
return null;
}
- expressionExpressionInfoMap.put(needCompensate,
ExpressionInfo.EMPTY);
+ residualCandidates.put(expression, ExpressionInfo.EMPTY);
+ }
+ return ImmutableMap.copyOf(residualCandidates);
+ }
+
+ private static Set<Expression>
collectNonInferredExpressions(Collection<Expression> expressions) {
+ return expressions.stream()
+ .filter(expression -> !ExpressionUtils.isInferred(expression))
+ .filter(expression -> !BooleanLiteral.TRUE.equals(expression))
+ .collect(Collectors.toCollection(LinkedHashSet::new));
+ }
+
+ private static Set<Expression>
collectNonInferredQueryBasedExpressions(Collection<Expression> expressions,
+ SlotMapping viewToQuerySlotMapping) {
+ Map<SlotReference, SlotReference> slotReferenceMap =
viewToQuerySlotMapping.toSlotReferenceMap();
+ return expressions.stream()
+ .filter(expression -> !ExpressionUtils.isInferred(expression))
+ .map(expression -> ExpressionUtils.replace(expression,
slotReferenceMap))
+ .filter(expression -> !BooleanLiteral.TRUE.equals(expression))
+ .collect(Collectors.toCollection(LinkedHashSet::new));
+ }
+
+ private static boolean validateCompensationByViewResidual(
+ Expression combinedQueryBasedViewResidual,
+ PredicateCompensation compensationCandidates) {
+ // Safety check: combinedQueryCandidates must imply viewResidual.
+ Expression combinedQueryCandidates = buildCombinedPredicate(
+ compensationCandidates.getEquals().keySet(),
+ compensationCandidates.getRanges().keySet(),
+ compensationCandidates.getResiduals().keySet());
+ return impliesByDnf(combinedQueryCandidates,
combinedQueryBasedViewResidual);
+ }
+
+ @SafeVarargs
+ private static Expression buildCombinedPredicate(Collection<Expression>...
predicateCollections) {
+ List<Expression> combinedPredicates = new ArrayList<>();
+ for (Collection<Expression> predicateCollection :
predicateCollections) {
+ for (Expression predicate : predicateCollection) {
+ if (!BooleanLiteral.TRUE.equals(predicate)) {
+ combinedPredicates.add(predicate);
+ }
+ }
+ }
+ return ExpressionUtils.and(combinedPredicates);
+ }
+
+ private static Map<Expression, ExpressionInfo>
removePredicatesImpliedByViewResidual(
+ Map<Expression, ExpressionInfo> predicates,
+ Expression viewResidual) {
+ // Remove candidates already implied by the view residual predicate.
+ Map<Expression, ExpressionInfo> remainingPredicates = new
LinkedHashMap<>();
+ for (Map.Entry<Expression, ExpressionInfo> entry :
predicates.entrySet()) {
+ // If viewResidual => candidate, candidate is redundant and can be
dropped.
+ if (!impliesByDnf(viewResidual, entry.getKey())) {
+ remainingPredicates.put(entry.getKey(), entry.getValue());
+ }
+ }
+ return ImmutableMap.copyOf(remainingPredicates);
+ }
+
+ private static boolean impliesByDnf(Expression source, Expression target) {
Review Comment:
add a test case for a stronger-but-not-identical range predicate in residual
implication: query: id > 15 OR (score = 1 AND id = 5), view: id > 10 OR (score
= 1 AND id = 5). Per the PR
goal, this should succeed, but with the current implementation it will
likely still fail because impliesByDnf() only does branch-level set containment
instead of predicate-level
implication.
--
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]
