Joins – MJ

The final join mechanism in my “all joins are nested loop joins” argument is the Merge Join – a join mechanism that depends on both its row sources being pre-sorted on the join columns. (For a quick reference list of URLs to all three articles see: Joins.)

The note on hash joins pointed out that a “traditional” nested loop join may result in repeated visits to data blocks that make up the second (inner) table as we work through the data from the first (outer) table – and argued that there were cases where it made sense for Oracle to copy a subset of the second table into private memory and structure the copy as a single table hash cluster. Towards the end of the note, though, there was a brief mention of the increased complexity and I/O cost when that subset was too large to fit completely into memory. This is where the merge join may turn out to be better than the hash join as a way of removing the stress of random I/O and buffer visits.

We’ll start with a simple, visual, example of how the merge join works. Take the following (pre-sorted) data sets from which I’ve only made visible the single join column values. The first data set, in order, is:

	(1 ,...) (3, ...)  (3, ...) (4, ...) (5, ...) (8, ...) (10, ...)

The second data set, again in order, is:

	(0, ...) (1, ...) (1, ...) (2, ...) (2, ...) (3, ...) (3, ...) (3, ...)
	(5, ...) (5, ...) (5, ...) (7, ...) (7, ...) (8, ...) (8, ...) (9, ...)

Our target is to join items from set 1 that match items from set 2. To do this we read the first value (1, …) from the first data set and scan the second data set to find matches, then we read the second value from the first data set and scan the second data set to find matches and so on. Immediately you can see that we’re doing a nested loop join – for each row in the (sorted) first data set we scan the second data set.

Where, then, is the special feature of the merge join that gives it a separate name and execution plan? Most of it is in the benefit we get from the two data sets being sorted in the same order as we repeatedly scan the second data set. (There’s extra benefit, which we also saw in the hash join, because the data has been copied from the buffer cache into private memory allowing us to avoid latching and pinning overheads as we re-visit data).

Think about what happens as we hit the (4, …) in the first data set. We have to scan the second data set, but how much of it do we need to scan ? Because the first data set is sorted we can take advantage of remembering what we did with the previous element of the first data set. At worst we will need to start in the second data set at the point where we found the first match for previous element from the first data set; and because the second data set is sorted we can stop the scan the moment we overshoot our target value.

Assuming (for this example) that our test is for equality, we could imagine the code doing the following:

• Select (4,…) from first set
  Start at the 3’s in the second set (because that’s where we got the first match last time)

… (3,…) too small
… (3,…) too small
… (3,…) too small
… (5,…) too big – stop, no matches for 4

• Select 5 from first set
  Start at the 3’s in the second set (because we didn’t get any matches for 4 the start point hasn’t changed)

… (3,…) too small
… (3,…) too small
… (3,…) too small
… match, match, match
… (7,…) too big

• Select 8 from the first set
  Start at the 5’s in the second set (smallest match of previous value)

… (5,…) too small
… (5,…) too small
… (5,…) too small
… (7,…) too small
… (7,…) too small
… match, match
… (9,…) too big

For each value in the first set (apart from the very first one – where we may simply start at the lowest value in the second set) we have a way of minimising the scan on the second set. Moreover if the second set is too large to keep entirely in memory this “windowing” effect means the extra I/O that we do on the merge is also kept to a minimum.

So where are the costs and benefits compared to the nested loop join and the hash join:

The benefit is the same as the benefit we got from the hash join – we avoid repeated access into data blocks that are in public memory and may even be on disc; so random I/O, latch acquisition, and buffer pinning costs are reduced.

The cost is that we need to have the data in the right order as we operate the join – so we may have to sort both sets of data first and sorting can be expensive, particularly if it spills to disc.

These observations may give you some way to compare nested loops joins with merge joins – but why bother with merge joins at all when you’ve got the hash join mechanism. (One feature, of course, is that merge joins need not be restricted to equality predicates as hash joins are, but we’ll ignore that for the present.) What’s the critical comparison there? The answer lies in the closing comment I made about hash joins – the complications that arise when the hash table doesn’t fit in memory.

If the hash table fits in memory the only I/O that Oracle does for the second data set (probe table) is to read it once. If the hash table doesn’t fit in memory Oracle will have to copy some of it to disc, and then copy a similar proportion of the probe table to disc as well. Then it will have to re-read matching portions of the two data sets to join them. The larger the first data set is (relative to the available memory), the larger the fraction of the second data set that has to be copied to disc, and the more times some parts of it may have to be re-read to complete the join.

