Query front end — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 3: Turning requests into execution

Prerequisites: Lesson 12 and the preceding foundations.

Learning outcomes

• Trace SQL text through parsing, name binding, type checking, and logical-plan construction.
• Explain catalog visibility, ambiguity, NULL behavior, and semantic error handling.
• Separate syntactic acceptance from executable meaning and optimization.

Valid text is not yet a valid query

A client submits a syntactically valid SQL query. The parser accepts it, but a column name exists in two joined tables. Another query names a table that the caller cannot access. A prepared query was valid before a schema change but now depends on a different type. These are different failures at different stages. A reliable front end must distinguish them before execution begins.

A query front end translates a user-facing language into a typed internal representation. It establishes names, types, scope, parameters, privileges, and dependencies. Optimization should begin only after the engine knows what the query means.

Lexing and parsing

Lexing recognizes tokens such as identifiers, keywords, literals, and operators. Parsing organizes them according to grammar into an abstract syntax tree, or AST. Parentheses, precedence, and clause structure determine the tree. The AST records syntax, not necessarily a ready execution plan.

SELECT name FROM player WHERE player_id = 17

Select
  output: Name(name)
  source: Name(player)
  predicate: Equal(Name(player_id), Integer(17))

The representation is illustrative. At this stage, name and player_id may still be unresolved names. A malformed statement should produce a controlled error with a useful location, not invoke arbitrary execution or allocate without bounds. Deeply nested expressions and extremely large statements need limits because parsing is itself a resource-consuming operation exposed to clients.

A parser’s acceptance does not establish safe interpolation. Applications should bind parameters rather than construct SQL by inserting untrusted text. Parameter binding separates values from grammar. Identifiers such as table names generally require a different controlled construction strategy because they are not ordinary value parameters.

Binding names and scopes

Binding resolves a name to a concrete catalog object or scoped expression. The binder needs to know which relations are visible, which aliases refer to them, and which columns they expose. Unqualified ambiguous names must not be guessed silently.

SELECT p.player_id, i.item_id
FROM player AS p
JOIN item AS i ON i.owner_id = p.player_id
WHERE p.player_id = 17;

The aliases define local names. The binder resolves each reference to an attribute in a specific input. A subquery introduces another scope, and a correlated reference can refer to an outer scope under the language’s rules. Rewriting those scopes incorrectly can change query meaning before any physical operator runs.

The catalog provides schemas, types, constraints, indexes, functions, and statistics. Catalog data is itself database state. A concurrent schema change must not leave a query using half-old metadata. Engines use locking, versioning, invalidation, or other protocols to give planning and execution a coherent view.

Types and conversions

Type checking determines whether operations are valid and what result type they produce. Comparing an integer with a string may require an explicit or implicit conversion. Arithmetic can overflow. Numeric precision and scale affect money and aggregate results. Collation determines comparison and ordering for text.

Implicit conversions are convenient but can alter access paths. If an index stores one type while the query applies a function or cast to every indexed value, the ordinary index ordering may no longer directly satisfy the predicate. The optimizer must reason about the expression actually evaluated, not the developer’s informal expectation.

Functions also have semantic properties. A deterministic expression can be moved or precomputed under conditions that do not apply to a volatile function. An expression that raises an error may require care when reordering evaluation. A query front end should preserve enough information for later transformations to remain valid.

Nulls and three-valued logic

SQL comparisons involving null often produce unknown. A WHERE clause retains rows for which its predicate is true; false and unknown do not pass. This differs from treating null as an ordinary value equal to itself.

SELECT item_id
FROM item
WHERE owner_id = NULL;

The statement is syntactically valid but generally does not express the intended null test. IS NULL supplies the appropriate predicate. Similar subtleties affect NOT IN when its input can contain null, outer joins, and aggregate behavior. An optimizer that assumes ordinary two-valued boolean algebra can produce incorrect results.

A worked example makes the distinction concrete. Suppose values are 1, 2, and null. The predicate value = 1 yields true, false, and unknown respectively. Negating it yields false, true, and unknown. The null row does not suddenly pass the negated filter. This behavior must survive expression simplification and code generation.

From syntax to a logical plan

A logical plan expresses operations such as scan, filter, join, project, and aggregate without committing to a particular access algorithm. It separates semantic transformation from physical choice.

