Re: Join order and access path

[Jeffrey Lichtman]

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
                                [EMAIL PROTECTED]
                                Check out Swazoo Koolak's Web Jukebox at
                                http://swazoo.com/