Jul 22, 2026

OLAP – Phase 9 Query Planner and Optimizer

The parser produces an AST — a syntactic representation of the SQL query. But the AST doesn’t know whether table names exist, what types columns have, or how to execute the query efficiently. This phase bridges the gap with three components: a binder that resolves names and types, an optimizer that rewrites the logical plan for efficiency, and a physical planner that maps logical operators to executable physical operators.

The pipeline is: AST → Binder → Logical Plan → Optimizer → Physical Planner → Physical Plan.

In DuckDB, these are the Binder (src/planner/binder/), Optimizer (src/optimizer/), and PhysicalPlanGenerator (src/execution/physical_plan_generator.cpp).

Here is the roadmap for the phases to come:

Phase 9: Query planner and optimizer
Phase 10: Sorting, parallel execution, REPL, and server

Full Source Code

The code referenced in this post can be found in https://gitlab.com/kimserey.lam/olap-learn.

Logical Operators

The logical plan is a tree of operators that describe what to compute, not how:

type LogicalOperator interface {
    Children() []LogicalOperator
    SetChildren(children []LogicalOperator)
}

The concrete operators mirror the query structure:

type LogicalGet struct {
    TableName     string
    ColumnIndices []int
    ColumnTypes   []vector.LogicalType
    ColumnNames   []string
}

type LogicalFilter struct {
    Predicate BoundExpr
    child     LogicalOperator
}

type LogicalProjection struct {
    Expressions []BoundExpr
    Aliases     []string
    child       LogicalOperator
}

type LogicalAggregate struct {
    GroupBy    []BoundExpr
    Aggregates []AggregateBinding
    child      LogicalOperator
}

type LogicalJoin struct {
    JoinType  LogicalJoinType
    Condition BoundExpr
    left      LogicalOperator
    right     LogicalOperator
}

type LogicalSort struct {
    Keys  []LogicalSortKey
    child LogicalOperator
}

type LogicalLimit struct {
    Limit  int64
    Offset int64
    child  LogicalOperator
}

Bound Expressions

The binder resolves AST expressions into bound expressions — expressions with resolved types and column indices:

type BoundColumnRef struct {
    TableName string
    ColName   string
    ColIndex  int
    Typ       vector.LogicalType
}

type BoundConstant struct {
    Value any
    Typ   vector.LogicalType
}

type BoundBinaryExpr struct {
    Left  BoundExpr
    Op    string
    Right BoundExpr
    Typ   vector.LogicalType
}

type BoundFunctionCall struct {
    Name     string
    Args     []BoundExpr
    Star     bool
    Distinct bool
    Typ      vector.LogicalType
}

The key difference from AST expressions: a BoundColumnRef has a resolved ColIndex and Typ, not just a name string.

The Binder

The binder walks the AST and resolves every name against the catalog:

Look up the table name → get schema (column names and types)
Resolve each column reference → find the column index and type
Type-check expressions → ensure comparisons and arithmetic are valid
Build the logical plan tree

For a query like:

SELECT region, SUM(amount)
FROM orders
WHERE year > 2023
GROUP BY region

The binder:

Looks up orders in the catalog, gets its columns
Resolves region → column index 1, type Varchar
Resolves amount → column index 2, type Float64
Resolves year → column index 0, type Int32
Checks that year > 2023 is a valid comparison (Int32 > Int64)
Builds: LogicalProjection → LogicalAggregate → LogicalFilter → LogicalGet

Optimizer

The optimizer rewrites the logical plan to reduce work. We implement three rules:

1. Predicate Pushdown

Move filter conditions as close to the data source as possible. Before:

Filter(country='US')
  └── Join(o.rid = r.id)
        ├── Scan(orders)
        └── Scan(regions)

After:

Join(o.rid = r.id)
  ├── Scan(orders)
  └── Filter(country='US')
        └── Scan(regions)

The filter on country only references the regions table, so it can be pushed below the join. This eliminates non-matching regions before the join, reducing the number of rows that flow through the (expensive) join operator.

