Skip to content

Relational Algebra in SQL: JOINs, Set Operations & Atomic UPSERTs

Created: 2026-11-08  ·  Last updated: 2026-11-08  ·  Nejat Hakan

Executive Summary: The relational database model derives its power from set theory. Rather than procedurally iterating over records with application loops, developers query database engines using declarative relational algebra. Understanding the mathematical mechanics of INNER, OUTER, SEMI, and ANTI joins—alongside how the query optimizer executes them physically via Nested Loops, Hash Joins, or Merge Joins—is essential for eliminating slow queries. This guide provides an engineering breakdown of relational join operations, set-theoretic operators (UNION, INTERSECT, EXCEPT), and concurrent, atomic UPSERT (ON CONFLICT) patterns.

  • Join Mechanics & Venn Semantics

    Differentiate INNER, LEFT, RIGHT, FULL, and CROSS joins with mathematical precision across nullable relationships.

  • Semi- & Anti-Joins

    Eliminate Cartesian bloat: filter parent rows via EXISTS (Semi-Join) and identify missing records via NOT EXISTS (Anti-Join) safely handling NULLs.

  • Physical Engine Algorithms

    Understand how PostgreSQL and MariaDB execute joins in memory: Nested Loop, in-memory Hash Join, and sorted Merge Join.

  • Atomic Idempotent UPSERT

    Eliminate read-then-insert race conditions: execute atomic INSERT ... ON CONFLICT DO UPDATE using the EXCLUDED pseudo-record.

1. Relational Join Mechanics & Set Semantics

In relational algebra, joining two relations A and B produces a new relation containing attributes derived from both sources based on a join predicate.

%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
    A_TAB["Left Relation (A)<br/>(e.g., customers)"]
    B_TAB["Right Relation (B)<br/>(e.g., orders)"]
    JOIN_OP{"Join Predicate<br/>A.customer_id = B.customer_id"}
    R_INNER["INNER JOIN<br/>Intersection: (A ∩ B)"]
    R_LEFT["LEFT OUTER JOIN<br/>All A + Matching B or NULL"]
    R_FULL["FULL OUTER JOIN<br/>Union: (A ∪ B) with NULLs"]
    R_ANTI["ANTI-JOIN (A \\ B)<br/>Rows in A with NO match in B"]

    A_TAB --> JOIN_OP
    B_TAB --> JOIN_OP
    JOIN_OP --> R_INNER
    JOIN_OP --> R_LEFT
    JOIN_OP --> R_FULL
    JOIN_OP --> R_ANTI

The Join Classification Matrix

Join Type Mathematical Set Definition Output Behavior Common Use Case
INNER JOIN A ∩ B Keeps only rows where the join predicate evaluates to TRUE in both tables. Fetching orders together with confirmed customer data.
LEFT OUTER JOIN A ∪ (A ∩ B) Keeps all rows from table A. Attributes from table B are populated if matched, or set to NULL. Displaying all customers, including those who have placed zero orders.
RIGHT OUTER JOIN (A ∩ B) ∪ B Syntactic mirror of LEFT JOIN. Keeps all rows from table B. Rarely used; engineers rewrite as LEFT JOIN for readability.
FULL OUTER JOIN A ∪ B Retains all rows from both tables, filling unmatched attributes with NULL. Reconciling discrepancies between two billing Ledgers.
CROSS JOIN A × B Cartesian product: combines every row in A with every row in B (N × M rows). Generating scheduling matrix grids or date dimension ranges.

2. Advanced Filtering: Semi-Joins & Anti-Joins

A common source of performance degradation and duplicate row bugs is misusing INNER JOIN or LEFT JOIN simply to check for the existence or absence of child records.

Semi-Join: Filter Without Multiplying Rows

If a customer has placed 100 orders, an INNER JOIN between customers and orders emits 100 rows for that single customer, requiring an expensive DISTINCT or GROUP BY to collapse:

-- Anti-Pattern: Cartesian row multiplication followed by DISTINCT
SELECT DISTINCT c.customer_id, c.company_name
FROM customers c
INNER JOIN orders o ON o.customer_id = c.customer_id;

-- Production Best Practice: Relational Semi-Join via EXISTS
-- Stops scanning orders immediately upon finding the first match!
SELECT c.customer_id, c.company_name
FROM customers c
WHERE EXISTS (
    SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id
);

Anti-Join: The NOT IN vs. NOT EXISTS Trap

