Приветствую!

В «Тантор Лабс» я работаю разработчиком СУБД и закономерно увлекаюсь базами данных. Как-то раз во время пролистывания красной книги во мне что-то щелкнуло, и я захотел глубже поизучать планировщик. Я углубился в алгоритмы соединений таблиц и наткнулся на алгоритм DPhyp, который, как оказалось, используют многие современные (и не очень) базы данных. Стало интересно — а есть ли такое в PostgreSQL? К удивлению, оказалось, что нет. Ну, а если чего-то нет, надо создать самим.

Эта статья не о DPhyp как таковом, а о том, с чем мне пришлось столкнуться в процессе написания соответствующего расширения для PostgreSQL. Но вначале — небольшое введение.

Алгоритмы работы планировщиков запросов

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

SELECT *
FROM t1 
JOIN t2 ON t1.x = t2.x
JOIN t3 ON t2.x = t3.x
JOIN t4 ON t3.x = t4.x;

...имеет 14 возможных комбинаций соединений таблиц. В общем случае — это число возможных представлений бинарного дерева из N узлов, где под узлами понимаются таблицы, число Каталана, которое для 7 таблиц уже равно 429, а для 8 — 1430. Стоит ли говорить, что с определенного момента число это становится настолько огромным, что становится практически невозможно найти оптимальный план простым перебором комбинаций?

То, как мы собираемся выполнять перебор, и определяет наш лагерь архитектуру планировщика: top-down или bottom-up. Подход top-down — это подход "сверху вниз" (его еще называют goal-oriented, ориентированным на цель). Мы заходим в корень, понимаем его "цель" (есть ли группировка или фильтрация, что на выходе и т.д.) и на основании этого создаем план запроса. Преимуществом здесь является то, что у нас на руках есть полный контекст и мы можем его использовать. Примером может служить планировщик (грубо говоря, это архитектура) cascades, который используется в Microsoft SQL Server: он с легкостью может перемещать узлы графа запроса под GROUP-BY, чего другой подход без помощи со стороны сделать не может (архитектура предполагает статический набор отношений для соединения).

Bottom-up ("снизу вверх") — это противоположный лагерь, где вначале планируют все JOIN'ы и только потом "навешивают" сортировку/группировку и другие операторы. Этот подход используются во многих СУБД, включая PostgreSQL. Его преимущество — масштабируемость, так как он позволяет планировать огромное количество JOIN'ов. Например, в статье Adaptive Optimization of Very Large Join Queries представлен подход, который позволяет выполнять планирование запросов с несколькими тысячами таблиц, комбинируя несколько разных алгоритмов. В пример в статье приводится SAP, который из-за постоянного использования представлений внутри других представлений может создать запрос, использующий тысячи обычных таблиц.

Алгоритмов bottom-up существует довольно много. Рассмотрим кратко те, которые используются в PostgreSQL.

DPsize

Во времена рассвета РСУБД никто до конца не понимал, как все должно работать, и делали кто как умеет. Тогда появился первый алгоритм динамического программирования для поиска порядка соединений. Сегодня все (как минимум, в статьях) называют его DPsize.

Вспомним, что такое отношение. На работе с отношениями построена реляционная алгебра, и отношение можно назвать простым источником данных со своей схемой (атрибутами). Самый простой пример отношения – таблица, но другой важный пример — это JOIN, т.к. по факту он отвечает требованиям (дает кортежи и есть атрибуты). Далее я буду использовать термин "отношение", но там, где важно подчеркнуть различие, буду говорить "таблица".

Идея DPsize проста: чтобы создать JOIN из i таблиц отношений, нужно соединить другие отношения, которые в сумме количества таблиц дадут этот i. Например, для 4 нам нужно соединить 1 и 3, 2 и 2. Собственно, в этом и состоит динамическое программирование, когда ответ текущего шага зависит от ответа прошлых, ну а базой выступают отношения размером 1, то есть обычные таблицы. Алгоритм неплохо себя показывает на OLTP-нагрузке, когда таблиц мало, и дает практически оптимальные планы запросов, а проблемы начинаются, когда таблиц становится слишком много.

Как можно заметить, сложность этого алгоритма — экспоненциальная, поскольку на каждом последующем шаге требуется обрабатывать еще больше пар отношений. Разные СУБД борются с этим по-разному, в PostgreSQL стали использовать другой алгоритм.

GEQO

GEQO (Genetic Query Optimizer) — это генетический алгоритм поиска оптимального плана запроса. Если вы попробуете запустить в PostgreSQL запрос сначала на 12 таблиц, а потом на 13, то удивитесь, потому что затраченное время снизилось с нескольких секунд до почти десяти миллисекунд. Почему? Дело в том, что это рандомизированный алгоритм, его работу можно описать так: вначале строим хоть какой-нибудь план запроса, а затем проводим несколько итераций (это определяется конфигурацией), в каждой из которых случайно меняем какие-нибудь узлы, и в следующую итерацию идет план с лучшей стоимостью. Отсюда и название "генетический" ввиду того, что в следующее поколение (итерацию) переходят сильнейшие (то есть в нашем случае — самые дешевые).

DPhyp

Переходим к основной теме — алгоритму DPhyp. DPhyp — это алгоритм динамического программирования для перебора JOIN'ов, его основная идея заключается в том, что сам запрос содержит указания на то, как должно происходить соединение таблиц. Так почему бы его не использовать? Основная проблема — в самом представлении запроса. Ранее я упомянул, что запрос можно представить в виде графа, но можно ли так сделать для целей перебора JOIN'ов? Чтобы понять, в чем трудность, посмотрим на пример из статьи:

SELECT *
FROM R1, R2, R3, R4, R5, R6
WHERE R1.x = R2.x AND R2.x = R3.x AND R4.x = R5.x AND R5.x = R6.x AND
      R1.x + R2.x + R3.x = R4.x + R5.x + R6.x

Да, видим, что есть несколько явно соединенных между собой таблиц — для них мы можем создать ребра в нашем графе (например, R1 - R2), но что делать с последним предикатом, который по факту соединяет множества таблиц? Эту проблему и решает DPhyp — алгоритм динамического программирования (DP), основанный на гиперграфах (hyp — hypergraph). Пугаться не стоит, предполагаю, что вы знакомы с обычным графом — множеством узлов, соединенных между собой ребрами, а вот гиперграф — это множество гиперузлов, соединенных между собой гиперребрами:

• гиперузел (hypernode) — это множество обычных узлов;

• гиперребро (hyperedge) — это ребро, соединяющее 2 гиперузла.

В запросе из примера у нас имеются следующие гиперребра:

1. {R1} - {R2}

2. {R2} - {R3}

3. {R4} - {R5}

4. {R5} - {R6}

5. {R1, R2, R3} - {R4, R5, R6}

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

Чтобы создать план для множества из i узлов, нам нужно обойти уже не все возможные пары, дающие i в сумме, а все пары гиперузлов, которые в объединении дают то же множество. Такая пара — это пара из двух непересекающихся множеств: connected subgraph (csg, подграф) и connected complement (cmp, дополнение). Эти аббревиатуры будут часто встречаться в статье.

Чтобы все заработало оптимально, требуется ввести небольшое ограничение — порядок узлов. Над узлами (т.е. таблицами) должно быть отношение порядка, грубо говоря, они должны быть пронумерованы (нумерация используется чаще всего) для того, чтобы потом мы могли их сравнить и отсортировать. Чтобы понять зачем, рассмотрим ядро алгоритма — соседство.

В процессе работы алгоритма для перехода от одного гиперузла к другому мы используем соседей (neighborhood). В статье приводится математическое определение, но проще всего сказать, что соседи для какого-либо гиперузла — это множество других достижимых узлов. Также требуется, чтобы это множество было минимальным, в противном случае мы будем обрабатывать одни и те же узлы несколько раз. Вот тут и нужен порядок — когда для нахождения соседей мы обходим ребра, то в множество добавляем только представителя гиперузла, его минимальный элемент. Дальше нужно просто проверить, что другие ребра не содержат уже добавленные узлы. Последняя важная деталь алгоритма — исключенное множество (excluded set). В DPsize в качестве оптимизации итерирование по дополняющим парам мы начинаем не с 0, а со следующего индекса, или в противном случае попытаемся соединить себя с собой же, а некоторые пары — обработать дважды. Здесь примерно та же идея, мы ведем учет узлов, которые не стоит рассматривать (исключенных) и проверяем это практически везде, даже при нахождении соседей. Благодаря этому мы можем не рассматривать одно и то же множество дважды.

Основная логика алгоритма в статье представлена пятью функциями, а ядро алгоритма вкратце можно описать так: нам нужно найти csg-cmp пару, которая в объединении дает весь запрос, поэтому с помощью поиска соседей будет поочередно/рекурсивно увеличиваться csg и cmp. Вопрос только в том, с чего начать. Ответ здесь такой — мы начинаем итерироваться по всем узлам начиная с конца, а при дальнейшем вызове в excluded записываем все узлы, которые меньше текущего. В итоге мы начинаем с простого гиперузла, который никто не рассматривал, а затем рекурсивно его расширяем и находим cmp для него с помощью соседей.

Собственно, теперь нетрудно понять функции:

• Solve — входная точка алгоритма. Итерируемся по простым гиперузлам с конца и вызываем EmitCsg и EnumerateCsgRecursive;

• EmitCsg — принимает уже фиксированный csg, для которого находит подходящий cmp, а затем вызывает EmitCsgCmp и/или EnumerateCmpRecursive;

• EmitCsgRecursive — принимает csg, который расширяет с помощью соседей, затем вызывает EmitCsg и/или EnumerateCsgRecursive;

• EnumerateCmpRecursive — принимает фиксированный csg и cmp, с помощью соседей расширяет cmp, затем вызывает EmitCsgCmp и/или EnumerateCmpRecursive;

• EmitCsgCmp — создает готовый план для фиксированных csg и cmp.

Основная идея алгоритма понятна, в качестве примера в статье также есть пошаговая иллюстрация работы алгоритма для запроса из примера:

Вот что здесь происходит:

1. Итерирование происходит в обратном порядке, поэтому начинаем с отношения R6 (самый большой по индексу), но для него соседей нет, так как все остальные узлы находятся в исключенном множестве.

2. Переходим к R5.

3. Для него нашли соседа R6 и создаем из него cmp {R6}.

4. Теперь увеличиваем сам csg до {R5, R6}.

5. Переходим к R4.

6. Для него есть сосед {R5}, для которого создаем cmp {R5}.

7. После увеличиваем этот cmp до {R5, R6}, так как R6 — сосед R5.

8. Возвращаемся к шестой итерации и вместо cmp увеличиваем сам csg до {R4, R5}.

9. Для уже этого подграфа мы нашли cmp {R6}.

10. Увеличиваем csg {R4, R5} до {R4, R5, R6}.

11. Переходим к R3 (множество исключенных {R1, R2}), но для него соседей нет, поскольку:

    • Все гиперузлы, с которыми есть соединение через простые гиперребра (R1, R2), лежат во множестве исключенных;

    • Представитель левой вершины единственного сложного гиперребра (min({R1, R2, R3}) = R1) тоже лежит в множестве исключенных.

12. Переходим к R2.

