Relational Algebra — Comma Join Led to 3-Hour Query

Every time you fire off a SELECT query, your database engine doesn't execute it the way you wrote it. It translates your SQL into a tree of Relational Algebra operations, optimizes that tree, and then executes the cheapest plan it can find. If you don't understand Relational Algebra, you're essentially writing queries blind — you can't reason about why the query planner made a particular choice, why a rewrite performs better, or why two syntactically different queries produce identical execution plans. This isn't academic trivia; it's the internal language of every RDBMS from PostgreSQL to Oracle.

Relational Algebra solves a specific problem: how do you formally describe data retrieval in a way that is both mathematically precise and implementation-independent? Before it existed, query languages were ad-hoc, ambiguous, and tightly coupled to storage details. E.F. Codd's 1970 paper gave us a closed algebra — meaning every operation takes relations as input and produces a relation as output. That closure property is what allows operations to be composed, reordered, and optimized freely without breaking correctness.

By the end of this article you'll be able to translate any SQL query into its Relational Algebra expression tree, reason about which algebraic equivalences the query optimizer exploits, spot inefficient query patterns before they hit production, and answer the deep 'why' questions that trip people up in senior engineering interviews. We'll also walk through runnable PostgreSQL demonstrations so the theory stays grounded in reality.

Relational Algebra Is the Query Optimizer's Native Language

Relational algebra is a formal system of operators — select, project, join, union, difference, rename — that consume one or two relations (tables) and produce a new relation. Every SQL query compiles down to an algebraic expression tree; the optimizer rewrites that tree using algebraic equivalences (e.g., pushing selections before joins) to find a cheaper execution plan. Without understanding these operators, you're guessing at performance.

Each operator has a precise signature: σ (select) filters rows by a predicate, π (project) keeps only specified columns, ⨝ (join) combines rows where a condition holds. The algebra is closed — every operation yields a relation — so you can compose expressions arbitrarily. The key property for performance is that operators commute and distribute under certain conditions, which is exactly what the optimizer exploits to reduce I/O and CPU.

Use relational algebra reasoning when debugging slow queries: trace the logical plan to see if expensive cross products or late filters are present. In practice, a comma join (Cartesian product) followed by a WHERE clause is algebraically identical to an inner join, but the optimizer may not push the filter down if the predicate references columns from both sides — leading to a massive intermediate relation. Knowing the algebra lets you rewrite the query to give the optimizer a better starting tree.

Derived Operations: Joins, Division & Intersection

Real SQL queries rarely use raw union or Cartesian product; they rely on joins. All joins are built from the fundamental six.

Theta Join (θ-join): σ_condition(A × B). A Cartesian product followed by selection. SQL's JOIN ... ON condition is theta join.

Equi-Join: A theta join where condition is equality. SQL's natural inner join.

Natural Join: Combines two relations on all common attribute names, automatically removing duplicate columns. Used less in practice because you lose control over join keys.

Outer Joins (LEFT, RIGHT, FULL): Preserves rows from one or both sides when no match is found. Algebraic definition: Left Outer Join = (Inner Join) ∪ (Rows from left with NULLs on right).

Division (÷): The trickiest operation. Find rows in one relation that match ALL rows in another. Example: 'Find employees who work on ALL projects from the R&D department.' SQL implementations typically use double NOT EXISTS or GROUP BY + COUNT.

Intersection (∩): Rows present in both relations. Derived via A − (A − B). SQL's INTERSECT operator (which is Core SQL, but less common).

Semi-join (⋉) returns rows from left relation that have at least one match in right. It's a projection after join. SQL uses EXISTS or IN. Anti-join (▷) returns rows from left with no match. SQL uses NOT EXISTS. These are not fundamental but appear in optimization.

Production reality of outer joins: LEFT JOINs in SQL can degrade performance if the join key is not indexed on the right side. The optimizer may still choose a nested loop because it expects most rows to have matches. When that assumption fails — e.g., only 10% of left rows have matches — the performance tanks. You can sometimes rewrite an outer join as a UNION of an inner join and an anti-join to give the optimizer better options.

