Indexes: B-tree, multicolumn, partial, expression and GIN

A B-tree index keeps a column's values (or a tuple of columns) sorted, each pointing at a row's location in the table (the heap). Finding a value is a seek: a few page reads down the tree, then along the sorted leaf pages for as long as values match. A sequential scan reads every page of the table instead. Neither is always better: the planner estimates how many rows match and picks the cheaper plan.

Three ways to read a table

• Index Scan — walk the index and fetch each matching row from the heap in index order. Good for few rows, and for ORDER BY ... LIMIT because rows arrive sorted.
• Bitmap Index Scan + Bitmap Heap Scan — collect all matching row locations first, then read the heap pages in physical order, each once. Good for a moderate number of rows, or for combining two indexes.
• Seq Scan — read everything. Wins when a large share of rows match.

The examples use a helper, plan_of(query), defined in their setup: it runs EXPLAIN (COSTS OFF) with parallel workers disabled (so plans stay short) and joins the plan lines with |. The table has 200,000 orders and three indexes: (customer_id, created_at), a partial index on created_at for open orders only, and one on lower(email).

1CREATE FUNCTION plan_of(q text) RETURNS text LANGUAGE plpgsql2  SET max_parallel_workers_per_gather = 0 AS $$3DECLARE4  line text;5  result text := '';6BEGIN7  FOR line IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP8    result := result || CASE WHEN result = '' THEN '' ELSE ' | ' END || trim(line);9  END LOOP;10  RETURN result;11END $$;12CREATE TABLE orders (13  id int PRIMARY KEY, customer_id int NOT NULL, status text NOT NULL,14  created_at timestamp NOT NULL, email text NOT NULL15);16INSERT INTO orders17SELECT g, g % 5000,18       CASE WHEN g % 50 = 0 THEN 'open' ELSE 'done' END,19       timestamp '2024-01-01' + g * interval '1 minute',20       'User' || (g % 5000) || '@Example.com'21FROM generate_series(1, 200000) AS g;22CREATE INDEX orders_customer_created ON orders (customer_id, created_at);23CREATE INDEX orders_open_created ON orders (created_at) WHERE status = 'open';24CREATE INDEX orders_email_lower ON orders (lower(email));25ANALYZE orders;

1SELECT label, plan_of(q) AS plan2FROM (VALUES3  (1, 'both columns',4      $$SELECT * FROM orders WHERE customer_id = 42 AND created_at >= '2024-03-01'$$),5  (2, 'leading column + ORDER BY',6      $$SELECT * FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 3$$),7  (3, 'second column only',8      $$SELECT * FROM orders WHERE created_at >= '2024-03-01' AND created_at < '2024-03-01 02:00'$$),9  (4, 'most rows match',10      $$SELECT * FROM orders WHERE status = 'done'$$),11  (5, 'partial: open',12      $$SELECT id FROM orders WHERE status = 'open' AND created_at >= '2024-04-01' ORDER BY created_at LIMIT 10$$),13  (6, 'partial: done',14      $$SELECT id FROM orders WHERE status = 'done' AND created_at >= '2024-04-01' ORDER BY created_at LIMIT 10$$),15  (7, 'expression',16      $$SELECT id FROM orders WHERE lower(email) = 'user42@example.com'$$),17  (8, 'raw column',18      $$SELECT id FROM orders WHERE email = 'User42@Example.com'$$)19) AS t(n, label, q)20ORDER BY n;

Reading the results

• Both columns and leading column + ORDER BY use the multicolumn index. In the second, the index is read backwards and the Limit stops after three rows: no Sort node at all, because the index already holds each customer's orders in created_at order.
• Second column only cannot seek: the index is sorted by customer_id first, so orders from a given minute are scattered across it. This is the leftmost-prefix rule: an index on (a, b, c) can seek on a, a, b or a, b, c, not on b or c alone.
• Most rows match: 98% of orders are done, so reading the whole table is cheaper than 196,000 index lookups.
• Partial index: WHERE status = 'open' matches the index's own predicate, so the small index (2% of the rows) is usable; the same query for done cannot use it.
• Expression index: an index on lower(email) serves only predicates written on ; a plain cannot use it.

1CREATE FUNCTION plan_of(q text) RETURNS text LANGUAGE plpgsql2  SET max_parallel_workers_per_gather = 0 AS $$3DECLARE4  line text;5  result text := '';6BEGIN7  FOR line IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP8    result := result || CASE WHEN result = '' THEN '' ELSE ' | ' END || trim(line);9  END LOOP;10  RETURN result;11END $$;12CREATE TABLE events (id int PRIMARY KEY, payload jsonb NOT NULL, tags text[] NOT NULL);13INSERT INTO events14SELECT g,15       jsonb_build_object('type', CASE WHEN g % 100 = 0 THEN 'refund' ELSE 'view' END, 'user', g % 5000),16       CASE WHEN g % 200 = 0 THEN ARRAY['vip', 'eu'] ELSE ARRAY['eu'] END17FROM generate_series(1, 100000) AS g;18CREATE INDEX events_payload_gin ON events USING gin (payload);19CREATE INDEX events_tags_gin ON events USING gin (tags);20ANALYZE events;

1SELECT label, plan_of(q) AS plan2FROM (VALUES3  (1, 'containment @>',     $$SELECT count(*) FROM events WHERE payload @> '{"type": "refund"}'$$),4  (2, 'extracted text ->>', $$SELECT count(*) FROM events WHERE payload ->> 'type' = 'refund'$$),5  (3, 'array contains @>',  $$SELECT count(*) FROM events WHERE tags @> ARRAY['vip']$$)6) AS t(n, label, q)7ORDER BY n;

The cost side

Every index gets an entry for every INSERT, and for most UPDATEs: only an update that changes no indexed column and finds room on the same page (a HOT update) can skip them. More indexes mean slower writes, more disk and more cache pressure. Index the queries you actually run, and drop indexes nothing uses (pg_stat_user_indexes.idx_scan stays at 0), after checking the index does not back a primary key or unique constraint, which does its job without ever being scanned by a query.

Common mistakes

• Creating (created_at, customer_id) for a query that filters on customer_id with a range on created_at. Put equality columns first, the range column last.
• Expecting a partial index to be used by a query whose WHERE does not imply the index predicate.
• Indexing email and querying lower(email), or the reverse.
• Adding a GIN index and filtering with payload ->> 'type' = ..., which it cannot serve, as the gin example shows.

What interviewers ask

• Index on (a, b): which queries can seek with it? a, a and b, a with ; a condition on alone cannot seek (at most the whole index is read). Explain with the sorted-order picture.