Как хранятся данные: страницы и файлы

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

Страница (блок) — это минимальная единица обмена данными между диском и оперативной памятью. СУБД читает и пишет данные не по одной строке, а целыми страницами фиксированного размера (обычно 4–16 КБ).

Зачем понимать физику хранения

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

Иерархия памяти: почему диск так дорог

Чтобы прочувствовать, почему всё крутится вокруг числа дисковых чтений, полезно знать иерархию памяти. Регистры процессора и кеш — наносекунды. Оперативная память — десятки наносекунд. А вот обращение к накопителю — совсем другой порядок: у обычного жёсткого диска (HDD) случайное чтение занимает миллисекунды, то есть в миллионы раз медленнее памяти. SSD намного быстрее HDD, но всё равно на порядки уступает оперативной памяти. Эта пропасть и определяет инженерию СУБД: пока данные в памяти — всё летает; как только нужно идти на диск — мы платим огромную цену. Отсюда два следствия, на которых стоит вся производительность баз данных: во-первых, читать с диска нужно как можно реже (для этого — буферный кеш); во-вторых, когда уж читаем, брать сразу полезный блок целиком (для этого — страницы). Все дальнейшие приёмы — индексы, кеширование, выбор организации — это, по сути, способы сократить число дорогих походов на диск.

От строк к страницам

СУБД не хранит строки «россыпью». Строки таблицы упакованы в страницы — блоки фиксированного размера. На одной странице помещается много строк (сколько именно — зависит от их размера). Когда нужно прочитать строку, СУБД читает с диска всю страницу, в которой та лежит. Это ключевой факт: единица ввода-вывода — страница, а не строка. Поэтому, если нужные строки разбросаны по многим страницам, чтений будет много; если собраны на немногих — мало.

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

Что лежит внутри страницы

Заглянем внутрь страницы чуть глубже — это проясняет несколько практических эффектов. Страница состоит из заголовка (служебные данные: сколько строк, сколько свободного места), области строк и «каталога слотов» — маленькой таблички указателей, говорящей, где внутри страницы лежит каждая строка. Зачем такая косвенность? Чтобы можно было перемещать строки внутри страницы (например, при их изменении в размере), не ломая ссылки на них: внешний указатель ведёт на слот, а слот — на актуальное место строки. Отсюда следствия. Во-первых, на странице есть свободное место, и СУБД часто оставляет его про запас (fill factor), чтобы будущие обновления не вытесняли строку на другую страницу. Во-вторых, когда строка вырастает и перестаёт помещаться, её могут перенести, оставив «пересылку», — это удорожает доступ. Эти детали объясняют, почему таблицы со временем «распухают» и почему их периодически реорганизуют. Знать о них не обязательно для повседневной работы, но они снимают ореол загадочности с физического уровня.

Способы организации таблицы

Как именно строки разложены по страницам — это способ организации файла. Три классических варианта:

Куча — самый простой случай: новые строки дописываются в конец. Вставка быстрая, но поиск конкретной строки требует, в худшем случае, прочитать все страницы (полное сканирование). Упорядоченный файл держит строки отсортированными, что ускоряет поиск по диапазону, но замедляет вставку (нужно вставлять «в середину»). Хеш-файл мгновенно находит страницу по точному ключу, но бесполезен для диапазонов и сортировки.

Строковое и колоночное хранение

Стоит упомянуть фундаментальную развилку в том, как раскладывать таблицу. Строковое хранение (row store) держит все поля одной строки рядом: прочитал страницу — получил целые строки. Это идеально для типичной транзакционной нагрузки, где работают со строкой целиком: «покажи весь заказ», «обнови этого клиента». Колоночное хранение (column store) раскладывает данные по столбцам: все значения cena лежат вместе, все city — вместе. Это проигрывает на «возьми всю строку», но выигрывает на аналитике вида «средняя цена по всем заказам»: нужен только столбец cena, и читается лишь он, а не вся таблица. Плюс однотипные значения в столбце прекрасно сжимаются. Поэтому транзакционные системы (OLTP) обычно строковые, а аналитические (OLAP, хранилища данных) — колоночные. Выбор раскладки — стратегическое решение под характер нагрузки, и оно напрямую вытекает из того, что единица чтения — страница: важно, чтобы на читаемой странице оказалось как можно больше нужного и как можно меньше лишнего.