13. Для него есть сосед R3, для которого создаем cmp.

14. Увеличиваем сам csg до {R2, R3}.

15. Переходим к R1.

16. Для него есть сосед {R2}, для которого и создаем cmp.

17. Для самого R2 есть сосед R3 — увеличиваем cmp.

18. Увеличиваем исходный подграф {R1} до {R1, R2} (сосед).

19. Для получившегося подграфа есть сосед R3 (вывели из соседства с R2).

20. Увеличиваем подграф {R1, R2} до {R1, R2, R3} с помощью этого соседа.

21. Используем единственное сложное гиперребро и получаем соседа для {R1, R2, R3} — это {R4}, представитель правой вершины {R4, R5, R6}. Создаем для него cmp.

22. Увеличиваем cmp до {R4, R5} с помощью простого соседа.

23. Еще раз увеличиваем cmp, уже до {R4, R5, R6}.

24. Возвращаемся к шагу 20 и начинаем увеличивать подграф: добавляем {R4}.

25. Затем добавляем {R5}.

26. Наконец добавляем {R6}. Теперь csg равен всему гиперграфу и мы можем закончить.

Алгоритм хороший, а можно добавить его в PostgreSQL? Да, и всегда было можно! Для это и существует join_search_hook — точка, позволяющая подменить алгоритм перебора JOIN'ов.

Расширение pg_dphyp

Идея для создания этого расширения пришла ко мне спонтанно: я изучал разные алгоритмы JOIN'ов и наткнулся на него. Поиск в интернете не дал ничего такого для PostgreSQL, и я понял, что надо делать самому. Кому уже сразу хочется посмотреть на то, что получилось, вот ссылка на репозиторий. В контексте ядра работы алгоритма я не принес ничего нового, даже наоборот, больше копипастил у других. Перед тем как приступить к реализации своего, я посмотрел реализации в нескольких СУБД, в частности, YDB, MySQL и DuckDB. Если кто-то хочет изучить DPhyp по коду — рекомендую посмотреть на код YDB — чистый и понятный, очень легко читать. Но сам я начал не с YDB, а с MySQL, и вот в нём реализация значительно изменена и оптимизирована, сразу разобраться не получится, только по комментариям и с изначальным пониманием самого DPhyp.

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

Представление множеств

Множества являются "лошадкой" алгоритма, лежат в основе все его эффективности. Разные СУБД делают это по-разному, например:

• DuckDB использует числа напрямую и хранит их в массиве;

• YDB - std::bitset<>;

• MySQL - простое 8-байтное число.

Кто работает с PostgreSQL, знает, что там имеется своя реализация множества — Bitmapset. Она используется повсеместно и часто для хранения ID отношений. Казалось бы, "бери, раз дают", но проблема в том, что операций над множествами — огромное количество, а Bitmapset создает новую копию каждый раз когда меняется, то есть, это лишние аллокации памяти. В PostgreSQL эта проблема часто не возникает, поскольку после создания Bitmapset меняется редко, но не в моем случае, и это не критично. Проблему я решил, реализовав сразу два подхода, — создал два файла, где в одном использовал bitmapword (восьмибайтное число, как в MySQL), а в другом — Bitmapset для сложных запросов. Но это произошло в самом начале разработки, когда я еще не особо понимал тонкостей работы алгоритма, поэтому через некоторое время на файл с Bitmapset я "забил" (решил добавить изменения позже), а потом и совсем удалил. Сейчас я использую представление множества с помощью числа, и проблем это не доставляет, основные операции со множеством выполняются простыми битовыми |, & и ~. Но есть и еще пара операций, которая важна для самого алгоритма, например, итерирование по элементам множества в процессе вычисления соседей. Таких операций много, поэтому я вынес их в отдельный заголовочный файл.

Другая интересная операция — итерирование по всем подмножествам, это нужно для расширения csg/cmp. Так как множество — это число, то и операция проводится с числом. В MySQL это решили с помощью битового трюка (init - state) & state, который при постоянном применении ведет себя как инкремент, но при этом изменяются только биты множества. Эту реализацию я взял себе. Например, для множества 01010010 мы получим следующие подмножества:

00000010    001
00010000    010
00010010    011
01000000    100
01000010    101
01010000    110
01010010    111

Слева — само множество, а справа — его битовая маска. Так как мы итерируемся инкрементом, то можно сказать, что эта битовая маска в числовом представлении также отображает и номер итерации. Далее это свойство будет использоваться часто.

DP-таблица

DPhyp — это алгоритм динамического программирования, и у него есть своя таблица для отслеживания состояния выполнения. Если посмотреть на алгоритм из статьи, то видно, что эта таблица используется только для хранения готовых планов. В PostgreSQL для готовых планов (представлений отношений) используется структура RelOptInfo, и она уже хранится в хэш-таблице. Вроде бы "вот и хорошо", не надо думать о создании своей, но нет. Проблема заключается уже в самом PostgreSQL, а точнее, его обработке FULL JOIN. Для этого типа соединений сейчас поддерживается только предикат равенства, а в коде, когда встречается такой предикат, все отношения в левой и правой части попадают в отдельные списки, которые планируются независимо. Это причина, по которой для внутренних таблиц используется своя система индексации (то есть индексы узлов DPhyp не обязательно соответствуют индексам отношений). Поэтому даже если я буду на время превращать bitmapword в Bitmapset, что потребует еще выделения памяти, то не смогу этого сделать, если индексы отношений превышают 64 (максимального значения для восьмибайтного числа).

Поэтому для алгоритма используется своя DP-таблица. По факту, это хэш-таблица — HTAB *, часть PostgreSQL. Особенность ее в том, что в ней хранится только одна структура, а ее ключ элемента должен хранится в начале этой структуры. Из-за этого была добавлена еще одна структура HyperNode, которая представляет гиперузел. Но сейчас это не просто пара из множества узлов и отношения — в ней хранятся и другие данные.

Построение графа

Другая не менее важная задача — построение самого графа. Проблема в том, что в отличие от YDB или MySQL, балом я не правлю и должен подстраиваться под саму БД. С одной стороны, проблемы вроде нет, я могу пройтись по всем предикатам, используемым в запросе, и из них создать ребра. Собственно, сейчас это так и реализуется. Но дьявол кроется в деталях.

Информацию для этой операции мне приходится брать из трех различных мест:

1. PlannerInfo->join_info_list — список из non-INNER JOIN условий.

2. RelOptInfo->joinclauses — список из предикатов, которые используют больше одного отношения, то есть по факту это JOIN-условие.

3. PlannerInfo->eq_classes — список классов эквивалентности (далее).

Первое — самое простое. Этот список содержит ограничения, которые накладывают разные не INNER (т. е. LEFT/RIGHT/FULL и т.д.) JOIN'ы. В нем есть две пары частей: синтаксические ограничения и минимальные, нужные для непосредственного вычисления. На всякий случай я создаю гиперребро для обеих пар. Про остальные тоже надо сказать. Второе имеет сложности с точки зрения самого выражения — оно может не быть бинарным, а может и быть, но по обеим сторонам используется одно и то же отношение. Для таких моментов я добавил свое понятие — cross join set (cjs). По факту это просто множество отношений, которые должны соединиться между собой. Для каждого отношения в cjs я создаю простые ребра (каждый с каждым). Это решает проблему того, что какие-то предикаты могут отсутствовать. DPsize, тот, который в PostgreSQL по умолчанию, решает это за счет того, что обрабатывает каждую возможную пару.

Теперь 3 — классы эквивалентности. Класс эквивалентности — это механизм PostgreSQL, с помощью которого он определяет, что какие-то выражения равны друг другу. Это используется не только в выражениях. Например, выражения в ORDER BY или GROUP BY представляются именно классом эквивалентности (возможно вырожденным, с единственным элементом). Но сейчас не об этом, а том, как это стреляет. Такие классы эквивалентности появляются, когда в запросе имеются выражения равенства, причем даже одного достаточно для создания класса эквивалентности. Как уже можно догадаться, они также используются для JOIN'ов. Когда я встречаю класс эквивалентности с несколькими отношениями, приходится создавать гиперребра для каждой пары. Поэтому подобные запросы с одними равенством под капотом превращаются в клику.

Клика — это граф, в котором все узлы соединены друг с другом.

Для примера рассмотрим такой запрос:

SELECT * FROM t1 
         JOIN t2 ON t1.x = t2.x AND t1.y > t2.y
         JOIN t3 ON t1.x + t2.x = t3.x
    LEFT JOIN t4 ON t4.x = t3.x;

Он сочетает:

• классы эквивалентности {t1.x, t2.x} и {t1.x + t2.x, t3.x};

• предикат JOIN t1.y > t2.y;

• особый JOIN-предикат t4.x = t3.x.

Из них будут созданы следующие гиперребра:

• {t1} - {t2}

• {t3} - {t1, t2}

• {t3} - {t4}

Несвязные подграфы

Из вышесказанного вытекает еще одна проблема. Что будет, если мы получили несвязный граф (то есть лес)? В таком случае алгоритм ничего не сможет сделать. Точнее, он создаст план для каждого графа в лесу, но для всего запроса уже не сможет. Причем эта проблема может появиться не только из-за CROSS JOIN или ,, но и из-за внешних параметров подзапросов. Приведу пример:

SELECT * FROM t1
WHERE t1.x IN 
    (SELECT t2.x FROM t2, t3 WHERE t2.x = t1.x AND t3.x = t1.x);

В этом подзапросе t1.x является параметром, но на выходе в графе у нас лес, потому что для t1 в подзапросе нет индекса. Можно представить себе и более сложные запросы, которые могут упасть таким образом. Вообще это я обнаружил, когда запустил \d (чтобы отобразить все таблицы) в psql, и оказалось, что там был примерный запрос. С одной стороны, на практике несвязные графы — довольно редкое явление, чтобы тратить ресурсы для обнаружения подобного, с другой — мы можем потратить лишнее время (просто удвоить время планирования без полезной нагрузки). Поэтому решение, как поступать, я отдал на откуп пользователям.

Есть отдельный параметр pg_dphyp.cj_strategy, который может принимать три значения:

• no – если не смогли построить план, то вызвать DPsize/GEQO;

• pass – если не смогли построить план, то собрать все готовые планы несвязных деревьев и отдать DPsize/GEQO на финальную доработку;

• detect – создавать гиперребра для несвязных графов перед началом работы.

Первый вариант выглядит лишним, но на деле это не так, поскольку планы, созданные для этих подграфов, могут быть неоптимальными ввиду того, что между несвязными подграфами могут быть неявные связи, которые могли бы помочь создать оптимальный план. Поэтому и финальный план тоже может быть неоптимальным.

Остается вопрос: как находить несвязные графы? Ответ на поверхности — с помощью алгоритма Union-Set. Для производительности используется оптимизированная версия с ранжированием и обновлением лидера у обеих частей.

Хранение гиперрёбер

Еще одна задача — хранение гиперграфа. Граф можно хранить в виде списка ребер, а можно таблицей смежности. Но для гиперграфа остается только первый вариант, поскольку практически невозможно построить таблицу смежности для гиперребер (это не 1 элемент, а целое множество).

