How SQL evaluates a query: logical order

A SQL query describes a result, and SQL defines that result through a fixed logical order. FROM builds the input rows, WHERE keeps some of them, GROUP BY forms groups and computes aggregates, HAVING keeps some groups, SELECT computes the output columns, DISTINCT removes duplicate rows, UNION, INTERSECT and EXCEPT combine whole results, ORDER BY sorts, and LIMIT keeps a slice. Almost every step is an operator of relational algebra applied to a bag of rows, a collection in which the same row may appear several times. The order decides what a query means, which names each clause can see and how many rows come out. It does not decide how the engine computes the answer: any plan that returns the same rows is allowed.

This lesson maps each clause to an operator of relational algebra, counts rows through the steps of a real query, and shows where SQLite and PostgreSQL read the same text differently. Alias errors are drilled in the SQL track’s lesson on the order of execution; this one looks at the algebra underneath.

The logical order, clause by clause

1. FROM, a product (×) or a join: the tables go in, one bag of combined rows comes out.
2. WHERE, a selection (σ): it keeps the rows whose condition is TRUE.
3. GROUP BY with the aggregates, grouping (γ): one row per group comes out, with its aggregates.
4. HAVING, a selection on the groups: it keeps the groups whose condition is TRUE.
5. SELECT, a projection (π): it computes the output columns and keeps duplicate rows.
6. DISTINCT, duplicate elimination (δ): the bag becomes a set.
7. UNION, INTERSECT and EXCEPT (∪, ∩, −): two results go in, one comes out.
8. ORDER BY, a sort (τ): the bag becomes an ordered list.
9. LIMIT and OFFSET: a slice of that list, with no operator of its own.

PostgreSQL’s manual describes the processing of a SELECT in this order, with WITH queries computed first and row locks (FOR UPDATE) taken last (PostgreSQL 18: SELECT). SQLite’s manual walks through the same steps and warns that the walk is only an explanation: no engine has to follow it, as long as the result is the one it defines (SQLite: SELECT).

Two consequences follow straight from the list. A clause can only use what an earlier step produced, so WHERE cannot filter on an aggregate, which step 3 computes later. And only steps 8 and 9 know about order: everything before them works on bags, which have no first or last row.

SELECT-FROM-WHERE is π over σ over ×

The core of most queries is one block of SELECT, FROM and WHERE. In algebra it reads from the inside out: take the product of the tables, select the rows that satisfy the condition, then project the columns asked for.

Here θ is the condition s.roll = e.roll AND e.code LIKE 'CS%', S the students and E the enrolments. The same expression as SQL, followed by the result of each step, on four students and six enrolments:

-- Four students and six enrolments. Which departments have a student in a CS course?
CREATE TABLE students (roll INTEGER PRIMARY KEY, name TEXT NOT NULL, dept TEXT NOT NULL);
CREATE TABLE enrolments (roll INTEGER NOT NULL, code TEXT NOT NULL);
INSERT INTO students VALUES (101, 'Aarav', 'CSE'), (102, 'Diya', 'ECE'), (103, 'Kabir', 'CSE'), (104, 'Meera', 'ME');
INSERT INTO enrolments VALUES
  (101, 'CS201'), (101, 'CS202'), (102, 'CS201'),
  (102, 'EC210'), (103, 'CS201'), (104, 'ME105');

-- The whole query.
SELECT DISTINCT s.dept
FROM students AS s, enrolments AS e
WHERE s.roll = e.roll AND e.code LIKE 'CS%'
ORDER BY s.dept;

-- Step 1, FROM: the product of the two tables, 4 x 6 rows.
SELECT count(*) AS rows_after_from FROM students AS s, enrolments AS e;

-- Step 2, WHERE: only the pairs that satisfy the condition stay.
SELECT s.roll, s.dept, e.code
FROM students AS s, enrolments AS e
WHERE s.roll = e.roll AND e.code LIKE 'CS%';

