The operations underneath SQL

SQL is a language. Underneath it is a small set of operations on sets of rows, and every query is a combination of them. Knowing them makes query plans readable, because a plan is written in these terms rather than in SQL.

The operations

Select, written with the Greek letter sigma, keeps rows matching a condition. In SQL this is WHERE.

Project, written pi, keeps only named columns and removes duplicates. In SQL this is the column list after SELECT.

Union, intersection and difference work as they do on sets, and require both sides to have the same shape.

Cartesian product pairs every row of one with every row of the other. A table of 1,000 and a table of 1,000 gives a million rows, which is what a missing join condition produces.

Join is a product followed by a select. That is not a metaphor, it is the definition, and it is why a join with no condition is a product.

Rename, written rho, gives a relation or a column a new name so it can be used twice, which is what a self join needs.

Mapping to SQL

SELECT name FROM customers WHERE city = 'Chennai';

is project(name) applied to select(city = 'Chennai') applied to customers.

Why the order matters

These two produce the same answer:

select(amount > 1000, join(orders, customers))
join(select(amount > 1000, orders), customers)

The second filters first, so the join handles far fewer rows. A query optimiser spends most of its effort on exactly this kind of rewriting, and pushing the selection down is the most valuable one it does.

You do not have to do it yourself; the planner usually will. Knowing it is happening is what makes a plan comprehensible when it does not.

One thing SQL adds

Relational algebra works on sets, so duplicates do not exist. SQL works on multisets, so they do. That is why SELECT city FROM customers returns the same city many times while the algebra's project would not, and why UNION ALL exists alongside UNION.