POSTD PRODUCED BY NIJIBOX

POSTD PRODUCED BY NIJIBOX

ニジボックスが運営する
エンジニアに向けた
キュレーションメディア

2015年9月16日

リレーショナルデータベースの仕組み (2/3)

How does a relational database work

(2015-08-19)by Christophe Kalenzaga

本記事は、原著者の許諾のもとに翻訳・掲載しております。

クライアントマネージャ

client manager in databases
クライアントマネージャは、クライアントとの通信を扱います。クライアントとは、（Web）サーバであったり、もしくはエンドユーザ、またはエンドアプリケーションであったりします。ここではJDBC、ODBC、OLE-DBといった良く知られる一連のAPIを介してデータベースにアクセスできる様々な方法が提供されています。

また、データベースアクセスのための専用のAPIも提供されています。

データベースと接続する手順は以下の通りです。

  • マネージャは最初に 認証を行い （ログイン情報とパスワードの確認）、次にデータベースにアクセスできる 権限 を持ち合わせているかチェックする。これらのアクセス権はDBAによって規定されている。
  • その後、クエリを管理できるプロセス（もしくはスレッド）が利用可能かチェックする。
  • データベースに高負荷がかかっていないかどうかも確認する。
  • 要求されているリソースを入手するために待機する。万が一タイムアウトになった場合には接続を遮断し、エラーメッセージを文章で表示する。
  • クエリをクエリマネージャに送信する。 その後、クエリの処理が始まる。
  • クエリの処理は「全か無か」ではないので、クエリマネージャから何らかのデータを受け取った時点で、 部分的な結果でもバッファに保存し、それらの送信を開始する。
  • 問題が生じた場合は通信を中断し、文章で問題を説明した上でリソースを開放する。

クエリマネージャ

query manager in databases

データベースの威力は、このクエリマネージャにあります。 書き方のひどいクエリはここで変換されて、素早く実行できるコードになるのです。そしてコードは実行されて、結果がクライアントマネージャに返されます。処理は以下のように複数のステップで行われます。

  • クエリは、有効性を確認するためにまず 構文解析 される
  • 次に、無駄な演算を除去し事前最適化を追加するために 書き換え られる
  • 次に、パフォーマンス向上のために 最適化 され、実行とデータアクセスのプランに変換される
  • 次に、そのプランが コンパイル される
  • 最後に、 実行 される

ここでは、最後の2点については重要度が低いので、詳しくは説明しません。

このパートを読んだ後、さらに理解を深めたい方には、以下の資料がお薦めです。

  • 1979年に発表された、コストベース最適化に関する初期の研究論文「 Access Path Selection in a Relational Database Management System 」。わずか12ページの論文で、コンピュータサイエンスの平均的な知識があれば理解できます。
  • DB2 9.xのクエリ最適化方法が詳しく説明されている、非常に優れた プレゼンテーション
  • PostgreSQLのクエリ最適化方法が説明されている、非常に優れた プレゼンテーション 。これは、「PostgreSQLで使われているアルゴリズムを見てみる」というより「PostgreSQLがこのような状況でどんなクエリプランを作成するか見てみる」という内容なので、大変理解しやすい資料です。
  • 最適化についての公式の SQLiteドキュメンテーション 。SQLiteのルールはシンプルなので、”読みやすい”資料です。しかも、その仕組みがきちんと説明されている唯一の公式文書です。
  • SQL Server 2005のクエリ最適化方法が説明されている、優れた プレゼンテーション
  • Oracle 12cでの最適化に関する ホワイトペーパー
  • クエリ最適化に関して、書籍『Database System Concepts』の著者が提供する2つの理論コースが こちら と こちら 。ディスクI/Oのコストに焦点を当てている優れた資料ですが、コンピュータサイエンスの相当な知識が必要です。
  • それとは別の 理論コース 。こちらの方が理解しやすいと思いますが、主に取り上げられているのは結合演算子とディスクI/Oのみです。

クエリパーサ

各SQL文はパーサに送られ、構文の正しさがチェックされます。クエリに誤りがあった場合は、パーサが拒否します。例えば、”SELECT …”とするべきところで”SLECT …”と書いてあると、処理はそこで終了します。

パーサはさらに、キーワードが正しい順序になっているかもチェックします。例えば、WHEREがSELECTの前にあるような文も拒否します。

次に、クエリに含まれるテーブルとフィールドを解析します。パーサはデータベースのメタデータを使って以下の点をチェックします。

  • テーブルが存在 するか
  • テーブルの フィールド が存在するか
  • フィールドの型に対してその 演算 が 可能 であるか（例：整数と文字列は比較不可。整数に対してsubstring()関数は使用不可）

次に、クエリ内のテーブルに対して読み込み（または書き込み）の権限があるかをチェックします。繰り返しますが、このようなテーブルへのアクセス権はDBAが設定しています。

この解析中に、SQLクエリは内部表現（多くはツリー）に変換されます。

全ての点で問題がなければ、内部表現はクエリリライタへ送られます。

クエリリライタ

この段階で、クエリの内部表現が得られています。リライタの目的は以下の通りです。

  • クエリを事前に最適化する
  • 不必要な演算を回避する
  • オプティマイザが最善のソリューションを見つけられるようにする

リライタは、クエリに対して既知のルールのリストを実行します。クエリがルールのパターンに一致した場合は、ルールが適用されクエリは書き換えられます。以下は網羅的なものではありませんが、（オプションの）ルールのリストです。

  • ビューのマージ ：クエリ内でビューを使っている場合、ビューは、ビューのSQLコードで変換される。
  • サブクエリのフラット化 ：サブクエリがあると最適化が非常に難しいため、リライタは、サブクエリを含むクエリを、サブクエリを使わない形に変えようとする。

