Rabbit Slide Show

PGroongaの実装

2015-11-27

Description

PGroongaはPostgreSQLに日本語全文検索機能を追加する拡張機能で、インデックスアクセスメソッドとして実装されています。インデックスアクセスメソッドの拡張機能は少なく、どのように実装すればよいか知らない人が多いでしょう。 PGroonga の実装を紹介することでインデックスアクセスメソッドをどのように実装すればよいかを説明します。

Text

Page: 1

PGroongaの実装
ぴーじーるんがのじっそう
須藤功平
株式会社クリアコード
PostgreSQLカンファレンス2015
2015-11-27
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 2

(建前の)目的
PostgreSQLの
amindexを説明
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 3

方法
PGroongaの実装
を紹介
PGroongaはamindexとして実装されているため
ただし、ヒントだけなので詳細はPGroongaのソースを参照
https://github.com/pgroonga/pgroonga
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 4

本当の目的
PGroongaの自慢
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 5

PGroongaとは
amindexの一種
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 6

amindex
索引の実装を
PostgreSQLに
追加する仕組み
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 7

amindexの使い方
CREATE INDEX name ON table
USING pgroonga (column);
組み込みの索引と同じ
(USINGを指定するだけ)
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 8

PGroongaの提供機能
索引を使った
超高速な
全文検索機能
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 9

PostgreSQLと全文検索
課題あり
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 10

PostgreSQLと全文検索1
CREATE INDEX name ON table
USING gin (to_tsvector('english', column));
SELECT * FROM table
WHERE to_tsvector('english', column) @@ '...';
組み込みの全文検索機能
日本語非対応
http://www.postgresql.org/docs/current/static/
textsearch.html
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 11

PostgreSQLと全文検索2
CREATE INDEX name ON table
USING gin (column gin_trgm_ops);
SELECT * FROM table
WHERE column LIKE '%...%';
contrib/pg_trgm
日本語非対応
http://www.postgresql.org/docs/current/static/pgtrgm.html
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 12

PostgreSQLと全文検索
日本語非対応
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 13

PGroongaとPostgreSQL
日本語対応!
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 14

PGroongaを使う
CREATE INDEX name ON table
USING pgroonga (column);
SELECT * FROM table
WHERE column @@ '全文検索';
日本語対応!
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 15

しかも
速い!

Page: 16

ヒット数と検索時間
ヒット数
368
17,172
22,885
625,792
検索時間
0.030s
0.121s
0.179s
0.646s(*)
(*) work_memを10MBに増やしている
データ:Wikipedia日本語版
約184万レコード・平均サイズ約3.8KB
詳細:http://www.clear-code.com/blog/2015/5/25.html
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 17

検索時間:比較
ヒット数
368
17,172
22,885
625,792
PGroonga
0.030s
0.121s
0.179s
0.646s
pg_bigm
0.107s
1.224s
2.472s
0.556s
(*)
(*) 他は検索語が3文字以上でこれだけ2文字
PGroongaは安定して速い!
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 18

なぜ速いのか
バックエンドが
外部の本格的な
全文検索
ライブラリー
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 19

amindexでのポイント
_PG_init()
ライブラリーを初期化
on_proc_exit()
後始末
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 20

全文検索ライブラリー
Groonga
(ぐるんが)
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 21

Groonga
本格的な
全文検索
エンジン
サーバーとしてもライブラリーとしても使える
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 22

本格的な例1
長い文書でも検索性能が落ちない
この特徴が有用なサービス例:
Wiki
イメージ:Wikipedia
ドキュメント検索
イメージ:ファイルサーバー検索
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 23

長い文書でも速い理由
完全
転置索引
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 24

転置索引
完全:位置情報あり
Groonga
無印:位置情報なし
GIN
Groonga (必要なければ入れないことができる)
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 25

転置索引の違い
文書
内容
ID
10 全文検索
20 全文を検索
分解
全文|検索
1
2
全文|を|検索
1
2 3
PGroongaの実装 - ぴーじーるんがのじっそう
完全転置索引 (文書ID+位置)
キーワード ポスティングリスト
10:1,20:1
全文
10:2,20:3
検索
20:2
を
転置索引
キーワード
全文
検索
を
(文書IDのみ)
ポスティングリスト
10:1,20:1
10,20
10:2,20:3
10,20
20
20:2
Powered by Rabbit 2.1.9