Project(player_id, item_id)
  Filter(player_id = 17)
    InnerJoin(item.owner_id = player.player_id)
      Relation(player)
      Relation(item)

The engine can later push the filter into an input and choose an index scan or hash join. Those alternatives must preserve bag multiplicity, null behavior, and observable semantics. Logical plans also carry output schemas so every parent knows what its children produce.

A three-table inner join has six left-deep table permutations before considering access paths and join algorithms. Four tables have twenty-four permutations. More general tree shapes and physical properties expand the search further. This combinatorial growth motivates the optimizer structures in Lessons 14 and 16, but the front end first needs a correct typed representation of every alternative’s meaning.

Authorization and planning

The engine checks whether the caller may access referenced objects and execute functions. Row and column restrictions may influence the plan or be enforced during execution. These checks must not disappear because a query is prepared, cached, or rewritten.

A prepared statement is associated with metadata and possibly security context. If the schema or relevant privileges change, the engine needs a rule for revalidation or invalidation. Reusing a plan under another tenant’s session without appropriate checks can leak data even when the original planning was correct.

Errors also need a policy. A diagnostic that reveals hidden object names or values can become an information channel. At the same time, overly vague errors make operations difficult. Security and observability should be designed together rather than choosing either unrestricted detail or no explanation.

Prepared execution and schema dependencies

Preparation can amortize parsing and planning across repeated calls. Parameter values are supplied later. A generic plan can avoid repeated planning work while being suboptimal for highly skewed values. A parameter-specific plan can adapt but adds planning cost and cache complexity.

Schema dependencies include table identity, column types, index availability, and function definitions. A schema name resolving to a new object after replacement is not necessarily the same dependency. Mature engines track object identities and invalidate dependent plans when necessary.

The failure scenario is a rolling deployment that introduces a column or changes a function while old prepared statements remain in use. A complete protocol must define whether the statement is recompiled, rejected, or continues against compatible metadata. Silent reinterpretation risks correctness. Lesson 41 treats this as a broader compatibility problem.

Follow one query from tokens to typed expressions

Consider a constructed report over player(player_id, region_id) and payment(payment_id, player_id, amount). It asks for regional totals above 1,000 currency units:

SELECT p.region_id, SUM(x.amount) AS total
FROM player AS p
JOIN payment AS x ON x.player_id = p.player_id
WHERE x.amount > 0
GROUP BY p.region_id
HAVING SUM(x.amount) > 1000;

Lexing recognizes identifiers, punctuation, and numeric literals. Parsing recognizes a join, a row predicate, grouping, an aggregate expression, and a group predicate. Binding resolves p and x to the two source relations. It resolves x.amount to a particular column identity and obtains its numeric type. Aggregate analysis establishes that region_id is a grouping key and that SUM(amount) is evaluated over each group’s qualifying rows.

The front end then creates a typed logical plan. The row filter belongs below aggregation because it excludes nonpositive payments before grouping. The HAVING predicate belongs above aggregation because it inspects the resulting group sum. The alias total is an output name whose visibility in other clauses follows the SQL dialect’s rules; it should not be treated as an arbitrary global variable.

Project(region_id, total)
  Filter(total > typed_literal(1000))
    Aggregate(group: region_id, total: SUM(amount))
      Filter(amount > typed_literal(0))
        Join(payment.player_id = player.player_id)
          BoundRelation(player_object_id)
          BoundRelation(payment_object_id)

This is a semantic representation, not an execution order dictated by the written clause order. A later optimizer might infer that some filters can move or an index can accelerate access. The front end’s job is to preserve enough identity, type, grouping, and null information for those decisions to be meaningful.

Scope determines what a name can mean

An alias establishes a name within a scope; it does not rename the underlying persistent object. In a query containing nested subqueries, the same text can name different columns in different scopes. A correlated reference deliberately reaches an outer scope when no valid local interpretation exists under the language rules. A binder usually maintains scope frames and resolves each name against the applicable frames in a defined order.

Suppose an outer query uses alias p for players and an inner subquery also declares p for payments. Inside the subquery, p.player_id refers to the local payment alias, not the outer player. A developer intending correlation can accidentally write a self-comparison. The syntax is valid and types may match, so the front end cannot always infer intent. Clear qualification and distinct aliases make the meaning reviewable.

