194: Indexes: B-Tree, Hash, GIN, GiST, BRIN, Composite, Partial, and Expression Indexes

Learning outcomes

By the end of this lesson, you should be able to:

explain and apply a b-tree index in a realistic implementation;
explain and apply composite indexes in a realistic implementation;
explain and apply partial indexes in a realistic implementation;
explain and apply expression indexes in a realistic implementation;
explain and apply GIN, GiST, and BRIN indexes in a realistic implementation.

The goal is not to collect index names. It is to connect an observed query shape to an index that helps that query, then verify the result without ignoring write cost, storage, or correctness.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where this concern showed up. Perhaps a list endpoint became slow as a table grew, or a query needed to find active records, search a JSON value, or match a normalized email address. The point is to anchor the terminology in a decision you might actually need to defend.

You are not trying to memorize a catalog of PostgreSQL features. You are learning to make a defensible choice inside a PostgreSQL-backed transactional application, where schema design, correctness, query plans, and concurrency all matter.

Terminology

B-tree: B-tree is PostgreSQL’s default general-purpose index. It supports equality and range comparisons, ordering, and many composite predicates whose leading columns match the query’s access pattern.
Composite indexes: A composite index contains more than one indexed key column. The order of those columns matters because it determines which query predicates and sort orders can use the index efficiently. Treat column order as a precise engineering decision, not merely vocabulary.
Partial indexes: A partial index contains only rows that satisfy an index predicate. This is useful for a hot subset, such as active, pending, or unprocessed records. A query must give the planner enough information to imply that predicate before the partial index is a candidate.
Expression indexes: An expression index indexes a computed value, such as lower(email), rather than the stored column value directly. It is useful when queries use the same expression consistently and that derived access pattern is stable.
GIN GiST BRIN: GIN is common for inverted membership and search structures such as arrays, JSON, and full-text search. GiST is an extensible search-tree framework that supports geometric and range use cases, among others. BRIN summarizes value ranges for physical block ranges and can be effective for huge tables whose rows are naturally ordered on disk.
Index costs: Every index consumes disk space and cache, and every insert, delete, or relevant update may need to maintain it. Duplicate or low-value indexes can therefore make writes, vacuum, and other maintenance more expensive.

The useful distinction is between the value stored in a table and the access path used to find it. An index does not make every query faster. It gives the planner another way to locate rows, and that way is useful only when the query shape, data distribution, and estimated cost make it preferable to a sequential scan or another plan.

Mental model

Treat Indexes: B-Tree, Hash, GIN, GiST, BRIN, Composite, Partial, and Expression Indexes as a design problem with observable inputs, outputs, invariants, and failure modes. The input is the workload: predicates, sort requirements, result limits, data distribution, and table size. The output is not simply “an index exists”; it is a query plan that meets the latency and resource expectations while preserving the database’s correctness guarantees.

Indexes accelerate specific access paths by adding storage, write, and maintenance cost. The right index comes from observed query predicates, ordering, selectivity, and table characteristics. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, execution plans, or diagrams—to prove why the design is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Start with the requirement: which rows must be found, in what order, and within what operational budget? Then identify constraints such as uniqueness, transaction behavior, write volume, and the possibility of concurrent requests. Only after that should you choose an index type and column order. Finally, inspect the actual plan and measure the workload. EXPLAIN is evidence about a plan; it is not a substitute for understanding the requirement.

Do not jump from a requirement directly to a library call or CREATE INDEX statement. First state what must remain true. Then choose the mechanism that enforces or supports it. Also keep the distinction between an index that improves lookup and a constraint that enforces correctness: an index may support a unique constraint, but an ordinary index alone does not make values unique.

Deep dive

1. B-tree

When a query filters by equality, asks for a range, or needs ordered results, the first index type to evaluate is usually a b-tree. It is PostgreSQL’s default general-purpose index for equality, range, ordering, and many prefix-compatible composite predicates. For example, a b-tree can support a lookup by customer_id, a time range on created_at, or an ordered result that follows the index keys.

That does not mean every equality query deserves an index. If a table is tiny, if a predicate matches most rows, or if a query returns a large fraction of the table, a sequential scan may be cheaper. The planner makes a cost-based choice using statistics, so test the real query against representative data rather than assuming an index will always appear in the plan.

Decision rule: Use b-tree deliberately when it makes the access path, contract, or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. When uniqueness is required, use the appropriate unique constraint or unique index; when the goal is only faster lookup, use a non-unique index and verify that its maintenance cost is justified.

2. Composite indexes

Column order matters. Put columns according to the equality, range, and ordering access patterns the application actually uses, rather than applying a simplistic “most selective first” rule. A composite index is ordered by its first key, then by the next key within equal values, and so on. As a result, a query that constrains the leading column can often use the index more directly than a query that constrains only a later column.

