Query Optimization

How Databases Execute Queries

When you submit a SQL query, it goes through several stages before returning results. Understanding this process helps you write faster queries.

Query Execution Pipeline

SQL Query
  ->
1. Parsing (syntax check)
  ->
2. Validation (table/column existence, permissions)
  ->
3. Optimization (choose execution plan)
  ->
4. Execution (run the plan)
  ->
5. Result Set (return data)

Detailed Execution Steps

-- Step 1: Parser converts SQL to internal representation
SELECT name, email FROM users WHERE department_id = 5 ORDER BY name;

-- Step 2: Validator checks:
-- - 'users' table exists
-- - 'name', 'email', 'department_id' columns exist
-- - User has SELECT permission
-- - Data types are compatible

-- Step 3: Optimizer considers multiple plans:
-- Plan A: Full table scan + sort
-- Plan B: Use index on department_id + index for sort
-- Plan C: Use covering index (no table lookup)
-- Chooses the cheapest plan based on statistics

-- Step 4: Executor runs the chosen plan

The Optimizer's Role

The query optimizer is the brain of the database. It uses:

• Statistics: Row counts, value distributions, histograms
• Cost model: CPU, I/O, memory estimates
• Index information: Available indexes and their selectivity
• Join strategies: Nested loop, hash join, merge join

-- The optimizer might transform your query:
-- Original:
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id
WHERE c.country = 'USA' AND o.total > 100;

-- Optimizer might rewrite as:
-- 1. Filter customers by country using index
-- 2. For each matching customer, find orders using index on customer_id
-- 3. Filter orders by total > 100

Statistics and Cost-Based Optimization

-- PostgreSQL: View table statistics
SELECT relname, reltuples, relpages 
FROM pg_class WHERE relname = 'users';

-- MySQL: View index statistics
SHOW INDEX FROM users;

-- Update statistics (if data has changed significantly)
ANALYZE TABLE users;  -- MySQL
ANALYZE users;        -- PostgreSQL

The optimizer uses statistics to estimate the cost of each possible plan and chooses the one with the lowest estimated cost.

Using EXPLAIN to Understand Query Plans

EXPLAIN shows the execution plan a database will use for a query without actually running it. EXPLAIN ANALYZE runs the query and shows actual execution statistics.

MySQL EXPLAIN

EXPLAIN SELECT u.name, o.total 
FROM users u 
JOIN orders o ON u.id = o.customer_id 
WHERE u.country = 'USA';

+----+-------------+-------+--------+-------------------+---------+---------+------------------+------+-------------+
| id | select_type | table | type   | possible_keys     | key     | key_len | ref              | rows | Extra       |
+----+-------------+-------+--------+-------------------+---------+---------+------------------+------+-------------+
|  1 | SIMPLE      | u     | ref    | idx_country       | idx_country | 51    | const            |  500 | Using where |
|  1 | SIMPLE      | o     | ref    | idx_customer_id   | idx_customer_id | 5  | u.id             |    3 | NULL        |
+----+-------------+-------+--------+-------------------+---------+---------+------------------+------+-------------+

Key EXPLAIN Fields

Field	Meaning
type	Access type (system > const > eq_ref > ref > range > index > ALL)
possible_keys	Indexes that could be used
key	Index actually chosen
rows	Estimated rows to examine
Extra	Additional information (Using index, Using where, Using filesort)

PostgreSQL EXPLAIN ANALYZE

EXPLAIN ANALYZE 
SELECT u.name, COUNT(o.id) as order_count
FROM users u 
LEFT JOIN orders o ON u.id = o.customer_id
WHERE u.country = 'USA'
GROUP BY u.id, u.name
ORDER BY order_count DESC
LIMIT 10;

-- Output shows:
-- Sort (cost=1234.56..1234.81 rows=10) (actual time=45.123..45.145 rows=10 loops=1)
--   Sort Key: (count(o.id)) DESC
--   Sort Method: quicksort  Memory: 25kB
-- -> HashAggregate (cost=1230.00..1234.00 rows=500) (actual time=44.567..44.890 rows=500 loops=1)
--       Group Key: u.id, u.name
--       Batches: 1  Memory Usage: 81kB
-- -> Hash Right Join (cost=100.00..1200.00 rows=5000) (actual time=2.345..42.123 rows=5000 loops=1)

Reading EXPLAIN Output

-- Good plan indicators:
-- Index Scan (not Seq Scan on large tables)
-- Low rows estimate
-- No filesort
-- Using index (covering index)

-- Bad plan indicators:
-- Seq Scan on large table
-- High rows estimate
-- Using filesort (expensive sort)
-- Using temporary (temp table created)

Common EXPLAIN Patterns

