mixi engineer blog

＊＊＊ 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers ＊＊＊ ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

3行でできる超お手軽全文検索

mixi

梅雨。部屋干しした洗濯物による異臭騒ぎに苦しむmikioです。今回は、Tokyo Cabinetのテーブルデータベースで超お手軽に全文検索をする方法について説明します。

tcindexvariants

使い方

テーブルデータベースについてまずおさらいしておきましょう。PerlやRubyのハッシュのようにコラム名とその値を関連づけた構造を、主キーを識別子として保存するデータベースです。例えばRubyからデータを保存するに以下のように行います。データベースであることをほとんど意識させないというのが素敵ポイントです。APIはCでもPerlでもRubyでもほとんど同じなので、言語にかかわらず同じようにレコードを操作できます。 

require 'tokyocabinet'
include TokyoCabinet

# データベースを開く
tdb = TDB::new
tdb.open("casket", TDB::OWRITER | TDB::OCREAT)

# レコードを入れる
tdb.put("12", { "name" => "mikio", "lang" => "c,c++,perl,ruby,java,lua",
                "birth" => 19780211, "intro" => "趣味はサーフィンです。" })
tdb.put("34", { "name" => "jonathan", "lang" => "c,c++,perl" })
tdb.put("56", { "name" => "joseph", "lang" => "c++,perl,ruby,php" })
tdb.put("789", { "name" => "jotaro", "lang" => "ruby,python,java" })

# データベースを閉じる
tdb.close

一般的なリレーショナルデータベースと違ってスキーマがなく、レコード毎のデータ構造が同じである必要はありません。上記のように、mikioだけ生年月日と本名を入れるみたいなことが普通にできます。さて、上記のDBにいろんな条件で検索をしてみましょう。 

require 'tokyocabinet'
include TokyoCabinet

# データベースを開く
tdb = TDB::new
tdb.open("casket", TDB::OREADER)

# nameが「jo」で始まる人を探す （普通の文字列検索）
qry = TDBQRY::new(tdb)
qry.addcond("name", TDBQRY::QCSTRBW, "jo")
p qry.search

# C++とRubyが使える人を探す （タグ検索）
qry = TDBQRY::new(tdb)
qry.addcond("lang", TDBQRY::QCSTRAND, "c++,ruby")
p qry.search

# 自己紹介に「サーフィン」を含む人を探す （全文検索）
qry = TDBQRY::new(tdb)
qry.addcond("intro", TDBQRY::QCFTSPH, "サーフィン")
p qry.search

# データベースを閉じる
tdb.close

このように、任意のコラムを対象にして様々な演算子で条件を設定することができます。テーブルDBにさえ入れておけば、いわゆるタグ検索（"c++"と"ruby"を含む）や全文検索（部分文字列として"サーフィン"を含む）などの高度な検索条件でレコードを取り出すことができます。100万レコードくらいの規模であれば、専用の全文検索エンジンを使わなくても、おそらくTCだけでそこそこ実用的な情報検索システムや文書管理システムを構築することができるでしょう。もちろんTokyo Tyrant経由でも利用できるので、Solr（Lucene）っぽい位置づけで使えるとも言えるでしょう。

本当に3行で全文検索機能を追加できる

この仕組みを使って、前回とりあげた100行チャットのデモサイトにも検索機能が加えられました。データベースと検索エンジンが統合されているので、特に工夫しなくてもリアルタイム検索になっているのが自慢です。それでいて、加えたのは以下のたった3行です。 

...
// 検索クエリをパラメータから受け取る
const char *search = tcstrskipspc(tcmapget4(params, "search", ""));
...
// 検索クエリがあれば、チャットログの表示条件にそれを加える
if(*search != '\0') tctdbqryaddcond(qry, "t", TDBQCFTSEX, search);
...
// ページ遷移でクエリを引き継ぐためにテンプレート変数に渡す
tcmapprintf(vars, "search", "%s", search);
...

表示部分が既にあるならば、その絞り込み条件を入力として受けて1行、それをクエリオブジェクトに渡して1行、結果画面に反映させるために出力に渡して1行、合計3行です。これは極端な例ですが、ストレージ層が検索機能を備えているならば、検索システムを構築する際の実装工程は刺身にタンポポを乗せるような簡単な仕事になります。浮いた分の工数を要求分析や設計やテストに注力できたらハッピーですよね。

転置インデックス

タグ検索も全文検索も、TCのテーブルデータベースで従来からサポートされていました。何が新しいのかというと、それらの検索操作を高速化するために、2種類の転置インデックスを使うことができるようになったことです。タグ検索を高速化する「トークン転置インデックス」と、全文検索を高速化する「q-gram転置インデックス」です。

