全文検索エンジンgroongaを囲む昼下がり@札幌はたっぷり3時間もあるので、「groongaがどのように動いているか」、「より効率的に検索するためにはどうしたらよいか」などといった話ができるはずです。

この文書は、札幌でのgroonga勉強会で使うための「groongaがどのように動いているか」を説明に使うための文書です。後でgroongaのドキュメントにマージする予定です。

それでは、groongaがどのように全文検索用のインデックスを作成しているかを説明します。まず、全文検索機能で重要なオブジェクトを説明して、その後にそれらを使ってどのようにインデックスを作成しているかを説明します。

主要オブジェクト

groongaの全文検索機能で大事なオブジェクトは以下の3つです。

1. テーブル

2. カラム

3. トークナイザー

それぞれ順に説明します。

テーブル

groongaでは、ひとまとまりのデータを「レコード」と呼びます。これはRDBと同じです。RDBでも行ごとにまとまったデータをレコードと呼んでいます。

groongaのテーブルは「レコードID」を管理するオブジェクトです。「レコードID」とはレコードを一意に識別する数値です。

なお、1つのテーブルで管理できるレコード数（レコードID）の理論的な上限値は約2億6千万レコードです。

テーブルには以下の3つの種類があります。

1. 配列

2. ハッシュテーブル

3. パトリシアトライ

配列はID列を持ったテーブルです。レコードを追加すると新しいレコードIDを払い出します。基本的にレコードIDは1, 2, 3, ...というように順に払い出されます。

ハッシュテーブルはID列とIDと1対1に対応するキーを持ったテーブルです。レコードを追加するときは必ずキーも一緒に指定します。レコードが追加されるとキーに対応したレコードIDを払い出します。ハッシュテーブルが払い出すレコードIDも1, 2, 3, ...というように順に払い出されます。もし、レコードを追加するときに指定したキーが既存のレコードと同じキーだった場合は新しくレコードIDを払い出さず、既存のレコードと同じIDを返します。

パトリシアトライもハッシュテーブルと同様にID列とIDと1対1に対応するキーを持ったテーブルです。レコードの追加も同じように動きます。

配列ではレコードIDでのみレコードを特定できますが、ハッシュテーブルとパトリシアトライはレコードIDだけではなくキーでもレコードを特定できます。

パトリシアトライとハッシュテーブルとの違いはキーの検索方法です。

ハッシュテーブルではキーの検索方法は完全一致検索のみです。つまり、キーからレコードIDを求めるには、求めたいレコードのキーと同一のキーを指定するしかないということです。一方、パトリシアトライでは、完全一致検索だけではなく前方一致検索もできます。

例えば、ククログのデータがgroongaのデータベースに入っているとします。1エントリが1レコードに対応し、エントリが書かれた日付をキーにしているとします。すると、ここ2ヶ月では以下のようなキーになります。

• "2011-8-11"
• "2011-8-24"
• "2011-9-5"
• "2011-9-13"
• "2011-9-29"

この中から2011/9に書かれたエントリのみを表示したいとします。すると、2011/9に書かれたエントリのレコードIDの一覧を取得しなければいけません。この場合、パトリシアトライを使っていると"2011-9-"でキーを前方一致検索することで実現できます。しかし、ハッシュテーブルではこのようなことはできません。

また、パトリシアトライを使うとキーワードリンクなどといったこともできるようになります。

なお、レコードの参照速度の速い順にテーブルの種類を並べると以下のようになります。

1. 配列

2. ハッシュテーブル

3. パトリシアトライ

配列と他の2つのテーブルの使い分けは、ID以外にレコードを特定するキーが欲しいかどうかで考えます。ハッシュテーブルとパトリシアトライの使い分けは、キーを完全一致検索だけで使うかどうかで考えます。

カラム

テーブルはレコードIDを管理するだけで、レコードが持つ値はカラムに保存します。1つのレコードに対して複数のカラムをひもづけることができるため、レコードは複数の値を持つことができます。

カラムには以下の3つの種類があります。

1. スカラーカラム

2. ベクターカラム

3. インデックスカラム

スカラーカラムは1つの値だけを保存できるカラムです。数値を保存するカラムなら「29」や「2929」などを保存できます。文字列を保存するカラムなら「"groonga"」や「"札幌"」などを保存できます。

ベクターカラムは複数の値を保存できるカラムです。同じ種類の値だけを保存できる配列と考えるのがよいでしょう。数値を保存するカラムなら「[2, 29, 292]」などを保存できます。文字列を保存するカラムなら「["groonga", "札幌"]」などを保存できます。

