by Hayato Matsuura.

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


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

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

協力してください

この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。

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

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

著者について

Markus Winandの写真

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

彼の本

カバー『SQLパフォーマンス詳解』

核心をわかりやすく 解説。

Markusから購入します
(送料無料+PDF)

Amazonで購入
(印刷版のみ)

“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