Как Lucene так быстро рассчитывает пересечение документов?

Question

Что такое внутреннее хранилище и поиск, которые позволяют это? Как в мельчайших песках?

Например, у меня есть миллион документов, совпадающих с термином, и миллион других, совпадающих со вторым термином запроса AND. Как lucene делает пересечение так быстро, давая мне top k?

Хранит ли документ документ в порядке увеличения ID документа для каждого термина? И затем, когда необходимо пересечь документы двух терминов, он ищет первые общие k документов в обоих наборах, перебирая их оба постепенно, за один проход.

Или он использует простой неупорядоченный хэш-набор из массива документов для поиска общих документов?

Или оба таких (или, возможно, более) типа политик пересечения используются в зависимости от количества документов, запрашиваемых пользователем, сопоставляемых отдельными терминами и т. Д. Среди прочих факторов?

Будут оценены любые статьи, которые могут указать на мелочность слияния массивов документов.

Edit: Спасибо за информацию, ребята. Это имеет смысл сейчас. Пропуск списков делает магию. Я углублюсь в это, чтобы получить ясное понимание.

Answer 1

1. Указатели содержат отсортированные документы. Когда вы выполняете запрос с помощью оператора и (term1 AND term2), он использует два итератора, поэтому, когда вы знаете, что первый term1 начинается с docN, вы можете пропустить весь документ для term2 до docN. Так что есть не только итератор со следующим методом, но и очень эффективный метод skipTo. Это реализовано с помощью индекса списка пропусков Таким образом, используя метод next и skipTo, мы очень быстро выполняем итерации по большим кускам, а поскольку данные редки (например, они не будут работать для обычной базы данных), они очень эффективны.
2. Другое замечание, что lucene содержит только N лучше, так что это намного быстрее, чем сортировать все документы с результатами. Если вы запрашиваете 10 лучших, это в два раза быстрее, чем если вы запрашиваете 20 лучших документов

Answer 2

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

Answer 3

Lucene будет пересекать отсортированные идентификаторы документов или использовать окна наборов битов, в зависимости от ситуации. Смотрите комментарии вверху BooleanScorer .