SQLが実行されるまでには,SQLの文法をチェックしたり,実行効率を上げるために書き換える処理など,いくつかの工程があります。また,RDBMSのレコードの検索ではBツリー・インデックスやビットマップ・インデックス,テーブルの結合ではソート・マージ結合やハッシュ結合など,常に最適な方法でデータの検索を実行しています。最近のRDBMSは,SQL文の最適な実行計画を作成して実行するコスト・ベース方式が主流です。
「正しいSQL文を発行しているはずなのに処理にやたらと時間がかかる」という経験をお持ちの方はたくさんいらっしゃると思います。それは,SQL文を書いた人がRDBMSの内部構造を理解していないということが原因である場合がほとんどです。ここでは,RDBMSがSQL文を処理して,プログラマが意図するデータを引き出すまでの過程を追いながら,RDBMSの内部構造に迫っていきます。
効率を見積もって実行計画を立てる
図1に,RDBMSがSQL文を処理する様子を大まかに描いてみました。これはOracleの例ですが,基本的にはどんなRDBMSも同じような順序で動作します。
ユーザーやプログラムからSQL文を受け取ったRDBMSが行う最初の処理は,そのSQL文が文法的に妥当であるかどうかをチェックすることです。この処理を受け持つのが「パーサー」です。パーサーは一般に,文法的なチェックを行うだけではなく,SQL文が指定しているテーブルが実際に存在するかどうか,ユーザーが指定したフィールド(列)名に誤りがないか,ユーザーがテーブルに対してアクセス権限を持っているかどうかといったことも調べます。
パーサーの次は,「クエリー・トランスフォーマ」というプログラムの出番です。ここでは,実行効率を上げるためにSQL文を書き換える処理を行います。例えば,ビューやサブ・クエリーを含んだSQL文を,結合を使って書き換えたりします。
クエリー・トランスフォーマによるSQL文の書き換えがすんだら,SQL文の実行計画,つまりRDBMSが実際に実行する処理を決めます。同じSQL文でも,データベースのインデックスの有無,保持しているデータの偏り,テーブルの結合方法などによって実行効率は大幅に変わってきます。
つまり,SQL文の最適な実行計画は,そのときの環境によって異なるのです。データベースを利用し続ければ,格納されるデータがどんどん変化し,最適な実行計画が変わっていきます。最近のRDBMSは,場面の変化に応じて適切な実行計画を立てる機能を実装しています。
実行計画を立てる際にはまず,クエリー・トランスフォーマが書き換えた結果に対し,「エスティメータ」がデータベースのカタログ情報(ディクショナリ)を参照して,実行時の効率を見積もります。そして,その結果を受けて,よりよい実行計画を「プラン・ジェネレータ」が作成します。プラン・ジェネレータが作成した実行計画はエスティメータに戻して,再び実行効率を見積もります。こうしたやり取りを何度か繰り返すことによって,最適と思われる実行計画を作成するわけです。
インデックスの基本はBツリー・インデックス
実行計画の見積もりについて,もう少し詳しく説明しましょう。見積もりの際には主に,インデックスの使い方とテーブル結合の方式を評価します。インデックスにもテーブル結合にも複数の方式がありますので,ここでは代表的な方式について紹介していきます。
インデックスはテーブル検索を高速化するために作成する“索引”のようなものです。本の巻末にある索引を思い出してください。普通なら,本の中から特定の言葉を含むページを探すには,索引を利用しますね。キーワードで索引を引いて,目的のページを開くのです。
RDBMSのインデックスも同じ役目を果たします。例えば,商品情報を格納したテーブル(syohin)から,商品番号(scode)12番の商品データを引き出すには以下のようなSQL文を実行します。
SELECT * FROM syohin WHERE scode=12;
データベースにインデックスが付けられていない場合は,こうした単純なSELECT文を実行するだけでもテーブル上にあるデータをすべて検索(全表検索)しなければなりません。レコード数が少ないうちはテーブルのデータをすべて検索しても大した問題にはなりません。しかし,レコードが数千,数万の単位になってくると,全表検索にかかる時間を無視できなくなってきます。ここで,商品番号の列にインデックスを作っておけば,インデックスのデータを検索することで,素早く目的のデータにたどり着けるのです。
一口にインデックスといっても,いろいろな方式があります。RDBMSのインデックスとしては最も標準的なのは「Bツリー(BalancedTree)という方式です(図2)。Bツリーは,ノードを文字通りツリー(木)のようにつなぎ合わせた構造になっています。
最上位層にあるノードをルート・ノード,最下位層にあるノードをリーフ・ノード,中間層にあるノードをブランチ・ノードと呼びます。データの数によって,ブランチ・ノードが複数の層を形成することもあります。それぞれのノードには,一定の個数のキーとポインタ(位置情報)が入っており,キーとそのポインタを辿っていくことで,目的のデータにたどり着けるようになっています。
図2で「12」というキーを探すには次のような手順を踏みます。まずルート・ノードにあるキーを調べて,12より大きく,12に最も近い値を探します。この場合,19が該当するので,19のポインタを調べて,ブランチ・ノードに移動します。ブランチ・ノードでも再びキーを調べて,12より大きく,12に最も近い値を探します。ここでは13が該当しますので,13が指し示すポインタを辿り,リーフ・ノードに移行します。リーフ・ノードには12を指し示すポインタがあるので,それを頼りにデータを引き出します。
図2で示した例ではデータの数がそれほど多くないので,Bツリーの効果を実感していただくことは難しいかもしれません。しかし,1から30まであるデータの中から12だけを取り出すのに全表検索をすると,最悪の場合で30個のデータを読まなければなりません。一方,図2のようにBツリーを使えば,3回データを読み出すだけで目的のデータにたどり着けます。
インデックスの効果はデータ量が増えれば増えるほど上がります。1万件あるデータからたった一つのデータを探すのに,全表検索をしたら大変だということはおわかりいただけると思います。