11 - Join algorithms

Materialization

• Early (all data)
• Late(record ID only)

Algorithms

Important

The costs of different join algorithms is thought in terms of IO operations since they dominate.

Nested Loop

• Simple Nested Loop: Traverse all pages of the inner table for each tuple of the outer table
• Block Nested Loop: For each page in the outer table, fetch a page in the inner table and compare
• Index Nested Loop: Lookup by index in the inner table for each element of the outer table

If $M$ is the number of pages on the outerr table , $m$ is the number of tuples in the outer table, $N$ is the number of pages in the inner table with $n$ tuples,

• Nested loops require potentially scanning all $M$ pages for each of the $n$ tuples. $Cost=M+m\ast N$
• Block nested loop: $M+(M\ast N)$. This cost can further be decreased if we have more buffers in the buffer pool since we can hold $B-2$ pages in memory so we need $M+(M/(B-2))\ast N$ since we don’t need to load the N pages M time, but we can reuse
• Index Nested Loop, assuming a fixed cost $C$ for the index lookup, $Cost=N+m\ast C$

Sort Merge Join

Useful if one of the tables is already sorted (i.e. clustered index) or if the output need to be sorted anyways. The cost is the $M+N+(sortcost)$ as defined in 10 - Sorting and Aggregation

Hash Join

Basic Hash Join: build outer relation hashtable, probe on loop on inner Grace Hash Join / Partitioned Hash Join: hash inner table into partitions to write them to disk

Comparison

This assumes $M=1000,m=100000,N=500,n=40000,B=10,i/o=0.1ms$

Algorithm	I/O Cost	Example
Simple Nested Loop Join	$M+(m\ast N)$	1.4 hours
Block Nested Loop Join	$M+(M\ast N)$	50 seconds
Index Nested Loop Join	$M+(m\ast C)$	varies
Sort Merge Join	$M+N+(sortcost)$	0.75 seconds
Hash Join	$3\ast (M+N)$	0.45 seconds