10.2.2.3 Optimizing Subqueries with the EXISTS Strategy — MySQL 9.2

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, «Переключаемые оптимизации».