10.2.2.3 Optimizing Subqueries with the EXISTS Strategy — MySQL 8.4

10.2.2.3 Оптимизация подзапросов с помощью стратегии EXISTS

Некоторые оптимизации применимы к сравнениям, которые используют оператор IN (или =ANY) для проверки результатов подзапроса. В этом разделе рассматриваются эти оптимизации, особенно в отношении проблем, которые представляют собой значения NULL. Последняя часть обсуждения предлагает, как вы можете помочь оптимизатору.

Рассмотрим следующее сравнение подзапроса:

outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)

MySQL оценивает запросы «“от внешнего к внутреннему.” То есть, он сначала получает значение внешнего выражения outer_expr, а затем выполняет подзапрос и сохраняет строки, которые он генерирует.

Очень полезная оптимизация заключается в том, чтобы «“информировать” подзапрос о том, что единственные строки, представляющие интерес, — это те, где внутреннее выражение inner_expr равно outer_expr. Это делается путем внедрения соответствующего равенства в предложение WHERE подзапроса, чтобы сделать его более ограниченным. Преобразованное сравнение выглядит следующим образом:

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)

После преобразования MySQL может использовать внедренное равенство, чтобы ограничить количество строк, которые он должен проверить для оценки подзапроса.

Более общим образом, сравнение значений N с подзапросом, возвращающим строки с значениями N, подчиняется тому же преобразованию. Если oe_i и ie_i представляют соответствующие значения внешнего и внутреннего выражений, это сравнение подзапроса:

(oe_1, ..., oe_N) IN
  (SELECT ie_1, ..., ie_N FROM ... WHERE subquery_where)

Становится:

EXISTS (SELECT 1 FROM ... WHERE subquery_where
                          AND oe_1 = ie_1
                          AND ...
                          AND oe_N = ie_N)

Для простоты в последующем обсуждении предполагается одна пара значений внешнего и внутреннего выражений.

Стратегия «“внедрения”, которая только что была описана, работает, если выполняется одно из этих условий:

outer_expr и inner_expr не могут быть NULL.
Вам не нужно различать результаты подзапроса NULL от FALSE. Если подзапрос является частью выражения OR или AND в предложении WHERE, MySQL предполагает, что вам это не нужно. Другой случай, когда оптимизатор замечает, что результаты подзапросов NULL и FALSE не нужно различать, — это такой конструкт:
```
... WHERE outer_expr IN (subquery)
```
В этом случае предложение WHERE отвергает строку, независимо от того, вернул ли подзапрос IN (subquery) значение NULL или FALSE.

Предположим, что outer_expr известно как значение, отличное от NULL, но подзапрос не генерирует строку, такую, что outer_expr = inner_expr. Тогда outer_expr IN (SELECT ...) оценивается следующим образом:

NULL, если оператор SELECT генерирует хотя бы одну строку, где inner_expr равно NULL
FALSE, если оператор SELECT генерирует только значения, отличные от NULL, или не генерирует ничего

В этой ситуации подход к поиску строк с outer_expr = inner_expr больше недействителен. Необходимо искать такие строки, но если они не найдены, также следует искать строки, где inner_expr равно NULL. Грубо говоря, подзапрос можно преобразовать во что-то вроде этого:

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND
        (outer_expr=inner_expr OR inner_expr IS NULL))

Необходимость оценки дополнительного условия IS NULL объясняет, почему у MySQL есть метод доступа ref_or_null:

mysql> EXPLAIN
       SELECT outer_expr IN (SELECT t2.maybe_null_key
                             FROM t2, t3 WHERE ...)
       FROM t1;
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: t1
...
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: t2
         type: ref_or_null
possible_keys: maybe_null_key
          key: maybe_null_key
      key_len: 5
          ref: func
         rows: 2
        Extra: Using where; Using index
...

Методы доступа подзапросов unique_subquery и index_subquery также имеют варианты «“или NULL”.

Дополнительное условие OR ... IS NULL делает выполнение запроса немного сложнее (и некоторые оптимизации внутри подзапроса становятся неприменимыми), но, как правило, это приемлемо.

Ситуация становится намного хуже, когда outer_expr может быть NULL. Согласно интерпретации SQL значения NULL как «“неизвестное значение,”” NULL IN (SELECT inner_expr ...) должно оцениваться как:

NULL, если оператор SELECT генерирует любые строки
FALSE, если оператор SELECT не генерирует строк

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

В сущности, должны быть разные способы выполнения подзапроса в зависимости от значения outer_expr.

Оптимизатор выбирает соответствие стандартам SQL над скоростью, поэтому он учитывает возможность того, что outer_expr может быть NULL:

Если outer_expr равно NULL, для оценки следующего выражения необходимо выполнить оператор SELECT, чтобы определить, генерирует ли он какие-либо строки:
```
NULL IN (SELECT inner_expr FROM ... WHERE subquery_where)
```
Здесь необходимо выполнить исходный оператор SELECT без каких-либо внедренных равенств, упомянутых ранее.
С другой стороны, когда outer_expr не равно NULL, абсолютно необходимо, чтобы это сравнение:
```
outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)
```
Было преобразовано в это выражение, использующее внедренное условие:
```
EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)
```
Без этого преобразования подзапросы работают медленно.

