B-trees, query planning, and reading EXPLAIN like an owner
What the planner does with your indexes, and the explains you should be able to narrate cold.
Concept → your projects
A B-tree (Postgres default) is a sorted, balanced tree: internal nodes route by key ranges, leaves hold entries + heap pointers (and form a linked list for range scans). Depth is ~3–4 for billions of rows (fanout ≈ index page / entry size). Insertions keep it balanced via node splits — that's the write cost you pay per index.
The planner picks access paths by cost (sequential+random page costs, table stats from ANALYZE, cardinality estimates). Its decision cascade for WHERE tenant_id=$1 AND status='ACTIVE':
- Any index whose leading column(s) match the predicates?
- Estimated selectivity — will the index return few enough rows that random heap fetches beat a full seq scan + filter?
- Combine bitmap indexes if two single-column indexes are both selective (BitmapAnd).
Where estimates go wrong: stale stats (autovacuum/ANALYZE lag), skewed distributions (a status enum where 99% is 'PENDING' — the planner's average selectivity estimate is lies), cross-column correlation (WHERE tenant_id AND status where statuses correlate with tenants). The fixes: extended statistics (CREATE STATISTICS), partial indexes for the skewed slice, or LIMIT-batches like your expiry loop (LIMIT 100 makes even a mediocre plan acceptable).
The EXPLAIN vocabulary to recite: Seq Scan (fine for small/filter-everything), Index Scan (ordered, selective), Index Only Scan (visibility map permitting — the covering case), Bitmap Heap Scan + Bitmap Index Scan (two-phase: build the bitmap, then fetch), Nested Loop vs Hash Join vs Merge Join (inner-loop for small outer, hash for unsorted equality, merge for two sorted inputs). rows= vs actual is the lying-detector: estimated 10, actual 100,000 → stats problem.
Your three explains (narrate these cold)
- Outbox relay scan:
SELECT ... WHERE published_at IS NULL ORDER BY created_at LIMIT 100 FOR UPDATE SKIP LOCKED. Walk: partial indexidx_outbook_unpublishedon created_at → index scan gives order + predicate in one → LIMIT stops early → FOR UPDATE row-locks claimed rows. The partial index means the planner sees an index whose size = backlog, always. - Manager-chain CTE: recursive term joins
users uonu.id = mc.manager_id— driven byidx_users_manager_id; each recursion level is an index lookup on a ~25-deep chain. Small, fixed cost. - pgvector search:
ORDER BY embedding <=> $2::vector LIMIT 3— without the HNSW index this is a seq scan computing cosine distance on every row; withhnsw (vector_cosine_ops)it's an approximate graph traversal visiting a few hundred nodes. The migration 007 exists because someone watched this seq-scan and fixed it — the index was added specifically so policy-doc similarity search stopped scanning. That's a real "EXPLAIN-driven optimization" story: measure → index → re-measure.
Practical checklist for your own queries
EXPLAIN (ANALYZE, BUFFERS)on the five hottest queries per project — you've effectively done this for one (HNSW); do it for the expiry loop and the notifications claim.- Watch
rowsestimates vs actuals on the skewed enums (status). pg_stat_statementsfor "which queries cost the most cumulative" — the honest priority queue (not the slowest single query — the most frequent slow one).
Bulletproof your resume
Say these answers aloud before moving on
These are the follow-ups an interviewer will actually ask about your projects.
When does Postgres prefer a seq scan over your index, and when is that right?
When the predicate matches a large fraction of the table (rule of thumb: ~5–10%+): random heap fetches for many rows cost more than a sequential read of everything. So 'all ACTIVE requests' on a table that's 80% ACTIVE should seq scan. My expiry query survives this because of LIMIT 100 + the partial indexes — the planner sees a bounded ask. The trap is skewed data: if stats say a status is rare but it's actually common, the planner picks the index and pays random I/O. Partial indexes sidestep it: index only the rare slice you query for.
Your vector search seq-scanned before migration 007. How would you have diagnosed it?
EXPLAIN (ANALYZE, BUFFERS) on SearchByEmbedding: Seq Scan on policy_documents with a filter computing embedding <=> $1 per row, plus high shared read counts. Rows-out scale linearly with documents. The fix is the HNSW index (vector_cosine_ops for cosine distance) — approximate nearest neighbors via graph traversal, ms-scale, at the cost of approximate recall (tuned via hnsw.ef_search). The meta-lesson: embeddings search without an ANN index is a hidden O(n) — it feels fine at 1k docs and dies at 100k.
Bitmap scan vs index scan — when each?
Index scan walks the index in order and fetches heap rows one-by-one — great for highly selective or ordered access (my LIMIT 100 relay scan). Bitmap scan first builds a bitmap of matching heap pages, sorts by physical location, then reads sequentially — better for moderately selective predicates (thousands of rows) because it converts random I/O into fewer sequential reads; two predicates can combine via BitmapAnd. Merge/hash joins then work on the sorted/batched output. The tradeoff: bitmap loses index order, so it can't serve ORDER BY.