Benchmarking of Hash Join Options in SQL for Fixed-Depth Hierarchies

Posted on by

In this article, Dimensional Benchmarking of SQL for Fixed-Depth Hierarchies I compared the performance characteristics of three traversal methods, two recursive and one non-recursive, using my own benchmarking package (A Framework for Dimensional Benchmarking of SQL Performance), on a test problem of a fixed level organization structure hierarchy, with 5 levels for performance testing and 3 levels for functional testing.

It is interesting to note that all joins in the execution plan are hash joins, and in the sequence you would expect. The first three are in the default join ‘sub-order’ that defines whether the joined table or the prior rowset (the default) is used to form the hash table, while the last two are in the reverse order, corresponding to the swap_join_inputs hint. I wrote a short note on that subject, A Note on Oracle Join Orders and Hints, last year, and have now written an article using the largest data point in the current problem to explore performance variation across the possible sub-orders.

This article uses the dimensional performance framework to test all 32 possible combinations in the given sequence of tables.

Notation and Hints

Dot-Bracket Code

In the note mentioned above I found a concise notation for representing a sequence of hash joins. A bracketted expression represents a rowset, and a ‘.’ represents a hash-join between a table and a rowset. As I noted there the standard idea of join order does not fully specify the hash join, and I found it convenient to use the idea of outer-level order – the sequence in which tables are joined to each other – and ‘inner-level order’ – which of the two factors goes on the ‘left’ side of the join, to form the hash table.

As Oracle documentation refers to the idea of swapping join inputs in a hash join to mean making the table the hash table, i.e. the left side of the join, we can think of that as being the non-default inner order.

When joining table c to a prior rowset, say (a.b), the default with (a.b) forming the hash table on the left is represented by:

(a.b).c

This can be forced by the hints use_hash(c) and no_swap_join_inputs(c).

In our example, defaulting each inner-join order is represented by:

((((s1.o1).s2).s3).s4).o5

The non-default is represented by:

c.(a.b)

This can be forced by the hints use_hash(c) and swap_join_inputs(c).

In our example, undefaulting each inner-join order is represented by:

o5.(s4.(s3.(s2.(o1.s1))))

Binary Code

In enumerating all combinations, it is convenient to represent a combination by 5 0/1 digits. I use 0 to mean the default and 1 to mean the non-default. Therefore

  • 00000 is equivalent to ((((s1.o1).s2).s3).s4).o5
  • 11111 is equivalent to o5.(s4.(s3.(s2.(o1.s1))))

Hints

To ensure that the desired options are followed, we need three types of hint:

  • leading – to guarentee sequence of outer-level ordering
  • use_hash – to ensure hash joins
  • swap_join_inputs/no_swap_join_inputs – to force swap or no swap on the inner-order

As mentioned in my earlier note, the inner-order on the first two tables can only be forced by the leading hint.

Graph of CPU, ElapsedTime, and disk_writes by Plan


From the graph we observe that a step-change in performance occurs between plan 16 and 17, with the second half of the plans consuming around half as much elapsed time as the first half, and that this correlates very strongly with disk accesses. There is also a roughly 1 second increase in CPU time in the second half, which is no doubt a knock-on effect of the disk access processing.

It’s clear that the final join to orgs with alias o5 is much faster when applied in the ‘swapped’ inner-order. It is well known that hash joins become much slower when the size of the hash table becomes too large for it to fit into memory and it has to spill to disk, and this is presumably what is happening here. We can see in my earlier article that the CBO, left to itself, in fact chooses one of the better plans.

Execution Plans for H01, H16, H17, H32

H01_QRY

  • Dot-Bracket Code: ((((s1.o1).s2).s3).s4).o5
  • Binary Code: 00000
  • Hints: leading(s1 o1 s2 s3 s4) use_hash(o1 s2 s3 s4 o5) no_swap_join_inputs(s2) no_swap_join_inputs(s3) no_swap_join_inputs(s4) no_swap_join_inputs(o5)
Plan hash value: 892313792

