Стратегия материализации полусоединения

Материализация полусоединения — это особый вид материализации подзапросов, используемый для подзапросов полусоединения. Она фактически включает две стратегии:

• Материализация/поиск
• Материализация/сканирование

Идея

Рассмотрим запрос, который находит страны в Европе, имеющие большие города:

select * from Country 
where Country.code IN (select City.Country 
                       from City 
                       where City.Population > 7*1000*1000)
      and Country.continent='Europe'

Подзапрос некоррелирован, то есть его можно выполнить независимо от основного запроса. Идея материализации полусоединения заключается в том, чтобы сделать именно это и заполнить временную таблицу возможными значениями поля City.country для крупных городов, а затем выполнить соединение со странами в Европе:

Соединение можно выполнить в двух направлениях:

1. Из материализованной таблицы в страны Европы
2. Из стран Европы в материализованную таблицу

Первый способ включает полное сканирование материализованной таблицы, поэтому мы называем его «Материализация-сканирование».

Если вы выполните соединение от стран к материализованной таблице, самый дешевый способ найти совпадение в материализованной таблице — выполнить поиск по первичному ключу (он у неё есть: мы использовали его для удаления дубликатов). Поэтому мы называем эту стратегию «Материализация-поиск».

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

Материализация-Сканирование

Если мы решили искать города с населением более 7 миллионов человек, оптимизатор воспользуется стратегией Материализация-Сканирование, и EXPLAIN покажет это:

MariaDB [world]> explain select * from Country where Country.code IN 
  (select City.Country from City where  City.Population > 7*1000*1000);
+----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
| id | select_type  | table       | type   | possible_keys      | key        | key_len | ref                | rows | Extra                 |
+----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
|  1 | PRIMARY      | <subquery2> | ALL    | distinct_key       | NULL       | NULL    | NULL               |   15 |                       |
|  1 | PRIMARY      | Country     | eq_ref | PRIMARY            | PRIMARY    | 3       | world.City.Country |    1 |                       |
|  2 | MATERIALIZED | City        | range  | Population,Country | Population | 4       | NULL               |   15 | Using index condition |
+----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
3 rows in set (0.01 sec)

Здесь вы можете увидеть:

• Всё ещё есть две SELECT (ищите столбцы с id=1 и id=2)
• Второй select (с id=2) имеет select_type=MATERIALIZED. Это означает, что он будет выполнен, и его результаты будут сохранены во временной таблице с уникальным ключом по всем столбцам. Уникальный ключ нужен, чтобы предотвратить наличие в таблице дублирующих записей.
• Первый select получил имя таблицы <subquery2>. Это таблица, которая была получена в результате материализации select с id=2.

Оптимизатор выбрал полное сканирование материализованной таблицы, поэтому это пример использования стратегии Материализация-Сканирование.

Что касается затрат на выполнение, мы будем читать 15 строк из таблицы City, записывать 15 строк в материализованную таблицу, считывать их обратно (оптимизатор предполагает, что дубликатов не будет), а затем выполнить 15 eq_ref обращений к таблице Country. В итоге мы выполним 45 чтений и 15 записей.

Для сравнения, если вы запустите EXPLAIN в MySQL, вы получите следующее:

MySQL [world]> explain select * from Country where Country.code IN 
  (select City.Country from City where  City.Population > 7*1000*1000);
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+
| id | select_type        | table   | type  | possible_keys      | key        | key_len | ref  | rows | Extra                              |
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+
|  1 | PRIMARY            | Country | ALL   | NULL               | NULL       | NULL    | NULL |  239 | Using where                        |
|  2 | DEPENDENT SUBQUERY | City    | range | Population,Country | Population | 4       | NULL |   15 | Using index condition; Using where |
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+

...что является планом для выполнения (239 + 239*15) = 3824 чтений таблиц.

Материализация-Поиск

Давайте немного изменим запрос и найдём страны, имеющие города с населением более одного миллиона (вместо семи):

MariaDB [world]> explain select * from Country where Country.code IN 
  (select City.Country from City where  City.Population > 1*1000*1000) ;
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
| id | select_type  | table       | type   | possible_keys      | key          | key_len | ref  | rows | Extra                 |
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
|  1 | PRIMARY      | Country     | ALL    | PRIMARY            | NULL         | NULL    | NULL |  239 |                       |
|  1 | PRIMARY      | <subquery2> | eq_ref | distinct_key       | distinct_key | 3       | func |    1 |                       |
|  2 | MATERIALIZED | City        | range  | Population,Country | Population   | 4       | NULL |  238 | Using index condition |
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
3 rows in set (0.00 sec)

