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
