Oracle Tuning Tip#20: Hash Join

TOPIC:

Hash Join

DEFINITION:

To perform hash join, Oracle follows these steps:

1.     Oracle chooses the smallest of two tables as the hash table (otherwise called as driving table). Oracle built the hash table in RAM after applying the hash function on the joining column(s) of the driving table.

2.     Oracle chooses the other [big] table as the probe table (otherwise called as driven table or probing table). It traverse through all the records of this probe table, applies the same hash function on the joining column(s) [column(s) used to join these two tables] and will hit the corresponding entry in the hash table.

3.     Oracle returns the output if a record from driving table is already present in the same hash key, else no record will be returned.

It may look like Nested loop join & Hash join have the same architecture since both these have the concept of driving & driven tables but they have entirely different design if you closely look at how the tables are being joined. In nested loop join, for each record in driving [outer] table, the corresponding records from the driven [inner] table will be joined and the output will be returned. But in the hash join, the driving [hash] table will be built at first in RAM by applying the hash function, then the driven [probe] table will be traversed next. While traversing each record in the probe table, Oracle applies the hash function on the joining column(s) and then hit the corresponding entry in the hash table. If a record from the driving table is already there in the same hash key, then the output will be returned.

A brief explanation on what is meant by hash table, hash function, hash value & hash key is mentioned below.

Hash Table:

=========

Hash table is one of the common data structures. Hash table is nothing but an array holds the data. In hash table, each record is uniquely identified by hash key which is nothing but the memory address [in ORACLE]. Hash function accepts an input value and returns an output value which is otherwise called as hash value (or hashed value).

From the above diagram, you can see that each record in hash table is uniquely identified by hash key(like 1,2,3,…,n).

In general, hash function is a set of formulas that accepts a number as an input and returns a number as an output [from mathematical perspective] where in output number is shorter and more compact than input number.

From Oracle perspective, hash function is a set of formulas that is applied to each value of joining column(s) of driving table, to get the address of RAM in which the row should be stored. Same hash function will be applied on each value of joining column(s) of driven table, to get the address of RAM in order to locate the data from the driving table if exists.

So, Oracle applies hash function on the joining column’s value to get the output which is otherwise called as hashed value. In Oracle, this returned hashed value is always been an address in RAM.

The logical activity diagram for this methodology will be like this,

Read all the required data from the driving table and built the hash table in RAM after applying hash function

Loop (for all the records in the driven table)

• ·         Apply the hash function for each record to get the address [hashed value] in RAM
• ·         Hit RAM in the corresponding address
• ·         If a record from the driving table is already present in the same hash key, then return the output else, don’t return the output

End loop

LITTLE-KNOWN FACTS TO BE REMEMBERED:

• ·         /*+ USE_HASH(<<driving table>>) */ is the hint that can be used to impose this hash natural join.
• ·         This methodology is opted by Oracle only if both the tables are joined by equal (=) operator.
• ·         In RAM, hash join will be carried out only in the allocated memory space which is nothing but HASH_AREA_SIZE component of PGA.
• ·         Only driving table will be inserted in the hash table in RAM and the driven table will never be written into the hash table in RAM. Hash function will be applied in the driven table only to locate the corresponding memory entry in the hash table to look for the matching entry from the driving table there.
• ·         This is very successful when one table is smaller and another table is bigger. In this case, it outplays both nested loop and sort merge joins.
• ·         If the driving table cannot be hashed in RAM in single pass (i.e., at one shot or one go), then a portion of the hash-table spills to disk(actually, TEMP tablespace will be used here to hold that spilled dataset from the driving table). When the hash table is probed by the driven table, the rows with join keys that match those parts of the in-memory hash table are joined immediately; the rest [of the driven table] are also written into TEMP tablespace and joined in the second pass. The bigger driving table is, the smaller the proportion of the hash table that can fit in RAM, the remaining data will be spilled into TEMP tablespace and have to go through the subsequent passes till it takes care of all the records spilled into TEMP tablespace from both these driving and driven table. This slows the Hash Join down considerably and also makes the join non-scalable in this scenario.