----------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation               | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
----------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |               |      1 |        |   3330K|00:00:19.68 |     782 |  96903 |  96872 |       |       |          |         |
|   1 |  SORT ORDER BY          |               |      1 |   3905K|   3330K|00:00:19.68 |     782 |  96903 |  96872 |   454M|  7027K|  163M (1)|     400K|
|*  2 |   HASH JOIN             |               |      1 |   3905K|   3330K|00:00:13.64 |     778 |  45725 |  45694 |   458M|    17M|  137M (1)|     372K|
|*  3 |    HASH JOIN            |               |      1 |   3905K|   3330K|00:00:00.38 |     771 |      0 |      0 |  4258K|  1196K| 6842K (0)|         |
|*  4 |     HASH JOIN           |               |      1 |    133K|  30520 |00:00:00.01 |     580 |      0 |      0 |   973K|   973K| 1314K (0)|         |
|*  5 |      HASH JOIN          |               |      1 |   4575 |    780 |00:00:00.01 |     389 |      0 |      0 |  1126K|  1126K| 1250K (0)|         |
|*  6 |       HASH JOIN         |               |      1 |     56 |     56 |00:00:00.01 |     198 |      0 |      0 |  1214K|  1214K| 1130K (0)|         |
|*  7 |        TABLE ACCESS FULL| ORG_STRUCTURE |      1 |     56 |     56 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|   8 |        TABLE ACCESS FULL| ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|   9 |       TABLE ACCESS FULL | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|  10 |      TABLE ACCESS FULL  | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|  11 |     TABLE ACCESS FULL   | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|  12 |    TABLE ACCESS FULL    | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
----------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O5"."ID"="S4"."CHILD_ORG_ID")
   3 - access("S4"."ORG_ID"="S3"."CHILD_ORG_ID")
   4 - access("S3"."ORG_ID"="S2"."CHILD_ORG_ID")
   5 - access("S2"."ORG_ID"="S1"."CHILD_ORG_ID")
   6 - access("O1"."ID"="S1"."ORG_ID")
   7 - filter("S1"."STRUCT_LEVEL"=1)

H16_QRY

  • Dot-Bracket Code: (s4.(s3.(s2.(o1.s1)))).o5
  • Binary Code: 11110
  • Hints: leading(o1 s1 s2 s3 s4) use_hash(s1 s2 s3 s4 o5) swap_join_inputs(s2) swap_join_inputs(s3) swap_join_inputs(s4) no_swap_join_inputs(o5)
Plan hash value: 1359118369

----------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation               | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
----------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |               |      1 |        |   3330K|00:00:31.46 |     782 |  96902 |  96871 |       |       |          |         |
|   1 |  SORT ORDER BY          |               |      1 |   3905K|   3330K|00:00:31.46 |     782 |  96902 |  96871 |   453M|  7021K|  163M (1)|     400K|
|*  2 |   HASH JOIN             |               |      1 |   3905K|   3330K|00:00:24.45 |     778 |  45725 |  45694 |   458M|    17M|  135M (1)|     371K|
|*  3 |    HASH JOIN            |               |      1 |   3905K|   3330K|00:00:00.49 |     771 |      0 |      0 |  2764K|  1580K| 4059K (0)|         |
|   4 |     TABLE ACCESS FULL   | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|*  5 |     HASH JOIN           |               |      1 |    133K|  30520 |00:00:00.01 |     580 |      0 |      0 |  2764K|  1580K| 4104K (0)|         |
|   6 |      TABLE ACCESS FULL  | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|*  7 |      HASH JOIN          |               |      1 |   4575 |    780 |00:00:00.01 |     389 |      0 |      0 |  2764K|  1580K| 4104K (0)|         |
|   8 |       TABLE ACCESS FULL | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|*  9 |       HASH JOIN         |               |      1 |     56 |     56 |00:00:00.01 |     198 |      0 |      0 |  1519K|  1519K| 1546K (0)|         |
|  10 |        TABLE ACCESS FULL| ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|* 11 |        TABLE ACCESS FULL| ORG_STRUCTURE |      1 |     56 |     56 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|  12 |    TABLE ACCESS FULL    | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
----------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O5"."ID"="S4"."CHILD_ORG_ID")
   3 - access("S4"."ORG_ID"="S3"."CHILD_ORG_ID")
   5 - access("S3"."ORG_ID"="S2"."CHILD_ORG_ID")
   7 - access("S2"."ORG_ID"="S1"."CHILD_ORG_ID")
   9 - access("O1"."ID"="S1"."ORG_ID")
  11 - filter("S1"."STRUCT_LEVEL"=1)

H17_QRY

  • Dot-Bracket Code: o5.((((s1.o1).s2).s3).s4)
  • Binary Code: 00001
  • Hints: leading(s1 o1 s2 s3 s4) use_hash(o1 s2 s3 s4 o5) no_swap_join_inputs(s2) no_swap_join_inputs(s3) no_swap_join_inputs(s4) swap_join_inputs(o5)
Plan hash value: 2901541859

