Indexes & query performance

Without an index, finding WHERE email = 'a@x.com' means reading every row: a sequential (full table) scan. An index keeps a copy of one or more columns in sorted order with a pointer to each row, so the database can binary-search-like descend a tree to the match in a few page reads.

The default index type in PostgreSQL and in MySQL's InnoDB engine is the B-tree (strictly a B+ tree): a shallow, wide tree where each node is a disk page holding hundreds of keys, so even 100 million rows need only about 3 to 4 levels. B-trees support equality, ranges (<, >, BETWEEN), prefix LIKE 'abc%' (in PostgreSQL this needs the C collation or a text_pattern_ops index) and ORDER BY on the indexed columns.

A composite index on (a, b) is sorted by a, then by b within each a, like a phone book sorted by last name then first name. A covering index contains every column a query needs, so the table itself is never read (an index-only scan). In InnoDB the table is stored inside the primary key B-tree (a clustered index), and secondary indexes store the primary key; in PostgreSQL tables are heaps and every index points to a row location.

1. 1The planner estimates the cost of each possible plan from table statistics (row counts, value distribution) and picks the cheapest: a sequential scan, an index scan, a bitmap index scan (PostgreSQL, for many matches) or an index-only scan.
2. 2An index lookup starts at the root page and follows pointers down to a leaf page. With a fan-out of a few hundred keys per page, each level multiplies the reachable rows by a few hundred, so depth grows as O(log n).
3. 3Leaf pages are linked in key order, so a range condition finds the first match and then walks forward along the leaves until the range ends.
4. 4For each match, a plain index scan then fetches the row from the table (a random read). If a large fraction of the table matches, a sequential scan is cheaper, so the planner may ignore the index. That is selectivity at work.
5. 5A composite index (a, b, c) can be used for conditions on a; a and b; or a, b and c (the leftmost prefix). Put equality-filtered columns first and the range or sort column last: for WHERE a = 1 AND b > 10, (a, b) is ideal, while (b, a) is weaker.
6. 6Every INSERT, UPDATE of an indexed column and DELETE must also update each index, so more indexes mean slower writes and more disk and memory use.

-- orders(id, customer_id, created_at, total)

-- Composite index: equality column first, range/sort column second
CREATE INDEX idx_orders_cust_created
  ON orders (customer_id, created_at);

-- PostgreSQL: build without blocking writes, and make it covering
-- CREATE INDEX CONCURRENTLY idx_orders_cust_created_cov
--   ON orders (customer_id, created_at) INCLUDE (total);

-- Check the plan (actually runs the query)
EXPLAIN ANALYZE
SELECT id, total
FROM orders
WHERE customer_id = 42
  AND created_at >= DATE '2026-01-01'
ORDER BY created_at;

-- Index-friendly rewrite of a function on a column
-- Slow:  WHERE EXTRACT(YEAR FROM created_at) = 2026
SELECT COUNT(*) FROM orders
WHERE created_at >= DATE '2026-01-01'
  AND created_at <  DATE '2027-01-01';

The index lets the example query seek directly to customer 42's 2026 orders and return them already sorted. EXPLAIN ANALYZE should show an Index Scan (or Bitmap Index Scan) instead of a Seq Scan. The last query shows the range rewrite that lets an index on created_at be used.

Cost: B-tree lookup O(log n) page reads (3 to 4 levels for hundreds of millions of rows); range scan O(log n + k) for k matches; full scan O(n). Each index adds O(log n) work to every insert and delete and to updates of its columns.