Groongaの複数カラムにまたがるインデックスの仕組み

Groonga Advent Calendar 2016 15日目は、複数カラムにまたがるインデックスの仕組みを取り上げます。

Groongaは複数のカラムにまたがっての全文検索に対応しています。しかし、インデックスの作り方や検索時の使用インデックスの指定の仕方によって、検索結果や処理効率に差が生まれます。目的に応じた最適なインデックスや検索クエリを組み立てられるよう、今日と明日の2回に分けて解説したいと思います。

この記事ではまずGroongaの全文検索用インデックスの基本的な使われ方を説明し、次に複数カラムにまたがるインデックスの使われ方を説明します。「全文検索のインデックスとは何か？」「全文検索エンジンであるGroongaは一体何をしているのか？」ということの説明にもなっていますので、なんとなくでGroongaを使っていたという方もぜひご一読頂ければ幸いです。

なお、以下の説明は--queryと--match_columnsを指定した場合を想定していますが、--filterで使用できるスクリプト構文のquery()関数でも同じことが言えます。--filterの方を使っている場合には、適宜説明を読み替えて下さい。

準備

実験用に、インデックスを持たないテーブルを用意します。

$ cat dump.grn
table_create Entries TABLE_HASH_KEY ShortText
column_create Entries title COLUMN_SCALAR ShortText
column_create Entries body COLUMN_SCALAR ShortText
load --table Entries
[
["_key","title","body"],
["http://example.com/entry1","Hello Groonga.", "This is my first entry."],
["http://example.com/entry2","Hello world.","I love Groonga!"],
["http://example.com/entry3","Hello Mroonga, bye Groonga.","I use Mroonga."],
["http://example.com/entry4","Say, Hello Groonga!","I'm back."]
]
$ rm -rf /tmp/groonga-databases
$ mkdir -p /tmp/groonga-databases
$ groonga -n /tmp/groonga-databases/database.db quit
$ cat dump.grn | groonga /tmp/groonga-databases/database.db

このデータベース内には、以下のような内容を持つEntriesというテーブルだけがある状態です。

_id	_key	title	body
1	http://example.com/entry1	Hello Groonga.	This is my first entry.
2	http://example.com/entry2	Hello world.	I love Groonga!
3	http://example.com/entry3	Hello Mroonga, bye Groonga.	I use Mroonga.
4	http://example.com/entry4	Say, Hello Groonga!	I'm back.

以下、これを材料にしてGroongaのインデックスの仕組みを解説していきます。

通常の全文検索用インデックスの使われ方：WITH_POSITIONフラグの作用

複数カラムにまたがるインデックスの前に、通常のインデックスの場合を改めて説明してみます。

$ cat add_indexes.grn
table_create Terms TABLE_PAT_KEY ShortText --default_tokenizer TokenBigram --normalizer NormalizerAuto
column_create Terms entries_title COLUMN_INDEX|WITH_POSITION Entries title
column_create Terms entries_body COLUMN_INDEX|WITH_POSITION Entries body
$ cat add_indexes.grn | groonga /tmp/groonga-databases/database.db

この操作によって、語彙表のTermsテーブルと、そのテーブルに2つのインデックスカラムが作られます。インデックスカラムの内容を模式的に表すと以下のようになります（簡単のため、ここではtitleカラム由来のトークンだけ示します）。

_key	entries_title	entries_body
Hello	[id=1,pos=1], [id=2,pos=1], [id=3,pos=1], [id=4,pos=2]
Groonga	[id=1,pos=2], [id=3,pos=4], [id=4,pos=3]	[id=2,pos=3]
world	[id=2,pos=2]
bye	[id=3,pos=3]
Mroonga	[id=3,pos=2]	[id=3,pos=3]
Say	[id=4,pos=1]

各インデックスにpos=...という情報が付いています¹が、これがWITH_POSITIONフラグによって付与される出現位置の情報です（あくまでこれは模式的な表記です。実際のデータの持ち方とは関係ありませんので注意して下さい）。

Groongaの場合、トークンの出現位置の情報は全文検索用のインデックスには必須です。何故なら、これが無いと適切な検索結果を返せないからです。

インデックスを使った検索

select --table Entries --match_columns title --query "Hello Groonga" --output_columns=_key,titleという検索クエリが与えられた場合を例に、出現位置の情報の使われ方を説明しましょう。

Groongaはまず、クエリとして与えられた文字列を語彙表のキーのトークナイズの仕方と同じ方法でトークナイズします。

トークン	出現位置
Hello	1
Groonga	2

次に、語彙表のTermsテーブルからクエリのトークンと_keyが一致するレコードを探してきて、--match_columnsに指定されたカラムであるtitleカラムに対応するインデックス＝Terms.entries_titleを見ます。