Anti-join optimization trick: When you need NOT EXISTS, the optimizer often converts it to an anti-join automatically. But if you write LEFT JOIN ... WHERE right.id IS NULL, the optimizer might not recognize the pattern. Prefer EXISTS/NOT EXISTS for clarity and better transformation opportunities.

Division in practice: I've seen teams struggle with 'find customers who bought every product in a category'. The naive double NOT EXISTS is correct but can be slow. An alternative: pre-aggregate the total required products, then GROUP BY customer with HAVING COUNT(DISTINCT product_id) = total. This uses a single scan instead of nested subqueries.

One more nuance about set operations: UNION removes duplicates by default. If you know duplicates aren't possible or don't matter, use UNION ALL — it skips the sort/distinct step. This is a direct algebra-level decision: σ and π don't remove duplicates either (a relation is a set, so duplicates aren't allowed in pure algebra, but SQL works with bags).

-- TheCodeForge: Joins in action
-- Equi-join (theta join with equality)
SELECT e.name, d.dept_name
FROM Employees e
JOIN Departments d ON e.dept_id = d.dept_id;

-- Left outer join
SELECT e.name, p.project_name
FROM Employees e
LEFT JOIN Projects p ON e.employee_id = p.lead_id;

-- Division: find employees who work on ALL 'important' projects
SELECT employee_id
FROM Assignments a1
WHERE NOT EXISTS (
    SELECT project_id
    FROM Projects
    WHERE priority = 'Important'
    EXCEPT
    SELECT a2.project_id
    FROM Assignments a2
    WHERE a2.employee_id = a1.employee_id
);

Relational Algebra Trees and Query Optimization

When you submit a SQL statement, the database engine doesn't execute it verbatim. It parses the SQL into a parse tree, then converts that into an initial Relational Algebra tree — a tree whose nodes are algebra operations and leaves are base tables.

This tree is then passed to the query optimizer, which applies a set of algebraic equivalences to transform the tree into a semantically equivalent but cheaper form.

Key optimization strategies (all based on algebra rewrites):

• Selection pushdown: Move σ operations closer to the leaves to reduce rows early. Equivalent: σ_p(A ⋈ B) = (σ_p(A)) ⋈ B if p references only A.
• Projection pushdown: Move π operations earlier to reduce columns carried through joins. Reduces I/O and memory.
• Join reordering: Change join order (e.g., do small table first) using commutativity and associativity of join.
• Eliminate redundant operations: Remove unnecessary projections or selections that don't filter anything.
• Combine selections: Multiple filters on same relation can be merged into one σ.

Example: Consider the query: SELECT name FROM Employees WHERE dept = 'Engineering' AND salary > 100000. Initial algebra tree: π_name (σ_dept='Eng' AND salary>100k (Employees)). The optimizer could push selection before projection? Actually projection is after selection. But if we had a join, push selection to the appropriate side.

The optimizer also chooses physical join algorithms (hash join, merge join, nested loop) based on the algebra tree structure and statistics.

The optimizer uses table cardinalities, column selectivity, and index statistics to estimate costs. For example, it estimates how many rows will pass a filter (selectivity) using histograms. These estimates drive join ordering and operator choices. Poor statistics lead to bad plans.

