Physical joins

---

What are merge join, hash join, and nested loop? Example in PostgreSQL.Medium

Video explainer

---

Physical joins are the actual algorithms that database engines use to execute join operations. While logical joins (INNER, LEFT, OUTER) describe what you want, physical joins determine how the database retrieves and combines the data.

Logical join = what you ask for Physical join = how the database actually performs it

The Three Main Physical Join Algorithms

1. Nested Loop Join

The simplest approach: for each row in the first table, scan through all rows in the second table looking for matches.

How it works:

For each row in Table A:
    For each row in Table B:
        If join condition matches:
            Return combined row

Example:

SELECT e.name, d.dept_name
FROM employees e
JOIN departments d ON e.dept_id = d.id

If employees has 1,000 rows and departments has 10 rows, the database might scan departments 1,000 times (worst case: 10,000 comparisons).

Best for:

• Small tables

• When one table is tiny (the "inner" table)

• When the outer table returns very few rows after filtering

Visual representation:

Employees (outer)          Departments (inner)
┌─────┬──────────┐        ┌────┬───────────┐
│ ID  │ dept_id  │        │ ID │ dept_name │
├─────┼──────────┤        ├────┼───────────┤
│ 101 │    1     │───┐    │ 1  │   Sales   │
│ 102 │    2     │   └───→│ 2  │   IT      │
│ 103 │    1     │───────→│ 3  │   HR      │
└─────┴──────────┘        └────┴───────────┘
      Scan all →

---

2. Hash Join

The database builds a hash table from one table, then probes it with rows from the other table.

How it works:

Build phase:
    For each row in Table B (build table):
        Hash the join key
        Store row in hash table bucket

Probe phase:
    For each row in Table A (probe table):
        Hash the join key
        Look up matching rows in hash table
        Return combined rows

Example with same query:

Build phase (departments):

Hash Table:
bucket[hash(1)] → {id: 1, dept_name: "Sales"}
bucket[hash(2)] → {id: 2, dept_name: "IT"}
bucket[hash(3)] → {id: 3, dept_name: "HR"}

Probe phase (employees):

Employee 101, dept_id=1 → hash(1) → finds "Sales" instantly
Employee 102, dept_id=2 → hash(2) → finds "IT" instantly
Employee 103, dept_id=1 → hash(1) → finds "Sales" instantly

Best for:

• Large tables with no indexes

• Equality joins (=) only

• When you have sufficient memory

• When tables are similar in size

Performance: O(n + m) where n and m are table sizes

---

3. Merge Join (Sort-Merge Join)

Both tables are sorted by the join key, then merged together like a zipper.

How it works:

Sort phase:
    Sort Table A by join key
    Sort Table B by join key

Merge phase:
    pointer_A = first row of A
    pointer_B = first row of B
    
    While not end of either table:
        If A.key = B.key:
            Output combined row
            Advance both pointers
        Else if A.key < B.key:
            Advance pointer_A
        Else:
            Advance pointer_B

Visual representation:

Sorted Employees        Sorted Departments
dept_id                 id
   1  ─────────┐          1
   1  ─────────┼────────→ 2
   2  ─────────┘          3
   2
   3  ──────────────────→

Best for:

• Tables already sorted (or indexed) on join columns

• Large tables

• Non-equality joins (>, <, BETWEEN)

• When output needs to be sorted anyway

Performance: O(n log n + m log m) if sorting needed, O(n + m) if already sorted

---

Practical Example Comparison

Let's say you're joining orders (1 million rows) with customers (100,000 rows):

SELECT o.order_id, c.customer_name
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
WHERE o.order_date = '2024-01-15'

Query Optimizer's Decision Process:

1. Nested Loop: Used if the WHERE clause filters orders down to ~100 rows. Then it's efficient to loop through customers 100 times.

2. Hash Join: Used if no good indexes exist. Build hash table on customers (smaller table), probe with orders. Fast for large datasets.

3. Merge Join: Used if both tables have indexes on customer_id. No sorting needed, just merge the sorted data streams.

---

How to See What Your Database Is Using

-- PostgreSQL
EXPLAIN ANALYZE
SELECT ...

-- MySQL
EXPLAIN FORMAT=JSON
SELECT ...

-- SQL Server
SET SHOWPLAN_ALL ON
SELECT ...

Look for keywords like:

• "Nested Loop"

• "Hash Join" or "Hash Match"

• "Merge Join"

Key Takeaways

• You don't choose physical joins directly—the query optimizer does

• Indexes matter hugely: They can make nested loops efficient and enable merge joins

• Statistics matter: The optimizer uses table statistics to choose the best algorithm

• Table size matters: Small tables favor nested loops, large tables favor hash/merge

• Memory matters: Hash joins need RAM; if unavailable, optimizer may choose differently

The optimizer considers costs like I/O operations, CPU usage, and memory before selecting the most efficient physical join for your query.