Unqualified names can change meaning when schemas evolve. If an inner table gains a column whose name previously resolved to an outer reference, a newly prepared query can bind differently. Persistent prepared plans need dependency invalidation rules; new query text needs review of name resolution. Explicit qualification reduces the ambiguity, though it does not solve every compatibility issue.

Wildcard expansion is another binding-time choice. SELECT * depends on the current source schema and can change output shape after a column addition. Client decoders expecting fixed column positions can fail even when the query still executes. Online schema evolution is easier when important interfaces name output columns and define their types explicitly.

Null behavior extends through aggregates and subqueries

COUNT(*) counts rows. COUNT(column) counts nonnull values of that expression. If three rows contain amounts 10, null, and 20, the two counts are three and two respectively. SUM(amount) ignores the null in this example and returns 30. Over an empty qualifying set, aggregate results have specific semantics rather than all defaulting to zero. The binder and aggregate implementation must agree on result nullability and type.

NOT IN is a useful counterexample to ordinary set intuition. Suppose candidate value 5 is compared against subquery values 1 and null. 5 = 1 is false, while 5 = NULL is unknown. The membership result is unknown, and negating it remains unknown, so a WHERE clause does not retain the row. A simple “no equal key found” implementation would incorrectly return true.

A correlated NOT EXISTS asks whether any row satisfies its explicit predicate. It often expresses an absence condition more directly, but it is not mechanically interchangeable with every NOT IN. The query’s treatment of null candidates and null subquery values must be preserved. Lesson 14 shows how this distinction constrains decorrelation.

An engine’s internal expression representation can carry nullability information and use null-aware operators. An optimizer can simplify an operation when trusted constraints prove a value cannot be null. If it assumes that proof without a valid constraint or ignores nulls introduced by an outer join, it can make an incorrect rewrite. Semantic metadata needs provenance, not just a boolean guessed from a column declaration.

Parameter binding separates values from grammar

Suppose an application wants a player by name. Building ... WHERE display_name = ' followed by user text and another quote makes the text part of SQL grammar. Escaping mistakes can permit syntax injection. A parameterized query parses a fixed grammar containing a value placeholder, then sends the value separately. Quotes and comment markers inside the parameter remain data under the protocol’s binding rules.

The parameter still needs a type, size limit, and authorization context. A ten-megabyte name parameter can exhaust resources even though it cannot inject syntax. A parameter naming another player’s identifier can be perfectly typed but unauthorized. Parameter binding solves a grammar boundary; input validation and permission checks solve different boundaries.

Identifiers require separate treatment. A placeholder for a value generally cannot stand for a table name, sort direction, or arbitrary expression. An application offering dynamic sort choices can map a small allowed set of choices to predefined SQL fragments. Treating an untrusted identifier as an ordinary bound scalar either fails or encourages unsafe fallback interpolation. The interface should make the allowed structural variation explicit.

Type inference also affects planning. If a parameter’s type is unknown until execution, the engine must choose a rule for resolving overloaded operators and casts. A cast applied to every stored key can interfere with an index path; converting the parameter to the column type can have a different cost and error behavior. Correct typing comes before deciding which form is faster.

Catalog consistency is a transaction-like requirement

Planning reads several related metadata objects: a table’s columns, an index’s key definition, a function’s signature, and possibly privileges. If a concurrent migration changes these independently from the planner’s perspective, it can build a plan whose parts never coexisted. A coherent catalog view prevents that impossible combination.

One strategy holds schema-level protection while planning and executing relevant work. Another uses catalog versions and validates dependencies before execution. A cached plan can record object identities and invalidate when those objects change. These mechanisms have different contention and cache-reuse costs, but all need a safe rule when a dependency disappears.

Dropping and recreating a table with the same textual name does not necessarily recreate the same object. A plan retaining the old object’s column offsets cannot simply point at the new table because the name matches. Object identity, schema version, and persistent format are separate pieces of metadata. Plan invalidation must follow the actual dependencies.

This is also relevant to function definitions. Replacing a function with behavior inconsistent with a cached assumption can invalidate constant folding or security properties. If the function was treated as immutable, the planner may have precomputed a value. Accurate declarations and dependency management make those optimizations safe. A function’s convenient signature is not its complete semantic contract.

Front-end resource limits protect the engine before execution

