1. 全文検索は、どうして必要なの？
「全文検索」という言葉をご存知の方は多いと思います。
Wikipediaによると、全文検索とは、「複数の文書（ファイル）から特定の文字列を検索すること」です。イメージとしては、UNIXのgrepコマンドに近いかもしれません。grepコマンドでは、ファイルをシリアルに走査して文字列を探すため、データ量に比例した検索時間がかかります。 Oracle Database における、grepコマンドに相当する機能としては、ワイルドカード検索があります。例えば、データベース表から「ウェンディ」という文字列を含む行を探すには、
SELECT xxx FROM <表名> WHERE <列名> LIKE '%ウェンディ%'
のように検索を実行します。
中間一致のワイルドカード検索は、grepコマンドと同様、全データをシリアルに走査して文字列を探します。このため、データ量に比例した検索時間がかかります。
Oracle Database において、検索処理を速くする仕組みとして、すぐに思い浮かぶのは、B*TREE 索引です。しかし、B*TREE索引は、列値の前方一致または完全一致を高速に評価するためのものであり、全文検索のような中間一致を高速にすることはできません。 そこで、全文検索を高速に実行するための特別な仕組みが必要となってきます。
2. Oracle Database と文字列処理の仕組み
Oracle Database が持つ全文検索の仕組みは、Oracle Text と呼ばれています。 Oracle Text は、Oracle Database 本体のライセンスだけで利用できる機能です。Oracle Text を利用するために追加のオプション・ライセンスは必要ありません。また、Oracle Text は、Enterprise Edition だけではなく、Standard Edition や Standard Edition One でも利用できます。実は、無料で利用できる Express Edition でも使えます。製品サポートに関しては、DB本体のサポート契約だけで、Oracle Text に関するサポート対応が得られます。
Oracle Text の全文検索用の索引は、「CONTEXT 索引」(コンテキスト索引) と呼ばれています。 CONTEXT 索引は、内部的に4つの表と、1つのB*TREE索引から構成されます。
つまりOracle Textは、Oracle Databaseの基本的な表と索引を組み合わせることで、実現されている機能なのです。 それでは、どのように言語を処理し、Oracle Databaseに実装しているのかを見てみましょう。
特に $I 表は、全文検索のためのメインとなる表で、転置インデックス (inverted index) の構造を持ちます。 転置インデックスには、検索対象のデータに含まれる単語の位置情報が格納されます。 例えば、次のような表が全文検索の対象の場合・・・
ID TEXT
--- ------------------------------
1 Oracle Database
2 Oracle Text
転置インデックス($I表)には、次のようなデータが格納されます。
TOKEN_TEXT TOKEN_INFO
-------------------- -------------------------
Oracle 1-1, 2-1
Database 1-2
Text 2-2
この表の1行目で、「Oracle」という単語の出現位置情報が、「1-1, 2-1」となっています。これは、「Oracle」という単語が、1つ目の文書の1つ目の単語、および2つ目の文書の1つ目の単語として登場していることを表しています。
同様に、「Database」は、1つ目の文書の2つ目の単語として登場していますので、「1-2」です。「Text」は、2つ目の文書の2つ目の単語ですので、「2-2」です。
この転置インデックスで単語が格納された列 (上記の例では TOKEN_TEXT 列) に対して B*TREE 索引を作成することで、特定の単語を高速に検索する、すなわち全文検索を高速に行えるようになります。
3. 検索パフォーマンス
転置インデックスのサイズは、検索対象のサイズにほぼ比例して大きくなります。 それでは、検索パフォーマンスは、検索対象のサイズにほぼ比例して遅くなってしまうのでしょうか。 答えは No です。
すでに見たように、Oracle Text の転置インデックスには、検索を高速に実行するための B*TREE 索引が作成されています。 B*TREE 索引の検索パフォーマンスは、実際には検索対象のサイズにはほとんど影響を受けません。
これは、データ量が n 倍になった時、B*TREE 索引の深さは log n 増えるだけであることが理由です。(B*TREE索引本体のサイズはほぼ n 倍になります。)
例えば、1つの画面に20件の検索結果を表示するような検索アプリケーションの場合、元データのサイズが10倍になったとしても、B*TREE 索引へのアクセスにおいては、最大で20回のディスクI/Oが増えるだけです。仮に元データのサイズが1億倍 (＝10^8倍) になったとしても、B*TREE 索引へのアクセスにおいては、最大で20*8=160回のディスクI/Oが増えるだけです。これは、人間の感覚からすると、一瞬で終わる処理です。
さらに、B*TREE 索引や転置インデックス($I表)がデータベース・バッファ・キャッシュに乗っている場合には、検索はもっと高速になります。 具体的なパフォーマンス値として、260 GB の日本語テキスト・データに対する全文検索で、ディスクI/Oした場合で1秒程度、キャッシュにヒットした場合で0.05秒未満、という結果が残っています。参考までに、新聞2年分 (テキストのみ) で、およそ 1 GB 程度のようです。
4. Oracle Databaseと日本語文字列処理の仕組み
いま、日本語の全文検索の話が出ましたが、転置インデックスを作成するにあたっては、英語と日本語とでは、その処理方法が少し異なります。 英語の場合、単語がスペースで区切られているので、単語に基づく転置インデックスを作成することは容易です。
しかし、日本語の場合は、単語と単語がスペースで区切られておらず、英語のように、単語ベースの転置インデックスを作成することが困難です。 そこで Oracle Text では、日本語に対し、次の3通りの転置インデックスの作成方法を提供しています。
[1] 日本語を基本的に2文字ずつ区切って転置インデックスを作成する [2] 日本語の単語を辞書に基づいて認識し、その単語をベースに転置インデックスを作成する (単語辞書はカスタマイズ可能) [3] 日本語の単語を形態素解析に基づいて認識し、その単語をベースに転置インデックスを作成する [1] が、最も単純な方法で、[2]、[3] と番号が大きくなるにつれて、よりインテリジェント (＝CPUコストが高い) ものになっていきます。
転置インデックス作成の仕組みは、インテリジェントであればあるほどいいというものではなく、ユーザーの要件や、ハードウェアリソースとの兼ね合いで選択します。仕組みがインテリジェントであるほど、索引作成には時間がかかります。また、日本語の単語抽出は、100％正しく動作させることは難しく、誤った単語認識によって検索漏れが発生する場合があります。
このような背景から、日本では [1] の仕組みが主流となっています。 それでは、[1] の動作を簡単に見てみましょう。 例えば、次のようなデータが表に格納されている場合・・・
ID TEXT
--- ------------------------------
1 東京都港区
2 東京都千代田区
この表に、[1] の仕組みを適用すると、日本語テキストはそれぞれ、
- 「東京都港区」→「東京」「京都」「都港」「港区」「区」
- 「東京都千代田区」→「東京」「京都」「都千」「千代」「代田」「田区」「区」
のように分割され、転置インデックス($I表)は次のように作成されます。
TOKEN_TEXT TOKEN_INFO
-------------------- -------------------------
東京 1-1, 2-1
京都 1-2, 2-2
都港 1-3
港区 1-4
区 1-5, 2-7
都千 2-3
千代 2-4
代田 2-5
田区 2-6
検索時には、転置インデックスを作成する時と同じ仕組みで検索文字列が分割され、TOKEN_INFO 列の出現位置情報が照会された上で、検索結果が返されます。
たとえば、「千代田区」という検索条件は、まず、この文字列が「千代」、「代田」、「田区」のように分割され、このそれぞれを、転置インデックスから探し出します。この時、転置インデックスにはB*TREE索引が作成されており、高速に検索を実行可能であることを思い出してください。最後に、「千代」、「代田」、「田区」が、この順序で連続して出現しているドキュメントが探し出されます。このとき、各キーワードの出現位置情報が参照され、文書番号が同一で、オフセット位置が、この順で連続した整数値となっているもののみが返されます。
このように転置インデックスを作成することで、日本語のどの部分文字列で検索を行っても、検索結果が正しく返るようになります。
5. 参考文献
Oracle Text には、ここで紹介した以外にも、バイナリ・ファイルからテキスト文字列を抽出して索引を作成したり、HTMLタグやXMLタグに基づく索引を作成したりと、様々な機能があります。
さらに技術情報をお知りになりたい方は、以下の資料を参考にしていただければと思います。