Joins in SQL

A join is a relational operator that produces a new relation (table) by combining rows from two input relations whenever they satisfy a specified join condition, typically an equality between attributes that appear in both tables (a foreign key referencing a primary key, in the common case). Formally, in relational algebra, the join is derived from two simpler operators: the Cartesian product (×), which pairs every row of one relation with every row of another, and selection (σ), which filters rows satisfying a predicate. The theta join `R ⋈θ S` is defined as `σθ(R × S)` — form all pairs, then keep only pairs satisfying condition θ. When θ is an equality condition, this is called an equijoin; when θ additionally requires dropping one copy of each duplicated column name, it is a natural join. SQL exposes joins in two syntactic styles that are logically equivalent for inner joins. The implicit style lists tables in the `FROM` clause separated by commas (forming a cross product) and states the join condition in the `WHERE` clause. The explicit style uses the `JOIN` keyword with an `ON` clause to state the condition directly, syntactically separating "how tables relate" from "which rows to keep." The SQL standard and most style guides favor the explicit form because it is unambiguous, self-documenting, and — crucially — it is the only form capable of expressing outer joins, since a plain `WHERE` filter cannot resurrect a row that the cross product never paired with anything. The critical semantic distinction is between inner joins, which output only rows with a matching partner in both tables, and outer joins, which additionally preserve unmatched rows from one or both sides, filling in the missing columns with `NULL`. A `LEFT OUTER JOIN` keeps every row of the left table even if unmatched; a `RIGHT OUTER JOIN` keeps every row of the right table; a `FULL OUTER JOIN` keeps every row from both. This connects to Basic SELECT Queries and Projection: once rows are combined by a join, the same `SELECT` list, `WHERE` filter, and projection machinery applies to the combined rows exactly as it would to a single table.

Conceptually — never literally, for performance reasons discussed below — every join can be understood as a three-step pipeline: form the cross product, apply the join predicate, then project the desired columns. This mental model is exact for inner joins and needs one extra step for outer joins: after filtering, re-insert any row from the preserved side that had zero matching partners, padding the other side's columns with `NULL`.

Inner join, implicit (`WHERE`) style. List the tables in `FROM`, then state equality (or any) conditions in `WHERE`: ```sql SELECT s.name, e.course_id FROM Students AS s, Enrolled AS e WHERE s.id = e.student_id; ```

Inner join, explicit (`JOIN ... ON`) style, semantically identical: ```sql SELECT s.name, e.course_id FROM Students AS s JOIN Enrolled AS e ON s.id = e.student_id; ```

Natural join drops the explicit condition and matches automatically on every column sharing a name in both tables, keeping only one copy of each: ```sql SELECT name, course_id FROM Students NATURAL JOIN Enrolled; ``` This works correctly here because the only shared column, if named consistently (e.g., both called `id`), is the intended join key — but if `Enrolled` happens to also have an unrelated column named, say, `updated_at` that also exists in `Students`, `NATURAL JOIN` will silently add it to the join condition, corrupting results. This is why explicit `JOIN ... ON` or `JOIN ... USING (id)` is generally safer.

Outer joins require the explicit syntax because there is no `WHERE`-only way to reintroduce a row the cross product paired with nothing: ```sql -- Every student, even those enrolled in nothing SELECT s.name, e.course_id FROM Students AS s LEFT OUTER JOIN Enrolled AS e ON s.id = e.student_id; -- Every enrollment, even for student IDs missing from Students SELECT s.name, e.course_id FROM Students AS s RIGHT OUTER JOIN Enrolled AS e ON s.id = e.student_id; -- Every student AND every enrollment, matched where possible SELECT s.name, e.course_id FROM Students AS s FULL OUTER JOIN Enrolled AS e ON s.id = e.student_id; ``` The following pseudocode gives the precise, engine-agnostic semantics — a conceptual nested evaluation that defines what the answer must be, independent of how an optimizer actually computes it (that "how" is the subject of Join Algorithms: Nested-Loop and Query Processing Overview). ```pseudocode function INNER_JOIN(R, S, predicate): result = empty set for r in R: for s in S: if predicate(r, s): result.add(concatenate(r, s)) return result function LEFT_OUTER_JOIN(R, S, predicate): result = empty set for r in R: matched = false for s in S: if predicate(r, s): result.add(concatenate(r, s)) matched = true if not matched: result.add(concatenate(r, NULL_ROW(S))) // pad S's columns with NULL return result function RIGHT_OUTER_JOIN(R, S, predicate): return LEFT_OUTER_JOIN(S, R, swap(predicate)) // symmetry: swap roles function FULL_OUTER_JOIN(R, S, predicate): left = LEFT_OUTER_JOIN(R, S, predicate) right = LEFT_OUTER_JOIN(S, R, swap(predicate)) return UNION(left, right) // duplicates on matched pairs removed by set union ``` A subtlety in `FULL_OUTER_JOIN`: matched pairs appear in both `left` and `right` (once each, in opposite concatenation order), so implementations must normalize concatenation order before taking the union, or equivalently compute matched pairs once and separately append the two sets of unmatched rows. Real database engines never materialize the full cross product; they use algorithms such as block nested-loop join, sort-merge join, or hash join to find matching pairs directly, but all of them must produce results consistent with this conceptual definition.

