Oracleのビットマップインデックスを学ぶ

@kagamihoge ppは基本的にOracleサイトから落とせますよ( ＾ω＾) 商用利用せずに個人で実験するレベルであれば、製品版と同じ物を使用できますよ☆ xeは機能制限が多くて、、、

— かーりん (@curry9999) August 5, 2014

OTN開発者ライセンス付きのソフトウエアは、評価・学習・テスト・アプリケーション開発に利用できます。

http://www.oracle.com/technetwork/jp/indexes/downloads/index.html より抜粋

というわけで、Database 11g Enterprise Editionsも個人の日記レベルの学習用途であれば問題無く使用可能なことを教えて頂いた。OracleではビットマップインデックスはExpress Editionでは使用出来なかったので学習対象から外していたのだが、個人で自由に試せる環境を整えることができた。

今回のエントリはビットマップインデックスを使ってみるだけの内容。検証めいたことはやらず、ただ単に使ってみて特徴などを確認するだけに留める。

環境

• DB
  • CentOS-6.5-x86_64
  • Oracle Database 11g Release 2(11.2.0.1.0) Enterprise Edition
• ツール
  • Oracle SQL Developer 4.0.3(4.0.3.16.84)
  • rlogin Version 2.16.6

やったこと

テーブルとデータの準備

まず検証用のデータ入れるテーブルを作る。

テーブルは二つ作る。一つは通常のBTreeインデックスを作り、もう一つはビットマップインデックスを作る。ただし、列と作成するデータは同一なものにする。

なお、列の構成とデータの意図については後述。

DROP TABLE bitmap_test PURGE;
CREATE TABLE bitmap_test
  (
    column1 INTEGER ,
    column2 CHAR(3) ,
    column3 INTEGER ,
    VALUE   VARCHAR2(20)
  );
  
DROP TABLE btree_test PURGE;
CREATE TABLE btree_test
  (
    column1 INTEGER ,
    column2 CHAR(3) ,
    column3 INTEGER ,
    VALUE   VARCHAR2(20)
  );

300万件データを作成する。以下はビットマップ用のテーブルに対するクエリだが、BTree用はbitmap_testがbtree_testに変わるだけなので省略する。

column1は10000種類、column2はabcとdefの2種類、column3は1000種類。あまりカーディナリティが高くない状態にしておく。

INSERT /*+ APPEND */ INTO bitmap_test(column1, column2, column3, VALUE)
  SELECT 
    mod(ROWNUM, 10000),
    CASE WHEN mod(ROWNUM, 2) = 0 THEN 'def' ELSE 'abc' END ,
    mod(ROWNUM, 1000),
    dbms_random.string('X', 20)
    FROM 
      (SELECT ROWNUM FROM all_catalog WHERE ROWNUM <= 3000),
      (SELECT ROWNUM FROM all_catalog WHERE ROWNUM <= 1000);
COMMIT;

後述のインデックス作成後にはスキーマ統計を収集する。以下はSQL Developerのスキーマ統計の収集機能で実行されるクエリを抜粋したもの。

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

インデックスの作成時間とuser_indexes

以下のようなクエリで各列に対してインデックスを作成する。

CREATE BITMAP INDEX bitmap_index1 ON bitmap_test (column1);
CREATE BITMAP INDEX bitmap_index2 ON bitmap_test (column2);
CREATE BITMAP INDEX bitmap_index3 ON bitmap_test (column3);

CREATE INDEX btree_index1 ON btree_test (column1);
CREATE INDEX btree_index2 ON btree_test (column2);
CREATE INDEX btree_index3 ON btree_test (column3);

インデックスの作成時間を計測する。

ビットマップ	1	2	3
bitmap_index1	6.245	6.285	6.208
bitmap_index2	1.562	1.560	1.615
bitmap_index3	6.306	6.245	6.309

BTree	1	2	3
btree_index1	22.319	22.275	22.322
btree_index2	22.264	22.354	22.182
btree_index3	22.152	22.409	22.355

ビットマップインデックスの作成時間がかなり早いことに驚かされる。特に、2種類しか存在しないcolumn2に対するインデックスはほぼ一瞬で終了している。

速度差が生じる理由はどこにあるか。user_indexesを確認してみる。

SELECT index_name,
  leaf_blocks,
  clustering_factor,
  num_rows
FROM user_indexes
ORDER BY index_name
;

以下が実行結果。

