Skip to content
POLARISAI ACADEMY
R03-201 · Navigator

Databases, Caching and Data Durability

You can commit a transfer of 30 so both balances change together, name which isolation level still returns a dirty read, count the pages a composite index touches for 250 matching rows, and replace an N+1 loop of 101 queries with 2.

Level
Navigator
Time
24 h (estimate)
Prerequisites
R03-101, R02-201
Course 2 of 4
Jump to

After this course you can

The student can index and cache a slow 100,000-row database so p95 query time drops below target thresholds and execute an automated point-in-time backup restoration script that verifies 100% row integrity.

One transfer and the four ACID checks

The request that reached the database is now two writes that belong in one story. A transaction is the bracket around those writes. This lesson keeps two accounts. Account 7 starts at 80 and account 8 starts at 20, so the sum is 100. A transfer of 30 subtracts 30 from account 7 and adds 30 to account 8. After both writes the balances are 50 and 50, and 50 + 50 is still 100. Atomicity means the debit and the credit commit together or roll back together. If the process stops after account 7 has been written as 50 inside the still-open transaction, and before commit, rollback restores 80 and 20. The half-written pair 50 and 20 sums to 70, and that pair is the state atomicity clears away.

Consistency in this lesson is a rule you can check with ordinary arithmetic. A transfer is legal only when the source balance is at least the amount. 80 is at least 30, so the transfer of 30 is legal. 80 is below 90, so a transfer of 90 is refused before either balance changes, and the two balances stay 80 and 20 with the sum still 100. Isolation means a second transaction reads balances that follow the level you set, and the next section counts what each level still lets through. Durability means a commit that has already returned survives a crash. After the transfer of 30 has committed, a crash still leaves account 7 at 50 and account 8 at 50. A crash that arrives while the transaction is still open leaves 80 and 20.

Four isolation levels on one stock row

The SQL standard names four isolation levels: read uncommitted, read committed, repeatable read, and serializable. You can tell them apart with one stock row and one count of open orders. The stock row starts at 5. A second transaction sets that stock to 0 and has not committed. At read uncommitted the first transaction can read that 0. The second transaction then rolls back, and the stored stock is 5 again. The 0 was a dirty read: a read of a write that never committed. At read committed the same read returns 5, because the write to 0 is still open. Read committed blocks that dirty read. Read uncommitted is the only level of the four that still returns the uncommitted 0.

A non-repeatable read uses data that did commit. The first transaction, running at read committed, reads stock 5. The second transaction sets stock to 2 and commits. The first transaction reads the same row again and now gets 2. Two reads of one row inside one transaction returned 5 and then 2. At repeatable read the second read of that same row stays 5 until the first transaction ends. A phantom is a new row in a range you already counted. Open orders start as two rows, ids 7 and 8. The first transaction at repeatable read counts open orders and gets 2. The second transaction inserts order 9 with status open and commits. In the SQL standard, repeatable read still allows the next count in the first transaction to return 3. Serializable keeps that second count at 2. You write these four results down, then you pick the level that matches the count you need to keep stable.

Pages in a composite B-tree

The orders table in this lesson holds 100,000 rows. The composite index idx_cust_created is a B-tree on (customer_id, created_at), in that column order. Each leaf page holds 100 index entries, so the leaf level is 100,000 / 100 = 1,000 pages. The fanout is 100, meaning one internal page points at 100 children. Those 1,000 leaves hang under 1,000 / 100 = 10 internal pages, and one root page points at those 10. A point lookup descends the root, then one internal page, then one leaf. That is 3 pages. A pass with no usable index reads all 100,000 rows. The page sizes here are the lesson's model, chosen so the division comes out even, and a real file uses whatever page size that engine was built with.

The tree can seek only from the left column. WHERE customer_id = 42 can seek. WHERE customer_id = 42 AND created_at falls inside a range can seek on customer_id and then walk forward along created_at. WHERE created_at falls inside a range and customer_id is absent from the predicate cannot seek in this index. The plan line for that date-only query is a scan of all 100,000 rows. Now take the range that does seek. Customer 42 has 250 matching entries, packed 100, then 100, then 50, and the first of those keys is the first entry on its leaf. Those keys fill 3 leaf pages. The descent still costs the root and one internal page, because one internal page can parent all 3 of those leaves, and the leaf walk costs 3. The range reads 2 + 3 = 5 pages. Finding the same 250 rows by scanning the table would read all 100,000 rows.

The plan line and the N+1 count

EXPLAIN QUERY PLAN prints the strategy for one statement. The shell in this lesson shows one detail line per table it reads, in the form documented for current SQLite. A missing seek on orders shows SCAN orders, the pass over all 100,000 rows. The indexed range, selecting the amount column so the index is not covering, shows SEARCH orders USING INDEX idx_cust_created (customer_id=? AND created_at>?). That line is the 5-page read from the hand model above. The plan names the index and the WHERE terms it uses. It does not print the page count. You read SCAN or SEARCH from the plan, then you multiply pages only from the stated leaf size of 100 and the stated fanout of 100.

N+1 is a loop that shows up in the query count. One query loads the orders for customer 42. A second query, sent once per order, loads the items for that order. Three orders, ids 101, 102 and 103, cost 1 + 3 = 4 queries. One hundred orders cost 1 + 100 = 101 queries. The batched form loads the orders, then loads every item with one query whose IN list holds exactly those order ids, so the total is 2 queries. This lesson prices one query at 2 milliseconds of round trip, the wait for that one statement to go out and the rows to come back. The loop of 101 queries costs 101 × 2 = 202 milliseconds. The batched pair costs 2 × 2 = 4 milliseconds. The gap is 202 − 4 = 198 milliseconds. Both versions return the same item rows when the IN list is exactly the ids from the first query.

An example

Thirty units, five pages, 101 queries

Start with account 7 at 80 and account 8 at 20. The sum is 100. Open a transaction and apply a transfer of 30. Write account 7 as 80 − 30 = 50. Write account 8 as 20 + 30 = 50. Check 50 + 50 = 100, then commit. A crash after that commit returns still shows 50 and 50. Replay the same start and stop the process after the debit has been written and before commit. Rollback runs because the transaction was open, and the balances read 80 and 20 again. A transfer of 90 from the same start fails the rule 80 >= 90, so neither balance changes. The refused pair is still 80 and 20.

Stock starts at 5, and open orders are the two rows 7 and 8. Transaction T2 sets stock to 0 and stays open. Transaction T1 at read uncommitted reads 0. T2 rolls back, and stock is 5. The same read at read committed returns 5 while T2 is still open. Next, T1 at read committed reads stock 5, T2 sets stock to 2 and commits, and T1 reads that row again and gets 2. The same second read at repeatable read stays 5. T1 at repeatable read counts open orders and gets 2. T2 inserts order 9 with status open and commits. In the SQL standard the next count at repeatable read can return 3, and the next count at serializable stays 2.

The orders table has 100,000 rows and the index idx_cust_created on (customer_id, created_at). Leaf capacity is 100, so there are 1,000 leaf pages. Fanout is 100, so there are 10 internal pages and 1 root. A point lookup on customer_id = 42 touches 3 pages. The January range for that customer holds 250 entries, packed 100, 100 and 50 from the start of a leaf, so it touches 3 leaf pages plus the root and one internal page, which is 5 pages. The predicate that names only created_at cannot seek this index. Its plan line is SCAN orders, and that scan reads 100,000 rows. The range that names customer_id = 42 and a lower bound on created_at, while also selecting amount, has the plan line SEARCH orders USING INDEX idx_cust_created (customer_id=? AND created_at>?).

Customer 42 has 100 orders in that range. Loading the orders is 1 query. Loading items once per order is 100 more queries. The sum is 101 queries. At 2 milliseconds a query, the loop costs 202 milliseconds. Loading the orders and then loading items with one IN list costs 2 queries and 2 × 2 = 4 milliseconds. For a smaller bag of three orders, ids 101, 102 and 103, the per-order loop costs 1 + 3 = 4 queries, and the IN-list form still costs 2. The rows that come back match when every id in the IN list is an id the first query returned, and no extra id is added.

Exercise

Run a second transfer on paper

Use the same two accounts, 7 at 80 and 8 at 20. Transfer 25 and commit. Write both balances, and write both balances again for a crash that lands after the debit is written and before commit. Write the sum of that half-written pair. Stock starts at 9. A second transaction has set stock to 1 and has not committed. Write what the first transaction reads at read uncommitted, what it reads at read committed, and what stock is after the second transaction rolls back. Then the first transaction at read committed has already read 9, and the second commits stock = 4. Write the second read at read committed, and write the second read at repeatable read. Open orders start at 4 rows. After another transaction commits one new open order, write what the SQL standard allows the next count to be at repeatable read, and what serializable keeps. On the same B-tree, 100 entries per leaf and fanout 100, write the leaf-page count and the pages a point lookup touches. A range of 160 keys is packed 100 then 60, with the first key at the start of a leaf. Write the page count for that range. Finally, 40 orders each load items with their own query, plus the one orders query, at 2 milliseconds a query. Write the query count and the milliseconds for that loop, then the query count and the milliseconds for the IN-list form.

The committed transfer of 25 leaves 55 and 45. The crash before commit leaves 80 and 20. The half-written pair is 55 and 20, and 55 + 20 = 75. Read uncommitted returns 1, read committed returns 9, and rollback leaves stock at 9. The second read at read committed is 4, and the second read at repeatable read stays 9. The SQL standard allows the next open-order count at repeatable read to be 5, and serializable keeps 4. The tree still has 1,000 leaf pages, and a point lookup touches 3 pages. The range of 160 keys touches 2 leaf pages plus the root and one internal page, which is 4 pages. Forty orders make 1 + 40 = 41 queries and 41 × 2 = 82 milliseconds. The IN-list form makes 2 queries and 4 milliseconds.

Check questions

Answer on your own first. Then open a question to see the answer.

Account 7 starts at 80 and account 8 starts at 20. After a committed transfer of 30, what are the two balances, and what are they if the crash comes before commit?

After commit the balances are 50 and 50. If the crash comes before commit, rollback leaves 80 and 20.

Stock starts at 5. A second transaction has written 0 and has not committed. What does a read uncommitted read return, and what does a read committed read return?

Read uncommitted returns 0. Read committed returns 5. The 0 is a dirty read of a write that is still open.

The index is on (customer_id, created_at), with 100 entries per leaf, fanout 100, and 100,000 rows. How many pages does a point lookup touch, and how many pages does the 250-key range touch when those keys fill 3 leaves from the start of a leaf?

A point lookup touches 3 pages. The 250-key range touches 5 pages: the root, one internal page, and 3 leaf pages.

One hundred orders each run their own items query, plus the one orders query, at 2 milliseconds a query. How many queries and milliseconds does that loop take, and how many queries and milliseconds does the IN-list form take?

The loop takes 101 queries and 202 milliseconds. The IN-list form takes 2 queries and 4 milliseconds.

Take with you

You commit the debit and the credit together, you pick the isolation level by the count it keeps stable, and you turn a scan of 100,000 rows into a 5-page index range and a 101-query loop into 2 queries.

Final task

Submit SQL indexes, cache-aside logic, and a backup/restore script that pass automated performance (p95 < 15ms on fixture hardware), stampede-prevention, and point-in-time recovery checksum tests.

The final task is marked against fixed answer keys and automated tests once the tests open.

Terms in this course

19 terms in the glossary belong to this course.

More lessons coming

The first lesson is open to read. The rest of the course is being written, and tests and diplomas come later. Join the waitlist