Correctness argument. The defining invariant of `INNER_JOIN(R, S, predicate)` is: a combined row `(r, s)` appears in the output if and only if `r ∈ R`, `s ∈ S`, and `predicate(r, s)` holds. This is immediate from the algorithm's structure — the nested loop enumerates every pair in `R × S` exactly once, and the `if predicate(r, s)` guard admits a pair to the result exactly when the predicate holds, so the algorithm computes precisely `σ_predicate(R × S)`, matching the relational-algebra definition of theta join. `NATURAL JOIN` and `JOIN ... USING` are the special case where `predicate` is "equality on every shared column name," followed by a projection that keeps only one copy of each shared column; correctness reduces to the inner-join argument plus a straightforward projection fact. For `LEFT_OUTER_JOIN`, the invariant is two-part: (1) every matched pair `(r, s)` with `predicate(r, s)` true appears, by the same argument as inner join; (2) every `r ∈ R` for which no `s ∈ S` satisfies the predicate appears exactly once, padded with `NULL`, because the `matched` flag is set to `true` on the first (and only tested-for) successful match, and rows with `matched = false` after exhausting all of `S` are exactly those with no valid partner — added exactly once, immediately after the inner loop concludes. This shows the output is precisely "inner join, plus unmatched left rows padded with `NULL`," which is the textbook definition of left outer join. `RIGHT_OUTER_JOIN` inherits correctness from `LEFT_OUTER_JOIN` by the symmetry `R RIGHT JOIN S ≡ S LEFT JOIN R` (with roles swapped), and `FULL_OUTER_JOIN`'s correctness follows because a full outer join's row set is exactly the union of "matched pairs," "left-unmatched rows," and "right-unmatched rows," which is precisely what `UNION(LEFT_OUTER_JOIN(R,S), LEFT_OUTER_JOIN(S,R))` computes once duplicate matched pairs are reconciled.

Complexity. Let `|R| = n` and `|S| = m` be the number of rows in the two tables. The naive nested-loop formulation above examines every pair, giving:

because the outer loop runs `n` times and, for each iteration, the inner loop runs `m` times, with the predicate check taking O(1) (or O(k) for a k-column comparison, a constant independent of table size). Space is `O(n·m)` in the worst case (a join condition satisfied by almost all pairs, e.g., a near-Cartesian join), but for a well-selected equijoin on a key with `s`-side fan-out bounded by a small constant, output size — and hence realistic space — is closer to `O(n + m)` or `O(n·s)`. This quadratic bound is the conceptual worst case, not what real systems execute. Because the join condition in practice is almost always an equality on an indexed or sortable column, real query engines replace the nested loop with asymptotically faster algorithms:

• Sort-merge join: sort both relations by the join key — `O(n log n + m log m)` — then merge in a single linear pass, `O(n + m)`, exploiting the sorted order to avoid comparing every pair. Total: `O(n log n + m log m)`.
• Hash join: build an in-memory hash table on the smaller relation, `O(n)`, then probe it with each row of the larger relation, `O(m)` expected time with O(1) expected lookup. Total: `O(n + m)` expected.
• Index nested-loop join: if `S` has an index on the join column, scan `R` once (`O(n)`) and look up matches in `S` via the index (`O(log m)` per lookup for a B-tree), giving `O(n log m)` total.

These algorithmic choices — deferred in full to Join Algorithms: Nested-Loop and the broader Query Processing Overview — are why the conceptual `O(n·m)` cross-product-then-filter model is a correctness specification, never an execution plan: the query optimizer proves that a faster algorithm produces an identical result set, and correctness of that proof rests exactly on the invariants argued above.

