Архивариус

Прошлая глава кончилась книгой законов острова Паксос: сто тысяч записей, одинаковых на всех узлах, и на каждый вопрос жителей — «сколько законов о козах предложил Главк после 300 года?» — приходилось писать новый цикл по всей книге. Узлы научились договариваться о записях, но не научились отвечать на вопросы о них. Эта глава о том, как хранить миллионы записей, чтобы от человека требовался только вопрос, а искать ответ умела машина.

Представьте, что вас приняли в архив. Предшественник ушёл на пенсию и оставил три коробки и записку. В первой коробке — каталог землетрясений, с которым мы дежурили ночью в главе 6: 19 073 толчка магнитудой от пяти, с 2015 по 2025 год. Во второй — справочник аэропортов мира: все крупные и все средние, куда летают рейсы по расписанию, 3291 штука. В третьей — словарь «Войны и мира» из главы 8: каждое слово романа и сколько раз оно встречается. Записка короткая: «На каждый вопрос посетителя пиши программу. Других способов нет».

Первый день: программа на каждый вопрос

Первой приходит журналистка. Ей нужны пять сильнейших землетрясений в Японии с 2020 года. Предшественник отвечал на такие вопросы циклом, и мы умеем так же: обойти каталог, отобрать подходящие, отсортировать, отрезать пять.

Сравнение time >= "2020" работает потому, что время записано строкой вида 2021-02-13 14:07:49: у таких строк алфавитный порядок совпадает с порядком во времени. Журналистка уходит довольная. Следом заходит сейсмолог: а сколько среди них глубже 300 километров? Потом студент: сколько толчков было в каждом году? Потом пилот: какие крупные аэропорты стоят в местах, где трясёт сильнее шестёрки? Каждый вопрос — новая программа строк на десять, и все они похожи до скуки: цикл, условие, иногда словарь-счётчик, как в главе 8. Мы каждый раз объясняем машине, как перебирать записи, хотя посетителя интересует только, что в ответе.

Вторая беда серьёзнее. Посетителей много, а архив один. Если в нём есть данные, которые нельзя терять, — деньги, билеты, медицинские карты, — то каждая такая программа должна сама заботиться о том, чтобы две одновременные правки не затёрли друг друга (это мы проходили в главе 39) и чтобы отключение света не оставило половину записи (глава 40). Писать это заново в каждой программе немыслимо. Нужен посредник: одна программа, которая сама хранит данные и отвечает на короткие вопросы, где сказано только, что найти.

Сан-Хосе, 1970. Математик против навигаторов

Через полвека после статьи Кодда таблицы и SQL — то, чем пользуется почти каждая программа, которая что-то хранит. Самая распространённая база данных на свете — SQLite, библиотека, которую Ричард Хипп написал весной 2000 года, работая над программой для эсминцев ВМС США. Она живёт в каждом телефоне на Android и iOS, в браузерах Chrome, Firefox и Safari, в самом Python. По оценке разработчиков SQLite, в мире больше триллиона её баз, по нескольку сотен на каждом смартфоне. С ней мы и будем работать: она уже есть в песочнице курса, и её не нужно устанавливать.

Опись архива: таблицы, строки, ключи

Программу, которая хранит данные и отвечает на вопросы о них, называют системой управления базами данных, а сами данные под её присмотром — базой данных. В реляционной базе всё лежит в таблицах. У таблицы есть имя и столбцы, у каждого столбца — имя и тип. Каждая строка — одна запись: один аэропорт, одно землетрясение. Порядка у строк нет, как нет его у элементов множества из главы 8. Если нужен порядок, его просят явно.

Вот как это выглядит в Python. Модуль sqlite3 входит в стандартную библиотеку. Функция connect открывает базу: файл на диске или, как здесь, базу в памяти, которая исчезнет вместе с программой. Метод execute отправляет базе одну команду на языке SQL, а если команда спрашивает, — возвращает строки ответа, по которым можно пройти циклом. Каждая строка приходит кортежем.

Три команды SQL: CREATE TABLE заводит таблицу, INSERT кладёт строку, SELECT спрашивает. Ключевые слова SQL принято писать заглавными буквами, но это только обычай: база поймёт и select. Пометки NOT NULL и PRIMARY KEY — правила, которые база соблюдает сама. Столбец с пометкой PRIMARY KEY — первичный ключ: по нему строку можно назвать однозначно, и база не пустит вторую полку с кодом Q. Это та же идея, что ключ словаря, только охраняет её база. Что значит NULL у третьей полки и почему она не попала в ответ, хотя коробок у неё, может быть, и больше двух, — разговор для конца главы.

