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, і якщо продуктивність буде кращою, залиште її увімкненою, інакше поверніть параметр `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, але в іншому воно краще? Справа в тому, що читання індексу в статистиці показують кількість записів, прочитаних за допомогою індексу, вони не показують загальну кількість звернень до індексу, деякі з яких взагалі не призводять до отримання записів, але ці звернення не є безкоштовними.

Читач може запитати: чому хеш-напівз’єднання показує в 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 (повний збіг)
                -> Bitmap
                    -> Index "FK_COVER_FATHER" Range Scan (повний збіг)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (повний збіг)

                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 (повний збіг)
                -> Record Buffer (record length: 49)
                    -> Filter
                        -> Table "COVER" Access By ID
                            -> Bitmap
                                -> Index "FK_COVER_DEPARTURE" Range Scan (повний збіг)

                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 бути перетворений на напівз’єднання? Ні, не будь-який. Наприклад, якщо підзапит містить фільтри FETCH/FIRST/SKIP/ROWS, то такий підзапит не може бути перетворений на напівз’єднання, і він буде виконаний як корельований підзапит. Ось приклад такого запиту:

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 (повний збіг)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (повний збіг)

                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 і знову зберемо статистику.

Code

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (semi)
                -> Filter
                    -> Table "HORSE" as "H" Access By ID
                        -> Bitmap
                            -> Index "FK_HORSE_DEPARTURE" Range Scan (повний збіг)
                -> 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 виконуються як зазвичай.

Тепер вимкнемо перетворення на напівз’єднання і подивимося на статистику виконання.

Code

Sub-query
    -> Filter
        -> Table "COVER" Access By ID
            -> Bitmap
                -> Index "FK_COVER_FATHER" Range Scan (повний збіг)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (повний збіг)

                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 як підказку для вимкнення перетворення на напівз’єднання.

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

sql

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

Code

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)

Як я вже зазначив вище, перетворення на напівз’єднання не відбулося, підзапит виконується для кожного запису основного запиту.

Продовжимо експерименти, напишемо запит із використанням рівності та ще одного предиката, окрім рівності.

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 у напівз’єднання дозволяє в деяких випадках значно прискорити виконання запитів, але наразі ця функція все ще недосконала, тому вимкнена за замовчуванням. У Firebird 6.0 спробують додати оцінку вартості для цієї функції, а також виправити низку інших недоліків. Крім того, у Firebird 6.0 планується додати перетворення підзапитів ALL/NOT IN/NOT EXISTS в антиз’єднання.

На завершення огляду виконання підзапитів в 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| | | | ——————————–+———+———+———+———+———+

Code


Жодних зайвих читань, запит виконується дуже швидко. Звідси висновок - завжди дивіться на план виконання підзапитів у IN/EXISTS/ANY/SOME та перевіряйте альтернативні варіанти написання запитів.