Хорошо, определились, но можно ли применить какие-нибудь оптимизации? Да, можно. Почти у всех реализаций (например, YDB и MySQL) для простых гиперребер есть оптимизация. Напомню еще раз, что у простого гиперребра по обеим сторонам находятся множества из единственного элемента. Эта оптимизация заключается в том, что мы храним все узлы, с которыми нас связывают простые гиперребра, в одном единственном множестве. Далее в процессе работы нам нужно сделать единственную операцию для проверки сразу нескольких ребер. Такое множество часто называют simple neighborhood, думаю, понятно, почему. Я тоже взял себе эту оптимизацию, но пошел чуть дальше, и храню этот simple neighborhood для каждого гиперузла (в структуре HyperNode). Это немного упрощает работу, так как не нужно тратить время на дополнительное итерирование по узлам, а места он занимает всего 8 байт.

По сложным гиперребрам — тоже не без замечаний. Ранее я сказал, что для одного и того же выражения в тексте запроса может быть создано несколько экземпляров RestrictInfo (представление выражения в исходном коде), но с разным набором индексов необходимых отношений. Тогда же я и сказал, что не могу обработать эти дополнительные индексы, поэтому в результате могу получить множество дубликатов. С этим я решил бороться обычной сортировкой: все ребра я храню в отсортированном виде, и если при вставке нахожу равное ребро, то ничего не делаю (не вставляю).

Создание плана

Эта статья — не только про алгоритм на гиперграфах, но и про эффективное создание плана. Это важный момент, так как некоторые JOIN-операторы не коммутативны (например, LEFT JOIN), и если это не учитывать, то, возможно, придется вычислять одну и ту же пару дважды. Но это еще не все. Напомню, что DPsize плотно "засел" в кодовой базе — настолько, что нельзя создать план для i таблиц без нахождения оптимального плана для нижележащих.

Изначально я так и делал: после создания плана вызывал set_cheapest для нахождения лучшего плана, и дальше мог спокойно вызывать make_join_rel для других. Но если посмотреть внутрь, то увидим, что функция проходит по всем найденным путям для нахождения лучшего, то есть по мере работы программы время, затраченное на ее выполнение, будет только увеличиться. Из-за этого я перешел на DPsize-like подход. Для каждого гиперузла я веду список пар гиперузлов-кандидатов, которые могут его создать, а в конце рекурсивно вызываю создание плана, эдакий pull-подход. Да, есть вероятность, что внутри окажется пара, которая не сможет создать план запроса, и я потрачу время впустую, но накладные расходы на изначальный подход (с постоянным вызовом set_cheapest) все же больше, а вероятность того, что какая-то пара гиперузлов не создаст полезного JOIN'а крайне мала из-за самой идеи DPhyp.

Оптимальное итерирование по соседям

Наконец-то мы пришли к самой интересной части — как мы будем обходить соседей. В алгоритме можно выделить три функции, занятые перебором пар csg/cmp, и в них нам нужно вычислять соседей целых четыре раза. Все начинает выглядеть более устрашающим, когда осознаешь, что алгоритм предполагает итерирование по всем возможным подмножествам соседей (power set без пустого множества) — это комбинаций.

Да, мы добавили оптимизацию простого соседства (simple neighborhood), но все же нам необходимо обработать все узлы в подмножествах (кроме того, есть и основная часть, к которой это подмножество добавляется — для него тоже надо посчитать). Всего получается узлов, которые надо обработать в сумме для всех подмножеств.

Количество разных комбинаций подмножеств из элементов составляет , но для каждого подмножества размером нужно обработать каждый его элемент, а их . Другими словами, количество элементов во всех подмножествах размером равно .

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

Вначале создается множество — гиперрёбра, принадлежащие текущему гиперузлу и указывающие за его пределы. Затем это множество сжимается до минимального, и из него выбираются представители (наименьшие элементы). Второй шаг, нахождение минимального множества, — это сложная вычислительная задача, поэтому для ее облегчения многие используют оптимизацию: по мере обхода узлов в соседи попадают только представители (минимальные узлы), а перед добавлением проверяют, что очередной гиперузел не пересекается с уже найденными соседями. Этот подход использует как сам MySQL, так и YDB. Имеет ли смысл оптимизировать этот фрагмент? В коде MySQL довольно много комментариев, которыми они описывают те или иные принятые решения (чаще всего на основании микробенчмарков). Один из таких комментариев написан к функции вычисления соседей FindNeighborhood:

...
This function accounts for roughly 20–70% of the total DPhyp running time, depending on the shape of the graph (~40% average across the microbenchmarks)
...

То есть практически все время работы алгоритма занимает логика вычисления соседей, и поэтому да, смысл в ее оптимизации есть. Для того, чтобы ускорить вычисление соседей, в MySQL используется кеширование по подмножествам.

Подход в MySQL

Идея, реализованная в MySQL, построена на свойстве подмножеств, которые мы получаем при итерировании инкрементом. Если приглядеться, можно заметить, что при таком подходе на следующем шаге мы часто получаем надмножество предыдущего шага, и при этом очень часто (буквально каждый следующий шаг) первый бит постоянно переключается то в 0, то в 1. А если его переключить из 0 в 1, то мы получим подмножество! Например, 0011100 -> 0011101.

Сразу возникает желание просто взять предыдущих соседей и добавить этим первым элементом, но возникает вопрос — а корректно ли это? Да, корректно. Если мы еще раз посмотрим на определение соседей из статьи, то не увидим там ограничения на порядок обхода узлов, а это значит, что мы можем взять одно множество и дополнить еще одним. Чтобы идея стала понятнее, рассмотрим пример итерации по подмножеству из 4 узлов. Привожу пример из комментария:

0001
0010 *
0011
0100 *
0101
0110 *
0111
1000 *
1001
1010 *
1011
1100 *
1101
1110 *
1111

Звездочкой я указал места, в которых нам придется полностью вычислять соседей, то есть очищать кеш, но после — на следующем подмножестве — нам будет достаточно обработать только один узел (первый). Если всё делать честно, то для исходного множества размера 4 придется обрабатывать 32 узла, а с помощью этой эвристики — только 20. В комментарии также было указано, что существуют оптимальные порядки обхода подмножеств, которые дадут еще больший прирост. Для множества из четырех элементов он будет таким (в комментарии в коде, наверное, очепятка — после 0111 идет 1110, что не позволяет оптимально вычислить соседей, поэтому здесь моя поправленная версия). Идея проста: мы как бы итеративно делаем сдвиг правого (первого) бита вправо, пока он не упрется в левую часть, а когда эта левая часть закончилась, то начинаем новый разряд — кеш обновляем в начале нового разряда или когда этот бит упирается в последовательность единиц:

0001 
0010 *
0011 
0100 *
0101
0110 *
0111
1000 *
1010
1100
1001 *
1011
1101
1110 *
1111

Здесь нам нужно уже только 15 итераций. На практике даже такая эвристика с отслеживанием последнего бита дает значительный прирост, требуется практически в 2 раза меньше итераций.

Известен ли оптимальный порядок для большего множества? Да, но только для пяти (приводить здесь не буду, его можно глянуть в том же комментарии). Если кто-то подумал "просто захардкодить и все", то увы. Не забывайте, что перед вами сейчас просто битовая маска включенных/исключенных элементов из множества. В реальности элементы в битовой маске разрознены, например, итерация по множеству из трех элементов 00101001 будет выглядеть так (слева подмножество, справа — эта маска/номер итерации):

00000001   001
00001000   010
00001001   011
00100000   100
00100001   101
00101000   110
00101001   111

// EnumerateComplementsTo() resets the forbidden set, since nodes that
// were forbidden under this subgraph may very well be part of the
// complement. However, this also means that the neighborhood we just
// computed may be incomplete; it just looks at recently-added nodes,
// but there are older nodes that may have neighbors that we added to
// the forbidden set (X) instead of the subgraph itself (S). However,
// this is also the only time we add to the forbidden set, so we know
// exactly which nodes they are! Thus, simply add our forbidden set
// to the neighborhood for purposes of computing the complement.
//
// This behavior is tested in the SmallStar unit test.
new_neighborhood |= forbidden & ~TablesBetween(0, lowest_node_idx);

// This node's neighborhood is also part of the new neighborhood
// it's just not added to the forbidden set yet, so we missed it in
// the previous calculation).
new_neighborhood |= neighborhood;

Для реализации своего одноэлементного кеша они используют класс NeighborhoodCache и прокидывают его почти везде. Его логика проста: перед началом поиска соседей находим дельту множеств, но по факту проверяем, что последний бит выставлен, а в конце сохраняем рассчитанных соседей — но только если не стоит первый бит (его они назвали taboo bit).

Как только я понял идею, то переписал код себе почти слово в слово, только Васю на Петю taboo на forbidden поменял (чтобы хоть что-то свое было). Код жил в таком виде довольно долго, аж несколько недель, а потом я спохватился — GPLv2! Код MySQL распространяется под лицензией GPLv2, а учитывая, что я переписал почти все слово в слово (на тот момент, наверное, еще даже не до конца понимая саму идею), то нарушил эту лицензию: мой-то проект под MIT, они несовместимы. Тогда я встал перед вопросом — выкинуть эту хорошую оптимизацию и сделать код медленным, или оставить, но поменять лицензию на GPLv2? По итогу выбрал первое, и это стало началом увлекательной несколько-недельной рефлексии о том, как мне оптимизировать эту комбинаторику.

Суффиксный кеш

Передо мной стоит задача — оптимизировать алгоритм, но так, чтобы это не было калькой MySQL (в моем случае это важный аспект, потому что после нахождения первого решения часто использую только его). Сама идея ясна: зачем вычислять все множество соседей, если можно просто его дополнять этой дельтой. Нам как-то нужно найти то ли шаблон, то ли еще что-то, что поможет нам обнаружить подобное подмножество.

А что если посмотреть с другой стороны? Действительно, у нашего способа итерирования по подмножествам есть хорошее свойство: верхняя часть (MSB) меняется гораздо реже, чем нижняя (LSB). Так почему бы нам не использовать это свойство? Просто закешируем то, что редко меняется! Но что такое "редко меняется" по существу? В первой идее за эту константу я взял замыкающие единицы — последовательность последних единиц (при фиксированном разряде) в числе может только увеличиваться, то есть достаточно только подсчитать соседей для этой последовательности, а затем добавлять меняющуюся. Отделить базовую (неизменную) часть мы можем простой битовой маской, а ее размер мы знаем (подсчитали).

Если вспомнить оптимальную последовательность итерирования, предложенную MySQL, то можно заметить, что эта стратегия идеально подходит под такую последовательность.

Как нам отследить изменение этой части? Легко, ведь это двоичная арифметика: просто отслеживаем сколько итераций до следующей новой 1, а затем делим на 2 и ожидаем полученное количество итераций. Когда начинается новый разряд, то просто сбрасываем счетчик и повторяем. Алгоритм следующий:

1. Инициализация:

   1. nb_cache = 0 — закешированные соседи.

   2. nb_cache_subset = 0 — маска множества, для которого хранится nb_cache.

   3. prev_update = 0 — сохраненное значение next_update.

   4. next_update = 0 — итераций до следующего обновления кеша.

