Name Resolution and Binding a Query to the Catalog

Between the parse tree and the planner sits a stage that every query must pass through and that almost no query language specification describes as a distinct component. It takes a tree full of uninterpreted strings and produces a tree in which every name points at a specific catalog object and every expression has a resolved type. This is binding, sometimes called semantic analysis or analysis proper. Its failure modes are the ones users meet most often: unknown column, ambiguous column, function does not exist, operator is not unique.

The reason the stage is large is that SQL’s namespace rules are more intricate than they appear, and because the type system permits implicit conversions whose legality depends on the operands. A binder that gets either wrong produces queries that resolve to the wrong object or that fail with an error message describing a candidate the user never wrote. Its input is the tree produced by SQL parsing, in which every name is still an uninterpreted string.

The range table and its namespaces

Every FROM item contributes an entry to a range table: one row per table, view, subquery, or function call in the query’s scope, each with a name, an optional alias, and a list of columns with types. The range table is the binder’s working model of “what is visible here”. A column reference resolves against it, in order of preference: an explicit qualifier (t.col), then an unqualified name matched against all entries.

Qualifiers themselves live in a namespace separate from column names. SELECT t FROM t is legal when t has a column named t, and the unqualified reference resolves to the column, because column names shadow table names in an unqualified reference. This shadowing is the source of one of the more confusing diagnostics in SQL: a query that selects the whole row when a column of the same name exists.

Aliases replace names rather than adding to them. FROM orders o makes orders unresolvable elsewhere in the query; the range table entry is named o and its column list comes from orders. Products differ on whether the original name remains usable, and the standard’s rule is that the alias is the exposed name, so relying on the original is not portable.

Lateral references complicate the model. In FROM a, LATERAL (SELECT ... WHERE x = a.x) b, the subquery’s scope includes the entries to its left. Without LATERAL, a subquery in FROM cannot see its siblings, which is why an unqualified reference to a sibling’s column is an error there and succeeds in a correlated subquery in WHERE. The binder tracks this by building the scope incrementally as it walks the from-list left to right.

Ambiguity is an error, not a guess

When an unqualified name matches columns in more than one range table entry, the standard requires an error. A binder that silently picks the first match produces queries whose meaning changes when a column is added to a table. The error message normally lists the candidates and their qualifiers, which is the only useful information the binder has.

The subtle case is when the candidates have different types. Some products resolve the ambiguity by preferring the candidate that requires no conversion, which makes the query succeed where the standard would reject it. That behaviour is a portability hazard: a query that runs on one system and fails on another, with the failure appearing only after a schema change.

Ambiguity also arises inside a single range table entry, for a subquery whose select list has two identically named output columns. SELECT * FROM (SELECT a.x, b.x FROM a, b) s produces a derived table with two columns named x, and any reference to s.x is ambiguous. Products that allow duplicate output names in a subquery force the outer query to rename them, which is why SELECT * over a join of tables with overlapping column names is legal at the top level but unusable as a derived table.

Views are expanded, not executed

A view is stored as a query, and the binder inlines it. Referencing a view in FROM substitutes its defining query into the range table, applies the view’s own column aliases, and continues resolution as if the user had written the definition. This is why predicates on a view can be pushed into the underlying tables by the planner: after expansion there is no view boundary left to cross.

Expansion has costs. A view built on another view expands recursively, and a chain of definitions multiplies the tree; a self-referential view is rejected rather than expanded forever. Column names in the view’s select list are resolved at creation time in some products and at reference time in others. The difference is observable: a view defined as SELECT * FROM t and referenced after t gains a column returns different columns depending on which policy the system follows. Products that store the expanded column list produce a stable view; products that re-expand produce a view that tracks the base table.

Security is the other reason expansion matters. A view’s definition runs with the privileges of its owner in many systems, and the binder is where that check is applied: after expansion, the reference to the base table is evaluated against the owner’s rights rather than the caller’s. That decision is a policy choice, and it is why view definitions are treated as schema objects with their own ownership.

Type resolution and the implicit cast decision

SQL’s operators are overloaded. + is defined for numeric pairs, for date plus interval, for interval plus date, and for a handful of other combinations; = is defined for nearly every pair of comparable types. The binder’s job is to select one operator instance from the catalog and insert casts where the argument types do not match exactly.

The rule is a preference ordering. An exact match wins. Otherwise the binder looks for a candidate where every argument is either an exact match or can be implicitly converted, and if several candidates qualify it applies a tie-break based on the “type category” and preferred-type rules. Numeric literals are a special case: an untyped literal has a type determined by context, so 1 in x + 1 takes the type of x when x is numeric, which is why 1 can be added to a smallint column without an explicit cast.

The consequence of getting this wrong is a query that resolves to a different function than intended. A string literal compared to a numeric column is the classic case: the comparison can be performed by converting the literal to a number or by converting the column to text. The first may fail at run time on a non-numeric value; the second cannot use an index on the column and turns the predicate into a sequential scan. Implementations choose one, document it, and users discover the other by reading the plan.

Casts are also where the binder can refuse. An implicit cast between two unrelated types is not permitted, and the error names the operator and the argument types it considered. This error is often the first sign that a column’s type is not what the user assumed, because the parse tree carried no type information at all.

Functions, aggregates, and window calls

Function name resolution runs through the same candidate search, with an extra wrinkle: a function may be resolved by name alone before its arguments are known, in which case the binder must defer. The common implementation collects candidate functions by name, resolves argument types, and then selects. A call with an unresolvable argument list reports every candidate it considered, which is why the diagnostic can run to several lines.

Aggregates need an additional check that the call appears in a clause where aggregation is legal, and that no aggregate is nested inside another aggregate. The second rule is syntactic in intent but not in form: sum(sum(x)) is rejected because the inner aggregate’s result is not a column, and detecting that requires walking the expression tree after resolution.

Window calls carry a OVER clause whose partition and ordering expressions are resolved in a scope of their own, one that includes the from-list but excludes the select list’s aliases in most products. A window’s ORDER BY is not the query’s ORDER BY, and the binder must keep the two separate: the first determines frame movement, the second determines final row order. Confusing them changes results without producing an error.

The output of binding is a tree the planner can cost: every column reference carries a type and a relation identity, every operator is a specific catalog entry, and every subquery is a separately bound unit with its own range table. Queries that reach this stage with correlated references have those references recorded explicitly, which is what allows later decorrelation to rewrite them as joins. That rewrite, and the choice among join orders, belongs to logical plan construction and rewrite rules.