Join Surprise

Imagine I have a simple SQL statement with a “where” clause that looks like this:

        t2.id1(+) = t1.id1
and     t2.id2(+) = t1.id2

Would you expect it to run several times faster (25 minutes instead of a few hours) when the only change you made was to swap the order of the join predicates to:

        t2.id2(+) = t1.id2
and     t2.id1(+) = t1.id1

You may recall that a couple of years ago I wrote about some bugs in the optimizer and pointed you to a blog article by Alberto Dell’Era that demonstrated an anomaly in cardinality calculations that made this type of thing possible. But here’s an example which has nothing to do with cardinality errors. We start with a suitable dataset – initially running on 11.1.0.6 (though the anomaly is still present in 19c)

rem
rem     Script:         merge_order_anomaly.sql
rem     Author:         Jonathan Lewis
rem     Dated:          Nov 2010
rem
rem     Last tested 
rem             19.3.0.0        -- still sub-optimal
rem

create table t1
as
with generator as (
        select
                rownum id 
        from dual 
        connect by 
                rownum <= 1e4 -- > comment to avoid wordpress format issue
)
select
        trunc(dbms_random.value(1,1000))        id1,
        trunc(dbms_random.value(1,1000))        id2,
        lpad(rownum,10,'0')                     small_vc,
        rpad('x',1000)                          padding
from
        generator       v1
;

create table t2
as
with generator as (
        select  --+ materialize
                rownum id 
        from dual 
        connect by 
                rownum <= 7 -- > comment to avoid wordpress format issue
)
select
        t1.id1,
        t1.id2,
        v1.id,
        lpad(rownum,10,'0')     small_vc,
        rpad('x',70)            padding
from
        t1              t1,
        generator       v1
;


begin
        dbms_stats.gather_table_stats(
                ownname          => user,
                tabname          =>'T1',
                method_opt       => 'for all columns size 1'
        );

        dbms_stats.gather_table_stats(
                ownname          => user,
                tabname          =>'T2',
                method_opt       => 'for all columns size 1'

        );
end;
.

This data set models a problem – stripped to the bare essentials – that I came across at a client site some time ago. We have a “parent/child” relationship between the tables (although I haven’t declared referential integrity in this example) with roughly seven child rows per parent row. The parent rows are quite long, the child rows are quite short. Some parents may not have children (although in this data set they all do).

We now run a report that generates data for a number-crunching tool that extracts all the data from the tables, using an outer join so that parent rows don’t get lost. For various reasons the tool wanted the data sorted in a certain order so there’s also an order by clause in the query. I’m going to show you a model of the original query – first unhinted, then hinted to use a merge join:

prompt  ================================
prompt  Join opposite to order - default
prompt  ================================

select
        t1.padding, 
        t2.padding
from
        t1, t2
where
        t2.id1(+) = t1.id1
and     t2.id2(+) = t1.id2
order by
        t1.id2,
        t1.id1
;


---------------------------------------------------------------------------------------
| Id  | Operation              | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |      | 10000 |    10M|       |  3720   (1)| 00:00:45 |
|   1 |  SORT ORDER BY         |      | 10000 |    10M|    22M|  3720   (1)| 00:00:45 |
|*  2 |   HASH JOIN RIGHT OUTER|      | 10000 |    10M|  6224K|  1436   (1)| 00:00:18 |
|   3 |    TABLE ACCESS FULL   | T2   | 70000 |  5400K|       |   260   (1)| 00:00:04 |
|   4 |    TABLE ACCESS FULL   | T1   | 10000 |  9853K|       |   390   (1)| 00:00:05 |
---------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("T2"."ID1"(+)="T1"."ID1" AND "T2"."ID2"(+)="T1"."ID2")

prompt  ===============================
prompt  Join opposite to order - hinted
prompt  ===============================

select
        /*+ leading(t1 t2) use_merge(t2) */
        t1.padding, 
        t2.padding
from
        t1, t2
where
        t2.id1(+) = t1.id1
and     t2.id2(+) = t1.id2
order by
        t1.id2,
        t1.id1
