日別アーカイブ: 2015/01/11

「オプティマイザ統計の保留」の検証（序章①）

オプティマイザの正体

「HOW型」「WHAT型」コンピュータとは？

コンピュータを大きく分類すると「HOW型」と「WHAT型」という２つのタイプに分けることができるという説があります。

これは私が勝手に言っていることではなく１９８０年代にTRONを提唱した東大・坂村健教授の言葉です。（新版 TRONで変わるコンピュータ P.44〜、TRONプロジェクト Wikipedia）

「HOW型」というのは、現在使われているコンピュータつまりノイマン型コンピュータと呼ばれるコンピュータのことで、コンピュータがどのように振る舞うかを人間がプログラムという形で指示するものです。コンピュータが行う複雑な処理の一つ一つを厳密に定義しなければならないためプログラムを作るのは大変ですが、いったんプログラムができてしまえばコンピュータはそれを忠実に実行するだけというものです。

コンピュータ制御された車を考えると、「次の角を左に曲がれ。」とか「国道１号線を東京方面に進め。」等の指示を次々に与えながら目的地に誘導していくのが「HOW（どうやってやる）型」です。

一方「WHAT型」というのは１９８０年代当時研究されていた第五世代コンピュータとか、人工知能専用コンピュータに該当するもので、コンピュータ・カーの例で言うと「道路の左側を車線に沿って走れ。」とか「赤信号では止まること。」のように基本的なルール（専門的には知識ベース）だけを先に教えておいて、「何処何処へ行け！」という指示だけで目的地に向かわせるのが「WHAT（何をする）型」です。

第五世代コンピュータは当時最高の頭脳を結集させたプロジェクトだったようですが、結局は成果を出すことができずに終了してしまいました。まだコンピュータのパワーが非力だったということが最大の原因だったと思いますが、とりあえずムチャクチャに動いて（プログラムなしでコンピュータを動かすのは大変な事）最終的に結果を出せば良いというアプローチにやはり無理があったようです。

オプティマイザは「HOW型」でもあり「WHAT型」でもある

オプティマイザはリレーショナル・データベースの中で最も重要な機能と言っても過言ではありません。正しい結果をより早く返すためのアプローチを最適化する（optimize）機能・プログラムがオプティマイザ（optimizer）です。

それは当然「HOW型」コンピュータの上で動くプログラムですが、「WHAT型」しての性格も色濃く持っています。それはSQL（Structured Query Language）がまさに「（求める）結果＝WHAT」の構造を記述するものだからです。

これはカーナビで経路検索をすることに似ています。例えば「日本橋から横浜ランドマークタワー」まで車で行きたい場合、Google Mapで検索すると

  1. 首都高速1号羽田線 と 首都高速神奈川1号横羽線 経由：35.1km、46分（31分）
  2. 首都高速3号渋谷線 と 第三京浜道路 経由：41.8km、49分（41分）
  3. 第二京浜/国道1号線 経由：35.2km、1時間8分（50分）

という結果が返ってきました。

GoogleMapの例（イメージと記事の内容は異なります。）

この２点間を結ぶ道は無数にあります（遠回りして新宿駅経由のルートでも目的地には着くことができます）が

  1. どんなにお金がかかっても最短時間で着くことができるルート
  2. 有料道路でも若干安いルート
  3. 有料道路を使わないルート

というような基準でそれぞれのルートを算出し（文字通り計算で求め）たのが上の結果です。ちなみにこれらは渋滞情報も加味されていて（カッコ）内は渋滞なしの場合の所要時間です。（これは実に興味深いことなので次回で取り上げます。）

カーナビで検索されたルートに該当するのが「アクセスパス」です。オプティマイザが最終的に１つに決定したアクセスパスに従って、実際のデータにアクセスされ、加工され、結果が返されます。

言い換えると、オプティマイザの役割は最適なアクセスパスを算出するところまでで、実際の物理的なI/Oやメモリ間操作などはオプティマイザの関知するところではありません。運転前にルートを検索することと実際にそのルートに従って車を運転することが違うことに相当します。

オプティマイザの計算量は膨大

オプティマイザは前述のように、決められたアルゴリズムに従って最適解を得ると言った面では「HOW型」と言えますが、ユーザの求める結果を実現するための「アクセスパス」を最終的に１つに決定するということでは「WHAT型」です。

２点間を結ぶルート検索であれば選択すべき経路はそれほど多くないのですが、複数のテーブルから求める結果を得るということは想像以上に大変なことです。

