MySQLの曖昧検索にもうlike+%は不要

はじめに

InnoDBで曖昧検索を行う際に「%xx」を使用するとインデックスが効かなくなることはよく知られていますが、要件上そうせざるを得ない場合も多々あります。例えば、検索エンジンではユーザーデータのキーワードに基づく全文検索が必要であり、eコマースサイトではユーザーの検索条件に基づいて商品詳細説明内を検索する必要が生じることがあります。これらはB+ツリーインデックスではうまく処理できません。

数値比較や範囲フィルタリングなどにより、必要なクエリの大半は実現できます。しかし、キーワードのマッチングによるクエリフィルタリングが必要な場合、従来の厳密な数値比較ではなく、類似度に基づくクエリが必要となります。全文インデックスは、まさにこのようなシナリオのために設計されています。

全文検索（Full-Text Search）は、データベースに格納された書籍や記事全体から任意の情報を抽出する技術です。必要に応じて章、節、段落、文、単語などの情報を取得でき、様々な統計や分析も行えます。

初期のMySQLではInnoDBは全文検索技術をサポートしていませんでしたが、MySQL 5.6からInnoDBが全文検索をサポートするようになりました。

転置インデックス

全文検索は通常、転置インデックス（inverted index）を用いて実現されます。転置インデックスはB+ツリーと同様、インデックス構造の一種です。補助テーブルに単語と、その単語が1つ以上のドキュメント内で出現する位置とのマッピングを格納し、通常は連想配列を用いて実装されます。表現形式には以下の2種類があります。

inverted file index: {単語, 単語が出現するドキュメントのID}
full inverted index: {単語, (単語が出現するドキュメントのID, そのドキュメント内での位置)}

上図はinverted file indexの連想配列です。単語"code"がドキュメント1と4に存在していることが分かります。このように格納しておけば、全文クエリは単純にDocumentsから検索キーワードを含むドキュメントを直接取得できます。一方、full inverted indexはペア（DocumentId, Position）を格納するため、その転置インデックスは下図のようになります。例えばキーワード"code"はドキュメント1の6番目の単語とドキュメント4の8番目の単語に存在します。full inverted indexはより多くの領域を消費しますが、データの位置特定が容易になり、検索機能を拡張できます。

全文検索

全文インデックスの作成

テーブル作成時に全文インデックスを作成する構文は以下の通りです。

CREATE TABLE table_name ( id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY, author VARCHAR(200),
title VARCHAR(200), content TEXT(500), FULLTEXT full_index_name (col_name) ) ENGINE=InnoDB;

クエリ文を入力します。

SELECT table_id, name, space from INFORMATION_SCHEMA.INNODB_TABLES
WHERE name LIKE 'test/%';

上記6つのインデックステーブルが転置インデックスを構成し、補助インデックステーブルと呼ばれます。入力されたドキュメントがトークン化されると、単語は位置情報および関連するDOC_IDとともに、単語の最初の文字の文字セットソート重みに基づいて6つのインデックステーブルに完全にソートおよび分割されます。

既存のテーブルに全文インデックスを作成する構文は以下の通りです。

CREATE FULLTEXT INDEX full_index_name ON table_name(col_name);

全文インデックスの使用

MySQLデータベースは全文検索のクエリをサポートしています。全文インデックスはInnoDBまたはMyISAMテーブルでのみ使用でき、char、varchar、text型のカラムに対してのみ作成できます。

構文は以下の通りです。

MATCH(col1,col2,...) AGAINST(expr[search_modifier])
search_modifier:
{
    IN NATURAL LANGUAGE MODE
    | IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION
    | IN BOOLEAN MODE
    | WITH QUERY EXPANSION
}

全文検索はMATCH() AGAINST()構文を使用して実行します。MATCH()はカンマ区切りのリストで検索対象のカラムを指定します。AGAINST()は検索文字列と、実行する検索タイプを指定するオプションの修飾子を受け取ります。全文検索には3種類のタイプがあります：自然言語検索、ブーリアン検索、クエリ拡張検索。以下、各検索モードについて説明します。