Page: 26

索引での検索の違い
クエリー
全文検索
分解
全文|検索
1
2
文書
内容
ID
10 全文検索
20 全文を検索
PGroongaの実装 - ぴーじーるんがのじっそう
完全転置索引 (文書ID+位置)
キーワード ポスティングリスト
10:1,20:1 AND
全文
隣接
10
10:2,20:3 隣接
検索
チェック 結果
20:2
を
転置索引
キーワード
全文
検索
を
(文書IDのみ)
ポスティングリスト
10,20 AND
10,20
10,20
結果候補
20
Powered by Rabbit 2.1.9

Page: 27

検索速度の違い
完全転置索引:安定して速い
索引だけで検索完了
転置索引:速さが安定しない
索引での検索+全件スキャン
候補文書が多い・長い→遅くなる
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 28

amindexでのポイント
全件スキャンを無効にする
scan->xs_recheck = false
tbm_add_tuples(..., false)
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 29

本格的な例2
常時更新・常時検索に強い
この特徴が有用なサービス例:
SNS
イメージ:Twitter
ナレッジ共有サービス
イメージ:Qiita・teratail
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 30

常時更新・検索に強い?
更新中も
参照性能が
落ちない
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 31

性能傾向
更新が増えても
検索性能は落ちない
更新スループット
PGroongaの実装 - ぴーじーるんがのじっそう
GIN
検索スループット
Groonga
更新が増えると
検索性能が落ちる
更新スループット
Powered by Rabbit 2.1.9

Page: 32

落ちない理由
更新時に
参照ロックなし
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 33

参照ロック
獲得したら
他の処理は
参照不可になる
ロック
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 34

GINと更新と参照
INSERT
開始
GINの場合
INSERT
完了
接続1
接続2
SELECT ブロック
開始 性能劣化!
PGroongaの実装 - ぴーじーるんがのじっそう
SELECT
完了
Powered by Rabbit 2.1.9

Page: 35

Groongaと更新と参照
Groongaの場合
追加・更新
追加・更新
開始
完了
接続1
接続2
検索
開始
PGroongaの実装 - ぴーじーるんがのじっそう
検索
完了 性能劣化なし!
Powered by Rabbit 2.1.9

Page: 36

PGroongaと更新と参照
PGroongaの場合
INSERT
INSERT
開始
完了
接続1
接続2
SELECT SELECT
性能劣化なし!
開始
完了
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 37

参照ロックフリーの実現
ユーザー1 値 データ
ユーザー1 値 データ
1. 初期状態
2. 新データ作成
新データ
ユーザー1
値
データ
ユーザー2
新データ
PGroongaの実装 - ぴーじーるんがのじっそう
3. ポインターの
指す先を変更
アトミックな操作
ロック不要
Powered by Rabbit 2.1.9

Page: 38

amindexでのポイント
Lock*() (*) を呼ばない
(*) PostgreSQL提供のロックAPI
呼ぶとGroongaの参照ロックフリー
の有意性を殺してしまう
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 39

本格的な例3
継続的な更新に強い
この特徴が有用なサービス例:
SNS
イメージ:Twitter・Facebook
チャット
イメージ:Slack
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 40

継続的な更新に強い?
間欠的な性能劣化がない
更新も検索も
GINは両方ある
FASTUPDATEを無効にしていない場合
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 41

間欠的性能劣化:Groonga
Groongaは間欠的性能劣化なし
常に最新ポスティングリストを
維持しているから
更新負荷が高くならない対策入り
https://github.com/groonga/groonga/wiki/Memo
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 42

Groongaの索引更新
文書
内容
ID
10 全文検索
20 全文を検索
分解
全文|検索
1
2
全文|を|検索
1
2 3
PGroongaの実装 - ぴーじーるんがのじっそう
完全転置索引 (文書ID+位置)
キーワード ポスティングリスト
10:1,20:1
全文
10:2,20:3
検索
20:2
を
更新を続けても
最新状態を維持
Powered by Rabbit 2.1.9

Page: 43

