The archivist

The last chapter ended with the book of laws of the island of Paxos: a hundred thousand entries, the same on every node, and every question the citizens asked (“how many laws about goats did Glaucus propose after the year 300?”) meant writing a new loop over the whole book. The nodes had learned to agree on the entries, but not to answer questions about them. This chapter is about storing millions of records so that a person only has to ask the question and the machine works out how to find the answer.

Imagine you have started work at an archive. Your predecessor has retired and left you three boxes and a note. The first box holds the earthquake catalog from our night shift in Chapter 6: 19,073 quakes of magnitude five and up, from 2015 through 2025. The second holds a directory of the world’s airports: every large one and every medium one with scheduled flights, 3,291 in all. The third holds the word count of War and Peace from Chapter 8: every word of the novel and how many times it occurs. The note is short: “Write a program for every visitor’s question. There is no other way.”

Day one: a program for every question

The first visitor is a journalist. She needs the five strongest earthquakes in Japan since 2020. Your predecessor answered questions like this with a loop, and so can we: go through the catalog, pick the matching quakes, sort them, cut off five.

The comparison time >= "2020" works because the time is stored as a string like 2021-02-13 14:07:49, and for such strings alphabetical order is the same as order in time. The journalist leaves happy. Next comes a seismologist: how many of those were deeper than 300 kilometers? Then a student: how many quakes were there each year? Then a pilot: which large airports stand where the ground shakes harder than magnitude six? Every question is a new program of a dozen lines, and they are all tediously alike: a loop, a condition, sometimes a counting dictionary as in Chapter 8. Each time we explain to the machine how to go through the records, while the visitor cares only about what is in the answer.

The second problem is more serious. There are many visitors and one archive. If it holds data that must not be lost (money, tickets, medical records), then every such program has to make sure on its own that two simultaneous edits don’t overwrite each other (we went through that in Chapter 39) and that a power cut doesn’t leave half a record behind (Chapter 40). Writing all that again in every program is out of the question. We need a go-between: one program that keeps the data itself and answers short questions that say only what to find.

San Jose, 1970. A mathematician against the navigators

Half a century after Codd’s paper, tables and SQL are what nearly every program that stores anything relies on. The most widely deployed database in the world is SQLite, a library that Richard Hipp wrote in the spring of 2000 while working on software for US Navy guided-missile destroyers. It lives in every Android and iOS phone, in the Chrome, Firefox and Safari browsers, and in Python itself. By its developers’ estimate there are over a trillion SQLite databases in use, several hundred on every smartphone. That is the one we will use: the course sandbox already has it, and there is nothing to install.

Taking stock: tables, rows, keys

A program that keeps data and answers questions about it is called a database management system, and the data in its care is a database. In a relational database everything lives in tables. A table has a name and columns, and each column has a name and a type. Each row is one record: one airport, one earthquake. Rows have no order, any more than the items of a set in Chapter 8 do. If you need an order, you ask for it.

Here is what it looks like in Python. The sqlite3 module is part of the standard library. The function connect opens a database: a file on disk or, as here, a database in memory that disappears when the program ends. The method execute sends the database one command in SQL and, if the command asks something, returns the rows of the answer, which you can loop over. Each row arrives as a tuple.

Three SQL commands: CREATE TABLE makes a table, INSERT puts a row into it, SELECT asks. SQL keywords are customarily written in capitals, but that is only a habit: the database is equally happy with select. The marks NOT NULL and PRIMARY KEY are rules that the database enforces by itself. A column marked PRIMARY KEY is the primary key: it names a row unambiguously, and the database won’t let in a second shelf with the code Q. It is the same idea as a dictionary key, except that here the database guards it. What NULL on the third shelf means, and why that shelf didn’t make it into the answer although it may well have more than two boxes, we will discuss at the end of the chapter.

Our archive is already assembled. The course module cs.archive built it much like the cell above, only with more than twenty thousand rows. The function sql sends a query and draws the answer as a table, and schema prints the inventory: how each table is laid out and how many rows it has.

The asterisk after SELECT means “all columns.” The first query found Sheremetyevo in Moscow, the second found earthquake number 17,977, the magnitude 8.8 Kamchatka quake from the night shift in Chapter 6. Sheremetyevo’s country is stored as the code RU, and that code is the primary key of the table countries. A column that refers to the primary key of another table is called a foreign key. This is how a relational database records links: with a value that matches a key in another table. There are no pointers here, unlike the linked list of Chapter 14. The description of all the tables, their columns, keys and links is called the database’s schema.

The column region in the earthquake catalog was added by your predecessor: he took the description of the place, place, and kept only what follows the last comma, so that “57 km ENE of Namie, Japan” became “Japan.” Remember that column. It will let us down as soon as the first visitor comes back.

