--- title: 'Advanced SQL' source: 'https://academia.sh/en/courses/advanced-sql' language: en updated: '2026-08-23T07:00:36+00:00' license: 'CC BY-SA 4.0' lessons: 20 outcomes: - 'Uses subqueries, common table expressions, and window functions in the right place' - 'Explains transactions and isolation levels through their behavior' - 'Reads a query plan and improves the query by rewriting it' --- # Advanced SQL An intermediate course that teaches how to build a multi-step computation inside a single query with subqueries, common table expressions, recursive queries, and window functions; transaction, isolation, and locking behavior; and how to read a query plan and rewrite the query. ## Compound Queries Scalar, row, and table subqueries, the per-row cost of a correlated subquery, common table expressions, hierarchy traversal with recursive queries, window and ranking functions, and pivot operations. ### Subqueries Source: https://academia.sh/en/courses/advanced-sql/subqueries Where scalar, row, and table subqueries are written, derived tables, the difference between IN and EXISTS, and a null value silently emptying a subquery's result. The SQL Fundamentals course built statements that produce a single result set: selecting rows, joining tables, grouping and summarizing. What these statements share is that the computation finishes in **one step**. Real questions, though, are often two steps: the question "members who borrowed more than the average" first needs the average, then needs whichever members exceed it. Questions like this can be answered with two separate queries whose results are combined by hand, but the data can change between queries and carrying an intermediate result over is wasted work. SQL's answer is to place one query inside another. The previous course used this placement only to write a condition; here it is treated as a construct in its own right. This lesson builds the forms that placement takes and where each one can be written. #### Subqueries and the Shape They Return A **subquery** is a `SELECT` statement embedded in parentheses inside another statement. The one thing that determines where it can be written is the **shape it returns**: | Shape | What it returns | Where it is used | |---|---|---| | Scalar subquery | One row, one column | Anywhere a single value can appear | | Row subquery | One row, many columns | In row comparisons | | Table subquery | Many rows, many columns | `FROM`, `IN`, `EXISTS` | This triple is the skeleton of the lesson. When the shape does not match, the engine raises an error; when the shape matches but the result is unexpected, a null value is almost always the cause — the last section of the lesson takes that up. The same example runs through the whole course: a library's loan records. There are four tables — `branch`, `member`, `book`, and `loan`. Each code block sets up the tables it needs on its own; copied and run as written, a block produces the output shown. #### Scalar Subquery A scalar subquery produces exactly one value, so it can be written anywhere a constant or a column name would be written. Its most common place is the right side of a comparison. The question "members who borrowed more books than the average member" is expressed with a scalar subquery inside `HAVING`: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5), (5,'Evan',6),(6,'Fiona',6),(7,'Grace',4),(8,'Hannah',5); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); SELECT m.name, COUNT(*) AS count FROM loan l JOIN member m ON m.id = l.member_id GROUP BY m.id, m.name HAVING COUNT(*) > (SELECT COUNT(*) * 1.0 / COUNT(DISTINCT member_id) FROM loan) ORDER BY count DESC, m.name; SQL ``` ```text ┌───────┬───────┐ │ name │ count │ ├───────┼───────┤ │ Alice │ 5 │ │ Ben │ 4 │ │ Clara │ 4 │ └───────┴───────┘ ``` The subquery does not reference any column of the outer query. This independence has two consequences: the engine evaluates it **once** and treats the result as a constant, and the subquery can be run by itself and verified in isolation. Once a link is drawn between the subquery and the outer query the picture changes — that is the subject of the next lesson. The scalar subquery's contract is strict: it must return **at most one row**. If it returns zero rows the result is a null value; if it returns more than one row, the standard requires an error. For this reason scalar subqueries either contain an aggregate function or are filtered down to a key. #### Row Subquery A comparison does not have to be limited to single values. Standard SQL also compares row values: the parenthesized column list on the left is matched, column by column, against the row a subquery on the right returns. ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (2,3,1,'2024-03-01','2024-03-20'),(11,3,3,'2024-03-06','2024-03-27'), (22,3,6,'2024-03-20',NULL),(3,5,1,'2024-03-04','2024-03-18'); SELECT id, book_id, member_id, pickup FROM loan WHERE (book_id, pickup) = (SELECT book_id, MIN(pickup) FROM loan WHERE book_id = 3); SQL ``` ```text ┌────┬─────────┬───────────┬────────────┐ │ id │ book_id │ member_id │ pickup │ ├────┼─────────┼───────────┼────────────┤ │ 2 │ 3 │ 1 │ 2024-03-01 │ └────┴─────────┴───────────┴────────────┘ ``` Row comparison writes a question that holds two conditions together, such as "the **first** loan of this book," as a single expression. The same result can be reached with two separate scalar subqueries, but that phrasing visually loses the fact that both subqueries come from the same row. Row value comparison is standard, but the degree of support varies by engine, and it varies further when combined with ordering operators (`<`, `>`). If portable code is being written, the target engine's support has to be confirmed. #### Table Subquery and Derived Tables A subquery that returns many rows behaves like a table. It has two uses. The first is appearing inside `FROM` as a **derived table**. This is the standard way to write two-layer computations, such as regrouping the result of a grouping: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); SELECT MIN(count) AS minimum, MAX(count) AS maximum, ROUND(AVG(count), 2) AS average FROM (SELECT member_id, COUNT(*) AS count FROM loan GROUP BY member_id) AS tally; SQL ``` ```text ┌─────────┬─────────┬─────────┐ │ minimum │ maximum │ average │ ├─────────┼─────────┼─────────┤ │ 1 │ 5 │ 3.13 │ └─────────┴─────────┴─────────┘ ``` An aggregate function cannot be nested directly; `AVG(COUNT(*))` is invalid. A derived table turns the inner computation into a table, which opens the way for the outer computation. Giving the derived table an **alias** (here `tally`) is required, because the outer query refers to it by name. The second use is a table subquery appearing as a **list** in a filter: `WHERE id IN (SELECT …)`. This phrasing reads well, but its negation, `NOT IN`, behaves incorrectly, and silently, once a null value gets mixed into the list. #### A Null Value Emptying the List Suppose lost-item reports at the library are kept in a separate table. If a report has not yet identified which book it belongs to, its `book_id` column is left null when the row is recorded. Both "books with a lost report" and "books without one" can be written with `IN`: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, genre TEXT); INSERT INTO book VALUES (1,'Lost Time','fiction'),(2,'Silent House','fiction'), (3,'Number Theory','science'),(4,'The Structure of the Universe','science'); CREATE TABLE lost(id INTEGER PRIMARY KEY, book_id INT, reported TEXT); INSERT INTO lost VALUES (1,2,'2024-03-08'),(2,NULL,'2024-03-19'); SELECT title FROM book WHERE id IN (SELECT book_id FROM lost); SELECT title FROM book WHERE id NOT IN (SELECT book_id FROM lost); SQL ``` ```text ┌──────────────┐ │ title │ ├──────────────┤ │ Silent House │ └──────────────┘ ``` The first query gave one row, as expected. The second query gave **no rows** at all, which is why only one table appears in the output. Yet three books have no lost report. The cause is the three-valued logic introduced in the Data Modeling and Relational Theory course. The expression `x NOT IN (a, b)` means `x <> a AND x <> b`. If the list contains a null value, that comparison is neither true nor false — it becomes **unknown**, and an unknown factor in a conjunction pulls the whole result to unknown, so the unknown row does not pass the filter: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, genre TEXT); INSERT INTO book VALUES (1,'Lost Time','fiction'),(2,'Silent House','fiction'), (3,'Number Theory','science'),(4,'The Structure of the Universe','science'); CREATE TABLE lost(id INTEGER PRIMARY KEY, book_id INT, reported TEXT); INSERT INTO lost VALUES (1,2,'2024-03-08'),(2,NULL,'2024-03-19'); SELECT 3 IN (2, NULL) AS "3 IN (2,NULL)", 3 NOT IN (2, NULL) AS "3 NOT IN (2,NULL)"; SELECT title FROM book b WHERE NOT EXISTS (SELECT 1 FROM lost y WHERE y.book_id = b.id); SQL ``` ```text ┌───────────────┬───────────────────┐ │ 3 IN (2,NULL) │ 3 NOT IN (2,NULL) │ ├───────────────┼───────────────────┤ │ │ │ └───────────────┴───────────────────┘ ┌───────────────────────────────┐ │ title │ ├───────────────────────────────┤ │ Lost Time │ │ Number Theory │ │ The Structure of the Universe │ └───────────────────────────────┘ ``` The two blank cells in the first row show that both expressions produced a null value: neither true nor false. `EXISTS`, in contrast, asks a different question — "**does** a matching row exist" — and its answer is always true or false; it never produces a null value. This is why `NOT EXISTS` returned all three books. As a rule: if the column a subquery returns can hold a null value, `NOT IN` is replaced with `NOT EXISTS`, or a `WHERE book_id IS NOT NULL` condition is added to the subquery. If the schema guarantees the column cannot be null, `NOT IN` is safe. #### Where a Subquery Can Be Written There are four positions where a subquery can be written, and each has a typical job: - In the `SELECT` list: producing one additional value per row. - Inside `FROM`: turning an intermediate result into a table. - Inside `WHERE`: filtering rows against another query's result. - Inside `HAVING`: filtering groups against another query's result. A subquery in the `SELECT` list reads well, but it hides its cost: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (4,7,1,'2024-03-11',NULL),(6,2,2,'2024-03-01','2024-03-12'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'); SELECT m.name, (SELECT COUNT(*) FROM loan l WHERE l.member_id = m.id) AS total, (SELECT MAX(pickup) FROM loan) AS last_transaction_date FROM member m ORDER BY m.id; SQL ``` ```text ┌───────┬───────┬───────────────────────┐ │ name │ total │ last_transaction_date │ ├───────┼───────┼───────────────────────┤ │ Alice │ 3 │ 2024-03-21 │ │ Ben │ 2 │ 2024-03-21 │ │ Clara │ 1 │ 2024-03-21 │ │ Derek │ 0 │ 2024-03-21 │ └───────┴───────┴───────────────────────┘ ``` The two columns in the output look alike, but their structure differs. The subquery in the third column does not depend on the outer query; it is computed once and copied to every row. The subquery in the second column depends on the outer row through `m.id`: it has to be evaluated separately for every member. This link multiplies the subquery's cost by the number of rows. A side benefit of this phrasing also becomes visible: `Derek`, who has no loan record at all, gets a zero. Written with an inner join, this member would drop out of the result entirely, and getting the member back would require an outer join; the subquery produced a zero when there was no match. #### Summary - A subquery is classified as scalar, row, or table by the shape it returns; the shape determines where it can be written. - A scalar subquery must return at most one row; zero rows produce a null value. - A derived table inside `FROM` is the standard way to layer aggregate functions, and it must be given an alias. - If the subquery's column can hold a null value, `NOT IN` silently returns an empty result; `NOT EXISTS` gives the correct answer because it is unaffected by three-valued logic. - A subquery that does not reference a column of the outer query is evaluated once; one that does is evaluated per row. #### Next Step The last example in this lesson placed two subqueries side by side: one evaluated once, the other evaluated per row. In the phrasing, the difference was a single column reference, but the difference in the amount of work is measured by a multiplying factor. The next lesson defines this second form — the one tied to the outer row, the correlated subquery — measures it by counting how many times it is evaluated, and compares it against an equivalent join-based phrasing. ### Correlated Subqueries Source: https://academia.sh/en/courses/advanced-sql/correlated-subqueries Per-row evaluation of a subquery tied to the outer row, measuring the amount of work by counting, comparison with a join-based rewrite, and the duplication difference between EXISTS and a join. The last example in the previous lesson placed two subqueries side by side. One looked at the whole table and produced a single value; the other referenced the outer query's `m.id` column. In the phrasing, the difference was a single column name, but this reference changes when the subquery gets evaluated. A subquery that references a column of the outer query is called a **correlated subquery**. This lesson takes up what the correlation means, how it grows the amount of work, and how a phrasing that asks the same question with less work is built. #### What the Link Means An independent subquery can be run by itself; its result does not depend on the outer query. Because of this, the engine can evaluate it once and treat it as a constant. A correlated subquery cannot be run by itself: it contains a name that cannot be resolved. Its meaning is defined as "each time the outer query produces a row, the subquery is re-evaluated with that row's values." The conceptual order of evaluation is: 1. The outer query produces a candidate row. 2. The outer column references inside the subquery are replaced with that row's values. 3. The subquery runs. 4. The result is used in filtering the outer row, or in one of its columns. This definition is **semantic**: it determines what the query produces. Whether the engine actually runs it row by row is a separate question, taken up at the end of the lesson. The typical job of a correlated subquery is a question that requires a per-group comparison, such as "the extreme value inside each group." The question "each member's most recent loan" is one of these: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (4,7,1,'2024-03-11',NULL),(6,2,2,'2024-03-01','2024-03-12'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'); SELECT l.id, l.member_id, l.pickup FROM loan l WHERE l.pickup = (SELECT MAX(i.pickup) FROM loan i WHERE i.member_id = l.member_id) ORDER BY l.member_id; SQL ``` ```text ┌────┬───────────┬────────────┐ │ id │ member_id │ pickup │ ├────┼───────────┼────────────┤ │ 4 │ 1 │ 2024-03-11 │ │ 9 │ 2 │ 2024-03-21 │ │ 10 │ 3 │ 2024-03-04 │ └────┴───────────┴────────────┘ ``` Giving the inner `loan` table the alias `i` and the outer one `l` is required: the same table appears in two different roles, so only the alias determines which one the `member_id` column belongs to. The row that draws the link is the `WHERE i.member_id = l.member_id` condition; because `l` is visible from inside, the subquery is correlated. #### Measuring the Amount of Work The cost of per-row evaluation can be shown by counting. To do this, a counter is placed into the query: a user-defined function called `passthrough` that increments a variable every time it is called and returns its argument unchanged. The function is placed in the inner table's **condition**, so it runs once for every row scanned in the inner table, and the total call count gives the number of rows the inner table was touched for. Two phrasings that produce the same result are compared: the correlated subquery, and a phrasing that groups the inner table once and then joins it. ```bash cat > measure.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const db = new DatabaseSync(':memory:'); db.exec(` CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, member_id INT, pickup TEXT); INSERT INTO member VALUES (1,'Alice'),(2,'Ben'),(3,'Clara'),(4,'Derek'), (5,'Evan'),(6,'Fiona'),(7,'Grace'),(8,'Hannah'); INSERT INTO loan VALUES (1,1,'2024-03-01'),(2,1,'2024-03-01'),(3,1,'2024-03-04'),(4,1,'2024-03-11'), (5,1,'2024-03-18'),(6,2,'2024-03-01'),(7,2,'2024-03-06'),(8,2,'2024-03-11'), (9,2,'2024-03-21'),(10,3,'2024-03-04'),(11,3,'2024-03-06'),(12,3,'2024-03-13'), (13,3,'2024-03-25'),(14,4,'2024-03-04'),(15,4,'2024-03-13'),(16,4,'2024-03-20'), (17,5,'2024-03-06'),(18,5,'2024-03-11'),(19,5,'2024-03-25'),(20,6,'2024-03-04'), (21,6,'2024-03-13'),(22,6,'2024-03-20'),(23,7,'2024-03-11'),(24,7,'2024-03-18'), (25,8,'2024-03-13'); `); let visits = 0; db.function('passthrough', (value) => { visits += 1; return value; }); visits = 0; const correlated = db.prepare(` SELECT m.name, (SELECT COUNT(*) FROM loan l WHERE passthrough(l.member_id) = m.id) AS count FROM member m ORDER BY m.id`).all(); console.log('correlated:', correlated.map((s) => s.count).join(','), '| visits:', visits); visits = 0; const joined = db.prepare(` SELECT m.name, COALESCE(s.count, 0) AS count FROM member m LEFT JOIN (SELECT member_id, COUNT(*) AS count FROM loan WHERE passthrough(member_id) IS NOT NULL GROUP BY member_id) AS s ON s.member_id = m.id ORDER BY m.id`).all(); console.log('joined :', joined.map((s) => s.count).join(','), '| visits:', visits); JS node measure.mjs ``` ```text correlated: 5,4,4,3,3,3,2,1 | visits: 200 joined : 5,4,4,3,3,3,2,1 | visits: 25 ``` Both phrasings produced the same eight numbers. The touch count on the inner table, though, was 200 against 25. The number is not surprising: the outer table has 8 rows, the inner table has 25. In the correlated phrasing the inner table is scanned in full for every outer row, giving $8 \times 25 = 200$. In the joined phrasing the inner table is scanned and grouped **once**, giving 25; the two eight-row sets are then matched. In general, with $m$ rows in the outer table and $n$ rows in the inner table, the correlated phrasing does $O(m \cdot n)$ work, and the phrasing that groups first and then joins does $O(m + n)$ work. In a library where the member count and the transaction count both grow tenfold together, the first phrasing's work grows a hundredfold, and the second's grows tenfold. #### Seeing It in the Query Plan Measurement shows what the engine actually did, from the outside. What the engine planned to do is read from the query plan. `EXPLAIN QUERY PLAN` prints the plan without running the query: ```bash sqlite3 <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); .print -- without index -- EXPLAIN QUERY PLAN SELECT m.name, (SELECT COUNT(*) FROM loan l WHERE l.member_id = m.id) AS count FROM member m ORDER BY m.id; CREATE INDEX loan_member ON loan(member_id); .print .print -- with index -- EXPLAIN QUERY PLAN SELECT m.name, (SELECT COUNT(*) FROM loan l WHERE l.member_id = m.id) AS count FROM member m ORDER BY m.id; SQL ``` ```text -- without index -- QUERY PLAN |--SCAN m `--CORRELATED SCALAR SUBQUERY 1 `--SCAN l -- with index -- QUERY PLAN |--SCAN m `--CORRELATED SCALAR SUBQUERY 1 `--SEARCH l USING COVERING INDEX loan_member (member_id=?) ``` The `CORRELATED SCALAR SUBQUERY` line in the plan says the subquery is correlated and returns a single value. The line below it gives how the inner table is accessed: without an index, `SCAN l` — a full scan from start to end; with an index, `SEARCH l USING … INDEX` — direct access. The measured value of 200 is the first plan's scan repeated eight times. The second plan shows that a correlated subquery is **not** inherently expensive; what is expensive is a repeated scan without a suitable access path. With an index, each repeat is not a full scan but a single search, and the total work becomes proportional not to the row count but to the match count. #### The Engine's Right to Rewrite A query says what is to be done, not how. Subject to leaving the result unchanged, the planner can convert a correlated subquery into a join or a semi-join, or materialize the inner result once and reuse it. These transformations are called **subquery flattening**, and their scope varies by engine. The consequence cuts two ways. On one hand, saying "this is slow" every time a correlated phrasing is seen is wrong — the engine may have rescued it. On the other hand, it is also true that the rescue is **not guaranteed**: if the subquery has an aggregate function, a `LIMIT`, a null-sensitive condition, or a function with a side effect, the transformation would change the meaning, so it is not performed. Not assuming without measuring is, for this reason, a habit. #### The Difference Between EXISTS and a Join The second common form of correlated subquery is the `EXISTS` predicate, which asks about **existence** rather than a value. The same question can also be written with a join, but the two are not equivalent: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5); INSERT INTO loan VALUES (4,7,1,'2024-03-11',NULL),(9,8,2,'2024-03-21',NULL), (13,2,3,'2024-03-25',NULL),(16,4,3,'2024-03-20',NULL); SELECT m.name FROM member m WHERE EXISTS (SELECT 1 FROM loan l WHERE l.member_id = m.id AND l.returned IS NULL) ORDER BY m.id; SELECT m.name FROM member m JOIN loan l ON l.member_id = m.id AND l.returned IS NULL ORDER BY m.id; SQL ``` ```text ┌───────┐ │ name │ ├───────┤ │ Alice │ │ Ben │ │ Clara │ └───────┘ ┌───────┐ │ name │ ├───────┤ │ Alice │ │ Ben │ │ Clara │ │ Clara │ └───────┘ ``` `Clara` appears twice in the second result, because she has two unreturned records and the join produces a row for every match. `EXISTS`, in contrast, asks "is there at least one match"; it stops at the first match and does not duplicate the row. This difference is the limit of a join-based rewrite: if a transformation is wanted that does not change the row count, `DISTINCT` or a grouping has to be added to the join's result. These additions are not free either — they bring a sorting or temporary-structure cost. Before turning a predicate written with `EXISTS` into a join, whether the match is unique has to be asked first. #### Summary - A correlated subquery references a column of the outer query and is, semantically, re-evaluated for each outer row. - For $m$ rows in the outer table and $n$ rows in the inner table, a repeated scan does $O(m \cdot n)$ work, and a phrasing that groups first and then joins does $O(m + n)$ work; in the measurement this came out as 200 against 25. - In `EXPLAIN QUERY PLAN` output, the `CORRELATED SCALAR SUBQUERY` line shows the correlation, and the `SCAN` or `SEARCH` line below it shows the access path. - A correlated phrasing is not inherently expensive; with a suitable access path, each repeat comes down to a single search instead of a full scan. - `EXISTS` does not duplicate a row, a join does; the two phrasings produce the same result only when the match is unique. #### Next Step The join-based phrasing in this lesson built its intermediate result as a subquery embedded inside `FROM`. Two or three layers deeper, this phrasing stops being readable: the intermediate result's name gets lost in the middle of the query, and if the same intermediate result is needed in two places, it gets written twice. The next lesson introduces common table expressions, which name intermediate results at the start of the query and keep the body plain. ### Common Table Expressions Source: https://academia.sh/en/courses/advanced-sql/common-table-expressions Naming intermediate results with WITH, giving a column list, chaining expressions, reusing the same intermediate result, measuring the materialization decision, and use inside data-modifying statements. The previous lesson's join-based phrasing built its intermediate result as a subquery embedded inside `FROM`. This reads fine at one layer; it stops reading at two. The intermediate result's definition is buried in the middle of the query, its name is only visible after the closing parenthesis, and if the same intermediate result is needed in two places, its definition gets written twice. A **common table expression** solves all three problems at once: it gives the intermediate result a name at the **start** of the query, reduces the body to a plain query that uses that name, and allows the same name to be used more than once inside the body. #### Naming A common table expression begins with the `WITH` keyword and contains a name, an optional column list, and a query in parentheses. After this definition, the name is used like a table in the body of the statement that follows. The question "average loans per member, per branch" is two layers: first a per-member count, then an average within the branch. The block below asks the same question two ways — once with an embedded subquery, once with a named expression: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT, parent_id INT); CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO branch VALUES (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3); INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5), (5,'Evan',6),(6,'Fiona',6),(7,'Grace',4),(8,'Hannah',5); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); .print -- embedded subquery -- SELECT b.name AS branch, ROUND(AVG(t.count), 2) AS per_member FROM (SELECT m.branch_id, m.id, COUNT(l.id) AS count FROM member m LEFT JOIN loan l ON l.member_id = m.id GROUP BY m.branch_id, m.id) AS t JOIN branch b ON b.id = t.branch_id GROUP BY b.id, b.name ORDER BY per_member DESC; .print -- common table expression -- WITH member_count AS ( SELECT m.branch_id, m.id AS member_id, COUNT(l.id) AS count FROM member m LEFT JOIN loan l ON l.member_id = m.id GROUP BY m.branch_id, m.id ) SELECT b.name AS branch, ROUND(AVG(t.count), 2) AS per_member FROM member_count t JOIN branch b ON b.id = t.branch_id GROUP BY b.id, b.name ORDER BY per_member DESC; SQL ``` ```text -- embedded subquery -- ┌──────────┬────────────┐ │ branch │ per_member │ ├──────────┼────────────┤ │ Kadikoy │ 3.67 │ │ Besiktas │ 3.0 │ │ Uskudar │ 2.67 │ └──────────┴────────────┘ -- common table expression -- ┌──────────┬────────────┐ │ branch │ per_member │ ├──────────┼────────────┤ │ Kadikoy │ 3.67 │ │ Besiktas │ 3.0 │ │ Uskudar │ 2.67 │ └──────────┴────────────┘ ``` The results are the same; what changes is the order in which they read. In the first phrasing, the reader has to descend into the parenthesized part first to understand what the outer query is doing; what the `FROM` clause corresponds to only becomes clear once the `AS t` after the closing parenthesis is reached. In the second, the definition has already finished above, and `member_count` can be thought of as a table while the body is being read. `LEFT JOIN` preserves members with no loans as zero in both phrasings. A common table expression is not a **view**. A view is a permanent object in the schema that other queries can also use; a common table expression exists only for the duration of the statement it is written in, and its name disappears once the statement ends. This impermanence is not a limitation but a design choice: adding a permanent schema object for a single report's intermediate step turns that object into something someone has to maintain. #### Giving Column Names in the Definition A column list can be written in parentheses after the name. This list names the inner query's produced columns in order, and removes the need to write `AS` for each expression individually inside the inner query: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (4,7,1,'2024-03-11',NULL),(6,2,2,'2024-03-01','2024-03-12'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (13,2,3,'2024-03-25',NULL); WITH duration(loan_id, member_id, days) AS ( SELECT id, member_id, julianday(COALESCE(returned, '2024-03-31')) - julianday(pickup) FROM loan ) SELECT member_id, COUNT(*) AS record_count, CAST(AVG(days) AS INT) AS average_days FROM duration GROUP BY member_id ORDER BY member_id; SQL ``` ```text ┌───────────┬──────────────┬──────────────┐ │ member_id │ record_count │ average_days │ ├───────────┼──────────────┼──────────────┤ │ 1 │ 3 │ 17 │ │ 2 │ 2 │ 10 │ │ 3 │ 2 │ 6 │ └───────────┴──────────────┴──────────────┘ ``` If a column list is given, the number of columns the inner query produces must match the list **exactly**; a mismatch is a semantic error, not a syntax one, and the engine rejects the statement. Here the `days` column is an expression that assumes a count-through date for records not yet returned; naming it in the definition means the body never has to see that expression again. #### Chaining and Reuse Several definitions, separated by commas, can be written after `WITH`. Later definitions can reference earlier ones, so a computation is built step by step. The same name can also be used more than once in the body — something not possible in an embedded subquery: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT, parent_id INT); CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO branch VALUES (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3); INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5), (5,'Evan',6),(6,'Fiona',6),(7,'Grace',4),(8,'Hannah',5); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); WITH member_count AS ( SELECT m.branch_id, m.id AS member_id, COUNT(l.id) AS count FROM member m LEFT JOIN loan l ON l.member_id = m.id GROUP BY m.branch_id, m.id ), branch_total AS ( SELECT branch_id, SUM(count) AS total FROM member_count GROUP BY branch_id ) SELECT b.name AS branch, t.total, ROUND(100.0 * t.total / (SELECT SUM(total) FROM branch_total), 1) AS percent FROM branch_total t JOIN branch b ON b.id = t.branch_id ORDER BY t.total DESC; SQL ``` ```text ┌──────────┬───────┬─────────┐ │ branch │ total │ percent │ ├──────────┼───────┼─────────┤ │ Kadikoy │ 11 │ 44.0 │ │ Uskudar │ 8 │ 32.0 │ │ Besiktas │ 6 │ 24.0 │ └──────────┴───────┴─────────┘ ``` The computation was built in three steps: a per-member count, a per-branch total, and the total's share of the grand total. `branch_total` appears in two places — once as a row source in `FROM`, once as the scalar subquery that supplies the grand total in the `SELECT` list. In the embedded phrasing, that would mean copying the same definition twice; if one copy got updated and the other got forgotten, the percentages would silently become inconsistent. Because the name is singular, a drift like that is impossible. The chain is also a debugging tool. The body can be temporarily replaced with `SELECT * FROM member_count` to see the first step's output directly, and then `branch_total` can be tested next. In the embedded phrasing, this requires manually pulling the parenthesized part out to run it and then putting it back. The order of the definitions is binding: an expression can only reference expressions defined **before** it. A self-reference is a special case that requires a separate keyword — the subject of the next lesson. #### The Materialization Decision Even with a single name, the computation does not have to happen once. The engine has two options: compute the expression once and hold the result in a temporary structure (**materialization**), or inline the definition at each place it is used. The first avoids recomputing; the second lets outer conditions be pushed into the expression and lets indexes be used. Neither is always better, so the decision is left to the planner. The difference can be measured with the same counter as the previous lesson. The three queries below use the same expression twice; the only difference is the materialization directive given to the engine: ```bash cat > cte-measure.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const db = new DatabaseSync(':memory:'); db.exec(` CREATE TABLE loan(id INTEGER PRIMARY KEY, member_id INT, pickup TEXT); INSERT INTO loan VALUES (1,1,'2024-03-01'),(2,1,'2024-03-01'),(3,1,'2024-03-04'),(4,1,'2024-03-11'), (5,1,'2024-03-18'),(6,2,'2024-03-01'),(7,2,'2024-03-06'),(8,2,'2024-03-11'), (9,2,'2024-03-21'),(10,3,'2024-03-04'),(11,3,'2024-03-06'),(12,3,'2024-03-13'), (13,3,'2024-03-25'),(14,4,'2024-03-04'),(15,4,'2024-03-13'),(16,4,'2024-03-20'), (17,5,'2024-03-06'),(18,5,'2024-03-11'),(19,5,'2024-03-25'),(20,6,'2024-03-04'), (21,6,'2024-03-13'),(22,6,'2024-03-20'),(23,7,'2024-03-11'),(24,7,'2024-03-18'), (25,8,'2024-03-13'); `); let visits = 0; db.function('passthrough', (value) => { visits += 1; return value; }); const measure = (label, query) => { visits = 0; const row = db.prepare(query).get(); console.log(label, JSON.stringify(row), '| visits:', visits); }; measure('default ', ` WITH count AS (SELECT member_id, COUNT(*) AS count FROM loan WHERE passthrough(member_id) IS NOT NULL GROUP BY member_id) SELECT (SELECT MAX(count) FROM count) AS maximum, (SELECT MIN(count) FROM count) AS minimum`); measure('MATERIALIZED ', ` WITH count AS MATERIALIZED (SELECT member_id, COUNT(*) AS count FROM loan WHERE passthrough(member_id) IS NOT NULL GROUP BY member_id) SELECT (SELECT MAX(count) FROM count) AS maximum, (SELECT MIN(count) FROM count) AS minimum`); measure('NOT MATERIALIZED ', ` WITH count AS NOT MATERIALIZED (SELECT member_id, COUNT(*) AS count FROM loan WHERE passthrough(member_id) IS NOT NULL GROUP BY member_id) SELECT (SELECT MAX(count) FROM count) AS maximum, (SELECT MIN(count) FROM count) AS minimum`); JS node cte-measure.mjs ``` ```text default {"maximum":5,"minimum":1} | visits: 25 MATERIALIZED {"maximum":5,"minimum":1} | visits: 25 NOT MATERIALIZED {"maximum":5,"minimum":1} | visits: 50 ``` The three results are the same; the amount of work differs. When materialized, the 25-row table is scanned once; when inlined, the definition is copied to each of the two use sites and the table is scanned twice, for a total of 50 rows. In this measurement, the default behavior matches materialization; if the query's shape were different, the planner could just as well have made the other decision. The `MATERIALIZED` and `NOT MATERIALIZED` directives used here are **engine-specific**; standard SQL defines no such control, and they are not present in every engine. What is standard is the common table expression's **meaning**: what result it produces is defined, but how many times it is computed is left to the planner. For this reason the sentence "using a common table expression means the result is computed once" is not a portable assumption; some engines always materialize the expression, some never do, and in some the decision depends on the query. If an expression is used in more than one place and its definition is expensive, the target engine's behavior has to be measured. #### In Data-Modifying Statements `WITH` can be written not only before a `SELECT` statement but also before `INSERT`, `UPDATE`, and `DELETE` statements. The logic that determines which rows get changed is thereby separated from the statement and becomes readable on its own: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (4,7,1,'2024-03-11',NULL),(9,8,2,'2024-03-21',NULL),(13,2,3,'2024-03-25',NULL), (16,4,4,'2024-03-20',NULL),(22,3,6,'2024-03-20',NULL),(1,1,1,'2024-03-01','2024-03-15'); WITH overdue AS ( SELECT id FROM loan WHERE returned IS NULL AND pickup <= '2024-03-20' ) UPDATE loan SET returned = '2024-03-31' WHERE id IN (SELECT id FROM overdue); SELECT changes() AS updated; SELECT id, pickup, returned FROM loan WHERE returned IS NULL ORDER BY id; SQL ``` ```text ┌─────────┐ │ updated │ ├─────────┤ │ 3 │ └─────────┘ ┌────┬────────────┬──────────┐ │ id │ pickup │ returned │ ├────┼────────────┼──────────┤ │ 9 │ 2024-03-21 │ │ │ 13 │ 2024-03-25 │ │ └────┴────────────┴──────────┘ ``` Three rows were updated; two records whose pickup date passed March 20 remained open. This phrasing's practical benefit is that the **same** expression can be run as a `SELECT` before the update to see which rows will be affected. Because the selection criterion is defined in exactly one place, no drift is left between the check and the application — writing the condition twice has, as its most expensive consequence, the update hitting a different set than the one checked. #### Summary - A common table expression names an intermediate result at the start of a statement; the name lives only for that statement and does not create a permanent schema object. - An optional column list can be added to the name; when given, the inner query's column count must match the list exactly. - Multiple expressions are chained with commas; each expression can reference only those defined before it, and the same name can be used more than once in the body. - A single name does not mean a single computation: the materialization decision belongs to the planner, and the same expression can be computed twice; in the measurement this came out as 25 against 50 rows. - `WITH` can also be written before data-modifying statements; the selection criterion can then be checked with `SELECT` before it is applied. #### Next Step It was said that a common table expression can reference only expressions defined before it; the one exception is an expression referencing **itself**. This exception is not a small syntax detail: it opens SQL up to computations that cannot be expressed with a fixed number of steps — climbing to the root in a branch tree, finding every node reachable from a given node. The next lesson introduces the recursive common table expression, computes depth over a hierarchy, and shows what happens with no cycle guard, in a bounded number of steps. ### Recursive Queries Source: https://academia.sh/en/courses/advanced-sql/recursive-queries Building the anchor and recursive members with WITH RECURSIVE, moving down and up a tree, subtree totals, what happens with no cycle guard, and sequence generation. The previous lesson said that a common table expression can only reference expressions defined before it, and named the one exception: an expression can reference **itself**. This exception grows SQL's expressive power qualitatively. Suppose a library's branches are organized as a tree: every branch has a parent branch, and Central sits at the root. The question "every branch under Central" cannot be written without knowing the depth of the tree — three levels need three joins, four levels need four. Depth, though, is a property of the data and changes over time. Computations like this, which cannot be expressed with a fixed number of joins, are written with a **recursive common table expression**. #### The Two-Step Structure A recursive expression starts with `WITH RECURSIVE`, and its body is made of two parts separated by `UNION ALL`: - **Anchor member**: the query that does not reference the expression. It produces the starting rows. - **Recursive member**: the query that references the expression itself. It derives new rows from the rows produced in the previous round. Evaluation proceeds as follows: the anchor member runs and its result goes into a working table. Then the recursive member runs, but only over the rows **added in the last round**; the rows it produces are appended to the result and become the input for the next round. Processing stops in the round where no new row is produced. This is the query-language counterpart of the breadth-first search from the Data Structures course: it advances level by level. Descending from the root of the branch tree, computing depth and path, is written with this structure: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id)); INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1), (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4); WITH RECURSIVE tree(id, name, depth, path) AS ( SELECT id, name, 0, name FROM branch WHERE parent_id IS NULL UNION ALL SELECT b.id, b.name, t.depth + 1, t.path || ' > ' || b.name FROM branch b JOIN tree t ON b.parent_id = t.id ) SELECT depth, name, path FROM tree ORDER BY path; SQL ``` ```text ┌───────┬──────────┬────────────────────────────────────────┐ │ depth │ name │ path │ ├───────┼──────────┼────────────────────────────────────────┤ │ 0 │ Central │ Central │ │ 1 │ Anadolu │ Central > Anadolu │ │ 2 │ Kadikoy │ Central > Anadolu > Kadikoy │ │ 3 │ Bostanci │ Central > Anadolu > Kadikoy > Bostanci │ │ 3 │ Moda │ Central > Anadolu > Kadikoy > Moda │ │ 2 │ Uskudar │ Central > Anadolu > Uskudar │ │ 1 │ Avrupa │ Central > Avrupa │ │ 2 │ Besiktas │ Central > Avrupa > Besiktas │ └───────┴──────────┴────────────────────────────────────────┘ ``` The anchor member selects the root: the row with no parent branch, at depth zero. The recursive member finds the children of every node found so far, increments the depth by one, and extends the path string. Depth and path are values that are **not present** in the table but accumulate while traversing; this is the real power of a recursive expression. Because the ordering is done with `ORDER BY path`, the output reads in tree order: each node's own subtree comes immediately below it. The depth column rises and falls as it goes, because the sort key is the path, not the depth. #### Moving Upward The same structure can also be built in the opposite direction. If the direction of the join condition is reversed, the walk goes from a node toward the root; this answers the question "which region does this branch belong to": ```bash sqlite3 -box -header <<'SQL' CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id)); INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1), (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4); WITH RECURSIVE parent_chain(id, name, parent_id, step) AS ( SELECT id, name, parent_id, 0 FROM branch WHERE name = 'Moda' UNION ALL SELECT b.id, b.name, b.parent_id, z.step + 1 FROM branch b JOIN parent_chain z ON b.id = z.parent_id ) SELECT step, name FROM parent_chain ORDER BY step; SQL ``` ```text ┌──────┬─────────┐ │ step │ name │ ├──────┼─────────┤ │ 0 │ Moda │ │ 1 │ Kadikoy │ │ 2 │ Anadolu │ │ 3 │ Central │ └──────┴─────────┘ ``` The only difference is in the join condition: descending writes `b.parent_id = t.id`, ascending writes `b.id = z.parent_id`. The chain stops at the root, because the root's parent branch is null and matches no row. #### Aggregating Over a Subtree A recursive expression's result is a table; it can be joined with other tables and grouped. The question "the total loan count within each branch's own subtree" is answered by first producing, for every node, the nodes in its subtree, and then aggregating over that mapping: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id)); INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1), (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4); CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice',7),(2,'Ben',8),(3,'Clara',5),(4,'Derek',5), (5,'Evan',6),(6,'Fiona',6),(7,'Grace',7),(8,'Hannah',5); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); WITH RECURSIVE subtree(root_id, id) AS ( SELECT id, id FROM branch UNION ALL SELECT a.root_id, b.id FROM branch b JOIN subtree a ON b.parent_id = a.id ) SELECT r.name AS branch, COUNT(l.id) AS subtree_total FROM subtree a JOIN branch r ON r.id = a.root_id LEFT JOIN member m ON m.branch_id = a.id LEFT JOIN loan l ON l.member_id = m.id GROUP BY a.root_id, r.name ORDER BY subtree_total DESC, r.name; SQL ``` ```text ┌──────────┬───────────────┐ │ branch │ subtree_total │ ├──────────┼───────────────┤ │ Central │ 25 │ │ Anadolu │ 19 │ │ Kadikoy │ 11 │ │ Uskudar │ 8 │ │ Moda │ 7 │ │ Avrupa │ 6 │ │ Besiktas │ 6 │ │ Bostanci │ 4 │ └──────────┴───────────────┘ ``` Here the anchor member does not take a single root but treats **every** branch as the root of its own subtree. The result is a mapping of "which node belongs to which subtree." The numbers are internally consistent: Kadikoy's 11 transactions are the sum of Moda's 7 and Bostanci's 4; Anadolu's 19 is the sum of Kadikoy's 11 and Uskudar's 8. The 25 at the root is every transaction in the table. #### With No Cycle Guard Whether the branch tree is truly a tree depends on the correctness of the data. If an update mistakenly attaches a parent branch to its own child, the structure turns into a cyclic graph and the recursion never stops: every round reproduces the same nodes. The block below deliberately produces this situation — Anadolu gets attached to Moda, which is its own descendant. So the query does not run forever, a **depth limit** is placed on the recursive member; the limit does not resolve the cycle, it only makes the result visible: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id)); INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1), (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4); UPDATE branch SET parent_id = 7 WHERE id = 2; WITH RECURSIVE tree(id, name, depth) AS ( SELECT id, name, 0 FROM branch WHERE id = 4 UNION ALL SELECT b.id, b.name, t.depth + 1 FROM branch b JOIN tree t ON b.parent_id = t.id WHERE t.depth < 7 ) SELECT depth, id, name FROM tree ORDER BY depth, id; SQL ``` ```text ┌───────┬────┬──────────┐ │ depth │ id │ name │ ├───────┼────┼──────────┤ │ 0 │ 4 │ Kadikoy │ │ 1 │ 7 │ Moda │ │ 1 │ 8 │ Bostanci │ │ 2 │ 2 │ Anadolu │ │ 3 │ 4 │ Kadikoy │ │ 3 │ 5 │ Uskudar │ │ 4 │ 7 │ Moda │ │ 4 │ 8 │ Bostanci │ │ 5 │ 2 │ Anadolu │ │ 6 │ 4 │ Kadikoy │ │ 6 │ 5 │ Uskudar │ │ 7 │ 7 │ Moda │ │ 7 │ 8 │ Bostanci │ └───────┴────┴──────────┘ ``` Kadikoy reappears at depth three and six, Moda at depth one, four, and seven. The pattern repeats every three steps: `4 → 7 → 2 → 4`. Had the limit been removed, the query would not have stopped; it would have kept producing rows until memory or temporary disk space ran out. The correct fix is to track the nodes already visited and prevent a revisit. The path walked is accumulated in a string, and the recursive member refuses to take a node a second time if it has already appeared in the path: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id)); INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1), (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4); UPDATE branch SET parent_id = 7 WHERE id = 2; WITH RECURSIVE tree(id, name, depth, path) AS ( SELECT id, name, 0, '/' || id || '/' FROM branch WHERE id = 4 UNION ALL SELECT b.id, b.name, t.depth + 1, t.path || b.id || '/' FROM branch b JOIN tree t ON b.parent_id = t.id WHERE t.path NOT LIKE '%/' || b.id || '/%' ) SELECT depth, id, name, path FROM tree ORDER BY depth, id; SQL ``` ```text ┌───────┬────┬──────────┬───────────┐ │ depth │ id │ name │ path │ ├───────┼────┼──────────┼───────────┤ │ 0 │ 4 │ Kadikoy │ /4/ │ │ 1 │ 7 │ Moda │ /4/7/ │ │ 1 │ 8 │ Bostanci │ /4/8/ │ │ 2 │ 2 │ Anadolu │ /4/7/2/ │ │ 3 │ 5 │ Uskudar │ /4/7/2/5/ │ └───────┴────┴──────────┴───────────┘ ``` The query stopped at five rows. The `/4/7/2/4/` step, which would have reached Kadikoy a second time, was eliminated because `/4/` had already appeared in the path. Identifiers are written between slashes precisely so that the `/4/` pattern is not confused with `/14/` or `/41/`. This guard visits every node **once per path**; in a general graph, the same node can be reached by different paths, so the row count can still grow. When every node needs to be visited exactly once, `UNION` — which removes duplicates — is used instead of `UNION ALL`; its cost is a uniqueness check on every round. #### Outside a Hierarchy The anchor member of a recursive expression does not have to come from a table. Starting from a fixed row and applying a rule, a sequence can be generated. A typical use for this is showing days with no data as zero in a report: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(6,2,2,'2024-03-01','2024-03-12'), (10,1,3,'2024-03-04','2024-03-10'),(14,5,4,'2024-03-04','2024-03-09'); WITH RECURSIVE day(date) AS ( SELECT '2024-03-01' UNION ALL SELECT date(date, '+1 day') FROM day WHERE date < '2024-03-06' ) SELECT d.date, COUNT(l.id) AS transaction_count FROM day d LEFT JOIN loan l ON l.pickup = d.date GROUP BY d.date ORDER BY d.date; SQL ``` ```text ┌────────────┬───────────────────┐ │ date │ transaction_count │ ├────────────┼───────────────────┤ │ 2024-03-01 │ 3 │ │ 2024-03-02 │ 0 │ │ 2024-03-03 │ 0 │ │ 2024-03-04 │ 3 │ │ 2024-03-05 │ 0 │ │ 2024-03-06 │ 0 │ └────────────┴───────────────────┘ ``` Had only the `loan` table been grouped, March 2nd and 3rd would not appear at all; empty days would disappear from the report. The generated calendar forms the left side of the left outer join and fills the missing days with zero. The name of the date function varies by engine; what does not vary is the structure made of the anchor member and the stopping condition. The stopping condition has to sit **inside the recursive member**. If the condition is written into an outer `WHERE` clause instead, generation does not stop; the outer filter only weeds out the rows already produced. This is the most common mistake made when writing a recursive query. #### Summary - A recursive common table expression is made of an anchor member and a self-referencing recursive member joined with `UNION ALL`; it stops in the round where no new row is produced. - Values like depth, path, and step number are not present in the table; they accumulate during the traversal. - Reversing the direction of the join condition lets the same structure walk both the subtree and the parent chain. - If the data contains a cycle, the recursion does not stop; accumulating the visited nodes in a path and eliminating a repeated step is the guard that terminates the query. - The anchor member can be a fixed row; this is the standard way to generate the calendar that fills in missing days in reports. #### Next Step What the computations in this lesson had in common is that the result changed the **row set**: traversal produced new rows, grouping reduced rows to one per group. In some questions, though, the rows should be preserved, and a value that looks at its neighbors added next to each one — a member's running total next to that member's transaction, up to that day. Grouping cannot do this, because grouping swallows rows. The next lesson introduces window functions, which compute over neighboring rows while preserving them, and shows how the frame definition changes the result within the same query. ### Window Functions Source: https://academia.sh/en/courses/advanced-sql/window-functions Aggregating over rows without losing them with the OVER clause, partitioning, the RANGE versus ROWS distinction in a frame definition, running totals and sliding windows, and access to a neighboring row. What the previous lesson's computations had in common was that they changed the row set: traversal produced new rows, grouping reduced rows to one per group. In some questions, though, the rows should be preserved, and a value that looks at its neighbors added next to each one. "Each loan transaction, alongside that member's total transaction count" is a question like this. Grouping cannot give this directly: once `GROUP BY` is applied, the detail rows vanish and what is left is one row per group. Preserving the detail means the grouped result has to be joined back with the detail. **Window functions** make this join unnecessary: they run an aggregate function over each row's own field of view, without swallowing the rows. #### The Same Function, Two Uses When an `OVER` clause is added after an aggregate function, the function turns into a **window function**. If `OVER` is left empty, the window is the entire result set; if `PARTITION BY` is given, the result set is split into partitions and each row sees only its own partition. ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (6,2,2,'2024-03-01','2024-03-12'),(3,5,1,'2024-03-04','2024-03-18'), (7,4,2,'2024-03-06','2024-03-25'),(4,7,1,'2024-03-11',NULL), (8,6,2,'2024-03-11','2024-03-19'),(23,2,7,'2024-03-11','2024-03-16'), (5,9,1,'2024-03-18','2024-03-29'),(24,5,7,'2024-03-18','2024-03-24'), (9,8,2,'2024-03-21',NULL); SELECT member_id, COUNT(*) AS count FROM loan GROUP BY member_id ORDER BY member_id; SELECT id, member_id, pickup, COUNT(*) OVER (PARTITION BY member_id) AS member_count FROM loan ORDER BY member_id, pickup LIMIT 6; SQL ``` ```text ┌───────────┬───────┐ │ member_id │ count │ ├───────────┼───────┤ │ 1 │ 5 │ │ 2 │ 4 │ │ 7 │ 2 │ └───────────┴───────┘ ┌────┬───────────┬────────────┬──────────────┐ │ id │ member_id │ pickup │ member_count │ ├────┼───────────┼────────────┼──────────────┤ │ 1 │ 1 │ 2024-03-01 │ 5 │ │ 2 │ 1 │ 2024-03-01 │ 5 │ │ 3 │ 1 │ 2024-03-04 │ 5 │ │ 4 │ 1 │ 2024-03-11 │ 5 │ │ 5 │ 1 │ 2024-03-18 │ 5 │ │ 6 │ 2 │ 2024-03-01 │ 4 │ └────┴───────────┴────────────┴──────────────┘ ``` The first query reduced eleven rows to three. The second preserved all eleven rows and wrote each member's total next to it — the 5, 4, and 2 that the first query produced now appear next to the rows that belong to them. `PARTITION BY` does the same partitioning as `GROUP BY`; the difference is whether the rows get swallowed as a result of that partitioning. The order of evaluation explains this distinction. Window functions run **after** `WHERE`, `GROUP BY`, and `HAVING` have been applied. Two consequences follow: a window function's input is the already-filtered set, and a window function's result cannot be used in the same query's `WHERE` clause. If filtering on a window result is needed, the query is wrapped in a common table expression and the filtering is done on the outside. #### Frame Definition When `ORDER BY` is added inside `OVER`, the window becomes ordered and the concept of a **frame** comes into play: what a row sees is no longer the whole partition but an ordered slice of it. A frame is defined in one of two ways: - `ROWS`: bounds are measured **by row count**. Two rows back from the current row means physically two rows. - `RANGE`: bounds are measured **by value**. Rows that share the same value in the sort key — peers — enter the frame together, or not at all. If `ORDER BY` is given and no frame is written, the default frame is `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`. The difference shows up when the sort key has repeated values. The query below places three frames side by side on the same data: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (6,2,2,'2024-03-01','2024-03-12'),(3,5,1,'2024-03-04','2024-03-18'), (7,4,2,'2024-03-06','2024-03-25'),(4,7,1,'2024-03-11',NULL), (8,6,2,'2024-03-11','2024-03-19'),(23,2,7,'2024-03-11','2024-03-16'), (5,9,1,'2024-03-18','2024-03-29'),(24,5,7,'2024-03-18','2024-03-24'), (9,8,2,'2024-03-21',NULL); SELECT pickup, COUNT(*) OVER (ORDER BY pickup) AS default_frame, COUNT(*) OVER (ORDER BY pickup ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS row_based, COUNT(*) OVER (ORDER BY pickup ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS sliding_three FROM loan ORDER BY pickup, id; SQL ``` ```text ┌────────────┬───────────────┬───────────┬───────────────┐ │ pickup │ default_frame │ row_based │ sliding_three │ ├────────────┼───────────────┼───────────┼───────────────┤ │ 2024-03-01 │ 3 │ 1 │ 1 │ │ 2024-03-01 │ 3 │ 2 │ 2 │ │ 2024-03-01 │ 3 │ 3 │ 3 │ │ 2024-03-04 │ 4 │ 4 │ 3 │ │ 2024-03-06 │ 5 │ 5 │ 3 │ │ 2024-03-11 │ 8 │ 6 │ 3 │ │ 2024-03-11 │ 8 │ 7 │ 3 │ │ 2024-03-11 │ 8 │ 8 │ 3 │ │ 2024-03-18 │ 10 │ 9 │ 3 │ │ 2024-03-18 │ 10 │ 10 │ 3 │ │ 2024-03-21 │ 11 │ 11 │ 3 │ └────────────┴───────────────┴───────────┴───────────────┘ ``` Three columns produced three different answers from the same data. In the first column, all three of March 1st's rows got the value 3: a value-based frame counts rows sharing the same date as a single set of peers and gives all of them the total at the end of that set. This is the answer to the question "the total as of the end of March 1st," and it is not affected by the rows' order in the table. The second column is row-based: each row adds one to the previous one, proceeding 1, 2, 3. Rows sharing the same date getting different values shows that the result depends on **ordering**. If the sort key does not fully separate the rows, this column's value is not deterministic: the same query could give a different distribution within a group of three, run on the engine reading the rows in a different order, in a different version, or under a different plan. If separation is required, a column that guarantees uniqueness is added to the `ORDER BY` key. The third column is a sliding window: the current row plus the two before it. In the first two rows the frame had not yet filled, so the values 1 and 2 came out; after that a constant 3 remained. Unlike a running total, a sliding window is **local**: the distant past falls out of the frame. This difference in the three behaviors shows that a frame is not a detail. The same function, the same ordering, and the same data written as three expressions produced three separate columns; which one is correct depends on the question being asked. #### Running Total and Sliding Average If frames were rewritten for every column, a query would stop being readable. The `WINDOW` clause names frame definitions; only the name is written after `OVER`: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (6,2,2,'2024-03-01','2024-03-12'),(3,5,1,'2024-03-04','2024-03-18'), (7,4,2,'2024-03-06','2024-03-25'),(4,7,1,'2024-03-11',NULL), (8,6,2,'2024-03-11','2024-03-19'),(23,2,7,'2024-03-11','2024-03-16'), (5,9,1,'2024-03-18','2024-03-29'),(24,5,7,'2024-03-18','2024-03-24'), (9,8,2,'2024-03-21',NULL); SELECT pickup, CAST(SUM(julianday(COALESCE(returned,'2024-03-31')) - julianday(pickup)) OVER cumulative AS INT) AS running_total_days, ROUND(AVG(julianday(COALESCE(returned,'2024-03-31')) - julianday(pickup)) OVER sliding, 1) AS sliding_average FROM loan WINDOW cumulative AS (ORDER BY pickup ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW), sliding AS (ORDER BY pickup ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) ORDER BY pickup, id; SQL ``` ```text ┌────────────┬────────────────────┬─────────────────┐ │ pickup │ running_total_days │ sliding_average │ ├────────────┼────────────────────┼─────────────────┤ │ 2024-03-01 │ 14 │ 14.0 │ │ 2024-03-01 │ 33 │ 16.5 │ │ 2024-03-01 │ 44 │ 14.7 │ │ 2024-03-04 │ 58 │ 14.7 │ │ 2024-03-06 │ 77 │ 14.7 │ │ 2024-03-11 │ 97 │ 17.7 │ │ 2024-03-11 │ 105 │ 15.7 │ │ 2024-03-11 │ 110 │ 11.0 │ │ 2024-03-18 │ 121 │ 8.0 │ │ 2024-03-18 │ 127 │ 7.3 │ │ 2024-03-21 │ 137 │ 9.0 │ └────────────┴────────────────────┴─────────────────┘ ``` The value being measured is how many days each transaction lasted; for records not yet returned, a count-through date is assumed. The first column is the cumulative total of these durations, and it keeps rising. The second column is the average duration of the last three transactions, and it rises and falls: after mid-March, as short transactions start arriving, the average drops from 17.7 to 7.3. A running total hides a trend; a sliding average reveals it — the two are separate pieces of information read from the same data. The `WINDOW` clause is standard and is written at the end of the query, before `ORDER BY`. In an engine that does not support it, the definitions are copied out explicitly into `OVER`; the meaning does not change. #### Access to a Neighboring Row Some functions exist only as window functions; they have no aggregate counterpart. `LAG` and `LEAD` fetch the value of a row a given number of positions before or after the current one, within the same partition: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (6,2,2,'2024-03-01','2024-03-12'),(3,5,1,'2024-03-04','2024-03-18'), (7,4,2,'2024-03-06','2024-03-25'),(4,7,1,'2024-03-11',NULL), (8,6,2,'2024-03-11','2024-03-19'),(23,2,7,'2024-03-11','2024-03-16'), (5,9,1,'2024-03-18','2024-03-29'),(24,5,7,'2024-03-18','2024-03-24'), (9,8,2,'2024-03-21',NULL); SELECT member_id, pickup, LAG(pickup) OVER (PARTITION BY member_id ORDER BY pickup) AS previous, CAST(julianday(pickup) - julianday(LAG(pickup) OVER (PARTITION BY member_id ORDER BY pickup)) AS INT) AS days_between FROM loan ORDER BY member_id, pickup; SQL ``` ```text ┌───────────┬────────────┬────────────┬──────────────┐ │ member_id │ pickup │ previous │ days_between │ ├───────────┼────────────┼────────────┼──────────────┤ │ 1 │ 2024-03-01 │ │ │ │ 1 │ 2024-03-01 │ 2024-03-01 │ 0 │ │ 1 │ 2024-03-04 │ 2024-03-01 │ 3 │ │ 1 │ 2024-03-11 │ 2024-03-04 │ 7 │ │ 1 │ 2024-03-18 │ 2024-03-11 │ 7 │ │ 2 │ 2024-03-01 │ │ │ │ 2 │ 2024-03-06 │ 2024-03-01 │ 5 │ │ 2 │ 2024-03-11 │ 2024-03-06 │ 5 │ │ 2 │ 2024-03-21 │ 2024-03-11 │ 10 │ │ 7 │ 2024-03-11 │ │ │ │ 7 │ 2024-03-18 │ 2024-03-11 │ 7 │ └───────────┴────────────┴────────────┴──────────────┘ ``` The first row of every partition has no previous row; `LAG` gives a null value there, and subtracting with a null value also produces a null value. Not crossing the partition boundary is part of the frame's definition: when `member_id` changes, history resets, and one member's last transaction is not considered a neighbor of another member's first. The same result could be produced with a correlated subquery — "the largest of the dates smaller than this row's" — but that phrasing performs a search for every row. A window function sorts the partition once and proceeds in a single pass. #### Summary - The `OVER` clause turns an aggregate function into a window function that preserves rows; `PARTITION BY` does the same partitioning as `GROUP BY` without swallowing rows. - Window functions run after `WHERE`, `GROUP BY`, and `HAVING`; filtering on their result requires wrapping the query in a common table expression. - A frame is measured by row count with `ROWS`, by value with `RANGE`; if `ORDER BY` is given and no frame is written, the default is `RANGE … CURRENT ROW`, and peer rows get the same result. - On the same data, the default frame, a row-based running total, and a three-row sliding window produced three separate columns; which is correct depends on the question asked. - `LAG` and `LEAD` access a neighboring row within a partition and do not cross the partition boundary. #### Next Step In this lesson, a window ran a computation over rows but did not give the rows a **rank**. Yet questions like "the three members who borrowed the most" call for a rank number, and immediately after that a decision has to be made: should two members with an equal count get the same rank, or different ones? The next lesson places row number, rank, and dense rank side by side on the same data and shows the difference in their tie behavior. ### Ranking Functions Source: https://academia.sh/en/courses/advanced-sql/ranking-functions The tie behavior of row number, rank, and dense rank, tile and percentile distribution functions, selecting the top N within a partition, and deduplication with row number. The previous lesson ran computations over a window but did not give the rows a rank. Questions like "the three members who borrowed the most" first want a rank number, and right after that call for a decision: should two members with an equal count get the same rank, or different ones? This question has three possible answers, and SQL defines all three as separate functions. This lesson places the ranking functions side by side on the same data, shows their differences, and establishes the condition needed for a ranking to be deterministic. #### Three Functions, Three Tie Decisions All three functions order the window with `ORDER BY` and give every row an integer. Where they part ways is what happens with rows that are **equal in value** on the sort key: - `ROW_NUMBER`: does not recognize ties. It gives every row a different number, proceeding 1, 2, 3. - `RANK`: gives ties the same rank, then **skips**. If two rows are second, the next one is fourth. - `DENSE_RANK`: gives ties the same rank, **without skipping**. If two rows are second, the next one is third. All three can be written in the same query; the shared window is defined once in a `WINDOW` clause: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(3,'Clara','Uskudar'), (4,'Derek','Uskudar'),(5,'Evan','Besiktas'),(6,'Fiona','Besiktas'), (7,'Grace','Kadikoy'),(8,'Hannah','Uskudar'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); WITH count AS ( SELECT m.name, m.branch, COUNT(l.id) AS count FROM member m LEFT JOIN loan l ON l.member_id = m.id GROUP BY m.id, m.name, m.branch ) SELECT name, count, ROW_NUMBER() OVER s AS row_num, RANK() OVER s AS rank, DENSE_RANK() OVER s AS dense_rank FROM count WINDOW s AS (ORDER BY count DESC) ORDER BY count DESC, name; SQL ``` ```text ┌────────┬───────┬─────────┬──────┬────────────┐ │ name │ count │ row_num │ rank │ dense_rank │ ├────────┼───────┼─────────┼──────┼────────────┤ │ Alice │ 5 │ 1 │ 1 │ 1 │ │ Ben │ 4 │ 2 │ 2 │ 2 │ │ Clara │ 4 │ 3 │ 2 │ 2 │ │ Derek │ 3 │ 4 │ 4 │ 3 │ │ Evan │ 3 │ 5 │ 4 │ 3 │ │ Fiona │ 3 │ 6 │ 4 │ 3 │ │ Grace │ 2 │ 7 │ 7 │ 4 │ │ Hannah │ 1 │ 8 │ 8 │ 5 │ └────────┴───────┴─────────┴──────┴────────────┘ ``` Two members have four loans each. `RANK` gave both of them 2, and gave the next member 4, not 3: third place was counted as consumed. `DENSE_RANK` gave both of them 2 and gave the next one 3; the rank numbers advanced with no gap. `ROW_NUMBER` did not see the tie at all and distributed 2 and 3 arbitrarily. These three columns correspond to three separate questions. `RANK` is "how many members got more than me" with one added — the habit of competition rankings. `DENSE_RANK` answers "how many distinct values are greater than mine" and is suited for counting levels. `ROW_NUMBER` produces not a rank but an **identity**: it is used to tell rows apart from each other. In the last row, `RANK` gives `Hannah` 8, `DENSE_RANK` gives 5. The difference between the two numbers is the combined effect of the ties: eight members, but five distinct values. #### The Indeterminacy of a Tie In the `ROW_NUMBER` column, `Ben` got 2 and `Clara` got 3. This distribution does not follow from how the query is written: since both have a `count` value of 4, `ORDER BY count DESC` does not separate them. Which number went to which was the engine's decision. This is a situation to be avoided. The same query, under a different plan, in a different version, or with the table read in a different order, can swap the numbers. If `ROW_NUMBER` is being used to paginate or deduplicate a result set, this swap turns into a silent bug: a record appears twice across pages, and another one never appears at all. The rule is clear: in a window where `ROW_NUMBER` is used, the `ORDER BY` key must determine the rows **uniquely**. If the key does not do this, a unique column, such as a primary key, is added to the end — the phrasing `ORDER BY count DESC, name` removes the indeterminacy shown above. `RANK` and `DENSE_RANK` are not affected by this problem, because they already give tied rows the same value. #### Tile and Percentile Distribution The other members of the ranking family give a row's **position** in the ordering as a proportion. `NTILE(n)` splits the partition into `n` parts as evenly as possible; `PERCENT_RANK` gives the rank's counterpart between zero and one, and `CUME_DIST` gives "the proportion of rows up to and including this one": ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(3,'Clara','Uskudar'), (4,'Derek','Uskudar'),(5,'Evan','Besiktas'),(6,'Fiona','Besiktas'), (7,'Grace','Kadikoy'),(8,'Hannah','Uskudar'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); WITH count AS ( SELECT m.name, COUNT(l.id) AS count FROM member m LEFT JOIN loan l ON l.member_id = m.id GROUP BY m.id, m.name ) SELECT name, count, NTILE(4) OVER s AS tile, ROUND(PERCENT_RANK() OVER s, 2) AS percent_rank, ROUND(CUME_DIST() OVER s, 2) AS cume_dist FROM count WINDOW s AS (ORDER BY count DESC) ORDER BY count DESC, name; SQL ``` ```text ┌────────┬───────┬──────┬──────────────┬───────────┐ │ name │ count │ tile │ percent_rank │ cume_dist │ ├────────┼───────┼──────┼──────────────┼───────────┤ │ Alice │ 5 │ 1 │ 0.0 │ 0.13 │ │ Ben │ 4 │ 1 │ 0.14 │ 0.38 │ │ Clara │ 4 │ 2 │ 0.14 │ 0.38 │ │ Derek │ 3 │ 2 │ 0.43 │ 0.75 │ │ Evan │ 3 │ 3 │ 0.43 │ 0.75 │ │ Fiona │ 3 │ 3 │ 0.43 │ 0.75 │ │ Grace │ 2 │ 4 │ 0.86 │ 0.88 │ │ Hannah │ 1 │ 4 │ 1.0 │ 1.0 │ └────────┴───────┴──────┴──────────────┴───────────┘ ``` The row that stands out is `Ben` and `Clara`: they have the same `count` value, the same percentile rank, and the same cumulative distribution, but they fell into different tiles. `NTILE` does not consider ties; it splits rows by number, and if a partition boundary falls in the middle of a set of peers, it splits them apart. This is why the tile number is, for rows of equal value, as indeterminate as `ROW_NUMBER`. `PERCENT_RANK` always gives the first row 0, `CUME_DIST` always gives the last row 1. The difference between the two is in their definitions: percentile rank measures the proportion "how many rows are ahead of me," cumulative distribution measures the proportion "of me and everyone not greater than me." #### Top N Within a Partition The most common use of ranking functions is selecting the best of each partition. As noted in the previous lesson, a window function's result cannot be used in the same query's `WHERE` clause; the ranking is done in a common table expression and the filtering happens on the outside: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(3,'Clara','Uskudar'), (4,'Derek','Uskudar'),(5,'Evan','Besiktas'),(6,'Fiona','Besiktas'), (7,'Grace','Kadikoy'),(8,'Hannah','Uskudar'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); WITH count AS ( SELECT m.name, m.branch, COUNT(l.id) AS count FROM member m LEFT JOIN loan l ON l.member_id = m.id GROUP BY m.id, m.name, m.branch ), ranked AS ( SELECT branch, name, count, RANK() OVER b AS rank, ROW_NUMBER() OVER b AS row_num FROM count WINDOW b AS (PARTITION BY branch ORDER BY count DESC) ) SELECT branch, name, count, rank, row_num FROM ranked WHERE rank <= 1 ORDER BY branch, name; SQL ``` ```text ┌──────────┬───────┬───────┬──────┬─────────┐ │ branch │ name │ count │ rank │ row_num │ ├──────────┼───────┼───────┼──────┼─────────┤ │ Besiktas │ Evan │ 3 │ 1 │ 1 │ │ Besiktas │ Fiona │ 3 │ 1 │ 2 │ │ Kadikoy │ Alice │ 5 │ 1 │ 1 │ │ Uskudar │ Clara │ 4 │ 1 │ 1 │ └──────────┴───────┴───────┴──────┴─────────┘ ``` Besiktas gave two rows, the others gave one each. The cause is the choice of function: with `RANK`, filtering keeps all the tied rows; with `WHERE row_num <= 1`, `Fiona` would have dropped out, and which one dropped would have been indeterminate. The choice depends on what the question wants. If "each branch's top-borrowing member" wants two names on a tie, `RANK` is right; if it wants exactly one row, `ROW_NUMBER` is right — and in the second case an additional tie-breaking column also has to be specified. Changing the threshold in `WHERE rank <= 3` extends the same query to the top three. #### Deduplication with Row Number `ROW_NUMBER` is also used as a deduplication tool, not just a ranking one. Taking only the first of the numbered rows within a partition is the "one representative per group" pattern: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(3,'Clara','Uskudar'), (4,'Derek','Uskudar'),(5,'Evan','Besiktas'),(6,'Fiona','Besiktas'), (7,'Grace','Kadikoy'),(8,'Hannah','Uskudar'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); WITH numbered AS ( SELECT id, member_id, pickup, ROW_NUMBER() OVER (PARTITION BY member_id ORDER BY pickup DESC, id DESC) AS n FROM loan ) SELECT n.member_id, m.name, n.id AS loan_id, n.pickup FROM numbered n JOIN member m ON m.id = n.member_id WHERE n.n = 1 ORDER BY n.member_id; SQL ``` ```text ┌───────────┬────────┬─────────┬────────────┐ │ member_id │ name │ loan_id │ pickup │ ├───────────┼────────┼─────────┼────────────┤ │ 1 │ Alice │ 5 │ 2024-03-18 │ │ 2 │ Ben │ 9 │ 2024-03-21 │ │ 3 │ Clara │ 13 │ 2024-03-25 │ │ 4 │ Derek │ 16 │ 2024-03-20 │ │ 5 │ Evan │ 19 │ 2024-03-25 │ │ 6 │ Fiona │ 22 │ 2024-03-20 │ │ 7 │ Grace │ 24 │ 2024-03-18 │ │ 8 │ Hannah │ 25 │ 2024-03-13 │ └───────────┴────────┴─────────┴────────────┘ ``` The sort key `pickup DESC, id DESC` has two columns. `pickup` alone can repeat within the same member; adding `id`, which is a primary key, makes the result deterministic. This is the previous section's rule put into practice. The same result could have been produced with the `MAX` subquery from the Correlated Subqueries lesson. The difference between the two phrasings shows up on a tie: the subquery-based phrasing returns both records that share the same date, the row-number phrasing selects exactly one. #### Summary - `ROW_NUMBER` does not recognize ties, `RANK` gives ties the same rank and skips, and `DENSE_RANK` gives ties the same rank without skipping. - `RANK` answers "how many rows are ahead of me," `DENSE_RANK` answers "how many distinct values are ahead of me"; `ROW_NUMBER` produces not a rank but an identity. - `ROW_NUMBER` and `NTILE` results are not deterministic if the sort key does not determine the rows uniquely; a unique column has to be added to the key. - Filtering on a window result requires wrapping the query in a common table expression; in a top-N-per-partition selection, `RANK` returns all the tied rows and `ROW_NUMBER` returns exactly N. - `PERCENT_RANK` gives the first row 0, `CUME_DIST` gives the last row 1; `NTILE` can split peer rows into different tiles. #### Next Step Every query written up to this point produced a result whose columns were known at the time the query was written. In reports, though, the opposite is often wanted: values sitting in rows should move up to a **column header**, so that each genre or each month becomes a separate column. This transformation reduces the row count and raises the column count, and it runs directly against SQL's rule of a fixed column list. The next lesson shows how pivot operations are written with conditional aggregation and how the reverse transformation, from column to row, is done. ### Pivot Operations Source: https://academia.sh/en/courses/advanced-sql/pivot-operations Pivoting from long form to wide form with conditional aggregation, the FILTER clause, the two phrasings of unpivoting, and the requirement that the column list be known when the query is written. Every query written up to this point produced a result whose columns were known at the time the query was written. In reports, though, the opposite is often wanted: values sitting in rows should move up to a column header, each book genre should get its own column, and the branches should stay in the rows. This transformation is called a **pivot**. The source form is **long form**: each measurement is one row, and a distinguishing column carries the value. The target form is **wide form**: each value of the distinguishing column turns into a column. The transformation is in tension with one of SQL's fundamental rules — the result's column list has to be known when the query is compiled. #### Long Form The starting point is the ordinary summary produced by grouping: loan count per branch-and-genre pair. ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, genre TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(3,'Clara','Uskudar'), (4,'Derek','Uskudar'),(5,'Evan','Besiktas'),(6,'Fiona','Besiktas'), (7,'Grace','Kadikoy'),(8,'Hannah','Uskudar'); INSERT INTO book VALUES (1,'Lost Time','fiction'),(2,'Silent House','fiction'), (3,'Number Theory','science'),(4,'The Structure of the Universe','science'),(5,'Short History','history'), (6,'Anatolian Notes','history'),(7,'Poems','poetry'),(8,'Essays','essay'), (9,'Roadmap','fiction'),(10,'Epistemology','philosophy'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); SELECT m.branch, k.genre, COUNT(*) AS count FROM loan o JOIN member m ON m.id = o.member_id JOIN book k ON k.id = o.book_id GROUP BY m.branch, k.genre ORDER BY m.branch, k.genre; SQL ``` ```text ┌──────────┬────────────┬───────┐ │ branch │ genre │ count │ ├──────────┼────────────┼───────┤ │ Besiktas │ essay │ 1 │ │ Besiktas │ fiction │ 2 │ │ Besiktas │ history │ 1 │ │ Besiktas │ philosophy │ 1 │ │ Besiktas │ science │ 1 │ │ Kadikoy │ essay │ 1 │ │ Kadikoy │ fiction │ 4 │ │ Kadikoy │ history │ 3 │ │ Kadikoy │ poetry │ 1 │ │ Kadikoy │ science │ 2 │ │ Uskudar │ fiction │ 2 │ │ Uskudar │ history │ 1 │ │ Uskudar │ philosophy │ 1 │ │ Uskudar │ poetry │ 1 │ │ Uskudar │ science │ 3 │ └──────────┴────────────┴───────┘ ``` This form is convenient for data processing: when a new genre is added, the query does not change, only the row count grows. For reading, it is inconvenient. Comparing Kadikoy's and Uskudar's fiction counts requires the eye to scan up and down through fifteen rows, and cells that are zero — Besiktas has no poetry — do not appear at all. #### Pivoting with Conditional Aggregation The portable way to pivot is to write one conditional aggregation expression per target column. A `CASE` expression produces 1 or 0 depending on whether the row belongs to that column; `SUM` adds them up. ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, genre TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(3,'Clara','Uskudar'), (4,'Derek','Uskudar'),(5,'Evan','Besiktas'),(6,'Fiona','Besiktas'), (7,'Grace','Kadikoy'),(8,'Hannah','Uskudar'); INSERT INTO book VALUES (1,'Lost Time','fiction'),(2,'Silent House','fiction'), (3,'Number Theory','science'),(4,'The Structure of the Universe','science'),(5,'Short History','history'), (6,'Anatolian Notes','history'),(7,'Poems','poetry'),(8,'Essays','essay'), (9,'Roadmap','fiction'),(10,'Epistemology','philosophy'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); SELECT m.branch, SUM(CASE WHEN k.genre = 'fiction' THEN 1 ELSE 0 END) AS fiction, SUM(CASE WHEN k.genre = 'science' THEN 1 ELSE 0 END) AS science, SUM(CASE WHEN k.genre = 'history' THEN 1 ELSE 0 END) AS history, SUM(CASE WHEN k.genre = 'poetry' THEN 1 ELSE 0 END) AS poetry, SUM(CASE WHEN k.genre = 'essay' THEN 1 ELSE 0 END) AS essay, SUM(CASE WHEN k.genre = 'philosophy' THEN 1 ELSE 0 END) AS philosophy, COUNT(*) AS total FROM loan o JOIN member m ON m.id = o.member_id JOIN book k ON k.id = o.book_id GROUP BY m.branch ORDER BY m.branch; SQL ``` ```text ┌──────────┬─────────┬─────────┬─────────┬────────┬───────┬────────────┬───────┐ │ branch │ fiction │ science │ history │ poetry │ essay │ philosophy │ total │ ├──────────┼─────────┼─────────┼─────────┼────────┼───────┼────────────┼───────┤ │ Besiktas │ 2 │ 1 │ 1 │ 0 │ 1 │ 1 │ 6 │ │ Kadikoy │ 4 │ 2 │ 3 │ 1 │ 1 │ 0 │ 11 │ │ Uskudar │ 2 │ 3 │ 1 │ 1 │ 0 │ 1 │ 8 │ └──────────┴─────────┴─────────┴─────────┴────────┴───────┴────────────┴───────┘ ``` Fifteen rows shrank to three, and empty cells showed up as zero. This is information the long form could not give: the difference between Besiktas **having no** poetry loans and poetry being **unknown** at Besiktas is now readable. If the `ELSE 0` part is omitted, non-matching rows produce a null value. Since `SUM` skips null values, the result does not change in most cases; but if **all** of a group's rows fail to match, the column stays null instead of zero. In reports where zero is meaningful, either `ELSE 0` has to be written, or the result has to be wrapped in `COALESCE`. This phrasing's cost is a single scan: every row is read once, and the six expressions are all evaluated over the same row. Producing the same result by combining six separate queries would mean scanning the table six times. #### The FILTER Clause Standard SQL defines a separate phrasing for conditional aggregation: the `FILTER (WHERE …)` clause following an aggregate function makes that function see only the rows that satisfy the condition. Its purpose is the same as `CASE`'s, and it reads better — the condition sits right next to the thing being counted: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, genre TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(3,'Clara','Uskudar'), (4,'Derek','Uskudar'),(5,'Evan','Besiktas'),(6,'Fiona','Besiktas'), (7,'Grace','Kadikoy'),(8,'Hannah','Uskudar'); INSERT INTO book VALUES (1,'Lost Time','fiction'),(2,'Silent House','fiction'), (3,'Number Theory','science'),(4,'The Structure of the Universe','science'),(5,'Short History','history'), (6,'Anatolian Notes','history'),(7,'Poems','poetry'),(8,'Essays','essay'), (9,'Roadmap','fiction'),(10,'Epistemology','philosophy'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'), (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL), (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'), (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'), (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'), (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'), (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'), (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL), (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'), (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'), (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL), (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'), (25,4,8,'2024-03-13','2024-03-24'); SELECT m.branch, COUNT(*) FILTER (WHERE k.genre = 'fiction') AS fiction, COUNT(*) FILTER (WHERE k.genre = 'science') AS science, COUNT(*) FILTER (WHERE k.genre = 'history') AS history, COUNT(*) FILTER (WHERE o.returned IS NULL) AS not_returned, COUNT(*) AS total FROM loan o JOIN member m ON m.id = o.member_id JOIN book k ON k.id = o.book_id GROUP BY m.branch ORDER BY m.branch; SQL ``` ```text ┌──────────┬─────────┬─────────┬─────────┬──────────────┬───────┐ │ branch │ fiction │ science │ history │ not_returned │ total │ ├──────────┼─────────┼─────────┼─────────┼──────────────┼───────┤ │ Besiktas │ 2 │ 1 │ 1 │ 1 │ 6 │ │ Kadikoy │ 4 │ 2 │ 3 │ 2 │ 11 │ │ Uskudar │ 2 │ 3 │ 1 │ 2 │ 8 │ └──────────┴─────────┴─────────┴─────────┴──────────────┴───────┘ ``` The fiction, science, and history columns are the same as the previous result. The fourth column shows that pivoting is not limited to a single distinguishing column: `not_returned` is an independent condition unrelated to genre, and it was computed in the same scan. Bringing different criteria together side by side in the same row is conditional aggregation's real benefit, independent of pivoting. The `FILTER` clause is standard but is not present in every engine; where it is not supported, the `CASE` phrasing always works. #### The Reverse Direction: Column to Row The reverse operation converts a wide-form table into long form. The need arises when a wide summary coming from an external source is loaded into a normalized table, or when a query is wanted that does not break as the genre count changes. The portable phrasing is to turn the column names into a list of values and cross join that with the source table: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE summary(branch TEXT PRIMARY KEY, fiction INT, science INT, history INT); INSERT INTO summary VALUES ('Besiktas',2,1,1),('Kadikoy',4,2,3),('Uskudar',2,3,1); WITH genres(genre) AS (VALUES ('fiction'),('science'),('history')) SELECT s.branch, g.genre, CASE g.genre WHEN 'fiction' THEN s.fiction WHEN 'science' THEN s.science WHEN 'history' THEN s.history END AS count FROM summary s CROSS JOIN genres g ORDER BY s.branch, g.genre; SQL ``` ```text ┌──────────┬─────────┬───────┐ │ branch │ genre │ count │ ├──────────┼─────────┼───────┤ │ Besiktas │ fiction │ 2 │ │ Besiktas │ history │ 1 │ │ Besiktas │ science │ 1 │ │ Kadikoy │ fiction │ 4 │ │ Kadikoy │ history │ 3 │ │ Kadikoy │ science │ 2 │ │ Uskudar │ fiction │ 2 │ │ Uskudar │ history │ 1 │ │ Uskudar │ science │ 3 │ └──────────┴─────────┴───────┘ ``` The cross join matched three branches with three genres and produced nine rows; `CASE` picked the correct column on every row. The source table is read **once**. The same result can also be produced by writing one query per column and combining them with `UNION ALL`: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE summary(branch TEXT PRIMARY KEY, fiction INT, science INT, history INT); INSERT INTO summary VALUES ('Besiktas',2,1,1),('Kadikoy',4,2,3),('Uskudar',2,3,1); SELECT branch, 'fiction' AS genre, fiction AS count FROM summary UNION ALL SELECT branch, 'science', science FROM summary UNION ALL SELECT branch, 'history', history FROM summary ORDER BY branch, genre; SQL ``` ```text ┌──────────┬─────────┬───────┐ │ branch │ genre │ count │ ├──────────┼─────────┼───────┤ │ Besiktas │ fiction │ 2 │ │ Besiktas │ history │ 1 │ │ Besiktas │ science │ 1 │ │ Kadikoy │ fiction │ 4 │ │ Kadikoy │ history │ 3 │ │ Kadikoy │ science │ 2 │ │ Uskudar │ fiction │ 2 │ │ Uskudar │ history │ 1 │ │ Uskudar │ science │ 3 │ └──────────┴─────────┴───────┘ ``` The results are the same; readability and cost differ. The union-based phrasing scans the table once per column: three columns, three scans. For small summary tables this does not matter; for a large source, the cross-join phrasing is preferred. #### Why the Column List Is Fixed In both directions, the genre names were written into the query's text by hand. This is not a shortcoming but a consequence of the relational model: a query's result is a relation, and a relation's header — its column names and types — is known before the query runs. Producing columns by looking at the data would break this definition. The practical consequence is this: when a new book genre is added, the wide-form query does not gain a column on its own; the query has to be updated. Anyone who wants to derive the column list from the data has to assemble the query text on the application side and send it to the engine. This path is open, but it carries two costs: queries produced by string concatenation open an injection surface, and because each distinct column list produces a different query text, it does not benefit from the plan cache. These two subjects are taken up in the Dynamic SQL Risks lesson in the course's Query Performance topic. Some engines offer a `PIVOT` keyword or something similar. These phrasings are not part of standard SQL, and they still want the column list at the time the query is written; what they do is shorten conditional aggregation. #### Summary - Long form is convenient for data processing, wide form for reading; a pivot is the transformation between these two forms. - The portable pivot phrasing is one conditional aggregation expression per target column, completed in a single scan; if `ELSE 0` is not written, a group that matches nothing at all leaves its column null. - The `FILTER (WHERE …)` clause writes the same job more readably and allows independent criteria to be gathered into the same row. - The reverse pivot is written by turning column names into a value list and cross joining, in a single scan, or with `UNION ALL`, at one scan per column. - The result columns have to be known when the query is written; deriving the column list from the data requires assembling the query text on the application side. #### Next Step Every query written throughout this topic was a single statement and answered a single question. Data-modifying work, though, often does not fit into one statement: lending a book requires both opening a loan record and updating the book's status together. If one of the two happens and the other does not, the data is left inconsistent. The next topic takes up the operations that turn several statements into a single indivisible unit; its first lesson begins with starting, committing, and rolling back a transaction. ## Transactions Transaction control, partial rollback with savepoints, isolation levels and read anomalies, row and table locks with deadlock, stored procedures and functions, and the implicit side effects of triggers. ### Transaction Control Source: https://academia.sh/en/courses/advanced-sql/transaction-control Autocommit mode, starting an explicit transaction with BEGIN, COMMIT and ROLLBACK, why a statement error does not end the transaction by itself, and implicit rollback when a connection drops. Every query written in the previous topic was a single statement answering a single question. Work that changes data rarely fits in one statement. Lending a book requires two changes: opening a loan record and updating the book's shelf status. If one happens and the other does not, the database describes a state that never actually existed — a loan that looks open while the book is still on the shelf, or the reverse. The Relational Theory course introduced the ACID properties and defined atomicity as all-or-nothing. A **transaction** is what that definition becomes in practice: it turns several statements into a single unit the engine treats as indivisible. #### Autocommit Any statement run without an explicit transaction is its own transaction. This behavior is called **autocommit**: if the statement succeeds, its effect is permanent; if it fails, it is as though nothing happened. ```bash rm -f k1.db sqlite3 -box -header k1.db <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT NOT NULL DEFAULT 1); INSERT INTO book VALUES (1,'Lost Time',1),(2,'Silent House',1),(3,'Number Theory',1); UPDATE book SET on_shelf = 0 WHERE id = 1; SQL sqlite3 -box -header k1.db 'SELECT id, title, on_shelf FROM book ORDER BY id;' rm -f k1.db ``` ```text ┌────┬───────────────┬──────────┐ │ id │ title │ on_shelf │ ├────┼───────────────┼──────────┤ │ 1 │ Lost Time │ 0 │ │ 2 │ Silent House │ 1 │ │ 3 │ Number Theory │ 1 │ └────┴───────────────┴──────────┘ ``` The first command created and updated the database, then ended; the second opened as a separate process and saw the change. Nothing here wrote a commit, because every statement committed on its own. This mode suits isolated changes and is dangerous for changes that must travel together: if an error occurs between two statements, the first one is already permanent. Whether autocommit is on or off by default, and how it gets turned off, depends on the engine — some require writing `BEGIN`, others require flipping a setting. What never changes is that an explicit transaction must be closed with `COMMIT` or `ROLLBACK`. #### Starting, Committing, and Rolling Back An explicit transaction begins with `BEGIN`. Every change made after that point is visible only from inside that transaction; it is not permanent until `COMMIT` runs. `ROLLBACK` erases every change made since the transaction started: ```bash rm -f k2.db sqlite3 -box -header k2.db <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT NOT NULL DEFAULT 1); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO book VALUES (1,'Lost Time',1),(2,'Silent House',1),(3,'Number Theory',1); BEGIN; INSERT INTO loan(book_id, member_id, pickup) VALUES (1, 4, '2024-03-11'); UPDATE book SET on_shelf = 0 WHERE id = 1; SELECT 'in transaction' AS moment, (SELECT COUNT(*) FROM loan) AS loan_count, (SELECT on_shelf FROM book WHERE id = 1) AS book1_on_shelf; ROLLBACK; SELECT 'after rollback' AS moment, (SELECT COUNT(*) FROM loan) AS loan_count, (SELECT on_shelf FROM book WHERE id = 1) AS book1_on_shelf; SQL rm -f k2.db ``` ```text ┌────────────────┬────────────┬────────────────┐ │ moment │ loan_count │ book1_on_shelf │ ├────────────────┼────────────┼────────────────┤ │ in transaction │ 1 │ 0 │ └────────────────┴────────────┴────────────────┘ ┌────────────────┬────────────┬────────────────┐ │ moment │ loan_count │ book1_on_shelf │ ├────────────────┼────────────┼────────────────┤ │ after rollback │ 0 │ 1 │ └────────────────┴────────────┴────────────────┘ ``` Inside the transaction, the loan record existed and the book had left the shelf. After the rollback, both returned to their earlier state — not one at a time, but **together**. That is what atomicity means: a rollback leaves no partial result behind. The `SELECT` inside the transaction sees its own changes even though they are not yet committed. This is a requirement of the transaction being consistent with itself; whether another connection can see these rows at the same time is a separate question, addressed in the isolation levels lesson. Had `COMMIT` been written instead, both changes would have become permanent. Committing has a defined meaning for durability too: once `COMMIT` returns successfully, the changes survive even a power failure immediately afterward. How the engine guarantees this — the write-ahead log — is the subject of the Relational Database Administration course. #### A Statement Error Does Not End the Transaction A common assumption is that a statement failing inside a transaction automatically rolls the transaction back. That is not the standard behavior: the failing **statement** has no effect, the transaction stays open, and the decision belongs to the application. The schema below carries a partial uniqueness index: a book cannot have more than one open loan at a time. A second attempt to lend it runs into that constraint: ```bash rm -f k3.db sqlite3 -box -header k3.db <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT NOT NULL DEFAULT 1); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); CREATE UNIQUE INDEX loan_open ON loan(book_id) WHERE returned IS NULL; INSERT INTO book VALUES (1,'Lost Time',0),(2,'Silent House',1); INSERT INTO loan(book_id, member_id, pickup) VALUES (1, 4, '2024-03-11'); BEGIN; INSERT INTO loan(book_id, member_id, pickup) VALUES (1, 7, '2024-03-12'); UPDATE book SET on_shelf = 0 WHERE id = 1; SELECT 'in transaction after error' AS moment, COUNT(*) AS loan_count FROM loan; ROLLBACK; SELECT 'after rollback' AS moment, COUNT(*) AS loan_count FROM loan; SQL rm -f k3.db ``` ```text Runtime error near line 8: UNIQUE constraint failed: loan.book_id (19) ┌────────────────────────────┬────────────┐ │ moment │ loan_count │ ├────────────────────────────┼────────────┤ │ in transaction after error │ 1 │ └────────────────────────────┴────────────┘ ┌────────────────┬────────────┐ │ moment │ loan_count │ ├────────────────┼────────────┤ │ after rollback │ 1 │ └────────────────┴────────────┘ ``` Three things are visible at once. First, the failing `INSERT` had no effect; the loan count stayed at 1. Second, the transaction did **not** close: the following statement kept running and the `UPDATE` was applied. Third, the rollback erased that `UPDATE`'s effect too. The second point is a real source of bugs. Had the error message been ignored and `COMMIT` written, the book would have committed as off the shelf even though no loan had actually opened — exactly the inconsistency the design was meant to avoid. This is why application code checks the result of every statement and issues an explicit `ROLLBACK` when one fails. The shape of the error message depends on the engine; the text here is a typical example naming the constraint and its kind. What does not change is that the violation is reported at the **statement** level and the transaction's fate is left to the application. Some engines instead put the transaction into a locked state after an error, accepting only a rollback; this distinction needs to be known for the target engine. #### When the Connection Drops An uncommitted transaction is rolled back when the connection ends. This requires no explicit action from the application; it is a guarantee from the engine. The script below starts a transaction, inserts a row, and ends the process without writing `COMMIT`: ```bash cat > interrupted.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const db = new DatabaseSync('interrupted.db'); db.exec(` CREATE TABLE IF NOT EXISTS loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT); `); db.exec("BEGIN"); db.exec("INSERT INTO loan(book_id, member_id, pickup) VALUES (1, 4, '2024-03-11')"); console.log('row seen inside transaction:', db.prepare('SELECT COUNT(*) AS n FROM loan').get().n); process.exit(0); JS rm -f interrupted.db node interrupted.mjs sqlite3 -box -header interrupted.db 'SELECT COUNT(*) AS reopened FROM loan;' rm -f interrupted.db ``` ```text row seen inside transaction: 1 ┌──────────┐ │ reopened │ ├──────────┤ │ 0 │ └──────────┘ ``` The process saw the row inside its own transaction; the row was gone when the database file was reopened. The table definition did persist, because `CREATE TABLE` ran in autocommit mode before the transaction began. This behavior shows that committing is a threshold: nothing is promised before `COMMIT` returns. On the application side, the matching discipline is that the code opening a transaction must close it on every exit path — error, early return, or interruption. #### Setting the Transaction Boundary How wide a transaction should be is a design decision under pressure from two directions. Too narrow, and changes that must travel together end up in separate transactions, where an error in between leaves an inconsistency. The transaction's boundary is the boundary of the **business rule**: in a "lend a book" operation, opening the record and updating the shelf status belong in the same transaction. Too wide, and the transaction stays open for a long time; the resources it holds keep other connections waiting, and the cost of rolling it back grows. Holding an open transaction while waiting on user input is the best-known form of this mistake: the database can hold a lock for minutes while it waits for the user's response. How these two pressures get balanced will take concrete shape in the locking behavior lesson. For now, the rule is: a transaction spans the smallest set of statements the business rule requires, and once started, it does not wait on the outside world. #### Summary - Any statement run without an explicit transaction is its own transaction; this mode is called autocommit. - In a transaction opened with `BEGIN`, changes are not permanent until `COMMIT` runs; `ROLLBACK` erases every change made during the transaction together. - A statement error disables only that statement; the transaction stays open and the rollback decision belongs to the application — committing after an error makes a partial result permanent. - An uncommitted transaction is rolled back when the connection ends. - The transaction's boundary is the business rule's boundary; a transaction kept wider than necessary holds resources and keeps other connections waiting. #### Next Step Rollback in this lesson was a single "delete everything" button: the only option was to return to the start of the transaction. That is too blunt for batch work — if the third record out of a hundred books being loaded fails, discarding the first two is unnecessary. The next lesson defines intermediate stops inside a transaction, rolling back only past that stop, and how nested savepoints behave. ### Savepoints Source: https://academia.sh/en/courses/advanced-sql/savepoints Defining an intermediate stop inside a transaction with SAVEPOINT, partial rollback with ROLLBACK TO, why RELEASE is not a commit, how nested points behave, and returning to the same point more than once. In the previous lesson, rollback had a single button: `ROLLBACK` returns to the start of the transaction and erases everything done along the way. That is too blunt for batch work. If the third record in a hundred-book inventory transfer fails, discarding the first two is wasted work; the transfer would have to start over. Standard SQL defines intermediate stops inside a transaction for this. A **savepoint** is a name given to a specific point in the transaction; a rollback can target that name, and everything before it is preserved. #### Setting an Intermediate Stop There are three statements. `SAVEPOINT name` names the current point. `ROLLBACK TO name` erases every change made after that point, without ending the transaction. `RELEASE name` drops the point from the list, and that point can no longer be returned to. ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT NOT NULL, genre TEXT NOT NULL); INSERT INTO book VALUES (1,'Lost Time','fiction'); BEGIN; INSERT INTO book VALUES (11,'Island','fiction'); SAVEPOINT batch2; INSERT INTO book VALUES (12,'The Well','fiction'); INSERT INTO book VALUES (13,'Summer Diary','essay'); ROLLBACK TO batch2; INSERT INTO book VALUES (14,'Hourglass','poetry'); COMMIT; SELECT id, title FROM book ORDER BY id; SQL ``` ```text ┌────┬───────────┐ │ id │ title │ ├────┼───────────┤ │ 1 │ Lost Time │ │ 11 │ Island │ │ 14 │ Hourglass │ └────┴───────────┘ ``` Four rows were attempted to be added, two committed. Books 12 and 13, inserted after the `batch2` point, were deleted; book 11, inserted before the point, was kept. The transaction continued after the rollback, and book 14 was added — `ROLLBACK TO` does not close the transaction. This is the basis of the standard batch-transfer pattern: a savepoint is placed before each batch, released if the batch finishes without error, and returned to and the batch skipped if it fails. The work of earlier batches is preserved. #### RELEASE Is Not a Commit The word `RELEASE` is misleading; it makes nothing permanent. All it does is remove that name from the list of active points. Changes made after a point is released are still part of the transaction, and an outer `ROLLBACK` erases them too: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT NOT NULL, genre TEXT NOT NULL); BEGIN; SAVEPOINT batch; INSERT INTO book VALUES (11,'Island','fiction'); RELEASE batch; SELECT 'after release' AS moment, COUNT(*) AS row_count FROM book; ROLLBACK; SELECT 'after rollback' AS moment, COUNT(*) AS row_count FROM book; SQL ``` ```text ┌───────────────┬───────────┐ │ moment │ row_count │ ├───────────────┼───────────┤ │ after release │ 1 │ └───────────────┴───────────┘ ┌────────────────┬───────────┐ │ moment │ row_count │ ├────────────────┼───────────┤ │ after rollback │ 0 │ └────────────────┴───────────┘ ``` The row was still there right after the release; it disappeared once the transaction was rolled back. The only statement that makes something durable is `COMMIT`. Savepoints organize the structure **inside** a transaction; they do not change what the transaction promises to the outside. This distinction also means savepoints are not "nested transactions." A genuine nested transaction could commit the inner transaction independently of the outer one. There is no such thing with savepoints: if the outer transaction is rolled back, everything inside it goes with it. #### Nested Points Savepoints behave like a stack: each new point sits on top of the earlier ones. Returning to a point invalidates every point defined after it as well. ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT NOT NULL, genre TEXT NOT NULL); BEGIN; INSERT INTO book VALUES (11,'Island','fiction'); SAVEPOINT outer; INSERT INTO book VALUES (12,'The Well','fiction'); SAVEPOINT inner; INSERT INTO book VALUES (13,'Summer Diary','essay'); ROLLBACK TO inner; INSERT INTO book VALUES (14,'Hourglass','poetry'); ROLLBACK TO outer; INSERT INTO book VALUES (15,'Distant Shore','fiction'); COMMIT; SELECT id, title FROM book ORDER BY id; SQL ``` ```text ┌────┬───────────────┐ │ id │ title │ ├────┼───────────────┤ │ 11 │ Island │ │ 15 │ Distant Shore │ └────┴───────────────┘ ``` Five inserts were made, two survived. `ROLLBACK TO inner` deleted only book 13; books 12 and 14 remained standing. Then `ROLLBACK TO outer` ran and erased everything defined after the `outer` point — books 12 and 14, plus the `inner` point itself. Book 11, added before the outer point, was kept, and book 15, added after the rollback, was committed. Indentation only helps with reading; it has no meaning in SQL. The only thing that makes the stack behavior readable is choosing names that reflect their scope. #### Returning to the Same Point More Than Once `ROLLBACK TO` does not **consume** the point it returns to. The point stays in place and can be reused. This makes it possible to try several options in sequence inside one transaction: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT NOT NULL, genre TEXT NOT NULL); INSERT INTO book VALUES (11,'Island','fiction'); BEGIN; SAVEPOINT trial; INSERT INTO book VALUES (11,'Colliding','fiction'); ROLLBACK TO trial; INSERT INTO book VALUES (12,'The Well','fiction'); ROLLBACK TO trial; INSERT INTO book VALUES (13,'Summer Diary','essay'); RELEASE trial; COMMIT; SELECT id, title FROM book ORDER BY id; SQL ``` ```text Runtime error near line 6: UNIQUE constraint failed: book.id (19) ┌────┬──────────────┐ │ id │ title │ ├────┼──────────────┤ │ 11 │ Island │ │ 13 │ Summer Diary │ └────┴──────────────┘ ``` The `trial` point was returned to twice, and it worked both times. The first attempt hit a constraint violation; the second succeeded but was rolled back anyway; the third committed. None of the earlier attempts left a trace in the transaction. Writing `SAVEPOINT` a second time with the same name creates a new point that shadows the old one; a rollback targets the most recently defined one. To avoid confusion, names should be chosen uniquely, or the point should be released once it is no longer needed. #### The Batch Pattern The full pattern is completed by application code that catches the error and makes the decision. The script below runs a three-batch transfer; the second batch has a colliding identifier: ```bash cat > transfer.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const db = new DatabaseSync(':memory:'); db.exec(`CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT NOT NULL, genre TEXT NOT NULL); INSERT INTO book VALUES (11,'Island','fiction');`); const batches = [ [[21, 'The Well', 'fiction'], [22, 'Hourglass', 'poetry']], [[23, 'Summer Diary', 'essay'], [11, 'Colliding', 'fiction']], [[24, 'Distant Shore', 'fiction']], ]; const insert = db.prepare('INSERT INTO book VALUES (?, ?, ?)'); db.exec('BEGIN'); batches.forEach((batch, index) => { db.exec(`SAVEPOINT batch_${index}`); try { for (const row of batch) insert.run(...row); db.exec(`RELEASE batch_${index}`); console.log(`batch ${index}: accepted (${batch.length} rows)`); } catch (error) { db.exec(`ROLLBACK TO batch_${index}`); console.log(`batch ${index}: skipped — ${error.message}`); } }); db.exec('COMMIT'); for (const s of db.prepare('SELECT id, title FROM book ORDER BY id').all()) { console.log(s.id, s.title); } JS node transfer.mjs ``` ```text batch 0: accepted (2 rows) batch 1: skipped — UNIQUE constraint failed: book.id batch 2: accepted (1 rows) 11 Island 21 The Well 22 Hourglass 24 Distant Shore ``` The second batch's first row — book 23 — was valid and had been inserted; once the batch was rolled back, it went too. This is a deliberate choice in the pattern: a batch is accepted as a whole or rejected as a whole. If keeping valid rows is required, the batch size is reduced to one, at the cost of a savepoint per row. In the script, `RELEASE` runs only for successful batches. The point for a failed batch stays in place, but since `COMMIT` closes every point, this does not create a leak. #### Where It Is Used Savepoints have three typical uses. **Batch transfers.** A point is placed before each batch; if a batch fails, it is rolled back to that point, the record is written to an error log, and the transfer continues. The alternative is making each batch its own transaction, which loses the integrity guarantee across batches. **Steps that can be tried and abandoned.** A costly path in a computation is tried first; if the result is unsuitable, it is rolled back and a different path is chosen. Because the whole transaction stays open, intermediate results never leak outward. **Reusable code at library boundaries.** A function that does not know whether it is already inside a transaction cannot unconditionally write `BEGIN` — it would fail if a transaction is already open. Instead it opens a savepoint; if an error occurs, it rolls back only its own work and leaves the caller's transaction untouched. This is what "nested transaction" support in most data-access libraries actually is. On the cost side, savepoints are not free: the engine keeps extra bookkeeping so it can undo the changes made after each point. A transfer that opens a savepoint per row inflates its own bookkeeping more than the work itself. Point count is kept at the batch level, not the row level. #### Summary - `SAVEPOINT` names an intermediate stop inside a transaction; `ROLLBACK TO` erases everything after that point without closing the transaction. - `RELEASE` is not a commit; it only drops the point from the list, and the only statement that makes something durable is `COMMIT`. - Points behave like a stack: returning to one invalidates every point defined after it. - `ROLLBACK TO` does not consume the point; returning to the same point more than once lets different options be tried. - Because extra bookkeeping is kept per point, savepoints are used at the batch level, not the row level. #### Next Step Across these two lessons, only one connection reached the database; all a transaction ever saw was its own changes. In real systems, many connections read and write at the same time. The questions "can someone else see an uncommitted change" and "does the same query inside a transaction return the same result twice" only become meaningful then. The next lesson defines the concept of isolation that ties the answers to those questions to a level, and walks through the read anomalies the standard defines one by one. ### Isolation Levels Source: https://academia.sh/en/courses/advanced-sql/isolation-levels The dirty read, non-repeatable read, and phantom row anomalies, the four standard isolation levels, a real observation with two connections, and describing the level that cannot be shown through a model. Across the previous two lessons, only one connection reached the database. A transaction saw its own changes, and nothing happened outside it. In real systems, many connections read and write at the same time, and two questions become meaningful: can a transaction see a change another transaction has not yet committed? Does the same query return the same result when run twice inside one transaction? **Isolation** is the property that determines the answers to these questions. It is the third letter of the ACID sequence introduced in the Relational Theory course. Full isolation asks for the result of transactions running concurrently to be the same as running them one after another. This strong guarantee is costly, which is why the standard defines relaxed levels and describes each one by **which anomaly it allows**. #### Three Anomalies The standard defines three read anomalies. All three are about "data read while another transaction stepped in getting corrupted," but the shape of the corruption differs. **Dirty read.** A transaction reads a change another transaction has not yet committed. If the other transaction is rolled back, the value that was read is a value that never actually existed. **Non-repeatable read.** A transaction reads the same row twice and sees different values; another transaction updated and committed that row in between. **Phantom row.** A transaction queries the same condition twice and, the second time, sees **new rows** matching the condition; another transaction inserted rows in between. The difference from a non-repeatable read is that what changed is not a row's value but the membership of a set. The distinction matters in practice, because it separates what row locks can prevent from what they cannot: an existing row can be locked, a row that does not yet exist cannot. #### Four Levels The standard defines four levels. Each level also prevents everything a looser level prevents: | Level | Dirty read | Non-repeatable read | Phantom row | |---|---|---|---| | `READ UNCOMMITTED` | possible | possible | possible | | `READ COMMITTED` | not possible | possible | possible | | `REPEATABLE READ` | not possible | not possible | possible | | `SERIALIZABLE` | not possible | not possible | not possible | Two points should not be missed when reading this table. First, the table lists what is **allowed**, not what will happen. At `READ COMMITTED`, a non-repeatable read "is possible"; that does not mean it always happens. An engine can offer a stronger guarantee and still use that level's name. Second, the levels are not an implementation, they are a **contract**. Two engines carrying the same name can satisfy it in different ways: one through locking, another through multi-version concurrency control. The result is that the forbidden anomalies do not occur; the path there is unconstrained. The level is selected with the standard's `SET TRANSACTION ISOLATION LEVEL` statement. Which levels are actually offered depends on the engine: some accept all four but map some of them to a stronger level, others offer no choice at all. The engine used in the observation below belongs to the second group — there is no level selection, and reads are made through a consistent view. #### An Observation with Two Connections The script below opens **two separate connections** to the same database file and produces a controlled version of another transaction stepping in. First the reader reads twice without opening a transaction; then it performs the same read inside an open transaction. The writer does the same work in both cases: it updates one row and adds a new open loan record. ```bash rm -f isolation.db isolation.db-wal isolation.db-shm cat > isolation.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const reader = new DatabaseSync('isolation.db'); const writer = new DatabaseSync('isolation.db'); reader.exec('PRAGMA journal_mode = WAL'); writer.exec(` CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,4,'2024-03-01',NULL),(2,3,4,'2024-03-04',NULL), (3,5,7,'2024-03-06',NULL); `); const read = (b) => b.prepare( `SELECT (SELECT pickup FROM loan WHERE id = 1) AS loan1_pickup, (SELECT COUNT(*) FROM loan WHERE returned IS NULL) AS open_count`).get(); console.log('— reading without a transaction —'); console.log('read 1:', JSON.stringify(read(reader))); writer.exec("UPDATE loan SET pickup = '2024-03-02' WHERE id = 1"); writer.exec("INSERT INTO loan VALUES (4,7,4,'2024-03-11',NULL)"); console.log('writer updated one row, inserted one row, committed'); console.log('read 2:', JSON.stringify(read(reader))); console.log('— reading inside a transaction —'); reader.exec('BEGIN'); console.log('read 1:', JSON.stringify(read(reader))); writer.exec("UPDATE loan SET pickup = '2024-03-03' WHERE id = 1"); writer.exec("INSERT INTO loan VALUES (5,9,7,'2024-03-13',NULL)"); console.log('writer did the same work once more and committed'); console.log('read 2:', JSON.stringify(read(reader))); reader.exec('COMMIT'); console.log('transaction ended, read 3:', JSON.stringify(read(reader))); JS node isolation.mjs rm -f isolation.db isolation.db-wal isolation.db-shm ``` ```text — reading without a transaction — read 1: {"loan1_pickup":"2024-03-01","open_count":3} writer updated one row, inserted one row, committed read 2: {"loan1_pickup":"2024-03-02","open_count":4} — reading inside a transaction — read 1: {"loan1_pickup":"2024-03-02","open_count":4} writer did the same work once more and committed read 2: {"loan1_pickup":"2024-03-02","open_count":4} transaction ended, read 3: {"loan1_pickup":"2024-03-03","open_count":5} ``` In the first section, the reader did not open a transaction; each `SELECT` was its own transaction. Between the two reads, both the row's value changed — the definition of a non-repeatable read — and the count of matching rows grew — the definition of a phantom row. This is not a bug: the world changing between two separate transactions is expected. In the second section, the reader opened a transaction with `BEGIN`. The writer made the same two changes and committed, but the reader's second read **did not change at all**: neither the value nor the count. The third read, made after the transaction closed, showed the new state. The difference is that the transaction kept the consistent view it took on its first read all the way to the end — that is, it kept reading through a snapshot. The observation makes the difference concrete across the table's first three rows. The side reading without a transaction showed the behavior `READ COMMITTED` allows: it saw only committed data, but its repeated reads differed. The side reading inside a transaction showed the read-side behavior of `SERIALIZABLE`: both the non-repeatable read and the phantom row disappeared. #### The Level That Cannot Be Shown One of the four levels in the table cannot be observed on this engine. `READ UNCOMMITTED` allows reading an uncommitted change; the engine in use here does not offer that under any setting, because reads are always made from an already-committed snapshot. Real engine output cannot be produced to show what the result of a dirty read would be. Instead, the behavior can be **modeled**. The script below is not a database; it is a small timing model holding the committed and uncommitted values of a single record. It compares what the reader would see with and without dirty reads allowed: ```bash cat > dirty-model.mjs <<'JS' // Dirty read model: mimics the behavior of an engine that can see an // uncommitted value. It is not real engine output; the goal is to show // what the result would be. const record = { onShelf: 1, uncommitted: null }; const read = (dirtyReadAllowed) => dirtyReadAllowed && record.uncommitted !== null ? record.uncommitted : record.onShelf; const attempt = (dirtyReadAllowed) => { record.uncommitted = 0; // writer: lent the book, not yet committed const seen = read(dirtyReadAllowed); // reader steps in record.uncommitted = null; // writer: rolled back the transaction return { seenByReader: seen, actualAfterRollback: record.onShelf }; }; console.log('level that allows dirty reads :', JSON.stringify(attempt(true))); console.log('level that disallows dirty reads :', JSON.stringify(attempt(false))); JS node dirty-model.mjs ``` ```text level that allows dirty reads : {"seenByReader":0,"actualAfterRollback":1} level that disallows dirty reads : {"seenByReader":1,"actualAfterRollback":1} ``` In the first line, the reader saw the book as lent; because the writer rolled back the transaction, that value never became real. That is the harm of a dirty read: what gets read is not a stale value, it is a value that **never existed**. A decision made on that basis — such as not reserving the book — corresponds to no real state at all. Because this block is a model, its output is not evidence of any engine's behavior; it only makes the definition's consequence visible. If an engine genuinely offers `READ UNCOMMITTED`, the same result needs to be measured on that engine. #### Choosing a Level Lower levels give less coordination and therefore more concurrency. The price is that the application has to handle the anomalies on its own. The decision is made by looking at what the work does with the data it reads. If the value read is only displayed, a relaxed level is enough; if a **write** is made based on the value read — "check whether it is on the shelf, and if so, lend it" — a relaxed level opens the door to a silent error. Two transactions can both see the book on the shelf at the same time and lend the same book to two different members. This is called a **lost update**, and it can be prevented not only by raising the isolation level but also by locking the read. Both paths cost the same thing: transactions touching the same row have to wait for each other. That waiting mechanism is the subject of the next lesson. #### Summary - A dirty read sees uncommitted data, a non-repeatable read sees a changed row value, a phantom row sees new rows matching a condition. - The standard defines its four levels by which anomaly they allow; the table lists what is allowed, not what will happen. - A level is a contract, not an implementation; two engines carrying the same name can satisfy it through locking or through multi-version control. - In the two-connection observation, the side reading without a transaction saw both a changed value and a changed row count; the side reading inside an open transaction kept the view from its first read all the way to the end. - If a write is made based on a value that was read, a relaxed level opens the door to a lost update. #### Next Step Isolation levels say what will and will not be visible, but they do not say what that costs. When two transactions want to write to the same row, one of them has to wait; how long the wait lasts depends on what got locked. If two transactions wait on resources held by each other, neither can proceed. The next lesson covers lock types, the real error an engine gives on an actual conflict, and how mutual waiting gets resolved. ### Locking Behavior Source: https://academia.sh/en/courses/advanced-sql/locking-behavior Shared and exclusive locks, lock granularity, a real conflict and its error message produced with two connections, lock upgrade conflict, the deadlock cycle, and lock timeout. Isolation levels say what will be visible; they do not say what that costs. The cost is that transactions touching the same data have to wait for each other. The mechanism that governs the waiting is the **lock**: a transaction acquires a right on a resource before touching it, holds that right until its work is done, and then releases it. This lesson defines lock types, produces a real conflict with two connections, and reads the error the engine gives. #### Two Kinds of Locks The basic model rests on two kinds of locks. A **shared lock** is for reading. Multiple shared locks can sit on the same resource at once; readers do not block each other. An **exclusive lock** is for writing. If a resource carries an exclusive lock, neither another shared lock nor another exclusive lock can be placed on it. The compatibility rule fits in one sentence: reading does not block reading, writing blocks everything. Engines using multi-version concurrency control relax this rule on the read side — readers see an older version, so they do not wait on the writer. That is an implementation choice covered in the Relational Database Administration course. **What** a lock is placed on is a separate axis: a row, a page, a table, or the whole database. Finer granularity increases concurrency but grows the number of locks and the bookkeeping behind them. The engine in the observation below locks the entire database for writes; on an engine using row-level locking, two transactions writing to different rows in the same scenario would not block each other. This is engine-dependent behavior, and it needs to be known when writing portable code. #### A Real Conflict The script below opens two connections to the same file. The first connection opens a write transaction and keeps it open; the second tries to write: ```bash rm -f lock.db lock.db-wal lock.db-shm cat > lock.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const a = new DatabaseSync('lock.db'); const b = new DatabaseSync('lock.db'); a.exec('PRAGMA journal_mode = WAL'); a.exec(`CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT); INSERT INTO book VALUES (1,'Lost Time',1),(2,'Silent House',1);`); a.exec('BEGIN IMMEDIATE'); a.exec('UPDATE book SET on_shelf = 0 WHERE id = 1'); console.log('A: write transaction open, book 1 updated'); try { b.exec('BEGIN IMMEDIATE'); b.exec('UPDATE book SET on_shelf = 0 WHERE id = 2'); console.log('B: updated'); } catch (error) { console.log('B got an error:', error.code, '-', error.message); } console.log('can B still read:', b.prepare('SELECT on_shelf FROM book WHERE id = 1').get().on_shelf); a.exec('COMMIT'); console.log('A committed; B can write now'); b.exec('BEGIN IMMEDIATE'); b.exec('UPDATE book SET on_shelf = 0 WHERE id = 2'); b.exec('COMMIT'); console.log('final state:', JSON.stringify(a.prepare( 'SELECT id, on_shelf FROM book ORDER BY id').all())); JS node lock.mjs rm -f lock.db lock.db-wal lock.db-shm ``` ```text A: write transaction open, book 1 updated B got an error: ERR_SQLITE_ERROR - database is locked can B still read: 1 A committed; B can write now final state: [{"id":1,"on_shelf":0},{"id":2,"on_shelf":0}] ``` Three things are worth noting. First, B wanted to write to the **second** book while A had written to the first. It was still blocked: on this engine, the write lock is database-wide. On an engine using row-level locking, this attempt would have succeeded. Second, the error message reports **rejection**, not waiting. Because the lock timeout was zero, the engine returned immediately instead of joining a queue. The message's shape is engine-specific; what is common is that the conflict reaches the application as an error. Third, B could not write but **could read**, and it saw the old value, not the one A had not yet committed. The reader making progress independently of the writer is the lock-side counterpart of the snapshot behavior from the previous lesson. Once A committed, B's same write went through without issue. A conflict is not a permanent block; it is a timing-dependent race. #### Lock Upgrade Conflict A more subtle case is two transactions that both read first and write second. Both start with a read right, then both want to **upgrade** to a write right. If one upgrades, the other's request cannot be satisfied: ```bash rm -f lock2.db lock2.db-wal lock2.db-shm cat > upgrade-conflict.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const a = new DatabaseSync('lock2.db'); const b = new DatabaseSync('lock2.db'); a.exec('PRAGMA journal_mode = WAL'); a.exec(`CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT); INSERT INTO book VALUES (1,'Lost Time',1),(2,'Silent House',1);`); a.exec('BEGIN'); b.exec('BEGIN'); console.log('A read:', a.prepare('SELECT on_shelf FROM book WHERE id = 1').get().on_shelf); console.log('B read:', b.prepare('SELECT on_shelf FROM book WHERE id = 1').get().on_shelf); a.exec('UPDATE book SET on_shelf = 0 WHERE id = 1'); console.log('A wrote'); try { b.exec('UPDATE book SET on_shelf = 0 WHERE id = 1'); console.log('B wrote'); } catch (error) { console.log('B got an error:', error.code, '-', error.message); } b.exec('ROLLBACK'); a.exec('COMMIT'); console.log('final state:', JSON.stringify(a.prepare( 'SELECT id, on_shelf FROM book ORDER BY id').all())); JS node upgrade-conflict.mjs rm -f lock2.db lock2.db-wal lock2.db-shm ``` ```text A read: 1 B read: 1 A wrote B got an error: ERR_SQLITE_ERROR - database is locked final state: [{"id":1,"on_shelf":0},{"id":2,"on_shelf":1}] ``` Both transactions saw the book on the shelf; both wanted to lend it. Without isolation, both would have succeeded, and the book would have appeared to be lent to two members at once — the lost update from the previous lesson. The lock prevented that: one won, the other got an error. The correct behavior for the side that got the error is to roll back and **retry**. On retry, the read fetches the current value and shows that the book is no longer on the shelf. Resolving the conflict is completed by the application writing this retry loop; all the engine does on its own is not leave the conflict silent. The standard way to build this pattern without the error is to do the read with write intent from the start. Standard SQL defines a form for this that locks the rows it reads: ```sql SELECT on_shelf FROM book WHERE id = 1 FOR UPDATE; ``` This form takes an exclusive right on the row while reading it; the second transaction enters a wait during the read step, and the upgrade conflict never occurs. The engine in the observation above does not recognize this clause; its counterpart is opening the transaction with write intent through `BEGIN IMMEDIATE`. The statement itself was not run here; only its form is shown. #### Deadlock If two transactions wait on resources held by each other, neither can proceed. This is called a **deadlock**, and its simplest form arises with two resources: | Step | Transaction A | Transaction B | |---|---|---| | 1 | locks the `book` row | — | | 2 | — | locks the `member` row | | 3 | requests and waits on the `member` row | — | | 4 | — | requests and waits on the `book` row | After the fourth step there is a cycle in the wait-for graph, and no wait ends on its own. Engines resolve this in two ways. Engines that detect deadlocks scan the wait-for graph, pick a **victim** transaction when a cycle is found, and roll it back; the victim gets a deadlock error. Engines without detection set a lock timeout; when the time runs out, the waiting transaction gets an error. In the second approach, a genuine deadlock cannot be told apart from a merely slow transaction. No cycle formed in the observation above, because that engine allows only one writer at a time; the second writer is rejected before it even starts waiting. Deadlock is a problem for engines that hold locks at a finer granularity — more the cost of more concurrency. Prevention works by keeping the cycle from forming: - Touching resources **in the same order every time**. If both transactions lock `book` before `member`, the third and fourth steps go in the same direction and the cycle never closes. - Keeping transactions short. The shorter the lock is held, the lower the chance of conflict. - Acquiring all locks up front where possible, instead of escalating rights as work proceeds. These three do not eliminate the conflict, they lower its odds. Because the chance of an error remains, every transaction that might conflict needs to be written so it can be retried: running the same transaction a second time must not produce an additional side effect, meaning it has to be idempotent. #### Lock Timeout The choice between rejecting and waiting is a setting. If a lock timeout is given, a conflicting transaction waits for the lock to free up for the stated duration instead of getting an error immediately: ```bash rm -f lock3.db lock3.db-wal lock3.db-shm cat > wait-timeout.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const a = new DatabaseSync('lock3.db'); const b = new DatabaseSync('lock3.db', { timeout: 250 }); a.exec('PRAGMA journal_mode = WAL'); a.exec(`CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT); INSERT INTO book VALUES (1,'Lost Time',1);`); a.exec('BEGIN IMMEDIATE'); a.exec('UPDATE book SET on_shelf = 0 WHERE id = 1'); const start = process.hrtime.bigint(); try { b.exec('BEGIN IMMEDIATE'); } catch (error) { const elapsed = Number(process.hrtime.bigint() - start) / 1e6; console.log('B got an error:', error.code); console.log('is the wait past the 250 ms limit:', elapsed >= 250); } a.exec('COMMIT'); JS node wait-timeout.mjs rm -f lock3.db lock3.db-wal lock3.db-shm ``` ```text B got an error: ERR_SQLITE_ERROR is the wait past the 250 ms limit: true ``` The measured duration itself depends on the machine and its load, so it was not printed; what was printed is whether the limit was exceeded. The result is the same error as in the first observation — the difference is that the error arrives not immediately, but after the stated duration has been waited out. Choosing the limit is a trade-off. A short limit reports conflict quickly and lets the application retry; a long limit hides transient conflicts from the application entirely but extends resource holding in a genuine deadlock. Both rest on the assumption that transactions are kept short. #### Summary - A shared lock is for reading, an exclusive lock is for writing; reading does not block reading, writing blocks everything. - Lock granularity ranges from row to database; finer granularity increases concurrency and grows the bookkeeping. - In the observation, the second writer got a `database is locked` error but could still read; a conflict is not a permanent block, it is a timing-dependent race. - Two transactions that read then write produce a lock upgrade conflict; the standard fix is locking the read with write intent, the application fix is rolling back and retrying. - A deadlock is a cycle forming in the wait-for graph; touching resources in the same order, keeping transactions short, and writing retry-safe code are preventive habits. #### Next Step Up to this lesson, the transaction's boundary, what to do on error, and retrying were all decided by application code; the database only took the statements it was given. Some of this logic can also be defined inside the database itself: the lending rule can be put into a procedure that the application triggers with a single call. The next lesson covers the standard form of procedures and functions that run on the server side, what they provide, and the trade-offs they bring. ### Stored Procedures and Functions Source: https://academia.sh/en/courses/advanced-sql/stored-procedures-and-functions The standard form of server-side procedures and functions, the distinction between procedure and function, the consequences of determinism, measuring the round-trip count, and comparison with views. Up to this point, the transaction's boundary, what to do on error, and retrying were all decided by application code; the database only took the statements it was sent. Some of this logic can also be defined inside the database itself. If the "lend a book" rule is put into a procedure, the application sends one call instead of two statements; the rule stays in the same place as the data. A **stored procedure** and a **stored function** are code units stored on the server side and called by name. This lesson covers their standard form, the distinction between them, and the trade-offs they bring. #### Procedure and Function What separates them is how they are called and what they return. A **procedure** is called with `CALL`. It is not required to return a value; it can take input, output, and input-output parameters, and its body can contain statements that change data. A **function** returns a value and can be used anywhere an expression is allowed — in a `SELECT` list, in a `WHERE` condition. It is therefore expected to have no side effects. The procedural subset of standard SQL writes the lending rule like this: ```sql CREATE PROCEDURE lend_book(IN p_book_id INTEGER, IN p_member_id INTEGER) LANGUAGE SQL BEGIN ATOMIC INSERT INTO loan(book_id, member_id, pickup) VALUES (p_book_id, p_member_id, CURRENT_DATE); UPDATE book SET on_shelf = 0 WHERE id = p_book_id; END; ``` Its call is one line: ```sql CALL lend_book(1, 4); ``` The late-days calculation, by contrast, is a function: it returns a value and is used in a query: ```sql CREATE FUNCTION late_days(p_pickup DATE, p_returned DATE) RETURNS INTEGER LANGUAGE SQL DETERMINISTIC RETURN CASE WHEN (COALESCE(p_returned, CURRENT_DATE) - p_pickup) - 14 > 0 THEN (COALESCE(p_returned, CURRENT_DATE) - p_pickup) - 14 ELSE 0 END; ``` These three blocks are **not executed**; they are written to show the form. The reason is that support for the procedural subset varies by engine: some offer a language close to the standard, some use their own procedural language, and some — including this course's observation environment — do not support stored procedures at all. What does not change is the distinction between `CREATE PROCEDURE` and `CREATE FUNCTION` and the `CALL` form of invocation. The `BEGIN ATOMIC` block states that the statements in the body form an indivisible unit: if one fails, none of them apply. The atomicity from the transaction control lesson becomes part of the procedure's definition here. #### A Function Defined in the Application On an engine that does not support stored procedures, the counterpart of a function is an application function registered on the connection. The code lives in the application, but it runs inside the query — the engine calls it for every row: ```bash cat > function-in-app.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const db = new DatabaseSync(':memory:'); db.exec(` CREATE TABLE loan(id INTEGER PRIMARY KEY, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,'2024-03-01','2024-03-15'),(2,1,'2024-03-04','2024-03-18'), (3,2,'2024-03-06','2024-03-25'),(4,2,'2024-03-11',NULL),(5,7,'2024-03-18','2024-03-24'); `); const DAY = 86400000; db.function('late_days', { deterministic: true }, (pickup, returned) => { const end = returned === null ? Date.parse('2024-03-31') : Date.parse(returned); const days = Math.round((end - Date.parse(pickup)) / DAY); return Math.max(0, days - 14); }); for (const s of db.prepare( `SELECT id, member_id, pickup, COALESCE(returned, '(open)') AS returned, late_days(pickup, returned) AS late FROM loan WHERE late_days(pickup, returned) > 0 ORDER BY id`).all()) { console.log(JSON.stringify(s)); } JS node function-in-app.mjs ``` ```text {"id":3,"member_id":2,"pickup":"2024-03-06","returned":"2024-03-25","late":5} {"id":4,"member_id":2,"pickup":"2024-03-11","returned":"(open)","late":6} ``` Two of the five records exceeded the fourteen-day period. The rule was written in one place and used in both the `SELECT` list and the `WHERE` condition; the same calculation did not need to be duplicated in two places. This is exactly what a stored function provides — the difference is only where the code lives. #### Determinism The word `DETERMINISTIC` in the function definition is a promise: called with the same arguments, it always returns the same result. That promise gives the planner two permissions — caching the result instead of recomputing it, and storing the function's result in an index. The second permission can be measured. The script below defines two functions; both have the same body, only one declares itself deterministic. An index is attempted on each: ```bash cat > deterministic.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const db = new DatabaseSync(':memory:'); db.exec(`CREATE TABLE loan(id INTEGER PRIMARY KEY, pickup TEXT, returned TEXT);`); db.function('fixed_duration', { deterministic: true }, (pickup, returned) => (returned === null ? -1 : 1)); db.function('variable_duration', (pickup, returned) => (returned === null ? -1 : 1)); for (const [name, fn] of [['fixed_duration', 'fixed_duration'], ['variable_duration', 'variable_duration']]) { try { db.exec(`CREATE INDEX index_${name} ON loan(${fn}(pickup, returned))`); console.log(`${name}: index created`); } catch (error) { console.log(`${name}: ${error.message}`); } } JS node deterministic.mjs ``` ```text fixed_duration: index created variable_duration: non-deterministic functions prohibited in index expressions ``` The reason is simple: an index stores a function's result. If the result can change over time, the value in the index falls out of sync with the data, and queries return the wrong answer. The engine cuts off this danger before it starts. The same reasoning explains why a non-deterministic function gets called **freshly for every row** inside a query. A function that reads the current time, a random number, or session information, if declared deterministic, turns the engine's optimizations into silent errors. Because the declaration is a promise, the responsibility falls on whoever wrote it. #### The Round-Trip Cost The most concrete benefit of server-side logic is reducing the number of round trips between the application and the engine. This cost does not depend on how much work there is: every statement means a separate request and a separate response. The script below lends two hundred books. First it sends two statements per book, then it does the same work with two set-based statements: ```bash cat > round-trip.mjs <<'JS' import { DatabaseSync } from 'node:sqlite'; const db = new DatabaseSync(':memory:'); db.exec(` CREATE TABLE book(id INTEGER PRIMARY KEY, on_shelf INT NOT NULL); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT); `); for (let i = 1; i <= 200; i += 1) db.exec(`INSERT INTO book VALUES (${i}, 1)`); let statements = 0; const run = (sql, ...arg) => { statements += 1; db.prepare(sql).run(...arg); }; statements = 0; db.exec('BEGIN'); for (let i = 1; i <= 200; i += 1) { run('INSERT INTO loan(book_id, member_id, pickup) VALUES (?, 4, ?)', i, '2024-03-11'); run('UPDATE book SET on_shelf = 0 WHERE id = ?', i); } db.exec('COMMIT'); console.log('row by row : statements sent =', statements, '| loan count =', db.prepare('SELECT COUNT(*) AS n FROM loan').get().n); db.exec('DELETE FROM loan; UPDATE book SET on_shelf = 1;'); statements = 0; db.exec('BEGIN'); run(`INSERT INTO loan(book_id, member_id, pickup) SELECT id, 4, '2024-03-11' FROM book WHERE on_shelf = 1`); run('UPDATE book SET on_shelf = 0 WHERE on_shelf = 1'); db.exec('COMMIT'); console.log('set-based : statements sent =', statements, '| loan count =', db.prepare('SELECT COUNT(*) AS n FROM loan').get().n); JS node round-trip.mjs ``` ```text row by row : statements sent = 400 | loan count = 200 set-based : statements sent = 2 | loan count = 200 ``` The same two hundred records were produced with 2 statements instead of 400. Because the engine and the application share a process here, the effect of the difference is small; in an application talking over a network, 400 statements mean 400 round trips, and the latency of each round trip alone can exceed the cost of the work itself. This is what a stored procedure earns: the loop stays on the server side, the application makes a single call. But the measurement says something else too — cutting round trips does not require a procedure. The set-based statement achieved the same gain without any stored procedure. A procedure can only be justified by this reasoning when a control flow is needed that cannot be expressed with a set-based statement. #### Comparison with a View Procedures are not the only thing put on the server side. A **view** names a query and stores it in the schema; it takes no parameters, but it collects repeated join and filter logic in one place: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch TEXT); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO member VALUES (1,'Alice','Kadikoy'),(2,'Ben','Kadikoy'),(7,'Grace','Kadikoy'); INSERT INTO loan VALUES (1,1,1,'2024-03-01','2024-03-15'),(4,7,1,'2024-03-11',NULL), (9,8,2,'2024-03-21',NULL),(23,2,7,'2024-03-11','2024-03-16'); CREATE VIEW open_loans AS SELECT l.id, m.name, l.pickup FROM loan l JOIN member m ON m.id = l.member_id WHERE l.returned IS NULL; SELECT * FROM open_loans ORDER BY id; SELECT COUNT(*) AS open_count FROM open_loans; SQL ``` ```text ┌────┬───────┬────────────┐ │ id │ name │ pickup │ ├────┼───────┼────────────┤ │ 4 │ Alice │ 2024-03-11 │ │ 9 │ Ben │ 2024-03-21 │ └────┴───────┴────────────┘ ┌────────────┐ │ open_count │ ├────────────┤ │ 2 │ └────────────┘ ``` The definition of an "open loan" stood in one place, and both queries used it. If the definition changes — say, canceled records should also be excluded — a single place gets updated. Unlike a common table expression, a view is persistent and part of the schema. Putting code on the server side has a cost too. Procedure bodies fit into version control and test suites with more friction than application code does; since every engine's procedural language differs, portability is lost; debugging tools are more limited than for the application language. The measure is drawn from the nature of the logic placed there: rules that protect **data integrity** gain from staying close to the data, workflow decisions gain from staying in the application. #### Summary - A procedure is called with `CALL` and can change data; a function returns a value and is used inside an expression. - The standard procedural subset is defined with `CREATE PROCEDURE` and `CREATE FUNCTION`; the degree of support varies by engine. - A `DETERMINISTIC` declaration grants the planner caching and indexing permission; a non-deterministic function cannot be used in an index expression. - Server-side logic reduces the round-trip count; in the measurement, 400 statements of work dropped to 2, but the same gain was reached with a set-based statement and no procedure. - A view is a parameterless server-side abstraction that keeps repeated query logic in one place in the schema. #### Next Step In this lesson, server-side code was always **called**: the procedure by `CALL`, the function by name inside a query. Because it was read from where it was called, what it did was visible. The database also defines code that runs without being called: triggers, which fire on their own when a table is written to. The next lesson covers how they are defined, what they are good for, and why code that runs without being called deserves special care. ### Triggers Source: https://academia.sh/en/courses/advanced-sql/triggers Trigger definition, running per row with BEFORE and AFTER, audit logging and updating derived state, enforcing a rule with RAISE, INSTEAD OF on a view, and the risk of recursion. In the previous lesson, server-side code was always called: the procedure by `CALL`, the function by name inside a query. Because it was read from where it was called, what it did was visible. A **trigger** is not called. When an insert, update, or delete happens on a table, the engine runs it on its own. This is a powerful tool and just as much of a trap: an ordinary looking `UPDATE` statement can write to tables that never appear in its text. #### Definition and Timing A trigger is defined by three things: which table it watches, which event it runs on, and whether it runs before or after that event. - `BEFORE`: runs before the statement processes the row. Used to correct a value or reject the operation. - `AFTER`: runs after the row has been processed. Used to write to other tables. - `INSTEAD OF`: the row is not processed; the trigger runs **in its place**. This is for views. The `FOR EACH ROW` form states that the trigger runs separately for every affected row. Two special names can be used inside the body: `NEW`, which gives the row's new state, and `OLD`, which gives its old state. `OLD` is undefined on an insert event, and `NEW` is undefined on a delete event. The first use is a pair of triggers doing two things at once: updating derived state and writing an audit record. ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT NOT NULL DEFAULT 1); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); CREATE TABLE audit(id INTEGER PRIMARY KEY, event TEXT, loan_id INT, detail TEXT); INSERT INTO book VALUES (1,'Lost Time',1),(2,'Silent House',1); CREATE TRIGGER loan_opened AFTER INSERT ON loan FOR EACH ROW BEGIN UPDATE book SET on_shelf = 0 WHERE id = NEW.book_id; INSERT INTO audit(event, loan_id, detail) VALUES ('opened', NEW.id, 'book ' || NEW.book_id || ' member ' || NEW.member_id); END; CREATE TRIGGER loan_closed AFTER UPDATE OF returned ON loan FOR EACH ROW WHEN OLD.returned IS NULL AND NEW.returned IS NOT NULL BEGIN UPDATE book SET on_shelf = 1 WHERE id = NEW.book_id; INSERT INTO audit(event, loan_id, detail) VALUES ('closed', NEW.id, 'returned ' || NEW.returned); END; INSERT INTO loan(id, book_id, member_id, pickup) VALUES (1, 1, 4, '2024-03-11'); UPDATE loan SET returned = '2024-03-20' WHERE id = 1; SELECT id, title, on_shelf FROM book ORDER BY id; SELECT id, event, loan_id, detail FROM audit ORDER BY id; SQL ``` ```text ┌────┬──────────────┬──────────┐ │ id │ title │ on_shelf │ ├────┼──────────────┼──────────┤ │ 1 │ Lost Time │ 1 │ │ 2 │ Silent House │ 1 │ └────┴──────────────┴──────────┘ ┌────┬────────┬─────────┬─────────────────────┐ │ id │ event │ loan_id │ detail │ ├────┼────────┼─────────┼─────────────────────┤ │ 1 │ opened │ 1 │ book 1 member 4 │ │ 2 │ closed │ 1 │ returned 2024-03-20 │ └────┴────────┴─────────┴─────────────────────┘ ``` Two statements were written: one `INSERT` and one `UPDATE`. Six things happened: the loan record opened, the book left the shelf, an audit row was written; then the record closed, the book returned to the shelf, a second audit row was written. The final `on_shelf` value being 1 shows that the second trigger undid the first trigger's effect. The `WHEN` clause makes the trigger run only for particular rows. The condition here isolates updates where the loan actually **closed**; an update that corrects the return date will not put the book back on the shelf a second time. The `AFTER UPDATE OF returned` form ties the trigger to a single column. Without a column list, the trigger would run on an update to any column of the table — usually an unwanted breadth. #### Enforcing a Rule `BEFORE` triggers can reject an operation. Standard SQL defines a signal statement for this; on engines its counterpart is an error-raising function. The trigger below blocks lending a book that is not on the shelf: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, on_shelf INT NOT NULL DEFAULT 1); CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO book VALUES (1,'Lost Time',0),(2,'Silent House',1); CREATE TRIGGER loan_check BEFORE INSERT ON loan FOR EACH ROW WHEN (SELECT on_shelf FROM book WHERE id = NEW.book_id) = 0 BEGIN SELECT RAISE(ABORT, 'book not on shelf'); END; INSERT INTO loan(id, book_id, member_id, pickup) VALUES (1, 2, 4, '2024-03-11'); INSERT INTO loan(id, book_id, member_id, pickup) VALUES (2, 1, 7, '2024-03-11'); SELECT id, book_id, member_id FROM loan ORDER BY id; SQL ``` ```text Runtime error near line 13: book not on shelf (19) ┌────┬─────────┬───────────┐ │ id │ book_id │ member_id │ ├────┼─────────┼───────────┤ │ 1 │ 2 │ 4 │ └────┴─────────┴───────────┘ ``` The loan for the book on the shelf went through; the one for the unavailable book was rejected with the message the trigger gave. The message text is written inside the trigger; the error reaching the application arrives by the same path as a constraint violation error. This tool does not replace constraints. If a rule can be expressed by a single column's own value, use a `CHECK` constraint; if it can be expressed by the existence of a row in another table, use a foreign key — both are declarative, known to the planner, and cheaper than a trigger. A trigger is only needed for rules that examine multiple tables together. #### On a View A complex view cannot be updated directly: the engine cannot derive how a change to a view row should be reflected in the underlying tables. An `INSTEAD OF` trigger defines that mapping by hand: ```bash sqlite3 -box -header <<'SQL' CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT); INSERT INTO loan VALUES (1,1,4,'2024-03-01',NULL),(2,3,7,'2024-03-04',NULL); CREATE VIEW open_loans AS SELECT id, book_id, member_id, pickup FROM loan WHERE returned IS NULL; CREATE TRIGGER close_open_loan INSTEAD OF DELETE ON open_loans FOR EACH ROW BEGIN UPDATE loan SET returned = '2024-03-31' WHERE id = OLD.id; END; DELETE FROM open_loans WHERE id = 1; SELECT id, pickup, COALESCE(returned,'(open)') AS returned FROM loan ORDER BY id; SQL ``` ```text ┌────┬────────────┬────────────┐ │ id │ pickup │ returned │ ├────┼────────────┼────────────┤ │ 1 │ 2024-03-01 │ 2024-03-31 │ │ 2 │ 2024-03-04 │ (open) │ └────┴────────────┴────────────┘ ``` The statement that was written was a delete; what happened is an update. The row still sits in the table, only its return date got filled in. From the view's angle it is correct — the row is no longer an "open loan" — but the statement's text does not say so. This is the clearest example of an implicit side effect. #### Recursion A trigger that updates the very table it watches can run again. Engines either block this outright or stop it with a depth limit: ```bash sqlite3 -box -header <<'SQL' PRAGMA recursive_triggers = ON; CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, counter INT NOT NULL DEFAULT 0); INSERT INTO book VALUES (1,'Lost Time',0); CREATE TRIGGER counter_increment AFTER UPDATE OF counter ON book FOR EACH ROW BEGIN UPDATE book SET counter = NEW.counter + 1 WHERE id = NEW.id; END; UPDATE book SET counter = 1 WHERE id = 1; SELECT id, counter FROM book; SQL ``` ```text Runtime error near line 11: too many levels of trigger recursion ┌────┬─────────┐ │ id │ counter │ ├────┼─────────┤ │ 1 │ 0 │ └────┴─────────┘ ``` A single `UPDATE` was written; the trigger called itself, and the chain was cut off at the recursion depth limit. Because the whole statement was rolled back, the counter stayed at zero — atomicity holds here too. Whether recursion is on or off by default varies by engine; while off, the same definition runs silently for a single pass and the problem stays invisible. This is one of the places where the behavior of a schema carried between two engines can change. #### The Cost of an Implicit Side Effect The benefit triggers provide is clear: a rule applies at all times, independent of the code that triggered it. Whichever layer of the application the change comes from, an audit row gets written whenever a loan opens. This guarantees the rule cannot be skipped. The cost is that the statement's text and its effect diverge. This has concrete consequences: - **Debugging.** The source of an unexpected row change does not appear in query logs; the triggers defined in the schema have to be read. - **Order ambiguity.** The order in which multiple triggers bound to the same event run is not defined by the standard; writing two triggers that depend on each other is fragile. - **Batch operations.** A trigger that runs per row runs a hundred thousand times on a hundred-thousand-row update; on some bulk-loading paths it may not run at all. - **Invisible cost.** The plan of a statement that looks simple also includes the queries inside the trigger body. The measure is this: a trigger fits rules that protect **data integrity** and must not be skipped — audit logging, consistency of a derived column, multi-table constraints. Workflow decisions — sending a notification, calculating a fee, calling an external system — belong in the application layer. When triggers are written, they should be kept short and documented alongside the schema. #### Summary - A trigger is not called; the engine runs it when an event occurs on the table it watches, and it reaches the row's two states through `NEW` and `OLD`. - `BEFORE` is for correcting and rejecting, `AFTER` for writing to other tables, `INSTEAD OF` for updating a view; the `WHEN` clause narrows when it runs. - Rules expressible with a single column should be declared with `CHECK` or a foreign key; a trigger is needed for multi-table rules. - A trigger that updates its own table produces recursion; the engine cuts it off with a depth limit and the whole statement is rolled back. - An implicit side effect separates a statement's text from its effect, affecting debugging, ordering assumptions, and batch-operation cost. #### Next Step Across this topic, queries focused on giving the correct result: a subquery selected the right set, a window saw the right frame, a transaction committed at the right moment. Correctness is not the only measure. The Correlated Subqueries lesson measured two forms producing the same result by visiting 200 rows against 25, with the access path making the difference; in that lesson, adding an index made the plan say `SEARCH` instead of `SCAN`. The next topic starts from that point. Its first lesson establishes what an index is and how it lowers the cost of searching; from there it moves to reading a query plan and to rewrites that give the same result for less work. ## Query Performance How an index lowers search cost, reading a query plan, syntax that disables an index, join order and algorithm choice, equivalent rewriting of subqueries, the planner's statistics source, and the effects of dynamic SQL on correctness, security, and the plan cache. ### Index Concept Source: https://academia.sh/en/courses/advanced-sql/index-concept The cost of a full table scan, what an index converts that cost into, the same query measured without and with an index, the index's cost on the space and write side, and how selectivity determines the payoff. The Transactions topic completed the discipline a database needs in order to give the correct answer: commit boundaries, isolation levels, locks, and the implicit side effects of triggers. What that topic left in hand at its end was a query that produces the correct result. This lesson does not ask the same query a second time. What it asks is: how many rows did the database look at while producing that correct result? A query that asks for a single member's records in a two-million-row table can deliver the correct answer by reading all two million rows, or in about sixty steps. The difference between the two is not in how the query is written, but in how the data is organized. #### A Measurable Data Set Performance claims do not show up on small tables: every path is fast on a table of a hundred rows. For the measurement to rise above the noise, the table has to be large enough. The following script sets up a data set built from library loan records. The rows are generated with a recursive common table expression; no external file is required. ```sql -- setup.sql — library data set CREATE TABLE branch ( branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL ); CREATE TABLE member ( member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, registration_date TEXT NOT NULL ); CREATE TABLE book ( book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL, year INTEGER NOT NULL, branch_id INTEGER NOT NULL ); CREATE TABLE loan ( loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT ); INSERT INTO branch (branch_id, name, city) VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'), (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'), (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara'); INSERT INTO member (member_id, name, city, registration_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000) SELECT n, 'Member ' || n, CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir' WHEN 3 THEN 'Bursa' ELSE 'Konya' END, date('2015-01-01', '+' || (n % 3200) || ' days') FROM counter; INSERT INTO book (book_id, title, author, year, branch_id) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000) SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8) FROM counter; INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000) SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000), date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'), CASE WHEN n % 9 = 0 THEN NULL ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END FROM counter; ``` The script is saved under the name `setup.sql` and run. Every measurement in this topic is made on this data set. ```sh rm -f library.db sqlite3 library.db < setup.sql sqlite3 library.db "SELECT 'member', count(*) FROM member UNION ALL SELECT 'book', count(*) FROM book UNION ALL SELECT 'loan', count(*) FROM loan;" ``` ``` member|120000 book|200000 loan|2000000 ``` #### The Default Cost of a Search A single member's loan records are being asked for. How does the database meet this query? A **query plan** is the tree that shows which steps a query will be executed with; it is requested from the command line with the `EXPLAIN QUERY PLAN` prefix. Two more tools are used for measurement: `.timer on` prints the elapsed time, and `.stats vmstep` prints the number of virtual machine steps the query spent. ```sh sqlite3 library.db <<'SQL' EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan WHERE member_id = 4242; .timer on .stats vmstep SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(*) FROM loan WHERE member_id = 4242; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN `--SCAN loan 17 VM-steps: 6000028 Run Time: real 0.038 user 0.029739 sys 0.008274 17 VM-steps: 6000028 Run Time: real 0.036 user 0.027952 sys 0.007465 17 VM-steps: 6000028 Run Time: real 0.035 user 0.028067 sys 0.007407 ``` The plan has a single node: `SCAN loan`. This means a **full table scan** — every row in the table is read, and the condition is tested separately for each row. Two million rows were visited in order to return seventeen rows. The two measures have to be read together. Time depends on the environment: the same query comes out differently on a faster disk or a more loaded machine, so time is read not as an absolute value but as a **ratio** against another time in the same environment. Step count, by contrast, is independent of the environment: the same data and the same plan give the same step count on every machine. The source of the six million steps is also clear — an average of three virtual machine instructions for each of the two million rows. This cost is directly proportional to table size. If the number of loans doubles, the scan doubles too: $O(n)$. This is the result from the Linear Search lesson in the Algorithms course; the only difference is that the array lives on disk. #### What an Index Is An **index** is a separate structure that keeps a column's values in sorted order and records which row each value belongs to. The table data stays in place; the index opens a second access path to that data. The library analogy applies directly: the books on the shelves are arranged in some order, but in a library with no catalog, the only way to find a given author's books is to walk every shelf. Catalog cards sit in a separate box sorted by author name, and each card carries a shelf number. A search in the card box proceeds by opening the middle of the box and deciding which direction to go. In relational databases, the counterpart to this box is most often a **B-tree**. This is the structure built in the B-Trees lesson in the Data Structures course: every node is wide enough to fit a disk page, the tree is balanced, and its height grows with the logarithm of the record count. Finding a key means descending from the root to a leaf; in an index of two million records, that means reading a handful of pages. When the table grows tenfold, the scan grows ten times more expensive, while the number of levels descended in the tree usually does not change at all: adding a level takes growth by as many times as a page holds keys — hundreds, not ten. #### The Index's Measured Effect The same query is repeated with an index on `member_id`. ```sh sqlite3 library.db <<'SQL' .timer on CREATE INDEX loan_member ON loan(member_id); .timer off EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan WHERE member_id = 4242; .timer on .stats vmstep SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(*) FROM loan WHERE member_id = 4242; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` Run Time: real 0.257 user 0.213982 sys 0.036173 QUERY PLAN `--SEARCH loan USING INDEX loan_member (member_id=?) 17 VM-steps: 62 Run Time: real 0.000 user 0.000016 sys 0.000013 17 VM-steps: 62 Run Time: real 0.000 user 0.000007 sys 0.000005 17 VM-steps: 62 Run Time: real 0.000 user 0.000006 sys 0.000005 ``` The plan node changed from `SCAN` to `SEARCH ... USING INDEX`. This is what should be read here: the database no longer reads the table from start to end; it descends the index to the `member_id = 4242` key and looks only at the rows there. Step count dropped from 6,000,028 to 62 — roughly a hundred thousand times. Time, in turn, became unmeasurable: a value of `0.000` does not mean "zero time," it means falling below the timer's resolution. This is a reminder of the first rule of measurement discipline: once a path becomes cheap enough, time stops carrying information, and what needs to be measured is the work done. Building the index is not free either; sorting two million rows took about a quarter second in this environment. #### The Index's Cost While an index makes reading cheaper, it makes two things more expensive: space and writes. The following measurement adds the same two hundred thousand rows to two copies of the same data set; one copy has no index, the other has three indexes on `loan`. ```sh rm -f noindex.db indexed.db sqlite3 noindex.db < setup.sql cp noindex.db indexed.db sqlite3 indexed.db 'CREATE INDEX l_member ON loan(member_id); CREATE INDEX l_book ON loan(book_id); CREATE INDEX l_pickup ON loan(pickup_date);' for db in noindex.db indexed.db; do printf '%s ' "$db" sqlite3 "$db" <<'SQL' .timer on INSERT INTO loan (book_id, member_id, pickup_date, return_date) WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 200000) SELECT 1 + ((n*7) % 200000), 1 + ((n*13) % 120000), date('2024-01-01','+'||(n%300)||' days'), NULL FROM s; SQL done ls -l noindex.db indexed.db | awk '{print $9, $5}' ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` noindex.db Run Time: real 0.060 user 0.056476 sys 0.003023 indexed.db Run Time: real 0.396 user 0.281373 sys 0.096411 indexed.db 191676416 noindex.db 91152384 ``` With three indexes in place, the same insert took about six and a half times longer in this environment, and the file grew to more than double its size. The reason is direct: for every row inserted, a key is written into each of the three trees, and the balance of those trees is maintained. The same cost applies to deletes and to `UPDATE` statements that change a key column. An index is therefore not the kind of option that is only nice to have — it is a deliberate trade-off between reading and writing. #### Selectivity Opening an index on every column multiplies the cost while usually not paying off. The deciding measure is **selectivity**: how small a fraction of the table a condition selects. In the `book` table, `branch_id` takes eight distinct values, while `author` takes four thousand. The following measurement runs the same query shape for both columns, without an index and then with one. ```sh rm -f selectivity.db sqlite3 selectivity.db < setup.sql echo "without index:" sqlite3 selectivity.db <<'SQL' .stats vmstep SELECT sum(year) FROM book WHERE branch_id = 3; SELECT sum(year) FROM book WHERE author = 'Author 7'; SQL sqlite3 selectivity.db 'CREATE INDEX book_branch ON book(branch_id); CREATE INDEX book_author ON book(author);' echo "with index:" sqlite3 selectivity.db <<'SQL' .stats vmstep SELECT sum(year) FROM book WHERE branch_id = 3; SELECT sum(year) FROM book WHERE author = 'Author 7'; SQL ``` ``` without index: 49674950 VM-steps: 650011 99075 VM-steps: 600111 with index: 49674950 VM-steps: 125012 99075 VM-steps: 262 ``` The author condition got roughly twenty-three hundred times cheaper; the branch condition only about five times cheaper. The split comes from selectivity: `author = 'Author 7'` selects fifty of two hundred thousand books, while `branch_id = 3` selects twenty-five thousand of them. In the second case, the database still has to fetch twenty-five thousand rows from the table after reading twenty-five thousand index entries — work that is not much cheaper than reading the table in sequence. An index opened on a column with low selectivity pays the write cost without returning it on the read side. #### Summary - A condition on a column with no index is met with a full table scan; the cost is directly proportional to row count. - An index is a separate structure that keeps column values sorted; in a B-tree-shaped index, search cost grows with the logarithm of row count. - The same query in this data set dropped from 6,000,028 steps to 62; because time fell below the timer's resolution, step count was used as the measure. - An index takes up space and makes every insert, delete, and key update more expensive; inserting into a table with three indexes took about six and a half times longer in this environment. - The payoff is determined by selectivity: an index pays off greatly on conditions that select few rows, and the payoff disappears on conditions that select a large fraction of the table. #### Next Step This lesson looked at plan output twice and distinguished two words: `SCAN` and `SEARCH`. Real queries do not have a single node — joins, sorting, grouping, and subqueries turn the plan into a multi-row tree. The next lesson takes up reading that tree: the order in which nodes run, which node drives which table, and how sorting shows up in the plan. The shape of plan output changes from engine to engine; what needs to be read is not the shape but the decision inside the plan. ### Reading Query Plans Source: https://academia.sh/en/courses/advanced-sql/reading-query-plans The structure and reading direction of the plan tree, the distinction between scan and search nodes, the covering index's trace in the plan, the order of join nodes, the sort node's measured cost, and the effect of column order in a composite index on the plan. The previous lesson looked at plan output twice and distinguished two words: `SCAN` and `SEARCH`. In a single-table, single-condition query, the plan is a single line and easy to read. Real queries are not like this. The plan for a query that joins three tables, filters, groups, and sorts is a multi-node tree, and every node in that tree carries a decision. This lesson takes up reading that tree: what the nodes say, which table drives the others, and how sorting is reflected in the plan. #### Data Set Measurements are made on the library data set from the previous lesson. The following block sets up that data set from scratch; no other file is required. ```sh rm -f library.db cat > setup.sql <<'SQL' CREATE TABLE branch ( branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL ); CREATE TABLE member ( member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, registration_date TEXT NOT NULL ); CREATE TABLE book ( book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL, year INTEGER NOT NULL, branch_id INTEGER NOT NULL ); CREATE TABLE loan ( loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT ); INSERT INTO branch (branch_id, name, city) VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'), (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'), (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara'); INSERT INTO member (member_id, name, city, registration_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000) SELECT n, 'Member ' || n, CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir' WHEN 3 THEN 'Bursa' ELSE 'Konya' END, date('2015-01-01', '+' || (n % 3200) || ' days') FROM counter; INSERT INTO book (book_id, title, author, year, branch_id) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000) SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8) FROM counter; INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000) SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000), date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'), CASE WHEN n % 9 = 0 THEN NULL ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END FROM counter; SQL sqlite3 library.db < setup.sql ``` #### A Plan Is a Tree A query asking who has borrowed a given author's books touches three tables. Its plan is three lines too. ```sh sqlite3 library.db <<'SQL' CREATE INDEX loan_member ON loan(member_id); CREATE INDEX loan_book ON loan(book_id); CREATE INDEX book_author ON book(author); EXPLAIN QUERY PLAN SELECT m.name, b.title, l.pickup_date FROM loan l JOIN member m ON m.member_id = l.member_id JOIN book b ON b.book_id = l.book_id WHERE b.author = 'Author 7'; SQL ``` ``` QUERY PLAN |--SEARCH b USING INDEX book_author (author=?) |--SEARCH l USING INDEX loan_book (book_id=?) `--SEARCH m USING INTEGER PRIMARY KEY (rowid=?) ``` Three lines are three table accesses, and their order carries meaning. The topmost node is the **driving table**: the database starts its work there. The nodes below it run once for each row coming from the driver. Here, the work starts from the `book` table, because that is where the only filter condition sits; `author = 'Author 7'` leaves fifty rows. For each of these fifty books, a `book_id` search is done inside `loan`, and for every loan record found, a single row is pulled from the `member` table by primary key. In the query text, `loan` was written first. The plan paid no attention to this: the order in the `FROM` clause is not an execution order, it is a list of names. The planner decides the access order. #### Scan and Search Nodes The first distinction among plan nodes is whether the table is read from start to end or entered from a key. `SCAN` says that every record in the table or index is read in sequence. `SEARCH` says that entry happens through a key and only the matching portion is read; the `(member_id=?)` in parentheses shows which condition was used as the key. A third distinction is the structure being searched itself: `USING INTEGER PRIMARY KEY (rowid=?)` is not a separate index but the table's own primary key. A fourth word says that the table was not touched at all. ```sh sqlite3 library.db <<'SQL' EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id = 4242; EXPLAIN QUERY PLAN SELECT count(return_date) FROM loan WHERE member_id = 4242; .stats vmstep SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(return_date) FROM loan WHERE member_id = 4242; SQL ``` ``` QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_member (member_id=?) QUERY PLAN `--SEARCH loan USING INDEX loan_member (member_id=?) 17 VM-steps: 62 17 VM-steps: 97 ``` Both queries use the same index, but the first one's plan carries the word `COVERING`. A **covering index** is an index that holds every column the query asks for within itself: `member_id` is already in the index, no other column is needed for counting, so the table is never visited. The second query asks for the `return_date` column; since that column is not in the index, every matching index entry triggers a return to the table. For seventeen rows, the difference is thirty-five steps; this difference grows in direct proportion to the number of matching rows. #### The Sort Node Some nodes correspond not to a table but to an operation performed on data. Sorting is the most expensive of these. ```sh sqlite3 library.db <<'SQL' EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5; .timer on .stats vmstep SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5; .timer off .stats off CREATE INDEX loan_pickup ON loan(pickup_date); EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5; .timer on .stats vmstep SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN |--SCAN loan `--USE TEMP B-TREE FOR ORDER BY 2437|2018-01-01 4874|2018-01-01 7311|2018-01-01 9748|2018-01-01 12185|2018-01-01 VM-steps: 12000130 Run Time: real 0.061 user 0.052669 sys 0.008248 QUERY PLAN `--SCAN loan USING COVERING INDEX loan_pickup 2437|2018-01-01 4874|2018-01-01 7311|2018-01-01 9748|2018-01-01 12185|2018-01-01 VM-steps: 32 Run Time: real 0.000 user 0.000015 sys 0.000015 ``` The `USE TEMP B-TREE FOR ORDER BY` node says that sorting is done by building a temporary structure. Asking for only five rows does not make this cheaper: finding the five smallest dates requires seeing all two million rows, because the order is not known. Once the index is created, the sort node disappears from the plan. The index is already sorted by date; the database reads five entries from the start and stops. Twelve million steps drop to thirty-two — this is the index's second function: alongside making search cheaper, it offers a **ready-made order**. Time again falls below the measurement limit; what stays stable is not the time, which depends on the environment, but the direction of the ratios. #### Column Order in a Composite Index A **composite index** is an index defined over more than one column, and it sorts its entries by the first column first, and by the second column when the first is tied. Order is not a detail; it is the decision that determines what the index is good for. The following measurement runs the same query with two different column orders. ```sh for order in "pickup_date, member_id" "member_id, pickup_date"; do rm -f order.db sqlite3 order.db < setup.sql sqlite3 order.db "CREATE INDEX loan_composite ON loan($order);" printf 'index: (%s)\n' "$order" sqlite3 order.db <<'SQL' EXPLAIN QUERY PLAN SELECT loan_id FROM loan WHERE member_id = 4242 ORDER BY pickup_date; .stats vmstep SELECT count(*) FROM (SELECT loan_id FROM loan WHERE member_id = 4242 ORDER BY pickup_date); SQL done ``` ``` index: (pickup_date, member_id) QUERY PLAN `--SCAN loan USING COVERING INDEX loan_composite 17 VM-steps: 6000101 index: (member_id, pickup_date) QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_composite (member_id=?) 17 VM-steps: 135 ``` The two indexes contain the same two columns, take up the same space, and run the same query. The difference is forty-four thousand times. The reason is the sort order: if a phone book is sorted by surname, it cannot be searched by first name. In the `(pickup_date, member_id)` index, `member_id` values are spread across dates; finding one member requires reading the entire index — the plan says this by saying `SCAN`. In the `(member_id, pickup_date)` index, all of the same member's records sit next to each other and are already in date order; the plan says `SEARCH`, and the sort node never appears. The rule is this: columns filtered by equality go at the start of the index, and columns used for a range condition or for sorting come after them. #### What Should Be Read Is the Decision, Not the Shape The output here is the shape of a single engine. In other engines, the plan comes not as a tree but as an indented list, a table, or rows carrying an estimated row count and cost per node; node names change too — names like sequential scan, index scan, hash join are other names for the same concepts. What does not change is the decisions read from the plan: was the table looked at from start to end or entered from a key, which table drove the others, was a return to the table required, and was a separate sort performed. Reading a plan's output means extracting the answers to these four questions. #### Summary - A plan is a tree; the top node is the driving table, and the nodes below it run for every row coming from the driver. The order in the `FROM` clause does not determine execution order. - `SCAN` shows reading from start to end, `SEARCH` shows entering from a key; the condition in parentheses says which column was used as the key. - The word `COVERING` reports that the query was answered from the index alone, with no return to the table at all. - The sort node is a separate cost; a suitable index removed sorting from the plan entirely, and the same query dropped from 12,000,130 steps to 32. - Column order in a composite index determines which query the index is good for; reversing the order of the same two columns pushed the same query from 135 steps up to 6,000,101. #### Next Step In every measurement in this lesson, an index existed and was used. The situation commonly seen in practice is different: an index exists, the query filters on that column, and the plan still says `SCAN`. The next lesson takes up this situation — how a function applied to the column, a left-open pattern match, or a collation mismatch disables the index, and which equivalent rewrite brings the index back. ### Syntax That Prevents Index Usage Source: https://academia.sh/en/courses/advanced-sql/syntax-that-prevents-index-usage How using a function on a column disables the index, converting date filters into a range condition, the limit of a left-open pattern match, matching the collation rule to the index, and the expression index for when the function cannot be given up. In the previous two lessons, an index existed and was used. The situation commonly seen in practice is the reverse: an index exists, the query filters exactly on that column, the plan still says `SCAN`, and time does not drop. The reason for this usually lies not in the index or the data, but in how the condition is written. An index keeps a given column's values sorted **in the form they are stored**. When the condition asks not for that value itself but for another value computed from it, the index becomes useless. This lesson takes up these forms of writing and the equivalents that give the same result. #### Data Set ```sh rm -f library.db cat > setup.sql <<'SQL' CREATE TABLE branch ( branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL ); CREATE TABLE member ( member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, registration_date TEXT NOT NULL ); CREATE TABLE book ( book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL, year INTEGER NOT NULL, branch_id INTEGER NOT NULL ); CREATE TABLE loan ( loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT ); INSERT INTO branch (branch_id, name, city) VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'), (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'), (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara'); INSERT INTO member (member_id, name, city, registration_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000) SELECT n, 'Member ' || n, CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir' WHEN 3 THEN 'Bursa' ELSE 'Konya' END, date('2015-01-01', '+' || (n % 3200) || ' days') FROM counter; INSERT INTO book (book_id, title, author, year, branch_id) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000) SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8) FROM counter; INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000) SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000), date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'), CASE WHEN n % 9 = 0 THEN NULL ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END FROM counter; SQL sqlite3 library.db < setup.sql ``` #### A Function Applied to the Column Two columns carry an index. The same two questions are asked, one applying a function to the column, the other without. ```sh sqlite3 library.db <<'SQL' CREATE INDEX book_author ON book(author); CREATE INDEX loan_member ON loan(member_id); EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE upper(author) = 'AUTHOR 7'; EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE author = 'Author 7'; EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id + 0 = 4242; EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id = 4242; .timer on .stats vmstep SELECT count(*) FROM book WHERE upper(author) = 'AUTHOR 7'; SELECT count(*) FROM book WHERE author = 'Author 7'; SELECT count(*) FROM loan WHERE member_id + 0 = 4242; SELECT count(*) FROM loan WHERE member_id = 4242; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN `--SCAN book USING COVERING INDEX book_author QUERY PLAN `--SEARCH book USING COVERING INDEX book_author (author=?) QUERY PLAN `--SCAN loan USING COVERING INDEX loan_member QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_member (member_id=?) 50 VM-steps: 800061 Run Time: real 0.012 user 0.011517 sys 0.000696 50 VM-steps: 161 Run Time: real 0.000 user 0.000011 sys 0.000007 17 VM-steps: 8000029 Run Time: real 0.029 user 0.026113 sys 0.002210 17 VM-steps: 62 Run Time: real 0.000 user 0.000017 sys 0.000013 ``` Two of the four plans are `SCAN`, two are `SEARCH`. The results are the same: fifty and seventeen. The step counts are 800,061 against 161, and 8,000,029 against 62, respectively. The reason can be said in one sentence: the index keeps `author` values sorted, not `upper(author)` values. Since the database has no sorted structure for `upper(author)`, it has to compute the function separately for every row and compare the result. The same holds for arithmetic: `member_id + 0` is not an index key. Even though `+ 0` looks like it changes nothing, it is enough to disable the index. #### The Date Form of the Same Mistake The most common form of this mistake is date filtering: when a year's records are requested, extracting the year from the date looks natural. ```sh sqlite3 library.db <<'SQL' CREATE INDEX loan_pickup ON loan(pickup_date); EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE strftime('%Y', pickup_date) = '2019'; EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE pickup_date >= '2019-01-01' AND pickup_date < '2020-01-01'; .timer on .stats vmstep SELECT count(*) FROM loan WHERE strftime('%Y', pickup_date) = '2019'; SELECT count(*) FROM loan WHERE pickup_date >= '2019-01-01' AND pickup_date < '2020-01-01'; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN `--SCAN loan USING COVERING INDEX loan_pickup QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_pickup (pickup_date>? AND pickup_date? AND title=?) 50 VM-steps: 212 Run Time: real 0.000 user 0.000015 sys 0.000011 ``` The same query, unchanged, dropped from 800,061 steps to 212. The plan showing `` in place of a key column name indicates that the index is keyed not on a column but on an expression. An expression index has two conditions. The expression must be **deterministic**: it must always produce the same value for the same row; an expression that reads the current time or a session setting cannot be indexed, because the value in the index goes stale the moment it is written. Second, the expression in the query must match the expression in the index; an `upper(author)` index is no use for a `lower(author)` condition. #### The General Shape of the Rule This lesson examined four separate forms of writing; all of them reduce to a single rule. For a condition to take advantage of an index, **the indexed column must sit on one side of the comparison with no computation applied to it.** In the literature, conditions of this shape are called a *sargable predicate*. In practice, this means bringing the condition into one of three forms: comparing the column against a constant, putting the column into a range, or moving the computation into the index's definition. The computation does not have to disappear from the query entirely — it can stay on the right side of the condition, over constant values. The condition `pickup_date >= date('2019-01-01', '-7 days')` uses the index, because the computation is done once at the start of the query and its result is a constant value. #### Summary - An index keeps a column's values sorted in the form they are stored; any function or arithmetic applied to the column makes that order unusable, and the plan becomes `SCAN`. - A `strftime` condition asking for a year's records, once converted into an equivalent half-open range condition, spent nine times fewer steps and forty times less time in this environment. - A left-open pattern match cannot take advantage of any sorted index; the solution is not to rewrite the query but to build a different index structure. - The index's sort rule and the condition's comparison rule must be the same; a difference in letter case alone can disable the index. - If a computed value must be searched for, an expression index is used; the expression must be deterministic and must match its form in the query exactly. #### Next Step All the measurements up to this point were on a single table, and the decision was a single one: index or scan. When more than one table is joined, the number of decisions grows — which table to read first, which access path to use at each step, and which method to use to match rows are chosen separately. The next lesson takes up the plan's counterpart to join order and join algorithm, and their measured effect. ### Join Optimization Source: https://academia.sh/en/courses/advanced-sql/join-optimization The cost multiplier of nested loop join, how decisive the index on the inner side is, the measured effect of join order, the loop's linear scaling with outer row count, and when hash join and merge join win out. All the measurements in the previous lessons were on a single table, and the decision was a single one: index or scan. When more than one table is joined, the number of decisions grows. The database decides three things separately: the order in which the tables are read, the path by which each table is accessed, and the method by which rows are matched. These three decisions are tied to each other, and the wrong combination costs hundreds of times more than the right one. This lesson takes up the plan's counterpart to these decisions and their measured effect. #### Data Set ```sh rm -f library.db cat > setup.sql <<'SQL' CREATE TABLE branch ( branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL ); CREATE TABLE member ( member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, registration_date TEXT NOT NULL ); CREATE TABLE book ( book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL, year INTEGER NOT NULL, branch_id INTEGER NOT NULL ); CREATE TABLE loan ( loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT ); INSERT INTO branch (branch_id, name, city) VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'), (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'), (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara'); INSERT INTO member (member_id, name, city, registration_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000) SELECT n, 'Member ' || n, CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir' WHEN 3 THEN 'Bursa' ELSE 'Konya' END, date('2015-01-01', '+' || (n % 3200) || ' days') FROM counter; INSERT INTO book (book_id, title, author, year, branch_id) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000) SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8) FROM counter; INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000) SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000), date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'), CASE WHEN n % 9 = 0 THEN NULL ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END FROM counter; SQL sqlite3 library.db < setup.sql ``` #### Nested Loop and the Inner Index The most basic join method is **nested loop join**: for every row read from the outer table, matching rows are searched for in the inner table. Its cost is given by a single product — the outer row count times the cost of one inner search. What determines the second factor is whether there is an index on the join column on the inner side. ```sh sqlite3 library.db <<'SQL' CREATE INDEX book_author ON book(author); EXPLAIN QUERY PLAN SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE b.author = 'Author 7'; .timer on .stats vmstep SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE b.author = 'Author 7'; .timer off .stats off CREATE INDEX loan_book ON loan(book_id); EXPLAIN QUERY PLAN SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE b.author = 'Author 7'; .timer on .stats vmstep SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE b.author = 'Author 7'; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN |--SCAN l `--SEARCH b USING INTEGER PRIMARY KEY (rowid=?) 500 VM-steps: 10000512 Run Time: real 0.367 user 0.327078 sys 0.039688 QUERY PLAN |--SEARCH b USING COVERING INDEX book_author (author=?) `--SEARCH l USING COVERING INDEX loan_book (book_id=?) 500 VM-steps: 1712 Run Time: real 0.000 user 0.000060 sys 0.000045 ``` In the first plan, `loan` is the driving table: two million loan records are read, for each of them `book` is visited by primary key, and only at the end does the author condition filter. The query spends ten million steps to return five hundred rows. In the second plan, the order reversed. The difference is the presence of a single index: as soon as an index exists on `loan.book_id`, starting from the `book` table becomes sensible. The author condition leaves fifty books, and for each book, loan records are searched from the index. Ten million steps dropped to 1,712. The rule that follows from this is the shortest summary of join performance: **if there is no index on the join columns, order cannot be chosen.** The number of options in front of the planner is determined by the access paths that indexes open up. #### The Measured Effect of Order To isolate the effect of order, the same query is run in reverse order while the indexes stay in place. In this engine, the `CROSS JOIN` syntax pins the join order: the table on the left becomes the outer loop. The syntax for pinning order varies by engine; here it is used as a measurement tool. ```sh sqlite3 library.db <<'SQL' EXPLAIN QUERY PLAN SELECT count(*) FROM loan l CROSS JOIN book b ON b.book_id = l.book_id WHERE b.author = 'Author 7'; .timer on .stats vmstep SELECT count(*) FROM loan l CROSS JOIN book b ON b.book_id = l.book_id WHERE b.author = 'Author 7'; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN |--SCAN l USING COVERING INDEX loan_book `--SEARCH b USING INTEGER PRIMARY KEY (rowid=?) 500 VM-steps: 10000512 Run Time: real 0.068 user 0.063411 sys 0.004218 ``` Same data, same indexes, same result: 500. Only the order changed, and step count rose from 1,712 to 10,000,512 — about fifty-eight hundred times. When the outer loop holds two million rows, it barely matters how cheap the inner search is. This output shows a second thing too. The step count is identical to the measurement from the no-index case: 10,000,512. Time, however, is about five times shorter. This is where it becomes visible that the two measures count different things: step count counts the instructions the virtual machine executes, while time also accounts for the bytes read. A scan over a covering index runs the same number of instructions as a scan over the table, but reads much less data. #### How the Loop Scales The cost of a nested loop is directly proportional to the outer row count. The following measurement grows the outer side with two different filter conditions. ```sh sqlite3 library.db <<'SQL' CREATE INDEX book_year ON book(year); .stats vmstep SELECT count(*) FROM book WHERE author = 'Author 7'; SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE b.author = 'Author 7'; SELECT count(*) FROM book WHERE year = 1990; SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE b.year = 1990; SQL ``` ``` 50 VM-steps: 161 500 VM-steps: 1712 2667 VM-steps: 8012 26670 VM-steps: 90690 ``` When the outer side grows from fifty rows to 2,667 rows (53.3 times), the join's step count grows from 1,712 to 90,690 (53.0 times). The ratio is nearly one-to-one: the loop behaves as $O(n)$ in outer row count, while the cost of the inner search stays constant. This linearity is both the strength and the limit of the nested loop. When the outer side is small, the method is unbeatable: no preparation is done, only the required rows are touched. As the outer side grows, a separate tree descent is made for every row, and the sum of those descents becomes more expensive than reading both tables from start to end once. #### Two Set-Based Methods When the outer side grows large, two set-based methods are used instead of row-by-row search. Both are part of standard relational optimization; which engine implements which one varies. **Hash join** reads the smaller side once and builds a hash table from the join column, then reads the larger side once and looks up each row's match in that table. Its cost is the sum of the two inputs, not their product. It has a condition: the comparison must be equality, and the hash table is expected to fit in memory; if it does not fit, the table is split into partitions and spilled to disk. This is the structure built in the Hash Tables lesson in the Data Structures course. **Merge join** reads both inputs sorted by the join column and matches them in a single pass by advancing two cursors together. If the inputs are already sorted — for instance, if both sides have an index on that column — there is no preparation cost and memory use is low. If they are not sorted, sorting is required first, and then the cost is determined by sorting. The choice looks at three measures: the size of the inputs, whether the join condition is equality, and whether the inputs arrive already sorted. A small outer side with an indexed inner side points to nested loop, two large tables point to hash join, and two large, already sorted inputs point to merge join. Every plan measured throughout this lesson is a nested loop; that is the join method used by this engine. Which family shows up in plan output depends on the engine, but the decision to be read is the same: which side drives, how the inner side is accessed, and whether matching is done row by row or as a set. #### Summary - The cost of a nested loop join is the product of the outer row count and the cost of one inner search; the index on the inner side determines the second factor. - When there is no index on the join column, the planner has no order to choose from; once the index was added, the same query dropped from 10,000,512 steps to 1,712. - Order alone is decisive: reversing the order while the indexes stayed in place raised the same query's step count by about fifty-eight hundred times. - The same step count does not mean the same time; a scan over a covering index ran in about a fifth of the time of a table scan at the same instruction count. - As the outer side grows, the nested loop grows linearly; past this point, set-based methods such as hash join or merge join are preferred. #### Next Step A join is not the only way to bring tables side by side. The same question can often be written with a subquery too, and the two forms can give the same result while producing very different plans — especially when the subquery depends on the outer row. The next lesson compares these forms: which subquery is evaluated once, which is evaluated per row, and which equivalent rewrite closes the gap between them. ### Subquery Reduction Source: https://academia.sh/en/courses/advanced-sql/subquery-reduction The per-row evaluation of a correlated subquery and its reduction to a single pass with a window function, the measured plans of the same question written with IN, EXISTS, and a join, the interaction between NOT IN and NULL, and the equivalence conditions for a rewrite. A join is not the only way to bring tables side by side. The same question can often be written with a subquery too; the two forms give the same result but do not produce the same plan. The source of the distinction is a single question: is the subquery evaluated once, or once for every row of the outer query? A subquery that does not depend on the outer query runs once, and its result is used. A **correlated subquery**, one that takes a value from the outer row, runs again for every row — in other words, it is a hidden loop, and its cost follows the nested loop formula from the previous lesson. #### Data Set ```sh rm -f library.db cat > setup.sql <<'SQL' CREATE TABLE branch ( branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL ); CREATE TABLE member ( member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, registration_date TEXT NOT NULL ); CREATE TABLE book ( book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL, year INTEGER NOT NULL, branch_id INTEGER NOT NULL ); CREATE TABLE loan ( loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT ); INSERT INTO branch (branch_id, name, city) VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'), (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'), (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara'); INSERT INTO member (member_id, name, city, registration_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000) SELECT n, 'Member ' || n, CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir' WHEN 3 THEN 'Bursa' ELSE 'Konya' END, date('2015-01-01', '+' || (n % 3200) || ' days') FROM counter; INSERT INTO book (book_id, title, author, year, branch_id) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000) SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8) FROM counter; INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000) SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000), date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'), CASE WHEN n % 9 = 0 THEN NULL ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END FROM counter; SQL sqlite3 library.db < setup.sql ``` #### A Correlated Subquery Is a Loop The question is: which is each member's most recent loan? The direct way to write it is to compute that member's maximum date for every loan record and compare against it. ```sh sqlite3 library.db <<'SQL' CREATE INDEX loan_member ON loan(member_id); CREATE INDEX loan_book ON loan(book_id); CREATE INDEX loan_pickup ON loan(pickup_date); EXPLAIN QUERY PLAN SELECT count(*) FROM loan l WHERE l.pickup_date = (SELECT max(l2.pickup_date) FROM loan l2 WHERE l2.member_id = l.member_id); .timer on .stats vmstep SELECT count(*) FROM loan l WHERE l.pickup_date = (SELECT max(l2.pickup_date) FROM loan l2 WHERE l2.member_id = l.member_id); .timer off .stats off EXPLAIN QUERY PLAN SELECT count(*) FROM (SELECT pickup_date, max(pickup_date) OVER (PARTITION BY member_id) AS last_pickup FROM loan) WHERE pickup_date = last_pickup; .timer on .stats vmstep SELECT count(*) FROM (SELECT pickup_date, max(pickup_date) OVER (PARTITION BY member_id) AS last_pickup FROM loan) WHERE pickup_date = last_pickup; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN |--SCAN l `--CORRELATED SCALAR SUBQUERY 1 `--SEARCH l2 USING INDEX loan_member (member_id=?) 120000 VM-steps: 232279993 Run Time: real 7.486 user 6.674963 sys 0.810437 QUERY PLAN |--CO-ROUTINE (subquery-1) | |--CO-ROUTINE (subquery-3) | | `--SCAN loan USING INDEX loan_member | `--SCAN (subquery-3) `--SCAN (subquery-1) 120000 VM-steps: 73200032 Run Time: real 1.009 user 0.987930 sys 0.020616 ``` In the first plan, the `CORRELATED SCALAR SUBQUERY` node says that the subquery depends on the outer row. There are two million rows on the outer side; for each of them, all of that member's records are looked at to find the maximum date. The presence of the index lowers the inner cost but does not remove the loop: two hundred and thirty-two million steps. The second form does the same computation with a **window function**. This construct, introduced in the Compound Queries topic, attaches its partition's aggregate value to every row. The nodes in the plan describe a single pass: the index is read in `member_id` order, and because the same member's rows are already adjacent, the partition's maximum is determined in one pass. Step count dropped to about a third, and time dropped to roughly a seventh in this environment. The result is the same in both forms: 120,000. The source of the gain is not a better index but not repeating the same work. #### Three Forms of the Same Question The question "how many books were borrowed at least once in 2024?" can be written in three separate forms. All three give the same number. ```sh sqlite3 library.db <<'SQL' EXPLAIN QUERY PLAN SELECT count(*) FROM book b WHERE b.book_id IN (SELECT l.book_id FROM loan l WHERE l.pickup_date >= '2024-01-01'); EXPLAIN QUERY PLAN SELECT count(*) FROM book b WHERE EXISTS (SELECT 1 FROM loan l WHERE l.book_id = b.book_id AND l.pickup_date >= '2024-01-01'); EXPLAIN QUERY PLAN SELECT count(DISTINCT b.book_id) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE l.pickup_date >= '2024-01-01'; .timer on .stats vmstep SELECT count(*) FROM book b WHERE b.book_id IN (SELECT l.book_id FROM loan l WHERE l.pickup_date >= '2024-01-01'); SELECT count(*) FROM book b WHERE EXISTS (SELECT 1 FROM loan l WHERE l.book_id = b.book_id AND l.pickup_date >= '2024-01-01'); SELECT count(DISTINCT b.book_id) FROM book b JOIN loan l ON l.book_id = b.book_id WHERE l.pickup_date >= '2024-01-01'; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN |--SEARCH b USING INTEGER PRIMARY KEY (rowid=?) `--LIST SUBQUERY 1 `--SEARCH l USING INDEX loan_pickup (pickup_date>?) QUERY PLAN |--SCAN b `--CORRELATED SCALAR SUBQUERY 1 `--SEARCH l USING INDEX loan_book (book_id=?) QUERY PLAN |--USE TEMP B-TREE FOR count(DISTINCT) |--SEARCH l USING INDEX loan_pickup (pickup_date>?) `--SEARCH b USING INTEGER PRIMARY KEY (rowid=?) 105374 VM-steps: 1536319 Run Time: real 0.261 user 0.148644 sys 0.112857 105374 VM-steps: 9251955 Run Time: real 0.375 user 0.358855 sys 0.016175 105374 VM-steps: 1527452 Run Time: real 0.445 user 0.241398 sys 0.202772 ``` Three forms, three separate plans. The `IN` form produces the subquery as a list and filters the outer side against that list. The `EXISTS` form is correlated: it searches inside `loan` for each of two hundred thousand books, and its step count is about six times higher. The join form spends the fewest steps, but because it builds a temporary structure for `DISTINCT`, it takes the longest time in this environment. The conclusion to draw is not that one form is superior to another. The three measurements give three separate rankings, and step count and time do not point to the same winner. The `EXISTS` form pulls ahead when the searched condition is highly selective and it can stop at the first match; the `IN` form when the subquery's result is small; the join form when both sides are large and duplication is not a problem. The decision is made by measurement. The join form also has a side effect: if a book had more than one loan in 2024, the join produces that book as more than one row. The `count(DISTINCT ...)` form is therefore mandatory — equivalence breaks not in the count of the result, but in row multiplicity. #### NOT IN and NULL Whether a rewrite is equivalent is not always as clear as it looks. The difference between `NOT IN` and `NOT EXISTS` is the sharpest example of this. ```sh sqlite3 library.db <<'SQL' SELECT count(*) FROM book WHERE book_id NOT IN (SELECT 1 UNION ALL SELECT 2); SELECT count(*) FROM book WHERE book_id NOT IN (SELECT 1 UNION ALL SELECT NULL); SELECT count(*) FROM book b WHERE NOT EXISTS (SELECT 1 FROM (SELECT 1 AS v UNION ALL SELECT NULL) t WHERE t.v = b.book_id); SELECT count(*) FROM loan WHERE return_date IS NULL; SQL ``` ``` 199998 0 199999 222222 ``` The second query returns zero. The reason is three-valued logic: the expression `book_id NOT IN (1, NULL)` means `book_id <> 1 AND book_id <> NULL`; the second comparison is never true, it stays unknown. A row whose condition is unknown cannot pass the filter, so the result set becomes empty. `NOT EXISTS` does not fall into the same trap: it searches for a match, and if it does not find one, it lets the row through. The third query returns 199,999 — the expected number. This is not an academic detail. The fourth query shows that more than two hundred and twenty-two thousand records in the `loan` table have a `return_date` field that is empty. A `NOT IN` subquery built over this column silently produces an empty result; the query does not fail, it only gives the wrong answer. The `NOT EXISTS` form is both independent of this behavior and better optimized by most planners. #### The Rule for Rewriting This lesson compared four pairs of forms. The shared method has three steps. The first step is to see whether the subquery depends on the outer row. If it does, a marker saying so appears in the plan node, and the cost is multiplied by the outer row count. The second step is to look for a structure that reduces per-row work to a single pass: a window function, grouping, a common table expression, or a join. The third step is to check that the rewrite is truly equivalent — NULL behavior, row multiplicity, and empty-result cases are the three separate items of this check. The most reliable form of an equivalence check is to run both forms and compare the results. In this lesson, every comparison showed both forms returning the same number; this is not a confirmation, it is a precondition for the rewrite. #### Summary - A subquery that depends on the outer row is re-evaluated for every row; its cost follows the nested loop formula and it appears in the plan with a node that marks it as correlated. - A per-row aggregation, once reduced to a single pass with a window function, dropped from 232,279,993 steps to 73,200,032 in this data set. - When the same question was written with `IN`, `EXISTS`, and a join, three separate plans came out; step count and time did not point to the same form, so the decision is made by measurement. - A subquery converted into a join can change row multiplicity; equivalence requires `DISTINCT` or grouping. - If the subquery's result contains a single NULL, `NOT IN` returns an empty set; `NOT EXISTS` is unaffected by this behavior. #### Next Step Up to this point, every decision the planner made turned out to be the right one: it drove the correct table, it chose the correct index. What it based those decisions on has not been asked yet. The planner does not read the data at query time; it looks at statistics collected beforehand about tables and indexes, and it **estimates** how many rows each step will return. The next lesson takes up the source of that estimate, how its accuracy is measured, and how the plan changes when the estimate goes wrong. ### Statistics and Cardinality Source: https://academia.sh/en/courses/advanced-sql/statistics-and-cardinality The planner's row count estimate, the default values used before statistics are collected, the estimate's correction after ANALYZE, the estimate's measured effect on the plan, the consequences of stale statistics, and the average's failure to describe a skewed distribution. In the previous lessons, the planner's decisions always turned out to be the right ones: it drove the correct table, it chose the correct index, it avoided unnecessary sorting. What it based those decisions on has not been asked. The planner decides before the query runs. It has no data in hand; if it did, it would already have run the query itself. Instead, it **estimates** how many rows each step will return and compares options based on these estimates. The source of the estimate is statistics collected beforehand about tables and indexes. This lesson makes that estimate visible, measures it, and shows what happens when it goes wrong. #### Data Set ```sh rm -f library.db cat > setup.sql <<'SQL' CREATE TABLE branch ( branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL ); CREATE TABLE member ( member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, registration_date TEXT NOT NULL ); CREATE TABLE book ( book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL, year INTEGER NOT NULL, branch_id INTEGER NOT NULL ); CREATE TABLE loan ( loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT ); INSERT INTO branch (branch_id, name, city) VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'), (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'), (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara'); INSERT INTO member (member_id, name, city, registration_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000) SELECT n, 'Member ' || n, CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir' WHEN 3 THEN 'Bursa' ELSE 'Konya' END, date('2015-01-01', '+' || (n % 3200) || ' days') FROM counter; INSERT INTO book (book_id, title, author, year, branch_id) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000) SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8) FROM counter; INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000) SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000), date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'), CASE WHEN n % 9 = 0 THEN NULL ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END FROM counter; SQL sqlite3 library.db < setup.sql ``` #### The Estimate Can Be Made Visible The `.scanstats est` command adds four numbers next to plan nodes: how many times the node ran (`loops`), how many rows it produced in total (`rows`), rows per run (`rpl`), and what the planner **estimated** this would be (`est`). `.scanstats` is not present in every `sqlite3` build; in a build that does not support the command, these fields do not appear in the output. {/* run: skip */} ```sh sqlite3 library.db <<'SQL' CREATE INDEX loan_member ON loan(member_id); CREATE INDEX book_author ON book(author); .scanstats est SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(*) FROM book WHERE author = 'Author 7'; SQL ``` ``` 17 QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_member (member_id=?) (loops=1 rows=17 rpl=17.0 est=10.0) 50 QUERY PLAN `--SEARCH book USING COVERING INDEX book_author (author=?) (loops=1 rows=50 rpl=50.0 est=10.0) ``` The estimate is the same in both nodes: ten. The two indexes have different densities, the tables are different sizes, and the actual counts are seventeen and fifty. The estimate being ten in both cases shows that this is not a computation but a **default value**: for an index with no collected statistics, the planner assumes an equality condition will return a fixed number of rows. This assumption is harmless when the options are close to each other. If one option is a hundred times more expensive than another, and the difference comes from exactly this number, the wrong plan gets chosen. #### Collecting Statistics `ANALYZE` scans the tables and indexes and writes summary information into a system table. {/* run: skip */} ```sh sqlite3 library.db <<'SQL' ANALYZE; SELECT tbl, idx, stat FROM sqlite_stat1 ORDER BY tbl, idx; .scanstats est SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(*) FROM book WHERE author = 'Author 7'; SQL ``` ``` book|book_author|200000 50 branch||8 loan|loan_member|2000000 17 member||120000 17 QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_member (member_id=?) (loops=1 rows=17 rpl=17.0 est=16.0) 50 QUERY PLAN `--SEARCH book USING COVERING INDEX book_author (author=?) (loops=1 rows=50 rpl=50.0 est=48.0) ``` Every row in the statistics table carries two numbers: the table's row count and the average number of rows per index key. `loan_member` reading `2000000 17` says that there are two million loan records and that a member has an average of seventeen records. This number is called a **cardinality estimate**. The estimates rose to sixteen and forty-eight instead of ten; the actual values are seventeen and fifty. The planner can now tell the two indexes apart. #### The Estimate's Effect on the Plan Correcting the estimate is not just a matter of one number improving; the plan changes too. ```sh rm -f plan.db sqlite3 plan.db < setup.sql sqlite3 plan.db <<'SQL' CREATE INDEX book_branch ON book(branch_id); EXPLAIN QUERY PLAN SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3; .timer on .stats vmstep SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3; .timer off .stats off ANALYZE; EXPLAIN QUERY PLAN SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3; .timer on .stats vmstep SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3; SQL ``` {/* mask: (?<=Run Time: real )[0-9.]+ */} {/* mask: (?<=user )[0-9.]+(?= sys) */} {/* mask: (?<=sys )[0-9.]+ */} ``` QUERY PLAN |--SCAN l `--SEARCH b USING COVERING INDEX book_branch (branch_id=? AND rowid=?) 250000 VM-steps: 10250011 Run Time: real 0.357 user 0.347190 sys 0.010091 QUERY PLAN |--SCAN l |--BLOOM FILTER ON b (branch_id=? AND rowid=?) `--SEARCH b USING INDEX book_branch (branch_id=? AND rowid=?) 250000 VM-steps: 13425016 Run Time: real 0.105 user 0.094947 sys 0.009198 ``` The query, the indexes, and the data are the same; the only thing that changed is the presence of statistics. A new node was added to the plan: the fact that most of the two million loan records do not belong to the searched branch is now weeded out with a cheap filter beforehand, and the tree descent is done only for what remains. Time dropped by about three and a half times in this environment. Step count, however, rose: from 10,250,011 to 13,425,016. This is where the two measures diverge. The filter itself also runs instructions; what it saves is not instructions but tree descents and page reads. This is the limit of treating step count as the only measure — step count counts the work the plan does, not the unit cost of that work. #### When Statistics Go Stale Statistics describe the data as it was at the moment they were collected. As the data changes, what they describe drifts away from reality. {/* run: skip */} ```sh rm -f stale.db sqlite3 stale.db < setup.sql sqlite3 stale.db <<'SQL' CREATE INDEX loan_member ON loan(member_id); ANALYZE; INSERT INTO loan (book_id, member_id, pickup_date, return_date) WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 500000) SELECT 1 + ((n * 7) % 200000), 4242, date('2025-01-01', '+' || (n % 200) || ' days'), NULL FROM s; SELECT tbl, idx, stat FROM sqlite_stat1 WHERE idx = 'loan_member'; .scanstats est SELECT count(*) FROM loan WHERE member_id = 4242; .scanstats off ANALYZE; SELECT tbl, idx, stat FROM sqlite_stat1 WHERE idx = 'loan_member'; .scanstats est SELECT count(*) FROM loan WHERE member_id = 4242; SELECT count(*) FROM loan WHERE member_id = 5000; SQL ``` ``` loan|loan_member|2000000 17 500017 QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_member (member_id=?) (loops=1 rows=500017 rpl=500017.0 est=16.0) loan|loan_member|2500000 21 500017 QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_member (member_id=?) (loops=1 rows=500017 rpl=500017.0 est=20.0) 16 QUERY PLAN `--SEARCH loan USING COVERING INDEX loan_member (member_id=?) (loops=1 rows=16 rpl=16.0 est=20.0) ``` A contrived situation has been set up: five hundred thousand records were added for a single member. Because the statistics were collected before the insert, they still say `2000000 17` and the estimate stays at sixteen; the actual number is 500,017. The estimate is off by more than thirty thousand times. When `ANALYZE` runs again, the statistics become `2500000 21`. The estimate rises from sixteen to twenty — still not even close to 500,017. This is not a bug, it is the definition of the measure: the stored number is an **average**, and when two and a half million records are divided across one hundred and twenty thousand members, the average really does come out to twenty-one. #### What the Average Cannot Describe The last line of the last output completes the distinction: for member number 5000, the actual value is sixteen, the estimate is twenty. The average works perfectly well for ordinary members; it is only completely wrong for the outlier member. In a skewed distribution, a single average cannot serve two groups at once. The answer to this is to keep statistics per value: a list of the most frequent values and the distribution of value ranges — in other words, a **histogram**. Some engines collect this information and produce separate estimates for `member_id = 4242` and `member_id = 5000`. In engines that do not, the only remedy is to manage the skew through query writing or partial indexes. The second limit is dependency between columns. The planner mostly treats conditions like `city = 'Bursa'` and `registration_date >= '2020-01-01'` as independent and multiplies their selectivities. If the conditions are actually dependent, the result inflates or shrinks significantly. The lesson to draw on the practical side is short: statistics collection should be repeated after data volume changes substantially — after bulk loads, archiving, and schema changes. When a query slows down for no apparent reason, one of the first places to look is the gap between the estimate and the actual value. #### Summary - The planner bases its decisions on estimates of how many rows each step will return; these estimates can be seen side by side with actual counts in plan output. - Before statistics are collected, the estimate is a fixed default value; it came out as ten for two separate indexes in this data set. - `ANALYZE` writes table row count and average rows per key into a system table; estimates moved closer to actual values afterward. - The presence of statistics changed the plan and cut time by about three and a half times in this environment; because step count rose on the same query, the two measures did not point in the same direction. - The stored number is an average; in skewed distributions, the estimate can be off by thousands of times for outlier values, which is why some engines keep a histogram per value. #### Next Step Every query in this topic so far has been a fixed piece of text. Applications, however, often build queries at run time: conditions get added depending on the fields filled in a search screen, the sort column comes from the user. Building the query text by string concatenation has consequences on the correctness side, the security side, and the performance side. The final lesson takes up these three consequences and the answer a bound parameter gives to all of them at once. ### Dynamic SQL Risks Source: https://academia.sh/en/courses/advanced-sql/dynamic-sql-risks The correctness and security consequences of building query text by string concatenation, how a bound parameter processes the same input correctly, measuring parse and plan cost, the condition under which the plan cache works, and the safe construction of queries with variable shape. Every query in this topic has been fixed text. Applications, however, often build queries at run time: conditions get added depending on the fields filled in on a search screen, the sort column comes from the user, and the page number changes with every request. Building the query text by concatenating it with user input looks, at first glance, like nothing more than a writing convenience. It has three separate consequences: the query breaks on ordinary input, it opens the door for the input to change the meaning of the query, and it makes the planner's work repeat on every call. This lesson takes up all three. #### Data Set ```sh rm -f library.db cat > setup.sql <<'SQL' CREATE TABLE branch ( branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL ); CREATE TABLE member ( member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, registration_date TEXT NOT NULL ); CREATE TABLE book ( book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL, year INTEGER NOT NULL, branch_id INTEGER NOT NULL ); CREATE TABLE loan ( loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT ); INSERT INTO branch (branch_id, name, city) VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'), (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'), (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara'); INSERT INTO member (member_id, name, city, registration_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000) SELECT n, 'Member ' || n, CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir' WHEN 3 THEN 'Bursa' ELSE 'Konya' END, date('2015-01-01', '+' || (n % 3200) || ' days') FROM counter; INSERT INTO book (book_id, title, author, year, branch_id) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000) SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8) FROM counter; INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date) WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000) SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000), date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'), CASE WHEN n % 9 = 0 THEN NULL ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END FROM counter; SQL sqlite3 library.db < setup.sql ``` #### Input That Mixes Into the Text Consider a screen that searches the library catalog by title. The input is placed into the query text between quotes. A book whose title contains an apostrophe has been added to the catalog. ```sh sqlite3 library.db "INSERT INTO book VALUES (200001, 'Moon''s Daughter', 'Author 7', 1998, 3);" wanted="Book 4242" sqlite3 library.db "SELECT book_id, title FROM book WHERE title = '$wanted';" wanted="Moon's Daughter" echo "--- same query, with a title containing a quote ---" sqlite3 library.db "SELECT book_id, title FROM book WHERE title = '$wanted';" echo "exit code: $?" ``` ``` 4242|Book 4242 --- same query, with a title containing a quote --- Error: in prepare, near "s": syntax error LECT book_id, title FROM book WHERE title = 'Moon's Daughter'; error here ---^ exit code: 1 ``` The first search works. The second, with completely harmless input — an apostrophe found in a book title — produces a syntax error. The error message shows the reason clearly: the apostrophe in the input was read as the quote closing the string, and the rest of the query broke. The source of the break is not that a quote character is special. The source is this: **the input reached the database not as data, but as a part of the query text.** The database parses the text that reaches it as a program, and it has no information within that text to distinguish where the input ends and the program begins. The same mechanism is also the definition of the security vulnerability. If the input is part of the query text, a suitably crafted input can change the meaning of the query: a condition can be made always true, the scope of the query can be widened, a table that was never meant to be reached can be accessed. This is called **SQL injection**, and its source is not that the input contains special characters, but that the text is built by concatenating it with the input. This is why the solution is not to sanitize characters either: escape lists stay incomplete, encoding differences bypass the list, and every new context demands a new list. The solution is for the input to never mix into the text at all. #### Bound Parameter A **bound parameter** places a placeholder in the query text where the value should sit; the value is sent through a channel separate from the query. The database first parses and plans the text, then places the value into that plan. ```sh wanted="Moon's Daughter" sqlite3 library.db < simple.sql : > complex.sql while [ "$i" -le 20000 ]; do printf 'SELECT 1;\n' >> simple.sql printf "SELECT s.name, count(*) FROM loan l JOIN book b ON b.book_id = l.book_id JOIN member m ON m.member_id = l.member_id JOIN branch s ON s.branch_id = b.branch_id WHERE b.author = 'None %s' AND m.city = 'Bursa' GROUP BY s.name ORDER BY 2 DESC;\n" "$i" >> complex.sql i=$((i + 1)) done printf 'simple : '; { time sqlite3 library.db < simple.sql > /dev/null ; } 2>&1 | tr '\n' ' '; echo printf 'complex : '; { time sqlite3 library.db < complex.sql > /dev/null ; } 2>&1 | tr '\n' ' '; echo ``` {/* mask: [0-9]+m[0-9.]+s */} ``` simple : real 0m0.023s user 0m0.014s sys 0m0.008s complex : real 0m0.211s user 0m0.156s sys 0m0.054s ``` Both files contain twenty thousand statements. The queries in the complex file return no rows at all: the author condition matches no record, and execution is close to zero thanks to the index. The difference — about 0.19 seconds in this environment, around ten microseconds per statement — is the parsing and planning of the four-table join. The times depend on the environment; what matters is that planning has a measurable cost. Databases pay this cost with a **plan cache**: the compiled plan is stored, and when the same query comes in again, it is not planned again. The cache's key is the query text. When a bound parameter is used, the text is identical on every call, and the cache hits. In a query built by string concatenation, on the other hand, every different value produces a different text: the cache never hits, and it fills up with single-use entries, evicting plans that would otherwise be useful. A bound parameter has a trade-off too. The plan is chosen jointly for all values, not for a single one; on a skewed column, the same plan is used for both a frequent value and a rare one. This is the same discussion as the average from the previous lesson. Some engines look at the values of the first few calls and apply methods that address this. #### Queries With Variable Shape Values can be passed with a bound parameter; column and table names cannot, because they belong to the structure of the query. If the sort column comes from the user, what needs to be done is to validate the incoming name against a fixed list and put only the name from that list into the text. ```sh column_input="year" wanted="Moon's Daughter" case "$column_input" in title|author|year) column="$column_input" ;; *) echo "invalid sort column"; exit 1 ;; esac sqlite3 library.db <