Join order optimization: алгоритм DPccp и статистика

Из всех решений оптимизатора порядок соединения таблиц влияет на скорость сильнее всего. Запрос с пятью join-ами можно исполнить тысячами способов, и разница между лучшим и худшим порядком — это не проценты, а порядки величины: один план обрабатывает миллион промежуточных строк, другой — триллион. Этот урок разбирает, как DuckDB решает задачу join ordering: что такое граф соединений, почему наивный перебор невозможен, и как алгоритм DPccp находит оптимум за разумное время.

Это единственный по-настоящему cost-based проход оптимизатора, и потому самый чувствительный к качеству статистики.

Trino: join distribution — BROADCAST против PARTITIONED Понимание его механики объясняет, почему иногда полезно пересобрать статистику и как читать оценки кардинальности в EXPLAIN.

Почему порядок join критичен

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

Рассмотрим три таблицы: orders (10 млн строк), customers (100 тыс строк), countries (200 строк). Запрос соединяет все три, и есть фильтр countries.region = 'EU', который оставляет 50 стран.

Хороший порядок начинает с того, что фильтр уже урезал countries до 50 строк; join с customers даёт мелкий промежуточный результат, и только в конце подключается большая orders. Плохой — соединяет две большие таблицы первыми. Логически результат одинаков, по стоимости — разница в сотни раз.

Граф соединений

Чтобы рассуждать о порядке формально, оптимизатор строит граф соединений (join graph). Вершины — таблицы, рёбра — условия соединения между ними. Запрос

SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.id
JOIN countries n ON c.country_id = n.id
JOIN line_items l ON l.order_id = o.id;

даёт такой граф:

Задача join ordering — найти такое дерево соединений на этом графе, чтобы суммарная стоимость была минимальной. Дерево должно соединять только связанные рёбрами подмножества (иначе получается декартово произведение — обычно катастрофа по стоимости).

Почему наивный перебор невозможен

Сколько вообще существует порядков? Для соединения n таблиц число возможных деревьев соединений растёт сверхэкспоненциально. Даже если ограничиться только «левоглубокими» деревьями (left-deep trees, где каждый новый join добавляет одну таблицу), число перестановок — n!.

Полный перебор всех деревьев для 12 таблиц — сотни миллионов вариантов, и это без учёта bushy-деревьев (где соединяются два промежуточных результата). Перебирать каждый и считать его стоимость нереально. Нужен алгоритм умнее перебора.

Динамическое программирование: ключевая идея

Спасает динамическое программирование. Наблюдение: оптимальный план для большого множества таблиц строится из оптимальных планов для его подмножеств. Если мы знаем лучший способ соединить {orders, customers} и лучший способ обработать {countries}, то лучший способ соединить {orders, customers, countries} — это какая-то комбинация уже найденных оптимальных подпланов, а не что-то, требующее перебора заново.

Алгоритм идёт снизу вверх. Сначала находит оптимальные «планы» для одиночных таблиц (тривиально — это просто скан). Затем для всех пар связанных таблиц. Затем для троек, используя уже посчитанные пары. И так далее, пока не построит оптимальный план для всего множества. Каждый промежуточный результат запоминается в таблице (мемоизация), чтобы не считать дважды.

DPccp: динамика по связным подграфам

Простое динамическое программирование всё ещё рассматривало бы много бесполезных комбинаций — например, подмножества таблиц, не связанные рёбрами (они дали бы декартово произведение). DuckDB использует более тонкий алгоритм — DPccp (Dynamic Programming connected subgraph complement pairs).

Идея в названии. DPccp перечисляет не все подмножества вершин, а только связные подграфы (connected subgraphs) графа соединений, и для каждого — его дополнения-пары (complement pairs), которые тоже связны. То есть алгоритм рассматривает только те разбиения множества таблиц на два join-аргумента, где обе части связны рёбрами и соединение между ними существует. Декартовы произведения в перечисление просто не попадают.

