ch11From SQL to a logical plan

What you build: A tokenizer and a recursive-descent parser for the book's SQL, binding against each file's schema, and a planner that builds the plain logical plan and the operators to run it.

The question#

How does an engine turn the text of a query into a plan it can run, and what does the plainest plan cost?

Every plan so far was written by hand. ch01 read DuckDB’s plan and built the same operators; each chapter since has added an operator and wired it in by hand, choosing the columns each scan reads and the conditions it tests. An engine does that for every query it is given, from nothing but the text. This chapter writes the first half of that work: reading the text, checking every name in it, and building the plan the text describes, in the plainest way. Then it measures what the plainest way costs.

Observe#

The query asks for the pricier orders of enterprise customers, with each customer’s country:

-- ch11, From SQL to a logical plan: the pricier orders of enterprise
-- customers, with each customer's country. A condition on each table, both
-- written after the join.
SELECT o.order_id, c.country, o.amount / o.quantity AS unit_price
FROM 'fixtures/orders-sorted.parquet' AS o
JOIN 'fixtures/customers.parquet' AS c ON o.customer_id = c.customer_id
WHERE c.segment = 'enterprise'
  AND o.amount / o.quantity > 100;

DuckDB can show the plan it built from the text, before it changed anything:

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│        Expressions:       │
│          order_id         │
│          country          │
│         unit_price        │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│        Expressions:       │
│      (segment = CAST(     │
│ 'enterprise' AS VARCHAR)) │
│  ((amount / CAST(quantity │
│  AS DOUBLE)) > CAST(100 AS│
│          DOUBLE))         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│      COMPARISON_JOIN      │
│    ────────────────────   │
│      Join Type: INNER     │
│                           ├──────────────┐
│        Conditions:        │              │
│(customer_id = customer_id)│              │
└─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│        PARQUET_SCAN       ││        PARQUET_SCAN       │
│    ────────────────────   ││    ────────────────────   │
└───────────────────────────┘└───────────────────────────┘

And the plan it runs:

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│          order_id         │
│          country          │
│         unit_price        │
│                           │
│         ~800 Rows         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         HASH_JOIN         │
│    ────────────────────   │
│      Join Type: INNER     │
│                           │
│        Conditions:        │
│ customer_id = customer_id ├──────────────┐
│                           │              │
│        Build Min: 1       │              │
│      Build Max: 1000      │              │
│                           │              │
│         ~800 Rows         │              │
└─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│           FILTER          ││       PARQUET_SCAN        │
│    ────────────────────   ││    ────────────────────   │
│  ((amount / CAST(quantity ││         Function:         │
│    AS DOUBLE)) > 100.0)   ││        PARQUET_SCAN       │
│                           ││                           │
│                           ││        Projections:       │
│                           ││        customer_id        │
│                           ││          country          │
│                           ││                           │
│                           ││          Filters:         │
│                           ││  segment='enterprise' AND │
│                           ││     segment IS NOT NULL   │
│                           ││                           │
│         ~4000 Rows        ││         ~200 Rows         │
└─────────────┬─────────────┘└───────────────────────────┘
┌─────────────┴─────────────┐
│       PARQUET_SCAN        │
│    ────────────────────   │
│         Function:         │
│        PARQUET_SCAN       │
│                           │
│        Projections:       │
│        customer_id        │
│           amount          │
│          quantity         │
│          order_id         │
│                           │
│        ~20000 Rows        │
└───────────────────────────┘

1. The first plan follows the text. A projection for the SELECT list, a filter for the WHERE, a join for the JOIN, and a scan for each table, in the order SQL says a query means: join the tables, keep the rows, compute the columns.
2. Its scans test nothing. Both conditions wait in the filter above the join, which sees every pair of order and customer.
3. Every name is resolved and every type is explicit. segment and amount lost their tables’ names, because DuckDB has already worked out which table each came from. DuckDB also wrote down each type it must convert: quantity becomes a DOUBLE for the division, and the 100 too, to be compared with a DOUBLE.
4. The plan it runs is another plan. The segment is tested inside the customers’ scan, the price in a filter on the orders alone, below the join, and each scan reads only the columns it needs. The rows out are the same; the work is not.

The first plan says what the query means, and nothing about how to run it: it is a logical plan, a tree of steps such as join, filter and read a table, each saying what it hands up. The plan an engine runs is its physical plan, from ch01. Between the two, DuckDB rewrote the logical plan, and rewriting is the next chapter’s subject. This chapter builds the logical plan and runs it as it stands.

Predict, then measure#

