長大な LEFT OUTER JOIN へのビットマップ・インデックス(EVI)の有効性

よく見かける SQL の中に、あるベースとなるテーブルにたくさんの LEFT OUTER JOIN がくっついている長大な SQL があります。

おそらく帳票的な発想の Query で、たいていはデータ・ウェアハウス/BI まではいかないものの、その第一歩となりそうなものであることが多くあります。

もともと、データ・ウェアハウス/BI の分野では "スター・ジョイン"とか"スター・スキーマ処理"と言われている独特の SQL があり、、そうした処理に有効なものとして「ビットマップ・インデックス」というインデックスが開発されてきました。

実際のところ、とてもとても単純化していうと、大量のデータからある程度(60% とか 70%とか)のデータを取ってくるというのは実はいわゆる普通のインデックスにはあまり得意なことではないんです。
インデックスというのはもともと少量のデータを選択して取ってくるようなケースに有効なもので、あまりたくさんのデータをとってくるにはオーバーヘッドが高いものなんです。イメージとしては、ポパイのほうれんそうとかゼロヨンのニトロというか試合前の栄養ドリンク(後でどっと疲れませんか?!)とか、そんなかんじのものなんですね、実は。

テーブルスキャンだとちょっと効率が悪く、インデックスを使用するとオーバーヘッドがありすぎる、といったようなケースに有効なもの、としてビットマップ・インデックスが利用できることが多くあります。

たいていの場合、最初にふれた"よく見かける SQL"には LEFT OUTER JOIN の左側になっているテーブルにフラグなどの条件での選択があります。
フラグは 1 か 0、もしくはいくつかのコードであるケースがほとんどなので、ビットマップ・インデックスが有効に使えるかもしれません。

ビットマップ・インデックスというのは、SQL Server には存在しませんし、Oracle の場合は Enterprise Edition のみでしか使用できない機能です。
が、DB2 for IBM i では、コード化ベクトル・インデックス (Encoded Vector Index) という、ビットマップ・インデックスをさらに進化させたインデックスが標準で使用できるようになっています。

この「ビットマップ・インデックス」が"よく見かける、あるベースとなるテーブルにたくさんの LEFT OUTER JOIN がくっついている長大な SQL "に有効なのかどうか、DB2 for IBM i を例にとって調べてみたいと思います。


LEFT OUTER JOIN の例

わざとらしく作るのもなんだと思いましたので、「外部結合の使い方 - 結果のフォーマット整形と集合演算を外部結合で行う - 」からいくつかのSQL をお借りして実験してみました。

こちらがまず最初のテストに使用させていただいた SQL です。

--クロス表を求める水平展開 その1:外部結合の利用
SELECT    C0.name,
  CASE WHEN C1.name IS NOT NULL THEN '○' ELSE NULL END AS "SQL-Entry",
  CASE WHEN C2.name IS NOT NULL THEN '○' ELSE NULL END AS "UNIX-Basic",
  CASE WHEN C3.name IS NOT NULL THEN '○' ELSE NULL END AS "Java-Advanced"

FROM  (SELECT DISTINCT name FROM  Courses) C0
  LEFT OUTER JOIN
    (SELECT name FROM Courses WHERE course = 'SQL入門' ) C1
    ON  C0.name = C1.name
      LEFT OUTER JOIN
        (SELECT name FROM Courses WHERE course = 'UNIX基礎' ) C2
        ON  C0.name = C2.name
          LEFT OUTER JOIN
            (SELECT name FROM Courses WHERE course = 'Java中級' ) C3
            ON  C0.name = C3.name;

ベースのテーブルとなるのは Course テーブルで、そこから name カラムを重複なしにもってきて、LEFT OUTER JOIN を行っています。

そのままの実行 ("その1"について最初の試行)

まずそのまま実行し、Visual Explain を見てみました。

インデックスの作成がアドバイスされています。

インデックス・アドバイスに従ってみる ("その1"について 2回目の試行)

インデックスアドバイスに従ってインデックスをそれぞれ作成してみましょう。

COURSES テーブルの NAME カラムに対する索引タイプ EVI (ビットマップ)のインデックスと、

COURSES テーブルの COURSE カラムに対する通常のインデックスとを作成します。

アドバイスされたインデックスを作成後、同じSQL を実行してみました。

最適化時間・実行時間ともに短縮されていることがわかります。

最適化時間が 194 → 145 に、
実行時間が 312 → 47 になっていることが確認できます。