Это даёт огромную экономию: для типичных «цепочечных» и «звёздных» графов соединений (а реальные запросы почти всегда такие) число связных подграфов на порядки меньше числа всех подмножеств. DPccp находит гарантированно оптимальный порядок (в рамках модели стоимости), перебирая при этом лишь осмысленные варианты. Алгоритм описан в работе Moerkotte и Neumann «Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees» (2006) и считается стандартом для join-ordering.

Роль статистики

DPccp — это процедура поиска, но искать она может только при наличии функции стоимости. А стоимость плана определяется размерами промежуточных результатов, то есть оценками кардинальности: сколько строк выдаст каждый join.

Кардинальность оценивается по статистике, которую DuckDB ведёт для таблиц:

• Число строк в каждой таблице.
• Zonemap-статистика по колонкам — min/max значений в сегментах, по которой оценивается селективность фильтров.
• Оценка числа уникальных значений в колонке, влияющая на оценку результата join.

Из этого оптимизатор оценивает: фильтр region = 'EU' оставит примерно столько-то строк; join по такому-то ключу размножит/сократит результат во столько-то раз. Эти оценки складываются в стоимость плана, и DPccp выбирает план с минимальной стоимостью.

Критическая зависимость: порядок join хорош ровно настолько, насколько точны оценки кардинальности. Если статистика говорит «после фильтра останется 100 строк», а реально остаётся миллион, оптимизатор выберет план под 100 строк — и тот окажется плохим для миллиона.

-- Оценки кардинальности видны в плане:
EXPLAIN
SELECT count(*)
FROM orders o JOIN customers c ON o.customer_id = c.id
WHERE c.country = 'DE';

В выводе EXPLAIN у каждого оператора есть строка EC (estimated cardinality) — оценочное число строк. EXPLAIN ANALYZE рядом покажет фактическое. Большое расхождение между ними — главный признак, что оптимизатор работал с плохой статистикой и порядок join мог получиться неоптимальным.

Что делать с плохими оценками

Если EXPLAIN ANALYZE показывает сильное расхождение оценок с фактом и запрос медленный из-за порядка join:

1. Внешние файлы. При запросах к Parquet/CSV напрямую DuckDB опирается на метаданные файла; для CSV они беднее, чем для нативных таблиц. Загрузка данных в нативную таблицу даёт оптимизатору полноценную статистику.
2. Сложные коррелированные фильтры. Оценки селективности предполагают независимость условий. Если WHERE a = 1 AND b = 2 сильно коррелируют, оценка будет неточной — это известное ограничение почти всех оптимизаторов.
3. Диагностика отключением. PRAGMA disable_optimizer уберёт и переупорядочивание join; сравнив планы, вы поймёте, виноват ли именно join order.

Важно: в подавляющем большинстве запросов DPccp с обычной статистикой выбирает хороший порядок автоматически, и вмешиваться не нужно. Ручная диагностика join order — инструмент для редких проблемных запросов, а не рутина.

Попробуй сам

1. Создай три таблицы разного размера: big (1 млн строк через range), mid (50 тыс строк), small (500 строк). Свяжи их числовыми ключами так, чтобы каждая строка одной соединялась с одной строкой другой.
2. Напиши запрос, соединяющий все три с фильтром на small (например, WHERE small.id < 50). Выполни EXPLAIN и определи, в каком порядке оптимизатор поставил join-ы. Начал ли он с отфильтрованной мелкой таблицы?
3. Найди в плане строки EC (estimated cardinality) у каждого join. Затем выполни EXPLAIN ANALYZE и сравни EC с фактическим числом строк. Насколько точны оценки?
4. Подумай: если бы фильтр на small был не id < 50, а сложным коррелированным условием по двум колонкам, как это могло бы повлиять на точность оценки кардинальности и, как следствие, на выбранный порядок join?