250K +文字列のワイルドカード検索のための高速な方法

Question

MySQLデータベースの英文辞書が250Kをわずかに超える英文辞書があり、単純なルビのフロントエンドを使ってその先頭にワイルドカードを使用して検索しています文字列。これまでのところ、私はこのようにそれを行ってきた：

SELECT * FROM words WHERE word LIKE '_e__o' 

あるいは

SELECT * FROM words WHERE word LIKE '____s' 

私はいつも言葉の正確な長さを知っているが、単一の文字が、すべては潜在的に未知です。

これは糖蜜よりも遅く、先頭のワイルドカードのない類似のクエリよりも約15倍遅くなります。これは、その列のインデックスを使用できないためです。

私は、検索の範囲を狭めるいくつかの方法を試しました。たとえば、私は各単語の個々の文字数を含む26の追加の列を追加し、それらを最初に使って検索を絞り込みました。私も単語の長さで絞り込みを試みました。これらのメソッドは、ワイルドカード検索の本質的な非効率性のおかげでほとんど違いはありませんでした。私はさらに遅いREGEXPステートメントを試しました。

SQLiteとPostgreSQLはMySQLと同じくらい制限されていますが、NoSQLシステムの経験は限られていますが、私の研究は、私が必要とするパフォーマンスではなくスケーラビリティに優れているという印象を与えてくれます。

私の質問はどこで解決策を探すべきですか？クエリを最適化する方法や、潜在的なレコードセットを絞り込むことのできる補助列を追加する方法を見つけようとしていますか？このような状況でワイルドカード検索を高速に実行できるように設計されたシステムはありますか？

Answer 1

PostgreSQL 9.1およびpg_trgm拡張では、あなたが記述しているような条件で使用できるインデックスを作成できます。例えば

はこちらを参照してください。http://www.depesz.com/2011/02/19/waiting-for-9-1-faster-likeilike/

私はLIKE '____1'を使用して30万行をテーブルの上にそれを検証し、それは、このようなインデックスを使用しません。そのテーブルの行数を（古いラップトップの）数えるには約120msかかりました。面白いことに、表現LIKE 'd___1'はそれほど高速ではありませんが、それはほぼ同じ速度です。

それはまた、検索用語の文字数にもよりますが、それが取得するロンジーの数によって異なりますが、それは私が知る限り遅くなります。

パフォーマンスが許容できる場合は、データで確認する必要があります。

Answer 2

フルテキスト検索エンジンApache Luceneを試すことができます。このような質問に答えるために作られたので、もっと運があるかもしれません。

Wildcard searching with lucene。

Answer 3

メモリ内ルックアップテーブルソリューションを作成します。各長さのソートテーブルを作成できます。

次に、4番目と8番目の文字が一致するように、各4番目の文字のみをチェックします。彼らはすべて同じ長さですので、すばやくなります。文字が一致する場合のみ、8番目の文字を確認します。

それはブルートフォースですが、速くなります。あなたが50,000の8文字の単語を持っている最悪の場合を考えてみましょう。 50,000回の比較。ルビー実行時間perf問題を仮定すると、それはまだ< 1秒であるはずです。

必要なメモリは250k x 10です。したがって、2.5メガバイトです。

Answer 4

私は最初に単語を挿入してインデックスを設定するのにかかる時間は重要ではないと仮定しています。また、単語リストの更新を頻繁にはしないので、基本的に静的なデータです。

あなたは、このようなアプローチを試みることができる： - あなたは常にワード長さを知っているので

など、長さ1のすべての単語、単語の長さ2の別のテーブルを含むテーブルを作成し、

• をクエリを実行するときは、単語の長さに基づいて適切なテーブルから選択します。それでも、そのテーブルをフルスキャンする必要があります。

RDBMSで使用できる場合は、1つのテーブルと単語の長さで分割する方がよいでしょう。

まだ十分な速度でない場合は、さらに長さと既知の文字で分割できます。たとえば、「Z」を含む8文字すべての単語をリストした表を作成できます。

質問すると、「E」と「Z」を含む8文字の単語があることがわかります。最初にデータ辞書を照会して、どの文字が8文字の単語で稀であるかを調べ、その表をスキャンします。データ辞書を照会すると、テーブルwords_8Eまたはテーブルwords_8zのレコード数が最も少ないことがわかります。通常のフォームとグッドプラクティス

について

これは、データをモデル化するとき、私は一般的に推薦するものの一種ではありません。あなたの特別な場合、単語全体を1文字の列に格納するのは実際には1st normal formにはありません。これは、単語内の個々の要素を気にするためです。あなたのユースケースを考えると、単語は単一の単語よりも文字のリストです。いつものように、どのようにモデル化するかは、気にするものに依存します。

あなたの質問は、それが最初の通常の形式ではないため、問題を引き起こしています。

この問題の完全正規化モデルには、word（WordId PK）とWordLetter（WordId PK、Position PK、Letter）の2つのテーブルがあります。その後、適切な位置に複数のWHERE EXISTS文字を含むすべての単語を照会します。

データベースの理論によれば正しいが、これはうまくいくとは思わない。

Answer 5

