Query Optimization: The Foundation of Database Performance - Database Performance Optimization | OneNoughtOne

0/319

System Design (HLD)Database Performance

Database Performance Optimization

LevelAdvanced

Duration90 mins

TopicDatabase Performance

1 / 5

Query Optimization: The Foundation of Database Performance

The Most Expensive Lines of Code You'll Ever Write

In most production systems, database queries are the single largest contributor to response latency. A single poorly-optimized query can transform a snappy 50ms API response into an agonizing 30-second timeout. At scale, inefficient queries don't just slow down individual requests—they consume database CPU, saturate connection pools, create lock contention, and ultimately cascade into system-wide outages.

Query optimization is not an optional skill—it's a fundamental competency for any engineer building systems that touch persistent data. The difference between a junior developer and a senior engineer is often visible in the SQL they write: one writes queries that work; the other writes queries that scale.

What You Will Learn

By the end of this page, you will understand: how database query planners work and why they make the decisions they do; how to read and interpret execution plans; the systematic methodology for identifying and fixing slow queries; common anti-patterns that kill performance; and advanced techniques used at scale by companies like Netflix, Uber, and Stripe.

Understanding the Query Planner

Before you can optimize queries, you must understand how databases execute them. Every modern relational database contains a sophisticated component called the query planner (or query optimizer) that transforms your SQL statement into an executable plan.

The query planner's job:

Parse the SQL statement into an abstract syntax tree
Analyze the query semantics and validate against the schema
Generate multiple candidate execution plans
Estimate the cost of each plan using statistics
Select the plan with the lowest estimated cost
Execute the chosen plan

The critical insight is that the same SQL query can be executed in radically different ways. Consider a simple join between two tables: should the database read table A first, then look up matching rows in B? Or read B first and probe A? Should it use an index, or would a full table scan be faster? These decisions can change query performance by orders of magnitude.

The Planner Is Not Omniscient

Query planners make decisions based on statistics about your data—row counts, value distributions, correlation between columns. If these statistics are stale or inaccurate, the planner may choose a catastrophically bad plan. This is why running ANALYZE (PostgreSQL) or UPDATE STATISTICS (SQL Server) regularly is essential in production systems.

Query Planner Components Across Major Databases
Database	Statistics Command	Plan Cache	Parallel Query	Cost Model
PostgreSQL	ANALYZE	No session-level cache	Yes (9.6+)	Cost-based with I/O, CPU weights
MySQL (InnoDB)	ANALYZE TABLE	Query cache (deprecated 8.0)	Limited	Cost-based, simpler model
SQL Server	UPDATE STATISTICS	Plan cache (global)	Yes	Cost-based with memory grants
Oracle	DBMS_STATS.GATHER_*	Shared pool + AWR	Yes	Cost-based with adaptive plans

Reading Execution Plans

Execution plans are your X-ray vision into query performance. Without them, you're optimizing blind—guessing at what might be slow rather than seeing exactly what the database is doing.

Every database provides a way to view the execution plan:

PostgreSQL: EXPLAIN or EXPLAIN ANALYZE
MySQL: EXPLAIN or EXPLAIN ANALYZE (8.0+)
SQL Server: SET SHOWPLAN_XML ON or graphical plan in SSMS
Oracle: EXPLAIN PLAN FOR or DBMS_XPLAN.DISPLAY

The difference between EXPLAIN and EXPLAIN ANALYZE is critical:

Command	What It Shows	When To Use
EXPLAIN	Estimated plan and costs	Quick look, won't execute query
EXPLAIN ANALYZE	Actual execution with real timings	Deeper analysis, runs the query

execution_plan_example.sql
PostgreSQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
-- Basic EXPLAIN: shows estimated plan only
EXPLAIN 
SELECT o.id, c.name, SUM(o.amount)
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.created_at > '2024-01-01'
GROUP BY o.id, c.name;
 
-- EXPLAIN ANALYZE: executes query and shows actual timings
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT o.id, c.name, SUM(o.amount)
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.created_at > '2024-01-01'
GROUP BY o.id, c.name;
 
-- Example output:
-- Hash Join  (cost=10.50..1050.00 rows=5000 width=64)
--            (actual time=2.1..45.3 rows=4823 loops=1)
--   Hash Cond: (o.customer_id = c.id)
--   Buffers: shared hit=523 read=89
--   ->  Index Scan using orders_created_at_idx on orders o
--       (cost=0.42..800.00 rows=5000 width=32)
--       (actual time=0.05..28.7 rows=4823 loops=1)
--       Index Cond: (created_at > '2024-01-01')
--   ->  Hash  (cost=8.00..8.00 rows=200 width=36)
--       (actual time=0.9..0.9 rows=200 loops=1)
--       ->  Seq Scan on customers c
--           (cost=0.00..8.00 rows=200 width=36)
--           (actual time=0.01..0.4 rows=200 loops=1)
-- Planning Time: 0.8 ms
-- Execution Time: 48.5 ms

