अभिव्यक्ति

Building a simple Query Optimizer from scratch: Part 3

A Composable Rule Engine and Logical Rewrites

This series

Code for this series

This is Part 3 in a 6-part series on building a query optimizer from scratch in Java. Part 2 built the parser and logical plan builder.

At the end of the last post, we could parse SQL and produce clean, canonical logical plans. But those plans aren't optimized - filters sit above joins, the join order is whatever the user wrote, and projections happen at the very end. In this post, we'll build the machinery that transforms these plans into better ones.

The key ideas are simple. An optimization rule matches a pattern in the plan tree and replaces it with something equivalent but cheaper. A rule engine applies rules repeatedly until nothing changes. And the canonical form we established in Part 2 - one predicate per filter node - makes the rules themselves remarkably straightforward to write.

Designing the Rule interface

Let's revisit the Rule interface from Part 1, now that we're about to put it to work:

public interface Rule {
    String getName();
    boolean matches(LogicalNode node);
    LogicalNode apply(LogicalNode node);
}

The design is deliberately minimal. matches checks whether this rule can do anything useful with a given node - this is pattern matching. apply performs the actual transformation, returning a new subtree (or null if no transformation was actually made). The separation matters: the engine calls matches on every node in the tree, and apply only when there's a hit. This keeps rules easy to reason about - you can test matches and apply independently.

Each rule does exactly one thing. Predicate pushdown only pushes filters below joins. Projection pushdown only swaps projections past filters. Filter merge only combines adjacent filters. By keeping rules small and focused, they're easier to understand, test, and compose. The engine handles the orchestration.

The RuleEngine: fixpoint iteration

The rule engine's job is to apply rules until the plan stops changing. This is called fixpoint iteration - you keep going until you reach a fixed point where no rule produces a transformation.

public class RuleEngine {
    private final List<Rule> rules;
    private final int maxIterations;
    private boolean verbose = false;

    public RuleEngine(List<Rule> rules, int maxIterations) {
        this.rules = rules;
        this.maxIterations = maxIterations;
    }

    public LogicalNode optimize(LogicalNode plan) {
        LogicalNode current = plan;

        for (int iter = 1; iter <= maxIterations; iter++) {
            LogicalNode previous = current;

            for (Rule rule : rules) {
                current = applyRuleExhaustively(current, rule);
            }

            if (plansEqual(previous, current)) {
                break;  // fixpoint reached
            }
        }

        return current;
    }
}

The outer loop iterates up to maxIterations times. Each iteration applies every rule in sequence, and each rule is applied exhaustively - meaning it's applied to every node in the tree, not just the root. If a full pass through all rules produces no changes (checked by plansEqual), we've reached fixpoint and stop.

Why a limit? Some rule combinations can theoretically cycle - rule A undoes what rule B did. The maxIterations cap prevents infinite loops. In practice, our rules converge quickly (usually 1-2 iterations).

Bottom-up application

Rules are applied bottom-up: children are transformed before their parents. This is important because many rules need their children to be in a particular form. For example, predicate pushdown needs to see the filter's child as a join - but that child might itself need transformation first.

private LogicalNode applyRuleExhaustively(LogicalNode node, Rule rule) {
    // First, recursively apply to children (bottom-up)
    List<LogicalNode> newChildren = new ArrayList<>();
    boolean childrenChanged = false;

    for (LogicalNode child : node.getChildren()) {
        LogicalNode newChild = applyRuleExhaustively(child, rule);
        newChildren.add(newChild);
        if (newChild != child) {
            childrenChanged = true;
        }
    }

    // If children changed, create new node with updated children
    LogicalNode current = childrenChanged
        ? node.withChildren(newChildren)
        : node;

    // Now try to apply rule to current node
    if (rule.matches(current)) {
        LogicalNode transformed = rule.apply(current);
        if (transformed != null && transformed != current) {
            // Recursively apply rule to the transformed node
            return applyRuleExhaustively(transformed, rule);
        }
    }

    return current;
}

There's a subtle but important detail here. After a successful transformation, the method recursively applies the same rule to the result. Why? Because a transformation can create new opportunities. Pushing a filter past one join might expose it to another join below - the rule should keep pushing until it can't go any further.