The search space for optimal join order is exponential (n! for n tables). Optimizers use dynamic programming (e.g., PostgreSQL's dynamic programming for up to 12 tables) or heuristic rules (e.g., left-deep trees) to keep search manageable.

A real optimizer blind spot: Some databases don't push selections through window functions or set operations (UNION, EXCEPT) because those operations can change the number of rows in unpredictable ways. If you have a UNION with a WHERE on the outer query, the optimizer might not push it into each branch. You often have to write the filter in each UNION branch explicitly.

Statistics matter more than you think. I've seen a query where the optimizer chose a nested loop join on 10M rows because it thought the outer table had only 1000 rows. The statistics were stale after a bulk insert. An ANALYZE fixed the plan. Always run ANALYZE after major data changes.

Cost estimation nuance: The optimizer's cost model uses arbitrary units (disk pages, CPU cycles). In PostgreSQL, you can see the costs in EXPLAIN output. If a filter's selectivity estimate is off by an order of magnitude, the optimizer may choose a sequentially scan over an index scan. Tuning default_statistics_target can improve estimates.

Advanced tip: If you're stuck with a bad plan that the optimizer refuses to change despite fresh stats, consider using a plan hint (like PostgreSQL's pg_hint_plan extension) or rewriting the query to force a specific join order. But that's a last resort — prefer to fix the algebra tree first.

-- TheCodeForge: Query optimization example
-- Suppose we have two large tables: Orders (50M) and Users (2M)
-- Original query:
SELECT u.name, o.amount
FROM Users u
JOIN Orders o ON u.id = o.user_id
WHERE u.active = true AND o.amount > 1000;

-- Optimizer may rewrite:
-- Step 1: Selection pushdown on Users (σ_active)
-- Step 2: Selection pushdown on Orders (σ_amount>1000)
-- Step 3: Join the reduced relations (much smaller)

-- Equivalent algebra tree:
-- π_name,amount ( σ_active(Users) ⋈_id=user_id σ_amount>1000(Orders) )

-- You can test this with:
EXPLAIN (ANALYZE, BUFFERS)
SELECT u.name, o.amount
FROM (SELECT * FROM Users WHERE active = true) u
JOIN (SELECT * FROM Orders WHERE amount > 1000) o ON u.id = o.user_id;
-- Compare vs original EXPLAIN to see if optimizer already does this.

Translating SQL to Relational Algebra Step by Step

Let's walk through a realistic SQL query and convert it to an algebra tree. This skill is crucial for senior roles — interviewers often ask you to draw the tree or explain why a query runs slow.

SQL query:

SELECT e.name, p.project_name FROM Employees e JOIN Assignments a ON e.employee_id = a.employee_id JOIN Projects p ON a.project_id = p.project_id WHERE e.department = 'R&D' AND p.status = 'Active';

Step 1: Identify base tables and initial operations - Tables: Employees (E), Assignments (A), Projects (P) - Selections: σ_department='R&D'(E) and σ_status='Active'(P) - Joins: Two equi-joins on employee_id and project_id - Projection: π_name, project_name

Step 2: Build the tree from the bottom up - Leaf nodes: E, A, P - Apply selections first (push down): σ_RD = σ_department='R&D'(E); σ_active = σ_status='Active'(P) - Join 1: Join σ_RD with A on employee_id (call it J1) - Join 2: Join J1 with σ_active on project_id (call it J2) - Finally, project π_name, project_name on J2.

Algebra expression: π_name, project_name ( ( σ_department='R&D'(Employees) ⋈_employee_id Assignments ) ⋈_project_id σ_status='Active'(Projects) )

Why this order is often optimal: - By filtering employees early to only R&D, we reduce rows for the first join. - By filtering projects early to only Active, we reduce rows for the second join. - The optimizer may further reorder to join the smallest intermediate result first.

Interview tip: When asked to translate, always push selections and projections down as far as possible in the tree. That's what the optimizer does, and it shows you understand optimization.

Let's also handle a correlated subquery: 'Find employees who earn more than the average in their department.' This requires a derived relation with grouped averages. The algebra: π_{name}(Employees ⋈_{dept_id} (γ_{dept_id, AVG(salary)}(Employees))). The optimizer may introduce a window function to avoid nested loops.

Real-world twist: When you have a subquery in the SELECT clause, it becomes a dependent join. The algebra tree has a correlated subquery node that the optimizer can sometimes flatten into a join. For example: SELECT e.name, (SELECT COUNT(*) FROM Orders o WHERE o.employee_id = e.id) AS order_count FROM Employees e; This is a scalar correlated subquery. The optimizer often rewrites it as a left join with aggregation.

