Introduction

When you join tables, the optimizer has to decide how to combine the data sets. There are three key algorithms to do this:

• Hash Joins
• (Sort) Merge Joins
• Nested Loops

This tutorial gives examples of these by joining a table of playing cards to itself in various ways:

select * from card_deck;

Hash Joins

The steps to do a hash join are:

1. Return all the rows from the smaller data set
2. Build a hash table using the join columns for these rows
3. Read the rows in the larger table
4. Probe the hash table built at step 2 by applying the same hash function to the join columns of the second table
5. If this finds a matching entry in the hash table, the database passes the joined rows to the next step of the plan

This query uses a hash join:

select /*+ gather_plan_statistics */count(*)
from   card_deck d1
join   card_deck d2
on     d1.suit = d2.suit
and    d1.val = d2.val;

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

There must be equality "=" conditions in the join for the optimizer to choose a hash join. When there is, it may choose this join method when joining either:

• Large data sets OR
• Most of the rows in small tables OR
• There are no indexes on the join columns for either table

Merge Joins

Also known as a sort merge join, the algorithm for this is:

• Sort the rows in the first data set
• Sort the rows in the second data set
• For each row in the first data set, find a starting row in the second data set
• Read the second data set until you find a row with a value greater than the current row in the first data set
• Read the next row in the first data set and repeat

This query shows a merge join in action:

select /*+ gather_plan_statistics */count(*)
from   card_deck d1
join   card_deck d2
on     d1.suit < d2.suit
and    d1.val < d2.val;

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

Note that the database reads the second table once (starts = 1 at line 7). But runs the BUFFER SORT once for each row from the first table (starts = 52 for line 6).

The optimizer may choose a merge join when:

• The join uses range comparisons (<, >=, between, etc.)
• The join has an equality (=) and one of the data sets is already ordered, enabling the database to avoid a sort

Sorting is slow, so it's rare for the optimizer to use a merge join.

Indexes are ordered data structures. So if there is an index on the join columns for one table, the optimizer can use this to avoid a sort. Oracle Database will always sort the second data set, even if it there are indexes on the second table's join columns.

Nested Loops

The process for nested loops is:

• Read rows from the first (outer) data set
• For each row in this, query the second (inner) data set for matching rows
• Repeat until all the rows are read from the outer table or the client stops fetching rows

This query to find all rows with different values in each table uses nested loops:

select /*+ gather_plan_statistics */count(*)
from   card_deck d1
join   card_deck d2
on     d1.suit <> d2.suit
and    d1.val <> d2.val;

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

Note that this reads the inner table once for each row from the outer table. This means it does 52 full table scans of the second table!

The optimizer may choose nested loops when:

• Joining small data sets
• Fetching a small fraction of large data sets
• The query of the inner table is efficient (e.g. there is an index on its join columns)
• All the join criteria are inequalities (not equals)

Merge Join Cartesian

This query does a cross join - linking every row in the first table to every row in the second table. This uses a Cartesian merge join:

select /*+ gather_plan_statistics */count(*)
from   card_deck d1
cross join card_deck d2;

select * 
from   table(dbms_xplan.display_cursor ( :LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

The optimizer considers a merge join Cartesian if:

• It's joining every row in one table to every row in another (a cross join)
• It expects to get exactly one row from the first table and join it to every row in the second table
• It may generate the Cartesian product of two tiny tables before joining these to a huge table

It's rare to see this join method. And it's often a sign of a problem. For example missing join criteria or out-of-date statistics.

If you see this double-check your join criteria and table stats. If a join is missing, add it!

If you get this because the optimizer estimates one row for the first table, check this is correct. Look at the actual number of rows fetched from this table. If this is greater than one - even just two or three rows, Cartesian joins can take hours to complete! When this happens see if you can tweak the stats to improve row estimates.

Top-N Queries

This query joins the tables and returns the first five rows:

select /*+ gather_plan_statistics */*
from   card_deck d1
join   card_deck d2
on     d1.suit = d2.suit
and    d1.val = d2.val
order  by d1.val
fetch  first 5 rows only;

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

Note that this reads 52 rows from both tables. And the join also returns 52 rows. You can see this from the A-rows column in the plan for lines 3-5:

| Id  | Operation                | Name      | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
...
|*  3 |    HASH JOIN             |           |      1 |     52 |     52 |00:00:00.01 |      30 |
|   4 |     TABLE ACCESS FULL    | CARD_DECK |      1 |     52 |     52 |00:00:00.01 |      15 |
|   5 |     TABLE ACCESS FULL    | CARD_DECK |      1 |     52 |     52 |00:00:00.01 |      15 |

This is because are no indexes on the join column, so the optimizer chooses a hash join. This means it must read all the rows in one table before reading any rows from the second. You can make this query faster by adding an index on the join columns:

create index card_val_suit_i 
  on card_deck ( val, suit );

For a HASH JOIN, the optimizer can still use an index on the second table if you use its columns in the WHERE clause. It's indexes on the join columns that a HASH JOIN can't take advantage of.

This enables the optimizer to use nested loops to join the tables:

select /*+ gather_plan_statistics */ *
from   card_deck d1
join   card_deck d2
on     d1.suit = d2.suit
and    d1.val = d2.val
order  by d1.val
fetch first 5 rows only;

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, null, 'IOSTATS LAST'));

Note this does a "double nested loop". It first joins the outer table to the index. Then joins matching rows to the inner table. This approach is common when using indexed nested loops.