INDEX_NAME	LEAF_BLOCKS	CLUSTERING_FACTOR	NUM_ROWS
BITMAP_INDEX1	1431	10014	10014
BITMAP_INDEX2	126	252	252
BITMAP_INDEX3	1469	2939	2939
BTREE_INDEX1	6435	3079551	3079551
BTREE_INDEX2	6424	37367	3070518
BTREE_INDEX3	6420	3092560	3092560

BTreeは当然のことながらテーブル行数分のブロック数となっているが、ビットマップインデックスはそうではない。ここから読み取れることとしては、ビットマップインデックスが使用する容量は、ざっくり言えば、行数×ビットマップの種類数となる。よって、2種類しかないBITMAP_INDEX2は相当少ない容量で済むことになる。

このことから、インデックスの作成時間にかなりの差が生じる要因は、作成後のサイズの大きさに起因している、と考えられる。

ビットマップ・BTreeそれぞれを使用するクエリの実行計画の比較

同一のクエリに対し、ビットマップインデックス・BTreeインデックスそれぞれを使用し、実行計画を比較してみる。

使用するクエリは、データベースパフォーマンスアップの教科書 基本原理編 第2章 インデックスの種類と特徴 2.2.3 ビットマップインデックスのアクセス で例として取り上げているものを使用する。

B-Treeインデックスとの相違点を明確にするために、次のようなクエリを考えてみよう。このクエリは、B-Treeインデックスではインデックスに使用できなかった「NOT」を使用したケースと、これを再度「OR」条件で結合した形態である。

データベースパフォーマンスアップの教科書 基本原理編 第2章 インデックスの種類と特徴 2.2.3 ビットマップインデックスのアクセス　より抜粋

上記の引用文で上げられているクエリは以下。

SELECT * FROM table1
WHERE  COL1 = 123
  AND  COL2 <> 'ABC'
  OR   COL3 < 100 ;

実行計画を取得するクエリは以下の通り。上がビットマップインデックスで、下がBTree用。なお、書籍のサンプルクエリを再現しようと思ったけどCOL3 < 100はCOLUMN3 < 10にしないとインデックス使う実行計画にならなかったので、少し変えている。*1

select * from BITMAP_TEST where COLUMN1 = 1 and COLUMN2 <> 'abc' or COLUMN3 < 10;
select * from BTREE_TEST  where COLUMN1 = 1 and COLUMN2 <> 'abc' or COLUMN3 < 10;

まず、以下はビットマップインデックスの方の実行計画。実行計画のキャプチャはSQL Developerの機能を使用して取得したもの。

ビットマップの方はインデックスのみでアクセスが済んでいるのが分かる。COLUMN2 <> 'abc'に対応するインデックスはBITMAP_INDEX2だが、これは2箇所出現している。まずCOLUMN1 = 1 から COLUMN2 IS NULL をBITMAP_MINUSしている。その結果から更にCOLUMN2 = 'abc'をBITMAP_MINUSしている。これは、否定条件の実現には、'abc'である場合とNULLである場合の両方を除外しなければならないこと、に対応している。

それから、上記の結果とCOLUMN3 < 10とをBITMAP ORしている。COLUMN3 < 10は範囲処理なので、BITMAP_INDEX3をBITMAP INDEX(RANGE SCAN)している。範囲スキャンからは複数のビットマップが返ってくるのでBITMAP MERGEにひとまとめにしている。

最後に、上記で得られたビットマップをROWIDに変換BITMAP CONVERSION(TO ROWIDS)して、インデックスのROWIDを基にしてテーブルアクセスTABLE ACCESS(BY INDEX ROWID)を行う。

次に、BTreeインデックスの方の実行計画を見ていく。

興味深いことにコストはそこまで大きく変わらないものになった。その理由は何故か。

実行計画を見てみるとBITMAP CONVERSION(FROM ROWIDS)というROWIDからビットマップに変換する操作が行われている。どうやら実行計画はCOLUMN1 = 1とCOLUMN3 < 10のORを取るために、それぞれのインデックススキャン結果のROWIDをビットマップへ、アドホックに変換しているようだ。

ただし、否定形のCOLUMN2 <> 'abc'はどうにもならないらしい。上記のアドホックなビットマップから取得したROWIDを基にしてテーブルアクセスをするが、その際のフィルタ条件として指定している。このことから予測出来るのは、このクエリがどのくらい効率的になるかは、このフィルタ条件で減らされる行数がどのくらいあるかに依存すると思われる。

オプティマイザは何気に賢くて、アドホックにビットマップインデックスを作ったほうが良いと判断すれば、BTreeインデックスから勝手に作ってくれる、ということのようだ。

参考文献

データベースパフォーマンスアップの教科書 基本原理編

続き

*1:ヒント使うのもめんどかったので妥協した