PostgreSQLにおけるPAXページレイアウトの実装

PostgreSQL

この記事は PostgreSQL Advent Calendar 2014 の12月24日担当分です。

筑波大学情報科学類の情報特別演習（担当：川島先生、対象は2年生 or 3年生）で「PostgreSQLにPAXを実装」というテーマがありましたのでやってみました。中途半端で拙い内容ですが、そのご報告を致します。コメントやアドバイスを頂けたら嬉しいです。

ページレイアウト

RDBMSのデータはテーブルとしてモデル化されています。テーブルには縦と横があるので二次元とみなすことができます。一方、ストレージ中のアドレス空間は一次元です。そのため、ストレージにデータを格納するには、テーブルを縦に切るか、あるいは横に切るかする必要があります。横に切るページレイアウトはNSM (N-ary Storage Model）と呼ばれ、縦に切るページレイアウトはDSM（Decomposition Storage Model）と呼ばれます。PostgreSQLはNSMを採用しています。

PAXレイアウト

さて、NSMを用いるとScan処理等においてCPUキャッシュ使用率が低くなるために性能が劣化する可能性があることが、2001年にWeaving Relations for Cache Performanceで指摘されました。この論文の著者らはNSMとページコンテンツは同一（但し属性数と行数が同じ場合のみ）だがページ内のレイアウトがDSMライクになっているPAXというページレイアウトを提案しています。PAXを用いればCPUキャッシュミス率をNSMに比して削減できることが論文中に示されています。当時はDBMSのボトルネックといえばI/Oのみが考えられていたのにCPUキャッシュミスが新しいボトルネックになる点を未来に先駆けて示した点で、この論文は示唆に富んでいると思います。PAXには性能改善だけでなく、実装が容易であることが述べられています。著者の発表資料（10枚目）には "low-implementation-cost, high-impact" と述べられており、先般の論文（2ページ、第二段落）には次のように記載されています。

"Finally, PAX has several additional advantages. Implementing PAX on a DBMS that uses NSM requires only changes to the page-level data manipulation code.
PAX can be used as an alternative data layout, and the storage manager can decide to use PAX or not when storing a relation, based solely on the number of attributes."

Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, and Marios Skounakis. 2001. Weaving Relations for Cache Performance. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB '01), Peter M. G. Apers, Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Kotagiri Ramamohanarao, and Richard Thomas Snodgrass (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 169-180.

実装例の調査

そうすると実装は簡単なのかなぁと思いました。でも色々探したのですが、PostgreSQLにおけるPAX実装のコードを見つけることができませんでした。こちらの先生の授業でこちらの方が実装していたようですが、詳細な資料がありません。また、A hybrid page layout integrating PAX and NSMとQuery processing techniques for solid state drivesでは実装しているようですが、やはり詳細な資料がありません。仕方がないので自力で作ることになりました。

実装

select id from test_32 where age = 20;

を対象問合せとしました。この問合せは実行プランになると下記のようになります。

                       QUERY PLAN
--------------------------------------------------------
 Seq Scan on test_32  (cost=0.00..16.38 rows=3 width=4)
   Filter: (age = 20)

この一番下の演算子はExecSeqScanです。ExecSeqScanの主たる動作モジュール(workhorse)はSeqNextです。この中に次の記載がありました。

 66         tuple = heap_getnext(scandesc, direction);

そのため、heap_getnextを辿ってみました。この中には heapgettup と heapgettup_pagemode があります。今回はページアクセスをしますので、heapgettup_pagemodeを辿ってみました。

ここで残念なことに気づきました。下記から明らかなようにタプルのデータはページ内データへのポインタとなっていたのです。下記の場所でページ内タプルへのポインタが与えられた後、ExecQualまでこのポインタは保持され、ExecQualでようやくselection operatorが処理される実装になっていました。このためにページはまずpin downされ、クエリプロセスが終わった段階でpin upされる模様です。これには驚きました。なぜならば高性能化のために selection operator が物理的なオペレータの最下層まで push down されることは常識だと思っていたからです。つまり下記の場所においてselectionが実行され、その結果が真となるタプルへのポインタのみが与えられるのだと思っていました。PAX実装の戦略として、PAXページのスキャン結果が真となるタプルを動的に構成してt_dataに与えようと思っていましたので、これには困りました。

 831                 tuple->t_data = (HeapTupleHeader) PageGetItem((Page) dp, lpp);

そこでPostgreSQLのデフォルト実装（NSM）において t_data を malloc & memcpy することにしました。PAXにおいても同様にしました．これによりPAXと同等な比較ができるようになったと考えています。

コード

作った結果をこちら (Github)に掲載しました。

性能

利用したPostgreSQLのバージョンは9.3.5です。キャッシュミス測定ツールにはPAPIを利用しました。性能測定ツールとしては oprofile, operf, perf, vTune, PAPIを試してみました。その結果vTuneとPAPIが類似した結果を示しました。他の方にこの結果を追試して頂くことを考えまして
PAPIを採用しました。PAPI周りのコードはexecMain.cのstandard_ExecutorRun()内に埋め込みました。CPUはIntel(R) Core(TM) i7-2760QM CPU @ 2.40GHzです。実験結果を下記に示します。

実験結果（結果タプル数が4、"select id from test_32 where age = 20"、10回の平均）
Layout L1D Cache Miss
NSM 571.2
PAX 606.4

Layout L2D Cache Miss
NSM 347.5
PAX 358.5

Layout L3 Total Cache Miss
NSM 406.6
PAX 355
実験結果（結果タプル数が1、"select id from test_32 where age = 20 and sc10 = 19"、10回の平均）
Layout L1D Cache Miss
NSM 580.2
PAX 634.1

Layout L2D Cache Miss
NSM 345.7
PAX 355.8

Layout L3 Total Cache Miss
NSM 327.7
PAX 336.2

結果タプル数が4の場合，L3（Last Level Cache）においてはPAXのキャッシュミス率が少しだけ低くなる現象を観察できました。しかし結果タプル数が1の場合にはPAXはNSMに負けています。これは不要なExecQual処理を行うためだと考えています。つまりデフォルトではExecQualでselection処理を行うのですが、我々のPAX実装ではもっと深部で行いますのでExecQualは不要です。しかし整合性のためにExecQualを残してあるので、無駄な処理が行われてしまいます。この問題は本日までに解決できませんでした。

問題

現状の実装には少なくとも下記の問題があることがわかっています。これらの問題を今後、検討して行きたいと思います。

  1. メモリ確保：PostgreSQLは一番下のレイヤーでmallocをしませんが、今回は実装の都合上mallocをしてしまいました．属性アドレス変換アルゴリズムを構築すればこの問題は解決できるかもしれません。Weaving Relations for Cache Performanceには "To reconstruct a record one needs to perform a mini-join among minipages, which incurs minimal cost because it does not have to look beyond the page" 等と書いてありますのでタプル再構成がPAXでは基本なのかもしれませんが、少なくともPostgreSQLでタプル再構成方式は不適切だと思います。ちなみに論文が発表された頃のPostgreSQLのコードも同様です。Shoreだと事情が異なるのかもしれません。
  2. 不要なExecQual：PAX実装ではExecQualでselection evaluationをする必要はありません。しかし現実装ではそれを行ってしまっているので無駄なオーバーヘッドになってしまっています。この無駄な処理をなくせば PAX の性能はもっと向上するように思います。
  3. カラム数：カラム数が増えるとミニページが増えます。ミニページがkのときに必要なポインタ数（ページヘッダー内）はkとなります。従ってミニページが多いとNSMよりも必要なデータ容量が増えてしまいますので、I/O回数が増大して性能が劣化するように考えられます。この問題をどうやって解決するべきか、現状ではアイディアはありません。

感想

  1. PostgreSQLは selection pushdown をもっと真面目に実装すべきだと思います。このままでは Big Scan 時に性能が悪くなります。
  2. PostgreSQLにPAXを実装することは不自然なように感じています。Read only DBMSであり、バッファ容量を2倍使って良いならば、PAXページを横に準備しておいて、それを用いたselection結果のNSM内タプルへのポインタを返すという実装方式がありえます。最初はこの方式で実装しました。しかしPostgreSQLは主記憶DBではないし空間性能悪化率に対する時間性能改善率がかなり悪いので、この実装方式について私は否定的です（但し性能は明確に向上しました）
  3. 私にとってはPAXの実装は簡単じゃなかったです。Weaving Relations for Cache Performanceの著者にとっては簡単らしいので凄いプログラマーだな～と思いました。