2. Для очередной итерации (начиная с 1):

   1. Если next_update == 0:

      1. Довычисляю соседей последним элементом.

      2. next_update = prev_update / 2 — следующая единица в последовательности появится ровно через половину числа предыдущих операций.

      3. prev_update = next_update — это нужно для вычисления следующих соседей.

      4. nb_cache = *вычисленные сейчас соседи*.

      5. nb_cache_subset = *текущее подмножество*.

   2. Если в множестве только 1 элемент:

      1. Вычисляю соседей для этого единственного элемента.

      2. next_update = 2^*номер разряда - 2* — столько осталось до добавления еще одной единицы в множество.

      3. prev_update = next_update.

      4. nb_cache = *вычисленные сейчас соседи*.

      5. nb_cache_subset = *текущее подмножество*.

   3. В противном случае:

      1. Из подмножества удаляем закешированные элементы (храним в nb_cache_subset).

      2. Вычисляем соседей с nb_cache в качестве базы.

Однослойный кеш

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

Вернемся в самое начало. Мы обсуждали то, что кешировать нужно редко меняющиеся части. За эту часть мы взяли последовательность замыкающих единиц. Она действительно редко меняется, но заметим, что эта часть вариативна, то есть, требуется отслеживать ее размер. Теперь сделаем эту часть фиксированной, то есть кешировать будем определенный суффикс множества.

Что даст больший прирост — кеширование замыкающих единиц или MSB? Давайте посчитаем на том же множестве из 4 элементов. Для схемы кеширования лидирующих 1 мы имеем следующую схему расчета (второй столбец показывает количество обработанных узлов, а звездочкой отмечены места обновления кеша):

0001  1
0010  1  *
0011  2
0100  1  *
0101  2
0110  2  *
0111  1
1000  1  *
1001  1
1010  1
1011  2
1100  2  *
1101  1
1110  3  *
1111  1 

Всего надо обработать 22 элемента — на два больше, чем схема с табу-битом.

Со схемой кеширования MSB надо вначале ответить на вопрос — а что такое MSB, каков его размер? Возьмем мало — будем очень много вычислять, возьмем много — будем часто вычислять этот MSB. В принципе, вычислить можно всё, так как тут та же самая двоичная математика. Но для наглядности возьмем MSB равный 2:

0001  1
0010  1
0011  2
0100  1  *
0101  1
0110  1
0111  2
1000  1  *
1001  1
1010  1
1011  2
1100  2  *
1101  1
1110  1
1111  2

Тут уже 20 элементов — столько же, сколько в подходе MySQL, но меньше, чем подход замыкающих единиц.

Здесь каждый раз при обновлении кеша я честно полностью рассчитывал соседей. Вы могли заметить, что при расчете закешированной части для соседей мы могли использовать ту же самую оптимизацию с последним битом — добавить к закешированным соседям этот последний элемент. Такая оптимизация позволит достичь всего лишь 16 итераций, что намного эффективнее. Тогда я упустил этот момент и не стал рассматривать, но это было к лучшему — скоро узнаете, почему.

Схема с кешированием фиксированной части MSB показала себя лучше, да и к тому же у нее есть возможность настраивания (параметр — размер кешированной части). По итогу выбираем схему кеширования с одним элементом — MSB. Далее эту неизменяемую часть, которую используем за стартовое значение для вычисления соседей, я буду называть base (базой). Алгоритм работы с ней довольно прост: через каждые элементов сохраняем в кеш эту базовую часть, а затем просто используем как стартовую точку при расчете соседей.

Двухслойный кеш

Погодите, мы ведь работаем со множествами, а любое множество можно создать из предыдущего добавлением одного элемента! Например, множество 011010 можно построить из любого 001010, 010010 или 011000. Но это также значит, что можно создать текущее множество простым добавлением самого крайнего с начала элемента. Тот же изначальный пример с табу-битом — это частный случай, когда мы добавляли первый элемент.

Давайте построим таблицу из 4 элементов и посмотрим, как мы можем создать текущее множество из предыдущего:

0000 <+  <+  <+
   ^  |   |   |
0001  |   |   |
      |   |   |
0010 -+   |   |
   ^      |   |
0011      |   |
          |   |
0100 <+  -+   |
   ^  |       |
0101  |       |
      |       |
0110 -+       |
   ^          |
0111          |
              |
1000 <+  <+  -+
   ^  |   |
1001  |   |
      |   |
1010 -+   |
   ^      |
1011      |
          |
1100 <+  -+
   ^  |
1101  |
      |
1110 -+
   ^
1111

Вы видите этот паттерн? Мы берем элементы в ячейке под индексом меньше нашей на какую-то степень двойки и используем как базу для создания текущего множества добавлением текущего крайнего элемента. Что это за степень двойки? Можно увидеть из этой же схемы — это количество текущих лидирующих нулей, то есть множество соседей, которое может использоваться для создания текущего, располагается в шагах назад, где — количество текущих лидирующих нулей номера итерации.

Но ведь это таблица динамического программирования! Для вычисления текущего множества мы используем результат предыдущего вычисления. Стоп, и еще раз погодите! Не значит ли это, что для вычисления соседей для каждого из подмножества нам потребуется обработать ровно узлов? Да, значит! Таким образом все наше множество можно поделить на 2 части: базовую (base), где мы закешировали редко меняющуюся старшую часть, и табличную (table), которая вычисляется с помощью нашей таблицы динамического программирования. Вопроса о размере каждой части не возникает — table-часть берет то, что осталось: (либо наоборот). По итогу мы имеем следующий алгоритм:

1. Если итерация делится на , то честно рассчитываем всех соседей и сохраняем в base.

2. В противном случае:

   1. Берем нижнюю часть номера итерации (битовой маской)

   2. Считаем количество нулей и вычисляем:

   3. Берем соседей родителя:

   4. Довычисляем соседей для первого элемента

   5. Сохраняем полученное значение в таблицу

Возникает уже практический вопрос: а сколько мы готовы отдать на эту таблицу? Для хранения множества используется восьмибайтное число, поэтому размер каждого множества фиксирован. Значит, для хранения таблицы с элементами требуется байтов. Теперь можно сделать грубые прикидки.

Легенда:

• Размер таблицы — размер множества, которое мы кешируем.

• Занимаемая память — количество памяти, которое занимает таблица для текущей реализации ().

• Всего элементов — сумма элементов из всех подмножеств ().

• Итераций — количество элементов, которое должны обработать в оптимизированной реализации, тоже самое что и количество итераций, но первую (пустую) не считаем ().

• Итераций сохранено — разница между "Всего элементов" и "Итераций".

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

Увеличение таблицы только уменьшает количество итераций

Мне стало интересно — а какой выигрыш дает увеличение таблицы? Например, сколько мы можем сохранить итераций, если вместо таблицы с tbl элементами использовать tbl + 1. Для начала вот формула общего числа итераций. Представим, что количество наших соседей (т. е. размер множества) равен max, а размер таблицы tbl. Тогда, количество итераций, необходимое для обработки всех подмножеств соседей, равняется:

$$

То есть, для каждого нового base итераций для вычисления его соседей, а потом еще итераций табличных. Делаем это для каждого подмножества (). Теперь мы можем вычислить разницу между количествами итераций для текущей таблицы и увеличенной на 1.

$$

Если раскроем суммы под скобками в первом слагаемом, то получим сумму такого вида: . Легко увидеть, что слагаемые взаимно уничтожаются, и на выходе мы получаем — первое слагаемое равно нулю. Тогда итоговое выражение:

$$

Учитывая, что

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

Трехслойный кеш

Итак, мы пришли к идее хранения таблицы вычисленных соседей с постоянным ее дополнением. Неплохо, но грустно, что в кеше только 10 узлов — для сложных запросов мы будем постоянно перерасчитывать base. Да, мы можем сделать размер таблицы настраиваемым, но в любом случае с какого-то момента размер таблицы может стать непозволительно большим, например, уже с 15 элементов потребуется таблица размером 256 Кб. В худшем случае после нескольких подобных рекурсивных вызовов (например, тот же EnumerateCsgRecursive) память, выделенная только под таблицы, может составить больше мегабайта. А можно ли как-то еще оптимизировать? Можно.

Вернемся к началу. Вся идея кеширования в MySQL основывалась на дорасчете соседей первым узлом текущего множества, но когда наступал момент сохранения соседей для дальнейших расчетов, они не сохраняли соседей, если в текущем множестве участвует этот первый taboo-бит. Почему? А потому, что это конечная остановка! Соседи, созданные в таком множестве, при итерировании инкрементом никем использоваться больше не будут. За доказательством долго ходить не нужно — посмотрите на предыдущую схему, и увидите, что соседи, вычисленные в нечетных итерациях, никем не используются. То есть мы спокойно можем не сохранять соседей нечетных итераций. Сколько же такая оптимизация нам сохраняет? Ровно половину: половина множеств четна, а другая — нечетна. Код, конечно, придется немного доработать, надо учитывать индексацию новой схемы: для получения предыдущего индекса нужно взять не , а элементов назад.

Подождите, но если мы обрежем первые биты, то останется другая часть со схожим паттерном. Что если и ее тоже так оптимизировать, и сколько раз можно так повторять? Не буду утомлять рассуждениями, скажу сразу — я смог применить подобное префиксное сжатие для четырех элементов, при этом потребовалось только две дополнительных переменных для расчета текущих соседей. Таким образом, мы приходим к трехслойной схеме кеширования: base, table, hot (изначально я их назвал well-done, medium и rare). Третью часть, hot, можно назвать сжатым префиксом.

Алгоритм работы теперь еще сильнее зависит от номера итерации: в зависимости от его значения мы работаем с base-, table- или hot-частью.

Для начала рассмотрим порядок обработки hot-части. Она состоит из четырех элементов, и главное — паттерн повторяется. Схему обращений мы уже видели, но здесь повторю ее в контексте ее вычисления:

0   0000 <+  <+  <+    quad leader
       ^  |   |   |
1   0001  |   |   |
          |   |   |
2   0010 -+   |   |
       ^      |   |
3   0011      |   |
              |   |
4   0100 <+  -+   |
       ^  |       |
5   0101  |       |
          |       |
6   0110 -+       |
       ^          |
7   0111          |
                  |
8   1000 <+  <+  -+    quad leader
       ^  |   |
9   1001  |   |
          |   |
10  1010 -+   |
       ^      |
11  1011      |
              |
12  1100 <+  -+
       ^  |
13  1101  |
          |
14  1110 -+
       ^
15  1111

Все эти 16 элементов мы делим пополам на 2 части, у каждой из которых есть свой лидер — quad leader. По факту это закешированные соседи для множества, в котором выставлен только последний бит. Его мы рассчитываем 2 раза: на итерациях 0 и 8. Далее, мы также используем оптимизацию для нечетных итераций — для них мы специально на каждой итерации сохраняем соседей четных множеств и на следующей (уже нечетной) итерации просто используем готовое значение (то есть сохранять для нечетных ничего не надо). В итоге у нас остались итерации: 2, 4, 6, 10, 12, 14. Здесь можем заметить, что для 2, 6, 10, 14 нужно просто взять соседей предыдущей четной итерации — его мы и так сохраняем для нечетных итераций, — но вот 4 и 12 требуют отдельной обработки: в качестве стартовой точки нужно взять quad leader, но и его мы тоже сохраняем. В итоге мы храним только два вычисленных значения соседей: предыдущая четная итерация и quad leader.

