Expression Trees

Every query you write has a hidden structure—a shape that determines how it will be executed, optimized, and understood by the database engine. This structure is the expression tree, a hierarchical representation that captures the complete logic of a relational algebra expression.

When you write SQL, the database parses your text, validates the semantics, and translates everything into an expression tree. This tree becomes the central representation that the query optimizer manipulates, the execution engine interprets, and debuggers display. Understanding expression trees means understanding how databases actually process queries.

In this page, we'll explore expression trees in depth: their structure, how they're built, how they're evaluated, and how they're transformed during optimization. By the end, you'll be able to visualize any query as a tree and understand why certain tree shapes lead to better performance.

An expression tree is a hierarchical data structure where:

• Nodes represent operations or data sources
• Edges represent data flow from producer to consumer
• The root represents the final query result
• Leaves represent base relations (tables)

Node Types:

Leaf Nodes (Operands):

• Represent base relations: Employees, Departments, Orders
• Have no children
• Produce data by reading from storage
• Schema comes from table definition

Internal Nodes (Operators):

• Represent relational algebra operations: σ, π, ⋈, ∪, etc.
• Have one child (unary) or two children (binary)
• Consume input relations from children
• Produce output relation for parent
• Schema determined by operation and input schemas

The Root Node:

• Special internal node at the top
• Produces the final query result
• Output goes to the client, not another operator

Edge Direction:

By convention, edges point FROM child TO parent, representing data flow upward. A join node has two incoming edges (from its two input relations) and one outgoing edge (to its parent or the result).

Tree Properties:

• Height: Number of edges from root to deepest leaf; indicates query complexity and nesting depth
• Width: Maximum number of nodes at any level; indicates parallelism potential
• Size: Total number of nodes; correlates with query complexity
• Balance: Whether subtrees have similar heights; affects execution strategies

Formal Definition:

An expression tree T is a tuple (N, E, root, label) where:

• N is a finite set of nodes
• E ⊆ N × N is a set of directed edges
• root ∈ N is the designated root node
• label: N → (RelName ∪ OpName) assigns each node a relation name or operator
• The graph (N, E) forms a tree rooted at root
• Every leaf is labeled with a relation name
• Every internal node is labeled with an operator

Translating a relational algebra expression into a tree is straightforward—the nested structure of the expression directly maps to the tree structure.

The Recursive Construction:

Tree(R) where R is a base relation:
  Create leaf node labeled R
  
Tree(Op(E)) where Op is a unary operator:
  Create internal node labeled Op
  Add Tree(E) as its child
  
Tree(E1 Op E2) where Op is a binary operator:
  Create internal node labeled Op
  Add Tree(E1) as left child
  Add Tree(E2) as right child

Example Construction:

For the expression:

π_name(σ_{salary>50000}(Employees ⋈_{dept_id=id} Departments))

Step-by-step:

1. Start from the outermost operator: π_name
2. Its child is σ_{salary>50000}(...)
3. Selection's child is Employees ⋈ Departments
4. Join's children are Employees and Departments (leaves)

Building bottom-up:

Step 1: Create leaf nodes
  node_E = Leaf(Employees)
  node_D = Leaf(Departments)
  
Step 2: Create join node
  node_J = Internal(⋈, condition=dept_id=id)
  node_J.left = node_E
  node_J.right = node_D
  
Step 3: Create selection node
  node_S = Internal(σ, predicate=salary>50000)
  node_S.child = node_J
  
Step 4: Create projection node (root)
  node_P = Internal(π, columns=[name])
  node_P.child = node_S
  
Result: Tree with root = node_P

Expression trees aren't just representations—they're executable specifications. The database evaluator traverses the tree to compute the query result. Two primary evaluation strategies exist.

Bottom-Up (Materialized) Evaluation:

Start at the leaves and work upward:

1. Read base relations from storage (leaves produce data)
2. For each internal node, wait for all children to complete
3. Apply the operator to child results, producing a new relation
4. Pass the result upward to the parent
5. The root's output is the query result

Characteristics:

• Simple to implement and reason about
• Each intermediate result is fully materialized (stored)
• Memory usage can be high for large intermediates
• Natural for operators that need complete input (e.g., sort, aggregation)

Top-Down (Demand-Driven/Pipelined) Evaluation:

Start at the root and propagate requests downward:

1. Root requests its first result tuple
2. Root asks its child for input
3. Child propagates request to its children
4. Leaves fetch data on demand
5. Results flow back up tuple-by-tuple

