2012-12-20

11gR2再帰SQL(Oracleアドベントカレンダー 2012/12/20)

想定読者：
SQLを扱い始めたばかりの駆け出しデータベース/アプリ開発者の方。

普段はPostgreSQLを専門で扱っていますが、ご縁で書くことになりました。

サポート契約を持ってない人に公開ができて、業務上知り得たノウハウでもなく、かつ面白いネタ、
なかなか見つけるのが難しいですね。

はじめに

機能面でPostgreSQLがOracleより優れているところを探す場合、"Oracleは標準SQLに対応していない"
という点が良く出てきました。

具体的には、一昔前(Oracle8i)までは特にJOINが槍玉に上がっていましたがOracle9iから標準SQLに
準拠するようになり、Oracleの隙はどんどん無くなってきています。(でもOracle9iも10年前か・・・)

そのような中、重箱の隅に残っていた、「再帰 SQLの標準SQL非対応」ですが、Oracle11gR2にて対応
となりました。本日はこのあたりについて書いてみたいと思います。

はじめに2

もうひとつこの記事を書きたかった理由はこの再帰 SQLという方法は「知らなければ発見が難しい
ノウハウ」に(私の分類によると)分類されるためです。

エラーが発生する場合はそのメッセージで検索すれば何かしら情報が出てきますが、このような
ノウハウはちょっと検索が難しいです。なので、このアドベントカレンダーという、少しでも目に
触れることの大きい今回の機会にblogに書いておこうと思い立ちました。

この記事をきっかけに

「今までがんばってPL/SQL書いてたのに！」
「できないと思っていた！」

という方の生産性が少しでも上がると幸いです。

そもそも再帰 SQLって？

再帰 SQLと聞いただけで脳味噌が拒絶反応を示すひとがいるかもしれません。(私が実際にそうなので0ではない。)
しかし、使い方によってはSQLを非常にシンプルに表現できる便利なSQLなので、ちょっと
覚えておきましょう。

・再帰 SQLとはSQLの結果を使ってSQLを実行するためのSQLです。
・WITH句を使って実装します。
・基本的には初期値とループを抜けるための終了条件が必要です。

うーん、言葉で説明することが難しいため、簡単な例にて。

最も小さな再帰 SQL(?)

検証環境：RHEL5.5　Oracle 11.2.0.1.0

まずは小さなSQLから作っていきましょう。

1.WITH句で仮想テーブルを指定し
2.開始条件となるSQLを1つ書き
3.UNION ALLで仮想テーブルで使った表と
　列を使うことで再帰を表現
4.終了条件に向かうための記述
5.終了条件



WITH rectab(col1) --1.仮想テーブルの作成

 AS

 (SELECT 0 from dual --2.開始条件

  UNION ALL

  SELECT col1+1 FROM rectab --4.終了条件に向かうためにCOL1に1を加える

  WHERE col1 < 7)           --5.終了条件

SELECT col1 FROM rectab;

ここでうっかり終了条件のWHERE句を付け忘れたり、終了条件に向かう処理を入れ忘れると
無限ループに入る

はずですが、

そこはかゆいところに手が届くOracleです。



WITH rectab(col1)

 AS

 (SELECT 0 from dual

  UNION ALL

  SELECT col1+1 FROM rectab) --where句忘れ

SELECT col1 FROM rectab;
ERROR:

ORA-32044: 再帰的WITH問合せの実行中にサイクルが検出されました


レコードが選択されませんでした。


SQL> WITH rectab(col1)

 AS

 (SELECT 0 from dual

  UNION ALL

  SELECT col1 FROM rectab --col1のカウントアップ忘れ

  WHERE col1 < 7)

SELECT col1 FROM rectab;

ERROR:

ORA-32044: 再帰的WITH問合せの実行中にサイクルが検出されました


レコードが選択されませんでした。

ちゃんと検知してくれます。素晴らしいですね。

