株式会社クリアコード > ククログ

ククログ


PGroongaでのJSON検索の実装方法

PGroonga(ぴーじーるんが)はPostgreSQLから全文検索エンジンGroonga(ぐるんが)を使えるようにするためのPostgreSQLの拡張機能です。PGroongaを使うとPostgreSQLに格納したデータに対して高速な全文検索を実現できます。PostgreSQLは標準では日本語テキストを全文検索できません。LIKEでシーケンシャルサーチする必要があり、レコード数・テキストサイズが増えるほど性能が劣化します。PGroongaを導入することで大量の日本語テキストデータに対しても高速に全文検索できます。

さて、そんなPGroongaですが、2015年9月29日(肉の日)にリリースされた0.9.0からjsonb型をサポートしました。サポートしたというのはjsonb型のデータをインデックスを使って高速に検索できるようになったということです。

jsonb型というのはPostgreSQLでJSONを保存するための型の1つです。JSONを正規化する点が特徴で、生のJSONよりも扱いやすいです。

たとえば、JSONでは次の2つはどちらも正しいです。

{
  "a": 1,
  "a": "b"
}
{
  "a": "b"
}

RFC 7159の「4. Objects」には次のように名前は一意である「べき」としているだけだからです。

The names within an object SHOULD be unique.

その後の説明には、名前が重複している場合の挙動は実装依存だと書いてあります。

When the names within an object are not unique, the behavior of software that receives such an object is unpredictable. Many implementations report the last name/value pair only. Other implementations report an error or fail to parse the object, and some implementations report all of the name/value pairs, including duplicates.

jsonbは正規化処理の中で名前を一意にする(最後の名前と値のペアだけを使う)処理もあります。そうすると、扱うときは名前が重複しているかも!?と考えずに済むので扱いやすいのです。

この記事では、PGroongaでどうやってjsonb型をサポートしているかを説明します。まず、何ができるのかを説明し、その後、実現方法を説明します。

できること

PGroongaではjsonb型のデータに対してインデックスを使って次の検索をできます。

  • 指定したjsonb型のデータを含んでいるレコードを検索
  • 指定したキーの値に対する完全一致検索
  • 指定したキーの値に対する範囲検索(a)
  • 指定したキーの値に対する全文検索(a)(b)
  • 全部の値に対する完全一致検索
  • 全部の値に対する範囲検索(a)
  • 全部の値に対する全文検索(a)(b)

PostgreSQLが提供する機能(GINとjsonb_ops)を使ってjsonb用インデックスを作成した場合、「(a)」と書いている操作は実現できません。

JsQueryという拡張機能を使うとPostgreSQLが提供する機能を使う場合よりも高度な検索を実現できますが、それでも「(b)」と書いている操作(全文検索)は実現できません。

このように、PGroongaを使うとjsonb型のデータに対して、既存の機能よりもより高度な検索をインデックスを使って高速に実現できます。

なお、あらかじめ全文検索対象の値が入っているキーがわかっている場合は、式に対するインデックスを使うことでjsonb型のデータの値に対して全文検索できます。

参考までに、それぞれの検索がどのような検索になるか例を示します。

指定したjsonb型のデータを含んでいるレコードを検索

検索対象のJSONとして次の2つのJSONがあるとします。

{"a": "hello", "b": "world"}
{"a": "hello", "c": "world"}

クエリーが次の場合は両方ヒットします。どちらもトップのオブジェクトに「a」というキーがあり、その値が「"hello"」だからです。

{"a": "hello"}

クエリーが次の場合は「{"a": "hello", "b": "world"}」だけヒットします。もう片方はトップのオブジェクトに「b」というキーが存在しないからです。

{"b": "world"}
指定したキーの値に対する完全一致検索

この検索は「指定したjsonb型のデータを含んでいるレコードを検索」のサブセットなので省略します。

指定したキーの値に対する範囲検索(a)

検索対象のJSONとして次の2つのJSONがあるとします。

{"code": 200}
{"code": 300}

code」の値が200番台という条件で検索できるということです。「200 <= code < 300」という条件で検索できるイメージです。この場合は{"code": 200}だけがヒットします。

指定したキーの値に対する全文検索(a)(b)

検索対象のJSONとして次の2つのJSONがあるとします。

{"message": "サーバーが起動しました"}
{"message": "サーバーがダウンしました"}

message」の値に「起動」というテキストを含むかという条件で検索できるということです。この場合は{"message": "サーバーが起動しました"}だけがヒットします。

全部の値に対する完全一致検索

検索対象のJSONとして次の2つのJSONがあるとします。

