Как быстро найти очень большой список строк / записей в базе данных

32

У меня следующая проблема: у меня есть база данных, содержащая более 2 миллионов записей. Каждая запись имеет строковое поле X, и я хочу отобразить список записей, для которых поле X содержит определенную строку. Каждая запись имеет размер около 500 байт.

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

Интересно, есть ли эффективный способ сделать это, используя соответствующие структуры индекса и / или кэширование. Как объяснено выше, я хочу отображать только первые N элементов, которые соответствуют запросу. Следовательно, для достаточно малого N это не должно быть большой проблемой при загрузке соответствующих элементов из базы данных. Кроме того, кэширование элементов в основной памяти может ускорить поиск.

Я думаю, что основная проблема заключается в том, как быстро найти подходящие элементы, учитывая строку шаблона. Могу ли я полагаться на некоторые средства СУБД или мне нужно самостоятельно составить некоторый индекс в памяти? Любые идеи?

РЕДАКТИРОВАТЬ

Я провел первый эксперимент. Я разделил записи на разные текстовые файлы (не более 200 записей на файл) и поместил файлы в разные каталоги (я использовал содержимое одного поля данных для определения дерева каталогов). Я получаю около 50000 файлов в 40000 каталогах. Затем я запустил Lucene для индексации файлов. Поиск строки с помощью демонстрационной программы Lucene довольно быстрый. Разделение и индексация заняли несколько минут: для меня это полностью приемлемо, потому что это статический набор данных, который я хочу запросить.

Следующим шагом является интеграция Lucene в основную программу и использование обращений, возвращаемых Lucene, для загрузки соответствующих записей в основную память.

Джорджио
источник
2
2 миллиона записей * 500 байтов = 1 ГБ данных. Это большое количество данных для поиска, в зависимости от того, как вы поступите - будет ли каждое значение X уникальным или у вас будет много записей с одинаковым значением X?
1
Это также было бы много данных, чтобы попытаться сохранить в памяти в качестве кэша для быстрого поиска. Это будет эквивалентно более 1 ГБ на пользовательский сеанс.
maple_shaft
Мой предыдущий комментарий предполагает веб-приложение. Это веб-приложение?
maple_shaft
Это настольное приложение. Значения в записях не обязательно являются уникальными. Кроме того, я ищу подстроку не для точного соответствия.
Джорджио
@maple_shaft: я бы кэшировал только те записи, к которым я недавно обращался. Если я изменяю строку запроса и запись все еще совпадает, она все еще находится в кэше.
Джорджио

Ответы:

20

Вместо того, чтобы помещать свои данные в БД, вы можете хранить их как набор документов (текстовые файлы) отдельно и хранить ссылку (путь / URL-адрес и т. Д.) В БД.

Это важно, потому что SQL-запрос по своей структуре будет очень медленным как при поиске подстроки, так и при поиске.

Теперь ваша проблема сформулирована как необходимость поиска текстовых файлов, которые содержат набор строк. Здесь есть две возможности.

  1. Соответствие подстроки Если ваши текстовые объекты представляют собой одну строку или слово (без пробелов), и вам необходимо найти в ней произвольную подстроку. В таких случаях вам нужно проанализировать каждый файл, чтобы найти наилучшие возможные файлы, которые соответствуют. Каждый использует алгоритмы как алгоритм Бойера Мура. Смотрите это и это для деталей. Это также эквивалентно grep - потому что grep использует подобные вещи внутри. Но вы все равно можете заработать как минимум 100+ grep (в худшем случае 2 миллиона), прежде чем вернуться.

  2. Индексированный поиск. Здесь вы предполагаете, что текст содержит набор слов, а поиск ограничен фиксированной длиной слова. В этом случае документ индексируется по всем возможным вхождениям слов. Это часто называют «полнотекстовым поиском». Существует ряд алгоритмов для этого и количество проектов с открытым исходным кодом, которые можно использовать напрямую. Многие из них также поддерживают поиск по шаблону, приблизительный поиск и т. Д., Как показано ниже:
    a. Apache Lucene: http://lucene.apache.org/java/docs/index.html
    b. OpenFTS: http://openfts.sourceforge.net/
    c. Сфинкс http://sphinxsearch.com/

Скорее всего, если вам нужны «фиксированные слова» в качестве запросов, второй подход будет очень быстрым и эффективным.

Дипан Мехта
источник
2
Это интересная концепция, но кажется маловероятным, что разработчик может легко осуществлять поиск по 1 ГБ текстовых данных быстрее и эффективнее, чем механизм базы данных. Гораздо умнее, чем вы, и я работали над оптимизаторами запросов, чтобы сделать именно это, и немного наивно думать, что вы можете каким-то образом сделать это более эффективно.
maple_shaft
4
@maple_shaft Приведенные мною примеры не являются ядрами СУБД. Они больше похожи на «поисковые системы», если вы хотите это назвать. Существует огромная концептуальная разница между выбором списка из индекса (или хеш-таблицы) и поиском в 1 ГБ данных снова и снова при каждом запуске запроса. Так что я предлагаю не мелкий твик.
Дипан Мехта
Это кажется интересной идеей, но мне интересно, как это будет работать. У меня было бы более 2 000 000 файлов, каждый размером примерно в пол килобайта. Или вы предлагаете иметь более одной записи на файл? Какая разница в базе данных?
Джорджио
Я не уверен, что это обязательно будет работать лучше, чем, скажем, полнотекстовый индекс SQL.
Кирк Бродхерст
@ Джорджио - да, именно так будут работать полнотекстовые поисковые системы. Ключевое отличие здесь - это предварительно проиндексированные страницы по сравнению с поиском в памяти (опять же, каждый раз, когда приходит запрос).
Дипан Мехта
21

