by Hayato Matsuura.

インデックスの結合


「各列を含むインデックスを1つ作るのと、 where句に出てくる全ての列にそれぞれインデックスを作るの、 どっちがいいの?」というのは、インデックス作成に関する一番よくある 質問でしょう。その答えは非常に簡単で、多くの場合は、複数の列を含む 1つのインデックスの方がよいでしょう。そのような インデックスを、連結あるいは複合インデックスといいます。 詳しくは複合インデックスで説明しています。

とは言え、どうインデックスを作ったとしても1つのインデックスでは 完璧な動きにできないクエリもあります。例えば以下の例のように、 2つ以上の範囲条件を含むクエリがそうです。

SELECT first_name, last_name, date_of_birth 
  FROM employees
 WHERE UPPER(last_name) < ? 
   AND date_of_birth    < ?

フィルタ述語なしにBツリーインデックスでこのようなクエリを サポートすることはできません。これを考えるには、 インデックスは連結リストであることを 思い出す必要があります。

インデックスをUPPER(LAST_NAME), DATE_OF_BIRTHの順で定義した時、リストはAから始まり Zで終わります。誕生日は、同名の従業員が2人いる時にだけ考慮されます。 インデックスを逆の順序で定義した場合は、リストは最も年上の従業員で 始まり、最も若い従業員で終わります。この時、従業員の名前は、 並べ替えの順序に大きな影響を与えません。

いくらインデックスの定義をいじっても、エントリは常に鎖のように つながりになります。一端には小さな値が、反対側には大きな値が来ます。 そのため、インデックスはアクセス述語としては1つの範囲条件しかサポート できないのです。2つの独立した範囲条件をサポートするには、チェスの 盤のように、2つ目の軸が必要になります。上で挙げたようなクエリは チェス盤の角から全てのエントリを検索できます。しかしインデックスは チェス盤ではなく鎖のようになっており、角はありません。

フィルタ述語を使うことはできますので、結局はマルチカラム インデックスと組み合わせて使うことになります。多くの場合は、それが 最適解になります。選択性のより高い列をインデックス定義の最初に置くことで、 アクセス述語に使うことができます。 これが、「最も選択性の高い列を最初に」と いう都市伝説の根拠です。ただし、これはフィルタ述語を使わざるを得ない 時にのみ当てはまる法則です。

もう1つの方法として、別々の列に対して作成したインデックスを 2つ使う手もあります。この場合は、データベースはまずそれぞれの インデックスをスキャンし、その結果をまとめなくてはなりません。複数の インデックスを使うのは、それぞれのインデックスツリーをたどらなくては ならないことから、それだけでそれなりの負荷が要求されます。 さらに加えて、データベースは中間結果をまとめるのに多くのメモリとCPU リソースを消費する必要があるのです。

注記

インデックスは、2つ使うより1つだけ使う方が高速。

データベースは、インデックスをまとめるのに2つの 方法を使います。最初は、インデックスの結合演算です。第4章「結合処理で、関連するアルゴリズムに ついて説明しています。2つ目は、データウェアハウスの機能を活用した アプローチです。

データウェアハウス は、アドホックなクエリを実行する環境のルーツであるとも言えます。 任意の条件をクリックで選んでいき、それをクエリとして実行する必要が あります。where句に現れる列の組み合わせを 事前に予想することが難しいので、ここまで述べてきたように、その 状況では、インデックスをうまく使うのはほぼ無理ということになります。

データウェアハウスでは、この問題を解決するために特別な インデックスタイプを使います。それが、いわゆるビットマップインデックスです。 ビットマップインデックスが有利なのは、比較的簡単に結果をまとめることが できる点です。つまり、各列にそれぞれインデックスを作成した時に それなりのパフォーマンスが得られるということです。逆に言えば、 クエリが事前に分かっていて、マルチカラムなBツリーインデックスを作って おいた方が、複数のビットマップインデックスをまとめるよりも 高速だということです。

一方で、ビットマップインデックスの飛び抜けた弱点は、 insertupdatedeleteのスケーラビリティがとんでもなく悪いという ことです。同時書き込みは実質的に不可能です。これは、データのロードの 処理が順番にスケジュールされることの多いデータウェアハウスにおいては 特に問題にはなりません。しかしオンラインアプリケーションでは、ビット マップインデックスはほぼ使い物にならないと言えます。

重要

ビットマップインデックスは、オンライン トランザクション処理(OLTP)では使い物になりません。

多くのデータベース製品では、Bツリーとビットマップインデックスの ハイブリッドな仕組みが提供されています。適当なアクセスパスがない時は、 Bツリーのスキャンの結果を、メモリ上のビットマップ構造に変換します。 この変換は、効率的にできます。ビットマップ構造は永続化して保存される ことはなく、SQL文の実行後に破棄されるので、書き込みのスケーラビリティが ないことによる問題を回避できます。この方法のマイナス面としては、 メモリとCPUが大量に必要になることです。結局のところこの方法は、 オプティマイザがやけくそになった時の最終手段です。

著者について

Markus Winandの写真

Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。

“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | 接触 | 無保証 | 商標 | Privacy | CC-BY-NC-ND 3.0 license