アペフチ

ドリルダウン(ファセット検索)の仕組み

Groongaで学ぶ全文検索 2015-12-18に行って来た。今日のお題はドリルダウン(ファセット検索)。

ドリルダウン

ある検索語で検索した時に、検索結果をさらに絞り込むと何件になるかなどの集計をする(発表した時に間違いを指摘してもらった。ドリルダウンは絞り込みではなく集計)ことを、予め(検索時に同時に)Groongaがやっておいてくれる、という機能だ。例えばるりまサーチで、「call」を検索した場合、callを含むページのほか、画面左にインスタンスメソッドが何件あるか、特異メソッドは何件あるか……といった結果も表示されている。これは、「callを含み、かつインスタンスメソッドのページ」は何件あるか、という数になっている。

このように、検索結果に対して、既に(与えられた)キーで集計した結果を返すのがドリルダウン。まず、既に分類が終わっているので、検索結果を絞り込む作業が簡単に(クリックするだけで)できる。また、0件の時はそのことが分かるので、不要な絞りこみ作業をユーザーがわざわざする必要がない。というように、ドリルダウンは全文検索を補助する機能だ。全文検索とは関係ない文脈では集計機能ということになる。

ドリルダウンを高速にするために、Groongaのデータ構造が活きている。RDBMSは行指向のテーブル型データベースだから、ストレージ上、一行のデータが複数カラム分、まとまった場所に置かれるようになっている。あるカラムに関する集計(インスタンスメソッドは何件で、特異メソッドは何件で……)をする場合には各行をループさせて、その中で注目しているカラムの場所まで移動して、内容に応じて集計結果を更新する必要がある。

Groongaは列指向データベースだから、ストレージ上、あるカラムのデータがまとまった場所に置かれている。だから集計する場合には一箇所からデータをまとめて取って来て数えたりしていけばよい。

集計に関してはこうなっていて、全文検索では更に「検索結果の中で」のそういった集計を行うことになるが、特別なことはない。一旦全文検索を行ってレコードを取得する。その中で更に集計する。ヒットしなかったレコード分はスキップして集計するのでややもったいないが、列指向でのやり方よりは効率がいい。

多段ドリルダウン

多段ドリルダウンはどうやっているのかも聞いた。本のデータベースがあった時に、雑誌 -> プログラミングというように下位分類を持つようなやつだ(こうじゃないタイプの「多段ドリルダウン」も考えられるそうだが思い出せないとのこと)。

Groongaにはキーを二個使ってドリルダウンができる機能があるそうだ。列指向データベースなので大分類カラム(「雑誌」)、小分類カラム(「プログラミング」)のデータはそれぞれの場所にまとまって置かれているが、ドリルダウンする時に、それぞれから同じレコードの物を取り出してペアにしてまとめることができるのだ。

例えば、何かで検索して結果セットが得られた後に、ドリルダウン結果を大分類と小分類のペアである[雑誌,プログラミング]、[ハードカバー,小説]……の集まりというデータとみなして作ることができる。つまり「大分類が雑誌で小分類がプログラミング」というレコード(本)が何件あるか、という結果を作ることができる。

この結果を使えば、大分類+小分類での絞り込みをサポートすることができる。が、これだけだと大分類のみでの絞り込み結果を出さない。その結果も勿論欲しいので、更に大分類カラムのみの集計もする……ということはしないで、Groongaは頑張って、あるカラムの一回のスキャンで色んな結果用の処理を行うようになっているらしい(ということは、インデックスを調べる前の計画を頑張っているということかな?-> 別に頑張ると言うほど大変なことではなかった)。

また、この話は(Groongaでは)二個に限らず、n個に一般化できるらしい。

ユーザー定義の集約関数

参加者から「平均、最大値……」といった予め用意された関数以外の、ユーザーが定義した関数は使えるのか、という質問がでた。結論は「できない」。

一つはいいインターフェイスがないから。もう一つは、そういう機能を入れると遅くなってしまうから。

ドリルダウン結果のデータ構造

ドリルダウンの結果はハッシュテーブルになっている。

分類カラムの集計処理中、「雑誌」という物を見付けた場合、 「雑誌」が、ドリルダウン結果に既にあるかどうかを素早く知る必要があるからだ。なければ結果データに「雑誌」を加えて「1件」というデータにすることになるし、あれば既存の値をインクリメントする必要がある。

ハッシュのキーはカラムの値その物だとして、バリューの方は、Groongaでは「バリュー」という物になっているらしい。配列とかではない。どんなデータでもよい長さの決まったバイト列で、それを使用する機能の方で適宜解釈して使う、とのこと。

このバリューの方は、ここまでの話だと合計や最大値などになるので、単独の数値でよさそう。だがもっと別の物を入れてもよくて、実際、全文検索結果レコードの内容を入れると便利になる。ドリルダウン結果に加えて、より詳細な結果を同時に見せられるからだ。例えばGoogle検索でたまに、サイトの下位ページが出ることがあるが、そういった情報を出すために検索結果データの内容を使うことができる。