Indexing
An index is a sorted structure that lets a query find rows without a read of the whole table. Without one, a filter on 1,000,000 rows reads each row for each query. With a matching index the query reads a few rows, but each write must also update the index.
See it on the board
The same traffic runs on two boards. The simulator measured both when this page was built.
| Measure | Goal | Each read scans the whole table | Index on the filtered column |
|---|---|---|---|
| p99 latency | under 50 ms | 10.1 s Fail | 25 ms Pass |
| Monthly cost | 8 USD/mo | 8 USD/mo | |
| Error rate | 100% | 0% |
Key numbers
| Number | Value |
|---|---|
| Rows in a table, default | 1,000,000 rows |
| Database read with an index (Postgres), median | 0.5 ms |
| Indexed reads per second for each vCPU | 15,000 reads/s |
| Disk operations for each write, default | 2 IOPS |
Index · 4 pages read per query · disk writes per insert: 2
How it works
To find the rows that match a filter without an index, the database must read every row. This full scan is fine for 1,000 rows and slow for 1,000,000 rows. Under load, scans fill the CPU and the disk, and every other query waits.
An index keeps the values of one or more columns in sorted order, with a pointer to each row. Most databases use a balanced tree, so a lookup needs only a few steps, also for millions of rows. A query that filters or sorts on the indexed columns reads only the rows that it needs.
An index must match the query. An index on two columns helps a filter on the first column, or on both, but not a filter on the second column alone. An index on a column that no query uses gives no help.
Indexes have a cost. Each insert and update must also change each index, which adds disk work and makes writes slower. Each index also uses disk space and memory. Add the indexes that your main queries need, and remove the others.
In the levels you add the index that a slow query needs and check that the writes still fit.