Мотивация

Планирование порядка Join операторов является NP-сложной задачей, и может быть решена только приблизительно. Коммерческие СУБД зачастую делают полный перебор доступных комбинаций для простых запросов, но переключаются на greedy эвристики по мере того, как количество таблиц в запросе возрастает. Неоптимальная реализация планирования Join операторов может привести к существенному замедлению планировщика, и неоправданному возрастанию latency запросов.

Планирование порядка Join в Trino реализовано с помощью простого top-down алгоритма, который является неэффективным. Мы регулярно наблюдаем, что планирование порядка Join в даже в умеренно сложных запросах может превышать 1s.

Необходимо разработать более совершенный алгоритм планирования порядка Join для уменьшения latency планирования.

Решение

1. Для простых запросов - применить эффективный алгоритм исчерпывающего перебора порядка Join-ов, который учитывает топологию Join-графа. Кандидаты: DPSub, TDMinCutConservative.
2. Для сложных запросов - сделать fallback на greedy алгоритм со сложностью не более O(N^2). Например, мы видели, что соответствующий алгоритм Apachе Calcite демонстрирует достаточно хорошую точность при крайне малом времени выполнения.