The library and the bank

The last chapter ended with an experiment: a million readings from seismic stations, a question about one station’s readings that took tens of milliseconds, and then, after a single CREATE INDEX command, hundredths of a millisecond. The query didn’t change by a letter, and the data stayed the same. What did that command build? And there was a second question we put off: how does a database avoid losing money when two people transfer it at the same moment and the lights go out in the middle of a transfer? The answers are in two places: first a library, then a bank.

Scene one. A library without a catalog

Imagine a library where the books stand on the shelves in the order they arrived. A reader asks for the books by Tolstoy. The librarian has no choice but to walk along every shelf and check every spine. That is how a database without an index works: the rows of a table lie in the order they arrived, and to answer a question about station 4242 it reads them all. This is called a full scan. Ask the database with the command EXPLAIN QUERY PLAN, and it will tell you how it intends to carry out a query; what it tells you is called the query plan.

A plan of one word: SCAN readings, look through everything. The time grows with the table: twice as many rows take about twice as long. This is the linear search of Chapter 20, only written inside the database in C. For a million rows in memory that means tens of milliseconds; on disk, and for a billion rows, minutes.

The card catalog

Libraries solved this problem long before computers: they set up a catalog. For every book there is a card with the author’s name and the shelf number, and the cards stand in drawers in alphabetical order. To find Tolstoy you don’t walk the shelves: you open the drawer marked T, flip through it, and there is the shelf number. The catalog knows nothing about the books themselves except the key and the address. A database index is built the same way: the values of the column station in order, each with the number of its row, the rowid, by which the row can be fetched.

How do you keep ordered cards in a computer’s memory? We know three ways, and each has its own trouble. A sorted list can be searched by binary search in twenty comparisons per million, as in Chapter 20, but inserting into the middle shifts the whole tail, the $O(n)$ of Chapter 14, and new cards arrive every second. The hash table of Chapter 16 finds a key in one step, but it can’t do “all stations from 4000 to 4999” and doesn’t hand out keys in order. The AVL tree of Chapter 17 does it all: search, insertion, order, in $O(\log n)$. For a million keys it has twenty-odd levels, no more than 28, as we proved in that chapter.

Twenty-odd levels mean twenty-odd nodes scattered around memory. While the tree is in RAM, that is nothing. But the indexes of large databases live on disk, and a disk, as we saw in Chapter 40, reads in blocks of 4,096 bytes, and each read from a hard disk costs milliseconds. For a processor, as we worked out in Chapter 34, that is an eternity. Twenty reads at ten milliseconds each make a fifth of a second for a single lookup. And from each block it reads, an AVL tree uses one node: a key and two links, a few dozen bytes out of four thousand. The rest is read for nothing.

Boeing, 1970. Wide drawers

Bayer and McCreight reasoned like this: if the disk reads a whole block anyway, let a tree node fill a whole block. Then a node holds hundreds of keys, in order, and between them links to the children: everything less than the first key is in the first child, everything between the first and second keys in the second child, and so on. It is a catalog drawer with guide cards: the guides read “A–Be” and “Be–Bi,” and you know at once which drawer to open next. A B-tree is a search tree in which every node has many children and all the leaves lie at the same depth.

A binary tree splits the keys in two at every level, and for a million keys it needs twenty levels. A node of a hundred keys splits them a hundred ways, and the same million fits into three levels: $100^3 = 10^6$. The height of a B-tree is $\log_m n$, where $m$ is the width of a node: the same logarithm, only to a large base.

A billion keys take only four levels. Every lookup needs the root and the second level, so they almost always sit in the cache in memory, and only one or two blocks are left to read from disk.

Insertion: a drawer splits in two

How do you keep all the leaves at one depth when keys arrive in any order? In Chapter 17 that took rotations, but a B-tree does without them. A new key always goes into a leaf, in its place in the order. As long as the leaf has room, that is all. If the leaf overflows, it is split in half, and the middle key moves up into the parent, where it becomes the separator between the two halves. If that makes the parent overflow, it is split too. If the root splits, a new root with one key appears above it. An ordinary search tree grows downward, at the leaves; a B-tree grows upward, at the root, and that is why all its leaves are always at the same depth.