Natural Language

自然言語検索は、検索文字列を自然言語のフレーズとして解釈します。MATCH()はデフォルトでNatural Languageモードを使用し、指定されたキーワードを含むドキュメントをクエリします。

次に、demoを使ってNatural Languageをより理解しましょう。

SELECT
    count(*) AS count
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( 'MySQL' );

上記の文は、title、body列に'MySQL'キーワードを含む行数をクエリします。また、以下のように記述することもできます。

SELECT
    count(IF(MATCH ( title, body )
    against ( 'MySQL' ), 1, NULL )) AS count
FROM
    `fts_articles`;

上記2つの文は同じ結果を返しますが、内部処理を見ると2番目のSQLの方が実行速度が速くなります。これは1番目のSQL（whereインデックスによるクエリ方式）では関連性のソート統計処理が追加で必要になるのに対し、2番目の方式では不要だからです。

また、SQL文で関連性をクエリすることもできます。

SELECT
    *,
    MATCH ( title, body ) against ( 'MySQL' ) AS Relevance
FROM
    fts_articles;

関連性の計算は以下の4つの条件に基づきます。

wordがドキュメント内に出現するかどうか
wordがドキュメント内に出現する回数
インデックス列内のwordの数
いくつのドキュメントがそのwordを含んでいるか

InnoDBストレージエンジンの全文検索では、さらに以下の要素を考慮する必要があります。

クエリのwordがストップワード列にある場合、その文字列のクエリは無視されます。
クエリのwordの文字長が範囲[innodb_ft_min_token_size, innodb_ft_max_token_size]内にあるかどうか

単語がストップワードに含まれている場合、その単語はクエリされません。例えば'for'という単語をクエリした結果は以下の通りです。

SELECT
    *,
    MATCH ( title, body ) against ( 'for' ) AS Relevance
FROM
    fts_articles;

'for'はドキュメント2、4に出現していますが、ストップワードであるため関連性は0となっています。

パラメータinnodb_ft_min_token_sizeとinnodb_ft_max_token_sizeは、InnoDBエンジンにおけるクエリ文字の長さを制御します。長さがinnodb_ft_min_token_size未満、またはinnodb_ft_max_token_sizeを超える場合、その単語の検索は無視されます。InnoDBエンジンでは、innodb_ft_min_token_sizeのデフォルト値は3、innodb_ft_max_token_sizeのデフォルト値は84です。

Boolean

ブーリアン検索は、特殊なクエリ言語のルールに従って検索文字列を解釈します。この文字列には検索対象の単語が含まれ、さらに要件を指定する演算子を含めることもできます。例えば、マッチする行に特定の単語が存在する、または存在しない、あるいはその重みが通常より高い、または低いことを指定できます。次の文は、文字列"Pease"を含み"hot"を含まないドキュメントをクエリするものです。+と-はそれぞれ単語が必ず存在する、または存在しないことを示します。

select * from fts_test where MATCH(content) AGAINST('+Pease -hot' IN BOOLEAN MODE);

Boolean全文検索でサポートされるタイプは以下の通りです。

+：単語が必ず存在することを示す
-：単語が必ず存在しないことを示す
(演算子なし)その単語はオプションだが、出現した場合の関連性はより高くなる
@distance クエリする複数の単語間の距離がdistance以内であることを示す。distanceの単位はバイト。この全文検索はProximity Searchとも呼ばれる。例：MATCH(context) AGAINST('"Pease hot"@30' IN BOOLEAN MODE) は文字列Peaseとhotの距離が30バイト以内であることを要求する。
：単語が出現した場合に関連性を上げる
<：単語が出現した場合に関連性を下げる
~：単語の出現を許容するが、出現した場合の関連性は負になる
*：その単語で始まる単語。例：lik*はlik、like、likesを許容する
" ：フレーズを示す

以下はBoolean Modeの使用例です。

demo1：+ -

SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( '+MySQL -YourSQL' IN BOOLEAN MODE );

上記の文は、'MySQL'を含み'YourSQL'を含まない情報をクエリします。

demo2： no operator

SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( 'MySQL IBM' IN BOOLEAN MODE );

上記の文は、'MySQL IBM'に'+'、'-'の識別がないため、単語はオプションであり、出現した場合に関連性が高くなります。

demo3：@

SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( '"DB2 IBM"@3' IN BOOLEAN MODE );
上記の文は、"DB2"と"IBM"の2つの単語間の距離が3バイト以内であることを示します。

demo4：> <

SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( '+MySQL +(>database <DBMS)' IN BOOLEAN MODE );

上記の文は、'MySQL'、'database'、'DBMS'をすべて含む行情報をクエリしますが、'DBMS'を含まない行の関連性が'DBMS'を含む行よりも高くなります。

demo5: ~

SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( 'MySQL ~database' IN BOOLEAN MODE );

上記の文は、'MySQL'を含む行をクエリしますが、その行が同時に'database'を含む場合、関連性が低下します。

demo6：*

SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( 'My*' IN BOOLEAN MODE );

上記の文は、キーワードに'My'を含む行情報をクエリします。

demo7："

SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH ( title, body ) AGAINST ( '"MySQL Security"' IN BOOLEAN MODE );

上記の文は、正確なフレーズ'MySQL Security'を含む行情報をクエリします。

Query Expansion

クエリ拡張検索は自然言語検索の変形です。このクエリは通常、検索キーワードが短すぎてユーザーに暗示的知識（implied knowledge）が必要な場合に使用されます。例えば、databaseという単語のクエリでは、ユーザーはdatabaseを含むドキュメントだけでなく、MySQL、Oracle、RDBMSなどの単語を含むドキュメントも検索したい場合があります。このような場合にQuery Expansionモードを使用して全文検索の暗示的知識を有効にできます。

クエリ文にWITH QUERY EXPANSION / IN NATURAL LANGUAGE MODE WITH QUERY EXPANSIONを追加することで、ブラインドクエリ拡張（自動関連性フィードバックとも呼ばれる）を有効にできます。このクエリは2つのフェーズで構成されます。

第1フェーズ：検索語に基づいて全文インデックスをクエリ
第2フェーズ：第1フェーズで生成されたトークンに基づいて再度全文検索を実行

次に、Query Expansionの使用例を見てみましょう。

-- インデックスを作成
create FULLTEXT INDEX title_body_index on fts_articles(title,body);

-- Natural Language モードでクエリ
SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH(title,body) AGAINST('database');

Query Expansion使用前のクエリ結果：

-- Query Expansion モードでクエリ
SELECT
    *
FROM
    `fts_articles`
WHERE
    MATCH(title,body) AGAINST('database' WITH QUERY expansion);

Query Expansion使用後のクエリ結果：

Query Expansionの全文検索は多くの無関係なクエリを引き起こす可能性があるため、使用には十分な注意が必要です。

全文インデックスの削除

全文インデックスを直接削除する構文は以下の通りです。

DROP INDEX full_idx_name ON db_name.table_name;

alter tableを使用して全文インデックスを削除する構文は以下の通りです。

ALTER TABLE db_name.table_name DROP INDEX full_idx_name;

まとめ

本稿では、理論と実践を組み合わせてfulltext indexについて紹介しました。MySQLにご興味があれば、引き続きMySQLコラムをご覧ください。

MySQLの曖昧検索にもうlike+%は不要

はじめに

転置インデックス

全文検索

全文インデックスの作成

全文インデックスの使用

Natural Language

Boolean

Query Expansion

全文インデックスの削除

まとめ

関連読書

MySQL最適化のコツ：5つのステップ + 10の事例

MySQL 8.0.28 x64 Windows向け超軽量ポータブル版、わずか16MB

プロジェクトでよく使われる19のMySQL最適化

DockerでMySQLを動かしてる？おめでとう、解雇だ！