間欠的性能劣化:GIN
GINは間欠的性能劣化あり
最新ポスティングリスト維持を
サボって高速化しているから
サボったつけを払うときに性能劣化
例:検索時・更新が溜まりすぎた時
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 44

GINの索引更新
文書
内容
ID
10 全文検索
20 全文を検索
分解
全文|検索
1
2
全文|を|検索
1
2 3
PGroongaの実装 - ぴーじーるんがのじっそう
転置索引
キーワード
全文
検索 (文書IDのみ)
ポスティングリスト
10
10
とりあえず
放り込む 最新状態維持を
がんばらない
ペンディングリスト
溢れた!
全文 20 を 20 検索 20 ...
Powered by Rabbit 2.1.9

Page: 45

GINの索引検索
クエリー
全文検索
分解
全文|検索
1
2
文書
内容
ID
10 全文検索
20 全文を検索
PGroongaの実装 - ぴーじーるんがのじっそう
転置索引
キーワード
全文
検索
(文書IDのみ)
ポスティングリスト
10
10
10,20
結果候補
ペンディングリスト
マージ
全文 20 を 20 検索 20
Powered by Rabbit 2.1.9

Page: 46

本格的な例4
索引の作り直しが速い
この特徴が有用なケース:
ダンプのリストア
サービス復旧
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 47

索引作成
元データの
索引
ロード時間
作成時間
16分31秒
25分37秒
データ:Wikipedia日本語版
約184万レコード・平均サイズ約3.8KB
詳細:http://www.clear-code.com/blog/2015/5/25.html
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 48

索引作成:比較
PGroonga
pg_bigm
25分37秒 5時間56分15秒
pg_bigmより約14倍速い!
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 49

速い理由
静的
索引構築を
サポート
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 50

索引構築方法
動的索引構築
構築中も完了した分は検索可能
即時反映可・一括登録不向き
静的索引構築
構築完了まで使えないが速い
(処理時間は入力に比例。指数関数的ではない。)
即時反映不可・一括登録向き
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 51

SQLの違い
-- 動的索引構築
CREATE INDEX ...;
INSERT ...;
-- 静的索引構築
INSERT ...;
CREATE INDEX ...;
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 52

amindexでのポイント
aminsert()
動的索引構築を実装
ambuild()
静的索引構築を実装
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 53

速い理由のまとめ
索引だけで検索可能
更新中も検索可能
間欠的な性能劣化なし
静的索引構築をサポート
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 54

速さ以外の利点1
便利な独自機能
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 55

独自機能1
見慣れた
クエリー言語
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 56

例
body @@ 'PostgreSQL OR MySQL -Oracle'
Web検索エンジン互換
→ユーザーの入力をそのまま使える
デフォルトAND
OR・-(除外)あり
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 57

独自機能2
配列+全文検索
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 58

例
CREATE TABLE logs (hosts text[]);
INSERT INTO logs
VALUES (Array['web', 'db']);
CREATE INDEX index ON logs
USING pgroonga (hosts);
SELECT * FROM logs
WHERE hosts @@ '各ホスト名を全文検索';
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 59

独自機能3
JSON+全文検索
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 60

例
INSERT INTO logs (record)
VALUES ('{"host": "ダウンホスト"}'),
('{"message": "シャットダウン"}');
SELECT * FROM logs
WHERE record @@ 'string @@ "ダウン"'
--
record
-- ----------------------------
-- {"host":
"ダウンホスト"}
-- {"message": "シャットダウン"}
JSON内の全テキストから全文検索
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 61

独自機能4
ノーマライザー
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 62

ノーマライザー
文字を正規化するモジュール
表記の違いを吸収できる
アルファベット:全部小文字
ひらがな・カタカナ:全部全角
㍉→ミリ
UnicodeのNFKCベース
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 63

独自機能5
トークナイザー
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 64

トークナイザー
キーワード切り出しモジュール
クエリーに指定できる
キーワードを調整
例:すもも|も|もも|も
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 65

デフォルト:可変長Ngram
英語:字種区切り
例:Hello|World|!!!
Bigramだとノイズが多い
日本語:Bigram
例:ポスグレ→ポス|スグ|グレ|レ
漏れがない
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 66

