Oracle Scratchpad

November 3, 2006

Table Order

Filed under: CBO,Execution plans,trace files,Troubleshooting — Jonathan Lewis @ 8:52 am BST Nov 3,2006

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.

The reason why it can happen is simple. First, the optimizer does not examine every possible join order (after all, you only need a ten table join to have 3,628,800 (viz: 10!) possible join orders). Secondly, when deciding an intial join order, the optimizer uses the cardinality of the single table access path to order the tables; if two tables have the same 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 demonstration of how things work, consider a four table join, and pretend that the optimizer is only allowed to examine 10 join orders.  The first eight join orders are  properly sequenced, and then two ‘jump discontinuities’ are checked 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 carefully constructed so that the optimizer decides that that is also a good initial join order, then the 24 possible join orders – in the order you would see them in a 10053 trace –  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 rules, the optimizer looks at the first 8 paths, then jumps to the first of the join orders starting with table C, then the first of the join orders  starting with table D. The join orders examined are 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 checks, 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 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. A change in 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, 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. I suspect that you won’t see it at all until you have at least seven, or possibly eight, tables in your query as the optimizer can work through a very large number of permutations very quickly and may easily examine every permutation of six or seven tables. On my current laptop, I have an example where the optimizer examines 5,040 permuations (7! … 7 factorial, a.j.a. 7-shriek) in a little less than 2 seconds – dumping a 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 – and 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.