ちなみに、COURSE テーブルの NAME カラムに対して、索引タイプを EVI から通常のバイナリー・ツリーのインデックスに変更して作成してみたらどうなるでしょうか??

答えは「採用されません(Table Scan cost is better)」でした。

EVI を通常に変更して変化がなかった件はそれで終わりとして、
素直にインデックス・アドバイスに従った後でも、さらにインデックスのアドバイスがありました。

COURSES テーブルに対して、COURSE カラム, NAME カラムの複合インデックスのお勧めです。

アドバイスに従って作成したインデックスは意味なかったの?! と思うかもしれませんが、そんなことはありません。

インデックスには、照会を行う際に実際に利用される、という仕事と、最適なアクセス・プランを作成するための情報源、という仕事との、大きく二つの役割があります。

インデックス、といって想像されるのは通常前者だけかもしれませんが、後者も大事な仕事をしています。

たとえば、テーブルの中のデータの分布等がどうなっているかなどで、それによってテーブルを全部読んだ方がよっぽど効率的かインデックスを使用すべきか、が最新の状況でわかるわけですね。

IX_1 (EVI) は Visual Explain でみたとおり使用されていますし、後者にあたる情報源としても使用されていることが「照会統計使用回数」からわかります。

IX_2 も「照会使用回数」(実際に使用された回数ですね)は 0 ですが、「照会統計使用回数」から情報源として重要な仕事をしてくれていることがわかるわけですね。

追加のインデックス・アドバイスに従う ("その1"について 3回目の試行)

では、気を取り直して(?!)新しくアドバイスされたインデックス(COURSES テーブルに対しての COURSE カラム, NAME カラムの複合インデックス)を作成してみましょう。

同じSQL を再度実行してみると、さらに最適化時間・実行時間ともに短縮されたことが確認できました。

最適化時間が 194 → 145 → 84 に、
実行時間が 312 → 47→ 44 になっていることが確認できます。

3回の試行それぞれについての考察

それぞれ(アドバイスされたインデックス作成前/ 1回目のアドバイス実行後/ 2回目のアドバイス実行後)について、どこが変わってきているのかを簡単に見てみましょう。

一番最初のものでも INDEX PROBE なのですが、

アドバイスされたインデックス作成前の Visual Explain です。

COURSES テーブルの NAME カラムに対するテーブル・スキャンと、LEFT OUTER JOIN される SQL についてのプライマリー・キー制約を使用したインデックス・アクセスを組み合わせたアクセス・プランになっています。

最初のインデックスアドバイスに従って IX_1(EVI) と IX_2 と作成した後の状態です。

「COURSES テーブルの NAME カラムに対するテーブル・スキャン」に対して、それを置き換えるかたちで EVI が使用されていることがわかります。

その他の部分は元のままですね。

2回目のインデックスアドバイスの後のものです。

まさしくアドバイスされたインデックスが使われています。

ちなみに、2回目のインデックス・アドバイスの後はもうアドバイスはありませんでした。

EVI の使用については、最初のインデックス・アドバイスの後と、2回目のインデックス・アドバイスの後とでの変化はありませんでした。

2回目のインデックス・アドバイス後の情報ですが、特別変化がないことがわかります。


LEFT OUTER JOIN の書き換え例

ひとつだけではなんなので、続けて"その1"の書き換え例について実験してみました。(こちらは "LEFT OUTER JOIN を使用したSQL" ではすでになくなっているので、書き換えた場合の影響はどうか? という観点になります)

↓がその "その2" の SQL になります。

--水平展開 その2:スカラ・サブクエリの利用
SELECT  C0.name,
  (SELECT '○'
     FROM Courses C1
    WHERE course = 'SQL入門'
      AND C1.name = C0.name) AS "SQL-Entry",
  (SELECT '○'
     FROM Courses C2
    WHERE course = 'UNIX基礎'
      AND C2.name = C0.name) AS "UNIX-Basic",
  (SELECT '○'
     FROM Courses C3
    WHERE course = 'Java中級'
      AND C3.name = C0.name) AS "Java-Advanced"
  FROM (SELECT DISTINCT name FROM Courses) C0;

そのままの実行 ("その2"について最初の試行)

実行結果の Visual Explain です。

↓の 2つのインデックス・アドバイスがありました。

テーブル・スキャンのノードについて詳細を見てみると、そこでも EVI のインデックスがアドバイスされているのが確認できます。

インデックス・アドバイスに従ってみる ("その2"について 2回目の試行)

アドバイスされているインデックスが"その1"での、IX_1 と IX_3 に相当していますので、それをそのまま再度作成して使用しました。

