DERBY-3288
Some (simplified)
background:
-----------------------------
As the optimizer tries to
find the best join order for a given query, it tries out various join order
permutations for the Optimizables (aka FromTables) in the FROM list of the SELECT
node.
After preprocessing and
subquery flattening has occurred, the SELECT list for the query in the
description of this issue ends up with the following FROM list:
select ...
from ...{
HalfOuterJoin (HOJ), FromTable (TAB_D), FromTable (TAB_V) }
/ \
JoinNode TAB_A
/ \
TAB_B TAB_C
where ...
So the optimizer will try
out various orderings of HOJ, TAB_D, and TAB_V until it finds the order that is
cheapest.
It's possible that, for some
queries, one Optimizable will have a dependency on another Optimizable. Or put differently, it may be the case that
one Optimizable *MUST* appear before another Optimizable in the join order in
order to ensure correct results.
Whenever the optimizer is about to place an Optimizable in the join
order, it first checks the dependencies to see if such placement is
"legal".
For the query given in this
issue, Optimizable TAB_D has a dependency on HOJ, and thus HOJ must always
appear *before* TAB_D in the join order. This dependency comes from the fact
that we have a WHERE EXISTS clause-- but the specifics aren't as important as
the fact that a dependency does exist.
Enforcement of dependencies
is done through a field call "assignedTableMap", in which bits are
set for each Optimizable that has a position within the currently proposed join
order. The bits are set when the
Optimizable is placed into the join order.
So if the current join order is:
{ HOJ, TAB_V, - }
then assignedTableMap will have
bits set to represent HOJ and TAB_V.
When it comes time to place TAB_D into the join order, the optimizer
will first make sure that the bits for all tables on which TAB_D depends appear
in assignedTableMap. If that's not the
case then TAB_D will be not be placed and the optimizer moves on to another
join order.
As part of
"iteration" through the join orders, the optimizer has to
"pull" Optimizables from the the join order before re-placing them in
a different order. As an example, in
order to get from:
{ HOJ, TAB_V, TAB_D
}
to
{ HOJ, TAB_D, TAB_V}
the optimizer will first pull TAB_D
from the join order, then it will pull TAB_V, then it will place TAB_D, and
finally place TAB_V. I.e.:
{ HOJ, TAB_V, - }
{ HOJ, -, - }
{ HOJ, TAB_D, - }
{ HOJ, TAB_D, TAB_V
}
The general sequence of
events when adding Optimizables to the join order is as follows:
[ Let "k"
represent the position of the most recently placed Optimizable
in the join order.
]
1. See if current join order (up through [k],
inclusive) is
more expensive
than the best join order so far.
a ==> If it's
cheaper, or if there is no "best join order"
so far, then
find the next available position in
the current
join order; let that be our new "k".
b ==>
Otherwise, leave "k" as it is: we'll try to find another
optimizable
to put at position "k" in the join order (i.e.
we're going
to effectively "replace" whatever Optimizable
is currently
at position "k" with a different one).
2. Find the next available Optimizable whose
dependencies are all
satisifed by
assignedTableMap. Call it NEXT_OPT.
3. See if there is already an Optimizable at
position k. (If we
reached
"1.b" above then this *will* be the case). If so,
pull that
Optimizable from the join order. Call
the pulled
Optimizable PULLED_OPT.
4. Update assignedTableMap to reflect the
removal of PULLED_OPT
from the join
order.
5. Place NEXT_OPT in the join order.
6. Update assignedTableMap to reflect the
addition of NEXT_OPT
to the join
order.
7. Cost-based optimization to see cost of
join order so far
(up through
position [k], inclusive). Then back to #1.
The Problem:
------------
The bug that underlies this
Jira issue is related to step 1.b: namely, the fact that "k", our
current position in the join order, does *NOT* change when we short-circuit a
join order means that when we reach step 2, we're looking for an Optimizable
NEXT_OPT to *replace* the Optimizable at position k (call it
"REJECTED_OPT"). That is,
placement of NEXT_OPT (step 5) will only occurr after REJECTED_OPT has been
removed from the join order (step 3).
But that said, when we
search for a new NEXT_OPT as part of Step 2, we look for the next available
Optimizable "whose dependencies are all satisified by
assignedTableMap". Since removal of
REJECTED_OPT does not get reflected in assignedTableMap until Step 4, the bits
corresponding to REJECTED_OPT will >> REMAIN SET << while we search
for NEXT_OPT. This ultimately means that
we can end up filling position "k" in the join order with a NEXT_OPT
that depends on REJECTED_OPT--and then subsequently remove REJECTED_OPT from
the join order to put NEXT_OPT in its place.
So in the end, the requirement that REJECTED_OPT appear in the join
order before NEXT_OPT is broken, and we end up with incorrect results.
To illustrate this more
concretely, let's go back to the query given for this issue. Assume we've already tried out the join order
{ HOJ, TAB_D, TAB_V } and it has an estimated cost of
"1934". Notice how TAB_D
appears after (later in the join order than) HOJ, so TAB_D's dependency on HOJ
is satisfied.
Then we move a little
further in the optimization and eventually end up with a partial join order of { TAB_V, HOJ, - }, whose estimated cost is
"160303". "k" is 1 at this point because the most recently placed
Optimizable was HOJ at position 1 (join order positions are zero-based). assignedTableMap at
this point references the Optimizables in the join order, i.e. [TAB_V, HOJ].
We'll try out a new join
order as follows:
[ Let k be 1 -- i.e.
second position in the join order. ]
1. Current join order up through k is the
cost of
{ TAB_V, HOJ, -
}, which is estimated to be "160303".
Since that's more expensive than
"1934", we go to step 1.b:
1.b ==> Leave
k at "1" (second position in the join order).
2. Next available Optimizable is TAB_D (it's
the only one
that is not yet
in the join order). We see that TAB_D
has a dependency
on HOJ--but since HOJ is represented
in assignedTableMap,
we say that the dependency is
satisfied. (This
is wrong).
3. We see that there is already an
Optimizable at position k--
namely, HOJ. So we pull HOJ from the join order and it
becomes our
PULLED_OPT.
4. We update assignedTableMap to reflect the
fact that we
pulled HOJ from
the join order. So assignedTableMap
how just has
[TAB_V].
5. We place our NEXT_OPT, i.e. TAB_D, into
the join order.
6. We update assignedTableMap to reflect the
addition of
TAB_D to the join order. So it now becomes [TAB_V, TAB_D].
7. Cost-based optimization of the join order
{TAB_V, TAB_D, - }.
This is wrong: we ended up
placing TAB_D into the join order when HOJ was not present, which violates
TAB_D's dependency. It turns out that
the final join order of { TAB_V, TAB_D, HOJ } is
estimated to be "cheapest", so that's what
Note that the
"short-circuit" logic used for step 1.b was not correct until
DERBY-1357--so prior to DERBY-1357, we would never actually reach
"1.b", and hence this bug was not exposed until DERBY-1357 was fixed.
The Solution:
-------------
From what I can tell, the
easiest way to resolve this problem is to expand step 1.b by saying that, in
addition to leaving k unchanged, we explicitly remove the Optimizable at
position k from assignedTableMap--instead of waiting until step 4 to do
so. Then when we try to find the next
available Optimizable in step 2, we'll notice that TAB_D's dependency on HOJ is
no longer satisified, which means the join order { TAB_V,
TAB_B, HOJ } will be rejected as invalid.
So the optimizer will be forced to find another join order--one that is
legal and that returns the correct results…