Новые возможности оптимизатора в Firebird 5.0.1

(С) Денис Симонов, IBSurgeon, 21-Aug-2024

Недавно вышел пойнт релиз СУБД Firebird 5.0 Firebird 5.0.1. В нём помимо исправления ошибок была добавлена новая экспериментальная функция оптимизатора о которой и будет рассказано в этой статье.

Преобразование подзапросов в ANY/SOME/IN/EXISTS в semi-join

Полусоединение (semi-join) — это операция соединения двух отношений, которая возвращает строки только одного из отношений, без выполнения соединения полностью. В отличие от других операторов соединений, не существует явного синтаксиса для указания исполнения полусоединения. Однако выполнить полусоединение можно с помощью подзапросов в ANY/SOME/IN/EXISTS.

Традиционно Firebird преобразует подзапросы в предикатах ANY/SOME/IN в коррелированные подзапросы в предикате EXISTS, и выполняет подзапрос в EXISTS для каждой записи внешнего запроса. При выполнении подзапроса внутри предиката EXISTS используется стратегия FIRST ROWS, и его выполнение немедленно прекращается после возврата первой записи.

Начиная с Firebird 5.0.1 подзапросы в предикатах ANY/SOME/IN/EXISTS могут быть преобразованы в полусоединения (semi-joins). По умолчанию эта возможность отключена, для её включения необходимо установить параметр конфигурации SubQueryConversion равным значению true в файле firebird.conf или database.conf

Данная функция является экспериментальной, поэтому по умолчанию она отключена. Вы можете включить её и протестировать свои запросы с подзапросами в предикатах ANY/SOME/IN/EXISTS, и если производительность окажется лучше, то оставить её включенной, в противном случае верните значение параметра SubQueryConversion в значение по умолчанию (false).

Значение по умолчанию для параметра конфигурации SubQueryConversion может быть изменено в будущем или же этот параметр может быть вовсе удалён. Это произойдёт как только будет доказано, что новый способ выполнения является более оптимальным в большинстве случаев.

В отличие от выполнения ANY/SOME/IN/EXISTS с подзапросами непосредственно, то есть как коррелированных подзапросов, выполнение их как semi-join даёт больше пространства для оптимизации. Полусоединение может быть выполнено различными алгоритмами Hash Join (semi) или Nested Loop Join (semi), в то время как коррелированные подзапросы всегда выполняются для каждой записи внешнего запроса.

Попробуем включить данную функцию, установив параметру SubQueryConversion значение true в файле firebird.conf. Теперь проведём несколько экспериментов.

Выполним следующий запрос:

SELECT
  COUNT(*)
FROM
  HORSE H
WHERE H.CODE_DEPARTURE = 1
  AND H.CODE_SEX = 2
  AND H.CODE_HORSE IN (
    SELECT COVER.CODE_FATHER
    FROM COVER
    WHERE COVER.CODE_DEPARTURE = 1
      AND EXTRACT(YEAR FROM COVER.BYDATE) = 2023
  )

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (semi)
                -> Filter
                    -> Table "HORSE" as "H" Access By ID
                        -> Bitmap And
                            -> Bitmap
                                -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)
                            -> Bitmap
                                -> Index "FK_HORSE_SEX" Range Scan (full match)
                -> Record Buffer (record length: 41)
                    -> Filter
                        -> Table "COVER" Access By ID
                            -> Bitmap And
                                -> Bitmap
                                    -> Index "IDX_COVER_BYYEAR" Range Scan (full match)
                                -> Bitmap
                                    -> Index "FK_COVER_DEPARTURE" Range Scan (full match)

                COUNT
=====================
                  297

Current memory = 552356752
Delta memory = 352
Max memory = 552567920
Elapsed time = 0.045 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 43984
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |     1516|         |         |         |
HORSE                           |         |    37069|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

В плане выполнения мы видим новый метод соединения Hash Join (semi). Результат подзапроса в IN был буферизирован, что видно в плане как Record Buffer (record length: 41). То есть в данном случае подзапрос в IN, был выполнен однократно, его результат сохранён в память хеш таблицы, а затем внешний запрос просто производил поиск в этой хеш таблице.

Для сравнения выполним тот же запрос с отключенным преобразованием подзапросов в полусоединение.