すべてがインデックスに登録されます。

create table letter_index (
    id integer not null primary key, 
    letter varchar(1), 
    position integer 
) 

create unique index letter_index_i1 (letter, position) 

create table letter_index_words (
    letter_index_id integer, 
    word_id integer 
) 

その後

インデックスあなたの言葉のすべて：

あなたのような表を作成することができます。

あなたは第二位の「E」で、すべての単語のリストが必要な場合：

select words.* from words, letter_index_word liw, letter_index li 
where li.letter = 'e' and li.position = 2 
and liw.letter_index_id = li.id 
and words.id = liw.word_id 

あなたは第二位の「E」、および「S」内での単語のすべてをしたい場合5番目の位置：

select words.* from words, letter_index_word liw, letter_index li 
where li.letter = 'e' and li.position = 2 
and liw.letter_index_id = li.id 
and words.id = liw.word_id 
and words.id in (
    select liw.word_id from letter_index_word liw, letter_index li 
    where li.letter = 's' and li.position = 5 
    and liw.letter_index_id = li.id 
) 

2つの簡単なクエリを実行して、結果を自分でマージすることができます。

もちろん、メモリ内のリストをキャッシュして反復するだけで、これらのいずれよりも高速になる可能性があります。しかし、毎回DBから250Kリストをロードする価値があるほど速くはありません。

Answer 6

これは実際の解決策より多くの演習です。アイデアは、単語を文字に分割することです。

最初に必要なテーブルを設計します。

INSERT INTO letter_search 
    (word_id, position, letter) 
SELECT 
    w.word_id 
    , num.i 
    , SUBSTRING(w.word, num.i, 1) 
FROM 
    words AS w 
    JOIN 
    num 
     ON num.i <= w.size 

サイズ：

CREATE TABLE num 
(i UNSIGNED TINYINT NOT NULL 
, PRIMARY KEY (i) 
) ; 

INSERT INTO num (i)    --- I suppose you don't have 
VALUES       --- words with 100 letters 
    (1), (2), ..., (100) ; 

当社letter_searchテーブルを移入するには：

CREATE TABLE letter_search 
(word_id INT NOT NULL 
, position UNSIGNED TINYINT NOT NULL 
, letter CHAR(1) NOT NULL 
, PRIMARY KEY (word_id, position) 
, FOREIGN KEY (word_id) 
    REFERENCES words (word_id) 
     ON DELETE CASCADE 
     ON UPDATE CASCADE 
, INDEX position_letter_idx (position, letter) 
, INDEX letter_idx (letter) 
) ENGINE = InnoDB ; 

我々はauxilary "数字" テーブルをする必要があります：私はあなたのwords表は列word_id, word, sizeていると仮定しますこの検索テーブルのサイズは約10 * 250K行（ここでは10、あなたの言葉の平均サイズを入力します）です。あなたは、結果セットのサイズよりも、それ以上をスキャンすることなく、完全にインデックスこのクエリをすることができます

SELECT w.* 
FROM 
    words AS w 
    JOIN 
    letter_search AS s2 
     ON (s2.position, s2.letter, s2.word_id) = (2, 'e', w.word_id) 
    JOIN 
    letter_search AS s5 
     ON (s5.position, s5.letter, s5.word_id) = (5, 'o', w.word_id) 
WHERE 
    w.size = 5 

Answer 7

：

SELECT * FROM words WHERE word LIKE '_e__o' 

のように記述されます。最後に、クエリは

---

これは最適です。

そうのようなルックアップテーブルを作成します。あなたのワードテーブルを参照する

Table: lookup 
pattern  word_id 
_o_s_  1 
_ous_  1 
... 

を：

Table: word 
word_id  word 
1   mouse 

パターンにインデックスを入れて、そのような選択を実行します。

select w.word 
from lookup l, word w 
where l.pattern = '_ous_' and 
l.word_id = w.word_id; 

もちろん、このルックアップテーブルを作成するには、パターンが可能なすべてのパターンである小さなルビースクリプトが必要です辞書のすべての単語。つまり、マウス用のパターンは次のようになります。

m____ 
mo___ 
mou__ 
mous_ 
mouse 
_o___ 
_ou__ 
... 

与えられた単語のすべてのパターンを生成するためのRubyは次のようになります。たとえば

def generate_patterns word 
    return [word, '_'] if word.size == 1 
    generate_patterns(word[1..-1]).map do |sub_word| 
    [word[0] + sub_word, '_' + sub_word] 
    end.flatten 
end 

：

> generate_patterns 'mouse' 
mouse 
_ouse 
m_use 
__use 
mo_se 
_o_se 
m__se 
___se 
mou_e 
_ou_e 
m_u_e 
__u_e 
mo__e 
_o__e 
m___e 
____e 
mous_ 
_ous_ 
m_us_ 
__us_ 
mo_s_ 
_o_s_ 
m__s_ 
___s_ 
mou__ 
_ou__ 
m_u__ 
__u__ 
mo___ 
_o___ 
m____ 
_____ 

Answer 8

速いですそれを10分の1に減少させる方法は、文字列長の列を作成し、その上に索引を付けてwhere句で使用することです。