Почему surrogate keys ускоряют JOIN: до железа

В уроке 2 мы перечислили преимущества surrogate key и среди них — «узость, быстрый JOIN». Это утверждение легко принять на веру. Но цель этого курса — «до железа»: не верить, а понимать механику. Почему JOIN по узкому целочисленному ключу физически быстрее, чем JOIN по широкому строковому или составному? Ответ лежит на четырёх уровнях: байты, страницы, B-tree индекс, CPU-cache. Пройдём их по порядку.

Договоримся о примере. Сравниваем два варианта ключа таблицы users, на которую через foreign key ссылается таблица orders:

• Вариант A (surrogate): user_id BIGINT — 8 байт.
• Вариант B (natural, составной): (country_code CHAR(2), email VARCHAR(254)) — в среднем, скажем, около 32 байт на строку.

JOIN orders с users по ключу. Где именно вариант A выигрывает.

Уровень 1: байты и сравнение значений

Самый базовый уровень. JOIN постоянно сравнивает значения ключа на равенство: «эта строка orders соответствует этой строке users?». Сколько стоит одно сравнение?

Сравнить два 8-байтных целых — это одна машинная инструкция. Процессор грузит оба числа в регистры и сравнивает за один такт. 64-битный регистр вмещает 8-байтное целое целиком.

Сравнить две строки переменной длины — это посимвольное сравнение (по сути memcmp): цикл, который идёт по байтам, пока не найдёт различие или не дойдёт до конца. Для 32-байтных строк это в разы больше работы, чем одна инструкция. А составной ключ — это ещё и сравнение нескольких столбцов подряд: сначала country_code, потом email.

Сравнение ключей при JOIN:

BIGINT (8 байт):       cmp reg1, reg2     -- 1 инструкция, 1 такт

CHAR(2)+VARCHAR(254):  цикл по ~32 байтам -- десятки тактов,
                       плюс проверка длины, плюс два столбца

JOIN двух таблиц по миллиону строк выполняет миллионы сравнений ключа. Разница «1 инструкция против цикла по 32 байтам» на каждом сравнении складывается в ощутимое время.

Уровень 2: страницы — как СУБД читает диск

Второй уровень — самый важный, и его новички пропускают. СУБД никогда не читает данные построчно. Она читает и пишет диск блоками фиксированного размера — страницами (page, в PostgreSQL — 8 КБ). Минимальная единица ввода-вывода — одна страница. Нужна одна строка — читается вся страница в 8 КБ, где эта строка лежит.

Из этого следует ключевая идея: сколько строк помещается на одну страницу — настолько эффективно чтение. Если на странице больше строк, то одно чтение с диска (один I/O — самая дорогая операция в базе) приносит больше полезных данных.

Теперь посчитаем на нашем примере. Страница 8 КБ = 8192 байта. Упрощённо, без учёта служебных полей:

Страница 8192 байта. Сколько ключей поместится?

BIGINT, 8 байт на ключ:
  8192 / 8   = ~1024 ключа на страницу

Составной natural key, ~32 байта на ключ:
  8192 / 32  = ~256 ключей на страницу

Узкий ключ -> в 4 раза больше ключей на одной странице
           -> в 4 раза меньше страниц нужно прочитать
           -> в 4 раза меньше дорогих операций I/O

Узкий ключ означает: тот же объём ключевых данных умещается в в 4 раза меньшее число страниц. А число прочитанных страниц — это и есть число обращений к диску, главная стоимость в работе СУБД. Это не «немного быстрее» — это кратная разница в I/O.

Уровень 3: B-tree индекс — глубина дерева

JOIN почти всегда использует индекс на ключе. Доминирующий тип индекса в реляционных СУБД — B-tree (точнее, B+ tree). Понять, как ширина ключа влияет на B-tree, — третий уровень.

B-tree — это сбалансированное дерево. У него есть корень, внутренние узлы и листья; данные (или указатели на данные) лежат в листьях. Каждый узел дерева — это одна страница (те самые 8 КБ). Поиск по индексу — это спуск от корня к листу: на каждом уровне читается одна страница, по ней выбирается, в какого ребёнка спускаться.

Стоимость поиска по B-tree = число уровней дерева (его высота), потому что на каждый уровень — одно чтение страницы.

А от чего зависит высота дерева? От того, сколько ключей помещается в один узел — то есть в одну страницу. Это называется fan-out (ветвление): чем больше ключей в узле, тем больше у узла детей, тем «шире» дерево и тем оно ниже при том же числе строк.