Наш архив уже собран — его построил модуль курса cs.archive, примерно так же, как ячейка выше, только строк в нём двадцать с лишним тысяч. Функция sql отправляет запрос и рисует ответ таблицей, а schema печатает опись: как устроена каждая таблица и сколько в ней строк.

Звёздочка после SELECT значит «все столбцы». Первый запрос нашёл Шереметьево, второй — землетрясение номер 17 977, камчатский толчок 8,8 из ночной смены главы 6. Страна у Шереметьева записана кодом RU, и этот код — первичный ключ таблицы countries. Столбец, который ссылается на первичный ключ другой таблицы, называют внешним ключом. Так в реляционной базе записывают связи: значением, которое совпадает с ключом другой таблицы. Указателей, как в связном списке из главы 14, здесь нет. Описание всех таблиц, их столбцов, ключей и связей называют схемой базы.

Колонку region в каталоге землетрясений завёл ваш предшественник: он отрезал от описания места place всё, что после последней запятой, — из «57 km ENE of Namie, Japan» получилось «Japan». Запомните эту колонку. Она подведёт нас на первом же посетителе.

Посетитель первый: SELECT

Журналистка вернулась: в редакции попросили перепроверить. Теперь у нас есть база, и вопрос «пять сильнейших землетрясений в Японии с 2020 года» записывается одной командой. Прочтите её вслух — она читается почти как английская фраза.

Каждая часть запроса отвечает за своё. FROM — из какой таблицы. WHERE — какие строки оставить: условие с AND, OR и NOT, как if в Python. SELECT — какие столбцы показать; там можно и вычислять: mag * 2, round(depth), substr(time, 1, 4). ORDER BY — как упорядочить, DESC — по убыванию. LIMIT — сколько строк отдать. Пишется запрос в одном порядке, а выполняется по смыслу в другом: сначала FROM, потом WHERE, потом вычисляются столбцы SELECT, потом сортировка и LIMIT. Строки в SQL берут в одинарные кавычки, а = — это сравнение, а не присваивание.

Цикла в запросе нет. Мы не сказали, как обходить таблицу, куда складывать подходящие строки, как сортировать. Мы описали, каким должен быть ответ, а как его получить, решает база. Языки, на которых описывают «что» и молчат про «как», называют декларативными. Таков SQL; таковы и регулярные выражения, до которых мы дойдём в главе 54. Свобода выбирать «как» и делает базу быстрой: в следующей главе мы увидим, что один и тот же запрос база умеет выполнить очень разными способами.

Сравните ответ с тем, что печатала программа на Python в начале главы. Первые четыре строки совпадают, а пятые разные: в одном ответе толчок 6,8 у Миядзаки, в другом — тоже 6,8, но у Ямады. Обе правильные. ORDER BY mag DESC ничего не обещает о порядке строк с одинаковой магнитудой, а LIMIT 5 отрезает по живому. Нужен определённый ответ — дайте второй ключ сортировки, через запятую: ORDER BY mag DESC, time DESC. Так же работает кортеж в ключе sorted из главы 10.

Ошибка архивариуса

Журналистка ушла, а архивариус засомневался. В ответе нет землетрясения на полуострове Ното 1 января 2024 года, а о нём писали все газеты. Ослабим условие: вместо точного совпадения region = 'Japan' попросим строки, где в описании места вообще встречается слово Japan. Для этого есть оператор LIKE: в его образце знак % заменяет любую цепочку символов, а _ — ровно один символ.

Первым ответом журналистку обманули. Два самых сильных толчка — 7,6 у префектуры Аомори в декабре 2025 года и 7,5 на Ното — в него не попали. Второй запрос объясняет почему. DISTINCT выбрасывает повторы, и видно, что слово Japan живёт в четырёх разных «регионах». У знаменитых землетрясений USGS переписывает описание места в заголовок — «2024 Noto Peninsula, Japan Earthquake», — и предшественник отрезал от него «Japan Earthquake». Толчки у островов Бонин записаны как «Japan region», а «Sea of Japan» — вообще не про Японию: Японское море омывает и Россию, и Корею.

Запрос был правильным. Подвели данные: страна, записанная свободным текстом, рано или поздно будет записана по-разному. LIKE выручил сегодня, но он ловит и лишнее, и цена ему — внимательный человек, который знает про Ното. Лечат это устройством самого архива: у страны должен быть код, и код должен вести в справочник. Сейсмологи это давно поняли: ещё в 1965 году Эдвард Флинн и Э. Р. Энгдаль предложили поделить Землю на пронумерованные районы, и у каждого толчка можно записать номер района, а не фразу. К этому мы вернёмся в разделе о порядке в справочниках. А урок на сегодня такой: прежде чем верить ответу, проверьте, какие значения лежат в столбце, по которому вы ищете. SELECT DISTINCT — первый инструмент архивариуса.

