More than 5 years have passed since last update.

16章プアマンズ・サーチエンジン(貧者のサーチエンジン)

Last updated at 2014-12-04Posted at 2014-12-03

16.1 目的：全文検索を行う

FAQ Webサイトなどで、キーワードで全文検索を行いたい。

要件

検索語との一致度の高い記事を上位に表示
語形変化対応( crash, crashed, crashed, crashing)
スケールすること

これをSQLで実現することは困難と伴う。これはそもそもSQL(とその背後にリレーショナル理論)の原則に、列の値のアトミック性があるためである。つまり、SQLは列の値全体での比較は得意だが、部分文字列の比較は非効率となる。

16.2 アンチパターン：パターンマッチング述語を使う

SQLのパターンマッチング述語を使おう。

Like演算子

SELECT * FROM Bugs WHERE description LIKE '%crash%';

MySQLの正規表現述語

SELECT * FROM Bugs WHERE description REGEXP 'crash';

問題点
- パフォーマンス低下
  - インデックスが使えず、テーブルスキャンが発生
- 意図しないマッチの発生
  - '%one%'で'%money%'がヒットするなど
  - ただし単語境界をサポートするデータベースもある
    - MySQL: SELECT * FROM Bugs WHERE description REGEXP '[[:<:]]one[[:>:]]'
    - 正規表現のメタ文字\b(単語境界), \B(単語境界以外)
    - 日本語の場合どうする？

16.3 アンチパターンの見つけ方

「Like述語の2つのワイルドカードの間に変数を挿入する方法を知らない？」
「複数の語を含む文字列の正規表現はどうやって書ける？」
「特定の語を含まない文字列の正規表現はどうやって書ける？」
「ある語の語形のどれかを含む文字列の正規表現はどうやって書ける？」
「検索機能は、データベースのデータが増えると、許容できないほど遅くなるけど何故？」

16.4 アンチパターンを用いても良い場合

検索したいケースが単純である
パフォーマンスが問題にならない場合

16.5 解決策: 適切なツールを使用する

解決策その１：そもそもSQLを用いない。専用の全文検索エンジンを用いる。

解説策その２：SQL標準に準拠しつつ、部分文字列マッチングより効率的な転置インデックスを用いる。

#16.5.1 ベンダ拡張

主要なデータベース製品では、全文検索というあり増えた要件に対して、独自の解決策を用意している。ただしベンダー間で互換性はない。

#16.5.2 MySQLのフルテキストインデックス

特徴

MyISAM(MySQL3.23以降)
InnoDB(MySQL5.6以降)
CHAR, VARCHAR, TEXT型のみ
日本語の分かち書き非対応なので、使おうと思うと事前に分かち書きしてスペース区切りにしてからDBに格納する

フルテキストインデックスの定義

ALTER TABLE Bugs ADD FULLTEXT INDEX bugfts (summary, description);

問い合わせ

SELECT * FROM Bugs WHERE MATCH(summary, description) AGAINST ('crash');

問い合わせ(MySQL4.1以降)

SELECT * FROM Bugs WHERE MATCH(summary, description) AGAINST ('+crash -save' IN BOOLEAN MODE);

#16.5.4 Oracleでのテキストインデックス

単一のテキスト列用のインデックス、短いテキストに特化したインデックス、XMLドキュメントの検索に特化したインデックスなどがある

#16.5.4 Microsoft SQL Serverでの全文検索

フルテキストインデックスを作成後、CONTAINS述語でクエリ検索できる。

16.5.5 PostgreSQL

専用のデータ型TSVECTORを用い、そのカラムに対して汎用転地インデックス(GIN)を作成する。その後テキスト検索演算子@@を使うことで全文検索ができる。

16.5.6　SQLite

SQLiteの拡張機能 FTSを用いることで利用可能である。

16.5.7 サードパーティーのサーチエンジン

データベース製品独自の機能に依存したくない場合は、SQLデータベースから独立して動作する検索エンジンが利用できる。

Sphinx Serach
- MySQLやPostgreSQLとうまく連携できる
- インデックスの作成と検索が高速
- 分散クエリもサポート
- 更新頻度が低いデータに対して、高いスケーラビリティを出すことに向く
Apache Lucene
- 独自形式のインデックスを構築。データを更新すると、都度Luceneのインデックスの更新が必要

16.5.8 転置インデックスの自作

転置インデックスとは、検索対象になりえる全ての語のリストのことである。これを自作することで、SQLだけで完結した全文検索が実現できる。

ユーザーが検索するキーワード一覧を格納するKeywordsテーブルと、多対多関係のための交差テーブルBugsKeywordsを定義する。

CREATE TABLE Keywords (
  keyword_id SERIAL PRIMARY KEY,
  keyword    VARCHAR NOT NULL,
  UNIQUE KEY (keyword)
);

CREATE TABLE BugsKeywords (
  keyword_id INT NOT NULL,
  bug_id     INT NOT NULL,
  PRIMARY KEY (keyword_id, bug_id)
);

ユーザーが全文検索するときのフロー

キーワードをKeywordsからSELECT
存在していなかった場合
- KeywordsにINSERT
- 新しいキーワードで、Bugsテーブルを全文検索
- マッチしたBugsのレコードについて、交差テーブルにINSERT
交差テーブルより、そのキーワードを含むBugsをSELECT

特徴

ユーザーが新規単語で検索する場合、全文検索が発生
- あらかじめ全ての単語に対し、キーワードリストを用意しておけば回避可能
編集があった場合、交差テーブルの更新が必要
Keywordsテーブルに、ユーザーがそのキーワードを検索するたびに値が増える列を用意することで、どのキーワードへの需要が高いか分かる。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

16章 プアマンズ・サーチエンジン(貧者のサーチエンジン)