Переходим к table-части. Изменения коснулись прежде всего расчета индекса — теперь для дельты нужно из количества нулей вычесть 4 (размер hot части): . Стоит заметить, что когда начинается новая table-часть, то также начинается и новая hot-часть, поэтому каждый раз после расчета соседей и сохранения этого значения в таблицу нам следует очистить состояние hot-части — назначить нового quad-leader текущим значением соседей.

С base-частью изменений почти нет. Во-первых, как можно понять из предыдущих шагов, при начале новой base-части нам нужно сбросить состояние table-части (вычисление таблицы начинается заново), а также и hot-части (quad leader выставить в текущее вычисленное значение соседей). Но и это еще не все: почему бы нам не использовать тот же трюк с нечетными итерациями? И ведь верно: если первый бит текущего номера итерации base части равен 1, то мы можем просто довычислить соседей, так же как делали раньше.

Последний вопрос: как это все комбинировать? Здесь надо использовать префикс. Легко увидеть, что:

• каждые итераций следует обновлять base-часть (что в терминах двоичных чисел означает, что первые битов 0);

• каждые итераций следует делать новые записи в таблицу;

• каждые итераций следует обновлять quad leader в hot-части.

Алгоритм значительно усложнился, но чего не сделаешь ради оптимизаций. Зато теперь для того же размера множества требуется не байт, а всего лишь . Например, вместо 8Кб теперь требуется только 0.5Кб, но при этом кешируется все 10 элементов.

И вот когда эта идея устаканилась в голове и я вовсю принялся писать код, меня вдруг осенило.

Идеальный кеш

Я еще раз посмотрел на схему обращений, расписал ее на пять элементов и заметил то, что было все время на виду, но я не замечал. Вот эта схема, справа в которой — количество обращений к элементам (для нечетных не писал):

00000 <+  <+  <+  <+    5
    ^  |   |   |   |  
00001  |   |   |   |
       |   |   |   |
00010 -+   |   |   |    1
    ^      |   |   |
00011      |   |   |
           |   |   |
00100 <+  -+   |   |    2
    ^  |       |   |
00101  |       |   |
       |       |   |
00110 -+       |   |    1
    ^          |   |
00111          |   |
               |   |
01000 <+  <+  -+   |    3
    ^  |   |       |
01001  |   |       |
       |   |       |
01010 -+   |       |    1
    ^      |       |
01011      |       |
           |       |
01100 <+  -+       |    2
    ^  |           |
01101  |           |
       |           |
01110 -+           |    1
    ^              |
11111              |
                   |
10000 <+  <+  <+  -+    4  
    ^  |   |   |
10001  |   |   |
       |   |   |
10010 -+   |   |        1
    ^      |   |
10011      |   |
           |   |
10100 <+  -+   |        2
    ^  |       |
10101  |       |
       |       |
10110 -+       |        1
    ^          |
10111          |
               |
11000 <+  <+  -+        3
    ^  |   |
11001  |   |
       |   |
11010 -+   |            1
    ^      |
11011      |
           |
11100 <+  -+            2
    ^  |
11101  |
       |
11110 -+                1
    ^
11111

Видите паттерн? Если еще нет, то вот подсказка — связь между префиксом номера итерации и количеством обращений. Количество повторных обращений к элементу равно количеству нулей в начале, и после этого количества обращений значение вообще не будет использоваться — вместо него будет уже новое, но номер итерации будет иметь столько же нулей в начале. То есть нам незачем хранить эти значения, а поскольку наше итерирование идет только вперед (инкремент), мы спокойно можем удалять старые элементы. При таком подходе максимальный размер таблицы равен размеру исходного множества. Так как я представляю множество числом, то мне даже думать не надо — на стеке выделяю массив размером 64 элемента (64 * 8 = 512 байт).

Но как правильно это использовать? Вспомним, как мы вычисляем соседей: мы берем родительских соседей и дорассчитываем первым элементом. А вот и второе наблюдение: родительское множество — это наше, но без крайнего бита, например, для 01110 родителем будет 01100. А в какой ячейке хранятся соседи для 01100? Правильно — под индексом 2, поскольку у него два нуля в начале. Крайний случай — когда мы переходим в новый старший разряд, — тогда после удаления бита мы получим пустое множество, но для пустого множества мы возвращаем пустое множество, ведь у него не может быть соседей.

А теперь, собственно, и сам алгоритм:

1. Создаем DP-таблицу, (динамический) массив.

2. Начинаем очередную итерацию.

3. Из номера итерации убираем первый выставленный бит и считаем количество нулей.

4. Из DP-таблицы берем элемент под этим индексом.

5. Рассчитываем соседей, беря за основу закешированных, а за обновление — первый элемент текущего подмножества.

6. Сохраняем в таблицу полученное значение.

Корректно ли это? Корректно. Вот доказательство от обратного. Базой будет то, что соседи пустого множества — это пустое множество (либо другое, но определенное значение). Само доказательство исходит из свойства алгоритма перебора подмножеств — инкремента.

Доказательство:

1. Нам дана текущая итерация iter.

2. Мы убираем последний бит/элемент и получаем число iter_parent.

3. Считаем количество нулей, и из таблицы берем родительское множество nb_parent.

Утверждается, что nb_parent — это соседи множества iter_parent. Представим, что это не так, то есть в той ячейке хранятся соседи iter_parent_2, который не равен iter_parent. Тогда это число может быть либо больше, либо меньше его, но:

• iter_parent_2 точно не может быть больше iter_parent, поскольку это означает, что он был бы больше и изначального iter (так как различия в MSB-части), но мы итерируемся строго возрастающим способом, а значит, этого числа мы еще не встречали, и его значение в таблице находиться не может;

• числом меньше оно тоже быть не может, потому что это означало бы, что iter_parent мы пропустили: у обоих чисел одинаковое количество лидирующих нулей (по нашему предположению), а поскольку iter_parent идет после iter_parent_2 (так как больше в числовом представлении), то значение под соответствующим индексом мы должны были перезаписать (перезаписать соседей iter_parent_2), но мы не сделали это и таким образом нарушили алгоритм.

Единственный оставшийся вариант — под этим индексом хранятся соседи множества iter_parent. Учитывая, что для пустого множества соседи определены, мы также можем утверждать, что и мусора мы получить не можем:

• если текущее множество состоит из одного элемента, то значит мы перешли в новый старший разряд, в котором раньше не были. Убрав этот элемент, мы получим пустое множество, но для него соседи определены и для этого нового индекса, ранее не виденного, соседи сохранятся, и далее значение будет определено;

• в противном случае количество лидирующих нулей будет не больше номера старшего разряда (иначе мы начали новый разряд и это случай 1), и соседей для них мы уже должны были записать в таблицу, то есть оно определено.

Вот мы и доказали, что данная схема кеширования корректна. Вот сам код, который это все вычисляет:

typedef struct SubsetIteratorState
{
    /* Текущее подмножество */
    bitmapword subset;
    /* Переменные состояния для итерирования */
    bitmapword state;
    bitmapword init;
    /* Номер текущей итерации */
    bitmapword iteration;
    /* кеш соседей */
    bitmapword cached_neighborhood[64];
} SubsetIteratorState;

/* Получение соседей родителя для текущей итарации */
static inline bitmapword
get_parent_neighborhood(DPHypContext *context, SubsetIteratorState *iter_state)
{
    int zero_count;
    bitmapword last_bit_removed;

    /* Удаляем первый бит */
    last_bit_removed = bmw_difference(iter_state->iteration, bmw_lowest_bit(iter_state->iteration));
    if (last_bit_removed == 0)
    {
        /* Соседей нет */
        return 0;
    }

    zero_count = bmw_rightmost_one_pos(last_bit_removed);
    return iter_state->cached_neighborhood[zero_count];
}

static bitmapword
get_neighbors_iter(DPHypContext *context, bitmapword subgroup,
                   bitmapword excluded, SubsetIteratorState *iter_state)
{
    int i;
    int idx;
    int zero_count;
    bitmapword neighbors;
    EdgeArray *complex_edges;

    excluded |= subgroup;

    iter_state->iteration++;

    idx = bmw_rightmost_one_pos(iter_state->subset);

    /* База вычисления - соседи родителя текущей итерации */
    neighbors = get_parent_neighborhood(context, iter_state);

    /* Добавляем узлы простых соседей */
    neighbors |= bmw_difference(context->simple_edges[idx], excluded);

    /* Обрабатываем сложные ребра */
    complex_edges = &context->complex_edges[idx];
    i = get_start_index(complex_edges, neighbors | excluded);
    for (; i < complex_edges->size; i++)
    {
        HyperEdge edge = complex_edges->edges[i];
        if ( bmw_is_subset(edge.left, subgroup) &&
            !bmw_overlap(edge.right, neighbors | excluded))
        {
            neighbors |= bmw_lowest_bit(edge.right);
        }
    }

    neighbors = bmw_difference(neighbors, excluded);

    /* Сохраняем соседей */
    zero_count = bmw_rightmost_one_pos(iter_state->iteration);
    iter_state->cached_neighborhood[zero_count] = neighbors;

    return neighbors;
}

Схему также можно чуть-чуть оптимизировать, не сохраняя нечетные множества, но это уже область микро-оптимизаций.

А нельзя ли еще добавить оптимизаций? Можно. Пример этого уже есть в коде, который только я что привел — индексирование.

1. S = 00000001, X = 00000001, N = 00001110
2. S = 00001001, X = 00001111, N = 01110000
3. S = 01001001, X = 01111111, N = 10000000

Индексирование ребер

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

• при поиске соседей множество исключенных узлов (excluded) неизменно (либо только увеличивается);

• при определении связи между гиперузлами оба гиперузла фиксированы.

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

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

Покажу на примере. У нас имеется несколько отсортированных по количеству лидирующих нулей гиперребер. Справа написал индексы для удобства (левая часть гиперребра не важна, только правая):

[
    xxxxx - 00101    0
    xxxxx - 00111    1
    xxxxx - 00100    2
    xxxxx - 00100    3
    xxxxx - 01100    4
    xxxxx - 10100    5
    xxxxx - 11100    6
    xxxxx - 01000    7
]

Теперь легко понять, с какого индекса нам стоит начать итерацию в зависимости от того, какое перед нами множество исключенных узлов:

Несколько моментов:

1. Мы можем быть уверены только в размере лидирующих единиц, остальная часть для нас — черный ящик. Например, из-за этого в третьем примере итерацию начинаем со второго индекса, хотя видно, что остальная часть полностью исключена.

2. Для обобщения кода в случае когда нет подходящих ребер мы можем возвращать длину массива (большое число).

Чтобы понять пользу этой оптимизации, вспомните, что все ребра в графе — двунаправленные, то есть для каждого гиперребра мы создаем две пары с обменянными левой и правой частями. Может оказаться, что на какой-то узел ссылается очень большое количество таблиц (например, это таблица фактов, а размерностей у нас 100+), а сама эта таблица имеет самый большой индекс, то есть excluded будет включать почти все таблицы. В этом случае нам придется безуспешно проходить по всем сложным ребрам, зная, что это не даст никакого результата.

