Friday, December 19, 2014

GINインデックスの進化 - PostgreSQL9.4

この記事はPostgreSQL Advent Calendar 2014の12/19担当分です。
昨日の12月18日、ついにPostgreSQL9.4がリリースされました!!

0. はじめに
PostgreSQL9.4では様々な新機能が組み込まれたほか、既存機能の進化もありました。 その中でも全文検索等に使われる”GINインデックス”では、
  1. インデックスサイズの縮小
  2. 特定ケースでの検索速度向上
の2つの大きな進化がありました。
本記事では、これらの内容について具体的にどのような改善があったかをご紹介いたします。GINインデックスって?全文検索って? という方はこちら(pg_bigmを用いた全文検索のしくみ)をご参照ください。

1. インデックスサイズの縮小
9.4ではGINインデックスサイズが大幅に縮小されました。
”varbyteエンコーディング”といわれる圧縮方法を用いて、GINインデックスのPostingListを圧縮することでインデックスサイズの縮小を実現しています。ざっくり書くと下図のようになります。


9.3までのPostingListの各要素にはタプルのctid(ブロック番号とオフセット番号)が記録されていたのに対し、9.4のPostingListの各要素には"一つ前の要素からの差分"が記録されています。このようにすることで、上記の例では19bytesの圧縮が実現しています。
そして、”ひとつ前の要素の差分”を記録する際の”差分”は以下のように表しています。

  • 1 - 6Byte(s)で差分を表現
  • 最初の10bitはオフセット番号、残りはブロック番号で使用
  • 各1Byteでは127までの数字を表すことができる
  • 128以上の数字は第8ビット目を1にする
  • 「第8ビット目が1」= 「次の1byteも含めてサイズを計算する
例えば、
127 = 01111111
128 = 11111111 00000001
という感じ。

2. 特定ケースでの検索速度向上
全文検索では検索キーワードを元にいくつかのキー生成します。そして、キーを元にGINインデックスを検索し、各キーのPostingListの内容を照らしあわせて、結果を返します
(たとえば、pg_bigmでは検索キーワードを2文字ずつ一文字ずらしながらキーを生成します)。これまでは、各PostingListすべてにマッチしたタプルを見つける際に、タプルのctidが最小のものから順番にすべてのctidについて判別を行っていました。


しかし、例えば上記のケースの場合、”と京”にぶら下がっているPostingListには2つしか要素が無いため、すべてのctidについて判別していく必要はありまあせん。上記のような場合は”一番要素数の少ないPostingListのctid”だけ(上記例の場合は(1,2)と(2,1)のみ)をチェックすれば無駄な処理をスキップすることができます。


9.4からは上図のように、各キーが持つPostingListの要素数の”一番少ないPostingList”を元に結果を判別していきます。この変更がGINインデックスの検索性能を向上させたました。ただすべての検索において劇的な向上があったわけではなく、特に「稀なデータとよく出るデータを含んだ検索」をする時がこの改善効果が大きく出ます。

3. まとめ
PostgreSQL9.4のGIN改善内容の紹介はいかがでしたでしょうか?圧縮によりインデックスサイズも小さくなり、検索性能も向上しました。また、9.4に新しく追加されたJSONB型もGINインデックスと組み合わせることで検索性能を向上させることができます。9.4の正式にリリースされたので、今後のGINインデックスのさらなる発展を期待しながら使ってみましょう!
(まさか9.4リリースの次の日の担当になるとは。たまたま新機能についてと書こうと思ってたからよかった。)

明日のPostgreSQL Advent Calendar 2014はkwatchさんです。よろしくおねがいします!