PostgreSQLの開発に参加する人が増えるといいなぁと思っている須藤です。
自分たちが使うケースでPostgreSQLがいい感じの実行計画を使ってくれないことがわかったので、PostgreSQLを改良したいなぁと思っています。べつにここで宣言しなくてもちまちま進めるのですが、もし、興味がある人（PostgreSQLの開発に参加したいけど題材が見つからなくて手を動かせずにいる人とか）がいればその人と一緒に取り組めるといいなぁと思ってまとめることにしました。そうすれば、PostgreSQLの開発に参加する人を増やす機会になるんじゃないかと思うからです。
ここにまとめた内容を読んで、一緒にやってみたいと思った人は連絡してください。うーん、どうやって連絡してもらうのがいいかな。そうだなぁ、PGroongaのチャットがあるのでそこから連絡してください。
対象ケース
まず、どんなケースでいい感じの実行計画を作ってくれないかを説明します。
次のようなメッセージを格納するテーブルがあります。各メッセージにはIDが振ってあり、このIDは増加する一方です。つまり、大きいほど新しいメッセージになります。
CREATE TABLE messages (
id serial,
content text
);
このメッセージに対してcontentで絞り込み、新しい方から10件返すケースがいい感じの実行計画を作ってくれないケースです。
それでは、どんな実行計画を作って欲しいかを説明します。
次のようなマルチカラムインデックスを用意します。
CREATE INDEX messages_index ON messages (content, id);
次のようにテストデータを用意します。contentがaのメッセージが100件、bとcもそれぞれ10000件のデータです。
INSERT INTO messages (content)
SELECT content FROM (SELECT 'a' AS content, generate_series(0, 9999)) AS values;
INSERT INTO messages (content)
SELECT content FROM (SELECT 'b' AS content, generate_series(0, 9999)) AS values;
INSERT INTO messages (content)
SELECT content FROM (SELECT 'c' AS content, generate_series(0, 9999)) AS values;
これに対して次のように検索します。contentがbのメッセージを新しい順に10件取得するSELECTです。
SELECT * FROM messages
WHERE content = 'b'
ORDER BY id DESC LIMIT 10;
いい感じの実行計画は次のようになります。インデックスがcontent='b'で絞り込みつつidで逆順にソートした結果を順に返します。この実行計画の場合はインデックスが10件返せばそれで必要な結果が得られるのでとてもいい感じです。
Limit (cost=0.29..26.33 rows=10 width=36)
-> Index Only Scan Backward using messages_index on messages (cost=0.29..390.91 rows=150 width=36)
Index Cond: (content = 'b'::text)
で、組み込みのbtreeインデックスを使うとこの実行計画になります。
しかし、拡張機能として追加したインデックスではこうなりません。拡張機能として実装されているインデックスの代表的なもの（？）はPGroongaです。PGroongaは全文検索ができるインデックスですが、btreeインデックスのようにソートした結果を返すこともできます。
たとえば、次のようにWHEREがない単純なケースでは前述のいい感じの実行計画になります。インデックスでソートして順に10件取得して終わり、です。
DROP INDEX IF EXISTS messages_index;
CREATE INDEX messages_index ON messages USING PGroonga (id);
EXPLAIN
SELECT * FROM messages
ORDER BY id DESC LIMIT 10;
-- QUERY PLAN
-- -----------------------------------------------------------------------------------------------------
-- Limit (cost=0.00..0.28 rows=10 width=36)
-- -> Index Scan Backward using messages_index on messages (cost=0.00..832.00 rows=30000 width=36)
-- (2 rows)
しかし、WHEREを追加するとそうなりません。
WEHRE用にcontentもインデックス対象にします。
DROP INDEX IF EXISTS messages_index;
CREATE INDEX messages_index ON messages
USING PGroonga (content, id);
このときの実行計画は次のようになります。
Limit (cost=511.24..511.27 rows=10 width=36)
-> Sort (cost=511.24..511.62 rows=150 width=36)
Sort Key: id DESC
-> Seq Scan on messages (cost=0.00..508.00 rows=150 width=36)
Filter: (content = 'b'::text)
シーケンシャルスキャンを無効にしてみましょう。
SET enable_seqscan = no;
それでもこうなります。インデックスでヒットするレコードを全部見つけてから、（インデックスは使わずに）ソートしています。
Limit (cost=511.28..511.30 rows=10 width=36)
-> Sort (cost=511.28..511.65 rows=150 width=36)
Sort Key: id DESC
-> Bitmap Heap Scan on messages (cost=0.04..508.04 rows=150 width=36)
Filter: (content = 'b'::text)
-> Bitmap Index Scan on messages_index (cost=0.00..0.00 rows=30000 width=0)
この実行計画ではヒット数が多くなるほど遅くなりやすいのであんまりいい感じではありません。
なお、この説明は実際のケースを単純化したものです。実際のケースはZulipというチャットツールでのケースです。ZulipはデータストアにPostgreSQLを使っています。オプションでPGroongaを使うこともできて、PGroongaを使うと高速にメッセージを探せます。Webサイトの検索やファイルサーバーの検索では検索クエリーにマッチする度合いで並び替えることが多いですが、チャットツールは時間順に並び替えます。そのため、全文検索してメッセージ投稿順に並び替える使い方になります。
このあたりのことをZulipの開発者と私で調べていたときのissueがzulip/zulip#9595で、結論がPostgreSQLがいい感じの実行計画を作ってくれないです。
Zulipはクリアコードの社内のチャットツールとして使っています。クリアコードはユーザーが自由に使えるソフトウェアを大事にしているのですが、Zulipを選んだのはZulipが自由に使えるソフトウェアだからです。自由に改造できるのでPGroongaサポートを追加して使っています。
PostgreSQLもユーザーが自由に改造できるソフトウェアなので今回のケースもいい感じにできるようにPostgreSQLを改良したいと思っています。
改良方法
どうやって改良するとよさそうか少し調べたので記録を残しておきます。あとで自分で取り組むときにも役に立ちそうですし。
インデックススキャンを使った実行計画はsrc/backend/optimizer/path/indxpath.cのbuild_index_paths()で作られます。
ソート済みのインデックススキャンを使う実行計画は↓らへんで作られるのですが、index_is_orderedが真にならないと作られません。で、真になるためにはindex->sortopfamilyが設定されないといけません。
index_is_ordered = (index->sortopfamily != NULL);
if (index_is_ordered && pathkeys_possibly_useful)
どういうときにindex-sortopfamilyが設定されるかというのはsrc/backend/optimizer/util/plancat.cのget_relation_info()を見るとわかります。
1つ目のパターンはbtreeを使っているときです。特別扱いです。
if (info->relam == BTREE_AM_OID)
{
/*
* If it's a btree index, we can use its opfamily OIDs
* directly as the sort ordering opfamily OIDs.
*/
Assert(amroutine->amcanorder);
info->sortopfamily = info->opfamily;
2つ目のパターンはamcanorder（インデックスを登録するときに拡張機能で設定できる項目の1つで、このインデックスはソートできるよ！というのを示す設定）が設定されているときです。つまり、btree以外のインデックスでもソート済みのインデックススキャンをできるようにするためのところです。
else if (amroutine->amcanorder)
この中でさらにチェックがあります。使っている演算子がbtreeの比較演算子と同じ演算子か、というチェックです。同じならソート済みのインデックスキャンできる扱いにしています。
ltopr = get_opfamily_member(info->opfamily[i],
info->opcintype[i],
info->opcintype[i],
BTLessStrategyNumber);
if (OidIsValid(ltopr) &&
get_ordering_op_properties(ltopr,
&btopfamily,
&btopcintype,
&btstrategy) &&
btopcintype == info->opcintype[i] &&
btstrategy == BTLessStrategyNumber)
{
/* Successful mapping */
info->sortopfamily[i] = btopfamily;
}
ということで、ここをもっと賢くするといい感じの実行計画を作れそうです。
まとめると次の通りです。
-
btreeが
WEHREがあるケースでもないケースでもいい感じの実行計画になるのはget_relation_info()でbtreeが特別扱いされているから -
PGroongaが
WHEREがないケースではいい感じの実行計画になるのはソートの時は暗黙的に演算子として<が使われ、get_relation_info()では<があるときはソートできる扱いになっているから -
PGroongaが
WHEREがあるケースでいい感じの実行計画にならないのは、get_relation_info()のチェックで=が条件を満たせないから
テスト方法案
今の実装でbtree決め打ちになっているところがあるのは、組み込みのインデックスでamcanorderなインデックスがbtreeしかないからです。そのため、既存のインデックスを使って期待した動きになっているかを確認するテストを書くのは難しいです。
次の2つでテストするのがよいのではないかと考えています。
-
btreeに特化した処理を汎用性のある実装に置き換えてもPostgreSQLの既存のテストが動くようにする
- 基本的にテストを追加しない
-
PGroongaにテストを追加し、汎用性のある実装に書き換えたPostgreSQLならPGroongaでも期待した実行計画になることを確認する
btreeだけでテストしていると本当に汎用的な実装になっているか確認漏れがでやすいので、PGroongaというbtreeではないインデックスでも確認するといいんじゃないかという案です。
まとめ
Zulipでよく使うパターンでPostgreSQLがいい感じの実行計画を作れないので作れるようにPostgreSQLを改良したいという話をまとめました。どういうケースで発生するかと、どのあたりから改良していけばいいかもまとめたので、一緒にやりたくなった人はPGroongaのチャットで連絡してください。一緒にPostgreSQLの開発に参加しましょう。
