Indexes & Query Optimization

The Problem: Full Table Scans

Without an index, a database has no choice but to read every row in a table to find the ones that match your query. This is a full table scan. On a table with a million rows, every query that lacks an index reads a million rows, even if the result is a single record.

-- Table: users (1,000,000 rows)
-- Query: find a user by email

SELECT * FROM users WHERE email = 'alice@example.com';

-- What happens internally:
-- Row 1:  email = 'bob@...'      -> skip
-- Row 2:  email = 'carol@...'    -> skip
-- ...
-- Row 847,291: email = 'alice@...' -> match!
-- Row 847,292 ... 1,000,000       -> still have to check

-- Total rows read: 1,000,000
-- Time: ~200ms on a warm SSD

An index is a separate data structure maintained alongside your table. It stores a sorted copy of the indexed column(s) along with pointers to the actual rows. Instead of scanning the table, the database searches the index, finds the pointer, and jumps directly to the matching row. The same query drops from O(n) to O(log n).

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

-- Same query, now uses the index
SELECT * FROM users WHERE email = 'alice@example.com';

-- What happens internally:
-- B-tree root: 'alice' < 'mike', go left
-- Next node:   'alice' > 'adam', go right
-- Next node:   'alice' found -> row pointer: #847291
-- Heap fetch:  read row #847291 directly

-- Total rows read: 1
-- Comparisons: ~20 (log2 of 1M)
-- Time: <1ms

The cost of indexes

Indexes are not free. Every index you add must be maintained by the database on every INSERT, UPDATE, and DELETE. For read-heavy workloads, this is a good trade. For write-heavy workloads, excessive indexing becomes the bottleneck.

How B-tree Indexes Work

The default index type in PostgreSQL, MySQL, and most other relational databases is a B-tree (balanced tree). The B-tree is a self-balancing sorted tree that keeps all leaf nodes at the same depth. This guarantees that any lookup takes exactly O(log n) comparisons, regardless of which key you are searching for.

The visualizer below uses a 16-row table. Select a search target, then click "Run comparison" to see a full table scan and a B-tree lookup side by side. Notice that the scan checks rows one by one while the index descends the tree in exactly 4 comparisons, regardless of which value you search for.

B-tree properties

Index Design: Types and Trade-offs

Not all indexes are equal. The type of index and how you design it determines whether the database can use it for a given query. Understanding these types lets you build indexes that are both fast and efficient.

CREATE INDEX idx_users_email ON users(email);

-- Queries that use this index:
WHERE email = 'alice@example.com'    -- equality
WHERE email > 'l@...'               -- range
ORDER BY email                       -- sort

-- Index on (last_name, first_name, age)
CREATE INDEX idx_name ON users(last_name, first_name, age);

-- Uses the index:
WHERE last_name = 'Smith'
WHERE last_name = 'Smith' AND first_name = 'Alice'
WHERE last_name = 'Smith' AND first_name = 'Alice' AND age > 30

-- Does NOT use the index:
WHERE first_name = 'Alice'  -- skips leftmost column
WHERE age > 30              -- skips two leftmost columns

-- Query: get name and email for users in a role
SELECT name, email FROM users WHERE role = 'admin';

-- A covering index includes all needed columns
CREATE INDEX idx_role_covering ON users(role, name, email);

-- Now the query never touches the users table:
-- Index has role (for filtering) + name + email (for SELECT)
-- Result: index-only scan, zero heap fetches

-- Only index active users (not the 90% who churned)
CREATE INDEX idx_active_users
  ON users(email)
  WHERE status = 'active';

-- Only index unprocessed orders
CREATE INDEX idx_pending_orders
  ON orders(created_at)
  WHERE processed = false;

-- The query must include the same WHERE clause
-- for the database to choose the partial index

Composite index column order

The leftmost prefix rule catches many engineers off-guard. Given an index on (A, B, C), the database can use it for queries filtering on A, on A+B, or on A+B+C. It cannot use it for queries filtering only on B or only on C.

Query Optimization and Common Pitfalls

Even with indexes in place, queries can be slow if they are written in ways the database cannot optimize. The most common culprits are the N+1 problem, functions applied to indexed columns, and access patterns that invalidate the index entirely.

Reading EXPLAIN output

Every major database has an EXPLAIN command that shows how a query will be executed. Reading EXPLAIN output is the fastest way to understand why a query is slow.

EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;

-- Without index:
Seq Scan on orders  (cost=0.00..18334.00 rows=1 width=52)
                    (actual time=128.3..128.3 rows=1 loops=1)
  Filter: (customer_id = 42)
  Rows Removed by Filter: 999999        <- scanned 1M rows!
Planning Time: 0.1 ms
Execution Time: 128.4 ms

-- After: CREATE INDEX idx_orders_customer ON orders(customer_id);

Index Scan on orders using idx_orders_customer
                    (cost=0.42..8.44 rows=1 width=52)
                    (actual time=0.04..0.04 rows=1 loops=1)
  Index Cond: (customer_id = 42)
Planning Time: 0.1 ms
Execution Time: 0.05 ms            <- 2,500x faster

Common slow query patterns

# Django ORM, looks clean, performs terribly
posts = Post.objects.all()       # 1 query
for post in posts:
    # Each iteration fires a NEW query!
    author = post.author          # N queries
    comments = post.comments.all() # N more queries

# For 100 posts: 201 queries sent to the database

# Use eager loading to fetch in bulk
posts = Post.objects.select_related('author') \
            .prefetch_related('comments') \
            .all()

# Now: exactly 3 queries total, regardless of post count:
# 1. SELECT posts
# 2. SELECT authors WHERE id IN (...)
# 3. SELECT comments WHERE post_id IN (...)

-- Index on created_at exists, but this doesn't use it:
SELECT * FROM orders
WHERE YEAR(created_at) = 2025;

-- Or in PostgreSQL:
WHERE DATE_TRUNC('year', created_at) = '2025-01-01';

-- The function wraps the column, breaking the index.
-- Database falls back to full scan.

-- Rewrite to a range query on the raw column:
SELECT * FROM orders
WHERE created_at >= '2025-01-01'
  AND created_at <  '2026-01-01';

-- Now the B-tree index on created_at is used.
-- Alternative: create an expression index
CREATE INDEX idx_year ON orders (YEAR(created_at));

-- Index on name exists, but this causes a full scan:
SELECT * FROM users WHERE name LIKE '%smith';

-- The leading wildcard prevents the B-tree from
-- knowing where to start. Every row must be checked.

-- Trailing wildcard works (prefix search):
SELECT * FROM users WHERE name LIKE 'smith%';

-- For full-text search, use the right tool:
-- PostgreSQL: tsvector + GIN index
-- MySQL: FULLTEXT index
-- Or: Elasticsearch for advanced text search

When not to add an index