Контакты
IBSurgeon
Эта страница переведена машинным переводом. Читайте английский оригинал. English

Библиотека IBSurgeon

Улучшения оптимизатора в Firebird 5.0.1

(c) D.Simonov, IBSurgeon, 21-Aug-2024

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

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

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

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

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

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

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

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

sql 
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
  )
Code 
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 был выполнен один раз, его результат сохранен в памяти в виде хеш-таблицы, а затем внешний запрос просто искал значения в этой хеш-таблице.

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

Code 
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 раза хуже.
Читатель может спросить: почему хеш-полу-соединение показывает в 5 раз больше чтений по индексу таблицы COVER, но в остальном оно лучше? Дело в том, что чтения по индексу в статистике показывают количество записей, прочитанных с использованием индекса, они не показывают общее количество обращений к индексу, некоторые из которых вообще не приводят к извлечению записей, но эти обращения не бесплатны.

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

sql 
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. Рассмотрим еще один пример:

sql 
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. Посмотрим, как он выполняется без преобразования в полу-соединение.

Code 
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 и выполним запрос снова.

Code 
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, запрос будет выглядеть так:

sql 
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 преобразовать в semi-join? Нет, не любой. Например, если подзапрос содержит фильтры FETCH/FIRST/SKIP/ROWS, то такой подзапрос не может быть преобразован в semi-join и будет выполняться как коррелированный подзапрос. Вот пример такого запроса:

sql 
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 не меняет семантику запроса, и результат его выполнения будет таким же, как и без неё. Посмотрим на план и статистику этого запроса.

Code 
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|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

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

Code 
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|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

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

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

Code 
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.

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

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

sql 
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
  )
Code 
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.

sql 
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
  )
Code 
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 хотелось бы отметить, что если у вас есть запрос вида

Code 
SELECT ...
FROM T1
WHERE  IN (SELECT field FROM T2 ...)

или

Code 
SELECT ...
FROM T1
WHERE EXISTS (SELECT ... FROM T2 WHERE T1. = T2.field)

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

Code 
SELECT ...
FROM
  T1
  JOIN (SELECT DISTINCT field FROM T2) tmp ON tmp.field = T1.

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

sql 
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)

Code 
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 читается полностью.

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

Code 
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

sql 
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
Code 
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 и проверяйте альтернативные варианты написания запросов.