Join reordering: enumeration и стратегии

Запрос с пятью таблицами в JOIN вы пишете в каком-то порядке — но этот порядок почти никогда не оптимален для исполнения. Порядок джойнов определяет, какие промежуточные результаты возникают по дороге, а их размеры различаются на порядки. Один порядок породит промежуточную таблицу в миллиард строк, другой — в тысячу. Это разница между «запрос за секунды» и «запрос упал по памяти».

Хорошая новость: вы не обязаны угадывать порядок. CBO сам переупорядочивает джойны — это называется join reordering. Этот урок — про то, как именно он это делает: про перебор вариантов (enumeration), про роль статистики и про свойство, которым поведением reordering управляют.

Почему порядок джойнов решает всё

Join по своей природе ассоциативен и коммутативен: (A join B) join C даёт тот же результат, что A join (B join C) или (B join C) join A. Результат один, а вот стоимость пути к нему — разная.

Корень в том, что джойн часто раздувает или сжимает данные. Join большой fact-таблицы с маленькой отфильтрованной dimension-таблицей по селективному условию может схлопнуть миллиард строк в тысячу. А join двух таблиц без селективного условия, по столбцу с малым NDV, наоборот раздувает результат.

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

Цель join reordering — найти порядок, при котором промежуточные результаты как можно меньше: сжимать данные рано, раздувать поздно или не раздувать вовсе.

Enumeration: перебор вариантов под оценку стоимости

Как CBO находит хороший порядок. Он перебирает возможные порядки джойнов и для каждого оценивает стоимость по статистике — это и есть join enumeration.

Механика для каждого варианта порядка:

1. Взять порядок джойнов — например, сначала A join C, потом результат join B.
2. По статистике (row count, NDV, селективность предикатов) оценить кардинальность каждого промежуточного результата — сколько строк даст A join C, сколько даст следующий джойн.
3. Из кардинальностей и размеров вывести стоимость: сколько CPU, памяти, сетевого обмена потребует этот порядок.
4. Сравнить с другими вариантами, в конце выбрать самый дешёвый.

Здесь видно, почему предыдущие два урока были фундаментом. Шаг 2 целиком держится на статистике. Нет статистики — нет оценки кардинальности — enumeration сравнивает варианты вслепую, и «лучший» выбирается наугад. Точность join reordering ровно настолько хороша, насколько точна статистика, поданная коннектором.

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

Стратегии: join-reordering-strategy

Поведением join reordering управляет одно свойство. Конфигурационное — optimizer.join-reordering-strategy, сессионное — join_reordering_strategy. У него три значения.

AUTOMATIC — значение по умолчанию. Полноценное cost-based reordering: CBO делает enumeration и выбирает порядок по оценке стоимости из статистики. Это режим, который и описан выше, и именно его держат включённым в нормальной ситуации.

ELIMINATE_CROSS_JOINS — более скромный режим. CBO переупорядочивает джойны только чтобы избежать cross join (декартова произведения). Cross join — соединение без условия, дающее каждую пару строк: для таблиц на миллион и миллион строк это триллион строк, катастрофа. Этот режим не делает полную cost-based enumeration, а лишь следит, чтобы порядок не порождал cross join там, где его можно избежать.

NONE — reordering выключен. Джойны исполняются ровно в том синтаксическом порядке, в каком написаны в запросе. CBO не вмешивается в порядок вообще.

Что происходит без статистики

Ключевой момент, связывающий урок с предыдущими. AUTOMATIC требует статистики — на ней держится оценка кардинальности в enumeration. Что если статистики нет?

CBO в режиме AUTOMATIC при отсутствии статистики не пытается перебирать варианты вслепую — это бессмысленно, оценить их всё равно нечем. Вместо этого он откатывается к ELIMINATE_CROSS_JOINS: раз cost-based выбор невозможен, делается хотя бы безопасный минимум — не порождать декартовых произведений. Полная оптимизация порядка при этом не происходит.

Это объясняет частую картину: запрос с джойнами вдруг работает плохо, хотя join-reordering-strategy стоит в AUTOMATIC. Формально режим правильный, но фактически он деградировал до ELIMINATE_CROSS_JOINS, потому что статистики нет. Лечится это не подкруткой стратегии, а сбором статистики — ANALYZE, — после которой AUTOMATIC заработает в полную силу.

Зафиксируем, почему откат к ELIMINATE_CROSS_JOINS, а не, скажем, к синтаксическому порядку, — разумный выбор разработчиков Trino. Cross join — это худший из возможных исходов: соединение без условия порождает декартово произведение, и для таблиц на миллион и миллион строк это триллион строк промежуточного результата, который почти наверняка убьёт запрос по памяти или по времени. Синтаксический порядок (NONE) этого не предотвращает — если в запросе таблицы перечислены так, что наивный порядок ведёт к cross join, он его и породит. ELIMINATE_CROSS_JOINS же гарантирует: каким бы плохим ни был порядок, катастрофы декартова произведения не будет. То есть при потере статистики CBO жертвует оптимизацией, но удерживает страховку от наихудшего сценария. Это та же логика «защита худшего случая важнее оптимизации в среднем», что и у anti-starvation в планировщике сплитов.

Практический вывод для инженера. Видя медленный многотабличный запрос, не спешите переключать join-reordering-strategy — почти всегда проблема не в стратегии, а в её голодании по статистике. Стратегия — последнее, что трогают; статистика — первое, что проверяют.

Как увидеть результат reordering

Порядок джойнов в итоговом плане виден в EXPLAIN. Сравнив EXPLAIN до и после ANALYZE, можно прямо наблюдать, как сбор статистики меняет выбранный порядок. В выводе EXPLAIN join-узлы образуют дерево, и порядок их вложенности — это и есть порядок исполнения джойнов:

EXPLAIN
SELECT c.name, sum(o.totalprice)
FROM tpch.sf1.customer c
JOIN tpch.sf1.orders o ON c.custkey = o.custkey
JOIN tpch.sf1.nation n ON c.nationkey = n.nationkey
WHERE n.name = 'GERMANY'
GROUP BY c.name;

В плане видно, что CBO, зная про селективный фильтр n.name = 'GERMANY', скорее всего сначала соединит customer с маленькой отфильтрованной nation (резко сузив набор клиентов), и лишь потом присоединит крупную orders. Порядок в EXPLAIN может отличаться от порядка в тексте JOIN — это и есть видимый результат join reordering.

Попробуй сам

На песочнице курса (Trino 481):

1. Возьмите EXPLAIN для трёхтабличного запроса выше (customer join orders join nation с фильтром по nation). Найдите в плане join-узлы и определите, в каком порядке CBO решил джойнить таблицы. Сравните этот порядок с порядком в тексте запроса.

2. Выполните тот же EXPLAIN, но добавив в начало SET SESSION join_reordering_strategy = 'NONE';. Сравните план с предыдущим: изменился ли порядок джойнов. Объясните, что именно делает режим NONE и почему план стал соответствовать тексту запроса. Затем верните AUTOMATIC.

3. Рассуждение в двух абзацах. Первый: почему перебрать все возможные порядки джойна, скажем, пятнадцати таблиц нереально и что CBO делает вместо полного перебора. Второй: почему запрос с джойнами может работать плохо, даже когда join-reordering-strategy стоит в AUTOMATIC, и какой первый шаг диагностики.