総評
以上、B-treeとハッシュという代表的なパフォーマンスチューニングのアルゴリズムについて見てきました。どちらの技術を採用するかは、業務要件に依存するところが大きいのですが、ここで目安として一般的な結論も述べておきましょう。
- 結論1:とりあえずB-treeインデックスを使って大敗することはない。
B-treeはバランスのとれたオールラウンダーですので、だいたいどんな要件にもそこそこ対応します。安心して使ってください。
一方、ハッシュについての結論は、こうです。
- 結論2:等値条件で性能を追求したいならハッシュを使いなさい。ただし大敗も覚悟しなさい。
ハッシュが効果を発揮するのは、等値条件(=)のときだけです。また、ソート処理の助けにもなりません。したがって、使う局面は非常に限られてきます。PostgreSQLのように、マニュアルに「ハッシュインデックスの使用は推奨しない」とはっきり書いているDBもあるぐらいです[5]。
ハッシュを使うときは、諸刃の剣であることを知ったうえで利用してください。
終わりに
さて、長々とインデックスについての説明を行ってきましたが、最後にちょっとパフォーマンスチューニングの本質的なところについて話しておきたいと思います。それは、「そもそもチューニングは必要なのか」という点です。
これはちょっと酷い問いに聞こえるかもしれませんが、「チューニングは必要か」という問いに対する答えは、「あなた(および顧客)が必要と思えば必要だし、必要と思わなければ必要でない」というものです。たとえ検索に1時間かかるクエリがあろうとも、それで業務に支障がないのであれば、そのクエリをチューニングする必要はありません。一方、1秒しかかからないクエリであっても、顧客が「遅い、これじゃ困る」と言えば、チューニングの必要は生じてきます。平たく言うと、チューニングの要否はSLA(Service Level Agreement )しだいです。
逆に言うと、「このクエリは○分以内のレスポンスを確保できること」という明確な目標を設定しておかないと、チューニングにはキリがありません。そして、..DBエンジニアなら一度は経験があると思いますが..チューニングというのは、やり始めると結構ハマります。1時間かかっていたクエリが自分の力によって1分で返るようになると、うれしくなって、ついつい必要ないほどのオーバーアチーブ(やりすぎ)をしてしまうのです。
でも、0.1秒のレスポンスが0.01秒になったところで、たいていの場合、費用対効果は低いでしょう。その意味で、パフォーマンスチューニングには、一種、麻薬のようなところがあります。「チューニングのためのチューニング」に陥らないよう歯止めをかけるためにも、明確な目標設定を行い、目標を達成した時点で打ち切るのが正しい服用方法です[6]。
では最後に、2つ演習問題を出しましょう。この問いに答えられたら、本稿の理解は十分であると保証しましょう。
演習問題
- 演習1.
多くのDBでは、主キーや一意キー制約を作成すると、対象の列にB-treeインデックスが暗黙に作成されます。これはなぜでしょう。
- 演習2.
もしハッシュ関数が不運にもすべてのキーについて衝突を起こした最悪の場合、検索にかかる計算量はどうなるでしょう。
参考資料
- R.Bayer 『B-tree and UB-tree』
- B-tree とB+tree の考案者Bayer 自ら監修した、ScholarpediaのB-treeについての記事です。発明者本人の説明ですので、正確でわかりやすく、B-treeインデックスについて学びたい人すべてにお勧めです(でも「B」がどういう意味かはやっぱり教えてくれない)。本稿のBayerの言葉はすべて、この記事からの引用です。
- Postgre SQLグローバル開発グループ 『Postgre SQL 8.3.6文書』
- 「第11章 インデックス」には、Postgre SQLに限らず、一般的に当てはまるインデックスについてのコンパクトな解説があり、有用です。