SQL Join Algorithms Lab (Interactive)
Swap nested-loop, hash, and sort-merge physical plans over growing tables. Compare nested-loop, hash, and sort-merge join costs as table sizes grow exponentially, toggle the FK index, and measure how badly the ORM N+1 pattern defeats the database.
Physical Join Engine: NL vs Hash vs Sort-Merge
Pick the optimizer's physical algorithm and see real operation counts — plus the ORM N+1 penalty next door.
How It Works Under the Hood
A JOIN clause only states what the result should be; the engine chooses a physical algorithm to produce it. Index nested loop scans the smaller table and probes an index O(M log N) — cheap when the foreign key is indexed. Hash join builds an in-memory hash table on the smaller input and probes it once, spilling to disk past work_mem. Sort-merge joins two sorted streams. Without the FK index the planner falls back to O(M×N) nested loop, and ORM lazy loading multiplies everything into N+1 network round trips.
Core Architectural Principles
- Indexed nested loop costs O(M log N) and wins for small inputs with a supporting index; unindexed it degenerates to O(M×N).
- Hash join builds a hash table on the smaller relation and probes it once, spilling batches to disk when work_mem is exceeded.
- The N+1 problem: one query fetches parents and N follow-up queries fetch children, so network round-trip latency dominates the SQL join alternative.
When designing or debugging an API, separate logical join semantics from physical algorithms. Always index foreign keys so the planner can choose indexed nested loop; verify eager loading to kill N+1. For large equi-joins say hash join; for already-sorted or very large inputs say sort-merge — and quantify with row counts.
Each join algorithm trades memory, sort cost, and index dependency differently — the right pick depends on row counts, available work_mem, and index support.