B-tree, GiST, GIN, BRIN, sargability

What to say

A B-tree is a balanced tree of pages. The root and internal pages hold separators: a key plus a link to a child page. The leaves hold keys in sorted order and links to heap rows (`ctid`). The search goes from the root down: at each level the separators pick the right branch, and in a few steps (the tree height) you reach a leaf. The height grows with the logarithm of the row count, so even on billions of records it is a handful of page accesses. The leaves are linked left and right, which gives a fast range walk and `ORDER BY` without a separate sort.

What they want to hear

A senior should: - describe the levels: root, internal pages with separators, leaves with keys and ctid - tie the logarithmic complexity to the tree height and the number of page accesses - explain why a B-tree is good for ranges and sorting: the leaves are sorted and linked - mention the optimizations: deduplication of equal keys and suffix truncation of separators save space

Pitfalls

• ✗ Thinking B-tree leaves store the rows themselves. They store the key and a `ctid`, and the row is in the heap
• ✗ Assuming a B-tree is efficient for `LIKE '%x'` or an inequality over an expression. The order does not help there
• ✗ Forgetting the height is small: even on large tables it is a few levels, not dozens

Follow-up

• ? Why does a B-tree give `ORDER BY` without a separate sort?
• ? What is stored in a B-tree leaf?
• ? What is deduplication in a B-tree, and why does it exist?

What to say

An index on a column stores the values of that column. If the condition wraps the column in a function or expression, `WHERE lower(email) = 'a@b.c'`, `WHERE created_at::date = '2024-01-01'`, `WHERE id + 0 = 5`, an index on the raw column does not fit: it has no `lower(email)` values. The same with `LIKE '%abc'`: the leading percent kills the ability to descend the tree, because the start of the string is unknown. A condition the index can use directly is called sargable. There are three cures: rewrite the predicate so the column is "bare"; build an index on the expression (`CREATE INDEX ON t (lower(email))`); for patterns and substrings take a trigram index (`pg_trgm`).

What they want to hear

A senior should: - explain the root: an index stores the column's values, and a function over the column yields different values - give the typical anti-cases: a function/cast over the column, `LIKE '%...'`, arithmetic over the column - give the three cures: rewrite the predicate, an index on the expression, a trigram for substrings - know that `text_pattern_ops` is needed for `LIKE 'abc%'` in a locale other than C

Pitfalls

• ✗ Wrapping a column in a function in `WHERE` and expecting a plain index to work
• ✗ Building a plain B-tree and being surprised `LIKE '%abc%'` does not use it. That needs a trigram
• ✗ Forgetting `text_pattern_ops` for a prefix `LIKE` in a non-C locale

Follow-up

• ? How do you make an index work for `WHERE lower(email) = ...`?
• ? Why is `LIKE 'abc%'` indexable while `LIKE '%abc'` is not?
• ? Why do you need `text_pattern_ops`?

What to say

A composite index `(a, b, c)` is a list sorted by `a`, within equal `a` by `b`, and so on. So it works for conditions on a left prefix: `a`, `a` and `b`, `a` and `b` and `c`. On `b` alone, or on the pair `b, c` without `a`, it is useless. The rule: put first the column that is always an equality, and last the one with a range or a sort. A column from `WHERE a = ? AND b > ?` fits the index `(a, b)` well, while `(b, a)` is already worse here. The column order is not cosmetics. It directly decides whether the planner uses the index.

What they want to hear

A senior should: - explain the "sorted list" model and the left-prefix rule - give the practical rule: equality up front, range and sort at the end - show on `WHERE a = ? AND b > ?` why `(a, b)` is better than `(b, a)` - understand that an extra wide composite index is a cost on writes and space, not only a read benefit

Pitfalls

• ✗ Putting the range column before the equality column. The index works only up to the range
• ✗ Expecting `(a, b, c)` to help a query on `b` alone. The left prefix is not satisfied
• ✗ Breeding composite indexes for every combination. Each one slows writes and eats space

Follow-up

• ? Why does the index `(a, b)` not help a condition on `b` only?
• ? Where in a composite index do you put a column from `ORDER BY`?
• ? What do you pay for each extra index on a table?

