1 From SQL text to a plan โ the front-end
Imagine you write a wish on a piece of paper and hand it to a genie. The genie can't grant it straight away. First he reads the letters and groups them into words. Then he checks the words form a real sentence, not gibberish. Then he makes sure the things you asked for actually exist ("you want the red bicycle โ okay, that one is real"). Only then does he write himself a little to-do list of steps to make the wish come true. A database does exactly this with your SQL before it fetches a single row.
Back in Session 1 we saw the big picture of how a query travels through the database engine. This session zooms into the very first stretch of that journey โ the part we call the query front-end (also called the query compiler). Its job is to take the SQL string you typed and convert it into a precise, unambiguous internal form the rest of the engine can work with.
Where the front-end sits in the pipeline
A database processes a query in stages, like an assembly line. The front-end is the first three or four stations; everything after it (optimisation and execution) we cover in later sessions.
Notice the shape of the transformation. We start with unstructured text and end the front-end with a structured tree of operations. Each stage adds more meaning:
| Stage | Input | Output | What it adds |
|---|---|---|---|
| Lexing | Raw characters | Tokens | Groups characters into meaningful words/symbols. |
| Parsing | Tokens | AST (parse tree) | Checks grammar; reveals structure (which clause is which). |
| Binding | AST + catalog | Resolved / bound AST | Connects names to real tables/columns; checks types. |
| Logical planning | Bound AST | Logical plan | Restates the query as relational-algebra operators. |
The front-end is a translator with a fact-checker. It turns human-friendly SQL into a machine-friendly tree, rejecting anything that is misspelt, ungrammatical, or refers to things that don't exist โ before the engine wastes effort touching real data.
SQL is a declarative language: you say what you want ("give me customers in London"), not how to get it. The front-end (plus the optimiser later) is what bridges that gap โ it figures out the how. A language like C, by contrast, is imperative: you spell out every step yourself.
Take this query:
SELECT name FROM customers WHERE city = 'London';
By the end of the front-end this becomes, roughly, a three-step plan: scan the customers table โ keep only rows where city = 'London' โ output just the name column. That little tree is what we hand to the optimiser. We'll build exactly this tree by the end of the session.
2 Lexing & parsing โ text into a tree
When you learn to read, you first see a row of letters: t-h-e c-a-t.
Your eyes group them into words: "the", "cat". That's lexing. Then your brain
figures out the sentence's shape โ "the cat" is the thing doing something. That's
parsing. The database does the same two steps to your SQL: first chop it into
words, then work out the sentence structure.
Step A โ Lexing (tokenising)
The lexer (also called a tokeniser or scanner) reads the SQL one character at a time and groups characters into tokens โ the smallest meaningful units. It also throws away things that don't matter, like extra spaces and comments. Each token has a type (keyword, identifier, number, string, operator, punctuation) and a value.
Input SQL:
SELECT name, age FROM users WHERE age > 18;
The lexer emits this stream of tokens:
# type value
KEYWORD SELECT
IDENTIFIER name
PUNCT ,
IDENTIFIER age
KEYWORD FROM
IDENTIFIER users
KEYWORD WHERE
IDENTIFIER age
OPERATOR >
NUMBER 18
PUNCT ;
Notice the whitespace is gone, and each piece now carries a label. SELECT
is recognised as a reserved keyword, while name and users
are identifiers (names of things in your database).
A keyword is a word SQL reserves for itself (SELECT,
FROM, WHERE, JOINโฆ). An
identifier is a name you chose for a table, column, or alias. The
lexer keeps a list of reserved keywords so it can tell them apart. This is why you usually can't
name a column select without quoting it.
Step B โ Parsing (applying the grammar)
The parser takes that flat list of tokens and checks they form a valid sentence according to SQL's rules. Those rules are written as a grammar: a set of patterns describing what a legal statement looks like. Grammars are usually written in a notation called BNF (BackusโNaur Form).
<select_stmt> ::= SELECT <select_list> FROM <table> [ WHERE <condition> ] ; <select_list> ::= "*" | <column> { "," <column> } <condition> ::= <column> <op> <value> <op> ::= "=" | ">" | "<" | ">=" | "<="
Read ::= as "is defined as", | as "or",
[ ] as "optional", and { } as "repeated zero or
more times". So a SELECT statement is the word SELECT, then a list of
columns, then FROM and a table, then an optional WHERE.
As the parser matches tokens against the grammar, it builds an Abstract Syntax Tree (AST) โ a tree that captures the structure of the statement, with each grammar rule becoming a node. "Abstract" means it drops noise like commas, semicolons, and parentheses, keeping only what matters for meaning.
Parsing SELECT name, age FROM users WHERE age > 18; produces this AST:
SelectStatement
โโโโโโโโโผโโโโโโโโโโโโโโ
โ โ โ
projection from where
โ โ โ
โโโโโโดโโโโ Table BinaryExpr (>)
Column Column "users" โโโโโโดโโโโโ
"name" "age" Column Literal
"age" 18
Read it top-down: the root says "this is a SELECT". It has three children โ the
projection (the columns we want), the from (the source table),
and the where (the filter). The filter itself is a binary
expression: a > operator with a column on the left and the
number 18 on the right.
If the tokens don't fit the grammar, parsing fails with a syntax error. Type
SELECT name FORM users; (misspelt FROM) and the parser sees an identifier
where it expected the FROM keyword, and complains โ often pointing at the
exact spot. Crucially, the parser only checks grammar, not meaning: it doesn't
yet know or care whether a table called users actually exists. That's the
next topic's job.
You'll hear both terms. A parse tree (or concrete syntax tree) keeps
every token, including punctuation. An AST is the cleaned-up
version with the noise removed. Most engines build something close to an AST directly. PostgreSQL,
for instance, produces a tree of parse nodes at this stage.
3 Binding & semantic analysis
Suppose you write a grammatically perfect sentence: "Please bring me the purple elephant from the kitchen." It's a real sentence โ but there is no purple elephant, and elephants don't live in kitchens. A friend checking your note would say "that doesn't make sense." The database has a friend like that too. After the grammar is fine, this step checks that the tables and columns you named really exist and that you're using them sensibly.
The AST from Topic 2 is grammatically correct but naรฏve: the names in it are still just
text. The word users is a string, not yet connected to a real table. The
job of binding (also called semantic analysis,
or name resolution) is to give those names meaning by looking them up.
The catalog โ the database's phone book
To resolve names, the binder consults the catalog (also called the
system catalog or data dictionary): the database's own internal
record of every table, column, data type, index, and constraint. It's "metadata" โ data about your
data. When the binder sees users, it asks the catalog: "Is there a table
called users? What columns does it have? What are their types?"
The catalog is itself stored as tables inside the database. In PostgreSQL you can literally query
it (pg_class, pg_attribute); the SQL standard
exposes a tidy view of it called INFORMATION_SCHEMA. So the database stores
knowledge about itself in the same way it stores your data.
What semantic analysis actually checks
Binding walks the AST and performs several checks and transformations:
| Check / task | What it does | Example error it catches |
|---|---|---|
| Table resolution | Confirms each named table/view exists and you may access it. | relation "userz" does not exist |
| Column resolution | Confirms each column exists in the right table; attaches its data type. | column "naem" does not exist |
| Ambiguity check | If two joined tables both have a column id, an unqualified id is ambiguous. | column reference "id" is ambiguous |
| Type checking | Verifies operators/functions get sensible types; may insert casts. | operator does not exist: integer > text |
Expanding * | Replaces SELECT * with the real, explicit column list from the catalog. | โ |
| Function/aggregate validity | Checks functions exist and aggregates like COUNT are used in legal places. | function lengthh(text) does not exist |
You write:
SELECT * FROM users;
The binder asks the catalog what columns users has and rewrites the
query internally to the explicit list:
SELECT id, name, age, city FROM users;
From here on, the engine works with the real columns and their types. This is also why
SELECT * can be slightly slower to plan and is discouraged in production
code โ and why adding a column to a table can change what * returns.
Imagine age is an INTEGER column and you write
WHERE age > '18' (a string). A strict binder would reject comparing an
integer to text. Many databases instead insert an implicit cast, quietly
turning the AST node into age > CAST('18' AS INTEGER). The bound AST now
carries explicit type information on every expression.
Binding lets the database catch mistakes early, before any disk is touched or any row is read. A typo in a column name costs microseconds to detect here, versus scanning a billion-row table only to discover the column was never real. Catching errors at compile time is far cheaper than at run time.
The output of this stage is the same tree shape as before, but enriched: each
table node now points at a real catalog object, each column node knows its table and data type, and
* is expanded. Some textbooks call this a resolved query
tree. It is unambiguous and ready to be turned into a plan.
*. This is where "table/column does not exist" and type errors are caught โ
early and cheaply. The output is an annotated, fully-resolved query tree.
4 Logical plan generation
Think of a recipe. "Chocolate chip cookies" is what you want. The recipe card is the ordered list of steps: get flour, mix in sugar, add chips, bake. The logical plan is the database writing itself a recipe card from your wish โ a stack of simple steps, each feeding the next. It doesn't yet say which oven or how fast (that's the optimiser later); it just lists the steps in a sensible order.
We now have a clean, fully-resolved query tree. The final front-end step turns it into a logical plan: a tree of relational-algebra operators. Relational algebra is the mathematical foundation of SQL โ a small set of operations that each take one or more tables (relations) as input and produce a table as output. Because every operator outputs a table, you can stack them into a tree.
The core relational-algebra operators
| Operator | Symbol | Plain English | SQL clause it comes from |
|---|---|---|---|
| Scan | โ | Read all rows from a table. | FROM users |
| Filter (selection) | ฯ (sigma) | Keep only rows matching a condition. | WHERE age > 18 |
| Project | ฯ (pi) | Keep only certain columns. | SELECT name, age |
| Join | โ (bowtie) | Combine rows from two tables on a condition. | JOIN โฆ ON โฆ |
| Aggregate | ฮณ (gamma) | Group rows and compute sums/counts/etc. | GROUP BY, COUNT() |
| Sort | ฯ (tau) | Order the rows. | ORDER BY |
A logical operator says what to do ("join these two tables"), not how. There are usually several physical operators that implement the same logical one โ a join could be done as a nested-loop join, a hash join, or a merge join. Choosing the actual physical algorithm is the optimiser's job in Session 11. The logical plan deliberately leaves the "how" open.
Building the plan from the query tree
The planner reads the bound query and assembles operators bottom-up, so that data flows from the leaves (tables) up to the root (final result). A handy way to remember the canonical order: FROM โ WHERE โ SELECT becomes Scan โ Filter โ Project, reading the tree from the bottom up.
Recall the query:
SELECT name FROM customers WHERE city = 'London';
The logical plan is a three-node tree. Data flows upward: the scan produces all rows, the filter throws most away, the project trims the columns.
Project [ name ] # ฯ โ keep only the name column โ โผ Filter [ city = 'London' ] # ฯ โ drop rows that don't match โ โผ Scan [ customers ] # read every row of the table
Equivalently, in relational-algebra notation:
ฯname ( ฯcity = 'London' ( customers ) )
Read the algebra inside-out: scan customers, apply the filter ฯ, then
project ฯ. The tree and the algebra say the same thing.
Now a two-table query:
SELECT c.name, o.total FROM customers c JOIN orders o ON c.id = o.customer_id WHERE c.city = 'London';
Its logical plan has two leaves (one scan per table) feeding a join, then a filter, then a project:
Project [ c.name, o.total ]
โ
โผ
Filter [ c.city = 'London' ]
โ
โผ
Join [ c.id = o.customer_id ] # โ
โโโโโโดโโโโโโ
โผ โผ
Scan [ customers ] Scan [ orders ]
This plan is correct but not necessarily fast โ for instance, filtering London customers before the join would usually be cheaper. Rearranging the plan into a faster but equivalent one is precisely what the optimiser does next. The front-end just needs a correct starting tree.
You write SELECT first, but logically it happens almost last.
The true logical evaluation order is roughly: FROM โ JOIN
โ WHERE โ GROUP BY โ HAVING
โ SELECT โ ORDER BY โ LIMIT.
That mismatch explains a classic beginner error: you can't use a column alias defined in
SELECT inside the WHERE clause, because WHERE runs
before SELECT exists.
Producing a correct logical plan from a SQL string is the goal we'll call Milestone M2 in our build-a-database project. M2 ends the front-end: you have lexing, parsing, binding, and logical-plan generation all working. The next milestone hands this plan to the optimiser (Session 11), which chooses physical operators and access paths (using the index structures from Session 7), and then the executor (Session 9) actually runs it.
โ Putting it all together
You just walked the entire query front-end โ the path from a raw SQL string to a plan. Here's the one-paragraph story that connects all four topics:
Your SQL starts as plain text. The lexer chops it into
tokens; the parser checks those tokens against SQL's
grammar and builds an Abstract Syntax Tree, catching
syntax errors. Binding then consults the catalog to
resolve every table and column, check types, and expand *,
catching semantic errors early and cheaply. Finally, logical-plan generation
restates the resolved query as a tree of relational-algebra operators (scan,
filter, project, join) โ a correct but unoptimised plan, our Milestone M2. That
tree is the baton passed to the optimiser (Session 11) and then the
executor (Session 9).
Quick self-check
What's the difference between lexing and parsing?
Lexing groups raw characters into labelled tokens (keywords, identifiers, numbers, operators). Parsing takes that token stream and checks it against SQL's grammar, building an AST that captures the statement's structure. Lexing = words; parsing = sentence structure.
A query is grammatically perfect but names a table that doesn't exist. Which stage catches it, and why not the parser?
Binding / semantic analysis catches it, by looking the table up in the catalog. The
parser only checks grammar (structure), not meaning โ to it, users is just a
valid identifier whether or not the table is real.
What is the catalog, and why does binding need it?
The catalog (system catalog / data dictionary) is the database's internal metadata:
every table, column, type, index, and constraint. Binding needs it to resolve names to real objects
and attach data types so it can type-check expressions and expand *.
What does it mean that a logical plan is "logical" and not "physical"?
It says what to do (e.g. "join these tables", "filter these rows") but not how. Choosing the concrete algorithm (nested-loop vs hash vs merge join, which index to use) is the optimiser's job in Session 11.
Write the logical plan for SELECT name FROM users WHERE age > 18;
Bottom-up: Scan[users] โ Filter[age > 18] โ Project[name]. In algebra: ฯname(ฯage > 18(users)).
Why can't you reference a SELECT alias inside the WHERE clause?
Because of logical evaluation order: WHERE is evaluated before SELECT, so the alias defined in SELECT doesn't exist yet when WHERE runs. The order is roughly FROM โ JOIN โ WHERE โ GROUP BY โ HAVING โ SELECT โ ORDER BY โ LIMIT.
๐ References & Further Reading
Class material
- ๐ Original course notes / handout (source sheet) โ open the shared class material for this session.
- ๐ Class handout: "DBMS Session 8 โ Query Parsing".
Papers, docs & deep dives
- CMU 15-445/645 โ Database Systems โ the gold-standard free course; see the query-processing lectures (parser, binder, optimiser) for a working engine's view.
- PostgreSQL Docs โ The Parser Stage โ a real production database explaining exactly how it lexes, parses, and produces parse trees.
- PostgreSQL Docs โ Planner / Optimizer โ how the resolved query becomes a plan tree; the stage right after the front-end.
- "Database System Concepts" (Silberschatz, Korth, Sudarshan) โ the query-processing chapter covers parsing, translation to relational algebra, and logical plans in depth.
- PostgreSQL Docs โ The Information Schema โ a concrete look at the catalog/metadata that binding queries to resolve names and types.