Any chance you could add a paragraph or two and relate this five-way join to
an actual sample query to show just what the permutations might be and the
order that they would be processed? This also might help clarify your use of
'depth first' and 'left deep'.
I'll do my best. You should know that the optimizer looks at so many
potential plans in a five-way join that it's not feasible to show all of
them in an manually-written explanation.
Let's take the following query:
select *
from t1, t2, t3, t4, t5
where t1.c1 = t2.c2
and t1.c3 = t3.c4
and t3.c5 = t4.c6
and t4.c7 = t5.c8
and t1.c9 = 1
and t3.c10 = 2
and t5.c11 = 3
One possible way to execute this query is to take the tables in the order
of the FROM clause. For each row in a table, join it with the matching rows
from the next table to form a set of joined row. The plan would look
something like this (I hope the formatting doesn't get screwed up):
JOIN
/ \
JOIN t5
/ \
JOIN t4
/ \
JOIN t3
/ \
t1 t2
This is a left-deep tree. That is. it's skewed to the left. Let's assume
for the sake of argument that each JOIN node is a nested-loop join. What
this means is that each JOIN node gets a row from its left (outer) table
and probes into its right (inner) table to find all the matching rows. For
all but the leftmost JOIN node, the outer table is also a JOIN. So, at
execution, this plan goes all the way down to the left, gets the first
qualifying row from t1, then finds a matching row in t2. It then puts the
matching rows from t1 and t2 together into a joined row and feeds it up to
the JOIN node above it. This JOIN node uses its outer row to probe into t3
to find a matching row. When it finds such a row, it puts together its
outer and inner rows into a joined row, which it feeds to the JOIN node
above it. It keeps doing this all the way up the plan. When the top JOIN
node finds a matching row in t5, it returns that row from the SELECT statement.
More sophisticated optimizers consider "bushy" trees, which can take shapes
other than the left-deep shape shown above. For example, it might consider
a plan with the following join tree:
JOIN
/ \
JOIN JOIN
/ \ / \
t1 t2 t3 JOIN
/ \
t4 t5
As you can see, the tables are in the same order but the shape of the join
tree is entirely different. As I mentioned in my original mail, bushy trees
are harder to implement but they are good for some types of big
decision-support queries.
Because the Derby optimizer only models left-deep trees, it doesn't have to
model the shape of the tree. All it has to model is the order of the tables
in the tree (since the tree is always the same shape for a given number of
tables). It does this the simple way: by using an array representing the
assignment of tables to positions in the join order.
The basic idea of a cost-based optimizer is to come up with an estimated
cost for all the possible execution plans for a query and to choose the
cheapest plan. The number of possible plans grows with the number of
tables, indexes, join strategies, etc. Most optimizers do something to
reduce the search space, so that for big queries the best plan (or a
reasonable plan) is found in an acceptable length of time. One way the
Derby optimizer prunes its search space is by skipping over plans that it
knows will be more expensive than the best plan it's found so far.
The optimizer does this by depth-first searching. That is, rather than
coming up with a join order for all the tables in the query and then
considering all the access paths for those tables, it adds one table at a
time to the join order and figures out the best access path for that table
(in its current spot in the join order) before going on to add another
table to the join order. While doing this, it keeps track of the cost of
the plan its considering so far. If, when it adds a table to the join
order, it finds that this makes the current plan under consideration more
costly than the best plan found so far, it abandons the consideration of
that table in that position of the join order. By doing this, the optimizer
can avoid considering many join orders. This is important when there are a
lot of tables in the query, because the number of join orders is the
factorial of the number of tables.
For example, let's say that in the sample query given above, the optimizer
has already found a complete plan with an estimated cost of 10000. Now
suppose it is considering the following partial join order:
(outer) t4 - t5 (inner)
Let's say this partial plan has an estimated cost of 2000. Now suppose the
optimizer considers placing the table t1 as the next table in the join order:
(outer) t4 - t5 - t2 (inner)
Note that the query has no direct join clause between t1 and either t4 or
t5. The optimizer would go through all possible access paths for t2 in this
context, and would see that with no useful qualification on the table it
would have to do a full scan of t2 for every outer row resulting from the
join of t4 and t5. If t2 is anything but a very small table, it could be
expensive. Let's say the estimated total best cost for t2 in this position
in the join order is 50000. That would make the total cost of the query
equal to 52000, which is higher than the cost of the best plan found so far
(10000). So it doesn't make sense to look at this join order any further.
Rather than consider the following join orders:
(outer) t4 - t5 - t2 - t1 - t3 (inner)
(outer) t4 - t5 - t2 - t3 - t1 (inner)
the optimizer abandons consideration of any plan starting with t4 - t5 - t2.
That's enough for now. Please let me know if you have any more questions.
- Jeff Lichtman
swazoo-KealBaEQdz4@xxxxxxxxxxxxxxxx
Check out Swazoo Koolak's Web Jukebox at
http://swazoo.com/
|