例を見てみましょう。

SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE 'christophe%');

これは以下のように書き換えられます。

SELECT PERSON.*
FROM PERSON, MAILS
WHERE PERSON.person_key = MAILS.person_key
and MAILS.mail LIKE 'christophe%';
  • 不必要な演算子の除去 ：例えば、データの重複を排除するUNIQUE制約があるのにDISTINCTが使われている場合、DISTINCTキーワードは除去される。
  • 冗長な結合の削除 ：1つの結合条件がビューに隠れているために同じ結合条件が2回与えられていたり、中間に無駄な結合があったりする場合、その結合は除去される。
  • 定数計算の評価 ：計算の必要な処理が書かれている場合は、書き換え中に1回計算される。例えば、「WHERE AGE > 10+2」は「WHERE AGE > 12」に変換され、「TODATE(“ある日付”)」はdatetime形式の日付に変換される。
  • （高度）パーティションプルーニング ：パーティションテーブルが使われている場合、リライタはどのパーティションを使うべきか認識する。
  • （高度）マテリアライズドビューの書き換え ：クエリ内の述語のサブセットに一致するマテリアライズドビューがある場合、リライタはビューが最新の状態であるかチェックし、生のテーブルの代わりにマテリアライズドビューを使うようクエリを変更する。
  • （高度）カスタムルール ：クエリ変更のカスタムルールがある場合（Oracleのポリシーなど）、リライタはそれらのルールを実行する。
  • （高度）OLAP変換 ：分析/ウィンドウ関数、スター結合、ロールアップなども変換される（ただし、これがリライタとオプティマイザのどちらによって処理されるのか確信がありません。というのも、両プロセスは密接な関係があるので、それはデータベースによって異なるはずだからです）。

こうして書き換えられたクエリは、クエリオプティマイザに送られます。さあ、面白い部分に入ってきました！

統計

データベースの最適化について触れる前に、まず 統計 について見ておく必要があります。 統計なしではデータベースは役に立たない からです。指示を出さなければデータベースはデータ分析をしませんし、（非常に）精度の低い想定をします。

データベースが必要とする情報とはどのようなものでしょうか。

まず手短に、データベースとオペレーティングシステムのデータ格納方法について説明します。

データ格納にはページまたはブロック（初期値で4～8キロバイト）と呼ばれる最小単位が用いられます。つまり1KBしか必要ではなかったとしても、1ページ分が使用されるということです。ページが8KB確保する場合、7KBは無駄になります。

統計の話に戻りましょう。データベースに対し統計を収集するよう指示を出すと、下記のような値を算出します。

  • テーブル上の行数とページ数

  • テーブル上の各列に対して

    • ディスティンクトなデータ値
    • データ値の長さ（最小、最大、平均）
    • データレンジの情報（最小、最大、平均）
  • テーブルのインデックスについての情報

上記のような統計値を参考にして、オプティマイザはクエリのディスクI/Oや、CPUとメモリの使用量を推定します。

各列の統計はとても重要です。PERSONというテーブルを2列、すなわちLASTNAMEとFIRSTNAMEに結合する必要があるとします。統計値から、データベースは「FIRSTNAMEの異なる値は1 000しかなく、LASTNAMEには1 000 000の異なる値がある」と把握しているので、LASTNAME,FIRSTNAMEという順番でデータを結合します。FIRSTNAME,LASTNAMEの順ではないのは、LASTNAMEが同じ値になる可能性が低いため、比較する値が少なくて済むからです。大抵の場合、LASTNAMEの最初の2～3文字を比較すれば十分です。

これは基本的な統計です。ヒストグラムと呼ばれるより高度な統計値を算出させることもできます。ヒストグラムは、列内の値の分布についての情報を表す統計です。下記に例を挙げます。

  • 最頻値
  • 数量
  • などなど

このような追加の統計値によってデータベースはより良いクエリプランを導き出すことができます。特に等値の述語（例：WHERE AGE = 18）や、範囲を問う述語（例：WHERE AGE > 10 and AGE <40）はそうです。データベースがこれらの述語に関連した行の数量についてよりよく分かるからです（注： この概念を専門的に言うと「選択性」です）。

統計値はデータベースのメタデータの中に格納されます。例えば、（非パーティションの）テーブルの統計は下記のような箇所にあります。

  • OracleではUSER/ALL/DBATABLESとUSER/ALL/DBAtAB_COLUMNS
  • DB2ではSYSCAT.TABLESとSYSCAT.COLUMNS
    統計値は最新でなくてはなりません。 実際はテーブルに1 000 000の列があるのに、データベースが500列しかないと判断したら最悪です。統計のたった1つの欠点は、 算出に時間がかかるということです。 そのため、デフォルトでは多くのデータベースで自動的に算出されません。膨大な量のデータを元に計算するのは難しいからです。この場合、基本的な統計値だけ、またはデータベースのサンプルについてだけ統計値を算出することも選択できます。

以前、各テーブルで数億規模の行を扱うプロジェクトに私が関わっていた時、全データの10%だけ計算するという選択をして時間が大変節約できたことがあります。しかしこれは実際のところ悪い判断で、Oracle 10Gが選択した10%のテーブルの列は、全体と比較して全く違うものでした（列の数が100M程度であればこういうことは起こりにくいでしょう）。この誤った統計値のせいで、30秒で終わるはずのクエリは8時間かかり、原因を探すのは大変な作業でした。統計値がどれほど重要かこの例からお分かりになるでしょう。

