Joins – HJ

In the second note on my thesis that “all joins are nested loop joins with different startup costs” I want to look at hash joins, and I’ll start by going back to the execution plan I posted on “Joins – NLJ”. (For a quick reference list of URLs to all three articles in turn, see: Joins.)

---------------------------------------------------------------------------------------------
| Id  | Operation                    | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |              |     1 |   191 |     3   (0)| 00:00:01 |
|   1 |  NESTED LOOPS                |              |     1 |   191 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS BY INDEX ROWID| T1           |     2 |   152 |     3   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | T1_PK        |     2 |       |     2   (0)| 00:00:01 |
|*  4 |   TABLE ACCESS HASH          | HASHED_TABLE |     1 |   115 |            |          |
---------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("T1"."ID">=1 AND "T1"."ID"<=2)
   4 - access("HT"."ID"="T1"."N1")
       filter("HT"."SMALL_VC"='a')

In this query I created my second table as a “single table hash cluster” so, if I’ve done a perfect job (and been a bit lucky), for each row selected from the first table (t1) Oracle will hit one “cache buffers chains” latch to find the correct block, go directly to the correct row in that block, read the required columns, and drop the latch. This action is reported in the session statistics (v$sesstat) as a “consistent get – examination” and is probably the most efficient way of getting data from an “unpinned” block in the buffer cache. (For a few more esoteric details, see this note on my old website).

So this particular path for a simple nested loop is about as efficient as it can be. But what performance threats does it still have, and can we make it better ?

What if it’s a very big single table hash cluster – perhaps every row is 500 bytes long and our query is only interested in a couple of columns that are 10 bytes long: in this case we may find that the table is so big that we can’t keep the blocks we want in memory as the query runs and have to keep repeating random I/Os to get at them. Even if we can keep the blocks in memory there may be other users who are also constantly looking at the same table and blocks: so we may find that we are constantly competing for the “cache buffers chains” latches that protect the blocks in that table. (Of course most tables are simple heap table with B-tree indexes where we could be walking through the root, a branch, and a leaf block of an index before hitting the required table block – which means we could be competing for several latches for each row we want to see from the second table in our nested loop.)

Can we do better than the nested loop into a single table hash cluster ? Yes, we can, if we really need to. We can copy just the bits of the table we need, just once, into a private, in-memory, single table hash cluster (or “hash table” as it’s usually called in this context) before we start running the join. But if we do that we call it a hash join and the tables appear to be back to front in the execution plan.

Here’s an example, running under 11.1.0.6, to demonstrate the principle:

rem
rem     Script:         hash_nl.sql
rem     Author:         Jonathan Lewis
rem     Dated:          Aug 2010
rem     Purpose:        
rem
rem     Last tested 
rem             11.1.0.6
rem

create table hash_target(
        hash_value      number,
        status          varchar2(2),
        small_vc        varchar2(10),
        padding         varchar2(100)
)
;

insert into hash_target 
select
        rownum,
        dbms_random.string('U',2),
        lpad(rownum,10),
        rpad('x',100)
from
        all_objects
where
        rownum <= 1000
;

create index ht_i1 on hash_target(status);
create unique index ht_i2 on hash_target(hash_value);

create table t1(
        join_value      number,
        status          varchar2(1),
        small_vc        varchar2(10),
        padding         varchar2(100)
)
;

insert into t1 
select
        mod(rownum,1000),
        dbms_random.string('U',1),
        lpad(rownum,10),
        rpad('x',100)
from
        all_objects
where
        rownum <= 20000
;

create index t1_i1 on t1(status);

-- gather stats at this point.

set autotrace traceonly explain

select
        t1.small_vc,
        ht.small_vc
from
        t1,
        hash_target     ht
where
        t1.status = 'X'
and     ht.hash_value = t1.join_value
and     ht.status = 'XX'
;

set autotrace off

The way I’ve written this query, a possible execution path would be a nested loop using an indexed access (or tablescan) into t1 to collect the data for t1.status = ‘X’ then, for each row acquired, an indexed access path on the unique index ht_i2 into hash_target. Here’s a possible execution plan (with the 11g nlj_batching disabled to make the plan look more like the tradition 9i/10g plan):

---------------------------------------------------------------------------
| Id  | Operation                   | Name        | Rows  | Bytes | Cost  |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |             |     3 |   105 |   827 |
|*  1 |  TABLE ACCESS BY INDEX ROWID| HASH_TARGET |     1 |    18 |     1 |
|   2 |   NESTED LOOPS              |             |     3 |   105 |   827 |
|*  3 |    TABLE ACCESS FULL        | T1          |   769 | 13073 |    58 |
|*  4 |    INDEX UNIQUE SCAN        | HT_I2       |     1 |       |       |
---------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("HT"."STATUS"='XX')
   3 - filter("T1"."STATUS"='X')
   4 - access("HT"."HASH_VALUE"="T1"."JOIN_VALUE")

This isn’t very efficient, of course, because we will pick up several hundred rows from t1, and index into hash_target several hundred times. We could improve efficiency in this case if hash_target were a single table hash cluster – but it isn’t, so Oracle “fakes” it. We pay the overhead of Oracle collecting all the relevant data (the select and join columns where ht.status = ‘XX’) and building this subset of the data as a single table hash cluster in memory so that it can then do the nested loop join with using a variant of “table access hash” into this in-memory table.

But since the first physical operation was acquiring data from hash_target that’s the table the optimizer reports as the first child of the join operation and since it’s building a single table in-memory hash cluster it calls the operation a hash join.

----------------------------------------------------------------------------
| Id  | Operation                    | Name        | Rows  | Bytes | Cost  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |             |     3 |   105 |    62 |
|*  1 |  HASH JOIN                   |             |     3 |   105 |    62 |
|   2 |   TABLE ACCESS BY INDEX ROWID| HASH_TARGET |     2 |    36 |     3 |
|*  3 |    INDEX RANGE SCAN          | HT_I1       |     2 |       |     1 |
|*  4 |   TABLE ACCESS FULL          | T1          |   769 | 13073 |    58 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("HT"."HASH_VALUE"="T1"."JOIN_VALUE")
   3 - access("HT"."STATUS"='XX')
   4 - filter("T1"."STATUS"='X')

So that’s it: a hash join is a nested loop join where Oracle has extracted a subset of the data from the thing that would have been the “inner” table and recreated it as an in-memory single table hash cluster. The startup cost is the cost of getting the data once and building the hash cluster in memory; the saving comes from eliminating the repeated buffer visits and latch competition that we would see if Oracle left the data in the buffer cache and accessed it through the typical indexed access mechanisms.

Inevitably the cost/saving equation becomes difficult when the “in-memory hash cluster” can’t fit in memory and spills to disc, increasing the physical I/O count … but if that does happen then maybe the nested loop with indexed access might have been doing a lot of random disk I/O as well. But if you spend at least a little time thinking of hash joins as a variant of nested loops, it becomes easier to focus on what bottleneck you are trying to avoid and what efficiencies you are trying to achieve.

*** Footnote: for a nested loop join the first child table (or rowsource, if you want to be fussy) is usually called the “outer” table, and the second the “inner” table. For a hash join the first child table is called the “build” table – from which we build the in-memory hash cluster – and the second child table is called the “probe” table – which we use to probe the in-memory hash cluster for matches.