SQL Server 7.0: Hash Joins

In this article I want to tell you about Hash joins, what kinds
of Hash joins exist, and when SQL Server will choose this kind
of join operation.

The Hash join will be used, if there are no adequate indexes on
the join columns. This is a worst situation. In that case, hash
table will be created. Hash join is most efficient when one of
the tables is significantly differ in size than another one.

The query optimizer make a Hash join in two phases: build and
probe. So Hash join has two inputs: the build input and the probe
input.

On the build phase, hash table will be created by scanning each
value in the build input and applying the hashing algorithm to
the key.

Let me to describe Hash join on the example with two tables.

Look at this example:

if object_id(‘dbo.Table1’) is not null drop table Table1

GO

CREATE TABLE Table1 (id int, Name char(10))

GO

if object_id(‘dbo.Table2’) is not null drop table Table2

GO

CREATE TABLE Table1 (id int, Name char(20))

GO

DECLARE @i int

SELECT @i = 1

WHILE @i < 1000
  BEGIN
    INSERT INTO Table1 VALUES (@i, LTRIM(str(@i)))
    SELECT @i = @i + 1
  END
GO

DECLARE @i int
SELECT @i = 1
WHILE @i < 1000
  BEGIN
    INSERT INTO Table2 VALUES (@i, LTRIM(str(@i)))
    SELECT @i = @i + 1
  END
GO

SET SHOWPLAN_TEXT ON
GO
SELECT a.Name FROM Table1 a INNER JOIN Table2 b
  ON a.Name = b.Name
GO
SET SHOWPLAN_TEXT OFF
GO

These are the results:

StmtText

———————————————————————————————-

  |–Hash Match(Inner Join, HASH:([a].[Name])=([b].[Name]),

RESIDUAL:([a].[Name]=[b].[Name]))

       |–Table Scan(OBJECT:([pubs].[dbo].[Table1] AS [a]))

       |–Table Scan(OBJECT:([pubs].[dbo].[Table2] AS [b]))

The smaller table will be build input, the other – probe input.
Field Name (column that joins the tables) is called hash key.
The hash table consists of linked lists called hash buckets.
The result of using a hash function on a hash key is called
hash value. Hash value and RID (row identifier) will be placed
into hash table.

Hash value must be smaller than hash key. So, query processor
economies on the size of the hash table. The real example of
hashing is notebook. You can open notebook on the appropriate
letter and scan all surnames on this letter to find necessary
ones. So, notebook is the example of hash table, and pages on
the appropriate letter is the example of hash bucket.

During the probe phase, the entire probe input is scanned,
and for each probe row computes the same hash value on the
hash key to find any matches in the corresponding hash bucket.

There are two main kinds of Hash join:

In-memory Hash Join will be used if entire build input can be
placed into memory.

Grace Hash join will be used if your server have not enough
memory to hold the entire build input. In that case, query
processor proceeds Hash Join in several steps (hash table
will be divided into multiple partitions and relevant
partition will be loaded as need).

Because the query optimizer usually selects the best execution plan
for a given select statement, it is not necessary to change the kind
of join, but sometimes it can be useful. You can enforce the desirable
join type with OPTION clause.

This is the example to enforce Hash join:

USE pubs

GO

SET SHOWPLAN_TEXT ON

GO

SELECT a.au_id FROM authors a JOIN titleauthor b

   ON a.au_id = b.au_id OPTION (HASH JOIN)

GO

SET SHOWPLAN_TEXT OFF

GO

These are the results:

StmtText

———————————————————————————————–

SELECT a.au_id FROM authors a JOIN titleauthor b

   ON a.au_id = b.au_id OPTION (HASH JOIN)

(1 row(s) affected)
StmtText

————————————————————————————————–

  |–Hash Match(Inner Join, HASH:([a].[au_id])=([b].[au_id]),

RESIDUAL:([a].[au_id]=[b].[au_id]))

       |–Index Scan(OBJECT:([pubs].[dbo].[authors].[aunmind] AS [a]))

       |–Index Scan(OBJECT:([pubs].[dbo].[titleauthor].[titleidind] AS

[b]))
(3 row(s) affected)