The optimizer chooses nested loops over hash join because it knows the query will return at most five rows. Nested loops can search for rows in the inner table immediately after reading them from the outer table. So it can stop processing after reading just five rows from each table.

You can see that - unlike a hash join - the nested loops fetch and join at most five rows from each table:

| Id  | Operation                       | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
...
|   3 |    NESTED LOOPS                 |                 |      1 |      5 |      5 |00:00:00.01 |      24 |
|   4 |     NESTED LOOPS                |                 |      1 |      5 |      5 |00:00:00.01 |      19 |
|   5 |      TABLE ACCESS BY INDEX ROWID| CARD_DECK       |      1 |     52 |      5 |00:00:00.01 |      10 |
|   6 |       INDEX FULL SCAN           | CARD_VAL_SUIT_I |      1 |      5 |      5 |00:00:00.01 |       5 |
|*  7 |      INDEX RANGE SCAN           | CARD_VAL_SUIT_I |      5 |      1 |      5 |00:00:00.01 |       9 |
|   8 |     TABLE ACCESS BY INDEX ROWID | CARD_DECK       |      5 |      1 |      5 |00:00:00.01 |       5 |

This highlights a key difference between hash joins and nested loops. A hash join must read all the rows in the first data set to build the hash table. Then start reading the second table.

Nested loops can read rows in the inner table after reading just one row from the outer table. Provided the lookup of the inner table is fast, this means it can start returning rows faster than a hash join.

This makes nested loop operations the best way to get a small fraction of large data sets. For example, when doing top-N queries or master-detail joins, such as orders to order items.

Try It!

Replace /*TODO*/ in this query to experiment with fetching different numbers of rows:

select /*+ gather_plan_statistics */*
from   card_deck d1
join   card_deck d2
on     d1.suit = d2.suit
and    d1.val = d2.val
order  by d1.val
fetch first /*TODO*/ rows only;

select * 
from   table(dbms_xplan.display_cursor ( :LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

How many rows do you have to fetch before the optimizer changes from nested loops to a hash join?

Adaptive Plans

It can be tough to choose between nested loops and hash joins. Provided there is an index on the join columns, nested loops are fast when you fetch few rows from the first table.

But nested loops query the inner table once for each row from the outer table. As you fetch more rows from the first table, you quickly reach a point where it's faster to use a hash join. This fetches all the rows from the second table once.

There is only one row in the table where the NOTES store "SQL is awesome!". So this query uses nested loops:

select /*+ gather_plan_statistics */*
from   card_deck d1
join   card_deck d2
on     d1.val = d2.val
where  d1.notes = 'SQL is awesome!';

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

Picking the best join method relies on the optimizer knowing how many rows have the value "SQL is awesome!". If the table stats are even slightly out-of-date, the optimizer may choose the "wrong" join.

To handle this, Oracle Database 12c added adaptive plans. This is one plan which considers two different join methods. You can see this query uses an adaptive plan by looking at the Note section:

Note
-----
   - this is an adaptive plan

The database can then choose the best join method at runtime. It does this by looking at the actual number of rows the query processes.

To see which joins the optimizer considered, get the plan with the +ADAPTIVE format:

select /*+ gather_plan_statistics */*
from   card_deck d1
join   card_deck d2
on     d1.val = d2.val
where  d1.notes = 'SQL is awesome!';

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST +ADAPTIVE'));

This has some key differences to a standard plan:

• The plan includes both NESTED LOOPS and HASH JOIN operations
• There is a STATISTICS COLLECTOR operation above the first table in the plan
• A minus ('-') appears before some of the steps in the plan

The new information shows how the optimizer managed the plan.

Statistics Collector

This operation watches the number of rows flowing out of the table below it. Provided this number stays under a threshold, the optimizer will use nested loops. But if the number of rows exceeds this threshold, it'll switch to a hash join.

Inactive Operations

The minus before an operation indicates that the database did not execute this step. You can verify this further by noting that the Starts column reports zero for the full scan in step 8.

Try It!

Find how many rows in the table have DAMAGED = 'Y'

select count (*)
from   card_deck d1
where  d1.damaged = 'Y';

Replace /* TODO */ in the get the adaptive execution details for this query. But before you do - predict whether the query will use NESTED LOOPS or a HASH JOIN:

select /*+ gather_plan_statistics */* 
from   card_deck d1
join   card_deck d2
on     d1.suit = d2.suit
and    d1.val = d2.val
where  d1.damaged = 'Y';

select * 
from   table(dbms_xplan.display_cursor( :LIVESQL_LAST_SQL_ID, format => '/* TODO */'));

Which join method did the query use?

Try It Challenge!

There are no indexes on the join columns for this query, so the optimizer uses a hash join:

select /*+ gather_plan_statistics */*
from   card_deck d1
join   card_deck d2
on     d1.damaged = d2.damaged
where  d1.notes = 'SQL is awesome!';

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

Complete the index definition, so the optimizer chooses nested loops instead:

drop  index card_join_i;

create index card_join_i
  on card_deck ( /* TODO */ );

select /*+ gather_plan_statistics */ *
from   card_deck d1
join   card_deck d2
on     d1.damaged = d2.damaged
where  d1.notes = 'SQL is awesome!';

select * 
from   table(dbms_xplan.display_cursor(:LIVESQL_LAST_SQL_ID, format => 'IOSTATS LAST'));

Experiment with different indexes. Which enables the query to do the least consistent gets/buffers? Does creating two indexes make any difference?