形態素解析器ベース
MeCab:OSS
新語対応には辞書メンテが必要
参考:mecab-ipadic-neologd
JMAT:商用製品
ジャストシステム社製
ATOKでも使っている辞書を提供
新語にも強い
参考:「JMAT Groonga Tokenizer Talks」で検索
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 67

amindexでのポイント
amoptions()
CREATE INDEXでのオプションを定義
CREATE INDEX index ON memos
USING pgroonga (content)
WITH (normalizer = 'NormalizerMySQLUnicodeCI',
tokenizer = 'TokenMecab');
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 68

速さ以外の利点2
見慣れた機能
B-tree・GINの代わりに使える
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 69

タグ検索
CREATE TABLE memos (
tags varchar(1023)[]
);
CREATE INDEX index ON memos
USING pgroonga (tags);
SELECT * FROM memos
WHERE tags %% 'タグ';
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 70

範囲検索
CREATE TABLE users (age int);
CREATE INDEX index ON users
USING pgroonga (age);
SELECT * FROM users
WHERE age < 20;
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 71

Index Only Scan
索引がデータも返す
テーブルにアクセスしないので高速
PGroonga・B-tree:サポート
PostgreSQL 9.5からはGiSTもサポート
GIN:未サポート
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 72

amindexでのポイント
amcanreturn()
trueを返す
amgettuple()
scan->xs_want_itupなら
scan->xs_itupにデータを設定
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 73

LIKE
CREATE INDEX index ON memos
USING pgroonga (content);
SELECT * FROM memos
WHERE content LIKE '%...%';
索引を使って高速検索
アプリケーションの変更不要
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 74

マルチカラムインデックス
CREATE INDEX index ON memos
USING pgroonga (title, content);
SELECT * FROM memos
WHERE title @@ '...' AND
content @@ '...';
titleでもcontentでもマッチ!
と書けないのでそんなにうれしくない
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 75

設計
ミス

Page: 76

text @@ text
組み込みの定義と競合
ts_vector @@ ts_queryにキャストされる
回避方法:
ALTER DATABASE name
SET search_path = '$user',public,pgroonga,pg_catalog;
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 77

jsonb @@ text
全文検索にすればよかった
jsonb @@ 'string @ "キーワード"'
-- ↓
jsonb @@ 'キーワード'
今の細かい検索条件を指定できる機能は別演算子にする
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 78

今後

Page: 79

もっとGroongaを活かす
PGroonga
pg_bigm
0.646s
0.556s
Groonga
0.085s
ヒット数635,792、検索語は2文字
生Groongaは1桁速い!
詳細:https://github.com/groonga/wikipedia-search/issues/3
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 80

同義語展開サポート
body @@ pgroonga.expand_query('ネジ')
-- ↓
body @@ 'ネジ OR ねじ OR ボルト'
Groongaでは使える
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 81

ステミングサポート
found/finds
↓
find
Groongaでは使える
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 82

text @@ pgroonga.query
body @@ 'ポスグレ'::pgroonga.query
組み込みのtext @@ textとの競合回避
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 83

重みサポート
-- タイトルのほうが本文より10倍重要
body @@ ('title * 10 || body', 'ポスグレ')
Groongaでは使える
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 84

複合主キーサポート
CREATE TABLE t (
c1 INT,
c2 INT,
PRIMARY KEY (c1, c2)
);
CREATE INDEX index ON t
USING pgroonga (c1, c2);
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 85

まとめ
時間が余ったらチュートリアルを自慢する
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 86

まとめ
PGroongaは速い
PGroongaは便利
PGroongaには設計ミスがある
PGroongaはもっと便利になる
PGroongaを使おう!
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Page: 87

おしらせ
Groonga Meatup 2015
https://groonga.doorkeeper.jp/events/31482
PGroongaの話題もアリ
多少空きアリ (定員を多少増やせる)
11月29日(日)13:30開始
来年2月9日は「MySQLとPostgreSQLと日本語全文検索」
https://groonga.doorkeeper.jp/events/35295
PGroongaの実装 - ぴーじーるんがのじっそう
Powered by Rabbit 2.1.9

Other slides

Mroonga!
2015-10-30