Your planner builds the plain plan. Each table becomes a scan of every column, the conditions become one filter above the scans and the join, and the SELECT list becomes a projection at the top.

Predict the bytes the plain plan reads for three queries: ch01’s returned orders, ch03’s fortnight in March, and this chapter’s enterprise orders. Beside each, the panel shows what the plan written by hand for that query read.

The panel draws what your engine counted when the book was built. Its button runs the same plans again in your browser.

• The plain plan reads the whole file, whatever the query asks. Every column of every row group, for the returned orders and for the fortnight alike: the query’s text changes nothing the scan does.
• The plans written by hand read less, in the ways Part II built. They read only the columns they use, test conditions inside the scan, and skip the row groups the file’s statistics rule out.
• The chart widens the fortnight. The plain plan reads the same bytes for a day and for most of the year. The hand-written plan reads a row group more each time the window reaches one, and still reads only three columns.
• Every plain plan gives the right rows. A plan’s cost and its answer are separate things. The planner’s first duty is the answer, and everything after this chapter is about cost.

Building it#

Tokens#

The text arrives as characters. The parser’s first step cuts it into tokens: the words, numbers, strings and operators the grammar is made of, with the spaces and comments dropped. One regular expression names each kind:

TOKEN = re.compile(
    r"""\s*(?:
        (?P<comment>--[^\n]*)
      | (?P<number>\d+\.\d*|\d*\.\d+|\d+)
      | (?P<string>'(?:[^']|'')*')
      | (?P<quoted>"(?:[^"]|"")*")
      | (?P<word>[A-Za-z_][A-Za-z_0-9]*)
      | (?P<op><=|>=|<>|!=|[-+*/=<>(),.;])
    )""",
    re.VERBOSE,
)

#: The words that are part of the grammar, not names: a column may not be called ``from``.
KEYWORDS = {
    "select", "from", "where", "group", "by", "order", "limit", "as", "join", "inner", "on",
    "and", "or", "not", "asc", "desc", "date", "true", "false", "null", "between", "in",
}  # fmt: skip

A word is a keyword, such as SELECT, or a name, such as amount: the keywords are listed, and anything else is a name. A string keeps its quotes until the parser reads it, so 'returned' is never mistaken for a column.

Recursive descent#

The parser reads the tokens by recursive descent: a method for each kind of phrase in the grammar, each calling the methods for the phrases inside it. A query is a SELECT list, a table, and optional clauses; a condition is an expression. The expressions carry SQL’s precedence, one method for each level, loosest first. Each method reads its operands by calling the next, tighter one, so a tighter operator is grouped first:

    def disjunction(self) -> Expression:
        left = self.conjunction()
        while self.is_word("or"):
            self.take()
            left = Call("or", (left, self.conjunction()))
        return left

    def conjunction(self) -> Expression:
        left = self.negation()
        while self.is_word("and"):
            self.take()
            left = Call("and", (left, self.negation()))
        return left

    def negation(self) -> Expression:
        if self.is_word("not"):
            self.take()
            return Call("not", (self.negation(),))
        return self.comparison()

    def comparison(self) -> Expression:
        left = self.sum()
        if self.is_op("=", "!=", "<>", "<", "<=", ">", ">="):
            op = self.take().text
            left = Call("!=" if op == "<>" else op, (left, self.sum()))
        return left

    def sum(self) -> Expression:
        left = self.product()
        while self.is_op("+", "-"):
            op = self.take().text
            left = Call(op, (left, self.product()))
        return left

    def product(self) -> Expression:
        left = self.unary()
        while self.is_op("*", "/"):
            op = self.take().text
            left = Call(op, (left, self.unary()))
        return left

Swap "or" and "and" between disjunction and conjunction, in the test and in the call, so that AND is the looser, and run the engine’s tests on your edit: a = 1 OR b = 1 AND c = 1 now reads as (a = 1 OR b = 1) AND c = 1, and the precedence tests say so.

What comes out is the query’s syntax tree: the text’s parts, as the text wrote them, in ch06’s expression trees and a Query that holds the rest. It says which tables and which conditions, and nothing about whether they make sense.

Binding#