ADVANTAGE:

• ·         If the driving table is small enough to fit in RAM and equal (=) operator is used in the query, then hash join outplays both nested loop and sort merge joins.
• ·         Still nested loop will be the fastest way to retrieve the first matching record [since hash join takes some time to build the hash table in RAM for the driving table as it applies hash function] but hash join will be the fastest way to get all the matching records when compared to both nested loop and sort merge join. Hash function (in hash join) will perform more efficient and better than merging activity (in sort merge join).

DISADVANTAGE:

• ·         When this is opted for joining 2 big tables, TEMP tablespace will be used extensively as the spilled dataset from both driving and driven tables will be written into TEMP tablespace
• ·         The above scenario makes hash join as more non-scalable as it has to go through subsequent passes to join these spilled dataset (available in TEMP tablespace) from both these tables

HOW TO VERIFY:

How to verify whether Oracle follows hash natural join or not while executing the sql query. If a query follows this, then you will find similar execution plan like this,

In the explain plan, whenever it chooses this methodology, it displays the keyword (HASH JOIN) in the operation column. Whichever the table name that is getting displayed immediately after this keyword is nothing but the driving table (otherwise called as hash table) and the next one is the driven table(otherwise called as probe table).

EXAMPLE:

Create 2 tables.

One table is store the information of the sales done by the employees for January Month and inserts 6 records.

Another table is store the information of the sales done by the employees for February Month and inserts 3 records.

The tables will look like this,

DATA TABLE:

EMP_JAN:

ROWID	Empid	empname	Sales_Amt
AAAAA1	3825	CHARLES	2500
AAAAA2	9827	FERGUSON	1000
AAAAA3	2389	NADAL	3000
AAAAA4	1784	ERIN	7000
AAAAA5	4556	ROONEY	5500
AAAAA6	8711	TOMMY	6500

EMP_FEB:

ROWID	Empid	empname	Sales_Amt
AAAAA7	9827	FERGUSON	6000
AAAAA8	2389	NADAL	8500
AAAAA9	5642	JOHN	4000

Fire this query against these tables where the requirement is to display all the employee name(s) along with their sales information whoever able to do the sales on both the months,

Select a.empname, a.sales_amt january_amt, b.sales_amt february_amt

from emp_jan a, emp_feb b

where a.empid = b.empid;

since one table is small and another table is big, equal (=) operator is used , hash join will be the best candidate for joining these 2 tables.

Assume, Oracle can hold 10 records at a time in the allocated memory space(defined by HASH_AREA_SIZE global parameter) in RAM.

For easy understanding, pls assume the memory address will be from 0 to 9 to hold the records in the hash table.

For easy understanding, pls assume MOD function for the base 10 will be used as hash function here. In real world, the hash function would be more complex and hard to decode it.

EMPTY HASH TABLE:

=================

As per the design of hash join, the following steps will be followed while executing this query,

1.     Since EMP_FEB is the smallest of these two tables, EMP_FEB is considered as the driving table

2.     For the first record in EMP_FEB, hash function is applied and it returns 7 as the hashed value (i.e.,hash(9827)èmod(9827/10)è7)

3.     So, this record will be inserted as the 8^th record in hash table

4.     For the second record in EMP_FEB, hash function is applied and it returns 9 as the hashed value (i.e.,hash(2389)èmod(2389/10)è9)

5.     So, this record will be inserted as the 10^th record in hash table

6.     For the third record in EMP_FEB, hash function is applied and it returns 2 as the hashed value (i.e.,hash(5642)èmod(5642/10)è2)

7.     So, this record will be inserted as the 3^rd record in hash table. So, the hash table will look like this at the end of this step,

8.     Since EMP_JAN is the biggest of these two tables, EMP_JAN is considered as the driven table

