Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 79 ยท SQL for Database Courses

Queries Through the Lens of Theory

Read SELECT-FROM-WHERE as relational algebra: bag semantics, the logical evaluation order of a query, how joins and GROUP BY really work, with step-by-step demos.

You already know how to write SQL queries. This lesson asks a different question: what does a query mean? A database course expects you to read a SELECT statement as a small program in relational algebra, to know that SQL tables are bags rather than sets, and to know the logical order in which the clauses are evaluated. That order is not the order you write them in, and many confusing errors (such as using an alias in the wrong place) disappear once you know it.

The engine is free to run a query in any order it likes, as long as the result is the same as the logical order would produce. So treat what follows as the meaning of a query, not as its execution plan; execution is the subject of the query processing pipeline.

The logical order of a query

FROM Join the tables.
WHERE Filter rows.
GROUP BY Form groups.
HAVING Filter groups.

Then SELECT, DISTINCT, ORDER BY and LIMIT.

1 / 2

SELECT-FROM-WHERE as algebra

The core of SQL is the single block SELECT a, b FROM R, S WHERE condition. Its meaning in algebra is

ฯ€(a, b) ( ฯƒ(condition) ( R ร— S ) )

Form the Cartesian product of the FROM tables, keep the rows that satisfy WHERE, and project the SELECT columns. A JOIN ... ON is the same thing written with the condition next to the tables. Because WHERE conditions come out as ฯƒ and the select list as ฯ€, the optimizer can move them around using algebra rules.

Bags, not sets

Relational algebra works on sets: a row is either present or absent. SQL works on bags (also called multisets): the same row can appear several times. That is why SELECT dept FROM employee can return Sales three times, and why SQL needs DISTINCT to get set behaviour. The set operators have two forms for the same reason: UNION removes duplicates, UNION ALL keeps them. The bag rules are exactly the arithmetic you would hope for: if a row occurs 3 times in A and 2 times in B, UNION ALL gives 5, INTERSECT ALL gives 2 and EXCEPT ALL gives 1 (support for the ALL forms of INTERSECT and EXCEPT varies by engine; SQLite lacks them).

SQL Sets versus bags

Press Run (or Ctrl + Enter) to see the result here.

DISTINCT is not free: the engine must sort or hash to find duplicates. Use it when you need set semantics, not as a reflex to hide a join mistake.

The evaluation order

The logical order is:

  1. FROM (and joins): build the combined rows.
  2. WHERE: discard rows for which the condition is not true.
  3. GROUP BY: partition the remaining rows into groups.
  4. HAVING: discard groups.
  5. SELECT: compute the output columns (including aggregates and aliases).
  6. DISTINCT: remove duplicate output rows.
  7. ORDER BY: sort.
  8. LIMIT / OFFSET: cut.

The consequences you can feel are these. WHERE runs before grouping, so it cannot contain aggregates: use HAVING for conditions on groups. Aliases defined in SELECT are created after WHERE, so standard SQL does not let you use them there (SQLite is lenient and allows it, which can hide a bug that fails on PostgreSQL). ORDER BY runs after SELECT, so it can use aliases. Watch the order happen, one stage at a time, on a small order table:

SQL One query, evaluated stage by stage

Press Run (or Ctrl + Enter) to see the result here.

Boris disappears at stage 2 because his only order is below 20. Ana's total is 110 and Chen's is 125 (after dropping the 20); both pass HAVING, and the final statement keeps the largest, Chen.

Joins and aggregation semantics

An inner join keeps only pairs of rows that satisfy the condition. A left outer join keeps every left row, and fills the right columns with NULL when there is no match. Aggregates ignore NULL inputs, except count(*), which counts rows. Careful with a left join followed by an aggregate: counting the right table's column gives 0 for unmatched rows, while count(*) gives 1.

An important rule for GROUP BY queries: every column in the select list must either be in the GROUP BY clause or be inside an aggregate function. Standard SQL rejects other queries because a group has many values of that column. SQLite allows them and returns an arbitrary value from the group, so do not rely on it. Another subtlety is that NULLs compare as equal for grouping: all rows with a NULL key fall into one group, even though NULL = NULL is not true in a WHERE clause. See Nulls and Three-Valued Logic.

SQL Outer join, NULL and counting

Press Run (or Ctrl + Enter) to see the result here.

Legal has no employees, yet it appears (outer join). Its count(*) is 1 because the join produced one padded row, while count(e.id) is 0. Research has two employees but only one non-null bonus, and sum ignores the NULL. A group that has no non-null inputs returns NULL for sum, not 0.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which clause is evaluated first in the logical order of a query?

    FROM (with joins) builds the input rows. WHERE, GROUP BY, HAVING, SELECT, DISTINCT, ORDER BY and LIMIT follow.
  2. 2. Why can't a WHERE clause contain sum(amount) > 100?

    Aggregates are computed per group, and groups are formed after WHERE. Conditions on aggregates belong in HAVING.
  3. 3. Table A has the row 7 three times and table B has it twice. How many times does it occur in A UNION ALL B?

    UNION ALL adds the multiplicities (bag semantics). UNION would remove duplicates and return the row once.
  4. 4. What is the algebra form of SELECT a FROM R, S WHERE c?

    Product of the FROM tables, selection by the WHERE condition, projection of the select list.

Summary

  • A single-block query means ฯ€(select list)(ฯƒ(where)(product of FROM tables)).
  • SQL tables are bags; DISTINCT, UNION, INTERSECT and EXCEPT give set behaviour, UNION ALL keeps duplicates.
  • Logical order: FROM, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, ORDER BY, LIMIT; the engine may execute differently if the result is the same.
  • Aggregates ignore NULL (except count(*)); outer joins pad with NULL; NULLs form one group.
  • Select-list columns must be grouped or aggregated; SQLite lets other queries through, but they are not portable.

Next: Nested Queries, Views and Materialization.