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

**and**

*t1***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.**

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

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 BST Jan 24,2007 |

@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 BST Jan 24,2007 |

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 BST Jan 24,2007 |

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 BST Jan 24,2007 |

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 BST Jan 24,2007 |

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

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

Or yeah, that was a typo.

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

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 BST Feb 5,2007 |

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 BST Feb 6,2007 |

[...] 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 BST Mar 5,2007 |