Посетитель второй: GROUP BY

Студент пишет курсовую о том, становится ли Земля беспокойнее. Ему нужно, сколько сильных толчков было в каждом году и какой был самым сильным. В главе 8 мы решали такие задачи словарём-счётчиком: ключ — год, значение — сколько раз встретился. В SQL для этого есть отдельная часть запроса.

GROUP BY year раскладывает строки по кучкам с одинаковым годом; так же словарь в главе 8 собирал анаграммы. Потом для каждой кучки считаются агрегатные функции: count(*) — сколько в ней строк, max(mag) — наибольшая магнитуда; есть ещё sum, avg, min. Та же свёртка из главы 10: много значений превращаются в одно. Каждая кучка даёт одну строку ответа. AS даёт столбцу имя, по которому к нему можно обратиться дальше.

Студенту придётся объяснить два всплеска. В 2021 году случились сразу три толчка сильнее восьми — у островов Кермадек, Аляски и Южных Сандвичевых, — а за каждым большим идут сотни повторных. В 2025-м такой хвост оставила Камчатка. Беспокойнее Земля не стала: у сильных землетрясений длинное эхо.

Следом за студентом приходит сейсмолог: в каких регионах толчки не слабее шестёрки случались двадцать раз и чаще за эти одиннадцать лет и на какой глубине они в среднем? Тут нужен фильтр дважды: по строкам и по готовым кучкам.

WHERE отбирает строки до группировки: в кучки попадут только толчки от шести. HAVING отбирает кучки после: остаются регионы, где таких толчков набралось двадцать. Перепутать их нельзя: в WHERE ещё нет никакого count(*), а в HAVING уже нет отдельных строк. Средние глубины рассказывают геологию. Почти везде толчки неглубокие, десятки километров, а «south of the Fiji Islands» — в среднем 433 километра: там одна плита уходит под другую и ломается глубоко в мантии. И опять видна старая болезнь: «Japan» и «Japan region» — две разные строки.

Вернём долг парламенту Паксоса. В конце прошлой главы на два вопроса о книге законов ушло два цикла. Положим ту же книгу — с тем же зерном случайности — в таблицу и спросим на SQL. Функция sql умеет работать с любой базой: её передают параметром con.

Ответы те же, что дали циклы прошлой главы: 820 законов о козах и Биант впереди всех по вину. Только вопрос теперь занимает строку, а третий, четвёртый и сотый вопрос не потребуют ни одного нового цикла.

Стол выдачи

Пока вы читали, у стола выдачи собралась очередь. У каждого посетителя один вопрос; ответьте запросом. Сервер курса выполнит его на том же архиве и сравнит ответ с тем, что ждёт посетитель: те же строки, те же столбцы в том же порядке. Если не выходит, загляните в схему архива выше: имена таблиц и столбцов — там.

Посетитель третий: JOIN

Диспетчер авиакомпании собирает справку о крупных аэропортах Океании: код, название, город и страну. Код, название и город лежат в airports, а название страны — в countries. В строке аэропорта есть только код страны. Значит, каждую строку аэропорта нужно склеить со строкой страны, у которой тот же код.

JOIN … ON — соединение таблиц. Его часто рисуют двумя пересекающимися кругами, но это сбивает с толку: соединение не пересекает множества, а составляет пары строк. Для каждой строки airports база ищет строки countries, для которых условие ON истинно, и каждую найденную пару склеивает в одну широкую строку. Нашлось две пары — будет две строки, ни одной — строка аэропорта в ответ не попадёт. Имена a и c, данные через AS, — короткие прозвища таблиц: столбец name есть в обеих, и a.name отличает название аэропорта от c.name, названия страны.

Самый прямой способ выполнить соединение — вложенный цикл из главы 4: для каждой из 3291 строки аэропортов перебрать 249 стран. Это 819 тысяч сравнений, квадратичная работа из главы 13. База поступает умнее: страну с данным кодом она находит, не перебирая остальные, — по первичному ключу. Как именно, расскажет следующая глава. Запрос от этого не меняется: «как» — забота базы.