{"code": 200}
{"codes": [200]}

JSONのどこかに「200」という数値があるかという条件で検索できるということです。この場合はどちらにもヒットします。「200」がどこにあるかは問わないからです。

全部の値に対する範囲検索(a)

検索対象のJSONとして次の2つのJSONがあるとします。

{"code": 200}
{"codes": [299]}

JSONのどこかに200以上300未満という数値があるかという条件で検索できるということです。この場合はどちらにもヒットします。最初のJSONには「200」があり、2つめのJSONには「299」があるからです。

全部の値に対する全文検索(a)(b)

検索対象のJSONとして次の2つのJSONがあるとします。

{"message": "サーバーが起動しました"}
{"tags": ["起動失敗"]}

JSONのどこかに「起動」というテキストを含む値があるかという条件で検索できるということです。この場合はどちらもヒットします。最初のJSONは「"起動しました"」に「起動」が含まれていて、2つめのJSONは「"起動失敗"」に「起動」が含まれているからです。

実現方法

だいぶ前置きが長くなりましたが、このような検索をインデックスを使って高速に実現するためにどのように実装しているかを説明します。

ポイントは次の2点です。

  • JSONの値をそれぞれ1つのデータとして分割する
  • 内部で複数のインデックスを組み合わせる

まず、それぞれ1つのデータとして分割するということについて説明します。

次のJSONを考えます。

{"a": "hello", "b": "world"}

このJSONには「"hello"」と「"world"」という2つの値があるので、次のように2つのデータに分割します。ABという書き方は「Aというパスの値はBだよ」ということを示したつもりです。

  • .a"hello"
  • .b"world"

Groongaにはストレージ機能があり、RDBMSのようにテーブルを作り、そこにレコードを保存することができます。PGroongaはそれぞれの値を1つのレコードとして保存します。このレコードを保存しているテーブルを「Valuesテーブル」と呼んでいます。

今回の例だと次のようなレコードを保存するということです。

id path string
1 .a "hello"
2 .b "world"

これだけだとJSONの値は見つけられてもその値を持っている(PostgreSQLの)レコードを見つけることができません。そのため、もう1つテーブルを作ります。「Sourcesテーブル」と呼んでいるもので、インデックス対象のデータを管理しています。このテーブルのレコードがインデックス対象のレコードに対応します。このSourcesテーブルの各レコードにValuesテーブルへの参照を格納します。元のJSONがどの値から成り立っていたかを示しています。

なお、Valuesテーブルへの参照にはGroongaのベクター型のカラムを使います。これは、PostgreSQLでいう配列型です。

今回の例では次のようなレコードを保存するということです。valuesカラムの中に入っている12も前述のValuesテーブルのレコードのIDです。(ctidというのはPostgreSQL特有のIDでデータの実体を識別するIDのようなものだと思ってください。)

id ctid values
100 [1,1] [1, 2]

あとは、次のような流れで検索できるようにするだけです。

  1. Valuesテーブルから検索(たとえば、「.aカラムの値が"hello"」という完全一致検索)
  2. 1.で見つかったレコードをvaluesカラムに持つレコードをSourcesテーブルから検索
  3. 2.で見つかったレコードからctidカラムの値を参照し、PostgreSQLのレコードを特定する

この、1.と2.を高速に実現するために「内部で複数のインデックスを組み合わせる」ということをしています。

まず、Valuesテーブルを考えます。

id path string
1 .a "hello"
2 .b "world"

.aカラムの値が"hello"」という完全一致検索をするためには「path == "." && string == "hello"」という条件を評価すればよいことになります。そして、これを高速に実現するためにpathstringにインデックスを用意します。

これで、「1. Valuesテーブルから検索」を高速に実現できるようになります。

次に、「2. 1.で見つかったレコードをvaluesカラムに持つレコードをSourcesテーブルから検索」を高速に実現するためのインデックスを用意します。

これは、Valuesテーブルにインデックスカラムindexを追加します。indexにはこのレコードを参照しているSourcesテーブルのレコードのIDのリストが入ります。(インデックスカラムは転置インデックスでレコードのIDのリストはポスティングリストだと言えばわかる人にはわかります。)

今の例ではどちらの値もSourcesテーブルのID100のレコードから参照されているので、どちらも[100]になります。

id path string index
1 .a "hello" [100]
2 .b "world" [100]

この情報があると、「2. 1.で見つかったレコードをvaluesカラムに持つレコードをSourcesテーブルから検索」を高速に実現できます。なぜなら、indexカラムに入っているレコードIDのリストが求めるものだからです。

