Skip to content

04 · Database Indexing — Speed Up Read Query Performance

Foundations · Topic 4 of 4


What is an Index?

An index is a data structure that allows the database to find rows without scanning the entire table. Trading write overhead and storage for read speed.


How Indexes Work (B-Tree)

Most relational databases use a B-Tree index by default. See B-Tree vs LSM Tree for internals.

graph TD
    Root["Root: [50]"] --> L["Left: [10, 20, 30]"]
    Root --> R["Right: [60, 70, 80]"]
    L --> D1["Data Pages"]
    R --> D2["Data Pages"]

Index Types

Type Use Case Example
B-Tree Equality and range queries WHERE age > 30
Hash Exact equality only WHERE id = 42
GIN Full-text search, JSONB, arrays WHERE doc @@ 'keyword'
BRIN Very large sorted tables (time-series) WHERE created_at > '2024-01-01'
Composite Multi-column queries WHERE (user_id, created_at)
Covering Index-only scans INCLUDE (email)
Partial Filtered subset WHERE active = true

Index Design Rules

Column order matters for composite indexes

For (a, b, c), leading equality predicates usually narrow the scan most effectively, followed by a range column. A predicate on b alone may still use the index; PostgreSQL 18 supports B-tree skip scans when the cost model favors them. Always inspect the plan rather than assuming an index is guaranteed or impossible.

-- ✅ Uses index (a, b)
SELECT * FROM orders WHERE user_id = 1 AND status = 'active';

-- ❌ Won't use index (a, b) — leading column missing
SELECT * FROM orders WHERE status = 'active';

Cloud Index Implementations

  • B-Tree (default), GIN, GiST, BRIN, Hash
  • EXPLAIN ANALYZE to verify index usage
  • Partial indexes: CREATE INDEX ON orders(user_id) WHERE status = 'active'
  • Secondary indexes stored as separate interleaved tables
  • INTERLEAVE IN PARENT for locality
  • Storing columns in index to avoid back-joins: STORING (email)
  • GSI (Global Secondary Index): different partition key, eventual consistency
  • LSI (Local Secondary Index): same partition key, different sort key, strongly consistent
  • Sparse indexes: only items with the attribute appear in the index
  • Primary index = partition key (hash ring distribution)
  • Distinguish legacy secondary indexes (2i) from Storage-Attached Indexing (SAI), available in Cassandra 5.0
  • Compare SAI with query-specific tables using measured selectivity, partition fan-out and write cost
  • B-Tree indexes, compound, text, geospatial, hashed
  • explain() to check index usage
  • Covered queries (all returned fields in index)
  • Columnar storage, partition pruning and clustering reduce scans; specialized search and vector indexes support eligible workloads
  • Partition by date/timestamp column; cluster by frequently filtered columns

Common Pitfalls

Too many indexes

Every index slows down writes. Audit with pg_stat_user_indexes (Postgres) for unused indexes.

Index on low-cardinality column

An index on a boolean column is rarely useful — the optimizer will prefer a full scan.


Design an Index from a Real Query

For the schema in the foundations lab, retrieve the latest 20 orders for one customer:

CREATE INDEX orders_customer_recent_idx
ON orders (customer_id, created_at DESC, order_id DESC)
INCLUDE (status);

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

Equality on customer_id narrows the key range; the next keys match ordering and make ties deterministic. INCLUDE stores payload without changing key order. An index-only scan still depends on PostgreSQL's visibility map; it does not guarantee zero heap fetches. On tiny tables a sequential scan can be cheaper and entirely correct.

Check estimated versus actual rows, heap fetches, sort nodes and buffer reads. Refresh statistics after bulk changes. EXPLAIN ANALYZE executes its statement, so do not casually use it on production writes. Benchmark write overhead and index size as well as read latency.

Check Your Understanding

#

Question 1

Why can an index on a boolean still help?

#

Question 2

Does a foreign key create an index on its referencing column in PostgreSQL?

Sources: PostgreSQL multicolumn indexes, BigQuery search indexes, Cassandra SAI.