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

• выбросить DISTINCT или GROUP BY, которые ничего не делают;

• пометить соединение как Inner Unique: внутренней стороне соответствует не больше одной строки на каждую внешнюю; executor может закончить поиск совпадения по условиям соеднинения, а планировщик использует эту гарантию при оценке стоимости;

• не делать правую сторону IN (SELECT ...) уникальной перед соединением, если она уже уникальна.

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

-- id — первичный ключ, дубликатов нет, но DISTINCT честно выполняется
SELECT DISTINCT id, customer_id FROM orders;
 
-- (b JOIN c) по первичным ключам уникально по b.id,
-- но доказать это для внешнего LEFT JOIN нечем
SELECT ... FROM a LEFT JOIN (b JOIN c ON b.id = c.id) ON a.x = b.id;

В Tantor Postgres мы это исправили: включили в него UniqueKeys. Это механизм, который сейчас предложен и в сообщество PostgreSQL. Разберём, что он умеет, где сознательно не срабатывает и почему выводить уникальность через LEFT JOIN сложнее, чем может показаться.

Что PostgreSQL уже умеет и чего не хватает

Нельзя сказать, что планировщик сейчас совсем ничего не знает об уникальности. Несколько точечных оптимизаций все-таки есть:

• Inner Unique у соединений: Если внутренняя сторона соединения гарантированно даёт не больше одной строки на каждую внешнюю, поиск пары для строки заканчивается на первом совпадении. В EXPLAIN VERBOSE это видно как Inner Unique: true.

• Удаление LEFT JOIN: если к таблице присоединились по уникальному ключу и ни одна её колонка не нужна, соединение просто выбрасывается.

• Удаление лишних колонок из GROUP BY: если в GROUP BY уже есть первичный ключ, остальные колонки этой таблицы из ключа группировки можно убрать.

У всех этих механизмов есть общая проблема: каждый из них сам по-своему смотрит на базовую таблицу и её индексы (иногда ещё на подзапрос с DISTINCT/GROUP BY). Нет общего места, где хранилось бы знание «вот это отношение уникально по вот этим колонкам» и где оно поднималось бы вверх по дереву соединений. Поэтому:

• DISTINCT по первичному ключу не удаляется вообще;

• если внутренняя сторона соединения сама является соединением (например, LEFT JOIN (b JOIN c ON ...)), доказать её уникальность нечем;

• уникальность, известная внутри подзапроса, не всегда доходит до внешнего запроса.

Как это было сделано раньше

До UniqueKeys в Tantor Postgres была отдельная оптимизация: удаление лишнего DISTINCT после GROUP BY. Планировщик проверял, что все выражения группировки присутствуют среди выражений DISTINCT. Тогда разные группы уже не могут дать одинаковые выходные строки, и повторная дедупликация не нужна.  Например:

SELECT DISTINCT customer_id, count(*)
FROM orders
GROUP BY customer_id;
 
--- До оптимизации
HashAggregate                       -- DISTINCT: повторная дедупликация
  Group Key: customer_id, count(*)
  -> HashAggregate                  -- GROUP BY: одна строка на клиента
       Group Key: customer_id
       -> Seq Scan on orders
 
-- После оптимизации
HashAggregate                       -- GROUP BY и вычисление count(*)
  Group Key: customer_id
  -> Seq Scan on orders

GROUP BY уже выдаёт не более одной строки для каждого customer_id, поэтому DISTINCT здесь ничего не меняет. Эта оптимизация оставляла группировку и вычисление count(*), но пропускала построение отдельного шага DISTINCT. Для DISTINCT ON, GROUPING SETS и функций, возвращающих множество строк в SELECT, эта проверка не применялась.

Этот патч был отправлен в рассылку pgsql-hackers. В обсуждении указали, что готовится более общее решение - UniqueKeys. Вместо отдельной проверки сочетания DISTINCT и GROUP BY оно позволяет хранить и передавать между отношениями планировщика доказательства уникальности. Поэтому при интеграции UniqueKeys прежний патч был удалён: его задачу теперь решает общий механизм, который также учитывает уникальные индексы, подзапросы и соединения.

