Быстрый (er) метод для поиска по шаблону строк 250K +

Ответ 1

С PostgreSQL 9.1 и расширением pg_trgm вы можете создавать индексы, которые можно использовать для аналогичного условия, которое вы описываете.

Пример см. здесь: http://www.depesz.com/2011/02/19/waiting-for-9-1-faster-likeilike/

Я проверил его на таблице с 300 тыс. строк, используя LIKE '____1', и он использует такой индекс. Для подсчета количества строк в этой таблице (на старом ноутбуке) потребовалось около 120 мс. Довольно интересно выражение LIKE 'd___1' не быстрее, это примерно такая же скорость.

Это также зависит от количества символов в поисковом терминах, времени ожидания, тем медленнее, насколько я могу судить.

Вам нужно будет проверить свои данные, если производительность будет приемлемой.

Ответ 2

Я предполагаю, что время, первоначально принятое для вставки слов и настройки индексации, несущественно. Кроме того, вы не будете делать обновления в списке слов очень часто, поэтому в основном статические данные.

Вы можете попробовать такой подход: -

• Поскольку вы всегда знаете длину слова, создайте таблицу, содержащую все слова длины 1, другую таблицу слов длиной 2 и т.д.
• Когда вы выполняете запрос, выберите из соответствующей таблицы на основе длины слова. Он все равно должен будет выполнить полное сканирование этой таблицы.

Если RDBMS позволяет это, вам будет лучше с одной таблицей и разделом по длине слова.

Если это еще не достаточно быстро, вы можете разделить его по длине и известной букве. Например, у вас может быть таблица, в которой перечислены все 8 буквенных слов, содержащих "Z".

Когда вы запрашиваете, вы знаете, что у вас есть 8-буквенное слово, содержащее "E" и "Z". Сначала запросите словарь данных, чтобы увидеть, какая буква является редкими в 8 буквенных словах, а затем сканировать эту таблицу. По запросу словарь данных, я имею в виду выяснить, имеет ли таблица words_8E или таблица words_8z наименьшее количество записей.

Относительно нормальных форм и хорошей практики

Это не то, что я обычно рекомендую при моделировании данных. В вашем конкретном случае хранение всего слова в столбце с одним символом фактически не находится в 1-я нормальная форма. Это потому, что вы заботитесь о отдельных элементах слова. С учетом вашего варианта использования слово представляет собой список букв, чем одно слово. Как всегда, как модели зависит от того, что вам нужно.

Ваши вопросы дают вам проблемы, потому что они не в первой нормальной форме.

Полностью нормализованная модель для этой проблемы будет иметь две таблицы: word (WordId PK) и WordLetter (WordId PK, Position PK, Letter). Затем вы запрашивали бы все слова с несколькими ГДЕ СУЩЕСТВУЕТ букву в соответствующей позиции.

Правильно в соответствии с теорией базы данных, я не думаю, что это будет хорошо.

Ответ 3

Все сводится к индексированию.

Вы можете создать таблицу типа:

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" во 2-й позиции:

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" во 2-й позиции и "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
)

Или вы можете запускать два простых запроса и самостоятельно объединять результаты.

Конечно, просто кеширование и повторение через список в памяти, скорее всего, быстрее, чем любой из них. Но не достаточно быстро, чтобы каждый раз загружать список 250K из базы данных.

Ответ 4

Вы можете полностью проиндексировать этот запрос, не требуя сканирования больше, чем размер оптимального набора результатов.

Создайте таблицу поиска следующим образом:

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 ​​ script, чтобы создать эту таблицу поиска, где шаблон - всевозможный шаблон для каждого слова в словаре. Другими словами, шаблоны для мыши будут:

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____
_____

Ответ 5

Быстрый способ получить его в 10 раз или около того - создать столбец для длины строки, поместить на него индекс и использовать его в предложении where.

Ответ 6

Вы можете использовать Apache Lucene, полнотекстовую поисковую систему. Это было сделано для ответа на такие запросы, поэтому вам может быть повезло больше.

Подстановочный поиск с lucene.

Ответ 7

Создайте решение для поиска в таблице памяти: у вас может быть отсортированная таблица для каждой длины.

Затем, чтобы соответствовать, скажем, вы знаете 4-ю и 8-ю буквы, пропустите слова, проверяющие только каждую четвертую букву. Они имеют одинаковые длины, так что они будут быстрыми. Только если письмо соответствует 8-й букве.

это грубая сила, но будет быстро. Пусть говорят, что в худшем случае у вас 50 000 буквенных слов. Это 50 000 сравнений. при условии, что первичным задачам рубинового времени выполнения все равно должно быть < 1 сек.

Требуемая память должна быть 250k x 10. Так что 2.5 Meg.

Ответ 8

Это больше упражнение, чем реальное решение. Идея состоит в том, чтобы разделить слова на символы.

Сначала спроектируем нужную таблицу. Я предполагаю, что ваша таблица 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 * 250 тыс. строк (где 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