Хорошо, а как мы будем получать стартовый индекс? Первое что приходит в голову, когда говорят "отсортированный" — бинарный поиск, но не спешите с выводами. Вспомним, что наше пространство "ключей" (это количество лидирующих нулей/единиц) — дискретное. Начинается оно с нуля и может только увеличиваться (в моем случае есть предел — 64). А что подходит под описание такой структуры? Массив. Под индексом i будет храниться первый индекс массива гиперребер, первый элемент правой части (гиперребра) которого не меньше этого i.

А что делать с пробелами? В примере после 00111 сразу идет 00100, без 00010. Эти пробелы мы заполняем предыдущим значением, то есть если для какой-то длины i я не знаю, с какого индекса мне лучше начать итерацию, то нужно взять предыдущий индекс, так как если мой первый элемент i, то я буду удовлетворять и всем последовательностям исключенных длиной меньше этого i. За базу мы возьмем индекс 0, то есть если такой последовательности исключенных узлов нет, то ее значение будет 0, так как в этом случае мы должны проитерироваться по всем гиперребрам.

Затраты на использование такого индекса равны только расчету количества лидирующих единиц во множестве исключенных узлов. Но это можно оптимизировать простым битовым трюком — прибавляем 1 и получаем последовательность из 0 такой же длины, но оканчивающуюся на 1, а затем рассчитываем позицию этой единицы. Получить это значение можно специальной инструкцией, например, POPCNT.

Для ребер из примера мы можем построить такой индекс (индекс массива ребер справа):

[
    0: 0
    1: 2
    2: 2
    3: 7
    4: 8
    5: 8
]

Размер этого индекса зависит только от максимального количества лидирующих 0 во всем массиве ребер. Для примера видно, что я мог бы создать массив только из четырех элементов, а дальше всегда возвращать 8 (как размер массива).

Мы научились быстро отсекать ненужные ребра при поиске соседей. Но по ребрам мы ходим также для определения связанности двух гиперузлов. Можно ли использовать этот индекс и здесь? Да, можно. Два гиперузла соединены, когда есть гиперребро, левая часть которого — подмножество левого гиперузла, а правая часть — правого. Гиперузлы на входе никак не меняются, точно так же, как и множество исключенных. А теперь надо заметить, что правая часть гиперребра точно не будет подмножеством, если в этой части есть элементы, индекс которых меньше, чем наименьший в гиперузле справа. Пример: правая часть гиперребра 001010 никак не будет подмножеством гиперузла 001100, поскольку в ребре есть элемент с индексом 2. То есть семантика здесь практически та же, что и в случае исключенного множества, — мы должны исключать все ребра, у которых есть элементы меньше наименьшего элемента правого гиперузла.

Вычисление стартового индекса находится в функции get_start_index. Для удобства на вход она принимает не готовый индекс, а множество исключенных узлов. Эта функция также используется при определении связанности двух гиперузлов: надо просто перед передачей аргумента из множества, представляющего правое гиперребро, вычесть единицу, тогда последовательность нулей обратно станет последовательностью единиц, что по требуемой семантике — одно и то же.

static int
get_start_index(EdgeArray *edges, bitmapword excluded)
{
    int index;
    int lowest_bit;

    lowest_bit = bmw_rightmost_one_pos(excluded + 1);

    if (edges->start_idx_size <= lowest_bit)
        return edges->size;

    index = (int)edges->start_idx[lowest_bit];
    return index;
}

Определение сложности запроса

Итак, PostgreSQL использует 2 алгоритма: DPsize и GEQO, причем последний используется, если в запросе таблиц больше, чем значение параметра geqo_threshold. Но почему именно количество таблиц? Дело в том, что сложность DPsize определяется количеством таблиц — мы безусловно будем рассматривать все возможные комбинации. Но с DPhyp все обстоит иначе, его сложность зависит от самого графа запроса. В оригинальной статье сравниваются производительности алгоритмов на некоторых типах запросов, но они не дают прямого ответа на то, как определять сложность запроса (а может, я проглядел). Этот ответ приводится в другой статье — "Adaptive Optimization of Large Join Queries".

Автор этой статьи предлагает метаалгоритм, который, комбинируя несколько разных алгоритмов JOIN'а, позволяет создать планы запросов с количеством таблиц в несколько тысяч. В простых запросах авторы предлагают использовать DPhyp, но что такое простой запрос? Например, если в запросе 100 таблиц, то это не значит, что DPhyp с ним не справится. Если граф запроса представляет простую цепочку, например, все предикаты в форме Ti.x OP T(i + 1).x, то план для него найти несложно, но вот если это клика (каждый с каждым), то даже 15 таблиц — это уже много. Для DPhyp сложность надо определять не в количестве таблиц, а в сложности графа запроса — количестве связных подграфов. Значение в 10000 связных подграфов — как предел эффективности запроса, это соответствует примерно 14 таблицам в клике.

В этой же самой статье не только предлагается идея, но также и функция для вычисления количества связных подграфов. Посмотрев на нее, я понял: она идеально ложится на схему кеширования, описанную выше. Вот эта функция:

static uint64
count_cc_recursive(DPHypContext *context, bitmapword subgraph, bitmapword excluded,
                   uint64 count, uint64 max, bitmapword base_neighborhood)
{
    SubsetIteratorState subset_iter;
    subset_iterator_init(&subset_iter, base_neighborhood);
    while (subset_iterator_next(&subset_iter))
    {
        bitmapword set;
        bitmapword excluded_ext;
        bitmapword neighborhood;
  
        count++;
        if (count > max)
            break;

        excluded_ext = excluded | base_neighborhood;
        set = subgraph | subset_iter.subset;
        neighborhood = get_neighbors_iter(context, set, excluded_ext, &subset_iter);
        count = count_cc_recursive(context, set, excluded_ext, count, max, neighborhood);
    }

    return count;
}

static uint64
count_cc(DPHypContext *context, uint64 max)
{
    int64 count = 0;
    int rels_count;

    rels_count = list_length(context->initial_rels);
    for (size_t i = 0; i < rels_count; i++)
    {
        bitmapword excluded;
        bitmapword neighborhood;

        count++;
        if (count > max)
            break;

        excluded = bmw_make_b_v(i);
        neighborhood = get_neighbors_base(context, i, excluded);
        count = count_cc_recursive(context, bmw_make_singleton(i), excluded,
                                   count, max, neighborhood);
    }

    return count;
}

Названия функций я оставил теми же, что и в статье, но адаптировал сигнатуру для поддержки эффективного итерирования по соседям.

Бонус: количество связных подграфов — это размер результирующей DP-таблицы. Сейчас это значение используется для ее предварительной аллокации.

Тестирование

Проверим все вначале на каком-нибудь простом запросе:

EXPLAIN ANALYZE
SELECT * 
FROM t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13, t14
WHERE 
    t1.x + t2.x + t3.x + t4.x + t5.x + t6.x + t7.x > t8.x + t9.x + t10.x + t11.x + t12.x + t13.x + t14.x;

Это 14 таблиц, соединенных одним гиперребром: {t1, t2, t3, t4, t5, t6, t7} - {t8, t9, t10, t11, t12, t13, t14}. Каждая таблица — одноколоночная, с тремя значениями (чтобы запрос долго не выполнялся). Для DPsize результат следующий:

                                                                  QUERY PLAN                                   
-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215311.78 rows=1594323 width=56) (actual time=1.672..1330.944 rows=2083371 loops=1)
   Join Filter: (((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) + t7.x) > ((((((t8.x + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   Rows Removed by Join Filter: 2699598
   ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.057..0.612 rows=2187 loops=1)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.042..0.128 rows=81 loops=1)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.029..0.061 rows=9 loops=1)
                     ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4) (actual time=0.018..0.028 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.003..0.008 rows=3 loops=3)
                           ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.012 rows=3 loops=1)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.005 rows=9 loops=9)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.007..0.025 rows=9 loops=1)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.010 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.002..0.004 rows=3 loops=3)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.006 rows=3 loops=1)
         ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.001..0.002 rows=27 loops=81)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.014..0.037 rows=27 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.008..0.022 rows=9 loops=1)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.008 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.002..0.004 rows=3 loops=3)
                                 ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.007 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=9)
                           ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.004 rows=3 loops=1)
   ->  Materialize  (cost=0.00..47.29 rows=2187 width=28) (actual time=0.000..0.078 rows=2187 loops=2187)
         ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.039..0.405 rows=2187 loops=1)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.021..0.043 rows=81 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.010..0.014 rows=9 loops=1)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.005 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.002..0.002 rows=3 loops=3)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.004 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.002 rows=9 loops=9)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.009..0.013 rows=9 loops=1)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.005 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.002 rows=3 loops=3)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.000..0.001 rows=27 loops=81)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.016..0.026 rows=27 loops=1)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.010..0.014 rows=9 loops=1)
                                 ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4) (actual time=0.005..0.006 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.002 rows=3 loops=3)
                                       ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=9)
                                 ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.005 rows=3 loops=1)
 Planning Time: 3069.835 ms
 Execution Time: 1371.090 ms
(44 rows)

На планирование ушло 3 секунды, хотя на выполнение — меньше 1.5 секунд. Что нам даст DPhyp:

                                                                  QUERY PLAN                                   
-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215311.78 rows=1594323 width=56) (actual time=1.612..1325.670 rows=2083371 loops=1)
   Join Filter: (((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) + t7.x) > ((((((t8.x + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   Rows Removed by Join Filter: 2699598
   ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.039..0.551 rows=2187 loops=1)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.029..0.131 rows=81 loops=1)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.021..0.051 rows=9 loops=1)
                     ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4) (actual time=0.015..0.023 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.006 rows=3 loops=3)
                           ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.012 rows=3 loops=1)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.006 rows=9 loops=9)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.006..0.034 rows=9 loops=1)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.012 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.005 rows=3 loops=3)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.009 rows=3 loops=1)
         ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.000..0.002 rows=27 loops=81)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.009..0.032 rows=27 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.006..0.020 rows=9 loops=1)
                           ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.008 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.003 rows=3 loops=3)
                                 ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.006 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.000..0.001 rows=3 loops=9)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.003 rows=3 loops=1)
   ->  Materialize  (cost=0.00..47.29 rows=2187 width=28) (actual time=0.000..0.078 rows=2187 loops=2187)
         ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.025..0.397 rows=2187 loops=1)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.013..0.037 rows=81 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.007..0.012 rows=9 loops=1)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.005 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.002 rows=3 loops=3)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.002 rows=9 loops=9)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.006..0.009 rows=9 loops=1)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=3)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.003 rows=3 loops=1)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.000..0.001 rows=27 loops=81)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.011..0.021 rows=27 loops=1)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.007..0.011 rows=9 loops=1)
                                 ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.004 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=3)
                                       ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.000..0.001 rows=3 loops=9)
                                 ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.004 rows=3 loops=1)
 Planning Time: 4.706 ms
 Execution Time: 1365.543 ms
(44 rows)

4 миллисекунды! При этом планы идентичные — прирост производительности почти в 600 раз!

