JOIN — не дорогая операция: бенчмарк на миллиарде строк это доказывает

Вы наверняка слышали: «JOIN — это дорого, сделайте одну большую таблицу». Это заблуждение — одно из самых живучих в мире баз данных. Особенно часто его повторяют те, кто продвигает Data Lake и подход «One Big Table» (OBT). Но так ли это на самом деле?

Автор блога Database Doctor провёл серию бенчмарков на DuckDB и PostgreSQL (подробнее о нём — в нашем гайде по PostgreSQL), сравнив классическую размерную модель (dimensional model) с подходом «One Big Table». Результаты оказались неожиданными для многих — JOIN не просто «не дорогой», он зачастую быстрее плоской таблицы.

Постановка эксперимента

Рассмотрим два конкурирующих подхода к моделированию данных:

• Размерная модель (dimensional model) — атрибуты продуктов хранятся в отдельной таблице product, и мы делаем JOIN с таблицей sales каждый раз при чтении
• One Big Table (OBT) — все атрибуты продуктов заранее «вклеены» в таблицу sales_obt, и мы читаем данные через SELECT без JOIN

Очевидно, что вторую таблицу дороже строить в ETL-пайплайне. Но какая из них потребляет меньше CPU при чтении?

Размерная модель

Схема данных:

			CREATE TABLE product (
    id_product INT NOT NULL PRIMARY KEY
    , c01 VARCHAR
    , c02 VARCHAR
    ...
    , c20 VARCHAR
)

CREATE TABLE sales (
    k INT       /* Уникальное значение для доступа к строкам */
    , v DOUBLE  /* Значение для агрегации */
    , id_product INT NOT NULL REFERENCES product(id_product)
);
		

Здесь c01 ... c20 — строковые колонки с атрибутами продуктов. Кардинальности:

• product — 100 000 строк; каждая из колонок c01–c20 содержит ~100 уникальных значений (MD5-хеши)
• sales — 1 миллиард строк со случайным v и равномерно распределённым id_product

Эта модель, где сущность (product) хранится отдельно от фактов (sales), называется размерной моделью (dimensional model). Подробнее о ней — в конце статьи.

Генерация тестовых данных

Сначала создаём seed-таблицу — универсальный способ генерации последовательности чисел, который работает практически на всех SQL-платформах:

			CREATE TABLE seed10 (
   n INT NOT NULL
);

INSERT INTO seed10
SELECT 0 AS n
UNION ALL SELECT 1 AS n
UNION ALL SELECT 2 AS n
UNION ALL SELECT 3 AS n
UNION ALL SELECT 4 AS n
UNION ALL SELECT 5 AS n
UNION ALL SELECT 6 AS n
UNION ALL SELECT 7 AS n
UNION ALL SELECT 8 AS n
UNION ALL SELECT 9 AS n;
		

Примечание: да, можно было бы использовать INSERT ... VALUES с несколькими кортежами, но не каждая аналитическая БД поддерживает этот синтаксис. Зато UNION ALL работает, кажется, вообще везде.

С помощью seed-таблицы генерируем миллиард строк для sales:

			CREATE TABLE sales AS
SELECT
      CAST(random() * 99999 + 1 AS INT) AS id_product
    , random() AS v
FROM seed10 S
   , seed10 P10
   , seed10 P100
   , seed10 P1000
   , seed10 P10000
   , seed10 P100000
   , seed10 P1000000
   , seed10 P10000000
   , seed10 P100000000
;
		

Таблицу product заполняем MD5-хешами для получения строковых значений с контролируемой кардинальностью:

			CREATE TABLE product AS
SELECT ROW_NUMBER() OVER () AS id_product
    , md5(CAST(1000 + CAST(random()*100 AS INT) AS VARCHAR(32))) AS c01
    , md5(CAST(2000 + CAST(random()*100 AS INT) AS VARCHAR(32))) AS c02
    , md5(CAST(3000 + CAST(random()*100 AS INT) AS VARCHAR(32))) AS c03
    ...
    , md5(CAST(20000+ CAST(random()*100 AS INT) AS VARCHAR(32))) AS c20
