System Design
1. System Prerequisites

Query Optimization & EXPLAIN Plans

⏱ 0s active on this topic

In simple words

When you write a database query, you say what you want, not how to get it. The database has a built-in planner (the query optimizer) that decides how: which index to use, and in what order to combine tables. The same query can run in milliseconds or in minutes depending on that choice. EXPLAIN is a command that shows you the plan it chose, so when a query is slow you can see why — usually a missing index, or a step that reads far more rows than it needs — and fix it.

What is Query Optimization?

Query optimization is the process by which the database automatically determines the most efficient way to execute a SQL query, and the manual techniques developers use to help the database make better decisions.

You write SQL (declarative — WHAT you want):
  SELECT u.name, COUNT(o.order_id)
  FROM users u JOIN orders o ON u.user_id = o.user_id
  WHERE o.created_at > '2024-01-01'
  GROUP BY u.user_id
  ORDER BY COUNT DESC LIMIT 10;

The query optimizer decides HOW to execute it:
  Which table to scan first?
  Which index to use?
  Which join algorithm? (Nested Loop / Hash Join / Merge Join)
  What order to apply filters?
  Can any operations be skipped?

Same SQL → 10x to 1000x performance difference
depending on whether the optimizer makes good choices

The Query Optimizer — How It Works

SQL Query
    ↓
Parser (syntax check)
    ↓
Resolver (validate tables/columns exist)
    ↓
Query Rewriter (logical transformations — e.g. subquery → join)
    ↓
Query Optimizer ← THIS IS THE KEY STEP
  - Enumerates possible execution plans
  - Estimates cost of each plan (using statistics: table size, cardinality, etc.)
  - Picks the lowest-cost plan
    ↓
Execution Engine (runs the chosen plan)
    ↓
Results

Optimizer Statistics

The optimizer relies on statistics — metadata about the data distribution.

For each table, MySQL/PostgreSQL maintains:
  - Row count (approximate)
  - Index cardinality (number of distinct values per index)
  - Data distribution histograms (in newer versions)

How statistics go stale:
  Table has 100 rows → optimizer estimates 100 rows in plan
  After bulk insert → table has 10 million rows
  Statistics not updated → optimizer still thinks 100 rows
  → Wrong plan chosen → terrible performance

Update statistics:
  MySQL:      ANALYZE TABLE users;
  PostgreSQL: ANALYZE users;
  SQL Server: UPDATE STATISTICS users;

Run ANALYZE regularly on tables with frequent inserts/deletes

EXPLAIN — Reading the Execution Plan

EXPLAIN shows you exactly how MySQL plans to execute your query before actually running it.

EXPLAIN SELECT u.name, COUNT(o.order_id) AS order_count
FROM users u
JOIN orders o ON u.user_id = o.user_id
WHERE o.created_at > '2024-01-01'
GROUP BY u.user_id
ORDER BY order_count DESC
LIMIT 10;

EXPLAIN Output — Each Column Explained

┌────┬─────────────┬───────┬────────┬───────────────────┬─────────────┬──────┬────────────────────────┐
│ id │ select_type │ table │  type  │   possible_keys   │     key     │ rows │         Extra          │
├────┼─────────────┼───────┼────────┼───────────────────┼─────────────┼──────┼────────────────────────┤
│  1 │ SIMPLE      │ o     │ range  │ idx_created_at    │idx_created  │50000 │ Using index condition  │
│  1 │ SIMPLE      │ u     │ eq_ref │ PRIMARY           │ PRIMARY     │    1 │                        │
└────┴─────────────┴───────┴────────┴───────────────────┴─────────────┴──────┴────────────────────────┘

Column: type — Most Important Column

The type column shows the access method — how the table is read. From WORST to BEST performance:

ALL        → Full table scan. No index. Reads every row.
             RED FLAG for large tables. Fix: add an index.

index      → Full index scan. Scans entire index (not table).
             Better than ALL but still scans everything.
             OK for small tables or covering index scenarios.

