Indexing & Query Optimization

Difficulty: Advanced

Question

How do database indexes work? When should you add or avoid indexes?

Answer

An index is a data structure (usually B-tree) that speeds up data retrieval at the cost of slower writes and extra storage.

How it works: Instead of scanning every row (full table scan), the database looks up the value in the index (like a book's index) and jumps directly to the matching rows.

When to index: - Columns in WHERE clauses - Columns in JOIN conditions - Columns in ORDER BY - High-cardinality columns (many unique values)

When NOT to index: - Small tables (full scan is fast enough) - Low-cardinality columns (boolean, gender) - Tables with heavy write operations - Columns rarely used in queries

Code examples

Index Basics

-- Without index: full table scan O(n)
SELECT * FROM users WHERE email = 'alice@example.com';
-- Scans all 1M rows

-- Create index
CREATE INDEX idx_users_email ON users(email);

-- With index: B-tree lookup O(log n)
SELECT * FROM users WHERE email = 'alice@example.com';
-- Finds it in ~20 comparisons (log2 of 1M)

-- Composite index (multi-column)
CREATE INDEX idx_orders_user_date 
  ON orders(user_id, created_at DESC);

-- This index helps with:
SELECT * FROM orders WHERE user_id = 5;           -- YES
SELECT * FROM orders WHERE user_id = 5 
  ORDER BY created_at DESC;                         -- YES
SELECT * FROM orders WHERE created_at > '2024-01'; -- NO (leftmost prefix rule)

-- Unique index (also enforces uniqueness)
CREATE UNIQUE INDEX idx_users_email_unique ON users(email);

Composite indexes follow the leftmost prefix rule: the index on (user_id, created_at) can be used for queries on user_id alone, but NOT for created_at alone.

Reading EXPLAIN Output

-- Check how a query will execute
EXPLAIN ANALYZE
SELECT u.name, COUNT(o.id) as order_count
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
WHERE u.created_at > '2024-01-01'
GROUP BY u.id, u.name
HAVING COUNT(o.id) > 5
ORDER BY order_count DESC;

-- Key things to look for in EXPLAIN:
-- 1. Seq Scan → full table scan (usually bad for large tables)
-- 2. Index Scan → using an index (good)
-- 3. Nested Loop → OK for small tables, bad for large
-- 4. Hash Join → good for large table joins
-- 5. Sort → check if an index could avoid this
-- 6. Rows estimate → is it accurate?

-- Fix: add indexes for the WHERE and JOIN columns
CREATE INDEX idx_users_created ON users(created_at);
CREATE INDEX idx_orders_user ON orders(user_id);

EXPLAIN ANALYZE shows the actual execution plan and timing. Use it to identify full table scans, missing indexes, and expensive operations.

Common Optimization Patterns

-- 1. AVOID: functions on indexed columns
-- BAD: index on created_at can't be used
SELECT * FROM orders WHERE YEAR(created_at) = 2024;
-- GOOD: range query uses the index
SELECT * FROM orders 
WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';

-- 2. AVOID: wildcard at start of LIKE
-- BAD: can't use index
SELECT * FROM users WHERE name LIKE '%smith';
-- GOOD: can use index
SELECT * FROM users WHERE name LIKE 'smith%';

-- 3. SELECT only needed columns (covering index)
CREATE INDEX idx_cover ON orders(user_id, status, total);
-- This query is answered entirely from the index:
SELECT status, total FROM orders WHERE user_id = 5;
-- No table lookup needed = "index-only scan"

-- 4. Pagination: avoid OFFSET for large pages
-- BAD: OFFSET 100000 scans and discards 100K rows
SELECT * FROM products ORDER BY id LIMIT 20 OFFSET 100000;
-- GOOD: cursor-based pagination
SELECT * FROM products WHERE id > 100000 ORDER BY id LIMIT 20;

These patterns can make orders-of-magnitude difference in query performance. The cursor-based pagination alone can turn a 5-second query into 5ms.

Key points

Concepts covered

B-Tree Index, Composite Index, EXPLAIN, Query Plan, Covering Index