インデックスに関する検証 その5

<インデックスに関する検証 その5> ペンネーム つけまい

— インデックス利用の落とし穴
レンジ検索で全件検索よりも性能ダウン —

前回、TREEDUMPを基に、インデックスに対してどのようにアクセスしていくか
という様子を見てきた。

今回は、この1万件のテーブルを100万件まで拡張させ、リーフ分割が多発する
様子を見ていく。

テーブルTEST01(1万件)に対して、リーフ分割を多発させながら100万件まで
拡張させた結果(イメージ)を示す。

●100万件まで拡張した過程の説明

1.現行の10000010~10100000までの1万件に、さらに10100010~11000000までの
9万件(増分10)を挿入し、合計10万件のテーブルに拡張(末尾がすべて0)

2.10000001~10999991までの10万件(増分10)を挿入し、合計20万件のテーブ
ルに拡張(末尾がすべて1)

3.以後、末尾が2~9までの各10万件(増分10)を順にそれぞれ挿入し、
10000001~11000000までの合計100万件のテーブルに拡張

なんだかややこしい説明になってしまったが、つまりはリーフ分割を多発させ
たいがために、このような既存のキーとキーとの間に新しいキーの挿入を繰り
返しただけのことなので、拡張の過程についてはあまり深い意味はない。

単に昇順で100万件のテーブルを作成したよりは、リーフ分割を頻発させている
分だけ、リーフ・ブロックの数が多いことだけを認識していただければよい。

この100万件に拡張したテーブルTEST01に対して、1万件の時と同様の検索を行っ
た結果を示す。

検索結果を簡単に説明すると、<検索1>と<検索2>はともに100万件の真中
である50万件目の値10500000をイコール検索したものである。

一方の<検索3>と<検索4>は、1万件の時と同様1~5000件目までをレンジ検
索したものである。

この検索結果で1万件の時と違う点は、<検索1>のインデックスに対するI/O回
数が2から3に増えていることだ。これはただ単に、データが100万件に増えたた
めにHEIGHT(ブランチ・ノードの階層の高さ)が1増えただけであって(下記の
INDEX_STATSの検索結果 HEIGHTを参照)、1万件中の5000件目を検索するのと、
100万件中の50万件目を検索するのとでは、アクセスするブロックが1つ増える
だけで、パフォーマンスに影響を及ぼすものではない。

また、<検索3>のインデックスに対するI/O回数が、1万件の時と同様1~5000
件目までのレンジ検索なのに、45から72に増えているのは、下記のTREEDUMPを
ご覧になっていただければお分かりの通り、リーフ分割を繰り返した結果1リー
フ・ブロック当たりのROWIDの密度が低くなったからである。

その他の値については、1万件から100万件にデータが増えたわけであるから、
それに伴ってI/O回数が増えるのは当然の結果である。

●TEST01(100万件)のINDEX_STATSの内容

ANALYZE INDEX TEST01 VALIDATE STRUCTURE ;

索引が分析されました。

SELECT HEIGHT,BLOCKS,LF_ROWS,LF_BLKS,BR_ROWS,BR_BLKS FROM INDEX_STATS ;

   HEIGHT    BLOCKS   LF_ROWS   LF_BLKS   BR_ROWS   BR_BLKS
--------- --------- --------- --------- --------- ---------
        3     51200   1000000     13793     13792       112
       └→100万件に拡張したことによって
           ブランチ・ノードの階層の高さが増加

●TEST01(100万件)のTREEDUMPの内容(拡張後)

ALTER SESSION SET EVENTS 'IMMEDIATE TRACE NAME TREEDUMP LEVEL 3539' ;
----- begin tree dump
branch: 0x2000003 33554435 (0: nrow: 111, level: 2)
   branch: 0x20000a3 33554595 (-1: nrow: 120, level: 1)
      leaf: 0x2000004 33554436 (-1: nrow: 81)
      leaf: 0x2001b2c 33561388 (0: nrow: 78)
      leaf: 0x2000d98 33557912 (1: nrow: 72)
      leaf: 0x2002c34 33565748 (2: nrow: 68)
      leaf: 0x200036b 33555307 (3: nrow: 77)
      leaf: 0x2001b2d 33561389 (4: nrow: 76)
      leaf: 0x2000d99 33557913 (5: nrow: 79)
      leaf: 0x2001b2e 33561390 (6: nrow: 68)
      leaf: 0x2000369 33555305 (7: nrow: 77)
      leaf: 0x2001b2f 33561391 (8: nrow: 76)
      leaf: 0x2000d9a 33557914 (9: nrow: 79)
      leaf: 0x2001b30 33561392 (10: nrow: 68)
                         :
                         :
                         :
      leaf: 0x2002c31 33565745 (116: nrow: 81)
      leaf: 0x2000a39 33557049 (117: nrow: 81)
      leaf: 0x2002c32 33565746 (118: nrow: 78)
      leaf: 0x200151d 33559837 (119: nrow: 77)
      leaf: 0x2002c33 33565747 (120: nrow: 73)
      leaf: 0x2000a38 33557048 (121: nrow: 70)
      leaf: 0x200344b 33567819 (122: nrow: 62)
      leaf: 0x2001b2a 33561386 (123: nrow: 70)
      leaf: 0x200344c 33567820 (124: nrow: 68)
      leaf: 0x2000d97 33557911 (125: nrow: 70)
      leaf: 0x200344d 33567821 (126: nrow: 62)
      leaf: 0x2001b2b 33561387 (127: nrow: 70)
      leaf: 0x200344e 33567822 (128: nrow: 68)
      leaf: 0x2000368 33555304 (129: nrow: 71)
----- end tree dump

●TEST01(1万件)のTREEDUMPの内容(拡張前)

----- begin tree dump
branch: 0x5800003 92274691 (0: nrow: 87, level: 1)
   leaf: 0x2000004 33554436 (-1: nrow: 116)
   leaf: 0x2000005 33554437 (0: nrow: 116)
   leaf: 0x2000006 33554438 (1: nrow: 116)
   leaf: 0x2000007 33554439 (2: nrow: 116)
   leaf: 0x2000008 33554440 (3: nrow: 116)
                      :
                      :
   leaf: 0x2000018 33554456 (19: nrow: 116)
   leaf: 0x2000019 33554457 (20: nrow: 116)
   leaf: 0x200001a 33554458 (21: nrow: 116)
   leaf: 0x200001b 33554459 (22: nrow: 116)
   leaf: 0x200001c 33554460 (23: nrow: 116)
                      :
                      :
   Leaf: 0x2000058 33554520 (83: nrow: 116)
   Leaf: 0x2000059 33554521 (84: nrow: 116)
   Leaf: 0x200005a 33554522 (85: nrow: 24)
                             ↑        ↑
                           Leaf No.  キーの数
----- end tree dump

拡張前と拡張後を比較していただければお分かりの通り、1リーフ・ブロック当
たりに格納されているインデックス・キーの数が少なくなっている。

拡張前の1万件は、昇順に挿入したので1リーフ・ブロック当たりに116個のイン
デックス・キーが格納されていたが、拡張後の100万件は、昇順ではなく飛び飛
び(末尾が 0 → 1 → 2 ・・・ → 8 → 9 の順)に挿入が行われたため、リー
フ分割が多発し、その結果1リーフ・ブロック中に格納されるインデックス・キー
の数が62~81と少なくなってしまったのである。

次回は、この100万件のテーブルに対して大量の削除を行った結果、インデック
ス検索が全件検索よりも遅くなるという不可解な動きについての検証を行う。

初夏 茅ヶ崎にて

~インデックスに関する検証 その5~
by つけまい