インデックスカラムは転置インデックスを保存するカラムです。転置インデックスは単語IDとその単語IDが含まれている文書IDをひもづけたデータ構造です。

groongaのインデックスカラムでは、単語IDはインデックスカラムのあるテーブルのレコードIDに対応します。文書IDは検索対象のテーブルのレコードIDに対応します。なお、インデックスカラムがあるテーブルのことを「語彙表（lexicon）」と呼びます。

スカラーカラムとベクターカラムはどのテーブルでも一緒に使えますが、インデックスカラムは配列と一緒に使うことはできません。ハッシュテーブルかパトリシアトライと一緒に使う必要があります。これは、groongaでは単語をキーとしたレコードを作成することによりレコードID（= 単語ID）を作成しているためです。

トークナイザー

トークナイザーとは文書から単語を切り出すオブジェクトのことです。例えば、"I am a boy"という文書から「I」、「am」、「a」、「boy」という4つの単語を切り出したりします。この切りだすことを「トークナイズ」と呼びます¹。転置インデックスを作成するときは、単語IDと文書IDをひもづけるために文書内の単語を抽出する必要があります。それを行うのがトークナイザーです。

groongaでは、語彙表用のテーブル毎にトークナイザーを指定します²。

転置インデックスの更新は元の文書を登録・更新・削除したときにgroongaが自動的に行います。そのため、ユーザが明示的にトークナイザーを使うことはありません。単に指定するだけです。

groongaで利用できるトークナイザーの一部は以下の通りです。

• TokenBigram: バイグラムでトークナイズする。
• TokenMecab: MeCabを使ってトークナイズする。
• TokenDelimit: 空白区切りでトークナイズする。

データ更新時の動作

データを更新するとgroonga内部で自動的に転置インデックスが更新されます。そのときの動作を説明します。

まず、最初は、検索対象のテーブル（= 文書を保存するテーブル）にも語彙表のテーブルにもなにもレコードがありません。

それでは、検索対象のテーブルにデータを保存しましょう。

"Yes good"という文書を保存しました。最初の文書なのでレコードID（= 文書ID）は1になっています。データが保存されるとgroongaが内部で自動的に転置インデックスを更新します。

"Yes good"は「Yes」と「good」という2つの単語にトークナイズされます。まずは、「Yes」が語彙表に登録されます。これは最初の単語なのでレコードID（= 単語ID）は1になっています。続いて、単語IDが1に対応するインデックスカラムには保存された文書の文書IDとして1を登録します。

次に2つ目の単語である「good」を処理します。

「good」も「Yes」と同様に処理します。まずは、「good」が語彙表に登録されます。「good」の単語IDは2になります。続いて、単語IDが2に対応するインデックスカラムに保存された文書の文書IDである1を登録します。

もうひとつ文書を保存します。

2番目の文書なので文書IDは2になりました。データが保存されるとgroongaが内部で自動的に転置インデックスを更新します。

"Hey good"は「Hey」と「good」という2つの単語にトークナイズされます。まずは、「Hey」が語彙表に登録され、単語IDが3になります。続いて、単語IDが3に対応するインデックスカラムには保存された文書の文書IDとして2を登録します。

次に2つ目の単語である「good」を処理します。

「good」はすでに登録されている単語なので、新しく追加せずに既存の「good」と同じ単語IDを使います。「good」の単語IDは2なので、対応するインデックスカラムに文書IDとして2を登録します。このとき、すでに文書ID 1も登録されているので文書ID 2は追加します。

このようにして転置インデックスが作成されます。

まとめ

groonga内部でどのように転置インデックスを更新しているかを説明しました。この動作がわかっていると検索が期待通りに動かないときにどこが問題かを見つけやすくなります。例えば、語彙表のキーに期待通りの単語が入っていなかったら、間違ったトークナイザーを指定しているかもしれません。もし、そもそも語彙表に単語が入っていなかったら、転置インデックスの自動更新が動いていないのでしょう。異なるカラム用にインデックスカラムを作成していないかを確認する必要があります。

それでは、全文検索エンジンgroongaを囲む昼下がり@札幌で会いましょう。

1. トークナイズして切り出されたものは「トークン」と呼びますが、ここでは「単語」で統一します。「トークン」と呼ばれるのは切り出されたものが必ずしも「単語」単位とはならないからです。 ↩

2. 今後、インデックスカラム毎に指定できるようになるかもしれませんが、今のところテーブル毎の設定でとても困っているという声がないため、近い将来に実現されることはないでしょう。 ↩