『RDBMS解剖学』の第六章

rdbms-6.md

六章 物理プランの生成

1. この章のテーマ

物理プランの生成および最適化がテーマ。

物理プラン:

• 「SQLを解釈実行するパーツ」=> 「プランナ」=> 「物理プラン」
  • 論理プランの次のフェーズに位置する
• 実行エンジン(五章)に搭載されているさまざまな機能モジュールをどのような順序で実行するかを記述したもの
  • 記述方法はデータベースごとに異なる

2. 物理プラン生成の位置付け

五章までのおさらい (「SQLを解釈実行するパーツ」の流れ):

1. [SQL構文解析] 入力: SQL文 => 構文解析およびバリデーションを行う => 出力:構文ツリー
2. [論理プランナ] 入力: 構文ツリー => 関係代数の演算群に変換 => 出力: 論理プラン
3. [物理プランナ] 入力: 論理プラン => 実行エンジンの各機能モジュールの実行順序を決定 => 出力: 物理プラン
4. [実行エンジン] 入力: 物理プラン => プランに従い各機能モジュールを実行 => 出力: SQL文に対応する結果データ

物理プランナは「オプティマイザ」とも呼ばれる。

• 論理プランを実行するために最適と思われる手順を推定/決定するのが物理プランナの役目

LIST6-1: PostgreSQLのEXPLAIN文(物理プラン)の例

3. 物理プランの最適化とは

図6-3の従業員テーブルと部署テーブルを用いた例

入力SQL:

SELECT 従業員名,部署名 FROM 従業員テーブル,部署テーブル
WHERE 従業員テーブル.部署番号 = 部署テーブル.部署番号
AND 性別 = '男'

SQLに対応する論理プラン:

1. 従業員テーブルで、性別が「男」のもののみを残す
2. 上の結果と部署テーブルとの直積を求め部署番号同士が等しいものだけを残す
3. 結果から、従業員名と部署名のみを選んで出力する

論理プランから生成され得る物理プラン:

• 図6.5
  • 今回の例では、単一の論理プランから六通りの異なる物理プランが生成し得る
  • 実際にどのような機能モジュールが使用可能かはデータベースによって異なる
• 論理プランの各フェーズで、異なる機能モジュールが選択可能なため
  • 1. 性別が男の従業員を抽出:
    • 機能モジュール:「インデックススキャン」or「テーブルスキャン」
  • 2. 二つのテーブル内の部署番号が等しいレコードのみを抽出:
    • 機能モジュール:「ネストループ結合」or「ソートマージ結合」or「ハッシュ結合」
  • 3. 「従業員名」および「部署名」フィールドだけ出力する
    • 機能モジュール: 「フィルタ」

物理プランナは、このような候補の中から最適と思われるプラン(論理プランの実行方法)を選択しなければならない。

最適なプランとは？

• 実行に要する処理時間が一番短いと思われるもの
• 実際に実行することなく、処理時間が一番短いものを確実に選択することは不可能
  • データファイルのフラグメンテーションやCPUおよびディスクI/Oの負荷状況は予測が難しい
    • 実際に実行したとしても、必ずしも再現性がない
  • 対象のテーブルやSQL文が同じ場合でも、格納されているデータの内容によって処理時間は変わり得る
    • ex: レコード数が数件なら「テーブルスキャン」が、数百万件なら「インデックススキャン」が適切
    • スキーマなどの静的な情報だけでは確実な予測は難しい
• 予測のための指標を決めて、より優れた近似解を算出できるようにすることが重要
  • 物理プランの決定処理が重すぎても本末転倒 (ex. 複雑なSQL文の場合など)
  • PostgreSQLでの例：https://www.postgresql.jp/document/9.2/html/geqo.html
    • 基本はコストベースの全探索だが、結合処理が多いと組み合わせ爆発が起こる
    • 遺伝的アルゴリズムを使って近似解を求める方法を導入

最適な物理プランの生成は、データベースシステムにとって非常に重要な課題。

4. 物理プランの最適化方式

「ルールベース方式」と「コストベース方式」が有名。

ルールベース方式

比較的古くから使われている方法。

前もって用意しておいた優先度付きのルール表を使って、採用する機能モジュールを選択していく。

表6-1: Oracle(9i以前)でのルール定義の例

• 例. 優先度9のルールにより、カラムにインデックスが存在する場合は、常に「インデックススキャン」が採用される

データの内容(テーブルの容量やカラム値の部分、etc)に依存せず、スキーマとSQL文が同じなら常に同じ物理プランが生成される。

きめ細かい最適化は困難。

コストベース方式

「コスト」とは:

• 物理プランを実行する上で必要となるリソース(ex. CPU, DiskI/O)の使用量を定量化したもの
• データベースシステムのカタログ内に格納されている各種統計情報から算出する

コストベース方式では、このコストが最も小さくなるプランを選択する。

例えば、カラムにインデックスが存在する場合でも、コストがより小さいなら「データスキャン」が選択されることもある。 (レコード数がごく少数の場合など)

最近のデータベースシステムでは、プランナにコストベース方式を採用していることが多い

• 一般的にはコストベース方式の方が、ルールベース方式より最適な物理プランを生成できるため

5. コストベース方式の例

コストベース方式の一般的な考え方を 表6-2 の従業員テーブルを使って説明。

SQL:

SELECT 従業員名 FROM 従業員テーブル
WHERE 出身地 = '北海道'

インデックスが存在しない場合

出身地カラムにインデックスが存在しない場合は、常に「テーブルスキャン」

インデックスが存在する場合

「テーブルスキャン」or「インデックススキャン」のどちらを選択すれば良いか？

判断条件:

• 「北海道」が、出身地カラム全体のどの程度の割合を占めているか
• 「どの程度含まれているかという割合」 == セレクティビティ(selectivity)
  • selectivityが小さい 1. 対象レコード数が少ない 2. インデックススキャンを採用
  • selectivityが大きい 1. 対象レコード数が多い 2. インデックス探索のオーバヘッド(コスト)が大きくなる 3. テーブルスキャンを採用

selectivityの算出方法は?

• (今回のケースでは)対象となる値の全体に占める割合が分かれば良い
• ただ、値域が狭い場合を除いて、全部の値の出現件数を保存しておくのは現実的ではない
• (例えば)「値の種類数」,「平均値」,「中央値」といった統計値を保持しておき、そこから算出するというのが現実的
  • あくまで推定値

今回の例では「北海道」を持つレコードは一つしかないため「インデックススキャン」が選択される。

条件が「東京」の場合

• 15件中8件も存在する
• selectivityが非常に大きい
• インデックスが存在するとしても「テーブルスキャン」が優先される

条件値が与えられなかった場合

物理プランの作成までを事前に行っておき、実際に実行する際に条件値を与えるケース。 ストアドプロシージャ内などでよく使用される。

SELECT 従業員名 FROM 従業員テーブル
WHERE 出身地 = ?

「インデックススキャン」と「テーブルスキャン」のどちらがより望ましいかは、物理プラン作成の時点では不明。

• コストベース方式の場合でも最適解が出せるとは限らないことを示す一例
• 物理プランナの最適化は難しい

6. まとめ

• 物理プランの最適化方式について解説した
• 結合演算は取り上げていないけど、さらに複雑
• コストベース方式は標準化・規格化されているものではないので、データベースシステムによって実態はかなり異なる