お問い合わせ
IBSurgeon
このページは機械翻訳されています。英語の原文をお読みください。 English

IBSurgeon ライブラリ

Firebird 5.0.1 オプティマイザの改善点

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

最近、Firebird 5.0 DBMSのポイントリリースがリリースされました Firebird 5.0.1。エラーの修正に加えて、新しい実験的なオプティマイザ機能が追加されました。この記事ではそれについて説明します。

サブクエリのセミジョインでのANY/SOME/IN/EXISTSへの変換

セミジョインとは、2つのリレーションを結合し、完全な結合を実行せずに一方のリレーションからのみ行を返す操作です。他の結合演算子とは異なり、セミジョインを実行するかどうかを指定する明示的な構文はありません。ただし、ANY/SOME/IN/EXISTSのサブクエリを使用してセミジョインを実行できます。

従来、FirebirdはANY/SOME/IN述語のサブクエリをEXISTS述語の相関サブクエリに変換し、外部クエリの各レコードに対してEXISTS内のサブクエリを実行していました。EXISTS述語内のサブクエリを実行する場合、FIRST ROWS戦略が使用され、最初のレコードが返された直後に実行が停止します。

Firebird 5.0.1以降、ANY/SOME/IN/EXISTS述語のサブクエリをセミジョインに変換できます。この機能はデフォルトで無効になっており、firebird.confまたはdatabase.confファイルでSubQueryConversion設定パラメータをtrueに設定することで有効にできます。
この機能は実験的なものであるため、デフォルトでは無効になっています。有効にして、ANY/SOME/IN/EXISTS述語のサブクエリを含むクエリをテストし、パフォーマンスが向上する場合は有効のままにし、そうでない場合はSubQueryConversionパラメータをデフォルト値（false）に戻すことができます。
SubQueryConversion設定パラメータのデフォルト値は将来変更される可能性があり、パラメータ自体が完全に削除される可能性もあります。これは、新しい方法がほとんどの場合でより最適であることが証明された時点で発生します。

ANY/SOME/IN/EXISTSをサブクエリに対して直接、つまり相関サブクエリとして実行するのとは異なり、セミジョインとして実行すると最適化の余地が広がります。セミジョインはさまざまなHash Join (semi)やNested Loop Join (semi)アルゴリズムで実行できますが、相関サブクエリは常に外部クエリの各レコードに対して実行されます。

firebird.confファイルでSubQueryConversionパラメータをtrueに設定して、この機能を有効にしてみましょう。次に、いくつかの実験を行います。

次のクエリを実行してみましょう：

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のサブクエリは1回実行され、その結果がハッシュテーブルメモリに保存され、その後、外部クエリは単にこのハッシュテーブルを検索します。

比較のために、サブクエリからセミジョインへの変換を無効にして同じクエリを実行してみましょう。

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倍悪化しています。
読者は疑問に思うかもしれません：なぜハッシュセミジョインはCOVERテーブルのインデックス読み取りが5倍多いのに、それ以外は優れているのでしょうか？実際、統計のインデックス読み取りはインデックスを使用して読み取られたレコード数を示しており、インデックスアクセスの総数は示していません。その一部はレコードの取得にまったく至らず、これらのアクセスも無料ではありません。

何が起こったのでしょうか？サブクエリの変換をよりよく理解するために、架空のセミジョイン演算子「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 内の相関サブクエリはすべてセミジョインに変換できるでしょうか？ いいえ、すべてではありません。例えば、サブクエリに 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 (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "HORSE" as "H" Access By ID
                -> Bitmap
                    -> Index "FK_HORSE_DEPARTURE" Range Scan (full match)

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

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

ご覧のとおり、セミジョインへの変換は発生していません。では、OFFSET 0 ROWS を削除して、再度統計を取得しましょう。

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

ここではセミジョインへの変換が発生しており、実行時間が悪化していることがわかります。その理由は、現在オプティマイザが 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 (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 句をセミジョイン変換を無効にするヒントとして使用できるということです。

次に、サブクエリで等価比較と 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)

前述の通り、セミジョインへの変換は行われず、サブクエリはメインクエリの各レコードに対して実行されます。

実験を続けましょう。等価条件と、等価以外の述語を1つ使ったクエリを書いてみます。

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中子查询的执行计划，并检查编写查询的替代变体。