Что такое UniqueKeys

Каждое отношение, которое строит планировщик (RelOptInfo: таблица, подзапрос, соединение, результат группировки), получает список uniquekeys. Один UniqueKey - это утверждение «в выходе этого отношения нет двух строк, совпадающих по вот этому набору выражений». Этот список может оставаться пустым. Две детали делают структуру удобной.

• Выражения хранятся как классы эквивалентности (EquivalenceClass, EC), так же как pathkeys. Для подходящего условия равенства, например во внутреннем соединении, планировщик может объединить a.aid = b.aid в один класс. Там где это равенство выполняется для всех выходных строк, уникальность по одному выражению означает уникальность по другому. Для внешнего соеднинения такой вывод нельзя делать без учета NULL-дополнения. Не нужно хранить отдельный ключ для каждого синонима;

• У ключа есть флаг null_aware. Тут начинается самое интересное.

Проблема NULL

Уникальный индекс и DISTINCT по-разному понимают равенство NULL-ов:

CREATE TABLE t (u int UNIQUE);
INSERT INTO t VALUES (NULL), (NULL), (1);   -- уникальный индекс не против
 
SELECT DISTINCT u FROM t;
-- 1
-- NULL      -- две NULL-строки схлопнулись в одну

Для уникального индекса два NULL-а различны, а для DISTINCT и GROUP BY равны. Значит, UNIQUE (u) по nullable-колонке не даёт права удалить DISTINCT u.

Но для соединений этого достаточно. Условие a.x = t.u с NULL-ом никогда не истинно, поэтому строки с u IS NULL ни с чем не совпадут, и для доказательства Inner Unique они не важны.

Отсюда два уровня гарантии:

• null_aware = true. Строки различны по ключу, даже если считать NULL-ы равными. Это позволяет удалить лишний DISTINCT или GROUP BY при выполнении остальных условий оптимизации.

• null_aware = false. Уникальность гарантирована только для строк без NULL в выражениях ключа. Этого достаточно для Inner Unique, если строгие условия соединения покрывают ключ: NULL-строки не найдут пару. Для удаления DISTINCT или GROUP BY такой гарантии недостаточно.

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

Базовые таблицы

Источник ключей - уникальные индексы, но не любые:

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

• индекс не должен быть частичным (WHERE ...), иначе он покрывает не всю таблицу;

• для обычного индекса ключ получает null_aware = true, если каждый оставшийся компонент - Var, для которого код установил NOT NULL или исключение NULL ограничением, например WHERE u > 0; NULLS NOT DISTINCT дает такую гарантию и без NOT NULL. Для индексов по выражениям вывод NULL-awareness более консервативен.

Колонка ключа, приравненная к константе, из ключа выпадает. Если PRIMARY KEY - (a, b), а в запросе WHERE a = 5, то остаток уникален уже по одному b

EXPLAIN (COSTS OFF) SELECT DISTINCT b FROM uk_pk2 WHERE a = 5;
               QUERY PLAN
----------------------------------------
 Bitmap Heap Scan on uk_pk2
   Recheck Cond: (a = 5)
   ->  Bitmap Index Scan on uk_pk2_pkey
         Index Cond: (a = 5)

Никакого HashAggregate / Unique нет.

Подзапросы и операции над множествами

Подзапрос во FROM может наследовать ключи своего итогового отношения, если все компоненты ключа удаётся сопоставить доступным выходным выражением и интересным EC внешнего запроса. DISTINCT и GROUP BY могут дать такие ключи. Обычный агрегат без GROUP BY и без SRF выдает не более одной строки: HAVING может убрать и её Эта гарантия представляется пустым набором EC внутри UniqueKey. Этоне то же самое, что отсутсвие ключей. UNION, INTERSECT и EXCEPT без ALL дают ключ по всей строке, UNION ALL - нет.