Sub-query
    -> Filter
        -> Filter
            -> Table "COVER" Access By ID
                -> Bitmap And
                    -> Bitmap
                        -> Index "FK_COVER_FATHER" Range Scan (full match)
                    -> Bitmap
                        -> Index "IDX_COVER_BYYEAR" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap And
                    -> Bitmap
                        -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)
                    -> Bitmap
                        -> Index "FK_HORSE_SEX" Range Scan (full match)

                COUNT
=====================
                  297

Current memory = 552046496
Delta memory = 352
Max memory = 552135600
Elapsed time = 0.395 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 186891
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |      297|         |         |         |
HORSE                           |         |    37069|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

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

Читатель может задать вопрос: а почему же hash semi-join показывает в 5 раз больше индексных чтений таблицы COVER, но в остальном он лучше. Дело в том, что индексированные чтения в статистике отображают количество записей прочитанных с помощью индекса, они не отображают общее количество обращений к индексам, часть из которых вообще не приводят к извлечению записей, но при этом эти обращения не являются бесплатными.

Что же произошло? Для лучшего понимания трансформации подзапросов введём воображаемый оператор полусоединия "SEMI JOIN". Как я уже говорил данный вид соединения не представлен в языке SQL. Наш запрос с оператором IN был преобразован в эквивалентную форму, которую можно записать так:

SELECT
  COUNT(*)
FROM
  HORSE H
  SEMI JOIN (
    SELECT COVER.CODE_FATHER
    FROM COVER
    WHERE COVER.CODE_DEPARTURE = 1
      AND EXTRACT(YEAR FROM COVER.BYDATE) = 2023
  ) TMP ON TMP.CODE_FATHER = H.CODE_HORSE
WHERE H.CODE_DEPARTURE = 1
  AND H.CODE_SEX = 2

Теперь стало яснее. Тоже самое происходит и для подзапросов с использованием EXISTS. Давайте посмотрим ещё один пример:

SELECT
  COUNT(*)
FROM
  HORSE H
WHERE H.CODE_DEPARTURE = 1
  AND EXISTS (
    SELECT *
    FROM COVER
    WHERE COVER.CODE_DEPARTURE = 1
      AND COVER.CODE_FATHER = H.CODE_FATHER
      AND COVER.CODE_MOTHER = H.CODE_MOTHER
  )

В настоящее время такой EXISTS невозможно написать с использованием IN. Посмотрим как он выполняется без трансформации в полусоединение.

Sub-query
    -> Filter
        -> Table "COVER" Access By ID
            -> Bitmap And
                -> Bitmap
                    -> Index "FK_COVER_MOTHER" Range Scan (full match)
                -> Bitmap
                    -> Index "FK_COVER_FATHER" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)

                COUNT
=====================
                91908

Current memory = 552240400
Delta memory = 352
Max memory = 554680016
Elapsed time = 19.083 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 935679
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |    91908|         |         |         |
HORSE                           |         |    96021|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Очень медленно. А теперь установим SubQueryConversion = true и выполним запрос ещё раз.

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (semi)
                -> Filter
                    -> Table "HORSE" as "H" Access By ID
                        -> Bitmap
                            -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)
                -> Record Buffer (record length: 49)
                    -> Filter
                        -> Table "COVER" Access By ID
                            -> Bitmap
                                -> Index "FK_COVER_DEPARTURE" Range Scan (full match)

                COUNT
=====================
                91908

Current memory = 552102000
Delta memory = 352
Max memory = 561520736
Elapsed time = 0.208 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 248009
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |   140254|         |         |         |
HORSE                           |         |    96021|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Запрос выполнился в 100 раз быстрее! Если его переписать с помощью нашего выдуманного оператора SEMI JOIN, то запрос будет выглядеть следующим образом:

SELECT
  COUNT(*)
FROM
  HORSE H
  SEMI JOIN (
    SELECT
      COVER.CODE_FATHER,
      COVER.CODE_MOTHER
    FROM COVER
  ) TMP ON TMP.CODE_FATHER = H.CODE_FATHER AND TMP.CODE_MOTHER = H.CODE_MOTHER
WHERE H.CODE_DEPARTURE = 1

Любой коррелированный подзапрос в IN/EXISTS можно преобразовать в полусоединение? Нет, не любой, например, если подзапрос содержит ограничители FETCH/FIRST/SKIP/ROWS, то преобразовать подзапрос в полусоединение нельзя и он будет выполняться как обычный коррелированный подзапрос. Приведу пример такого запроса:

SELECT
  COUNT(*)
FROM
  HORSE H
WHERE H.CODE_DEPARTURE = 1
  AND EXISTS (
    SELECT *
    FROM COVER
    WHERE COVER.CODE_FATHER = H.CODE_HORSE
    OFFSET 0 ROWS
  )