注： もちろん各データベースに特有の高度な統計があります。興味があれば、データベースのドキュメントを読んでみてください。参考までに、私なりに統計の使用法の理解に努めた範囲で、オフィシャルなドキュメントの中で最高なのは PostgreSQL のものでした。

クエリオプティマイザ

CBO

最新のデータベースはクエリの最適化に全てコストベース・オプティマイザ（またはCBO）を利用しています。この概念は、全ての処理にコストを加味して、結果を得るため一番安価な一連の処理を使い、クエリのコストを削減するベストな方法を見つけるというものです。

コスト・オプティマイザの機能を理解するためには、タスクの複雑性を「感じる」ことのできる例を挙げるのがいいでしょう。このパートでは、2つのテーブルを結合する一般的な手法を3つ提示します。シンプルなクエリによる結合でも、最適化するのは大変だということがすぐに分かると思います。それから、実際のオプティマイザの仕事ぶりを見ることにしましょう。

今回の結合に関しては時間計算量に着目しますが、 データベースオプティマイザはCPUコスト、ディスクI/Oコストと、必要メモリを算出します 。時間計算量とCPUコストの違いは、時間のコストはかなり大雑把だということです（私のような怠け者にはぴったりです）。CPUコストの場合、加算や”if文”、乗算、反復処理や、その他いろいろな要素を考慮しなくてはなりません。例えば下記のようになります。

  • 高水準なコード処理は、複数個の低水準なCPU処理からなり、その個数はコード処理ごとに一意に定まります。
  • CPUサイクルの観点から言うと、CPU処理のコストはIntel Core i7を使っているか、Intel Pentium 4なのか、AMD Opteronなのかによって異なります。つまりCPUのアーキテクチャに依存するということです。

時間計算量を用いると（少なくとも私にとっては）楽ですし、それによってCBOの概念を理解できます。私はよくディスクI/Oのことについて言及しますが、それは重要な概念だからです。大抵の場合 ディスクI/Oこそがボトルネックであり、CPU使用率ではない ということを覚えておいてください。

インデックス

B+ツリーについての項でインデックスについても説明しましたが、その場合 インデックスはソート済み です。

ご参考まで、他にも ビットマップインデックス などのインデックスもあります。CPU、ディスクI/Oやメモリの観点では、B+ツリーのインデックスと同等のコストではできません。

更に、多くの最新のデータベースは、実行プランのコストを改善できる場合、現在のクエリのためだけに 動的にテンポラリのインデックスを作成することができ ます。

アクセスパス

結合演算子を適用する前に、まずはデータを取得しなくてはなりません。ここではデータ取得方法について説明します。

注：全てのアクセスパスにおける本当の問題はディスクI/Oなので、時間計算量についてはあまり触れません。

フルスキャン

実行プランを読んだことがあるなら、 フルスキャン （または、単にスキャン）という言葉を見かけたことがあるかもしれません。フルスキャンとはデータベースが全てのテーブルやインデックスを読み込むことです。 ディスクI/Oの観点から言うと、テーブルのフルスキャンはインデックスのフルスキャンよりも明らかに高価です。

レンジスキャン

さらに、 インデックス・レンジスキャン などの他のタイプのスキャンもあります。”WHERE AGE > 20 AND AGE <40″などのような述語を用いる時の例として用いられます。

もちろんインデックス・レンジスキャンを使うためには、AGEフィールドのインデックスを持っていなくてはなりません。

さて、レンジクエリの時間のコストはlog(N) +Mのような値になるということに触れました。Nはこのインデックスのデータの数量で、Mはレンジ内の行の数量の予測値です。 NとMの値はどちらも、統計値のおかげで分かりました （注：MはAGE >20 AND AGE<40という述語の選択性です）。更に、レンジスキャンでは、全部のインデックスを読み込む必要がないので、 フルスキャンに比べてディスクI/Oの観点からはより安価である と言えます。

ユニークスキャン

インデックスから1つの値だけが必要ならばユニークスキャンが使えます。

行番号によるアクセス

データベースがインデックスを用いている場合は大抵、インデックスに関連付けられた行を探さなくてはなりません。そのためには、行番号によるアクセスを使います。

例えば、以下のようになります。

SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

年齢を列に持つインデックスがある場合、オプティマイザはそのインデックスを使って28歳の人を全て探し、それからテーブルに関連した行を問い合わせます。インデックスには年齢についての情報しかなく、lastnameとfirstnameも知る必要があるからです。

次に、下記のようにしてみます。

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
WHERE PERSON.AGE = TYPE_PERSON.AGE

この場合はPERSONのインデックスが用いられ、TYPE_PERSONと結合されますが、PERSONというテーブルは行番号ではアクセスできないので、このテーブルでは情報を問い合わせません。

少量のアクセスに関してはうまく機能しますが、この処理の本当の問題はディスクI/Oです。行番号による大量のアクセスが必要なら、データベースはフルスキャンを選択するかもしれません。

他のパス

全てのアクセスパスに関してここでは紹介していません。もっと知りたければ Oracleのドキュメント を参照してください。他のデータベースとは違う用語を使っているかもしれませんが、基本的なコンセプトは同じです。

結合演算子

データの入手方法が分かったところで、それらを結合しましょう。