Honest tradeoffs. Explicit `JOIN ... ON` syntax is unambiguous and required for outer joins, but adds verbosity for simple multi-table inner joins. `NATURAL JOIN` is concise but brittle under schema evolution — adding an unrelated same-named column anywhere silently changes query semantics. Outer joins preserve information (no silent data loss) but complicate downstream logic, since consumers of the result must handle `NULL` in previously "always populated" columns; forgetting this is the single most common outer-join bug.

Consider two small tables tracking a bookstore's inventory and its orders. `Books`

`Orders`

Note `Orders` references `isbn = 999`, which does not exist in `Books` (a dangling reference, perhaps from a deleted title), and `Books` has `isbn = 333` with no orders at all.

Query 1 — inner join (both syntaxes give identical results): ```sql SELECT b.title, o.qty FROM Books b JOIN Orders o ON b.isbn = o.isbn; ``` Trace of the conceptual algorithm — for each `Books` row, scan all `Orders` rows and keep matches:

Result: 2 rows — `(Dune, 2)`, `(Dune, 1)`. `Foundation` and `Neuromancer` vanish (no orders); order `A3` vanishes (dangling isbn).

Query 2 — left outer join, preserving every book: ```sql SELECT b.title, o.qty FROM Books b LEFT OUTER JOIN Orders o ON b.isbn = o.isbn; ``` `Books` row `222` (Foundation) and `333` (Neuromancer) find no match in `Orders`, so per the `LEFT_OUTER_JOIN` invariant they are emitted once each with `o.qty = NULL`:

Result: 4 rows. Order `A3` (dangling isbn 999) still does not appear, because the left side (`Books`) is what's being preserved, not the right side.

Query 3 — full outer join, preserving everything: ```sql SELECT b.title, o.order_id, o.qty FROM Books b FULL OUTER JOIN Orders o ON b.isbn = o.isbn; ``` Now the unmatched `Orders` row `A3` also survives, with `b.title = NULL`:

Result: 5 rows — every book and every order is represented at least once, exactly matching the correctness invariant that a full outer join is the union of matched pairs, left-unmatched rows, and right-unmatched rows.

A pitfall in miniature: suppose someone tries to "filter to only cheap orders" by writing: ```sql SELECT b.title, o.qty FROM Books b LEFT OUTER JOIN Orders o ON b.isbn = o.isbn WHERE o.qty < 3; ``` The `WHERE o.qty < 3` condition evaluates to `UNKNOWN` (not `TRUE`) for `Foundation` and `Neuromancer`, since `NULL < 3` is `UNKNOWN` in three-valued logic, and `WHERE` keeps only rows evaluating to `TRUE`. So both books silently disappear — the outer join's whole purpose (preserving unmatched rows) is defeated by a post-hoc `WHERE` filter. The fix is to move the condition into the `ON` clause, or guard it explicitly: `WHERE o.qty < 3 OR o.qty IS NULL`.

The join operator originates in the relational model itself, formalized as part of relational algebra before SQL existed as a language, and SQL's join syntax was later standardized and progressively refined across decades of committee work.

Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server, SQLite — implements the full join family described here, and query optimizers in each system spend enormous engineering effort choosing how to execute a logically specified join efficiently, a topic developed in Join Algorithms: Nested-Loop and generalized in Query Processing Overview. Data warehouses (Snowflake, BigQuery, Redshift) built for analytics rely on joins to combine fact tables (transactions, events) with dimension tables (customers, products, dates) in star-schema designs, often at petabyte scale where join algorithm choice is the dominant cost driver. Object-relational mapping (ORM) frameworks like Hibernate, Django ORM, and ActiveRecord translate application-level object relationships into SQL joins behind the scenes, meaning developers who never write raw SQL still depend on correct join semantics whenever they load "a user and their orders" in one round trip. Outer joins specifically underpin reporting and auditing use cases — "list all customers, including those with zero purchases," "list all scheduled jobs, including those that never ran" — where the absence of a matching row is itself meaningful information that an inner join would erase. Data-quality and ETL (extract-transform-load) pipelines frequently use full outer joins to reconcile two snapshots of a dataset, surfacing records present in one version but missing in the other. Understanding joins precisely is also the gateway to Nested Subqueries, since many subquery patterns (correlated subqueries, `EXISTS` checks, `IN` with a subquery) are semantically equivalent to, and often optimized into, joins by the query planner.

Ask the tutor: How would you rewrite a `FULL OUTER JOIN` using only `LEFT JOIN`, `RIGHT JOIN`, and `UNION`, for a database that doesn't support `FULL OUTER JOIN` natively?