Combining Operations

Selection filters rows. Projection selects columns. But real-world queries rarely need just one or the other—they need both, often multiple times, combined in sophisticated ways. Finding "the names and salaries of Engineering employees earning over $100,000" requires filtering (Selection) and column extraction (Projection), working together seamlessly.

The power of relational algebra lies in composability—the ability to combine simple operations into arbitrarily complex expressions. Because each operation produces a valid relation, that result can immediately become input to another operation. This closure property is the foundation of declarative query languages.

This page explores how Selection and Projection combine, the algebraic laws that govern their interaction, how query optimizers exploit these laws for efficiency, and practical patterns for constructing robust, maintainable queries.

The closure property of relational algebra states that every operation produces a relation, which can then serve as input to any other operation. This enables operation composition or chaining.

Basic Composition:

Given operations Op₁ and Op₂, their composition is written as:

$$Op_1(Op_2(R))$$

Read from inside out: first apply Op₂ to R, then apply Op₁ to the result.

Common Composition Patterns:

1. Selection then Projection: $$π_{name, salary}(σ_{department='Engineering'}(Employee))$$

Filter rows first, then select columns.

2. Projection then Selection: $$σ_{salary>100000}(π_{name, salary}(Employee))$$

Select columns first, then filter rows.

3. Multiple Selections: $$σ_{status='active'}(σ_{department='Engineering'}(Employee))$$

Apply multiple filters sequentially.

4. Multiple Projections: $$π_{name}(π_{name, salary}(Employee))$$

Narrow columns progressively (the second projection further restricts the first).

Expression Trees:

Complex expressions are often visualized as trees:

          π_{name, salary}
               │
               ▼
    σ_{dept='Eng' ∧ salary>100000}
               │
               ▼
           Employee

Leaves are base relations; internal nodes are operations. Evaluation proceeds bottom-up.

Canonical Form:

Queries can be written in different but equivalent forms. A canonical form is a standard representation that makes comparison and optimization easier. For Selection and Projection, a common canonical form places all Selections before all Projections:

$$π_L(σ_P(R))$$

This "filter first, project last" pattern often corresponds to efficient execution.

Understanding when operations can be reordered—and when they cannot—is fundamental to query optimization and correct query construction.

Selection-Selection Commutativity:

Multiple Selections always commute: $$σ_{P1}(σ_{P2}(R)) = σ_{P2}(σ_{P1}(R)) = σ_{P1 ∧ P2}(R)$$

The order of applying filters doesn't affect the result, and cascaded filters can be combined into a single conjunctive filter.

Projection-Projection Absorption:

For Projections, the outer one dominates: $$π_{L1}(π_{L2}(R)) = π_{L1}(R) \text{ where } L1 ⊆ L2$$

Projecting to a superset then to a subset equals projecting directly to the subset.

Selection-Projection Commutativity (Conditional):

Selection and Projection commute only if the selection predicate references only attributes retained by the projection:

$$π_L(σ_P(R)) = σ_P(π_L(R)) \text{ if } attributes(P) ⊆ L$$

One of the most important optimizations in query processing is predicate pushdown (also called filter pushdown or selection pushdown)—applying selection predicates as early as possible in the query plan.

The Principle:

Reducing the number of tuples early in a query plan reduces work for all subsequent operations. If you can filter 1 million rows down to 1,000 before joining, every subsequent operation processes 1,000 rows instead of 1 million.

Mathematical Basis:

Predicate pushdown relies on the cascade and commutativity laws:

$$σ_P(R_1 ⋈ R_2) = σ_P(R_1) ⋈ R_2 \text{ (if P references only } R_1 \text{ attributes)}$$

Example Transformation:

Original query plan:

σ_{E.dept='Eng'}(Employee ⋈ Department)

Optimized with pushdown:

(σ_{dept='Eng'}(Employee)) ⋈ Department

Filtering Employee before the join means the join processes fewer rows.

When Pushdown Applies:

1. Single-table predicates: Predicates referencing attributes from only one table can always be pushed to that table's scan.

2. Join predicates: Can be pushed into the join itself (becomes the join condition).

3. Predicates after aggregation: Some predicates on grouped results can be pushed before grouping if they reference only grouping columns.

When Pushdown Doesn't Apply:

1. Post-join predicates: Predicates comparing attributes from multiple tables must wait until after the join.

   WHERE E.salary > D.avg_salary  -- Must evaluate after join
   

2. Aggregate-dependent predicates: HAVING conditions can't be pushed before GROUP BY.

3. Outer join complications: For LEFT/RIGHT/FULL joins, pushdown rules are more complex—pushing to the 'null-supplying' side changes semantics.

SQL and Pushdown:

Optimizers automatically identify pushdown opportunities:

-- Written:
SELECT e.name, d.location
FROM Employee e
JOIN Department d ON e.dept_id = d.id
WHERE e.status = 'active' AND d.country = 'US';

-- Optimizer pushes:
-- e.status = 'active' → to Employee scan
-- d.country = 'US' → to Department scan
-- Both predicates evaluated before join

Complementing predicate pushdown, projection pushdown (also called column pruning) eliminates unnecessary columns as early as possible in query execution.

The Principle:

Carrying fewer columns through operations reduces:

• Memory usage for intermediate results
• I/O for reading from disk (in column stores)
• Network transfer (in distributed systems)
• Hash/sort key sizes for joins and deduplication

Determining Necessary Columns:

The optimizer traces column usage backward from the output:

1. Start with columns in final SELECT
2. Add columns used in ORDER BY, GROUP BY, HAVING
3. Add columns used in predicates (WHERE, JOIN conditions)
4. Add columns for any subqueries that reference outer columns

