Почему lucene не требует составного индекса, а база данных отношений требует? - PullRequest
Новая
       6

Почему lucene не требует составного индекса, а база данных отношений требует?

3 голосов
/ 21 июня 2011

Lucene хранит индекс для каждого поля отдельно. Поэтому, когда мы выполняем запрос «fld1: a AND fld2: b», мы перебираем Termdocs для первого и второго члена. Это не может быть быстрее. В случае базы данных два отдельных индекса для fld1 и fld2 будут работать медленно, и будет использоваться только один. В этом случае БД требует составного ключа для fld1 и fld2.

Мой вопрос Почему DB не может использовать алгоритм индекса Lucene для выполнения логических запросов, если он работает так же быстро, как индекс DB и не требует различных комбинаций столбцов?

Некоторые подробности поиска Lucene Boolean Query: Он использует интерфейс TermDoc . Основная идея в использовании двух методов boolean skipTo(int) и boolean next(). Таким образом, это не зависит от порядка терминов (популярный или не популярный термин), потому что количество вызовов этих методов всегда будет самым редким термином (из-за метода skipTo). Таким образом, нет необходимости в составном иерархическом индексе, он не принесет никакой дополнительной производительности. 

TermDocs t1 = searcher.docs(fld1:a);
TermDocs t2 = searcher.docs(fld2:b); 
int doc = -1;
t1.next(); t2.next();
while(t1.doc()!=-1 && t2.doc()!=-1) {
if(t1.doc()<t2.doc()) {
  if(!t1.skipTo(t2.doc)) return;
}
if(t2.doc()<t1.doc()) {
 if(!t2.skipTo(t1.doc)) return;
}
if(t1.doc()==t2.doc()) {
println("found doc:"+t1.doc());
t1.next()
}
}

1 Ответ

6 голосов
/ 24 июня 2011

Я думаю, что комментарий @Frank Farmer дает вам большую часть вашего ответа: для RDB вполне возможно использовать несколько индексов, даже если они не являются «составными».

Более конкретный вопрос имеет более сложный ответ: почему RDB не используют парадигму многоиндексного поиска Люсена?

Напомним, что Lucene использует инвертированный индекс со списком пропусков; Напомним также, что они эффективны только в том случае, если индекс чрезвычайно редок, а число терминов очень велико.

В типе столбца, в котором вы, вероятно, сделаете запрос, например where a = b, число возможных b s, вероятно, довольно мало, и, следовательно, индекс будет относительно плотным. Поэтому имеет больше смысла использовать растровые изображения (как это делает PostgreSQL) и получить ускорение параллелизма на уровне битов, чем хранить его в виде списка пропусков и иметь дело с погоней за указателями.

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

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

...