Оптимизация Asymmetric Join (AJ) — это новый подход к объединению партицированных (partitioned relation, PR) и непартицированных связей (non-partitioned relation, NR). Её суть в том, что каждая партиция присоединяется с помощью NR, а результаты объединяются с помощью APPEND. Всё это выглядит как эволюция техники Partitionwise Join (PWJ).
Мы можем переписать запрос:
SELECT * FROM A JOIN partitioned B ON A.x=B.x;с помощью UNION ALL:
(SELECT * FROM A JOIN B_1 ON A.x=B_1.x)
UNION ALL
(SELECT * FROM A JOIN B_1 ON A.x=B_2.x);Стратегия реализуется в основном в файлах 'relnode.c' и 'joinrels.c'.
Преимущества стратегии
Повышает эффективность Parallel Append
Позволяет выбирать стратегию присоединения для каждой партиции
Оператору Аppend не приходится комбинировать большие связи, т. к. он может отсеивать кортежи в дочернем join. Это поможет и в случаях, когда join или целевой список содержат «тяжёлое» условие
Позволяет пушить условие партиционирования напрямую в inner, что улучшает фильтрацию процедуры сканирования таблицы
Уменьшает размер хэш-таблицы каждого дочернего HashJoin и снимает проблему перекоса данных
Позволяет находить дополнительные способы обрезки партиций
Помогает FDW развиваться в направлении отправляемых FOREIGN TABLES по аналогии с отправляемыми функциями
Недостатки и ограничения стратегии
Недостаток стратегии заключается в постоянно растущем пространстве поиска планов, а ограничений два:
в качестве inner AppendJoin (AJ) может быть таблица или поддерево запроса, который не содержит партицированных таблиц в родительском дереве;
outer AJ не может ссылаться на inner.
Как работает стратегия
Код почти аналогичен partitionwise_join, изменения коснулись лишь трёх его частей. Их мы сейчас и рассмотрим.
build_joinrel_partition_info
В первой части AJ инициализируются два свойства партиционирования структуры RelOptInfo: part_scheme и part_exprs. Логика AJ добавлена в конец функции — мы переходим к ней, если не можем применить PWJ. Поскольку оптимизатор не вызывает эту функцию с обратным порядком inner и outer (для метода partitionwise это не имеет смысла), проверяем оба варианта размещения инпутов. В случае AJ inner не имеет свойств партиционирования, они наследуются от outer. Здесь же оптимизатор устанавливает флаг consider_asymmetric_join, а значит, joinrel потенциально может выполняться методом PWJ и служить инпутом для PWJ или AJ (только outer) на более высоком уровне.
Асимметричная природа build_joinrel_partition_info отличает эту технику присоединения от других. Допустим, нужно соединить две партицированные по одной схеме таблицы P1, P2 и одну обычную таблицу T. Если при первой попытке outer = (P1, P2), inner = (T), то построить PWJ невозможно, и инициализируется AJ. При следующей попытке external = (P1, T), inner = (P2), и вариант PWJ не рассматривается. Если изменить порядок перебора комбинаций, оптимизатор попытается сначала построить (P1, T) JOIN (P2), затем проинициализировать PWJ, а последующие AJ между (P1, T) JOIN (P2) или (P1) JOIN (T, P2) будут отклонены. Например, в регрессионные тесты в файле partition_join.sql добавлены следующие запросы:
EXPLAIN (COSTS OFF) -- PWJ on top
SELECT * from prt1 d1, unnest(array[3,4]) n, prt2 d2
WHERE d1.a = n AND d2.b = d1.a;
EXPLAIN (COSTS OFF) -- AJ on top
SELECT * from prt1 d1, prt2 d2, unnest(array[3,4]) n
WHERE d1.a = n AND d2.b = d1.a;Неважно, из какой комбинации inner и outer оптимизатор пытается построить joinrel — part_scheme будет точно таким же указателем, а part_exprs соответствовать перестановке элементов. В дальнейшем можно будет устранить зависимость от вышеописанного порядка комбинаций inner и outer.
Остаётся открытым вопрос: могут ли для одного и того же joinrel одни комбинации inner и outer разрешать AJ, а другие — нет? Чтобы ответить на него, мы добавили в build_join_rel() с включенными assertions, который проверяет, создана ли part_scheme для уже существующего joinrel. Если не создана, то и после выполнения процедуры build_joinrel_partition_info она не появится. Этот механизм не рассматривает все возможные варианты, но помогает выявить ошибки в автотестах.
При использовании AJ мы должны либо сохранять разрешённые комбинации inner и outer, либо перепроверять условия AJ в функции try_asymmetric_partitionwise_join. С точки зрения логики первый вариант дешевле.
В отличие от AJ, флаг consider_partitionwise_join в PWJ устанавливается в RelOptInfo постепенно на разных уровнях, начиная с самого нижнего — партицированной таблицы. Получается дерево, все элементы которого имеют разрешенные свойства. Если идти тем же путём в AJ, то сначала придётся проверить всевозможные TABLESAMPLE, Function Scan и т. д. Допрасходов не избежать даже в запросах без парттицированных таблиц. В этой реализации build_joinrel_partition_info проверяет и устанавливает свойства AJ для поддерева запроса.
Проверять все записи и условия поддерева в каждой комбинации слишком дорого. Может быть изобрести флаг safe_for_asymmetric_join? Тогда нужно будет проверять только текущий RelOptInfo и флаги нижележащих — близко к реализации PWJ.
try_asymmetric_partitionwise_join
Вызывается в populate_joinrel_with_paths сразу после try_partitionwise_join. Поскольку caller навряд ли будет проверять упорядочивание входов, сделаем это сами. Логически мы можем поменять местами inner и outer, заменив, например, jointype с LEFT OUTER JOIN на RIGHT OUTER JOIN. Будет ли это технически просто и целесообразно — хороший вопрос. В любом случае, первым шагом должен стать демозапрос, показывающий ограничения нашей оптимизации, которые привносит этот фрагмент кода.
Здесь мы просто перепроверяем корректность AJ на внутреннем уровне в момент построения дочернего joinrel.
Далее мы инициализируем boundinfo, nparts, part_rels — поля RelOptInfo, связанные с партиционированием. Если эти поля уже инициализированы, просто проверяем идентичность схемы разбиения:
Assert(joinrel->nparts == prel->nparts && joinrel->part_rels != NULL);Если всё в порядке, мы проходим по каждому разделу из внешнего и строим join с внутренним. Сложный момент — замена ссылок на relid партицированной таблицы с relid её партиции.
Затем вызываем populate_joinrel_with_paths и добавляем пути в pathlist дочернего joinrel для комбинации inner и outer.
generate_partitionwise_join_paths
Здесь мы собираем все «живые» part_rels данного rel (рекурсивно) и строим APPEND — завершаем построение partitionwise-путей. Изменения минимальны: с точки зрения этой функции, связанные с разделами поля RelOptInfo для AJ и PWJ идентичны. Нам просто нужно исправить некоторые проверки на консистентность.
Репараметризация
Репараметризация (Parameterised NestLoop) — важная функция, которая взаимодействует с AJ. Параметризованное выражение может ссылаться на outer AJ, который может находиться на внешней стороне параметризованного NestLoop (PNL). Каждый путь в дочернем join AJ может ссылаться на один и тот же базовый путь в outer. При репараметризации, изменяющей такой путь, предварительно сделайте его копию.
Для корректной обработки мы ввели функцию is_asymmetric_join, которая выявляет случаи, когда путь является асимметричным join, и вызывает замену relid в копии пути. Критерий AJ следующий: один из инпутов — партиция, а другой — baserel или joinrel. Мы можем захватить и лишние случаи, но копирование вместо замены не ухудшит ситуацию — мы просто потратим больше памяти.
Нерешённые вопросы
До сих пор не очевидно, проверяем ли мы внутреннее поддерево полностью и корректно. Что если условие join содержит волатильную функцию?
Мы не выяснили, как расширить массив root->simple_***. Без этого у нас нет нативной интеграции с ядром PostgreSQL.
Схема AJ и PWJ такова, что многократное применение AJ к одному и тому же joinrel с различными комбинациями inner/outer, похоже, не приводит к различным схемам партиционирования. Но может ли одно простое условие партиционирования вызывать различия с другой комбинацией простых и партиционированных связей? Может ли это привести к разным part_rels[i] и как это может повлиять на построение плана?