• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版
  • PR

  • PR

  • PR

  • PR

  • PR

特集:基礎から理解するデータベースのしくみ

基礎から理解するデータベースのしくみ(4)

SQL文はどのように実行されるのか(3)

2006/01/20 日経ソフトウエア
出典:日経ソフトウエア 2002年1月号56ページより
(記事は執筆時の情報に基づいており、現在では異なる場合があります)
目次一覧
表2●リスト1~3で利用したテーブルcustomersの内容
表2●リスト1~3で利用したテーブルcustomersの内容
[画像のクリックで拡大表示]
リスト1 ●「!=」で比較した場合の実行計画。オプティマイザは全表走査を選択しています
リスト1 ●「!=」で比較した場合の実行計画。オプティマイザは全表走査を選択しています
[画像のクリックで拡大表示]
リスト2 ●条件をIN 演算子で書き換えた場合の実行計画。オプティマイザは,やはり全表走査を選
リスト2 ●条件をIN 演算子で書き換えた場合の実行計画。オプティマイザは,やはり全表走査を選
[画像のクリックで拡大表示]
リスト3 ●ヒント句(赤枠内)を指定した例。オプティマイザはインデックスでアクセスしています
リスト3 ●ヒント句(赤枠内)を指定した例。オプティマイザはインデックスでアクセスしています
[画像のクリックで拡大表示]
図4●ネスト・ループ結合アルゴリズム。テーブルAの各レコードについてテーブルBのすべてのレコードと比較します
図4●ネスト・ループ結合アルゴリズム。テーブルAの各レコードについてテーブルBのすべてのレコードと比較します
[画像のクリックで拡大表示]
図5●マージ結合アルゴリズム。あらかじめソートした二つのテーブルのそれぞれについてポインタを進めながら比較します
図5●マージ結合アルゴリズム。あらかじめソートした二つのテーブルのそれぞれについてポインタを進めながら比較します
[画像のクリックで拡大表示]
図6●ハッシュ結合アルゴリズム。テーブルBに対してハッシュ・テーブルを作成し,それを利用してテーブルAの各レコードについて検索を実行します
図6●ハッシュ結合アルゴリズム。テーブルBに対してハッシュ・テーブルを作成し,それを利用してテーブルAの各レコードについて検索を実行します
[画像のクリックで拡大表示]

データベースの統計情報は定期的に更新する

 基本的には,ほとんどの場合にコスト・ベース・アプローチに基づくオプティマイザは最適な実行計画を選択してくれると考えてさほど問題はありません。ただ,コスト・ベースの基になるコストの計算は,テーブルのフィールドの値が均等に分布していると仮定して行います。そのため,データの分布に極端な偏りがある場合などは,実際には全件走査のほうが処理は早く終わるのに,インデックス検索を選択してしまうような場合もあり得ます。

 コスト・ベース・アプローチを使って効率の良い実行計画を立てるには,定期的に統計情報を更新することが重要なポイントとなります。統計情報は,あくまでもそれを作成したときのデータベースの状態を反映しています。したがって,統計情報を作成した後にデータを大量に追加したり,更新したりするとデータベースの正確な内容を反映していないものになってしまいます。

 適切なインデックスを定義しても,統計情報が不正確では,オプティマイザは最適な実行計画を選択してくれません。例えば,実際はレコードが100万件あったとしても,レコード件数100件の時点で統計情報の作成/更新を行ったままだと,オプティマイザはレコード件数が100件であることを前提に実行計画を決定してします。つまり,本来ならインデックスを使ってアクセスしたほうが高速なのに全表走査を選択し,100万件のレコードを順にアクセスしてしまう,といったことになるわけです。Oracleの場合であれば,ANALYZEコマンドやDBMS_STATSパッケージなどを使って定期的に統計情報を更新することを心がけてください。