8 Comments »

  1. I guess n tables can provides more than n! joins. With four tables, it could do a ((t1=t2)=t3)=t4 or a (t1=t2)=(t3=t4). a quick test with four empty tables:

    create table w(n number,w number);
    create table x(n number,x number);
    create table y(n number,y number);
    create table z(n number,z number);
    select * from w,x,y,z where w.n=x.n and x.n=y.n and y.n=z.n;
    ------------------------------------------------------------------------------
    | Id | Operation             | Name | Rows | Bytes | Cost (%CPU)| Time       |
    ------------------------------------------------------------------------------
    |  0 | SELECT STATEMENT      |      | 1    | 104   |      9 (12)| 00:00:01   |
    |* 1 |  HASH JOIN            |      | 1    | 104   |      9 (12)| 00:00:01   |
    |  2 |   MERGE JOIN CARTESIAN|      | 1    |  78   |      7 (15)| 00:00:01   |
    |* 3 |    HASH JOIN          |      | 1    |  52   |      5 (20)| 00:00:01   |
    |  4 |     TABLE ACCESS FULL |    W | 1    |  26   |      2  (0)| 00:00:01   |
    |  5 |     TABLE ACCESS FULL |    X | 1    |  26   |      2  (0)| 00:00:01   |
    |  6 |    BUFFER SORT        |      | 1    |  26   |      5 (20)| 00:00:01   |
    |  7 |     TABLE ACCESS FULL |    Z | 1    |  26   |      2  (0)| 00:00:01   |
    |  8 |   TABLE ACCESS FULL   |    Y | 1    |  26   |      2  (0)| 00:00:01   |
    ------------------------------------------------------------------------------

    select * from x,y,z,w where w.n=x.n and x.n=y.n and y.n=z.n;
    -------------------------------------------------------------------------------
    | Id | Operation              | Name | Rows | Bytes | Cost (%CPU)| Time       |
    -------------------------------------------------------------------------------
    |  0 | SELECT STATEMENT       |      | 1    | 104   |      9 (12)| 00:00:01   |
    |* 1 |  HASH JOIN             |      | 1    | 104   |      9 (12)| 00:00:01   |
    |* 2 |   HASH JOIN            |      | 1    |  78   |      7 (15)| 00:00:01   |
    |  3 |    MERGE JOIN CARTESIAN|      | 1    |  52   |      4  (0)| 00:00:01   |
    |  4 |     TABLE ACCESS FULL  |    X | 1    |  26   |      2  (0)| 00:00:01   |
    |  5 |     BUFFER SORT        |      | 1    |  26   |      2  (0)| 00:00:01   |
    |  6 |      TABLE ACCESS FULL |    Z | 1    |  26   |      2  (0)| 00:00:01   |
    |  7 |    TABLE ACCESS FULL   |    Y | 1    |  26   |      2  (0)| 00:00:01   |
    |  8 |   TABLE ACCESS FULL    |    W | 1    |  26   |      2  (0)| 00:00:01   |
    -------------------------------------------------------------------------------


    Interesting is the new hint in 10g called LEADING, which is much
    less aggressive than ORDERED. But in this case, I prefer the ORDERED ;-)

    select /*+ORDERED*/ * from w,x,y,z where w.n=x.n and x.n=y.n and y.n=z.n;
    -----------------------------------------------------------------------------
    | Id | Operation            | Name | Rows | Bytes | Cost (%CPU)| Time       | 
    -----------------------------------------------------------------------------
    |  0 | SELECT STATEMENT     |      | 1    |  104  |     10 (20)| 00:00:01   |
    |* 1 |  HASH JOIN           |      | 1    |  104  |     10 (20)| 00:00:01   |
    |* 2 |   HASH JOIN          |      | 1    |   78  |      7 (15)| 00:00:01   |
    |* 3 |    HASH JOIN         |      | 1    |   52  |      5 (20)| 00:00:01   |
    |  4 |     TABLE ACCESS FULL|    W | 1    |   26  |      2  (0)| 00:00:01   | 
    |  5 |     TABLE ACCESS FULL|    X | 1    |   26  |      2  (0)| 00:00:01   | 
    |  6 |    TABLE ACCESS FULL |    Y | 1    |   26  |      2  (0)| 00:00:01   | 
    |  7 |   TABLE ACCESS FULL  |    Z | 1    |   26  |      2  (0)| 00:00:01   |
    -----------------------------------------------------------------------------

    YMMV

    Comment by Laurent Schneider — November 3, 2006 @ 10:58 am BST Nov 3,2006 | Reply

  2. Laurent,
    It’s going to sound like splitting hairs, but there really are only 4! join orders for a four table join. If you join t1 to t2, and t3 to t4, then join the two result sets, that’s three two table joins. However, your statement is also correct, because it wasn’t exactly the same as my statement – you were talking about ‘four tables’, not a ‘four table join’.

    Your examples with only 4 tables explain why I talked about “real life with real data and real indexes”. If you know what the trap is, you just have to create and join N identical tables to demonstrate the principle.

    In passing, I tried to tidy up your output – but the ‘pre’ command gets stripped out in comments so the white space disappears. But in my tidy versions your 3 join orders show up (despite appearances to the contrary) as:
    W X Z Y
    X Z Y W
    W X Y Z

    William,

    leading() has been around for a long time, but in it’s initial form you specified just the first table in the join order. In 10g, you can specify every single table in the query in the order you want, and if that order can be reached the optimizer will use it. There may be some limitations that block it in special cases, but I haven’t tested it thoroughly yet.

    Comment by Jonathan Lewis — November 3, 2006 @ 11:50 am BST Nov 3,2006 | Reply

  3. Thanks for the update. I remember having used the ORDERED hint to get rid of those MERGE JOIN CARTESIAN + BUFFER SORT.

    Comment by Laurent Schneider — November 3, 2006 @ 2:45 pm BST Nov 3,2006 | Reply

  4. but probably good statistics would have help. It was in 2001 with 9.2.0.2 and a pretty awful db model generated from Java…

    Comment by Laurent Schneider — November 3, 2006 @ 2:49 pm BST Nov 3,2006 | Reply

  5. Do Order of the tables in Joins is relevant with CBO?I have found one controversy article which tells it doesn’t matter.Please clarify doubts.

    http://asktom.oracle.com/pls/ask/f?p=4950:8:::::F4950_P8_DISPLAYID:29986416015789

    Comment by murtuja — November 24, 2006 @ 12:41 pm BST Nov 24,2006 | Reply

  6. Murtuja, if you read the article carefully, you will realise that it answers your question.

    Comment by Jonathan Lewis — November 25, 2006 @ 9:48 am BST Nov 25,2006 | Reply

  7. Hello Sir,

    I have 2 different plan for same SQL with same data. How it possible. i.e. I am joining 3 tables (table1 has 60,920 records, table2 has 1,165,155, table3 has 11,115,085 records) this data remain same since last one month, when i check plan yesterday I got 46K cost and time =9 minutes today is it showing 135K cost and time=28 minutes. why that much big change? there is no change in data/query. One more observation is yesterday it was doing hash join between table2 to table1 but today it is doing table1 to table2 (The orders in the plan has been changed), this is the exact reason? how can i tell optimizer that do has join table2 to table1 and then result of this to table3?

    Comment by Silvance — August 6, 2008 @ 5:21 pm BST Aug 6,2008 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 3,508 other followers