9.     For the first record in EMP_JAN, hash function is applied and it returns 5 as the hashed value (i.e.,hash(3825)èmod(3825/10)è5)

10.  So, it hits 6^th record of hash table

11.  Since there is no record from EMP_FEB is available in 6^th record of hash table, no data will be returned in the output

12.  For the second record in EMP_JAN, hash function is applied and it returns 7 as the hashed value (i.e.,hash(9827)èmod(9827/10)è7)

13.  So, it hits 8^th record of hash table

14.  Since there is a record from EMP_FEB is available in 8^th record of hash table, data will be returned in the output

15.  For the third record in EMP_JAN, hash function is applied and it returns 9 as the hashed value (i.e.,hash(2389)èmod(2389/10)è9)

16.  So, it hits 10^th record of hash table

17.  Since there is a record from EMP_FEB is available in 10^th record of hash table, data will be returned in the output

18.  For the fourth record in EMP_JAN, hash function is applied and it returns 4 as the hashed value (i.e.,hash(1784)èmod(1784/10)è4)

19.  So, it hits 5^th record of hash table

20.  Since there is no record from EMP_FEB is available in 5^th record of hash table, no data will be returned in the output

21.  For the fifth record in EMP_JAN, hash function is applied and it returns 6 as the hashed value (i.e.,hash(4556)èmod(4556/10)è6)

22.  So, it hits 7^th record of hash table

23.  Since there is no record from EMP_FEB is available in 7^th record of hash table, no data will be returned in the output

24.  For the sixth(last) record in EMP_JAN, hash function is applied and it returns 1 as the hashed value (i.e.,hash(8711)èmod(8711/10)è1)

25.  So, it hits 2^nd record of hash table

26.  Since there is no record from EMP_FEB is available in 2^nd record of hash table, no data will be returned in the output

So, the output will look like this,

Empname	January_amt	February_amt
FERGUSON	1000	6000
NADAL	3000	8500

If you close look at the output, you can see that the output is displayed in the traversing order of records from EMP_JAN because while probing the driven table, FERGUSON is processed first and then NADAL.

Now, explain table will look like this,

From the explain plan, we can say that both the tables are joined by hash natural join methodology, EMP_FEB is considered as the driving table [hash table] and EMP_JAN is considered as the driven table [probe table].

Oracle Tuning Tip#19: Sort Merge Join

TOPIC:

Sort Merge Join

DEFINITION:

To perform sort merge join, Oracle follow these steps[assume table-a & table-b have to be joined]:

1. 1.     Oracle read all the required records from table-a and sort the data by the joining column(s)
2. 2.     Oracle read all the required records from table-b and sort the data by the same joining column(s)
3. 3.     Oracle then compare all these sorted data from both these tables record-by-record based on the joining column(s) and returns the output if it gets matched

In this join, there is no concept of driving & driven table like nested loop join. Important point to understand is, unlike nested loop join where driven(inner) table is read as many number of times as the input from outer table, in sort merge join each of the tables involved are accessed at most once. Actually sort merge join has two phases, Sorting & Merging. Step-1 & Step-2 are of Sorting phase and Step-3 is of Merging phase. In the sorting phase, all the required records from both the tables are read and then get sorted. In the merging phase, records from both these tables are joined and only the matching records will be returned in the output.

The logical flow diagram for this methodology will be like this,

PHASE-I (Sorting)

   Read the records from table-A

   Sort the retrieved records of table-A by the join_key (which is nothing but the column(s) used for joining these two tables)

   Dump into temp_a (assume logically that temp_a is just a temporary memory space to hold this sorted data of table-A)

   Read the records from table-B

   Sort the retrieved records of table-B by the same join_key

   Dump into temp_b

PHASE-II (Merging)

   read 1^st record from temp_a

   read 1^st record from temp_b

   while [NOT End Of Record] on temp_a and temp_b

   loop

        if ( temp_a.join_key = temp_b.join_key )

                 then output joined record

        else if ( temp_a.join_key <> temp_b.join_key )

                 then don’t output the joined record

        end if

        if ( temp_a.join_key <= temp_b.join_key )

                 then read the next record in temp_a

        else if ( temp_a.join_key > temp_b.join_key )

                 then read the next record in temp_b

        end if

   end loop