И тут вступает уровень 2: узкий ключ -> больше ключей на страницу -> выше fan-out -> ниже дерево.

Таблица на 1 миллиард строк. Высота B-tree:

Узкий ключ (8 байт), fan-out ~1000:
  1000^1 = 1 000           (1 уровень)
  1000^2 = 1 000 000       (2 уровня)
  1000^3 = 1 000 000 000   (3 уровня) -> дерево высотой ~3-4

Широкий ключ (~32 байта), fan-out ~250:
  250^1 = 250
  250^2 = 62 500
  250^3 = 15 625 000
  250^4 = 3 906 250 000    -> дерево высотой ~4-5

Узкий ключ: поиск ~3-4 чтения страниц.
Широкий ключ: поиск ~4-5 чтений страниц.

Разница в 1-2 уровня кажется маленькой. Но JOIN по миллиону строк делает миллион таких спусков по дереву. Лишний уровень = лишний миллион чтений страниц. И это на КАЖДОМ индексе — а индексов в схеме много.

Уровень 4: CPU-cache — последняя миля

Четвёртый, самый глубокий уровень. Допустим, нужная страница уже в оперативной памяти (RAM) — диск не при чём. Узкий ключ всё равно быстрее. Почему?

Между процессором и RAM есть кеш процессора — L1, L2, L3. Это маленькая, но очень быстрая память. Доступ к данным в L1-кеше — несколько тактов; доступ в RAM — сотни тактов. Разница — два порядка.

Процессор подгружает данные из RAM в кеш не байтами, а кеш-линиями — блоками обычно по 64 байта. Запросил процессор 8 байт — в кеш приехали 64 байта (вся линия, куда эти 8 байт попали).

Теперь сравним при сканировании ключей в памяти:

Кеш-линия 64 байта. Сколько ключей в одной линии?

BIGINT, 8 байт:        64 / 8  = 8 ключей в одной кеш-линии
Широкий ключ, 32 байта: 64 / 32 = 2 ключа в одной кеш-линии

Узкий ключ -> 8 ключей подряд читаются из кеша БЕЗ обращения
              к RAM. Высокая cache-hit rate.
Широкий ключ -> кеш-линии «вымываются» в 4 раза чаще,
              больше промахов кеша (cache miss), больше
              дорогих обращений к RAM.

Узкие ключи дают высокую локальность данных: много ключей подряд лежат в одной кеш-линии, процессор обрабатывает их, ни разу не сходив в RAM. Широкие ключи вымывают кеш быстрее — больше cache miss, и каждый miss стоит сотни тактов. На hot-path хеш-джойна (где ключи перебираются массово) это заметно.

Складываем всё вместе

Один JOIN orders с users по ключу выигрывает от узкого surrogate key одновременно на всех четырёх уровнях:

Эти эффекты не складываются арифметически — они перемножаются, и каждый из них масштабируется с размером данных. На таблице в тысячу строк разницы вы не заметите. На таблице в сотни миллионов строк, с десятком индексов и постоянными JOIN-ами — это разница между запросом за секунду и запросом за минуту.

И ещё один эффект, не про производительность, а про стабильность (урок 2): surrogate key не меняется. JOIN всегда идёт по ключу, который не «переедет» при смене email или переименовании страны. Узость даёт скорость, стабильность даёт надёжность — вместе это и есть причина, по которой surrogate key стал стандартом.

Попробуй сам

Поставьте эксперимент в PostgreSQL (он показывает страницы и планы детальнее SQLite).

1. Создайте две версии таблицы customers: customers_int с BIGINT primary key и customers_str с широким текстовым primary key (например, сгенерированная строка из 30+ символов). Налейте в каждую по 100 000 строк.
2. Создайте к каждой дочернюю таблицу orders_* с foreign key и индексом на нём, налейте по 500 000 строк.
3. Выполните EXPLAIN ANALYZE для JOIN orders с customers на обеих версиях. Сравните: время выполнения, тип JOIN, число прочитанных строк.
4. Посмотрите на размер индексов: SELECT pg_size_pretty(pg_relation_size('имя_индекса')). Индекс по широкому ключу будет заметно больше — объясните, почему, через «байты на ключ -> строк на страницу».
5. Проговорите своими словами все четыре уровня (байты, страницы, B-tree, кеш) на примере именно вашего эксперимента. Если можете объяснить разницу в числах плана через эти четыре уровня — вы поняли урок «до железа».