----------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation               | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
----------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |               |      1 |        |   3330K|00:00:12.65 |     782 |  51181 |  51181 |       |       |          |         |
|   1 |  SORT ORDER BY          |               |      1 |   3905K|   3330K|00:00:12.65 |     782 |  51181 |  51181 |   454M|  7031K|  163M (1)|     400K|
|*  2 |   HASH JOIN             |               |      1 |   3905K|   3330K|00:00:02.58 |     778 |      0 |      0 |  1519K|  1519K| 1435K (0)|         |
|   3 |    TABLE ACCESS FULL    | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|*  4 |    HASH JOIN            |               |      1 |   3905K|   3330K|00:00:00.34 |     771 |      0 |      0 |  4258K|  1196K| 6851K (0)|         |
|*  5 |     HASH JOIN           |               |      1 |    133K|  30520 |00:00:00.01 |     580 |      0 |      0 |   973K|   973K| 1345K (0)|         |
|*  6 |      HASH JOIN          |               |      1 |   4575 |    780 |00:00:00.01 |     389 |      0 |      0 |  1126K|  1126K| 1260K (0)|         |
|*  7 |       HASH JOIN         |               |      1 |     56 |     56 |00:00:00.01 |     198 |      0 |      0 |  1214K|  1214K| 1138K (0)|         |
|*  8 |        TABLE ACCESS FULL| ORG_STRUCTURE |      1 |     56 |     56 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|   9 |        TABLE ACCESS FULL| ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|  10 |       TABLE ACCESS FULL | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|  11 |      TABLE ACCESS FULL  | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|  12 |     TABLE ACCESS FULL   | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
----------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O5"."ID"="S4"."CHILD_ORG_ID")
   4 - access("S4"."ORG_ID"="S3"."CHILD_ORG_ID")
   5 - access("S3"."ORG_ID"="S2"."CHILD_ORG_ID")
   6 - access("S2"."ORG_ID"="S1"."CHILD_ORG_ID")
   7 - access("O1"."ID"="S1"."ORG_ID")
   8 - filter("S1"."STRUCT_LEVEL"=1)

H32_QRY

  • Dot-Bracket Code: o5.(s4.(s3.(s2.(o1.s1))))
  • Binary Code: 11111
  • Hints: leading(o1 s1 s2 s3 s4) use_hash(s1 s2 s3 s4 o5) swap_join_inputs(s2) swap_join_inputs(s3) swap_join_inputs(s4) swap_join_inputs(o5)
Plan hash value: 1006677044

----------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation               | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
----------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |               |      1 |        |   3330K|00:00:13.57 |     782 |  51173 |  51173 |       |       |          |         |
|   1 |  SORT ORDER BY          |               |      1 |   3905K|   3330K|00:00:13.57 |     782 |  51173 |  51173 |   454M|  7030K|  163M (1)|     400K|
|*  2 |   HASH JOIN             |               |      1 |   3905K|   3330K|00:00:01.30 |     778 |      0 |      0 |  1519K|  1519K| 1563K (0)|         |
|   3 |    TABLE ACCESS FULL    | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|*  4 |    HASH JOIN            |               |      1 |   3905K|   3330K|00:00:00.29 |     771 |      0 |      0 |  2764K|  1580K| 4085K (0)|         |
|   5 |     TABLE ACCESS FULL   | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|*  6 |     HASH JOIN           |               |      1 |    133K|  30520 |00:00:00.01 |     580 |      0 |      0 |  2764K|  1580K| 4102K (0)|         |
|   7 |      TABLE ACCESS FULL  | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|*  8 |      HASH JOIN          |               |      1 |   4575 |    780 |00:00:00.01 |     389 |      0 |      0 |  2764K|  1580K| 4102K (0)|         |
|   9 |       TABLE ACCESS FULL | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
|* 10 |       HASH JOIN         |               |      1 |     56 |     56 |00:00:00.01 |     198 |      0 |      0 |  1519K|  1519K| 1547K (0)|         |
|  11 |        TABLE ACCESS FULL| ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|* 12 |        TABLE ACCESS FULL| ORG_STRUCTURE |      1 |     56 |     56 |00:00:00.01 |     191 |      0 |      0 |       |       |          |         |
----------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O5"."ID"="S4"."CHILD_ORG_ID")
   4 - access("S4"."ORG_ID"="S3"."CHILD_ORG_ID")
   6 - access("S3"."ORG_ID"="S2"."CHILD_ORG_ID")
   8 - access("S2"."ORG_ID"="S1"."CHILD_ORG_ID")
  10 - access("O1"."ID"="S1"."ORG_ID")
  12 - filter("S1"."STRUCT_LEVEL"=1)
Database VersionOracle Database 12c 12.1.0.2.0
OutputBatch_Org_Hints
GitHubA Framework for Dimensional Benchmarking of SQL Query Performance
Overview ArticleA Framework for Dimensional Benchmarking of SQL Performance






Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.