Have you ever wondered how hard the optimizer has to work to produce an execution plan. Consider a simple query with four tables in a straight join, where each table has a few B-tree indexes. How many different executions plans could the optimizer produce.
I won’t guarantee that I’ve covered all the options in the following list (and I’ve deliberately ignored some special cases), even so it’s an extraordinary result.
First: How many join orders are there. The answer is 4! (That’s 4 factorial, not 4 with a following exclamation mark – i.e. 4 x 3 x 2 x 1 = 24).
Second: What about join mechanisms. There are three join mechanisms (nested loop, hash, and merge joins), and given there are 4 tables there are three joins, so we have to multiply the 24 join orders by 3 x 3 x 3 for a total of 27 * 24 = 648.
Finally, we have to worry about the access mechanisms – how do we get the data from each table. There are a surprising number of options here, and I think it’s probably fair to count: full table scan, index scan (I am not going to count full scan, range scan, unique scan and skip scan as different), index fast full scan, index hash join, and-equal (deprecated in 10g, alas), and bitmap conversion – for a total of 6. (Again, I’m not going to distinguish between all the cases of hash join, and-equal, and bitmap conversion)
Since we have 4 tables to acquire data from we have to multiple our current total by 6 x 6 x 6 x 6 = 1,296, for a grand total of 1,296 * 648 = 839,808.
And that’s just a 4-table, simple join! (And that is an exclamation mark).
Isn’t it lucky that the optimizer has all sorts of clever mechanisms for minimising the work it does to optimize SQL.
Footnote: I’ve highlighted the key steps: join order, join mechanism, access mechanism. If you’re going to put hints into SQL, you need to cover all three stages if you want to ensure that the only path available to the optimizer is the one you want – and this means you need at least two hints per table to specify the execution plan completely. And that doesn’t include considerations of the extra hints relevant to subqueries, non-mergeable views, and set operations.
Oracle Scratchpad 
Sorry Jonathan, what’s an “index hash join” – perhaps an hash join fetching rows from the index/indices using “index fast full scan”, or something else ? TIA of course.
Comment by Alberto Dell'Era — December 9, 2006 @ 8:20 pm GMT Dec 9,2006 |
It’s an access path that appeared in 8i although it had to be hinted, or enabled by a hidden parameter, in that version.
It allows Oracle to combine data from several indexes by scanning them (unique, range, skip, or fast full) then hash joining the sets of results on rowids.
It’s another way of getting a result set without having to visit the table.
Comment by Jonathan Lewis — December 9, 2006 @ 8:29 pm GMT Dec 9,2006 |
It’s really mind-boggling stuff — when you start to consider the special cases of star transformation and star query, then all the combinations of bitmap merges on all join columns, on a subset of them etc. then it’s a miracle that the queries ever get executed at all.
Actually it’s an excellent thought process for considering the overhead of hard parsing and the benefits of bind variables also.
Comment by David Aldridge — December 9, 2006 @ 11:58 pm GMT Dec 9,2006 |
thank god plans are stored…too bad they are not all good plans :-(
Comment by kevinclosson — December 10, 2006 @ 12:15 am GMT Dec 10,2006 |
>>How many different executions plans could the optimizer produce.
I guess, this should be in the upper limit of
optimizer_max_permutations value.
Jaffar
Comment by Jaffar — December 10, 2006 @ 6:44 am GMT Dec 10,2006 |
Jaffar, three corrections needed on that remark.
First, that limit applies to the number of join orders (permutations) and not to the mechanisms or access paths (i.e. it only limits the “4!” bit of the calculation)
Second, I believe the limit is “per query block” so that a query with a couple of non-mergeable views, and a couple of filter subqueries could have 5 query blocks, each subject separately to the limit – and the 10g optimizer may then also consider query blocks derived by using transformation methods to combine the initial query blocks.
Third, there are cases where that limit is ignored anyway – I have an example where the optimizer worked through 5,040 join orders even though the parameter was set to 2,000.
Comment by Jonathan Lewis — December 10, 2006 @ 8:38 am GMT Dec 10,2006 |
Thanks for the clarifications.
Regarding your third point, why do then Oracle put an upper limit/hard limit?
It remaind me another parameter of oracle, which is, pga_aggregate_target. There are possibilities where oracle aquires more value than the specified value.
Is this so with optimizer_max_permutations?
Jaffar
Comment by Jaffar — December 10, 2006 @ 8:55 am GMT Dec 10,2006 |
Jaffar, the pga_aggregate_target has to be soft – since you can’t stop processes from demanding some memory unless you crash them; and the very name indicates that there the limit is a ‘soft’ one.
In the case of optimizer_max_permutations, it is possible that the example I have is a bug; it is possible that it is a deliberate special case (my example appears when a query is hinted into a star transfomation). Bear in mind that the official (Server Reference Guide 9i) documentation of the parameter is wrong anyway – so how can we know what the parameter is really supposed to do ?
Comment by Jonathan Lewis — December 10, 2006 @ 2:45 pm GMT Dec 10,2006 |
Jonathan, if I remember correctly, when we enable 10053 event, the trace gives the list parameters and their values used by the Optimizer and you see this parameter as well.
Have you try to enable the 10053 event on your example to find out what is the value for this parameter?
I am just curious becuase its a special case.
Jaffar
Comment by Jaffar — December 10, 2006 @ 2:53 pm GMT Dec 10,2006 |
Jaffar, I had to be running the 10053 to determine how many join orders the optimizer examined – so I did check that the parameter was set to 2,000 at the same time.
Comment by Jonathan Lewis — December 10, 2006 @ 3:05 pm GMT Dec 10,2006 |
Jonathan, please consider that not all cases are available in real life, some combinations are naturally excluded by remaining parts of sql statement, object configuration and available statistics, what makes a number of permutations much smaller, however big enough to cost much.
Comment by Joachim Rupik — December 11, 2006 @ 7:49 am GMT Dec 11,2006 |
Joachim, On the contrary, nothing is naturally excluded. Things are excluded because the optimizer does the arithmetic that excludes them and, as I pointed out, it “has all sorts of clever mechanisms for minimising the work”.
See Chapter 14 of Cost Based Oracle Fundamentals for a few examples of the clever mechanisms.
Comment by Jonathan Lewis — December 11, 2006 @ 8:09 am GMT Dec 11,2006 |
Jonathan, Yes I know, but please notice when bitmaps are not available won’t be taken into consideration any bitmap operation – that is a kind of a clever mechanisms for minimizing the work.
Comment by Joachim Rupik — December 11, 2006 @ 9:02 am GMT Dec 11,2006 |
Joachim, if you check carefully you will see that the initial specification said: “where each table has a few b-tree indexes” deliberately excluding bitmaps. Then the join mechanism I mentioned was: “and bitmap conversion – for a total of 6”.
You are perhaps not familiar with the fact that the optimizer can do a btree/bitmap conversion even in the complete absence of any bitmap indexes.
Comment by Jonathan Lewis — December 11, 2006 @ 10:16 am GMT Dec 11,2006 |
So what replaces AND_EQUAL in 10g+??
Comment by Jason Bucata — December 11, 2006 @ 4:14 pm GMT Dec 11,2006 |
Jason, I can’t say. But I suspect the idea is that bitmap conversion should make and-equal redundant, since (a) it isn’t restricted to equality on single-column indexes and (b) it isn’t restricted to the arbitrary limit that and-equal has of five indexes. Unfortunately, bitmap indexes and the bitmap conversion are not available if you’re running Standard Edition.
Comment by Jonathan Lewis — December 11, 2006 @ 4:48 pm GMT Dec 11,2006 |
[…] Jonathan Lewis poses a very interesting question: Have you ever wondered how hard the optimizer has to work to produce a plan ? […]
Pingback by in praise of CBO » Andy C — December 11, 2006 @ 9:49 pm GMT Dec 11,2006 |
[…] Pragmatic solution – put a stack of hints into the SQL. […]
Pingback by Meaningless Keys « Oracle Scratchpad — December 29, 2006 @ 6:21 pm GMT Dec 29,2006 |