Gowtham Potureddi

Posted on Sep 4

Database Indexes Explained: B-Tree, Hash, GIN, BRIN & Bloom

#python #sql #interview #dataengineering

database indexes are the single biggest lever you have over query latency, and the one that most engineers reach for without ever asking the question that actually matters — which index type. Adding CREATE INDEX ON orders(customer_id) is muscle memory; knowing that a B-tree helps a BETWEEN but a hash index does nothing for it, that a GIN index turns a full-table jsonb scan into a millisecond lookup, that a BRIN index on a billion-row time-series table fits in a few kilobytes while a B-tree would cost gigabytes, and that a bloom index can replace five separate B-trees for ad-hoc equality — that is what separates an engineer who adds indexes from one who designs them. The wrong index type is worse than no index at all: it consumes write throughput, bloats storage, and still leaves the planner choosing a sequential scan.

This guide is the walkthrough you wished existed the first time an interviewer asked "when would you pick a hash index over a B-tree?" or "how would you index a jsonb column that users filter on arbitrary keys?" or "why is Postgres ignoring the index you just created?" It walks the five access methods every data engineer must reason about — the general-purpose b-tree index, the equality-only hash index, the inverted gin index for composite and document data, the block-range brin index for naturally-ordered giants, and the probabilistic bloom filter for many-column queries — plus the cost model that ties them together: index selectivity, random-versus-sequential I/O, bitmap scans, and index-only scans. You will learn the composite index column-ordering rules, the covering index INCLUDE trick, partial indexes, and the decision matrix that turns "add an index" into "add this index." Each section pairs a teaching block with a Solution-Tail interview answer — code, a step-by-step trace, an output table, then a concept-by-concept breakdown of why it works.

When you want hands-on reps immediately after reading, drill the indexing practice library →, warm up on the database practice library →, and sharpen query-writing on the SQL practice library →.

On this page

Why the index type decides query cost
B-Tree indexes — the general-purpose default
Hash indexes — equality-only, O(1) lookups
GIN & BRIN — inverted and block-range indexes
Bloom filters & the index-selection decision matrix
Cheat sheet — database index recipes
Frequently asked questions
Practice on PipeCode

1. Why the index type decides query cost

An index is a derived, ordered copy of your data — and the access method decides which queries it can accelerate

The one-sentence invariant: a database index is a redundant, separately-stored data structure that maps column values to the physical locations (TIDs) of the rows that contain them, and the access method — B-tree, hash, GiST, SP-GiST, GIN, BRIN, or bloom — determines which query shapes the planner can answer from the index instead of scanning the whole table, so picking the access method is picking which queries get fast. An index is never free: every one you create is a second copy of a slice of your table that Postgres must keep in sync on every INSERT, UPDATE, and DELETE. You buy read speed with write cost and disk, and the type of index decides exactly which reads you bought.

What an index actually is.

A separate on-disk structure. The heap (the table itself) stores rows in insertion/VACUUM order with no useful ordering. An index is a second structure — a tree, a hash table, an inverted dictionary, a block summary — whose entries point back at heap rows by tuple identifier (ctid / TID: block number + offset).
Maintained on every write. Each INSERT adds an index entry; each UPDATE that changes an indexed column adds a new one; each DELETE leaves a dead entry for VACUUM to reclaim. This is the write-amplification tax you pay for read speed.
Chosen by the planner, not you. You create an index; the planner decides at query time whether using it is cheaper than a sequential scan. A syntactically valid index that the planner never uses is pure overhead — write cost with zero read benefit.
Not one shape but several. "Index" is not a single thing. Postgres ships seven access methods, each a different data structure tuned for a different query shape. Using the wrong one is the most common indexing mistake.

The access methods Postgres ships — and the query shape each serves.

btree — the default. A balanced sorted tree serving equality, range (<, >, BETWEEN), prefix (LIKE 'abc%'), sorting (ORDER BY), and MIN/MAX. If you do not name an access method, you get this.
hash — equality only (=). Stores 32-bit hashes of keys in buckets; O(1) average lookup, but no range, no sort, no prefix, no multicolumn.
gist — generalised search tree for overlapping/nearest-neighbour data: geometric types, ranges, && overlap, KNN <-> ordering.
spgist — space-partitioned GiST for non-balanced structures: quadtrees, radix trees, IP prefixes, text prefix search.
gin — the inverted index. Maps each element inside a composite value (array member, jsonb key/value, full-text lexeme) to the rows containing it. The answer for "does this document contain X?"
brin — block-range index. Stores a tiny min/max summary per range of heap blocks. Microscopic on disk; only useful when the column is physically correlated with row order.
bloom — an extension. A probabilistic signature per row across many columns, giving a compact "definitely not / maybe" filter for arbitrary equality combinations.

The cost model — how the planner decides.

Selectivity. The fraction of rows a predicate keeps. WHERE status = 'pending' on a table that is 1% pending is selective (0.01); on a table that is 90% pending it is not. The planner estimates selectivity from pg_statistic (populated by ANALYZE).
Random vs sequential I/O. An index scan reads index pages then jumps to scattered heap pages — random reads (random_page_cost, default 4.0). A sequential scan reads the heap in order — sequential reads (seq_page_cost, default 1.0). Below a break-even selectivity, a seq scan of the whole table is cheaper than thousands of random index-plus-heap fetches.
Bitmap scans — the middle ground. For moderate selectivity, Postgres builds an in-memory bitmap of matching TIDs from the index, sorts it into heap order, then reads the heap sequentially. This blends index precision with sequential I/O and is why you see Bitmap Index Scan + Bitmap Heap Scan pairs in EXPLAIN.
Index-only scans. If every column the query needs lives in the index (and the page is visible per the visibility map), Postgres never touches the heap at all. This is the fastest read path and the reason covering indexes exist.

What interviewers listen for.

Do you say "it depends on selectivity" before naming an index? — senior signal.
Do you know why the planner ignores an index (low selectivity, stale stats, type mismatch, function wrapping the column)? — required answer.
Do you distinguish index scan / bitmap scan / index-only scan in an EXPLAIN plan? — senior signal.
Do you name the access method per query shape rather than saying "add an index"? — the whole point.
Do you mention the write cost of an index unprompted? — senior signal.

Worked example — reading EXPLAIN: seq scan vs index scan vs bitmap

Detailed explanation. The single most useful indexing skill is reading EXPLAIN (ANALYZE, BUFFERS) and recognising which access path the planner chose and why. The three paths you will see most — Seq Scan, Index Scan, and Bitmap Heap Scan — map directly onto selectivity. Walk through the same query at three different selectivities on an orders table.

Table. orders(id, customer_id, status, total_cents, created_at) — 10 million rows.
Index. CREATE INDEX idx_orders_status ON orders(status).
The variable. How many rows match WHERE status = ? — this is what flips the plan.

Question. Show which access path the planner picks as the matching-row count grows from 100 to 100,000 to 5,000,000, and explain the flip.

Input.

Predicate	Matching rows	Selectivity	Expected plan
`status = 'refunded'`	100	0.00001	Index Scan
`status = 'pending'`	100,000	0.01	Bitmap Heap Scan
`status = 'delivered'`	5,000,000	0.50	Seq Scan

Code.

-- Build the table + index
CREATE INDEX idx_orders_status ON orders (status);
ANALYZE orders;                       -- refresh planner statistics

-- Highly selective: 100 rows out of 10M
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE status = 'refunded';

-- Moderately selective: 100k rows
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE status = 'pending';

-- Non-selective: 5M rows (half the table)
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE status = 'delivered';

Step-by-step explanation.

For status = 'refunded' (100 rows), the planner estimates a tiny fraction of the table matches. It descends the B-tree to find the 100 index entries, then does 100 random heap fetches — cheaper than reading 10M rows. You see Index Scan using idx_orders_status.
For status = 'pending' (100k rows), 100k random heap fetches would thrash the buffer cache. Instead the planner builds a bitmap of all matching TIDs from the index, sorts it into physical page order, and reads those heap pages sequentially. You see a Bitmap Index Scan feeding a Bitmap Heap Scan.
For status = 'delivered' (5M rows, half the table), touching the index at all is wasted work — the planner will read most heap pages anyway. A plain Seq Scan that streams the heap sequentially wins. The index is ignored on purpose; this is correct, not a bug.
The exact break-even points depend on random_page_cost, seq_page_cost, effective_cache_size, and row width. The default random_page_cost = 4.0 assumes spinning disks; on SSDs, lowering it to 1.1 makes the planner prefer index scans at higher selectivities.
BUFFERS shows shared-buffer hits vs reads — the ground truth for whether the index actually saved I/O. A plan that "used the index" but read the same number of buffers as a seq scan saved nothing.

Output.

Query	Plan chosen	Heap access	Why
100 rows	Index Scan	100 random fetches	Fraction tiny; random cost < full scan
100k rows	Bitmap Heap Scan	pages read in heap order	Too many for random; too few for seq
5M rows	Seq Scan	full sequential read	Index would cost more than reading all

Rule of thumb. The plan is a function of selectivity, not of whether an index "exists." An index on a column you always filter for 50% of the table will never be used for that filter — and still costs you on every write.

Worked example — why the planner ignores your index

Detailed explanation. "I added an index and the query is still slow" is the most common indexing complaint, and it almost always traces to one of five causes. Each is diagnosable from EXPLAIN plus a schema check. Walk through the five and the fix for each.

Low selectivity. Covered above — correct behaviour.
Stale statistics. pg_statistic is out of date, so the planner mis-estimates row counts.
Type mismatch. The column is bigint but the literal is a text/numeric, so the index's operator class does not apply.
Function-wrapped column. WHERE lower(email) = 'x' cannot use a plain index on email — the index stores email, not lower(email).
Leading-wildcard LIKE. WHERE name LIKE '%smith' cannot use a B-tree; the tree is ordered by prefix.

Question. Given a query that ignores its index, identify the cause and write the fix for the function-wrapping and stale-stats cases.

Input.

Symptom	Likely cause	Fix
Rows estimate wildly off	stale stats	`ANALYZE table`
`WHERE lower(email)=...` seq scans	function wrapping	expression index
`WHERE id = '42'` seq scans	text/int mismatch	fix literal type
`LIKE '%term'` seq scans	leading wildcard	trigram GIN index

Code.

-- CAUSE 1: stale statistics — planner thinks few rows match when many do
ANALYZE orders;                         -- or turn up autovacuum_analyze_scale_factor

-- CAUSE 2: function-wrapped column. This index is NOT used:
CREATE INDEX idx_users_email ON users (email);
-- ... because the query wraps the column:
SELECT * FROM users WHERE lower(email) = 'ada@x.io';   -- seq scan!

-- FIX: index the EXPRESSION, matching the query exactly
CREATE INDEX idx_users_email_lower ON users (lower(email));
SELECT * FROM users WHERE lower(email) = 'ada@x.io';   -- index scan

-- CAUSE 3: type mismatch — quoting an integer literal
SELECT * FROM orders WHERE id = '42';   -- may cast and skip the index
SELECT * FROM orders WHERE id = 42;     -- clean int match uses the index

-- Diagnose: compare estimated vs actual rows
EXPLAIN (ANALYZE) SELECT * FROM orders WHERE status = 'pending';
--   "rows=100000" (estimate) vs "actual rows=98342" → stats are healthy
--   "rows=5" (estimate) vs "actual rows=98342"     → run ANALYZE