FROM (SELECT 1 FROM sales LIMIT 100000);
		

Примечание: да, можно было бы взять ровно 100 различных значений вместо ~101 для c01–c20, но с приведённым выше кодом проще.

Модель «One Big Table»

На другой стороне ринга — заранее объединённая широкая таблица:

			CREATE TABLE sales_obt AS
SELECT v
     , c01, c02, c03, c04, c05
     , c06, c07, c08, c09, c10
     , c11, c12, c13, c14, c15
     , c16, c17, c18, c19, c20
FROM sales JOIN product USING (id_product);
		

Гипотеза: JOIN медленнее, чем плоская таблица

Итак, вопрос: что быстрее?

Размерная модель с JOIN:

			SELECT v, c01 ... cN
FROM sales
JOIN product USING (id_product)
		

Или OBT без JOIN:

			SELECT v, c01 ... cN
FROM sales_obt
		

Если «JOIN — это дорого», то размерная модель должна быть медленнее. Мы также должны увидеть более высокое потребление CPU.

Чтобы быть максимально нечестным по отношению к размерной модели, автор запускает тесты на системе, где вся база помещается в оперативную память. Так мы моделируем «бесконечный I/O» и не платим за дисковые операции.

Результаты DuckDB

Тестовая машина: ноутбук с 14 ядрами, 32 ГБ RAM, SSD на 3 ГБ/с. Размер базы — 45 ГБ, из которых sales_obt занимает ~40 ГБ. DuckDB отлично утилизирует ядра: CPU загружен на 100% во время выполнения запросов.

Для тестов автор использовал серию запросов с нарастающим числом колонок:

			EXPLAIN ANALYZE
SELECT v
     ... c01.... cN
		

Примечание: DuckDB использует написание EXPLAIN ANALYZE (а не ANALYSE). В оригинале автор шутит, что DuckDB «правильно» использует британское написание — но на самом деле в DuckDB работает американский вариант.

Базовый замер (measurement 0) — просто чтение v: мы платим за JOIN, но не запрашиваем колонки из product. Читатели, которых интересует эта крайняя ситуация и способы оптимизации, могут изучить тему join elimination в планировщиках запросов. Каждый запрос выполняется трижды, берётся лучшее время.

Время выполнения (wall clock)

Время выполнения: размерная модель (Dim) vs One Big Table (OBT) в DuckDB

Выводы из графика:

• При запросе 1–2 колонок OBT незначительно быстрее
• С ростом числа колонок стоимость OBT взлетает — до 15 секунд при 20 колонках
• JOIN остаётся практически константным по времени (~1 секунда) независимо от числа колонок
• Рост OBT напоминает O(n log n) — нелинейная зависимость

Потребление CPU

DuckDB позволяет замерить CPU-время по каждому оператору в запросе:

Потребление CPU: OBT vs Dim (CPU по всем ядрам суммарно). Для размерной модели показаны stacked-значения: scan + join

Та же закономерность: OBT при 20 колонках потребляет ~200 секунд CPU, тогда как размерная модель — всего ~15 секунд (scan + join). Разница — на порядок.

Почему JOIN быстрее при масштабировании?

Казалось бы, мы читаем каждую строку. Почему не быстрее просто отдать её из плоской таблицы?

Ответ кроется в том, как работают колоночные хранилища (DuckDB, Parquet и другие):

1. Декомпрессия колонок. Сжатые строки хранятся в словаре (dictionary encoding). Чтобы получить данные, движок «соединяет» указатели в сегментах сжатия со словарём. Это по сути тоже своего рода JOIN — но уже внутри Storage Engine. В размерной модели строки уже «материализованы» в таблице product, и эта «декомпрессия» фактически заранее выполнена
2. Сборка строк из колонок. В колоночном формате данные каждой колонки хранятся отдельно. Чтобы собрать строку, нужно пройти по метаданным, найти местоположение каждой колонки и скопировать данные в финальный результат. Каждая колонка — это отдельная аллокация (и деаллокация) памяти. Именно этот механизм, вероятно, и даёт нелинейный рост стоимости сканирования широкой OBT-таблицы

