SRA OSS は PostgreSQL 関連サービスを提供しているだけではなく、PostgreSQL の開発にも参加しています。過去には再帰SQLの実装や、ラージオブジェクトの64bit化などを行ってきました。
そして、最近は Incremental View Maintenance という機能の実装を提案することを検討しています（2018年12月末にPostgreSQL開発MLにて議論開始）。これはマテリアライズドビューの更新を高速に行うための技術です。PostgreSQLが大規模システムの採用が増加する中、マテリアライズドビューの利用は増えていると考えており、またその高速リフレッシュは喫緊の課題であると考えています。
これに関する発表を昨年の10月にポルトガルのリスボンで開催された PostgreSQL Conference Europe (PGConf.EU) 2018 で発表してきました（レポートはこちら）。本記事では、その内容について解説します。
ビュー、マテリアライズドビュー、そして IVM
通常のビューは、それを定義する SELECT クエリのみを持っていて、ビューに対する問い合わせが発生したときにはこのクエリが実行され、その結果がクライアントに返ります。マテリアライズドビューでは通常のビューと異なり、ビューを定義するときに問い合わせの結果がデータとして保存されます。これにより、マテリアライズドビューへの問い合わせが発生した時には、保存されている結果を使用することで高速な応答が可能です。PostgreSQL では 9.3 からマテリアライズドビューをサポートしています。
ただし、ビューの定義に含まれる実テーブルが更新された場合には、マテリアライズドビューに保存されている内容は古くなってしまいます。そのため、これを最新の状態に更新する必要が出てきます。これはビューのメンテナンスと呼ばれています。ビューをメンテンスする最も単純な方法は、マテリアライズドビューの内容を全て「再計算」することです。PostgreSQL にはこれを行う REFRESH MATERIALIZED VIEW という SQL コマンドが用意されており、これを実行するとビューを定義する SELECT クエリが再度実行され、その新しい結果でマテリアライズドビューの中にある古いデータが置き換えられます。
しかし大抵の場合、実テーブルの中で更新される行は、テーブル全体のごく一部だけのことがほとんどです。そのわずかな変更のために、マテリアライズドビューを一から作り直すのは出来れば避けたい所です。そこで、実テーブルに発生した更新差分を元に、マテリアライズドビューに発生する差分のみを計算して、これを適用することでマテリアライズドビューをメンテナンスすることを考えます。これが、Incremental View Maintenance（以下、IVM と呼びます）という考え方です。
Incremental View Maintenance（IVM） の概念図：通常のリフレッシュではビュー定義と更新後の実テーブルからマテリアライズドビューを作り直す（緑のルート）が、IVM では実テーブルに発生した差分からマテリアライズドビューの差分を計算し、これを適用する（赤のルート）。
OID を使用した IVM の実装
IVM はマテリアライズドビューを使用しているユーザにとって非常に有用な機能ですが、今の PostgreSQL ではサポートされていません。そこで、我々はこの機能の実装にチャレンジすることにしました。まずは、一緒に共同研究をしているお茶の水女子大学名誉教授の増永良文先生のアイデアを元に、テーブルの行 OID を使用した PoC（Proof of Concept, 概念実証: アイデアの実現可能性を評価するための試作）の実装を行いました。
基本的なアイデア
OIDを利用したIVM実装の基本的アイデア：ビューとテーブルの行OIDの対応付け（OID map）を持っていれば、実テーブルの行の更新がビューのどの行に影響を与えるかを知ることができる。
基本的なアイデアは以下の通りです。
この図は実テーブル devices と parts の JOIN 結果のマテリアライズドビュー V を表しています。それぞれの実テーブルとビューの行には、OID が付与されており、実テーブルとビューの OID の対応関係は OID map に保存されています。例えば、ビューの中で OID が 301 の行は、OID が 101 および 201 の行から生成されています。ここで、parts テーブルの OID が 201 の行が変更されたとします。この場合、 OID map を参照することで ビューの OID が 301 の行のみが影響を受けるのがわかります。つまり、再計算が必要なのはこの行だけで、他の行はそのまま残しておくことができるというわけです。
全体像
次の図は今回行った PoC 実装で行われる処理の全体像です。処理されるタイミングによって、大きく３つの部分に分けられています。
今回のPoC実装の全体像：ビュー定義時、テーブル更新時、ビューメンテナンス時の３つの処理に分けることができる。
１つは「ビューを定義」するときに行われる処理で、図ではオレンジの矢印で表されています。このタイミングでは、ビューを定義するクエリが実行されたマテリアライズドビューに格納されるデータが計算されるだけではなく、ビュー定義に含まれる実テーブルとビューの間の行 OID の関連付け（OID map の作成）や、実テーブル毎に「差分テーブル」と AFTER トリガの生成、および、マテリアライズドビューを更新するときに実行すべき「クエリスクリプト」の生成が行われます。
２つ目は「実テーブルが更新」された時の処理で、図では緑の矢印で表されています。この時、実テーブルに発生した差分が、それぞれの「差分テーブル」に格納されます。
最後は実際に「ビューのメンテナンス」、すなわち、マテリアライズドビューの更新を行うときの処理で、青の矢印で表されています。この時点で、ビュー定義時に生成しておいた「クエリスクリプト」が実行され、マテリアライズドビューの内容が最新に更新されます。
前提条件
この実装方法は 行 OID を使用するので、マテリアライズドビューの定義に含まれる実テーブルは、CREATE TABLE で定義されるときに WITH OIDS を使用するか、ALTER TABLE で WITH OIDS オプションを追加する必要があります。同様にマテリアライズドビューにも行 OID が保持しておく必要があるのですが、PostgreSQL の CREATE MATERIALIZED VIEW では WITH OIDS の使用はサポートされていません。そこで、今回の PoC 実装ではこの構文を改造して、WITH OIDS 付きのマテリアライズドビューを作成できるようにしています。
PoC 実装の詳細
ビューの定義時
マテリアライズドビューを定義する時に、ビューと実テーブルの行 OID の対応表が作成されます。ビューを定義する SELECT 文を実行している最中に、ビューのある１行を生成するために使用された実テーブルの行の OID が収集されます。そして、結果の行がマテリアライズドビューに挿入される時に、ビューの行 OID も取得します。その関連は pg_ivm_oidmap という名前のテーブルに保存されます。次の図はその例です。例えば、マテリアリズドビューの OID が 301 の行が、devices テーブルの OID が 101 の行と parts テーブルの OID が 201 の行から生成されたことなどが記録されています。
OIDマップ生成の例：devicesテーブルとpartsテーブルのJOINを行うビューの場合
また、この時にはビューを定義する SELECT クエリが解析され、そこに含まれる実テーブルが抽出されます。各実テーブルに対して、その差分を格納するための「差分テーブル」が作成されます。実テーブル１つごとに old と new の２つの差分テーブル作成され、その名前は pg_ivm_<実テーブルのOID>_old（または _new）となります。例えば、OID が 1111 の実テーブルの OLD 差分を格納するテーブルの名前は pg_ivm_1111_old です。さらに、各実テーブル上には AFTER トリガが作成されます。
その他、マテリアライズドビューを更新するときに実行すべき「クエリスクリプト」が生成され、これは pg_ivm_script というテーブルに保存されます。
実テーブルの更新時
差分テーブルの例：partsテーブルのpriceが10から15に変更された場合
実テーブルが更新された時には、そのテーブルに定義された AFTER トリガが発動します。このトリガの中では、OLD 差分と NEW 差分が取得され、それぞれ対応する pg_ivm_…_old テーブルと、pg_ivm_…_new テーブルに格納されます。OLD 差分には、テーブルから削除された行、および、更新によって置き換えられた行の古い内容が含まれます。また、NEW 差分には、テーブルに新しく挿入された行、および、更新によって置き換えられた行の新しい内容が含まれます。例えば、parts テーブル（OID は 2222）の price というカラムの値が 10 から 15 に更新された場合、price の値が 10 である古い行の内容は pg_ivm_2222_old に、price の値が 15 である新しい行の内容は pg_ivm_2222_new に格納されます。このとき、対応する行の OID も一緒に格納されます。なお、この機能は AFTER トリガの「遷移テーブル」の機能を使って実装しました。
同じ行が複数回更新された場合には、NEW 差分の内容を新しく更新することで対応しています。例えば、上記の例に続いて、parts テーブルの price カラムの値が 15 から 25 に更新された場合には、pg_ivm_111_new から price が 15 の行を削除し、代わりに price が 25 の行を挿入することで、古い更新差分の情報を上書きしています。
ビューのメンテナンス時
今回の実装では、ビューのメンテナンス、すなわちマテリアライズドビューの更新は、以下の SQL コマンドが実行された時に行うようにしました。
REFRESH MATERIALIZED VIEW INCREMENTALLY [view name];
この INCREMENTALLY というキーワードは今回の PoC 実装で行った拡張です。これが指定されているときには IVM すなわち、マテリアライズドビューの差分更新を行い、これが指定されなかった場合には通常のリフレッシュ、つまりマテリアライズドビューの作り直しを行います。
IVM が実行された場合には、pg_ivm_script テーブル内に保存されている「クエリスクリプト」が実行されます。具体的には、まずマテリアライズドビューから「古くなった行」を削除します。例えば、pg_ivm_2222_old テーブルに OID が 201 の行が含まれている場合、pg_ivm_oidmap に保存されている OID マップを参照することで、OID 301 の行をマテリアライズドビューから削除すべきことがわかります。
次に、マテリアライズドビューに新しい行を挿入します。これは、JOIN を行うビューの場合、実テーブルと実テーブルの NEW 差分テーブルの JOIN を実行することで求めることができます。例えば、devices テーブルと parts テーブルを JOIN するビューの場合、devices テーブルそのものと、parts テーブルの NEW 差分テーブルである pg_ivm_2222_new の JOIN によって生成された行がマテリアライズドビューに新しく挿入すべき行となります。
マテリアライズドビューに新しく挿入すべき行の計算の例。devicesテーブルとpartsテーブルのNEW差分のJOINを行う。
動作例
今回の PoC 実装の動作確認には pgbench で使用される２つのテーブル pgbench_acounts と pgbench_tellers を JOIN するマテリアリズドビューを用いました。
IVM を使用するマテリアライズドビュー mv_ivm は以下のように、WITH OIDS を使用して作成しました。２つのテーブルは bid カラムで結合し、WHERE 句には tid カラムの値に条件を指定しています。pgbench_acounts と pgbench_tellers には、予め ALTER TABLE で WITH OIDS オプションを追加してあります。
CREATE MATERIALIZED VIEW mv_ivm WITH OIDS AS SELECT a.aid, a.abalance, t.tbalance FROM pgbench_accounts a JOIN pgbench_tellers t ON a.bid = t.bid WHERE t.tid in (1,2,3) ;
また、比較のため、IVM を用いない通常のマテリアライズドビュー mv_normal を、以下のように WITH OIDS を使用せずに作成しておきます。
CREATE MATERIALIZED VIEW mv_normal AS SELECT a.aid, a.abalance, t.tbalance FROM pgbench_accounts a JOIN pgbench_tellers t ON a.bid = t.bid WHERE t.tid in (1,2,3) ;
なお、pgbench でテーブルを生成するときのスケールファクターは 500 を使用しました。この場合、pgbench_accounts の行数は 50,000,000、pgbench_tellers の行数は 5,000、結果となるマテリアライズドビューの行数は 300,000 となります。
性能評価
まず、最初に pgbench_accounts テーブルの１行のみを更新した場合を見てみます。
ivm_demo=# UPDATE pgbench_accounts SET abalance = abalance + 1 WHERE aid = 1;
UPDATE 1
Time: 9.749 ms
ivm_demo=# REFRESH MATERIALIZED VIEW mv_normal;
REFRESH MATERIALIZED VIEW
Time: 39979.546 ms (00:39.980)
ivm_demo=# REFRESH MATERIALIZED VIEW INCREMANTALLY mv_ivm;
REFRESH MATERIALIZED VIEW
Time: 537.591 ms
ivm_demo=# SELECT count(1) FROM (
(SELECT * FROM mv_normal EXCEPT SELECT * FROM mv_ivm)
UNION ALL
(SELECT * FROM mv_ivm EXCEPT SELECT * FROM mv_normal)) q;
count
-------
0
(1 row)
この場合、通常のマテリアライズドビュー mv_normal で REFRESH MATERIALIZED VIEW コマンドを使用した場合、およそ 40 秒ほど時間がかかりました。一方で、mv_ivm に対して REFRESH MATERIALIZED VIEW INCREMENTAL コマンドを使用して IVM を行った所、500 ミリ秒ほどしかかかりませんでした。通常のリフレッシュに比べると非常に速いことが確認できました。ここで最後に実行しているクエリは EXCEPT と UNION を使って２つのマテリアライズドビューの内容に差がないことを確認しています。つまり、IVM を利用した場合でも、正しくリフレッシュが行えていることを意味しています。
以下のグラフは、pgbench_accounts で更新する行数を 500 から 500,000 まで増やしていった場合に、IVM に要する時間の変化を表したものです。赤い線は、通常のリフレッシュを行った場合の所要時間を表しています。更新する行数が増えると IVM に要する時間も増える傾向にはありますが、この状況では IVM は通常のリフレッシュに比べて非常に速いことが見て取れます。
pgbench_accounts の更新行数に対する IVM 所要時間の変化
次に、pgbench_tellers テーブルの１行を更新した場合を見てみます。最初に tid = 5 の行を更新していますが、ビューの定義より、この行はマテリアライズドビューの内容に関わりのないことに注意してください。すなわち、ビュー定義の WHERE 句では tid IN (1, 2, 3) となっており、tid = 5 の行は含まれていません。この場合には、IVM は行うべき処理がほとんどないため、500 ms ほどですぐに完了しています。
一方、tid = 1 の行を更新した場合はどうでしょう。この場合には、19 秒ほど時間がかかってしまいました。
ivm_demo=# UPDATE pgbench_tellerss SET tbalance = tbalance + 1 WHERE tid = 5; UPDATE 1 Time: 10.007 ms ivm_demo=# REFRESH MATERIALIZED VIEW INCREMENTALLY mv_ivm; REFRESH MATERIALIZED VIEW Time: 512.998 ms ivm_demo=# UPDATE pgbench_tellers SET tbalance = tbalance + 1 WHERE tid = 1; UPDATE 1 Time: 9.201 ms ivm_demo=# REFRESH MATERIALIZED VIEW INCREMENTALLY mv_ivm; REFRESH MATERIALIZED VIEW Time: 19555.446 ms (00:19.555)
pgbench_tellers の行を更新した時に IVM に時間がかかる理由は、このビューでは pgbench_tellers の１行が pgbench_accounts の全ての行と JOIN されているためです。以下のグラフは、pgbench_tellers で更新する行数を 1, 2, 3 と増やしていった場合に、IVM に要する時間の変化を表したものです。赤い線は、通常のリフレッシュの所要時間です。行数を増やす毎に IVM の所要時間は大幅に増えていき、tid の値が 1, 2, 3 の３行全てを更新した場合には通常のリフレッシュの所要時間を上回ってしまいました。これは、OID マップのメンテナンスなど、今回の実装における IVM のオーバヘッドが現れたものと思われます。
pgbench_tellers の更新行数に対する IVM 所要時間の変化
このように、今回の PoC 実装では、ある場合にはIVM の効果は大きいが、逆にかえって時間がかかる場合もあることがわかりました。巨大のテーブルのごく一部が更新された場合には有効に働くように思われますが、それもビューの定義次第です。オーバーヘッドの少ない実装の工夫ももちろう必要ですが、もし通常のリフレッシュより IVM の方が時間がかかることが事前に推測できるのであれば IVM を使用せず通常のリフレッシュを行う、といった方法も考える必要があるでしょう。
おわりに
実意は今回の実装はあくまで PoC ということで非常に簡約に作られているため、多くの制約があります。例えば、ビュー定義としては２つのテーブルの単純な JOIN ビューしかサポートしておらず、テーブルの数が３つ以上になったビューや、集約やサブクエリを含むようなビューには対応していません。また、マテリアライズビューの作成や更新の際のクエリ実行で利用可能なプランの種類も限られており、例えばネステッドループやマージジョインは使えますがハッシュジョインには対応していません。
実装に OID を使っていること自体にも問題があります。実は PostgreSQL では次期バージョン以降で行 OID の廃止が決まっており、WITH OIDS を使ったテーブル定義ができなくなる予定です。そのため、今回の PoC 実装の方法は少なくともそのままでは使用できません。それ以外にも、OID を用いた実装には、OID マップのメンテンナンスのコストが大きいことや、実行プラン毎の対応が必要になるといった実装上の困難があります。そのため、OID に依存しない実装方法の調査研究も進めているところです。
このように、まだ IVM の実装は途上のプロジェクトで、本記事で紹介した内容とは異なる方法で進めていく可能性も高いのですが、今後は、PoC 実装で得た知見をベースにして、PostgreSQL 上での IVM の実装にむけ、コミュニティと議論しながら開発を進めて行く予定です。何かご意見がありましたら、どうぞよろしくお願いいたします。