Почему префиксные запросы Lucene / Elasticsearch медленнее, чем термические запросы?

Я недавно читал о 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) особенно сложен, потому что необходимо проверить все термины в указателе на случай, если они совпадают


search solr lucene inverted-index
person John Magnus    schedule 10.12.2020    source источник
comment
Чтобы добавить к моему примечанию, почему я считаю, что 1 истинно. Это должно быть так, иначе зачем людям возиться с EdgeNGrams.   -  person John Magnus    schedule 10.12.2020

Ответы (1)


arrow_upward
2
arrow_downward

Я не так хорошо знаком с конкретными деталями 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) заключается в том, что вы перемещаете как можно большую часть необходимой обработки во время индексации (выполняя работу, которую вы знаете, время запроса, даже если префиксные запросы не очень дороги, они по-прежнему имеют стоимость), и, кроме того, запросы с подстановочными знаками не поддерживают большую часть анализа. Так много людей в конечном итоге получают запросы с подстановочными знаками к набору токенов, которые были заблокированы или обработаны иным образом, а затем удивляются, когда их запросы с подстановочными знаками не генерируют совпадения. К запросам с подстановочными знаками можно применить только небольшой набор фильтров (например, LowercaseFilter). Эти фильтры известны как с учетом нескольких терминов, поскольку условия процесса могут в конечном итоге расширяются до нескольких терминов, прежде чем произойдет сбор документов.

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

person MatsLindh    schedule 10.12.2020
comment
В этом огромный смысл, спасибо! Статья, на которую я ссылался (medium.com/ @ mourjo_sen /) упоминается ... запросы, подобные префиксу, никогда не должны использоваться в производственных средах, поскольку они очень медленные. Причина этого в том, что токены в ES не имеют прямого префикса. Таким образом, Elasticsearch должен проверять каждый токен во время выполнения, чтобы узнать, начинается ли он с требуемого текста. судя по тому, что вы сказали, это неправда. Вы будете анализировать только все токены в пределах диапазона. это правильно? - person John Magnus; 10.12.2020
comment
Вы не анализируете токены; токены являются результатом токенизатора и затем обрабатываются путем анализа перед сохранением. Входной текст анализируется и фильтруется, а полученные токены сохраняются в индексе Lucene. Я недостаточно знаком с деталями Elasticsearch, чтобы сказать, на что ссылается статья, но из того, что в статье говорится о match_prefix_queries, это особенность, отличная от префиксных запросов с подстановочными знаками (которые, как вы можете видеть, расширяются до максимума 25 значений и, выполняющих анализ, ни то, ни другое не подходит для запроса префикса с подстановочными знаками). - person MatsLindh; 11.12.2020