Quiz Night

I have four simple (non-partitioned, non-clustered, not views, not object type – really I’m not trying to be cunning or devious here) heap tables, and write a query that joins them:

rem
rem     Script:         c_treblehash_2.sql
rem     Author:         Jonathan Lewis
rem     Dated:          June 2010
rem

select
	/*+
		leading(t1 t2 t3 t4)
		use_hash(t2) use_hash(t3) use_hash(t4)
	*/
	count(t1.small_vc),
	count(t2.small_vc),
	count(t3.small_vc),
	count(t4.small_vc)
from
	t1,
	t2,
	t3,
	t4
where
	t2.id2 = t1.id1
and	t3.id3 = t2.id2
and	t4.id4 = t3.id3
;

Given that I’ve specified the join order and every join method, and given that there are no indexes on any of the tables, how many different execution plans are there for this query.

Update: When I say I’m not trying to be cunning or devious, it means I’m not trying to be cunning or devious – it doesn’t mean that I’m being really, really cunning and devious. Honestly, I’m just trying to make a simple but important point that isn’t terribly well-known.

Update 2: And when I said simple tables I should also have said they weren’t declared parallel, weren’t going to be hinted parallel, weren’t external or remote/non-oracle, etc., etc., etc.

The Answer:

The answer to the question I was trying to ask is eight – as stated then demonstrated by Pavol Babel and explained very succinctly by Greg Rahn.

The answer to the question I actually asked is four as stated by Vyacheslav Rasskazov. In my attempts to describe the situation as clearly and simply as possible I forgot about a special case that I will comment on at the end of this note.

Going back to the “expected” answer. The key point is this:

You have not defined a hash join completely until you have specified which rowsource should be used as the build table and which as the probe table; so every time you supply the use_hash() hint for a table, you should also supply the swap_join_inputs() hint or the no_swap_join_inputs() hint. (If you are expecting to use parallel execution you should also specifiy the pq_distribute() hint, but that another whole blog note.)

So my original query is suffering from incomplete hinting. There are three hash joins, so there should be three hints about swapping or not swapping join inputs. For example:

/*+
	leading(t1 t2 t3 t4)
	use_hash(t2) no_swap_join_inputs(t2)
	use_hash(t3) no_swap_join_inputs(t3)
	use_hash(t4) no_swap_join_inputs(t4)
*/

Since there are two possibilities for the swap/no_swap option, there are 2 x 2 x 2 = 8 possibilities in total for the execution plan – even though only one join order is examined. (If you check the 10053 trace file for this query you will find all the computation for these execution plans under one line that reads: Join order [1]. There will not be a Join order[2])

Pavol did list all the different patterns of hints with their execution plans – but I’m going to do it again, stripped to the minimum output:

use_hash(t2) no_swap_join_inputs(t2)
use_hash(t3) no_swap_join_inputs(t3)
use_hash(t4) no_swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|*  3 |    HASH JOIN          |      |    70 |  1260 |     8 |
|*  4 |     HASH JOIN         |      |    70 |   840 |     5 |
|   5 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
|   6 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
|   7 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
|   8 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
--------------------------------------------------------------

use_hash(t2)    swap_join_inputs(t2)
use_hash(t3) no_swap_join_inputs(t3)
use_hash(t4) no_swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|*  3 |    HASH JOIN          |      |    70 |  1260 |     8 |
|*  4 |     HASH JOIN         |      |    70 |   840 |     5 |
|   5 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
|   6 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
|   7 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
|   8 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
--------------------------------------------------------------

use_hash(t2) no_swap_join_inputs(t2)
use_hash(t3)    swap_join_inputs(t3)
use_hash(t4) no_swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|*  3 |    HASH JOIN          |      |    70 |  1260 |     8 |
|   4 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
|*  5 |     HASH JOIN         |      |    70 |   840 |     5 |
|   6 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
|   7 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
|   8 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
--------------------------------------------------------------

use_hash(t2)    swap_join_inputs(t2)
use_hash(t3)    swap_join_inputs(t3)
use_hash(t4) no_swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|*  3 |    HASH JOIN          |      |    70 |  1260 |     8 |
|   4 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
|*  5 |     HASH JOIN         |      |    70 |   840 |     5 |
|   6 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
|   7 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
|   8 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
--------------------------------------------------------------

use_hash(t2) no_swap_join_inputs(t2)
use_hash(t3) no_swap_join_inputs(t3)
use_hash(t4)    swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|   3 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
|*  4 |    HASH JOIN          |      |    70 |  1260 |     8 |
|*  5 |     HASH JOIN         |      |    70 |   840 |     5 |
|   6 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
|   7 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
|   8 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
--------------------------------------------------------------

use_hash(t2)    swap_join_inputs(t2)
use_hash(t3) no_swap_join_inputs(t3)
use_hash(t4)    swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|   3 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
|*  4 |    HASH JOIN          |      |    70 |  1260 |     8 |
|*  5 |     HASH JOIN         |      |    70 |   840 |     5 |
|   6 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
|   7 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
|   8 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
--------------------------------------------------------------