Step-by-step explanation.

Stale statistics are the sneakiest cause: after a bulk load, pg_statistic still reflects the old distribution, so the planner may think a value is rare and pick an index scan that fetches millions of rows one at a time — or the reverse. ANALYZE (or aggressive autovacuum) refreshes the histograms.
A function on the indexed column defeats a plain index because the index stores raw email values, sorted as raw text. lower(email) is a different value the index knows nothing about. An expression index on lower(email) stores exactly what the query asks for.
Type mismatches can force an implicit cast on the column side (id::text = '42'), which — like a function wrap — hides the raw indexed value from the planner. Match literal types to column types.
A leading-wildcard LIKE '%term' cannot use a B-tree because the tree is ordered left-to-right; you cannot binary-search for a suffix. The fix is a pg_trgm trigram GIN index, covered in section 4.
Always diagnose with EXPLAIN (ANALYZE) and compare the estimated rows= against actual rows in the same node. A large gap means stale stats or a correlation the planner cannot see (fixable with extended statistics or CREATE STATISTICS).

Output.

Fix applied	Before	After
`ANALYZE`	estimate off 1000×	estimate within 10%
expression index	Seq Scan	Index Scan on `lower(email)`
literal type fixed	implicit cast, seq scan	direct index scan
trigram GIN	Seq Scan on `LIKE '%x'`	Bitmap Index Scan

Rule of thumb. Before blaming Postgres for ignoring an index, run ANALYZE, check for functions/casts wrapping the column, and read the estimated-vs-actual row counts. The planner is almost always right about selectivity; it is your stats or your predicate shape that is wrong.

Worked example — the access-method decision matrix

Detailed explanation. Given a column and a query shape, a senior engineer runs a short decision procedure to pick the access method. Codifying it makes the interview answer reproducible: hand me a column and how it is queried, and I name the index type in seconds. Walk the procedure across four canonical columns.

created_at on an append-only 1B-row table, queried by range. → BRIN (physically correlated, huge).
email queried only by exact equality. → hash or B-tree (B-tree unless the key is very wide and you never sort).
tags text[] queried by containment. → GIN.
(country, plan, status) queried in arbitrary equality combinations. → bloom (or several B-trees).

Question. Walk the decision matrix and record the access method each column should use.

Input.

Column & query	Range?	Inside a value?	Correlated?	Best access method
`created_at` range, 1B rows	yes	no	yes	BRIN
`email` equality only	no	no	no	B-tree (or hash)
`tags text[]` containment	n/a	yes	no	GIN
`(country,plan,status)` ad-hoc `=`	no	no	no	bloom

Code.

# Access-method decision helper (illustrative)
def pick_index(range_query: bool,
               inside_composite: bool,
               physically_correlated: bool,
               table_rows: int,
               many_column_equality: bool) -> str:
    if inside_composite:
        return "gin"                       # array / jsonb / full-text membership
    if range_query and physically_correlated and table_rows > 50_000_000:
        return "brin"                      # huge, naturally ordered
    if many_column_equality:
        return "bloom"                     # arbitrary AND-of-equality combos
    if range_query:
        return "btree"                     # ranges/sorts need ordered leaves
    return "btree"                         # equality default; hash only for wide keys, no sort


print(pick_index(True,  False, True,  1_000_000_000, False))  # → brin
print(pick_index(False, False, False, 5_000_000,     False))  # → btree
print(pick_index(False, True,  False, 5_000_000,     False))  # → gin
print(pick_index(False, False, False, 5_000_000,     True))   # → bloom

Step-by-step explanation.

The first question is always "does the predicate look inside a composite value?" — array containment, jsonb key/value, full-text match. If yes, only GIN (or GiST for some cases) can help; B-tree indexes the value as an opaque blob, not its members.
The second question is "is this a range scan over a huge, physically-ordered column?" A billion-row events table where created_at increases with insertion order is the textbook BRIN case: a summary a few KB in size prunes 99% of blocks.
The third question is "am I filtering many columns in unpredictable combinations?" If users can filter by any subset of (country, plan, status, tier, source), maintaining a B-tree per combination is untenable; one bloom index covers them all at the cost of a recheck.
If none of those apply and you need ranges or sorting, B-tree is the answer — it is the only method that serves ORDER BY. Reach for hash only when the key is wide, you query by equality exclusively, and you never sort.
The procedure is deliberately ordered: GIN and BRIN are the "special-case winners," bloom is the "many-column" winner, and B-tree is the default that catches everything else. Hash is a narrow optimisation, not a starting point.

Output.

Column	Access method	One-line reason
`created_at` (1B, ordered)	BRIN	tiny summary prunes block ranges
`email` (equality)	B-tree	default; hash only if very wide + no sort
`tags text[]`	GIN	indexes members, not the whole array
`(country,plan,status)` ad-hoc	bloom	one index for arbitrary `=` combos

Rule of thumb. Ask three questions in order — "inside a value? / huge and ordered? / many columns of equality?" — and the special-case index falls out. If all three are "no," you want a B-tree.

SQL Interview Question on index selection and EXPLAIN

A senior interviewer often opens with: "Here is a 200-million-row events table. Analysts run SELECT * FROM events WHERE event_type = 'purchase' AND created_at >= now() - interval '1 day'. The query takes 40 seconds. Walk me through how you would diagnose it with EXPLAIN, decide which index to add, and prove the fix — including why a naive single-column index might still be ignored."

Solution Using EXPLAIN ANALYZE and a selective composite index

-- Step 1 — diagnose the current plan
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM events
WHERE  event_type = 'purchase'
  AND  created_at >= now() - interval '1 day';
-- Reveals: Seq Scan on events (actual rows=180k, buffers read=2.1M) — reading all 200M

-- Step 2 — refresh stats so estimates are trustworthy
ANALYZE events;

-- Step 3 — add a composite index: equality column FIRST, range column SECOND
CREATE INDEX idx_events_type_created
    ON events (event_type, created_at);

-- Step 4 — re-check the plan
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM events
WHERE  event_type = 'purchase'
  AND  created_at >= now() - interval '1 day';
-- Now: Index Scan / Bitmap Heap Scan on idx_events_type_created (buffers read ~3k)

Step-by-step trace.

Trace input — events distribution: 200M rows, event_type='purchase' is ~5% (10M rows), of which ~180k fall in the last day.

Step	What happens	Rows in play
1	Seq Scan reads all 200M rows, filters both predicates	200,000,000 scanned → 180,000 kept
2	`ANALYZE` refreshes histograms; planner now estimates 180k, not 5	—
3	Composite `(event_type, created_at)` built; `event_type=` narrows to 10M, then `created_at>=` range-scans the ordered second column	10,000,000 → 180,000
4	Index descends to `purchase`, walks the ordered `created_at` leaves for one day	180,000 fetched

Final result — the plan flips from a 200M-row Seq Scan (~40 s) to an index range scan touching ~180k rows (~80 ms).

Output:

Metric	Before (Seq Scan)	After (composite index)
Rows scanned	200,000,000	~180,000
Buffers read	~2.1M pages	~3k pages
Latency	~40 s	~80 ms
Index used	none	idx_events_type_created

Why this works — concept by concept:

EXPLAIN ANALYZE first — never guess. The plan shows the actual access path, the estimated-vs-actual row gap, and buffer counts, which together tell you whether the problem is stats, selectivity, or a missing index.
Equality column before range column — in a composite B-tree, the leftmost column must be an equality predicate to narrow the search; the second column can then be range-scanned within that narrowed slice. Reversing the order (created_at, event_type) would scan a full day across all event types.
ANALYZE for honest estimates — the planner only picks the index if it believes the predicate is selective. Stale stats can make it either over- or under-use the index; refreshing them is step zero.
Bitmap vs index scan — with 180k matches, Postgres may choose a bitmap heap scan to convert random heap access into sequential access; both are dramatically cheaper than the seq scan.
Cost — one composite index (~a few GB on 200M rows), refreshed on every write to event_type/created_at. The eliminated cost is a 200M-row sequential scan per query. Read cost drops from O(N) to O(log N + matches); write cost rises by one index maintenance per row.

SQL
Topic — indexing
Indexing and EXPLAIN-plan problems

Practice →

SQL Topic — database Database internals and query-cost problems

Practice →

2. B-Tree indexes — the general-purpose default

`btree` is the balanced sorted tree that serves equality, range, prefix, sort, and index-only scans — the one index that does almost everything

The mental model in one line: a b-tree index is a self-balancing, multi-level, sorted tree whose leaf pages hold the indexed keys in order and are linked into a doubly-linked list, so Postgres can descend from root to leaf in O(log N) to answer an equality lookup, then walk the linked leaves in either direction to answer a range, a prefix match, or an ORDER BY — and because the keys are stored in the index, a query that needs only indexed columns can be answered without touching the heap at all. It is the default when you write CREATE INDEX with no USING clause, it is what backs every primary key and unique constraint, and it is the only access method that can satisfy sorting. If you learn one index type deeply, learn this one.

The structure — root, internal, leaf.

Root and internal pages. Hold separator keys and child pointers. Descending the tree is a binary search at each level; the height is typically 3–4 even for hundreds of millions of rows, so a lookup is a handful of page reads.
Leaf pages. Hold the actual indexed key values in sorted order, each paired with the heap TID(s) that contain that value. This is where the answers live.
Doubly-linked leaves. Adjacent leaf pages are linked both forward and backward. Once a range scan lands on the first matching leaf, it walks the links to stream every subsequent match without re-descending the tree — this is what makes BETWEEN and ORDER BY cheap.
Balance. Splits and merges keep every leaf at the same depth, so worst-case and average-case lookups are both O(log N). No key is ever more expensive to find than any other.

The operators a B-tree serves.

Equality and inequality. =, <, <=, >, >=, <> (the last only via full scan), BETWEEN, IN (...).
Prefix matching. LIKE 'abc%' and ~ '^abc' use the index because a prefix defines a contiguous key range — but LIKE '%abc' (leading wildcard) cannot.
Sorting. ORDER BY col [ASC|DESC] is answered by reading leaves in order; a matching DESC index or a reverse leaf walk avoids a sort node entirely.
MIN / MAX. Answered by reading the first or last leaf entry — O(log N), not a scan.
NULL handling. NULLS FIRST/NULLS LAST and IS NULL are indexable; a B-tree stores NULLs and can find them.

Composite indexes and the leftmost-prefix rule.

Column order is everything. An index on (a, b, c) is sorted by a, then b within equal a, then c within equal (a,b). It can serve predicates on a, on (a,b), and on (a,b,c) — the leftmost prefix.
What it cannot serve well. A predicate on b alone, or c alone, cannot use the index efficiently — there is no contiguous range for it. (Postgres may still do a slower full index scan, but that is not the win you wanted.)
Equality before range. Put equality columns first and the range/sort column last. (event_type, created_at) serves event_type = ? AND created_at > ?; the reverse does not.
Order by the query, not by "cardinality." The old "most selective column first" folklore is often wrong; order columns to match how your WHERE/ORDER BY clauses read left to right.

Covering indexes and partial indexes — the two power moves.

