You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-dev@db.apache.org by "A B (JIRA)" <de...@db.apache.org> on 2006/02/18 02:23:25 UTC
[jira] Created: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
----------------------------------------------------------------------------------------------------------------------------
Key: DERBY-1007
URL: http://issues.apache.org/jira/browse/DERBY-1007
Project: Derby
Type: Bug
Components: Performance
Versions: 10.2.0.0
Reporter: A B
Priority: Minor
When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
Following example of what I saw when tracing through the code demonstrates the problem.
select x1.j, x2.b from
(select distinct i,j from t1) x1,
(select distinct a,b from t3) x2
where x1.i = x2.a;
During optimization of this query we will create three instancesof OptimizerImpl:
OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
OI_1: For "select distinct i,j from t1"
OI_2: For "select distinct a,b from t3"
Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
-- Top-level call is made to the optimize() method of the
outermost SelectNode, which creates OI_0.
-- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
-- X1: *creates* OI_1 and makes calls to optimize it.
-- OI_1: picks join order {T1} and calls T1.optimizeIt()
-- T1: returns a cost of 20.
-- OI_1: saves 20 as new best cost and tells T1 to save it.
-- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
then returns 20 to OI_0.
-- OI_0: calls X2.optimizeIt()
-- X2: *creates* OI_2 and makes calls to optimize it.
-- OI_2: picks join order {T3} and calls T3.optimizeIt()
-- T3: returns a cost of 64700.
-- OI_2: saves 64700 as new best cost and tells T3 to save it.
-- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
then returns 64700 to OI_0.
-- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
X1 to save 20 and X2 to save 64700.
-- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
-- X2: *fetches* OI_2 and makes calls to optimize it.
-- OI_2: picks join order {T3} and calls T3.optimizeIt()
-- T3: returns a cost of 10783.
-- OI_2: saves 10783 as new best cost and tells T3 to save it.
-- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
then returns 10783 to OI_0.
-- OI_0: calls X1.optimizeIt()
-- X1: *fetches* OI_1 and makes calls to optimize it.
-- OI_1: picks join order {T1} and calls T1.optimizeIt()
-- T1: returns a cost of *1 MILLION!*.
-- OI_1: rejects new cost (1 mil > 20) and does nothing.
-- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
then returns 20 to OI_0...this seems WRONG!
-- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
X2 to save 10783 and X1 to save 20.
So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Resolved: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "A B (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
A B resolved DERBY-1007:
------------------------
Fix Version: 10.2.0.0
10.1.2.5
10.1.2.4
Resolution: Fixed
Follow-up patch checked into trunk with svn 397675; both patches (original and followup) checked into 10.1 with svn 397682. So I'm marking this issue as resolved. Thanks for the commits, Satheesh.
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Fix For: 10.2.0.0, 10.1.2.4, 10.1.2.5
> Attachments: d1007_followup_v1.patch, d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Closed: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "A B (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
A B closed DERBY-1007:
----------------------
Changes have been in 10.1 and 10.2 codelines for over a month now, so I'm marking the issue as closed.
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Fix For: 10.2.0.0, 10.1.2.4, 10.1.2.5
> Attachments: d1007_followup_v1.patch, d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "A B (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=comments#action_12376837 ]
A B commented on DERBY-1007:
----------------------------
While waiting for the followup patch to be committed to 10.2 (trunk), I've also included the patch to port these changes (the original plus the followup) to 10.1--the patch for doing so is attached to DERBY-805 and also posted here:
http://article.gmane.org/gmane.comp.apache.db.derby.devel/19330.
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Attachments: d1007_followup_v1.patch, d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "Dag H. Wanvik (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DERBY-1007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Dag H. Wanvik updated DERBY-1007:
---------------------------------
Derby Categories: [Performance]
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: https://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Issue Type: Bug
> Affects Versions: 10.2.1.6
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Fix For: 10.1.3.1, 10.2.1.6
>
> Attachments: d1007_followup_v1.patch, d1007_v1.patch, d1007_v1.stat
>
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "A B (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
A B reassigned DERBY-1007:
--------------------------
Assign To: A B
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "Satheesh Bandaram (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=comments#action_12369235 ]
Satheesh Bandaram commented on DERBY-1007:
------------------------------------------
Patch submitted to trunk.
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Attachments: d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "A B (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
A B updated DERBY-1007:
-----------------------
Other Info: [Patch available]
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Attachments: d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "A B (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
A B updated DERBY-1007:
-----------------------
Attachment: d1007_followup_v1.patch
In a word, the fix for this issue ensures that, in the case of subqueries, the optimizer will correctly propagate the estimated costs for subqueries up to the parent subquery(-ies), thus allowing the parent query to make a better decision about which join order is ultimately the best. As seen in the example scenario included above, the correct estimates are higher--sometimes much higher--than what the optimizer was returning prior to this change: in the example, the optimizer was returning an incorrect cost estimate of 10783 before the patch, and a correct estimate of 1 million after the patch (where "correct" means that it's the value calculated by the optimizer and thus the value that should be returned; I'm not saying anything about the accuracy of the estimate here).
One side effect of this is that, for very deeply nested queries and/or queries with a high number of FROM tables/expressions, the higher cost estimates can be multiplied--sometimes many times over--throughout the optimization process, which means that the overall query estimate can climb to a much larger number much more quickly. If the query is big enough, this can actually cause the optimizer to reach an estimated cost of INFINITY.
That said, the current optimizer logic for choosing a plan does not expect to see an estimate of infinity for its plans. As a result the optimizer does comparisons of, and arithmetic with, cost estimates and row counts that, when applied to Infinity, give unexpected results.
I have filed DERBY-1259 and DERBY-1260 to address the "infinity problem" in more detail, but am attaching here a follow-up patch that takes some basic steps toward making the optimizer more robust in the face of infinite cost estimates, which are now more likely to occur given the DERBY-1007 changes. In particular, the d1007_followup_v1.patch does the following:
1) Fixes a couple of small problems with the handling of estimates for FromBaseTables, to ensure that a FromBaseTable's estimate is correctly propagated to (and handled by) the ProjectRestrictNode that sits above it. This parallels the original DERBY-1007 work but is a much simpler "follow-up" task as it deals only with base tables instead of subqueries, and thus the changes are fairly minor.
2) There are several places in OptimizerImpl where the optimizer will only choose to accept a plan's cost if the cost is less than the current "bestCost". If no best cost has been found yet, bestCost is set to an uninitialized value of Double.MAX_VALUE with the assumption that the first valid plan will have a cost less than Double.MAX_VALUE and thus will be chosen as the best so far. However, since a plan's cost estimate can actually end up being Double.POSITIVE_INFINITY, which is greater than Double.MAX_VALUE, it's possible that the optimizer will reject a valid join order because its cost is infinity, and then end up completing without ever finding a valid plan--which is wrong. What we want is for the optimizer to accept the first valid plan that it finds, regardless of what the cost is. Then if it later finds a better plan, it can use that. So in several places the d1007_followup_v1.patch adds a check to see if bestCost is uninitialized and, if so, we'll always accept the first valid join order we find, regardless of what its cost is--even if it's infinity--because that's better than no plan at all.
3) Modifies the "compare" method in CostEstimateImpl.java to try to account for comparisons between two plans that both have infinite costs. If this happens, we don't have much choice but to guess as to which plan is actually better. So the changes for followup_v1 make that guess based on a comparison of row counts for the two plans. And if the row counts themselves are infinity, then we'll guess based on the single scan row counts. And finally, if those values are both infinity, as well, then we're out of luck and we just say that the two costs are "equal" for lack of better alternative.
4) And finally, due to unexpected behavior that results from arithmetic using infinity (see DERBY-1259), it is currently possible (though rather rare) for the optimizer to decide to do a hash join that has a cost estimate of Infinity. An example of a query for which this could happen can be found in DERBY-1205, query #1. That said, the BackingStoreHashtable that is used for carrying out a hash join currently creates a Java Hashtable instance with a capacity that matches the optimizer's estimated row count. So if the row count is infinity we'll try to create a Hashtable with some impossibly large capacity and, as a result, we'll end up with an OutOfMemory error. So the d1007_followup_v1.patch adds some code to handle this kind of situation in a more graceful manner.
I ran derbyall with these changes on Linux Red Hat using ibm142 and saw no new failures.
So if anyone has time to review/commit, I'd appreciate it.
Thanks.
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Attachments: d1007_followup_v1.patch, d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "A B (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
A B updated DERBY-1007:
-----------------------
Attachment: d1007_v1.patch
d1007_v1.stat
Attaching a patch, d1007_v1.patch, to resolve this issue. The changes are summarized as follows:
1. Added the "prepForNextRound()" method that was part of OptimizerImpl to the Optimizer interface since that seems like an appropriate place for it.
2. Added a single line to OptimizerImpl.prepForNextRound() to reset the "bestCost" for the current round of optimization. Note that I do _not_ reset the "foundABestPlan" variable nor the "bestJoinOrder" array. This is because it's possible that a "best join order" may not exist for the current round, in which case the optimizer must know whether or not it found a best join order in a previous round (foundABestPlan) and if so what the corresponding join order was (bestJoinOrder). That information is required so that a valid query plan can be generated after optimization is complete.
3. After making the above changes, I noticed that the optimizer cost estimates were not always showing up when logQueryPlan was set to true--they were sometimes being printed as question marks to represent "Infinity". The reason for this was that most of the code in the "modifyAccessPaths" phase of query compilation uses the estimates as they sit in the ResultSetNode.costEstimate field--which, for nodes above subqueries, will hold the "bestCost" estimates for the most recent plan chosen by the OptimizerImpl for the subquery. Since I am now (with DERBY-1007) resetting the "bestCost" variable at the start of every round, it's possible that "bestCost" will hold an estimate that has been "reset" to Double.MAX_VALUE. This can happen if it was reset (in prepForNextRound()) and then no valid join order was found for the current round (ex. if no valid join order exists or if there was an optimizer "timeout"). That in turn meant that the "costEstimate" field for nodes above the OptimizerImpl would have been "reset" as well, and hence the "infinity" value (i.e. question mark) was showing up in the logged query plan. So I had to find all nodes that use "costEstimate" during modifyAccessPaths() and update them to use the final, best cost estimate for that node (instead of just using the most recent value of "costEstimate"). This touched several of ResultSetNode's subclasses, but the diff in most cases is just a few lines. The exceptions are FromTable, SelectNode, UnionNode, IntersectOrExceptNode, and JoinNode, where I added new "getFinalCostEstimate" methods to correctly figure out the final cost estimate based on the final estimates for child nodes, as appropriate.
4. The current optimizer "timeout" mechanism is based on the value in OptimizerImpl.bestCost. Since I'm now resetting that value at the start of every round, the timeout mechanism had to be changed in order to preserve its current functionality while removing the dependency on bestCost. So I've added a new variable, timeLimit, to OptimizerImpl that plays the same role w.r.t optimizer "timeout" that the old bestCost value did.
5. Updated master/derived.out to match new behavior. There's one query in derived.sql that is affected by this issue. Before these changes the optimizer thought one join order B was cheaper than another join order A and so it chose to generate join order B. With these changes, though, it now (correctly) sees that join order A and join order B are equivalent, so it just goes with join order A. This difference manifests itself in the ordering of two rows in the result set for that query--so I've updated the masters accordingly.
6. Added a new, simple test case specific to DERBY-1007 to lang/subquery.sql, and updated the master file accordingly. The test case is the same one mentioned in the description for this issue.
I ran derbyall on Red Hat Linux using IBM 1.4.2 with my changes and saw no failures. I would very much appreciate any comments/feedback from any available reviewers/ committers out there...
Note to committers: The changes in d1007_v1.patch depend on code changes made as part of d805_phase1_v3.patch for DERBY-805. Since that patch was only recently committed, you'll have to be sure to sync up before trying to apply d1007_v1.patch....
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Attachments: d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "Satheesh Bandaram (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
Satheesh Bandaram updated DERBY-1007:
-------------------------------------
Other Info: (was: [Patch available])
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Attachments: d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (DERBY-1007) Optimizer can return incorrect "best
cost" estimates with nested subqueries, which leads to generation of
sub-optimal plans.
Posted by "Mike Matrigali (JIRA)" <de...@db.apache.org>.
[ http://issues.apache.org/jira/browse/DERBY-1007?page=all ]
Mike Matrigali updated DERBY-1007:
----------------------------------
I have reviewed the BackingStoreHashtable.java changes, and they look ok to me. As the comments mention it is
wierd to compare row count and memory size, but the issue is well documented in the change - and addresses
the problem. I have added some comments to DERBY-1259, with regard to fixing the issue that this change addresses in the caller - but it still seems reasonable to "bulletproof" this routine even if in a running system we don't expect the case. Better to have the routine work than fail a query. I will leave the commit/review of the optimizer part to those with expertise in that area.
> Optimizer can return incorrect "best cost" estimates with nested subqueries, which leads to generation of sub-optimal plans.
> ----------------------------------------------------------------------------------------------------------------------------
>
> Key: DERBY-1007
> URL: http://issues.apache.org/jira/browse/DERBY-1007
> Project: Derby
> Type: Bug
> Components: Performance
> Versions: 10.2.0.0
> Reporter: A B
> Assignee: A B
> Priority: Minor
> Attachments: d1007_followup_v1.patch, d1007_v1.patch, d1007_v1.stat
>
> When optimizing a query that has nested subqueries in it, it's possible that the optimizer for the subqueries will return cost estimates that are lower than what they were actually calculated to be. The result is that the outer query can pick an access plan that is sub-optimal.
> Filing this jira issue based on the thread "[OPTIMIZER] OptimizerImpl "best plans" for subqueries?" from derby-dev. Description that follows is pasted from that email:
> http://article.gmane.org/gmane.comp.apache.db.derby.devel/14836
> Following example of what I saw when tracing through the code demonstrates the problem.
> select x1.j, x2.b from
> (select distinct i,j from t1) x1,
> (select distinct a,b from t3) x2
> where x1.i = x2.a;
> During optimization of this query we will create three instancesof OptimizerImpl:
> OI_0: For "select x1.j, x2.b from x1, x2 where x1.i = x2.a"
> OI_1: For "select distinct i,j from t1"
> OI_2: For "select distinct a,b from t3"
> Query ran against a clean codeline when T1 had 1 row and T3 had 50,000.
> -- Top-level call is made to the optimize() method of the
> outermost SelectNode, which creates OI_0.
> -- OI_0: picks join order {X1, X2} and calls X1.optimizeIt()
> -- X1: *creates* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of 20.
> -- OI_1: saves 20 as new best cost and tells T1 to save it.
> -- X1: calls OI_1.getOptimizedCost(), which returns 20. X1
> then returns 20 to OI_0.
> -- OI_0: calls X2.optimizeIt()
> -- X2: *creates* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 64700.
> -- OI_2: saves 64700 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 64700. X2
> then returns 64700 to OI_0.
> -- OI_0: saves 20 + 64700 = 64720 as new best cost and tells
> X1 to save 20 and X2 to save 64700.
> -- OI_0: picks join order {X2, X1} and calls X2.optimizeIt()
> -- X2: *fetches* OI_2 and makes calls to optimize it.
> -- OI_2: picks join order {T3} and calls T3.optimizeIt()
> -- T3: returns a cost of 10783.
> -- OI_2: saves 10783 as new best cost and tells T3 to save it.
> -- X2: calls OI_2.getOptimizedCost(), which returns 10783. X2
> then returns 10783 to OI_0.
> -- OI_0: calls X1.optimizeIt()
> -- X1: *fetches* OI_1 and makes calls to optimize it.
> -- OI_1: picks join order {T1} and calls T1.optimizeIt()
> -- T1: returns a cost of *1 MILLION!*.
> -- OI_1: rejects new cost (1 mil > 20) and does nothing.
> -- X1: calls OI_1.getOptimizedCost(), which returns *20*. X1
> then returns 20 to OI_0...this seems WRONG!
> -- OI_0: saves 10783 + 20 = 10803 as new best cost and tells
> X2 to save 10783 and X1 to save 20.
> So in the end, the outer-most OptimizerImpl chooses join order {X2, X1} because it thought the cost of this join order was only 10783, which is better than 64720. However, the _actual_ cost of the join order was really estimated at 1 million--so the outer OptimizerImpl chose (and will generate) a plan that, according to the estimates, was (hugely) sub-optimal.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira