What JOIN types exist

A JOIN is an SQL operation that combines rows from two or more tables based on a related column between them.

🟢 Junior Level

A JOIN is an SQL operation that combines rows from two or more tables based on a related column between them.

Why Relational Databases Use JOINs

Relational databases are normalized: data is split across specialized tables (such as users and orders) to eliminate data redundancy and prevent update anomalies. JOIN operations stitch related entities back together dynamically at query time.

Simple Analogy

Imagine two spreadsheets:

Sheet A (Customers): customer_id, name, city
Sheet B (Orders): order_id, customer_id, total_amount

A JOIN compares customer_id across both sheets to produce a single combined row showing which customer made which order.

The 5 Standard Logical JOIN Types

JOIN Type	How It Combines Data	Result When No Match Is Found
`INNER JOIN`	Returns only rows where there is a match in both tables	Discards unmatched rows from both sides
`LEFT JOIN` (`LEFT OUTER`)	Returns all rows from the left table, plus matched rows from the right table	Fills right-side columns with `NULL`
`RIGHT JOIN` (`RIGHT OUTER`)	Returns all rows from the right table, plus matched rows from the left table	Fills left-side columns with `NULL` (rarely used; rewritten as `LEFT JOIN`)
`FULL JOIN` (`FULL OUTER`)	Returns all rows whenever there is a match in either table	Fills missing columns on either side with `NULL`
`CROSS JOIN`	Computes the complete Cartesian Product of both tables ($N \times M$)	Combines every row of Table A with every row of Table B

-- 1. INNER JOIN: Returns only customers who have placed at least one order
SELECT c.name, o.order_id, o.total_amount
FROM customers c
INNER JOIN orders o ON c.customer_id = o.customer_id;

-- 2. LEFT JOIN: Returns ALL customers, even those with zero orders
SELECT c.name, o.order_id, o.total_amount
FROM customers c
LEFT JOIN orders o ON c.customer_id = o.customer_id;
-- If a customer has no orders, order_id and total_amount will be NULL

🟡 Middle Level

Physical Join Execution Strategies (PostgreSQL Engine)

While SQL syntax specifies the logical relationship, the database execution engine chooses between three distinct physical algorithms:

1. Nested Loop Join

Iterates through each row of the outer table and searches for matches in the inner table:

For each row in Outer Table A:
    Scan Inner Table B for matching join key (ideally via an Index)

Optimal When: The outer table is small (or filtered to few rows) and the inner table has an index on the join key.
Complexity: $O(N \log M)$ with an index; $O(N \times M)$ without an index.

2. Hash Join

Builds an in-memory hash table from the smaller relation and probes it with the larger relation:

Phase 1 (Build): Hash the join keys of the smaller table into memory.
Phase 2 (Probe): Stream through the larger table, hashing each key to check for matches.

Optimal When: Joining large, unsorted datasets with equality predicates (=).
Memory Dependency: Bound by work_mem. If the hash table exceeds work_mem, it spills to disk across multiple batches.
Complexity: $O(N + M)$.

3. Merge Join

Requires both inputs to be sorted by the join key before advancing two pointers in parallel:

Sort Input A by join_key (or retrieve via pre-sorted B-Tree index)
Sort Input B by join_key (or retrieve via pre-sorted B-Tree index)
Step through both sorted streams simultaneously like a merge sort

Optimal When: Inputs are already pre-sorted by existing B-tree indexes or range/inequality join conditions (<, >).
Complexity: $O(N + M)$ if pre-sorted ($O(N \log N + M \log M)$ if explicit sorting is required).

Advanced Relational Joins

Semi-Join (`EXISTS` / `IN`)

Returns rows from the left table as soon as the first match is found in the right table without duplicating rows:

-- Returns customers who have placed at least one order (no duplicate customer rows)
SELECT * FROM customers c
WHERE EXISTS (
    SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id
);
-- Compiles to: Hash Semi-Join (much faster than INNER JOIN + DISTINCT)

Anti-Join (`NOT EXISTS`)

Returns rows from the left table where no matching rows exist in the right table:

-- Returns customers who have NEVER placed an order
SELECT * FROM customers c
WHERE NOT EXISTS (
    SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id
);
-- Compiles to: Hash Anti-Join

