8.2.2.3 Optimizing Subqueries with the EXISTS Strategy — MySQL 5.7

8.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)

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

У описанного преобразования есть ограничения. Оно применимо только при игнорировании возможных значений NULL. То есть, стратегия «проталкивания» работает, если оба этих условия верны:

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.
Генератор условий таблицы: если подзапрос является соединением нескольких таблиц, триггерное условие проверяется как можно скорее.

END_OF_DOCUMENT_MARKER

Когда оптимизатор использует триггерное условие для создания доступа на основе поиска по индексу (как для первых двух элементов предыдущего списка), он должен иметь резервный план на случай, если условие отключено. Этот резервный план всегда один и тот же: выполнить полный табличный сканирование. В выводе 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 IN (SELECT inner_expr FROM ...)
```
на это выражение:
```
(outer_expr IS NOT NULL) AND (outer_expr IN (SELECT inner_expr FROM ...))
```
Тогда NULL IN (SELECT ...) никогда не оценивается, потому что MySQL прекращает оценку частей AND как только результат выражения становится ясным.

Еще один возможный вариант переработки:
```
EXISTS (SELECT inner_expr FROM ...
        WHERE inner_expr=outer_expr)
```
Это применимо, когда вам не нужно различать результат подзапроса NULL от FALSE, в этом случае вы можете фактически захотеть EXISTS.

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