github-actions[bot] commented on code in PR #67796:
URL: https://github.com/apache/doris/pull/67796#discussion_r4004760630
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PushDownTopNDistinctThroughJoin.java:
##########
@@ -197,6 +201,34 @@ private List<OrderKey> getPushedOrderKeys(Set<Slot>
groupBySlots, Set<Slot> join
notFound = true;
}
}
- return pushedOrderKeys.build();
+ List<OrderKey> pushedOrderKeyList = pushedOrderKeys.build();
+ if (pushedOrderKeyList.size() == orderKeys.size()
+ || isOrderKeyPrefixUniqueAfterDistinct(joinChild,
pushedOrderKeyList)) {
+ return pushedOrderKeyList;
+ }
+ return ImmutableList.of();
+ }
+
+ /**
+ * A partial order-key prefix is safe for a hard limit only when it
uniquely orders the rows produced by
+ * {@link PlanUtils#distinct(Plan)}. This is true when a leading part of
the prefix either is already a
+ * non-null unique key, covers every child output, or functionally
determines every remaining child output.
+ */
+ private boolean isOrderKeyPrefixUniqueAfterDistinct(Plan joinChild,
List<OrderKey> orderKeyPrefix) {
+ Set<Slot> childOutput = joinChild.getOutputSet();
+ DataTrait childTrait = joinChild.getLogicalProperties().getTrait();
+ FuncDeps validFuncDeps = childTrait.getAllValidFuncDeps(childOutput);
Review Comment:
[P2] Avoid eagerly expanding the full FD relation for impossible prefixes
This rebuilds all valid transitive FDs before examining the prefix. For a
cross-join child with no leading order key, the prefix is empty and must be
rejected, yet its FD relation is still materialized. An `n`-slot dependency
chain makes `findValidFuncDeps` emit Theta(n^2) root/descendant pairs; with the
reverse prefix, each of Theta(n) iterations eventually exhausts that set trying
to derive the missing root, so the nested scan performs at least Theta(n^3)
planner comparisons. The row-limit threshold does not bound expression width.
Please reject an empty prefix before loading traits, check output coverage
before computing the trait, defer FD construction until non-null uniqueness
fails, and use an indexed or incremental closure instead of rescanning every FD
item.
--
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]