Here is the same in Python. A node is a list of keys and a list of children; a leaf has no children. The function bisect_left from the module bisect is the binary search of Chapter 20: it returns the place where a key would go in a sorted list. In an inner node that place is the number of the child to go down into.

_insert returns None if the node didn’t overflow, or the pair “middle key and new right half” if it had to split, and the parent takes that pair in. The slider under the picture steps through all sixteen insertions. The tree grew a level only once, on the fifth insertion, when the root split. Next, the same code at three widths, on three hundred thousand keys.

With four keys per node, a tree of three hundred thousand keys needs ten levels; with 32, four; with 255, three. The loop for M in … changes a global variable that _insert reads, so the same tree is built three times with different widths. A lookup reads as many nodes as there are levels and not one more: a B-tree has no long branches.

A look inside SQLite

SQLite keeps both its indexes and its tables in B-trees. A table is a tree whose key is the rowid, with the rows stored in the leaves; an index is a tree whose keys are the values of a column together with the rowid. In the sandbox SQLite is built with the virtual table dbstat, which reports on every page of the database: which level it is on and how many entries it holds. We build a log of a million readings with an index and count the levels.

The column path of each page is its address in the tree: / for the root, /000/ for its first child, /000/003/ for its first child’s fourth child. So the level equals the number of slashes. The table and the index both have three levels. The root of the index holds about ten keys, the second level about eleven pages of some 250 keys each, and the leaves almost three thousand pages of about 350 each. To find a station’s readings, SQLite goes down three pages of the index; there, in one leaf, all the station’s entries lie side by side, twenty on average, with their rowids. For each row it goes down another three pages of the table’s tree, but by then the root and the second level are already in the cache. That makes a few dozen pages and twenty rows instead of all five thousand pages of the table and the million rows in them. In pages the difference is a factor of a hundred or so; the work on rows adds the rest, since a full scan unpacks and checks every one of the million. Together they account for the gap of hundreds or thousands of times that we saw at the end of the last chapter.

The second descent, through the table’s tree, is needed to fetch the columns that the index doesn’t have, here value. If every column the query needs is in the index itself, the second descent isn’t needed. Such an index is called covering, and SQLite writes USING COVERING INDEX in the plan.

How the database chooses its path

In the last chapter we said that SQL describes the “what” and the database chooses the “how.” The part of the database that chooses is called the query planner: for every query it goes through the options (scan everything, follow one index, follow another), estimates how many rows each would read, and takes the cheapest. But an index doesn’t help every query, and three rules are enough to guess which ones it will help.

First: an index on several columns is ordered like a phone book, by last name and then, within a last name, by first name. An index on (station, day) instantly finds “station 7 from March 1 to March 7” and plain “station 7,” but it won’t help with “all stations on March 1”: you can’t find all the Johns in a phone book without leafing through the whole thing. Second: a function of a column hides the column from the index. WHERE substr(time, 1, 10) = '2021-03-01' makes the database compute substr for every row, while WHERE time >= '2021-03-01' AND time < '2021-03-02' asks the same thing, and with an index on time it is answered at once. Third: an index answers “from … to …” as well as “equals.” With two descents through the tree the database finds the start and the end of the range, and between them the keys run in order: what we did with two binary searches in Chapter 20.

The words from “war” to “was,” thirty-three of them, are found in hundredths of a millisecond: SEARCH … (word>? AND word<?), a descent to the start of the range and a walk to its end. The same question asked through substr turns into a SCAN: the database reads the whole index from start to finish. At least the index is covering, so the database doesn’t visit the table itself, but it still looks through all twenty thousand words. And LIKE 'war%' didn’t use the index here either: by default LIKE in SQLite doesn’t distinguish capital and lowercase Latin letters, while the index does, so the planner can’t promise that the answer would be the same. Check the plan before you count on an index.

Below is the planner’s lab. The course server builds a table of half a million earthquakes, creates the indexes you choose and runs six queries, showing the plan and the time of each. Turn indexes on and off and watch which queries respond.

A case from this site: 745 milliseconds

The planner estimates how many rows each option will read, but it doesn’t see the data itself. Until it is asked to look, it doesn’t know how many different magnitudes the table has, and by default it assumes that each value of the first column of an index comes with about ten rows. Under that assumption both indexes look equally good. ANALYZE walks the indexes, counts, and writes down statistics in the service table sqlite_stat1. From it the planner learns that there are only a few dozen different magnitudes (4.0, 4.1, 4.2…) and that each has thousands of rows. Now a move that SQLite never makes without statistics pays off: hopping through the compound index, finding the range of latitudes for magnitude 4.0, then for 4.1, and so on. We reproduce the story in the sandbox on six hundred thousand quakes.

The magnitudes here are distributed as in nature: each next unit of magnitude is about ten times rarer. This is the Gutenberg–Richter law, and the formula 3 - log10(1 - random()) is its simplest model. Before ANALYZE the plan is USING INDEX quakes_mag (mag>?): go through all sixty-odd thousand quakes of four and up and, for each, go down into the table. After it, the plan is ANY(mag) AND lat>? AND lat<?: hops from magnitude to magnitude, with a range of latitudes inside each. When this chapter was written, that meant 40–50 milliseconds before and 2–3 after; on the site, where the table has seven and a half times as many rows and lives on disk, the difference came out almost a hundredfold. The last line is the statistics themselves: the table has 600 thousand rows, one magnitude has about ten thousand of them, and a pair “magnitude and latitude” has one.

The price of an index

What stops us from building indexes on every column is writing: each index is one more B-tree, and every new row has to be inserted into all the trees.

The first index alone made writing more than twice as slow, three indexes about five or six times as slow, and each one added a few megabytes to the database. So indexes are built for the questions that are asked, not “just in case.” A table that is written a hundred times a second and read once a day is better off without a pile of indexes; a directory that is read thousands of times a second, the other way round. That is the craft of whoever looks after a database: watch which queries are slow, read their plans and build indexes for them.

Scene two. The bank

From the library to the bank. Here speed can wait: not a cent may be lost. In Chapter 12 we wrote the accounts of Ada and Grace and demanded that an operation either go through in full or change nothing. While an account lives in the memory of one program, that is easy: check first, then change. But a transfer is two writes to the database: take money from one account and put it into the other. What if the till crashes between them? We stage that accident. The bank lives in a file, and the till is a separate program that takes the money and dies before it gets to the deposit: os._exit ends a process instantly, like a pulled plug, without finishing or closing anything.

Without a transaction, thirty dollars vanished from the bank: taken from Ada, never given to Grace. In the second run the till crashed at the same spot, but before taking the money it said BEGIN, “I am starting one piece of work.” When the database was opened again, everything was as it had been before the transfer. The last column of the output shows that after the crash a file bank.db-journal was left next to the database. Before changing a page, SQLite puts the page’s old copy into it. If the work reaches COMMIT, the journal is erased. If not, whoever opens the database next finds the journal and puts the old pages back. The file system journal of Chapter 40 also guarded against a pulled plug, but it kept the intended new data rather than the old; we will come back to that kind of journal.

A group of commands that is carried out in full or not at all is called a transaction. It starts with the command BEGIN and ends with COMMIT, “make it final,” or ROLLBACK, “undo everything done since the start.” In Python it is convenient to write with con:, a block that commits the transaction by itself if everything went well and rolls it back if an exception was raised.

Jim Gray: all or nothing

These four letters are a contract that the database makes with the programmer. Here they are, spelled out with our bank as the example. ACID stands for:

• atomicity: a transfer can’t be carried out halfway; the journal we saw a moment ago takes care of that;
• consistency: the database’s rules hold both before and after; if the schema says CHECK (balance >= 0), a transaction that would take an account below zero is rejected as a whole;
• isolation: two simultaneous transfers don’t see each other’s halves and don’t overwrite each other; the section on the tellers below is about this;
• durability: once the database has answered “committed,” the write will survive both a program crash and a power cut, because before answering the database waits for the fsync of Chapter 40.

The log comes first