Covering with INCLUDE. CREATE INDEX ... ON t (a) INCLUDE (b, c) stores b and c in the leaf as non-key payload. A query SELECT b, c FROM t WHERE a = ? becomes an index-only scan — the heap is never read.
Index-only scan prerequisites. All selected columns must be in the index (as key or INCLUDE), and the page must be marked all-visible in the visibility map (kept fresh by VACUUM).
Partial indexes. CREATE INDEX ... ON t (a) WHERE status = 'active' indexes only the rows matching the predicate. Smaller, cheaper to maintain, and ideal for a hot subset (e.g. only un-archived rows).
Combine them. A partial covering index on the hot subset is the smallest possible structure that fully answers the hottest query.

Worked example — the leftmost-prefix rule on a composite index

Detailed explanation. The leftmost-prefix rule is the single most-tested B-tree concept and the one most engineers get subtly wrong. An index on (customer_id, status, created_at) can accelerate some queries and not others, entirely based on which columns the WHERE clause constrains. Walk through five queries against one composite index.

Index. CREATE INDEX idx ON orders (customer_id, status, created_at).
The rule. The index helps a query only if it constrains a leftmost prefix of the column list.
The test. For each query, ask: does it constrain customer_id? then status? then created_at?

Question. For the composite index (customer_id, status, created_at), decide which of five queries can use it and how far into the index each reaches.

Input.

Query predicate	Uses index?	Prefix reached
`customer_id = 7`	yes	`customer_id`
`customer_id = 7 AND status = 'paid'`	yes	`customer_id, status`
`customer_id = 7 AND status = 'paid' AND created_at > '2026-01-01'`	yes (full)	all three
`status = 'paid'`	no (efficient)	none — `status` is not leftmost
`customer_id = 7 AND created_at > '2026-01-01'`	partial	`customer_id`, then filters `created_at`

Code.

CREATE INDEX idx_orders_cust_status_created
    ON orders (customer_id, status, created_at);

-- USES the full index: all three columns, equality then equality then range
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE  customer_id = 7 AND status = 'paid' AND created_at > '2026-01-01';

-- USES only the customer_id prefix, then filters created_at in the heap-ish step
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE  customer_id = 7 AND created_at > '2026-01-01';

-- Does NOT use the index efficiently: status is not the leading column
EXPLAIN ANALYZE
SELECT * FROM orders WHERE status = 'paid';   -- likely Seq Scan

Step-by-step explanation.

customer_id = 7 AND status = 'paid' AND created_at > '2026-01-01' is the ideal case: two equality columns narrow the search to a contiguous slice, and the trailing range column is walked in order within that slice. The index answers the whole predicate.
customer_id = 7 AND created_at > '2026-01-01' reaches the customer_id prefix cleanly, but because status (the middle column) is unconstrained, the index cannot jump straight to the created_at range — it scans all of customer 7's entries and filters by created_at. Still far better than a full table scan, but not as tight as the three-column case.
status = 'paid' alone constrains no leftmost prefix (customer_id is skipped), so the index offers no contiguous range. Postgres falls back to a sequential scan (or a full index scan if that happens to be cheaper). A separate index on (status) would be needed.
The fix for query 2 depends on frequency: if customer_id + created_at (skipping status) is common, reorder the index to (customer_id, created_at, status) or add a second index. Index design follows query shape.
This is why "just index every column" fails: a five-column composite serves only queries that constrain its leftmost prefixes, and each ordering serves a different family of queries.

Output.

Query	Access path	Efficiency
all three columns	Index Scan (full use)	best
`customer_id` + `created_at`	Index Scan (partial)	good
`status` alone	Seq Scan	index unused

Rule of thumb. Order composite index columns to match the leftmost prefix your queries constrain, equality columns first and the range/sort column last. A column that is sometimes skipped in the middle breaks the prefix for everything after it.

Worked example — covering index and the index-only scan

Detailed explanation. An index-only scan is the fastest read Postgres can do: it answers the query entirely from the index without ever fetching a heap row. The requirement is that every column the query touches lives in the index. The INCLUDE clause lets you add non-key payload columns cheaply. Walk through converting a hot query to an index-only scan.

Hot query. SELECT total_cents FROM orders WHERE customer_id = ? AND status = 'paid'.
Naive index. (customer_id, status) — still fetches total_cents from the heap.
Covering index. (customer_id, status) INCLUDE (total_cents) — answers entirely from the index.

Question. Build a covering index that turns the hot query into an index-only scan and explain the visibility-map requirement.

Input.

Component	Value
Query	`SELECT total_cents WHERE customer_id=? AND status='paid'`
Key columns	`customer_id, status`
Payload column	`total_cents` (via `INCLUDE`)
Requirement	pages all-visible in visibility map

Code.

-- Naive index — key columns only; heap still read for total_cents
CREATE INDEX idx_orders_cust_status
    ON orders (customer_id, status);

-- Covering index — total_cents stored as non-key payload in the leaf
CREATE INDEX idx_orders_cust_status_cover
    ON orders (customer_id, status) INCLUDE (total_cents);

-- Keep the visibility map fresh so index-only scans stay eligible
VACUUM (ANALYZE) orders;

EXPLAIN (ANALYZE, BUFFERS)
SELECT total_cents
FROM   orders
WHERE  customer_id = 7 AND status = 'paid';
-- Plan: Index Only Scan using idx_orders_cust_status_cover
--       Heap Fetches: 0

Step-by-step explanation.

With the naive (customer_id, status) index, Postgres finds the matching TIDs in the index but must then visit each heap row to read total_cents, incurring random heap I/O proportional to the number of matches.
INCLUDE (total_cents) stores total_cents in the leaf pages as non-key payload. It is not part of the search key (so it does not affect ordering or key size in internal pages) but it is available to satisfy the SELECT.
The plan becomes Index Only Scan with Heap Fetches: 0 — every column the query needs is in the index, so the heap is never touched. This is the fastest possible read path.
The catch is the visibility map: Postgres can skip the heap only for pages marked all-visible. Recently modified pages are not all-visible until VACUUM runs, so a write-heavy table can show nonzero Heap Fetches even with a covering index. Keeping autovacuum healthy is what keeps index-only scans fast.
Use INCLUDE (not extra key columns) for payload you only return, never filter/sort on — it keeps the internal tree pages small (faster descent) while still covering the query.

Output.

Index	Plan	Heap fetches
`(customer_id, status)`	Index Scan	one per matching row
`(customer_id, status) INCLUDE (total_cents)`	Index Only Scan	0 (if all-visible)

Rule of thumb. Put filter/sort columns in the key and return-only columns in INCLUDE. An index-only scan needs both the covering index and a healthy visibility map — check Heap Fetches: 0 in the plan to confirm you actually got one.

Worked example — partial index for a hot subset

Detailed explanation. A partial index indexes only the rows that match a WHERE predicate, making it smaller and cheaper than a full index when queries always target a subset. The classic case is a status column where you only ever query the "active" minority. Walk through indexing only unprocessed jobs.

Table. jobs(id, status, priority, created_at) — 100M rows, but only ~50k are status = 'queued' at any moment.
Full index. (status, priority) indexes all 100M rows — mostly done rows you never query.
Partial index. (priority) WHERE status = 'queued' indexes only the ~50k hot rows.

Question. Build a partial index for the queue-poll query and quantify the size and maintenance savings.

Input.

Component	Full index	Partial index
Rows indexed	100,000,000	~50,000
On-disk size	multiple GB	a few MB
Maintained on `done` rows?	yes	no
Query served	queue poll	queue poll

Code.

-- Full index — wastefully indexes 100M rows, 99.95% of them 'done'
CREATE INDEX idx_jobs_status_priority ON jobs (status, priority);

-- Partial index — only the ~50k rows that are actually queried
CREATE INDEX idx_jobs_queued
    ON jobs (priority, created_at)
    WHERE status = 'queued';

-- The poll query MUST include the partial predicate to use the index
EXPLAIN ANALYZE
SELECT id FROM jobs
WHERE  status = 'queued'
ORDER  BY priority DESC, created_at ASC
LIMIT  100;
-- Plan: Index Scan using idx_jobs_queued (tiny; already ordered)

Step-by-step explanation.

The full (status, priority) index stores an entry for every one of the 100M rows, including the ~99.95% that are done and never queried through this index. Every INSERT/UPDATE maintains those useless entries.
The partial index WHERE status = 'queued' stores entries only for queued rows. At ~50k rows it is a few MB instead of several GB, fits in memory, and is maintained only when a row enters or leaves the queued state.
The query must contain the partial predicate (status = 'queued') — either literally or provably implied — for the planner to use the partial index. This is a feature: it guarantees the index is only consulted for the subset it covers.
Because the partial index is ordered by (priority DESC, created_at ASC) matching the ORDER BY, the queue-poll LIMIT 100 reads the first 100 leaf entries and stops — no sort node, no heap scan of the done rows.
When a job finishes (status = 'done'), its entry is removed from the partial index automatically, so the index stays small forever regardless of how many total rows the table accumulates.

Output.

Metric	Full index	Partial index
Entries maintained	100M	~50k
Size	several GB	a few MB
Poll latency	good	best (fits in cache)
Write overhead on `done` rows	yes	none

Rule of thumb. When queries always filter to a small, stable subset (active/queued/unarchived), a partial index on that subset is dramatically smaller and cheaper than a full index — and the poll query must repeat the partial predicate to use it.

SQL Interview Question on B-tree composite index design

A senior interviewer might ask: "A dashboard runs SELECT order_id, total_cents FROM orders WHERE customer_id = ? AND status = 'paid' ORDER BY created_at DESC LIMIT 20 thousands of times per minute. Design the single best B-tree index for it, explain the column order, and show how to make it an index-only scan that returns already-sorted rows with no sort step."

Solution Using a composite covering index with a matching sort order

-- One index that (a) matches the equality prefix, (b) provides the sort order,
-- and (c) covers the returned columns for an index-only scan.
CREATE INDEX idx_orders_dashboard
    ON orders (customer_id, status, created_at DESC)
    INCLUDE (order_id, total_cents);

VACUUM (ANALYZE) orders;    -- keep pages all-visible for index-only scans

EXPLAIN (ANALYZE, BUFFERS)
SELECT order_id, total_cents
FROM   orders
WHERE  customer_id = 42 AND status = 'paid'
ORDER  BY created_at DESC
LIMIT  20;
-- Plan: Index Only Scan using idx_orders_dashboard
--       Heap Fetches: 0    (no sort node; LIMIT stops after 20 leaves)

Step-by-step trace.

Trace input — orders for customer_id = 42:

order_id	status	created_at	total_cents
900	paid	2026-08-30	1500
901	pending	2026-08-29	900
902	paid	2026-08-28	2200
903	paid	2026-08-20	700

Descend the index to the slice customer_id = 42 AND status = 'paid' — an equality prefix, so it is one contiguous region of the leaves.
Within that slice the leaves are already ordered by created_at DESC, so the first entries are the newest paid orders: 900, then 902, then 903. Row 901 (pending) is not in the slice at all.
LIMIT 20 reads the first 20 leaf entries in order and stops — no sort node is needed because the index order is the requested order.
order_id and total_cents are in the leaf via INCLUDE, so each result row is fully formed from the index — Heap Fetches: 0.

Final result — the top-N newest paid orders, already sorted, from the index alone.

Output:

order_id	total_cents
900	1500
902	2200
903	700

Why this works — concept by concept:

Equality prefix then sort column — (customer_id, status) are equality predicates and come first; created_at DESC is the sort column and comes last, so the matching slice is contiguous and pre-sorted.
DESC in the index definition — declaring created_at DESC makes the leaf order match the ORDER BY DESC exactly, so the planner drops the sort node instead of reversing or re-sorting.
INCLUDE for returned columns — order_id and total_cents are returned but never filtered/sorted, so they belong in INCLUDE, keeping the key narrow while still covering the query.
LIMIT short-circuits the scan — because the rows arrive pre-sorted, LIMIT 20 stops after 20 leaf reads; the query cost is independent of how many paid orders the customer has.
Cost — one composite covering index, maintained on writes to the indexed/included columns. Query cost is O(log N + 20) with zero heap fetches, versus O(matches) heap reads plus a sort for a naive index. The trade is a slightly larger index for a sort-free, heap-free hot path.

SQL
Topic — indexing
Composite and covering index problems

Practice →

SQL Topic — sql SQL query-writing and ORDER BY problems

Practice →

3. Hash indexes — equality-only, O(1) lookups

`hash` stores a 32-bit hash of each key in buckets — a pure equality index with O(1) average lookup and none of the B-tree's extras

The mental model in one line: a hash index computes a 32-bit hash of the indexed value, uses it to select a bucket, and stores the hash plus the heap TID there, so an equality lookup (WHERE col = value) hashes the value once and jumps straight to the right bucket in O(1) average time — but because a hash destroys ordering, a hash index cannot serve ranges, sorting, prefix matching, pattern matching, or multicolumn predicates, and it has been crash-safe and WAL-logged only since PostgreSQL 10. It is a specialist: for pure equality on a wide key where you never need order, a hash index can be smaller than a B-tree and just as fast; for anything else, it is strictly worse than a B-tree.

The structure — hash, bucket, overflow.

Hash function. Postgres hashes the key to a 32-bit value. Two different keys can collide to the same bucket; the index stores the hash code so most collisions are resolved by comparing hash codes before touching the heap.
Buckets. A fixed-then-growing set of primary bucket pages. The high bits of the hash select the bucket. Lookups touch one bucket page in the common case.
Overflow pages. When a bucket fills, overflow pages chain off it. Heavy skew (many rows sharing a value) degrades a bucket into a long overflow chain — the hash equivalent of a hot partition.
Bucket splits. As the index grows, buckets split to keep chains short. This is amortised O(1); the index expands its bucket count over time.

What a hash index can and cannot do.

Serves only =. WHERE col = value and equality joins. That is the entire repertoire.
No ranges. <, >, BETWEEN are impossible — a hash scatters values, so "greater than" has no meaning in bucket space.
No sorting. It cannot satisfy ORDER BY, MIN, or MAX. There is no order to read.
No prefix / pattern. LIKE 'abc%' cannot use it; the hash of 'abcd' bears no relation to the hash of 'abc'.
No multicolumn. Hash indexes are single-column only. You cannot build hash(a, b).
No unique constraint backing. Unique constraints require a B-tree; a hash index cannot enforce uniqueness.

Size and the case for hash over B-tree.

The size argument. A B-tree leaf stores the full key; on a wide key (a long URL, a UUID as text, a 200-char token) that is a lot of bytes per entry. A hash index stores only the 32-bit hash — so on very wide keys it can be materially smaller.
The break-even. For narrow keys (int, bigint), a B-tree is as small or smaller and infinitely more flexible; there is no reason to use hash. The size win only appears on genuinely wide keys.
The equality-only precondition. You may use a hash index only if you are certain the column is queried by equality exclusively, forever. The moment someone needs a range or a sort, you need a B-tree anyway — and then the hash index is redundant overhead.
Crash safety since PG10. Before PostgreSQL 10, hash indexes were not WAL-logged (not crash-safe, not replicated) and were widely discouraged. Since PG10 they are fully durable — the historical warnings no longer apply.

When to reach for it — and the honest default.

Reach for hash when. The key is wide, queried only by =, never sorted, and index size matters (memory-constrained, huge table).
The honest default. A B-tree on the same column costs little more and does everything hash does plus ranges, sorts, and prefix. Most teams standardise on B-tree and never create a hash index — and that is a defensible choice.
Interview framing. Knowing when hash wins (wide key, equality-only, size-sensitive) and why it usually loses (no range/sort, single-column, marginal size win on narrow keys) is the senior signal — not reflexively creating them.

Worked example — hash vs B-tree for equality on a wide key

Detailed explanation. The clearest case for a hash index is exact-match lookup on a wide text key — a session token, an API key, a long external identifier — where you never sort and never range. Compare a B-tree and a hash index on such a column.

Table. sessions(id, token TEXT, user_id, expires_at) — 50M rows; token is a 43-char base64 string.
Query. SELECT user_id FROM sessions WHERE token = ? — pure equality, extremely hot.
Compare. B-tree on token vs hash on token.

Question. Build both indexes, compare their size and lookup path, and decide which fits the workload.

Input.

Aspect	B-tree on `token`	Hash on `token`
What the leaf stores	full 43-char key + TID	32-bit hash + TID
Lookup	O(log N) descent	O(1) bucket jump
Range / sort	yes	no
Relative size on wide key	larger	smaller

Code.

-- B-tree: flexible, but stores the full 43-char token in every entry
CREATE INDEX idx_sessions_token_btree ON sessions (token);

-- Hash: stores only a 32-bit hash; equality-only
CREATE INDEX idx_sessions_token_hash ON sessions USING hash (token);

-- The hot lookup — pure equality
EXPLAIN (ANALYZE, BUFFERS)
SELECT user_id FROM sessions WHERE token = 'x7Qf...base64...9kA';

-- Compare on-disk sizes
SELECT indexrelid::regclass AS index,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM   pg_index
WHERE  indrelid = 'sessions'::regclass;

Step-by-step explanation.

The B-tree stores the full 43-character token in every leaf entry and in the internal separator keys, so on 50M rows it carries ~50M copies of a long string plus tree overhead — a large index.
The hash index stores only a 32-bit hash code plus the TID per entry. The key width is constant regardless of how long the token is, so on a wide key it is materially smaller on disk.
The lookup: the B-tree descends 3–4 levels doing string comparisons at each; the hash index hashes the token once and jumps to the bucket, comparing 32-bit hash codes. Both are fast; the hash avoids repeated full-string comparisons.
The decision hinges on the workload: sessions is looked up only by exact token, never sorted, never ranged. That is exactly the hash sweet spot — so the hash index is defensible here.
If the product later needs "list a user's sessions ordered by expires_at," that is a different index ((user_id, expires_at) B-tree); it does not change the token-lookup decision. Each query gets the index its shape demands.

Output.

Index	Size (50M rows)	Lookup	Verdict
B-tree on `token`	larger (full keys)	O(log N), string compares	works, bigger
Hash on `token`	smaller (32-bit)	O(1), hash compares	best for equality-only

Rule of thumb. A hash index earns its place only on a wide, equality-only, never-sorted key where its constant-width entries beat the B-tree's full-key storage. On narrow keys or any column you might range/sort, use a B-tree.

Worked example — why a hash index cannot serve a range or ORDER BY

Detailed explanation. The defining limitation of a hash index is that hashing destroys order. This is not a Postgres quirk — it is inherent to hashing. Demonstrate why a range query and a sort both fall back to a sequential scan even with a hash index present.

Index. CREATE INDEX ... USING hash (created_at) — a deliberately wrong choice.
Range query. WHERE created_at > '2026-01-01' — needs ordered access.
Sort. ORDER BY created_at — needs ordered access.

Question. Show that a hash index on created_at is useless for a range or a sort, and name the correct index.

Input.

Query	Can hash index help?	Why
`created_at = '2026-01-01'`	yes	exact bucket
`created_at > '2026-01-01'`	no	no order in bucket space
`ORDER BY created_at`	no	no order to read

Code.

-- A hash index on a column you range/sort on — the wrong tool
CREATE INDEX idx_events_created_hash ON events USING hash (created_at);

-- Range: the hash index CANNOT help; planner uses Seq Scan
EXPLAIN ANALYZE
SELECT * FROM events WHERE created_at > '2026-01-01';   -- Seq Scan

-- Sort: same story
EXPLAIN ANALYZE
SELECT * FROM events ORDER BY created_at LIMIT 100;      -- Seq Scan + Sort

-- The correct index for both
CREATE INDEX idx_events_created_btree ON events (created_at);

Step-by-step explanation.

A hash function maps '2026-01-01' and '2026-01-02' to unrelated, scattered bucket numbers. There is no bucket ordering that corresponds to date ordering, so "all dates greater than X" cannot be expressed as a contiguous set of buckets.
For created_at > '2026-01-01', the planner sees that the only available index (hash) supports = and nothing else. It cannot use it for >, so it falls back to a sequential scan — the hash index is dead weight.
For ORDER BY created_at, the hash index offers no readable order, so the planner reads the heap and adds an explicit Sort node. Again the hash index is unused.
A B-tree on created_at fixes both: its ordered leaves make > a contiguous leaf walk and make ORDER BY a sort-free leaf read. This is why B-tree is the default and hash is a specialist.
The lesson: choose the access method from the query shapes, not from "this column is looked up a lot." A frequently-queried column that is ranged or sorted needs a B-tree, full stop.

Output.

Query	With hash index	With B-tree index
`created_at = X`	O(1) hit	O(log N) hit
`created_at > X`	Seq Scan	Index range scan
`ORDER BY created_at`	Seq Scan + Sort	sort-free leaf read

Rule of thumb. If a column is ever ranged, sorted, or prefix-matched, a hash index is the wrong choice — hashing destroys the order those operations need. Hash is for equality and nothing else.

SQL Interview Question on choosing hash vs B-tree

A senior interviewer might ask: "You have an api_keys table with 80 million rows; the only query is SELECT account_id FROM api_keys WHERE key_hash = ? where key_hash is a 64-character hex string. You are memory-constrained. Would you use a hash or a B-tree index? Defend the choice, and state what would change your answer."

Solution Using a hash index justified by the equality-only, wide-key workload

-- The workload: pure equality on a wide (64-char) key, never sorted, never ranged.
-- Hash index stores only a 32-bit hash per entry — smaller than a full-key B-tree.
CREATE INDEX idx_api_keys_hash ON api_keys USING hash (key_hash);

EXPLAIN (ANALYZE, BUFFERS)
SELECT account_id FROM api_keys WHERE key_hash = '9f86d081...64hex...b0f00a08';
-- Plan: Index Scan using idx_api_keys_hash (O(1) bucket lookup)

-- Compare sizes to justify the choice
SELECT 'btree' AS kind, pg_size_pretty(pg_relation_size(
         'idx_api_keys_hash'))  -- (build a btree separately to compare)
;

Step-by-step trace.

Trace input — api_keys sample:

key_hash (64 hex)	account_id
9f86d081...a08	1001
2c26b46b...c1d	1002
486ea462...f77	1003