Common translation mistake: People forget that GROUP BY and aggregation are also relational algebra operations — they produce a relation with one row per group. The grouping operation (γ) is an extension of the basic six, but it still satisfies closure.

One more practical exercise: Try translating a query with HAVING. SELECT department, AVG(salary) FROM employees GROUP BY department HAVING AVG(salary) > 50000. The algebra: σ_avg>50000(γ_department, AVG(salary)(Employees)). The HAVING is just a selection after grouping. Understanding this helps you decide whether to filter before or after aggregation.

-- TheCodeForge: The query we translated above
SELECT e.name, p.project_name
FROM Employees e
JOIN Assignments a ON e.employee_id = a.employee_id
JOIN Projects p ON a.project_id = p.project_id
WHERE e.department = 'R&D'
AND p.status = 'Active';

-- Check the planned tree with EXPLAIN:
EXPLAIN (COSTS, VERBOSE)
SELECT e.name, p.project_name
FROM Employees e
JOIN Assignments a ON e.employee_id = a.employee_id
JOIN Projects p ON a.project_id = p.project_id
WHERE e.department = 'R&D'
AND p.status = 'Active';
-- Look for 'Filter:' nodes to see if selections are pushed down.

Algebraic Equivalences: How Optimizers Rewrite Your Query

The query optimizer's power comes from a set of algebraic equivalences—rules that transform one algebra tree into another without changing the result. Understanding these lets you predict what the optimizer will do and write queries that are already in the best shape.

Selection Pushdown: σ_p(A ⋈ B) = (σ_p(A)) ⋈ B if p references only A. Reduces rows before join.

Projection Pushdown: π_c(A ⋈ B) = π_c(π_{c1}(A) ⋈ π_{c2}(B)) when c is a subset of columns from A and B. Reduces columns carried through join.

Join Commutativity: A ⋈ B = B ⋈ A. Optimizer chooses the smaller table first.

Join Associativity: (A ⋈ B) ⋈ C = A ⋈ (B ⋈ C). Enables different join orderings.

Selection Commutativity: σ_p(σ_q(A)) = σ_q(σ_p(A)). Order of filters doesn't matter.

Merge of Selections: σ_{p1}(σ_{p2}(A)) = σ_{p1 ∧ p2}(A). Multiple filters can be combined.

Idempotence of Projection: π_A(π_A(A)) = π_A(A). Repeated projections are redundant.

The optimizer uses these rules in a cost-based search. It generates multiple candidate trees, estimates their cost using statistics, and picks the cheapest. Modern optimizers (PostgreSQL, Oracle, SQL Server) use dynamic programming for join ordering but still rely on these algebraic rules for tree transformations.

The hidden assumption: Most equivalences assume that the functions in predicates are deterministic and have no side effects. If you use a volatile function (RANDOM(), NOW(), or a custom function marked VOLATILE), the optimizer cannot push it through joins because the result could change. This is a common source of plan inefficiencies.

Practical impact: When you wrap a filter in a function, you block pushdown. Example: WHERE calculate_bonus(salary) > 1000 cannot be pushed down even if the function only depends on one table. The optimizer doesn't know that. If possible, inline such functions or use generated columns to expose the condition.

Advanced equivalence: Selection pushdown also works through UNION. σ_p(R ∪ S) = σ_p(R) ∪ σ_p(S). This is how optimizers push filters into UNION branches. Some databases do this only if p references columns present in both branches. If not, pushdown is blocked.

Another equivalence often missed: σ_p(A − B) = σ_p(A) − σ_p(B) if p references only columns from A. This allows pushing selections into the left side of a set difference, reducing rows before the anti-join. Not all optimizers apply this, so manually pushing the selection into the left branch of EXCEPT can be a win.

-- TheCodeForge: Algebraic equivalence in action
-- Query: find active users with orders over $1000
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.active = true
AND o.amount > 1000;