Соединение может идти не только по ключу. Инженер, который оценивает сейсмический риск, спрашивает: какие крупные аэропорты чаще всего оказывались рядом с толчком не слабее шестёрки? «Рядом» запишем грубо, квадратом: широта и долгота толчка отличаются от координат аэропорта не больше чем на градус — это около 111 километров по широте и меньше по долготе, тем меньше, чем дальше от экватора. Условие ON — любое логическое выражение, а BETWEEN означает «от и до включительно».

Два архива, собранных разными людьми для разных целей, — каталог Геологической службы США и справочник аэропортов, который ведут добровольцы сайта OurAirports, — ответили на вопрос, которого не ждал ни один из них. Первым идёт Хуалянь на восточном побережье Тайваня: девятнадцать толчков от шести за одиннадцать лет. Следом — Генерал-Сантос и Давао на Минданао, Порт-Вила на Вануату, Сендай. Рейтингом опасности этот список считать нельзя: у аэропорта есть ещё фундамент, нормы строительства и расстояние до очага. База ответила на тот вопрос, который ей задали, а задать его точнее — дело посетителя; в задачах вы этим займётесь.

Строки без пары

Обычное соединение молча выбрасывает строки, которым не нашлось пары. Иногда именно они и нужны. В каких странах Европы нет ни одного аэропорта из нашего справочника? Тут поможет LEFT JOIN: каждая строка левой таблицы остаётся в ответе, даже без пары, а недостающие столбцы правой заполняются отметкой NULL — «значения нет».

Андорра, Лихтенштейн, Монако, Сан-Марино и Ватикан — пять карликовых государств, где своих аэропортов с рейсами по расписанию нет. Счётчиков в ответе два, и они расходятся. У Андорры count(*) равен единице: строка в ответе есть — та, где вместо аэропорта стоит NULL. А count(a.code) считает только строки, где a.code — не NULL, и у Андорры даёт ноль. Эта разница ещё не раз нам встретится.

Порядок в справочниках

Почему название страны лежит в отдельной таблице, если ради него приходится соединять? Было бы проще хранить его прямо в строке аэропорта. Так и делал ваш предшественник — переключатель на схеме архива показывает его справочник. Соберём такой же и поживём с ним. CREATE TABLE … AS SELECT заводит таблицу сразу с ответом на запрос.

Команда UPDATE … SET … WHERE меняет значения в строках, которые подходят под условие. Название «Turkey» повторено в справочнике предшественника пятьдесят два раза, по разу на аэропорт, и помощник исправил одно: у единственного аэропорта, город которого записан ровно как Istanbul. В справочнике стало на одну страну больше: Turkey с 51 аэропортом и Türkiye с одним. Любой отчёт «по странам» теперь врёт, и никто не заметит, пока не сложит числа. Ту же болезнь мы видели в каталоге землетрясений: Japan, Japan region и Japan Earthquake. Факт «у страны с кодом TR такое-то название» записан во многих местах, и места разошлись.

В справочнике с отдельной таблицей стран этот факт записан один раз.

Одна исправленная строка — и все 52 аэропорта показывают новое название. Перестроить данные так, чтобы каждый факт хранился в одном месте, а связи держались на ключах, — это нормализация. Нужна она там, где одно и то же значение повторяется во многих строках и меняться должно везде сразу. Название страны — свойство страны, и место ему в таблице стран. Предшественник рад был бы сделать так же с землетрясениями, но описание места пришло от USGS свободным текстом, без кода страны, и разложить его по справочнику без ручной работы нельзя.

Пустые полки: NULL

Последний посетитель — пилот. Он составляет памятку о необычных аэродромах. Сколько аэропортов в справочнике стоят ниже уровня моря, а сколько — нет? Два вопроса, которые вместе покрывают всё: либо ниже, либо не ниже. Проверим, что ответы сложатся в общее число.

Девять плюс 3245 — это 3254, а аэропортов 3291. Тридцать семь пропали из обоих ответов. Это аэропорты, высота которых в справочнике не записана: у Чжаотуна и Бэнбу в Китае, у Маунт-Гамбира в Австралии в клетке elevation_m стоит NULL — отметка «значение неизвестно». Это не ноль и не пустая строка: ноль метров — это высота, и вполне конкретная. NULL значит «мы не знаем».

А раз не знаем, то и на вопрос «ниже ли он уровня моря» можно ответить только «неизвестно». В SQL у логических выражений три значения: истина, ложь и неизвестно. Сравнение с NULL — любое, даже NULL = NULL, — даёт неизвестно: два неизвестных значения не обязаны быть равными. WHERE пропускает только строки, где условие истинно; неизвестно для него — то же, что ложь. Поэтому условие elevation_m = NULL не пропустило ни одной строки, а NOT (elevation_m < 0) не вернуло пропавших: «не неизвестно» — тоже неизвестно. Спрашивать «пусто ли здесь» нужно особым оператором IS NULL, который отвечает только «да» или «нет».

