Database Engine Internals — Bitmap Scans, Buffer Pins & Latching, Deadlock Detection (Deep Dive)

Three interview probes that all reduce to the same underlying question — what is the engine physically doing with pages in memory and on disk, one step below the query plan? How does the optimizer serve a predicate that is too common for a plain index scan but too rare for a full table scan? What stops a page from being evicted out from under a scan that is still reading it? And when two transactions each hold what the other wants, how does the engine even notice, and which one does it kill? This page derives the machinery underneath all three: bitmap scans (the medium-selectivity access path), buffer pins and latches (the two different reasons a page in memory is temporarily untouchable), and deadlock detection (the runtime mechanism that catches what lock ordering didn't prevent).

This assumes you already have the selectivity crossover from “Query Execution — Selectivity, the Cost Model, Join Algorithms & Sargability” (why a seq scan beats an index scan above roughly a few percent selectivity), the covering-index and visibility-map basics from “Indexing — Fanout, Stats, Composite Keys & NULL Pitfalls”, and the locking/MVCC vocabulary from “Transactions & Concurrency — Recovery, MVCC Internals, Serializability & Locking”. Those pages own that ground; this page goes one level deeper on the three mechanisms above.

1. The medium-selectivity answer: Bitmap Index Scan → Bitmap Heap Scan

Mechanism: a bitmap scan is a two-phase access path built to exploit one fact — the cost of visiting a heap page depends far more on how many distinct pages you touch and in what order than on how many rows match. Phase one (Bitmap Index Scan) walks the index and, instead of returning matching rows one at a time, builds an in-memory bitmap flagging every heap page that contains at least one match. Phase two (Bitmap Heap Scan) sorts those flagged pages by physical block number and visits each one exactly once, re-checking the predicate against the rows on that page. The two phases turn “fetch up to N scattered rows in index order” into “fetch at most N distinct pages, once each, in ascending disk order” — deduplication and physical ordering are the two wins, and both come from building the bitmap before touching the heap at all.

This is exactly the access path that belongs in the gap the selectivity crossover page leaves open: below the crossover, a plain index scan is cheap because there are few enough matches that random single-row heap fetches don't add up; above it, a seq scan wins because it pays a flat cost regardless of match count. In between — enough matches that a plain index scan's per-row random fetches pile up, but not so many that reading the entire table is the better bet — a bitmap scan can beat both, provided the matches are not so dense that nearly every page is flagged anyway (at that point it degenerates to a seq scan in all but name, and the planner will usually just pick the seq scan directly).

The same bitmap-first idea composes across indexes. BitmapAnd intersects two bitmaps (serving an AND across two single-column indexes with no composite index required); BitmapOr unions two bitmaps (serving an OR that no single index could answer alone). Both are cheap precisely because they operate on the bitmap — a compact in-memory structure — before a single heap page is touched.

One mechanical wrinkle: if the exact set of matching row identifiers (TIDs) would consume more memory than is budgeted, the bitmap degrades from row-level to page-level (“lossy”) — it still says which pages to visit, but no longer which rows on that page matched. A lossy bitmap forces the heap scan to re-check the full predicate against every row on each flagged page, not just the ones that actually matched — extra CPU, though no extra I/O beyond what was already required. EXPLAIN (ANALYZE) surfaces this directly: Heap Blocks: exact means row-level bitmaps throughout; Heap Blocks: lossy means at least one bitmap degraded and every row on those pages is being re-checked.

Traced worked example — a BitmapAnd that a composite index would otherwise have to serve. A 10M-row orders table, 100 rows/page → 100,000 heap pages. Only single-column indexes exist on status and region, and the query is WHERE status = 'pending' AND region = 'eu-west'. Assume matches are scattered close to uniformly at random (no useful physical correlation):

Step	What happens	Size
Index scan on status	Build a bitmap of pages containing status='pending'	8% of rows ≈ 800,000 rows
Index scan on region	Build a second bitmap for region='eu-west'	12% of rows ≈ 1,200,000 rows
BitmapAnd	Intersect the two bitmaps — exact row-level AND, purely in memory	≈0.96% ≈ 96,000 rows (independence estimate)
Bitmap Heap Scan	Sort the surviving flags by physical block, visit each flagged page once, ascending	≈62,000 distinct pages (≈62% of the table, since 96,000 matches spread across 100,000 pages still lands on most of them at ~1 match/page)

Neither single-column index could serve this predicate efficiently alone — an index scan on status by itself would still have to fetch 800,000 scattered rows, deep in seq-scan territory. Instead of forcing a full table scan or waiting for someone to add a composite (status, region) index, the planner ANDs the two existing single-column bitmaps before touching the heap, then reads only the pages that survive the intersection, in one ascending sweep. This is the mechanism, not a planner heuristic — it is why “the query is a two-column filter and I only have single-column indexes” is not automatically a seq-scan sentence.

When it's actually chosen (recap of the crossover, applied): below the selectivity crossover, a plain index scan wins outright — there's no need for a bitmap detour. Deep above it, a seq scan wins — almost every page is touched anyway, so paying for an index and a bitmap buys nothing. The bitmap path earns its keep in the band between them, and especially whenever the match set can only be assembled by combining more than one index (AND or OR) — that's the case a plain index scan structurally cannot serve at all, bitmap or not.

2. Covering indexes, index-only scans & the visibility map — the dependency, briefly

An index-only scan is the other lever for avoiding heap I/O, and it looks unconditional but isn't: PostgreSQL will skip the heap for a row only when that row's page is marked all-visible in the visibility map — meaning every tuple on the page is already visible to every current transaction. If the bit is unset (typically a page with recent inserts, updates, or deletes not yet vacuumed), the index alone cannot answer the visibility question, so the engine still fetches the heap tuple to check MVCC visibility — even though every column the query needs is already sitting in the index. A covering index on a hot, frequently-written table therefore delivers fewer of its promised heap-free reads until VACUUM catches the visibility map up; the full mechanism and pitfalls live on the Indexing page — this page just flags the dependency so it isn't mistaken for a bitmap-scan concern.

3. Buffer pin, reference counting & latching — three different things guarding one page

Mechanism: the buffer pool holds a fixed set of page-sized frames in memory, and a background replacement policy (commonly a CLOCK/clock-sweep approximation of LRU) has to pick a victim frame whenever a new page needs to be brought in and no frame is free. The senior-level probe is concrete: a scan is mid-read on page 58 — what stops the CLOCK hand from evicting it out from under that scan? The answer is the pin (a.k.a. reference count): the instant a backend starts using a page, it increments that frame's pin count; the instant it's done with the page, it decrements it. CLOCK's victim search has one hard rule that overrides everything else in the algorithm — a frame with pin count > 0 is skipped outright, full stop, regardless of its usage/reference bit. Unpinning doesn't mean instant eviction either: the page still has to survive however many more sweeps it takes for its usage bit to clear, which is exactly why hot pages accumulate high usage counts and keep surviving long after the last reader let go.

A latch is a completely different primitive that happens to guard the same page, which is exactly why the three concepts get confused. A latch is a short-duration, lightweight mutex (or read-write spinlock) that protects the physical bytes of a frame while they're actually being copied or mutated — held for microseconds, never across an I/O wait on a different page, and with no concept of transaction identity, no wait-for graph entry, and no deadlock detection, because the engine's own code paths are written to acquire latches in a fixed, short, provably-terminating order. A pin says “don't evict this page while I'm using it” for as long as a scan needs it (potentially the whole time a query is running); a latch says “don't let anyone else touch these exact bytes while I copy them” for a few instructions. A lock (row/table S or X locks, discussed on the Transactions page) is a third, unrelated thing again: it protects logical, transaction-level correctness (repeatable reads, no lost updates), can be held for the entire lifetime of a transaction — including across network round trips in a distributed transaction — and, because it can be held that long by user-controlled logic, it is exactly the kind of primitive that can deadlock and needs the machinery in §4 to resolve it.

	Pin (ref count)	Latch	Lock
Owned by	Buffer manager	Buffer manager	Transaction/lock manager
Typical duration	One operation's use of a page (can span the query)	Microseconds — one memory copy	Up to the whole transaction
Protects	The page against eviction	The page's bytes during a read/write	Logical/application correctness between transactions
Deadlock-aware?	No — not a wait primitive	No — avoided by strict, short, ordered code paths	Yes — detected via wait-for graph (§4)

CLOCK eviction is safe under concurrency for exactly this reason: it only ever needs to check one integer (the pin count) before touching a frame, and that check is itself made safe by a very short-lived latch on the frame's own descriptor — it never needs to know anything about which transaction is using the page or for how long. The three mechanisms stack cleanly: pin decides whether this frame is eviction-eligible at all, latch decides whether the bytes can be touched right now, and lock decides whether this transaction is allowed to see or change this data given every other concurrent transaction.

4. Deadlock mechanics: prevention, detection & victim selection

Prevention, cheaply: the simplest fix is structural — if every transaction that touches more than one row acquires its locks in the same fixed global order (e.g. always by ascending primary key), a wait cycle becomes mathematically impossible: a cycle needs at least one pair of transactions each waiting on what the other already holds, and a consistent acquisition order guarantees that whichever transaction gets there first always gets there first for every row, everywhere. This is why “always update rows in ascending id order” is not a style preference — it is deadlock prevention by construction, at zero runtime cost.

Detection, when prevention wasn't applied (or can't be, e.g. dynamic lock order from user-driven logic): the engine maintains a wait-for graph — one node per transaction, and a directed edge T_i → T_j whenever T_i is blocked waiting for a lock T_j currently holds. A background detector periodically (PostgreSQL: on a lock wait exceeding deadlock_timeout, default 1s) walks this graph looking for a cycle. A cycle by construction means every transaction on it is waiting for something held by another transaction also on the cycle — none of them can ever make progress without outside intervention, which is precisely the definition of deadlock; the detector's whole job is to notice that cycle exists, not to predict it in advance.

Victim selection: once a cycle is found, breaking it means aborting at least one transaction on the cycle so the others can proceed. Systems differ on the exact criterion: a common textbook approach aborts the transaction that has done the least work (cheapest to roll back and retry, minimizing wasted effort), which in practice often correlates with aborting the youngest transaction; some engines let the application influence this directly — SQL Server's SET DEADLOCK_PRIORITY lets a session mark itself as preferred-to-survive, and its default heuristic otherwise picks whichever transaction is estimated cheapest to undo. PostgreSQL's detector is simpler: it aborts the transaction whose blocked lock request is the one that triggered the check (the one that just timed out), rather than computing a global least-cost victim across the whole graph. Whichever policy is used, the victim receives a deadlock error and must be retried by the application — the engine guarantees the other transaction(s) on the cycle can now proceed, not that the aborted one was the objectively cheapest choice.

Pitfalls

• Assuming a covering index is heap-free. On a table with recent writes, an index-only scan still fetches the heap tuple for any page whose visibility-map bit isn't set — the covering index alone doesn't guarantee it (see §2).
• Treating a bitmap scan as free of recheck cost. A lossy bitmap (page-level only, triggered when the exact TID set would exceed the memory budget) forces a full predicate re-check against every row on each flagged page, not just the ones that matched — watch EXPLAIN (ANALYZE)'s Heap Blocks: exact vs lossy rather than assuming the bitmap phase already filtered everything.
• Conflating pin duration with latch duration. A page can be pinned (in active use) for the entire span of a long-running query while its latch is only ever held for microseconds at a time — "the page is pinned" does not mean "the page is latched right now," and neither one is a transaction-level lock.
• Expecting the deadlock detector to run instantly. Detection is triggered by a lock wait crossing a timeout (e.g. deadlock_timeout), not by a live graph-cycle check on every lock acquisition — a deadlock can sit unresolved for up to that timeout window before the engine even notices.
• Relying on lock ordering that isn't actually global. "We update by ascending id" only prevents deadlocks if every code path touching those tables honors it — one ad-hoc script or ORM-generated query that updates in a different order reopens the cycle.

