HASH JOIN STRATEGIES
In previous tips, we discussed nested iteration and merge join 
strategies. In this tip, we will continue our join strategies 
discussion 
with perhaps the most complex join strategy, the hash join. A hash join 
occurs when there are no useful indexes on the joined columns.

When SQL Server decides to use a hash join strategy, several things 
occur.

1. SQL hashes the data in question by a hashing algorithm to place like 
data into like buckets called a "hash bucket."
2. It forms what is called a "build input" to build these hash buckets.
3. It then compares the second input called the "probe input," usually 
the smaller of the two inputs.
4. Matches are then found by looking in the appropriate bucket(s).

This method reduces searching time since all of the same hashed 
values now reside in the same bucket.

SELECT dept.deptno, empl.deptno 
  FROM departments dept JOIN employees empl 
    ON dept.deptno=empl.deptno

Microsoft Press Inside SQL Server 7.0 has some good examples of this 
concept.
http://click.online.com/Click?q=2d-OxXyIbKV-l3sucYmdykVyv_yrRRR 

dept           empl 
deptno         deptno 
------         ---- 
1              1 
2              3 
3              4 
5              5 
6             

The query would return something like the following via a hashing 
scenario.

dept.deptno  empl.deptno 
-----------  ----------- 
1            1 
3            3 
5            5

Assume a modulo 2 operation on the above datasets dept

deptno       
------         
1 mod 2 = 1 or (bucket 1 build) 
2 mod 2 = 1 or (bucket 1 build)     
3 mod 2 = 1 or (bucket 1 build) 
5 mod 2 = 1 or (bucket 1 build) 
6 mod 2 = 0 or (bucket 0 build)   
 
empl - probe input as this set is smaller 
deptno        
------         
1 mod 2 = 1 or (bucket 1 probe) 
3 mod 2 = 1 or (bucket 1 probe) 
4 mod 2 = 0 or (bucket 0 probe) 
5 mod 2 = 1 or (bucket 1 probe)

Since you now have 2 buckets for each input, your searching algorithm 
is reduced. The probe input can now query the appropriate bucket for 
matches.

Hashing can be a very complex process. You can review BOL and the 
Microsoft Press Inside SQL Server books for more information regarding 
the hash join as well as the other join strategies that SQL Server 
uses.
http://click.online.com/Click?q=a7-fRT2Q8BoDDVi5p30FqSEDvj7wRRR 

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