Технология, которую вы ищете - это полнотекстовая индексация. Большинство СУБД имеют какие-то встроенные возможности, которые могут работать здесь, или вы можете использовать что-то вроде Lucene, если вы хотите стать более изящным и / или просто запустить его в памяти.

Уайетт Барнетт
источник
1
По моему мнению, полнотекстовые опции в любой СУБД - это обходной путь, заставляющий ее делать то, для чего она не предназначена: «искать в некоторой куче неструктурированных несвязанных данных». Если вы создаете поисковик, вы просто не используете RDBMS. Это может работать для небольших наборов данных, но не для любого масштабирования. Поиск в груде неструктурированных данных - это не гвоздь, поэтому не используйте молоток. Используйте правильный инструмент для работы.
Питер Б
8

Вы рассматривали три ? По сути, вы строите дерево, используя общие префиксы, поэтому все слова, начинающиеся с одинаковых букв, являются потомками одного и того же узла. Если вы собираетесь поддерживать сопоставление для любой подстроки, то вам нужно будет сгенерировать какой-нибудь перестановочный индекс и построить из него свое дерево. Впрочем, это может привести к тому, что ваши требования к хранению выйдут из строя.

TMN
источник
1
ДА! Я думал о древовидной структуре и вспомнил, что было что-то похожее, что могло бы мне подойти, но я не помнил три, потому что я никогда не использовал их. Что касается требований к памяти: помните, что мне нужно получить только первые N записей (например, N = 100), потому что нет смысла заполнять таблицу 20000 посещений. Таким образом, каждый узел дерева будет указывать не более чем на N записей. Кроме того, я забыл упомянуть, что мне нужен быстрый доступ, но мне не нужно быстрое обновление, потому что данные загружаются только один раз. Идея три на перестановочный индекс может действительно работать!
Джорджио
1
Хороший ответ, но, как вы заметили, три отлично подходит для сопоставления начала ваших слов, но быстро станет сложным и очень большим, если сопоставить любую подстроку ...
Кирк Бродхерст
В качестве первого эксперимента я попытался построить набор всех подстрок, появляющихся в строках, которые мне нужно найти, которые, если я правильно понимаю, соответствуют путям дерева. Я получил исключение нехватки памяти (с 256M кучи для JVM) на подстроки длины 6. Поэтому я боюсь, что это решение невозможно, если я не делаю что-то не так.
Джорджио
5

Я хотел бы добавить к ответу Уайета Барнетта, что будет работать решение СУБД с полнотекстовой индексацией в соответствующем столбце, но если вы хотите использовать локальный кэш ранее выбранных записей, вам необходимо составить план использования этих кэшированных записей. в ваших интересах.

Одним из вариантов является сбор уникальных идентификаторов этих записей, которые вы, очевидно, не хотите извлекать из запроса, и включение их, возможно, в a NOT INили a NOT EXISTS.

Тем не менее, предостережение: использование NOT INили, NOT EXISTSкак правило, не дешево и МОЖЕТ отрицательно повлиять на производительность вашего запроса или план запроса в зависимости от того, какой механизм базы данных вы используете. Запустите план объяснения для вашего окончательного запроса, чтобы убедиться, что все ваши индексы в затронутых столбцах используются.

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

maple_shaft
источник
maple_shaft и @Wyatt Barnett: Большое спасибо за предложения. Мне придется немного почитать и попробовать разные решения. Не все базы данных поддерживают полную индексацию, MySQL (которую я сейчас использую) поддерживает ( dev.mysql.com/doc/refman/5.5/en/fulltext-search.html ). Я постараюсь сделать несколько тестов, а затем сообщить здесь.
Джорджио
2

На всякий случай, если вы пропустили это. Если вы используете Lucene для своей базы данных вместо текстового поиска, поддерживаемого в БД, вам нужно быть предельно осторожным при внесении изменений в вашу БД. Как вы можете быть уверены, что можете иметь атомарность, когда нужно вносить изменения как в БД, так и во внешние ресурсы (Lucene)? Да, это можно сделать, но работы будет много.

Короче говоря, вы теряете поддержку транзакций БД, если вы добавляете Lucene в свою схему данных.

InformedA
источник
1
Как указывалось, проблема, похоже, не подходит для RDMS.
Питер Б
1

Вы рассматривали сфинкса? http://sphinxsearch.com, если вы можете использовать сторонний инструмент, это было бы идеально для того, чего вы пытаетесь достичь, гораздо эффективнее при полнотекстовом поиске, чем любая СУБД, которую я лично использовал.

Twigg
источник
3
а голосование за это?
веточка
1

Несколько странно, что ни один из ответов не представил термин «инвертированный индекс» , технология, лежащая в основе всех решений, аналогичных Apache Lucene и другим.

Инвертированный индекс является отображением слов в документы («инвертированный индекс на уровне записи») или даже точными местоположениями слов в документе («инвертированный индекс на уровне слова»).

Логические операции И и ИЛИ тривиальны для реализации. Если у вас есть точные местоположения слов, можно искать соседние слова, что делает возможным поиск по фразе.

Итак, подумайте об индексе, содержащем (слово, файл, местоположение) кортежи. Когда у вас есть, например, ("inverted", "foo.txt", 123), вы просто проверяете, является ли ("index", "foo.txt", 124) частью индекса, чтобы найти полную фразу "инвертированный индекс" ,

Хотя я не рекомендую вам заново реализовывать механизм полнотекстового поиска, полезно знать, как работают такие технологии, как Apache Lucene.

Поэтому я рекомендую узнать, как работают инвертированные индексы, и выбрать технологию, использующую их, такую ​​как Apache Lucene. Тогда у вас, по крайней мере, есть четкое понимание того, что можно сделать, а что нельзя.

juhist
источник