-- Step 3, SELECT: one output row per remaining pair, duplicates kept.
SELECT s.dept
FROM students AS s, enrolments AS e
WHERE s.roll = e.roll AND e.code LIKE 'CS%';

┌──────┐
│ dept │
├──────┤
│ CSE  │
│ ECE  │
└──────┘
┌─────────────────┐
│ rows_after_from │
├─────────────────┤
│ 24              │
└─────────────────┘
┌──────┬──────┬───────┐
│ roll │ dept │ code  │
├──────┼──────┼───────┤
│ 101  │ CSE  │ CS201 │
│ 101  │ CSE  │ CS202 │
│ 102  │ ECE  │ CS201 │
│ 103  │ CSE  │ CS201 │
└──────┴──────┴───────┘
┌──────┐
│ dept │
├──────┤
│ CSE  │
│ CSE  │
│ ECE  │
│ CSE  │
└──────┘

The row counts tell the story:

• After FROM: 24 rows. A product pairs every student with every enrolment, so its size is the product of the sizes, 4 × 6. Most of these pairs make no sense (Aarav paired with Meera’s enrolment), which is why the condition that matches the roll numbers matters.
• After WHERE: 4 rows. Only the pairs with equal roll numbers and a course code starting with CS survive.
• After SELECT: still 4 rows. Projection keeps one output row per input row. CSE appears three times because three surviving pairs belong to CSE students: Aarav twice (CS201 and CS202) and Kabir once.
• After DISTINCT: 2 rows, CSE and ECE. Meera’s only enrolment is in ME105, so ME never appeared.

The third step is where SQL parts company with classical relational algebra, which works on sets, so that its π removes duplicates by itself. SQL’s SELECT works on bags and keeps every copy; only DISTINCT removes them. An exam question that asks “how many rows does this query return” is really asking whether you counted copies or values.

Duplicates through the set operators

Each set operator has two forms: the plain one returns a set, and the ALL form keeps copies. If a row appears m times in the first result and n times in the second, the operators return it this many times:

With m = 3 and n = 2 that makes 5 copies for UNION ALL, 2 for INTERSECT ALL, 1 for EXCEPT ALL, 1 each for UNION and INTERSECT, and none for EXCEPT.

The ALL rules for INTERSECT and EXCEPT are the ones PostgreSQL’s manual states, and without ALL all three operators remove duplicates (PostgreSQL 18: SELECT). Note the asymmetry with SELECT: a plain SELECT keeps duplicates unless you write DISTINCT, while a plain UNION removes them unless you write ALL.

Two bags of course codes make this concrete. Bag A holds CS201 three times, CS202 once and MA101 once; bag B holds CS201 twice and CS202 twice:

-- Two bags of course codes: A holds CS201 three times, B twice.
CREATE TABLE a (code TEXT);
CREATE TABLE b (code TEXT);
INSERT INTO a VALUES ('CS201'), ('CS201'), ('CS201'), ('CS202'), ('MA101');
INSERT INTO b VALUES ('CS201'), ('CS201'), ('CS202'), ('CS202');

SELECT 'UNION ALL' AS operation, count(*) AS result_rows FROM (SELECT code FROM a UNION ALL SELECT code FROM b)
UNION ALL
SELECT 'UNION', count(*) FROM (SELECT code FROM a UNION SELECT code FROM b)
UNION ALL
SELECT 'INTERSECT', count(*) FROM (SELECT code FROM a INTERSECT SELECT code FROM b)
UNION ALL
SELECT 'EXCEPT', count(*) FROM (SELECT code FROM a EXCEPT SELECT code FROM b);

-- SQLite has no bag versions of INTERSECT and EXCEPT.
SELECT code FROM a INTERSECT ALL SELECT code FROM b;

┌───────────┬─────────────┐
│ operation │ result_rows │
├───────────┼─────────────┤
│ UNION ALL │ 9           │
│ UNION     │ 3           │
│ INTERSECT │ 2           │
│ EXCEPT    │ 1           │
└───────────┴─────────────┘

