Oracle の B*Tree インデックスの内部構造についてお勉強中（その３）

インデックス・ネタまだまだ（もう少し）続きます。前回の最後にちょろっと書いた、

このリーフは必ずソートされて状態で管理されているがために、データの挿入、更新でリーフ分割によるインデックスのパフォーマンス劣化が発生するわけです。また、この解析からわかるように同一ブロック内もしくは近くのブロック内には第一キーが同じものがかたまって存在します。それゆえ、複合索引の場合は、第一キーのみによる SELECT 文でも、効率よくアクセスが可能（ INDEX RANGE SCAN ）で、逆に第二キーのみによる SELECT 文では、いくつものブロックを読む（ INDEX SKIP SCAN もしくは TABE FULL SCAN ）必要がでてくるわけです。

についてもう少し詳しく書きたいと思います。今回の手順で構築された B*Tree を図に表すと、だいたいこんな構造になっています。

- スポンサーリンク -

ora005.png

見ての通り、同一ブロック内の第一キーの同一値がほぼ全て網羅されています。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 回ですんでいますが、最悪のケースでは、全レコードのスキャンが必要になります。それでも 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 について随分と理解が深まった気がするので、ここでお終いにします。

- スポンサーリンク -

関連する記事＆スポンサーリンク