Example Transformation:

Interaction with Storage Engines:

Row-Oriented Storage:

• Must read entire row from disk
• Projection benefit: Less data copied to memory/processed
• Still pays full I/O cost for each page

Column-Oriented Storage:

• Reads only needed columns from disk
• Projection benefit: Dramatic I/O reduction
• Ideal for analytical queries selecting few columns from wide tables

Covering Indexes:

• Include all queried columns
• Projection satisfied entirely from index
• No table access needed (index-only scan)

-- Query:
SELECT name, department FROM Employee WHERE status = 'active';

-- If index exists on (status, name, department):
-- Index-only scan possible—table never accessed!

Real-world queries combine multiple operations. Developing a systematic approach to constructing complex relational algebra expressions improves correctness and maintainability.

Step-by-Step Construction Method:

1. Identify the result schema: What columns should the final output contain?
2. Identify the base relations: Which tables are involved?
3. Identify filter conditions: What predicates must be satisfied?
4. Identify relationship conditions: How do tables relate (join conditions)?
5. Build from inside out: Start with base relations, add joins, then filters, then projections.

Example Construction:

Query: Find names and salaries of active Engineering employees with their department locations, for departments in the US.

Analysis:

• Result: name, salary, location
• Base relations: Employee, Department
• Filters: status='active', department='Engineering', country='US'
• Join: Employee.dept_id = Department.id

Common Expression Patterns:

Pattern 1: Simple Filter and Project

π_{columns}(σ_{predicate}(Table))

The most common pattern—equivalent to basic SELECT...FROM...WHERE.

Pattern 2: Join with Local Filters

π_{columns}(
  σ_{T1.pred}(Table1) ⋈_{join_cond} σ_{T2.pred}(Table2)
)

Apply table-specific filters before joining.

Pattern 3: Join with Post-Join Filter

π_{columns}(
  σ_{post_join_pred}(
    Table1 ⋈_{join_cond} Table2
  )
)

For predicates comparing attributes from both tables.

Pattern 4: Multi-Table Query

π_{columns}(
  σ_{predicates}(
    (Table1 ⋈ Table2) ⋈ Table3
  )
)

Multiple joins with filtering and final projection.

Pattern 5: Derived Table / Subquery

π_{outer_columns}(
  OuterTable ⋈ (
    π_{inner_columns}(σ_{inner_pred}(InnerTable))
  )
)

Nested expressions for subquery-like patterns.

Understanding how composite relational algebra expressions map to SQL helps bridge theory and practice.

Direct Mapping:

$$π_{A_1, A_2, ..., A_n}(σ_P(R))$$

maps to:

SELECT DISTINCT A1, A2, ..., An
FROM R
WHERE P;

(DISTINCT for set semantics; omit for bag semantics)

Join Expression:

$$π_{columns}(σ_P(R_1 ⋈_{condition} R_2))$$

maps to:

SELECT columns
FROM R1
JOIN R2 ON condition
WHERE P;

Complex Expression:

$$π_{E.name, D.location}(σ_{E.salary>100000}(Employee ⋈_{dept_id=id} Department))$$

maps to:

SELECT e.name, d.location
FROM Employee e
JOIN Department d ON e.dept_id = d.id  
WHERE e.salary > 100000;

SQL Clause Correspondence:

Key Differences:

1. Execution order: SQL is declarative; evaluation order differs from written order
2. Duplicate handling: SQL preserves duplicates by default; RA eliminates them
3. Extended features: SQL has aggregates, subqueries, window functions beyond basic RA
4. NULL handling: SQL uses three-valued logic; pure RA typically assumes no NULLs

Understanding optimization principles helps you write queries that are easier for the optimizer to handle and predict execution behavior.

Heuristic Optimization Rules:

These rules generally improve performance without cost estimation:

1. Push selections down: Apply filters as early as possible
2. Push projections down: Eliminate unused columns early
3. Combine cascaded selections: Multiple filters into one
4. Combine cascaded projections: Keep only final column set
5. Identify selection before Cartesian product: Convert to join
6. Preprocess selections with indexes: Use available indexes for selective predicates

Cost-Based Optimization Considerations:

Beyond heuristics, optimizers estimate costs:

1. Selectivity estimation: How many rows pass each filter?
2. Join order selection: Which table order minimizes intermediate results?
3. Access path selection: Table scan vs index scan vs index-only scan?
4. Join algorithm selection: Nested loop vs hash vs merge join?

Writing Optimization-Friendly Queries:

DO:

• Specify explicit column lists (enables projection pushdown)
• Use JOIN syntax with ON clause (clearer join conditions)
• Put most selective predicates where they can be pushed
• Use SARGable predicates (functions after, not on, indexed columns)
• Group related conditions logically

AVOID:

• SELECT * (defeats column pruning)
• OR conditions spanning multiple tables (prevents pushdown)
• Functions on indexed columns in predicates
• Implicit joining via Cartesian product and WHERE
• Unnecessary DISTINCT (costly if not needed)

-- Optimization-friendly:
SELECT e.name, e.salary, d.dept_name
FROM Employee e
JOIN Department d ON e.dept_id = d.id
WHERE e.status = 'active'
  AND e.hire_date >= '2020-01-01'
  AND d.country = 'US';

-- Less optimization-friendly:
SELECT *
FROM Employee e, Department d
WHERE e.dept_id = d.id
  AND (e.status = 'active' OR d.status = 'active')
  AND YEAR(e.hire_date) >= 2020;