[jira] [Comment Edited] (CALCITE-2204) Volcano Planner may not choose the cheapest cost of plan wrongly

["LeoWangLZ (JIRA)" <ji...@apache.org>]

    [ 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:35 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.

 


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->parent22->parent12.

use BFS, it maybe input->parent11->parent12->parent21->parent22,

and so, it only concern the relNode in RelSubset instead of RelSubset. it will no have a cycle in RelSubset, the cost will be propagated normally

> 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)