If the sorted data sets for a merge join are too large to fit into memory Oracle dumps them to disc, but only reads through them (at most) once each for equality joins and the commoner types of range-based joins. (Of course, if the data sets are large then the work done in sorting them may be expensive on CPU and I/O – and there are several variations in mechanism that you may have to consider when thinking about forcing a merge join).

You can probably find lots of books and internet notes that say something like “hash joins are good if one of the data sets is small, merge joins are better if both data sets are large”. There is an element of truth in this statement – but words like “small” and “large” don’t have any absolute meaning in this context, so it’s important to have an understanding of how the hash join and merge join work so you can recognise what the trade-off is between them.

There’s plenty more to say about the workings of hash joins and merge joins and I have several draft notes  about them that I will probably complete and publish eventually. In the meantime if you’re prepared to spend a little cash on understanding more of the mechanisms you could always buy a copy of “Cost Based Oracle – Fundamentals”.

I’ll just close with a couple of examples of execution plans (from 11g) for merge joins:

rem
rem     Script:         c_merge_join.sql
rem     Author:         Jonathan Lewis
rem     Dated:          March 2001
rem 

select 
	count(t1.v1)	ct_v1,
	count(t2.v2)	ct_v2
from
	t1, t2
where
	t2.n2 = t1.n1
;

-------------------------------------------------------------
| Id  | Operation            | Name | Rows  | Bytes | Cost  |
-------------------------------------------------------------
|   0 | SELECT STATEMENT     |      |     1 |  1508 |  1055 |
|   1 |  SORT AGGREGATE      |      |     1 |  1508 |       |
|   2 |   MERGE JOIN         |      |  1000 |  1472K|  1055 |
|   3 |    SORT JOIN         |      |  1000 |   980K|   184 |
|   4 |     TABLE ACCESS FULL| T1   |  1000 |   980K|    25 |
|*  5 |    SORT JOIN         |      | 10000 |  4921K|   871 |
|   6 |     TABLE ACCESS FULL| T2   | 10000 |  4921K|   113 |
-------------------------------------------------------------


-----------------------------------------------------------------------
| Id  | Operation                     | Name  | Rows  | Bytes | Cost  |
-----------------------------------------------------------------------
|   0 | SELECT STATEMENT              |       |     1 |  1508 |  1017 |
|   1 |  SORT AGGREGATE               |       |     1 |  1508 |       |
|   2 |   MERGE JOIN                  |       |  1000 |  1472K|  1017 |
|   3 |    TABLE ACCESS BY INDEX ROWID| T1    |  1000 |   980K|   146 |
|   4 |     INDEX FULL SCAN           | T1_I1 |  1000 |       |     3 |
|*  5 |    SORT JOIN                  |       | 10000 |  4921K|   871 |
|   6 |     TABLE ACCESS FULL         | T2    | 10000 |  4921K|   113 |
-----------------------------------------------------------------------


------------------------------------------------------------------------
| Id  | Operation                      | Name  | Rows  | Bytes | Cost  |
------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |       |     1 |  1508 |  1640 |
|   1 |  SORT AGGREGATE                |       |     1 |  1508 |       |
|   2 |   MERGE JOIN                   |       |  1000 |  1472K|  1640 |
|   3 |    TABLE ACCESS BY INDEX ROWID | T1    |  1000 |   980K|   146 |
|   4 |     INDEX FULL SCAN            | T1_I1 |  1000 |       |     3 |
|*  5 |    SORT JOIN                   |       | 10000 |  4921K|  1494 |
|   6 |     TABLE ACCESS BY INDEX ROWID| T2    | 10000 |  4921K|   736 |
|   7 |      INDEX FULL SCAN           | T2_I2 | 10000 |       |    21 |
------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   5 - access("T2"."N2"="T1"."N1")
       filter("T2"."N2"="T1"."N1")

The predicate section of the three plans was the same in all three cases.

It important to note that you can avoid sorting the first table  (see 2nd ad 3rd plans) if a suitable index exists – but even when there is an appropriate index on the second table Oracle still reports a sort operation (3rd plan). Mind you, as I’ve pointed out in the past, sorts aren’t necessarily what they seem to be.