Но это всего лишь небольшой запрос, давайте теперь возьмем что-то посолиднее. Возьмем к примеру готовый JOB (Join Order Benchmark), представленный в работе "How Good Are Query Optimizers, Really?" и использованный для сравнения планировщиков нескольких СУБД, включая сам PostgreSQL. Бенчмарк можно найти в этом репозитории.

В самой работе производилось сравнение не скорости работы планировщика, а оценок, которые он дает. Использовались несложные запросы — это INNER equi-JOIN'ы (т. е. условия JOIN — только равенство), однако для оценки реальной производительности следует использовать самые различные нагрузки, включая всякие сложные LEFT JOIN, но пока этого достаточно.

Как производилось тестирование:

• замер времени производился с помощью простенького расширения, которое замеряло время выполнения join_search_hook;

• после заливки данных итоговый размер БД — чуть больше 8Гб;

• всего имелось 113 запросов, но на самом деле их 33, все остальные суть вариации с различными константами. Для тестов каждый запрос запускался десять раз и рассчитывалось среднее время его выполнения, а затем, чтобы "шуметь", результаты одних и тех же классов запросов (с разными константами) группировались и рассчитывалось среднее значение.

По итогу всех запусков получилась такая таблица:

Когда я слегка пробежался по таблице, то не поверил своим глазам. Давайте посмотрим в виде графика:

DPhyp в подавляющем большинстве создает план лучше, чем DPsize. Да, время его выполнения больше, но зато план-то лучше, а значит в долгосроке мы выигрываем!

Однако что-то здесь явно не так. Как минимум, мы только управляли порядком обследуемых отношений, но сами планы-то не создавали, это на самом PostgreSQL. Так что же, встроенный планировщик сломан? Для чистоты эксперимента давайте посмотрим, что получается на выходе. "Под нож" пойдет запрос 6f (попался под руку). Вот что нам дает DPsize:

                                                                        QUERY PLAN                                           
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=15215.38..15215.39 rows=1 width=96)
   ->  Nested Loop  (cost=8.10..15175.34 rows=5339 width=48)
         ->  Nested Loop  (cost=7.67..12744.50 rows=5339 width=37)
               Join Filter: (ci.movie_id = t.id)
               ->  Nested Loop  (cost=7.23..12483.46 rows=147 width=41)
                     ->  Nested Loop  (cost=6.80..12351.21 rows=270 width=20)
                           ->  Seq Scan on keyword k  (cost=0.00..3691.40 rows=8 width=20)
                                 Filter: (keyword = ANY ('{superhero,sequel,second-part,marvel-comics,based-on-comic,tv-special,fight,violence}'::text[]))
                           ->  Bitmap Heap Scan on movie_keyword mk  (cost=6.80..1079.43 rows=305 width=8)
                                 Recheck Cond: (k.id = keyword_id)
                                 ->  Bitmap Index Scan on keyword_id_movie_keyword  (cost=0.00..6.72 rows=305 width=0)
                                       Index Cond: (keyword_id = k.id)
                     ->  Index Scan using title_pkey on title t  (cost=0.43..0.49 rows=1 width=21)
                           Index Cond: (id = mk.movie_id)
                           Filter: (production_year > 2000)
               ->  Index Scan using movie_id_cast_info on cast_info ci  (cost=0.44..1.33 rows=36 width=8)
                     Index Cond: (movie_id = mk.movie_id)
         ->  Index Scan using name_pkey on name n  (cost=0.43..0.46 rows=1 width=19)
               Index Cond: (id = ci.person_id)
(19 rows)

А вот что дает DPhyp:

                                                                        QUERY PLAN                                         
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=13720.08..13720.09 rows=1 width=96)
   ->  Nested Loop  (cost=8.10..13704.27 rows=2108 width=48)
         ->  Nested Loop  (cost=7.67..12744.50 rows=2108 width=37)
               Join Filter: (ci.movie_id = t.id)
               ->  Nested Loop  (cost=7.23..12483.46 rows=147 width=41)
                     ->  Nested Loop  (cost=6.80..12351.21 rows=270 width=20)
                           ->  Seq Scan on keyword k  (cost=0.00..3691.40 rows=8 width=20)
                                 Filter: (keyword = ANY ('{superhero,sequel,second-part,marvel-comics,based-on-comic,tv-special,fight,violence}'::text[]))
                           ->  Bitmap Heap Scan on movie_keyword mk  (cost=6.80..1079.43 rows=305 width=8)
                                 Recheck Cond: (k.id = keyword_id)
                                 ->  Bitmap Index Scan on keyword_id_movie_keyword  (cost=0.00..6.72 rows=305 width=0)
                                       Index Cond: (keyword_id = k.id)
                     ->  Index Scan using title_pkey on title t  (cost=0.43..0.49 rows=1 width=21)
                           Index Cond: (id = mk.movie_id)
                           Filter: (production_year > 2000)
               ->  Index Scan using movie_id_cast_info on cast_info ci  (cost=0.44..1.33 rows=36 width=8)
                     Index Cond: (movie_id = mk.movie_id)
         ->  Index Scan using name_pkey on name n  (cost=0.43..0.46 rows=1 width=19)
               Index Cond: (id = ci.person_id)
(19 rows)

План дешевле на почти на 20000 у.е.! То есть расширение действительно дает план лучше... Но стоп! планы идентичные, но стоимости разные? Различия наступают в третьем узле — Nested Loop с ci.movie_id = t.id предикатом: DPsize оценивает его в 5339 строк, а DPhyp — в 2108. Как такое вообще могло произойти? Надо найти причину.

Стартовой точкой будет трейсинг запроса, чтобы обнаружить, какие подпланы используются для создания этого NL. Придется делать это отладкой вручную, ведь для подобного нет специальных настроек (есть макрос OPTIMIZER_DEBUG, но он будет выводить уже готовые отношения, а нам нужно проследить порядок выбора, поэтому не подходит).

Для DPsize порядок будет таким:

{1, 2, 3} {5}
{1, 3, 5} {2}
{2, 3, 5} {1}
{1, 5} {2, 3}

Для DPhyp — таким:

{1} {2, 3, 5}
{1, 5} {2, 3}
{1, 3, 5} {2}
{1, 2, 3} {5}

Числа - это ID отношений:

1 - cast_info ci
2 - keyword k
3 - movie_keyword mk
5 - title t

Несмотря на разницу в порядке следования, обрабатываются одни и те же пары, то есть мы ничего не теряем. Но почему же тогда разная стоимость? Давайте зайдем с другой стороны — что это за числа 2108 и 5339 в планах запроса? Если посмотреть в коде, то это поле rows у структуры Path. А как это поле инициализируется? В коде же мы увидим, что rows у структуры Path инициализируется полем rows у RelOptInfo, причем это делается во всех типах узлов плана (небольшая часть примеров):

