You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@calcite.apache.org by "Xiening Dai (Jira)" <ji...@apache.org> on 2019/08/20 20:39:00 UTC
[jira] [Commented] (CALCITE-2166) Cumulative cost of RelSubset.best
RelNode is increased after calling RelSubset.propagateCostImprovements()
for input RelNodes
[ 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)