Judgment layer: how a senior engineer decides

• Index scan vs. bitmap scan vs. seq scan. Below the selectivity crossover, trust the plain index scan. Above it, expect (and don't fight) a seq scan. In between — or whenever the predicate can only be assembled by combining more than one index (a multi-column filter with no composite index, or an OR across columns) — expect and welcome a bitmap scan; it's usually the right plan, not a compromise.
• Deadlock prevention vs. detection. If the transaction's lock-acquisition order is static and known (a fixed set of tables/rows touched in a predictable sequence), enforce a consistent global order and eliminate the deadlock class entirely at zero runtime cost. If lock order is inherently dynamic (driven by user input, dependent on runtime data), prevention isn't available — budget for detection instead: keep transactions short (smaller blast radius, faster detector response), and make sure the application actually retries on a deadlock error rather than surfacing it to the user as a hard failure.
• Diagnosing "why did this stall" reports. A backend stuck for a long, unpredictable time is usually a lock (transaction-level, can span I/O and network waits); a stall on the order of microseconds under heavy concurrent write load is more likely latch contention (buffer manager, not the transaction manager) — the fix and the owning subsystem are different for each.

Takeaways

• A bitmap scan wins in the band between the index-scan and seq-scan crossover by building a page-level bitmap from the index first, then reading only the flagged heap pages once each, in ascending physical order — deduplication plus ordering, not magic.
• BitmapAnd/BitmapOr let existing single-column indexes jointly serve a multi-column predicate that neither could serve alone — but a lossy (page-level-only) bitmap still forces a full predicate recheck per flagged page.
• Pin, latch, and lock are three different primitives protecting three different things at three different timescales — only the lock (transaction-level) participates in deadlock detection; pin and latch are invisible to it by design.
• Lock ordering prevents deadlocks structurally at zero cost; the wait-for graph and its background detector are the fallback for whatever ordering can't cover, and victim selection is a policy choice (youngest / least work / explicit priority), not a correctness requirement — only breaking the cycle is required.

---

Re-authored/Deepened for this guide.

I just read a lesson on **Database Engine Internals — Bitmap Scans, Buffer Pins & Latching, Deadlock Detection (Deep Dive)** (Databases) and want to truly understand it. Explain Database Engine Internals — Bitmap Scans, Buffer Pins & Latching, Deadlock Detection (Deep Dive) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Database Engine Internals — Bitmap Scans, Buffer Pins & Latching, Deadlock Detection (Deep Dive)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Database Engine Internals — Bitmap Scans, Buffer Pins & Latching, Deadlock Detection (Deep Dive)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Database Engine Internals — Bitmap Scans, Buffer Pins & Latching, Deadlock Detection (Deep Dive)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.