Стратегия поиска для базы данных N-грамм

Question

У меня большая база данных (~ 2 ТБ в необработанном несжатом тексте) N-грамм .Пример строки из 4 грамма выглядит следующим образом:

cat in the cradle 2
cat in the hat 187
cat in the window 32

т.е. текст из 4 строк с одним (возможно большим) целым числом (w1,w2,w3,w4,c).Мне удалось поместить данные в базу данных с индексацией на [w1,w2,w3].Поиск, где первые слова соответствуют заданному запросу, а последнее является диким:

SELECT * FROM db WHERE (w1="cat" AND w2="in" AND w3="the")

, выполняются довольно быстро.Меня интересует как этот запрос, так и тот, в котором первое слово является диким:

SELECT * FROM db WHERE (w2="in" AND w3="the" AND w4="hat")

Независимо от того, как я, кажется, создаю индекс или базу данных, запрос медленный или размер базы данных увеличивается до чего-то экстремального.Кроме того, создание индекса занимает несколько дней на моем компьютере, поэтому экспериментирование идет медленно.Я ищу предложения о том, как управлять таким запросом.Я не думаю, что у меня достаточно места на жестком диске для построения индекса для [w1,w2,w3] и [w2,w3,w4], поэтому любой ответ должен пытаться вписаться в эти ограничения.

Answer 1

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

CREATE TABLE word
  ( id INT PRIMARY KEY
  , text VARCHAR(32) NOT NULL UNIQUE
  )

Сохраняется только одна копия символов каждого уникального слова с потенциальной экономией дискового пространства (только «потенциал» зависит от средней длины слова). Что еще более важно, теперь был бы только один строковый индекс, который можно было бы использовать для всех слов, независимо от их положения в N-грамме. N-граммы будут ссылаться на слова по их идентификаторам первичного ключа, а не по тексту:

CREATE TABLE ngram
   ( id INT PRIMARY KEY
   , w1Id INT FOREIGN KEY REFERENCES word(id)
   , w2Id INT FOREIGN KEY REFERENCES word(id)
   , w3Id INT FOREIGN KEY REFERENCES word(id)
   , w4Id INT FOREIGN KEY REFERENCES word(id)
   , n INT NOT NULL
   )

Все индексы внешнего ключа будут основаны на целых числах, а не на строках.

Запросы можно выразить примерно так:

SELECT w1.text, w2.text, w3.text, w4.text, ng.n
FROM ngram AS ng
INNER JOIN word AS w1 ON w1.id = ng.w1Id
INNER JOIN word AS w2 ON w2.id = ng.w2Id AND w2.text = 'in'
INNER JOIN word AS w3 ON w3.id = ng.w3Id AND w2.text = 'the'
INNER JOIN word AS w4 ON w4.id = ng.w4Id AND w2.text = 'hat'

Answer 2

Из руководства MySQL:

Если таблица имеет индекс из нескольких столбцов, любой крайний левый префикс индекса может использоваться оптимизатором для поиска строк.Например, если у вас есть индекс из трех столбцов (col1, col2, col3), у вас есть индексированные возможности поиска для (col1), (col1, col2) и (col1, col2, col3).

MySQL не может использовать индекс, если столбцы не образуют крайний левый префикс индекса.Предположим, что у вас есть операторы SELECT, показанные здесь:

Так что вы можете попытаться создать индекс со всеми четырьмя столбцами (w1, w2, w3, w4), а затем изменить свой второй запрос примерно так::

SELECT * FROM db WHERE (w1 IS NOT NULL AND w2="in" AND w3="the" AND w4="hat")

Этот индекс должен использовать индекс, но, конечно, он работает, только если у вас нет n-граммов с w1, установленным в NULL.(обратите внимание, что пустая строка, такая как '', не является нулевой)

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

Answer 3

Если вы не можете предсказать шаблон доступа или если вам необходимо учесть несколько произвольных шаблонов доступа, вероятно, лучшим выбором будут индексы с одним столбцом.Тестирование покажет;попробуйте протестировать подмножество данных на компьютере разработчика.

Если вы строите индекс по комбинации из четырех столбцов {w1, w2, w3, w4}, то любой запрос, в котором отсутствует столбец w1 изПредложение WHERE вероятно не будет использовать индекс.Значения «кот в шляпе», «человек в шляпе» и «где в шляпе» будут широко разделены в сводном индексе.

Ваши дБмс, независимо от того, какой из них даст вамкакой-то способ увидеть, что делает оптимизатор запросов.

• PostgreSQL EXPLAIN ANALYZE
• MySQL EXPLAIN
• Oracle EXPLAIN PLAN

Answer 4

Создать составной индекс для (w2, w3).Используйте запросы с предложением WHERE, которое сравнивает w2 и w3 в порядке индекса, а затем используйте другие неиндексированные сравнения.

SELECT * FROM db WHERE (w2="in" AND w3="the" AND w1="cat") 
SELECT * FROM db WHERE (w2="in" AND w3="the" AND w4="hat")