実行後の Visual Explain です。

最適化時間は少し伸びていますが、実行時間が大きく短縮されていることがわかります。

最適化時間が 71 → 77 に、
実行時間が 178 → 42 になっていることが確認できます。

インデックス作成前と比較してみると、
テーブルスキャンして重複を取り除いていたところが、

EVI での一発アクセスになっています。

2回の試行それぞれについての考察

追加のインデックス・アドバイスなどはなかったので、2回の試行について、それぞれを比較してみてみましょう。

今回は IX_2 をあらかじめ作成しておいてみたのですが、使用されていません。"その1"と同様に、プライマリー・キー制約を使用してのインデックス・アクセスが行われています。

インデックス・アドバイスに従った後のものです。

アドバイスされたインデックスが使用されているのが確認できます。

さらに書き換えたケースが"その3"として載っていたのですが、

--水平展開 その3:CASE式を入れ子にする
SELECT  name,
  CASE WHEN SUM(CASE WHEN course = 'SQL入門' THEN 1 ELSE NULL END) = 1
       THEN '○' ELSE NULL END AS "SQL-Entry",
  CASE WHEN SUM(CASE WHEN course = 'UNIX基礎' THEN 1 ELSE NULL END) = 1
       THEN '○' ELSE NULL END AS "UNIX-Basic",
  CASE WHEN SUM(CASE WHEN course = 'Java中級' THEN 1 ELSE NULL END) = 1
       THEN '○' ELSE NULL END AS "Java-Advanced"
FROM Courses
GROUP BY name;

インデックス・アドバイスもなく、アクセス・プランもシンプルなものだったので、今回はこれ以上の実験はしませんでした。

インデックスのアドバイスはありません

念のため、↓が使用した SQL です。DB2 for IBM i V6R1 では問題なくすべて実行できました。

CREATE SCHEMA SQLTEST;

SET SCHEMA SQLTEST;

--作成者:ミック
--作成日:2006/12/09
--最終更新日:2006/12/09


--*******************************************
--
--1.外部結合で行列変換 その1(行→列):クロス表を作る
--
--*******************************************

CREATE TABLE Courses (name   varchar(30), 
                      course varchar(30), 
                     PRIMARY KEY(name, course));

INSERT INTO Courses (name, course ) VALUES('赤井', 'SQL入門');
INSERT INTO Courses (name, course ) VALUES('赤井', 'UNIX基礎');
INSERT INTO Courses (name, course ) VALUES('鈴木', 'SQL入門');
INSERT INTO Courses (name, course ) VALUES('工藤', 'SQL入門');
INSERT INTO Courses (name, course ) VALUES('工藤', 'Java中級');
INSERT INTO Courses (name, course ) VALUES('吉田', 'UNIX基礎');
INSERT INTO Courses (name, course ) VALUES('渡辺', 'SQL入門');




--クロス表を求める水平展開 その1:外部結合の利用
SELECT    C0.name,
  CASE WHEN C1.name IS NOT NULL THEN '○' ELSE NULL END AS "SQL-Entry",
  CASE WHEN C2.name IS NOT NULL THEN '○' ELSE NULL END AS "UNIX-Basic",
  CASE WHEN C3.name IS NOT NULL THEN '○' ELSE NULL END AS "Java-Advanced"

FROM  (SELECT DISTINCT name FROM  Courses) C0
  LEFT OUTER JOIN
    (SELECT name FROM Courses WHERE course = 'SQL入門' ) C1
    ON  C0.name = C1.name
      LEFT OUTER JOIN
        (SELECT name FROM Courses WHERE course = 'UNIX基礎' ) C2
        ON  C0.name = C2.name
          LEFT OUTER JOIN
            (SELECT name FROM Courses WHERE course = 'Java中級' ) C3
            ON  C0.name = C3.name;


--水平展開 その2:スカラ・サブクエリの利用
SELECT  C0.name,
  (SELECT '○'
     FROM Courses C1
    WHERE course = 'SQL入門'
      AND C1.name = C0.name) AS "SQL-Entry",
  (SELECT '○'
     FROM Courses C2
    WHERE course = 'UNIX基礎'
      AND C2.name = C0.name) AS "UNIX-Basic",
  (SELECT '○'
     FROM Courses C3
    WHERE course = 'Java中級'
      AND C3.name = C0.name) AS "Java-Advanced"
  FROM (SELECT DISTINCT name FROM Courses) C0;