The lookup value '9f86d081...a08' is hashed once to a 32-bit code; the high bits select the bucket.
Postgres reads that one bucket page and compares 32-bit hash codes to find candidate entries — no 64-character string comparisons at each tree level.
The matching entry's TID points at the heap row; Postgres fetches it and returns account_id = 1001.
Because the workload is equality-only on a wide key, the hash index's constant 32-bit entries make it smaller than a B-tree that would store all 64 characters per entry — decisive under a memory constraint.

Final result — account_id = 1001 via an O(1) bucket lookup from the smallest index that serves the workload.

Output:

key_hash queried	account_id	access path
9f86d081...a08	1001	hash bucket, O(1)

Why this works — concept by concept:

Equality-only workload — the sole query is key_hash = ?; there is no range, sort, or prefix, so the B-tree's extra capabilities are pure waste here and the hash index loses nothing by lacking them.
Wide-key size win — a hash entry is a 32-bit code regardless of key width; on a 64-char key that is far smaller than a B-tree storing the full string in every leaf and separator, which matters under memory pressure.
O(1) bucket lookup — the value is hashed once and lands in a bucket, avoiding the repeated full-string comparisons a B-tree descent performs at each level.
What would change the answer — if the column ever needed uniqueness enforcement, a range, a sort, a prefix match, or a multicolumn combination, the answer flips to B-tree, because hash cannot do any of those.
Cost — one hash index, maintained on writes, crash-safe since PG10. Lookup is O(1) average (degrading toward O(chain length) under severe key skew). The trade is zero flexibility for minimum size on an equality-only wide key.

SQL
Topic — indexing
Index-type selection problems

Practice →

SQL Topic — optimization Query optimization and sizing problems

Practice →

4. GIN & BRIN — inverted and block-range indexes

`gin` indexes what is inside a value; `brin` summarises ranges of blocks — two specialists that beat B-trees on document data and on huge ordered tables

The mental model in one line: a gin index (Generalized Inverted Index) breaks each composite value — an array, a jsonb document, a full-text tsvector — into its component elements and maps each element to the list of rows that contain it, so a containment or membership query jumps straight to the matching rows instead of scanning every document; while a brin index (Block Range INdex) stores only a tiny min/max summary for each range of physical heap blocks, so a range query on a column whose values increase with physical row order can skip entire block ranges after reading a summary that fits in kilobytes. GIN is how you index jsonb, arrays, and full-text search; BRIN is how you index a billion-row time-series without spending gigabytes on the index.

GIN — the inverted index.

What it stores. For every distinct element (array member, jsonb key/value, lexeme), GIN keeps a sorted posting list of the TIDs of rows containing that element. This is the same structure a search engine uses.
The query it accelerates. "Which rows contain element X?" — tags @> '{urgent}', doc @> '{"status":"paid"}', body_tsv @@ to_tsquery('fox & socks'). It turns a full-document scan into a posting-list lookup.
Operators. Arrays/jsonb: @> (contains), <@ (contained by), ? (has key), ?| (any key), ?& (all keys). Full-text: @@. The operator must match the index's operator class.
Operator classes. jsonb_ops (default) indexes both keys and values, larger, supports more operators; jsonb_path_ops indexes only key-paths+values, smaller and faster for the common @> containment query but supports fewer operators.
The write trade-off. A single row can add many index entries (one per element), so GIN writes are heavier than B-tree. fastupdate buffers new entries in an unordered pending list merged later, trading read latency for write throughput.

BRIN — the block-range index.

What it stores. For each range of heap blocks (default 128 pages, pages_per_range), BRIN records a summary — for numeric/timestamp columns, the min and max value in that range. That is all.
The query it accelerates. A range predicate on a column correlated with physical order: WHERE created_at BETWEEN a AND b. BRIN reads the per-range summaries, skips ranges whose min/max cannot match, and scans only the surviving ranges' blocks.
The correlation requirement. BRIN only works if the column's values track the physical row order. Append-only time-series (rows inserted in timestamp order) are ideal. On a randomly-ordered column, every range's min/max spans the whole domain and BRIN prunes nothing.
The size. A BRIN index is orders of magnitude smaller than a B-tree — kilobytes to a few MB where a B-tree would be gigabytes — because it stores one summary per 128-page range, not one entry per row.
Lossy by design. BRIN gives candidate blocks, not exact rows; Postgres rechecks the predicate on the surviving blocks. It trades precision for a microscopic footprint.

Choosing between them and against B-tree.

Use GIN when. The predicate looks inside a multi-valued column — array containment, jsonb filtering on arbitrary keys, full-text search. A B-tree cannot index members of a value.
Use BRIN when. The table is huge, append-only or naturally ordered, and queried by range on the ordered column, and you want a tiny index. A B-tree would work but cost gigabytes.
Use B-tree when. The column is scalar and you need exact lookups, sorting, or the correlation for BRIN does not hold. B-tree is precise; BRIN is approximate; GIN is for composite values.
The interview tell. Reaching for GIN on jsonb/arrays/full-text and BRIN on ordered giants — instead of a default B-tree — shows you match the access method to the data shape.

Worked example — GIN on a jsonb column with containment queries

Detailed explanation. The most common GIN use case in modern schemas is a jsonb column that users filter on arbitrary keys. A B-tree on the whole column can only match the entire document; GIN indexes the keys and values so containment (@>) queries fly. Walk through indexing an event-properties column.

Table. events(id, props jsonb, created_at) — props holds {"type":"purchase","plan":"pro","region":"eu"}-shaped documents.
Query. WHERE props @> '{"plan":"pro"}' — find events whose props contain that key/value.
Index. GIN with jsonb_path_ops for the containment workload.

Question. Build a GIN index that accelerates @> containment on props and explain the operator-class choice.

Input.

Component	Value
Column	`props jsonb`
Query operator	`@>` (containment)
Operator class	`jsonb_path_ops` (smaller, faster for `@>`)
Alternative	`jsonb_ops` (default; more operators, larger)

Code.

-- Default GIN — indexes keys AND values, supports @>, ?, ?|, ?&
CREATE INDEX idx_events_props_gin ON events USING gin (props);

-- Optimised for containment — smaller and faster for @>, but no key-exists (?) ops
CREATE INDEX idx_events_props_pathops
    ON events USING gin (props jsonb_path_ops);

-- Containment query — jumps to matching rows via posting lists
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, created_at
FROM   events
WHERE  props @> '{"plan":"pro"}';
-- Plan: Bitmap Index Scan on idx_events_props_pathops → Bitmap Heap Scan

Step-by-step explanation.

Without a GIN index, props @> '{"plan":"pro"}' forces a sequential scan that parses every jsonb document and tests containment — O(N) document parses.
The GIN index breaks each document into indexable items. With jsonb_path_ops, it stores a hash of each key-path plus value, so {"plan":"pro"} maps to a posting list of exactly the rows that contain that pair.
The containment query hashes {"plan":"pro"}, looks up its posting list, and gets the matching TIDs directly — then a bitmap heap scan reads those rows. No document parsing across the whole table.
jsonb_path_ops is smaller and faster than the default jsonb_ops for @> because it indexes only paths+values, not every key and value independently. The trade is that it does not support key-existence operators (?, ?|, ?&). Choose jsonb_path_ops for pure containment; jsonb_ops if you also need ?.
GIN writes are heavier than B-tree because one document contributes many index entries; on write-heavy tables, fastupdate = on buffers entries in a pending list to keep inserts fast, merged into the main index by VACUUM or when the list fills.

Output.

Approach	Access path	Cost per query
no index	Seq Scan + parse every doc	O(N)
`jsonb_ops` GIN	Bitmap scan; more operators	fast, larger index
`jsonb_path_ops` GIN	Bitmap scan; `@>` only	fastest for containment

Rule of thumb. Index jsonb/array columns with GIN, and pick jsonb_path_ops when your queries are pure @> containment — it is smaller and faster than the default. Reserve jsonb_ops for when you also need key-existence operators.

Worked example — GIN for full-text search on a tsvector

Detailed explanation. Full-text search is the other flagship GIN use case. A tsvector column holds the normalised lexemes of a document; a GIN index over it maps each lexeme to the rows containing it, turning @@ match queries into posting-list lookups. Walk through indexing an articles table for search.

Table. articles(id, title, body, body_tsv tsvector).
Query. WHERE body_tsv @@ to_tsquery('english', 'index & performance').
Index. GIN on the tsvector column.

Question. Build a full-text GIN index and a query that ranks matching articles, and explain how the lexeme posting lists serve it.

Input.

Component	Value
Search column	`body_tsv tsvector` (generated from `body`)
Query	`@@ to_tsquery('index & performance')`
Index	GIN on `body_tsv`
Ranking	`ts_rank(body_tsv, query)`

Code.

-- Maintain a tsvector generated column (Postgres 12+)
ALTER TABLE articles
    ADD COLUMN body_tsv tsvector
    GENERATED ALWAYS AS (to_tsvector('english', coalesce(body, ''))) STORED;

-- GIN index over the lexemes
CREATE INDEX idx_articles_body_tsv ON articles USING gin (body_tsv);

-- Full-text query with ranking
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, title, ts_rank(body_tsv, q) AS rank
FROM   articles, to_tsquery('english', 'index & performance') AS q
WHERE  body_tsv @@ q
ORDER  BY rank DESC
LIMIT  10;
-- Plan: Bitmap Index Scan on idx_articles_body_tsv → Bitmap Heap Scan

Step-by-step explanation.

to_tsvector('english', body) normalises the article body into lexemes with positions — 'index':4 'perform':7 ... — stemming words and dropping stop-words. Storing it as a GENERATED ... STORED column keeps it in sync automatically.
The GIN index maps each lexeme ('index', 'perform') to a posting list of the article rows containing it. The dictionary of lexemes is sorted, so a lexeme lookup is fast.
body_tsv @@ to_tsquery('index & performance') looks up the posting lists for 'index' and 'perform', intersects them (the & requires both), and returns the matching TIDs — no full-body scan.
ts_rank scores each surviving row by lexeme frequency/position; the ORDER BY rank DESC LIMIT 10 returns the ten best matches. Ranking happens on the small matched set, not the whole table.
GIN is preferred over GiST for static-ish text corpora because GIN lookups are faster (GiST is lossy and rechecks more); GiST is only preferable when the column is updated extremely frequently and index build/update speed dominates.

Output.

id	title	rank
512	"Index performance deep dive"	0.19
88	"Tuning index performance"	0.14
301	"When indexes hurt performance"	0.11

Rule of thumb. For full-text search, store a tsvector generated column and put a GIN index on it; GIN's lexeme posting lists make @@ match plus ts_rank ordering a bitmap scan over the matched set instead of a full-corpus scan.

Worked example — BRIN on an append-only time-series table

Detailed explanation. BRIN's flagship case is a massive, append-only table whose timestamp increases with insertion order. Here a BRIN index a few KB in size prunes almost all blocks for a time-range query, where a B-tree would cost gigabytes. Walk through indexing a metrics table.

Table. metrics(ts timestamptz, device_id, value) — 2 billion rows, appended in ts order.
Query. WHERE ts BETWEEN '2026-08-01' AND '2026-08-02' — one day out of years.
Index. BRIN on ts.

Question. Build a BRIN index on the time-series and explain how block-range pruning serves the range query, plus what breaks the correlation.

Input.

Component	Value
Table	`metrics`, 2B rows, append-only by `ts`
Index	BRIN on `ts`
`pages_per_range`	128 (default) — tune smaller for tighter pruning
Query	one-day range out of multiple years