Соединения: два правила

Пусть соединяются A и B. Ключи соединения выводятся из ключей входов по двум правилам:

• Сохранение. Ключ одной стороны остаётся ключом соединения, если соединение не размножает её строки, то есть другая сторона уникальна по условию соединения. Пример: orders JOIN customers ON orders.customer_id = customers.id - каждой строке orders соответствует не больше одного клиента, поэтому соединение по-прежнему уникально по orders.id. semi- и anti-join не размножает строки сохраняемой стороны. Код также учитывает LATERAL: ключ зависимой стороны нельзя автоматически переносить между разными наборами параметров.

• Комбинация. Объединение ключа A и ключа B - ключ соединения. Если две выходные строки совпали и по ключу A, и по ключу B, они получены из одной и той же пары исходных строк, а каждая пара выдаётся не больше одного раза. Даже у CROSS JOIN есть ключ (a.id, b.id).

Внешние соединения и NULL

LEFT JOIN дописывает NULL-ы в колонки правой стороны для строк без пары. Ключ правой стороны можно сохранять отдельно только если левая сторона не размножает её строки; притаком переносе он теряет null_ware. Пустой ключ правой стороны не переносится вообще: отсутсвие колонок не позволяет исключить несколько NULL-дополненных строк. Две строки слева без пары дадут две строки с NULL в ключе правой стороны, и для DISTINCT они одинаковы:

EXPLAIN (COSTS OFF)
SELECT DISTINCT uk_q.id FROM uk_p LEFT JOIN uk_q ON uk_p.id = uk_q.id;
               QUERY PLAN
----------------------------------------
 HashAggregate
   Group Key: uk_q.id
   ->  Hash Left Join
         Hash Cond: (uk_p.id = uk_q.id)
         ...

Ключ левой стороны при LEFT JOIN сохраняется, если правая сторона даёт не более одной пары для каждой левой строки. В этом примере uk_q.id - первичный ключ, поэтому DISTINCT уходит:

EXPLAIN (COSTS OFF)
SELECT DISTINCT uk_p.id, uk_q.v FROM uk_p LEFT JOIN uk_q ON uk_p.id = uk_q.id;
            QUERY PLAN
----------------------------------
 Hash Left Join
   Hash Cond: (uk_p.id = uk_q.id)
   ->  Seq Scan on uk_p
   ->  Hash
         ->  Seq Scan on uk_q

При FULL JOIN реализации не выводит UniqueKeys. Это консервативное ограничение алгоритма, а не утверждение, что ни один FULL JOIN математически не может быть ключа.

Работает и обратное направление: если примененные условия внутреннего соединения позволяют коду доказать отсутсвие NULL для всех компонентов сохраняемого ключа, ему возвращают null_aware. Одного строгого условия по постронней колонке для этого недостаточно. Если uk_nul.u - nullable-колонка с UNIQUE, то сама по себе она не позволяет удалить DISTINCT u. Но после JOIN ... ON uk_nul.u = uk_p.idстрок с u IS NULL в выходе уже нет:

EXPLAIN (COSTS OFF)
SELECT DISTINCT u FROM uk_nul JOIN uk_p ON uk_nul.u = uk_p.id;
            QUERY PLAN
-----------------------------------
 Hash Join
   Hash Cond: (uk_nul.u = uk_p.id)
   ->  Seq Scan on uk_nul
   ->  Hash
         ->  Seq Scan on uk_p

Для semi-join это тоже верно, для anti-join - нет. Выход anti-join состоит как раз из строк, для которых совпадения не нашлось, в том числе с NULL-ами.

Ключи могут сохраняться через цепочки LEFT JOIN, если на каждом шаге выполнены условия сохранения. Сортировка, LIMIT, оконные функции и финальные LockRows/ModifyTable переносят уже известные ключи. GROUP BY и DISTINCT создают ключи по своим выражениям; из входных ключей сохраняются ключи внутри этого набора, а при no_op - все входные ключи.

