db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Army <qoz...@sbcglobal.net>
Subject [OPTIMIZER] OptimizerImpl "best plans" for subqueries?
Date Fri, 17 Feb 2006 18:37:05 GMT
As I was tracing through code for some work that I'm doing for DERBY-805, I came 
across a scenario in the Optimizer that looks to me like it could be a bug.  I'm 
wondering if anyone out there can either confirm that this is a bug or else help 
correct my understanding of how this is supposed to work...

An example of a scenario that's causing me to wonder is that of unflattened 
subqueries.  Ex:

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;

The first thing to note is that 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"

These OptimizerImpls are "created" from calls to the getOptimizer() method on 
the respective SelectNode.  I put "created" in quotes because the 
OptimizerImpl's are only created on the first call to SelectNode.getOptimizer(); 
thereafer, any calls to that method will return the same instance of the 
OptimizerImpl that was created the first time.

Each OptimizerImpl stores information about the best plan that it has found so 
far, namely best join order, best cost (for that join order), and best plan type 
("normal" or "sort avoidance").  I use the term "bestPlan" to refer these three 
values collectively, though that particular field doesn't actually exist in the 
code.

All of that said, I _think_ that bestPlan is intended to hold the best plan seen 
by the OptimizerImpl for this round of optimizing, where "this round" means 
"from the last time a call to getOptimizer() returned this OptimizerImpl until a 
call to this OptimizerImpl's getNextPermutation() method returns FALSE."  For 
every bestPlan that the OptimizerImpl finds, it calls "rememberAsBest" on each 
Optimizable in its list, which means that trulyTheBestAccessPath for each 
Optimizable will be updated to hold that Optimizable's best plan with respect to 
the OptimizerImpl's current join order.

When I was tracing through code for pushing predicates, though, I came to the 
realization that either:

  1) my definition of a "round" is incorrect, or
  2) the definition is correct, but the implementation is incorrect.

The reason I believe this to be the case is that bestPlan is never
reset.  For non-nested queries this isn't problem because the outer
SelectNode only calls "getOptimizer()" one time and then fetches the
bestPlan after that:

	optimizer = getOptimizer(fromList,
			wherePredicates,
			dataDictionary,
			orderByList);
	optimizer.setOuterRows(outerRows);

	/* Optimize this SelectNode */
	while (optimizer.getNextPermutation())
	{
		while (optimizer.getNextDecoratedPermutation())
		{
			optimizer.costPermutation();
		}
	}

	/* Get the cost */
	costEstimate = optimizer.getOptimizedCost();

With subqueries, though, a SelectNode will call getOptimizer() once for _every_ 
complete join order analyzed by the outer OptimizerImpl.  I think the inner 
OptimizerImpl is then supposed to "start fresh" and return the best permutation 
for the inner OptimizerImpl with respect to the _current_ permutation of the 
_outer_ query.  That's what my above definition of "this round" translates to.

However, since we never reset the inner OptimizerImpl's bestPlan, it's possible 
that _all_ permutations of the inner OptimizerImpl will be rejected because they 
are more expensive than a previous bestPlan from a previous permutation of the 
outer query.  That means that the call to optimizer.getOptimizedCost() will 
return the bestPlan found for an outer query join order that is _not_ the 
current join order.  As explained below, this can cause the outer-most optimizer 
to choose a plan that is not optimal.

Let's walk through this using the above example:

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;

Note that I ran this query against a clean codeline and did actually witness the 
behavior described here (T1 had 1 row, 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.

As it turned out, the actual difference between {X1,X2} and {X2,X1} for this 
particular query was minimal, so the behavior wasn't a big deal (I guess the 
estimates were off--but that's not the point ;)

But in the grand scheme of things, this behavior looks WRONG to me.  I think the 
correct thing is to reset an OptimizerImpl's best plan whenever it is "fetched" 
as part of a getOptimizer() call.  If we did that, then instead of rejecting the 
new cost of 1 million, OI_1 would have accepted it because it was the first plan 
that it found for "this round".  Then when X1 called "OI_1.getOptimizedCost()", 
it would have seen how bad the plan really was and propagated that information 
back to OI_0, who then would have rejected join order {X2,X1} in favor of {X1,X2}.

That said, I made what I thought was a simple change to address this 
issue--namely, resetting the bestPlan for an Optimizer on every call to 
getOptimizer()--and ran derbylang.  I saw four diffs: two seemed okay (rows had 
changed order, which was fine) but two were definite failures: one in 
refActions1.sql and one in views.sql; both failed because with "ERROR 42Y69: No 
valid execution plan was found for this statement."

Keep in mind: this was on a _clean_ codeline, so my predicate pushing logic for 
DERBY-805 isn't an issue here.

Can anyone comment on this behavior?  Namely, can I get feedback as to whether 
my interpretation of what makes a "bestPlan"--meaning the best plan in "this 
round"--is correct?  And if so, is this a bug in the current Derby optimizer? 
And if so, any ideas as to how this could be causing the two new failures in 
view.sql and refActions1.sql?

Any input/reactions/feedback/corrections at all would be greatly appreciated...

Thanks,
Army


Mime
View raw message