What to say

An ordinary index scan finds a `ctid` in the index and goes to the heap for the row itself, to check visibility and fetch the remaining columns. If the index contains every column the query needs (a covering index, including through `INCLUDE`), the heap trip could be skipped. But the index holds no information about version visibility. The visibility map (VM) saves you: if a page is marked in it as "all versions visible to everyone", the heap row need not be read. So an index-only scan is efficient only on a well-vacuumed table with an up-to-date VM. Under an UPDATE load without timely vacuum, an index-only scan degrades into an ordinary one with many `Heap Fetches`.

What they want to hear

A senior should: - explain that an index-only scan avoids the heap trip if the index covers the query - tie it to the visibility map: skipping the heap is allowed only for pages marked in the VM - name `INCLUDE` as a way to add columns to the index without their participation in sorting/uniqueness - understand vacuum's role: a stale VM kills the benefit, and `Heap Fetches` rises

Pitfalls

• ✗ Expecting an index-only scan on a table not vacuumed for a long time. The VM is stale and Heap Fetches happen
• ✗ Thinking a covering index is enough. Without an up-to-date VM the heap trip happens anyway
• ✗ Confusing `INCLUDE` columns with key ones. INCLUDE does not take part in the search or sort

Follow-up

• ? Why does an index-only scan go to the heap if the table was not vacuumed?
• ? What does `INCLUDE` add to an index, and how does it differ from key columns?
• ? What does a large number of `Heap Fetches` in the plan tell you?

What to say

GIN (generalized inverted index) is an inverted index: it stores not "row to value" but "element to the list of rows where it occurs". That is what you need for composite values: full-text search (word to documents), `jsonb` (key or path to rows), arrays (element to rows). A query like `WHERE tags @> '{postgres}'` or `WHERE doc @@ to_tsquery('...')` GIN serves directly. The price is expensive insert and update: one UPDATE of a document touches many index elements. A deferred pending list (`fastupdate`) smooths this out, but it adds periodic cleanup. GIN is large and slow to write, yet it is indispensable for search by content.

What they want to hear

A senior should: - explain the inverted "element to rows" model and why it suits jsonb, arrays, full-text - give the operators GIN handles: `@>`, `@@`, `?` and the like - name the price: heavy insert/update, large size, the role of `fastupdate` - contrast it with a B-tree: that stores the whole value and is no good for searching inside jsonb/an array

Pitfalls

• ✗ Building a B-tree on `jsonb` and expecting key search. That needs a GIN
• ✗ Putting a GIN on a table with very frequent updates of the indexed field without regard for the write cost
• ✗ Forgetting that GIN with `fastupdate` periodically cleans the pending list, which is a load spike

Follow-up

• ? Which jsonb operator does GIN serve, and which not?
• ? What does `fastupdate` do, and what does it trade off?
• ? Why is GIN more expensive than a B-tree on writes?

What to say

BRIN (block range index) stores not the row values but a summary over block ranges: for each stretch of the table it remembers the minimum and maximum value. The index comes out tiny, kilobytes where a B-tree would take gigabytes. It works only with good correlation: if the values grow physically along with row order (the typical example is a time column in a table written in increasing order), then by a range you can immediately drop blocks whose min/max do not fit. On poorly correlated data BRIN is useless: the matching rows are scattered across all blocks, with nothing to drop. This is the index for large append-only tables with a natural order.

What they want to hear

A senior should: - describe BRIN as a min/max summary over block ranges rather than over rows - stress the dependence on correlation: the benefit exists only when the value order matches the physical order - give the niche: large append-only tables, a time column or an increasing identifier - compare the size: BRIN is orders of magnitude smaller than a B-tree, at the cost of a coarse search

Pitfalls

• ✗ Putting BRIN on a poorly correlated column. It cannot drop blocks and becomes useless
• ✗ Expecting pinpoint search from BRIN like a B-tree. It drops blocks coarsely and then still scans the candidates
• ✗ Not rebuilding BRIN after bulk inserts out of order. The min/max summaries blur

Follow-up