Visitor one: SELECT

The journalist is back: her editors want the facts checked. Now we have a database, and the question “the five strongest earthquakes in Japan since 2020” is a single command. Read it aloud: it sounds almost like an English sentence.

Each part of the query has its own job. FROM says which table. WHERE says which rows to keep: a condition with AND, OR and NOT, like an if in Python. SELECT says which columns to show, and it can compute too: mag * 2, round(depth), substr(time, 1, 4). ORDER BY says how to sort, and DESC means descending. LIMIT says how many rows to return. A query is written in one order but, logically, carried out in another: first FROM, then WHERE, then the columns of SELECT are computed, then the sorting and the LIMIT. Strings in SQL go in single quotes, and = is a comparison, not an assignment.

There is no loop in the query. We didn’t say how to go through the table, where to put the matching rows or how to sort them. We described what the answer should be, and the database decides how to get it. Languages that describe the “what” and keep quiet about the “how” are called declarative. SQL is one; so are regular expressions, which we will reach in Chapter 54. The freedom to choose the “how” is what makes a database fast: the next chapter shows that the database can carry out one and the same query in very different ways.

Compare this answer with what the Python program printed at the start of the chapter. The first four rows match, but the fifth differs: one answer has a 6.8 near Miyazaki, the other a 6.8 near Yamada. Both are correct. ORDER BY mag DESC promises nothing about the order of rows with equal magnitude, and LIMIT 5 cuts wherever it falls. If you want a definite answer, give a second sort key after a comma: ORDER BY mag DESC, time DESC. A tuple as the key of sorted in Chapter 10 works the same way.

The archivist’s mistake

The journalist has gone, and the archivist has doubts. The answer doesn’t include the earthquake on the Noto Peninsula on January 1, 2024, which was in every newspaper. We loosen the condition: instead of the exact match region = 'Japan', we ask for the rows where the word Japan appears anywhere in the description of the place. That is what the LIKE operator is for: in its pattern, the sign % stands for any run of characters, and _ for exactly one character.

The first answer misled the journalist. The two strongest quakes, a 7.6 off Aomori Prefecture in December 2025 and the 7.5 on Noto, weren’t in it. The second query explains why. DISTINCT throws out repeats, and you can see that the word Japan lives in four different “regions.” For famous earthquakes the USGS rewrites the description of the place into a headline, “2024 Noto Peninsula, Japan Earthquake,” and the predecessor’s rule turned that into “Japan Earthquake.” Quakes near the Bonin Islands are written as “Japan region,” and “Sea of Japan” isn’t about Japan at all: the Sea of Japan also washes the coasts of Russia and Korea.

The query was right. The data let us down: a country written as free text will sooner or later be written in different ways. LIKE saved the day this time, but it also catches things it shouldn’t, and it worked only because someone careful knew about Noto. The cure lies in how the archive itself is built: a country should have a code, and the code should lead into a directory. Seismologists realized this long ago: back in 1965 Edward Flinn and E. R. Engdahl proposed dividing the Earth into numbered regions, so that each quake could carry the number of its region instead of a phrase. We will return to this in the section on putting the directories in order. The lesson for today: before you trust an answer, check what values are stored in the column you are searching. SELECT DISTINCT is the archivist’s first tool.

Visitor two: GROUP BY

A student is writing a term paper on whether the Earth is getting more restless. He needs the number of strong quakes in each year and the strongest one of each year. In Chapter 8 we solved problems like this with a counting dictionary: the year was the key, and the value was how many times it came up. SQL has a clause made for this.

GROUP BY year sorts the rows into piles with the same year, the way the dictionary in Chapter 8 collected anagrams. Then for each pile the aggregate functions are computed: count(*) is how many rows the pile has, max(mag) is the largest magnitude; there are also sum, avg and min. It is the fold from Chapter 10: many values turn into one. Each pile gives one row of the answer. AS gives a column a name that later parts of the query can refer to.

The student will have to explain two spikes. In 2021 there were three quakes stronger than eight (off the Kermadec Islands, off Alaska and off the South Sandwich Islands), and every big quake is followed by hundreds of aftershocks. In 2025 Kamchatka left a tail like that. The Earth has not become more restless: strong earthquakes have a long echo.

After the student comes a seismologist: in which regions did quakes of magnitude six or more happen twenty times or more in these eleven years, and how deep were they on average? This takes two filters: one on the rows and one on the finished piles.

WHERE picks rows before grouping: only quakes of six and up get into the piles. HAVING picks piles after grouping: what remains are the regions with at least twenty such quakes. The two can’t trade places: in WHERE there is no count(*) yet, and in HAVING there are no single rows any more. The average depths are a lesson in geology. Almost everywhere the quakes are shallow, tens of kilometers, but “south of the Fiji Islands” averages 433 kilometers: there one plate dives under another and breaks deep in the mantle. And the old disease shows up again: “Japan” and “Japan region” are two separate rows.

