morrySnow commented on code in PR #16992:
URL: https://github.com/apache/doris/pull/16992#discussion_r1114185335
##########
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:
refer to `ValidatePasswordPolicyConverter` to check nthOptimizedPlan value
or
`nthPlan <= 1`
##########
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:
the check for enforce props is hard to understand, add some comment to
explain it~
##########
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)));
+ bestChildrenCost +=
groupExpression.children().get(i).getLowestCostPlan(inputProperties.get(i)).get().first;
+ List<Pair<Long, Double>> idCostPair
+ = rankGroup(groupExpression.child(i),
inputProperties.get(i));
+ children.add(idCostPair);
+ }
+ List<Pair<Long, List<Integer>>> childrenId = new ArrayList<>();
+ permute(children, 0, childrenId, new ArrayList<>());
+ for (Pair<Long, List<Integer>> c : childrenId) {
+ double childCost = 0;
+ for (int i = 0; i < children.size(); i++) {
+ childCost += children.get(i).get(c.second.get(i)).second;
+ }
+ res.add(Pair.of(c.first,
+ childCost + groupExpression.getCostByProperties(prop) -
bestChildrenCost));
+ }
+ return res;
+ }
+
+ // we permute all children, e.g.,
+ // for children [1, 2] [1, 2, 3]
+ // we can get: 0: [1,1] 1:[1, 2] 2:[1, 3] 3:[2, 1] 4:[2, 2] 5:[2, 3]
Review Comment:
use javadoc style~
##########
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)));
+ bestChildrenCost +=
groupExpression.children().get(i).getLowestCostPlan(inputProperties.get(i)).get().first;
+ List<Pair<Long, Double>> idCostPair
+ = rankGroup(groupExpression.child(i),
inputProperties.get(i));
+ children.add(idCostPair);
+ }
+ List<Pair<Long, List<Integer>>> childrenId = new ArrayList<>();
+ permute(children, 0, childrenId, new ArrayList<>());
+ for (Pair<Long, List<Integer>> c : childrenId) {
+ double childCost = 0;
+ for (int i = 0; i < children.size(); i++) {
+ childCost += children.get(i).get(c.second.get(i)).second;
+ }
+ res.add(Pair.of(c.first,
+ childCost + groupExpression.getCostByProperties(prop) -
bestChildrenCost));
+ }
+ return res;
+ }
+
+ // we permute all children, e.g.,
+ // for children [1, 2] [1, 2, 3]
+ // we can get: 0: [1,1] 1:[1, 2] 2:[1, 3] 3:[2, 1] 4:[2, 2] 5:[2, 3]
+ private void permute(List<List<Pair<Long, Double>>> children, int index,
+ List<Pair<Long, List<Integer>>> result, List<Integer> current) {
+ if (index == children.size()) {
+ result.add(Pair.of(getUniqueId(children, current), current));
+ return;
+ }
+ for (int i = 0; i < children.get(index).size(); i++) {
+ List<Integer> next = new ArrayList<>(current);
+ next.add(i);
+ permute(children, index + 1, result, next);
+ }
+ }
+
+ private static long getUniqueId(List<List<Pair<Long, Double>>> lists,
List<Integer> current) {
Review Comment:
add some comment to explain the logic of id generator
--
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]