Буферный кеш

Поскольку диск медленный, СУБД держит в оперативной памяти буферный кеш (buffer pool) — область, куда подгружаются недавно использованные страницы. Запрос сначала ищет страницу в кеше; если она там (попадание, cache hit) — диск не трогаем, и это быстро. Если нет (промах) — читаем с диска и кладём в кеш, вытесняя давно не использованные страницы. Поэтому повторный запрос к тем же данным часто намного быстрее первого: данные уже в памяти.

Запись тоже идёт через кеш: изменённая («грязная») страница сначала меняется в памяти, а на диск сбрасывается позже — но, как мы знаем из темы про WAL, журнал изменения записывается на диск сразу, чтобы не потерять данные при сбое.

Кластеризация: почему важно, что лежит рядом

Раз единица чтения — страница, критично, какие строки оказались на одной странице. Это свойство называют кластеризацией, или локальностью. Представьте запрос «все заказы клиента №5». Если заказы этого клиента физически разбросаны по сотне разных страниц, понадобится сто чтений. Если же они лежат рядом, на двух-трёх страницах (потому что таблица упорядочена по клиенту), хватит трёх чтений. Один и тот же логический запрос — разная стоимость, и разница лишь в физической раскладке. Многие СУБД позволяют управлять кластеризацией: например, держать таблицу физически отсортированной по часто используемому ключу (кластеризованный индекс). Идея кластеризации объясняет, почему «одинаковые» по логике запросы могут отличаться по скорости в десятки раз: дело не в самом запросе, а в том, насколько удачно нужные данные собраны вместе на диске.

Почему это диктует производительность

Сведём воедино. Стоимость запроса в первом приближении — это число страниц, которые пришлось прочитать с диска. Полное сканирование таблицы в куче читает все её страницы — это дорого для большой таблицы, даже если нужна одна строка. Вот почему «найти клиента по email» в таблице из миллиона строк без индекса означает прочитать миллион строк (тысячи страниц). Индекс существует именно для того, чтобы вместо полного сканирования прочитать несколько страниц — об этом следующий урок.

CREATE TABLE clients (id INTEGER PRIMARY KEY, email TEXT, city TEXT);
INSERT INTO clients VALUES
  (1,'[email protected]','Москва'),
  (2,'[email protected]','Казань'),
  (3,'[email protected]','Москва');

-- без индекса по city этот поиск читает все строки (полное сканирование)
SELECT id, email FROM clients WHERE city = 'Москва';

Вывод: две строки — клиенты 1 и 3. На трёх строках это мгновенно, но на миллионе без индекса по city СУБД прошла бы все страницы таблицы.

Типичные ошибки понимания

• Думают, что СУБД читает по одной строке. Единица ввода-вывода — страница; читается весь блок целиком.
• Игнорируют разницу диск/память. Дисковое чтение на порядки дороже; именно оно — узкое место, а не процессор.
• Не учитывают буферный кеш. Сравнивают «холодный» и «горячий» запрос и удивляются разной скорости.
• Ждут от кучи быстрого поиска. Куча хороша для вставки; поиск без индекса в ней — полное сканирование.

Итог

• Данные хранятся страницами фиксированного размера; единица обмена с диском — страница, а не строка.
• Организация файла (куча, упорядоченный, хеш) определяет, что будет быстрым: вставка, диапазон или точный поиск.
• Буферный кеш держит горячие страницы в памяти, поэтому повторные запросы быстрее.
• Стоимость запроса в первом приближении — число прочитанных с диска страниц; полное сканирование большой таблицы дорого.