LATERAL Join (Correlated Subquery Join)

Acts like a parameterized flatMap, allowing the inner subquery to reference columns from the outer table row:

-- For every customer, fetch their top 3 highest-value orders
SELECT c.name, top_orders.order_id, top_orders.total_amount
FROM customers c
LEFT JOIN LATERAL (
    SELECT o.order_id, o.total_amount
    FROM orders o
    WHERE o.customer_id = c.customer_id
    ORDER BY o.total_amount DESC
    LIMIT 3
) top_orders ON true;

🔴 Senior Level

Query Optimizer Mechanics & Join Reordering

1. Join Associativity and Commutativity

INNER JOINs are fully commutative and associative: $(A \bowtie B) \bowtie C \equiv A \bowtie (B \bowtie C) \equiv (A \bowtie C) \bowtie B$ The cost-based optimizer can freely permute the join order across all $N!$ possibilities to discover the cheapest execution path.
OUTER JOINs (LEFT / RIGHT / FULL) are NOT associative: $(A \leftouterjoin B) \leftouterjoin C \not\equiv A \leftouterjoin (B \leftouterjoin C)$ The optimizer’s reordering freedom is constrained, which can prevent it from adopting cheaper execution trees unless conditions allow outer join reduction.

2. Outer Join Elimination (PostgreSQL 10+)

If a query contains a LEFT JOIN, but selects no columns from the right table and the join key on the right table is proven unique (PRIMARY KEY or UNIQUE NOT NULL), the optimizer completely removes the right table from the execution plan:

-- The planner eliminates the 'orders' table scan entirely if orders.order_id is UNIQUE:
SELECT c.customer_id, c.name 
FROM customers c
LEFT JOIN orders o ON c.customer_id = o.customer_id;

3. Genetic Query Optimizer (GEQO)

When a query joins more than geqo_threshold tables (default: 12 tables), calculating exhaustive dynamic programming permutations would consume seconds or minutes of CPU planning time. PostgreSQL switches to a Genetic Algorithm (GEQO) to find a near-optimal plan heuristically.

Multi-Batch Hash Joins & `work_mem` Sizing

When a Hash Join exceeds the allocated memory, EXPLAIN (ANALYZE, BUFFERS) reveals disk spills:

Hash Join (cost=...)
  Batches: 16  Memory Usage: 4096kB  Disk Spill: 85MB  <-- DISK SPILL BOTTLENECK!

The Mitigation:

-- Temporarily expand work_mem for the current analytical session
SET work_mem = '128MB';
-- ⚠️ Note: work_mem is allocated PER operation per backend! 
-- A query with 4 parallel workers executing 2 Hash Joins can allocate:
-- 4 workers * 2 operations * 128 MB = 1024 MB RAM.

4 Tricky Questions

1. Why does `WHERE col NOT IN (SELECT other_col FROM ...)` return zero rows if the subquery returns even a single `NULL`, while `NOT EXISTS` works as expected?

Answer:
This is the infamous Three-Valued Logic (TRUE, FALSE, UNKNOWN) trap in SQL.
The expression id NOT IN (1, 2, NULL) evaluates to: $\text{id} \neq 1 \land \text{id} \neq 2 \land \text{id} \neq \text{NULL}$ In SQL, comparing any value against NULL (x != NULL) yields UNKNOWN.
If all comparisons are true, the expression becomes: $\text{TRUE} \land \text{TRUE} \land \text{UNKNOWN} \equiv \text{UNKNOWN}$ Because an SQL WHERE clause only accepts rows where the predicate evaluates strictly to TRUE, all rows are discarded!
In contrast, NOT EXISTS evaluates whether a row exists or not, returning an unambiguous boolean TRUE or FALSE regardless of NULL columns. Always use NOT EXISTS or LEFT JOIN ... WHERE right.id IS NULL instead of NOT IN.

2. What is the behavioral difference between placing a filter in the `ON` clause versus the `WHERE` clause in a `LEFT JOIN`?

Answer:

