Внутреннее устройство баз данных

Что это такое

База данных хранит данные на диске и отвечает на запросы о них, ничего не теряя и не выдавая желаемое за действительное. Под языком SQL работают три механизма. Движок хранения решает, как разложены строки; индекс находит их, не читая всего подряд; планировщик выбирает, каким индексом воспользоваться. Если эти слова пока незнакомы, сначала прочитайте запись о реляционных базах данных.

Почему это важно

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

Ключевые идеи

Страница — единица ввода-вывода

Читают и пишут базы данных страницами фиксированного размера, обычно в несколько килобайт, а не строками. Как только страница оказалась в памяти, каждая строка на ней достаётся бесплатно. Зато каждая страница, которая не поместилась, стоит чтения. Поэтому важна ширина строки: чем шире текстовые столбцы, тем меньше строк умещается на страницу, и тем больше страниц задевает сканирование. Именно поэтому сканирование только по индексу оказывается быстрым: ответ лежит на страницах индекса, а таблица не читается вовсе.

страница 8192 байта
строки по 200 байт -> ~40 строк на страницу
строки по 800 байт -> ~10 строк на страницу   (в 4 раза больше страниц на скан)

B-деревья хранят порядок, поэтому диапазоны дешёвы

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

              [ 50 | 100 ]
             /      |      \
     [10|30]    [60|80]    [120|200]
листья связаны слева направо -> скан диапазона идёт по ним

Хранение в журнальном стиле меняет чтение на запись

Некоторые движки никогда не обновляют страницу на месте: каждое изменение они дописывают в журнал, а отсортированную таблицу держат в памяти и сбрасывают на диск по мере роста. Итоговые файлы объединяются в фоне. Запись становится последовательной, и такое поведение предпочитают диски и флеш-память. Однако чтению приходится проверять несколько файлов. Так устроены многие хранилища «ключ — значение» и ряд современных реляционных движков, а компромисс здесь в том, что скорость записи покупается дополнительными чтениями.

Планировщик выбирает путь, иногда ошибочно

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

Seq Scan on orders  (rows=1000000) (actual rows=2)
  Filter: customer_id = 42

Буферы и журнал упреждающей записи

Часто используемые страницы живут в буферном пуле в памяти, поэтому прогретая база быстрее холодной. Изменение попадает в журнал раньше, чем на страницы данных, а журнал сбрасывается при фиксации транзакции. Если машина падает, журнал проигрывается вперёд, и база восстанавливается до последнего зафиксированного состояния. Такой механизм лежит в основе слова «долговечность», и он же объясняет, почему зафиксированная запись медленнее записи в кэш страниц.

Практика

Прочитайте план одного запроса

Возьмите запрос, который запускаете часто. Попросите базу объяснить план и найдите шаг с самой большой оценкой числа строк. Проверьте, проиндексирован ли столбец в условии фильтра.

Готово, когда: вы можете сказать, сканирует запрос таблицу или ищет по индексу, и каким планировщик ожидал число строк.

Измерьте индекс, который создали

Выберите столбец, по которому фильтруете, но индекса на нём нет. Замерьте время запроса на достаточно большой таблице, затем создайте индекс и замерьте снова.

Готово, когда: второе измерение быстрее, а план сменился со сканирования на поиск по индексу.

Частые ошибки

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

Что читать дальше

SQL и реляционные базы данных (05-backend-data/07-sql-relational-databases) — язык запросов и моделирование, на которых держится эта запись, и лучшее место для начала.
Операционные системы (01-cs-fundamentals/15-operating-systems) — страницы, буферы и сбросы: тот же слой, только внутри базы данных.
Структуры данных (01-cs-fundamentals/02-data-structures) — дерево и журнал: две формы, между которыми выбирает любой движок хранения.