では、C言語のお勉強でよく出てくるツリーの作成をしてみましょう。



WITH rectab(col1)

 AS

 (SELECT 0 from dual

  UNION ALL

  SELECT col1+1 FROM rectab 

  WHERE col1 < 7)

SELECT 

 RPAD(' ',7-col1)||'*'||LPAD(' ',col1*2)||'*'  ctree

FROM rectab;




　CTREE

　--------------------------------------------------------------------------------

　       **

　      *  *

　     *    *

　    *	     *

　   *        *

　  *          *

　 *            *

　*              *
8行が選択されました。

少しアドベントカレンダーっぽくなりました。

では、ちょっと発展して、EMP表の上司部下の関係を表示するSQLを考えます。

定番のemp表の中身は以下のとおりです。



　     EMPNO ENAME	   MGR

　---------- -------- ----------

　      7369 SMITH	  7902

　      7499 ALLEN	  7698

　      7521 WARD 	  7698

　      7566 JONES	  7839

　      7654 MARTIN	  7698

　      7698 BLAKE	  7839

　      7782 CLARK	  7839

　      7839 KING

　      7844 TURNER	  7698

　      7900 JAMES	  7698

　      7902 FORD 	  7566

  　    7934 MILLER	  7782

  　    7788 SCOTT	  7566

  　    7876 ADAMS	  7788

では実際のSQLを見ていきましょう。



WITH emp_data(ename,empno,mgr,l)

  AS

  (SELECT 

    ename, empno, mgr, 1 lvl 

    FROM emp WHERE mgr IS null --開始条件。mgrがNULLの人を探す

   UNION ALL

   SELECT emp.ename, emp.empno, emp.mgr, ed.l+1

     FROM emp, emp_data ed

    WHERE emp.mgr = ed.empno --終了条件　テーブルという有限な値と

                                 --結合しているので今回はこれでOK

  )

  SEARCH DEPTH FIRST BY ename SET order_by

  SELECT l,

         LPAD('　',2*l,'　')||ename nm

    FROM emp_data

   ORDER BY order_by
　 L NM

　-- ----------------

　 1 　KING

　 2 　　BLAKE

　 3 　　　ALLEN

　 3 　　　JAMES

　 3 　　　MARTIN

　 3 　　　TURNER

　 3 　　　WARD

　 2 　　CLARK

　 3 　　　MILLER

　 2 　　JONES

　 3 　　　FORD

　 4 　　　　SMITH

　 3 　　　SCOTT

　 4 　　　　ADAMS

SEARCH DEPTH FIRST BY ename SET order_by
の1行がここで出てきた新しい構文です。SEARCHの後はBREADTHとDEPTHを選択できて、幅と深さの
どちらで並べ替えを行うのか選択できます。

今回はenameをDEPTH順に並べますよ、という指定をしています。

うっかり、BREADTHを指定するとどのようになるのでしょうか。

これは実行してみるとよく分かります。



WITH emp_data(ename,empno,mgr,l)

  AS

  (SELECT 

    ename, empno, mgr, 1 lvl 

    FROM emp WHERE mgr IS null

   UNION ALL

   SELECT emp.ename, emp.empno, emp.mgr, ed.l+1

     FROM emp, emp_data ed

    WHERE emp.mgr = ed.empno

  )

  SEARCH BREADTH FIRST BY ename SET order_by --変更したのはここだけ

  SELECT l,

         LPAD('　',2*l,'　')||ename nm

    FROM emp_data

   ORDER BY order_by

  /




　 L NM

　-- ----------------

　 1 　KING

　 2 　　BLAKE

　 2 　　CLARK

　 2 　　JONES

　 3 　　　ALLEN

　 3 　　　FORD

　 3 　　　JAMES

　 3 　　　MARTIN

　 3 　　　MILLER

　 3 　　　SCOTT

　 3 　　　TURNER