Code.

-- BRIN on the naturally-ordered timestamp — tiny index
CREATE INDEX idx_metrics_ts_brin
    ON metrics USING brin (ts) WITH (pages_per_range = 128);

-- Range query — BRIN prunes block ranges by min/max summary
EXPLAIN (ANALYZE, BUFFERS)
SELECT device_id, value
FROM   metrics
WHERE  ts BETWEEN '2026-08-01' AND '2026-08-02';
-- Plan: Bitmap Index Scan on idx_metrics_ts_brin → Bitmap Heap Scan
--       (only the block ranges overlapping the day are scanned)

-- Compare footprint against a hypothetical B-tree
SELECT pg_size_pretty(pg_relation_size('idx_metrics_ts_brin')) AS brin_size;
-- e.g. a few MB, vs tens of GB for a B-tree on 2B rows

-- Re-summarise after heavy appends so new ranges are covered
SELECT brin_summarize_new_values('idx_metrics_ts_brin');

Step-by-step explanation.

Because rows are appended in ts order, each 128-page block range holds a contiguous, non-overlapping slice of time. BRIN records just the min and max ts for each range — a handful of bytes per range.
For the one-day query, BRIN reads the per-range summaries (tiny, cached), and for each range asks "could [min, max] overlap the requested day?" All ranges outside the day are skipped without reading a single heap block.
Only the block ranges overlapping the day survive; Postgres bitmap-heap-scans those blocks and rechecks the exact ts predicate (BRIN is lossy — it yields candidate blocks, not exact rows).
The index is a few MB versus tens of GB for a B-tree on 2B rows, and it is far cheaper to maintain on append. That size-and-write win is the entire reason to choose BRIN.
The correlation is fragile: if rows are updated out of order, back-dated, or the table is not clustered by ts, block ranges start overlapping in time, min/max spans widen, and pruning collapses. Keep the load append-only (or CLUSTER/repack periodically), and run brin_summarize_new_values so freshly appended ranges get summarised promptly.

Output.

Metric	B-tree on `ts`	BRIN on `ts`
Index size (2B rows)	tens of GB	a few MB
One-day range scan	precise, larger index	prune ranges, recheck
Write cost on append	per-row entry	per-range summary
Needs correlation?	no	yes (fragile)

Rule of thumb. On a huge, append-only, naturally-ordered table, BRIN gives you range-scan pruning for a tiny fraction of a B-tree's size and write cost — but only while the physical/value correlation holds. Lose the correlation and BRIN prunes nothing.

SQL Interview Question on indexing jsonb and time-series together

A senior interviewer might ask: "You own a 3-billion-row events(ts timestamptz, props jsonb) table, appended in timestamp order. Two query families dominate: time-range scans (ts BETWEEN a AND b) and property filters (props @> '{...}'), often combined. Design the indexing strategy, justify BRIN vs B-tree for ts and GIN for props, and explain how the planner combines them."

Solution Using a BRIN on the timestamp plus a GIN on the jsonb, combined via bitmap AND

-- BRIN on the append-ordered timestamp — kilobytes, prunes block ranges
CREATE INDEX idx_events_ts_brin
    ON events USING brin (ts) WITH (pages_per_range = 64);

-- GIN on the jsonb for containment filters — path_ops for pure @>
CREATE INDEX idx_events_props_gin
    ON events USING gin (props jsonb_path_ops);

-- Combined query — planner can bitmap-AND the two indexes
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, ts
FROM   events
WHERE  ts BETWEEN '2026-08-01' AND '2026-08-02'
  AND  props @> '{"type":"purchase"}';
-- Plan: BitmapAnd
--         → Bitmap Index Scan on idx_events_ts_brin
--         → Bitmap Index Scan on idx_events_props_gin
--       → Bitmap Heap Scan (recheck both predicates)

Step-by-step trace.

Trace input — events sample (of 3B rows):

id	ts	props
1	2026-08-01 09:00	{"type":"purchase"}
2	2026-08-01 09:05	{"type":"view"}
3	2026-08-15 10:00	{"type":"purchase"}
4	2026-08-02 23:59	{"type":"purchase"}

The BRIN scan reads block-range summaries and keeps only ranges whose [min ts, max ts] overlaps Aug 1–2 — pruning the vast majority of the 3B rows down to a couple of days of blocks (candidate rows 1, 2, 4; row 3 is in an August-15 range that is pruned).
The GIN scan looks up the posting list for {"type":"purchase"}, yielding candidate TIDs for rows 1, 3, 4.
BitmapAnd intersects the two bitmaps: rows in the time window (1, 2, 4) AND rows matching the property (1, 3, 4) → rows 1 and 4.
The bitmap heap scan reads only those blocks and rechecks both predicates exactly (BRIN is lossy), confirming rows 1 and 4.

Final result — purchases in the Aug 1–2 window: rows 1 and 4, found without scanning the other ~3B rows.

Output:

id	ts	matched predicates
1	2026-08-01 09:00	time window + purchase
4	2026-08-02 23:59	time window + purchase

Why this works — concept by concept:

BRIN on the ordered timestamp — because events is appended in ts order, block-range min/max summaries prune whole ranges for a time window, at a few KB of index instead of a many-GB B-tree.
GIN with jsonb_path_ops — the inverted index maps {"type":"purchase"} to a posting list, turning a full-document containment scan into a direct TID lookup.
BitmapAnd combines them — each index produces a TID bitmap; Postgres intersects the bitmaps so only rows satisfying both the time and property predicates reach the heap.
Lossy recheck on the heap — BRIN yields candidate blocks and GIN yields candidate TIDs, so the bitmap heap scan rechecks both predicates exactly before returning rows.
Cost — a tiny BRIN plus a GIN whose writes are heavier than B-tree (many entries per document). Query cost is (block-range prune) ∩ (posting-list lookup), vastly cheaper than an O(3B) scan. The trade is GIN write amplification and BRIN's dependence on the append-order correlation.

SQL
Topic — indexing
GIN, BRIN, and jsonb indexing problems

Practice →

SQL Topic — data-processing Data-processing and time-series scan problems

Practice →

5. Bloom filters & the index-selection decision matrix

`bloom` builds a probabilistic per-row signature across many columns — one compact index for arbitrary equality combinations, with a mandatory recheck

The mental model in one line: a bloom filter index (the bloom extension) computes, for each row, a compact bit signature by running several columns through k hash functions into an m-bit array, so a query filtering any subset of those columns tests its own signature against each row's signature and gets a "definitely not present" (skip the row) or "maybe present" (recheck the heap) answer — which means one small bloom index can replace a fistful of separate B-trees for ad-hoc, many-column equality queries, at the cost of false positives that force a heap recheck and the hard limit that it serves equality only. It is the specialist for the "users can filter by any combination of these ten columns, all equality" problem that would otherwise demand an unmaintainable pile of composite B-trees.

The bloom filter, from first principles.

The bit array. A bloom filter is an m-bit array, all zero to start. To add an element, run it through k independent hash functions, each yielding a position in [0, m), and set those k bits to 1.
The membership test. To test an element, hash it the same k ways and check those k bits. If any is 0, the element is definitely not present. If all are 1, it is maybe present — it could be a false positive from other elements' bits.
No false negatives, tunable false positives. A bloom filter never says "absent" for something present. The false-positive rate rises with more elements and falls with a larger m and well-chosen k — the classic space-vs-accuracy dial.
Why it fits indexing. Each row's indexed columns become the "elements"; a query's equality values become the "test." "Definitely not" skips the row entirely; "maybe" sends it to a heap recheck. Many columns fold into one fixed-width signature.

The Postgres bloom index.

Enable and create. CREATE EXTENSION bloom; then CREATE INDEX ... USING bloom (c1, c2, ..., cN). Every listed column contributes to each row's signature.
The parameters. length (signature bits per row, default 80, max 4096) and per-column col1 ... colN (bits set per column, default 2). More length lowers false positives at the cost of index size; more per-column bits sharpen a column's discrimination.
What it serves. Equality (=) on any subset of the indexed columns — including subsets a composite B-tree's leftmost-prefix rule cannot serve. It does not serve ranges, sorts, prefixes, or IS NULL well.
Always a recheck. A bloom scan produces candidate rows ("maybe"), then Postgres rechecks the exact predicates on the heap to discard false positives. It is inherently a bitmap-heap-scan pattern.

When multi-column bloom beats N B-trees.

The combinatorics problem. If users filter arbitrary subsets of (a, b, c, d, e) by equality, no single composite B-tree serves them all (leftmost-prefix), and one B-tree per useful combination is a maintenance and write-cost nightmare.
The bloom answer. One bloom index over all five columns serves any equality subset with a single structure — smaller than the pile of B-trees and cheaper to maintain on writes.
The precision trade. Bloom returns false positives, so it reads more heap rows than a precise B-tree would for the same query; it wins when the alternative is a seq scan or an unmaintainable index sprawl, not when a single well-targeted B-tree would do.
The honest boundary. If one or two column combinations dominate, targeted composite B-trees beat bloom on precision. Bloom earns its place specifically when the combinations are unpredictable and many.

The index-selection decision matrix — all five types.

B-tree. Default. Equality, range, sort, prefix, MIN/MAX, unique constraints, index-only scans. Reach here first.
Hash. Equality-only on a wide key where size matters and you never sort. Narrow specialist.
GIN. Membership/containment inside composite values — arrays, jsonb, full-text. The document/array answer.
BRIN. Range scans on huge, physically-ordered tables where a tiny index is worth lossy pruning. The time-series answer.
Bloom. Ad-hoc equality across many columns in unpredictable combinations. The many-column answer.

Worked example — one bloom index for arbitrary many-column equality

Detailed explanation. The canonical bloom case: an analytics table users filter by any combination of several low-to-moderate-cardinality equality columns. One bloom index covers every combination. Walk through building it.

Table. assets(id, country, category, status, tier, source, owner_team) — users filter arbitrary subsets, all equality.
Alternative. A B-tree per combination — dozens of indexes, huge write cost.
Bloom. One USING bloom (country, category, status, tier, source, owner_team).

Question. Build a single bloom index that serves arbitrary equality subsets and show a three-column filter using it.

Input.

Component	Value
Columns	`country, category, status, tier, source, owner_team`
Query pattern	arbitrary equality subset
Index	one `USING bloom (...)`
Behaviour	candidate rows → heap recheck

Code.

CREATE EXTENSION IF NOT EXISTS bloom;

-- One bloom index over all six filter columns
CREATE INDEX idx_assets_bloom
    ON assets USING bloom (country, category, status, tier, source, owner_team)
    WITH (length = 128);      -- 128-bit signature per row → lower false-positive rate

-- An arbitrary 3-column equality subset — served by the ONE bloom index
EXPLAIN (ANALYZE, BUFFERS)
SELECT id
FROM   assets
WHERE  country = 'DE' AND status = 'active' AND tier = 'gold';
-- Plan: Bitmap Index Scan on idx_assets_bloom → Bitmap Heap Scan (Recheck Cond)

-- A DIFFERENT subset — same single index serves it too
EXPLAIN (ANALYZE, BUFFERS)
SELECT id
FROM   assets
WHERE  category = 'server' AND source = 'import';

Step-by-step explanation.