range      → Index range scan. Uses index to find a range of values.
             Good. Used for BETWEEN, >, <, IN, LIKE 'prefix%'

ref        → Non-unique index lookup. Finds all rows matching a value.
             Good. Used for non-unique indexes on equality (user_id in orders).

eq_ref     → Unique index lookup. At most ONE row per key value.
             Very good. Used for PRIMARY KEY or UNIQUE index join conditions.

const      → At most one matching row, read once and treated as constant.
             Best for single-row lookups by PK or UNIQUE.
             e.g. WHERE user_id = 1 (primary key)

system     → Table has exactly one row. Rare special case of const.

NULL       → MySQL can answer without accessing the table at all.
             e.g. SELECT MIN(id) FROM users (from index alone)

Performance ranking (best to worst):
  NULL > system > const > eq_ref > ref > range > index > ALL

Column: key — Which Index Was Used

possible_keys: indexes that COULD be used for this query
key:           index the optimizer ACTUALLY chose
key_len:       how many bytes of the index were used
               (for composite indexes — tells you how many columns were used)

key = NULL → no index used → full table scan → likely needs an index

Column: rows — Estimated Rows Scanned

The optimizer's estimate of rows it will examine.
This is an ESTIMATE based on statistics — not the actual count.

rows = 1         → excellent (single row lookup)
rows = 50000     → acceptable if filtered well after
rows = 10000000  → red flag — scanning most of the table

Column: Extra — Additional Information

Using index          → COVERING INDEX hit. No table lookup needed. ✅ Best case.
Using where          → WHERE filter applied after index scan (not all index)
Using index condition → Index Condition Pushdown (ICP). Filter pushed into index scan. ✅
Using temporary      → Query requires a temp table (GROUP BY, DISTINCT). ❌ Expensive.
Using filesort       → Sort cannot use index. External sort needed. ❌ Expensive.
Using join buffer    → Join uses a buffer (no index on join column). ❌ Add index on join.
Select tables optimized away → Result computed from index statistics alone. ✅ Very fast.
Impossible WHERE     → WHERE condition can never be true. Query returns nothing.

EXPLAIN ANALYZE — Actual Execution (MySQL 8.0+, PostgreSQL)

-- EXPLAIN shows estimated plan
-- EXPLAIN ANALYZE actually RUNS the query and shows real numbers

EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 1 ORDER BY created_at DESC LIMIT 20;

-- MySQL 8.0+ output:
-> Limit: 20 row(s)  (actual time=0.523..0.531 rows=20 loops=1)
    -> Sort: orders.created_at DESC  (actual time=0.520..0.525 rows=20 loops=1)
        -> Index lookup on orders using idx_user_id (user_id=1)
           (actual time=0.089..0.312 rows=147 loops=1)

-- PostgreSQL output:
Limit  (cost=0.43..5.22 rows=20 width=68) (actual time=0.089..0.112 rows=20 loops=1)
  -> Index Scan using idx_user_orders on orders
     (cost=0.43..38.2 rows=147 width=68) (actual time=0.085..0.105 rows=20 loops=1)
       Index Cond: (user_id = 1)
Planning Time: 0.231 ms
Execution Time: 0.156 ms