Parse error near line 16: near "ALL": syntax error

UNION ALL returns all 9 rows. UNION returns 3 distinct codes, INTERSECT the 2 codes both bags contain, and EXCEPT only MA101, the code that B lacks. The error at the end is SQLite’s: its grammar has UNION ALL but no ALL form of INTERSECT or EXCEPT (SQLite: compound SELECT), while PostgreSQL accepts both.

Bag intersection and difference in SQLite

The multiplicity rules suggest a portable way to get the ALL forms anyway. Number the copies of each value in each bag with row_number(): the copy numbered k exists in a bag exactly when the bag holds at least k copies. Two copies with the same value and number are then ordinary rows, and the plain set operators can compare them:

-- INTERSECT ALL and EXCEPT ALL in SQLite: number the copies of each value, then use the set operators.
CREATE TABLE a (code TEXT);
CREATE TABLE b (code TEXT);
INSERT INTO a VALUES ('CS201'), ('CS201'), ('CS201'), ('CS202'), ('MA101');
INSERT INTO b VALUES ('CS201'), ('CS201'), ('CS202'), ('CS202');

-- Copy k of a value exists in a bag when the bag holds at least k copies of it.
CREATE VIEW a_copies AS SELECT code, row_number() OVER (PARTITION BY code) AS k FROM a;
CREATE VIEW b_copies AS SELECT code, row_number() OVER (PARTITION BY code) AS k FROM b;

-- A INTERSECT ALL B: the copies both bags have, min(m, n) of each value.
SELECT code FROM (SELECT code, k FROM a_copies INTERSECT SELECT code, k FROM b_copies)
ORDER BY code;

-- A EXCEPT ALL B: the copies only A has, max(m - n, 0) of each value.
SELECT code FROM (SELECT code, k FROM a_copies EXCEPT SELECT code, k FROM b_copies)
ORDER BY code;

┌───────┐
│ code  │
├───────┤
│ CS201 │
│ CS201 │
│ CS202 │
└───────┘
┌───────┐
│ code  │
├───────┤
│ CS201 │
│ MA101 │
└───────┘

The intersection keeps copies 1 and 2 of CS201 (both bags have them) and copy 1 of CS202, which is min(m, n) copies of each code. The difference keeps copy 3 of CS201, which only A has, and MA101: max(m − n, 0) copies. PostgreSQL’s own INTERSECT ALL and EXCEPT ALL return the same rows for these two bags. row_number() without an ORDER BY inside its window numbers the copies in an arbitrary order, which does no harm here, since copies of one value are indistinguishable.

Which set operator binds first

With three results and two operators, something has to decide the grouping, and the two engines decide differently:

• PostgreSQL gives INTERSECT a higher precedence than UNION and EXCEPT, which group from left to right. So A UNION B INTERSECT C means A UNION (B INTERSECT C) (PostgreSQL 18: SELECT). MySQL 8.4 does the same (MySQL 8.4: set operations).
• SQLite groups every compound operator from left to right, so the same text means (A UNION B) INTERSECT C (SQLite: compound SELECT).

-- Three one-column results: who registered, who paid the fee, who submitted the form.
CREATE TABLE registered (roll INTEGER);
CREATE TABLE paid (roll INTEGER);
CREATE TABLE submitted (roll INTEGER);
INSERT INTO registered VALUES (101), (102);
INSERT INTO paid VALUES (102), (103);
INSERT INTO submitted VALUES (103), (104);

-- As SQLite reads it: (registered UNION paid) INTERSECT submitted.
SELECT roll FROM registered
UNION
SELECT roll FROM paid
INTERSECT
SELECT roll FROM submitted;