3つの主な結合演算子を紹介しましょう。マージ結合、ハッシュ結合、そしてネスト・ループ結合です。しかしその前に、新しい用語を紹介しておきます。 内部リレーションと外部リレーション です。リレーションとは、以下のようなものです。

  • テーブル
  • インデックス
  • 先に行っていたオペレーションの中間結果（例えば、前に行った結合の結果）

2つのリレーションを結合させるとき、結合のアルゴリズムはその2つを異なる方法で扱います。ここから先は、次のような仮定で説明していきます。

  • 外部リレーションは左のデータセット
  • 内部リレーションは右のデータセット

例えば、A JOIN Bとは、Aが外部リレーション、Bが内部リレーションのときにAとBの間を結合するということです。

ほとんどの場合、 A JOIN BのコストはB JOIN Aのコストとは同じになりません。
この項では、外部リレーションがN要素を持ち、内部リレーションがM要素を持っていると想定しましょう。 実際のオプティマイザは、統計からNとMの値を知っていることを覚えておいてください。

注：NとMはリレーションの基数を表す

ネステッド・ループ結合

一番簡単なのは、ネステッド・ループ結合です。

nested loop join in databases

これは、以下のようなものになります。

  • 外部リレーションの各行が対象で
  • 内部リレーションのすべての行に、適合する行があるかどうか調べます

ここに、疑似コードを記載します。

nested_loop_join(array outer, array inner)
  for each row a in outer
    for each row b in inner
      if (match_join_condition(a,b))
        write_result_in_output(a,b)
      end if
    end for
   end for

これは二重の反復なので、 時間計算量はO(N*M)となります。

ディスクI/Oについて考えてみます。外部リレーションのN行の各データについて、内部のループは内部リレーションからM行を読む必要があります。このアルゴリズムは、ディスクからN+N*M行を読み込む必要があります。しかし、内部リレーションが小さい場合、リレーションをメモリの中に入れ、読みこみをM+N 行だけに抑えるできます。この調整では、メモリの中に入りやすいよう、 内部リレーションは最小である必要があります。

時間計算量に関しては違いが生じませんが、ディスクI/Oに関しては両方のリレーションを一度だけ読みこんだ方がはるかにいい結果になります。

もちろん、内部リレーションはインデックスと置き換えることもできます。ディスクI/Oのためにはその方がいいでしょう。

このアルゴリズムはとてもシンプルなので、さらに別の方法も紹介しておきましょう。これは、内部リレーションが大きすぎてメモリに入らない場合に、よりディスクI/Oに有利な方法です。
それは、以下のようなものです。

  • 1行ずつ両方のリレーションを読むのではなく、
  • 固まりごとに読み、メモリに（それぞれのリレーションから）行の固まりを2つ保持します。
  • 2つの固まりの中で行を比較し、適合する行を保持します。
  • そしてディスクから新しい固まりを読み込み、それらを比較します。
  • 読み込む固まりがなくなるまで続けられます。

以下のようなアルゴリズムを用いることができるかもしれません。

// improved version to reduce the disk I/O.
nested_loop_join_v2(file outer, file inner)
  for each bunch ba in outer
  // ba is now in memory
    for each bunch bb in inner
        // bb is now in memory
        for each row a in ba
          for each row b in bb
            if (match_join_condition(a,b))
              write_result_in_output(a,b)
            end if
          end for
       end for
    end for
   end for

この例では時間計算量は変動しませんが、ディスクアクセスの回数は減ります。

  • 先に挙げた例では、アルゴリズムはN＋N*Mへのアクセスを要求しました（各アクセスで1つの行が得られます）
  • この新しい例では、ディスクアクセスの回数は
    numberofbunchesfor(outer)+ numberof_ bunchesfor(outer)* numberof_ bunches_for(inner)となります。
  • 固まりのサイズを大きくすると、ディスクアクセスの数を減らすことになります

注：各ディスクアクセスは、先ほどのアルゴリズムよりも多くのデータを集めます。しかし、それらはシーケンシャルアクセスなので関係ありません（機械式ディスクの本当の問題は、最初のデータを得るまでの時間です）。

ハッシュ結合

ハッシュ結合はもっと複雑ですが、多くの場合ネスト・ループ結合よりもコストが低くなります。

hash join in a database

ハッシュ結合の概念とは、以下のようなものです。

  • 1)全ての要素を内部リレーションから得る
  • 2)メモリ内部にハッシュテーブルを構築する
  • 3)外部リレーションの全ての要素を1つずつ得る
  • 4)内部リレーションの関連づけられたバケットを探すため、各要素のハッシュを（ハッシュテーブルのハッシュ関数で）計算する
  • 5)バケット内の要素と外部のテーブルの要素の間に一致があるか探す

時間計算量に関しては、問題をより単純にしてくれる前提を仮定する必要があります。

  • 内部リレーションはX個のバケットに分割されている
  • ハッシュ関数は、どちらのリレーションにもほぼ均等にハッシュ値を割り当てます。言い換えれば、バケットのサイズは等しくなります
  • 外部リレーションの要素とバケット内の全ての要素の関連は、バケット内の要素の数だけコストがかかります。

時間計算量は(M/X) * (N/X) + costtocreatehashtable(M) + costofhash_function*Nという式で表されます。

ハッシュ関数が十分に少数サイズのバケットを生成するならば、 時間計算量はO(M+N)で計算できます。

ハッシュ結合の別のバージョンでは、メモリの節約は利くけれども、ディスクI/Oには優しくないものがあります。今回は：

  • 1)内部リレーションと外部リレーション両方のハッシュテーブルの値を算出します
  • 2)求めたハッシュテーブルの値をディスクに置きます
  • 3)（1つはメモリ内に積んだもの、もう1つは行ごとに読まれているものと共に）バケットで2つのリレーションをバケットごとに比較します