SQLite записывает истину единицей, ложь нулём, а «неизвестно» — тем же NULL. Таблицы истинности этой трёхзначной логики легко вывести, если читать «неизвестно» как «то ли истина, то ли ложь». NULL AND 0 — ложь: что бы ни скрывалось за неизвестным, «и» с ложью ложно. NULL OR 1 — истина по той же причине. А вот NULL AND 1 остаётся неизвестным: ответ зависит от того, что скрыто. Это те же таблицы истинности, что мы составляли в главе 3 и собирали из вентилей в главе 29, только с третьей строкой и третьим столбцом. И осторожно с привычками из Python: там None == None истинно, а в SQL — неизвестно. Модуль sqlite3 превращает NULL в None, но правила сравнения остаются в базе.

Ловушка NOT IN

Самая коварная ловушка прячется в операторе IN, который проверяет, есть ли значение в списке. country NOT IN ('US', 'CN') раскрывается в country <> 'US' AND country <> 'CN': все аэропорты, кроме американских и китайских. Добавим в список один NULL.

Ноль. Условие превратилось в … AND country <> NULL, а последнее сравнение для любой строки даёт неизвестно. «Истина и неизвестно» — неизвестно, и сито не пропустило ничего. Явный NULL в списке никто не пишет, но список часто получают вложенным запросом: NOT IN (SELECT city FROM …). Если в том столбце найдётся хоть одна пустая клетка, ответ молча станет пустым — без ошибки и без предупреждения. На этом спотыкаются и опытные люди; в задачах эта ловушка встретится вам на данных архива.

С агрегатными функциями NULL обходятся вежливо: они его пропускают. count(elevation_m) считает только известные высоты, avg(elevation_m) — среднее по ним, а count(*) считает строки, какими бы они ни были.

Средняя высота крупных аэропортов — 295 метров, но посчитана она по 1169 аэропортам из 1175: о шести мы ничего не знаем. Обычно это и нужно. Плохо, если пропусков много и они не случайны: если бы высоту не записывали именно у горных аэродромов, среднее вышло бы обманчиво низким. Поэтому, прежде чем верить среднему, архивариус смотрит, сколько клеток пусты, — count(*) - count(столбец).

Вторая смена у стола

К концу дня очередь снова выросла, и вопросы стали труднее: где-то нужно соединить таблицы, где-то — не попасться на пустых клетках.

Задачи

Четыре запроса к архиву. В каждой задаче ответ — строка QUERY с текстом запроса; кнопка «Запустить» покажет, что он возвращает. Тесты выполняют ваш запрос на полном архиве и на маленьких подстроенных таблицах, где спрятаны края: равные значения, пустые клетки, пустые таблицы, — и сравнивают ответ с ожидаемым строка в строку.

Куда дальше

Архивариус больше не пишет программу на каждый вопрос: он описывает ответ, а база ищет его сама. Пора узнать, чего стоит это удобство. Наш архив маленький: двадцать тысяч толчков база просматривает за миллисекунды. Рабочие таблицы бывают куда больше. На сервере этого сайта каталог землетрясений с трекера — миллионы строк. Устроим опыт: миллион показаний с пятидесяти тысяч сейсмостанций, и сто вопросов «сколько показаний у станции и какое среднее».

Когда писалась глава, вопрос к миллиону строк занимал несколько десятков миллисекунд: база просматривала все строки подряд, как наш цикл в начале главы. Потом одна команда CREATE INDEX — и тот же запрос, не изменившийся ни на букву, стал отвечать за сотые доли миллисекунды. В сотни раз быстрее, а то и в тысячу. И разрыв растёт вместе с таблицей: строк в десять раз больше — просмотр в десять раз дольше, а запрос с индексом этого почти не замечает. Сайт, который на каждой странице задаёт базе десяток таких вопросов к десяти миллионам строк, без индекса открывался бы секунды, с индексом — мгновенно.

Что такое индекс, почему с ним поиск среди миллиона строк укладывается в несколько шагов и почему эти шаги рассчитаны на блоки диска из главы 40? И второй вопрос, который мы пока обходили: что будет, если два кассира одновременно переводят деньги с одного счёта, а посреди перевода гаснет свет? Об этом — следующая глава: библиотека с каталожными ящиками и банк.