　 3 　　　WARD

　 4 　　　　ADAMS

　 4 　　　　SMITH

これでは親子関係を表示するには不適切ですね。

再帰 SQLは例のような組織の構成を表現する他、部品管理(これを作るためにはネジAと、
ネジBと、パーツAが必要)など、意外に使うシーンはあります。あとはDB屋さん的には
SQLの実行計画なども階層問い合わせのように表現されます。

再帰 SQLの標準SQL非対応って？

Oracleでは再帰 SQLを以下のように書く必要がありました。当時は
再帰 SQLというより階層問い合わせという呼び名が一般的であったかも
しれません。



SELECT ename,job,empno,mgr,level

FROM emp

START WITH job = 'PRESIDENT'

CONNECT BY PRIOR empno = mgr

しかし、このSTART WITH CONNECT BYという構文、Oracleのオリジナル構文です。なので、
アプリケーションを他のデータベースに移植するとこのSQLは実行できません。
(PostgreSQLには一時期、互換のためのcontribがありました)

with句を使った再帰 SQLの方がより柔軟な対応ができますので、これからSQLを覚える人は
こちらを、START WITHで慣れている人もWITH句を使ったSQLを覚えておいたほうが良いかも
しれません。

まとめ

調子に乗って書いていたら結構長くなってきましたので今回はこの辺で。

本記事を読んでアプリケーションを書いている時に

「あれ、これ、もしかしたら再帰 SQLで書けるかも？」
「11gR2だから再帰 SQLを使おう」

と気づいていただける方がいらしたら幸いです。

PS:記事を書いた後にもっと詳しい素晴らしい記事があることを知りました。。
本編は入門記事ということでご容赦を。

http://www.oracle.com/technetwork/jp/articles/point4-155261-ja.html

明日はkingyokkunさんです。よろしくお願いしまーす。

2011-12-14

The patch for Index Only Scan committed

PostgreSQL9.2での新機能になるであろうIndex Only Scanがコミットされました。

アプリケーション＋しくみ分科会でExplainingExplainを担当した身として
とても気になる機能追加ですのでフライング気味ですがRobert Hassのblogを
追ってみました。

1.そもそもIndex Only Scanとは？

PostgreSQLのデータアクセス方法はおおまかに3種類あります。

・テーブルに直接アクセスするSeq Scan.
・インデックスにアクセスし、その後テーブルを参照するIndex Scan.
・論理計算が得意なビットマップを使って表に上手にアクセスするBitmap Scan.

※2011年6月4日しくみ分科会で発表された中西さんの資料が分かりやすいです。

今回、ここに新たなスキャン方法が加わることになります。

2.Index Only Scanとは
Index Only Scan はインデックスだけを走査し、テーブルには(ほとんど)アクセスしない
アクセス方法です。OracleのDBAにとっては至って普通じゃない？と思うお話ですが、
PostgreSQLでは簡単ではありませんでした。

Robert HASSのBlogの説明を借りると、

SELECT name FROM table WHERE id = 10, and there is an index on (id, name), you might assume
that we could use the index to check for tuples with id = 10, and the if one is found, return
the name directly from the index tuple, without consulting the underlying table.

SELECT name FROM table WHERE id = 10というSQLを実行する。ただし、テーブルにはid,nameの
複合インデックスが存在するとする。この場合、id=10というデータをインデックス上で見つけ、
テーブルにはアクセスせず、同じインデックスに格納されているnameのデータを返せば良いだけの
ように思うかもしれない。

Unfortunately, this does not work, because that tuple might not actually be one that
the SELECT statement can see.
しかし、残念ながらこれはうまくいかない。なぜならタプルはSELECT文が実際に見ることが
できるタプルでは無いかもしれないからである。