ヒント句を指定して実行計画を立てさせる

 次に,SQL文の記述のしかたによって,コスト・ベース・アプローチで作成する実行計画がどう変わるかを例で見てみましょう。ここでは,(表2[拡大表示])のようなテーブルに対して,リスト1~3のような3種類のSQL文を発行してみます。いずれも,フィールドstatusの値がvalidでないレコードを抽出する処理です。

 (リスト1[拡大表示])では,「status != 'valid'」でデータを選択しています。statusにはインデックスを作成してありますが,リスト1の下の実行計画を見るとオプティマイザが全表走査(FULL)を選択していることがわかります。「!=」を使う場合にオプティマイザはインデックスを利用するアクセス・パスを選択しないからです。

 (リスト2[拡大表示])では,インデックスを使うアクセス・パスを選ぶようにするために「status != 'valid'」を「status in ('canceled','overdue')」に置き換えてみました。このSQL文は,

(1)status = 'canceled'のレコードをインデックスを使って取得
(2)status = 'overdue'のレコードをインデックスを使って取得
(3)(1),(2)の結果を連結する

という手順を踏むことによって,インデックスを利用してアクセスすることを意図したものです。しかし実際には,リスト2の下の実行計画を見ると,リスト1と同じ全表走査が選択されていることがわかります。これはどうしたわけなのでしょうか。

 表2に示すように,statusフィールドは,valid,canceled,overdueの三つの値しかとりません。これらの値が平均して分布しているとすると,(1),(2)の処理はそれぞれ1/3ずつのレコードを取り出すことになります。条件によって検索候補をあまり絞り込めない場合は,インデックスによる検索よりも全表走査のほうが高速になります。そう考えると,オプティマイザが全表走査を選択したことにも一応納得がいきます。

 ただ,今回の場合はデータの分布に偏りがあり,canceledとoverdueの値をとるレコードがごくわずかしかありません。そのため,実際にはインデックスによる検索の方が高速に実行できます。こうした事態に対処するため,多くのRDBMSでは,ユーザーがオプティマイザに対してどのような実行計画を作るかを明示的に指示するための機能を提供しています。それがヒント句です。

 ヒント句は,オプティマイザによるアクセス・パスの選択をユーザーが制御するために,SQL文の中に埋め込む指示のことです。インデックスを使うようにヒント句を与えて実行計画を立てさせたのが(リスト3[拡大表示])です。ヒント句は,「/*+」と「*/」で囲んで指定しています。リスト3の下の実行計画を見てください。リスト2のときに説明した(1)~(3)の手順でインデックスを利用してアクセスしていることを確認できるでしょう。ヒント句は,オプティマイザに対してインデックスの使用を明示的に指示する場合だけでなく,アプローチの種類,アクセス・パス,結合順序などを指定するときにも利用できます。

結合アルゴリズムを使い分ける

 ここまで述べてきたことからおわかりのように,オプティマイザによる最適化は万能ではありません。データの分布が偏っていたり統計情報が不正確だったり,といったさまざまな原因で,最適でないアクセス・パスを選択してしまい,期待通りのパフォーマンスが出ないこともあります。

 こうしたことによるパフォーマンスの低下を防ぐには,明示的にヒントをつけるなどプログラマがSQL文の書き方を工夫する必要があります。以下では,そうした点の中から,特に速度に影響が出やすいものを取り上げましょう。

 まずは,テーブルを結合(JOIN)するアルゴリズムについてです。SQL文の処理には,大きく分けて,選択,射影,結合の3種類がありますが,最も負荷が大きいのがこの結合処理です。結合処理の最適化の優劣が,SQL文の高速化のカギを握っている,といっても過言ではありません。

 RDBMSがテーブルを結合する際に利用するアルゴリズムには,「ネスト・ループ結合」「マージ結合」「ハッシュ結合」の三つがあげられます。

●ネスト・ループ結合

 ネスト・ループ結合は,単純に二重ループを回してテーブルを結合する方法です。例えば,AとBの二つのテーブルがあった場合,Aの各レコードごとにBの全レコードとの比較して,フィールドの値が一致するものを探します(図4[拡大表示])。そのため,コストは二つのテーブルのレコード数の積に比例します。Bにインデックスが定義されている場合は,Bのレコードの検索にインデックスを利用することも可能です。一般には,インデックスが設定されていない小さなテーブルと,インデックスが設定されている大きなテーブルの二つを結合する場合に効果的です。

