Оптимизация EXISTS-в-IN

MySQL (включая MySQL 5.6) имеет только одну стратегию выполнения подзапросов EXISTS. Стратегия в сущности является прямой, «наивной» стратегией выполнения без каких-либо переписываний.

MariaDB 5.3 ввела богатый набор оптимизаций для подзапросов IN. С тех пор имеет смысл конвертировать подзапрос EXISTS в IN, чтобы использовать новые оптимизации.

EXISTS будет преобразовано в IN в двух случаях:

1. Тривиально коррелированные подзапросы EXISTS
2. Полусоединения EXISTS

Теперь мы подробно опишем эти два случая.

Тривиально коррелированные подзапросы EXISTS

Часто подзапрос EXISTS коррелирован, но корреляция тривиальна. Подзапрос имеет вид

EXISTS (SELECT ...  FROM ... WHERE outer_col= inner_col AND inner_where)

и «outer_col» — единственное место, где подзапрос ссылается на внешние поля. В этом случае подзапрос может быть переписан в некоррелированный IN:

outer_col IN (SELECT inner_col FROM ... WHERE inner_where)

(NULL значения требуют некоторой специальной обработки, см. ниже). Для некоррелированных подзапросов IN MariaDB способна выбирать между двумя стратегиями выполнения на основе стоимости:

• IN-в-EXISTS (в основном, преобразование обратно в EXISTS)
• Материализация

То есть преобразование тривиально коррелированного EXISTS в некоррелированный IN даёт оптимизатору запросов возможность использовать стратегию материализации для подзапроса.

В настоящее время преобразование EXISTS->IN работает только для подзапросов, которые находятся на верхнем уровне оператора WHERE или находятся под операцией NOT, которая непосредственно находится на верхнем уровне оператора WHERE.

Подзапросы EXISTS полусоединения

Если EXISTS подзапрос является частью AND-оператора в WHERE операторе:

SELECT ... FROM outer_tables WHERE EXISTS (SELECT ...) AND ...

то он удовлетворяет основному свойству подзапросов полусоединения:

с подзапросом полусоединения нас интересуют только записи внешних таблиц, которые имеют соответствия в подзапросе

Оптимизатор полусоединений предлагает богатый набор стратегий выполнения для как коррелированных, так и некоррелированных подзапросов. Набор включает стратегию FirstMatch, которая является эквивалентом того, как выполняются подзапросы EXISTS, поэтому мы не теряем никаких возможностей при преобразовании подзапроса EXISTS в полусоединение.

Теоретически имеет смысл преобразовывать все виды подзапросов EXISTS: преобразовывать как коррелированные, так и некоррелированные, независимо от того, имеет ли подзапрос равенство inner=outer.

На практике подзапрос будет преобразован только в том случае, если он имеет равенство inner=outer. Преобразуются как коррелированные, так и некоррелированные подзапросы.

Обработка значений NULL

TODO: перефразировать это:

• IN имеет сложную семантику NULL. NOT EXISTS — нет.
• EXISTS-в-IN добавляет IS NOT NULL перед предикатом подзапроса, если это необходимо

Управление

Оптимизация управляется флагом exists_to_in в optimizer_switch. До MariaDB 10.0.12 оптимизация по умолчанию была выключена. Начиная с MariaDB 10.0.12, она включена по умолчанию.

Ограничения

EXISTS-в-IN не обрабатывает

• подзапросы, содержащие GROUP BY, агрегатные функции или оператор HAVING
• подзапросы являются UNION
• ряд вырожденных особых случаев