Firebird 5.0.1 Vylepšení v optimalizátoru

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

Nedávno bylo vydáno bodové vydání systému správy databází Firebird 5.0 Firebird 5.0.1. Kromě oprav chyb byla přidána nová experimentální optimalizační funkce, o které bude pojednáno v tomto článku.

Převod poddotazů na ANY/SOME/IN/EXISTS v semi-join

Semi-join je operace, která spojuje dvě relace a vrací řádky pouze z jedné z relací bez provedení celého spojení. Na rozdíl od jiných operátorů spojení neexistuje explicitní syntaxe pro určení, zda provést semi-join. Semi-join však můžete provést pomocí poddotazů v ANY/SOME/IN/EXISTS.

Tradičně Firebird transformuje poddotazy v predikátech ANY/SOME/IN na korelované poddotazy v predikátu EXISTS a provádí poddotaz v EXISTS pro každý záznam vnějšího dotazu. Při provádění poddotazu uvnitř predikátu EXISTS se používá strategie FIRST ROWS a jeho provádění se zastaví okamžitě po vrácení prvního záznamu.

Počínaje Firebird 5.0.1 lze poddotazy v predikátech ANY/SOME/IN/EXISTS převést na semi-join. Tato funkce je ve výchozím nastavení zakázána a lze ji povolit nastavením konfiguračního parametru SubQueryConversion na true v souboru firebird.conf nebo database.conf.

Tato funkce je experimentální, takže je ve výchozím nastavení zakázána. Můžete ji povolit a otestovat své dotazy s poddotazy v predikátech ANY/SOME/IN/EXISTS, a pokud je výkon lepší, nechte ji povolenou, jinak nastavte parametr SubQueryConversion zpět na výchozí hodnotu ( false).
Výchozí hodnota konfiguračního parametru SubQueryConversion se může v budoucnu změnit, nebo může být parametr zcela odstraněn. K tomu dojde, jakmile se prokáže, že nový způsob je ve většině případů optimálnější.


	Tato funkce je experimentální, takže je ve výchozím nastavení zakázána. Můžete ji povolit a otestovat své dotazy s poddotazy v predikátech ANY/SOME/IN/EXISTS, a pokud je výkon lepší, nechte ji povolenou, jinak nastavte parametr `SubQueryConversion` zpět na výchozí hodnotu ( `false`). Výchozí hodnota konfiguračního parametru `SubQueryConversion` se může v budoucnu změnit, nebo může být parametr zcela odstraněn. K tomu dojde, jakmile se prokáže, že nový způsob je ve většině případů optimálnější.

Na rozdíl od provádění ANY/SOME/IN/EXISTS přímo na poddotazech, tj. jako korelovaných poddotazech, provádění jako semi-join dává více prostoru pro optimalizaci. Semi-join lze provádět různými algoritmy Hash Join (semi) nebo Nested Loop Join (semi), zatímco korelované poddotazy se vždy provádějí pro každý záznam vnějšího dotazu.

Zkusme povolit tuto funkci nastavením parametru SubQueryConversion na true v souboru firebird.conf. Nyní provedeme několik experimentů.

Proveďme následující dotaz:

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

V plánu provádění vidíme novou metodu spojení Hash Join (semi). Výsledek poddotazu v IN byl uložen do vyrovnávací paměti, což je v plánu viditelné jako Record Buffer (record length: 41). To znamená, že v tomto případě byl poddotaz v IN proveden jednou, jeho výsledek byl uložen do paměti hash tabulky, a poté vnější dotaz jednoduše vyhledával v této hash tabulce.

Pro srovnání spusťme stejný dotaz s vypnutým převodem poddotazu na semi-join.

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

Plán provádění ukazuje, že poddotaz se provádí pro každý záznam hlavního dotazu, ale používá další index FK_COVER_FATHER. To je také viditelné ve statistikách provádění: počet Fetches je 4krát větší, doba provádění je téměř 4krát horší.


	Čtenář se může zeptat: proč hash semi-join ukazuje 5krát více čtení indexu tabulky COVER, ale jinak je lepší? Faktem je, že čtení indexu ve statistikách ukazuje počet záznamů přečtených pomocí indexu, neukazuje celkový počet přístupů k indexu, z nichž některé vůbec nevedou k načtení záznamů, ale tyto přístupy nejsou zdarma.

