Ulepszenia optymalizatora w Firebird 5.0.1
(c) D.Simonov, IBSurgeon, 21-Aug-2024
Niedawno wydano punktowe wydanie systemu DBMS Firebird 5.0 - Firebird 5.0.1. Oprócz poprawek błędów dodano nową eksperymentalną funkcję optymalizatora, która zostanie omówiona w tym artykule.
Konwersja podzapytań na ANY/SOME/IN/EXISTS w semi-join
Semi-join to operacja łącząca dwie relacje, zwracająca wiersze tylko z jednej z nich bez wykonywania pełnego złączenia. W przeciwieństwie do innych operatorów złączeń, nie ma jawnej składni określającej wykonanie semi-join. Można jednak wykonać semi-join za pomocą podzapytań w ANY/SOME/IN/EXISTS.
Tradycyjnie Firebird przekształca podzapytania w predykatach ANY/SOME/IN na skorelowane podzapytania w predykacie EXISTS i wykonuje podzapytanie w EXISTS dla każdego rekordu zapytania zewnętrznego. Podczas wykonywania podzapytania wewnątrz predykatu EXISTS stosowana jest strategia FIRST ROWS, a jego wykonanie zatrzymuje się natychmiast po zwróceniu pierwszego rekordu.
Począwszy od Firebird 5.0.1, podzapytania w predykatach ANY/SOME/IN/EXISTS mogą być konwertowane na semi-join. Ta funkcja jest domyślnie wyłączona i można ją włączyć, ustawiając parametr konfiguracyjny SubQueryConversion na true w pliku firebird.conf lub database.conf.
Ta funkcja jest eksperymentalna, dlatego jest domyślnie wyłączona. Możesz ją włączyć i przetestować swoje zapytania z podzapytaniami w predykatach ANY/SOME/IN/EXISTS, a jeśli wydajność będzie lepsza, pozostaw ją włączoną; w przeciwnym razie ustaw parametr SubQueryConversion z powrotem na wartość domyślną (false).Wartość domyślna parametru konfiguracyjnego SubQueryConversion może zostać zmieniona w przyszłości lub parametr może zostać całkowicie usunięty. Stanie się tak, gdy nowy sposób działania okaże się bardziej optymalny w większości przypadków. |
W przeciwieństwie do wykonywania ANY/SOME/IN/EXISTS bezpośrednio na podzapytaniach, tj. jako skorelowanych podzapytań, wykonywanie ich jako semi-join daje więcej możliwości optymalizacji. Semi-join może być wykonywany przez różne algorytmy Hash Join (semi) lub Nested Loop Join (semi), podczas gdy skorelowane podzapytania są zawsze wykonywane dla każdego rekordu zapytania zewnętrznego.
Spróbujmy włączyć tę funkcję, ustawiając parametr SubQueryConversion na true w pliku firebird.conf. Teraz przeprowadźmy kilka eksperymentów.
Wykonajmy następujące zapytanie:
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| | | |
--------------------------------+---------+---------+---------+---------+---------+
W planie wykonania widzimy nową metodę złączenia Hash Join (semi). Wynik podzapytania w IN został buforowany, co widać w planie jako Record Buffer (record length: 41). Oznacza to, że w tym przypadku podzapytanie w IN zostało wykonane raz, jego wynik został zapisany w pamięci tabeli mieszającej, a następnie zapytanie zewnętrzne po prostu przeszukiwało tę tabelę mieszającą.
Dla porównania uruchommy to samo zapytanie z wyłączoną konwersją podzapytania na semi-join.
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| | | |
--------------------------------+---------+---------+---------+---------+---------+
Plan wykonania pokazuje, że podzapytanie jest wykonywane dla każdego rekordu zapytania głównego, ale używa dodatkowego indeksu FK_COVER_FATHER. Widać to również w statystykach wykonania: liczba Fetches jest 4 razy większa, a czas wykonania prawie 4 razy gorszy.
| Czytelnik może zapytać: dlaczego hash semi-join pokazuje 5 razy więcej odczytów indeksu tabeli COVER, a poza tym jest lepszy? Faktem jest, że odczyty indeksu w statystykach pokazują liczbę rekordów odczytanych przy użyciu indeksu; nie pokazują one całkowitej liczby dostępów do indeksu, z których niektóre w ogóle nie kończą się pobraniem rekordów, ale te dostępy nie są darmowe. |
Co się stało? Aby lepiej zrozumieć transformację podzapytań, wprowadźmy wyimaginowany operator semi-join “SEMI JOIN”. Jak już powiedziałem, ten typ złączenia nie jest reprezentowany w języku SQL. Nasze zapytanie z operatorem IN zostało przekształcone do równoważnej postaci, którą można zapisać następująco:
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
Teraz jest jaśniej. To samo dzieje się w przypadku podzapytań używających EXISTS. Spójrzmy na kolejny przykład:
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
)
Obecnie nie można zapisać takiego EXISTS za pomocą IN. Zobaczmy, jak jest to zaimplementowane bez przekształcania go w semi-join.
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| | | |
--------------------------------+---------+---------+---------+---------+---------+
Bardzo wolno. Teraz ustawmy SubQueryConversion = true i uruchommy zapytanie ponownie.
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| | | |
--------------------------------+---------+---------+---------+---------+---------+
Zapytanie zostało wykonane 100 razy szybciej! Jeśli przepiszemy je za pomocą naszego fikcyjnego operatora SEMI JOIN, zapytanie będzie wyglądać następująco:
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
Czy każde skorelowane podzapytanie w IN/EXISTS można przekształcić w semi-join? Nie, nie każde; na przykład, jeśli podzapytanie zawiera filtry FETCH/FIRST/SKIP/ROWS, to podzapytanie nie może zostać przekształcone w semi-join i będzie wykonywane jako skorelowane podzapytanie. Oto przykład takiego zapytania:
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
)
Tutaj fraza OFFSET 0 ROWS nie zmienia semantyki zapytania, a wynik jego wykonania będzie taki sam jak bez niej. Spójrzmy na plan i statystyki tego zapytania.
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
Aktualna pamięć = 551912944
Delta pamięci = 288
Maksymalna pamięć = 552002112
Czas wykonania = 0.201 s
Bufory = 32768
Odczyty = 0
Zapisy = 0
Pobrania = 408988
Statystyki per tabela:
--------------------------------+---------+---------+---------+---------+---------+
Nazwa tabeli | Naturalny| Indeks | Wstaw | Aktual. | Usuń |
--------------------------------+---------+---------+---------+---------+---------+
COVER | | 10971| | | |
HORSE | | 96021| | | |
--------------------------------+---------+---------+---------+---------+---------+
Jak widać, transformacja do semi-joina nie nastąpiła. Teraz usuńmy OFFSET 0 ROWS i ponownie pobierzmy statystyki.
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
Aktualna pamięć = 552112128
Delta pamięci = 288
Maksymalna pamięć = 585044592
Czas wykonania = 0.405 s
Bufory = 32768
Odczyty = 0
Zapisy = 0
Pobrania = 854841
Statystyki per tabela:
--------------------------------+---------+---------+---------+---------+---------+
Nazwa tabeli | Naturalny| Indeks | Wstaw | Aktual. | Usuń |
--------------------------------+---------+---------+---------+---------+---------+
COVER | 722465| | | | |
HORSE | | 96021| | | |
--------------------------------+---------+---------+---------+---------+---------+
Tutaj konwersja do semi-joina nastąpiła i jak widzimy, czas wykonania się pogorszył. Powodem jest to, że obecnie optymalizator nie ma oszacowania kosztów między algorytmami łączenia Hash Join (semi) a Nested Loop Join (semi) z użyciem indeksu, więc zasada jest następująca: jeśli warunek łączenia zawiera tylko równość, wybierany jest algorytm Hash Join (semi), w przeciwnym razie podzapytania IN/EXISTS są wykonywane jak zwykle.
Teraz wyłączmy konwersję semi-joina i spójrzmy na statystyki wykonania.
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
Aktualna pamięć = 551912752
Delta pamięci = 288
Maksymalna pamięć = 552001920
Czas wykonania = 0.193 s
Bufory = 32768
Odczyty = 0
Zapisy = 0
Pobrania = 408988
Statystyki per tabela:
--------------------------------+---------+---------+---------+---------+---------+
Nazwa tabeli | Naturalny| Indeks | Wstaw | Aktual. | Usuń |
--------------------------------+---------+---------+---------+---------+---------+
COVER | | 10971| | | |
HORSE | | 96021| | | |
--------------------------------+---------+---------+---------+---------+---------+
Jak widać, Pobrania są dokładnie równe przypadkowi, gdy podzapytanie zawierało klauzulę OFFSET 0 ROWS, a czas wykonania różni się w granicach błędu. Oznacza to, że możesz użyć klauzuli OFFSET 0 ROWS jako wskazówki do wyłączenia konwersji semi-joina.
Teraz przyjrzyjmy się przypadkom, w których w podzapytaniach używany jest jakikolwiek skorelowany warunek inny niż równość i 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)
Jak powiedziałem powyżej, nie nastąpiła żadna transformacja do semi-joina, podzapytanie jest wykonywane dla każdego rekordu głównego zapytania.
Kontynuujmy eksperymenty, napiszmy zapytanie używające równości i jeszcze jednego predykatu oprócz równości.
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)
Tutaj w planie widzimy pierwsze użycie metody łączenia Nested Loop Join (semi), ale niestety ten plan jest zły, ponieważ indeks FK_COVER_FATHER nie jest używany. Nie otrzymasz żadnych wyników z takiego zapytania. Można to naprawić za pomocą wskazówki 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
Aktualna pamięć = 554017824
Delta pamięci = 320
Maksymalna pamięć = 554284480
Czas wykonania = 45.548 s
Bufory = 32768
Odczyty = 0
Zapisy = 0
Pobrania = 84145713
Statystyki per tabela:
--------------------------------+---------+---------+---------+---------+---------+
Nazwa tabeli | Naturalny| Indeks | Wstaw | Aktual. | Usuń |
--------------------------------+---------+---------+---------+---------+---------+
COVER | | 75894621| | | |
HORSE | | 96021| | | |
--------------------------------+---------+---------+---------+---------+---------+
Nie najlepszy czas wykonania, ale w tym przypadku przynajmniej otrzymaliśmy wynik.
Zatem konwersja podzapytań na ANY/SOME/IN/EXISTS do semi-joina pozwala w niektórych przypadkach znacznie przyspieszyć wykonanie zapytania, ale obecnie ta funkcja jest nadal niedoskonała i dlatego domyślnie wyłączona. W Firebird 6.0 spróbują dodać oszacowanie kosztów dla tej funkcji, a także naprawić szereg innych niedociągnięć. Ponadto Firebird 6.0 planuje dodać konwersję podzapytań ALL/NOT IN/NOT EXISTS do anti-joina.
Podsumowując przegląd wykonywania podzapytań w IN/EXISTS, chciałbym zauważyć, że jeśli masz zapytanie postaci
SELECT ...
FROM T1
WHERE IN (SELECT field FROM T2 ...)
lub
SELECT ...
FROM T1
WHERE EXISTS (SELECT ... FROM T2 WHERE T1. = T2.field)
to takie zapytania prawie zawsze są bardziej efektywne do wykonania jako
SELECT ...
FROM
T1
JOIN (SELECT DISTINCT field FROM T2) tmp ON tmp.field = T1.
Podam jasny przykład:
SELECT
COUNT(*)
FROM
HORSE H
WHERE H.CODE_HORSE IN (
SELECT
CODE_FATHER
FROM COVER
WHERE EXTRACT(YEAR FROM COVER.BYDATE) = 2022
)
Plan wykonania i statystyki przy użyciu 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
Aktualna pamięć = 554176768
Delta pamięci = 288
Maksymalna pamięć = 555531328
Czas wykonania = 0.229 s
Bufory = 32768
Odczyty = 0
Zapisy = 0
Pobrania = 569683
Statystyki per tabela:
--------------------------------+---------+---------+---------+---------+---------+
Nazwa tabeli | Naturalny| Indeks | Wstaw | Aktual. | Usuń |
--------------------------------+---------+---------+---------+---------+---------+
COVER | | 6695| | | |
HORSE | 525875| | | | |
--------------------------------+---------+---------+---------+---------+---------+
Dość szybko, ale tabela HORSE jest czytana w całości.
Plan wykonania i statystyki z klasycznym wykonaniem podzapytania
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
Aktualna pamięć = 553472512
Delta pamięci = 288
Maksymalna pamięć = 553966592
Czas wykonania = 6.862 s
Bufory = 32768
Odczyty = 0
Zapisy = 0
Pobrania = 2462726
Statystyki per tabela:
--------------------------------+---------+---------+---------+---------+---------+
Nazwa tabeli | Naturalny| Indeks | Wstaw | Aktual. | Usuń |
--------------------------------+---------+---------+---------+---------+---------+
COVER | | 1616| | | |
HORSE | 525875| | | | |
--------------------------------+---------+---------+---------+---------+---------+
Bardzo wolno. Tabela HORSE jest skanowana w całości, a podzapytanie jest wykonywane wielokrotnie - dla każdego rekordu w tabeli HORSE.
A teraz szybka opcja z 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
Aktualna pamięć = 554349728
Delta pamięci = 320
Maksymalna pamięć = 555531328
Czas wykonania = 0.011 s
Bufory = 32768
Odczyty = 0
Zapisy = 0
Pobrania = 14954
Statystyki per tabela:
--------------------------------+---------+---------+---------+---------+---------+
Nazwa tabeli | Naturalny| Indeks | Wstaw | Aktual. | Usuń |
--------------------------------+---------+---------+---------+---------+---------+
```markdown
COVER | | 6695| | | |
HORSE | | 1616| | | |
--------------------------------+---------+---------+---------+---------+---------+
Brak zbędnych odczytów, zapytanie wykonuje się bardzo szybko. Stąd wniosek - zawsze sprawdzaj plan wykonania podzapytań w IN/EXISTS/ANY/SOME i testuj alternatywne warianty zapisu zapytań.