_key	entries_title
Hello	[id=1,pos=1], [id=2,pos=1], [id=3,pos=1], [id=4,pos=2]
Groonga	[id=1,pos=2], [id=3,pos=4], [id=4,pos=3]

この時、id=1、id=2、id=4は両方のレコードに含まれています。この事から、Entriesテーブルで_idが1、3、および4の3レコードが検索結果の候補となります。

しかしこの段階ではまだ検索結果として適切かどうか分かりません。そこで今度は各インデックスの出現位置情報を見ます。

	トークンの出現位置	各トークンの相対的な出現位置
クエリ（Hello Groonga）	1,2	0,1
_idが1のレコードのtitle（Hello Groonga.）に対するインデックス	1,2	0,1
_idが3のレコードのtitle（Hello Mroonga, bye Groonga.）に対するインデックス	1,4	0,3
_idが4のレコードのtitle（Say, Hello Groonga!）に対するインデックス	2,3	0,1

こうして見ると、_idが3のレコードは2つのトークンの出現位置が離れているので検索結果として不適切なのが分かります。よって、クエリと同じ位置関係でトークンが並んでいる以下の2レコードだけが検索結果としてヒットします。

_key	title
http://example.com/entry1	Hello Groonga.
http://example.com/entry4	Say, Hello Groonga!

Bigramのトークンの場合の例

先の例は英単語のトークンだけが登場しましたが、Bigramのトークンでも同じ事が行われます。例えばこんにちはというクエリであれば以下のようにトークナイズされます。

トークン	出現位置
こん	1
んに	2
にち	3
ちは	4

検索対象のデータとしてこにちは, こんちは, やあこんにちはの3つがあった場合、以下のようにマッチングされます。

	トークン	クエリのトークンの出現位置	各トークンの相対的な出現位置
クエリ（こんにちは）	こん,んに,にち,ちは	1,2,3,4	0,1,2,3
「こにちは」に対するインデックス	こに,にち,ちは	3	0
「こんちは」に対するインデックス	こん,んち,ちは	1,3	0,2
「やあこんにちは」に対するインデックス	やあ,あこ,こん,んに,にち,ちは	3,4,5,6	0,1,2,3

この例では、最後のやあこんにちはだけがクエリと同じ順番・位置関係でトークンが出現しているため、検索結果としてヒットします。

すべての検索エンジンがこのような形式でインデックスを持っているわけではありませんが、Groongaはこのようなアルゴリズムで検索を行っており、そのアルゴリズムに都合が良いような形でインデックスを構築しているというわけです。

複数カラムにまたがるインデックスの場合：WITH_SECTIONフラグの作用

複数のカラムにまたがるインデックスの場合も基本は同じなのですが、1つ前の例のインデックスと異なり、こちらの場合はWITH_SECTIONというフラグが必要になります。それでは実際にインデックスを追加してみましょう。

$ cat add_whole_index.grn
column_create Terms entries_whole COLUMN_INDEX|WITH_POSITION|WITH_SECTION Entries title,body
$ cat add_whole_index.grn | groonga /tmp/groonga-databases/database.db

この操作によって、語彙表のTermsテーブルに新たにインデックスカラムentries_wholeが作られます。インデックスカラムの内容を模式的に表すと以下のようになります。

_key	entries_title	entries_body	entries_whole
Hello	[id=1,pos=1], [id=2,pos=1], [id=3,pos=1], [id=4,pos=2]		[id=1,pos=1,sid=1], [id=2,pos=1,sid=1], [id=3,pos=1,sid=1], [id=4,pos=2,sid=1]
Groonga	[id=1,pos=2], [id=3,pos=4], [id=4,pos=3]	[id=2,pos=3]	[id=1,pos=2,sid=1], [id=3,pos=4,sid=1], [id=4,pos=3,sid=1], [id=2,pos=3,sid=2]
world	[id=2,pos=2]		[id=2,pos=2,sid=1]
bye	[id=3,pos=3]		[id=3,pos=3,sid=1]
Mroonga	[id=3,pos=2]	[id=3,pos=3]	[id=3,pos=2,sid=1], [id=3,pos=3,sid=2]
Say	[id=4,pos=1]		[id=4,pos=1,sid=1]

entries_wholeでは各インデックスにsid=...という情報が加わっています。これがWITH_SECTIONフラグによって付与されたセクション情報です。……はい、「セクションって何？」と思われた方は多いでしょう。ここでもう1度、検索対象のデータがあるEntriesテーブルを見てみます。

_id	_key	title (sid=1)	body (sid=2)
1	http://example.com/entry1	Hello Groonga.	This is my first entry.
2	http://example.com/entry2	Hello world.	I love Groonga!
3	http://example.com/entry3	Hello Mroonga, bye Groonga.	I use Mroonga.
4	http://example.com/entry4	Say, Hello Groonga!	I'm back.