Вывод EXPLAIN аналогичен выводу, использующему Материализация-сканирование, за исключением того, что:

• таблица <subquery2> обрабатывается с помощью метода доступа eq_ref
• доступ использует индекс под названием distinct_key

Это означает, что оптимизатор планирует выполнять поиск по индексу в материализованной таблице. Другими словами, мы будем использовать стратегию Материализация-поиск.

В MySQL (или с optimizer_switch='semijoin=off,materialization=off') вы получите следующее EXPLAIN:

MySQL [world]> explain select * from Country where Country.code IN 
  (select City.Country from City where  City.Population > 1*1000*1000) ;
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+
| id | select_type        | table   | type           | possible_keys      | key     | key_len | ref  | rows | Extra       |
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+
|  1 | PRIMARY            | Country | ALL            | NULL               | NULL    | NULL    | NULL |  239 | Using where |
|  2 | DEPENDENT SUBQUERY | City    | index_subquery | Population,Country | Country | 3       | func |   18 | Using where |
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+

Можно увидеть, что оба плана выполнят полное сканирование таблицы Country. На втором этапе MariaDB заполнит материализованную таблицу (238 строк из таблицы City и запишет их во временную таблицу), а затем выполнит поиск по уникальному ключу для каждой записи в таблице Country, что составляет 238 уникальных поисков по ключу. В итоге второй этап будет стоить (239+238) = 477 чтений и 238 записей во временную таблицу.

План MySQL для второго этапа заключается в чтении 18 строк с помощью индекса по City.Country для каждой записи, полученной для таблицы Country. Это приводит к затратам в (18*239) = 4302 чтений. Если бы вызовов подзапроса было меньше, этот план был бы лучше, чем тот, что с Материализацией. Кстати, в MariaDB тоже есть возможность использования такого плана запроса (см. Стратегию FirstMatch), но он не был выбран.

Подзапросы с группировкой

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

Это позволяет эффективно выполнять запросы, которые ищут лучший/последний элемент в определенной группе.

Например, давайте найдем города, имеющие наибольшее население на своем континенте:

explain 
select * from City 
where City.Population in (select max(City.Population) from City, Country 
                          where City.Country=Country.Code 
                          group by Continent)
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
| id   | select_type  | table       | type | possible_keys | key        | key_len | ref                              | rows | Extra           |
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
|    1 | PRIMARY      | <subquery2> | ALL  | distinct_key  | NULL       | NULL    | NULL                             |  239 |                 |
|    1 | PRIMARY      | City        | ref  | Population    | Population | 4       | <subquery2>.max(City.Population) |    1 |                 |
|    2 | MATERIALIZED | Country     | ALL  | PRIMARY       | NULL       | NULL    | NULL                             |  239 | Using temporary |
|    2 | MATERIALIZED | City        | ref  | Country       | Country    | 3       | world.Country.Code               |   18 |                 |
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
4 rows in set (0.00 sec)

города:

+------+-------------------+---------+------------+
| ID   | Name              | Country | Population |
+------+-------------------+---------+------------+
| 1024 | Mumbai (Bombay)   | IND     |   10500000 |
| 3580 | Moscow            | RUS     |    8389200 |
| 2454 | Macao             | MAC     |     437500 |
|  608 | Cairo             | EGY     |    6789479 |
| 2515 | Ciudad de México | MEX     |    8591309 |
|  206 | São Paulo        | BRA     |    9968485 |
|  130 | Sydney            | AUS     |    3276207 |
+------+-------------------+---------+------------+

Справочная информация

Материализация полусоединения

• Может использоваться для некоррелированных подзапросов IN. Подзапрос может использовать группировку и/или агрегатные функции.
• Показано в EXPLAIN как type=MATERIALIZED для подзапроса и строкой с table=<subqueryN> в основном подзапросе.
• Включается, когда в переменной optimizer_switch установлены значения materialization=on и semijoin=on.
• Флаг materialization=on|off используется совместно с нематериализацией полусоединения.