Co se stalo? Abychom lépe porozuměli transformaci poddotazů, zavedeme imaginární operátor semi-join “SEMI JOIN”. Jak jsem již řekl, tento typ spojení není v jazyce SQL reprezentován. Náš dotaz s operátorem IN byl transformován do ekvivalentní formy, kterou lze zapsat následovně:

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

Nyní je to jasnější. Totéž se děje pro poddotazy používající EXISTS. Podívejme se na další příklad:

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
  )

V současné době není možné takový EXISTS zapsat pomocí IN. Podívejme se, jak je implementován bez transformace na semi-join.

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

Velmi pomalé. Nyní nastavíme SubQueryConversion = true a spustíme dotaz znovu.

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

Dotaz byl proveden 100krát rychleji! Pokud jej přepíšeme pomocí našeho fiktivního operátoru SEMI JOIN, bude dotaz vypadat takto:

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

Lze jakýkoli korelovaný poddotaz v IN/EXISTS převést na semi-join? Ne, ne každý, například pokud poddotaz obsahuje filtry FETCH/FIRST/SKIP/ROWS, pak poddotaz nelze převést na semi-join a bude proveden jako korelovaný poddotaz. Zde je příklad takového dotazu:

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
  )

Zde fráze OFFSET 0 ROWS nemění sémantiku dotazu a výsledek jeho provedení bude stejný jako bez ní. Podívejme se na plán a statistiky tohoto dotazu.

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

Jak vidíte, k transformaci na semi-join nedošlo. Nyní odebereme OFFSET 0 ROWS a znovu získáme statistiky.

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

Zde došlo k převodu na semi-join, a jak vidíme, doba provádění se zhoršila. Důvodem je, že optimalizátor v současnosti nemá odhad nákladů mezi algoritmy spojení Hash Join (semi) a Nested Loop Join (semi) používajícími index, takže platí pravidlo: pokud podmínka spojení obsahuje pouze rovnost, je zvolen algoritmus Hash Join (semi), jinak se poddotazy IN/EXISTS provádějí obvyklým způsobem.

Nyní zakážeme konverzi na semi-join a podíváme se na statistiky provádění.

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

Jak vidíte, Fetches je přesně stejné jako v případě, kdy poddotaz obsahoval klauzuli OFFSET 0 ROWS, a doba provádění se liší v rámci chyby měření. To znamená, že můžete použít klauzuli OFFSET 0 ROWS jako nápovědu k zakázání konverze na semi-join.

Nyní se podíváme na případy, kdy se v poddotazech používá jiná korelovaná podmínka než rovnost a 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)

Jak jsem řekl výše, k transformaci na semi-join nedošlo, poddotaz se provádí pro každý záznam hlavního dotazu.

Pokračujme v experimentech, napišme dotaz používající rovnost a ještě jeden predikát kromě rovnosti.

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)

Zde v plánu vidíme první použití metody spojení Nested Loop Join (semi), ale bohužel je tento plán špatný, protože index FK_COVER_FATHER se nepoužívá. Z takového dotazu nezískáte žádné výsledky. To lze opravit pomocí nápovědy 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|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Není to nejlepší doba provádění, ale v tomto případě jsme alespoň získali výsledek.

Převod poddotazů ANY/SOME/IN/EXISTS na semi-join tedy v některých případech umožňuje výrazně urychlit provádění dotazů, ale v současnosti je tato funkce stále nedokonalá, a proto je ve výchozím stavu zakázána. Ve Firebird 6.0 se pokusí přidat odhad nákladů pro tuto funkci a také opravit řadu dalších nedostatků. Kromě toho se ve Firebird 6.0 plánuje přidání převodu poddotazů ALL/NOT IN/NOT EXISTS na anti-join.

Na závěr přehledu provádění poddotazů v IN/EXISTS bych rád poznamenal, že pokud máte dotaz ve tvaru

Code

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

nebo

Code

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

pak je téměř vždy efektivnější provést takové dotazy jako

Code

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

Uvedu jasný příklad:

sql

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

Plán provádění a statistiky pomocí 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|         |         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

Docela rychlé, ale tabulka HORSE se čte celá.

Plán provádění a statistiky s klasickým prováděním poddotazu

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

Velmi pomalé. Tabulka HORSE se čte celá a poddotaz se provádí vícekrát - pro každý záznam v tabulce HORSE.

A nyní rychlá varianta s 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


Žádná zbytečná čtení, dotaz se provede velmi rychle. Z toho plyne závěr - vždy se podívejte na plán provádění poddotazů v IN/EXISTS/ANY/SOME a zkontrolujte alternativní varianty zápisu dotazů.