/* https://github.com/postgres/postgres/blob/144ad723a4484927266a316d1c9550d56745ff67/src/backend/optimizer/path/costsize.c#L3375 */
void
final_cost_nestloop(PlannerInfo *root, NestPath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
{
    /* ... */
    if (path->jpath.path.param_info)
        path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
    else
        path->jpath.path.rows = path->jpath.path.parent->rows;
    /* ... */
}

/* https://github.com/postgres/postgres/blob/144ad723a4484927266a316d1c9550d56745ff67/src/backend/optimizer/path/costsize.c#L3873 */
void
final_cost_mergejoin(PlannerInfo *root, MergePath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
{
    /* ... */
    if (path->jpath.path.param_info)
        path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
    else
        path->jpath.path.rows = path->jpath.path.parent->rows;
    /* ... */
}

/* https://github.com/postgres/postgres/blob/144ad723a4484927266a316d1c9550d56745ff67/src/backend/optimizer/path/costsize.c#L4305 */
void
final_cost_hashjoin(PlannerInfo *root, HashPath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
{
    /* ... */
    if (path->jpath.path.param_info)
        path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
    else
        path->jpath.path.rows = path->jpath.path.parent->rows;
    /* ... */
}

Хорошо, а откуда тогда rows берется в RelOptInfo? Если поискать по коду, то для JOIN мы найдем единственное место ее инициализации — set_joinrel_size_estimates. Вызывается он в двух местах: build_join_rel — создает новый RelOptInfo типа JOIN и build_child_join_rel — то же самое, но для наследуемых таблиц (например, сюда попадают партиции). В нашем случае никаких партиций нет, поэтому используется build_join_rel. Финальная черта — где же в нем выставляется оценка количества строк? Ответ — при первом создании структуры вызывается set_joinrel_size_estimates, которая выставляет это поле, оценивая по текущей паре соединяемых отношений. Другими словами, оценка возвращаемого количества строк происходит единожды, а дальше мы используем эту оценку во всех случаях. Звучит вполне логично, так как на каждое множество отношений предикаты тоже фиксированы, поэтому количество возвращаемых строк не должно зависеть от физической реализации оператора. Но почему же тогда оценка так сильно разнится? Для этого еще раз проведем трейсинг, но на этот раз подсчитаем все вызовы и все оценки, которые мы делаем. Построим дерево, узлами которого будут множества отношений, а дочерними узлами — те, из которых создается родитель. Так как в запросе используется только JOIN INNER, формула вычисления количества кортежей будет такова: nrows = outer_rows * inner_rows * jselect:

• nrows — итоговое количество кортежей;

• outer_rows — количество кортежей во внешней части;

• inner_rows — количество кортежей во внутренней части;

• jselec — селективность предикатов.

Для DPsize стек вызовов будет следующим (под множествами написана селективность предикатов, ребра содержат количество кортежей на выходе):

                     {1, 2, 3, 5}
                        3.95e-7
                    /           \
                9813           1375372
                 /                   \
            {1, 2, 3}                {5}
             7.45e-6  
            /      \ 
     164574168      8
        /            \
    {1, 3}           {2}
     1e-6
    /     \
36245584  4523930 
  /          \
{1}          {3}  

Указанная селективность сильно обрезана, чтобы не занимать много места, так как числа длинные, но даже без этого можно подсчитать, что 9813 * 1375372 * 3.95e-7 = 5332. Если добавить отброшенные разряды, наберется на ожидаемое число — 5339.

Теперь посмотрим, что случилось в DPhyp:

                 {1, 2, 3, 5}
                    3.95e-7
                  /         \   
             36245584        147
               /               \
            {1}             {2, 3, 5}
                              7.45e-6
                            /        \
                           8       2461152
                          /             \
                        {2}           {3, 5}
                                      3.95e-7
                                     /      \
                                 4523930  1375372
                                   /          \
                                 {3}          {5} 

Что и следовало ожидать: 36245584 * 147 * 3.95e-7 = 2104, с округлением это дает 2108.

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

                                                                             QUERY PLAN                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=13720.08..13720.09 rows=1 width=96) (actual time=8753.807..8753.810 rows=1 loops=1)
   ->  Nested Loop  (cost=8.10..13704.27 rows=2108 width=48) (actual time=0.637..8530.663 rows=785477 loops=1)
         ->  Nested Loop  (cost=7.67..12744.50 rows=2108 width=37) (actual time=0.623..2643.045 rows=785477 loops=1)
               Join Filter: (ci.movie_id = t.id)
               ->  Nested Loop  (cost=7.23..12483.46 rows=147 width=41) (actual time=0.610..405.496 rows=14165 loops=1)
                     ->  Nested Loop  (cost=6.80..12351.21 rows=270 width=20) (actual time=0.597..140.721 rows=35548 loops=1)
                           ->  Seq Scan on keyword k  (cost=0.00..3691.40 rows=8 width=20) (actual time=0.143..37.305 rows=8 loops=1)
                                 Filter: (keyword = ANY ('{superhero,sequel,second-part,marvel-comics,based-on-comic,tv-special,fight,violence}'::text[]))
                                 Rows Removed by Filter: 134162
                           ->  Bitmap Heap Scan on movie_keyword mk  (cost=6.80..1079.43 rows=305 width=8) (actual time=0.993..12.278 rows=4444 loops=8)
                                 Recheck Cond: (k.id = keyword_id)
                                 Heap Blocks: exact=23488
                                 ->  Bitmap Index Scan on keyword_id_movie_keyword  (cost=0.00..6.72 rows=305 width=0) (actual time=0.501..0.501 rows=4444 loops=8)
                                       Index Cond: (keyword_id = k.id)
                     ->  Index Scan using title_pkey on title t  (cost=0.43..0.49 rows=1 width=21) (actual time=0.007..0.007 rows=0 loops=35548)
                           Index Cond: (id = mk.movie_id)
                           Filter: (production_year > 2000)
                           Rows Removed by Filter: 1
               ->  Index Scan using movie_id_cast_info on cast_info ci  (cost=0.44..1.33 rows=36 width=8) (actual time=0.008..0.148 rows=55 loops=14165)
                     Index Cond: (movie_id = mk.movie_id)
         ->  Index Scan using name_pkey on name n  (cost=0.43..0.46 rows=1 width=19) (actual time=0.007..0.007 rows=1 loops=785477)
               Index Cond: (id = ci.person_id)
 Planning Time: 1.419 ms
 Execution Time: 8753.873 ms
(24 rows)

В реальности узел дал 785477 кортежей, и ошибка составляет (кратность):

• DPhyp: 370;

• DPsize: 150.

Ошиблись в оценке количества кортежей более чем в два раза, причем в худшую сторону — недосчитались. Но и это еще не все. Вспомните первый пример — запрос с единственным гиперребром. Он планируется очень быстро, но вот если сделать шаг в сторону, например, перенести t7.x в правую строну выражения, мы получим такой план:

-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215344.72 rows=1594323 width=56)
   Join Filter: ((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) > (((((((t7.x + t8.x) + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   ->  Nested Loop  (cost=0.00..93.00 rows=6561 width=32)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                     ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4)
         ->  Materialize  (cost=0.00..5.80 rows=81 width=16)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4)
   ->  Materialize  (cost=0.00..19.94 rows=729 width=24)
         ->  Nested Loop  (cost=0.00..16.29 rows=729 width=24)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4)
 Planning Time: 9.477 ms
(42 rows)

Да, немного медленнее — 9 мс вместо 4 мс, но ведь это все равно быстро. Да, быстро, только вот дело уже не в скорости. Посмотрите, что дает DPsize:

                                                                  QUERY PLAN                                   
-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215311.78 rows=1594323 width=56)
   Join Filter: ((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) > (((((((t7.x + t8.x) + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                     ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4)
         ->  Materialize  (cost=0.00..3.69 rows=27 width=12)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4)
   ->  Materialize  (cost=0.00..47.29 rows=2187 width=28)
         ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4)
 Planning Time: 3337.097 ms
(42 rows)

Время планирования действительно гораздо дольше, но внимательнее всмотритесь в план запроса. Первое, что надо заметить, — стоимость меньше. Взгляните, за счет чего:

                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4)

Да, DPsize смог найти неявную связь между отношениями, даже если они были по разную сторону операндов. DPhyp такого не сделает, так как это разные стороны ребра, а по его правилам такое делать запрещено — нельзя соединять отдельные узлы разных гиперузлов, если они по разные стороны гиперребра, только все вместе. Из этого можно заключить, что DPhyp — это очень хорошая, но все же эвристика. Но, к сожалению, и это не все проблемы.

Для создания гиперребер используется три различных источника, но они не покрывают всех вариантов. Проблема кроется в joinclauses. Во время работы PostgreSQL создает все возможные варианты выражения с разным набором необходимых отношений левой и правой части. Это позволяет рассмотреть разные варианты расположения выражения в дереве. Проблема в том, что используемые там индексы отношений могут относиться не к таблицам, а к индексам узлов JOIN (RangeTblEntry типа RTE_JOIN). И они там не просто так, они "подсказывают" планировщику, какие отношения можно использовать и как переопределить отношения. Для понимания посмотрим на такой запрос (взят из регресс-тестов самого PostgreSQL):

select t1.* from
  text_tbl t1
  left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
    left join int8_tbl i8
      left join (select *, null::int as d2 from int8_tbl i8b2) b2
      on (i8.q1 = b2.q1)
    on (b2.d2 = b1.q2)
  on (t1.f1 = b1.d1)
  left join int4_tbl i4
  on (i8.q2 = i4.f1);

Проблемным здесь является предикат i8.q2 = i4.f1 — для него хранится три копии с разным набором отношений левой и правой части:

• {3} - {8}

• {3, 6} - {8}

• {3, 6, 7} - {8}

3 и 8 — индексы, соответствующие таблицам i8 и i4 соответственно. Но что это за 6 и 7? Это индексы JOIN'ов:

-- 6
(select *, '***'::text as d1 from int8_tbl i8b1) b1
    left join int8_tbl i8
      left join (select *, null::int as d2 from int8_tbl i8b2) b2
      on (i8.q1 = b2.q1)
    on (b2.d2 = b1.q2)

-- 7
text_tbl t1
  left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
    left join int8_tbl i8
      left join (select *, null::int as d2 from int8_tbl i8b2) b2
      on (i8.q1 = b2.q1)
    on (b2.d2 = b1.q2)
  on (t1.f1 = b1.d1)

Это отражает ограничения: i8.q2 = i4.f1 применяется не к самому i8, а к результату LEFT JOINа.

Хорошо, но почему тогда время выполнения больше? Если мы не рассматриваем дополнительные варианты, то это время должно быть меньше. Дело вот в чем.

Если посмотреть на код ванильного планировщика, то можем увидеть, что он достаточно умный. Функция join_search_one_level отвечает за обработку 1 уровня DPsize:

/* src/backend/optimizer/path/joinrels.c */
void
join_search_one_level(PlannerInfo *root, int level)
{
	List	  **joinrels = root->join_rel_level;
	ListCell   *r;
	int			k;

	root->join_cur_level = level;

	/*
	 * Соединяем все предыдущие уровни, с единственной таблицей.
	 */
	foreach(r, joinrels[level - 1])
	{
		RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);

		if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
			has_join_restriction(root, old_rel))
		{
			int			first_rel;

			if (level == 2)
				first_rel = foreach_current_index(r) + 1;
			else
				first_rel = 0;

			make_rels_by_clause_joins(root, old_rel, joinrels[1], first_rel);
		}
		else
		{
			make_rels_by_clauseless_joins(root,
										  old_rel,
										  joinrels[1]);
		}
	}

	/*
	 * Создание "ветвистых" планов - логика DPsize, где рассматриваются
     * пары из отношений с несколькими таблицами, по обеим сторонам
	 */
	for (k = 2;; k++)
	{
		int			other_level = level - k;

		foreach(r, joinrels[k])
		{
			RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
			int			first_rel;
			ListCell   *r2;

			if (k == other_level)
				first_rel = foreach_current_index(r) + 1;
			else
				first_rel = 0;

			for_each_from(r2, joinrels[other_level], first_rel)
			{
				RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);

                /* Создаем план, только есть подходящий предикат */
				if (!bms_overlap(old_rel->relids, new_rel->relids))
				{
					if (have_relevant_joinclause(root, old_rel, new_rel) ||
						have_join_order_restriction(root, old_rel, new_rel))
					{
						(void) make_join_rel(root, old_rel, new_rel);
					}
				}
			}
		}
	}

	/*
     * Создаем CROSS JOIN, если на текущем уровне ничего не смогли создать
	 */
	if (joinrels[level] == NIL)
	{
		foreach(r, joinrels[level - 1])
		{
			RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);

			make_rels_by_clauseless_joins(root,
										  old_rel,
										  joinrels[1]);
		}
	}
}

Ее логика такая:

1. Вначале создаем left-deep/right-deep планы — создаем текущий уровень присоединением 1 таблицы к предыдущему уровню (даже если нет предиката, то есть создаем CROSS JOIN).

2. Затем запускаем основную логику DPsize с рассмотрением всех возможных пар, дающих по итогу нужное количество.

3. В конце, если ничего не смогли найти, то создаем узлы CROSS JOIN'а.

Основная оптимизация заключается во 2 шаге — мы не создаем лишние CROSS JOIN, если они не нужны. Это, по факту, имитация поведения DPhyp, так как его идея в этом и заключается — соединять отношения, только если между ними есть связь.

Остальные микросекунды мы тратим на операционную деятельность:

• Созданием гиперграфа.

• Обход соседей.

• Работа с еще одной хэш-таблицей.

Все эти лишние такты накапливаются и выливаются в еще более длительное выполнение.

Итоги

Расширение, конечно, пока еще довольно сырое. Существующая инфраструктура заточена под особенности PostgreSQL, поэтому для реализации одного функционала приходится искать обходные пути, а другой работает "со скрипом".

Предвосхищаю вопрос: а зачем все это понадобилось? R&D. Как я сказал в начале, планировщик — важная деталь работы СУБД, поэтому исследования в этой области могут в какой-то момент обернуться существенным выигрышем (ключевое слово — "могут"). К сожалению, окупаемость конкретно этой инвестиции сейчас отрицательная — на практике этот алгоритм создает планы и не лучше, и не быстрее.

Подытожим недостатки:

1. Теряются некоторые возможные оптимизации: гиперребра создаются из предикатов, которые на данный момент нельзя полностью трансформировать в гиперребра из-за индексов RangeTable, указывающих НЕ на отношения (например, на JOIN'ы).

2. Несвязные подграфы требуют отдельной обработки: пользователь сам должен указывать расширению как действовать (параметр cj_strategy).

3. Оценка страдает из-за неоптимальных первых аргументов: порядок обрабатываемых пар отношений для JOIN'ов важен, но сейчас он не соотносится с тем, что делает встроенный планировщик.

4. Довольно долгое выполнение: сейчас используется встроенный make_join_rel, но он занимает львиную долю времени.

При всем этом есть и хорошая новость: все поправимо. Ограничения продиктованы одной лишь реализацией, то есть это не какие-то фундаментальные ограничения. Никто не запрещает нам написать свой make_join_rel, оптимизированный под DPhyp. В крайнем случае мы можем пропатчить ядро и добавить то, чего нам недостает. Тем более мы нашли как минимум один запрос, который смогли ускорить в сотни раз, а это может открыть целую область применимости, и значит, работа проделана не зря.

Всем слона.

Ссылки:

• Расширение pg_dphyp

• Dynamic Programming Strikes Back — DPhyp

• Adaptive Optimization of Very Large Join Queries — планирование огромных запросов