If the tuple was inserted by a transaction which began after the SELECT statement took
its MVCC snapshot, or deleted by a transaction which committed before the SELECT statement
took its MVCC snapshot, then the SELECT statement must not return it.
もしタプルがSELECT文実行後にINSERTされたものであったり、SELECT文実行前にDELETEされたもので
あった場合、そのタプルを返すべきではない。

つまり、インデックス自体にMVCCを判断する情報を持っていないため、その行を返すべきか、
そうでないものか判断できない、と。では、このMVCCを判断するための情報はどこにあるのか。

それは、テーブルが持っています。

「Index Only Scanしたいけど、MVCCのためにはテーブルを見なければいけない」

これがPostgreSQLではIndex Only Scanの実装は難しいとされていた最大の理由でした。

ところが、PostgreSQL8.4より実装されたvisibility mapの出現により状況が変わりました。
visibility mapは全ての実行中のトランザクションから可視、つまりSELECTして良いページ
の情報を0と1で保存しているビットマップです。

この機能追加によりインデックス＋visibility mapにアクセスをすることで、テーブルに
アクセスせずに、MVCCを判断できるようになりました。

しかし、ここで疑問が生じます。

「visibility mapはタプルの状態をbitつまり、0か1で保持しているのにそれだけで
MVCCを維持できるのか？」

答えはNo！

The index-only scan, therefore, will only be entirely index-only if every
relevant bit in the visibility map is set. We'll still access the table to
the extent necessary to be certain of returning correct answers.

Index Only Scanはvisibility mapに全てのビットが立っている場合は完璧にIndex Only
Scanである。しかし、そうでない場合は正しい結果を返すためにはまだテーブルに
アクセスする必要がある。

つまり、bitmapにbitが立っていればその行は返して問題ないですが、bitが立っていない
場合、改めてテーブルにアクセスし、その行を返して良いか判断する必要があります。

ということで、名前はIndex Only Scanですが、場合によっては完璧にIndex Onlyでは
ありません。それでも表の状態やクエリによってはこれまでのPostgreSQLでは出せなかった
パフォーマンスが出せる場合があり、楽しみな新機能であります。

さて、ここまで見てきた特徴を考えつつ、実際にIndex Only Scanがどのように使われるか
、またその効果はいかほどか、試してみたいと思います。

3.やってみた

環境　CentOS5　PostgreSQLは2011年12月4日時点のHEADです。

まずは単純にIndex Only Scanが有効そうなケースです。

テストしたスクリプトはこちら。

drop table test1;
CREATE TABLE test1 with(fillfactor=50) AS
SELECT g as col1,g as col2,md5(g::text) as col3,md5(g::text) as col4,md5(g::text) as col5 from generate_series(1,5000000) AS g;
CREATE INDEX test1_ind ON test1(col1,col2);
VACUUM ANALYZE test1;
explain analyze select col1,col2 from test1;

さて、実行結果をみてみましょう。

テーブルとインデックスのサイズの差を確認

- テーブルのサイズ　約1.4GB

postgres=# select pg_relation_size('test1');
pg_relation_size

- - - - -

1412415488
(1 row)

- インデックスのサイズ　約110MB

postgres=# select pg_relation_size('test1_ind');
pg_relation_size

- - - - -

112336896
(1 row)

- Index Only Scanを使ってのクエリ

postgres=# explain analyze select col1,col2 from test1;
QUERY PLAN

- - - - -

Index Only Scan using test1_ind on test1 (cost=0.00..129852.83 rows=5000002 width=8) (ac
tual time=0.039..2560.861 rows=5000000 loops=1)
Total runtime: 4415.536 ms
(2 rows)

- enable_indexonlyscan をOFFにして実行したクエリ

postgres=# explain analyze select col1,col2 from test1;
QUERY PLAN

- - - - -

Seq Scan on test1 (cost=0.00..222414.02 rows=5000002 width=8) (actual time=0.046..3340.1
68 rows=5000000 loops=1)
Total runtime: 5209.736 ms
(2 rows)

