Lukas Fittl of pganalyze makes the point that databases are just like any other code: they run algorithms with known strengths and limits, and you get good performance by understanding those limits rather than hoping the database figures it out.
The simplest model has two parts.
- The table (the heap) holds the rows in no particular order. Finding a row without help means reading the table from start to end. That is a sequential scan.
- An index is a separate structure, usually a B-tree, that stores a sorted copy of one or more column values with a pointer back to the row. Finding a row through an index means walking a short tree and then jumping to the row.
Two consequences follow. First, an index only helps when it narrows the search a lot. Fittl describes this as cardinality: a primary key has one row per value and makes an excellent index, while a column with ten possible tags returns huge numbers of rows per value and makes a weak one. Second, every index must be updated on every insert, update and delete that touches its columns. The official documentation states it plainly: indexes also add overhead to the database system as a whole, so they should be used sensibly.
There is a subtle third consequence. Because a B-tree is sorted, inserting values in random order forces page splits all over the index, while inserting values in increasing order only extends the end. Fittl notes this is part of why random UUIDs are bad in Postgres as indexed keys, and recommends sequence values or time-ordered identifiers instead.



