Oracle Scratchpad

January 24, 2007

Join Ordering – 1

Filed under: CBO,Execution plans,Hints,Oracle,Tuning — Jonathan Lewis @ 12:02 am GMT Jan 24,2007

Here’s a little puzzle about execution plans. How many (significantly) different strategies are there for the following SQL – and how many of them will the Cost Based Optimizer be unable to find without being explicitly hinted ?

        t1, t3
        t1.n2 = 100 
and     t3.n1 = t1.n1 
and     t3.n2 = 100 
and     exists ( 
                from    t2 
                where   t2.n1 = 15 
                and = 
and     exists ( 
                from    t4 
                where   t4.n1 = 15 
                and = 

I’m not expecting answers, by the way, it’s just a little query for you to play with. I’ll be making further comments about it later.

Updated 25th Jan: I’ve added a simple predicate to both t1 and t3 to make give some of the options a little more visibility, as some of the potential execution strategies are a little unbelievable if you don’t have any filtering on these two tables.



  1. Assuming that all the subqueries are unnested, and that tuple iteration execution semantics is not really different from nested loop, we should have 14 different executions (4th Catalan number). So the answer is 14 minus the number of join orders appearing in the 10053 trace.

    Comment by Mikito Harakiri — January 24, 2007 @ 3:30 am GMT Jan 24,2007 | Reply

  2. @Jonathan

    A question on the exists sub-query.

    In the sub-query, you write something like “select column”, I’m used to write something like “select *”.

    I saw other forms: “select 1” and even “select NULL” (this one in Oracle documentation).

    Are there any performance difference?

    Thank you.

    Comment by Antonio — January 24, 2007 @ 8:13 am GMT Jan 24,2007 | Reply

  3. Mikito, I was planning to be rather more informal; however, since you’ve mentioned Catalan numbers, why isn’t the starting value (Catalan(3) * 4!). Catalan(3) as the number of arrangements of a tree with 4 “leaf points”, and 4! as the possible permutations of the tables around the “leaf points”. Am I missing something like a commutativity assumption that changes the formula ?

    Antonio – there shouldn’t be any performance difference.

    Comment by Jonathan Lewis — January 24, 2007 @ 10:58 am GMT Jan 24,2007 | Reply

  4. That’s right, how the supposed answer 14 can be less than 4! ? Therefore, for unnested and merged plans there are 5*4! plans but the optimizer looks into only 5! of them. Some plans which are not unnested, howewer, are equivalent to bushy plans — this is one of the reason why unnesting&merging can potentially miss a good plan.

    Comment by Mikito Harakiri — January 24, 2007 @ 5:41 pm GMT Jan 24,2007 | Reply

  5. Mikito, what am I missing? Isn’t 5*4! the same as 5! (= 1*2*3*4*5)? Or was that a typo and you meant “there are 5*4! plans but the optimizer looks into only 4! of them”

    Comment by Wolfgang Breitling — January 24, 2007 @ 6:47 pm GMT Jan 24,2007 | Reply

  6. Catalan(3) = 5, which is a coincidence.

    Comment by Mikito Harakiri — January 24, 2007 @ 6:50 pm GMT Jan 24,2007 | Reply

  7. Or yeah, that was a typo.

    Comment by Mikito Harakiri — January 24, 2007 @ 6:51 pm GMT Jan 24,2007 | Reply

  8. JL, I think if both the subqs are un-nested then we have 4! possible methods. If the subqs are not un-nested then, we have 2! and then the evaluation of the subq. Also if the rules for semi-join applies, then that is another tree.

    On the whole, it depends on new initial join orders also.

    So unless we get a 10053 dump, i dont think we can give a number.

    by the way, apologies for using JL!!!!!!!!!!!!!!!

    Comment by Avanish — February 5, 2007 @ 11:43 am GMT Feb 5,2007 | Reply

  9. Avanish, I wasn’t specifically focusing on what the optimizer can do as on what the best strategy might be. In this 4-table query, there is a join strategy which Oracle’s optimizer won’t even consider (even though it might be the best one) because it it not a ‘left-deep’ strategy.

    I was interested in your comment about the semi-join and the unnesting being different trees. In some tests that I’ve forced onto the optimizer, I got all 24 possible join orders for a query of this type, and some of them included the simple unnesting (in-line view) aproach AND the semi-join approach in the same join order. So I had concluded that there was no ‘separate space’ to distinguish between the two – am I definitely wrong ?

    Comment by Jonathan Lewis — February 6, 2007 @ 7:16 pm GMT Feb 6,2007 | Reply

  10. […] The general structure of the query used was the one I first introduced in the blog item about Join Orders. […]

    Pingback by Web Presentation « Oracle Scratchpad — March 5, 2007 @ 11:45 pm GMT Mar 5,2007 | Reply

RSS feed for comments on this post. TrackBack URI

Comments and related questions are welcome.

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Website Powered by

%d bloggers like this: