Database internals: a query's lifecycle, the buffer cache and the query optimizer

This was the database-internals half of a technical screen: a discussion, not a coding exercise. Explain what a disk-based database engine does with a query from the moment it arrives until the results are returned, then go deep on two components: the buffer cache and the query optimizer. You may ground the answer in a relational engine with SQL, using a query such as the one below as a running example. ```sql SELECT c.name, COUNT(*) AS shipped_orders FROM customers c JOIN orders o ON o.customer_id = c.id WHERE o.status = 'shipped' GROUP BY c.name; ``` ### Clarifying Questions - Should the answer describe a generic disk-based relational engine, a specific one, or a document database? - Is the interest conceptual, or down to data structures and algorithms (page tables, replacement policies, plan enumeration)? - Are transactions, locking and recovery in scope, or only as far as they touch the buffer cache? ### Part 1 — The life of a query Describe the stages a query goes through between the client sending it and receiving rows, and what each stage produces for the next. ```hint Follow the representations The query is transformed several times before any data is read. Name each intermediate form and which component consumes it. ``` #### What This Part Should Cover - The stages in order, from receiving the text to returning rows, and what each one checks or produces - Where errors of each kind (syntax, unknown names, permissions) are detected - How execution actually pulls rows from storage, and what changes for a write ### Part 2 — The buffer cache Explain what the buffer cache (buffer pool) is, why the engine manages it itself, and how it works: finding a page, choosing a page to evict, and handling modified pages. ```hint A cached page has more states than present or absent Consider what must be true of a cached page before its memory can be reused, and what a crash at that moment could lose. ``` #### What This Part Should Cover - The structures involved and the path of a page request on a hit and on a miss - A replacement policy and how it copes with a large scan - Dirty pages, their interaction with the write-ahead log, checkpoints and crash recovery ### Part 3 — The query optimizer Explain how the optimizer turns a query into an execution plan: the alternatives it considers, how it estimates their cost, and where its choices go wrong. ```hint Every cost starts with a row count The cost of each plan depends on a guess of how many rows flow out of each step. Consider where that guess comes from and when it is badly wrong. ``` #### What This Part Should Cover - The plan space: access paths, join orders and join algorithms, and how the search is kept tractable - The cost model and cardinality estimation from statistics, with its assumptions - Typical misestimates, how to diagnose them, and how to fix them ### What a Strong Answer Covers - A correct, ordered account of query processing that connects the stages to the two deep dives - Buffer pool mechanics at the level of data structures, including pinning, replacement and the write-ahead rule - Optimizer mechanics including cardinality estimation, not just "it picks the cheapest plan" - Concrete examples (the running query, a misestimate) and the trade-offs behind each design choice ### Follow-up Questions - A full scan of a table larger than the buffer pool runs every night and the next morning's queries are slow. Why, and how do engines prevent it? - After a bulk load, a query that used to take milliseconds takes minutes and the plan shows a nested-loop join over millions of rows. How do you diagnose and fix it? - Why do some engines bypass the operating system's page cache, and what do they give up by doing so? - How do checkpoints bound recovery time, and what do they cost while the system is running?