マージ結合

マージ結合は、結果をソートされた状態で出力する唯一の結合です。

注：簡素化したマージ結合では、内部表（インナーテーブル）、外部表（アウターテーブル）とも存在しません。つまり、どちらも同じ役割をするということです。しかし実際の実行では異なります。例えば、データの複製を行う時などです。

マージ結合は2つのステップに分けられます。

1.（オプションとして）ソート結合の実行：入力した両方の値は結合キー上でソートされます

  1. マージ結合演算：ソートされた入力値は同時にマージされます

ソート

マージソートについては、すでに触れましたが、今回のケースでは（メモリを問題としないのであれば、最善ではありませんが）優れたアルゴリズムにおけるマージソートについて扱っていきます。

中にはデータセットがすでにソートされている場合もあります。以下がその例です。

  • テーブルに初めから規則性がある場合、例えば、結合条件における索引構成表（IOT）など
  • リレーションが結合条件で索引になっている場合
  • クエリの過程ですでにソートされている中間結果上で、この結合が採用される場合

マージ結合

merge join in a database
このパートはすでに見てきたマージソートでのマージにとても似ています。ですが、今回は2つのリレーションから全ての要素を取り出す代わりに、値が同じ要素だけを取り出します。考え方は以下のとおりです。

  • 1）2つのリレーションの現状の要素を比べてみます（最初は1番目から）
  • 2）もし値が同じであれば、両方の要素を結果に入れ、それぞれのリレーションの次の要素に移ってください
  • 3）もし値が同じでなければ、小さいほうの値を要素にもつリレーションを、次の要素に進めます（次の要素は一致するかもしれないからです）
  • 4）1から3の手順を繰り返し、どちらかのリレーションの最後の要素に到達するまで続けてください

この手順は2つのリレーションがソートされているので、うまくいきます。そのため、それぞれのリレーションを”戻る”必要はありません。

このアルゴリズムは簡易化されたバージョンです。とういうのも、同じデータが両方の配列で（言い換えれば複数が適合している場合に）何度も現れるケースを扱うことができないからです。実際のバージョンは、このような場合だけ、より複雑になります。簡易化されたバージョンを選択したのは、このためです。

2つのリレーションがすでにソートされている場合、 時間計算量はO(N+M)になります。

一方で2つのリレーションにソートが必要な場合は、時間計算量はソートする時間がかかるので、 O(N*Log(N) + M*Log(M)) で表されます。

CSオタクのための、複数適合する場合を扱う実行可能なアルゴリズムが以下になります（注：このアルゴリズムに100%自信があるわけではありません）。

mergeJoin(relation a, relation b)
  relation output
  integer a_key:=0;
  integer b_key:=0;

  while (a[a_key]!=null and b[b_key]!=null)
    if (a[a_key] < b[b_key]) a_key++; else if (a[a_key] > b[b_key])
      b_key++;
    else //Join predicate satisfied
      write_result_in_output(a[a_key],b[b_key])
      //We need to be careful when we increase the pointers
      integer a_key_temp:=a_key;
      integer b_key_temp:=b_key;
      if (a[a_key+1] != b[b_key])
        b_key_temp:= b_key + 1;
      end if
      if (b[b_key+1] != a[a_key])
        a_key_temp:= a_key + 1;
      end if
      if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1])
        a_key_temp:= a_key + 1;
        b_key_temp:= b_key + 1;
      end if
      a_key:= a_key_temp;
      b_key:= b_key_temp;
    end if
  end while

最適なのはどれか

結合に最適な型があれば、それは複数型ではないでしょう。これはとても難しい問題です。なぜなら以下のようにたくさんの要因が働いているからです。

  • メモリの使用量 ：十分なメモリがなければ、強力なハッシュ結合には別れを告げることになる（少なくともハッシュ結合のインメモリがいっぱいな場合）
  • 2つのデータセットのサイズ ：例としては、とても小さいテーブルと一緒に大きいテーブルがある場合、ネスト･ループ結合はハッシュ結合よりも処理が速いでしょう。ハッシュ結合がハッシュの生成に手間がかかるのが理由です。もし、巨大な2つのテーブルがあるのであれば、ネスト･ループ結合はとてもCPUを消費するでしょう。
  • インデックスの存在 ：B-treeインデックスがあれば、マージ結合が賢明な選択でしょう
  • 結果にソートが必要な場合 ：ソートされていないデータセットで処理をしている場合でさえ、コストのかかるマージ結合を（ソートと一緒に）使いたくなるでしょう。なぜなら、最終的には結果はソートされた状態になるため、その結果を別のマージ結合に用いることができるから(あるいは、明示的/暗黙的のどちらかを問わず、クエリがORDER BY/GROUP BY/DISTINCT演算子でソートされた結果を要求するから)です。
  • すでにソートされているリレーションの場合 ：このケースではマージ結合が最適な候補です。
  • 実行している結合の型：その結合が等結合（すなわちtableA.col1 = tableB.col2）になっているかどうか。そして インナー結合、アウター結合、カルテシアン積、 または 自己結合 になっているかどうか、という要因です。中にはある状況ではうまくいかない結合もあります。
  • データの分散 ：もし結合条件のデータが（例えば「人を表すレコードをラストネームで結合しようとしているのに、多くの人が同じ名前の場合など） 偏っている 場合、ハッシュ結合を使うのは面倒なことになるでしょう。結果的にハッシュ関数が、不適切な配分のバケットを作りだしてしまいます。
  • マルチスレッド/プロセス で実行された結合が欲しい場合。

