In the
previous post I've demonstrated an unexpected Nested Loop Join caused by an extreme data distribution. Although unexpected at first sight, the performance of the execution plan selected by the optimizer is decent - provided the estimates are in the right ballpark.
Here is another case of an unexpected execution plan, this time about
Merge Joins.
Merge Joins
In order to appreciate why the execution plan encountered is unexpected, first a quick summary about how Merge Joins work:
A Merge Join is essentially a
Nested Loop operation from one
sorted row source into another
sorted row source. In contrast to a Nested Loop the join condition is not used for a possible index-driven lookup from the driving, outer row source into the inner row source, simply because Oracle usually first needs to run separate operations on each rowsource for sorting.
This means that in most cases the Merge Join requires to sort
both row sources and therefore a Hash Join is usually preferred where possible (for example, Hash Joins are only suitable for
Equi-Joins, whereas a Merge Join also supports non-Equi Joins), because it only needs to "prepare"
one row source for building the
hash table, and can then process the second row source as it is without any further start-up cost / preparation steps.
Let's have a look at some common execution plans using Merge Joins. Consider this simple setup:
create table t1
as
select
rownum as id
, rpad('x', 100) as filler
from
dual
connect by
level <= 1e3
;
exec dbms_stats.gather_table_stats(null, 't1')
create unique index t1_idx on t1 (id);
create table t2
as
select
rownum as id
, 1 as fk
, rpad('x', 100) as filler
from
dual
connect by
level <= 1e6
;
exec dbms_stats.gather_table_stats(null, 't2')
So this is what a Merge Join usually looks like:
select /*+ use_merge(t1 t2) */
t1.filler as t1_filler
, t2.filler as t2_filler
from
t1
, t2
where
t1.id (+) = t2.fk
;
------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time |
------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1000K| 199M| | 28075 (1)| 00:05:37 |
| 1 | MERGE JOIN OUTER | | 1000K| 199M| | 28075 (1)| 00:05:37 |
| 2 | SORT JOIN | | 1000K| 99M| 217M| 28067 (1)| 00:05:37 |
| 3 | TABLE ACCESS FULL| T2 | 1000K| 99M| | 4333 (1)| 00:00:52 |
|* 4 | SORT JOIN | | 1000 | 102K| | 7 (15)| 00:00:01 |
| 5 | TABLE ACCESS FULL| T1 | 1000 | 102K| | 6 (0)| 00:00:01 |
------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("T1"."ID"(+)="T2"."FK")
filter("T1"."ID"(+)="T2"."FK")
As usual I had to force the Merge Join via a
hint, since in my (default 11.2.0.1) setup a Hash Join would be preferred. Notice the two
SORT JOIN operations that first create two (ideally in-memory) sorted/indexed tables from the two row sources to be joined and how the SORT JOIN on the larger row source basically determines the overall cost of this MERGE JOIN.
A corresponding Hash Join could use the smaller row source as hash table and therefore very likely would be much more efficient.
Since the MERGE JOIN usually needs to SORT both row sources it doesn't make such a big difference which of the two row sources comes first, but it is interesting to note that the MERGE JOIN is not able to
"swap" the join inputs as the HASH JOIN is able to, which, in particular for outer joins, makes the MERGE JOIN less flexible.
Here is a variation of a MERGE JOIN that
avoids a SORT JOIN operation. This is only supported for the
"driving" row source:
select /*+ use_merge(t1 t2) */
t1.filler as t1_filler
, t2.filler as t2_filler
from
t1
, t2
where
t1.id = t2.fk
and t1.id between 1 and 10
;
-----------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 909K| 181M| | 28081 (1)| 00:05:37 |
| 1 | MERGE JOIN | | 909K| 181M| | 28081 (1)| 00:05:37 |
| 2 | TABLE ACCESS BY INDEX ROWID| T1 | 10 | 1050 | | 3 (0)| 00:00:01 |
|* 3 | INDEX RANGE SCAN | T1_IDX | 10 | | | 2 (0)| 00:00:01 |
|* 4 | SORT JOIN | | 1000K| 99M| 217M| 28078 (1)| 00:05:37 |
|* 5 | TABLE ACCESS FULL | T2 | 1000K| 99M| | 4344 (2)| 00:00:53 |
-----------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("T1"."ID">=1 AND "T1"."ID"<=10)
4 - access("T1"."ID"="T2"."FK")
filter("T1"."ID"="T2"."FK")
5 - filter("T2"."FK">=1 AND "T2"."FK"<=10)
The MERGE JOIN knows that the driving row source will be accessed in
sorted order due to the suitable INDEX RANGE SCAN operation and therefore doesn't add a SORT operation on top.
If we now run the same statement using
Parallel Execution (note that the statement level PARALLEL hint used in the example is only supported from 11g on), we'll see the following:
select /*+ use_merge(t1 t2) parallel */
t1.filler as t1_filler
, t2.filler as t2_filler
from
t1
, t2
where
t1.id = t2.fk
and t1.id between 1 and 10
;
------------------------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time | TQ |IN-OUT| PQ Distrib |
------------------------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 909K| 181M| | 15594 (1)| 00:03:08 | | | |
| 1 | PX COORDINATOR | | | | | | | | | |
| 2 | PX SEND QC (RANDOM) | :TQ10001 | 909K| 181M| | 15594 (1)| 00:03:08 | Q1,01 | P->S | QC (RAND) |
| 3 | MERGE JOIN | | 909K| 181M| | 15594 (1)| 00:03:08 | Q1,01 | PCWP | |
| 4 | SORT JOIN | | 10 | 1050 | | 3 (0)| 00:00:01 | Q1,01 | PCWP | |
| 5 | BUFFER SORT | | | | | | | Q1,01 | PCWC | |
| 6 | PX RECEIVE | | 10 | 1050 | | 3 (0)| 00:00:01 | Q1,01 | PCWP | |
| 7 | PX SEND BROADCAST | :TQ10000 | 10 | 1050 | | 3 (0)| 00:00:01 | | S->P | BROADCAST |
| 8 | TABLE ACCESS BY INDEX ROWID| T1 | 10 | 1050 | | 3 (0)| 00:00:01 | | | |
|* 9 | INDEX RANGE SCAN | T1_IDX | 10 | | | 2 (0)| 00:00:01 | | | |
|* 10 | SORT JOIN | | 1000K| 99M| 217M| 15591 (1)| 00:03:08 | Q1,01 | PCWP | |
| 11 | PX BLOCK ITERATOR | | 1000K| 99M| | 2407 (1)| 00:00:29 | Q1,01 | PCWC | |
|* 12 | TABLE ACCESS FULL | T2 | 1000K| 99M| | 2407 (1)| 00:00:29 | Q1,01 | PCWP | |
------------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
9 - access("T1"."ID">=1 AND "T1"."ID"<=10)
10 - access("T1"."ID"="T2"."FK")
filter("T1"."ID"="T2"."FK")
12 - filter("T2"."FK">=1 AND "T2"."FK"<=10)
So usually, due to the way things run in parallel, Oracle assumes it
cannot guarantee the order of the row source and
includes a SORT operation for both row sources joined.
Although there are special cases where this could be avoided even for Parallel Execution, it looks like the code adds this SORT operation
unconditionally in case of Parallel Execution. We'll see how this can become a threat in a moment.
The Special Case
Now back to the special case I want to demonstrate here. Let's have a look at the following query:
select
t1.filler as t1_filler
, t2.filler as t2_filler
from
t1
, t2
where
t1.id (+) = t2.fk
and t2.fk = 1
----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1000K| 199M| 4342 (1)| 00:00:53 |
| 1 | MERGE JOIN OUTER | | 1000K| 199M| 4342 (1)| 00:00:53 |
|* 2 | TABLE ACCESS FULL | T2 | 1000K| 99M| 4339 (1)| 00:00:53 |
|* 3 | SORT JOIN | | 1 | 105 | 3 (34)| 00:00:01 |
| 4 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 105 | 2 (0)| 00:00:01 |
|* 5 | INDEX UNIQUE SCAN | T1_IDX | 1 | | 1 (0)| 00:00:01 |
----------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - filter("T2"."FK"=1)
3 - access("T1"."ID"(+)="T2"."FK")
filter("T1"."ID"(+)="T2"."FK")
5 - access("T1"."ID"(+)=1)
Notice that I now got a
MERGE JOIN although I haven't provided any hints to do so, so this execution plan was automatically favored by optimizer. Why?
This is a special case, because the optimizer understands that the join key is actually a
single value, due to the predicate on T2.FK. So for a serial execution it doesn't bother to SORT the large row source (since it knows there will only be the value "1") and hence the MERGE JOIN comes out with a (slightly) lower cost estimate than a corresponding HASH JOIN.
It's interesting to note that in this particular case here it could even be avoided to SORT the second row source, since it, too, can only return a single value. But obviously the MERGE JOIN always runs a SORT JOIN operation on the second row source, as already outlined above.
Due to the way the data is designed and the direction of the outer join a
NESTED LOOP join isn't a reasonable alternative either here.
Note that at runtime a
HASH JOIN seems to be slightly more efficient in this particular case here, so this is already an indication that the cost estimates do not reflect the efficiency at runtime very well, in particular the
CPU overhead of the actual join operation seems to be underestimated for the MERGE JOIN.
Now let's see what happens if we run this query using
Parallel Execution:
select /*+ parallel */
t1.filler as t1_filler
, t2.filler as t2_filler
from
t1
, t2
where
t1.id (+) = t2.fk
and t2.fk = 1
-----------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | TQ |IN-OUT| PQ Distrib |
-----------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1000K| 199M| 2406 (1)| 00:00:29 | | | |
| 1 | MERGE JOIN OUTER | | 1000K| 199M| 2406 (1)| 00:00:29 | | | |
| 2 | SORT JOIN | | 1000K| 99M| 2403 (1)| 00:00:29 | | | |
| 3 | PX COORDINATOR | | | | | | | | |
| 4 | PX SEND QC (RANDOM) | :TQ10000 | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,00 | P->S | QC (RAND) |
| 5 | PX BLOCK ITERATOR | | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,00 | PCWC | |
|* 6 | TABLE ACCESS FULL | T2 | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,00 | PCWP | |
|* 7 | SORT JOIN | | 1 | 105 | 3 (34)| 00:00:01 | | | |
| 8 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 105 | 2 (0)| 00:00:01 | | | |
|* 9 | INDEX UNIQUE SCAN | T1_IDX | 1 | | 1 (0)| 00:00:01 | | | |
-----------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
6 - filter("T2"."FK"=1)
7 - access("T1"."ID"(+)="T2"."FK")
filter("T1"."ID"(+)="T2"."FK")
9 - access("T1"."ID"(+)=1)
Look very carefully at the
order of the operations, and what part of the execution plan runs in
parallel and what is executed
serially.
This is where things become pretty weird and threatening: The TABLE ACCESS to the large row source T2 runs in parallel (with the corresponding lower cost), but the data is then handed over to the
Query Coordinator for a
SORT JOIN operation - which wasn't there in serial execution and is in fact unnecessary since we still have a single value in the join key.
After sorting the large row source, the
MERGE JOIN operation itself is performed by the Query Coordinator, so no
Parallel Execution is involved here either.
Both the
serial SORT JOIN of the large row source and the
MERGE JOIN operation itself are
literally free of cost here, which is clearly unreasonable, in particular if the row source is very large.
Although the SORT JOIN will basically turn into a simple
"BUFFER SORT" operation, since there is effectively nothing to sort, it still means that a potentially very big volume of data will have to be handed over from the Parallel Worker processes scanning the row source to the Query Coordinator - in this particular case by definition an inefficient operation, because a large data volume has to be passed from
multiple Parallel Processes to the
single Query Coordinator - and then this potentially very big volume of data will have to be SORTED by the Query Coordinator, which very likely means that this operation won't fit into
PGA memory of that single process, hence
spill to TEMP causing potentially significant additional (and unnecessary)
read and write I/O, all to be done
serially by the Query Coordinator.
This is a
textbook example of a Parallel Execution plan that is deemed to take
longer than the corresponding
serial execution plan, and it is the execution plan that is preferred by the optimizer when left unhinted.
Let's have a look at the
Parallel Execution plan when using a
HASH JOIN:
select /*+ parallel use_hash(t1 t2) */
t1.filler as t1_filler
, t2.filler as t2_filler
from
t1
, t2
where
t1.id (+) = t2.fk
and t2.fk = 1
---------------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | TQ |IN-OUT| PQ Distrib |
---------------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1000K| 199M| 2411 (1)| 00:00:29 | | | |
| 1 | PX COORDINATOR | | | | | | | | |
| 2 | PX SEND QC (RANDOM) | :TQ10001 | 1000K| 199M| 2411 (1)| 00:00:29 | Q1,01 | P->S | QC (RAND) |
|* 3 | HASH JOIN RIGHT OUTER | | 1000K| 199M| 2411 (1)| 00:00:29 | Q1,01 | PCWP | |
| 4 | BUFFER SORT | | | | | | Q1,01 | PCWC | |
| 5 | PX RECEIVE | | 1 | 105 | 2 (0)| 00:00:01 | Q1,01 | PCWP | |
| 6 | PX SEND BROADCAST | :TQ10000 | 1 | 105 | 2 (0)| 00:00:01 | | S->P | BROADCAST |
| 7 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 105 | 2 (0)| 00:00:01 | | | |
|* 8 | INDEX UNIQUE SCAN | T1_IDX | 1 | | 1 (0)| 00:00:01 | | | |
| 9 | PX BLOCK ITERATOR | | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,01 | PCWC | |
|* 10 | TABLE ACCESS FULL | T2 | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,01 | PCWP | |
---------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("T1"."ID"(+)="T2"."FK")
8 - access("T1"."ID"(+)=1)
10 - filter("T2"."FK"=1)
Looking at the child operations' cost estimates of the HASH JOIN it becomes obvious that it is the costing of the HASH JOIN itself that makes the whole operation more costly than the MERGE JOIN, which is clearly questionable.
So the strange thing about the MERGE JOIN Parallel Execution plan is that the
join operation itself is done
serially, whereas the HASH JOIN execution plan, although it uses the
same access to the row sources (INDEX UNIQUE SCAN and FULL TABLE SCAN), happily runs in parallel.
What causes this strange execution plan shape? Obviously it is the
UNIQUE index on the other, smaller row source. Somehow the MERGE JOIN code is mislead by the UNIQUE index scan, which causes the join operation to run serially.
Replacing the UNIQUE index with a
NON-UNIQUE index (and using a
UNIQUE constraint on top to achieve the same uniqueness) gives this execution plan:
drop index t1_idx;
create index t1_idx on t1 (id);
alter table t1 add constraint t1_uq unique (id) using index t1_idx;
select /*+ parallel */
t1.filler as t1_filler
, t2.filler as t2_filler
from
t1
, t2
where
t1.id (+) = t2.fk
and t2.fk = 1
----------------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | TQ |IN-OUT| PQ Distrib |
----------------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1000K| 199M| 2406 (1)| 00:00:29 | | | |
| 1 | PX COORDINATOR | | | | | | | | |
| 2 | PX SEND QC (RANDOM) | :TQ10001 | 1000K| 199M| 2406 (1)| 00:00:29 | Q1,01 | P->S | QC (RAND) |
| 3 | MERGE JOIN OUTER | | 1000K| 199M| 2406 (1)| 00:00:29 | Q1,01 | PCWP | |
| 4 | SORT JOIN | | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,01 | PCWP | |
| 5 | PX BLOCK ITERATOR | | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,01 | PCWC | |
|* 6 | TABLE ACCESS FULL | T2 | 1000K| 99M| 2403 (1)| 00:00:29 | Q1,01 | PCWP | |
|* 7 | SORT JOIN | | 1 | 105 | 3 (34)| 00:00:01 | Q1,01 | PCWP | |
| 8 | BUFFER SORT | | | | | | Q1,01 | PCWC | |
| 9 | PX RECEIVE | | 1 | 105 | 2 (0)| 00:00:01 | Q1,01 | PCWP | |
| 10 | PX SEND BROADCAST | :TQ10000 | 1 | 105 | 2 (0)| 00:00:01 | | S->P | BROADCAST |
| 11 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 105 | 2 (0)| 00:00:01 | | | |
|* 12 | INDEX RANGE SCAN | T1_IDX | 1 | | 1 (0)| 00:00:01 | | | |
----------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
6 - filter("T2"."FK"=1)
7 - access("T1"."ID"(+)="T2"."FK")
filter("T1"."ID"(+)="T2"."FK")
12 - access("T1"."ID"(+)=1)
So now we still have the
unnecessary SORT JOIN operation of the large row source, but at least the SORT JOIN and MERGE JOIN operations are now executed in
parallel, which should make it far less threatening.
Of course, a corresponding
HASH JOIN will still be much more efficient for larger row sources, but needs to be
hinted in this special case here.
Summary
For
MERGE JOINs there are some special cases where the current costing model doesn't properly reflect the actual work - together with some strange behaviour of the MERGE JOIN code when using
Parallel Execution this can lead to questionable execution plans preferred by the optimizer.
Carefully check the resulting execution plans when using Parallel Execution and MERGE JOINs get preferred by the optimizer.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.