Each row's six column values are hashed into a 128-bit signature stored in the index — a fixed-width blob per row regardless of how the columns are queried.
The query country='DE' AND status='active' AND tier='gold' builds a test signature from those three values and scans the bloom index: for each row, if any required bit is unset, the row is "definitely not" a match and is skipped.
Rows whose signature has all the required bits set are "maybe" matches — candidates. Postgres bitmap-heap-scans them and rechecks the exact equality predicates to discard false positives (Recheck Cond in the plan).
The second query filters a different subset (category, source) and is served by the same index — the whole point. No leftmost-prefix constraint applies; any subset works.
Replacing this with B-trees would require one composite per queried combination (and even then the leftmost-prefix rule blocks many subsets). The single bloom index is smaller and far cheaper to maintain on writes.

Output.

Query subset	Index used	Heap rows read
`country, status, tier`	idx_assets_bloom	candidates + recheck
`category, source`	idx_assets_bloom	candidates + recheck
any other subset	idx_assets_bloom	candidates + recheck

Rule of thumb. When users filter arbitrary equality subsets of many columns, one bloom index beats a sprawl of composite B-trees — accept the false-positive recheck as the price of covering every combination with a single structure.

Worked example — tuning the false-positive rate

Detailed explanation. The bloom index's length and per-column bit parameters trade index size against the false-positive rate, which drives how many heap rows the recheck must read. Walk through tuning them for a workload.

Default. length = 80, per-column = 2 — small index, higher false-positive rate.
Sharper. length = 256, boost bits on the most-filtered columns — bigger index, fewer false positives.
The metric. Rows Removed by Recheck in EXPLAIN ANALYZE — the false positives you paid heap I/O for.

Question. Tune a bloom index to cut recheck waste on the hottest columns, and state the size trade-off.

Input.

Parameter	Effect
`length` (total signature bits)	↑ length → ↓ false positives, ↑ size
per-column `colN` (bits per column)	↑ bits on hot columns → sharper discrimination
`Rows Removed by Recheck`	the false-positive cost to minimise

Code.

-- Baseline: default parameters
CREATE INDEX idx_assets_bloom_default
    ON assets USING bloom (country, category, status, tier, source);

EXPLAIN (ANALYZE)
SELECT id FROM assets WHERE country = 'DE' AND status = 'active';
--   Bitmap Heap Scan ... Rows Removed by Recheck: 41000   ← many false positives

-- Tuned: larger signature + more bits on the two hottest columns
CREATE INDEX idx_assets_bloom_tuned
    ON assets USING bloom (country, category, status, tier, source)
    WITH (length = 256, col1 = 4, col3 = 4);   -- country & status sharper

EXPLAIN (ANALYZE)
SELECT id FROM assets WHERE country = 'DE' AND status = 'active';
--   Bitmap Heap Scan ... Rows Removed by Recheck: 900     ← far fewer

SELECT pg_size_pretty(pg_relation_size('idx_assets_bloom_tuned'));

Step-by-step explanation.

With defaults, the 80-bit signature packs six columns tightly, so many rows accidentally share the queried bits — the recheck removes 41,000 false-positive rows it had to read from the heap.
Raising length to 256 gives each column more room in the signature, so unrelated rows are far less likely to collide on all queried bits — fewer "maybe" candidates reach the heap.
col1 = 4, col3 = 4 assigns more signature bits to country (col1) and status (col3) — the columns most often filtered — sharpening their discrimination where it pays off most.
Rows Removed by Recheck drops from 41,000 to 900: the recheck now discards far fewer false positives, so the query reads far fewer heap pages.
The cost is a larger index (256 bits/row vs 80) and more memory to cache it. Tuning bloom is explicitly a size-vs-precision dial; measure Rows Removed by Recheck and stop when the recheck waste is acceptable for your heap-I/O budget.

Output.

Config	Signature bits	Rows removed by recheck	Index size
default	80	~41,000	smaller
tuned	256 (+bits on hot cols)	~900	larger

Rule of thumb. Tune a bloom index by watching Rows Removed by Recheck: raise length and add per-column bits to the most-filtered columns until the false-positive recheck fits your heap-I/O budget, accepting a larger index in return.

Worked example — walking the decision matrix on one schema

Detailed explanation. The payoff of learning all five index types is a repeatable decision for any column. Walk one realistic table end to end, assigning each column its access method from its query shape.

Table. orders(id, customer_id, status, total_cents, created_at, shipping jsonb, tags text[]).
Query shapes. PK lookups, customer+status dashboards, time-range reports, jsonb filters, tag containment, ad-hoc multi-column filters.
Goal. One access method per query family, no redundant indexes.

Question. Assign an index type to each query family on orders and justify each in one line.

Input.

Query family	Column(s) & shape	Chosen index
PK / unique lookup	`id =`	B-tree (implicit PK)
dashboard	`customer_id =`, `status =`, sort `created_at`	composite B-tree
time-range report (huge, ordered)	`created_at BETWEEN`	BRIN
shipping filter	`shipping @> '{...}'`	GIN (`jsonb_path_ops`)
tag containment	`tags @> '{...}'`	GIN
ad-hoc many-column `=`	any subset of low-card cols	bloom

Code.

-- PK: automatic unique B-tree
-- (created by PRIMARY KEY (id))

-- Dashboard: composite covering B-tree (equality prefix + sort + covered payload)
CREATE INDEX idx_orders_dash
    ON orders (customer_id, status, created_at DESC)
    INCLUDE (total_cents);

-- Time-range on the append-ordered timestamp: tiny BRIN
CREATE INDEX idx_orders_created_brin
    ON orders USING brin (created_at);

-- jsonb containment: GIN path_ops
CREATE INDEX idx_orders_shipping_gin
    ON orders USING gin (shipping jsonb_path_ops);

-- array containment: GIN
CREATE INDEX idx_orders_tags_gin
    ON orders USING gin (tags);

-- ad-hoc many-column equality: one bloom
CREATE EXTENSION IF NOT EXISTS bloom;
CREATE INDEX idx_orders_bloom
    ON orders USING bloom (customer_id, status)
    WITH (length = 128);

Step-by-step explanation.

The primary key gets a unique B-tree automatically — the only index that can enforce uniqueness and the right tool for exact PK lookups and joins.
The dashboard query is equality-on-customer_id+status then sort-by-created_at, returning total_cents — a textbook composite covering B-tree with the sort column last and the payload in INCLUDE.
The time-range report scans a huge, append-ordered table by created_at range — BRIN prunes block ranges for kilobytes, far cheaper than a B-tree on that column if you do not also need exact created_at lookups.
shipping @> '{...}' and tags @> '{...}' look inside composite values — only GIN indexes their members; jsonb_path_ops for the pure-containment jsonb case.
The ad-hoc many-column equality family — analysts slicing by unpredictable subsets — goes to one bloom index rather than a combinatorial explosion of composite B-trees, accepting the recheck.

Output.

Column / shape	Access method	Reason
`id =`	B-tree (PK)	exact + unique
`customer_id,status` + sort	composite B-tree	prefix + sort + cover
`created_at` range (huge)	BRIN	tiny, prunes ranges
`shipping` jsonb	GIN path_ops	index the members
`tags` array	GIN	containment
many-column `=`	bloom	any subset, one index

Rule of thumb. Do not standardise on one index type — assign each query family the access method its shape demands. B-tree for scalars and sorts, BRIN for ordered giants, GIN for inside-a-value, hash for wide equality-only keys, bloom for many-column ad-hoc equality.

SQL Interview Question on the multi-column ad-hoc filter problem

A senior interviewer might ask: "An internal analytics tool lets users filter a 300-million-row assets table by any combination of eight low-cardinality equality columns. The team has created 15 composite B-tree indexes trying to cover the combinations and writes have slowed to a crawl. Redesign the indexing, explain why a bloom index fits, and describe the query behaviour including its downside."

Solution Using a single bloom index to replace the composite B-tree sprawl

CREATE EXTENSION IF NOT EXISTS bloom;

-- Drop the 15 composite B-trees; replace with ONE bloom over the eight columns
CREATE INDEX idx_assets_bloom
    ON assets USING bloom (country, category, status, tier,
                           source, owner_team, region, lifecycle)
    WITH (length = 160, col1 = 4, col3 = 4);   -- extra bits on the two hottest cols

-- Any equality subset is served by the single index
EXPLAIN (ANALYZE, BUFFERS)
SELECT id
FROM   assets
WHERE  country = 'DE' AND status = 'active' AND lifecycle = 'prod';
-- Plan: Bitmap Index Scan on idx_assets_bloom
--       → Bitmap Heap Scan (Recheck Cond: all three equalities)

Step-by-step trace.

Trace input — assets sample (of 300M):

id	country	status	lifecycle	(other cols)
10	DE	active	prod	...
11	DE	active	staging	...
12	FR	active	prod	...
13	DE	retired	prod	...

Each row's eight column values are hashed into a 160-bit signature at index-build time; country and status get extra bits for sharper discrimination.
The query builds a test signature from country='DE', status='active', lifecycle='prod' and scans the bloom index. Row 12 (FR) and row 13 (retired) miss required bits → "definitely not" → skipped.
Rows 10 and 11 have all the queried bits set → "maybe" candidates. (Row 11 is a false-positive risk because its lifecycle differs but its bits may overlap.)
The bitmap heap scan rechecks the exact equalities on the candidates: row 10 matches all three; row 11 fails lifecycle='prod' and is removed by recheck.

Final result — row 10, found via one index that serves this and every other equality subset.

Output:

id	country	status	lifecycle
10	DE	active	prod

Why this works — concept by concept:

One bloom index for any subset — the eight-column signature lets any equality subset be tested without a leftmost-prefix constraint, collapsing 15 composite B-trees into one structure.
Definitely-not vs maybe — an unset required bit proves absence and skips the row; all-bits-set means "maybe," so only candidates reach the heap.
Mandatory recheck — bloom is probabilistic, so the bitmap heap scan rechecks the exact predicates to discard false positives (row 11) — the Recheck Cond step is not optional.
Tuned bits on hot columns — extra length and per-column bits on country/status cut the false-positive rate where those columns are filtered most, shrinking the recheck set.
Cost — one bloom index (~fixed bits/row) maintained cheaply on writes, versus 15 composite B-trees' write amplification. The downside is false positives: it reads more heap rows than a perfectly-targeted B-tree, so it wins on unpredictable many-column filters, not on the one or two combinations a single B-tree could nail.

SQL
Topic — indexing
Bloom and multi-column index problems

Practice →

SQL
Topic — joins
Join and multi-predicate filtering problems

Practice →

Cheat sheet — database index recipes