--水平展開 その3:CASE式を入れ子にする
SELECT  name,
  CASE WHEN SUM(CASE WHEN course = 'SQL入門' THEN 1 ELSE NULL END) = 1
       THEN '○' ELSE NULL END AS "SQL-Entry",
  CASE WHEN SUM(CASE WHEN course = 'UNIX基礎' THEN 1 ELSE NULL END) = 1
       THEN '○' ELSE NULL END AS "UNIX-Basic",
  CASE WHEN SUM(CASE WHEN course = 'Java中級' THEN 1 ELSE NULL END) = 1
       THEN '○' ELSE NULL END AS "Java-Advanced"
FROM Courses
GROUP BY name;

--*******************************************
--
--2.外部結合で行列変換 その2(列→行):繰り返し項目を1列にまとめる
--
--*******************************************
CREATE TABLE Personnel (employee   varchar(30), 
                        child_1    varchar(30), 
                        child_2    varchar(30), 
                        child_3    varchar(30), 
                     PRIMARY KEY(employee));

INSERT INTO Personnel (employee, child_1, child_2, child_3) VALUES('赤井', '一郎', '二郎', '三郎');
INSERT INTO Personnel (employee, child_1, child_2, child_3) VALUES('工藤', '春子', '夏子', NULL);
INSERT INTO Personnel (employee, child_1, child_2, child_3) VALUES('鈴木', '夏子', NULL,   NULL);
INSERT INTO Personnel (employee, child_1, child_2, child_3) VALUES('吉田', NULL,   NULL,   NULL);

--列から行への変換:UNION ALLの利用
SELECT employee, child_1 AS child FROM Personnel
UNION ALL
SELECT employee, child_2 AS child FROM Personnel
UNION ALL
SELECT employee, child_3 AS child FROM Personnel;




--社員の子供リストを得るSQL(子供のいない社員も出力する)
SELECT EMP.employee, CHILDREN.child
FROM   Personnel EMP
  LEFT OUTER JOIN
   (SELECT child_1 AS child FROM Personnel
    UNION
    SELECT child_2 AS child FROM Personnel
    UNION
    SELECT child_3 AS child FROM Personnel) CHILDREN
  ON CHILDREN.child IN (EMP.child_1, EMP.child_2, EMP.child_3);






--*******************************************
--
--3.クロス表で入れ子の表側を作る
--
--*******************************************
CREATE TABLE TblSex (sex_cd   char(1), 
                     sex varchar(5), 
                     PRIMARY KEY(sex_cd));
CREATE TABLE TblAge (age_class char(1), 
                     age_range varchar(30), 
                     PRIMARY KEY(age_class));
CREATE TABLE TblPop (pref_name  varchar(30), 
                     age_class  char(1), 
                     sex_cd     char(1), 
                     population integer, 
                     PRIMARY KEY(pref_name, age_class,sex_cd));


INSERT INTO TblSex (sex_cd, sex ) VALUES('m',   '男');
INSERT INTO TblSex (sex_cd, sex ) VALUES('f',   '女');


INSERT INTO TblAge (age_class, age_range ) VALUES('1',  '21〜30歳');
INSERT INTO TblAge (age_class, age_range ) VALUES('2',  '31〜40歳');
INSERT INTO TblAge (age_class, age_range ) VALUES('3',  '41〜50歳');


INSERT INTO TblPop VALUES('秋田', '1', 'm', 400 );
INSERT INTO TblPop VALUES('秋田', '3', 'm', 1000 );
INSERT INTO TblPop VALUES('秋田', '1', 'f', 800 );
INSERT INTO TblPop VALUES('秋田', '3', 'f', 1000 );
INSERT INTO TblPop VALUES('青森', '1', 'm', 700 );
INSERT INTO TblPop VALUES('青森', '1', 'f', 500 );
INSERT INTO TblPop VALUES('青森', '3', 'f', 800 );
INSERT INTO TblPop VALUES('東京', '1', 'm', 900 );
INSERT INTO TblPop VALUES('東京', '1', 'f', 1500 );
INSERT INTO TblPop VALUES('東京', '3', 'f', 1200 );
INSERT INTO TblPop VALUES('千葉', '1', 'm', 900 );
INSERT INTO TblPop VALUES('千葉', '1', 'f', 1000 );
INSERT INTO TblPop VALUES('千葉', '3', 'f', 900 );



--外部結合で入れ子の表側を作る
SELECT
  MASTER.age_class AS age_class,
  MASTER.sex_cd    AS sex_cd,
  DATA.pop_tohoku  AS pop_tohoku,
  DATA.pop_kanto   AS pop_kanto
