clement13.net
Original photo: Un rapporteur, une équerre et un compas posés sur d'anciens plans dessinés.
Description
Un rapporteur, une équerre et un compas posés sur d'anciens plans dessinés.
Source
Sergey Zolkin (szolkin) · original page
Licence
CC0 Public domain
Original photo, unretouched. The background is a version of it stylised by the site.

Principles in detail

Nine ideas for understanding why and how to think in sets.

≈ 5 min readReading
In brief
  1. A relation is a set, with no order.
  2. Operations are closed and composable.
  3. You describe, the optimizer decides.
  4. The row-by-row loop costs something on every iteration.
  5. Define the grain first.
  6. Watch out: order, NULL, determinism.
On this page
  1. 1. The relational model
  2. 2. A declarative language and an optimizer
  3. 3. Why the row-by-row loop is expensive
  4. 4. Thinking in sets: a method
  5. 5. Order does not exist (unless you ask for it)
  6. 6. NULL and three-valued logic
  7. 7. Determinism
  8. 8. Atomicity and transactions
  9. 9. Common mistakes
  10. Sources and verification

1. The relational model#

SQL is based on the relational model proposed by E. F. Codd in 1970: a relation is a set of tuples (rows) characterized by the same attributes (columns). The operations of relational algebra have a decisive property: they are closed, meaning they take relations and return a relation. They can therefore be chained at will.

Relational operationSQL equivalentNote
Selection (σ)WHEREFilters rows according to a property
Projection (π)column list of the SELECTWith DISTINCT to remove duplicates
Join (⋈)JOININNER, LEFT, RIGHT, FULL, CROSS
Union (∪)UNION / UNION ALLUNION ALL keeps duplicates
Intersection (∩)INTERSECT
Difference (−)EXCEPTUseful for comparing two results
Cartesian product (×)CROSS JOINBasis of numbers tables and calendars
Aggregation (γ)GROUP BY, aggregate functionsExtension of basic algebra

SQL departs from the model on three points you need to know: tables can contain duplicates (multisets), the NULL value introduces three-valued logic, and order only exists if you ask for it.

2. A declarative language and an optimizer#

A SQL query describes what you want. The engine turns it into an execution plan in several steps: parsing, object resolution, then cost-based optimization. The optimizer relies on statistics (value distribution) to estimate the number of rows at each step, and chooses:

  • the join order and the algorithm (nested loops, hash join, merge join);
  • the access method (index seek, index or table scan);
  • parallelization and possible use of batch mode.

The more complete the statement, the more latitude the optimizer has. A loop deprives it of this overall view: it only sees isolated statements, one per iteration.

3. Why the row-by-row loop is expensive#

Row-by-row processing is often called RBAR (Row By Agonizing Row, an expression popularized by Jeff Moden). Its costs add up:

  • Per-iteration overhead: fetching the row, assigning variables, launching a statement.
  • Transaction log: without an explicit transaction, each statement is committed separately; the engine waits for the log write on every row.
  • Locks: acquired and released on each iteration, with a risk of prolonged waits under load.
  • No overall view for the optimizer: no global choice of algorithm, limited parallelism.
  • Repeated calls if the loop lives on the client side: one network round trip per row.
Clarification

A loop is not always disastrous: on a few dozen rows, the difference is invisible. The problem appears with volume, and above all with a doubling of volume that doubles (or worse) the processing time.

4. Thinking in sets: a method#

  1. Define the grain of the result: one row = what? (a sale, a customer per month, a date range).
  2. List the input relations: which tables supply the columns?
  3. Express the links with joins, choosing INNER or LEFT depending on whether the absence of a match should exclude or keep the row.
  4. Express the filters as properties (WHERE), not as tests inside a loop.
  5. Express the calculations by grouping (GROUP BY) or by window (OVER).
  6. Check determinism, NULLs and duplicates before validating.

5. Order does not exist (unless you ask for it)#

  • Without ORDER BY in the final query, no order is guaranteed, even if it seems stable in testing.
  • TOP without ORDER BY returns arbitrary rows; with a non-unique ordering, ties are broken arbitrarily too: add a unique key to the ordering.
  • In OVER (ORDER BY …), the order is logical: it defines the calculation window, not the display order.

6. NULL and three-valued logic#

A comparison with NULL is neither true nor false: it is unknown, and WHERE only keeps rows whose predicate is true.

  • COUNT(*) counts rows; COUNT(column) ignores NULLs.
  • A join on a column containing NULL never matches two NULLs.
  • NOT IN with a subquery that may contain NULL returns no rows.
-- Classic pitfall: NOT IN and NULL
DECLARE @A TABLE (v int NULL);
DECLARE @B TABLE (v int NULL);
INSERT INTO @A VALUES (1), (2), (3);
INSERT INTO @B VALUES (1), (NULL);

SELECT v FROM @A WHERE v NOT IN (SELECT v FROM @B);          -- 0 rows! (because of the NULL)
SELECT v FROM @A AS a
WHERE NOT EXISTS (SELECT 1 FROM @B AS b WHERE b.v = a.v);    -- 2 and 3, as expected

To compare two values treating two NULLs as equal:

-- WHERE clause excerpts — "null-safe" comparison (valid before SQL Server 2022)
WHERE EXISTS (SELECT c.Valeur EXCEPT SELECT r.Valeur)   -- true if the two values differ, NULL included

-- SQL Server 2022 and Azure SQL: dedicated operator
WHERE c.Valeur IS DISTINCT FROM r.Valeur

7. Determinism#

A result must depend on the data, not on the plan. Risky cases: an update with a join where several source rows match the same target row, a TOP without a unique ordering, a ROW_NUMBER with ties. Determinism is also an object property that the engine exploits: see Determinism and deterministic objects.

-- Non-deterministic: several rows of B for one row of A
UPDATE a
SET    a.Valeur = b.Valeur
FROM   dbo.A AS a
JOIN   dbo.B AS b ON b.Cle = a.Cle;        -- if B is not unique on Cle, the value retained is arbitrary

-- Make the result deterministic: guarantee the uniqueness of the source
-- (primary key / UNIQUE constraint on B.Cle, or prior aggregation / ROW_NUMBER)

8. Atomicity and transactions#

A statement is atomic: it succeeds entirely or fails entirely. A loop of statements is not: an error at row 40,000 leaves 39,999 rows already modified, unless an explicit transaction was opened around the loop (with its own locking and logging costs).

9. Common mistakes#

  • Replacing a cursor with a WHILE loop that does the same thing: it is the same row-by-row processing.
  • Calling a scalar function in a result column over large volumes (see fake set-based code).
  • Writing a trigger assuming that only one row is inserted: a statement can modify thousands.
  • Believing that a result is sorted because it was in testing.
  • Using NOT IN on a nullable column.
  • Multiplying rows with a join on a non-unique key, then "fixing" it with DISTINCT.

Sources and verification#