XieJiann commented on code in PR #16992:
URL: https://github.com/apache/doris/pull/16992#discussion_r1115453128
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/NereidsPlanner.java:
##########
@@ -250,6 +252,16 @@ public Group getRoot() {
return cascadesContext.getMemo().getRoot();
}
+ private PhysicalPlan chooseNthPlan(Group rootGroup, PhysicalProperties
physicalProperties, int nthPlan) {
+ if (nthPlan == 1) {
Review Comment:
done
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java:
##########
@@ -706,4 +710,172 @@ public String toString() {
}
return builder.toString();
}
+
+ /**
+ * rank all plan and select n-th plan, we write the algorithm according
paper:
+ * * Counting,Enumerating, and Sampling of Execution Plans in a
Cost-Based Query Optimizer
+ * Specifically each physical plan in memo is assigned a unique ID in
rank(). And then we sort the
+ * plan according their cost and choose the n-th plan. Note we don't
generate any physical plan in rank
+ * function.
+ *
+ * In unrank() function, we will extract the actual physical function
according the unique ID
+ */
+ public long rank(long n) {
+ Preconditions.checkArgument(n > 0, "the n %d must be greater than 0 in
nthPlan", n);
+ List<Pair<Long, Double>> plans = rankGroup(root,
PhysicalProperties.GATHER);
+ Queue<Pair<Long, Double>> rankingQueue = new PriorityQueue<>(
+ (l, r) -> -Double.compare(l.second, r.second));
+
+ for (Pair<Long, Double> plan : plans) {
+ if (rankingQueue.size() == 0 || rankingQueue.size() < n) {
+ rankingQueue.add(plan);
+ } else if (rankingQueue.peek().second > plan.second) {
+ rankingQueue.poll();
+ rankingQueue.add(plan);
+ }
+ }
+ return rankingQueue.peek().first;
+ }
+
+ private List<Pair<Long, Double>> rankGroup(Group group, PhysicalProperties
prop) {
+ List<Pair<Long, Double>> res = new ArrayList<>();
+ int prefix = res.size();
+ for (GroupExpression groupExpression :
extractGroupExpressionContainsProp(group, prop)) {
+ for (Pair<Long, Double> idCostPair :
rankGroupExpression(groupExpression, prop)) {
+ res.add(Pair.of(idCostPair.first + prefix, idCostPair.second));
+ }
+ prefix = res.size();
+ }
+ return res;
+ }
+
+ private List<Pair<Long, Double>> rankGroupExpression(GroupExpression
groupExpression,
+ PhysicalProperties prop) {
+ if (!groupExpression.getLowestCostTable().containsKey(prop)) {
+ return new ArrayList<>();
+ }
+ List<Pair<Long, Double>> res = new ArrayList<>();
+
+ List<PhysicalProperties> inputProperties =
groupExpression.getInputPropertiesList(prop);
+ if (groupExpression.getPlan() instanceof LeafPlan) {
+ res.add(Pair.of(0L, groupExpression.getCostByProperties(prop)));
+ return res;
+ }
+
+ double bestChildrenCost = 0;
+ List<List<Pair<Long, Double>>> children = new ArrayList<>();
+ for (int i = 0; i < inputProperties.size(); i++) {
+
Preconditions.checkArgument(!groupExpression.child(i).equals(groupExpression.getOwnerGroup())
+ || !prop.equals(inputProperties.get(i)));
Review Comment:
done
--
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]
