Chapter 14 · Indexes and Query Execution
B-Tree, Hash, Composite, Covering, and Specialized Indexes
Index design is not “one column, one index.” The access method, key order, included data, predicate, and expression determine which searches and orderings the database can satisfy efficiently.
Learning outcomes
Choose an index shape for a query shape
Compare B-tree, hash, GiST, SP-GiST, GIN, and BRIN at a conceptual level.
Apply the leading-column rules of composite B-tree indexes.
Design covering indexes that reduce or eliminate table-row fetches.
Use partial and expression indexes for stable, selective workload patterns.
Avoid redundant indexes whose useful prefixes are already provided elsewhere.
Index families solve different search problems
| Index family | Typical strengths | Important limitation |
|---|---|---|
| B-tree | Equality, ranges, prefix order, MIN/MAX, and ORDER BY. | Key order matters; not ideal for every multidimensional or containment search. |
| Hash | Equality lookups. | No natural range ordering; implementation and durability characteristics vary by product. |
| GiST / SP-GiST | Geometric, nearest-neighbor, ranges, trees, and extensible operator classes. | Behavior depends on the operator class and data type. |
| GIN | Inverted indexing for arrays, documents, full text, and containment. | Can be larger and more expensive to update. |
| BRIN | Very large physically correlated tables, such as append-ordered time series. | Summarizes page ranges; weak when physical order does not correlate with the indexed value. |
SQLite also offers specialized virtual-table modules such as FTS and R-Tree. PostgreSQL exposes multiple built-in access methods, including B-tree, Hash, GiST, SP-GiST, GIN, and BRIN.
Composite keys: equality first, then range and order
For a common B-tree workload, a useful starting heuristic is:
CREATE INDEX idx_order_customer_status_dateON sales_order (customer_id, status, ordered_at DESC);SELECT order_id, ordered_at, total_centsFROM sales_orderWHERE customer_id = 417 AND status = 'paid' AND ordered_at >= '2025-05-01'ORDER BY ordered_at DESCLIMIT 20;The optimizer can seek to one customer and one status, then scan the requested date range in output order.
The left-prefix principle
| Predicate | Usefulness of (customer_id, status, ordered_at) |
|---|---|
| customer_id = ? | Strong: constrains the first key. |
| customer_id = ? AND status = ? | Strong: constrains the first two keys. |
| customer_id = ? AND ordered_at >= ? | Useful for the customer prefix, but status breaks direct ordering into the date key. |
| status = ? | Usually cannot perform a narrow leading-key seek in a conventional B-tree. |
| ordered_at >= ? | Usually requires broad index scanning because earlier keys are unconstrained. |
Some optimizers can use skip-scan or combine indexes, but those are planner choices—not a substitute for designing around the dominant workload.
Covering indexes
A query is covered when all required predicate, ordering, join, and output columns are available from the index. SQLite reports USING COVERING INDEX when it can avoid a separate table lookup.
CREATE INDEX idx_order_status_date_totalON sales_order (status, ordered_at, total_cents);EXPLAIN QUERY PLANSELECT ordered_at, total_centsFROM sales_orderWHERE status = 'pending' AND ordered_at >= '2025-06-01'ORDER BY ordered_at;CREATE INDEX idx_order_customer_date_includeON sales_order (customer_id, ordered_at DESC)INCLUDE (status, total_cents, channel);Adding every output column makes an index wide, increases write amplification, and can reduce cache density. Cover only stable, high-value queries.
Partial indexes: index only the useful subset
CREATE INDEX idx_order_active_dateON sales_order (ordered_at, customer_id)WHERE status IN ('pending', 'processing');EXPLAIN QUERY PLANSELECT order_id, customer_id, ordered_atFROM sales_orderWHERE status IN ('pending', 'processing') AND ordered_at >= '2025-06-01'ORDER BY ordered_at;The index excludes paid and cancelled rows, reducing size and maintenance. The query predicate must logically imply the index predicate for the optimizer to use it.
Expression indexes: store a searchable transformation
CREATE INDEX idx_customer_email_lowerON customer (lower(email));EXPLAIN QUERY PLANSELECT customer_id, emailFROM customerWHERE lower(email) = lower('Customer0417@Example.com');SQLite requires the indexed expression to appear in the query in essentially the same written form. Only deterministic expressions are valid index keys.
Specialized PostgreSQL examples
-- Equality-only workload.CREATE INDEX idx_session_token_hashON session USING hash (token);-- JSON containment.CREATE INDEX idx_document_payload_ginON document USING gin (payload jsonb_path_ops);-- Append-ordered event time with physical correlation.CREATE INDEX idx_event_created_brinON event_log USING brin (created_at);-- Geometric nearest-neighbor workload.CREATE INDEX idx_place_location_gistON place USING gist (location);These statements are not portable to SQLite. They illustrate that “create an index” is incomplete without naming the operators and data distribution the index must support.
Detect redundancy
PRAGMA index_list('sales_order');PRAGMA index_info('idx_order_customer_status_date');SELECT name, sqlFROM sqlite_schemaWHERE type = 'index' AND tbl_name = 'sales_order'ORDER BY name;An index on (customer_id) is often redundant when a maintained composite index begins with customer_id. It is not always redundant: width, uniqueness, collation, sort direction, predicates, and workload can still differ.
Checkpoint
Design the key
- Which common index family naturally supports equality, range, and ordered output?
- Why does (customer_id, status, ordered_at) poorly serve a query filtered only by status?
- What is the difference between a composite key column and a PostgreSQL INCLUDE column?
- Why can a partial index be both smaller and cheaper to maintain?
- What must be true for an expression index on lower(email) to help?
Review the answers
B-tree is the general ordered family. A status-only predicate does not constrain the leading customer key. Composite key columns participate in ordering and search; INCLUDE columns are payload for coverage. A partial index omits rows outside its predicate. The query must use a matching deterministic expression, and the optimizer must estimate that route as beneficial.
Summary and references
- Choose the access method for the operators and data shape.
- Composite B-tree order should reflect equality, range, ordering, and coverage needs.
- Covering indexes save row fetches but increase width.
- Partial and expression indexes target stable specialized patterns.
- Review prefix redundancy before adding another index.