Оптимизации подзапросов без полусоединений

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

Две основные стратегии для подзапросов без полусоединений — материализация (также называемая материализацией снаружи внутрь) и преобразование IN в EXISTS. Материализация применима только для некоррелированных подзапросов, а преобразование IN в EXISTS можно использовать для коррелированных и некоррелированных подзапросов.

Применимость

Подзапрос IN не может быть приведен к полусоединению в следующих случаях. В примерах ниже используется база данных World из набора регрессионных тестов MariaDB.

Подзапрос в дизъюнкции (ИЛИ)

Подзапрос расположен непосредственно или косвенно под операцией ИЛИ в предложении WHERE внешнего запроса.

Шаблон запроса:

SELECT ... FROM ... WHERE (expr1, ..., exprN) [NOT] IN (SELECT ... ) OR expr;

Пример:

SELECT Name FROM Country
WHERE (Code IN (select Country from City where City.Population > 100000) OR
       Name LIKE 'L%') AND
      surfacearea > 1000000;

Отрицание предиката подзапроса (NOT IN)

Сам предикат подзапроса отрицается.

Шаблон запроса:

SELECT ... FROM ... WHERE ... (expr1, ..., exprN) NOT IN (SELECT ... ) ...;

Пример:

SELECT Country.Name
FROM Country, CountryLanguage 
WHERE Code NOT IN (SELECT Country FROM CountryLanguage WHERE Language = 'English')
  AND CountryLanguage.Language = 'French'
  AND Code = Country;

Подзапрос в предложении SELECT или HAVING

Подзапрос расположен в предложениях SELECT или HAVING внешнего запроса.

Шаблон запроса:

SELECT field1, ..., (SELECT ...)  WHERE ...;
SELECT ...  WHERE ... HAVING (SELECT ...);

Пример:

select Name, City.id in (select capital from Country where capital is not null) as is_capital
from City
where City.population > 10000000;

Подзапрос с UNION

Сам подзапрос является UNION, а предикат IN может находиться в любом месте запроса, где разрешено использование IN.

Шаблон запроса:

... [NOT] IN (SELECT ... UNION SELECT ...)

Пример:

SELECT * from City where (Name, 91) IN
(SELECT Name, round(Population/1000) FROM City WHERE Country = "IND" AND Population > 2500000
UNION
 SELECT Name, round(Population/1000) FROM City WHERE Country = "IND" AND Population < 100000);

Материализация для некоррелированных подзапросов IN

Основы материализации

Основная идея материализации подзапроса заключается в выполнении подзапроса и сохранении его результата во внутренней временной таблице, индексированной по всем её столбцам. Естественно, это возможно только в случае некоррелированного подзапроса. Предикат IN проверяет, присутствует ли его левое операнд в результате подзапроса. Поэтому нет необходимости хранить дублирующиеся строки результатов подзапроса во временной таблице. Хранение только уникальных строк подзапроса даёт две выгоды: размер временной таблицы меньше, и индекс по всем её столбцам может быть уникальным.

Если размер временной таблицы меньше системной переменной tmp_table_size, таблица является хеш-индексированной таблицей HEAP в оперативной памяти. В редких случаях, когда результат подзапроса превышает это ограничение, временная таблица хранится на диске в таблице с индексом B-дерева ARIA или MyISAM (ARIA по умолчанию).

Материализация подзапроса происходит по требованию во время первого выполнения предиката IN. После материализации подзапроса предикат IN оценивается очень эффективно с помощью поиска по индексу внешнего выражения во внутреннем индексе материализованной временной таблицы. Если совпадение найдено, IN истинно, в противном случае IN ложно.

Осведомлённое об отсутствии значения NULL эффективное выполнение

Предикат IN может возвращать NULL, если в одном из его аргументов есть значение NULL. В зависимости от своего расположения в запросе, значение NULL в предикате равно ложно. Это те случаи, когда замена NULL на FALSE отклонит точно те же строки результатов. Результат NULL для IN неотличим от FALSE, если предикат IN:

• не отрицается,
• не является аргументом функции,
• расположен в предложении WHERE или ON.

