Indexing Deep Dive

How database indexes work and when they help: B-tree internals, scan types, composite column order, covering, partial and expression indexes, the other index types, and what each index costs on writes.

Overview

An index is a second copy of some columns, kept sorted or otherwise organized so the database can find matching rows without reading the whole table. Each entry holds the indexed value and a pointer to the row. The right index turns a scan of millions of rows into a few page reads.

An index is not free. Every insert, every delete and many updates must change every index on the table, and each index takes disk space and room in the cache. So indexing is a trade: faster reads for the queries you run, slower writes for everything.

This chapter uses PostgreSQL for its examples, with notes on MySQL's InnoDB where it differs. The SQL runs on PostgreSQL 17, and the plans shown are the ones it produced.

What you will be able to do

  • Explain what a B-tree index stores and how an index scan, a bitmap scan and an index-only scan differ.
  • Choose the column order of a composite index for a given set of queries, and say which queries it cannot serve.
  • Use covering, partial and expression indexes where they fit.
  • Pick GIN, GiST, BRIN or hash over a B-tree when the data calls for it.
  • Explain why the planner sometimes ignores an index, and how to find indexes that cost more than they give.

Key concepts

  • B-tree index
  • Index scan types
  • Composite index column order
  • Covering index and index-only scan
  • Partial index
  • Expression index
  • Hash, GIN, GiST and BRIN
  • Selectivity
  • Index maintenance

Interview questions

  • You have an index on (customer_id, status, created_at). Which of these queries can use it well?
  • What is a covering index, and when does an index-only scan still read the table?
  • Why might the planner ignore an index you just created?
  • When would you use a partial index, and what are its limits?
  • GIN, GiST, BRIN or hash: which would you choose for tags, time ranges, a huge append-only log, and long URLs?
  • How do you add an index to a large production table safely, and how do you find indexes to remove?

Sign up free to read the full topic

More Databases & SQL topics

Start free on Cariara · Coding problems · System design studio