For instance, an index on (customer_id, created_at DESC) is a natural fit for “the newest orders for one customer.” It groups each customer’s entries and puts that customer’s newest entries first. An index with the reversed order may be useful for a different workload, but it does not express the same access path. Include a column only when the resulting lookup, ordering, or covering behavior earns its storage and write cost.

Test composite indexes with the actual workload, including queries that omit a leading column, use a range condition, or request a different sort. A query can sometimes use an index in a less direct way, but that is not the same as designing an index around the query’s strongest path.

Decision rule: Use composite indexes deliberately when their column order makes the contract or invariant easier to prove and the measured workload benefits from it. If the index only reduces typing while hiding an assumption, prefer the more explicit design. Avoid creating several near-duplicate permutations without evidence that each one serves a distinct important query.

3. Partial indexes

A full index carries an entry for every row. If an application repeatedly reads a small, hot subset such as active accounts, pending jobs, or unprocessed events, indexing that subset can be smaller and cheaper to scan. A partial index contains only rows satisfying a predicate, which can reduce index size and maintenance work for rows outside that subset.

The planner still needs to establish that the query’s conditions imply the partial-index predicate. If the index is defined for status = 'pending', a query that visibly restricts rows to that status is a straightforward match. A query hidden behind a parameter, a different expression, or a logically equivalent condition that the planner cannot prove may not use it. This is where people usually get confused: the fact that the application always intends to request pending rows does not automatically give the planner that fact.

A partial index is not a security boundary and does not prevent other rows from existing. It is an access-path optimization, unless it is combined with a suitable uniqueness design for a specific invariant. Keep the predicate stable and document the query shape it is intended to support.

Decision rule: Use partial indexes deliberately when they make a hot-subset access path or a narrowly scoped invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. Verify both the intended query and nearby queries that should not use the index.

4. Expression indexes

Sometimes the query does not compare a stored column directly. It normalizes or computes a value first, such as lower(email), and then compares that result. An ordinary index on email does not necessarily provide the ordered values needed for a predicate on lower(email). An expression index stores the result of that expression for index access.

The query and index must use the same expression closely enough for PostgreSQL to match the access path. That makes consistency important: if one code path uses lower(email) and another applies a different normalization rule, they are not interchangeable. Consider whether the expression is stable, whether the underlying data or collation behavior matters, and whether a database constraint is also needed to enforce the desired uniqueness semantics.

Expression indexes are useful, but they can hide application assumptions about normalization. Make the normalization rule explicit, test it with mixed case and boundary values, and inspect the plan for the exact query form used in production.

Decision rule: Use expression indexes deliberately when queries use the same computed expression and the resulting access pattern is stable enough to justify its maintenance cost. If the index only reduces typing while hiding an assumption, prefer the more explicit design. Do not treat an expression index as a replacement for validating untrusted input or for choosing the correct collation and data model.

5. GIN GiST BRIN

These index types solve different problems, so “which one is fastest?” is the wrong opening question.

GIN is an inverted structure. It is a common choice when one row contains multiple searchable members, such as array elements, JSON keys or values, or full-text terms. It can make membership and containment searches practical, but its entries and update behavior can be more expensive than a simple scalar b-tree index.

GiST is an extensible search-tree framework. It supports operator classes for use cases such as geometric data and ranges, where the indexed values do not fit a simple scalar ordering. The appropriate operator class and query operators matter; choosing GiST solely because the data “looks complex” is not enough.

BRIN stores summaries for physical block ranges rather than a detailed entry for every row. It can be effective on very large tables when a column, often a timestamp or sequence, is naturally correlated with the physical order in which rows are stored. If the data is frequently rewritten or randomly distributed, those summaries may be too broad to narrow the scan effectively.

For all three types, confirm that the operator class supports the predicate you actually issue, then compare plans and timings on representative data. A small test table can make an index look impressive while hiding the behavior that matters at production scale.

Decision rule: Use gin gist brin deliberately when the data shape, operator class, physical layout, and observed workload justify it. If it only reduces typing while hiding an assumption, prefer the more explicit design. Record why the selected type fits better than a b-tree or a different specialized index.

6. Index costs

Each index consumes disk space and cache and adds work to inserts, updates, and deletes. An update that changes an indexed value may need to maintain the relevant index entry; even updates that do not change a key can interact with storage and visibility behavior. Duplicate or unused indexes increase write amplification, vacuum work, planning complexity, and maintenance burden without necessarily improving a user-visible query.

That cost is not an argument against indexes. It is a reason to treat them as part of the schema and workload design. Measure the read improvement, inspect index usage, and consider write-heavy paths before adding another index. After a schema change, re-check plans and operational metrics rather than assuming the original trade-off still holds.