Во всех этих случаях вычисление IN выполняется, как описано в предыдущем абзаце, с помощью поиска по индексу в материализованном подзапросе. Во всех остальных случаях, когда NULL не может быть заменён на FALSE, использование поиска по индексу невозможно. Это не ограничение сервера, а следствие семантики NULL в стандарте ANSI SQL.

Предположим, что предикат IN вычисляется как

NULL IN (select
not_null_col from t1)

, то есть левое операнд IN имеет значение NULL, а в подзапросе нет значений NULL. В этом случае значение IN ни ложно, ни истинно. Вместо этого оно равно NULL. Если мы выполним поиск по индексу с NULL в качестве ключа, такое значение не будет найдено в not_null_col, и предикат IN неправильно вернёт FALSE.

В общем случае значение NULL с любой стороны от IN действует как «подстановочный символ», который совпадает с любым значением, и если совпадение существует, результат IN равен NULL. Рассмотрим следующий пример:

Если левое операнд IN имеет строку: (7, NULL, 9) , а результат правого операнда подзапроса IN — таблица:

(7, 8, 10)
(6, NULL, NULL)
(7, 11, 9)

Тогда предикат IN соответствует строке (7, 11, 9) , и результат IN равен NULL. Совпадения, где отличающиеся значения с обеих сторон аргументов IN совпадают с NULL в другом аргументе IN, называются *частичными совпадениями*.

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

• Частичное совпадение слиянием идентификаторов строк
  Этот метод используется, когда количество строк в результате подзапроса превышает определённое ограничение. Метод создаёт специальные индексы на некоторых столбцах временной таблицы и объединяет их путём альтернативного сканирования каждого индекса, выполняя операцию, аналогичную пересечению множеств.

• Частичное совпадение со сканированием таблицы
  Этот алгоритм используется для очень маленьких таблиц, когда накладные расходы алгоритма слияния идентификаторов строк не оправданы. Тогда сервер просто сканирует материализованный подзапрос и проверяет частичные совпадения. Поскольку эта стратегия не требует буферов в оперативной памяти, она также используется, когда нет достаточной памяти для хранения индексов стратегии слияния идентификаторов строк.

Ограничения

В принципе, стратегия материализации подзапроса универсальна, однако из-за некоторых технических ограничений в сервере MariaDB есть несколько случаев, когда сервер не может применить эту оптимизацию.

• Поле BLOB
  Либо левое операнд предиката IN ссылается на поле BLOB, либо подзапрос выбирает одно или несколько полей BLOB.

• Несравниваемые поля
  TODO

В указанных случаях сервер возвращается к преобразованию IN в EXISTS.

Преобразование IN в EXISTS

Эта оптимизация была единственной стратегией выполнения подзапросов в более ранних версиях MariaDB и MySQL до MariaDB 5.3. Мы внесли различные изменения и исправили ряд ошибок в этом коде, но по сути он остался прежним.

Обсуждение производительности

Пример ускорения по сравнению с MySQL 5.x и MariaDB 5.1/5.2

В зависимости от запроса и данных любая из двух описанных здесь стратегий может привести к плану, который в разы лучше/хуже, чем другая стратегия.

Более ранние версии MariaDB и любые текущие версии MySQL (включая MySQL 5.5 и MySQL 5.6 DMR по состоянию на июль 2011 года) реализуют только преобразование IN в EXISTS. Как показано ниже, эта стратегия во многих распространённых случаях уступает материализации подзапросов.

Рассмотрим следующий запрос над данными из бенчмарка DBT3 масштаба 10. Найдите клиентов с наибольшим балансом в их странах:

SELECT * FROM part
WHERE p_partkey IN
      (SELECT l_partkey FROM lineitem
       WHERE l_shipdate between '1997-01-01' and '1997-02-01')
ORDER BY p_retailprice DESC LIMIT 10;

Время выполнения этого запроса следующее:

• Время выполнения в MariaDB 5.2/MySQL 5.x (любой MySQL): > 1 ч
  Запрос занимает более одного часа (мы не ждали дольше), что делает его непрактичным для использования подзапросов в таких случаях. Ниже приведённый EXPLAIN показывает, что подзапрос был преобразован в коррелированный, что указывает на преобразование IN в EXISTS.
  

