[
https://issues.apache.org/jira/browse/CALCITE-2166?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16911714#comment-16911714
]
Xiening Dai commented on CALCITE-2166:
--------------------------------------
hi [~danny0405][~vvysotskyi], not sure what is the progress of this issue. I
spend some time looking into this and have a couple of proposals as below
(ranking from the easier to the hardiest) -
1. In propagateCostImprovements0() if we find bestrel cost is increased, we
just updated RelSubset.bestCost
This is the most trivial fix we can do. With that we can guarantee the internal
state of memo is consistent, but the plan generated can be sub-optimal.
2. In propagateCostImprovements0() if we find bestrel cost is increased, we
recompute cost for all rels within current subset, and choose the cheapest one
as the best.
This goes one step further than #1 to look for a potentially better plan when
the original bestrel cost is increased. Although this may generate better plans
under some cases, it is still not able to guarantee the optimal result.
3. Redesign the whole bestrel logic, so a given subset could have more than one
bestrel, and each best candidate would map to one or more parents.
The issue here is the fundamental assumption of our DP search model is broken
by exception case like this bug. The best of current subset does not
necessarliy uses the best of the input subset, because although the best of
input subset grantees the minimal of input cost, it doesn't necessarily
minimize the self cost of parent node since the row count could increase. With
this in mind, in order to find the optimal plan, we would need to have multiple
"best" candiates and take input rows into account when calculate parent's best.
Theoretically this would grantee an optimal plan, but it's fairly complex and
could incur significant overhead on runtime performance.
At this moment, I'd prefer proposal #1. #3 is too complex and requires drastic
change on the core framework which I don't see very feasible. #2 adds overhead
but again, same as #1, it doesn't grantee an optimal plan.
Let me know your thoughts. I would love to see this resolved so we can move on
to CALCITE-2018 which I believe is fairly important to the functionality of
core framework.
> Cumulative cost of RelSubset.best RelNode is increased after calling
> RelSubset.propagateCostImprovements() for input RelNodes
> -----------------------------------------------------------------------------------------------------------------------------
>
> Key: CALCITE-2166
> URL: https://issues.apache.org/jira/browse/CALCITE-2166
> Project: Calcite
> Issue Type: Bug
> Components: core
> Affects Versions: 1.15.0
> Reporter: Volodymyr Vysotskyi
> Assignee: Danny Chan
> Priority: Critical
>
> After calling {{RelSubset.propagateCostImprovements()}} cumulative cost of
> {{RelSubset.best}} {{RelNode}} may be increased due to the increase of the
> non-cumulative cost caused by changing of input best {{RelNode}}.
> To observe this issue, add this code:
> {code:java}
> if (subset.best != null) {
> RelOptCost bestCost = getCost(subset.best,
> RelMetadataQuery.instance());
> if (!subset.bestCost.equals(bestCost)) {
> throw new AssertionError(
> "relSubset [" + subset.getDescription()
> + "] has wrong best cost "
> + subset.bestCost + ". Correct cost is " + bestCost);
> }
> }
> {code}
> into {{VolcanoPlanner.validate()}} method (line 907).
> List of unit tests which fail with this check:
> {noformat}
> Failed tests:
>
> MaterializationTest.testJoinMaterializationUKFK9:1823->checkMaterialize:198->checkMaterialize:205->checkThatMaterialize:233
> relSubset [rel#226287:Subset#8.ENUMERABLE.[]] has wrong best cost {221.5
> rows, 128.25 cpu, 0.0 io}. Correct cost is {233.0 rows, 178.0 cpu, 0.0 io}
> ScannableTableTest.testPFPushDownProjectFilterAggregateNested:279 relSubset
> [rel#12950:Subset#5.ENUMERABLE.[]] has wrong best cost {63.8 rows, 62.308
> cpu, 0.0 io}. Correct cost is {70.4 rows, 60.404 cpu, 0.0 io}
> ScannableTableTest.testPFTableRefusesFilterCooperative:221 relSubset
> [rel#13382:Subset#2.ENUMERABLE.[]] has wrong best cost {81.0 rows, 181.01
> cpu, 0.0 io}. Correct cost is {150.5 rows, 250.505 cpu, 0.0 io}
> ScannableTableTest.testProjectableFilterableCooperative:148 relSubset
> [rel#13611:Subset#2.ENUMERABLE.[]] has wrong best cost {81.0 rows, 181.01
> cpu, 0.0 io}. Correct cost is {150.5 rows, 250.505 cpu, 0.0 io}
> ScannableTableTest.testProjectableFilterableNonCooperative:165 relSubset
> [rel#13754:Subset#2.ENUMERABLE.[]] has wrong best cost {81.0 rows, 181.01
> cpu, 0.0 io}. Correct cost is {150.5 rows, 250.505 cpu, 0.0 io}
> FrameworksTest.testUpdate:336->executeQuery:367 relSubset
> [rel#22533:Subset#2.ENUMERABLE.any] has wrong best cost {19.5 rows, 37.75
> cpu, 0.0 io}. Correct cost is {22.575 rows, 52.58 cpu, 0.0 io}
> {noformat}
> For the test {{MaterializationTest.testJoinMaterializationUKFK9}} initial
> best plan was:
> {noformat}
> EnumerableProject(empid0=[$5], empid00=[$5], deptno0=[$7]): rowcount = 15.0,
> cumulative cost = {15.0 rows, 45.0 cpu, 0.0 io}, id = 3989
> EnumerableJoin(subset=[rel#3988:Subset#34.ENUMERABLE.[]], condition=[=($1,
> $7)], joinType=[inner]): rowcount = 15.0, cumulative cost = {116.0 rows, 0.0
> cpu, 0.0 io}, id = 4797
> EnumerableFilter(subset=[rel#4274:Subset#47.ENUMERABLE.[0]],
> condition=[=(CAST($2):VARCHAR CHARACTER SET "ISO-8859-1" COLLATE
> "ISO-8859-1$en_US$primary", 'Bill')]): rowcount = 1.0, cumulative cost = {1.0
> rows, 1.0 cpu, 0.0 io}, id = 16522
> EnumerableTableScan(subset=[rel#158:Subset#11.ENUMERABLE.[0]],
> table=[[hr, m0]]): rowcount = 1.0, cumulative cost = {0.0 rows, 1.0 cpu, 0.0
> io}, id = 79
> EnumerableTableScan(subset=[rel#115:Subset#5.ENUMERABLE.[]], table=[[hr,
> depts]]): rowcount = 100.0, cumulative cost = {100.0 rows, 101.0 cpu, 0.0
> io}, id = 62
> {noformat}
> Its cumulative cost is \{221.5 rows, 123.75 cpu, 0.0 io}
> After applying some rules it became:
> {noformat}
> EnumerableProject(empid0=[$3], empid00=[$3], deptno0=[$0]): rowcount = 2.25,
> cumulative cost = {2.25 rows, 6.75 cpu, 0.0 io}, id = 4012
> EnumerableFilter(subset=[rel#4007:Subset#41.ENUMERABLE.[]],
> condition=[=(CAST($2):VARCHAR CHARACTER SET "ISO-8859-1" COLLATE
> "ISO-8859-1$en_US$primary", 'Bill')]): rowcount = 2.25, cumulative cost =
> {2.25 rows, 15.0 cpu, 0.0 io}, id = 4811
> EnumerableProject(subset=[rel#4203:Subset#61.ENUMERABLE.[]], deptno=[$7],
> deptno0=[$1], name0=[$2], empid0=[$5]): rowcount = 15.0, cumulative cost =
> {15.0 rows, 60.0 cpu, 0.0 io}, id = 4206
> EnumerableJoin(subset=[rel#4204:Subset#52.ENUMERABLE.[]],
> condition=[=($1, $7)], joinType=[inner]): rowcount = 15.0, cumulative cost =
> {116.0 rows, 0.0 cpu, 0.0 io}, id = 4795
> EnumerableTableScan(subset=[rel#158:Subset#11.ENUMERABLE.[0]],
> table=[[hr, m0]]): rowcount = 1.0, cumulative cost = {0.0 rows, 1.0 cpu, 0.0
> io}, id = 79
> EnumerableTableScan(subset=[rel#115:Subset#5.ENUMERABLE.[]],
> table=[[hr, depts]]): rowcount = 100.0, cumulative cost = {100.0 rows, 101.0
> cpu, 0.0 io}, id = 62
> {noformat}
> Its cumulative cost is {{\{233.0 rows, 148.0 cpu, 0.0 io\}}}.
--
This message was sent by Atlassian Jira
(v8.3.2#803003)