Decision rule: Use index costs deliberately when they make the contract or invariant easier to prove and the measured benefit pays for the additional storage and write work. If an index only reduces typing while hiding an assumption, prefer the more explicit design. Remove or consolidate indexes only with evidence that they are redundant and with an operational plan for the change.

Worked example

Suppose a PostgreSQL-backed transactional application needs to show the twenty most recent orders for one customer. The requirement is more useful than the index name: return the right rows, in descending creation order, without scanning every order as the table grows. Start by writing that requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode.

The input contract includes a valid customer identifier and a bounded result size. The output contract includes order identifiers and totals in newest-first order. The database owns persistence and query execution; the application owns request parsing and presentation. If the endpoint also promises uniqueness or a particular transaction view, state those separately rather than assuming an index provides them.

The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes edge cases, retries, and concurrent behavior much harder to reason about.

CREATE INDEX idx_orders_customer_created
  ON orders (customer_id, created_at DESC);

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total
FROM orders
WHERE customer_id = $1
ORDER BY created_at DESC
LIMIT 20;

The index orders rows first by customer_id, then by created_at descending within that customer. That matches the equality predicate, requested order, and small limit. EXPLAIN (ANALYZE, BUFFERS) lets you compare the estimated plan with what actually happened and see buffer activity. Check whether the plan uses the intended index, whether the actual row counts differ substantially from estimates, and whether the measured execution time is meaningful on representative data. Do not infer production behavior from the CREATE INDEX statement alone.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For the normal path, verify the order and the limit. For an empty or missing customer identifier, verify that boundary validation rejects it or that the database behavior is explicitly defined. For a duplicate or concurrent request, decide whether the operation is read-only, whether a stable tie-breaker is needed when timestamps can match, and what transaction consistency is expected. For a dependency failure, verify the repository or service returns a bounded, structured error rather than pretending the query succeeded.

For each case, state which layer detects the problem and what the caller observes. Inspect the actual execution plan for the database case, logs and metrics for a slow or failed request, and the request contract at the application boundary. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. Index creation itself can have operational implications, and a new index can improve one query while increasing write latency or storage pressure elsewhere. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. An index can improve performance, but it does not authorize a caller, validate input, or protect sensitive data.

Guided lab

Given five real query shapes, design the minimum useful index set. Include composite, partial, and expression examples. Run EXPLAIN ANALYZE before and after each relevant change, and record the read improvement alongside the write, storage, cache, and maintenance trade-offs. Include at least one query that should not use each specialized index so you can distinguish an intentional match from an accidental plan choice.

Complete the lab with this discipline:

Write the requirement and two non-requirements. For example, state what the query must return and what it does not promise, such as arbitrary filtering on every column.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing. Capture plans, actual row counts, timing, and relevant buffer information.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note. Include both read behavior and index maintenance cost.

Edge cases and failure modes

B-tree: test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Also test when a sequential scan is cheaper than the index and confirm that the planner’s choice is reasonable.
Composite indexes: test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Include queries with and without the leading column, range predicates, and different sort orders.
Partial indexes: test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm that intended queries imply the predicate and that logically related queries do not silently rely on an index they cannot use.
Expression indexes: test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Include case, normalization, collation, null, and expression-mismatch cases.
GIN GiST BRIN: test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify operator-class support, data distribution, physical correlation for BRIN, and update cost for multi-valued structures.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. Start from the query shapes and the result contract.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. Make the boundary and database assumptions explicit.
Testing only the happy path and therefore discovering contracts only after integration. Include empty results, malformed values, duplicates, concurrent behavior, and dependency failures where they apply.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. A specialized index is not automatically the right index.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. The client is untrusted, and an index does not change that.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. For a slow query, compare estimated and actual rows, check whether statistics and data distribution are representative, inspect buffer usage, and confirm that the query predicates match the intended index. For unexpected writes or storage growth, inspect index definitions and usage rather than assuming the query plan is the only source of cost.

Interview questions

What problem does B-tree solve, and what trade-off or failure mode would make you choose a different approach?
What problem do composite indexes solve, and what trade-off or failure mode would make you choose a different approach?
What problem do partial indexes solve, and what trade-off or failure mode would make you choose a different approach?
What problem do expression indexes solve, and what trade-off or failure mode would make you choose a different approach?
What problem do GIN, GiST, and BRIN solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Indexes: B-Tree, Hash, GIN, GiST, BRIN, Composite, Partial, and Expression Indexes to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

As part of the explanation, distinguish a general-purpose b-tree from specialized GIN, GiST, and BRIN access methods; explain why composite column order matters; and state why an index improves lookup but does not replace authorization or input validation. For the implementation, show the query shape, the reason for the index definition, and the evidence from an execution plan or measurement.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, write-amplification, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.