さらに知りたい場合は、 DB2 、 ORACLE または SQL サーバ のドキュメントを読んでください。

簡易例

結合演算の種類を3つ見てきました。

では、1人の情報を全て表示するのに5つのテーブルを結合するとしましょう。例えば以下のような情報を表示します。

  • 複数の携帯電話の番号（MOBILES）
  • 複数のメールのアドレス（MAILS）
  • 複数の住所（ADRESSES）
  • 複数の銀行口座番号（BANK_ACCOUNTS）

言い換えれば、以下のクエリに関して瞬時に応える必要があるということです。

SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID

クエリのオプティマイザとして、このデータを処理するベストな方法を見つけなければいけません。しかし、以下の2つの問題が生じます。

  • それぞれの結合にどの種類の結合を使えばいいのでしょうか？

結合の選択肢は3種類（ハッシュ結合、マージ結合、ネスト結合）あり、それぞれインデックスを0個、1個、2個使います（言うまでもなく、インデックス自体にいくつも種類があります）。

  • 結合を算出するのにどういう順序がいいのでしょうか？

以下の図は、4つのテーブルで3つの結合を使った数種類のプラン例です。

join ordering optimization problem in a database

ということで、以下のことが考えられます。

  • 1）総当たり方式を使う
    データベースの統計を使って、 ありとあらゆるプランのコストを計算し 、ベストな方法を割り出します。しかし、可能性は山ほどあります。仮に結合する順序を固定するとしても、それぞれの結合には3つの可能性(ハッシュ結合、マージ結合、ネスト結合)があります。結合順序が定まっている場合、プランは3 ⁴ 個だけ存在することになります。結合順序の個数は バイナリーツリー上の順列の問題 で、(2*4)!/(4+1)!個の可能性があります。この簡易化された問題では、結局、3 ⁴ *(2*4)!/(4+1)!個もの可能性があることになります。

非ギークの方向けに計算してみると、27,216個だけのプランがありうるということになります。もし、B+ツリーのインデックスを0～2個利用するマージ結合の可能性を追加した場合、プランの選択肢は210,000になります。クエリはとっても簡単だって、私言いましたよね？

  • 2）泣いて、そしてこの仕事を辞める
    とても魅力的な選択肢ですが、これでは答えが得られないし、生活費も払えなくなってします。
  • 3）いくつかのプランのみ試してみて、その中で一番低いコストのものを選ぶ。
    私はスーパーマンではないので、全てのプランのコストを計算するのは不可能です。その代わりに、 ありうる全てのプランの中から一部だけ無作為に選んで 、それらのコストを計算し、その中からベストなプランを選びます。
  • 4）賢い ルールを適用してプランの数を減らす。
    これには2種類のルールがあります。
    ”論理的な”ルールを使って、使えなさそうな選択肢を消していきます。ただしそれでも除外できるプランはそんなに多くはありません。例えば、”ネスト・ループ結合の内部のリレーションは、最も小さなデータセットである必要がある”というルールなどです。
    これではベストな解は見つかりません。多くの選択肢を減らすためにはもう少しアグレッシブなルールを適応します。例えば、”リレーションが小さければ、ネスト･ループ結合を使って、マージ結合やハッシュ結合は使わない”などです。

この単純な例では、多くの選択肢が残ってしまいます。しかし、 実際のクエリは、他のリレーショナル演算子を持っています。 例えば、OUTER JOIN、CROSS JOIN、 GROUP BY、 ORDER BY、 PROJECTION、UNION、INTERSECT、DISTINCTなどです。 つまり、さらに多くの選択肢があるということです。

では、データベースはどう対処しているのでしょうか？

ダイナミックプログラミング、貪欲アルゴリズム、ヒューリスティック

リレーショナルデータベースは、私が今説明したような複数の方法を試みます。オプティマイザの本来の役割は、時間に制約のある中で解を見つけることです。

オプティマイザは大抵の場合、最適解は見つけられませんが、”良い”解なら見つけられます。

クエリが少なければ、総あたり方式が使えます。しかし、無駄な計算を避けるようにする方法もあります。ですから、中くらいのクエリの場合でも総あたり方式が使えます。これをダイナミックプログラミングと呼びます。

ダイナミックプログラミング

この方法の裏に隠されているアイデアは、多くの実行されるプランがよく似ているということにあります。以下のプランをご覧ください。

overlapping trees optimization dynamic programming

これらは同じ(A JOIN B)のサブツリーです。つまり、各プランで毎回このサブツリーのコストを計算するのではなく、一度だけ計算をし、計算されたコストを保存し、別のプランで同じサブツリーが出てきた時に再利用します。堅苦しく言うと、重複問題に直面していると言えます。部分的に余計な計算を避けるため、メモ化をするのです。

この方法を使えば、(2*N)!/(N+1)!の計算量だったのが、”たった”の3Nまで減らすことができます。先ほどの4つの結合の例で言うと、順序が336から81にまで減らせます。例えば、 結合数が8のクエリだとすると （それほど大きい数ではありませんが）、 57,657が6,561になります。

これが 既にご紹介した、私がクラスの授業で発見したコンピュータサイエンスのプロ向けのアルゴリズム です。このアルゴリズムに関しては、ここでは説明を省きます。もし、ダイナミックプログラミングの知識が既にある人か、アルゴリズムが得意な人であれば読んでみてください（私は忠告しましたよ！　）。

