Как оптимизировать "текстовый поиск" для инвертированного индекса и реляционной базы данных?

Question

Обновление 2015-10-15

Еще в 2012 году я создавал персональное онлайн-приложение и на самом деле хотел заново изобрести колесо, потому что по натуре мне любопытно, для целей обучения и для улучшения моих алгоритмов и архитектурных навыков. Я мог бы использовать Apache Lucene и другие, однако, как я уже упоминал, я решил создать свой собственный мини-поисковик.

Вопрос: То есть, действительно, нет способа улучшить эту архитектуру, кроме как с помощью доступных сервисов, таких как asticsearch, lucene и других?

---

Оригинальный вопрос

Я занимаюсь разработкой веб-приложения, в котором пользователи ищут конкретные заголовки (например, книга x, книга y и т. Д.), Данные которых находятся в реляционной базе данных (MySQL).

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

Я разработал свой собственный мини-поисковик со следующей архитектурой:

Вот как это работает:

• а) Пользователь ищет имя записи
• б) Система проверяет, с какого символа начинается запрос, проверяет, есть ли запрос: получить запись. Если нет, добавьте его и получите все соответствующие записи из базы данных двумя способами:
  • Любой запрос уже существует в таблице "Запросы" (которая является своего рода таблицей истории), таким образом, получить запись на основе идентификаторов (Быстрая производительность)
    
  • Или, в противном случае, используйте оператор Mysql LIKE %% для получения записей / идентификаторов (также сохраните используемый пользователем запрос в таблице истории запросов вместе с идентификаторами, с которыми он сопоставлен).
    -> Затем он добавляет записи и их идентификаторы в кэш и только идентификаторы в инвертированную карту индекса.
• в) результаты возвращаются в пользовательский интерфейс

Система работает нормально, однако у меня есть две основные проблемы, которые я не смог найти хорошего решения (пытался в течение последнего месяца):

Первая проблема:
если вы отметили пункт (b), случай, когда "история" запроса не найдена, и он должен использовать оператор Like %%: этот процесс отнимает много времени, когда запрос сопоставляет многочисленные записи в базе данных (вместо одной или двух):

• Получение записей из Mysql займет некоторое время (именно поэтому я использовал INDEXES для определенных столбцов)
• Тогда время, чтобы сохранить историю запросов
• Затем время, чтобы добавить записи / идентификаторы в кеш и инвертированные индексные карты

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

• новая запись "woodX" добавляется в таблицу "records"
• затем я запускаю оператор Like %%, чтобы увидеть, какой уже существующий запрос в таблице "запросов" соответствует этой записи (например, "дерево"), затем добавляю этот запрос с новым идентификатором записи в качестве новой строки: [ wood, new Я бы].
• Затем в памяти обновите значение "дерева" ключа карты с инвертированным индексом (то есть список), добавив новый идентификатор записи в этот список.

-> Таким образом, теперь, если удаленный пользователь ищет "дрова", они получат из памяти: дрова и дрова.

Проблема здесь - также потребление времени. Сопоставление всех историй запросов (в табличных запросах) с вновь добавленным словом занимает много времени (чем больше совпадений запросов, тем больше времени). Тогда обновление в памяти также занимает много времени.

Что я думаю сделать, чтобы решить эту проблему времени, так это сначала вернуть желаемые результаты пользователю, а затем позволить приложению POST выполнить ajax- вызов с необходимыми данными для выполнения всех этих задач UPDATE. Но я не уверен, что это плохая практика или непрофессиональный способ делать вещи?
Таким образом, в течение последнего месяца (немного больше) я пытался придумать лучшую оптимизацию / модификацию / обновление для этой архитектуры, но я не эксперт в области поиска документов (фактически это моя первая мини-поисковая система, когда-либо созданная).

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

PS:

• Это приложение j2ee, использующее сервлеты.
• Я использую MySQL innodb (поэтому я не могу использовать опцию полнотекстового поиска)

Answer 1

Я настоятельно рекомендую Sphinx Search Server, который лучше всего оптимизирован для полнотекстового поиска. Посетите http://sphinxsearch.com/.

Он предназначен для работы с MySQL, поэтому он является дополнением к вашей текущей рабочей области.

Answer 2

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

Вот возможное решение:

1. Перепроектируйте вашу базу данных, чтобы она содержала только достоверные данные, но не производные данные. Таким образом, все записи кэша должны исчезнуть из MySQL.

2. Сохраняйте данные только на время запроса в памяти вашего приложения. Это значительно упрощает дизайн вашего приложения (подумайте о гоночных условиях) и позволяет масштабировать его до разумного количества клиентов.

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

Вы можете взглянуть на Redis или Memcached для слоя кэширования. Я думаю, что стратегия LRU должна соответствовать здесь. В зависимости от сложности ваших запросов также может иметь смысл отдельный механизм индексированного поиска, такой как Lucene.

Answer 3

Я не претендую на то, чтобы иметь решение, но вот мои идеи. Во-первых, хотя вы мне нравитесь для длительных запросов, LIKE%%: я бы выполнил запрос, ограниченный несколькими ответами в MySQL, например дюжину, возвратил бы его пользователю и дождался, чтобы увидеть, хочет ли пользователь больше подходящих записей, или запустить в фоновом режиме полный запрос, в зависимости от ваших потребностей в индексации для будущих поисков.

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

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

• Каждая вставка, удаление, обновление в базе данных намного медленнее
• Выбор данных для поисковой системы должен быть ожидаемым: если вы решите сохранить двухбуквенные слова, которые вы никогда не сохраняли, будет слишком поздно для уже записанных данных, если только вы не запустите полную повторную обработку данных.
• Вы должны позаботиться об УДАЛИТЬ, а также ОБНОВИТЬ и ВСТАВИТЬ

Но я думаю, что есть несколько больших преимуществ:

• Время вычислений, вероятно, совпадает с "решением для памяти" (в конце концов), но оно делится на каждую базу данных "Создать / Обновить / Удалить", а не на время запроса.
• Поиск целого слова или слов "начиная с" происходит мгновенно: при индексации поиск в таблице "Слова" дихотомичен. И запрос таблицы "WordLinks" очень быстрый либо с индексом.
• Поиск нескольких слов одновременно может быть простым: собрать группу "WordLinks" для каждого найденного Word и выполнить пересечение для них, чтобы сохранить только "Идентификаторы базы данных", общие для всех этих групп. Например, со словами "дерево" и "лист" первый может дать записи таблицы {1, 4, 6}, а второй - {1, 3, 6, 9}. Таким образом, с пересечением просто сохранить только общие части: {1, 6}.
• "Like %%" в таблице с одним столбцом, вероятно, быстрее, чем "Like %%" в разных полях разных таблиц. И каждый механизм базы данных обрабатывает некоторый кеш: таблицы "Words" может быть недостаточно для хранения в памяти.
• Я думаю, что если данные становятся огромными, существует небольшой риск проблем с производительностью и памятью.
• Поскольку каждый поиск быстрый, вы можете даже искать синонимы. Например, поиск "сеть", если пользователь не нашел ничего с "Ethernet".
• Вы можете применять правила, например, разделять слова падежа верблюда, чтобы генерировать, например, 3 слова "дерево", "X", "woodX" из "woodX". Каждое "слово" очень легкое для хранения и поиска, поэтому вы можете делать много вещей.

Я думаю, что решение, в котором вы нуждаетесь, может быть сочетанием методов: например, вы можете сохранять легкие UPDATE, INSERT, DELETE и запускать "Words" и "WordsLinks", питающиеся от TRIGGER.

Просто для анекдота, я увидел программное обеспечение, разработанное моей компанией, в котором было решено хранить "все" (!) В памяти. Это побуждает нас рекомендовать нашим клиентам покупать серверы с 64 ГБ оперативной памяти. Немного дороже. Это объясняет, почему я очень осторожен, когда вижу решения, которые могут в конечном итоге привести к заполнению памяти.

Answer 4

Я уверен, что это может быть реализовано в MySQL, но было бы намного меньше усилий, чтобы просто использовать существующую базу данных, ориентированную на поиск, такую ​​как Elasticsearch. Он использует библиотеку Lucene для реализации инвертированного индекса, имеет обширную документацию, поддерживает горизонтальное масштабирование, довольно простой язык запросов и так далее. Я думаю, что было достаточно много работы, чтобы продвинуться так далеко, и еще больше будет работать с кешами, условиями гонки, ошибками, проблемами с производительностью и т. Д., Чтобы сделать решение "серийным".