How to read an execution plan:

Execution plans are trees read from innermost to outermost (or bottom to top in text format). Each node represents an operation:

Scan operations read data from tables
- Seq Scan: Full table scan (often expensive)
- Index Scan: Uses an index to find rows
- Index Only Scan: Reads only from the index (fastest)
- Bitmap Heap Scan: Uses bitmap of matching pages
Join operations combine data from multiple sources
- Nested Loop: For each row in A, scan B (O(n×m) worst case)
- Hash Join: Build hash table from smaller set, probe with larger
- Merge Join: Merge two sorted inputs (requires sorted data)
Aggregation operations compute summaries
- Aggregate: Compute MIN, MAX, SUM, COUNT, AVG
- HashAggregate: Group using hash table
- GroupAggregate: Group pre-sorted data
Sort operations order data
- Sort: Standard sorting (may spill to disk)
- Incremental Sort: Exploit partial ordering

The Cardinal Sin: Estimations vs Reality

The most dangerous situation is when estimated rows differ dramatically from actual rows. If the planner estimates 100 rows but the query returns 1,000,000, the chosen plan is almost certainly wrong. Look for discrepancies of 10x or more between 'rows' (estimated) and 'actual rows' in EXPLAIN ANALYZE output—these are prime optimization targets.

Common Performance Anti-Patterns

Certain query patterns are almost universally problematic. Learning to recognize and avoid these anti-patterns will prevent the majority of performance issues before they start.

The Seven Deadly Sins of Query Performance

•**SELECT *** — Fetching all columns when you only need a few wastes I/O, network bandwidth, and prevents index-only scans. Always explicitly list the columns you need.
•N+1 Query Pattern — Fetching a parent record, then issuing N separate queries for related records. Use JOINs or batch queries (WHERE id IN (...)) instead.
•Functions on Indexed Columns — WHERE YEAR(created_at) = 2024 cannot use an index on created_at. Rewrite as WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01'.
•Implicit Type Conversions — WHERE varchar_column = 12345 forces conversion of every row. Match types explicitly to enable index usage.
•LIKE with Leading Wildcard — WHERE name LIKE '%Smith' requires a full table scan. Only trailing wildcards ('Smith%') can use B-tree indexes.
•Missing Pagination — Returning unbounded result sets. Always use LIMIT/OFFSET or keyset pagination for user-facing queries.
•Correlated Subqueries — Subqueries that reference outer query columns execute once per outer row. Rewrite as JOINs or use WITH (CTE) for clarity and performance.

anti_pattern.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
-- ❌ ANTI-PATTERN: N+1 queries
-- First query
SELECT id FROM orders 
WHERE status = 'pending';
 
-- Then for EACH order (N queries!)
SELECT * FROM order_items 
WHERE order_id = ?;
 
-- ❌ ANTI-PATTERN: Function on indexed column
SELECT * FROM orders
WHERE DATE(created_at) = '2024-06-15';
 
-- ❌ ANTI-PATTERN: Leading wildcard
SELECT * FROM customers
WHERE email LIKE '%@gmail.com';
 
-- ❌ ANTI-PATTERN: Correlated subquery
SELECT * FROM orders o
WHERE amount > (
  SELECT AVG(amount) 
  FROM orders 
  WHERE customer_id = o.customer_id
);

optimized.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
-- ✅ OPTIMIZED: Single query with JOIN
SELECT o.id, oi.* 
FROM orders o
JOIN order_items oi ON o.id = oi.order_id
WHERE o.status = 'pending';
 
 
-- ✅ OPTIMIZED: Range condition
SELECT * FROM orders
WHERE created_at >= '2024-06-15'
  AND created_at < '2024-06-16';
 
-- ✅ OPTIMIZED: Reverse domain + index
-- Store: reverse(email) or domain column
SELECT * FROM customers
WHERE email_domain = 'gmail.com';
 
-- ✅ OPTIMIZED: Window function or CTE
WITH customer_avg AS (
  SELECT customer_id, AVG(amount) as avg_amt
  FROM orders GROUP BY customer_id
)
SELECT o.* FROM orders o
JOIN customer_avg ca 
  ON o.customer_id = ca.customer_id
