DoorKeeper
http://sqlap.doorkeeper.jp/events/9851
以下の書籍をターゲットとした読書会なのです。
 | SQLアンチパターン (2013/01/26) Bill Karwin 商品詳細を見る |
場所はいつもの湯島、株式会社アルティネットさんです。
いつも会場提供ありがとうございます。
参加者は9人かな。
初参加も1人いらっしゃいました。新しい風が入るのは良いですね～
今回は16章「プアマンズ・サーチエンジン」が対象範囲でした。
■アジェンダ
今回は @natsu_nanana さんが急なお仕事で参加できないということで、急遽 @t_wada さんが章の説明＆仕切り役を担ってくださいました。感謝！
過去の講演資料を使って「プアマンズ・サーチエンジン」のポイントをわかりやすく説明する対応力、さすがです。
■ディスカッション
今回もディスカッションしたいネタをみんなで付箋に書き出しました。
激しくピンボケした。。。
付箋と太ペンを用意してくださった @inda_re さん、ありがとーございました。
---
■ アンチパターン
- 中間一致のLIKE検索はインデックスが使えない（フルスキャンになる）
■ 単語境界
- P.175のREGEXP '[[:<:]]one[[:>:]]は、単語境界にマッチさせるSQL上の正規表現である。
- 英語は単語間にスペースがあるが、日本語は明確な単語境界が無い。
→ そのため、分かち書きのライブラリと併用することが多い。
→ 日本語は、そもそも正規表現の世界以前の問題がある。
→ 日本語は、そもそも正規表現の世界以前の問題がある。
■ 正規表現
- 正規表現はSQL標準に入ってきているので、頑張れば書ける。
- ただ、SQL標準に正規表現を追加したことで、仕様がとても大きくなってしまった。
- 中間一致はインデックスが使えないが、前方一致はインデックスが使える。
- LIKE述語の２つのワイルドカードの間にPreparedStatementのプレースホルダを入れ、LIKE "%?%" のように書いてしまうことがある。
- 複雑な正規表現を考え始めたら、それは何かがおかしい、と疑うべき。
■ 解決策
- ベンダー拡張の全文検索機能
- サードパーティーの全文検索エンジン
- 転置インデックスの自作
■ １．ベンダー拡張の全文検索機能
- 全文検索のニーズはたくさんあるが、標準がない。
- ベンダー拡張は全部方言になるが、製品の差別化要因としてアピールしてくることも多い。
- MySQLのフルテキストインデックスは、MyISAMだけでなくInnoDBでも使えるようになった。
- ただし、日本語が使えない。。。
- 書籍の最新版では、その旨を脚注に追記している。
- Oracleはデフォルトでテキストインデックスをサポートしているので使いやすいかもしれない。
- SQL ServerはDBを停止させて設定しないと使えないのでハードルが高い。
- iPhoneのSQLiteでテキスト拡張が使えるかどうかは、FTS拡張を有効化するようにビルドされたかに左右される。
- 見事に全ベンダーの全文検索が違う。
■ ２．サードパーティーの全文検索エンジン
- Sphinx Searchはミドルウェアみたいな検索エンジン。
- Sphinxでググると、著名なドキュメント作成プログラムの方がヒットするので、検索がnoisyだったりする。
- Apache Luceneを使ってる人は多い。Apache経由でSolrを使うパターンが多い。
- 日本だと Groonga というオープンソースのカラムストア機能付き全文検索エンジンがある。
- http://groonga.org/ja/
- バインディングライブラリがいろいろあって、それを使うことも多い。
- ドキュメントの全文検索エンジンとしては Namazu というものがある。
■ ３．転置インデックスの自作
- 「全文検索の仕組みを自分で作っちゃおう」という、だいぶオレオレな解決策。
- ストアドプロシージャとトリガーが使用できれば、それっぽいことはまぁまぁ出来る。
- いきなりインデックスを作るのではなく、検索されたら１回目はフルスキャンさせる。
- その結果をインデックスに取っておき、次に検索が来たらそのインデックスを使うようにする。
- １回目の検索はパフォーマンスが悪いが、次の検索からは速くなる。
- そのため、裏で先に検索を流しておき、コツコツとインデックスを先回りで作っておくなどの工夫が考えられる。
- 検索頻度を表すカラムを追加しておき、ストアドを使って裏で事前に高頻度キーワードのインデックスを作成する、という対応もありえる。
- 思想は「１回目の検索が遅いのはかんべんしてください。ただし２回目以降の検索は速いので許してください」
- 転置インデックスの更新同期はトリガーを使って取る。
- オンライン業務に影響を与えないよう、トランザクションに注意する必要がある。
■ 解決策の選択指針
- まずベンダ拡張を探し、最後の手段として転置インデックスという方法もあるよ、というくらい
■ タイトル 「プアマンズ・サーチエンジン」 の由来
- 「プアマンズ（poor man's）」という語から始まる単語は、英語圏では結構使われるとのこと。
- なので「プアマンズ」は使いたくないと思い、最初はタイトルを「手作りサーチエンジン」にしようとした。
- ところが、この章の最後「転置インデックスの自作」で、著者が本当に"手作り"してしまったので、その命名は止めたｗ
■ パターンマッチ述語と全文検索エンジンの速度比較
- 一般に、全文検索はインデックスサーチより速い。
- ただし、速度比は検索対象の複雑さとかAnd/OR検索などの条件による。
- And検索はSQLだとだいぶ辛い。
- grepが100倍くらい速くなった、という経験談あり。
- ただし特定の状況では何倍も遅くなった。
- それはUTF-8のオプティマイザチューニングのせいだった。
- UNICODEで日本語を扱うとなると、文字の正規化とかが必要になるので、簡単に地獄になる。。。
- 濁点を独立させるか否かの判断とか、悲惨。。。
■ 転置インデックスと交差テーブル（p.183）
- KeywordsテーブルのkeywordカラムにUNIQUE KEY制約を付与しているんだから、keyword_idカラムっていらなくね？
- いや、そうじゃない。
- もし交差テーブルを設けなかったら、１つのkeywordに対して複数のbug_idが紐付くため、多対多の組み合わせの数だけレコードが存在することになる。
- そうなると、keywordの文字列×組み合わせ数分だけDB容量が必要となってしまう。
- 頻出するkeywordが長かったりすると、かなりの容量を食うことになる。
- 検索回数を保管するカラムを用意する場合も、keywordsテーブルを分離しておけばカラム追加で対応できる。
■ あいまい検索時にSQLを２回発行する是非
- 以下のようにSQLを２回に分けて発行してはどうか？
- Select count(*) from Table Where xxx LIKE %one%;
- Select カラム名 from Table Where xxx LIKE %one%;
- １個目のSQLでは件数だけ取得して、その値が閾値以内なら２個目のSQLでデータを取得するようにする。
- いや、SQLを２回に分けても速度的に意味はない。
- ただしSQLのヒット件数が多すぎてメモリに乗らない場合は、１個目のSQLで打ち切る設計は王道だったりする。
- Webの一覧画面に表示する件数とページ送りについて考える時によく遭遇する。
- この辺のTogetterが参考になる。ちなみに１個目の話題は、２週間くらい前にホットエントリになっていた。
- 検索ヒット件数は正確な数字を返さない、という設計も手である。
- 例えばGoogle検索とかはその典型。
- ヒット件数をキャッシュしておき、大体の数字を返す。
- 一覧画面のページ送りとかページ戻りとかは、律儀に毎回検索するのではなく、裏で非同期処理で前後のページのデータを先読みしておくなどの工夫をする。
- ただし、ページをめくる速度が速すぎると非同期処理が間に合わないことがある点に注意。
■ 複数カラムからのあいまい検索
- 複数カラムから全文検索したい時、どーすれば良いか？
- 複数カラムをconcatすると、１カラム目の末尾と２カラム名の冒頭の単語が合成されて、検索にヒットするのでダメ。
- 並列処理で複数カラムそれぞれに全文検索をかけれるならば、処理性能的に有利になるかも。
- 16.5.6節の最初のSQLは、複数カラムからのあいまい検索を実現しているので参考になる。
■ 検索方法の選択をユーザに任せる
- 検索用のテキストボックスに「前方一致」と「中間一致」のラジオボタンを設けておき、ユーザに選択させる設計は見たことがある。
- 氏名による検索の場合、珍しい苗字の人は苗字のみ検索でヒットするので苗字だけ入力させ、田中さんとか佐藤さんとかありふれた名前の場合は苗字と名前の両方を入力させて検索させる、という設計があった。
■ まとめ
- SQLだけで頑張らない。
- SQL標準外の力を借りる。
★感想：
全文検索エンジンって、私は使ったこともないし、それどころかこの章を読むまでは存在さえ知りませんでした。
あいまい検索ってのは身近な要件なので、今後、使用を検討することがあるかもしれないと思いました。
ちなみに弊社でよく使うHiRDBにもあるかどうか調べてみたら、あった。。。
ミッションクリティカル業務向け全文検索エンジン 「HiRDB Text Search Plug-in」
あと、読書会の最後に @grimrose さんから鹿児島のお土産、おまんじゅう戴きました～
薩摩のお芋のおまんじゅう。
ちなみに「薩摩」と聞けば、私は「サツマイモ」よりも「薩摩藩」が真っ先に思い浮かぶ。
ちょうど司馬遼太郎の「竜馬がゆく」を読み直してたところだったんですが、幕末の薩摩藩は熱い志を持った漢達が多くて泣ける。。。
次回、１７章「スパゲティクエリ」は私が最初の説明を担当することになったので、早めに予習することにしよう。
皆様、ありがとうございました～
■おまけ：過去の「SQLアンチパターン読書会」ブログ
1章：SQLアンチパターン読書会 「ジェイウォーク」に参加しました
http://makopi23.blog.fc2.com/blog-entry-65.html
2章：SQLアンチパターン読書会 「ナイーブツリー」に参加しました
http://makopi23.blog.fc2.com/blog-entry-70.html
3章：SQLアンチパターン読書会 「IDリクワイアド」に参加しました
http://makopi23.blog.fc2.com/blog-entry-73.html
3章：SQLアンチパターン読書会 「続・IDリクワイアド」 に参加しました
http://makopi23.blog.fc2.com/blog-entry-77.html
4章；SQLアンチパターン読書会 「キーレスエントリー」 に参加しました
http://makopi23.blog.fc2.com/blog-entry-84.html
5章：SQLアンチパターン読書会 「EAV(エンティティ・アトリビュート・バリュー)」に参加しました
http://makopi23.blog.fc2.com/blog-entry-90.html
6章：SQLアンチパターン読書会 「ポリモーフィック関連」 に参加しました
http://makopi23.blog.fc2.com/blog-entry-94.html
7章：SQLアンチパターン読書会 「マルチカラムアトリビュート」に参加しました
http://makopi23.blog.fc2.com/blog-entry-97.html
8章：SQLアンチパターン読書会 「メタデータトリブル」 に参加しました
http://makopi23.blog.fc2.com/blog-entry-105.html
9章：SQLアンチパターン読書会 「ラウンディングエラー」 に参加しました
http://makopi23.blog.fc2.com/blog-entry-109.html
10章：SQLアンチパターン読書会 「サーティーワンフレーバー」に参加しました
http://makopi23.blog.fc2.com/blog-entry-115.html
11章：SQLアンチパターン読書会 「ファントムファイル」に参加しました
http://makopi23.blog.fc2.com/blog-entry-118.html
12章：SQLアンチパターン読書会 「インデックスショットガン」に参加しました
http://makopi23.blog.fc2.com/blog-entry-121.html
13章：SQLアンチパターン読書会 「フィア・オブ・ジ・アンノウン」に参加しました
http://makopi23.blog.fc2.com/blog-entry-128.html
14章：SQLアンチパターン読書会 「アンビギュアスグループ」に参加しました
http://makopi23.blog.fc2.com/blog-entry-130.html
15章：SQLアンチパターン読書会 「ランダムセレクション」に参加しました
http://makopi23.blog.fc2.com/blog-entry-133.html
- 関連記事
-
- DevLOVE "「アジャイルソフトウェア要求」を学ぶ。" に参加しました
- SQLアンチパターン読書会 「プアマンズ・サーチエンジン」に参加しました
- SQLアンチパターン読書会 「ランダムセレクション」に参加しました