Notice how withChildren is used when children change. This creates a new node with the transformed children while preserving the node's own properties (its predicate, join condition, etc.). Since our plan nodes are effectively immutable - we never mutate fields, only create new nodes - we can always compare the before and after states safely.

Predicate pushdown

This is the highest-impact optimization rule. The idea: if a filter sits above a join and only references columns from one side of the join, push the filter down to that side. Filtering early means fewer rows flow into the join, which can dramatically reduce the work the join has to do.

The pattern

public class PredicatePushdown implements Rule {
    @Override
    public boolean matches(LogicalNode node) {
        if (!(node instanceof LogicalFilter filter)) return false;
        return filter.getChild() instanceof LogicalJoin;
    }
}

The pattern is simple: a Filter whose child is a Join. Thanks to canonical form, we know each filter has exactly one predicate, so we only have to reason about one predicate at a time.

The transformation

The core logic analyzes which tables the predicate references and decides where to push:

@Override
public LogicalNode apply(LogicalNode node) {
    LogicalFilter filter = (LogicalFilter) node;
    LogicalJoin join = (LogicalJoin) filter.getChild();

    Expression predicate = filter.getPredicate();
    Set<String> referencedTables = getReferencedTables(predicate);
    Set<String> leftTables = getTablesInSubtree(join.getLeft());
    Set<String> rightTables = getTablesInSubtree(join.getRight());

    boolean canPushLeft = leftTables.containsAll(referencedTables);
    boolean canPushRight = rightTables.containsAll(referencedTables);

    if (canPushLeft && !canPushRight) {
        // Push to left child
        LogicalNode newLeft = new LogicalFilter(predicate, join.getLeft());
        return new LogicalJoin(newLeft, join.getRight(),
            join.getJoinType(), join.getCondition());
    } else if (canPushRight && !canPushLeft) {
        // Push to right child
        LogicalNode newRight = new LogicalFilter(predicate, join.getRight());
        return new LogicalJoin(join.getLeft(), newRight,
            join.getJoinType(), join.getCondition());
    }

    return null; // Can't push - references both sides
}

The algorithm has three outcomes. If the predicate only references tables on the left side of the join, it gets pushed down as a new Filter above the left child. If it only references the right side, same thing but on the right. If it references both sides - like a cross-table comparison that isn't the join condition - it stays put and apply returns null to signal no transformation.

Table reference analysis

The two helper methods walk trees to collect information. getTablesInSubtree finds all table names reachable from a node by recursing into children and collecting LogicalScan table names:

private Set<String> getTablesInSubtree(LogicalNode node) {
    Set<String> tables = new HashSet<>();
    collectTablesInSubtree(node, tables);
    return tables;
}

private void collectTablesInSubtree(LogicalNode node, Set<String> tables) {
    if (node instanceof LogicalScan scan) {
        tables.add(scan.getTableName());
    }
    for (LogicalNode child : node.getChildren()) {
        collectTablesInSubtree(child, tables);
    }
}

getReferencedTables walks the expression tree instead, collecting the table qualifiers from ColumnRef nodes:

private Set<String> getReferencedTables(Expression expr) {
    Set<String> tables = new HashSet<>();
    collectReferencedTables(expr, tables);
    return tables;
}

private void collectReferencedTables(Expression expr, Set<String> tables) {
    if (expr instanceof Expression.ColumnRef col) {
        if (col.tableName() != null) {
            tables.add(col.tableName());
        }
    } else if (expr instanceof Expression.BinaryOp binaryOp) {
        collectReferencedTables(binaryOp.left(), tables);
        collectReferencedTables(binaryOp.right(), tables);
    }
}

There's a limitation visible here: unqualified column references (where tableName is null) don't contribute to the set, so the rule can't push them. In practice, predicates that reference specific tables use qualified names (c.city = 'Seattle'), so this works well enough. A production system would resolve unqualified names against schemas during semantic analysis.

Seeing it in action

Here's what predicate pushdown does to a join query with two filters:

SQL: SELECT c.name, o.total
     FROM customers c
     INNER JOIN orders o ON c.id = o.customer_id
     WHERE c.city = 'Seattle' AND o.total > 100

BEFORE:
└── Project[name, total]
    └── Filter[(o.total > 100)]
        └── Filter[(c.city = 'Seattle')]
            └── Join[INNER, (c.id = o.customer_id)]
                ├── Scan[customers]
                └── Scan[orders]