func pushFilter(filter *LogicalFilter) LogicalOperator {
    join, ok := filter.child.(*LogicalJoin)
    if !ok {
        return filter
    }

    leftTables := collectTableNames(join.left)
    rightTables := collectTableNames(join.right)
    refs := collectColumnRefs(filter.Predicate)

    allLeft := true
    allRight := true
    for _, ref := range refs {
        if !tableInSet(ref.TableName, leftTables) { allLeft = false }
        if !tableInSet(ref.TableName, rightTables) { allRight = false }
    }

    if allLeft && !allRight {
        join.left = &LogicalFilter{Predicate: filter.Predicate, child: join.left}
        return join
    }
    if allRight && !allLeft {
        join.right = &LogicalFilter{Predicate: filter.Predicate, child: join.right}
        return join
    }
    return filter // references both sides, can't push
}

2. Constant Folding

Evaluate constant expressions at plan time instead of at execution time:

func foldExpr(expr BoundExpr) BoundExpr {
    bin, ok := expr.(*BoundBinaryExpr)
    if !ok {
        return expr
    }
    bin.Left = foldExpr(bin.Left)
    bin.Right = foldExpr(bin.Right)

    leftConst, leftOk := bin.Left.(*BoundConstant)
    rightConst, rightOk := bin.Right.(*BoundConstant)
    if !leftOk || !rightOk {
        return bin
    }

    // both sides are constants — evaluate now
    switch bin.Op {
    case "+":
        return &BoundConstant{Value: lf + rf, Typ: bin.Typ}
    case "-":
        return &BoundConstant{Value: lf - rf, Typ: bin.Typ}
    // ...
    }
}

WHERE amount > 50 + 50 becomes WHERE amount > 100.0 — the 50 + 50 is folded into a single constant.

3. Projection Pushdown

Only read columns that are actually needed by the query. The optimizer collects all column references from the plan tree, then prunes each LogicalGet to only include those columns:

func ProjectionPushdown(plan LogicalOperator) LogicalOperator {
    needed := collectNeededColumns(plan)
    return applyProjectionPushdown(plan, needed)
}

If a table has 10 columns but the query only uses 2, the scan reads and decompresses only those 2 column segments.

Physical Planner

The physical planner maps logical operators to physical operators:

Logical	Physical
LogicalGet	SeqScanOperator
LogicalFilter	FilterOperator
LogicalProjection	ProjectionOperator
LogicalAggregate	HashAggregateOperator
LogicalJoin	HashJoinOperator
LogicalSort	SortOperator
LogicalLimit	LimitOperator

The mapping is mostly one-to-one, but the physical planner also handles details like:

Converting BoundExpr to Expression (execution-layer expressions)
Setting up column index mappings between operators
Choosing join build/probe sides

End-to-End Example

SELECT o.region, SUM(o.amount)
FROM orders o
JOIN regions r ON o.region_id = r.id
WHERE r.country = 'US'
GROUP BY o.region;

Before optimization:

Projection [o.region, SUM(o.amount)]
  └── Aggregate [GROUP BY o.region, SUM(o.amount)]
        └── Filter [r.country = 'US']
              └── Join [o.region_id = r.id]
                    ├── Get [orders]
                    └── Get [regions]

After predicate pushdown:

Projection [o.region, SUM(o.amount)]
  └── Aggregate [GROUP BY o.region, SUM(o.amount)]
        └── Join [o.region_id = r.id]
              ├── Get [orders]
              └── Filter [r.country = 'US']
                    └── Get [regions]

After projection pushdown:

Same structure, but Get[orders] only reads columns: region, amount, region_id
and Get[regions] only reads columns: id, country

Summary

The planner pipeline transforms SQL text into an executable plan through three stages: binding (name resolution and type checking), optimization (predicate pushdown, constant folding, projection pushdown), and physical planning (mapping logical to physical operators). Each optimization reduces the amount of data processed — fewer rows through early filtering, fewer columns through projection pruning, and fewer computations through constant folding.