Binding checks that they do. The planner reads each table’s schema from its file’s footer, and resolves every column the query names to the table it belongs to. A name no table has is an error; so is a name two tables share, unless the query says which:

    def resolve(self, name: str) -> str:
        """A column as the query wrote it, as the plan names it: plain for a query of one table,
        ``alias.column`` for a join, where two tables may share a name."""
        alias, _, column = name.rpartition(".")
        if alias and alias not in self.columns:
            raise PlanError(f"no table is called {alias!r}")
        owners = [alias] if alias else [a for a, cs in self.columns.items() if column in cs]
        if not owners or column not in self.columns[owners[0]]:
            raise PlanError(f"no table has a column {name!r}")
        if len(owners) > 1:
            raise PlanError(f"{column!r} is in {' and '.join(owners)}: say which, as {owners[0]}.{column}")
        return f"{owners[0]}.{column}" if self.joined else column

In a join, the planner names each column for its table, o.customer_id and c.customer_id, so the two stay apart all the way up the plan.

The plain plan#

The planner then builds the logical plan in the order SQL defines a query’s meaning. Read every table, whole. Join them as the text joins them. Keep the rows the WHERE holds for. Group, if the query groups. Compute the SELECT list. Sort, then limit:

def logical_plan(root: Path, query: Query) -> Node:
    """The query's meaning as a logical plan, built in the order SQL defines it."""
    tables = [query.table, *(j.table for j in query.joins)]
    scope = Scope({t.alias: columns_of(root, t) for t in tables}, joined=bool(query.joins))
    if len(scope.columns) != len(tables):
        raise PlanError("two tables have the same name: give each its own alias")
    gets = [Get(table=t, columns=scope.columns[t.alias], qualified=scope.joined) for t in tables]

    plan: Node = gets[0]
    for join, get in zip(query.joins, gets[1:], strict=True):
        on = scope.bind(join.on)
        if not (isinstance(on, Call) and on.op == "=" and all(isinstance(a, Column) for a in on.args)):
            raise PlanError(f"your planner joins on one column equal to another, not {join.on}")
        left, right = (a.name for a in on.args)
        if left.startswith(f"{join.table.alias}."):
            left, right = right, left
        plan = Join(children=[plan, get], left_key=left, right_key=right)
    if query.where is not None:
        plan = Select(children=[plan], condition=scope.bind(query.where))

    if query.star:
        items = [(c, Column(c)) for g in gets for c in output(g)]
    else:
        items = [(item.alias or name_of(item.expr), scope.bind(item.expr)) for item in query.items]
    if query.group_by or any(_aggregate(e) for _, e in items):
        plan, items = _grouped(plan, [scope.bind(e) for e in query.group_by], items)
    plan = Compute(children=[plan], items=items)

    if query.order_by:
        names = {n for n, _ in items}
        keys = []
        for e, descending in query.order_by:
            if not (isinstance(e, Column) and e.name in names):
                raise PlanError(f"your planner sorts by a column the query hands up, not {e}")
            keys.append((e.name, descending))
        plan = Order(children=[plan], keys=keys)
    if query.limit is not None:
        plan = Take(children=[plan], n=query.limit)
    return plan

Your planner’s logical plan for the chapter’s query, beside DuckDB’s first plan:

The same steps, in the same order. The two scans read every column their files hold.

Operators for the steps#

Each step of the logical plan becomes one of the operators the earlier chapters built. A read becomes a scan, and in a join a projection that renames its columns for its table; a filter evaluates ch06’s expression tree on each batch; a join becomes ch08’s hash join, built on the table the text names second:

def physical_plan(root: Path, node: Node) -> Operator:
    """The engine's operators for a logical plan: one for each step."""
    kids = [physical_plan(root, c) for c in node.children]
    match node:
        case Get(table=t, columns=columns, filters=filters, qualified=qualified):
            scan = Scan(root / t.path, columns, filters=filters)
            if not qualified:
                return scan
            # Two joined tables may share a column's name: each is renamed for its table.
            return Project(scan, {f"{t.alias}.{c}": partial(evaluate, Column(c)) for c in columns})
        case Select(condition=condition):
            return Filter(kids[0], str(condition), partial(evaluate, condition))
        case Join(left_key=left, right_key=right):
            columns = [("probe", c) for c in output(node.children[0])]
            columns += [("build", c) for c in output(node.children[1])]
            return HashJoin(kids[0], kids[1], left, right, columns)
        case Group(keys=keys, aggregates=aggregates):
            return HashAggregate(kids[0], keys, [Aggregate(n, f, c) for n, f, c in aggregates])
        case Compute(items=items):
            return Project(kids[0], {n: partial(evaluate, e) for n, e in items})
        case Order(keys=keys):
            return Sort(kids[0], keys)
        case Take(n=n):
            # The first rows as they come: ch09's top-k, with nothing to order them by.
            return TopK(kids[0], [], n)
        case Top(keys=keys, n=n):
            return TopK(kids[0], keys, n)
    raise PlanError(f"no operator for {node}")

