[CALCITE-4302] Improve cost propagation in volcano to avoid re-propagation

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.27.0
• Labels: pull-request-available
• Assignee: Danny Chen
• Reporter: Botong Huang
• Created: 02/Oct/20 20:29
• Updated: 03/Jun/21 22:32
• Resolved: 14/Oct/20 03:49

Description

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.

Issue Links

• is related to: CALCITE-4372 Correct specification getCumulativeCost and getNonCumulativeCost so it should always produce non-nullable value
• links to: GitHub Pull Request #2187