WHERE o.amount > ca.avg_amt;

Systematic Query Optimization Methodology

Effective query optimization follows a systematic methodology rather than random experimentation. This section presents a battle-tested framework used by database performance engineers.

The Query Optimization Loop:

The 6-Step Optimization Framework

•Identify — Find the slow query. Use slow query logs, APM tools (Datadog, New Relic), or pg_stat_statements. Prioritize by total time (frequency × duration), not just single-execution time.
•Measure — Establish a baseline. Run EXPLAIN ANALYZE multiple times to get consistent timings. Note: first run may differ due to cold cache. Record buffer hits/reads ratio.
•Analyze — Read the execution plan methodically. Find the nodes consuming most time. Look for Seq Scans on large tables, large row estimate discrepancies, and sorts spilling to disk.
•Hypothesize — Form a specific hypothesis: 'Adding an index on (customer_id, created_at) will convert this Seq Scan to an Index Scan and reduce time from 500ms to 50ms.'
•Implement — Make ONE change at a time. If you change multiple things simultaneously, you won't know which change helped (or hurt).
•Verify — Re-run EXPLAIN ANALYZE. Did the plan change as expected? Did execution time improve? If not, dig deeper—your hypothesis may have been wrong.

The 80/20 Rule of Query Optimization

In practice, 80% of database load comes from 20% of queries (often even more skewed—90/10 or 95/5). Focus your optimization efforts on the queries appearing most frequently in slow query logs. A 10% improvement to a query that runs 1 million times per day beats a 90% improvement to a query that runs 100 times.

What to look for in execution plans:

Warning Sign	What It Means	Typical Solution
`Seq Scan` on large table	No suitable index found	Add covering index
`Rows Removed by Filter: 999000`	Index used but highly non-selective	Better index or query restructure
`Sort Method: external merge Disk`	Sort exceeded work_mem	Increase work_mem or add sorted index
`Hash Batches: 16`	Hash table exceeded memory	Increase work_mem
`Nested Loop` with large inner table	Poor join order or missing index	Add index on join column
`Buffers: read=10000` (high reads)	Data not in cache, hitting disk	Add memory or optimize query

Critical metrics to track:

Execution time: Total wall-clock time
Planning time: Time spent by query planner
Rows returned: Ensure reasonable for use case
Buffer hits vs reads: Cache efficiency (aim for >99% hits)
Temp file usage: Indicates memory pressure

Advanced Query Rewriting Techniques

Sometimes adding an index isn't enough—the query itself needs to be restructured. These advanced techniques can yield dramatic improvements.

Common Table Expressions (CTEs) can improve readability and sometimes performance by materializing intermediate results or helping the planner make better decisions.

SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
-- Complex nested subqueries (hard to read and optimize)
SELECT * FROM products p
WHERE p.category_id IN (
  SELECT DISTINCT c.id FROM categories c
  WHERE c.department_id IN (
    SELECT d.id FROM departments d
    WHERE d.active = true
  )
)
AND p.price > (SELECT AVG(price) FROM products);
 
-- Refactored with CTEs (clearer, easier to optimize)
WITH active_departments AS (
  SELECT id FROM departments WHERE active = true
),
active_categories AS (
  SELECT DISTINCT c.id 
  FROM categories c
  WHERE c.department_id IN (SELECT id FROM active_departments)
),
avg_price AS (
  SELECT AVG(price) as price FROM products
)
SELECT p.* 
FROM products p
CROSS JOIN avg_price ap
WHERE p.category_id IN (SELECT id FROM active_categories)
  AND p.price > ap.price;
 
-- Note: In PostgreSQL 12+, use MATERIALIZED/NOT MATERIALIZED
-- to control whether CTEs are optimized inline or materialized
WITH active_cats AS MATERIALIZED (
  -- This will be computed once and reused
  SELECT id FROM categories WHERE active = true
)
SELECT * FROM products WHERE category_id IN (SELECT id FROM active_cats);

Real-World Query Optimization Case Study

Let's walk through a realistic optimization scenario from initial problem through solution.

Scenario: An e-commerce platform's order search is taking 8+ seconds. The query finds orders matching user-specified filters.

slow_query.sql
SQL
1
2
3
4
5
6
7
8
9
10
-- Original slow query (8.2 seconds)
SELECT o.*, c.name as customer_name, c.email
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status IN ('pending', 'processing')
  AND o.created_at >= '2024-01-01'
  AND o.total_amount > 100
  AND c.country = 'US'
