Tony’s Oracle Tips

December 27, 2008

Bushy Joins

Filed under: SQL Fun — tonyhasler @ 1:05 pm

Before I begin I should say that I am not the first to write on this subject.  There are numerous articles on the web on this subject.  This is just my way of thinking about all of this.

As I recently learned from Christian Antognini’s excellent book “Troubleshooting Oracle Performance”
there are four types of join trees: left-deep, right-deep, zig-zag and bushy.  Consider this SQL statement:


select count(*) from t1,t2,t3,t4 where t1.c1=t2.c2
and t2.c2=t3.c3 and t3.c3= t4.c4 ;

To keep things simple I will assume hash joins and full tablescans throughout.

It is far easier to see the difference between the types of joins from a diagram rather than with the output of autotrace or dbms_xplan:
Left-deep join tree:


       H
      / \
     H   t4
    / \
   H   t3
  / \
t1   t2

The left argument of the join operation is known as the “build” or “driving” table and the right argument is known as the “probe” table.  The optimizer has traditionally favoured this type of join, although in 11g I have found other tree types are selected even when the cost of the left-deep tree is identical.  One advantage of this scheme is that there are at most two workareas in use at any one time:  A hash area is built with the rows from t1 and then t2 is probed.  The join results produced are used to generate a second hash area.  However, the probe of t3 doesn’t begin until the probe of t2 is complete and the workarea containing t1 is released.

The right-deep tree looks like this:


   H
  / \
t4   H
    / \
   t3  H
      / \
     t1  t2

Here there are three workareas.  The more tables to be joined the more workareas.  In this example workareas are setup for t1, t3, and t4.  Table t2 is probed and the results matched with t1.  Each matching row is then matched with t3 and then t4.

It seems to me that the benefit of this scheme comes when the result of a join operation is larger than the size of the row sources being joined.  For example suppose that all four tables had 100 rows and the value of all joined columns was the same.  The join of any two tables would generate 10,000 rows and then 1,000,000 rows with the query finally returning a result of 100,000,000.  If you use a right-deep tree you get three workareas but they only contain 100 rows each.

A zig-zag tree is just a combination of the above:


   H
  / \
t4   H
    / \
   H   t3
  / \
t1   t2

You can force a specific tree by the use of the leading, swap_join_inputs and no_swap_join inputs hints.  The above tree can be forced as follows:
 


select

/*+

leading (t1 t2 t3 t4)
no_swap_join_inputs(t2)
no_swap_join_inputs(t3)
swap_join_inputs(t4)

use_hash(t2)
use_hash(t3)
use_hash(t4)

Note that no_swap_join_inputs is only available in 10g.

*/

count(*) from t1,t2,t3,t4 where t1.c1=t2.c2 and t2.c2 = t3.c3 and t3.c3 = t4.c4 ;

Incidentally, my experiments suggest that the swap_join_inputs and no_swap_join_inputs hints only work with hash joins.  If anybody has ever seen a right-deep or zig-zag tree with merge, nested loop, or cartesian join I would love to know!

There are a few basic points that confused me when I started learning about hints that nobody seems to mention. 

These are;

1.  A left-deep tree is assumed as the starting point.  This is how you identify the join order for the leading hint.
2.  A join is identified by the table operand.  In the case of the first join it is the probe (right) table.  So the use_hash hints do not apply to the table but to the join operation of which it is a part.
3.  The use_hash, use_merge and use_nl hints can be abbreviated by listing all the tables in one hint.  This doesn’t work for the swap_join_inputs or no_swap_join_inputs hints.

There are, however, a bunch of join trees that we haven’t discussed yet.  What about this one:


       H
      / \
     /   \
    /     \
   H       H
  / \     / \
t1   t2 t3   t4

In this case we have one join operation where both row sources are intermediate row sources.  One immediate observation about this join tree is that we will have difficulty identifying this join in our hints.  in fact, the

CBO never considers this type of join, known as a bushy join, unless it is forced to do so.  The only time that it is forced to do so, as far as I know, is when at least one of the join operands is an un-mergeable view.

Consider the following query:


select count(*) from t1, t2, t3, t4
where t1.c1=t2.c2 and t3.c3=t4.c4 and t1.c1+t2.c2=t3.c3+t4.c4;

A human being can instantly see that a bushy join is probably the best plan.  However, the CBO will not consider a bushy join at all (and neither will the SQL Tuning Adviser by the way).  The only way to force what may be the right plan is to both rewrite the code and also to add hints to prevent the CBO from rewriting the code back:


