[jira] [Created] (CALCITE-4302) Improve cost propagation in volcano to avoid re-propagation

["Botong Huang (Jira)" <ji...@apache.org>]

Botong Huang created CALCITE-4302:
-------------------------------------

             Summary: Improve cost propagation in volcano to avoid re-propagation
                 Key: CALCITE-4302
                 URL: https://issues.apache.org/jira/browse/CALCITE-4302
             Project: Calcite
          Issue Type: Improvement
            Reporter: Botong Huang


CALCITE-3330 changed the cost propagation in volcano from DFS to BFS. However, there is still room for improvement. A subset can be updated more than once in a cost propagation process. For instance, A -> D, A -> B -> C -> D. When subset A has an update, using BFS subset D (and thus all subsets above/after D) can be updated twice, first via A -> D and then C -> D. We can further improve the BFS by always popping the relNode with the smallest cost from the queue, similar to the Dijkstra algorithm. So that whenever a relNode is popped from the queue, its current best cannot be further deceased any more. As a result, all subsets will only be propagated at most once. 



--
This message was sent by Atlassian Jira
(v8.3.4#803005)