AFTER:
└── Project[name, total]
    └── Join[INNER, (c.id = o.customer_id)]
        ├── Filter[(c.city = 'Seattle')]
        │   └── Scan[customers]
        └── Filter[(o.total > 100)]
            └── Scan[orders]

Both filters have been pushed below the join, each landing above the scan for the table it references. The join now receives pre-filtered inputs - only Seattle customers and only orders over 100 - which means far fewer row combinations to evaluate.

Notice how canonical form makes this work smoothly. Each filter is independent, so the rule processes them one at a time. The first application pushes c.city = 'Seattle' to the left. The second application pushes o.total > 100 to the right. Without canonical form, we'd need a single rule invocation to decompose a compound AND, analyze each piece, route some left and some right, and reassemble what's left. That's much harder to get right.

Multi-level pushdown

The recursive re-application in applyRuleExhaustively handles multi-level joins automatically. Consider a three-way join:

SQL: SELECT p.name, o.total, c.city
     FROM products p
     INNER JOIN orders o ON p.id = o.product_id
     INNER JOIN customers c ON o.customer_id = c.id
     WHERE p.category = 'Electronics' AND c.city = 'Seattle'

BEFORE:
└── Project[name, total, city]
    └── Filter[(c.city = 'Seattle')]
        └── Filter[(p.category = 'Electronics')]
            └── Join[INNER, (o.customer_id = c.id)]
                ├── Join[INNER, (p.id = o.product_id)]
                │   ├── Scan[products]
                │   └── Scan[orders]
                └── Scan[customers]

AFTER:
└── Project[name, total, city]
    └── Join[INNER, (o.customer_id = c.id)]
        ├── Join[INNER, (p.id = o.product_id)]
        │   ├── Filter[(p.category = 'Electronics')]
        │   │   └── Scan[products]
        │   └── Scan[orders]
        └── Filter[(c.city = 'Seattle')]
            └── Scan[customers]

The p.category = 'Electronics' filter starts above the outer join. In the first application, it gets pushed to the left child of the outer join (the inner join subtree, which contains products). But now it's a filter above an inner join - the pattern matches again. The second application pushes it past the inner join to sit directly above Scan[products]. Meanwhile, c.city = 'Seattle' gets pushed to the right child of the outer join in a single step, since Scan[customers] is right there.

Projection pushdown

Projection pushdown is about eliminating columns early. If a Project sits above a Filter, and the filter doesn't need any columns that the projection would remove, we can swap them - filter first, then project. This means fewer columns flow through the filter operator.

public class ProjectionPushdown implements Rule {
    @Override
    public boolean matches(LogicalNode node) {
        if (!(node instanceof LogicalProject)) return false;
        LogicalProject project = (LogicalProject) node;
        return project.getChild() instanceof LogicalFilter;
    }

    @Override
    public LogicalNode apply(LogicalNode node) {
        LogicalProject project = (LogicalProject) node;
        LogicalFilter filter = (LogicalFilter) project.getChild();

        Set<String> projectedColumns = getProjectedColumns(project);
        Set<String> filterColumns = getReferencedColumns(filter.getPredicate());

        // Can only swap if projection keeps all columns the filter needs
        if (!projectedColumns.containsAll(filterColumns)) {
            return null;
        }

        // Safe to swap: Filter -> Project becomes Project -> Filter
        LogicalNode newProject = new LogicalProject(
            project.getProjections(),
            project.getColumnNames(),
            filter.getChild()
        );
        return new LogicalFilter(filter.getPredicate(), newProject);
    }
}

The safety check is essential. If the SELECT list doesn't include a column that the WHERE clause references, we can't push the projection below the filter - the filter would try to evaluate a predicate against a column that's already been dropped. The getProjectedColumns and getReferencedColumns helpers extract column names from expressions to make this comparison.