An attacker does not need a successful table scan to consume database resources. A statement with millions of tokens, deeply nested expressions, or a combinatorial number of joins can stress parsing and planning. Limits on message bytes, expression depth, parameter count, and planning effort bound this work. Controlled errors preserve service availability while explaining which limit was reached.

A prepared-statement cache can itself become a resource attack if each unique text creates a retained plan indefinitely. A bounded cache needs an eviction policy and accounting by session or tenant. Large literal variations can defeat reuse; parameterization can reduce that churn when it matches the query semantics. Evicting a cached plan must respect any execution still using it.

Error handling also needs memory discipline. Building a diagnostic by echoing an enormous query can allocate more than the rejected parse did. Logs can expose secrets embedded in literals. Truncation, redaction, and stable error codes help operators investigate without reproducing sensitive data unnecessarily. The same security principles apply to query text captured by profiling and tracing.

A bind-time error can be the correct fast path

Consider an invalid query referring to an ambiguous player_id in two joined relations. Rejecting it before scanning data is both correct and efficient. Silently selecting the first matching column would make the behavior dependent on internal relation order. Likewise, rejecting an unauthorized column before execution is preferable to fetching its values and hiding them afterward.

Some errors depend on actual data and cannot be resolved at bind time. Converting a particular string to an integer can fail only when that value is evaluated. Division by a column can encounter zero in one row. The front end should preserve error semantics without pretending that all errors are statically knowable. Later optimization must follow the database language’s rules rather than assume procedural left-to-right evaluation of every predicate.

The useful distinction is between syntactic validity, semantic validity, permission, and successful execution on a particular snapshot. A query can pass the first three and still fail during storage access or arithmetic. Client protocols should expose the relevant scope so applications can decide whether to fix the query, retry a transaction, or investigate an infrastructure failure.

Case analysis: different internal representations, common obligations

SQLite’s documented architecture uses a virtual machine for compiled statements, while PostgreSQL describes a parser, rewrite, planning, and execution path. Those facts establish different internal execution representations; they do not establish a universal latency ranking. SQLite architecture, PostgreSQL query path

A short prepared lookup benefits when front-end work is amortized. A new complex report may justify substantial analysis before execution. A client-facing realtime function may expose generated bindings rather than general SQL, reducing some language ambiguity while still requiring typed arguments, authorization, schema compatibility, and bounded work. The same semantic obligations survive a change in user-facing interface.

The front end is therefore part of engine correctness and capacity, not merely a parser placed before the interesting algorithms. It determines which operation the user actually requested and what assumptions every later stage may rely on.

Preserve error locations while resolving identity

SQL bytes
  -> tokens [source offsets]
  -> syntax tree [clause and expression spans]
  -> bound tree [object IDs, attribute IDs, scopes]
  -> typed tree [operators, casts, nullability]
  -> logical plan [schemas, dependencies, privileges]
  -> optimizer alternatives

The pipeline separates textual position from semantic identity. A name can resolve to a stable object identifier while the compiler retains the original source span for an error message. Losing that span during rewriting can make a useful type error point to generated internal text the author never wrote. Preserving provenance supports diagnostics without changing query semantics.

A rejected parse can identify an unexpected token. A binding error can identify an ambiguous name and the allowed qualification. A type error can identify incompatible operands. A permission error can use a deliberately restricted diagnostic policy. Distinguishing these stages helps clients classify permanent query problems separately from transient transaction conflicts or storage failures.

Some stages can be combined in a real implementation, and views or row policies can introduce further rewrites. The diagram is an explanatory decomposition, not a required sequence of separate processes. Whatever the representation, every stage must retain the facts the next stage needs: scope, type, object identity, output schema, and applicable trust boundaries. The result is a plan whose meaning is established before the optimizer starts searching for a cheaper way to produce it.

Case connection and design conclusion

PostgreSQL documents a query path through parser, rewriting, planner, and executor. SQLite compiles SQL into a bytecode program executed by its virtual machine. These are concrete implementation choices around a shared requirement: establish a valid meaning before choosing or running an access strategy.

A useful front-end design produces a typed, dependency-aware logical plan and clear errors. It bounds work on untrusted input and makes authorization part of the execution contract. Lesson 14 then asks which transformations can reduce work without changing that meaning.

Sources and further reading

• PostgreSQL 18 query path
• SQLite architecture

Course index · Lesson plan