--- title: "Database Query Optimization: Master Class" description: "Learn how to read EXPLAIN and EXPLAIN ANALYZE, optimize JOINs and CTEs, implement keyset pagination, and understand database engine MVCC load behaviors." published: 2026-05-31 faq: - question: "What is the difference between a Sequential Scan and an Index Scan?" answer: "A Sequential Scan reads every page in the table from start to finish to find matching rows. An Index Scan traverses the index tree to locate matching entries and then fetches only the corresponding pages from the heap. For small tables or queries retrieving a large percentage of rows, Seq Scan is often faster than the random I/O of an Index Scan." - question: "What are Nested Loops, Hash Joins, and Merge Joins?" answer: "Nested Loops join tables by scanning the outer table and looking up matching rows in the inner table (optimal for small sets). Hash Joins build a hash table in memory from the smaller relation and scan the larger relation to find matches (optimal for large unsorted sets). Merge Joins sort both relations on the join key and scan them in parallel (optimal for large pre-sorted sets or when index scans can avoid sorting)." - question: "Why is keyset pagination faster than LIMIT/OFFSET?" answer: "LIMIT/OFFSET queries must read and discard all rows up to the offset value, causing O(N) performance degradation as pages get deeper. Keyset pagination uses a WHERE filter on a sorted unique column (like `WHERE id > ?`) to jump directly to the target row using an index, achieving O(log N) constant-time lookup." - question: "What is a CTE optimization fence?" answer: "In older Postgres versions (pre-12), and optionally in newer ones using `MATERIALIZED`, Common Table Expressions (CTEs) act as an optimization barrier where the database executes the CTE first, saves the result to a temporary space, and then joins it. This prevents the optimizer from pushing outer query predicates (like WHERE clauses) down into the CTE, which can lead to slow execution." --- # Database Query Optimization: Master Class A single slow query can bring down an entire enterprise application. In production, database performance is rarely about CPU power; it is about how efficiently the query planner navigates disk pages, builds join tables in memory, and handles concurrency. When you write a SQL query, you are describing *what* data you want, not *how* to get it. The database engine's query optimizer is responsible for plotting the execution plan. To write high-performance applications, you must learn to think like the optimizer. In this master class, we will examine execution plans, dissect join algorithms, explore pagination scaling, and analyze the MVCC mechanics of PostgreSQL and MySQL. --- ## 1. Decoding EXPLAIN and EXPLAIN ANALYZE To optimize a query, you must first inspect its execution plan using `EXPLAIN`. However, a standard `EXPLAIN` only shows the optimizer's *estimation* of the query cost. To see what actually happened during execution, you must use `EXPLAIN ANALYZE` (which actually runs the query). ### Understanding the Cost Indicators (Postgres Format) An execution plan displays costs in the format: `cost=0.00..431.25 rows=10500 width=244`. * **Startup Cost (`0.00`):** The cost incurred before the first row can be returned (e.g., building a hash table or sorting index nodes). * **Total Cost (`431.25`):** The estimated cost to return all rows. This is measured in arbitrary units of page fetches (typically `1.0` for sequential page read, `4.0` for random page read). * **Rows (`10500`):** The estimated number of rows returned. * **Width (`244`):** The average size of returned rows in bytes. ### Node Scan Types 1. **Sequential Scan (Seq Scan):** The engine reads the entire table from beginning to end. It is optimal for small tables or when retrieving $> 20\%$ of the table's rows. 2. **Index Scan:** The engine traverses the index B-Tree, fetches matching TIDs/PKs, and then retrieves the corresponding pages from the heap/table. This involves random disk access. 3. **Index Only Scan:** If all columns selected are in the index itself, the database bypasses table reads entirely. 4. **Bitmap Index Scan & Bitmap Heap Scan (Postgres):** When retrieving multiple matching rows via index, Postgres first builds a bitmap of matching pages in memory (Bitmap Index Scan) and then reads those pages in sequential physical order (Bitmap Heap Scan). This converts slow random I/O into faster sequential I/O. ### Join Algorithms * **Nested Loop:** The database scans the outer table, and for each row, looks up matching rows in the inner table. This is extremely fast for small datasets, especially if the inner table's join column is indexed. * **Hash Join:** The database scans the smaller table, builds a hash table in memory from the join keys, and then scans the larger table, hashing its keys to find immediate matches. This is optimal for large, unsorted datasets. * **Merge Join:** Both tables are sorted by their join keys, and the database scans them in parallel, merging matching rows. This is highly efficient for very large datasets, particularly if they are already pre-sorted by indexes. --- ## 2. Advanced Join Optimization & CTEs Not all joins are created equal. The way you write subqueries and CTEs heavily impacts the optimizer's ability to prune paths. ### Inner vs. Outer Joins and Anti-Joins An anti-join finds records in one table that do *not* exist in another. Developers often write this using `NOT IN`, which has terrible performance and fails if the subquery returns `NULL`. A highly optimized approach is to use `NOT EXISTS`. ```sql -- database/queries/anti_join_bad.sql -- Bad: NOT IN scans the subquery and behaves unexpectedly if NULLs are present SELECT id, name FROM users WHERE id NOT IN (SELECT user_id FROM orders); -- database/queries/anti_join_good.sql -- Good: NOT EXISTS translates to a highly optimized Hash Anti Join or Merge Anti Join SELECT u.id, u.name FROM users u WHERE NOT EXISTS ( SELECT 1 FROM orders o WHERE o.user_id = u.id ); ``` ### LATERAL Joins (Correlated Subqueries) A `LATERAL` join acts like a SQL `foreach` loop. It allows a subquery to reference columns from preceding tables in the `FROM` clause. This is incredibly useful for fetching the "top N" records per group. ```sql -- database/queries/lateral_join.sql -- Fetch the latest 3 orders for each user (Postgres & MySQL 8.0.14+) SELECT u.id, u.name, recent_orders.id AS order_id, recent_orders.amount, recent_orders.created_at FROM users u CROSS JOIN LATERAL ( SELECT o.id, o.amount, o.created_at FROM orders o WHERE o.user_id = u.id ORDER BY o.created_at DESC LIMIT 3 ) AS recent_orders; ``` ### CTE Optimization Fences Common Table Expressions (CTEs) make query code clean, but they historically acted as **optimization fences**. * **Postgres (Pre-12):** CTEs were always materialized (computed and written to temporary space) before running the outer query. This prevented index usage from outer WHERE clauses. * **Postgres (12+):** CTEs are now inlined by default unless they are recursive or side-effecting. You can explicitly force or prevent materialization using `MATERIALIZED` or `NOT MATERIALIZED`. ```sql -- database/queries/cte_fence.sql -- Prevent materialization to allow the query planner to push the user_id predicate down WITH user_stats AS NOT MATERIALIZED ( SELECT user_id, COUNT(*) as total_orders, SUM(amount) as total_spent FROM orders GROUP BY user_id ) SELECT u.name, s.total_orders, s.total_spent FROM users u JOIN user_stats s ON u.id = s.user_id WHERE u.id = 42; ``` --- ## 3. Scaling Query Paths: Keyset Pagination & Partitioning As your database tables grow to billions of rows, simple queries will degrade unless you change the way you scan paths. ### Keyset Pagination (Cursor-based) vs. LIMIT / OFFSET Offset pagination (`LIMIT 10 OFFSET 100000`) forces the database to read and discard 100,000 rows just to return 10. Performance scales linearly ($O(N)$), degrading heavily at deep pages. Keyset pagination filters out previously seen rows using a where clause on a sorted index, scaling at $O(\log N)$ constant-time lookup. ```sql -- database/queries/offset_pagination_bad.sql -- Bad: Scans and discards 100,000 records before returning 10 SELECT id, amount, created_at FROM orders ORDER BY created_at DESC, id DESC LIMIT 10 OFFSET 100000; -- database/queries/keyset_pagination_good.sql -- Good: Jumps directly to the last seen keyset using a composite index scan SELECT id, amount, created_at FROM orders WHERE (created_at, id) < ('2026-05-30 15:30:00', 987654) ORDER BY created_at DESC, id DESC LIMIT 10; ``` > [!NOTE] > Keyset pagination requires a deterministic sort. If you sort on a non-unique column like `created_at`, you must append a unique tie-breaker column like `id` to prevent missing or duplicated rows. ### Table Partitioning Table partitioning breaks up one large table into smaller physical tables (partitions) based on a key (e.g., date ranges), while maintaining a single logical interface. * **Query Pruning:** When a query filters by the partition key, the planner ignores irrelevant partitions entirely, scanning only the matching partition. ```sql -- database/migrations/2026_05_31_partitioned_orders.sql -- PostgreSQL Declarative Range Partitioning CREATE TABLE orders_partitioned ( id BIGINT NOT NULL, user_id BIGINT NOT NULL, amount DECIMAL(10,2) NOT NULL, created_at TIMESTAMP NOT NULL, PRIMARY KEY (created_at, id) ) PARTITION BY RANGE (created_at); -- Create individual partition tables CREATE TABLE orders_2026_q1 PARTITION OF orders_partitioned FOR VALUES FROM ('2026-01-01 00:00:00') TO ('2026-04-01 00:00:00'); ``` --- ## 4. MVCC, Vacuuming, and Purge Lag Concurrency in modern databases is achieved through **Multi-Version Concurrency Control (MVCC)**. Instead of locking rows for reading, databases keep multiple versions of a row concurrently. ### PostgreSQL MVCC & Autovacuum In Postgres, every row (tuple) is stored on disk with metadata headers including `xmin` (the transaction ID that created the row) and `xmax` (the transaction ID that deleted/expired the row). * **Updates:** An `UPDATE` does not overwrite the row. It writes a completely new tuple to the heap and sets `xmax` on the old tuple to point to the updating transaction. * **Bloat:** The old version of the row becomes a "dead tuple" once no active transaction can see it. * **Vacuuming:** Postgres requires `VACUUM` (managed by the autovacuum daemon) to scan pages, reclaim space occupied by dead tuples, and update the visibility map. If autovacuum cannot keep up with heavy write workloads, table and index bloat will degrade query performance. ### MySQL InnoDB MVCC & Undo Logs MySQL's InnoDB engine handles MVCC differently. * **Updates in Clustered Index:** InnoDB performs updates in-place inside the clustered index leaf node. * **Undo Logs & Rollback Segments:** The old version of the row is not stored in the main table. Instead, InnoDB writes the historical row state to the **Undo Log** and stores a rollback pointer inside the updated row. When a reader transaction needs an older version, it reads the current row and reconstructs the old state using the undo logs. * **Purge Threads:** As old transactions finish, a background process called the **Purge Thread** cleans up undo logs and deletes records that were marked for deletion. Under heavy write workloads, **Purge Lag** can occur, leading to massive undo log file growth and performance degradation. --- ## 5. Common Mistakes ### Mistake 1: Deep Pagination with OFFSET **Bad Practice:** ```sql -- database/queries/bad_pagination.sql SELECT * FROM users ORDER BY id LIMIT 20 OFFSET 50000; ``` *Why it's bad:* The database must scan through the index/heap for 50,000 records, load them into memory, and discard them, consuming CPU and disk I/O. **Good Practice:** ```sql -- database/queries/good_pagination.sql -- Keyset pagination using the last seen ID (e.g. 50000) SELECT * FROM users WHERE id > 50000 ORDER BY id LIMIT 20; ``` *Why it's good:* The database performs an index seek to jump directly to `id > 50000` in $O(\log N)$ time, avoiding unnecessary row scans. ### Mistake 2: Missing Index on Foreign Keys **Bad Practice:** ```sql -- database/migrations/bad_foreign_key.sql CREATE TABLE orders ( id BIGINT AUTO_INCREMENT PRIMARY KEY, user_id BIGINT, FOREIGN KEY (user_id) REFERENCES users(id) ); ``` *Why it's bad:* PostgreSQL and MySQL do not automatically create indexes on foreign key columns. If you frequently join tables on `user_id` or delete users (which triggers cascade checks), the engine must perform a sequential scan on the child table. --- ## 6. Self-Test Quiz ### Question 1 During an `EXPLAIN ANALYZE` run in Postgres, you notice a node labeled `Bitmap Heap Scan` following a `Bitmap Index Scan`. What does this indicate?
Click here to reveal the answer **Answer:** It indicates that Postgres decided that reading rows directly via individual index seeks would result in random I/O that is too slow. Instead: 1. The `Bitmap Index Scan` scanned the index and built a bitmap of table page addresses containing matching rows. 2. The `Bitmap Heap Scan` then read the table pages in sequential physical order, accessing the matching rows on those pages. This turns random I/O into faster sequential disk reads.
--- ### Question 2 Under heavy write load in MySQL InnoDB, why does the undo log tablespace size swell, and how does this affect read queries that need older data?
Click here to reveal the answer **Answer:** When writes are highly intensive, the Purge Thread can lag behind (Purge Lag) in cleaning up historical rollback segments. Consequently, the undo log space grows rapidly to keep track of older row versions. Older read transactions will experience slower performance because they must traverse a long chain of undo logs to reconstruct the state of the data as of their transaction start time.
--- ### Question 3 Why can a CTE defined with a standard `WITH` clause in Postgres 10 cause a performance bottleneck if the outer query filters by a specific ID?
Click here to reveal the answer **Answer:** In Postgres 10 (and older versions), CTEs act as an optimization barrier. The engine evaluates the CTE independently and materializes its full results into memory/disk. Only then does it execute the outer query and apply the `WHERE id = 42` filter. In Postgres 12+ (or by writing `WITH ... AS NOT MATERIALIZED`), the optimizer can "inline" the CTE, allowing it to push the `WHERE id = 42` filter down into the subquery, enabling index-driven scans.