Projection Pushdown

If selection pushdown reduces the number of tuples flowing through a query plan, projection pushdown reduces their width. Together, these optimizations minimize the volume of data at every stage of query processing.

Consider a table with 50 columns and millions of rows. If your query only needs 3 columns, why carry the other 47 through joins, sorts, and aggregations? Each unnecessary column consumes memory, cache space, and I/O bandwidth. In column-oriented storage systems, unnecessary columns may avoid disk access entirely.

Projection pushdown systematically eliminates unused attributes as early as possible in the query plan. While less dramatic than selection pushdown in terms of row reduction, it provides consistent, multiplicative benefits across all operations by reducing the per-tuple processing cost.

The Width Problem

In database systems, tuple width directly affects:

1. Memory consumption: Every intermediate result consumes memory proportional to (rows × width). Wide tuples exhaust memory faster, causing spills to disk.

2. I/O bandwidth: Whether reading from disk or transferring between operators, wider tuples mean more bytes moved.

3. Cache efficiency: Modern CPUs rely heavily on cache. Narrower tuples mean more tuples fit in cache, dramatically improving performance.

4. Network transfer: For distributed databases, tuple width directly affects network costs.

5. Hash table efficiency: Hash joins and aggregations build in-memory structures. Narrower keys and values mean smaller hash tables.

Quantifying the Impact

Consider a concrete example:

Table: Orders (100 columns total, average 50 bytes per column)
Full row width: ~5,000 bytes
Query needs: order_id, customer_id, total (3 columns, ~150 bytes)

For 1 million rows:

• Without projection pushdown: ~5 GB of data flowing through operators
• With early projection: ~150 MB of data flowing through operators
• Reduction: 33×

This reduction applies to every operation: every join, sort, and aggregation processes 33× less data.

Core Objective

Projection pushdown aims to eliminate attributes as early as possible while preserving correctness. The fundamental constraint is:

An attribute can be projected out (removed) as soon as it's no longer needed by any subsequent operation in the query plan.

What Determines "Need"?

An attribute is needed downstream if it appears in:

1. Final output — Columns requested in SELECT
2. Selection predicates — Attributes in WHERE/HAVING conditions
3. Join conditions — Attributes used to match tuples between tables
4. Grouping keys — Columns in GROUP BY
5. Aggregate function inputs — Columns being aggregated (SUM(salary))
6. Order specifications — Columns in ORDER BY
7. Subquery correlations — Columns referenced by correlated subqueries

The Extended Attribute Set

For any node in the query tree, we compute its required attributes—the set of attributes that must flow upward from this node. This set includes:

required(node) = output_attrs(node) ∪ predicate_attrs(ancestors) 
                 ∪ join_attrs(ancestors) ∪ ...

The Basic Rule

π_L(Op(R, ...)) → Op(π_{L∪A}(R), ...)

Where A is the set of additional attributes needed by operator Op that aren't in the final output L.

Example:

SELECT name FROM Employees WHERE dept_id = 5;

• Final output needs: {name}
• Selection needs: {dept_id}
• Required set: {name, dept_id}

The 48 other columns in Employees can be projected out immediately at the base table scan.

Joins are the most impactful location for projection pushdown because they often combine large tables with many columns.

The Extended Projection Rule for Joins

π_L(R ⋈_θ S) ≡ π_L(π_{L_R ∪ A_R}(R) ⋈_θ π_{L_S ∪ A_S}(S))

Where:

• L_R = attributes of L that come from R
• L_S = attributes of L that come from S
• A_R = attributes of R needed for the join condition θ
• A_S = attributes of S needed for the join condition θ

Critical Insight: Before the join, we must retain:

1. Attributes that will be in the final output
2. Attributes needed for the join condition

After the join, we can project down to just the output attributes.

Step-by-Step Example:

SELECT c.name, o.total
FROM Customers c (50 columns)
JOIN Orders o (30 columns) ON c.id = o.customer_id
WHERE o.status = 'completed';

Analysis:

• Final output: {c.name, o.total}
• Join condition needs: {c.id, o.customer_id}
• Selection needs: {o.status}

Pushed projections:

• From Customers: project to {name, id} (2 columns, not 50)
• From Orders: project to {total, customer_id, status} (3 columns, not 30)

Multi-Way Joins

For queries with multiple joins, projection pushdown propagates through the entire join tree:

π_L((R ⋈ S) ⋈ T)
→ π_L(π_{L_RS∪A_RS}(R ⋈ S) ⋈ T)
→ π_L(π_{L_RS∪A_RS}(π_{L_R∪A_R}(R) ⋈ π_{L_S∪A_S}(S)) ⋈ π_{L_T∪A_T}(T))

