Database indexing — B-trees, composite order, partial indexes

An index trades write amplification for read acceleration. The mental model: a B-tree (balanced, ~O(log_f N) depth — fanout ~100s, so 3–4 levels for a billion rows) whose sorted structure serves equality, range, and prefix scans, plus ORDER BY for free.

Rules that matter in interviews and in your code:

1. Composite index column order = equality columns first, then range/sort. (user_id, status) serves WHERE user_id=? AND status=? and WHERE user_id=? — but not WHERE status=? alone. Your zoth indexes prove you know this: idx_access_requests_user_status, idx_access_requests_resource_status — both queries are "show my pending/active requests" (user equality + status filter) and "show this resource's active grants" (resource + status).
2. A partial index indexes only matching rows — smaller, hotter, and it documents the query's shape. Your idx_outbox_unpublished ON outbox_events(created_at) WHERE published_at IS NULL — the relay's backlog scan only ever touches unpublished rows; published rows (the vast majority over time) aren't indexed at all. This is a genuinely senior trick and it's in your migrations (006).
3. Unique constraints are indexes — @@unique([userId, idempotencyKey]) is not just integrity, it's the duplicate-check lookup path.
4. Index the FK columns — Postgres does NOT auto-index FKs; unindexed FKs make cascades and parent-child joins O(child). Yours: idx_users_manager_id (the CTE's join path).
5. Covering via INCLUDE — when a hot query needs 1–2 extra columns; know the term even if you didn't need it.
6. HNSW for vectors — approximate nearest-neighbor graph; your vector_cosine_ops index keeps similarity search ms-scale (Day 66).

Traverse's index story — with the war story

The schema's index set: Revision indexes on [userId, scheduledFor], [userId, completedAt], [userId, type], [modelVersion] — each maps to a named query ("due today," "history," "analytics per version"). Notification on [userId, createdAt], [userId, readAt], [userId, coalesceKey, readAt] — the third one exists specifically for coalescing lookups (find this user's unread row with this key) — an index designed for one function's access path. That's the discipline: indexes have client names.

The war story (streak walk): the old calculateCurrentStreak issued one findUnique per day inside a while loop — a 300-day streak = 300 round-trips — and it ran on every solve. The rewrite fetches the full history in two queries and walks contiguity in memory. The lesson isn't "batch your queries" — it's that the index was fine; the query shape was broken. Indexes can't save a chatty access pattern. Say it exactly like that.

What NOT to index

Write-heavy tables (submissions!) gain read speed at write cost — traverse indexes submissions selectively (the unique constraint is mandatory; the rest live on derived tables). Zoth's api_keys.key_hash has a unique constraint (implying the index) — no extra index needed. And every index must be nameable to a query: "which query uses this?" — no answer, no index.

Drill

SELECT * FROM access_requests WHERE tenant_id=$1 AND status='ACTIVE' AND expires_at < now() (the expiry loop) — ideal index: (status, expires_at) or partial WHERE status='ACTIVE' (expires_at). Your actual: idx_access_requests_status + batch LIMIT 100 — fine at this scale; be able to propose the better one and say why the difference is negligible at 100 rows/tick.