Здесь фраза OFFSET 0 ROWS не меняет семантику запроса, и результат его выполнения будет тем же, что и без неё. Посмотрим план и статистику данного запроса.

Sub-query
    -> Skip N Records
        -> Filter
            -> Table "COVER" Access By ID
                -> Bitmap
                    -> Index "FK_COVER_FATHER" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)

                COUNT
=====================
                10971

Current memory = 551912944
Delta memory = 288
Max memory = 552002112
Elapsed time = 0.201 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 408988
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |    10971|         |         |         |
HORSE                           |         |    96021|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Как видите преобразование в полусоединение не произошло. Теперь уберём OFFSET 0 ROWS и снимем статистику ещё раз.

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (semi)
                -> Filter
                    -> Table "HORSE" as "H" Access By ID
                        -> Bitmap
                            -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)
                -> Record Buffer (record length: 33)
                    -> Table "COVER" Full Scan

                COUNT
=====================
                10971

Current memory = 552112128
Delta memory = 288
Max memory = 585044592
Elapsed time = 0.405 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 854841
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |   722465|         |         |         |         |
HORSE                           |         |    96021|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Здесь преобразование в полусоединение произошло, и как мы видим время выполнения стало хуже. Причина в том, что в настоящее время в оптимизаторе нет стоимостной оценки между алгоритмами соединения Hash Join (semi) и Nested Loop Join (semi) с использованием индекса, поэтому используется правило: если в условии соединения присутствует только равенство, то выбирается алгоритм Hash Join (semi), в противном случае подзапросы IN/EXISTS выполняются как обычно.

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

Sub-query
    -> Filter
        -> Table "COVER" Access By ID
            -> Bitmap
                -> Index "FK_COVER_FATHER" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)

                COUNT
=====================
                10971

Current memory = 551912752
Delta memory = 288
Max memory = 552001920
Elapsed time = 0.193 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 408988
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |    10971|         |         |         |
HORSE                           |         |    96021|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Как видите Fetches в точности равно случаю когда в подзапросе присутствовала фраза OFFSET 0 ROWS, а время выполнения отличается в пределах погрешности. Это означает, что вы можете использовать предложение OFFSET 0 ROWS как подсказку для отключения преобразование в semi-join.

Теперь посмотрим на случаи, когда в подзапросах используется любое коррелированное условие кроме равенства и IS NOT DISTINCT FROM.

SELECT
  COUNT(*)
FROM
  HORSE H
WHERE H.CODE_DEPARTURE = 1
  AND EXISTS (
    SELECT *
    FROM COVER
    WHERE COVER.BYDATE > H.BIRTHDAY
  )

Sub-query
    -> Filter
        -> Table "COVER" Access By ID
            -> Bitmap
                -> Index "COVER_IDX_BYDATE" Range Scan (lower bound: 1/1)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)

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

Продолжим эксперименты, напишем запрос с использованием равенства и ещё одного любого предиката кроме равенства.

SELECT
  COUNT(*)
FROM
  HORSE H
WHERE H.CODE_DEPARTURE = 1
  AND EXISTS (
    SELECT *
    FROM COVER
    WHERE COVER.CODE_FATHER = H.CODE_FATHER
      AND COVER.BYDATE > H.BIRTHDAY
  )

Select Expression
    -> Aggregate
        -> Nested Loop Join (semi)
            -> Filter
                -> Table "HORSE" as "H" Access By ID
                    -> Bitmap
                        -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)
            -> Filter
                -> Filter
                    -> Table "COVER" Access By ID
                        -> Bitmap
                            -> Index "COVER_IDX_BYDATE" Range Scan (lower bound: 1/1)

Здесь в плане мы впервые видим использование метода соединения Nested Loop Join (semi), но к сожалению этот план плохой, так как не используется индекс FK_COVER_FATHER. Результатов такого запроса вы не дождётесь. Исправить это можно с помощью подсказки OFFSET 0 ROWS.

SELECT
  COUNT(*)
FROM
  HORSE H
WHERE H.CODE_DEPARTURE = 1
  AND EXISTS (
    SELECT *
    FROM COVER
    WHERE COVER.CODE_FATHER = H.CODE_FATHER
      AND COVER.BYDATE > H.BIRTHDAY
    OFFSET 0 ROWS
  )

Sub-query
    -> Skip N Records
        -> Filter
            -> Table "COVER" Access By ID
                -> Bitmap
                    -> Index "FK_COVER_FATHER" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)

                COUNT