+--+------------------+--------+--------------+-------------------+----+------+---------------------------+
|id|select_type       |table   |type          |key                |ref |rows  |Extra                      |
+--+------------------+--------+--------------+-------------------+----+------+---------------------------+
| 1|PRIMARY           |part    |ALL           |NULL               |NULL|199755|Using where; Using filesort|
| 2|DEPENDENT SUBQUERY|lineitem|index_subquery|i_l_suppkey_partkey|func|    14|Using where                |
+--+------------------+--------+--------------+-------------------+----+------+---------------------------+

• Время выполнения в MariaDB 5.3: 43 сек
  В MariaDB 5.3 выполнение того же запроса занимает менее минуты. EXPLAIN показывает, что подзапрос остаётся некоррелированным, что свидетельствует о его выполнении с помощью материализации подзапросов.
  

+--+------------+-----------+------+------------------+----+------+-------------------------------+
|id|select_type |table      |type  |key               |ref |rows  |Extra                          |
+--+------------+-----------+------+------------------+----+------+-------------------------------+
| 1|PRIMARY     |part       |ALL   |NULL              |NULL|199755|Using temporary; Using filesort|
| 1|PRIMARY     |<subquery2>|eq_ref|distinct_key      |func|     1|                               |
| 2|MATERIALIZED|lineitem   |range |l_shipdate_partkey|NULL|160060|Using where; Using index       |
+--+------------+-----------+------+------------------+----+------+-------------------------------+

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

Для демонстрации преимуществ частичного совпадения мы расширили таблицу customer из бенчмарка DBT3 двумя дополнительными столбцами:

• c_pref_nationkey — предпочтительная страна для покупок,
• c_pref_brand — предпочтительная марка.

Оба столбца имеют значения NULL в процентах в столбце, то есть c_pref_nationkey_05 содержит 5% значений NULL.

Рассмотрим запрос «Найдите всех клиентов, которые не покупали в предпочтительной стране и у предпочтительной марки в определённых диапазонах дат»:

SELECT count(*)
FROM customer
WHERE (c_custkey, c_pref_nationkey_05, c_pref_brand_05) NOT IN
  (SELECT o_custkey, s_nationkey, p_brand
   FROM orders, supplier, part, lineitem
   WHERE l_orderkey = o_orderkey and
         l_suppkey = s_suppkey and
         l_partkey = p_partkey and
         p_retailprice < 1200 and
         l_shipdate >= '1996-04-01' and l_shipdate < '1996-04-05' and
         o_orderdate >= '1996-04-01' and o_orderdate < '1996-04-05');

• Время выполнения в MariaDB 5.2/MySQL 5.x (любой MySQL): 40 сек
• Время выполнения в MariaDB 5.3: 2 сек

Ускорение для этого запроса составляет 20 раз.

Рекомендации по производительности

TODO

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

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

Все вышеуказанные стратегии можно контролировать с помощью следующих переключателей в системной переменной optimizer_switch.

• materialization=on/off
  В некоторых очень редких случаях, даже если материализация была принудительно включена, оптимизатор всё равно может вернуться к стратегии IN-TO-EXISTS, если материализация неприменима. В тех случаях, когда материализация требует частичного совпадения (из-за наличия значений NULL), существуют два подчиненных переключателя, которые управляют двумя стратегиями частичного совпадения:
  
  • partial_match_rowid_merge=on/off
    Этот переключатель управляет стратегией слияния идентификаторов строк. Кроме этого переключателя, системная переменная rowid_merge_buff_size контролирует максимальную память, доступную для стратегии слияния идентификаторов строк.
  • partial_match_table_scan=on/off
    Управляет альтернативной стратегией частичного совпадения, которая выполняет сопоставление с помощью сканирования таблицы.

• in_to_exists=on/off
  Этот переключатель управляет преобразованием IN в EXISTS.

• Переменные системы tmp_table_size и max_heap_table_size
  Переменная системы tmp_table_size устанавливает верхний предел для внутренних временных таблиц памяти. Если внутренняя временная таблица превышает этот размер, она автоматически преобразуется в таблицу Aria или MyISAM на диске с индексом B-дерева. Однако обратите внимание, что таблица памяти не может быть больше, чем max_heap_table_size.

Два основных переключателя оптимизатора - materialization и in_to_exists не могут быть одновременно выключены. Если оба установлены в выключенное состояние, сервер выдаст ошибку.