-- This is semantically equivalent to:
SELECT u.name, o.amount
FROM (SELECT * FROM users WHERE active = true) u
JOIN (SELECT * FROM orders WHERE amount > 1000) o ON u.id = o.user_id;

-- Check if PostgreSQL uses selection pushdown:
EXPLAIN (ANALYZE, BUFFERS)
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.active = true
AND o.amount > 1000;
-- Look for 'Filter' nodes on seq scans of users and orders
-- If filters are on the scans, pushdown happened.

Physical Operators: From Algebra Trees to Execution Plans

The algebra tree is logical—it defines what to compute, not how. The optimizer then chooses physical operators for each node: sequential scan or index scan for a relation, hash join vs merge join vs nested loop for a join, etc.

Sequential Scan vs Index Scan: An algebra tree leaf (a relation) can be executed by reading all blocks (seq scan) or by using an index to fetch only matching blocks (index scan). The optimizer picks based on selectivity estimates.

Hash Join: For equi-joins, build a hash table on one side, probe with the other. Best when one side fits in memory. Algebra: ⋈_{condition}.

Merge Join: Sort both sides on join key, then merge. Good when inputs are already sorted. No sort cost if indexes provide sorted order.

Nested Loop Join: For each row in outer, scan inner. Works well for small outer relations or when inner is indexed.

Materialization: Some operators (e.g., sorting, aggregate) require storing intermediate results. The optimizer may inject a 'Materialize' node.

Reading EXPLAIN output means mapping each node back to your SQL. A Filter node is a selection (σ). A Projection node (rarely shown explicitly) is π. Join nodes correspond to theta joins. Understanding this mapping lets you spot missing filters, wrong join order, or excessive materialization.

The hidden cost of materialization: When you see 'Materialize' in an EXPLAIN plan, it often means the optimizer decided to cache an intermediate result. This can happen with CTEs (especially on PostgreSQL before v12) or with subqueries in the FROM clause. Materialization has memory overhead and can cause spilling to disk for large intermediate sets. If you see a materialize node and the query is slow, consider reducing the intermediate size by pushing filters further down.

One more thing about nested loops: They're not always evil. If the outer table is tiny (e.g., 10 rows) and the inner table has an index on the join key, a nested loop can outperform hash or merge join because it avoids building a hash table. The optimizer should choose it, but if statistics are off, you might get a nested loop on 10M rows. Always verify.

Real-world example: I had a query joining a small lookup table (100 rows) to a large fact table (10M rows). The optimizer chose a hash join — but it built the hash table on the large fact table, which consumed ~500MB of memory. Rewriting with a nested loop hint reduced memory usage to near zero and improved latency because the large table had an index on the join key. Physical operators matter.

-- TheCodeForge: EXPLAIN output mapping
CREATE INDEX idx_users_active ON users(active) WHERE active = true;

EXPLAIN (ANALYZE, COSTS, VERBOSE)
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.active = true
AND o.amount > 500;

-- Look for:
-- 'Index Only Scan using idx_users_active' – selection pushdown via index
-- 'Hash Join' or 'Merge Join' – physical join operator
-- 'Filter on orders' – late selection if on wrong side

Advanced Optimization: Join Ordering and Cost Estimation

The join order in the algebra tree has the biggest impact on query performance. The optimizer must choose which join to execute first, second, etc. This is an NP-hard problem (join ordering is known to be NP-hard in some formulations), but databases use heuristics and dynamic programming to find good-enough plans.

Cost estimation in practice: The optimizer estimates the cost of each plan using: - Cardinality estimates: how many rows each operation will produce. - Selectivity factors: how selective a filter is (e.g., 'department = R&D' might select 10% of rows). - CPU and I/O costs: based on hardware characteristics.

Join ordering algorithms: - Dynamic programming: enumerates all possible join orders for up to about 10-12 tables. After that, the cost of enumeration becomes prohibitive. - Greedy heuristics: start with the smallest relation, join with the next smallest, etc. - Genetic algorithms: used by some databases for very large join queries.

