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 ?

 
select 
	t1.v1 
from 
	t1, t3 
where 
	t1.n2 = 100 
and	t3.n1 = t1.n1 
and	t3.n2 = 100 
and	exists ( 
		select	t2.id 
		from	t2 
		where	t2.n1 = 15 
		and	t2.id = t1.id 
	) 
and	exists ( 
		select	t4.id 
		from	t4 
		where	t4.n1 = 15 
		and	t4.id = t3.id 
	) 
; 

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.

For the next chapter in the treatment of the query, go to this page.

10 Comments »

  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

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

Theme: Rubric. Get a free blog at WordPress.com

Follow

Get every new post delivered to your Inbox.

Join 4,298 other followers