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

[Groonga Advent Calendar 2016](http://qiita.com/advent-calendar/2016/groonga) 15日目は、複数カラムにまたがるインデックスの仕組みを取り上げます。

Groongaは[複数のカラムにまたがっての全文検索](http://groonga.org/ja/docs/tutorial/match_columns.html#full-text-search-against-multiple-columns)に対応しています。しかし、インデックスの作り方や検索時の使用インデックスの指定の仕方によって、検索結果や処理効率に差が生まれます。目的に応じた最適なインデックスや検索クエリを組み立てられるよう、今日と明日の2回に分けて解説したいと思います。

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

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

## 準備

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

~~~bash:
$ 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`フラグの作用

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

~~~bash:
$ 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`フラグの作用

[複数のカラムにまたがるインデックス](http://groonga.org/ja/docs/tutorial/match_columns.html#creating-one-column-index-against-multiple-columns)の場合も基本は同じなのですが、1つ前の例のインデックスと異なり、こちらの場合は`WITH_SECTION`というフラグが必要になります。それでは実際にインデックスを追加してみましょう。

~~~bash:
$ 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は整数値なので、文字列であるカラム名よりも取り扱いやすいのです）。

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

~~~bash:
$ 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](http://qiita.com/advent-calendar/2016/groonga) 15日目として複数カラムにまたがるインデックスの詳細について述べました。[明日はこの続きとして、`--match_columns`パラメータの指定の仕方による検索動作の変化を解説します](http://qiita.com/groonga/items/4adc94f7c43303392991)。引き続きGroonga Advent Calendarをお楽しみ下さい！