Key difference:
  EXPLAIN: estimated cost and rows (safe, doesn't execute)
  EXPLAIN ANALYZE: actual timing and row counts (executes the query!)
                   For slow queries on large tables → may take long to run
                   For DELETE/UPDATE → use with caution (actually modifies data)
                   Wrap in BEGIN/ROLLBACK to safely analyze write queries:

BEGIN;
EXPLAIN ANALYZE DELETE FROM orders WHERE status = 'CANCELLED';
ROLLBACK;

Common Slow Query Patterns and Fixes

Pattern 1 — Missing Index (Full Table Scan)

-- ❌ Slow: no index on email, full scan of 10M rows
SELECT * FROM users WHERE email = 'alice@email.com';
-- EXPLAIN shows: type=ALL, rows=10000000

-- ✅ Fix: add index
CREATE INDEX idx_users_email ON users(email);
-- EXPLAIN shows: type=ref, rows=1

Pattern 2 — Function on Indexed Column (Index Bypass)

-- ❌ Slow: YEAR() function prevents index usage
SELECT * FROM orders WHERE YEAR(created_at) = 2024;
-- EXPLAIN: type=ALL (index on created_at is bypassed)

-- ✅ Fix: use range query instead
SELECT * FROM orders
WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';
-- EXPLAIN: type=range (index used)

-- Other common violations:
WHERE LOWER(email) = 'alice@email.com'     -- ❌ use index on LOWER(email)
WHERE DATE(created_at) = '2024-01-15'      -- ❌ use range query
WHERE CONCAT(first_name,' ',last_name) = X -- ❌ store full_name separately

Pattern 3 — Leading Wildcard (LIKE)

-- ❌ Slow: leading % forces full scan
SELECT * FROM products WHERE name LIKE '%shoes%';
-- EXPLAIN: type=ALL

-- ✅ Fix option 1: Use full-text search for text matching
ALTER TABLE products ADD FULLTEXT INDEX ft_name (name);
SELECT * FROM products WHERE MATCH(name) AGAINST ('shoes');

-- ✅ Fix option 2: Use Elasticsearch/OpenSearch for product search
-- Don't do text search in relational DB at scale
-- Index products into Elasticsearch, query there

-- ✅ Trailing wildcard is OK (uses B-Tree prefix):
SELECT * FROM users WHERE name LIKE 'Ali%';
-- EXPLAIN: type=range (index used)

Pattern 4 — N+1 Query Problem

-- ❌ N+1: 1 query to get 100 users, then 100 queries for their orders
users = SELECT * FROM users LIMIT 100;         -- 1 query
FOR each user:
    orders = SELECT * FROM orders              -- 100 queries!
             WHERE user_id = user.id;

-- Total: 101 queries → terrible for 1000 users → 1001 queries

-- ✅ Fix: JOIN to get everything in one query
SELECT u.*, o.*
FROM users u
LEFT JOIN orders o ON u.user_id = o.user_id
LIMIT 100;
-- Total: 1 query

-- ✅ Fix alternative: IN clause batch fetch
user_ids = [1, 2, 3, ..., 100]
SELECT * FROM orders WHERE user_id IN (1, 2, 3, ..., 100);
-- Total: 2 queries

N+1 is the most common performance killer in ORM-based apps.
Hibernate/JPA: use JOIN FETCH or batch fetching.
Sequelize: use include with eager loading.

Pattern 5 — SELECT * (Over-Fetching)

-- ❌ SELECT * fetches all columns even if you need only 2
SELECT * FROM orders WHERE user_id = 1;
-- Fetches: order_id, user_id, status, amount, shipping_address,
--          payment_method, notes, created_at, updated_at, ...
-- All transferred over network, all materialized in memory

-- ✅ Select only what you need
SELECT order_id, status, amount FROM orders WHERE user_id = 1;
-- Benefits:
--   Less network transfer
--   Smaller memory footprint
--   Enables covering index (if indexed columns match SELECT)
--   Query can avoid touching table entirely if using covering index

Pattern 6 — Inefficient Pagination (OFFSET)

-- ❌ Large OFFSET is slow: skip 1,000,000 rows then return 20
SELECT * FROM orders ORDER BY created_at DESC LIMIT 20 OFFSET 1000000;
-- DB must generate first 1,000,020 rows, then discard 1,000,000 → wasteful

-- ✅ Fix: Keyset Pagination (Cursor-based)
-- First page:
SELECT * FROM orders ORDER BY created_at DESC, order_id DESC LIMIT 20;
-- Returns rows: last row has created_at='2024-01-15', order_id=9876

-- Next page: use last row's values as cursor
SELECT * FROM orders
WHERE (created_at, order_id) < ('2024-01-15', 9876)
ORDER BY created_at DESC, order_id DESC
LIMIT 20;
-- Uses index on (created_at, order_id) → O(log n) regardless of page depth

-- ✅ Alternative: Remember the last ID (simpler if sorted by PK)
SELECT * FROM orders WHERE order_id < 9876 ORDER BY order_id DESC LIMIT 20;

Pattern 7 — Missing JOIN Index

-- ❌ Join without index on join column (right side)
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.user_id = o.user_id;  -- user_id in orders has no index

-- EXPLAIN shows: Using join buffer (Block Nested Loop)
-- For each row in users, scan entire orders table → O(n×m)
-- users=1M, orders=10M → 10 trillion comparisons

-- ✅ Fix: index the JOIN column on the many-side table
CREATE INDEX idx_orders_user_id ON orders(user_id);
-- EXPLAIN shows: eq_ref or ref, dramatically fewer rows examined

Pattern 8 — Implicit Type Conversion

-- Table: users.user_id is INT
-- ❌ String passed to INT column
SELECT * FROM users WHERE user_id = '123';
-- MySQL converts '123' to INT → still uses index (MySQL handles this)

-- BUT: if index column is VARCHAR and you pass INT:
-- Table: sessions.token is VARCHAR
SELECT * FROM sessions WHERE token = 12345;  -- INT passed to VARCHAR column
-- MySQL must convert every token to INT → full table scan → index bypassed ❌

-- ✅ Always match data types in queries to column definitions
SELECT * FROM sessions WHERE token = '12345';  -- VARCHAR → VARCHAR ✅

Join Algorithms — What the Optimizer Chooses

1. Nested Loop Join (NLJ)
   For each row in outer table, scan inner table for matches.
   Efficient when inner table is small or well-indexed.
   O(n × m) without index, O(n × log m) with index on inner.

   EXPLAIN Extra: (nothing special, or Using index)
   Best for: small tables, or when inner table has index on join column.

2. Block Nested Loop Join (BNL)
   Loads outer table rows into a join buffer (block).
   For each buffer load, scans inner table once.
   Better than NLJ when inner has no index (fewer scans).

   EXPLAIN Extra: Using join buffer (Block Nested Loop)
   Sign: index missing on join column → add index to fix.

3. Hash Join (PostgreSQL, MySQL 8.0+)
   Build phase: hash table from smaller table on join key.
   Probe phase: scan larger table, probe hash table for matches.
   O(n + m) — very efficient for large tables with no useful indexes.

   EXPLAIN Extra: (hash) or Hash Join in PostgreSQL EXPLAIN

   Best for: large tables, equi-joins, no good index available.
   Memory intensive: join buffer must fit in memory.

4. Merge Join (Sort-Merge Join)
   Sort both tables on join key, then merge like merge-sort.
   Efficient when both inputs are already sorted (via index).
   O(n log n + m log m) for sort, O(n + m) for merge.

   Best for: range joins, both tables large and sortable.

Query Rewriting Techniques

1. Subquery → JOIN (Usually Faster)

-- ❌ Correlated subquery: runs once per row
SELECT * FROM users u
WHERE EXISTS (
    SELECT 1 FROM orders o
    WHERE o.user_id = u.user_id
      AND o.created_at > '2024-01-01'
);

-- ✅ Rewrite as JOIN (single pass)
SELECT DISTINCT u.*
FROM users u
JOIN orders o ON u.user_id = o.user_id
WHERE o.created_at > '2024-01-01';

2. OR → UNION (When OR Prevents Index Use)

-- ❌ OR across different indexed columns — optimizer may not use both indexes
SELECT * FROM orders
WHERE user_id = 1 OR product_id = 'P01';

-- ✅ UNION uses each index separately
SELECT * FROM orders WHERE user_id = 1
UNION
SELECT * FROM orders WHERE product_id = 'P01';
-- Each part uses its own index → combined with UNION dedup

3. NOT IN → LEFT JOIN / NOT EXISTS

-- ❌ NOT IN with subquery — slow, and fails silently if subquery returns NULL
SELECT * FROM users
WHERE user_id NOT IN (SELECT user_id FROM orders WHERE status = 'BANNED');

-- ✅ LEFT JOIN (faster and NULL-safe)
SELECT u.*
FROM users u
LEFT JOIN orders o ON u.user_id = o.user_id AND o.status = 'BANNED'
WHERE o.user_id IS NULL;

-- ✅ NOT EXISTS (also good, optimizer often converts internally)
SELECT * FROM users u
WHERE NOT EXISTS (
    SELECT 1 FROM orders o
    WHERE o.user_id = u.user_id AND o.status = 'BANNED'
);

Slow Query Log — Finding Problems Proactively

-- Enable slow query log (MySQL)
SET GLOBAL slow_query_log = 'ON';
SET GLOBAL long_query_time = 1;  -- log queries taking > 1 second
SET GLOBAL slow_query_log_file = '/var/log/mysql/slow.log';

-- Analyze slow query log
-- mysqldumpslow tool (MySQL)
mysqldumpslow -s t -t 10 /var/log/mysql/slow.log
-- -s t: sort by total query time
-- -t 10: top 10 queries

-- pt-query-digest (Percona Toolkit — more powerful)
pt-query-digest /var/log/mysql/slow.log

-- PostgreSQL: pg_stat_statements extension
SELECT query, calls, mean_exec_time, total_exec_time
FROM pg_stat_statements
ORDER BY total_exec_time DESC
LIMIT 10;
-- Shows top 10 queries by total execution time
-- Most valuable for finding repeated slow queries

Query Optimization Checklist

Before writing a query:
  □ Do I need all these columns? → remove SELECT *
  □ Can I filter more rows early? → push WHERE conditions to reduce data early
  □ Is this join necessary? → can I denormalize or cache?

After writing a query:
  □ Run EXPLAIN — check type column for 'ALL'
  □ Check key column — is an index being used?
  □ Check rows — is the estimated row count reasonable?
  □ Check Extra — 'Using filesort' or 'Using temporary' = problem
  □ Are all JOIN columns indexed on the many-side table?
  □ Any functions on indexed columns in WHERE clause?

If query is slow despite indexes:
  □ Run ANALYZE TABLE to refresh statistics
  □ Check if index selectivity is too low
  □ Consider composite/covering index
  □ Check for lock contention (SHOW PROCESSLIST)
  □ Check for N+1 pattern in application layer
  □ Consider caching frequently-read results in Redis

System Design Context

Query Optimization at Scale

1 query × 100ms × 1 request/second     = 100ms total per second (fine)
1 query × 100ms × 10,000 requests/sec  = 1,000,000ms total per second
                                        = 16.7 minutes of DB time per second
                                        → impossible → DB saturated

Optimization target: p99 latency
  p99 = 99th percentile — 99% of queries complete within this time
  If p99 = 500ms → 1% of users see 500ms+ → too slow for API
  Target: p99 < 50ms for read queries, < 100ms for write queries

Tools used at scale:
  Slow query log → find worst offenders
  APM tools (Datadog, New Relic) → trace queries per request
  Database proxies (ProxySQL) → query analysis, caching, routing
  Read replicas → offload read queries from primary
  Query result caching (Redis) → bypass DB entirely for hot reads

When Optimization Isn't Enough

Even with perfect indexes, a single DB node has limits:
  ~10,000-50,000 simple queries/second on modern hardware
  Complex queries: much lower

Beyond single-node capacity:
  Read replicas → scale reads horizontally (Topic 15)
  Sharding → scale writes horizontally (Topic 16)
  Caching → eliminate DB calls for hot data (Module 6 in roadmap)
  CQRS → separate read model optimized for queries (later topic)

Query optimization is the FIRST step.
Architecture changes (caching, sharding) come when optimization hits its ceiling.

How This Connects

  • Indexing - B-Tree & Hash Indexes / Composite & Covering Indexes — 90% of query tuning is "add the right index" or "make the existing one cover / reorder its columns"; EXPLAIN is how you confirm it landed.
  • SQL - Joins, Aggregations, Subqueries — the join algorithms (nested loop / hash / merge) and the rewrites (subquery→join, OR→UNION, NOT IN→NOT EXISTS) live at the intersection of the two notes.
  • Concurrency Control - Locks & MVCC — a slow query isn't only I/O: lock waits and MVCC version chains (from long transactions) also show up as latency.
  • Module 6 — Caching — when the query is already optimal and still too hot, the next layer is Redis result caching, then read replicas.
  • Module 4 — Sharding / CQRS — when a single node can't keep up even with perfect plans, you split reads/writes or shard; a denormalized read model removes the expensive join entirely.
  • Module 8 — Observability — the slow query log, pg_stat_statements, and APM traces are how you find the query worth optimizing.

In the Interview

When to say it. Any "this endpoint got slow", any "the DB is at 90% CPU", any follow-up after you propose a schema — "show me the query and how you'd make it fast".

The ~20-second version:

"I start with EXPLAIN. The type column first — ALL means a full table scan, so the fix is almost always an index on the WHERE or JOIN columns. The Extra column next — Using filesort means the ORDER BY isn't served by an index, Using temporary means a GROUP BY or DISTINCT is building a temp table, and Using index is the goal: a covering index answering the query without touching the table. Then I look for the classic anti-patterns: a function wrapping an indexed column so the index can't be used, an ORM N+1 that should be one join, deep OFFSET pagination that should be keyset, and unindexed join columns. I run ANALYZE to refresh statistics, verify with EXPLAIN ANALYZE that estimated and actual rows agree, and if the query is already optimal I move up a layer — cache the result, add read replicas, or reshape the data model."

Follow-ups to expect:

  1. "WHERE YEAR(created_at) = 2024 is slow — why and fix?" — The function makes it non-sargable; the index on created_at can't be traversed. Rewrite as created_at >= '2024-01-01' AND created_at < '2025-01-01'.
  2. "Page 50,000 of results loads slowly — LIMIT 20 OFFSET 1000000." — The DB generates and discards a million rows. Switch to keyset/cursor pagination: WHERE (created_at, id) < (:last_ts, :last_id) ORDER BY ... LIMIT 20.
  3. "EXPLAIN says rows: 5 but the query still takes 2s." — Stale statistics (run ANALYZE), or the cost is elsewhere: Using filesort/Using temporary, lock waits, or a huge row width forcing lots of I/O per row.
  4. "N+1 — how do you spot and fix it?" — 1 query for the list + N for each item's children. Fix with a JOIN FETCH / eager load, or a single WHERE id IN (...) batch.
  5. "Optimization isn't enough — what next?" — Redis for hot reads, read replicas for read scaling, denormalized read model / CQRS, then sharding for write scaling.

Mistake to avoid: adding indexes blindly until it's fast. Each one taxes writes, and the planner may still ignore a non-selective or function-shadowed one. Read the plan, make one targeted change, re-measure.

Quick Revision — 7 Lines

  1. EXPLAIN type column: ALL=full scan❌, range=index range✅, ref=index lookup✅, const=single row✅
  2. Extra column: 'Using index'=covering index✅, 'Using filesort'=sort needs fix❌, 'Using temporary'=temp table❌
  3. Functions on indexed columns bypass indexes — use range queries instead
  4. N+1 problem: 1 query + N queries per row → fix with JOIN or IN batch fetch
  5. Large OFFSET pagination is O(n) → replace with keyset/cursor pagination
  6. Always index JOIN columns on the many-side table — missing join index → join buffer (slow)
  7. Optimization order: indexes first → query rewrite → statistics → caching → read replicas → sharding

Quick-revision quiz

Question 1 of 18
In MySQL EXPLAIN, the `type` column shows `ALL`. What does that mean and what's the usual first fix?