procedure findbestplan(S)
if (bestplan[S].cost infinite)
   return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
         set bestplan[S].plan and bestplan[S].cost based on the best way
         of accessing S  /* Using selections on S and indices on S */
     else for each non-empty subset S1 of S such that S1 != S
   P1= findbestplan(S1)
   P2= findbestplan(S - S1)
   A = best algorithm for joining results of P1 and P2
   cost = P1.cost + P2.cost + cost of A
   if cost < bestplan[S].cost
       bestplan[S].cost = cost
      bestplan[S].plan = “execute P1.plan; execute P2.plan;
                 join results of P1 and P2 using A”
return bestplan[S]

もっと多数のクエリの場合でもダイナミックプログラミングは使えますが、選択肢を減らすためにルール（または ヒューリスティック ）を追加しましょう。

  • もしある特定の種類のプランのみを分析する場合は（例えば、左側の深いツリー）、 n*2 ^(n) ではなく、 3 ^(n) となります。

left deep tree example

  • 論理的なルールを追加して、あるパターンのプランを排除すると（”テーブルが今回の仮の命題のインデックスであるならば、マージ結合はそのテーブルでは使わずにインデックスで使う”というふうに）、最適解を傷つけることなく、選択肢を減らすことができます。
  • もしフローの中でルールを追加したら（”全てのリレーショナル演算の前に結合演算を実行する”ように）、さらに多くの選択肢を減らすことができます。
  • などなど。

貪欲アルゴリズム

しかし、大量のクエリや素早く答えを出したい場合は（すごく速いクエリではなく）、別のアルゴリズムを使います。それが、貪欲アルゴリズムです。

この方法は、ルール（または ヒューリスティック ）に従い、増分法でクエリのプランを作成します。このルールで貪欲アルゴリズムを使えば、１回毎に問題に対する最適解を見つけます。この方法では、1つのJOINだけでクエリプランを始めます。それから、それぞれの段階で、同じルールを使って、クエリプランに新しいJOINを追加します。

簡単な例で説明しましょう。5つのテーブル（A、B、C、D、E）で4つの結合があるクエリだとします。問題を簡易化するのに、使える結合の中からネスト結合を使うことにしましょう。例えば、”最低のコストの結合を使う”というルールを使いましょう。

  • 5つのテーブルから1つを無作為に選びます（今回はAを選んだとしましょう）。
  • Aの全ての結合のコストを計算します（Aは内部もしくは外部のリレーションです）。
  • A JOIN Bが最低のコストだと分かりました。
  • それからA JOIN Bの結果を用いる全ての結合のコストを計算します（A JOIN Bは内部もしくは外部のリレーションです）。
  • (A JOIN B) JOIN Cがベストなコストだと分かりました。
  • 次に(A JOIN B) JOIN Cの結果を用いる全ての結合のコストを計算します。
  • これを繰り返していきます。
  • 最後には(((A JOIN B) JOIN C) JOIN D) JOIN E)が最適なプランだと分かりました。

初めに無作為にAを選んだら、次は同じアルゴリズムをBに適応し、次にC、次にD、最後にEと適応していくことができます。こうすれば、最低コストのプランを保つことができます。

ところで、このアルゴリズムには名前があります。 最近傍法 です。

詳細は省きますが、良いモデリングやN*log(N)のソートでは、この問題は 簡単に解決することができます 。 このアルゴリズムのコストはO(N*log(N))で、ダイナミックプログラミングではO(3 ^(N) )です。 例えば20の結合がある膨大なクエリの場合は、26と3,486,784の差が出ます。これは大きな差ですよね！

このアルゴリズムでの問題点は、2つのテーブル間でベストな結合を見つけ出せば、その後その結合に新しい結合を追加した場合でもベストなコストを導き出せると思い込んでしまうことです。しかし、それは違います。

  • A、B、Cの中でA JOIN Bがベストなコストだとしても、
  • (A JOIN C) JOIN Bが(A JOIN B) JOIN Cよりも良い結果になる可能性もあります。

結果を改善していくには、別のルールを使った複数の貪欲アルゴリズムを実行し、ベストなプランを保ってください。

他のアルゴリズム

[もうすでにアルゴリズムに飽き飽きしてしまっていたら、このパートは飛ばしてください。ここで話す内容は、この後の記事の内容にはあまり関わってきません。]

ベストなプランを見つけるという課題は、多くのコンピュータサイエンスの研究者がよく対面するトピックです。より重要な問題やパターンのために、より良い解はないかと彼らはしばしば模索しています。例えば、以下のような例が挙げられます。

  • クエリがスター結合なら（結合数の多いクエリのような種類のもの）、あるデータベースでは特定のアルゴリズムを使用します。
  • クエリが並列クエリなら、あるデータベースでは特定のアルゴリズムを使います。
  • などなど。

なお、ダイナミックプログラミングに取って代わる、膨大なクエリを処理できる他のアルゴリズムが研究されています。貪欲アルゴリズムは ヒューリスティックアルゴリズム と呼ばれる、より大きなカテゴリーに所属します。貪欲アルゴリズムはルール（またはヒュールスティック）に従って、前段階で見つけた最適解を維持し、現段階での最適解を見つけるために前回のものを”アペンド”します。一部のアルゴリズムではルールに従い、段階ごとにそれを適用しますが、前段階で見つけた最適解をいつも維持するとは限りません。これをヒューリスティックアルゴリズムと呼びます。

