Блог

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

1. префиксные запросы выполняются медленнее, чем запросы терминов
2. запросы с суффиксами (* ing) выполняются медленнее, чем запросы с префиксами (ing *)

Это кажется странным сочетанием свойств. Возможно, мне нужно расширить область моих структур данных, которые я рассматриваю, но если бы сегмент был структурирован как хэш-таблица, я мог бы легко увидеть, что 1 будет истинным (запрос с термином будет O (1), а запрос с префиксом потребует полного сканирования), однако 2 не будет истинным(как для префикса, так и для суффикса потребуется полное сканирование). Если бы сегмент был выложен как отсортированный массив, я мог бы легко увидеть, что 2 будет истинным (запрос префикса может быть выполнен с помощью двоичного поиска O (log n), а суффикс потребует полного сканирования), однако 1 больше не будет истинным (как запрос термина, так и запрос префикса будуттребуется двоичный поиск).

Моя единственная другая мысль заключается в том, что для объяснения этого поведения может существовать некоторая комбинация как хэша, так и сортировки (например, хэш для некоторого раздела и сортировка внутри этого раздела). Однако я понимаю, что разделы Elasticsearch разделяются по идентификатору документа, но инвертированный ключ индекса является термином. Таким образом, запрос для термина по-прежнему требует отправки запроса во все разделы.

Может ли кто-нибудь подсказать мне, как / почему такое поведение существует?

Примечание:

• https://www.youtube.com/watch?v=T5RmMNDR5XI можно предположить, что сегмент структурирован аналогично отсортированному массиву, а не хэш-таблице.
• Причина, по которой я считаю, что 1 верно, заключается в https://medium.com/@mourjo_sen/a-detailed-comparison-between-autocompletion-strategies-in-elasticsearch-66cb9e9c62c4 упоминает «Самая важная причина, по которой запросы, подобные префиксам, никогда не должны использоваться в производственных средах, заключается в том, что они чрезвычайно медленные. Причина этого в том, что токены в ES не имеют прямого префикса «
• Причина, по которой я считаю, что 2 верно, заключается в том, что https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-query-string-query.html упоминания «Разрешить подстановочный знак в начале слова (например, «* ing») особенно сложно, потому что необходимо проверить все термины в индексе на случай, если они совпадают

Я не очень хорошо знаком с конкретными деталями ES, поэтому они могут делать что-то другое, кроме простого Solr, но # 1 обычно не так.

Сопоставление префиксов будет дороже, чем поиск одного термина, но это не намного дороже. Это можно сравнить с выполнением поиска по диапазону (который вы можете выполнить, если хотите — field:[aa TO ab) можно сравнить с выполнением field:aa* (теоретически); эффективное извлечение всех токенов, которые находятся в пределах этого диапазона, а затем разрешение набора документов, соответствующего этим токенам.

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

Запрос foo* к индексируемому объекту со следующими условиями:

 bar, baz, foo, foobar, spam
          ^----------^
 

соберет список документов, прикрепленных к foo и foobar , объединит его, а затем извлекет документы.

Замедление не означает, что это катастрофично или никак не оптимизировано; просто это дороже, чем прямое сопоставление, когда набор документов уже определен. Однако у вас, вероятно, уже есть более одного термина в вашем запросе, поэтому тот же процесс (хотя и немного выше в иерархии) происходит и там.

Сопоставление с постфиксом (ваш # 2), т. Е. Сопоставление подстановочного знака в начале токена, обходится дорого, поскольку обычно необходимо учитывать все токены в индексе. В индексе термины отсортированы в алфавитно-цифровом порядке, поэтому, когда вы хотите просмотреть только конец строки, вы должны учитывать, что каждый токен может совпадать, независимо от того, где он находится в индексе — таким образом, вы получаете полное сканирование индекса. Однако, если вы часто сталкиваетесь с подобным вариантом использования, вы можете использовать обратный фильтр подстановочных знаков. Это работает путем изменения строки и наличия токенов, которые соответствуют терминам в обратном порядке, так что foo они индексируются как oof , а поиск по шаблону превращается в поиск oof* по шаблону.

Запрос *ar к индексируемому объекту со следующими условиями:

 bar, baz, foo, foobar, spam
?!   ?    ?    ?!      ?
 

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

Причина использования EdgeNGramFilter (ваш комментарий / # 3) заключается в том, что вы переносите как можно больше требуемой обработки на время индексации (выполняя работу, которую, как вы знаете, выполняет время запроса, даже если префиксные запросы не очень дороги, они все равно имеют стоимость), и дополнительно: запросы с подстановочными знаками не поддерживает большинство анализов. Так много людей в конечном итоге получают запросы с подстановочными знаками к набору токенов, которые были удалены или обработаны иным образом, а затем удивляются, когда их запросы с подстановочными знаками не генерируют совпадения. К запросам с подстановочными знаками можно применять только небольшое подмножество фильтров (например, фильтр нижнего регистра). Эти фильтры известны как «с учетом нескольких терминов», поскольку термины процесса могут в конечном итоге быть расширены до нескольких терминов, прежде чем произойдет сбор документов.

Другая причина заключается в том, что использование EdgeNGramFilter даст вам правильные оценки частоты для каждого префикса, что также даст вам эффективную оценку для терминов с префиксами.