インデックス

参考 この記事は、以下の記事を読んで疑問に思ったことを調べた学習記録である。 Zennの検索スピードを5倍に高速化した話 記事では、Zennのサイト内検索をpg_trgm拡張を使って平均6倍、95パーセンタイルで4.25倍高速化した事例が紹介されている。 なぜ中間一致検索は遅いのか 通常、PostgreSQLでLIKE '%keyword%'のような中間一致検索を実行すると、BTreeインデックスが使えずフルスキャンが発生する。BTreeインデックスは文字列の前方一致には有効だが、中間一致では活用できない構造になっているためである。 データ量が増えると、このフルスキャンが深刻なパフォーマンスボトルネックになる。参考記事では、検索に1秒〜数秒かかる状態だったとのことだ。 n-gramインデックスの仕組み n-gramインデックスは、文字列をn文字ずつに分割してインデックス化することで、中間一致検索でもインデックスを効かせる仕組みである。 3-gramの例 「PostgreSQL」という文字列を3-gram（トライグラム）で分割すると以下のようになる。 __P, _Po, Pos, ost, stg, tgr, gre, reS, eSQL, QL_, L__ 先頭と末尾にはパディング文字（_）が付与される。 検索時の動作 「stgre」というキーワードで検索する場合： 検索キーワードを3-gramで分割: stg, tgr, gre インデックスからこれらすべてのトライグラムを含む文書を抽出 抽出された候補に対してRecheck処理を実行 重要なのは「いずれか」ではなく「すべて」のトライグラムが存在する文書が候補になる点である。もし「いずれか」だと、無関係な文書が大量に候補に含まれてしまう。 Recheck処理が必要な理由 n-gramインデックスでは、インデックスレベルでの検索後に必ずRecheck処理が必要になる。 具体例 以下のような状況を考える。 本文: 「小学校校長」 クエリ: 「小学校長」 3-gramで分割すると： 「小学校校長」→ 小学校, 学校校, 校校長 「小学校長」→ 小学校, 学校長 「小学校」が共通しているため、n-gramレベルでは「小学校校長」が候補として抽出される。しかし実際には「小学校長」という文字列は含まれていない。 このようなfalse positive（誤検出）を除外するため、インデックスで絞り込んだ候補に対して、実際に検索キーワードが含まれているかを厳密にチェックする必要がある。これがRecheck処理である。 pg_trgmとpg_bigmの選択 PostgreSQLには2つの主要なn-gram拡張がある。 pg_trgm: 3-gram方式、PostgreSQL本体にcontribとして付属 pg_bigm: 2-gram方式、サードパーティ製（NECが開発） 比較表 機能 pg_trgm pg_bigm エコシステム PostgreSQLコミュニティ サードパーティ ILIKE対応 ○ × 2文字以下の検索 × ○ Recheck無効化 × ○ インデックスサイズ 小 大（約2倍） なぜpg_trgmが選ばれたか 参考記事では、以下の理由でpg_trgmのみを採用している。 ...