Стратегия FirstMatch

FirstMatch — это стратегия выполнения для подзапросов с полусоединением.

Идея

Она очень похожа на то, как подзапросы IN/EXISTS выполнялись в MySQL 5.x.

Давайте рассмотрим обычный пример поиска стран с большими городами:

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

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

Так как Германия имеет два больших города (на этой диаграмме), она будет включена в вывод запроса дважды. Это неверно, SELECT ... FROM Country не должно выдавать одну и ту же запись страны дважды. Стратегия FirstMatch избегает создания дубликатов, прерывая выполнение как только найден первый настоящий результат:

Обратите внимание, что прерывание должно произойти после применения «Используя where». Было бы неправильно прерывать после того, как мы нашли Трир.

Стратегия FirstMatch в действии

План выполнения для вышеприведённого запроса будет выглядеть следующим образом:

MariaDB [world]> explain select * from Country where Country.code IN 
  (select City.Country from City where City.Population > 1*1000*1000)
    and Country.continent='Europe';
+----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+
| id | select_type | table   | type | possible_keys      | key       | key_len | ref                | rows | Extra                            |
+----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+
|  1 | PRIMARY     | Country | ref  | PRIMARY,continent  | continent | 17      | const              |   60 | Using index condition            |
|  1 | PRIMARY     | City    | ref  | Population,Country | Country   | 3       | world.Country.Code |   18 | Using where; FirstMatch(Country) |
+----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+
2 rows in set (0.00 sec)

FirstMatch(Country) в столбце Extra означает, что как только мы сгенерировали одну сочетающуюся запись, прерываем выполнение и возвращаемся к таблице Country.

План выполнения запроса FirstMatch очень похож на тот, который вы бы получили в MySQL:

MySQL [world]> explain select * from Country  where Country.code IN 
  (select City.Country from City where City.Population > 1*1000*1000) 
   and Country.continent='Europe';
+----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+
| id | select_type        | table   | type           | possible_keys      | key       | key_len | ref   | rows | Extra                              |
+----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+
|  1 | PRIMARY            | Country | ref            | continent          | continent | 17      | const |   60 | Using index condition; Using where |
|  2 | DEPENDENT SUBQUERY | City    | index_subquery | Population,Country | Country   | 3       | func  |   18 | Using where                        |
+----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+
2 rows in set (0.01 sec)

и эти два конкретных плана выполнения будут выполняться за одинаковое время.

Разница между FirstMatch и IN->EXISTS

Общая идея, лежащая в основе стратегии FirstMatch, такая же, как и в основе преобразования IN->EXISTS, однако, FirstMatch имеет несколько преимуществ:

• Распространение равенств работает через границы полусоединения, но не через границы подзапросов. Поэтому преобразование подзапроса в полусоединение и использование FirstMatch может всё ещё дать лучший план выполнения. (TODO пример)

• Существует только один способ применения стратегии IN->EXISTS и MySQL сделает это безусловно. Со FirstMatch, оптимизатор может выбирать, следует ли ему запустить стратегию FirstMatch сразу же, как только все таблицы, используемые в подзапросе, окажутся в префиксе соединения, или в какой-то момент позже. (TODO: пример)

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

• Стратегия FirstMatch работает путём выполнения подзапроса и прерывания его выполнения как только найден первый результат.
• Это означает, что таблицы подзапроса должны находиться после всех таблиц родительского SELECT, которые ссылаются на предикат подзапроса.
• EXPLAIN показывает FirstMatch как «FirstMatch(tableN)».
• Стратегия может обрабатывать коррелированные подзапросы.
• Но она не может быть применена, если подзапрос имеет значимые GROUP BY и/или агрегатные функции.
• Использование стратегии FirstMatch контролируется флагом firstmatch=on|off в переменной optimizer_switch.

См. также

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

Подробный материал:

• WL#3750: начальное описание FirstMatch