Что это даёт на практике

Сам по себе список ключей нигде не печатается. Его видно по оптимизациям, которые им пользуются: удаление лишних DISTINCT и GROUP BY дают самые наглядные планы, а Inner Unique для соединений и semi-join без уникализации работают незаметнее, но могут срабатывать и в запросах с подходящими соединениями, если код сумел вывести и сопоставить нуный ключ.

Удаление лишнего DISTINCT

EXPLAIN (COSTS OFF) SELECT DISTINCT a, b, c FROM uk_pk2;   -- PRIMARY KEY (a, b)
     QUERY PLAN
--------------------
 Seq Scan on uk_pk2

Пример до/после есть в существующих регрессионных тестах PostgreSQL. max() без GROUP BY возвращает одну строку, поэтому DISTINCT над ним бессмыслен:

EXPLAIN (COSTS OFF) SELECT DISTINCT max(unique2) FROM tenk1;

--- До патча
 HashAggregate
   Group Key: (InitPlan minmax_1).col1
   InitPlan minmax_1
     ->  Limit
           ->  Index Only Scan Backward using tenk1_unique2 on tenk1
                 Index Cond: (unique2 IS NOT NULL)
 ->  Result
       Replaces: MinMaxAggregate
 
--- После патча
 Result
   Replaces: MinMaxAggregate
   InitPlan minmax_1
     ->  Limit
           ->  Index Only Scan Backward using tenk1_unique2 on tenk1
                 Index Cond: (unique2 IS NOT NULL)

Удаление лишнего GROUP BY

Реализация может убрать группировку, если её выражения покрывают NULL-aware ключ входа, при этом нет агрегатов, HAVING и grouping sets:

EXPLAIN (COSTS OFF) SELECT a, b FROM uk_pk2 GROUP BY a, b, c;
     QUERY PLAN
--------------------
 Seq Scan on uk_pk2

С count(*) группировка, конечно, остаётся: агрегат всё равно нужно посчитать, пусть даже по одной строке на группу.

Inner Unique для сложных внутренних сторон

Раньше Inner Unique доказывался только для базовой таблицы (или простого подзапроса) справа. Теперь внутренней стороной может быть целое соединение:

EXPLAIN (VERBOSE, COSTS OFF)
SELECT uk_p.v FROM uk_p
  LEFT JOIN (uk_q JOIN uk_r ON uk_q.id = uk_r.id) ON uk_p.v = uk_q.id;
 
 Hash Left Join
   Output: uk_p.v
   Inner Unique: true              -- доказано по ключу соединения uk_q ⋈ uk_r
   Hash Cond: (uk_p.v = uk_q.id)
   ->  Seq Scan on public.uk_p
   ->  Hash
         ->  Hash Join
               Inner Unique: true
               Hash Cond: (uk_q.id = uk_r.id)
               ...

Inner Unique не только сокращает поиск пары при выполнении. Он влияет и на стоимость, а значит, планировщик может выбрать другую форму плана. В тестах pg_stash_advice звёздная схема (факт + два измерения через LEFT JOIN) после патча стала строиться так: оба измерения сначала соединяются между собой, а результат идёт внутренней стороной одного Hash Join к таблице фактов:

Hash Join
  Hash Cond: ((f.dim1_id = d1.id) AND (f.dim2_id = d2.id))
  ->  Seq Scan on aa_fact f
  ->  Hash
        ->  Nested Loop
              ->  Seq Scan on aa_dim2 d2
                    Filter: (val2 = 1)
              ->  Seq Scan on aa_dim1 d1
                    Filter: (val1 = 1)

Без патча это были два последовательных соединения: Hash Join с d2 и Nested Loop с индексным доступом к d1.

Semi-join без лишней уникализации

