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さんです^^