Oracle Scratchpad

January 24, 2007

Left-deep trees

Filed under: Execution plans — Jonathan Lewis @ 11:42 pm BST Jan 24,2007

In response to an article on hinting, one reader asked me to describe what I meant by the terms “left-deep” and “bushy” when talking about optimization strategies.

To demonstrate the differences, I created a couple of stored outlines in a 9.2 database and used the OEM Outline Manager to generate the pictures that I’ve pasted below. To read a tree, walk around it in an anti-clockwise direction, ignoring nodes on the way down and “operating” them on the way back up. (But don’t operate them as you go “under” them, only as you go up, passing them to their right).

Left Deep

Walk down to the bottom left corner: we start with a tablescan of t4, then use an index into t3, joining the tables with a nested loop. We scan table t2 to join it with a merge join, then use an index into t1 to join it using a nested loop.

left_deep.jpg

Bushy

Again we head for the bottom-left corner, but in this case we start with a tablescan of t2 and use an index into t1 to join it with a nested loop join. Then we leave the join result set in suspension, and walk on round the tree to do a tablescan of t4, using an index into t3 to join it using a nested loop. This gives us a second we join result set, which we join to the first result set using a hash join.
bushy.jpg

As you can see, the typical left-deep tree will maximise the depth of the tree, with nothing but little twiglets branching to the right as you build it. The typical bushy tree will be stubbier with branchng bits sticking out all over the place.

8 Comments »

  1. Thanks for the explanation Jonathan, all has become clear.

    Comment by Graham — January 25, 2007 @ 10:09 am BST Jan 25,2007 | Reply

  2. Hi , in want cases we will have bushy tree ? does it mean that in those cases parallel execution code help us (one for each side ) ?

    Comment by amihay gonen — January 25, 2007 @ 11:23 am BST Jan 25,2007 | Reply

  3. Amihay, in general you will not get “bushy trees” unless you hint them. The optimizer always tries to transform your query to a “left-deep” tree.

    Interesting idea about the parallelism – but I don’t think it can work like that. However, the example I ran in parallel did exhibit some interesting “out of order” behaviour.

    Comment by Jonathan Lewis — January 26, 2007 @ 3:33 am BST Jan 26,2007 | Reply

  4. Hi, Can you please explain further how to go about improving performance of SQLs that need a bushy tree execution plan? I have been trying to tune some SQLs, and more or less all the badly performing ones needed bushy trees by nature.

    Is hints the only option? Or can CBO create nice bushy execution plans if we have corresponding composite indexes?

    Comment by Krishna R — February 23, 2007 @ 7:43 am BST Feb 23,2007 | Reply

  5. Krishna, I don’t think the optimizer can generate “bushy-tree” plans. It will always try to transform to a “left-deep”.

    The only option you have is to use hints – specifically the /*+ no_merge */ hint, or subquery factoring with the /*+ materialize */ hint.

    I will be writing about this in the future as part of my mini-series on Join Ordering.

    Comment by Jonathan Lewis — February 23, 2007 @ 7:58 am BST Feb 23,2007 | Reply

  6. I have seen cases where in a bushy tree based query evaluation is much better than a left deep tree based one. Am I right? Please correct me if I am wrong

    Comment by Smitha — March 18, 2009 @ 11:42 am BST Mar 18,2009 | Reply

    • Smitha

      It is perfectly feasible to find bushy tree plans that perform (much) better than left-deep trees. This is what makes the no_merge and push_pred hints so very important.

      Comment by Jonathan Lewis — March 22, 2009 @ 12:59 am BST Mar 22,2009 | Reply

  7. For those asking, here is an specific example I ran into that shows a bushy plan to be much less expensive than a left deep

    http://sites.google.com/site/embtdbo/sql-tuning-1#TOC-Query-3

    (main point of post was showing Visual SQL Tuning but the result was rewriting the query into two subqueries with NO_MERGE hint

    Comment by Kyle Hailey — May 30, 2010 @ 10:14 am BST May 30,2010 | Reply


RSS feed for comments on this post.

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,257 other followers