Which index when. B-tree is the default for scalars — equality, range, sort, prefix, MIN/MAX, unique constraints, index-only scans. Hash only for pure-equality lookups on wide keys where size matters and you never sort. GIN for membership/containment inside composite values (arrays, jsonb, full-text tsvector). BRIN for range scans on huge, physically-ordered, append-only tables where a tiny index is worth lossy pruning. Bloom for ad-hoc equality across many columns in unpredictable combinations. Pick from the query shape, not from habit.
Reading EXPLAIN. Seq Scan = whole heap (fine for non-selective predicates or small tables). Index Scan = descend + random heap fetches (selective predicates). Bitmap Index Scan + Bitmap Heap Scan = index builds a TID bitmap, heap read in page order (moderate selectivity, or combining indexes via BitmapAnd/BitmapOr). Index Only Scan with Heap Fetches: 0 = answered entirely from the index. Always compare estimated rows= against actual rows to catch stale stats.
Index-only scan requirements. Every selected column must be in the index as a key or INCLUDE column, and the heap pages must be all-visible in the visibility map (kept fresh by VACUUM). Confirm you got one by checking Heap Fetches: 0; nonzero fetches on a write-heavy table mean autovacuum is behind.
Selectivity thresholds. Below ~0.5–1% matching rows, an index scan usually wins; above a break-even (often single-digit percent, tuning-dependent), a seq scan wins. The break-even shifts with random_page_cost (lower it toward 1.1 on SSD), effective_cache_size, and row width. An index on a column you filter for half the table will not be used for that filter.
Composite index recipe. Order columns to match the leftmost prefix your WHERE/ORDER BY reads: equality columns first, the range or sort column last ((event_type, created_at), not the reverse). A composite serves only queries constraining a leftmost prefix; a skipped middle column breaks the prefix for everything after it. Declare created_at DESC in the index when the hot query sorts descending, to drop the sort node.
Covering index recipe. Put filter/sort columns in the key and return-only columns in INCLUDE — (customer_id, status, created_at DESC) INCLUDE (order_id, total_cents). This yields a sort-free, heap-free index-only scan for the hot dashboard query while keeping internal tree pages small.
Partial index recipe. When queries always target a small stable subset, index only it: CREATE INDEX ... (priority) WHERE status = 'queued'. It is a fraction of the size, is maintained only for the subset, and the query must repeat the partial predicate to use it.
GIN tradeoffs. GIN indexes the members of a value; use jsonb_path_ops for pure @> containment (smaller, faster) and jsonb_ops when you also need key-existence (?, ?|, ?&). GIN writes are heavy (many entries per row) — fastupdate = on buffers inserts in a pending list merged by VACUUM. For full-text, store a tsvector GENERATED ... STORED column and GIN-index it.
BRIN tradeoffs. BRIN is kilobytes where a B-tree is gigabytes, but only prunes when the column is physically correlated with row order (append-only time-series is ideal). Tune pages_per_range smaller for tighter pruning at slightly larger size; run brin_summarize_new_values() after heavy appends; CLUSTER/repack if the correlation degrades. BRIN is lossy — it yields candidate blocks and Postgres rechecks.
Bloom tradeoffs. One bloom index serves arbitrary equality subsets of many columns — no leftmost-prefix limit — replacing a sprawl of composite B-trees. It is equality-only (no range/sort/prefix) and always rechecks the heap for false positives. Tune length and per-column bits watching Rows Removed by Recheck; raise them on the hottest columns until recheck waste fits your I/O budget.
The write-cost reminder. Every index is a second copy maintained on every write to its columns. GIN and multiple composite B-trees are the heaviest; BRIN and bloom are the lightest per row. Drop indexes the planner never uses (pg_stat_user_indexes.idx_scan = 0) — they cost writes and disk for zero read benefit.
Diagnosing "ignored index." Run ANALYZE (stale stats), check for functions/casts wrapping the column (use an expression index to match), match literal types to column types, and remember leading-wildcard LIKE '%x' needs a trigram GIN, not a B-tree. The planner is almost always right about selectivity; fix your stats or your predicate shape.

Frequently asked questions

What is a database index in one sentence?

A database index is a separate, redundant data structure that maps column values to the physical locations of the rows containing them, letting the query planner find matching rows without scanning the whole table — at the cost of extra disk and slower writes, since every index must be updated on every INSERT, UPDATE, and DELETE. The critical decision is not whether to index but which access method to use: B-tree, hash, GIN, BRIN, or bloom, each of which accelerates a different query shape. Choosing the wrong type gives you all the write cost and none of the read benefit, because the planner will simply ignore an index that does not fit the query.

B-tree vs hash index — when do I pick each?

Default to a b-tree index for essentially everything: it serves equality, ranges (<, >, BETWEEN), sorting (ORDER BY), prefix matching (LIKE 'abc%'), MIN/MAX, and it backs unique constraints and index-only scans. Reach for a hash index only in a narrow case — pure equality (=) lookups on a wide key (a long token, a UUID or hash string) where you never sort or range and index size matters, because a hash index stores only a 32-bit hash per entry instead of the full key. On narrow keys a B-tree is just as small and infinitely more flexible, and hash indexes cannot enforce uniqueness, serve ranges, or support multiple columns. Since PostgreSQL 10 hash indexes are crash-safe and WAL-logged, so the old "never use them" advice no longer applies — but B-tree remains the right default.

What is a GIN index used for?

A gin index (Generalized Inverted Index) is for indexing the contents of composite values rather than the value as a whole. It maps each element inside a value — an array member, a jsonb key or value, a full-text lexeme — to the list of rows containing it, so containment and membership queries (tags @> '{urgent}', props @> '{"plan":"pro"}', body_tsv @@ to_tsquery('fox')) jump straight to matching rows. Use jsonb_path_ops for pure @> containment (smaller and faster) and the default jsonb_ops when you also need key-existence operators like ?. GIN is the standard choice for jsonb filtering, array containment, and full-text search; its trade-off is heavier write cost because one row contributes many index entries.

When should I use a BRIN index?

Use a brin index on a very large table when the indexed column's values are physically correlated with row order — the classic case being an append-only time-series where created_at (or an auto-incrementing id) increases with insertion order. BRIN stores only a min/max summary per range of heap blocks, so it is orders of magnitude smaller than a B-tree (kilobytes vs gigabytes on billions of rows) and far cheaper to maintain on append. A range query reads the tiny summaries, skips block ranges whose min/max cannot match, and scans only the survivors. The catch is the correlation requirement: if rows are updated out of order or back-dated, block ranges overlap in value and BRIN prunes nothing — so keep the load append-only or CLUSTER/repack periodically, and re-summarise new ranges after heavy appends.

What is a bloom filter index?

A bloom filter index (the bloom extension) stores a compact probabilistic bit-signature per row, computed by hashing several columns into a fixed-width bit array, so a query filtering any subset of those columns can quickly rule out non-matching rows ("definitely not present") and send only candidates to a heap recheck ("maybe present"). Its superpower is serving arbitrary equality combinations across many columns from a single small index — replacing the combinatorial sprawl of composite B-trees you would otherwise need when users filter unpredictable subsets of, say, eight low-cardinality columns. The costs are that it is equality-only (no ranges, sorts, or prefixes) and it always rechecks the heap to discard false positives, so you tune length and per-column bits against Rows Removed by Recheck. Bloom wins when the filter combinations are many and unpredictable, not when one or two combinations a single B-tree could target dominate.

Why does Postgres ignore my index?

The most common reasons, all diagnosable from EXPLAIN (ANALYZE): the predicate is not selective enough (matching a large fraction of the table makes a sequential scan genuinely cheaper — this is correct behaviour); statistics are stale, so run ANALYZE and compare the estimated rows= against the actual count; a function or cast wraps the column (WHERE lower(email) = ... cannot use a plain index on email — build an expression index on lower(email) instead); the literal type does not match the column type, forcing an implicit cast that hides the indexed value; or the query uses a leading-wildcard LIKE '%term', which a B-tree cannot serve (use a pg_trgm trigram GIN index). Fix the stats or the predicate shape first — the planner is almost always right about selectivity.

Practice on PipeCode

Drill the indexing practice library → for the B-tree, hash, GIN, BRIN, bloom, composite, covering, and partial-index problems senior interviewers love.
Warm up on the database practice library → for the query-cost, EXPLAIN-plan, and access-method problems that anchor every indexing decision.
Sharpen query-writing on the SQL practice library → for the range, sort, and containment queries that decide which index type wins.
Push into optimization and data-processing drills, and stack the prerequisites against PipeCode's broader 450+ data-engineering catalogue to anchor the five-type decision matrix against real graded inputs.

Lock in index-selection muscle memory

Docs explain what each index type is. PipeCode drills explain the decision — when a B-tree beats a hash, when GIN turns a jsonb scan into a lookup, when BRIN saves gigabytes on a time-series, when a bloom index replaces a wall of composite B-trees, and why the planner keeps ignoring the index you just added. Pipecode.ai is Leetcode for Data Engineering — pattern-first practice tuned for the production trade-offs data engineers actually face.

Practice indexing problems →
Practice database problems →

1. Why the index type decides query cost

An index is a derived, ordered copy of your data — and the access method decides which queries it can accelerate

Worked example — reading EXPLAIN: seq scan vs index scan vs bitmap

Worked example — why the planner ignores your index

Worked example — the access-method decision matrix

SQL Interview Question on index selection and EXPLAIN

Solution Using EXPLAIN ANALYZE and a selective composite index

2. B-Tree indexes — the general-purpose default

btree is the balanced sorted tree that serves equality, range, prefix, sort, and index-only scans — the one index that does almost everything

Worked example — the leftmost-prefix rule on a composite index

Worked example — covering index and the index-only scan

Worked example — partial index for a hot subset

SQL Interview Question on B-tree composite index design

Solution Using a composite covering index with a matching sort order

3. Hash indexes — equality-only, O(1) lookups

hash stores a 32-bit hash of each key in buckets — a pure equality index with O(1) average lookup and none of the B-tree's extras

Worked example — hash vs B-tree for equality on a wide key

Worked example — why a hash index cannot serve a range or ORDER BY

SQL Interview Question on choosing hash vs B-tree

Solution Using a hash index justified by the equality-only, wide-key workload

4. GIN & BRIN — inverted and block-range indexes

gin indexes what is inside a value; brin summarises ranges of blocks — two specialists that beat B-trees on document data and on huge ordered tables

Worked example — GIN on a jsonb column with containment queries

Worked example — GIN for full-text search on a tsvector

Worked example — BRIN on an append-only time-series table

SQL Interview Question on indexing jsonb and time-series together

Solution Using a BRIN on the timestamp plus a GIN on the jsonb, combined via bitmap AND

5. Bloom filters & the index-selection decision matrix

bloom builds a probabilistic per-row signature across many columns — one compact index for arbitrary equality combinations, with a mandatory recheck

Worked example — one bloom index for arbitrary many-column equality

Worked example — tuning the false-positive rate

Worked example — walking the decision matrix on one schema

SQL Interview Question on the multi-column ad-hoc filter problem

Solution Using a single bloom index to replace the composite B-tree sprawl

Cheat sheet — database index recipes

Frequently asked questions

What is a database index in one sentence?

B-tree vs hash index — when do I pick each?

What is a GIN index used for?

When should I use a BRIN index?

What is a bloom filter index?

Why does Postgres ignore my index?

Practice on PipeCode

Lock in index-selection muscle memory

`btree` is the balanced sorted tree that serves equality, range, prefix, sort, and index-only scans — the one index that does almost everything

`hash` stores a 32-bit hash of each key in buckets — a pure equality index with O(1) average lookup and none of the B-tree's extras

`gin` indexes what is inside a value; `brin` summarises ranges of blocks — two specialists that beat B-trees on document data and on huge ordered tables

`bloom` builds a probabilistic per-row signature across many columns — one compact index for arbitrary equality combinations, with a mandatory recheck