with t1t2 as
(
select

/*+

leading(t1 t2)
no_swap_join_inputs(t2)
use_hash(t2)
no_merge

*/

t1.c1,t2.c2 from t1,t2 where t1.c1=t2.c2

),
t3t4 as
(
select

/*+

leading(t3 t4)
no_swap_join_inputs(t4)
use_hash(t4)
no_merge

*/

t3.c3,t4.c4 from t3,t4 where t3.c3=t4.c4

)

select

/*+

leading(j1 j2)
use_hash(j2)
no_swap_join_inputs(j2)

*/

count(*) from t1t2 j1,t3t4 j2 where j1.c1+j1.c2=j2.c3+j2.c4;

If you do this the CBO may well estimate the cost to be less than that of any plan that it may have come up with on

its own.  If you create the four tables as follows:

create table t1 as select 1 c1 from dual connect by level <= 100;
create table t2 as select 1 c2 from dual connect by level <= 100;
create table t3 as select 1 c3 from dual connect by level <= 100;
create table t4 as select 1 c4 from dual connect by level <= 100;
exec dbms_stats.gather_table_stats(user,'T1');
exec dbms_stats.gather_table_stats(user,'T2');
exec dbms_stats.gather_table_stats(user,'T3');
exec dbms_stats.gather_table_stats(user,'T4'); 

The the CBO unhinted comes up with this right-deep tree in 11g:


--------------------------------------------------------------------------------
| Id  | Operation               | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |      |     1 |    12 |   576  (80)| 00:00:07 |
|   1 |  SORT AGGREGATE         |      |     1 |    12 |            |          |
|*  2 |   HASH JOIN             |      |  1000K|    11M|   576  (80)| 00:00:07 |
|   3 |    TABLE ACCESS FULL    | T4   |   100 |   300 |     3   (0)| 00:00:01 |
|*  4 |    HASH JOIN            |      |  1000K|  8789K|   121   (5)| 00:00:02 |
|   5 |     TABLE ACCESS FULL   | T2   |   100 |   300 |     3   (0)| 00:00:01 |
|   6 |     MERGE JOIN CARTESIAN|      | 10000 | 60000 |   113   (0)| 00:00:02 |
|   7 |      TABLE ACCESS FULL  | T1   |   100 |   300 |     3   (0)| 00:00:01 |
|   8 |      BUFFER SORT        |      |   100 |   300 |   110   (0)| 00:00:02 |
|   9 |       TABLE ACCESS FULL | T3   |   100 |   300 |     1   (0)| 00:00:01 |
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("T3"."C3"="T4"."C4")
       filter("T1"."C1"+"T2"."C2"="T3"."C3"+"T4"."C4")
   4 - access("T1"."C1"="T2"."C2")

With the hints this is the result:


------------------------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    52 |    18  (34)| 00:00:01 |
|   1 |  SORT AGGREGATE       |      |     1 |    52 |            |          |
|*  2 |   HASH JOIN           |      |  1000K|    49M|    18  (34)| 00:00:01 |
|   3 |    VIEW               |      | 10000 |   253K|     7  (15)| 00:00:01 |
|*  4 |     HASH JOIN         |      | 10000 | 60000 |     7  (15)| 00:00:01 |
|   5 |      TABLE ACCESS FULL| T1   |   100 |   300 |     3   (0)| 00:00:01 |
|   6 |      TABLE ACCESS FULL| T2   |   100 |   300 |     3   (0)| 00:00:01 |
|   7 |    VIEW               |      | 10000 |   253K|     7  (15)| 00:00:01 |
|*  8 |     HASH JOIN         |      | 10000 | 60000 |     7  (15)| 00:00:01 |
|   9 |      TABLE ACCESS FULL| T3   |   100 |   300 |     3   (0)| 00:00:01 |
|  10 |      TABLE ACCESS FULL| T4   |   100 |   300 |     3   (0)| 00:00:01 |
------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("J1"."C1"+"J1"."C2"="J2"."C3"+"J2"."C4")
   4 - access("T1"."C1"="T2"."C2")
   8 - access("T3"."C3"="T4"."C4")

As you can see even the CBO agrees that the human being has beaten it on this occasion by reducing the cost from 576 to 18.

Advertisements

Create a free website or blog at WordPress.com.