はじめに
Spannerが全文検索に対応しました[1]。この機能の基本的な使い方をまとめます。
実際に使う上では、トークナイザの使い分けが大きな考慮点になるでしょう。
RDBにおける全文検索とは
リレーショナルデータベース（以下、RDB）は関係モデルに基づいてデータを格納するデータベースです。関係モデルでは正規化によってデータを編成しますが、この正規化の1つとして「第一正規形」があります。この正規形ではカラムの値がこれ以上分割できない、つまりスカラー値であることを求めます。正規化された値であれば、RDBはインデックスを作ることでカラムの値に対して完全一致検索を効率よく実行できます。
これに対して、全文検索は文字列や文章の中から部分一致する結果を検索するものです。これをRDBで素直に行うと、たとえば以下のようなクエリが考えられます。
SELECT id, memo FROM memos WHERE memo like '%keyword%';
クエリで使われているLIKE検索の部分一致は通常のインデックスでは検索することはできないため、テーブルフルスキャンが必要となり非常に高コストとなります。このような検索を効率的に行うために全文検索の仕組みがあります。
Spannerでの全文検索の概要
Spannerでは全文検索についておおむね以下の4ステップに分けて考えます。
- トークナイズ
- インデックス
- クエリ
- スコアリング
トークナイズ
全文検索におけるトークナイズ（Tokenize）とは検索対象の文字列をトークンと呼ばれる単位に分解する操作です。英語の文章を対象にした場合、トークンとは単語とするのが一般的です。英語はスペース区切りで表記するため、トークン分割はスペースや改行で分割する操作で完了する場合が多いです。
トークナイズを行った結果はリストになるため、Spannerではトークンのリスト用にTOKENLIST型が追加されており、トークナイザがTOKENLIST型を返します。
英語の文章のトークナイズ例
The quick brown fox jumps over the lazy dog
=> [the,quick,brown,fox,jumps,over,the,lazy,dog]
これに対して日本語は単語をスペース区切りで表記しないため、単語に分解するために自然言語処理による分解を行います。Spannerではこの処理を行うための関数としてTOKENIZE_FULLTEXTが用意されています。対象の言語を指定できるので日本語を対象にしたトークナイズであればlanguage_tag=>'ja'を引数で指定すると良いでしょう。Content-Typeも指定可能で、通常はデフォルトのtext/plainで十分です。検索対象の文字列がHTMLを含む事がわかっている場合にはtext/htmlを指定することで、タグが除去されたりキーワードがどのタグ中に出てきたかによって単語の重要度に反映されます。
よく使われるもう1つのトークナイズの方法として、N-Gramがあります。こちらは単語単位への分解ではなく、文字単位で機械的に分解する方法です。こちらは関数としてはTOKENIZE_NGRAMSで提供されています。
これら2つの方式は以降、単にFULLTEXT、NGRAMSと表記します。
二方式での分解の比較（TOKENLIST型は直接参照することができないため、DEBUG_TOKENLIST関数を介して表示しています。）
spanner> SELECT DEBUG_TOKENLIST(TOKENIZE_FULLTEXT("東京都港区", language_tag=>'ja'));
+--------------------------------------+
| |
+--------------------------------------+
| 東京(boundary), 都, 港, 区(boundary) |
+--------------------------------------+
1 rows in set (1.35 msecs)
spanner> SELECT DEBUG_TOKENLIST(TOKENIZE_NGRAMS("東京都港区"));
+------------------------------------------------------------------------------------------+
| |
+------------------------------------------------------------------------------------------+
| [京, 京都, 京都港, 区, 東, 東京, 東京都, 東京都港, 港, 港区, 都, 都港, 都港区], 京都港区 |
+------------------------------------------------------------------------------------------+
1 rows in set (2.86 msecs)
トークナイザの使い分け
では、トークナイザとして、どちらを使うのが適切でしょうか。
上記の例での「東京都港区」には文字列の中に「京都」を含みますが、検索結果として京都を含めべきかはアプリケーションの使い方に依存するでしょう。検索対象が日本語の文章として意味のある検索を行いたい場合はマッチしなくても良いですが、くまなくマッチしたい場合もあります。FULLTEXTでトークナイズした場合は「京都」は独立したトークンとしてはみなされませんでしたが、NGRAMSでは「京都」もトークンであるとみなされているのが分かります。アプリケーションの要件として、結果の網羅性が重要で検索漏れを減らしたい場合にはNGRAMSの方が有用です。
一方で、分解されたトークン数を見るとNGRAMSの方が多くなっています。これは文章など長いテキストを対象にトークナイズすると本の文字列よりも大幅に大きくなることを意味します。FULLTEXTは自然言語処理により単語に分解するため、トークンの数は抑えられます。トークンの数は保存するためのストレージサイズと検索速度に影響があります。
これらを踏まえて使い所を考えると、たとえばユーザーが入力したニックネームなどのように比較的短い文字列で文章として単語単位への分解が難しい検索対象の場合はNGRAMSを使い、レビューや記事の文章などある程度の長さがある文字列を検索対象にする場合にはFULLTEXTの方が適切でしょう。
その他の視点として
- 検索漏れを減らしたい場合にはNGRAMS、検索ノイズを減らしたい場合にはFULLTEXT
- トークンのデータサイズを抑えたい場合にはFULLTEXTの方が有利
- クエリで複雑な検索式を使いたい場合にはFULLTEXT
などが考慮点となります。
自然言語処理によるトークナイズとNGRAMの使い分けはSpanner特有ではなく、全文検索の一般的な実装での考慮点でもあります。そのためWikipediaの全文検索に関する記事でもこの二方式を比較しています。ここでの議論はSpannerでの全文検索機能にもほぼ適用可能です。
実際のテーブルへの適用
Wikipediaの記事タイトルとページビュー数を格納するテーブルを想定します。検索対象のカラム（以下の例では title）を全文検索するためには、検索対象とは別のトークンリストを持つカラムを追加することになります。
トークンリストは検索対象のカラムから自動生成されるカラムとして、また通常のアクセス時に見える必要はないため隠しカラムとして定義します。
CREATE TABLE articles (
article_id STRING(36) DEFAULT (GENERATE_UUID()),
title STRING(MAX),
views INT64 NOT NULL,
title_tokens TOKENLIST AS (TOKENIZE_FULLTEXT(title, language_tag=>'ja')) HIDDEN,
) PRIMARY KEY(article_id);
title_tokens カラムがトークンリストを保持しています。この例ではTOKENIZE_FULLTEXTをトークナイザとして、検索対象データが日本語であることを指定しています。
インデックス
トークナイズを行っただけでは効率的な検索を行えないため、実際にはトークンリストに対してインデックスをつけることで効率的な検索が行えます。
トークンリストを対象にしたインデックスはSEARCH INDEXという従来のセカンダリインデックスとは異なるインデックスを使います。
シンプルなインデックス定義例
CREATE SEARCH INDEX articles_search ON articles(title_tokens);
titleが検索をしたい文字列の入ったカラムですが、title_tokensというトークンリストのカラムを対象にしたインデックスであることに注意ください。セカンダリインデックスと同様にインターリーブなども指定可能です。
最終更新時刻で検索結果をソートしたい場合に効率的に検索できるようにするため、タイムスタンプをINT64型で保持しておきそのカラムもインデックスに対象にすることも有用です（ただし、通常のセカンダリインデックスと異なりTIMESTAMP型でのソートには対応していないのでご注意ください）。
今回の例では各記事のページビュー数のカラムがあるので、このカラムに対して降順で順序付けをしてみます。
CREATE SEARCH INDEX articles_search ON articles(title_tokens)
ORDER BY views DESC;
SEARCH INDEXは全文検索以外にも使うことができ、セカンダリインデックスではカバーしきれなかった複雑な検索でも利用できます。
クエリ
FULLTEXTでトークナイズされたカラムへのクエリではSEARCHという専用の関数を使って条件を指定します（NGRAMの場合はSEARCH_NGRAMSを使います）。
検索クエリの例
SELECT title,views from articles WHERE SEARCH(title_tokens,'ガンダム')
ORDER BY views DESC LIMIT 100;
実行計画
SEARCH INDEXにORDER BY views DESCを指定して作っていた場合、15行目のインデックスへのスキャンが100行で打ち切りできていて、ソートの必要がないことも分かります。
spanner> explain analyze SELECT title,views from articles WHERE SEARCH(title_tokens,'ガンダム') ORDER BY views DESC LIMIT 100;
+-----+--------------------------------------------------------------------------------------------------------------------------------------------------+---------------+------------+---------------+
| ID | Query_Execution_Plan | Rows_Returned | Executions | Total_Latency |
+-----+--------------------------------------------------------------------------------------------------------------------------------------------------+---------------+------------+---------------+
| 0 | Cross Apply | 100 | 1 | 29.93 msecs |
| 1 | +- [Input] VerifyDeterminism | | | |
| 2 | | +- TVF (Name: Search Query Conversion) | 1 | 1 | 0.23 msecs |
| 3 | | +- Unit Relation | 1 | 1 | 0 msecs |
| 7 | +- [Map] Global Limit | 100 | 1 | 29.69 msecs |
| 8 | +- Distributed Union (distribution_table: _Dist__Search2aryIndex_articles_search, preserve_subquery_order: true, split_ranges_aligned: false) | 100 | 1 | 29.68 msecs |
| 9 | +- Serialize Result | 100 | 1 | 29.65 msecs |
| *10 | +- Distributed Cross Apply (order_preserving: true) | 100 | 1 | 29.63 msecs |
| 11 | +- [Input] Create Batch | | | |
| 12 | | +- Compute Struct | 100 | 1 | 13.57 msecs |
| 13 | | +- Local Limit | 100 | 1 | 13.53 msecs |
| 14 | | +- Local Distributed Union (preserve_subquery_order: true) | 100 | 1 | 13.53 msecs |
| 15 | | +- SearchIndex Scan (SearchIndex: articles_search, scan_method: Scalar) | 100 | 1 | 13.52 msecs |
| 28 | +- [Map] Cross Apply | 100 | 1 | 15.69 msecs |
| 29 | +- [Input] KeyRangeAccumulator | | | |
| 30 | | +- Batch Scan (Batch: $v2, scan_method: Scalar) | | | |
| 34 | +- [Map] Local Distributed Union | 100 | 100 | 15.59 msecs |
| 35 | +- Filter Scan | | | |
| *36 | +- Table Scan (Table: articles, scan_method: Scalar) | 100 | 100 | 15.52 msecs |
+-----+--------------------------------------------------------------------------------------------------------------------------------------------------+---------------+------------+---------------+
Predicates(identified by ID):
10: Split Range: IS_NOT_DISTINCT_FROM($articles_key_article_id'5, $articles_key_article_id'4)
36: Seek Condition: IS_NOT_DISTINCT_FROM($articles_key_article_id'5, $batched_articles_key_article_id'4)
100 rows in set (37.12 msecs)
timestamp: 2024-08-20T12:27:32.945172+09:00
cpu time: 14.32 msecs
rows scanned: 301 rows
deleted rows scanned: 0 rows
optimizer version: 6
optimizer statistics: auto_20240817_22_55_31UTC
SEARCH関数の引数にはトークナイズしたカラム（ここではtitle_tokens）、キーワードを与えます。ソート用のカラムもインデックスに含めていた場合、このようなクエリはインデックススキャンを途中で打ち切り可能となるため、効率的に実行可能です。
トークナイザがFULLTEXTの場合は拡張検索を有効にすることで、あいまい検索を含む拡張検索が可能で、GoogleでのWeb検索のような検索語の指定が可能です。以下に例を挙げます。
SELECT title FROM articles
WHERE SEARCH(title_tokens, 'ドラゴン -クエスト', enhance_query=>true);
たとえばこの例では「ドラゴン」を含むが、「クエスト」は含まないという記事タイトルを検索するというクエリとなります。もう少し複雑な()やORを含む検索式も指定可能です。
SELECT title FROM articles
WHERE SEARCH(title_tokens, '(東京 オリンピック) OR マラソン', enhance_query=>true);
スコアリング
検索結果は最終更新日などのカラムでソートしたい場合もありますが、文書検索などで検索キーワードの出現頻度など関連度が高い順で表示したい場合もあると思います。このような処理のためにSpannerではSCORE関数でランク付けをできます。この関数は概ねTF-IDF（TF-IDFは非常にざっくり説明すると、単語の出現頻度と対象の単語のユニークさで重み付けをする手法です）に基づき計算される値を返します。
SELECT title,views from articles WHERE SEARCH(title_tokens,'ガンダム')
ORDER BY SCORE(title_tokens, 'ガンダム') DESC LIMIT 100;
この例では記事タイトルという比較的短い文字列を対象にしているため、あまり適切な例ではありませんが検索結果の上位にはキーワードが複数出てくるレコードが返されます。
記事タイトルよりも長い記事本文などのような文章を対象にした検索時に利用するとよいでしょう。
まとめ
Spannerでの全文検索機能について紹介しました。RDBでの全文検索機能はMySQLやPostgreSQLのRDBにも実装されており、使ったことがある方も多いと思います。基本的なコンセプトは似ているため、同じ機能を使う範囲であればSpannerの全文検索機能がそれらと大きく変わるものではありません。トークナイザとインデックスが分離されているところなどがやや特徴的です。トークナイザにはGoogleのWeb検索での自然言語処理ノウハウが使われており、その拡張検索機能がユニークな点です。
-
2024年10月7日に正式リリースされました。 ↩︎
Discussion