Pattern	Meaning	Action
Seq Scan	Full table scan	Consider adding index
Index Scan	Using index efficiently	Good
Using filesort	Sort not covered by index	Add covering index
Using temporary	Temporary table created	Optimize GROUP BY
Using where	Filtering after index lookup	Add to index

How to Read Query Plans

Query plans are read from the inside out. The innermost operations execute first, and their results flow to outer operations.

Plan Tree Structure

Nested Loop (outer)
  +-- Index Scan on orders (inner)
  +-- Seq Scan on customers (inner)

Execution order:
1. Index Scan on orders -> produces rows
2. Seq Scan on customers -> produces rows
3. Nested Loop combines results

Example: Reading a JOIN Plan

EXPLAIN SELECT o.id, o.total, u.name
FROM orders o
JOIN users u ON o.customer_id = u.id
WHERE o.total > 100;

+----+-------------+-------+--------+
| id | select_type | table | type   |
+----+-------------+-------+--------+
|  1 | SIMPLE      | o     | range  |  -- Orders: scan orders where total > 100
|  1 | SIMPLE      | u     | eq_ref |  -- For each order, find user by primary key
+----+-------------+-------+--------+

Reading:
1. Range scan on orders (total > 100) -> ~1000 rows
2. For each order, eq_ref lookup on users (primary key) -> 1 row each
3. Total: ~1000 index lookups + 1000 PK lookups

Access Types (Best to Worst)

Type	Description	Speed
system	One row, one block	Fastest
const	Single row by primary key/unique	Very fast
eq_ref	Join on primary key/unique	Very fast
ref	Join on non-unique index	Fast
range	Index range scan	Fast
index	Full index scan	Medium
ALL	Full table scan	Slowest

Join Algorithms

-- Nested Loop: Good for small datasets
-- For each row in outer table, scan inner table
-- O(n * m) worst case

-- Hash Join: Good for large, unsorted datasets
-- Build hash table from smaller table
-- Probe with larger table
-- O(n + m) average

-- Merge Join: Good for sorted datasets
-- Both inputs sorted on join key
-- O(n + m) always

Cost Estimation

Cost = (CPU cost x rows) + (I/O cost x pages)

Example:
- Seq scan: 1000 pages x 1.0 cost = 1000
- Index scan: 3 levels x 1.0 + 100 rows x 0.1 = 13.0
- Index is 77x cheaper in this example

Reading PostgreSQL Plans

-- Actual vs Estimated rows
-- If actual >> estimated, statistics are stale
-- Run ANALYZE to update statistics

-- Loops: How many times the plan node executed
-- A node with loops=100 ran 100 times (nested loop inner)

-- Buffers: Cache hit/miss information
-- shared hit: read from buffer cache (good)
-- shared read: read from disk (bad)

Performance Red Flags in Plans

Red Flag	Problem	Solution
Seq Scan on large table	Missing index	Add index
Using filesort	Sort not covered by index	Add covering index
Using temporary	Temp table for GROUP BY	Optimize query
High row estimate	Poor selectivity	Better index
Nested loop on large sets	Wrong join strategy	Increase work_mem

How Indexes Are Used in Queries

Understanding when and how the database uses indexes helps you design better schemas and write faster queries.

Index Seek vs Index Scan

-- Index Seek: Directly jumps to matching rows (fast)
SELECT * FROM users WHERE email = 'alice@example.com';
-- Uses B-tree to navigate directly to 'alice@example.com'
-- O(log n) complexity

-- Index Scan: Reads all index entries (slower)
SELECT * FROM users WHERE LOWER(email) LIKE 'a%';
-- Function on column prevents index seek
-- Must scan all index entries
-- O(n) complexity

Index Usage Patterns

-- 1. Equality: Always uses index efficiently
SELECT * FROM users WHERE id = 123;  -- Primary key index

-- 2. Range: Uses index for range scan
SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';

-- 3. Prefix: Uses index with LIKE
SELECT * FROM users WHERE name LIKE 'John%';  -- Uses index
SELECT * FROM users WHERE name LIKE '%John%';  -- Cannot use index

-- 4. ORDER BY: Uses index to avoid sorting
SELECT * FROM orders ORDER BY created_at;  -- Uses index on created_at

-- 5. Covering index: Avoids table lookup
SELECT customer_id, total FROM orders WHERE customer_id = 101;
-- If index (customer_id, total) exists, no table scan needed

Why Indexes Are Not Used

-- 1. Function on indexed column
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';
-- Index on email is NOT used
-- Solution: Create functional index
CREATE INDEX idx_users_email_lower ON users(LOWER(email));

-- 2. Implicit type conversion
SELECT * FROM users WHERE phone = 5551234567;
-- phone is VARCHAR, but comparing to INT
-- Index not used due to implicit conversion
-- Solution: Use correct type
SELECT * FROM users WHERE phone = '5551234567';

