11

MySQL データベースに英語の辞書があり、エントリは 250,000 を少し超えています。シンプルな Ruby フロントエンドを使用して、文字列の先頭にワイルドカードを使用して検索しています。これまでのところ、私は次のようにしています。

SELECT * FROM words WHERE word LIKE '_e__o'

あるいは

SELECT * FROM words WHERE word LIKE '____s'

単語の正確な長さは常に知っていますが、1 文字を除いてすべてが不明な可能性があります。

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

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

SQLite と PostgreSQL は MySQL と同じように制限があり、NoSQL システムの経験は限られていますが、私の調査では、必要なパフォーマンスではなく、スケーラビリティに優れているという印象を受けました。

私の質問は、どこで解決策を探すべきですか? クエリを最適化する方法や、潜在的なレコードセットを絞り込むための補助列を追加する方法を探し続ける必要がありますか? この流れで高速なワイルドカード検索を実現するために特別に設計されたシステムはありますか?

4

8 に答える 8

5

PostgreSQL 9.1 と pg_trgm 拡張機能を使用すると、記述しているような条件に使用できるインデックスを作成できます。

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

を使用して30万行のテーブルで確認しましたが、LIKE '____1'そのようなインデックスを使用しています。そのテーブルの行数をカウントするのに約 120 ミリ秒かかりました (古いラップトップで)。興味深いことに、式LIKE 'd___1'は速くはなく、ほぼ同じ速度です。

また、検索用語の文字数にも依存します。私が知る限り、検索が長くなるほど遅くなります。

パフォーマンスが許容できるかどうかをデータで確認する必要があります。

于 2012-04-11T22:58:21.783 に答える
1

10倍程度にする簡単な方法は、文字列の長さの列を作成し、それにインデックスを付けて、where句で使用することです。

于 2012-04-12T02:28:08.043 に答える
1

それはすべて索引付けに帰着します。

次のようなテーブルを作成できます。

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
)

次に、すべての単語にインデックスを付けます。

2 番目の位置に「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

2 番目の位置に「e」があり、5 番目の位置に「s」があるすべての単語が必要な場合:

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 のリストをロードする価値があるほど高速ではありません。

于 2012-04-11T22:57:04.480 に答える
1

最適な結果セットのサイズを超えてスキャンする必要なく、このクエリを完全にインデックス化できます。

次のようにルックアップ テーブルを作成します。

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;

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

m____
mo___
mou__
mous_
mouse
_o___
_ou__
...

特定の単語のすべてのパターンを生成するルビは、次のようになります。

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____
_____
于 2012-04-12T00:01:02.273 に答える
1

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

次のようなアプローチを試すことができます:-

  • 単語の長さは常にわかっているので、長さ 1 のすべての単語を含むテーブルを作成し、長さ 2 の単語のテーブルをもう 1 つ作成します。
  • クエリを実行するときは、語長に基づいて適切なテーブルから選択します。そのテーブルのフル スキャンを実行する必要があります。

RDBMS で許可されている場合は、単一のテーブルとワード長によるパーティションの方が適しています。

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

クエリを実行すると、「E」と「Z」を含む 8 文字の単語があることがわかります。最初にデータ ディクショナリにクエリを実行して、8 文字の単語の中で最も珍しい文字を確認し、次にそのテーブルをスキャンします。データ ディクショナリにクエリを実行することで、テーブルwords_8Eまたはテーブルwords_8zのレコード数が最も少ないかどうかを判断します。

正規形とグッドプラクティスについて

これは、データをモデル化するときに私が通常推奨するようなものではありません。あなたの特定のケースでは、単語全体を単一の文字列に格納することは、実際には1st normal formではありません。これは、単語内の個々の要素に関心があるためです。ユースケースを考えると、単語は単一の単語ではなく文字のリストです。いつものように、どのようにモデル化するかは、何に関心があるかによって異なります。

クエリが最初の正規形ではないため、問題が発生しています。

この問題の完全に正規化されたモデルには、単語 (WordId PK) と WordLetter (WordId PK、Position PK、Letter) の 2 つのテーブルがあります。次に、複数の WHERE EXISTS 文字が適切な位置にあるすべての単語を照会します。

データベース理論によれば正しいですが、これがうまく機能するとは思いません。

于 2012-04-11T22:44:53.330 に答える
0

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

最初に必要なテーブルを設計しましょう。あなたのwordsテーブルには列があると思いますword_id, word, size：

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 ;

補助的な「数値」テーブルが必要です。

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テーブルにデータを入力するには:

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

この検索テーブルのサイズは、約 10 * 250K 行になります (ここで、10 は単語の平均サイズです)。

最後に、クエリ:

SELECT * FROM words WHERE word LIKE '_e__o'

次のように記述されます。

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
于 2012-04-11T22:58:54.767 に答える
0

全文検索エンジンApache Luceneの使用を試すことができます。このような質問に答えるために作られたので、もっと運がいいかもしれません.

lucene を使用したワイルドカード検索。

于 2012-04-11T22:18:08.390 に答える
0

メモリ内ルックアップ テーブル ソリューションを作成します。長さごとに並べ替えられたテーブルを作成できます。

次に、一致させるために、4 番目と 8 番目の文字を知っているとします。4 番目の文字だけをチェックする単語をループします。全部同じ長さなのですぐにできます。文字が一致する場合のみ、8 番目の文字をチェックします。

それは総当たりですが、高速になります。最悪の場合、8 文字の単語が 50,000 個あるとしましょう。それは50,000の比較です。ruby 実行時のパフォーマンスの問題を想定すると、それでも 1 秒未満であるはずです。

必要なメモリは 250k x 10 です。つまり、2.5 メガです。

于 2012-04-11T22:36:23.820 に答える