インデックスの結合

「各列を含むインデックスを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つの方法を使います。最初は、インデックスの結合演算です。第4章4, 「結合処理」で、関連するアルゴリズムに ついて説明しています。2つ目は、データウェアハウスの機能を活用したアプローチです。

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

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

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

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