use_hash(t2) no_swap_join_inputs(t2)
use_hash(t3)    swap_join_inputs(t3)
use_hash(t4)    swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|   3 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
|*  4 |    HASH JOIN          |      |    70 |  1260 |     8 |
|   5 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
|*  6 |     HASH JOIN         |      |    70 |   840 |     5 |
|   7 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
|   8 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
--------------------------------------------------------------

use_hash(t2)    swap_join_inputs(t2)
use_hash(t3)    swap_join_inputs(t3)
use_hash(t4)    swap_join_inputs(t4)

--------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    24 |    11 |
|   1 |  SORT AGGREGATE       |      |     1 |    24 |       |
|*  2 |   HASH JOIN           |      |    70 |  1680 |    11 |
|   3 |    TABLE ACCESS FULL  | T4   |    70 |   420 |     2 |
|*  4 |    HASH JOIN          |      |    70 |  1260 |     8 |
|   5 |     TABLE ACCESS FULL | T3   |    70 |   420 |     2 |
|*  6 |     HASH JOIN         |      |    70 |   840 |     5 |
|   7 |      TABLE ACCESS FULL| T2   |    70 |   420 |     2 |
|   8 |      TABLE ACCESS FULL| T1   |    70 |   420 |     2 |
--------------------------------------------------------------

Note the extreme change in shape and apparent order of tables in the plan. Despite this the join order really is t1 -> t2 -> t3 -> t4 in every case. I’ll give a quick description of the first and last plans to explain this.

First plan (/*+ no_swap_join_inputs */ on every join):

• We build a hash table from t1 and probe it with t2 to create a result set
• As this result set is generated we build a new hash table from it
• As the result set completes we discard the hash table from t1
• We probe the result set with t3 to create a second result set
• As the second result set is generated we build a new hash table from it
• As the second result set completes we discard the hash table from the first result set
• We probe the second result set with t4 to create a third result set
• As the third result set is generated we pass the results up to the aggregation step to count the output

It is very obvious from this description that the tables are being joined in the order we dictated.

Last plan (/*+ swap_join_inputs */ on every join):

• We build a hash table from t4
• We build a hash table from t3
• We build a hash table from t2
• We pick a row from t1 and probe the t2 hash
• if the row “survives” we probe the t3 hash
• if the row “survives” we probe the t4 hash
• if the row “survives” we pass it up to the aggregation step to be counted

With this description it becomes fairly clear that, once again, the tables are being joined in the order we dictated (though in this case we would have to say that t1 and t2 are the first pair of tables joined but to describe the activity accurately t1 is being joined to t2 and it’s the penultimate plan shown above where the t1 -> t2 -> t3 -> t4 join order can be seen most clearly).

Notice: the number of in-memory hash (build) tables we have in the first of the 8 plans at any instant after the first join starts is two and (no matter how many tables are involved in this pattern) the number of in-memory hash tables will always be two. The actual size of the two hash tables is a little unpredictable, though, [see update 2020 below] and, as a very crude guideline, you might expect the size to grow as more tables are joined into the result set. In the last case the number of simultaneous in-memory hash tables we end up with is N-1 (where N is the number of tables joined). We can predict the approximate size of each hash table because it is based on the data we expect to extract from the corresponding “real” table. If you have enough memory to hold all the hash tables in memory at once (i.e. if none of them spill to disc) you will find that this join pattern is likely to be the fastest option you can produce.

Footnote: although a hash join is not fully specified unless you have also supplied an associated “swap/no swap” hint, the no_swap_join_inputs() hint didn’t become available until 10g!

Footnote 2: I’ve had this note on my draft list for nearly a year now – after answering this question on OTN. Unfortunately I think it’s a bit too late to update the thread now.

Special Case

And now we come to the point made by Vyacheslav Rasskazov. I have changed the original code to hint the eight different paths that could come from a single join order with three hash joins. But if I were limited to changing the data (technically the statistics) and leaving the /*+ leading() */ hint in place I would only be able to persuade the optimizer to pick four of those paths for this join order. The four plans that the optimizer would not consider are the ones which I have hinted with /*+ swap_join_inputs(t2) */ – i.e. the 2nd, 4th, 6th and 8th above.

As far as I can tell the built-in decision process is this: when considering a hash join, the optimizer will examine the cost of swapping the inputs if the expected volume (i.e. predicted cardinality * extracted row length) of the second input is smaller than the expected volume of the first input. However, in the special case of the first join of the first join order, this does not happen when the /*+ leading() */ hint is in place. This is fairly easy to demonstrate by setting up a two-table example where the selected content is a small number of large rows from one table and a large number of small rows from the other table – the first join order that the optimizer examines is dictated by the number of rows, swapping is dictated by volume of data. I suspect, but cannot confirm, that this is an accident (i.e. bug) since I can think of no rational explanation of why this has to happen.

Since my original text only allowed for one join order (the leading() hint) the optimizer will not examine the option for swapping the (t1, t2) step of that join order – which is why Vyacheslav’s answer is the answer to the question I actually asked.

My apologies – this wasn’t intended to be a cunning trap – I simply forgot that little detail when I was writing up the question.

Update (Dec 2020)

I’ve just written a note in response to a question on the Oracle developer forum about this article. The question was checking whether it was correct to assume that the plan that created all the in-memory hash tables before doing any joining would be the most memory-intensive plan. The answer is no.