●マージ結合

 マージ結合は,ネスト・ループ結合の改良版と言える方法です。まず,二つのテーブルを,結合するフィールドについてあらかじめソートしておきます。そして,両方のテーブルのレコードに対して持たせたポインタを,レコードの上から下へと順に走査させながらフィールドの値が一致するものを探します(図5[拡大表示])。レコードの走査が1回で済むのが特徴です。

 例えば図5では,まずA,Bのポインタの両方を先頭のレコードにおき,Aの2とBの1を比較します。Bのレコードはソート済みなので,もしBに値2を持つレコードがあるなら,下方にあるはずです。そこでBのポインタを一つ下へ移動すると,2が見つかります。

 さらにBのポインタをもう一つ下に移動して,値3のレコードを取得します。仮にAに値3のレコードがあるなら,それは下方にあるはずなのでAのポインタを一つ下に移動してレコードの値を取り出します。この値は4と,3よりも大きくなってしまったので,今度はBのポインタを一つ下げて値4のレコードを取り出します。このように,「自分が相手よりも値が大きくなったら,相手のポインタを一つ進める」ことを繰り返していけば,最終的に条件に見合うレコードを取り出すことができます。

 マージ結合では,テーブルがソート済みでない場合,ソートに要するコストも考えなくてはなりません。しかしそれでも一般的には,ネスト・ループより低コストになります。ソートは,レコードそのものをソートするほかに,インデックスをソートする方法もあります。

●ハッシュ結合

 これもネスト・ループ結合の改良版と言うべきものです。ネスト・ループ結合では,テーブルAの各レコードについて,テーブルBを全件走査しています。この検索処理の部分にハッシュ法を使うことで高速化を図るのがハッシュ結合です(図6[拡大表示])。

 まず,結合するフィールドの値をキーとして,テーブルBに対するハッシュ・テーブルを作ります。あとはテーブルAのレコードごとにフィールドの値が一致するものをハッシュ・テーブルから検索すれば,テーブルの結合が完成します。元のテーブルのサイズが大きいと作成したハッシュ・テーブルがメモリーに収まらないため,一般にはあらかじめテーブルをいくつかのパーティションに分割してから,パーティションごとにハッシュ結合を行います。

 これらの三つのアルゴリズムは,一般的に言って,ネスト・ループ結合<マージ結合<ハッシュ結合の順で高速になります(ハッシュ結合が最速)。ただし,二つのテーブルのレコードの数が極端に違う場合や,両方のレコードの数が十分小さいときには,必ずしもこの順番にならないこともあります。加えて,応答時間が重要なとき,すなわち「処理がすべて終了するまでの時間を短くするより,とにかく最初に検索条件に合致した1レコードを早く返したい」というような場合には,ネスト・ループが向いています。

 テーブルの内容や処理の目的などに応じて最適なアルゴリズムは変わります。ヒントを使って結合アルゴリズムを明示的に指定するなどして,状況に応じて使い分けるようにしてください。例えばOracleでは,USE_NL,USE_MERGE,USE_HASHの各ヒント句を使って,ネスト・ループ結合,マージ結合,ハッシュ結合を使用するように指定できます。SQL Serverの場合は,LOOP,MERGE,HASHの各ヒントを利用すればいいでしょう。


布目 綾子

あなたにお薦め

連載新着

連載目次を見る

今のおすすめ記事

  • 【クラウド女子】

    2年で“クラウド部長”になったNTTデータ女性社員

     ぶちょー(部長)――。NTTデータの安東沙織さんは、周囲から親しみを込めてこう呼ばれる。といっても、会社での肩書きではない。部長とは、米マイクロソフトのパブリッククラウドサービスAzureのユーザーコミュニティーJapan Azure User Group(JAZUG)女子部での役職だ。

ITpro SPECIALPR

What’s New!

経営

アプリケーション/DB/ミドルウエア

クラウド

運用管理

設計/開発

サーバー/ストレージ

クライアント/OA機器

ネットワーク/通信サービス

セキュリティ

もっと見る