このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

実行エンジン

  • 実行エンジンはSQLを実際に処理するための部品である。

実行エンジン内での実際の動作の確認方法

  • DB2,PostgreSQL,MySQLの場合
    • EXPLAIN文
  • Oracleの場合
    • Explain Plan文
  • SQL Serverの場合
    • クエリアナライザ(GUI)

実行エンジンの機能モジュールインタフェース

Open

  • タプル(あるいは中間結果)を取り出す準備をする。
  • 実際にデータを読み込む必要はないが、他の機能モジュールを呼び出したりする必要がある場合は、この機能モジュールにもOpenを発行する。
  • Openの処理で必要になる引数は、機能モジュールによって異なる。

GetNext

  • 機能モジュールの結果を1タプル分だけ渡す。
  • この機能モジュールを使用する側は、データがなくなるまで(あるいは不要になるまで)繰り返しGetNextを使ってタプルや中間結果を読み込むことになる。

Close

  • 機能モジュールを終了させる。

代表的な機能モジュールの種類

テーブルスキャン

  • テーブルスキャンは最も基本的な機能モジュールである。
  • あるリレーションを全部読み込む機能を持つ。
    • これはリレーション同士の和や結合を作る際に必要になる。
  • タプルを読み込む順番に決まりはなく、ディスクなどに格納されている順であることが多いので、GetNext()で読み込まれるタプルの順序は一般的に保証されていないことに注意する。

例:

SELECT * FROM table;

 このような単純なSQLの場合は、テーブルスキャンだけが用いられることが多い。 ◇

ソートスキャン

  • テーブルを読み込む際に、特定のカラム(複数のこともある)の値にしたがってタプルをソートし、その順番にGetNext()でカラムを渡す処理である。
  • テーブルスキャンの際に同時にデータを並び替えたほうがよい場合が多い。
    • 例えば、ORDER BYが含まれるようなSQL文を処理するには、ORDER BYで指定されたカラムでタプルをソートする必要がある。
      • タプルをソートしておくと、その後の結合演算で効率のよい方式を利用できることがある。
    • また、GROUP BYのような集約演算を行うときも対象となるカラムでデータをソートしておいたほうがよい場合がある。

ネストループ結合

  • これは結合演算の最も基本的なものである。
    • どのような場合でも適用できる反面、高い性能を得るのは難しい。
  • ネスとループ結合では、それぞれのテーブルのカラムを1つずつ比較して総当りで調べていく。

例:2つのテーブルR(X,Y)、S(Y,Z)があり、この2つのテーブルを結合したいとする。

 どの順番に絡むが読み込まれてくるのかはわからないため、正直に1つずつ調べていくしかない。これは、2つのテーブルそれぞれについて繰り返すことになる。つまり、繰り返し回数は2つのテーブルのカラムの数の積になる。

 Rが100万タプル、Sが1000タプル持つとすると、この結合による比較回数は10億回となる。 ◇

  • 両方のテーブルがどちらも同時にメモリに格納できれば、ディスクのデータの読み込みは1回で済む。
    • そして、どちらか一方のテーブルでもメモリに格納できれば、それだけでもかなり処理は楽になる。

ソートマージ結合

  • ソートマージ結合では結合させるカラムの値の順にタプルを並べておけば、その後は2つのテーブルをマージさせるだけで結合できる。
  • ネストループ結合とソートマージ結合のどちらが高速であるかは場合による。
  • ソートマージ結合ではソート後に結合するのではなく、ソートサブリストを作成した後で、ソートを完了せずに結合することもできる。
    • こうすると、ソートを完全に実行した後でマージしながら結合するよりも効率が上がる。

インデックスを使った結合(2つのテーブルのそれぞれの結合カラムにインデックスがある場合)

  • テーブル中のタプルの配置はばらばらだが、インデックスはソートされているので、それぞれのインデックスをソートマージ結合と同じように調べていけば、それぞれのテーブルを1回スキャンするだけで結合を作ることができる。
    • つまり、インデックスがない場合に比べてかなり速いことが想像できる。
    • 結合処理が多用される場合には、それぞれのテーブルの結合カラムにインデックスを作っておくとよい理由はここにある。

ハッシュ関数を使う方法

  • ハッシュ関数を使うと、インデックスやソートよりもかなり効率よくデータを分類できる。
  • このような構造をインデックスとして使うこともできる(ハッシュインデックス)。
  • ハッシュのバケット数を固定せずに、データが増えるにしたがってバケットを増やせる方法もある。
  • これを使って結合演算だけでなく、SQLのDISTINCT句に相当する重複除去の演算を行うこともできる。

参考文献

  • 『RDBMS解剖学』