The 'star join' optimization: In data warehouse queries, a central fact table is joined to multiple dimension tables. The optimizer recognizes this pattern and may choose a hash join strategy where it builds a separate hash table for each dimension and probes the fact table once. This is a physical plan derived from the algebra tree.

Parameterized queries and plan caching: If you use parameterized queries (prepared statements), the optimizer may not know the actual parameter values until execution. It must choose a plan based on generic estimates. This can lead to 'parameter sniffing' problems where the first execution shapes the cached plan poorly for subsequent values. Some databases (like SQL Server) allow recompilation hints.

Parameter sniffing in practice: I had a query that worked fine for most days but was slow on Mondays. The first execution of the week used a value that returned few rows, so the optimizer cached a nested loop plan. On Monday, the parameter returned many rows, but the plan stayed nested loop — 20 seconds vs 2 seconds. The fix: use OPTION (RECOMPILE) in SQL Server or use a plan guide. In PostgreSQL, you can use PLAN CACHE settings or force generic plans.

What about parallel query execution? The algebra tree can be split across parallel workers for scans and joins. The optimizer decides when parallelism is profitable based on row estimates. If you see a Gather node in EXPLAIN, it's the parallel equivalent of the algebra tree. Understanding the algebra tree helps you diagnose why a query isn't using parallelism — maybe a missing filter prevents early row reduction, making parallelism less attractive.

-- TheCodeForge: Join order example
-- Suppose Orders (50M), Users (2M), Products (1M)
-- Bad order: join Users and Products first (produces 2M*1M = 2T rows) then join Orders
-- Good order: join Users and Orders first (filtered) then join Products

-- Use EXPLAIN to see order:
EXPLAIN (ANALYZE, COSTS)
SELECT u.name, o.amount, p.product_name
FROM users u
JOIN orders o ON u.id = o.user_id
JOIN products p ON o.product_id = p.product_id
WHERE u.active = true AND o.amount > 1000;
-- Notice which table is scanned first: that's the first in join order

Why Selection (σ) Doesn't Work Like You Think

Selection is the cheapest operation in relational algebra. It's also the most misunderstood. Junior devs treat it like a WHERE clause filter — just a simple condition check. But the query optimizer sees selection as an opportunity to prune entire data pages before they ever touch memory. That's why you'll see selections pushed down the tree in every optimized plan. The earlier you filter, the less data the join operators have to touch.

The real trap? Selection predicates are evaluated per tuple, not per column. A filter like σ age > 30 OR salary < 50000 forces a full scan of both attributes on every row. If you write σ age > 30 followed by a union of σ salary < 50000, the optimizer might split that into two passes and merge results. Different trees, wildly different I/O costs.

In production, never assume your WHERE clause maps 1:1 to a selection operator. The optimizer will push, split, or even invert your predicates. Know your algebraic equivalences — especially the distributive laws between selection and join — or your query spends its life reading pages it could have skipped.

// io.thecodeforge — cs-fundamentals tutorial

// Simulating optimizer's decision to push selection before join
# relations: orders (100k rows), customers (10k rows)
# naive plan: join first, then filter
naive_io = 100_000 + 10_000 + (100_000 * 10_000)  # cartesian
# optimized: push selection σ(orders.amount > 1000) before join
filtered_orders = 20_000
optimized_io = filtered_orders + 10_000 + (filtered_orders * 10_000)

print(f"Naive plan I/O cost: {naive_io}")
print(f"Pushdown plan I/O cost: {optimized_io}")
print(f"Speedup factor: {naive_io / optimized_io:.1f}x")

The Union Operator Exposes Your Schema Rot

Union in relational algebra is a set operation — it removes duplicates. That's the whole point. But in SQL, UNION ALL is the default for a reason, and it's not because the database loves you. UNION (without ALL) forces a sort or hash of both relations to suppress duplicates. On two tables with 10 million rows each, that's a temp table write, a sort, and a scan. You pay for deduplication even when you know the sets are disjoint.