=====================
                72199

Current memory = 554017824
Delta memory = 320
Max memory = 554284480
Elapsed time = 45.548 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 84145713
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         | 75894621|         |         |         |
HORSE                           |         |    96021|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Не самое лучшее время выполнения, но в данном случае мы хотя бы дождались результата.

Таким образом, преобразование подзапросов в ANY/SOME/IN/EXISTS в semi-join позволяет в ряде случаев значительно ускорить выполнение запросов, но в настоящее время эта функция ещё несовершенна, а потому отключена по умолчанию. В Firebird 6.0 для этой функциональности постараются добавить стоимостную оценку, а также исправить ряд других недостатков. Кроме того в Firebird 6.0 планируется добавить преобразование подзапросов ALL/NOT IN/NOT EXISTS в anti-join.

В заключении обзора выполнения подзапросов в IN/EXISTS, хотел бы отметить, что если у вас есть запрос вида

SELECT ...
FROM T1
WHERE <primary key> IN (SELECT field FROM T2 ...)

или

SELECT ...
FROM T1
WHERE EXISTS (SELECT ... FROM T2 WHERE T1.<primary key> = T2.field)

то такие запросы почти всегда эффективней выполнять как

SELECT ...
FROM
  T1
  JOIN (SELECT DISTINCT field FROM T2) tmp ON tmp.field = T1.<primary key>

Приведу наглядный пример:

SELECT
  COUNT(*)
FROM
  HORSE H
WHERE H.CODE_HORSE IN (
  SELECT
    CODE_FATHER
  FROM COVER
  WHERE EXTRACT(YEAR FROM COVER.BYDATE) = 2022
)

План и статистика выполнения с использованием Hash Join (semi)

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (semi)
                -> Table "HORSE" as "H" Full Scan
                -> Record Buffer (record length: 41)
                    -> Filter
                        -> Table "COVER" Access By ID
                            -> Bitmap
                                -> Index "IDX_COVER_BYYEAR" Range Scan (full match)

                COUNT
=====================
                 1616

Current memory = 554176768
Delta memory = 288
Max memory = 555531328
Elapsed time = 0.229 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 569683
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |     6695|         |         |         |
HORSE                           |   525875|         |         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Довольно быстро, но таблица HORSE читается целиком.

План и статистика выполнения с классическим выполнением подзапросов

Sub-query
    -> Filter
        -> Filter
            -> Table "COVER" Access By ID
                -> Bitmap And
                    -> Bitmap
                        -> Index "FK_COVER_FATHER" Range Scan (full match)
                    -> Bitmap
                        -> Index "IDX_COVER_BYYEAR" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Full Scan

                COUNT
=====================
                 1616

Current memory = 553472512
Delta memory = 288
Max memory = 553966592
Elapsed time = 6.862 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 2462726
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |     1616|         |         |         |
HORSE                           |   525875|         |         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Очень медленно. Таблица HORSE всё так же читается целиком, а подзапрос выполняется многократно — для каждой записи таблицы HORSE.

А теперь быстрый вариант с DISTINCT

SELECT
  COUNT(*)
FROM
  HORSE H
  JOIN (
      SELECT
        DISTINCT
        CODE_FATHER
      FROM COVER
      WHERE EXTRACT(YEAR FROM COVER.BYDATE) = 2022
  ) TMP ON TMP.CODE_FATHER = H.CODE_HORSE

Select Expression
    -> Aggregate
        -> Nested Loop Join (inner)
            -> Unique Sort (record length: 44, key length: 12)
                -> Filter
                    -> Table "COVER" as "TMP COVER" Access By ID
                        -> Bitmap
                            -> Index "IDX_COVER_BYYEAR" Range Scan (full match)
            -> Filter
                -> Table "HORSE" as "H" Access By ID
                    -> Bitmap
                        -> Index "PK_HORSE" Unique Scan

                COUNT
=====================
                 1616

Current memory = 554349728
Delta memory = 320
Max memory = 555531328
Elapsed time = 0.011 sec
Buffers = 32768
Reads = 0
Writes = 0
Fetches = 14954
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
COVER                           |         |     6695|         |         |         |
HORSE                           |         |     1616|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Никаких лишних чтений, запрос выполняется очень быстро. Отсюда вывод — всегда смотрите план выполнения подзапросов в IN/EXISTS/ANY/SOME, и проверяйте альтернативные варианты написания запросов.