[ https://issues.apache.org/jira/browse/CALCITE-2204?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16385600#comment-16385600 ]
LeoWangLZ edited comment on CALCITE-2204 at 3/5/18 5:49 AM: ------------------------------------------------------------ [~julianhyde] In function propagateCostImprovements0, This subset is already in the chain being propagated to. This means that the graph is cyclic, and therefore the cost of this relational expression - not this subset - must be infinite. it may miss the best plan. I think we should change the way of propagation. now the algorithm like pre-order, it may use Breadth-first Search. like {code:java} parent21,parent22 parent11, parent12 input{code} now the order of propagation is input->parent11->parent21->parent22->parent12. use BFS, it maybe input->parent11->parent12->parent21->parent22. Suppose the one parent of parent21 is parent12, then it exists a cycle. and the first propagation of parent12 happen in input->parent11->parent21->parent12, so it can get the cost and best relNode, and go to parent22, it's RelSubset maybe exists in activeSet, so it will stop. and when the next propagation of parent12, the cost have be calculated, and so it would not be less then itself, and it will not propagate to parents. then the best of parent12 can't be chosen. I propose my solution. Please review it. https://github.com/apache/calcite/pull/643 and it's hard for adding test for it. so I don't add test in this patch. and I will try to write one. Thanks was (Author: perid007): [~julianhyde] In function propagateCostImprovements0, This subset is already in the chain being propagated to. This means that the graph is cyclic, and therefore the cost of this relational expression - not this subset - must be infinite. it may miss the best plan. I think we should change the way of propagation. now the algorithm like pre-order, it may use Breadth-first Search. like {code:java} parent21,parent22 parent11, parent12 input{code} now the order of propagation is input->parent11->parent21->parent22->parent12. use BFS, it maybe input->parent11->parent12->parent21->parent22. Suppose the one parent of parent21 is parent12, then it exists a cycle. and the first propagation of parent12 happen in input->parent11->parent21->parent12, so it can get the cost and best relNode, and go to parent22, it's RelSubset maybe exists in activeSet, so it will stop. and when the next propagation of parent12, the cost have be calculated, and so it would not be less then itself, and it will not propagate to parents. then the best of parent12 can't be chosen. > Volcano Planner may not choose the cheapest cost of plan wrongly > ---------------------------------------------------------------- > > Key: CALCITE-2204 > URL: https://issues.apache.org/jira/browse/CALCITE-2204 > Project: Calcite > Issue Type: Bug > Reporter: LeoWangLZ > Assignee: Julian Hyde > Priority: Major > > Volcano Planner will propagate the cost improvement to parents that one of > the inputs has the best plan. But it not propagate to all parents firstly, it > propagate one parent and go to the parent s of parent. In the way, if one > parent may propagate to other parent on the same level, and the cost maybe > less than others, but when propagate the parent again, it will not propagate > because the cost is already calculated, and it's can't be less then the cost > of the self. -- This message was sent by Atlassian JIRA (v7.6.3#76005)