In our simplified optimizer, this rule only pushes projections past filters. A full implementation would also push through joins (projecting away columns from one side of a join that aren't needed downstream), which is significantly more complex because it requires schema analysis of both join inputs.

Filter merge

This rule is the mirror image of the canonical form split from Part 2. After predicate pushdown has moved individual filters to their optimal positions, adjacent filters sitting on top of each other can be merged back into a single filter with an AND predicate:

public class FilterMerge implements Rule {
    @Override
    public boolean matches(LogicalNode node) {
        if (!(node instanceof LogicalFilter)) return false;
        LogicalFilter filter = (LogicalFilter) node;
        return filter.getChild() instanceof LogicalFilter;
    }

    @Override
    public LogicalNode apply(LogicalNode node) {
        LogicalFilter outer = (LogicalFilter) node;
        LogicalFilter inner = (LogicalFilter) outer.getChild();

        Expression combined = new Expression.BinaryOp(
            Expression.BinaryOp.Operator.AND,
            outer.getPredicate(),
            inner.getPredicate()
        );

        return new LogicalFilter(combined, inner.getChild());
    }
}

The pattern is Filter -> Filter. The transformation collapses them into a single Filter with the two predicates joined by AND. Since applyRuleExhaustively recurses after a transformation, a chain of three or more adjacent filters will collapse into one.

This might seem like it undoes the work of canonical form, and in a sense it does. But the timing is what matters. The canonical form exists to make pushdown easy - each predicate can be analyzed and moved independently. Once pushdown is complete, merge recombines adjacent filters for execution efficiency. It's cheaper to evaluate one combined predicate per row than to pass each row through multiple filter operators, each with its own next() call overhead.

This split-then-merge lifecycle is a common pattern in optimizers. You normalize the plan into a form that makes transformations easy, apply the transformations, and then denormalize for efficient execution.

Greedy join reorder

The final rule tackles join ordering. In a multi-way join, the order in which tables are joined can have a massive impact on performance. Joining two small filtered tables first produces a small intermediate result, while joining two large unfiltered tables first can produce a combinatorial explosion.

Our join reorder rule is a greedy heuristic for left-deep trees. It looks at a Join -> Join pattern (a left-deep tree of at least two joins) and considers swapping the second and third inputs if it would reduce cost:

public class JoinReorder implements Rule {
    private final CostModel costModel;

    public JoinReorder(CostModel costModel) {
        this.costModel = costModel;
    }

    @Override
    public boolean matches(LogicalNode node) {
        if (!(node instanceof LogicalJoin topJoin)) return false;
        return topJoin.getLeft() instanceof LogicalJoin;
    }

    @Override
    public LogicalNode apply(LogicalNode node) {
        LogicalJoin topJoin = (LogicalJoin) node;
        LogicalJoin bottomJoin = (LogicalJoin) topJoin.getLeft();

        // We have: Join(Join(A, B), C)
        LogicalNode A = bottomJoin.getLeft();
        LogicalNode B = bottomJoin.getRight();
        LogicalNode C = topJoin.getRight();

        long cardB = costModel.estimateCardinality(B);
        long cardC = costModel.estimateCardinality(C);

        if (cardC < cardB) {
            // Try: Join(Join(A, C), B)
            LogicalJoin newBottomJoin = new LogicalJoin(
                A, C, bottomJoin.getJoinType(), topJoin.getCondition());
            LogicalJoin newTopJoin = new LogicalJoin(
                newBottomJoin, B, topJoin.getJoinType(),
                bottomJoin.getCondition());

            double oldCost = costModel.estimate(topJoin);
            double newCost = costModel.estimate(newTopJoin);

            if (newCost < oldCost) {
                return newTopJoin;
            }
        }

        return null;
    }
}

The heuristic is straightforward: if the right child of the outer join (C) has lower estimated cardinality than the right child of the inner join (B), we try swapping them. Then we cost both arrangements and only commit to the swap if it's actually cheaper.

This is a greedy approach - it only considers local swaps, not the globally optimal join order. For three tables, it works reasonably well. For larger joins, you'd want dynamic programming (the System R algorithm), which we'll implement in Part 5. But the greedy heuristic demonstrates the key idea: the optimizer uses cost estimates to make decisions, not just structural pattern matching.

Notice that JoinReorder is the first rule that takes a constructor argument - the CostModel. The earlier rules are purely structural transformations that don't need cost information. Join reordering is where cost-based and rule-based optimization meet.

Assembling the pipeline

With all four rules in hand, we compose them into an optimization pipeline:

SQLParser parser = new SQLParser();
LogicalPlanBuilder planBuilder = new LogicalPlanBuilder(catalog);
CostModel costModel = new SimpleCostModel(catalog);

List<Rule> rules = Arrays.asList(
    new PredicatePushdown(),
    new ProjectionPushdown(),
    new FilterMerge()
);

RuleEngine ruleEngine = new RuleEngine(rules, 5);

The rule ordering matters. Predicate pushdown runs first because it moves filters to where they can be most effective. Projection pushdown runs next. Filter merge runs last, after pushdown has positioned all filters. The JoinReorder rule (which needs a cost model) can be added when cost-based optimization is desired.

To see the full impact, we parse a query, build a plan, annotate it with costs, optimize, and then re-annotate:

AST.SelectStmt ast = parser.parse(sql);
LogicalNode initialPlan = planBuilder.build(ast);
annotatePlanWithCosts(initialPlan, costModel);

double initialCost = initialPlan.getEstimatedCost();

LogicalNode optimizedPlan = ruleEngine.optimize(initialPlan);
annotatePlanWithCosts(optimizedPlan, costModel);

double optimizedCost = optimizedPlan.getEstimatedCost();

The annotatePlanWithCosts helper walks the tree bottom-up, asking the cost model for cardinality and cost estimates at each node:

private static void annotatePlanWithCosts(LogicalNode node, CostModel costModel) {
    for (LogicalNode child : node.getChildren()) {
        annotatePlanWithCosts(child, costModel);
    }
    node.setEstimatedRows(costModel.estimateCardinality(node));
    node.setEstimatedCost(costModel.estimate(node));
}

After optimization, the cost typically drops significantly for queries where predicate pushdown can eliminate rows before they reach the join. The actual cost model and cardinality estimator are the subject of the next post - for now, the key point is that the rule engine works with the cost model to evaluate whether transformations are actually improvements.

The fixpoint in practice

Let's trace through the fixpoint loop for the two-predicate join query to see how rules interact:

Initial plan:

Project -> Filter[o.total > 100] -> Filter[c.city = 'Seattle'] -> Join -> Scan[customers], Scan[orders]

Iteration 1, PredicatePushdown:

Iteration 1, ProjectionPushdown:

Iteration 1, FilterMerge:

Iteration 2:

Two iterations, and the plan is fully optimized. The rules didn't interfere with each other because each one has a clear, narrow pattern. Predicate pushdown moved the filters, and the other rules had nothing left to do.

What production systems do differently

Our rule engine is simple and effective for a small rule set, but production optimizers operate at a different scale.

Volcano/Cascades framework. Instead of applying rules to a single plan tree, the Cascades framework (used in SQL Server, CockroachDB, and others) maintains a memo - a compact representation of many equivalent plan alternatives. Rules generate alternatives, and the framework uses branch-and-bound search with cost pruning to find the cheapest plan. This avoids the problem of rule ordering entirely: all transformations are explored, and cost decides which wins.

Cost-based rule ordering. In our engine, rule order is fixed by the programmer. Production systems may prioritize rules based on estimated benefit, or use heuristic groups (first apply "always good" rules like predicate pushdown, then explore alternatives with cost-based rules).

Bushy trees and full join enumeration. Our join reorder rule only considers left-deep trees. Production systems enumerate bushy trees (where both children of a join can themselves be joins) and use dynamic programming to find the optimal order. For 10+ tables, the search space is enormous, and sophisticated pruning is essential.

Physical properties. Production rule engines reason about physical properties of plans - sort order, partitioning, distribution. A rule might prefer a merge join if the inputs are already sorted, or avoid moving data across network partitions. Our rules only reason about logical structure.

Despite these differences, the architecture is recognizably the same: pattern-match on plan structure, produce equivalent alternatives, and use cost to choose. Our Rule interface, fixpoint engine, and concrete rules are a miniature version of what runs inside every major database.

What's next

The rule engine works, but we've been hand-waving about costs. What exactly does "estimated cost" mean? How does the optimizer estimate how many rows a filter will produce? What's the formula for join cost? In the next post, we'll build the cost model and cardinality estimator - the components that give the optimizer its ability to reason quantitatively about plan quality.

Next up: Part 4 - Cost Modeling and Cardinality Estimation