遅いインデックス パートI


ここまで書いたように、木の走査が効率がよいことは分かりましたが、 それでもインデックスによる検索が期待するほど高速でないケースがまだ 存在します。この矛盾が、長らく「劣化したインデックス」 という迷信が広まる原因になってきました。この考え方は、インデックスの 再構築が、奇跡の解決策だという意識を広めてしまいました。 Appendix Bで、これについてとその他の 都市伝説について、取り上げます。差し当たり、インデックスの再構築は 長期的に見てパフォーマンス上の利点は何もない、と考えてください。 単純なクエリが、インデックスを使っているにもかかわらず遅くなるのは、前節の 内容を元に説明できます。

インデックスによる検索が遅い原因の第1は、リーフノードのチェーンです。 図 1.3で「57」を 検索する場合をもう一度考えてみましょう。明らかに、インデックスには2つの一致する エントリがあります。最低でも2つ同じエントリが存在し得る場合をより深く 考えてみると、次のリーフノードにも「57」というエントリが存在する可能性が あることになります。すると、一致するエントリがまだあるかどうかを確認するために、 データベースは必ず次のリーフノードも読み込まなければ なりません。これはつまり、インデックスによる検索をする場合、ツリーの走査だけ ではなく、リーフノードのチェーンも追う必要があるということです。

このウェブサイトにぴったりのカップは僕たちのショップにあります。
#見た目もいい感じだし、ここでの僕の仕事を支えてくれています

インデックスによる検索が遅い原因の2つ目は、テーブルへのアクセスです。 ひとつのリーフノードだけでも、数百のエントリを保持していることがあります。 対応するテーブルのデータは、通常、たくさんのテーブルブロック (図 1.1参照)に分散して保存されています。つまり、 検索の度にテーブルへのアクセスが発生するということです。

インデックスによる検索は、(1) ツリーを走査し、(2) リーフノード チェーンをたどり、(3) テーブルからデータを読み出す、という3ステップで 行われます。ツリーの走査のみ、インデックスの深さによって、アクセスする ブロックの数に限りがあります。それに対して残りの2ステップでは、 たくさんのブロックにアクセスする必要があるため、インデックスによる検索が 遅い原因になってしまうのです。

「インデックスは遅い」という迷信は、インデックスによる検索が 木の走査だけで行われるという間違った思い込みから始まったものです。 つまり、インデックスによる検索が遅いのは、「壊れた」あるいは 「アンバランスな」木が悪いのだということです。実際は、 多くのデータベースにおいて、どのようにインデックスを使われるかを調べる ことができます。Oracleデータベースでは、この点に関してかなり詳細が 分かるようになっており、インデックスを使った基本的な検索の方法を表す、 以下のような3つのはっきりした区分があります。

INDEX UNIQUE SCAN

INDEX UNIQUE SCANでは、木の走査しか 行いません。Oracleデータベースでは、ユニーク制約により、検索条件が 必ず1つしかないことが確実な場合に、この方法を使います。

INDEX RANGE SCAN

INDEX RANGE SCANでは、一致する全ての エントリを探すために、木の走査に加えて リーフノードチェーンをたどった検索も行います。検索条件に対して 複数のエントリが存在する可能性がある場合の代替策です。

TABLE ACCESS BY INDEX ROWID

TABLE ACCESS BY INDEX ROWIDは、 テーブルから行を読み出します。この操作は、直前に行われたインデックス スキャンの結果から、一致するレコードを読み出すために行われます。

INDEX RANGE SCANは、インデックスのかなり大きな 割合を読み込む可能性があるということに注意しましょう。さらに、各行ごとに テーブルへのアクセスも必要なのだとすると、インデックスを使っていても クエリは遅くなるでしょう。

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