А что насчёт строковых хранилищ?

Не все базы данных используют колоночное сжатие. Строковые хранилища (row stores) хранят данные в формате строк (аналогично AVRO в мире Data Lake).

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

Вопрос: может быть, для OBT лучше использовать строковое хранилище? Давайте проверим.

Гипотеза автора

В пользу OBT в строковом хранилище:

• Данные можно отдать напрямую, без «сборки» строк из колонок
• Не нужна «неявная декомпрессия» сжатых строк
• JOIN на строковых форматах медленнее, чем на колоночных — нельзя векторизовать хеширование

В пользу JOIN:

• Если нужна часть колонок, проекция (отбрасывание ненужных) стоит CPU — это неявный memcpy
• Больший объём данных при сканировании — больше работы с буферами
• У JOIN лучше кеш-локальность для строк — меньше TLB-промахов

Интуиция автора подсказывает, что строковые хранилища могут сдвинуть «точку пересечения» дальше от одной колонки и дать больше преимуществ OBT — хотя бы потому, что не нужна «сборка» строки. Давайте проверим.

Тест на PostgreSQL 17

Для теста автор выбрал PostgreSQL 17 — классическое строковое хранилище. Датасет уменьшен до 1% (10 млн строк в sales, 10 000 строк в product), но и так sales_obt занимает 7 ГБ.

Чтобы убрать стоимость сериализации результата для клиента, вместо SELECT * используется:

Примечание: PostgreSQL сериализует результат в клиентский формат даже при EXPLAIN ANALYZE. Это дополнительная работа, которой лишены системы, использующие Arrow-буферы, — там промежуточная сериализация не нужна.

			EXPLAIN ANALYSE
SELECT COUNT(v), COUNT(c01), ... FROM sales_obt;
		

Чтобы убедиться, что PostgreSQL не «хитрит» с NULL-проверкой в COUNT, автор проверил план выполнения. Видно, что агрегат действительно работает со строкой, ширина которой пропорциональна числу входных колонок:

			->  Partial Aggregate
    (cost=977304.00..977304.01 rows=1 width=16)
    (actual time=1566.693..1566.694 rows=1 loops=3)
		

Время выполнения: PostgreSQL OBT vs JOIN (строковое хранилище)

Выводы:

• Как и предполагалось, стоимость «проекции» (отбрасывания ненужных колонок) доминирует при малом числе колонок — OBT проигрывает
• Вопреки ожиданиям, даже в базовом случае (0 колонок из JOIN) размерная модель оказывается быстрее
• Красивая линейная зависимость: строковое хранилище масштабируется предсказуемо в обоих случаях
• JOIN выигрывает или проигрывает OBT с минимальной разницей — но тренд в пользу JOIN

Глубокое погружение: что именно тормозит PostgreSQL?

С помощью EXPLAIN (ANALYZE, BUFFERS) автор убедился, что запрос работает полностью в памяти:

			Aggregate  (cost=1434136.80..1434136.81 rows=1 width=136)
         (actual time=5645.133..5645.134 rows=1 loops=1)
  Buffers: shared hit=909120
  ->  Seq Scan on sales_obt
     (cost=0.00..1009123.20 rows=10000320 width=536)
     (actual time=0.017..1161.646 rows=10000000 loops=1)
        Buffers: shared hit=909120
		

shared hit=909120 означает, что все буферы были прочитаны из памяти (shared buffers), без обращения к диску. PostgreSQL форкает процесс на каждое соединение, поэтому профилировать конкретный запрос можно через SELECT pg_backend_pid().

Автор использовал Windows Performance Recorder для профилирования PostgreSQL на 16-колоночном запросе:

Трассировка PostgreSQL: горячие функции при сканировании OBT

Два самых горячих вызова:

1. tts_buffer_heap_getsomeattrs (файл execTuples.c) — по сути, неоптимальный memcpy. Эта функция копирует данные из буферного пула в представление кортежа. Именно та «проекция», которую автор предсказывал — но реализованная неэффективно
2. ExecInterpExpr (файл execExprInterp.c) — интерпретатор выражений. Современные БД используют векторизованное или компилированное выполнение; PostgreSQL по умолчанию интерпретирует через гигантский switch-блок (JIT-компиляция через LLVM доступна с PG 11, но не используется на дефолтных настройках для дешёвых запросов). Основной вызывающий — ExecAgg: подсчёт COUNT обходится почти так же дорого, как само чтение данных

Важная оговорка: PostgreSQL — не идеальный представитель строковых хранилищ. Базы данных с компилируемыми запросами могут быть значительно быстрее при «сыром сканировании». Тем не менее, строковые хранилища, похоже, почти всегда выигрывают от использования JOIN — если только вы не планируете выбирать практически все колонки из OBT в каждом запросе. Даже денормализация одной колонки ради экономии CPU может оказаться ошибочной.

Как автор собирал PostgreSQL с отладочными символами

Для профилирования PostgreSQL нужны debug-символы. Ни пакет Chocolatey, ни установщик EnterpriseDB их не включают — пришлось собирать из исходников на Windows.

Необходимые пакеты:

			choco install meson
choco install strawberryperl
choco install winflexbison3
		

Файл msvc.ini в корне репозитория PostgreSQL:

			[binaries]
c = 'cl'
cpp = 'cl'
ar = 'lib'
ld = 'link'

[properties]
c_args = ['/O2', '/Zi']
cpp_args = ['/O2', '/Zi']
c_link_args = ['/DEBUG']
cpp_link_args = ['/DEBUG']

[host_machine]
system = 'windows'
cpu_family = 'x86_x64'
cpu = 'x86_x64'
endian = 'little'
		

Сборка:

			meson setup builddir --native-file=msvc-x64.ini --buildtype=release -Dreadline=disabled
meson compile -C builddir --verbose
		

Размерная модель: уроки прошлого

Всё, что мы наблюдаем, не ново. Ещё в 1996 году Ральф Кимбалл опубликовал книгу «The Data Warehouse Toolkit», которая до сих пор переиздаётся и считается классикой.

Кимбалл аргументировал:

• Большие аналитические таблицы (факты) должны содержать только метрики (то, что агрегируется) и целочисленные ключи измерений (то, по чему делается JOIN)
• Все атрибуты сущностей хранятся в отдельных таблицах измерений (dimension tables), к которым присоединяются через foreign key
• Колонки с высокой кардинальностью и единственным значением лучше хранить прямо в таблице фактов — «вырожденные измерения» (degenerate dimensions). Это идеально соответствует нашему наблюдению: чтение одной колонки через JOIN действительно немного медленнее

Кимбалл также рекомендовал объединять связанные таблицы внутри самого измерения (делая таблицу измерения шире) — но только для измерений, не для фактов. И делал он это не ради производительности, а для упрощения работы оптимизатора запросов.

Итоги

Главный вывод:

«JOIN — НЕ дорогая операция по сравнению с альтернативами»

Что мы выяснили:

• Даже при чтении всех строк JOIN зачастую дешевле, чем сканирование One Big Table
• В колоночных хранилищах (DuckDB) преимущество JOIN проявляется начиная с 4–6 колонок и растёт нелинейно
• В строковых хранилищах (PostgreSQL) JOIN тоже выигрывает на большинстве сценариев
• «Жертвовать диском ради экономии CPU на JOIN» — это миф, который противоречит измерениям
• Размерное моделирование (Кимбалл, 1996) — не устаревшая методология, а эффективный инженерный подход

Важно помнить: мы тестировали JOIN большой таблицы (1 млрд строк) с маленькой (100 000 строк). Что произойдёт при JOIN двух больших таблиц — вопрос для отдельного исследования.

В следующей статье автор обещает разобрать, что происходит с производительностью при добавлении фильтров. Спойлер: разрыв между OBT и JOIN становится ещё больше в пользу JOIN — благодаря bloom-фильтрам и pushdown-оптимизациям.

Перевод и адаптация статьи «Joins are NOT Expensive!» из блога Database Doctor. Если вы хотите глубже разобраться в SQL — рекомендуем нашу шпаргалку по SQL.