What is Database Index?

What happens without one

Without an index, the only way to find the row matching WHERE email = '[email protected]' is to read the whole table from start to finish, a sequential scan. On a thousand rows nobody notices. On an orders table with twenty million rows it costs seconds per page view, and a handful of concurrent requests can make the database look frozen. An index works like the index at the back of a book: look the value up in a sorted list and go straight to where the row lives.

The B-tree intuition

The default index type in relational databases is the B-tree, a tree that is kept balanced at all times, where every node is a disk page holding hundreds of keys. Because each node fans out so widely, even a table with hundreds of millions of rows can be searched by reading only a few pages. The leaf pages are sorted and linked to each other, so a B-tree serves not only equality lookups but also ranges (<, >, BETWEEN), ORDER BY and prefix patterns such as LIKE 'abc%'. It cannot help with a leading wildcard like LIKE '%abc'. PostgreSQL also offers other index types, including GIN for JSONB and full-text search and GiST for spatial data.

Column order in composite indexes

An index over several columns is sorted by the first column, then by the second within equal values of the first. Think of a phone book ordered by surname, then first name: finding a surname is fast, finding everyone called “Anna” is not.

CREATE INDEX idx_orders_customer_created
  ON orders (customer_id, created_at DESC);

This index fully serves “latest orders for one customer”, covering both the filter and the sort, and it also helps queries that filter on customer_id alone. It does nothing for a search on created_at by itself. Wrapping the column in a function defeats the index too: WHERE lower(email) = ... needs an expression index, or the data should be stored already normalised.

Checking the plan with EXPLAIN

Rather than guessing whether an index is used, look at the query plan. In PostgreSQL, EXPLAIN shows the planned strategy and EXPLAIN ANALYZE actually runs the query and reports measured timings; MySQL offers EXPLAIN as well. A shortened example:

EXPLAIN ANALYZE
SELECT id, total FROM orders
WHERE customer_id = 4821
ORDER BY created_at DESC LIMIT 20;

-- Without the index
Limit
  -> Sort
       -> Seq Scan on orders
            Filter: (customer_id = 4821)
            Rows Removed by Filter: 1999870

-- With the index
Limit
  -> Index Scan using idx_orders_customer_created on orders
       Index Cond: (customer_id = 4821)

A Seq Scan paired with a large “Rows Removed by Filter” count is the classic sign of a missing index. The planner skipping an index is not always a mistake, though: if a query returns a large share of the table, reading all of it really can be cheaper. Because EXPLAIN ANALYZE executes the statement, wrap it in a transaction and roll back when analysing an UPDATE or DELETE.

Every index sends a bill

• Write cost: each INSERT, UPDATE and DELETE must update every affected index. On a write-heavy table, each unnecessary index is a direct slowdown.
• Space and memory: indexes occupy disk and perform best when they fit in memory.
• Low selectivity: an index on a boolean column with two possible values rarely pays off.
• Locks while building: a plain CREATE INDEX in PostgreSQL blocks writes to the table until it finishes. On large tables use CREATE INDEX CONCURRENTLY, which cannot run inside a transaction block, and plan database migrations that add indexes accordingly.

Primary keys and UNIQUE constraints create their own indexes automatically. Columns holding a foreign key are not indexed automatically in PostgreSQL and usually need one for fast joins and deletes. The most reliable way to decide on indexes is to collect the real SQL statements from the slow query log and read the plan of each one.