• ? Why is BRIN useless on a randomly distributed column?
• ? How much smaller is BRIN than a B-tree, and how?
• ? What kind of table is an ideal BRIN candidate?

What to say

GiST (generalized search tree) is a framework for trees over "inexact" predicates: geometry and `PostGIS` (intersection, proximity), range types, nearest-neighbor search (`ORDER BY point <-> target`). SP-GiST is its relative for unbalanced structures: quadtrees, prefix trees, data with a natural partitioning of space. GIN is the inverted index for composite values: full-text, jsonb, arrays. A rough rule: searching by geometry, ranges, and nearest neighbors goes to GiST; by the content of a document, array, or jsonb to GIN; an exotic spatial structure with uneven partitioning to SP-GiST. Each has its own set of operator classes for specific types.

What they want to hear

A senior should: - lock in the niches: GiST for geometry/ranges/KNN, GIN for content, SP-GiST for uneven spatial structures - give KNN search (`<->`) as GiST's signature capability - understand the choice is driven by the data type and the available operator classes - not pit them as "better/worse": they are about different classes of tasks

Pitfalls

• ✗ Assuming GIN and GiST are interchangeable. They solve different tasks
• ✗ Reaching for GiST for full-text search by default. GIN is usually better, GiST only for specifics
• ✗ Forgetting a type needs a fitting operator class, or the index will not build

Follow-up

• ? Which index serves nearest-neighbor search `ORDER BY p <-> q`?
• ? For full-text search, which is usually better, GIN or GiST?
• ? Where is SP-GiST a good fit?

What to say

An index on its own does not know how to compare values of a specific type. The operator class provides that knowledge. It ties a data type and an access method to a set of operators and support functions: for a B-tree that is "less, less-or-equal, equal, greater" and a comparison function. So a single type can have several classes for different tasks. The canonical example is `text`: the default class sorts by locale and serves `=` and `ORDER BY`, but is no good for a prefix `LIKE` in a non-C locale; for that there is `text_pattern_ops`, which compares byte by byte and makes `LIKE 'abc%'` indexable. You name the class when creating the index: `CREATE INDEX ON t (col text_pattern_ops)`.

What they want to hear

A senior should: - define an operator class as the bundle "type plus access method plus a set of operators and support functions" - explain why a type has several classes, on the `text` and `text_pattern_ops` example - tie it to the previous point: the right class makes `LIKE 'abc%'` sargable in any locale - know the classes are visible in the catalog (`pg_opclass`) and are chosen explicitly for a non-standard task

Pitfalls

• ✗ Building an index on `text` in a non-C locale and expecting `LIKE 'abc%'` to use it. You need `text_pattern_ops`
• ✗ Thinking a type always has one operator class. There can be several for different operators
• ✗ Ignoring the operator class when creating an index for a specific search

Follow-up

• ? Why do you need `text_pattern_ops`, and when do you not?
• ? What goes into the operator class for a B-tree?
• ? Why does one type have several operator classes?

What to say

A hash index stores the hash of a value and serves only equality (`=`): no ranges, no sorting, no prefix search. In return it is more compact than a B-tree on long keys, and on pure `=` it can be a touch faster. Before PostgreSQL 10 hash indexes were not written to WAL and did not survive a crash, so people avoided them; since 10 they are full-fledged and replicate. In practice their niche is narrow: a B-tree also does equality perfectly and additionally handles ranges and sorting, so by default you take a B-tree, and hash only when the key is long, you need strict equality, and the index size matters.

What they want to hear

A senior should: - name the only operation of a hash index, equality, and the absence of ranges and sorting - know the history: before version 10 no WAL and no durability, since 10 full-fledged - explain why a B-tree is still the default: it covers equality and more - outline the rare hash niche: a long key, strict equality, saving on size

Pitfalls

• ✗ Reaching for a hash index for a range query. It is only for `=`
• ✗ Remembering the old rule "hash is unreliable". Since version 10 that is not so
• ✗ Defaulting to hash over a B-tree without a solid reason about the key size

Follow-up

• ? What changed for hash indexes in version 10?
• ? Why is a B-tree usually preferred even for pure equality?
• ? In what case does a hash index actually win?