ORDER BY o.created_at DESC
LIMIT 50;

Step 1: Analyze the execution plan

explain_output.txt

Text

Limit  (cost=125000..125000 rows=50) (actual time=8234..8234 rows=50)
  ->  Sort  (cost=125000..126000 rows=4000) (actual time=8232..8233 rows=50)
        Sort Key: o.created_at DESC
        Sort Method: top-N heapsort  Memory: 35kB
        ->  Hash Join  (cost=10000..120000 rows=4000) (actual time=890..8150 rows=3847)
              Hash Cond: (o.customer_id = c.id)
              ->  Seq Scan on orders o  (cost=0..80000 rows=50000)
                       (actual time=0.02..6100 rows=48293)
                    Filter: (status IN ('pending','processing') 
                            AND created_at >= '2024-01-01' 
                            AND total_amount > 100)
                    Rows Removed by Filter: 2951707
              ->  Hash  (cost=9000..9000 rows=80000) (actual time=850..850 rows=82451)
                    ->  Seq Scan on customers c  (cost=0..9000 rows=80000)
                               (actual time=0.01..650 rows=82451)
                          Filter: (country = 'US')
                          Rows Removed by Filter: 117549
Planning Time: 2.1 ms
Execution Time: 8234 ms

Analysis:

Seq Scan on orders — Reading 3M rows, filtering to 48K. No index used!
Rows Removed by Filter: 2.95M — Scanning way more data than needed
Seq Scan on customers — No index on country column
Hash Join — Building 80K row hash table in memory
6+ seconds spent just scanning orders table

Step 2: Form hypotheses and implement solutions

optimization_steps.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
-- Solution 1: Composite index on orders for the WHERE + ORDER BY
CREATE INDEX idx_orders_status_date_amount 
ON orders(status, created_at DESC, total_amount)
WHERE status IN ('pending', 'processing');
 
-- Solution 2: Index on customers.country
CREATE INDEX idx_customers_country ON customers(country);
 
-- After creating indexes, re-run EXPLAIN ANALYZE...
 
-- New execution plan (0.045 seconds!):
-- Limit  (cost=50..100 rows=50) (actual time=42..45 rows=50)
--   ->  Nested Loop  (cost=50..500 rows=4000) (actual time=42..45 rows=50)
--         ->  Index Scan using idx_orders_status_date_amount on orders
--             (cost=0..200 rows=5000) (actual time=0.05..38 rows=52)
--               Index Cond: (status IN ('pending','processing') 
--                           AND created_at >= '2024-01-01' 
--                           AND total_amount > 100)
--         ->  Index Scan using idx_customers_country on customers
--             (cost=0..0.5 rows=1) (actual time=0.1..0.1 rows=1)
--               Index Cond: (country = 'US')
--               Filter: (id = o.customer_id)
-- Execution Time: 45 ms
 
-- RESULT: 8200ms -> 45ms (182x faster!)

The Power of Proper Indexing

This case study demonstrates a common pattern: the original query was fine—the problem was missing indexes. Two targeted indexes reduced execution time from 8.2 seconds to 45 milliseconds. The partial index on status also keeps the index small and fast to update, since it only includes pending/processing orders.

Summary: Query Optimization Mastery

Query optimization is both an art and a science. The science lies in understanding how query planners work, reading execution plans, and applying well-known optimization techniques. The art is in developing intuition for which optimizations matter most and knowing when to stop optimizing.

Key Takeaways

•Understand the query planner — It makes decisions based on statistics; keep statistics fresh with regular ANALYZE.
•Always use EXPLAIN ANALYZE — Never optimize blind. Execution plans reveal exactly where time is spent.
•Watch for row estimate discrepancies — Large differences between estimated and actual rows indicate planner confusion.
•Avoid common anti-patterns — SELECT *, N+1 queries, functions on indexed columns, leading wildcards.
•Follow systematic methodology — Identify, measure, analyze, hypothesize, implement one change, verify.
•Learn advanced techniques — CTEs, LATERAL joins, partial indexes, and materialized views solve problems indexes can't.
•Focus on high-impact queries — Optimize the 20% of queries causing 80% of load.

What's next:

Query optimization works hand-in-hand with indexing strategy. The next page explores indexing in depth—B-tree internals, composite index design, covering indexes, and the critical tradeoffs between read and write performance.

Page Complete

You now have a comprehensive understanding of query optimization. You can read execution plans, identify performance bottlenecks, avoid common anti-patterns, and apply advanced optimization techniques. Next, we'll deep-dive into indexing strategies.