1. Introduction

Relational databases use normalization to eliminate redundancy, which means queries often need to reconstruct enformation by combining data from multiple tibles through join operations. This discussion focuses on binary equi-joins, with an emphasis on placing the smaller relation on the left side as the driving table.

1.1 Join Output Strategies

The content of output tuples depends on the processing model, storage model, and query requirements:

Early Materialization: The join copies all non-join attributes from both the inner and outer relations into the output. While this approach eliminates the need to access original tables in subsequent operations, it requires more memory.

Late Materialization: Only the join attributes and record identifiers are copied into the output. Subsequent operations retrieve the remaining data from the original tables as needed. This approach is particularly effective for column stores since irrelevant attributes are never copied.

1.2 Performance Metrics

The primary optimization target for join algorithms is disk I/O reduction, as database tables typically exceed available memory. The output size remains constant regardless of which join algorithm is employed, so result set size is not a concern for algorithm selection.

Notation for analysis:

• Relations (R) and (S) are being joined
• (R) contains (M) pages and (m) tuples
• (S) contains (N) pages and (n) tuples

2. Nested Loop Join

The nested loop approach uses brute-force iteration over both relations. The outer relation drives the computation, while the inner relation is scanned for each outer tuple. DBMS implementations prefer smaller relations as the outer table to maximize caching benefits and enable index utilization on the inner side.

2.1 Simple Nested Loop Join

This basic implementation iterates through every tuple in the outer relation and performs a full scan of the inner relation for each one.

I/O Cost: (M + (m \times N))

The cost accounts for reading the outer relation once and scanning the inner relation (m) times. No buffering optimization occurs, so locality principles are completely ignored.

2.2 Block Nested Loop Join

This variant processes relations in blocks rather than individual tuples, significantly improving cache utilization:

For each outer block, the algorithm retrieves an inner block and performs the join within those blocks. This reduces the number of inner scans to one per block instead of one per tuple.

Assuming one page per block for relation (R):

I/O Cost: (M + (M \times N))

With (B) available buffers, using one for output, one for the inner relation, and (B-2) for the outer relation:

I/O Cost: (M + (\lceil \frac{M}{B-2}\rceil \times N))

When the outer relation fits entirely in memory:

I/O Cost: (M + N)

2.3 Index Nested Loop Join

If an index exists on the join attributes of the inner relation, linear scans can be replaced with index lookups. The DBMS may construct a temporary index or leverage existing ones.

Assuming each index probe costs (C) I/Os:

I/O Cost: (M + (m \times C))

Optimization Guidelines:

• Select the smaller relation as the outer table
• Maximize outer relation caching to minimize inner scans
• Exploit indexes during inner relation access

3. Sort-Merge Join

This algorithm divides into two distinct phases:

Phase 1 - Sorting: Both relations are sorted on the join keys using external sorting algorithms.

Phase 2 - Merging: Two pointers scan through both sorted relations, outputting matching tuples. Pointer backtracking may occur when join keys contain duplicates.

External merge sort requires (1+\left \lciel log_{B-1}\frac{P}{B} \right \rceil) passes over the data, where (B) is buffer pages and (P) is the total pages.

Cost Breakdown:

• Sorting (R): (2M \times (1+\left \lceil log_{B-1}\frac{M}{B} \right \rceil))
• Sorting (S): (2N \times (1+\left \lceil log_{B-1}\frac{N}{B} \right \rceil))
• Merging: (M + N)

Total Cost: Sum of sorting and merging phases

The worst-case scenario occurs when all tuples in both relations share identical join key values, causing the merge phase to degrade to (M \times N). This situation rarely occurs in practical databases.

Optimal Use Cases:

• One or both relations are already sorted on the join key (clustered indexes)
• Query output must be ordered by the join key

4. Hash Join

The fundamental principle relies on a key property: if two tuples satisfy the join condition, their join attribute values are equal, and consequently, their hash values under any hash function must match. This enables partition-based processing where matching tuples from both relations fall into the same buckets.

4.1 Basic Hash Join

