ch12Optimiser rules

What you build: Rules that push each condition down to its table and into the scan, read only the columns used, and turn a sort under a limit into a top-k, rebuilding every hand-written plan.

The question#

Which rewrites of a plan save work whatever the data, and what does each one save?

ch11 built the plain plan: correct, and reading the whole of every file it names. Every plan the book wrote by hand before it was cheaper, and each was cheaper in a way a person could see from the query’s text alone: read only these columns, test this condition in the scan, keep ten rows instead of sorting all of them. This chapter teaches the planner to see the same things, as rules that rewrite the logical plan, and counts what each rule saves.

Observe#

The query is ch11’s, the enterprise orders:

-- 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 turn its rules off by name. Here it runs the query with every rule, then without the rule that moves filters down the plan, then without the rule that removes columns nothing uses:

1. Without filter_pushdown, the segment is tested above the customers’ scan. The scan hands up every customer, and a filter drops most of them. The bytes grow too: the scan must now read the segment column, to hand it up to the filter.
2. Without unused_columns, nothing changes. DuckDB’s binder asked each scan for only the columns the query names in the first place, so this rule had nothing to remove here. It matters after other rules have run, when a column that was needed no longer is.
3. Some of the moving happens anyway. Even without filter_pushdown, both conditions sit below the join, on their own tables. DuckDB builds its joins in a later step that places conditions too, and turning one rule off does not undo the other’s work.

A rule that rewrites a plan into one that gives the same rows for less work is a rewrite rule. The part of the planner that applies its rules, and later chooses between plans, is its optimiser. The rules here share one property: each makes the plan cheaper, or leaves it as it was, whatever the data holds. They can be applied without knowing anything about the files.

Predict, then measure#

Your planner gets three rules. The first moves each condition down the plan as far as its columns allow: below a join to the table it reads, and into the scan if it compares a column with a constant. The second has each table read only the columns something above it uses. The third turns a sort with a limit above it into ch09’s top-k.

Predict the bytes the enterprise orders read with the first rule alone, the second alone, and both. The panel shows the plain plan’s bytes beside each.

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

• Moving the filters saves no bytes. The customers’ file is one row group, so testing the segment in the scan skips nothing, and the orders’ condition is an expression the scan cannot test. But far fewer rows reach the join: the counters show it.
• Pruning the columns saves bytes, and no rows. Each scan reads the columns the query uses, and hands up every row it did before.
• Together they save both. Each rule saves a different thing, and the rules do not get in each other’s way.

Time the same four plans, run by your engine in your browser:

• Time follows the bytes here, more than the rows. Your engine spends most of a plan’s time decoding in its scans, as ch01’s profile showed, so pruning the columns saves the most, and moving the filters, which leaves the scans as they were, saves little.
• Both rules make the quickest plan. In an engine whose joins cost more than its scans, the rows the filters keep from the join would be worth more; the counters say what each rule saves, and the time what that is worth in this engine.

Building it#

Conditions, as far down as they go#

A condition joined by AND holds only where each of its parts holds, so each part can be tested on its own, anywhere below the filter that its columns are available. Each such part is a conjunct. The rule splits every filter into its conjuncts and pushes each down, one step at a time:

def push_filters(node: Node) -> Node:
    """The plan with every filter's conditions moved as far down as their columns allow."""
    node = replace(node, children=[push_filters(c) for c in node.children])
    if not isinstance(node, Select):
        return node
    below = node.children[0]
    for part in conjuncts(node.condition):
        below = _push(below, part)
    return below

def _push(node: Node, condition: Expression) -> Node:
    """``node`` with ``condition`` tested as low inside it as its columns allow."""
    match node:
        case Join():
            for i, side in enumerate(node.children):
                if columns_in(condition) <= set(output(side)):
                    children = list(node.children)
                    children[i] = _push(side, condition)
                    return replace(node, children=children)
        case Get() if (comparison := _in_scan(condition, node)) is not None:
            return replace(node, filters=[*node.filters, comparison])
    return Select(children=[node], condition=condition)

Delete the case Join(): branch and the lines under it, so that no condition passes a join, and run the panel’s report on your edit: every row of both tables reaches the join again, and the panel says your edit changed the answer.

A conjunct whose columns are all on one side of a join goes to that side. One that reads both sides, such as a condition on a customer’s segment or an order’s amount, stays above the join.

Into the scan#

At a table, the conjunct goes into the scan itself if it compares one column with a constant, which is what ch03’s scan can test, and skip row groups with. Anything else stays as a filter directly above the scan:

def _in_scan(condition: Expression, get: Get) -> Comparison | None:
    """``condition`` as a comparison the scan can test itself, if it compares one column of the
    table with a constant; otherwise None, and a filter above the scan tests it."""
    if not (isinstance(condition, Call) and condition.op in MIRRORED):
        return None
    match condition.args:
        case (Column(name), Literal(value)):
            op = condition.op
        case (Literal(value), Column(name)):
            op = MIRRORED[condition.op]
        case _:
            return None
    prefix = f"{get.table.alias}." if get.qualified else ""
    return Comparison(name.removeprefix(prefix), op, value)

Columns, from the top down#

The second rule walks down from the top, carrying the columns that the steps above need. Each step adds what it reads itself: a filter its condition’s columns, a join its keys, a sort its keys. At a table, the scan keeps only the columns in the set:

def prune_columns(node: Node, needed: set[str] | None = None) -> Node:
    """The plan with each table reading only the columns some step above it uses. ``needed`` is
    what the steps above ``node`` use of its output; at the top, all of it."""
    if needed is None:
        needed = set(output(node))
    match node:
        case Get(table=t, columns=columns, qualified=qualified):
            name = (lambda c: f"{t.alias}.{c}") if qualified else (lambda c: c)
            kept = [c for c in columns if name(c) in needed]
            # A step that counts rows needs no column, but a scan must read one to count them.
            return replace(node, columns=kept or columns[:1])
        case Compute(items=items):
            kept = [(n, e) for n, e in items if n in needed]
            below = set().union(*(columns_in(e) for _, e in kept))
            return replace(node, items=kept, children=[prune_columns(node.children[0], below)])
        case Select(condition=condition):
            below = needed | columns_in(condition)
        case Join(left_key=left, right_key=right):
            below = needed | {left, right}
            return replace(node, children=[prune_columns(c, below & set(output(c))) for c in node.children])
        case Group(keys=keys, aggregates=aggregates):
            below = set(keys) | {c for _, _, c in aggregates if c is not None}
        case Order(keys=keys) | Top(keys=keys):
            below = needed | {c for c, _ in keys}
        case _:
            below = needed
    return replace(node, children=[prune_columns(c, below) for c in node.children])

A count(*) needs no column at all, but a scan counts rows by reading something, so it keeps one.

A sort and a limit#

The third rule is the smallest. A limit directly above a sort becomes one step that keeps the first rows, which the planner runs as ch09’s top-k:

def top_k(node: Node) -> Node:
    """The plan with every limit directly above a sort turned into one top-k step."""
    node = replace(node, children=[top_k(c) for c in node.children])
    if isinstance(node, Take) and isinstance(node.children[0], Order):
        order = node.children[0]
        return Top(children=order.children, keys=order.keys, n=node.n)
    return node

Your planner’s plan for the enterprise orders, after all three rules:

Compare#

Every plan the book wrote by hand, beside the plan your rules make from the text alone:

• The rules rebuild every plan the book wrote by hand. From ch01’s filter and projection to ch09’s top-k and this part’s join, the bytes are the same, from nothing but the query’s text.
• Except the page index. ch04’s scan read the page index because its plan told it to. That is a way of scanning a file, not a rewrite of the plan, and the rules leave scans as ch03 built them. DuckDB 1.1.2 makes the same choice, as ch04 found.
• Every rewritten plan gives DuckDB’s rows. The book’s tests run each query through all three rules and compare the rows with DuckDB’s.

What this cannot tell you#

• How many rules a real optimiser has. DuckDB’s has dozens, applied in a fixed order: it folds constants, pulls filters up before pushing them down, removes duplicate work, rewrites subqueries into joins, and more. Three rules cover the book’s queries.
• Whether the order of rules matters. For these three, it does not. For a larger set it does: one rule can open the way for another, and optimisers apply some rules more than once.
• What rules cannot see. No rule here knows how big a table is, how many rows a condition keeps, or which side of a join is smaller. Those choices need statistics, which is the next chapter’s subject.

What this means for your design#

• Write conditions as a column against a constant. quantity > 2 can be tested in the scan and used to skip row groups; quantity + 1 > 3 cannot, unless the optimiser rewrites it, as problem 12.1 does. DuckDB rewrote it in ch06; a smaller engine may not.
• Keep conditions on one table where you can. A condition that reads two tables waits above their join, which sees every pair. Problem 12.3 measures one.
• Check the plan for your conditions. EXPLAIN shows where each condition ended up: in a scan’s filters, in a filter above it, or above a join.
• Do not hand-optimise the text. Moving a condition next to its table in the WHERE clause changes nothing: the rules put it there anyway.

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.

12.1 Move the constants. Write move_constants: rewrite quantity + 1 > 3 as quantity > 2, so that the scan can test it. The graders put your rewrite before the book’s rules and check that every condition they give it reaches the scan, with DuckDB’s rows. They also check your rewrite against the original on every order, for many random conditions, and that it leaves alone what it cannot move.

12.2 Across the join. Write across_the_join: a rule that copies a condition on one side’s join key to the other side’s key, since the two are equal in every joined row. The graders run it before push_filters, and check that both tables’ scans test the key, that the orders’ scan hands up fewer rows, and that the rows are DuckDB’s.

12.3 Diagnose the slow report. No test. A report wants the orders of enterprise customers, and every large order whoever placed it, in one query:

-- ch12, problem 12.3: the orders of enterprise customers, or any order over
-- 2000, with each customer's country. One condition that reads both tables.
SELECT o.order_id, c.country, o.amount
FROM 'fixtures/orders-sorted.parquet' AS o
JOIN 'fixtures/customers.parquet' AS c ON o.customer_id = c.customer_id
WHERE c.segment = 'enterprise' OR o.amount > 2000;

Your rules and DuckDB both leave its condition above the join:

Why can neither move the condition to a table? What does the join do as a result? How would you write the report so that each condition can reach its own table’s scan, and what must you take care of when you combine the two answers? A good answer explains why a condition joined by OR is not a conjunct, and proposes two queries whose rows are combined without counting an order twice.

Where to go next#

• Rules and their order. Goetz Graefe, The Cascades Framework for Query Optimization, IEEE Data Engineering Bulletin, 1995: rules as the unit of an optimiser, and how to apply many of them.
• The rules of a real engine. DuckDB’s source, in src/optimizer/: filter_pushdown.cpp, remove_unused_columns.cpp and topn_optimizer.cpp are this chapter’s three rules, and optimizer.cpp lists the order DuckDB applies all of them in.
• Why optimisers are hard. Viktor Leis and others, How Good Are Query Optimizers, Really?, VLDB 2015: what goes wrong when rules are not enough, and plans must be chosen.

Built from commit dc21108.