Filter in the ON clause: Filters the right table before performing the join.
```
SELECT c.name, o.status 
FROM customers c 
LEFT JOIN orders o ON c.id = o.customer_id AND o.status = 'ACTIVE';
```
If a customer has no active orders, the customer row is still returned, with o.status set to NULL.
Filter in the WHERE clause: Filters the final result after the join.
```
SELECT c.name, o.status 
FROM customers c 
LEFT JOIN orders o ON c.id = o.customer_id 
WHERE o.status = 'ACTIVE';
```
For customers without active orders, o.status is NULL. The condition NULL = 'ACTIVE' evaluates to UNKNOWN (falsy), discarding the customer row completely. This accidentally converts the LEFT JOIN into an INNER JOIN!

3. When will PostgreSQL choose a `Nested Loop Join` over a `Hash Join` on two massive tables, and why is this often a production catastrophe?

Answer:
PostgreSQL chooses a Nested Loop when the optimizer drastically underestimates row cardinality on the outer table due to stale statistics or the Cross-Column Independence Fallacy.
If the planner estimates that the outer filter matches only 3 rows, a Nested Loop with an index seek on the inner table appears cheapest. However, if the actual data matches 500,000 rows, the engine executes 500,000 individual B-tree index seeks on the inner table, locking the CPU and generating hours of random disk I/O.
Remediation: Run ANALYZE, create extended statistics (CREATE STATISTICS), or temporarily execute SET enable_nestloop = off; to force a single-pass Hash Join.

4. How does PostgreSQL handle a `Hash Join` when the hash table exceeds `work_mem`?

Answer:
PostgreSQL implements a Hybrid Grace Hash Join:

It partitions both the outer and inner relations into $2^k$ separate physical batches using a secondary hash function.
Batch 0 is retained in memory, while Batches $1 \dots 2^k - 1$ are written to temporary disk files (BufFile).
The engine completes the join for Batch 0 in RAM.
Next, it reads Batch 1 from disk, builds the in-memory hash table for Batch 1, probes it with Batch 1 of the outer relation, and repeats sequentially for each batch.
While this allows joins of arbitrary size to execute without running out of RAM, it incurs significant temporary file write/read I/O.

🎯 Interview Cheat Sheet

Core Concepts

Logical Types: INNER (both match), LEFT (all left + matched right), RIGHT (all right + matched left), FULL (all both), CROSS ($N \times M$ Cartesian).
Physical Strategies:
- Nested Loop: Outer rows looped over inner index seeks ($O(N \log M)$). Best for small outer row counts.
- Hash Join: In-memory hash table built on smaller input and probed by larger input ($O(N + M)$). Sized by work_mem.
- Merge Join: Simultaneous pointer sweep over pre-sorted inputs ($O(N + M)$).
Specialized Joins:
- Semi-Join (EXISTS): Emits left row on first match; avoids row duplication.
- Anti-Join (NOT EXISTS): Emits left row only when zero right rows match.
- LATERAL Join: Correlated per-row subquery join (ideal for top-N per group).

Critical Traps

NOT IN vs NOT EXISTS: NOT IN fails and returns 0 rows if the subquery returns any NULL. Always use NOT EXISTS.
LEFT JOIN Predicate Placement: A filter on the right table in WHERE turns the query into an INNER JOIN. Put right-table conditions in ON.
Outer Join Removal: The planner automatically removes unused unique LEFT JOIN tables.
GEQO Threshold: Queries joining $> 12$ tables switch to genetic heuristics.

Red Flags (What NOT to Say)

❌ “A JOIN is always faster than a subquery.” (Modern optimizers unnest correlated subqueries into identical Semi-Joins or Hash Joins).
❌ “NOT IN and NOT EXISTS are 100% equivalent.” (Three-valued logic with NULL breaks NOT IN).
❌ “RIGHT JOIN is necessary for advanced SQL.” (Any RIGHT JOIN can and should be rewritten as a LEFT JOIN for clarity).

Difference between INNER JOIN and LEFT JOIN — NULL semantics and outer join mechanics
What is better JOIN or subquery — Query unnesting, CTEs, and decorrelation
What is a correlated subquery — SubPlan execution and LATERAL alternatives
What is Explain plan — Analyzing Hash Join vs Nested Loop nodes