今の例ではValuesテーブルの次のレコードがヒットしています。

id path string index
1 .a "hello" [100]

このレコードを含んでいるSourcesテーブルのレコードは100だけです。なぜなら、index100だけが入っているからです。

Sourcesテーブルのレコードが見つかったら「3. 2.で見つかったレコードからctidカラムの値を参照し、PostgreSQLのレコードを特定する」は簡単です。ctidカラムの値を返すだけだからです。

今の例だと[1,1]を返すだけです。

id ctid values
100 [1,1] [1, 2]

このように、次の2つを組み合わせてjsonb型の値を高速に実現できるようにしています。

  • JSONの値をそれぞれ1つのデータとして分割する
  • 内部で複数のインデックスを組み合わせる

この実現方法の利点

この実現方法の利点を説明します。

この実現方法ではJSONそのものをそのまま検索しません。JSON内のそれぞれの値を別のレコードに分割し、それぞれの値に絞って検索します。これが範囲検索や全文検索といった高度な検索を使える理由です。

たとえば、先ほどの例では次のように値を保存しています。

id path string
1 .a "hello"
2 .b "world"

JSONは構造がネストしているため、条件を指定することが困難ですが、これは表になっているので、path == ".a" && string == "hello"と条件を指定できます。演算子を変えてstring @ "hello"とすれば簡単に全文検索をすることができます。(Groongaでは@は全文検索の演算子です。)

数値ならnumber > 100 && number < 200とすれば範囲検索になります。

また、単なる表なので、いつも通りインデックスを用意できます。操作に合わせたインデックスを作ればその操作を高速に実現できるというわけです。たとえば、文字列の前方一致検索をできるインデックスを用意すれば高速に文字列を前方一致検索できます。

この「表である」ということには別の利点もあります。JSONのどこにある値か関係なく検索できるという点です。

.aにある"hello"という値」という条件は「path == ".a" && string == "hello"」となりますが、pathを条件に加えなければ「どこにあってもいいけど"hello"という値」という条件「string == "hello"」となります。

JSONで値を格納したいということは、データの構造がブレることがある場合が多いでしょう。そのとき、「どこのキーかは問わないけど○○というキーワードを含んでいるJSONを全文検索」とできたら便利ではないでしょうか?

これもpathを条件に含めずに「string @ "○○"」とすれば実現できます。

この実現方法の欠点

この実現方法の欠点はディスク使用量が多いことです。

値を分解してGroongaに保存しているので、PostgreSQLが持っているデータを2重に持っています。

また、1つのJSONには複数の値があるので、Valuesテーブルのレコード数が多くなります。これもデータが増える原因になります。

ただし、少しでもValuesテーブルのサイズを小さくする工夫はしています。違うJSONの中に、同じパスで同じ値がある場合は同じValuesレコードを共有します。多くの場合、ある程度同じ構造や同じ値がでてくると予想していて、この工夫は効果があると期待しています。

たとえば、Webサーバーのログを考えます。次のようなJSONがたくさん保存されることでしょう。

{
  "code": 200,
  "path": "/"
}
{
  "code": 200,
  "path": "/favicon.png"
}

.codeに注目してください。値がすべて200です。HTTPのステータスコードは200404500などよく使われる値に偏ります。同じパスで同じ値のときにValuesレコードを共有すると.code200という値は共有できます。このようにValuesテーブルの肥大化を防ぐ工夫をしています。

説明しなかったこと

説明を単純にするために文字列型の値だけを例にして説明しました。JSONでは文字列型以外に数値型と真偽値型があります。それらをどう扱っているかの説明は省略しました。

また、JSON内の配列をどう扱っているか、パスをより簡単に指定するための工夫も省略しました。

実はpathカラムにはもう少し違う形でパスが入っているということの説明も省略しました。

速度面についても説明していません。

使い方(SQLの書き方)についても説明していません。

まとめ

PGroongaは0.9.0でjsonb型の検索をサポートしました。そして、その実現方法を説明しました。

興味がでてきた方はドキュメントを参考にして使ってみてください。使い方(SQLの書き方)を説明しています。

わからないことがあったらGitHubのissueメーリングリストチャットで質問してください。

ある程度大きなデータで性能を測定し、それを公開してくれると大変励みになるのでよろしくおねがいします。

2015-09-30

«前の記事: クリアコードとフリーソフトウェアとビジネス 最新記事 次の記事: Firefox 38以降で急にSSL/TLSのエラーが出るようになった、という問題の原因と対策»
タグ:
年・日ごとに見る
2008|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|