表の行順序とインデックス範囲スキャン

リレーショナルデータベースは論理レベルではテーブルの行順序は重要では無い。しかし、物理レベルではディスクなど順序が重要な意味を持つ媒体に格納されるのが現実である。このエントリでは、表の行の格納順序を昇順orランダムにし、それにインデックスを付与してインデックス範囲スキャンをしたときの速度の違いを見る。

環境

Oracle Database Express Edition 11g Release 2をWindows上で動作
Oracle SQL Developer 3.2
SQL*Plus: Release 11.2.0.2.0 Production

準備

テストデータ格納用のテーブルを作成する。column1には、1〜100万を入れて一意キーインデックスを張る。column2には、ランダム16桁の文字列を入れる。

drop table dest purge;
create table dest 
(
  column1 varchar2(16)
, column2 varchar2(16)
);

上記で作成したテーブルにテストデータを挿入する。
まず、SRCテーブルには下記のように1〜100万のデータが入っている。

0000000000000001
0000000000000002
0000000000000003
（以下略）

SRCからテストデータ用テーブルにデータを挿入する。当然、昇順とランダムとではデータ作成方法が異なる。

まず、昇順用のテストデータ。

insert into dest(column1, column2)
  select column1, DBMS_RANDOM.STRING('A', 16) from src order by column1;
commit;

次に、ランダム用のテストデータ。ランダムな順序は、SRCのデータを乱数値でソートする方法で実施した。

insert into dest(column1, column2)
  select column1, DBMS_RANDOM.STRING('A', 16) from src order by DBMS_RANDOM.NORMAL();
commit;

インデックスを作成する。

create unique index dest_pk on dest (column1);

統計収集。

begin
  DBMS_STATS.GATHER_SCHEMA_STATS (
    ownname => 'KAGAMIHOGE',
    estimate_percent => 1
  );
end;

実行時間の計測

SQL*Plusのset timing onで計測する。また、計測用のselect文を一回流すごとに、バッファキャッシュをクリアする。計測用のselect文は、インデックスヒントを用いてインデックス範囲スキャンに誘導する。実際に返される行は、40万／100万つまり表の40％のブロックにアクセスする。

set timing on;
ALTER SYSTEM FLUSH BUFFER_CACHE;
select /*+ INDEX(dest dest_pk) */ * from dest where column1 <= '0000000000400000';

計測結果

	1	2	3
ASC	00:51.09	00:53.10	00:52.82
RAND	01:38.35	01:37.07	01:45.57

そんなわけで、昇順はランダムより30〜40秒速い結果になりました。

感想とか

まず、昇順orランダムそれぞれでデータを挿入したときのuser_indexを確認する。

select index_name, leaf_blocks, clustering_factor, num_rows from user_indexes where index_name = 'DEST_PK';

	INDEX_NAME	LEAF_BLOCKS	CLUSTERING_FACTOR	NUM_ROWS
ASC	DEST_PK	3537	7555	940213
RAND	DEST_PK	3741	994770	994987

ここで重要なのはCLUSTERING_FACTORの値。静的データ・ディクショナリ・ビュー: ALL_ALL_TABLES〜ALL_OUTLINESによると、下記の通り。

CLUSTERING_FACTOR* NUMBER
索引の値に基づいて順序付けられている、表内の行の量を表す。
・値がブロック数に近い場合、表は高い秩序度を持つ。この場合、1つのリーフ・ブロック内の索引エントリは、同じデータ・ブロック内の行を指す。
・値が行数に近い場合、表はランダム。この場合、同じリーフ・ブロック内の索引エントリが同じデータ・ブロック内の行を指す可能性はほとんどない。
静的データ・ディクショナリ・ビュー: ALL_ALL_TABLES〜ALL_OUTLINES より抜粋

とまぁ、テストデータはほぼOracleのリファレンス通りの値になっている。計測結果の差は、ここから来ている。

インデックス範囲スキャンでかつ実テーブルアクセスが発生する場合を考える。実テーブルの行順序がインデックスの順序と一致している（昇順）とき、ある行を読み込んで次の行を読み込むときほとんどは同一ブロックアクセスとなる。そうでないときも、隣接ブロックに順次アクセスすれば済む。

対して、実テーブルの行順序がインデックスの順序と一致していない（ランダム）とき、ある行を読み込んで次の行を読み込むときほとんど異なるブロックアクセスとなる。さらに、その異なるブロックへのアクセスはバラバラなアドレスから読み込んでこなければならない。

もちろん、バッファキャッシュにテーブルの全ブロックが乗ってしまえば、それ以降は高速に結果を返せるようになる。実際この環境だと、最初の10万件くらいは猛烈に遅いが、それ以降は高速に結果が返ってくるようになる。最も、昇順では最小限のブロックアクセスで済むわけなので、不利なことに変わりは無い。

そういうわけで、インデックス範囲スキャンが頻繁にされるテーブルは、該当インデックスとテーブルの行順序を一致している方が望ましい、ことを見ることが出来た。

もちろん、これらはアクセス方法に依存する。テーブルフルスキャンしかしないとかインデックスの一意スキャンしかしないとかであれば、行順序がバラバラであろうが困ることはない。インデックス範囲スキャンが発生する場合でも、数％しかアクセスしないのであれば、読み込むブロック数に差は殆ど生まれないので、これもさほどは困らないハズである。どのくらいが分水嶺になるかは、環境ごとに変わってくると思うので、インデックス範囲スキャンとテーブルフルスキャンとの実際の速度差を計測して比較するしか無い。

アクセス方法で言えばネステッドループジョインの内部表として使われるかどうかも関係する。

kagamihogeの日記

kagamihogeの日記です。

表の行順序とインデックス範囲スキャン

環境

準備

実行時間の計測

計測結果

感想とか