Joins

Relational databases split data across tables to avoid duplication: customers in one table, orders in another, linked by orders.customer_id. A join puts them back together for a query by pairing rows whose join condition (usually in ON) is TRUE.

INNER JOIN keeps only pairs that match. LEFT JOIN keeps every row of the left table and fills the right side with NULLs when there is no match; RIGHT JOIN is the mirror image. FULL OUTER JOIN keeps unmatched rows from both sides. CROSS JOIN pairs every row with every row, giving m x n rows.

A self join joins a table to itself under two aliases, for example employees e JOIN employees m ON e.manager_id = m.id to show each employee next to their manager.

1. 1Conceptually, a join starts from every combination of left and right rows (the cross product) and keeps the pairs where the ON condition is TRUE. Real databases never build the full cross product; they use a smarter algorithm.
2. 2For an outer join, any left row (LEFT JOIN) or right row (RIGHT JOIN) or either (FULL JOIN) that found no partner is added back once, with NULLs for the other table's columns.
3. 3ON decides which rows match. WHERE runs after the join and filters the joined result. For inner joins the two are equivalent; for outer joins they are not, because WHERE also sees the NULL-filled rows.
4. 4Each left row appears once per matching right row. Joining one customer to 3 orders produces 3 rows, so joining to two different one-to-many tables at once multiplies rows (3 orders x 4 tickets = 12 rows per customer).
5. 5The engine chooses a physical algorithm: nested loop (good when one side is small or the inner side has an index), hash join (build a hash table on the smaller input, probe with the other; good for large equality joins) or merge join (walk two sorted inputs together). PostgreSQL has all three; MySQL uses nested loops and, since 8.0.18, hash joins.

-- customers(id, name), orders(id, customer_id, amount)

-- Every customer with their orders (customers without orders kept)
SELECT c.name, o.id AS order_id, o.amount
FROM customers c
LEFT JOIN orders o
  ON o.customer_id = c.id
 AND o.amount > 25          -- filter on the right table goes in ON
ORDER BY c.name, o.id;

-- Customers who never ordered (anti-join)
SELECT c.name
FROM customers c
WHERE NOT EXISTS (
  SELECT 1 FROM orders o WHERE o.customer_id = c.id
);

-- Each employee with their manager (self join)
SELECT e.name AS employee, m.name AS manager
FROM employees e
LEFT JOIN employees m ON m.id = e.manager_id;

On the example tables, the first query returns (Ana, 101, 50), (Ana, 102, 30), (Mei, NULL, NULL), (Raj, NULL, NULL): Raj stays because the amount filter is in ON. The second returns Mei. The self join keeps employees with no manager because it is a LEFT JOIN.

Cost: Nested loop: O(n x m) in the worst case, O(n log m) with an index on the inner table. Hash join: about O(n + m) time with memory for the smaller side. Merge join: O(n + m) on already-sorted inputs, plus O(n log n) to sort if they are not.