Oracle の B*Tree インデックスの内部構造についてお勉強中(その3)
インデックス・ネタまだまだ(もう少し)続きます。前回の最後にちょろっと書いた、
についてもう少し詳しく書きたいと思います。今回の手順で構築された B*Tree を図に表すと、だいたいこんな構造になっています。
見ての通り、同一ブロック内の第一キーの同一値がほぼ全て網羅されています。Oracle はブロック単位で I/O 管理されているため、上記の例だと where ID=1 のように第一キーの等価評価による絞り込みを行う場合、ブロックをまたぐ最悪ケースを想定しても、物理 I/O ( physical reads )は 3 回以下ですみます。多くの場合はブランチ + リーフの合計 2 回の物理 I/O で事足ります。
逆に第二キーのみでの絞り込みだと、リーフを横断してスキャンする必要があるのがわかっていただけると思います。そのためにリーフ同士は双方向リストで結ばれていて INDEX SKIP SCAN を行っているものと思われます。(←ここ推測です)
実例で解析してみます。まずは予めインデックスが無い状態での実行計画を取得しておきます。実行圭角は Oracle 再起動直後の状態のものです。
SQL> SELECT * FROM BTREE_TEST WHERE ID=1; 実行計画 ---------------------------------------------------------- Plan hash value: 1359717616 -------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | -------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 100 | 900 | 46 (0)| 00:00:01 | |* 1 | TABLE ACCESS FULL| BTREE_TEST | 100 | 900 | 46 (0)| 00:00:01 | -------------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 1 - filter("ID"=1) 統計 ---------------------------------------------------------- 342 recursive calls 0 db block gets 272 consistent gets 210 physical reads 0 redo size 2914 bytes sent via SQL*Net to client 535 bytes received via SQL*Net from client 8 SQL*Net roundtrips to/from client 14 sorts (memory) 0 sorts (disk) 100 rows processed
次にインデックスが存在する状態での実行計画を取得します。以下の SQL を実行してみてください。まず初めにテーブルデータを全てキャッシュにのせます。そうすることでインデックスに対する物理 I/O だけを検出可能となります。
SELECT * FROM BTREE_TEST; SET LINE 1000 SET PAGES 1000 SET AUTOTRACE ON SELECT * FROM BTREE_TEST WHERE ID=1;
結果は以下のようになると思います。物理 I/O はブランチ + リーフ -1 に対して 2 回発生し、リーフ -1 内のデータを頭から順にスキャン( INDEX RANGE SCAN )して 100 レコード取得したという結果になりまいた。
SQL> SELECT * FROM BTREE_TEST WHERE ID=1; ID NAME ---------- ---------- 1 DATA1 1 DATA10 ・・・中略・・・ 1 DATA98 1 DATA99 100行が選択されました。 実行計画 ---------------------------------------------------------- Plan hash value: 1761782662 ----------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ----------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 100 | 900 | 0 (0)| 00:00:01 | |* 1 | INDEX RANGE SCAN| IDX_BTREE_TEST | 100 | 900 | 0 (0)| 00:00:01 | ----------------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 1 - access("ID"=1) 統計 ---------------------------------------------------------- 1 recursive calls 0 db block gets 9 consistent gets 2 physical reads 0 redo size 2914 bytes sent via SQL*Net to client 535 bytes received via SQL*Net from client 8 SQL*Net roundtrips to/from client 0 sorts (memory) 0 sorts (disk) 100 rows processed
再び Oracle を再起動直後の状態にして、下記の SQL を実行してみます。
SELECT * FROM BTREE_TEST; SET LINE 1000 SET PAGES 1000 SET AUTOTRACE ON SELECT * FROM BTREE_TEST WHERE ID=1 AND NAME='DATA10';
先ほどと同じくブランチ + リーフ -1 に対する 2 回の物理 I/O が発生しています。Operation が INDEX RANGE SCAN の理由は、インデックスが UNIQUE インデックスではないためです。先ほどと同様にリーフ -1 のレコードを頭からスキャンして、NAME='DATA10' を評価します。そのため第二キーによる絞り込みが追加されたとしても INDEX RANGE SCAN になるわけです。
今回はたまたま 2 行目のレコードがヒットして3行目で異なるので、内部的なスキャンは 3 回ですんでいますが、最悪のケースでは、全レコードのスキャンが必要になります。それでも TABLE FULL SCAN と比較すれば圧倒的に高速なわけです。
SQL> SELECT * FROM BTREE_TEST WHERE ID=1 AND NAME='DATA10'; ID NAME ---------- ---------- 1 DATA10 実行計画 ---------------------------------------------------------- Plan hash value: 1761782662 ----------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ----------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 9 | 1 (0)| 00:00:01 | |* 1 | INDEX RANGE SCAN| IDX_BTREE_TEST | 1 | 9 | 1 (0)| 00:00:01 | ----------------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 1 - access("ID"=1 AND "NAME"='DATA10') 統計 ---------------------------------------------------------- 1 recursive calls 0 db block gets 3 consistent gets 2 physical reads 0 redo size 589 bytes sent via SQL*Net to client 469 bytes received via SQL*Net from client 2 SQL*Net roundtrips to/from client 0 sorts (memory) 0 sorts (disk) 1 rows processed
では UNIQUE INDEX の場合はどうなるのか?と言う疑問が自然に湧いてきます。というわけでインデックスを作成し直してみます。
DROP INDEX IDX_BTREE_TEST; CREATE UNIQUE INDEX IDX_BTREE_TEST ON BTREE_TEST(ID,NAME); TRUNCATE TABLE BTREE_TEST; BEGIN FOR i IN 1..100 LOOP FOR j IN 1..100 LOOP INSERT INTO BTREE_TEST VALUES(i,'DATA'||TO_CHAR(j)); END LOOP; END LOOP; COMMIT; END; /
結論だけを言うと、ブランチもリーフも構造が変化しました。
まずはブランチの TreeDump から。何故か初めのレコードが ID=3 のみになっています。col 1: TERM の意味も不明です。次のレコードからは ID=5, NAME='DATA2' と複合キーでの管理となっています。まぁぶっちゃけよくわからないです。
Branch block dump ================= header address 99111500=0x5e8524c kdxcolev 1 KDXCOLEV Flags = - - - kdxcolok 0 kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y kdxconco 2 kdxcosdc 1 kdxconro 48 kdxcofbo 124=0x7c kdxcofeo 7437=0x1d0d kdxcoavs 7313 kdxbrlmc 21765199=0x14c1c4f kdxbrsno 47 kdxbrbksz 8056 kdxbr2urrc 0 row#0[8035] dba: 21765212=0x14c1c5c col 0; len 2; (2): c1 04 col 1; TERM row#1[8043] dba: 21765225=0x14c1c69 col 0; len 2; (2): c1 06 col 1; len 5; (5): 44 41 54 41 32 row#2[8022] dba: 21765238=0x14c1c76 col 0; len 2; (2): c1 08 col 1; len 5; (5): 44 41 54 41 32 row#3[8009] dba: 21765264=0x14c1c90 col 0; len 2; (2): c1 0a col 1; len 5; (5): 44 41 54 41 32 ・・・中略・・・ row#45[7463] dba: 21765383=0x14c1d07 col 0; len 2; (2): c1 5e col 1; len 5; (5): 44 41 54 41 32 row#46[7450] dba: 21765189=0x14c1c45 col 0; len 2; (2): c1 60 col 1; len 5; (5): 44 41 54 41 32 row#47[7437] dba: 21765202=0x14c1c52 col 0; len 2; (2): c1 62 col 1; len 5; (5): 44 41 54 41 32 ----- end of branch block dump -----
次にリーフ -1 の TreeDump です。こちらも構造が変化し、rowid の管理がリーフレコードからヘッダー部分での管理になっています。
Leaf block dump =============== header address 99111524=0x5e85264 kdxcolev 0 KDXCOLEV Flags = - - - kdxcolok 1 kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y kdxconco 2 kdxcosdc 2 kdxconro 200 kdxcofbo 436=0x1b4 kdxcofeo 4448=0x1160 kdxcoavs 4012 kdxlespl 0 kdxlende 0 kdxlenxt 21765212=0x14c1c5c kdxleprv 0=0x0 kdxledsz 6 kdxlebksz 8032 row#0[4448] flag: ----S-, lock: 2, len=17, data:(6): 01 05 78 4e 00 00 col 0; len 2; (2): c1 02 col 1; len 5; (5): 44 41 54 41 31 row#1[4465] flag: ----S-, lock: 2, len=18, data:(6): 01 05 78 4e 00 09 col 0; len 2; (2): c1 02 col 1; len 6; (6): 44 41 54 41 31 30 row#2[4483] flag: ----S-, lock: 2, len=19, data:(6): 01 05 78 4e 00 63 col 0; len 2; (2): c1 02 col 1; len 7; (7): 44 41 54 41 31 30 30 ・・・中略・・・ row#197[7978] flag: ----S-, lock: 2, len=18, data:(6): 01 05 78 4e 00 c4 col 0; len 2; (2): c1 03 col 1; len 6; (6): 44 41 54 41 39 37 row#198[7996] flag: ----S-, lock: 2, len=18, data:(6): 01 05 78 4e 00 c5 col 0; len 2; (2): c1 03 col 1; len 6; (6): 44 41 54 41 39 38 row#199[8014] flag: ----S-, lock: 2, len=18, data:(6): 01 05 78 4e 00 c6 col 0; len 2; (2): c1 03 col 1; len 6; (6): 44 41 54 41 39 39 ----- end of leaf block dump ----- End dump data blocks tsn: 4 file#: 5 minblk 793679 maxblk 793679
木構造からは違いが見られたものの、イマイチそれによって何がどうなるかつかめません。そこで再び Oracle を再起動直後の状態にして、下記 SQL を実行して実行計画を取得してみることにします。
SELECT * FROM BTREE_TEST; SET LINE 1000 SET PAGES 1000 SET AUTOTRACE ON SELECT * FROM BTREE_TEST WHERE ID=1 AND NAME='DATA10';
実行計画は下記のようになりました。今度は INDEX RANGE SCAN ではなく INDEX UNIQUE SCAN に変わりました。意外にも物理 I/O は 33 回に増えてしまいました。おそらく UNIQUE INDEX の場合は、該当するブランチとリーフ以外にも、様々な情報を読み込む必要があると言うことなのでしょう。
また推測ですが、INDEX UNIQUE SCAN の探索アルゴリズムは RANGE SCAN と異なり、リーフ -1 を二分探索アルゴリズムで目的のレコードを探しているのではないかと考えています。そのためにリーフ内のレコードはソート済み状態で管理されているのです。二分探索ならば計算量は O(log2n) なので INDEX RANGE SCAN より高速です。実際にはインデックスはすぐにキャッシュ上にのるため、結果的に UNIQUE INDEX の方が高速に探索可能なんじゃないかと考えています。
SQL> SELECT * FROM BTREE_TEST WHERE ID=1 AND NAME='DATA10'; ID NAME ---------- ---------- 1 DATA10 実行計画 ---------------------------------------------------------- Plan hash value: 668490793 ------------------------------------------------------------------------------------ | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ------------------------------------------------------------------------------------ | 0 | SELECT STATEMENT | | 1 | 9 | 1 (0)| 00:00:01 | |* 1 | INDEX UNIQUE SCAN| IDX_BTREE_TEST | 1 | 9 | 1 (0)| 00:00:01 | ------------------------------------------------------------------------------------ Predicate Information (identified by operation id): --------------------------------------------------- 1 - access("ID"=1 AND "NAME"='DATA10') 統計 ---------------------------------------------------------- 1 recursive calls 0 db block gets 3 consistent gets 33 physical reads 80 redo size 589 bytes sent via SQL*Net to client 469 bytes received via SQL*Net from client 2 SQL*Net roundtrips to/from client 0 sorts (memory) 0 sorts (disk) 1 rows processed
というわけで、一部推測が入り込んでいますが、B*Tree について随分と理解が深まった気がするので、ここでお終いにします。
コメントやシェアをお願いします!