A、Bという２つのテーブルを結合して結果を得る場合、最初にAテーブルにアクセスしてその結果を基にBテーブルにアクセスすることを「A→B」と表現すると、A→BとB→Aという２通りのアクセスパスが存在します。

さらにA、B、Cの３つのテーブルでは、A→B、A→C、B→A、B→C、C→A、C→Bの６通りになります。（結合は原則的に２つのテーブルあるいは結果セット同士になります。）

テーブル数が増えるごとにアクセスパスは多くなり、簡単に説明すると（テーブル数）！：テーブル数の階乗となります。つまり１０個のテーブルを結合するSQL文の場合は実に 3,628,800通りとなってしまいます。この中から最適なものを１つだけ選択しなければならないのでオプティマイザの計算量は膨大なものとなってしまいます。

実は、Oracleのオプティマイザは300万通り以上の組み合わせを律儀に評価するようなことはしません。「OPTIMIZER_MAX_PERMUTATIONS」というOracle8から導入された初期化パラメータによって評価する組み合わせの上限値が決められています。（これは解析時間を短縮するための苦肉の策と思われます。）

Oracle8と8iではこの値は「80,000」でしたが、9i以降では「2,000」となり、さらに10g以降では隠しパラメータ「_optimizer_max_permutations」となったため基本的に変更しないパラメータとなってしまいました。

SQL> select
  2   a.ksppinm  "Parameter"
  3  ,b.ksppstvl "Value"
  4  from
  5   x$ksppi  a
  6  ,x$ksppcv b
  7  where a.indx    = b.indx
  8  and   a.ksppinm like '%optimizer_max_permutations%';

Parameter                      Value
------------------------------ ----------
_optimizer_max_permutations    2000

７個以上のテーブルを結合するとアクセスパス算出が不十分になる？

「OPTIMIZER_MAX_PERMUTATIONS（または _OPTIMIZER_MAX_PERMUTATIONS）」パラメータが2,000であることの意味を考えてみましょう。

前述のとおり複数テーブルを結合する組み合わせの数は「（テーブル数）！」となります。テーブル数６の場合6!=720、７の場合7!=5,040であるので、７つ以上のテーブルを結合する場合、すべての組み合わせを評価して真に最適なアクセスパスを算出する前に、オプティマイザが評価を諦めてしまう可能性があります。

以前、ある企業のコンサルティングを行った際「テーブルの結合は５つまでとする。」というルールを定めているのを目にしたことがあります。
これは恐らく本パラメータを意識したルールでなかなか興味深い考え方だなと記憶しているのですが、原則的には間違った発想だと思います。

一般的に５つのテーブルを結合するような複雑なクエリーを書くことは珍しいかもしれませんが

.....
from
 emp  e1
,emp  e2
,emp  e3
,dept d
.....

のように、FROM句の後に同じテーブルを複数記述するようなことは簡単にできてしまうので、５つという制限は意味のない足かせになるかもしれませんし、そもそも結合を減らすためにせっかく正規化したテーブルを非正規化するようなことは本末転倒です。

それではもし、正規化された７つ以上のテーブルをどうしても結合しなければならない場合はどうしたらよいでしょうか？

  • LEADINGヒントやORDEREDヒントにより、FROM句の後に記述された順にテーブルが結合されるようオプティマイザに情報を与える。
    • デメリット：テーブル順を間違えると悪い結果をもたらす。統計情報が変動した場合どうする？
  • PL/SQLでカーソルを定義し（例えば４テーブルのSELECT文）、カーソル・ループの中で残りのテーブルを参照する。
    • デメリット：想像のとおりプログラムが複雑になり、手間の割には成果が少ないかもしれない。
  • 一時的に_OPTIMIZER_MAX_PERMUTATIONSパラメータの値を変更する。
    • デメリット：解析済みSQLがキャッシュアウトされる度にパラメータが変更できるか？実行計画を固定化する高度なスキルが必要。

いろいろ考えられるのですが、一長一短ありでなかなか単純ではありません。（あえて言えば３番目が一番スマートでしょう。）

次回へ

「オプティマイザ統計の保留」というあまり注目されていない機能を取り上げ（検証し）ようとしているのですが、オプティマイザについて語ると脱線してしまってなかなかたどり着けません。

次回「序章②」として、オプティマイザを理解する上で前提として押さえておきたいことを説明し、次々回で検証に入りたいと思います。