Time to pay our debt to the parliament of Paxos. At the end of the last chapter, two questions about the book of laws took two loops. We put the same book, with the same random seed, into a table and ask our questions in SQL. The function sql works with any database, passed as the parameter con.

The answers match what the loops of the last chapter gave: 820 laws about goats, and Bias ahead of everyone on wine. But now a question takes one line, and the third, the fourth and the hundredth question won’t need a single new loop.

The reference desk

While you were reading, a line formed at the desk. Each visitor has one question; answer it with a query. The course server runs it on the same archive and compares your answer with what the visitor expects: the same rows, the same columns in the same order. If you get stuck, check the schema of the archive above: the names of the tables and columns are there.

Visitor three: JOIN

An airline dispatcher is putting together a list of the large airports of Oceania: code, name, city and country. The code, name and city are in airports, but the name of the country is in countries. An airport’s row holds only the country code. So each airport row has to be glued to the country row with the same code.

JOIN … ON is a join of tables. It is often drawn as two overlapping circles, which is misleading: a join doesn’t intersect sets, it makes pairs of rows. For each row of airports the database looks for rows of countries for which the ON condition is true, and glues each pair it finds into one wide row. If two pairs turn up, there will be two rows; if none, the airport’s row doesn’t appear in the answer. The names a and c, given with AS, are short nicknames for the tables: both have a column name, and a.name tells the airport’s name apart from c.name, the country’s.

The most direct way to compute a join is the nested loop from Chapter 4: for each of the 3,291 airport rows, go through the 249 countries. That is 819 thousand comparisons, the quadratic work of Chapter 13. The database is smarter: it finds the country with a given code without looking through the others, by its primary key. How it does that is the subject of the next chapter. The query stays the same either way: the “how” is the database’s business.

A join doesn’t have to go by a key. An engineer assessing seismic risk asks: which large airports have most often been near a quake of magnitude six or more? We will define “near” crudely, as a square: the latitude and longitude of the quake differ from the airport’s by no more than one degree. That is about 111 kilometers of latitude and less of longitude, shrinking the farther you go from the equator. The ON condition can be any logical expression, and BETWEEN means “from … to …, inclusive.”

Two archives, collected by different people for different purposes (the catalog of the US Geological Survey and the airport directory kept by the volunteers of the OurAirports site), have answered a question that neither of them anticipated. First comes Hualien on the east coast of Taiwan: nineteen quakes of six or more in eleven years. Then General Santos and Davao on Mindanao, Port Vila on Vanuatu, and Sendai. Don’t read this list as a ranking of danger: an airport also has foundations, building codes and a distance from the focus. The database answered the question it was asked; asking it better is the visitor’s job, and you will do that in the tasks.

Rows without a match

An ordinary join silently drops the rows that found no match. Sometimes those are the ones you want. Which countries of Europe have no airport at all in our directory? LEFT JOIN helps here: every row of the left table stays in the answer, even without a match, and the missing columns of the right table are filled with the mark NULL, “no value.”

Andorra, Liechtenstein, Monaco, San Marino and Vatican City: five microstates without an airport of their own with scheduled flights. The answer has two counters, and they disagree. For Andorra count(*) equals one: there is a row in the answer, the one with NULL in place of an airport. But count(a.code) counts only the rows where a.code is not NULL, and for Andorra it gives zero. We will meet this difference more than once.

Putting the directories in order

Why does the country’s name sit in a separate table if getting it takes a join? It would be simpler to store it right in the airport’s row. That is what your predecessor did; the switch on the schema of the archive shows his directory. We will build one like it and live with it for a while. CREATE TABLE … AS SELECT creates a table filled straight away with the answer to a query.

The command UPDATE … SET … WHERE changes values in the rows that match the condition. The name “Turkey” is repeated fifty-two times in the predecessor’s directory, once per airport, and the assistant fixed one of them: the only airport whose city reads “Istanbul” and nothing else. The directory now has one more country: Turkey with 51 airports and Türkiye with one. Every report “by country” now lies, and nobody will notice until they add up the numbers. We saw the same disease in the earthquake catalog: Japan, Japan region and Japan Earthquake. The fact “the country with the code TR has such-and-such a name” is written in many places, and the places have drifted apart.

In a directory with a separate table of countries, that fact is written once.

One corrected row, and all 52 airports show the new name. Rearranging data so that every fact is stored in one place and the links rest on keys is called normalization. You need it wherever the same value repeats in many rows and has to change everywhere at once. A country’s name is a property of the country, and its place is in the table of countries. The predecessor would gladly have done the same with the earthquakes, but USGS sends the description of the place as free text without a country code, and there is no sorting it into a directory without manual work.

