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)
