# Database Indexing, What, When and How A query is slow: ```sql SELECT * FROM orders WHERE customer_id = 123; ``` The usual fix is to add an index on `customer_id`, and it works. But the moment your query grows a second condition - ```sql SELECT * FROM orders WHERE customer_id = 123 AND total < 10; ``` - the "just add an index" advice runs out, and most people guess. This post is about not guessing: how an index actually works, how to build the *right* one for queries like that, what and when to index, the real costs of indexing, when indexing simply cannot fix a scale problem, and why the indexing story in NoSQL comes with serious catches. It builds on the [database fundamentals](/concepts-you-should-know-about-system-designing-part-1). ## Why the query is slow, and what an index does Without an index, `WHERE customer_id = 123` forces a **sequential scan**: the database reads every row in the table and checks each one. On a million-row table that is a million reads to find maybe five rows. You can see it: ```text EXPLAIN SELECT * FROM orders WHERE customer_id = 123; Seq Scan on orders (cost=0.00..18334.00 rows=5 width=...) Filter: (customer_id = 123) ``` An **index** is a separate, sorted copy of the indexed column(s) with a pointer back to each row - almost always a **B-tree**: a balanced tree kept in sorted order, so the database walks from the root to the right leaf in O(log n) instead of scanning O(n). Because the leaves are sorted and linked, a B-tree is fast at four things: equality lookups (`= 123`), range scans (`BETWEEN`, `<`, `>`), sorted retrieval (`ORDER BY`), and min/max. Create it and the same query becomes an index scan: ```sql CREATE INDEX idx_orders_customer ON orders (customer_id); ``` ```text Index Scan using idx_orders_customer on orders (rows=5 ...) Index Cond: (customer_id = 123) ``` A million-row scan became a handful of tree hops. That is the whole promise of an index - and also the whole reason its column *order* matters once you have more than one condition. ## The real question: `customer_id = 123 AND total < 10` You have two honest options. **Option 1 - index `customer_id` only, filter the rest.** If `customer_id = 123` already narrows the table to five rows, the database uses `idx_orders_customer` to find those five and then checks `total < 10` on each. Perfectly fine when the first column is *selective* (few matching rows). Nothing more is needed. **Option 2 - a composite index on `(customer_id, total)`.** When `customer_id` matches many rows and `total < 10` cuts it down a lot, you want both conditions satisfied by the index itself. A composite index is a copy sorted by the first column, then by the second within each first-column group. So `(customer_id, total)` is sorted by `customer_id`, and within each customer, by `total`: ```sql CREATE INDEX idx_orders_cust_total ON orders (customer_id, total); ``` Now `WHERE customer_id = 123 AND total < 10` is a single, tight operation: seek straight to the `customer_id = 123` block, and because that block is itself sorted by `total`, `total < 10` is a **contiguous range** at the start of it. One seek, one short range scan. ### Column order is the whole game: equality first, range last Here is the rule that answers the question and a hundred like it: > Put the columns with **equality** conditions first, then **one** column with a **range** condition last. Why? Reverse the index to `(total, customer_id)` and watch it fall apart. Now the copy is sorted by `total` first. `total < 10` is a range, so it is scattered across the whole low end of the index - and `customer_id = 123` rows sit *anywhere* within that range, not together. The database can use the index to satisfy `total < 10`, but then has to check `customer_id` on every one of those rows. You got one condition from the index instead of two. The general form, for an index on `(a, b, c)`: - Fully served: `a = 1 AND b = 2 AND c = 3`, and `a = 1 AND b = 2 AND c > 10`, and `a = 1 AND b > 5`, and `a = 1`. - **Not** served well: `b = 2` alone, or `c = 3` alone - because of the **leftmost-prefix rule**: the index is only usable from the left, up to and including the first range, with no gaps. A column with no condition is a gap that ends the usable prefix. Two consequences worth burning in: - **Only one range column earns its place.** After the first `<`, `>`, or `BETWEEN`, later columns can only *filter*, not *seek* - so `a = 1 AND b > 5 AND c > 3` uses the index for `a` and `b`, and `c` is just a filter. - **The index also gives you the sort for free.** `WHERE customer_id = 123 ORDER BY total` needs no separate sort step, because `idx_orders_cust_total` already stores that customer's rows in `total` order. For the deep, worked treatment of exactly this, [Use The Index, Luke](https://use-the-index-luke.com/) and the [MySQL index cookbook](https://mysql.rjweb.org/doc.php/index_cookbook_mysql) are the canonical references, and the [PostgreSQL indexes docs](https://www.postgresql.org/docs/current/indexes.html) cover the specifics for Postgres. ### Covering indexes: never touch the table If an index contains *every* column a query needs, the database answers straight from the index and never reads the table at all - an **index-only scan**. Add the returned columns to the index (or, in Postgres, `INCLUDE` them): ```sql CREATE INDEX idx_cover ON orders (customer_id, total) INCLUDE (status); -- SELECT status FROM orders WHERE customer_id = 123 AND total < 10; -> index-only ``` This is the single biggest win for a hot read query, because it removes the trip back to the table entirely. ## What to index Index the columns your queries actually filter, join, and sort on: - Columns in `WHERE`, `JOIN ... ON`, `ORDER BY`, and `GROUP BY`. - **Foreign keys** - joins hammer them. - **High-selectivity** columns - ones with many distinct values, so a lookup narrows to few rows. And do **not** bother indexing **low-selectivity** columns. If `WHERE status = 'active'` matches more than roughly 20% of the table, the optimizer will ignore the index and scan anyway - bouncing between index and table for a fifth of the rows is slower than reading the table straight through. An index on a boolean or a two-value flag is usually dead weight. ## When to index - and when not to **Index when:** you have confirmed a slow query with `EXPLAIN`, the table is large, the workload is read-heavy, and the predicate is selective. Index for *real* queries you run, not hypothetical ones. **Do not index when:** the table is tiny (a scan is already instant), the column is low-selectivity, the query runs rarely, or - critically - the table is **write-heavy on a hot path**, because every index you add taxes every write. Which brings us to the costs. ## The disadvantages of indexing Indexes are not free, and over-indexing is a real, common mistake: - **Write amplification.** Every `INSERT`, `UPDATE`, and `DELETE` must update *every* index on the table, in sorted position. Five indexes means a write does its own work plus five index maintenances. On a write-heavy table this is the dominant cost, and it is why you do not "just index everything." - **Storage.** An index is a copy of its columns; a few well-chosen indexes can rival the size of the table itself. - **Memory pressure.** Indexes compete with table data for the buffer cache; bloated or unused indexes evict pages you actually needed. - **Maintenance and drift.** Indexes fragment and bloat over time (needing `VACUUM`/`REINDEX`), and the more indexes you have, the more ways the query planner can pick the *wrong* one and make a query slower, not faster. - **Updating an indexed column is extra costly** - the row has to move to its new sorted position in the index, not just change in place. The discipline: add an index to fix a measured slow query, then check that it did not wreck your write throughput. Indexes you cannot tie to a real query should be dropped. ## When indexing cannot save you - the scale ceiling This is the part people miss. **An index makes one machine's queries faster; it does not add capacity.** So indexing hits a wall in exactly the cases where you most want a magic fix: - **Write-heavy workloads.** Indexes *slow writes down*. You cannot index your way to higher write throughput - past a point that is a job for partitioning and sharding, not indexes (the [scaling a database](/concepts-you-should-know-about-system-designing-part-1) ladder - cache, replicas, shards - takes over here). - **Data or traffic beyond one node.** If the working set or write volume exceeds what a single machine can hold or handle, no index changes that. You need read replicas for read capacity and sharding for write/storage capacity. - **Queries that inherently touch huge row counts.** Analytics that scan and aggregate millions of rows (`SUM`, `GROUP BY` over a year of data) get little from a B-tree, because there is no small set of rows to seek to. The answers there are precomputation: **denormalization, materialized views**, or a purpose-built store - a **columnar/OLAP** engine like [ClickHouse](https://clickhouse.com/) for analytics. - **Access patterns a B-tree cannot express.** A B-tree cannot do `LIKE '%foo%'` (leading wildcard), relevance-ranked full-text search, or fuzzy matching. Those need an **inverted index** and usually a dedicated engine like [Elasticsearch](https://www.elastic.co/elasticsearch); geospatial needs GiST/R-tree indexes. The right *kind* of index, or the right *system*, not a bigger B-tree. Indexing is the first and cheapest database-scaling lever - and it is a single-node, query-speed tool. When you have indexed correctly and it is still slow *at scale*, the fix is upstream: caching, replication, sharding, or a different data store. On the write side specifically, separating reads from writes with [CQRS](/command-query-responsibility-segregation-cqrs) lets a read-optimized, heavily-indexed store exist without taxing the write path. ## NoSQL: the indexing catches are serious NoSQL stores are often sold as "scales effortlessly," but the fine print is about indexing, and it is steep. The whole model is that you get one blazing-fast access path - the **partition/primary key** - and everything else is a problem. - **Off-key queries are second-class.** In a key-value or wide-column store, a query that is not on the partition key either is not allowed or degenerates into a scan. You do not get ad-hoc `WHERE anything = ?` the way SQL gives you. - **Secondary indexes are limited and costly.** In [DynamoDB](https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/SecondaryIndexes.html), a Global Secondary Index is a *separate copy of your data* under a different key, updated **asynchronously** - so it is **eventually consistent** (reads can be stale), it consumes **its own extra write capacity** on every write to the base table, and there is a hard limit on how many you can have. Local Secondary Indexes can be strongly consistent but must be defined at table creation and can never be added later. In [Cassandra](https://cassandra.apache.org/), a native secondary index queries *every node* in the cluster (a scatter), and performs badly on both high- and low-cardinality columns - which is why the community advice is to avoid it and instead **denormalize into a second table** keyed for that query. - **You model for queries, not for data.** Because you cannot cheaply "just add an index and query however," NoSQL forces **query-first design**: you enumerate your access patterns up front and build a table (or index) per pattern. A new query pattern discovered later often means a **new table plus a backfill** of all existing data - the flexibility SQL gives you for free is gone. - **No ad-hoc joins**, and index updates are eventually consistent, so a write is not immediately visible through its secondary index. None of this makes NoSQL wrong - it buys genuine horizontal write scale and predictable latency. But the price is exactly the thing indexing gives you in a relational database: **flexible, consistent, add-it-later querying.** Choose NoSQL when your access patterns are few, known, and key-shaped; reach for a relational database and its indexes when you need to slice the data many ways. ## The short version Start from a slow query and `EXPLAIN` it. Index the columns it filters, join, and sort on; for multi-condition queries, order composite indexes **equality-first, one range last**, and use covering indexes for hot reads. Index for real queries, not everything, because every index taxes writes. And know the ceiling: indexing speeds up one node's reads - it does not add capacity, cannot rescue write-heavy or huge-scan workloads, and in NoSQL it is a deliberately limited, eventually-consistent, design-it-upfront affair. Past that ceiling, the tools are caching, replicas, sharding, and the right store for the job.