タグ検索について考えてみます。コラムの値を空白またはコンマで区切ったトークンの集合とみなして、指定したトークンが存在するレコードを探す操作です。例えば、「ruby,python,java」という文字列があった場合、「ruby」と「python」と「java」が照合条件になります。タグ検索は広い意味では全文検索の一種とも言えるのですが、切り出したトークンを単位としてでないと検索できないことが特徴です。例えば、「python」の「thon」といったトークン内の部分文字列や、「by,py」といったトークンをまたがった部分文字列は照合条件にすることができません。

タグ検索を高速化するには、レコードの値そのものを検索キーとしたインデックスを作るわけにはいきません。そうでなく、レコードから切り出した各々のトークンを検索キーとして、それを含むレコードの主キーのリストを値としたインデックスを作る必要があります。このように、検索対象のレコードを分解して検索キーを作り出して、それに付随させてレコードを特定するための位置情報のリスト（posting listともいいます）を記録したインデックスのことを転置インデックスといいます。通常の文字列型および数値型のインデックスとの比較はこの記事の冒頭のイラストを見ていただけるとわかりやすいと思います。

全文検索について考えてみます。ここではタグ検索と対比して、アプリケーションレベルのトークンを無視して、全ての部分文字列でも検索対象にした検索操作を全文検索と呼ぶことにします。英文を検索する場合は空白などの記号でトークンを区切ればタグ検索の使用感と全文検索の使用感をほぼ同じにすることができるのですが、日本語だとMeCabなどの優れた形態素解析器をもってしても期待通りにトークンを切り出せるとは限らない（そもそも期待される切り出し方が一通りでないことも多い）ので、タグ検索と全文検索の仕組みは別個に実装しておく必要があります。

全文検索を高速化するには、任意の部分文字列を検索キーとして、それを含むレコードの主キーのリストを値としたインデックスを作る必要があります。とはいえ、任意の部分文字列の組み合わせ数はレコードの文字数の2乗という膨大な数になってしまうので、一定の文字数で区切って検索キーを作り出すことにします。このような方式をq-gram（文字N-gram）インデックスと呼びます。詳しい特性は以前の記事で述べましたので興味のある方はご確認ください。

転置インデックスの威力

転置インデックスの威力を見るために、インデックスを張った場合と張らない場合で検索性能がどう変わるかを見てみましょう。まずは、以下のコマンドで、100万レコードを登録したテスト用のデータベースを作ります。 

$ tcttest write casket 1000000

どんなレコードが入っているか確かめるべく、5件だけ表示してみます。 

$ tctmgr list -m 10 -pv casket
1    str    1    num    1    type    18   flag   4,6,9,12  text    4,6,9,12
2    str    2    num    1    type    8    flag   1,2       text    1,2
3    str    3    num    1    type    15
4    str    4    num    2    type    28
5    str    5    num    3    type    3    flag   2,4,7     text    2,4,7

この状態では転置インデックスは張っていません。flagコラムにトークンとして「19」を含むものを探してみましょう。"-ph" オプションでヒント情報を出力しています。 

$ tctmgr search -pv -ph casket flag STRAND 19
449   str  449   num  114   type  10   flag  5,10,15,19   text  5,10,15,19
1246  str  1246  num  1182  type  16   flag  5,9,14,19    text  5,9,14,19
1542  str  1542  num  973   type  14   flag  4,9,14,19    text  4,9,14,19
1941  str  1941  num  323   type  22   flag  5,9,14,19    text  5,9,14,19
2007  str  2007  num  1425  type  32   flag  4,9,14,19    text  4,9,14,19
...
        :::: scanning the whole table
        :::: result set size: 1292
        :::: leaving the natural order
        :::: number of records: 1292
        :::: elapsed time: 1.24810

ヒントの「scanning the whole table」は全表操作であることを示します。それにともない、転置インデックスを張らない状態だと、検索に1.25秒もかかっています（文字列型インデックスを張ったとしてもSTRANDとSTRORには効かないので性能は変わりません）。そこで、flagコラムにトークン転置インデックスを張ります。 

tctmgr setindex -it token casket flag

この規模なら1秒くらいでインデックスが張り終わると思います。"-it token" はインデックスの型がトークン転置インデックスであることを示しています。なお、q-gram型にしたい場合は "-it qgram" とします。では、転置インデックスのある状態で検索してみます。 

$ tctmgr search -pv -ph casket flag STRAND 19
449   str  449   num  114   type  10   flag  5,10,15,19   text  5,10,15,19
1246  str  1246  num  1182  type  16   flag  5,9,14,19    text  5,9,14,19
1542  str  1542  num  973   type  14   flag  4,9,14,19    text  4,9,14,19
1941  str  1941  num  323   type  22   flag  5,9,14,19    text  5,9,14,19
2007  str  2007  num  1425  type  32   flag  4,9,14,19    text  4,9,14,19
...
        :::: using an index: "flag" inverted (STRAND)
        :::: result set size: 1292
        :::: leaving the natural order
        :::: number of records: 1292
        :::: elapsed time: 0.00169