A LIMIT has no operator of its own: that is problem 3.3’s, which you may have written. The planner runs it as ch09’s top-k with nothing to order by, which keeps the first rows it is given. It reads every row its child hands up to do so, where problem 3.3’s limit stops asking.

The book’s tests plan every query in queries/ that reads one plain file, and require DuckDB’s rows for each. The three that read many files, or pass read_parquet options, are refused with a message that says why, and so are the few in later chapters that ask one question inside another, which this parser does not read.

Compare#

Your plain plan beside DuckDB’s, run:

• Both hand up the same rows. The plain plan is a correct plan.
• DuckDB read fewer bytes and handed fewer rows out of its scans. Its binder asks each scan for only the columns the query names, four of the orders’ seven, where your plain planner asks for all of them. And a rewrite moved the segment into the customers’ scan, which kept only the enterprise customers.
• DuckDB’s orders’ scan handed up a few orders fewer than there are. The join’s build side told the scan, as it ran, the smallest and largest customer id it held: ch08’s Build Min and Build Max. The few orders of customers outside that range never left the scan.
• DuckDB has no renaming projections. Its binder refers to a column by the number of its table and its place in that table, not by a name, so two tables’ customer_id never collide. Your planner renames them, and pays a projection for each table in a join.

What this cannot tell you#

• How much SQL DuckDB reads. Its parser is derived from PostgreSQL’s, and reads subqueries, window functions, common table expressions and much more. Your parser reads the book’s queries and little else.
• What planning costs. The counters count what a plan does, not the work of making it. For these queries it is small. For a query that joins many tables, choosing a plan can cost more than running it.
• How DuckDB types an expression. DuckDB’s binder decides each expression’s type before anything runs, and writes a cast wherever types differ. Your planner leaves types to Arrow’s kernels, which decide as each batch arrives.
• How a real parser reports mistakes. Yours stops at the first token it did not expect. Production parsers recover and report several errors at once, with a caret under each.

What this means for your design#

• Read both of DuckDB’s plans. PRAGMA explain_output = 'all' before EXPLAIN shows the plan as bound and the plan as rewritten. What moved between them is the rewriting’s work, and what did not move is what it could not do.
• Qualify every column in a join. An unqualified name that one table has today is an error the day another table gains a column of the same name.
• SELECT * asks for every column. In a plan with no rewriting, every column is read, held and handed up. A planner may prune the ones nothing uses, but only if it can see that nothing does.
• Write the query for its meaning, then read the plan. The text says what you want. How it runs is the planner’s choice, and the only way to know what it chose is to look.

Key takeaways#

Problems#

There are three problems. The first two are code with tests; the third is a slow query to diagnose, with no test. Write your answers to the first two in the workbench, and run the graders there. Your answers stay in this browser, and Reset to the stubs starts again.

11.1 Two more comparisons. Teach the parser BETWEEN and IN, with or without NOT, by writing its comparison method. Return a tree of the comparisons the engine already evaluates, so that nothing after the parser changes. The graders parse a range of conditions with your parser, run them through the book’s planner, and compare the rows with DuckDB’s. They also check that x BETWEEN a AND b AND c leaves the last AND to the condition around it.

11.2 Numbers for names. Write resolve_ordinals: bind GROUP BY 1 and ORDER BY 2 DESC, which name items of the SELECT list by their place in it, to what they name. The graders plan queries that group and sort by position, and compare the rows with DuckDB’s.

11.3 Diagnose the slow engine. No test. A colleague’s engine plans every query the plain way, and every answer it gives is right. Its dashboard runs five of the book’s queries, which you have also seen planned by hand:

For each query, which step of the plain plan does work the hand-written plan does not? What rewrite of the logical plan would remove it? Which of those rewrites need only the query’s text, and which need to know something about the data? A good answer finds the columns, the conditions and the sort, and notices which choices only statistics can make.

Where to go next#

• Parsing. Robert Nystrom, Crafting Interpreters, chapters 4 to 6: tokens, syntax trees and recursive descent, precedence level by level.
• The logical and the physical. Goetz Graefe, Query Evaluation Techniques for Large Databases, ACM Computing Surveys, 1993: the separation this chapter keeps, and the operators on both sides of it.
• A query engine from the ground up. Andy Grove, How Query Engines Work, which builds a logical plan through a DataFrame interface before its SQL parser.
• DuckDB’s binder. DuckDB’s source, in src/planner/binder/, which turns the parser’s tree into the logical plan you observed.

Built from commit dc21108.