Phase 1 - Build: The outer relation is scanned, and a hash table is constructed on the join attributes using hash function (h_1).

Static hash tables with linear probing perform optimally when the outer relation size is known in advance. Dynamic hash tables with overflow pages are necessary when the size is unknown.

Phase 2 - Probe: The inner relation is scanned, and for each tuple, the same hash function (h_1) locates the corresponding bucket in the hash table for matching.

Hash Table Structure:

• Key: Join attribute values
• Value: Either full tuples or tuple identifiers, depending on whether early or late materialization is desired

Full tuples eliminate subsequent table lookups but consume more space. Tuple identifiers minimize memory usage but require additional data access later.

For a relation with (N) pages, approximately (\sqrt{N}) buffers are needed. With a skew factor (f):

I/O Cost: (B \times \sqrt{f \times N})

A limitation of this approach emerges when the hash table exceeds available memory, causing random probing to thrash between memory and disk.

4.2 Probe Filter Optimization

Bloom filters optimize the probe phase by quickly determining whether a key might exist in the hash table. Before accessing the hash table, the system checks the Bloom filter—if it indicates the key is absent, the expensive hash table lookup is skipped entirely.

Bloom filters use (k) hash functions during insertion to set corresponding bits. Query operations verify all (k) bits are set. The structure guarantees no false negatives but may produce false positives.

4.3 Partitioned Hash Join (GRACE Algorithm)

When memory is insufficient for the entire hash table, Grace hash join extends the basic approach by partitioning both relations into disk-resident hash tables:

Phase 1 - Build: Both relations are partitioned using hash function (h_1) on their join attributes.

Phase 2 - Probe: Corresponding buckets from both relations are joined, and matching tuples are output.

Assuming adequate buffers exist for intermediate results:

I/O Cost: (3(M + N))

The partitioning phase requires reading and writing each relation once: (2(M + N)). The probing phase reads each relation once: (M + N).

Recursive Partitioning: When a bucket cannot fit in memory, a secondary hash function (h_2) further partitions that bucket. Both relations must undergo identical recursive partitioning to maintain bucket correspondence.

4.4 Hybrid Hash Join

For skewed data distributions, hybrid hash join keeps hot partitions in memory for immediate matching rather than spilling them to disk. This optimization is difficult to implement correctly and remains uncommon in production systems.

5. Algorithm Selection Summary

Hash join delivers optimal performance in most scenarios. However, sort-merge join becomes preferable when queries include ORDER BY clauses or when data exhibits extreme skew.

Modern database systems often employ multiple join strategies within a single query execution plan, selecting the appropriate algorithm for each join operation based on available statistics and runtime conditions.

6. SQL Join Variants

Inner Join: Returns only matching rows from both tables based on the equality condition specified in the ON clause.

SELECT t1.value, t2.value
FROM table_a AS t1 INNER JOIN table_b AS t2
ON t1.key = t2.key;

The same result can be achieved with implicit joins using comma-separated tables and a WHERE clause:

SELECT t1.value, t2.value
FROM table_a AS t1, table_b AS t2
WHERE t1.key = t2.key;

Self Join: An inner join where both operands refer to the same table, useful for hierarchical relationships.

-- Subquery approach
SELECT employee_name
FROM staff
WHERE department_id = (
    SELECT department_id
    FROM staff
    WHERE name = 'Alice'
);

-- Self join approach
SELECT s1.name
FROM staff s1 INNER JOIN staff s2
ON s1.department_id = s2.department_id
WHERE s2.name = 'Alice';

Natural Join: Automatically connects tables using all columns with matching names, equivalent to an implicit equi-join on those columns.

SELECT t1.value, t2.value
FROM table_a t1 NATURAL JOIN table_b t2;

Outer Joins: Preserve unmatched rows from one or both tables:

• Left outer join: Retains rows from the left table without matches, filling right side columns with nulls
• Right outer join: Retains rows from the right table without matches
• Full outer join: Retains unmatched rows from both tables

Outer joins replace subqueries that would otherwise require complex union operations to achieve similar results.