あれ、テーブルのサイズとインデックスのサイズは10倍以上違うはずなのに、10%程度の差しか出ません。
Robertの新しいblogを見るとこんな記述がありました。

If the index fits in memory but the table doesn't, the index-only scan comes
out way ahead, because it avoids hitting the disk, which is obviously a huge win.
indexはマシンに搭載しているメモリに乗り、テーブルは乗らない場合、Index Only Scan
は性能を発揮します。それはディスクへのアクセスを避けることができるからです。
この場合、明白にIndex Only Scanは大きく勝ります。

If the index fits in shared_buffers but the table doesn't, the index-only
scan still comes out significantly ahead, because buffer eviction isn't free.
Indexがshared_buffersに乗り、テーブルが乗らない場合は、Index Only Scan
は性能を発揮します。これはバッファのエイジアウトから開放されないためです。

If the table fits in shared buffers, and is actually fully resident in shared
buffers, it's faster to just sequentially scan it.
テーブルが shared_buffers に乗り、完全にshared buffer上から落ちない状況であれば
Sec Scanの方が速くなります。

ということで、インデックスのスキャンよりも、シーケンシャルスキャンの方が速く、
このくらいのサイズの差はそれほど大きなアドバンテージにはならないようです。

そこで、今回検証しているマシンはメモリが4G搭載しているのでOSキャッシュからも
落ちるようにテーブルのサイズを8Gにして、検証してみました。

drop table test1;
CREATE TABLE test1 with(fillfactor=50) AS
SELECT g as col1,g as col2,md5(g::text) as col3,md5(g::text) as col4,md5(g::text) as col5 from generate_series(1,30000000) AS g;
CREATE INDEX test1_ind ON test1(col1,col2);
VACUUM ANALYZE test1;
explain analyze select col1,col2 from test1;

- テーブルのサイズ　約8GB

postgres=# select pg_relation_size('test1');
pg_relation_size

- - - - -

8474484736
(1 row)

- インデックスのサイズ　約670MB

postgres=# select pg_relation_size('test1_ind');
pg_relation_size

- - - - -

673882112
(1 row)

- Index Only Scanを使ってのクエリ

postgres=# explain analyze select col1,col2 from test1;
QUERY PLAN

- - - - -

Index Only Scan using test1_ind on test1 (cost=0.00..779047.54 rows=30000000 width=8) (a
ctual time=29.482..24094.175 rows=30000000 loops=1)
Total runtime: 36060.251 ms
(2 rows)

- enable_indexonlyscan をOFFにして実行したクエリ

postgres=# explain analyze select col1,col2 from test1;
QUERY PLAN

- - - - -

Seq Scan on test1 (cost=0.00..1334483.00 rows=30000000 width=8) (actual time=7.694..9615
4.730 rows=30000000 loops=1)
Total runtime: 114663.807 ms
(2 rows)

今度はIndex Only Scanの方が310%ほど性能が上がっています。

このようなケースではIndex Only Scanが有効であることが分かります。

あと、お気づきの方もいらっしゃるかもしれないですが、このSQLにはWhere句はありません。
一見、Indexを使う必要性が無いようにも見えますが、countするだけであれば、indexだけを
数えれば良いので、このようにIndex Only Scanが使われることもあります。これまでの
PostgreSQLのチューニングとちょっと違うノウハウだと思います。

4.まとめ

・Index Only Scanは名前のとおり完全にIndexだけにアクセスするものではなく、
　必要な時は少しテーブルにもアクセスする。

・Index Scan よりSec scanの方が速いので有効に使えるケースは限られている。

・しかし、Index Only Scanの得意な状況になれば非常に強力な武器になりうる。

・これまでのPostgtreSQLでは一見Indexが使われないSQLでもIndexが有効なケースが
　現れることも！

ということで14日のAdvent Calenderでした！

明日15日のAdvent Calenderはshirouさんです^^