SQL Join Algorithms

SQL queries implement various joins when datasets are to be retrieved from one/multiple tables and merged on a certain criteria for final results. During query processing a join operator based on certain algorithm is chosen by SQL Server Optimizer that will retrieve these datasets in most efficient way possible. The Optimizer may choose a different algorithm for different scenarios based on the requested query, available indexes, statistics and number of estimated rows in each data set.

For more information on various SQL joins I'd recommend you to visit the below sites:

•  http://www.w3schools.com/sql/sql_join.asp
•  http://www.sql-join.com

This blog will help you understand the various algorithms available and the operator associated with it.

A.    Nested loop joins

 A Nested Loop join is a logical structure in which one loop(iteration) resides inside another.This join typically occurs when one worktable is quite a bit smaller than the other. The bigger the difference in number of rows between the outer and inner inputs, the more benefit this operator will provide over the other operator types. The inner loop, executed for each outer row, searches for matching rows in the inner input table. The search scans an entire table or index; this is called a naive nested loops join. If the search exploits an index, it is called an index nested loops join. If the index is built as part of the query plan (and destroyed upon completion of the query), it is called a temporary index nested loops join.

B.    Merge join

A merge join requires both the inputs to be sorted on join keys/merge columns (or both the input tables to have clustered indexes on the column that joins the tables). It also requires at least one equi-join (equality) expression. This join simultaneously reads a row from each input and compares them using the join key. If there's a match, the rows of both the sets are returned. Otherwise, the row with the smaller value can be discarded. As the input is in the sorted order the discarded rows will not match any further rows from the other data set.The biggest performance gain from this join type is that both input operators are executed only once. The costly part of merge join is sorting.

C.   Hash joins 

A hash join is the least efficient of all joins. When large tables are being joined and not all the common keys being joined exist in both sides and/or they are not sorted, this join type may be chosen. The hash join has two inputs: the build input and probe input. The query optimizer assigns these roles so that the smaller of the two inputs is the build input.

The following sections describe different types of hash joins: in-memory hash join, grace hash join, and recursive hash join.

In-Memory Hash Join

The hash join first scans or computes the entire build input and then builds a hash table in memory. Each row is inserted into a hash bucket depending on the hash value computed for the hash key. If the entire build input is smaller than the available memory, all rows can be inserted into the hash table. This build phase is followed by the probe phase. The entire probe input is scanned or computed one row at a time, and for each probe row, the hash key's value is computed, the corresponding hash bucket is scanned, and the matches are produced.

Grace Hash Join

If the build input does not fit in memory, a hash join proceeds in several steps. This is known as a grace hash join. Each step has a build phase and probe phase. Initially, the entire build and probe inputs are consumed and partitioned (using a hash function on the hash keys) into multiple files. Using the hash function on the hash keys guarantees that any two joining records must be in the same pair of files. Therefore, the task of joining two large inputs has been reduced to multiple, but smaller, instances of the same tasks. The hash join is then applied to each pair of partitioned files.

Recursive Hash Join

If the build input is so large that inputs for a standard external merge would require multiple merge levels, multiple partitioning steps and multiple partitioning levels are required. If only some of the partitions are large, additional partitioning steps are used for only those specific partitions. In order to make all partitioning steps as fast as possible, large, asynchronous I/O operations are used so that a single thread can keep multiple disk drives busy.

Best of the 3 Hash Joins

It is not always possible during optimization to determine which hash join is used. Therefore, SQL Server starts by using an in-memory hash join and gradually transitions to grace hash join, and recursive hash join, depending on the size of the build input.
If the optimizer anticipates wrongly which of the two inputs is smaller and, therefore, should have been the build input, the build and probe roles are reversed dynamically. The hash join makes sure that it uses the smaller overflow file as build input. This technique is called role reversal. Role reversal occurs inside the hash join after at least one spill to the disk.

You may also visit the below websites for more info

• https://www.simple-talk.com/books/sql-books/inside-the-sql-server-query-optimizer
• https://msdn.microsoft.com/en-us/library/ms191426.aspx