Walk through what a relational database does with a SQL statement from the moment the text arrives at the server until rows come back to the client. Name each stage and say what it produces.

## Why this question is asked This pipeline is the map that every other query-performance conversation hangs off. If you know which stage produced a given behaviour, you know where to look: a syntax error is a text problem, a "column does not exist" is a catalog problem, a bad join order is an optimizer problem, and a slow scan that matches the plan is an execution problem. Interviewers use it as a structuring question - they want to hear ordered stages, each with an input and an output, not a vague "it parses and runs it". ## Stage 1: parsing (syntax only) The server receives a string. A lexer splits it into tokens (keywords, identifiers, literals, operators), and a parser matches that token stream against the SQL grammar. The output is an **abstract syntax tree (AST)**: a tree whose nodes mirror the written statement - a select node with a projection list, a from list, a where expression, and so on. The critical property is that the parser has **no knowledge of your schema**. It does not know whether a table exists or whether a column is an integer. It only knows whether the words are arranged legally. A misspelled keyword, an unbalanced parenthesis, or a missing comma dies here, and the error message typically points at a character position in the text. ## Stage 2: semantic analysis / binding The binder (also called the analyser or resolver) walks the AST and connects it to reality by consulting the **system catalog** - the database's own tables that describe tables, columns, types, functions and privileges. For each identifier it answers: which object is this? Concretely it: - resolves an unqualified table name using the session's schema search order, and records the resolved object identifier; - resolves each column reference to a specific relation and column, and attaches that column's **data type**; - expands `*` into the actual column list, so the result shape is fixed now, not at execution time; - resolves function and operator calls to one specific overload, inserting implicit casts where the type rules allow; - inlines views by substituting their stored definitions; - checks that the user is permitted to touch the objects involved. The output is a fully annotated, type-checked tree - effectively a **logical plan**: an algebraic description (scan, filter, join, project, aggregate, sort) of what result is wanted, with no decision yet about *how*. Everything the parser could not know surfaces here: unknown table or column, ambiguous column reference, wrong argument types, insufficient privileges. ## Stage 3: rewrite / normalization Before costing anything, engines normalize the logical plan with transformations that are guaranteed to preserve meaning - folding constants, flattening nested structures, normalizing predicates into a canonical form. This is still a *logical* plan: it says what, not how. (The specific rewrite rules are a topic of their own.) ## Stage 4: optimization / planning The optimizer enumerates physically executable alternatives for the same logical plan and picks one. For a two-table join it might consider an index lookup driving a nested loop, or two scans feeding a hash join; for a three-table join it also chooses the order. Each candidate is costed using **catalog statistics** - row counts, distinct value counts, histograms, correlation - plus a cost model that weights I/O and CPU. The cheapest estimated candidate wins. The output is the **physical plan**: a tree of concrete operators, each with a chosen algorithm and its estimated row count and cost. Two runs of identical text can produce different physical plans if statistics, indexes, or the amount of available memory changed. That is the single most important consequence of this stage boundary. ## Stage 5: execution The executor takes the physical plan tree and runs it. The classic model is demand-driven: the top operator asks its child for the next row, which asks its own child, and rows are pulled up through the tree. Along the way the executor applies the transaction's visibility rules (which row versions this statement is allowed to see), acquires the locks or latches it needs, spills to disk if a sort or hash exceeds its memory budget, and pushes result rows back to the client - often incrementally, so a `LIMIT`-style query can stop early. ## What the stage boundaries buy you - **Diagnosis.** "Invalid identifier" means you never reached the optimizer. "The plan looks sensible but rows returned are 1000x the estimate" means binding and planning were fine and your statistics are wrong. - **Prepared statements.** Parsing and binding depend only on text plus catalog, so their results can be cached and reused; planning may or may not be reused, which is a separate design decision an engine makes. - **Version dependence.** Because the plan is chosen from statistics, a query that was fast for months can regress after a bulk load, with no code change at all. ## What interviewers listen for Named stages in order, one concrete artefact per stage (AST, logical plan, physical plan, rows), and the awareness that syntax, semantics and cost are three different kinds of knowledge consulted at three different times.