Query Engine

A SELECT is a request, not a program. Seven stages turn it into one: parser, binder, planner, optimizer, executor and storage — each with its own data structure and its own way of failing.

Before a query can be planned it must become a tree. The lexer cuts text into tokens, a recursive-descent parser builds the tree by the grammar, and semantic analysis resolves every name against the catalog — the same front end every compiler has.

For one bound query there are many correct procedures, differing by orders of magnitude. The planner lists them — access paths per table, join orders, join methods — and needs statistics to tell them apart. The tree it hands over is what EXPLAIN prints.

Statistics in, a number out: n_distinct, most-common values and histograms become a selectivity, a row estimate, and finally an I/O + CPU cost in units where a sequential page is 1.0 and a random page is 4.0. The arithmetic is simple; the inputs decide everything.

Three ways to pair rows from two inputs: loop over both (quadratic, needs nothing), hash one and probe with the other (linear, needs memory), or sort both and walk two cursors (linear after the sort, needs order). The planner picks by input sizes, available indexes and memory.

One real statement — best-selling products in a category — followed from text to result through every layer: parser, AST, candidate plans, cost, chosen plan, buffer pool, scans, joins, aggregate, sort, limit. At each step: what happens, why, the algorithm, the memory, the storage, the DSA concept underneath.