Here's the production insight: if you're UNIONing two tables and they share the same schema, ask yourself why they're separate tables. I've seen schemas with orders_2023, orders_2024, orders_2025 — all UNIONed in every reporting query. That's a smell. A partitioned table or a single orders table with a year column would eliminate the union entirely. The algebra tree collapses from a three-node union to a single selection.

When you absolutely need union, prefer UNION ALL if you know the sets don't overlap. The rename operator (ρ) can help you align attribute names before union — but if you're renaming just to make a union work, your schema design failed. Fix the schema, not the query.

// io.thecodeforge — cs-fundamentals tutorial

// Cost comparison: UNION vs UNION ALL on large tables
# simulate two tables, each 10M rows, average row size 256 bytes
row_size = 256  # bytes
num_rows_per_table = 10_000_000

# UNION ALL: just scan both, no dedup cost
union_all_cost = 2 * num_rows_per_table * row_size  # bytes read

# UNION: scan + sort + write temp + scan temp
sort_cost = num_rows_per_table * 2 * row_size * 1.5  # sort factor
write_temp = num_rows_per_table * 2 * row_size
scan_temp = num_rows_per_table * 2 * row_size
union_cost = union_all_cost + sort_cost + write_temp + scan_temp

print(f"UNION ALL I/O: {union_all_cost / 1e9:.2f} GB")
print(f"UNION I/O: {union_cost / 1e9:.2f} GB")
print(f"UNION overhead: {(union_cost - union_all_cost) / 1e9:.2f} GB")

Union (∪) Exposes Schema Rot Faster Than Any Linter

Union is not a free join. It's a merge that demands identical column types and counts. If two tables produce the same schema but you can't union them without casting—your schema is rotting.

Production reality: Union is the fastest way to catch column drift. When you union users and archived_users and the created_at column is TIMESTAMP in one and DATE in the other, your query breaks at runtime. Optimizers can't infer a fix. They just fail.

The correct fix: align schemas at the storage layer. Not with CASTs in queries. If you're unioning three reporting pipelines that each define total_revenue differently—decimal(10,2) vs numeric vs float—you have a data contract problem, not a SQL problem. Union forces you to care about type discipline. Use it as a health check, not a workaround.

// io.thecodeforge — cs-fundamentals tutorial

// Simulates union failure when schemas drift
class Table:
    def __init__(self, name, columns):
        self.name = name
        self.columns = columns  # list of (name, type) tuples

def can_union(a, b):
    if len(a.columns) != len(b.columns):
        return f"FAIL: Column count mismatch ({len(a.columns)} vs {len(b.columns)})"
    for (n1, t1), (n2, t2) in zip(a.columns, b.columns):
        if t1 != t2:
            return f"FAIL: Column '{n1}' type {t1} vs '{n2}' type {t2}"
    return "PASS: Schemas align"

users = Table("users", [("id", "int"), ("created_at", "timestamp")])
archived = Table("archived_users", [("id", "int"), ("created_at", "date")])
print(can_union(users, archived))

Union Distributivity: The Rewrite Rule That Kills Sorting

Here's the algebraic secret: σ(∪) can be rewritten as ∪(σ). Distributing selection over union lets the optimizer push filters down to each branch independently. This turns a full-table scan into two smaller scans—critical when you union hot partitions with cold archives.

Why this matters in production: Sorting is expensive. If you do SELECT FROM (q1 ∪ q2) ORDER BY date LIMIT 100, the optimizer pulls all rows from both branches, sorts them, then takes 100. That's wasteful. But union distributes sort: (SELECT FROM q1 ORDER BY date LIMIT 100) UNION ALL (SELECT * FROM q2 ORDER BY date LIMIT 100) followed by a priority-queue merge requires 1/10th the memory.