FROM
  (SELECT
     age_class,
     sex_cd,
     SUM(CASE WHEN pref_name IN ('青森', '秋田')
              THEN population ELSE NULL END) AS pop_tohoku,
     SUM(CASE WHEN pref_name IN ('東京', '千葉')
              THEN population ELSE NULL END) AS pop_kanto
   FROM TblPop
   GROUP BY age_class, sex_cd) DATA
     RIGHT OUTER JOIN
       (SELECT age_class, sex_cd
          FROM TblAge 
                CROSS JOIN
               TblSex ) MASTER
     ON  MASTER.age_class = DATA.age_class
    AND  MASTER.sex_cd    = DATA.sex_cd;



--*******************************************
--
--4.完全外部結合
--
--*******************************************

CREATE TABLE Class_A (id   char(1), 
                      name varchar(30), 
                      PRIMARY KEY(id));
CREATE TABLE Class_B (id   char(1), 
                      name varchar(30), 
                      PRIMARY KEY(id));

INSERT INTO Class_A (id, name) VALUES('1', '田中');
INSERT INTO Class_A (id, name) VALUES('2', '鈴木');
INSERT INTO Class_A (id, name) VALUES('3', '伊集院');


INSERT INTO Class_B (id, name) VALUES('1', '田中');
INSERT INTO Class_B (id, name) VALUES('2', '鈴木');
INSERT INTO Class_B (id, name) VALUES('4', '西園寺');



--完全外部結合は情報を「完全」に保存する
SELECT COALESCE(A.id, B.id) AS id,
       A.name AS A_name,
       B.name AS B_name
FROM Class_A  A  FULL OUTER JOIN Class_B  B
  ON A.id = B.id;


--完全外部結合が使えない環境での代替方法
SELECT A.id AS id, A.name, B.name
  FROM Class_A  A   LEFT OUTER JOIN Class_B  B
    ON A.id = B.id
UNION
SELECT B.id AS id, A.name, B.name
  FROM Class_A  A  RIGHT OUTER JOIN Class_B  B
    ON A.id = B.id;


--*******************************************
--
--5.完全外部結合
--
--*******************************************

--テーブル作成
CREATE TABLE Items (item varchar(30),
                    PRIMARY KEY(item));
CREATE TABLE ShopItems (shop varchar(30), 
                        item varchar(30),
                        PRIMARY KEY(shop, item));

INSERT INTO Items VALUES('ビール');
INSERT INTO Items VALUES('紙オムツ');
INSERT INTO Items VALUES('自転車');

INSERT INTO ShopItems VALUES('仙台', 'ビール');
INSERT INTO ShopItems VALUES('仙台', '紙オムツ');
INSERT INTO ShopItems VALUES('仙台', '自転車');
INSERT INTO ShopItems VALUES('仙台', 'カーテン');
INSERT INTO ShopItems VALUES('東京', 'ビール');
INSERT INTO ShopItems VALUES('東京', '紙オムツ');
INSERT INTO ShopItems VALUES('東京', '自転車');
INSERT INTO ShopItems VALUES('大阪', 'テレビ');
INSERT INTO ShopItems VALUES('大阪', '紙オムツ');
INSERT INTO ShopItems VALUES('大阪', '自転車');




--外部結合で差集合を求める:A-B
SELECT A.id AS id,  A.name AS A_name
  FROM Class_A  A LEFT OUTER JOIN Class_B B
    ON A.id = B.id
 WHERE B.name IS NULL;


--外部結合で差集合を求める:B-A
SELECT B.id AS id, B.name AS B_name
  FROM Class_A  A  RIGHT OUTER JOIN Class_B B
    ON A.id = B.id
 WHERE A.name IS NULL;


--完全外部結合で排他的和集合を求める
SELECT COALESCE(A.id, B.id) AS id,
       COALESCE(A.name , B.name ) AS name
  FROM Class_A  A  FULL OUTER JOIN Class_B  B
    ON A.id = B.id
 WHERE A.name IS NULL 
    OR B.name IS NULL;



--外部結合で関係除算:差集合の応用
SELECT DISTINCT shop
  FROM ShopItems SI1
WHERE NOT EXISTS
      (SELECT I.item 
         FROM Items I LEFT OUTER JOIN ShopItems SI2
           ON I.item   = SI2.item 
          AND SI1.shop = SI2.shop
        WHERE SI2.item IS NULL) ;

[Top Pageに戻る]

Ads by TOK2