Each join stage projects out attributes no longer needed by subsequent operations. The key is computing the correct required attribute sets at each level.

Different query operators have different relationships with projection.

Selection (σ)

π_L(σ_p(R)) ≡ π_L(σ_p(π_{L∪attrs(p)}(R)))

Projection can be pushed through selection, but must include predicate attributes. This is bidirectional: projection can go before or after selection.

Preferred order: Typically, project first (to narrow tuples), then select. The selection runs faster on narrower tuples.

Aggregation (γ)

π_L(γ_{G,F}(R)) ≡ π_L(γ_{G,F}(π_{G∪inputs(F)}(R)))

For aggregation, project to only:

• Grouping columns (G)
• Input columns for aggregate functions (e.g., the column being SUMmed)

Example:

SELECT dept, SUM(salary) 
FROM Employees (50 columns)
GROUP BY dept;

Only {dept, salary} need to flow into the aggregation—48 columns can be projected out.

Union / Intersect / Except

π_L(R ∪ S) ≡ π_L(R) ∪ π_L(S)

Projection distributes fully over all set operations. Both operands must be projected to the same schema.

Sort

π_L(sort_K(R)) ≡ π_L(sort_K(π_{L∪K}(R)))

Sort needs the ordering keys plus the output columns. Extra columns can be projected out before sorting, making the sort operate on narrower tuples.

The core of projection pushdown is computing, for each node in the query tree, exactly which attributes must be produced. This is the required attributes computation.

Algorithm Overview

The algorithm works in two passes:

Pass 1: Top-Down Requirement Propagation

Starting from the root (final output), propagate requirements downward:

required(root) = output columns

for each node, given required(node):
    compute required(children) by adding:
    - attributes needed by this node's operation
    - minus attributes this node generates

Pass 2: Bottom-Up Projection Insertion

Insert projections at each node to produce only required attributes:

for each node bottom-up:
    if produced(node) ⊃ required(node):
        insert π_{required(node)} above node (or integrate into node)

Handling Complex Cases

Expressions and Computed Columns

When a query includes expressions like a + b AS sum, the required set must include both a and b until the expression is computed:

required = {sum} → after expression computation
required = {a, b} → before expression computation

Subqueries

Correlated subqueries reference outer columns. These correlating columns must be tracked through the scope hierarchy and included in required sets at appropriate levels.

Projection pushdown becomes dramatically more impactful with columnar storage systems.

Row vs. Column Storage

Row-oriented storage (traditional RDBMS):

• All columns of a row stored contiguously
• Reading a row's subset of columns still requires reading the whole row from disk
• Projection saves memory/CPU but not disk I/O

Column-oriented storage (modern analytics systems):

• Each column stored separately
• Reading only needed columns avoids I/O for unreferenced columns entirely
• Projection pushdown can eliminate >90% of disk I/O

The Impact Is Multiplicative

For a table with 100 columns using columnar storage:

• Query needs 5 columns
• Without projection pushdown: read all 100 columns → 100 I/O units
• With projection pushdown: read 5 columns → 5 I/O units
• Savings: 95% of disk I/O eliminated

Predicate Pushdown Synergy

In columnar systems, projection and selection pushdown work together powerfully:

1. Zone maps / min-max statistics: Columnar systems maintain per-column metadata. Pushing selections allows skipping entire column chunks.

2. Late materialization: Read only filtering columns first, evaluate predicates, then fetch remaining columns only for qualifying rows.

3. Dictionary encoding: Operate on encoded values without decompression until projection extracts final needed values.

This is why analytical queries on columnar systems can be 10–100× faster than equivalent queries on row stores—and why projection pushdown is essential.

While projection pushdown is generally beneficial, there are nuances to be aware of.

The SELECT * Problem

-- Avoid this in production queries:
SELECT * FROM Orders WHERE status = 'pending';

-- Use this instead:
SELECT order_id, customer_id, total FROM Orders WHERE status = 'pending';

SELECT * prevents the optimizer from knowing which columns are actually needed downstream (especially important in views, CTEs, and application layers). Always specify needed columns explicitly.

When Extra Columns Are Free

In row-oriented storage with covering indexes, including extra columns may be essentially free if they're retrieved together anyway. The optimizer considers this.

Dynamic Column Requirements

Some application patterns (ORMs, generic query builders) make it difficult to know columns upfront. Modern systems handle this, but explicit column lists are always preferable.