;

-------------------------------------------------------------------------------------
| Id  | Operation            | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |      | 10000 |    10M|       |  6343   (1)| 00:01:17 |
|   1 |  SORT ORDER BY       |      | 10000 |    10M|    22M|  6343   (1)| 00:01:17 |
|   2 |   MERGE JOIN OUTER   |      | 10000 |    10M|       |  4059   (1)| 00:00:49 |
|   3 |    SORT JOIN         |      | 10000 |  9853K|    19M|  2509   (1)| 00:00:31 |
|   4 |     TABLE ACCESS FULL| T1   | 10000 |  9853K|       |   390   (1)| 00:00:05 |
|*  5 |    SORT JOIN         |      | 70000 |  5400K|    12M|  1549   (1)| 00:00:19 |
|   6 |     TABLE ACCESS FULL| T2   | 70000 |  5400K|       |   260   (1)| 00:00:04 |
-------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   5 - access("T2"."ID1"(+)="T1"."ID1" AND "T2"."ID2"(+)="T1"."ID2")
       filter("T2"."ID2"(+)="T1"."ID2" AND "T2"."ID1"(+)="T1"."ID1")

The hash join has a much lower cost than the merge join so it’s not surprising that the optimizer used it, but there’s something a little odd about the plan the optimizer has created for the merge join. Although our where clause references the join columns in the order id1, id2 our order by clause is on id2, id1 and the optimizer hasn’t taken advantage of the fact that it could do the sort join at operations 3 and 5 in the order (id2, id1) and avoid the final sort order by at operation 1.

So let’s rewrite the query to make the predicate ordering in the where clause match the ordering of the columns in the order by clause and see what happens to the plan:

select
        t1.padding, 
        t2.padding
from
        t1, t2
where
        t2.id2(+) = t1.id2
and     t2.id1(+) = t1.id1
order by
        t1.id2,
        t1.id1
;


------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      | 10000 |    10M|       |  4059   (1)| 00:00:49 |
|   1 |  MERGE JOIN OUTER   |      | 10000 |    10M|       |  4059   (1)| 00:00:49 |
|   2 |   SORT JOIN         |      | 10000 |  9853K|    19M|  2509   (1)| 00:00:31 |
|   3 |    TABLE ACCESS FULL| T1   | 10000 |  9853K|       |   390   (1)| 00:00:05 |
|*  4 |   SORT JOIN         |      | 70000 |  5400K|    12M|  1549   (1)| 00:00:19 |
|   5 |    TABLE ACCESS FULL| T2   | 70000 |  5400K|       |   260   (1)| 00:00:04 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   4 - access("T2"."ID2"(+)="T1"."ID2" AND "T2"."ID1"(+)="T1"."ID1")
       filter("T2"."ID1"(+)="T1"."ID1" AND "T2"."ID2"(+)="T1"."ID2")

The plan no longer has a final sort order by operation – and the cost of the plan is much lower as a consequence. You’ll also notice that the Predicate Information section (always check the Predicate Information section) is a little different  – the order of predicate evaluation has been reversed.

In my test case the overall cost of the merge join still hasn’t fallen below the cost of the hash join but in the case of the client the cost of the merge join bacame significantly less than the cost of the hash join when we changed the ordering in the where clause (and we had no need for any hints).

The three plan costs were:

hash join with sort:       5,455K
Merge join"badly ordered": 6,208K
Merge join "well ordered": 1,338K

This was a case where the cost was a fairly realistic indication of run time, and avoiding an operation that would have sorted roughly 35GB of generated data was a very good move.

tl;dr

With multi-column joins the order of predicates in the where clause can, contrary to all expectations, make a big difference to the way Oracle operates a merge join.

Update March 2018

The anomaly is still present in 12.1.0.2, 12.2.0.1 and 18.1 – as tested on Oracle Live SQL where I’ve left a minimal demonstration script. (Requires an account on Live SQL.) Also tested on 18.3 and still displays this unexpected effect.

Update May 2019

A quick re-run of the test I left on LiveSQL shows that the anomaly is still present in 19.2