Relational Algebra Trees

When you write a SQL query, you're expressing what data you want—not how to retrieve it. This declarative nature is SQL's greatest strength, but it creates a fundamental challenge: the database engine must translate your high-level request into a concrete sequence of operations that can actually execute against stored data.

This translation is not trivial. A simple query like SELECT name FROM employees WHERE salary > 50000 AND department = 'Engineering' could be executed in dozens of ways, each with vastly different performance characteristics. Should we first filter by salary, then by department? Or vice versa? Should we use an index? Which one? The answers depend on data distribution, indexes available, memory constraints, and countless other factors.

Relational algebra trees are the database's answer to this challenge. They provide a structured, mathematically grounded representation that captures the logical intent of a query while enabling systematic optimization and execution planning.

To understand relational algebra trees, we must first appreciate the gap they bridge. SQL is a declarative query language—you specify the desired result, not the steps to achieve it. This is fundamentally different from procedural programming where you write explicit instructions.

Consider the conceptual gulf:

SELECT e.name, d.department_name
FROM employees e
JOIN departments d ON e.dept_id = d.id
WHERE e.salary > 75000
ORDER BY e.name;

This SQL query makes no mention of:

• Which table to read first
• Whether to use indexes or sequential scans
• How to perform the join (nested loops? hash join? sort-merge?)
• When to apply the filter condition
• How to sort the results

Yet the database must make all these decisions—and must make them optimally. Relational algebra trees provide the intermediate representation that makes this possible.

The Query Processing Pipeline:

Relational algebra trees occupy a critical position in the query processing pipeline:

1. Parsing: SQL text → Parse Tree (syntactic structure)
2. Semantic Analysis: Parse Tree → Validated Query (name resolution, type checking)
3. Translation: Validated Query → Relational Algebra Tree (logical representation)
4. Optimization: Relational Algebra Tree → Optimized Logical Plan
5. Physical Planning: Logical Plan → Execution Plan (with concrete algorithms)
6. Execution: Execution Plan → Query Results

The relational algebra tree is where the query transitions from being a syntactic artifact to a semantic representation that captures exactly what operations must be performed, independent of how they'll be implemented.

A relational algebra tree is a directed acyclic graph (typically a tree, though some representations allow sharing) where:

• Leaf nodes represent base relations (tables) or constants
• Internal nodes represent relational algebra operations
• Edges represent the flow of data from child to parent
• The root produces the final query result

Data flows upward: Each node receives input from its child nodes, applies its operation, and passes the result to its parent. The root node's output is the query result.

Key Structural Properties:

Understanding the Example:

In this tree:

1. Leaf Node (employees): Represents scanning the employees table. Its output schema is all columns of the employees table.

2. Selection Node (σ): Receives all employee tuples, evaluates the compound predicate department='Engineering' AND salary > 80000, and outputs only tuples where this predicate is true. Output schema identical to input.

3. Projection Node (π): Receives filtered tuples, extracts only name and salary attributes, discards all others. Output schema contains only these two columns.

The final result flows out of the projection node—containing names and salaries of engineering employees earning over $80,000.

The transformation from SQL to relational algebra trees follows systematic rules. Understanding these rules illuminates how the database "understands" your queries and why certain SQL patterns produce certain tree shapes.

The Canonical Translation Algorithm:

For a SELECT-FROM-WHERE query, the basic translation produces:

π_<select list>(
  σ_<where condition>(
    <from clause translation>
  )
)

For the FROM clause:

• A single table becomes a leaf node
• Multiple tables become a chain of Cartesian products (×) or joins (⋈)
• Explicit JOINs with ON conditions become join operators with those conditions

Let's trace a complex example:

Critical Observations:

1. WHERE and HAVING differ fundamentally: WHERE filters rows before grouping (appears below γ), while HAVING filters groups after aggregation (appears above γ). This isn't just syntax—it's semantically different operations at different tree levels.

2. Join conditions vs. WHERE conditions: The join condition (c.customer_id = o.customer_id) is part of the join operator, while filter conditions appear in selection nodes. Some optimizers later push WHERE conditions into joins when beneficial.

3. ORDER BY comes last: Sorting produces the final ordered result, so it appears at or near the root.

4. The tree is canonical, not optimal: This is the initial translation. The optimizer will transform it extensively before execution.

Each node type in a relational algebra tree has specific semantics, input requirements, and output characteristics. Understanding these deeply is essential for reasoning about query behavior and optimization opportunities.

Each node in a relational algebra tree has input and output schemas. The output schema of a child becomes the input schema of its parent. Understanding how schemas propagate is crucial for:

• Query validation: Detecting references to non-existent columns
• Type checking: Ensuring operations are type-compatible
• Optimization: Knowing what columns are available at each point
• Physical planning: Determining tuple layouts for each operation

Schema Transformation Rules:

Type Propagation Example:

Consider the expression π_name, salary*1.1(employees):

1. employees has schema: {id: INT, name: VARCHAR(100), salary: DECIMAL(10,2), dept: INT}

2. Projection extracts name and computes salary * 1.1

3. Output schema: {name: VARCHAR(100), salary_adjusted: DECIMAL(12,3)}

Note how the type of the computed column (salary * 1.1) must be inferred. Multiplying DECIMAL(10,2) by a literal may widen precision. The query processor must:

• Infer that 1.1 is numeric (DECIMAL or FLOAT)
• Apply type promotion rules
• Determine the result type
• Optionally cast if the target column has a specific type

Production query processors attach extensive metadata to tree nodes beyond just the operation and schema. This metadata enables optimization and planning decisions.

Key Properties Tracked:

Why Annotations Matter:

These annotations drive optimizer decisions:

• Cardinality tells the optimizer whether an operation is cheap (few tuples) or expensive (many tuples)
• Sort order determines if a merge join is viable without a prior sort
• Unique keys let the optimizer eliminate redundant DISTINCT operations
• Partitioning in distributed systems determines if a shuffle is needed before a join

Without accurate annotations, the optimizer cannot make good decisions. This is why statistics maintenance is crucial for database performance.

Different database systems implement relational algebra trees with varying terminology and structures, but the fundamental concepts remain consistent. Understanding these implementations helps when reading EXPLAIN output and debugging query plans.

Key Observations from EXPLAIN:

1. Operations nest: The tree is visible in the indentation. Each indented block is a child of the parent above it.

2. Costs propagate upward: Parent costs include child costs. The root's cost is the total query cost.

3. Selection pushed to scan: The Filter: (e.salary > 75000) appears directly at the Seq Scan, not as a separate node. This is an optimization—the canonical tree had selection above the scan.

4. Physical decisions: "Hash Join" and "Seq Scan" are physical operators, not just logical algebra. This is the execution plan derived from the optimized logical tree.

5. Output columns listed: Each node shows what columns it produces, corresponding to projection.