Characteristics:

• Also called "iterator model" or "Volcano model"
• Tuples stream through operators without full materialization
• Memory efficient for large results
• Natural for producers connected directly to consumers

The Iterator Interface:

Most modern databases use the iterator model, where each node implements three operations:

Open()   - Initialize the operator, recursively open children
Next()   - Return the next output tuple (or null if exhausted)
Close()  - Clean up resources, recursively close children

Evaluation Example:

For π_name(σ_{salary>50000}(Employees)):

1. Query executor calls Root.Open()
2. π.Open() calls σ.Open()
3. σ.Open() calls Employees.Open() (init table scan)

4. Executor calls Root.Next()
5. π.Next() calls σ.Next()
6. σ.Next() calls Employees.Next() repeatedly:
   - Returns each tuple, σ checks predicate
   - If salary > 50000, σ returns tuple to π
   - If not, σ calls Next() again, filtering internally
7. π extracts 'name' column, returns to executor
8. Executor receives row, sends to client
9. Repeat 4-8 until Next() returns null

Pipeline Breakers:

Some operators can't stream—they need complete input before producing output:

• Sort: Must see all tuples to determine order
• Aggregation without grouping: Must see all tuples to compute aggregate
• Hash Join build phase: Must build complete hash table

These "pipeline breakers" force materialization at that point in the tree.

Real database systems maintain rich metadata in their expression trees beyond simple operator labels. Understanding this metadata is essential for reading query plans.

Node Annotations:

Each tree node typically includes:

1. Operator Type: SELECT, JOIN, AGGREGATE, etc.
2. Operator Parameters: Predicates, columns, join conditions
3. Schema Information: Output columns and types
4. Cardinality Estimate: Expected number of output tuples
5. Cost Estimate: Expected execution cost (I/O, CPU)
6. Physical Operator: The chosen algorithm (hash join, merge join, etc.)
7. Properties: Ordering, partitioning, uniqueness guarantees

Example Annotated Node:

HashJoin
  Type: Inner Join
  Condition: employees.dept_id = departments.id
  Output Schema: (emp_id, name, salary, dept_id, dept_name)
  Estimated Rows: 850
  Estimated Cost: 1250.0
  Build Input: Departments (smaller)
  Probe Input: Employees (larger)

Query Plan Visualization:

Databases display trees in various formats:

1. Indented Text: Each level indented, common in EXPLAIN output
2. Tree Diagrams: Visual trees with boxes and arrows
3. JSON/XML: Structured representation for programmatic access
4. Graphical Tools: Interactive visualizations (pgAdmin, MySQL Workbench)

Reading an EXPLAIN Plan:

1. Identify the root: The topmost operation produces the final result
2. Trace the data flow: Follow from leaves up to understand data sources
3. Note costs and cardinalities: Identify expensive operations
4. Check physical operators: Are appropriate algorithms chosen?
5. Look for warnings: Missing indexes, full scans, etc.

The Difference Between Logical and Physical Plans:

• Logical Plan: Expression tree with relational algebra operators (JOIN, SELECT)
• Physical Plan: Expression tree with executable algorithms (HASH_JOIN, INDEX_SCAN)

The optimizer converts logical to physical, choosing algorithms based on costs and constraints.

Query optimization is largely about transforming expression trees into equivalent but more efficient forms. The tree representation enables systematic application of transformation rules.

What Makes Trees Transformable:

1. Closedness under transformations: Transform a tree, get another valid tree
2. Local transformations: Most rules modify small subtrees
3. Composability: Multiple transformations can be applied sequentially
4. Reversibility: Transformations can be undone if not beneficial

Common Transformation Patterns:

Selection Pushdown:

Move selection closer to leaves to filter early:

Before:

      σ_p
       |
       ⋈
      / 
     R   S

After (when p involves only R):

       ⋈
      / 
   σ_p   S
    |
    R

Join Reordering:

Change the order of joins to minimize intermediate sizes:

Before:

         ⋈
        / 
       ⋈   T
      / 
     R   S

After (if S ⋈ T is smaller):

         ⋈
        / 
       R   ⋈
          / 
         S   T

Transformation as Tree Rewriting:

Each transformation rule can be expressed as a pattern matching and replacement:

Rule: Selection Pushdown over Join
Pattern:
  σ_p(R ⋈ S) where p references only R
Replacement:
  σ_p(R) ⋈ S

Algorithm:
  For each node N in tree:
    If N matches pattern left-hand side:
      Replace N with pattern right-hand side
      Update parent/child pointers