This isn't academic. PostgreSQL's Merge Append node implements exactly this. Snowflake's UNION ALL rewrite applies it. Know the algebra so you recognize when your execution plan is sorting an entire table when it only needed a slice.

// io.thecodeforge — cs-fundamentals tutorial

// Demonstrates distributed union sort with minimal memory
import heapq

def distributed_union_sort(q1, q2, limit=100):
    # Each source sorts independently and yields sorted rows
    def sorted_branch(data):
        data.sort(key=lambda r: r["date"])
        return data[:limit]
    
    branch1 = sorted_branch(q1)
    branch2 = sorted_branch(q2)
    # Merge two sorted lists with a heap (O(n log k))
    merged = heapq.merge(branch1, branch2, key=lambda r: r["date"])
    return list(merged)[:limit]

# Simulate a hot table and a cold archive
hot = [{"date": 20240101 + i} for i in range(1000)]
cold = [{"date": 20220101 + i} for i in range(5000)]
result = distributed_union_sort(hot, cold, limit=5)
print([r["date"] for r in result])

Common Mistakes and Confusions

Relational Algebra is unforgiving: it punishes subtle misreadings with wrong results. The most frequent error is confusing set union (∪) with bag union (union-all). SQL's UNION removes duplicates by default; relational algebra's ∪ is always set-based. If you use ∪ where SQL's UNION ALL is intended, you lose rows. Another trap: assuming selection (σ) can filter on attributes from a joined relation after the join. Selection is evaluated per-tuple on the relation you apply it to. To filter across relations, push selections down before the join, not after. Division (÷) is almost always misunderstood: it answers "which X values are associated with every Y value?" Not "which X values are associated with any Y value?" That's a join. Finally, cross product (×) without a subsequent selection is rarely correct; it pairs every row with every other row—often a performance disaster. Always pair × with σ or replace with a natural join. These distinctions matter because the optimizer transforms your algebra tree into execution plans. An incorrect algebra expression becomes an incorrect, slow plan.

// io.thecodeforge — cs-fundamentals tutorial

# Wrong: wants sailors who reserved boat 101 OR 102
# But ÷ requires ALL boats in set
sailors_reserved = {1, 2, 3}
boats_101_102 = {101, 102}

# (÷) returns sailor 1 only if they reserved both 101 AND 102
wrong = sailors_reserved  # This is not division. Division needs attribute matching

# Correct: join on reservation table then group
# Select sailors where boat count = 2
print("Wait — you need a full cross-product check")

Union (∪) Exposes Schema Rot Faster Than Any Linter

Set union (∪) is a strict operation: both input relations must be union-compatible, meaning they share the same number of attributes with identical domains. This constraint makes ∪ a brutal schema audit. If you try to union two tables that were designed independently—say 'customers_old' with columns (id, name, email) and 'customers_new' with (id, name, email, signup_date)—the union fails outright. The error is not a warning; it's a crash. This forces you to reconcile schemas, which reveals design drift: missing columns, renamed fields, or type mismatches. In production, union compatibility failures are the top cause of ETL pipeline breaks after column renames. Query optimizers exploit this: they treat ∪ as a hard boundary for predicate pushdown. If you need union-all semantics (preserving duplicates), use bag union—but relational algebra's ∪ is always set semantics. That means an implicit DISTINCT cost unless your optimiser deduplicates smartly. The lesson: before refactoring any schema, write a union query. The errors will show you exactly where your data model rotted.

// io.thecodeforge — cs-fundamentals tutorial

def union_compatible(r1, r2):
    return len(r1['schema']) == len(r2['schema']) and \
           all(d1 == d2 for d1, d2 in zip(r1['domains'], r2['domains']))

old = {'schema': ['id', 'name'], 'domains': ['int', 'text']}
new = {'schema': ['id', 'name', 'email'], 'domains': ['int', 'text', 'text']}

if not union_compatible(old, new):
    print("Schema rot: mismatch", list(set(new['schema']) - set(old['schema'])))
else:
    print("Union OK")