Чтобы разрешить дилемму о том, внедрять или нет условия в подзапрос, условия заключаются в «“триггерных” функциях. Таким образом, выражение следующего вида:

outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)

Преобразуется в:

EXISTS (SELECT 1 FROM ... WHERE subquery_where
                          AND trigcond(outer_expr=inner_expr))

Более общим образом, если сравнение подзапроса основано на нескольких парах внешних и внутренних выражений, преобразование принимает такое сравнение:

(oe_1, ..., oe_N) IN (SELECT ie_1, ..., ie_N FROM ... WHERE subquery_where)

И преобразует его в это выражение:

EXISTS (SELECT 1 FROM ... WHERE subquery_where
                          AND trigcond(oe_1=ie_1)
                          AND ...
                          AND trigcond(oe_N=ie_N)
       )

Каждая trigcond(X) — это специальная функция, которая возвращает следующие значения:

X, когда связанное внешнее выражение oe_i не равно NULL
TRUE, когда связанное внешнее выражение oe_i равно NULL

Примечание

Триггерные функции — это не триггеры того типа, которые вы создаёте с помощью CREATE TRIGGER.

Равенства, заключенные в функции trigcond(), не являются предикатными выражениями первого класса для оптимизатора запроса. Большинство оптимизаций не могут работать с предикатами, которые могут включаться и выключаться во время выполнения запроса, поэтому они предполагают, что любая trigcond(X) — это неизвестная функция и игнорируют её. Триггерные равенства могут быть использованы этими оптимизациями:

Оптимизации ссылок: trigcond(X=Y [OR Y IS NULL]) могут быть использованы для создания доступа к таблицам типа ref, eq_ref или ref_or_null.
Движки выполнения подзапросов на основе поиска по индексу: trigcond(X=Y) могут быть использованы для создания доступа типа unique_subquery или index_subquery.
Генератор условий таблиц: Если подзапрос является соединением нескольких таблиц, проверка триггерного условия производится как можно скорее.

Когда оптимизатор использует триггерное условие для создания какого-либо доступа на основе поиска по индексу (как в первых двух пунктах выше), он должен иметь стратегию резервного копирования для случая, когда условие отключено. Эта резервная стратегия всегда одинакова: выполнить полный сканирование таблицы. В выводе EXPLAIN резервная стратегия отображается как Full scan on NULL key в столбце Extra.

mysql> EXPLAIN SELECT t1.col1,
       t1.col1 IN (SELECT t2.key1 FROM t2 WHERE t2.col2=t1.col2) FROM t1\G
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: t1
        ...
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: t2
         type: index_subquery
possible_keys: key1
          key: key1
      key_len: 5
          ref: func
         rows: 2
        Extra: Using where; Full scan on NULL key

Если вы выполните EXPLAIN за которым следует SHOW WARNINGS, вы сможете увидеть сработавшее условие:

*************************** 1. row ***************************
  Level: Note
   Code: 1003
Message: select `test`.`t1`.`col1` AS `col1`,
         <in_optimizer>(`test`.`t1`.`col1`,
         <exists>(<index_lookup>(<cache>(`test`.`t1`.`col1`) in t2
         on key1 checking NULL
         where (`test`.`t2`.`col2` = `test`.`t1`.`col2`) having
         trigcond(<is_not_null_test>(`test`.`t2`.`key1`))))) AS
         `t1.col1 IN (select t2.key1 from t2 where t2.col2=t1.col2)`
         from `test`.`t1`

Использование сработавших условий имеет некоторые последствия для производительности. Выражение NULL IN (SELECT ...) теперь может привести к полному сканированию таблицы (что медленно), тогда как ранее этого не происходило. Это плата за правильные результаты (цель стратегии условий триггеров — улучшить соответствие, а не скорость).

Для подзапросов с несколькими таблицами выполнение NULL IN (SELECT ...) особенно медленно, потому что оптимизатор соединений не оптимизирует случай, когда внешнее выражение является NULL. Он предполагает, что оценки подзапросов с NULL в левой части очень редки, даже если существуют статистические данные, которые свидетельствуют об обратном. С другой стороны, если внешнее выражение может быть NULL, но фактически им никогда не является, никакой штраф за производительность не накладывается.

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

Объявите столбец как NOT NULL, если он действительно таковым является. Это также помогает другим аспектам оптимизатора, упрощая проверку условий для столбца.
Если вам не нужно различать результат подзапроса NULL от FALSE, вы можете легко избежать медленного пути выполнения. Замените сравнение, которое выглядит так:
```
outer_expr [NOT] IN (SELECT inner_expr FROM ...)
```
на это выражение:
```
(outer_expr IS NOT NULL) AND (outer_expr [NOT] IN (SELECT inner_expr FROM ...))
```
Тогда NULL IN (SELECT ...) никогда не будет вычисляться, потому что MySQL прекращает вычисление частей AND как только результат выражения становится ясен.

Еще один возможный пересмотр:
```
[NOT] EXISTS (SELECT inner_expr FROM ...
        WHERE inner_expr=outer_expr)
```

Флаг subquery_materialization_cost_based системной переменной optimizer_switch позволяет контролировать выбор между материализацией подзапроса и преобразованием подзапроса IN в EXISTS. См. Раздел 10.9.2, «Переключаемые оптимизации».