Table Order

Did you know that it is possible for the cost-based optimizer to come up with a different execution plan simply because you changed the order of the tables in the from clause.

Although this can happen in real-life with real data and real indexes,  it probably doesn’t happen often. Moreover, when it does happen you might not notice it because it’s likely to happen only in cases where the change doesn’t affect the performance of the query very much.

The reason why it can happen is simple and is based on two details of the mechanics:

1. The optimizer does not examine every possible join order (after all you only need a ten table join to have 3,628,800 (i.e. 10!) possible join orders), so it picks an initial join order and tests a number of permutations based around that order.
2. When deciding an initial join order the optimizer uses the estimated cardinality of each “single table access path” to decide on the first join order to examine; if two tables have the same estimated cardinality then their relative positions in the initial join order is dictated by their order in the from clause. Inevitably, therefore, there will be cases when the set of join orders considered will vary with the order of the tables in the from clause. This, ultimately, makes it possible for different execution paths to appear for different orders in the from clause.

As a though experiment demonstrating how things work consider a four table join and pretend that the optimizer is allowed to examine only 10 join orders.  The first eight join orders examined will be “properly sequenced” and then the optimizer will use two “jump discontinuities” to see if there is a much more efficient search space that should be examined. (This isn’t quite the way the optimizer works but it gives you some idea of the search algorithm.)

If we have tables A, B, C, D appearing in that  order in the from clause and have carefully populated them so that the optimizer decides this is also a good initial join order then the 24 possible join orders – in the order you would (normally) see them in a 10053 trace file –  would be:

A B C D    ** 
A B D C    ** 
A C B D    ** 
A C D B    ** 
A D B C    ** 
A D C B    **      

B A C D    ** 
B A D C    ** 
B C A D 
B C D A 
B D A C 
B D C A        

C A B D    ** 
C A D B 
C B A D 
C B D A 
C D A B 
C D B A          

D A B C    ** 
D A C B 
D B A C 
D B C A 
D C A B 
D C B A          

Following our imagined restriction, however, the optimizer would look at the first 8 paths, then jump to the first of the join orders starting with table C, then the first of the join orders  starting with table D, with the result that the only orders examined are those marked with “**”

But if we change the order of the tables in the from clause to A C B D and the optimizer decides that B and C have the same single table cardinality then the list of 24 permutations will start differently and the optimizer will end up examining the following 10 join orders:

A C B D 
A C D B 
A B C D 
A B D C 
A D C B 
A D B C       

C A B D 
C A D B       

B A C D       

D A C B      

As you can see, the two lists overlap on eight of their 10 join orders but there are two join orders checked in the first list that do not appear in the second list (and vice versa). In one list we examine “B A D C” and “D A B C” in the other we examine “C A D B” and “D A C B”.

Since the change in from clause order has resulted in two different sets of join orders being examined we’ve introduced the possibility that the optimizer will find the cheapest execution path(s) in the areas where the two lists don’t overlap – which is how we can deduce that a change of order in the from clause can mean a change in execution path.

But check the two pairs of join orders that didn’t overlap. All you have to do to get from one to the other is swap B and C. Since our starting assumption was that, from a cardinality perspective at least, tables B and C were so similar that the optimizer could not decide an appropriate initial order for them it is quite likely that the different execution paths will operate at very similar speeds.

You probably won’t spot this anomaly very often. In fact I suspect that you won’t see it at all until you have at least seven, or possibly eight, tables in your query since the optimizer can work through a very large number of permutations very quickly and may easily examine every possible permutation of six or seven tables. On my current laptop, I have an example where the optimizer examines 5,040 permutations (7! … 7 factorial, a.k.a. 7-shriek) in a little less than 2 seconds – dumping a 10053 trace file as it goes. (Interestingly this can happen even when the parameter optimizer_max_permutations is set to 2,000 – the default for 9i – in my example it didn’t stop the optimizer from hacking on to the bitter end).

So, in theory and for perfectly sensible reasons, the optimizer can produce a different execution plan if you switch table orders in the from clause. But it may never happen to you in a ‘real‘ system, and even if it does happen you may not notice a difference in performance.