Empty shelves: NULL

The last visitor is a pilot. He is putting together a handbook of unusual airfields. How many airports in the directory lie below sea level, and how many don’t? Between them the two questions cover everything: an airport either lies below sea level or it doesn’t. So the two answers should add up to the total. We check that they do.

Nine plus 3,245 is 3,254, but there are 3,291 airports. Thirty-seven have vanished from both answers. These are airports whose elevation the directory doesn’t record: for Zhaotong and Bengbu in China and for Mount Gambier in Australia, the cell elevation_m holds NULL, the mark for “value unknown.” This mark is neither zero nor an empty string: zero meters is an elevation, and a quite definite one. NULL means “we don’t know.”

And if we don’t know, the question “is it below sea level?” can only be answered with “unknown.” In SQL, logical expressions have three values: true, false and unknown. Any comparison with NULL, even NULL = NULL, gives unknown: two unknown values don’t have to be equal. WHERE lets through only the rows where the condition is true; to it, unknown is the same as false. That is why the condition elevation_m = NULL let no rows through, and NOT (elevation_m < 0) didn’t bring back the missing ones: “not unknown” is unknown too. To ask “is this empty?” you need a special operator, IS NULL, which answers only yes or no.

SQLite writes true as one, false as zero, and unknown as NULL itself. The truth tables of this three-valued logic are easy to work out if you read “unknown” as “either true or false.” NULL AND 0 is false: whatever hides behind the unknown, “and” with false is false. NULL OR 1 is true for the same reason. But NULL AND 1 stays unknown: the answer depends on what is hidden. These are the truth tables we wrote in Chapter 3 and built from gates in Chapter 29, with a third row and a third column. And beware of habits from Python: there None == None is true, while in SQL it is unknown. The sqlite3 module turns NULL into None, but the comparison rules stay in the database.

The NOT IN trap

The nastiest trap hides in the IN operator, which checks whether a value is in a list. country NOT IN ('US', 'CN') unfolds into country <> 'US' AND country <> 'CN': all airports except the American and Chinese ones. Now we add a single NULL to the list.

Zero. The condition has become … AND country <> NULL, and that last comparison gives unknown for every row. “True and unknown” is unknown, and the sieve let nothing through. Nobody writes an explicit NULL into a list, but the list often comes from a subquery: NOT IN (SELECT city FROM …). If that column has even one empty cell, the answer silently becomes empty, with no error and no warning. Experienced people trip over this too; in the tasks you will meet this trap on the archive’s data.

Aggregate functions treat NULL politely: they skip it. count(elevation_m) counts only the known elevations, avg(elevation_m) averages over them, and count(*) counts rows, whatever is in them.

The average elevation of large airports is 295 meters, but it is computed over 1,169 airports out of 1,175: we know nothing about six of them. Usually that is what you want. It goes wrong when the gaps are many and not random: if it were the mountain airfields whose elevations were missing, the average would come out deceptively low. So before trusting an average, the archivist checks how many cells are empty: count(*) - count(column).

The second shift at the desk

By the end of the day the line has grown again, and the questions are harder: some need a join, some need you to avoid tripping over empty cells.

Tasks

Four queries to the archive. In each task the answer is a string QUERY holding the text of the query; the Run button shows what it returns. The tests run your query on the full archive and on small rigged tables where the edge cases hide (equal values, empty cells, empty tables) and compare the answer with the expected one row by row.

What next

You no longer write a program for every question: you describe the answer, and the database finds it on its own. Time to find out what this convenience costs. Our archive is small: the database looks through twenty thousand quakes in milliseconds. Working tables are often much bigger. On this site’s server, the earthquake catalog of the tracker runs to millions of rows. Here is an experiment: a million readings from fifty thousand seismic stations, and a hundred questions “how many readings does a station have, and what is their average?”

When this chapter was written, a question to a million rows took a few tens of milliseconds: the database looked through every row in turn, like our loop at the start of the chapter. Then came a single command, CREATE INDEX, and the same query, unchanged by a single letter, began answering in hundredths of a millisecond. Hundreds of times faster, even a thousand. And the gap grows with the table: ten times more rows means a scan ten times longer, while the query with the index hardly notices. A site that asks the database a dozen such questions per page, against ten million rows, would take seconds to open without an index and open instantly with one.

What is an index, why does it let you find a row among a million in a few steps, and why are those steps designed around the disk blocks of Chapter 40? And a second question that we have been dodging so far: what happens if two tellers transfer money from the same account at the same moment, and the lights go out in the middle of a transfer? That is the next chapter: a library with card catalog drawers, and a bank.