例えば、 遺伝的アルゴリズム はルールに従いますが、最終ステップでの最適解は維持されるとは限りません。:

  • 解では、全てのクエリプランを表します。
  • 1つの解（すなわち、1つのプラン）ではなく、P個の解（すなわち、複数のプラン）を各段階で維持します。
  • 0）P個のクエリプランがランダムに作成されます。
  • 1）ベストなコストのプランのみがいくつか維持されます。
  • 2）それらのベストなプランは、P個の新しいプランを生成するために混在しています。
  • 3）P個の新しいプランの内のいくつかは無作為に修正されます。
  • 4）上記のステップ1、2、3がT回繰り返されます。
  • 5）そして最後のループでP個のベストなプランが維持されます。

回数を繰り返せば繰り返すほど、より良い結果が得られます。

これは魔法でしょうか？　いえ、これは自然の法則です。適者のみが生存できるのです！

参考までに言うと、遺伝的アルゴリズムは PostgreSQL で実装されています。しかし、これがデフォルトで使用されているのかどうかは私には分かりませんでした。

他にも下記のようなデータベースで使われているヒューリスティックアルゴリズムがあります。焼きなまし法、反復改良法、2段階最適化などです。しかし、これらが企業向けのデータベースで使われているのか、もしくは研究向けのデータベースでのみ使われているのかは私には分かりません。

実際のオプティマイザ

[この項目はスキップしても構いません。それほど重要な内容ではありません]
しかしここで述べている諸々のことは非常に理論的です。私は研究者ではなく開発者なので、 具体的な例 が好きなのです。

SQLiteオプティマイザ がどのように機能するのか見てみましょう。SQLiteは軽量なデータベースなので、選択肢を制限するために例外ルールを用いながら、貪欲アルゴリズムに基づいて単純な最適化を使います。つまり、

  • SQLiteはCROSS JOIN演算子の場合はテーブルを再度順序付けしません。
  • 結合はネスト結合として実装されています。
  • 外部結合は常に、外部結合が発生した順序で評価されます。
  • などなど。
  • SQLite 3.8.0より前のバージョンでは、 最適なクエリプランを見つける際に”最近傍”貪欲アルゴリズムが使われています。

ちょっと待ってください、このアルゴリズムを前に見たことがありますね。実に奇遇ですね。

  • SQLite 3.8.0（2015年にリリース）以降のバージョンでは、最適なクエリプランを見つける際に” N最近傍 “ 貪欲アルゴリズム が使われています。

他のオプティマイザがどのように機能するのか見てみましょう。IBMのDB2は他の全ての企業向けデータベースと同様ですが、私がビッグデータに移行する前に実際に使用していたデータベースなので、これに焦点を絞ってみることにします。

公式ドキュメンテーション によると、DB2オプティマイザでは7つの異なるレベルのオプティマイザが使えます。

  • 貪欲アルゴリズムを結合に使用

    • 0－最小の最適化　インデックススキャンとネスト･ループ結合を使い、クエリリライトを避ける
    • 1－低水準の最適化
    • 2－高水準の最適化

  • ダイナミックプログラミングを結合に使用

    • 3－中程度の最適化と大まかな概算
    • 5－高水準の最適化。ヒューリスティックを用いた全ての技術を使用
    • 7－5と同様の高水準の最適化。ヒューリスティックを用いない
    • 9－最高水準の最適化。 カルテシアン積を含む全ての可能な結合順序を考慮することをいとわない

DB2が貪欲アルゴリズムとダイナミックプログラミングを使用 していることが分かります。もちろん、クエリオプティマイザがデータベースのメインパワーなので、貪欲アルゴリズムとダイナミックプログラミングは使用するヒューリスティックを共有しません。

参考までに言うと、 最適化レベルの初期値は5です。 この初期値が設定されることにより、オプティマイザは次のような特徴を持ちます。

  • 全ての使用可能な統計 （頻出値および変位値の統計を含む）が使われます。
  • 全てのクエリリライトルール （マテリアライズクエリテーブルの経路指定を含む）を適用します。ごく例外的なケースにのみ適用される、計算を多用するルールを除きます。

  • 結合列挙のダイナミックプログラミング が以下のものと使用されます。

    • 複合内部表の限定使用
    • 参照表に関係するスター・スキーマに対するカルテシアン積の限定使用
  • リスト・プリフェッチ（注：この意味は後で分かります）、インデックスのANDing（注：インデックスの特殊な操作です）、およびマテリアライズクエリテーブルの経路指定を含めた広範囲のアクセス方式が考慮されます。

この初期値が設定されていると、 DB2は結合順序のヒューリスティクによって制限されたダイナミックプログラミングを使用します。

他の状態（GROUP BY、DISTINCT等）は単純なルールによって扱うことができます。

クエリプランのキャッシュ

プランの作成には時間がかかるので、ほとんどのデータベースは、同一クエリプランの無用な再計算を避けるために、 クエリプランキャッシュ にプランを保存しています。これは素晴らしいことです。というのも、データベースは無効となったプランの更新タイミングを知る必要があるからです。これには、閾値を設定するという考え方あります。これは、テーブルの統計がこの閾値以上になった場合は、テーブルに関連するクエリプランがキャッシュから削除されるという方法です。

クエリエグゼキュータ

この段階では既に、実行プランの最適化を終えています。プランは実行可能なコードにコンパイルされます。そして、十分なリソース（メモリやCPU）があれば、クエリエグゼキュータによって実行されます。プランの演算子（JOINやSORT BYなど）は順番に、もしくは同時に実行されます。どのように実行するかはエグゼキュータによります。データの取得もしくは書き出しを行うために、クエリエグゼキュータはデータマネージャに働きかけます。これは 次のパート で説明します。