The Optimizer's Task:

Given an input tree, the optimizer:

1. Enumerates applicable transformations
2. Generates alternative trees
3. Estimates cost of each alternative
4. Selects the lowest-cost tree (or uses heuristics)

This process might explore thousands of trees for complex queries, using dynamic programming or genetic algorithms to search efficiently.

Expression trees carry properties and maintain invariants that help optimizers make decisions and ensure correctness.

Logical Properties:

Properties determined by the logical expression, independent of physical execution:

1. Output Schema: Columns and types produced by the subtree
2. Candidate Keys: Sets of attributes that uniquely identify tuples
3. Functional Dependencies: Relationships between attribute values
4. NOT NULL Constraints: Attributes guaranteed non-null
5. Cardinality Estimate: Expected number of output tuples

Physical Properties:

Properties that depend on how the operator is executed:

1. Ordering: Tuples sorted by certain attributes (important for merge join, ORDER BY)
2. Partitioning: How tuples are distributed across parallel executors
3. Locality: Where data physically resides

Property Propagation:

Properties propagate through the tree:

• Selection preserves ordering, may affect cardinality
• Projection may destroy ordering if the sort column is removed
• Join combines properties from both inputs (complex rules)
• Sort creates ordering property but destroys previous ordering

Example: Ordering Propagation:

For tree: ORDER BY salary(σ_dept='Eng'(Employees))

If Employees has index on (dept, salary):
  - Scan returns rows ordered by (dept, salary)
  - Selection preserves ordering (single dept value)
  - Order by salary satisfied—no additional sort needed!
  
If Employees has no suitable index:
  - Scan returns unordered rows
  - Selection produces unordered result
  - ORDER BY requires explicit sort operation

Interesting Orders:

The concept of "interesting orders" is crucial for optimization:

• An ordering is "interesting" if it benefits a downstream operator
• ORDER BY creates demand for a specific order
• Merge join requires both inputs sorted on join column
• Group by benefits from grouped/sorted input

The optimizer tracks which orderings are interesting and prefers plans that produce them, even at slight extra cost, to avoid expensive sort operations later.

Property-Based Optimization:

Modern optimizers use properties for:

1. Plan pruning: If a plan can't produce required properties, discard it early
2. Algorithm selection: Choose merge join if inputs are sorted; hash join otherwise
3. Enforcer insertion: Add sort/exchange operators when required properties aren't present
4. Cost adjustment: Factor in property mismatches when comparing plans

The Volcano and Cascades optimizer frameworks formalize property-based optimization, treating properties as first-class optimization dimensions.

Expression trees naturally expose opportunities for parallel execution. Understanding these opportunities is essential for high-performance query processing.

Independent Subtrees:

Subtrees that share no data dependencies can execute concurrently:

           ⋈
          / 
         /   
     σ(R)     σ(S)

The two selection subtrees (on R and on S) can run simultaneously on different processors. The join waits for both to complete, then combines results.

Pipeline Parallelism:

In pipelining, producer and consumer operators run concurrently:

Producer: Table Scan on Employees
  → Stream tuples to →
Consumer: Selection (salary > 50000)
  → Stream tuples to →
Consumer: Projection (name)

All three operators can be active simultaneously, each processing different tuples.

Partition Parallelism:

Data is partitioned, and the same operator runs on multiple partitions:

         Gather
        /  |  
      σ    σ    σ
      |    |    |
   R(p1) R(p2) R(p3)

The relation R is split into partitions p1, p2, p3. Parallel selections run on each partition. Results are gathered at the end.

Exchange Operators:

Distributed databases insert exchange operators into trees to manage data distribution:

• Scatter/Partition: Split data and send to multiple nodes
• Gather: Collect data from multiple nodes
• Repartition: Redistribute data to align for join

            Gather
               |
            π(name)
               |
            ⋈ (on hash-partitioned dept_id)
           / 
   Repartition Repartition
       |           |
   σ(Employees) σ(Departments)

Blockers and Parallelism:

Pipeline-breaking operators create synchronization points:

• Before a sort, all input must be gathered
• Before global aggregation, partial aggregates must be collected
• Before broadcast join, the broadcast table must be fully distributed

These blockers limit parallelism but are sometimes unavoidable.

Tree Width and Parallelism:

• Narrow trees (long chains) have limited parallelism
• Wide trees (many sibling subtrees) have high parallelism potential
• The ideal width depends on available processors and data distribution