The rollback journal we saw keeps old copies of pages. There is also the opposite approach, the one used by the file system journal in Chapter 40, and most databases use it today: the write-ahead log, WAL for short. Changes are first appended to the end of the log, and the database file is left alone for the moment. A transaction is committed when its “done” mark is in the log. From time to time the database runs a checkpoint, copying what has piled up in the log into place. Appending to the end of a file is fast, and readers meanwhile go on calmly reading the old pages from the database itself. SQLite has had this mode since 2010, and it takes one command to turn it on.

After COMMIT the twenty thousand rows exist only in the log: the database file hasn’t changed by a byte, and the log has grown to almost four hundred kilobytes. Yet the transaction is already committed: if the power went out now, SQLite would read the log on the next open and restore everything. The checkpoint copies the pages into place, and the log empties. The database of this site’s earthquake tracker runs in this mode too: the program that regularly appends fresh quakes doesn’t get in the way of visitors reading the pages.

The tellers

One letter is left: I, for isolation. Atomicity protects against crashes, and isolation protects against neighbors. The bank has two tellers. At the first window Ada is paying in 50; at the second, in the same minute, 30 is being taken out of her account. Each teller reads the balance, computes the new one and writes it. If their steps interleave, the race of Chapter 39 happens again: both read 100, the first writes 150, the second writes 70, and fifty dollars vanish. The danger is an everyday one: any code that reads a value from a database, changes it inside the program and writes it back is built this way. In our experiment the tellers are two connections to one database.

Without transactions the balance became 70 instead of 120: the first teller’s write was overwritten as if it had never happened. This is a lost update. In the second run the first teller starts with BEGIN IMMEDIATE, “I am starting a transaction and taking the right to write right now.” SQLite lets only one connection write at a time, and the second teller is refused with database is locked: in a working program it would wait and try again (connect has the parameter timeout for that; here we set it to zero so that the refusal shows). When the first teller has committed its 150, the second starts over, reads 150 and writes 120. There is also a simpler way: don’t take the arithmetic out of the database. The command UPDATE accounts SET balance = balance + 50 reads and writes within a single operation, and it can’t be lost, as if counter += 1 from Chapter 39 were carried out by a single indivisible processor instruction, like the ones the lock was built from there.

The lost update is not the only trouble. Database researchers have drawn up a whole catalog of anomalies: things a transaction can see or spoil when its neighbors work at the same time. You can stage three of them yourself in the widget below.

The second story is a dirty read. An auditor adds up the balances while a transfer is still under way and, as it will turn out, about to be canceled. The auditor sees money that has left one account and not arrived in the other, and reports a shortfall that never existed. The third is write skew, the most insidious of the three. Ada and Grace share a credit limit: either account may go below zero as long as the sum of the two stays non-negative. Both check the sum at the same moment (100, enough) and each takes a hundred out of her own account. Each touched only her own record and kept the rule on her own, but together they broke it.

Which anomalies to guard against is decided by a setting called the isolation level. The SQL standard describes four levels, from “read even uncommitted data” to “serializable,” the guarantee that the result will be as if the transactions had run strictly one after another. The stricter the level, the more often transactions have to wait for each other or start over, so many databases choose a compromise by default: PostgreSQL uses “read committed,” MySQL “repeatable read.” SQLite is simpler and stricter: only one connection at a time may write to it, and all its transactions are serializable.

Tasks

Three tasks, one for each of the chapter’s crafts: choose indexes for a workload, write a transfer that never loses money, and walk a B-tree yourself.

What next

Both the library and the bank rest on the same disk, and the chapter’s last question is about it. Indexes and journals take up space: the database of the last chapter, saved to a file, weighs about three megabytes. What if we compress it?

The text of War and Peace shrinks almost threefold, the archive by a factor of two and a half, and three megabytes of random bytes don’t shrink by a single byte. So text and tables hold something superfluous that can be thrown away and later restored without a flaw, and random bytes hold nothing of the kind. What is it? And how does ZIP find that excess in a fraction of a second and squeeze three gigabytes of text into one? That is the next chapter, the packing contest.