Interview questions
Memory is a space resource
1Memory is called a space resource, unlike CPU, disk or network. What does that mean, and why does it matter for a database?
CPU, disk and network can be time-sliced: taking them away mid-use only delays the holder. Memory is held, so taking it back destroys whatever was built in it, such as a half-built hash table. So memory must be rationed before work starts, and the work reformulated (spilled, evicted) when the ration runs out.
Read moreMemory cannot be time-sliced
2Why do serious data systems turn swap off?
Swap chooses which pages to push out by recency, the only signal the kernel has. It cannot know which bytes are dead, which are a hash bucket about to be probed, or which are an index root. The application knows, so it takes the decision back, with spilling and its own buffer pool.
Who owns the bytes
3RAM on a database server has four claimants. Name them, and say which ones can substitute for each other.
The buffer pool, per-query working memory, the operating system's page cache, and runtime overhead. The buffer pool and page cache substitute for each other, since both hold file pages that can be re-read. Working memory holds state that exists nowhere else.
Read moreThe partition of RAM
4What is double buffering, and why does O_DIRECT exist?
Reading files through the kernel into your own buffer pool keeps each page twice, once in the kernel's cache and once in yours, so the memory you effectively have is less than the sum. O_DIRECT bypasses the kernel cache, removing the duplicate and giving the eviction decision back to the engine.
Read moreDouble buffering and O_DIRECT
5Why does Kafka not use its own application-level cache?
Its access pattern, reading the end of the log soon after writing it, matches the kernel's recency heuristic exactly, and Kafka has no extra knowledge to add. An application should take over caching only when it knows something the lower layer does not.
Read moreThe counter-example: Kafka
6What does an arena allocator trade, and how does it fail?
It gives up freeing objects individually, in any order, in exchange for allocation about 50× cheaper and bounded fragmentation: everything is freed at once at a reset point. It pays in peak memory held, and in silent dangling pointers if anything outlives the reset.
7Is it correct that off-heap memory avoids garbage-collection pauses?
Imprecise. Off-heap storage removes a large live set from what the collector must trace. But short-lived objects are nearly free for a generational collector, so off-heap can lose there. It wins for data that is large, long-lived and uniform in shape.
Read moreThe correction to a popular claim
8What goes wrong with a global string-intern table?
It is live state that grows with every distinct value and never shrinks, so a high-cardinality column turns a memory saving into an out-of-memory crash. Production dictionaries have a size cap and a fallback to plain encoding.
9On Linux, what decides which NUMA node a page of memory lives on, and what is the usual bug?
First touch: a page is placed on the node of the thread that first writes to it. The usual bug is one thread initializing a whole buffer, so every worker on the other sockets pays for remote memory access.
Read moreNUMA awareness
What stays in memory
10Why is a buffer-pool miss different from an ordinary cache miss?
A buffer pool is the only path to the data, not a shortcut beside it, and its frames can be dirty or pinned. Evicting a dirty page may first require flushing the log, an fsync on another device, before the page itself can be written.
Read moreA buffer pool is the path, not a shortcutEviction depends on the log
11What is Belady's MIN algorithm, and why do real replacement policies only approximate it?
MIN evicts the page that will be used furthest in the future: optimal, but it needs the future. Real policies estimate the future from the past (recency, frequency or rate of use), and then approximate even that statistic, to keep the hit path cheap.
Read moreThe replacement problem
12Why does LRU replacement fail on scans and loops?
A scan makes every page it touches the most recent, wiping out the working set. On a loop over n pages with fewer than n frames, LRU gets exactly 0% hits, always evicting the page needed next, while random replacement degrades smoothly.
Read moreSequential floodingCyclic access
13Why do databases use the Clock algorithm instead of LRU?
LRU turns every hit into a write to the head of a shared list, which becomes a bottleneck across many cores. In Clock, a hit just sets a bit in the frame's own metadata, so it scales. It was chosen for its hit path, not its hit rate.
Read moreClock: chosen for its hit path
14What is a ghost entry in a replacement policy, and why is it affordable?
The identifier of an evicted page, 8–20 bytes, kept without the page's 8 KB of data. Being 400–1,000× smaller, it lets the policy remember what it threw away and learn from mistakes, as 2Q and ARC do.
Read more2Q and ghost entriesARC
15How does PostgreSQL keep a large sequential scan from flushing its cache?
The executor declares the access pattern. A scan of a table larger than a quarter of shared_buffers gets a small 256 KB ring of buffers to reuse; bulk writes get 16 MB; vacuum gets its own ring. The replacement policy is simply bypassed.
Read moreScan resistance by declaration
16Why can a database not simply memory-map (mmap) its data files and let the kernel manage them?
It cannot control when the kernel writes pages back, so it cannot guarantee that the log reaches disk before the data page it describes. Page-fault stalls also hide inside critical sections, I/O errors arrive as SIGBUS signals, and TLB shootdowns get more expensive with more cores.
Read moreJust mmap the file
Rationing memory
17What does a memory grant do, and what does it cost?
It moves failure from an arbitrary moment in execution, where it destroys the most work, to admission, where it costs nothing and the victim is known. The price is memory reserved but never touched, and queries left waiting that would have fit.
Read moreMemory grants and reservationsReservation is not usage
18Why should memory grants be sized in steps rather than continuously?
Memory is the base of a logarithm in the number of merge passes, so cost falls as a staircase, not smoothly. Giving 1.5× the memory needed for a one-pass merge is waste, and giving 0.9× costs a whole extra pass. Grant at the step boundaries.
Read moreThe grant is a point on a curve
19Where does a memory grant's number come from, and why is it often wrong?
Estimated row count × estimated row width, from the optimizer's statistics. Those estimates scatter around the truth roughly log-normally, with a heavy right tail, and are off by several orders of magnitude for queries with many joins.
Read moreWhere the grant number comes fromThe error is large and not symmetric
20Which memory estimation error is cheaper: too small or too large?
Too small causes spilling, which is slow but correct, provided the operator can spill. Too large wastes concurrency. So underestimating is the cheaper error only if everything involved can spill.
Read moreThe two errors are not equal
21Why must memory-based admission control count bytes, not queries?
Query footprints span about six orders of magnitude, from kilobytes to hundreds of gigabytes. A limit on the number of queries is safe only if set for the worst case, which leaves the machine idle on ordinary days.
When memory runs out
22Why does spilling only 5% of a join's data make it about 6 times slower?
The spilled part becomes I/O-bound instead of memory-bound. With memory r = 50 times faster than the spill device, and the data written then read back, cost is (1 − f) + 2 f r = 0.95 + 5 = 5.95. The penalty follows the bandwidth ratio, not the fraction spilled.
Read moreWhat spilling actually costs
23What limits how much data one hash-partitioning pass can spill and handle, and what limits it for a single key?
One partitioning pass handles up to about M² / B of data, for memory M and buffer size B. But a single key whose rows exceed memory cannot be split by any hash function, so recursive partitioning never converges.
24Why does sort-merge survive in mature engines when hash-based operators are usually faster?
It has no requirement that anything fit in memory, so it cannot fail on skew or a bad estimate. When estimates have a heavy tail, you choose the algorithm with the better tail, not the better average.
25Why is the operating system's out-of-memory killer worse than killing a query?
It kills whole processes. Losing an executor loses its cached blocks and shuffle output and forces upstream work to be recomputed, so the damage grows faster than the memory freed.