Почему Trino такой быстрый: архитектура оптимизатора SQL-запросов

Сложный вопрос :-)

Оптимизатор формирует базовую структуру плана. После этого план разбивается на так называемые фрагменты по границам Exchange. Фрагмент - это набор операторов, которые могут быть выполнены независимо.

Далее фрагменты бьются на так называемые пайплайны по границам блокирующих операторов. Например, Join. Каждый пайплайн имеет не более одного входа (таблица или корень другого фрагмента).

Описания пайплайнов рассылаются по узлам, что бы каждый узел знал, какие операции принадлежат какому пайплайну. В терминах Trino эта метаинформация называется Task.

А далее становится интересно. Trino бьет входные данные таблиц на независимые куски, называемые Split. Каждый сплит отправляется на тот или иной узел в зависимости от загрузки узла или требований плана (например, для выполнения колоцированного джоина может потребоваться группировать сплиты по узлам особым образом). Аналогично перераспределяются и сплиты, произведенные промежуточными фрагментами.

Мы в некоторой степени описали этот процесс в другом блоге https://www.cedrusdata.ru/blog/trino-massively-parallel-processing, но вообще это заслуживет отдельной статьи.

В итоге — сам план статичен, но на каких узлах выполняются отдельные его части определяется в рантайме, в зависимости от загрузки узлов и требований операторов.

Кроме того, недавно в Trino был добавлен так называемый fault-tolerant execution (aka "project Tardigrade" https://trino.io/blog/2022/05/05/tardigrade-launch.html). Он позволяет перезапускать определенные части плана в случае ошибок. Благодаря этой фиче появляются некоторые точки в коде, где можно прямо в рантайме перехватить кусочек плана и как-то его поменять. Это дает возможность делать реоптимизацию планов (по некоторым заранее определенным границам) в рантайме. Однако в том самом месте, где происходит реоптимизация сейчас стоит заглушка, мол, "вставляйте сюда код runtime-реоптимизации, если хотите" :-)