WHERE (x, y) IN (SELECT ...) планировщик может выполнить как обычное соединение, предварительно сделав правую сторону уникальной HashAggregate / Unique. Если правая сторона уже уникальна по нужным колонкам, этот шаг пропускается. Раньше такое умели только когда справа одно отношение (таблица с подходящим уникальным индексом или подзапрос с DISTINCT/GROUP BY), теперь - для любого отношения с подходящим UniqueKey.

Секции и eager aggregation

UniqueKeys работают и с секционированием. Секция содержит подмножество строк родителя, а подмножество уникального множества уникально, поэтому дочерние отношения просто наследуют ключи родителя. В частности, при enable_partitionwise_join = on каждое соединение секций получает Inner Unique: true.

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

Ещё UniqueKeys стыкуются с eager aggregation -оптимизацией, которая позволяет выполнить частичную агрегацию до соединения. Частично сгруппированное отношение уникально по колонкам группировки, а eager aggregation и так обязана группировать по колонкам, нужным соединениям выше. В итоге соединение над частичным агрегатом получает Inner Unique:

Где оптимизация сознательно не срабатывает

Самая опасная ошибка в такой оптимизации - вывести ключ, которого на самом деле нет, и удалить DISTINCT, который был нужен. Запрос тогда вернёт дубликаты, то есть неверный результат. Поэтому в патче много «нет»:

• UNIQUE по nullable-колонке без NOT NULL. Несколько NULL-ов допустимы в индексе, но равны для DISTINCT;

• DEFERRABLE ограничение. Внутри транзакции дубликаты временно возможны;

• Частичный уникальный индекс. Не покрывает всю таблицу;

• Правая сторона LEFT JOIN, обе стороны FULL JOIN. Строки без пары дают NULL-дубликаты;

• UNION ALL. Не удаляет дубликаты;

• SRF в SELECT. Размножает строки;

• Наследование. Уникальность родителя не распространяется на потомков;

• Одна сторона CROSS JOIN. Каждая её строка повторяется для каждой строки другой стороны.

Во всех этих случаях в регрессионных тестах есть и проверка плана, и проверка результата.

Сколько это стоит

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

Чтобы ограничить расходы, патч отслеживает только «интересные» классы эквивалентности, то есть те, которыми может воспользоваться хоть один потребитель:

• колонки DISTINCT;

• колонки GROUP BY, если группировка потенциально может оказаться no-op;

• многотабличные EC, способные породить условия соединения, и обе стороны mergejoinable условий внешних соединений. Это не все выражения произвольного JOIN;

• колонки, которые участвуют в условиях соединения.

Есть и прямой лимит - 8 ключей на отношение. При добавлении ключей код отбрасывает избаточные гарантии: ключ по меньшему набору EC с не более слабой NULL-awareness делает большой ключ ненужным. Ключи joinrel выводятся один раз, из первой пары входов, с которой его построили.

Управление оптимизацией

В Tantor Postgres есть GUC-параметр enable_uniquekeys, включенный по умолчанию.

Итог

UniqueKeys - не одна оптимизация, а своего рода инфраструктура. Каждое промежуточное отношение (таблица, подзапрос, соединение, результат группировки) получает список наборов выражений, по которым его строки гарантированно различны. Ключи протаскиваются снизу вверх через соединения, подзапросы, секции и eager aggregation, с аккуратным учётом NULL-ов и внешних соединений. На этом знании работают сразу несколько оптимизаций:

- удаление лишних DISTINCT и GROUP BY;
- Inner Unique для соединений со сложной внутренней стороной;
- пропуск уникализации в semi-join;
- секции и eager aggregation.

Дальше на этом фундаменте можно строить и другое. В списке планов автора - UNION ALL, VALUES и собственные уникальные индексы секций.

В Tantor Postgres это работает уже сейчас, а если патч примут в PostgreSQL, - будет работать и там. Часть запросов станет дешевле без единой правки в приложении: и те, где ORM или BI добавили «защитный» DISTINCT, и те, где выигрыш даст более точное знание о соединениях.

Патчи UniqueKeys доступны для ревью в PostgreSQL CommitFest.