-- As PostgreSQL reads the same text: registered UNION (paid INTERSECT submitted).
SELECT roll FROM registered
UNION
SELECT roll FROM (SELECT roll FROM paid INTERSECT SELECT roll FROM submitted)
ORDER BY roll;

-- PostgreSQL also accepts parentheses around a member of a compound query; SQLite does not.
SELECT roll FROM registered
UNION
(SELECT roll FROM paid INTERSECT SELECT roll FROM submitted);

┌──────┐
│ roll │
├──────┤
│ 103  │
└──────┘
┌──────┐
│ roll │
├──────┤
│ 101  │
│ 102  │
│ 103  │
└──────┘

Parse error near line 23: near "(": syntax error

The first query is SQLite’s reading: the students who registered or paid, among those who submitted, which is only 103. The second spells out PostgreSQL’s reading of the same text with a subquery, so that SQLite can run it too: the students who registered, plus those who both paid and submitted, which is 101, 102 and 103. Neither engine reports an error for the first text, so the difference shows up only in the result.

The third query is the usual way to state the grouping, and it is where the engines part again: PostgreSQL accepts parentheses around a member of a compound query (PostgreSQL 18: combining queries), while SQLite rejects them, because each member must be a simple SELECT. Whenever a compound query mixes INTERSECT with UNION or EXCEPT, put the inner operation in a subquery in FROM, as the second query does: both engines accept that form and read it the same way.

What each step can see

The order also explains which names a clause can use. An output column’s alias is created in step 5, so clauses that run later, such as ORDER BY, can use it, and clauses that run earlier cannot. PostgreSQL holds to that with one extension: an alias works in ORDER BY and also in GROUP BY, but not in WHERE or HAVING (PostgreSQL 18: SELECT), and WHERE dbl > 100 fails with “column “dbl” does not exist”. SQLite is more lenient, as the first query below shows:

CREATE TABLE marks (roll INTEGER, score INTEGER);
INSERT INTO marks VALUES (101, 35), (102, 72), (103, 58);

-- An output alias in WHERE: SQLite looks the name up among the aliases when no column has it.
SELECT roll, score * 2 AS dbl FROM marks WHERE dbl > 100;

-- Integer and real division.
SELECT 7 / 2 AS int_div, 7 / 2.0 AS real_div, 7 % 2 AS remainder;

-- Bag intersection is not part of SQLite's grammar.
SELECT roll FROM marks INTERSECT ALL SELECT roll FROM marks;

┌──────┬─────┐
│ roll │ dbl │
├──────┼─────┤
│ 102  │ 144 │
│ 103  │ 116 │
└──────┴─────┘
┌─────────┬──────────┬───────────┐
│ int_div │ real_div │ remainder │
├─────────┼──────────┼───────────┤
│ 3       │ 3.5      │ 1         │
└─────────┴──────────┴───────────┘

Parse error near line 11: near "ALL": syntax error

• An alias in WHERE. SQLite looks the name up among the output aliases when no input column has it, and runs the query. The same text fails in PostgreSQL, so never rely on it in code that has to move between engines.
• Division. 7 / 2 is 3 in both engines, because both truncate the quotient of two integers towards zero (PostgreSQL 18: mathematical operators, SQLite: operators). Make either operand a decimal number, 7 / 2.0, to get 3.5.
• INTERSECT ALL is a syntax error in SQLite, as before.

The logical order is about clauses, not about the parts of one expression. Inside a WHERE condition, the order in which the operands of AND and OR are evaluated is not defined, and the planner may rearrange a condition in any way Boolean algebra allows. PostgreSQL’s manual gives WHERE x > 0 AND y/x > 1.5 as a condition that can still divide by zero, and recommends CASE when the order really matters (PostgreSQL 18: expression evaluation rules).

The logical order is not the plan

The pipeline example built a 24-row product on paper, but no engine would build it for this query. EXPLAIN QUERY PLAN shows what SQLite actually does with the same query (SQLite: EXPLAIN QUERY PLAN):

CREATE TABLE students (roll INTEGER PRIMARY KEY, name TEXT NOT NULL, dept TEXT NOT NULL);
CREATE TABLE enrolments (roll INTEGER NOT NULL, code TEXT NOT NULL);

-- The plan SQLite chooses for the query of the first example.
EXPLAIN QUERY PLAN
SELECT DISTINCT s.dept
FROM students AS s, enrolments AS e
WHERE s.roll = e.roll AND e.code LIKE 'CS%'
ORDER BY s.dept;

┌────┬────────┬─────────┬──────────────────────────────────────────────┐
│ id │ parent │ notused │                    detail                    │
├────┼────────┼─────────┼──────────────────────────────────────────────┤
│ 8  │ 0      │ 216     │ SCAN e                                       │
│ 13 │ 0      │ 45      │ SEARCH s USING INTEGER PRIMARY KEY (rowid=?) │
│ 16 │ 0      │ 0       │ USE TEMP B-TREE FOR DISTINCT                 │
└────┴────────┴─────────┴──────────────────────────────────────────────┘

Read the detail column from top to bottom. SQLite scans the enrolments once (SCAN e), finds the student of each enrolment through the primary key on roll (SEARCH s USING INTEGER PRIMARY KEY), and removes duplicate departments with a temporary B-tree, the sorted structure SQLite uses for DISTINCT, GROUP BY and ORDER BY. There is no product step at all, and no separate sort for ORDER BY either. The plan is a faster route to exactly the rows the logical order defines, which is the only promise an optimiser has to keep. SQLite’s manual warns that the format of this output may change between releases, so read it as a description, not as an interface. The track’s query-processing module looks at how such plans are chosen.

ORDER BY and LIMIT, the only steps that see order

Up to step 7 a result is a bag, and a bag has no order. Without ORDER BY, SQLite’s manual calls the order of the returned rows undefined, and PostgreSQL returns them in whatever order is fastest to produce. Three rules follow:

• ORDER BY applies to the whole compound query. In SELECT … UNION SELECT … ORDER BY x, the sort runs after the union, on its result, in both engines.
• LIMIT keeps a slice of the sorted list, so without ORDER BY it returns some rows, not particular ones. PostgreSQL’s manual advises an ORDER BY that makes the order unique whenever you use LIMIT.
• Ties are a choice too. ORDER BY marks DESC LIMIT 1 returns one of the students with the top marks, and which one may change from run to run. Add a column that breaks ties, such as roll, when the answer must be repeatable.

Interview questions

Fresher · In what logical order does SQL evaluate the clauses of a SELECT, and why does that order matter?

The order is FROM, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, then the set operators, ORDER BY and LIMIT. It defines what the query means: each clause works on the output of the one before it, so WHERE filters rows before any group exists and therefore cannot use an aggregate, HAVING filters whole groups, and an alias defined in SELECT is visible in ORDER BY but not in WHERE. It also explains row counts: SELECT keeps duplicates and only DISTINCT removes them. A good answer adds that the order is logical, not physical: the optimiser may use indexes, reorder joins or stop early, as long as the result is the same.

Key takeaways

• A SELECT means the pipeline FROM, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, set operators, ORDER BY, LIMIT, whatever order the clauses are written in.
• SELECT a FROM r, s WHERE p is π over σ over ×, but on bags: SQL’s projection keeps every copy and only DISTINCT removes them.
• With m and n copies of a row, UNION ALL returns m + n, INTERSECT ALL min(m, n) and EXCEPT ALL max(m − n, 0); the plain forms return sets.
• SQLite has no INTERSECT ALL or EXCEPT ALL; numbering copies with row_number() rebuilds them from the plain operators.
• INTERSECT binds first in PostgreSQL and MySQL; SQLite groups compound operators left to right. Use a subquery to make the grouping explicit.
• The logical order defines the answer, not the plan: engines skip products, use indexes and sort with B-trees, as long as the rows are the same.