[
https://issues.apache.org/jira/browse/CALCITE-3990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17104945#comment-17104945
]
James Kim edited comment on CALCITE-3990 at 5/11/20, 10:40 PM:
---------------------------------------------------------------
It is currently using DFS; if the cost of a subset became cheaper, it will
immediately move on to checking if that subset's parent became cheaper. This is
not optimal, however, since if that parent was the parent of more than one
subset that became cheaper, the following case could take place:
1. subset A became cheaper
2. cost propagation occurs to parent subset
3. cost propagation occurs further up the tree
3. subset B (under the same parent as A) became cheaper
4. if this makes parent subset even cheaper than it was with A, cost
propagation occurs to parent subset
5. now cost propagation must occur again towards the top of tree, and step 3
was waste of work
Please let me know if anything I said was inaccurate.
was (Author: levv):
It is currently using DFS; if the cost of a subset became cheaper, it will
immediately move on to checking if that subset's parent became cheaper. This is
not optimal, however, since if that parent was the parent of more than one
subset that became cheaper, the following case could take place:
1. subset A became cheaper
2. cost propagation occurs to parent subset
3. cost propagation occurs further up the tree
3. subset B (under the same parent as A) became cheaper
4. this makes parent subset even cheaper than it was with A, so cost
propagation occurs to parent subset
5. now cost propagation must occur again towards the top of tree, and step 3
was waste of work
Please let me know if anything I said was inaccurate.
> Use a more efficient algorithm for cost propagation in Volcano planner
> ----------------------------------------------------------------------
>
> Key: CALCITE-3990
> URL: https://issues.apache.org/jira/browse/CALCITE-3990
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: James Kim
> Priority: Minor
>
> The previous method uses a recursive, depth-first approach, which can result
> in repeatedly updating the cost of some relSubsets many times.
> This patch moves to a breadth-first approach with a priority queue,
> very similar to Djikstra's algorithm.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