-- 3. OR conditions (partial)
SELECT * FROM users WHERE id = 1 OR name = 'Alice';
-- Index on id is used, but name may cause full scan
-- Solution: Use UNION ALL
SELECT * FROM users WHERE id = 1
UNION ALL
SELECT * FROM users WHERE name = 'Alice' AND id != 1;

-- 4. NOT IN / NOT EXISTS on large sets
SELECT * FROM users WHERE id NOT IN (SELECT user_id FROM banned_users);
-- May cause full scan
-- Solution: Use LEFT JOIN
SELECT u.* FROM users u 
LEFT JOIN banned_users b ON u.id = b.user_id 
WHERE b.user_id IS NULL;

Index Monitoring

-- PostgreSQL: Find unused indexes
SELECT indexrelname, idx_scan, pg_size_pretty(pg_relation_size(i.indexrelid))
FROM pg_stat_user_indexes i
JOIN pg_index USING (indexrelid)
WHERE idx_scan = 0 AND NOT indisunique;

-- MySQL: Find unused indexes
SELECT * FROM sys.schema_unused_indexes;

-- Find missing indexes (PostgreSQL)
SELECT relname, seq_scan, idx_scan
FROM pg_stat_user_tables
WHERE seq_scan > 100 AND idx_scan = 0;

SQL Performance Best Practices

Follow these guidelines to write efficient SQL queries and design performant database schemas.

1. Avoid SELECT *

-- Bad: Fetches all columns including unnecessary ones
SELECT * FROM users WHERE country = 'USA';

-- Good: Only select what you need
SELECT id, name, email FROM users WHERE country = 'USA';

-- Why SELECT * is bad:
-- 1. Transfers more data over network
-- 2. Prevents covering index usage
-- 3. May return data you don't need
-- 4. Schema changes break your query

2. Use Index-Friendly WHERE Clauses

-- Bad: Function on indexed column
SELECT * FROM orders WHERE YEAR(order_date) = 2024;
-- Index on order_date is NOT used

-- Good: Range query on indexed column
SELECT * FROM orders 
WHERE order_date >= '2024-01-01' AND order_date < '2025-01-01';
-- Index on order_date IS used

-- Bad: Implicit type conversion
SELECT * FROM users WHERE phone = 5551234;
-- phone is VARCHAR, comparing to INT

-- Good: Correct type
SELECT * FROM users WHERE phone = '5551234';

3. Limit Result Sets

-- Bad: Fetches all rows, then processes in application
SELECT * FROM orders WHERE customer_id = 101;

-- Good: Limit at database level
SELECT * FROM orders WHERE customer_id = 101 LIMIT 100;

-- Good: Use pagination
SELECT * FROM orders 
WHERE customer_id = 101 
ORDER BY order_date DESC 
LIMIT 20 OFFSET 0;

4. Use JOINs Instead of Subqueries

-- Subquery (may be slower)
SELECT * FROM users 
WHERE id IN (SELECT user_id FROM orders WHERE total > 100);

-- JOIN (usually faster)
SELECT DISTINCT u.* FROM users u 
JOIN orders o ON u.id = o.user_id 
WHERE o.total > 100;

-- Or EXISTS (good for large datasets)
SELECT * FROM users u 
WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id AND o.total > 100);

5. Batch Operations

-- Bad: Individual inserts in loop
INSERT INTO logs (msg) VALUES ('msg1');
INSERT INTO logs (msg) VALUES ('msg2');
-- ... 1000 more

-- Good: Batch insert
INSERT INTO logs (msg) VALUES 
('msg1'), ('msg2'), ('msg3');
-- 1 transaction vs 1000 transactions

-- Bad: Individual updates
UPDATE users SET last_login = NOW() WHERE id = 1;
UPDATE users SET last_login = NOW() WHERE id = 2;

-- Good: Batch update
UPDATE users SET last_login = NOW() WHERE id IN (1, 2, 3);

6. Use EXPLAIN to Validate

-- Always check your query plan for:
-- 1. Seq Scan on large tables (add index)
-- 2. Using filesort (add covering index)
-- 3. Using temporary (optimize GROUP BY)
-- 4. High row estimates (improve selectivity)

EXPLAIN ANALYZE 
SELECT * FROM orders WHERE customer_id = 101;

Quick Reference Table

Practice	Impact	Difficulty
Avoid SELECT *	High	Easy
Index WHERE columns	High	Easy
Use covering indexes	Medium	Medium
Limit result sets	High	Easy
JOINs over subqueries	Medium	Medium
Batch operations	High	Easy
EXPLAIN validation	High	Easy