When joining Users (10k rows) with Orders (50M rows), the PostgreSQL planner evaluates estimated disk page I/O and CPU costs. It chooses a Hash Join (building an in-RAM hash table of Users, then streaming Orders) or an Index Nested Loop Join if filtered to a single user.
-- Analyzing Query Execution Plans in PostgreSQL EXPLAIN (ANALYZE, BUFFERS, VERBOSE) SELECT u.user_id, u.email, COUNT(o.order_id) AS total_orders, SUM(o.amount) AS total_spent FROM users u INNER JOIN orders o ON u.user_id = o.user_id WHERE u.country = 'CANADA' AND o.created_at >= '2024-01-01' GROUP BY u.user_id, u.email HAVING SUM(o.amount) > 500 ORDER BY total_spent DESC LIMIT 50;
Visual representation of control loops, memory layout, and execution flow for Query Processing, Execution Engines & Cost-Based Optimization.
1. Parsing: Verifies syntax, builds Abstract Syntax Tree (AST). 2. Semantic Analysis / Catalog Lookup: Binds column names to database catalog, verifies types and user access privileges. 3. Logical Plan Generation: Converts AST into Relational Algebra expression tree. 4. Logical Optimization (Heuristics): Pushes selections (filters) down closer to base tables (Predicate Pushdown) to minimize intermediate row counts; eliminates redundant columns (Projection Pruning). 5. Physical Cost Optimization: Generates candidate physical plans (e.g. Seq Scan vs Index Scan, Hash Join vs Sort-Merge) and estimates total cost using catalog statistics.
1. Nested Loop Join: For each outer tuple in R, scan inner relation S. Cost: O(|R| * |S|) disk reads. With an index on S (Index Nested Loop Join), cost drops to O(|R| * log(S)). Best for small outer tables. 2. Sort-Merge Join: Sort both relations on join key, then scan both simultaneously with a two-pointer merge. Cost: O(|R|log|R| + |S|log|S| + |R| + |S|). Best when inputs are already sorted or for range join conditions. 3. Hash Join: Build Phase: Hashes smaller relation into in-memory hash table. Probe Phase: Streams larger relation, probing hash table for matches. Cost: O(3 * (|R| + |S|)). Best for large unsorted tables with equality join predicates.
Cost Model Formula: Cost = (Page Fetches * Disk_Page_Cost) + (Tuples Processed * CPU_Tuple_Cost) + (Operators * CPU_Operator_Cost). Selectivity (s): Fraction of rows satisfying a predicate. For equality `column = constant`, Selectivity s = 1 / Distinct_Values(column). For range `column > val`, calculated via Equi-width or Equi-depth Histograms maintained by `ANALYZE` worker.
EXPLAIN shows the optimizer estimated plan (cost, estimated rows, width). EXPLAIN ANALYZE actually executes the query and prints REAL runtime statistics (actual time in ms, actual rows returned, loops, buffer hits vs disk reads). Scan Types: - Seq Scan: Full table scan from start to end. - Index Scan: Traverses B+ Tree, then reads corresponding heap page for each matching tuple. - Index Only Scan: Reads everything from B+ Tree payload without visiting heap pages. - Bitmap Index Scan: Gathers matching tuple pointers from index into a memory bitmap, sorts them by physical page order, then reads disk pages sequentially to prevent random I/O.
| Feature / Dimension | Nested Loop Join | Hash Join |
|---|---|---|
| Best Used When | One table is tiny (< 100 rows) or inner table has a high-selectivity B+ Tree index | Both tables are large, unsorted, and joined on an equality predicate (=) |
| Memory Requirements | Minimal (1 page buffer for outer, 1 for inner) | Requires sufficient RAM (work_mem) to hold the entire build hash table |
| Non-Equality Joins (<, >, BETWEEN) | Supported (can evaluate arbitrary theta join conditions) | NOT supported (hash functions only match exact equality) |
Detailed answers, interviewer pro tips, key takeaway summaries, and code examples formulated for technical rounds.
✅ Correction: If a query matches a large percentage of table rows (e.g. > 20%), an Index Scan would cause millions of slow random disk seeks. The optimizer correctly switches to a fast Sequential Scan with sequential read-ahead I/O.
✅ Correction: EXPLAIN only shows the optimizer's mathematical cost ESTIMATE without running the query. EXPLAIN ANALYZE actually executes the query and reports real elapsed millisecond timings and actual row counts.
Transforming declarative SQL statements into optimal physical execution tree plans.