LITTLE-KNOWN FACTS TO BE REMEMBERED:

• ·         /*+ USE_MERGE(<<table-1>> <<table-2>>) */ is the hint that can be used to impose this sort merge join.
• ·         It is completely untrue that Sort Merge join does only TABLE ACCESS FULL on both the tables because in some cases, it will access the index table also but only if that cost is less.
• ·         In sort merge join, Sort phase will be skipped if the data is read from the index because it doesn’t require the sorting as the data is being read from the index is already in the sorted order. Sort phase will be imposed only if the data is read from the data table directly(TABLE ACCESS FULL) because the sorting is required here as the data is not coming out in the sorted order.
• ·         This methodology is especially opted by Oracle when both the tables are joined by inequality operators like <,>,<=,>=. This is because Hash Join can’t be imposed when inequality operators are used and Nested Loop Join is definitely not an option if both these tables are too big.
• ·         This is very successful if both the tables are bigger and outplays nested loop join in this case.

ADVANTAGE:

• ·         If the columns mentioned in the ORDER BY clause of the sql statement is same as the joining columns, Optimizer prefers sort merge join over hash join as it is cheaper. Reason is, sorting doesn’t need to be done explicitly again as the data coming out from sort merge join would already be in the sorted order and that is not the case in hash join. In this case, you will not find this operation, SORT BY or ORDER BY in the explain plan which will confirm that explicit sorting is not done.

DISADVANTAGE:

• ·         TEMP tablespace will be used extensively if the data read from both the tables don’t fit into the allocated memory space [which is exactly SORT_AREA_SIZE component of PGA] and query will start to throw errors if even TEMP tablespace is not big enough to hold the data from both the tables
• ·         If you closely look at the logic of sort merge join, matching records start to get displayed only in the merging phase as none will be displayed till the sorting phase is completed. Due to this reason, this join has to be avoided in some OLTP applications if the initial matching records need to be displayed as quick as possible.
• ·         This is very resource intense process (especially CPU is utilized a lot) since both the bigger tables need to be sorted and merged in the memory

HOW TO VERIFY:

How to verify whether Oracle follows sort merge join or not while executing the sql query. If a query follows this, then you will find similar execution plan like this,

--------------------------------------------------------------------------------------------------------

| Id  | Operation                                                     | Name                                             | Rows  |

--------------------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                                   |                                                          |            | |   1 |    MERGE JOIN                                              |                                                          |            | |   2 |       SORT JOIN                                               |                                                          |            |

|   3 |          TABLE ACCESS (FULL)                       | <<table-a>>                                |            | |   4 |       SORT JOIN                                               |                                                          |            | |   5 |          TABLE ACCESS (FULL)                       | <<table-b>>                               |            |

In the explain plan, whenever it chooses this methodology, it displays the keyword (MERGE JOIN and SORT JOIN) in the operation column.

EXAMPLE:

Create 2 tables.

One table is store the information of the sales done by the employees for January Month and inserts 5 records.

Another table is store the information of the sales done by the employees for February Month and inserts 5 records.

The tables will look like this,

DATA TABLE:

EMP_JAN:

ROWID	Empid	empname	Sales_Amt
AAAAA1	5	CHARLES	2500
AAAAA2	7	FERGUSON	1000
AAAAA3	9	NADAL	3000
AAAAA4	4	ERIN	7000
AAAAA5	6	ROONEY	5500

EMP_FEB:

ROWID	Empid	empname	Sales_Amt
AAAAA6	9	NADAL	6000
AAAAA7	6	ROONEY	8500
AAAAA8	8	JOHN	4000
AAAAA9	7	FERGUSON	9000
AAAAA10	2	MIKE	4500

