技術と魚

技術調査、開発TIPS、駄文

タグ付けの実装比較 (中間テーブル or JSONB 等)

タグ付けの実装方法

あるリソースに対し、ユーザが任意複数のタグを付けられ、タグによる絞り込み等が行いたいという要件はよくあります。

タグの実装方法について、中間テーブルを使った実装をよく使ってきましたが、postgresのJSONB型を使った方が実は速くて実装も楽なのではなかろうか?と思い、いくつかの実装方法を試してみました。結構面白い結果になったので、結果をオープンにしてみます。

前提

  • Postgres 12.3
  • OS X (16GB), 2.9GHz デュアルコア Intel Core i5 OS X(64 GB) 3.2 GHz 6コア Intel Core i7 (別マシンで再調査しました)
  • 今回はINDEXの構築時間は考慮せず、SELECTの効率のみを考える

さらに今回、あり得そうな付随要件として「タグXを付けたユーザYによって絞り込むことができる」ことも考えます。

実装方法1 (中間テーブル)

リソース用のテーブルとは別にタグ用のテーブル(tags)タグ付けを表す中間テーブル(taggings)を用意してリソース:タグの多対多を実現するやり方。 Railsを使っている人は acts_as_taggable_on というgemがよく知られています。

タグ付けしたユーザに関する情報はtaggingsにカラムを増やせば実現できます。同様にしてタイムスタンプのような情報も簡単に付けられます。中間テーブルのメリットは、このようにタグ付けに対して情報を付加し、個別にインデックスを張れる点と言えます。

f:id:norainu234:20200622193000p:plain

今回は taggings 上の tag_id, record_id および tagger_id に対しそれぞれBTREEインデックスを張っておきます。

実装方法2 (JSONBにタグ名をキーとしたobjectを保存)

Foo, Barの2つのタグを付与した場合に {"Foo": ?, "Bar": ?} の形式でリソースのカラムに直接保存する方法。 ? には任意のjsonb型を埋め込めばよく、追加要件がなければ ? には 1 を入れれば良いですが、今回はタグを付けたユーザのIDを保持しておきます。

f:id:norainu234:20200622193015p:plain

このカラムにはGINインデックスを張っておきます。GIN (Generalized Inverted index; 汎用転置インデックス) についてはここでは省略。

実装方法3 (JSONBにタグ名をメンバとしたarrayを保存)

Foo, Barの2つのタグを付与した場合に ["Foo", "Bar"] の形式でリソースのカラムに直接保存する方法。 この場合、ユーザのIDは保存できません。 すぐに想像できることとして、重複したタグも保存できてしまうので、アプリケーション側の実装は注意する必要になります。

f:id:norainu234:20200622193030p:plain

このカラムにもGINインデックスを張っておきます。

実装方法4 (tsvectorにタグ列を語句として保存)

これはおまけ。tsvectorは全文検索のような用途で使うものと認識していますが、今回は比較対象として用意してみました。 実際のところあまり使ったことがないので詳しくないですが、テキストに対して内部的にパーサを呼び出して語彙素に分解して保持すると理解しています。デフォルトは英語なので "Foo Bar" を与えれば "Foo" "Bar" の語彙素集合として直接保存されます。 この場合、ユーザのIDは保存できません。また、スペースがタグ名称に入っている場合など面倒なことも考えられるので、本来的にはタグとして考えるのはあまり推奨できません。 tsvector型は、tsqueryを使って照合演算によって検索します。多分、前方一致,部分一致のような場合でも強いんじゃないかと思っています。(知らん)

jsonb同様、GINインデックスを張ります。

計測方法

  • タグの名称は100個、ランダムな10文字のアルファベット
  • タグをつけるユーザは100個のID(int)で識別する
  • 一つのリソースには100個からランダムに選んだ10個をそれぞれランダムなユーザでタグ付けする
  • リソースの総数が2N個の時に以下の各検索条件で実行時間の平均値をとる
  • 各ケースにおける実行計画でスキャン方法を取得しておく

検索条件

  • 単一のタグが付いているリソースの一覧
  • 2つのタグのいずれか(OR)が付いているリソース一覧
  • 単一のタグをあるユーザが付けたリソースの一覧 (実装方法1, 2のみ)

結果 (N=1~18)

単一タグによる検索

f:id:norainu234:20200623173436p:plain

2タグ(OR)検索

f:id:norainu234:20200623173506p:plain

単一タグ AND ユーザID での検索

f:id:norainu234:20200623173450p:plain

考察

  • 大体10000レコード超えるあたりからGINインデックスが使われ、そうでなければSeq Scanされる
  • タグによる検索(1つor複数)では、10000超えた辺りからGINインデックスが効き始めてjsonbの方が高速になる
  • jsonbをObjectで持つかArrayで持つかは、ほとんど影響しない
  • jsonbとtsvectorではほとんど大差がない。おそらくGINインデックスの性質に引っ張られている
  • タグ付けしたユーザIDを検索軸に加えた場合、データ量が多い時には、両方にインデックスを張れる中間テーブルが逆転する

まとめ

この結果を踏まえると、タグ付け自体に対する付加情報(ユーザやtimestamp)に関する積集合を検索キーの定義域に含めたい場合には、JSONBではインデックスを張るよりも中間テーブルの方が良さそうです。逆にタグのAND/ORぐらいしか検索する可能性がないような場合は、JSONBで十分と考えられます。 アプリケーションの実装上は、JSONBの方が確実に楽なので、単純なケースではJSONBでタグ付けを実装するほうが効率的と考えられます。

あまり厳格な試験をしたわけではないので、本記事は参考程度にご活用ください。補足/指摘等は大歓迎です。

詳細

実施内容

https://gist.github.com/mizukami234/65a54e39fa0c809163e363f56ff9e109

結果データ

docs.google.com