To find parent entities that have no matching children (e.g., customers who never placed an order), engineers frequently use NOT IN:

-- DANGEROUS: If orders.customer_id contains even a single NULL value,
-- NOT IN returns ZERO rows for the entire query due to 3-valued logic!
SELECT * FROM customers 
WHERE customer_id NOT IN (SELECT customer_id FROM orders);

-- Production Best Practice 1: Safe Anti-Join via NOT EXISTS
SELECT c.customer_id, c.company_name
FROM customers c
WHERE NOT EXISTS (
    SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id
);

-- Production Best Practice 2: LEFT ANTI-JOIN via IS NULL
SELECT c.customer_id, c.company_name
FROM customers c
LEFT JOIN orders o ON o.customer_id = c.customer_id
WHERE o.customer_id IS NULL;

3. Physical Join Algorithms in the Database Engine

When an SQL query executes, the cost-based query optimizer (CBO) analyzes table statistics (ANALYZE) to choose one of three physical algorithms:

%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
    CBO["Cost-Based Optimizer<br/>(Inspects Table Statistics)"]
    NL["1. Nested Loop Join<br/>Outer Loop scans Table A;<br/>Inner Loop probes Index on B"]
    HJ["2. Hash Join<br/>Builds In-Memory Hash Table on B;<br/>Streams and Probes Table A"]
    MJ["3. Merge Join<br/>Sorts both A and B on Join Key;<br/>Zips through both in linear time"]

    CBO -->|Small Outer + Indexed Inner| NL
    CBO -->|Large Unsorted Datasets| HJ
    CBO -->|Pre-Sorted or B-Tree Indexed| MJ
  1. Nested Loop Join: For each row in the outer relation, the engine executes a lookup on the inner relation. Highly efficient (O(N · log M)) when the outer table is small and the inner table has a matching B-Tree index.
  2. Hash Join: The engine scans the smaller relation and builds an in-memory hash table in RAM (work_mem). It then scans the larger relation, hashing each key to probe for matches (O(N + M)). If work_mem is exceeded, the hash table spills to disk temp files.
  3. Merge Join: Both relations are sorted by the join key (or scanned sequentially from pre-sorted B-Tree indexes). The engine advances pointers through both datasets simultaneously like a zipper in linear time (O(N + M)).

4. Atomic Idempotent Mutations: The UPSERT Pattern

In concurrent web services, checking if a record exists (SELECT) and then issuing an INSERT or UPDATE creates a classic Time-of-Check to Time-of-Use (TOCTOU) race condition. Two concurrent worker processes can both see that a row does not exist, attempt to insert simultaneously, and crash with a unique constraint violation.

PostgreSQL solves this with atomic INSERT ... ON CONFLICT:

-- File: /opt/db-ops/atomic_upsert_workshop.sql
-- Idempotently insert product or update stock and price if SKU already exists
INSERT INTO products (sku, title, price_cents, stock_qty)
VALUES 
    ('NVME-PCI5-4TB', 'PCIe 5.0 Enterprise NVMe 4TB', 48900, 20)
ON CONFLICT (sku) DO UPDATE
SET 
    price_cents = EXCLUDED.price_cents,
    stock_qty   = products.stock_qty + EXCLUDED.stock_qty,
    metadata    = products.metadata || '{"last_restocked": "2026-11-08"}'::jsonb;
  • EXCLUDED Table: A virtual pseudo-table containing the proposed values that conflicted with the existing row.
  • Atomic Execution: The engine takes a row lock on the conflicting index leaf, applies the update, and commits without race conditions.

5. Practical Analytical Join Lab

Execute this query in psql to calculate high-value customer lifetime revenue across three joined relations:

-- File: /opt/db-ops/customer_ltv_query.sql
SELECT
    c.customer_id,
    c.company_name,
    c.email,
    COUNT(DISTINCT o.order_id) AS completed_orders,
    ROUND(SUM(oi.quantity * oi.unit_cents) / 100.0, 2) AS total_revenue_eur,
    MAX(o.ordered_at) AS last_order_date
FROM customers c
INNER JOIN orders o ON o.customer_id = c.customer_id
INNER JOIN order_items oi ON oi.order_id = o.order_id
WHERE o.status IN ('PAID', 'SHIPPED')
GROUP BY c.customer_id, c.company_name, c.email
HAVING SUM(oi.quantity * oi.unit_cents) >= 50000
ORDER BY total_revenue_eur DESC;