読者です 読者をやめる 読者になる 読者になる

kagamihogeの日記

kagamihogeの日記です。

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

DB Oracle SQL SQL Developer

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

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

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

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

環境

やったこと

テーブルとデータの準備

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

テーブルは二つ作る。一つは通常の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_testbtree_testに変わるだけなので省略する。

column1は10000種類、column2はabcdefの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 < 100COLUMN3 < 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の機能を使用して取得したもの。

f:id:kagamihoge:20141019174254p:plain

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

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

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

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

f:id:kagamihoge:20141019174325p:plain

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

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

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

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

参考文献

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

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

続き

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