titleとbodyの各カラムにsidという情報が新たに出現しました。実は、Groongaは各カラムに「セクションID」という内部的なIDを与えていて、実際の処理ではそちらの方を使っています（セクションIDは整数値なので、文字列であるカラム名よりも取り扱いやすいのです）。

以後の説明を簡単にするため、ここでカラムごとのインデックスを一旦削除しておきます。

$ cat remove_needless_indexes.grn
column_remove Terms entries_title
column_remove Terms entries_body
$ cat remove_needless_indexes.grn | groonga /tmp/groonga-databases/database.db

インデックスは以下の通り、複数カラムにまたがる物だけがある状態となりました。それでは説明を続けます。

_key	entries_whole
Hello	[id=1,pos=1,sid=1], [id=2,pos=1,sid=1], [id=3,pos=1,sid=1], [id=4,pos=2,sid=1]
Groonga	[id=1,pos=2,sid=1], [id=3,pos=4,sid=1], [id=4,pos=3,sid=1], [id=2,pos=3,sid=2]
world	[id=2,pos=2,sid=1]
bye	[id=3,pos=3,sid=1]
Mroonga	[id=3,pos=2,sid=1], [id=3,pos=3,sid=2]
Say	[id=4,pos=1,sid=1]

複数カラムにまたがるインデックスでの、特定カラムを対象にした検索

select --table Entries --match_columns body --query "Groonga" --output_columns=_key,title,bodyという検索クエリが与えられた場合を例に、セクションIDの使われ方を説明しましょう。

今度はトークンが1つだけなので、語彙表のレコードも1つだけが参照されます。

_key	entries_whole
Groonga	[id=1,pos=2,sid=1], [id=3,pos=4,sid=1], [id=4,pos=3,sid=1], [id=2,pos=3,sid=2]

ここでインデックスカラムには4つのインデックス情報があり、これらのidを持つEntriesテーブルのレコードが検索結果としてヒットする……と言いたい所ですが、まだ早計です。このインデックスは複数カラムにまたがっているため、titleの内容にマッチしたのかbodyの内容にマッチしたのかを調べるまでは結論を出せません。

ここでセクションIDの情報が使われます。--match_columnsに指定されたカラムbodyに対応するセクションIDは2なので、sid=2であるインデックス以外を取り除きます。

_key	entries_whole
Groonga	[id=2,pos=3,sid=2]

すると、id=2のインデックスだけが残りました。今回はトークンが1つだけなので、これでもう検索結果を返せます。

_key	title	body
http://example.com/entry2	Hello world.	I love Groonga!

ということで無事、bodyカラムにクエリで指定された文字列を含むレコードだけがヒットしました。

なお、Hello Groongaのように複数トークンに分割されるクエリが与えられた場合には、前項の「出現位置情報での絞り込み」とこの項の「セクションIDでの絞り込み」の両方で絞り込んだ結果が検索結果となります。

複数カラムにまたがるインデックスのメリットとデメリット

検索対象になり得る各カラムの内容のトークナイズ結果が似ていて共通するトークンが多い場合、entries_wholeのように複数カラムにまたがるインデックスにはディスクやメモリの使用量を節約できるというメリットがあります。また、この記事では説明しませんでしたが、両方のカラムにまたがった検索を高速に行えるというメリットもあります。

しかし、デメリットもあります。entries_wholeには検索対象の両方のカラムに対応するインデックスが格納されるので、インデックスの数が増えて、「新しいレコードに対するインデックスを追加する処理」や「このトークンを含むEntriesテーブルのレコードはどれか？ を調べる処理」などにかかる時間が増大します。また、セクションIDを使ったマッチングの手間が増えるので、カラムを指定しての検索にも余計に時間がかかるようになります。

これらの点を踏まえると、以下のような使い分けができるでしょう。

• 何よりも検索や更新の性能を優先したい、そのためならディスクやメモリの消費の増大は許容する
  →個別のカラムに対するインデックスと、複数カラムにまたがるインデックスの両方を持たせる。
• 何よりもディスクやメモリの消費を抑えたい、そのためなら検索や更新の性能の多少の低下は許容する
  →複数カラムにまたがるインデックスだけを持たせる。
• 複数カラムにまたがる検索はしない
  →個別のカラムに対するインデックスだけを持たせる。

以上、Groonga Advent Calendar 2016 15日目として複数カラムにまたがるインデックスの詳細について述べました。明日はこの続きとして、--match_columnsパラメータの指定の仕方による検索動作の変化を解説します。引き続きGroonga Advent Calendarをお楽しみ下さい！

1. このように、トークンに対してそれを含むレコードの情報を保持しておくインデックスのことを「転置インデックス」と言います。また、この例のようにトークンの出現位置の情報も含む転置インデックスを「完全転置インデックス」と言います。 ↩