出力されるレコードは変わっていませんが、ヒントの「using an index: "flag" inverted (STRAND)」は転置インデックスが使われたことを示しています。そして今度は検索が0.0016秒で済んでいることがわかります。圧倒的に高速ですよね。

転置インデックスも他の型のインデックスと同じく、レコードを入れる前に張ってもレコードを入れてから張ってもかまいません。インデックスがある状態でレコードを入れるとインデックスも自動的に更新されます。スキーマなんてあまり考えずにとりあえず何でもデータベースに突っ込んでおいて、運用してみて高速化したくなった演算にだけインデックスを張るというお気楽な開発スタイルがとれるのが強みではないでしょうか（業務システムでそれやったらしばかれるでしょうが）。

全文検索用の演算子

トークン転置インデックスを張ると、今までインデックスが効かなかったSTRAND演算子とSTROR演算子が高速化されます。じゃあ全文検索用のq-gram転置インデックスを張るとSTRINC演算子（文字列の部分一致）が高速化されるのかと思うところですが、そうではありません。最新版からは全文検索用の以下の演算子が追加されていて、それらを高速化する効果があります。

  • FTSPH : フレーズ検索の全文検索を行う
  • FTSAND : コンマ区切り（または空白区切り）の文字列を用いてAND検索の全文検索を行う
  • FTSOR : コンマ区切り（または空白区切り）の文字列を用いてOR検索の全文検索を行う
  • FTSEX : 複合検索式の全文検索を行う

STRINCとは別に演算子を設けた理由の第一は、全文検索用の演算で文字列の正規化をしたいということです。すなわち、全角英数字と半角英数字を同一視したり、全角片仮名と半角片仮名を同一視したり、ウムラウトなどのアクセントマークの有無を同一視したりといった正規化です。STRINC演算子はあくまでそのままのバイト表現の中間一致を調べるべきで、現行の仕様は変えたくなかったので、正規化をした文字列の中間一致を調べるには別の演算子を設けるのが最善でしょう。

ということでSTRINC演算子の正規化版とも言えるFTSPH演算子をまず作りました。ただ、それだけだと全文検索でよく使うAND検索をうまく扱うことができません。FTSPH演算子で「unix linux」と入れると、「unix linux」が現れるレコードを探すのであって、「unix」と「linux」がそれぞれ任意の位置に現れるレコードを探すわけではありません。FTSAND演算子はそのために追加しました。さらに、AND検索があったらOR検索もあるだろうということで、FTSOR演算子も追加しました。

AND検索、OR検索と来たら、NOT検索とかそれらの複合条件も指定したくなるのが人情というものです。例えば、「リュウ」か「ryu」を含んで、かつ「ケン」か「ken」を含んで、かつ「魔弾戦記リュウケンドー」は含まないといった条件で検索をしたくなるわけです。その際にはFTSEX演算子による複合検索式として「リュウ || ryu && ケン || ken !! 魔弾戦記リュウケンドー」などと指定します。「&&」はAND検索、「||」はOR検索、「!!」はNOT検索を意味します。結合の優先度は「||」が上位で「&&」と「!!」はその下です。同一優先度の場合は左結合で評価されます。空白を照合条件に含めてフレーズ検索をするために、「""」でくくることもできます。これで全文検索のユースケースの99%以上はカバーできているのではないかと思います。

まとめ

Tokyo Cabinetのテーブルデータベースは、各種スクリプト言語のハッシュと同じような簡潔なインターフェイスを備え、それでいて強力な機能群によって実用的なアプリケーションを容易に構築することを可能にしてきました。それにさらに2種類の転置インデックスと全文検索用の演算子が加わり、専用の全文検索システムがなくても、データベースに入れるだけで一般的な情報検索や文書管理に必要な検索操作のほとんどを充足させることができるようになりました。とっても簡単で便利なのでぜひ試してみていただきたいところです。

タグ検索と全文検索といえば、Tokyo Dystopiaが同じような機能を既に実現しています。TCにタグ検索と全文検索がサポートされたからもうTDは不要なのかと思われるかもしれませんが、そうではありません。転置インデックスのライブラリとしてはTDの方がはるかに効率的かつスケールする設計になっていて、また業務に必要なカスタマイズを容易にするためにシンプルな実装になっています。一方でTCの転置インデックスは、パフォーマンスやスケーラビリティではTDに劣りますが、ものすごく簡単に導入できることが特徴です。既にテーブルDBでデータの管理をしているならば、setindexホゲホゲという文を書くだけで1分以内に検索機能を強化することができるのです。

実装の詳細についてもうちょっと書こうかなとも思ったけれど、「内部がどうなってるかなんて別に興味ない」とか「ソースとか張られても読み飛ばすだけだし」とか言われることが多いので割愛しました。10わっふる以上を検知したら次回以降に書くかもしれませんが...。