Fire this query against these tables where the requirement is to display all the employee name(s) along with their sales information whoever able to do the sales on both the months,

Select a.empname, a.sales_amt january_amt, b.sales_amt february_amt

from emp_jan a, emp_feb b

where a.empid = b.empid;

As per the design of sort merge join, the following steps will be followed while executing this query,

1.     Oracle reads all the records from EMP_JAN table and sorts it based on empid column. The intermediate result set will be like this, [as per sorting phase of logical flow diagram]

Empid	empname	Sales_Amt
4	ERIN	7000
5	CHARLES	2500
6	ROONEY	5500
7	FERGUSON	1000
9	NADAL	3000

2.     Oracle reads all the records from EMP_FEB table and sorts it based on empid column. The intermediate result set will be like this, [as per sorting phase of logical flow diagram]

Empid	Empname	Sales_Amt
2	MIKE	4500
6	ROONEY	8500
7	FERGUSON	9000
8	JOHN	4000
9	NADAL	6000

3.     It reads the first record from both these intermediate result sets (empid:4 from 1^st & empid:2 from 2^nd) [as per initial steps of merging phase in logical flow diagram]

4.     Since 4 is not equal to 2, the joined record will not be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

5.     It reads the next record from 2^nd table since 4 is greater than 2 (empid:4 from 1^st & empid:6 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

6.     Since 4 is not equal to 6, the joined record will not be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

7.     It reads the next record from 1^st table since 4 is less than 6  (empid:5 from 1^st & empid:6 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

8.     Since 5 is not equal to 6, the joined record will not be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

9.     It reads the next record from 1^st table since 5 is less than 6 (empid:6 from 1^st & empid:6 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

10.  Since 6 is equal to 6, the joined record will be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

11.  It reads the next record from 1^st table since 6 is equal to 6 (empid:7 from 1^st & empid:6 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

12.  Since 7 is not equal to 6, the joined record will not be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

13.  It reads the next record from 2^nd table since 7 is greater than 6 (empid:7 from 1^st & empid:7 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

14.  Since 7 is equal to 7, the joined record will be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

15.  It reads the next record from 1^st table since 7 is equal to 7 (empid:9 from 1^st & empid:7 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

16.  Since 9 is greater than 7, the joined record will not be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

17.  It reads the next record from 2^nd table since 9 is greater than 7 (empid:9 from 1^st & empid:8 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

18.  Since 9 is greater than 8, the joined record will not be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

19.  It reads the next record from 2^nd table since 9 is greater than 8 (empid:9 from 1^st & empid:9 from 2^nd) [as per 2^nd IF clause of merging phase in logical flow diagram]

20.  Since 9 is equal to 9, the joined record will be displayed [as per 1^st IF clause of merging phase in logical flow diagram]

21.  It exits as all the records from both the tables are processed [as per WHILE condition of merging phase in logical flow diagram]

So, the output will look like this,

Empname	January_amt	February_amt
ROONEY	5500	8500
FERGUSON	1000	9000
NADAL	3000	6000

If you close look at the output, you can see that the output is displayed in the order of empid column (empids, 6,7 &9 of the employees, ROONEY, FERGUSON & NADAL accordingly). This is because of the outcome of sorting phase of sort merge join.

Now, explain table will look like this,

--------------------------------------------------------------------------------------------------------

| Id  | Operation                                                     | Name                                             | Rows  |

--------------------------------------------------------------------------------------------------------

|   6 | SELECT STATEMENT                                   |                                                          |  3          | |   5 |    MERGE JOIN                                              |                                                          |  3          | |   2 |       SORT JOIN                                               |                                                          |  5          |

|   1 |          TABLE ACCESS (FULL)                       | EMP_JAN                                     |  5          | |   4 |       SORT JOIN                                               |                                                          |  5          | |   3 |          TABLE ACCESS (FULL)                       | EMP_FEB                                      |  5          |

From the explain plan, we can say that both the tables are joined by sort merge natural join methodology.