github-actions[bot] commented on code in PR #61345:
URL: https://github.com/apache/doris/pull/61345#discussion_r3031889823
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/Predicates.java:
##########
@@ -255,40 +262,249 @@ 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;
+ }
+ return compensateCandidatesByViewResidual(viewStructInfo,
viewToQuerySlotMapping,
+ compensationCandidates);
+ }
+
+ /**
+ * 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;
}
- viewResidualQueryBasedSet.remove(BooleanLiteral.TRUE);
+ }
+
+ private static PredicateCompensation doCompensateCandidatesByViewResidual(
+ StructInfo viewStructInfo,
+ SlotMapping viewToQuerySlotMapping,
+ PredicateCompensation compensationCandidates) {
+ Set<Expression> viewResidualPredicatesQueryBased =
+ collectViewResidualPredicates(viewStructInfo,
viewToQuerySlotMapping);
+ Expression combinedViewResidualQueryBased =
buildCombinedPredicate(viewResidualPredicatesQueryBased);
- 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)) {
+ if (!validateCompensationByViewResidual(combinedViewResidualQueryBased,
+ compensationCandidates)) {
return null;
}
- queryResidualSet.removeAll(viewResidualQueryBasedSet);
- Map<Expression, ExpressionInfo> expressionExpressionInfoMap = new
HashMap<>();
- for (Expression needCompensate : queryResidualSet) {
- if (needCompensate.anyMatch(AggregateFunction.class::isInstance)) {
+
+ return new PredicateCompensation(
+ removePredicatesImpliedByViewResidual(
+ compensationCandidates.getEquals(),
combinedViewResidualQueryBased),
+ removePredicatesImpliedByViewResidual(
+ compensationCandidates.getRanges(),
combinedViewResidualQueryBased),
+ removePredicatesImpliedByViewResidual(
+ compensationCandidates.getResiduals(),
combinedViewResidualQueryBased));
+ }
+
+ private static Set<Expression> collectViewResidualPredicates(StructInfo
viewStructInfo,
+ SlotMapping viewToQuerySlotMapping) {
+ Set<Expression> viewResidualPredicates = new LinkedHashSet<>();
+ for (Expression viewExpression :
viewStructInfo.getSplitPredicate().getResidualPredicateMap().keySet()) {
+ Expression queryBasedExpression =
+ ExpressionUtils.replace(viewExpression,
viewToQuerySlotMapping.toSlotReferenceMap());
+ if (!BooleanLiteral.TRUE.equals(queryBasedExpression)) {
+ viewResidualPredicates.add(queryBasedExpression);
+ }
+ }
+ return viewResidualPredicates;
+ }
+
+ private static Map<Expression, ExpressionInfo>
collectResidualCandidates(StructInfo queryStructInfo) {
+ Collection<Expression> expressions =
queryStructInfo.getSplitPredicate().getResidualPredicateMap().keySet();
+ Map<Expression, ExpressionInfo> residualPredicates = new
LinkedHashMap<>();
+ for (Expression expression : expressions) {
+ if (BooleanLiteral.TRUE.equals(expression)) {
+ continue;
+ }
+ // Aggregate functions in residual predicates are not safe for
detail-MV compensation.
+ if (expression.anyMatch(AggregateFunction.class::isInstance)) {
return null;
}
- expressionExpressionInfoMap.put(needCompensate,
ExpressionInfo.EMPTY);
+ residualPredicates.put(expression, ExpressionInfo.EMPTY);
+ }
+ return ImmutableMap.copyOf(residualPredicates);
+ }
+
+ private static boolean validateCompensationByViewResidual(
+ Expression combinedViewResidualQueryBased,
+ PredicateCompensation compensationCandidates) {
+ // Safety check: combinedQueryCandidates must imply viewResidual.
+ Expression combinedQueryCandidates = buildCombinedPredicate(
+ compensationCandidates.getEquals().keySet(),
+ compensationCandidates.getRanges().keySet(),
+ compensationCandidates.getResiduals().keySet());
+ return impliesByDnf(combinedQueryCandidates,
combinedViewResidualQueryBased);
+ }
+
+ @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) {
+ // Check whether source => target.
+ List<Set<Expression>> sourceBranches = extractDnfBranches(source);
+ List<Set<Expression>> targetBranches = extractDnfBranches(target);
+ if (sourceBranches.isEmpty()) {
+ return true;
+ }
+ if (targetBranches.isEmpty()) {
+ return false;
+ }
+ for (Set<Expression> sourceBranch : sourceBranches) {
Review Comment:
`impliesByDnf()` still treats implication as exact set containment inside
each DNF branch. That works for `A OR (B AND C)` vs `A OR B`, but it still
rejects stronger non-identical predicates. For example, if the query residual
is `id > 15 OR (score = 1 AND id = 5)` and the view residual is `id > 10 OR
(score = 1 AND id = 5)`, the first query branch *does* imply the first view
branch, but `sourceBranch.containsAll(targetBranch)` returns false because `id
> 15` is not textually equal to `id > 10`. In that case
`validateCompensationByViewResidual()` still bails out, so this doesn't yet
deliver the PR goal of handling logically implicative residuals beyond naive
set containment. Please add a branch-level implication check for comparable
predicates (at least the range predicates you already normalize elsewhere) and
cover it with a unit test.
--
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]
