Why lucene doesn't require composite index, but relation database does?

Lucene stores index for each field separetly. So when we perform query "fld1:a AND fld2:b" we iterate over Termdocs for first term and second term. This can't be faster. In case of database two separete indexes for fld1 and fld2 will work slow and only one will be used. In that case DB requres composite key for fld1 and fld2.

My question is. Why Can't DB utilize Lucene index algorithm for executing Boolean queries if it as fast as DB index and dosn't requires different combinations of columns?

Some details of Lucene Boolean Query search: It utilize interface TermDoc. The main idea in using two methods boolean skipTo(int) and boolean next(). So it is doesn't depend on term order(popular or not popular term) because count of those method calls will be always as most infrequent term(due to skipTo method). So there are no need in hierarchical composite index, it will not bring any additional performance.

TermDocs t1开发者_C百科 = 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()
}
}

---

I think @Frank Farmer's comment gives you most of your answer: it's perfectly possible for an RDB to use multiple indexes even if they aren't "composite".

A more specific question has a harder answer: why don't RDBs use Lucene's multi-index-search paradigm?

Recall that Lucene uses an inverted index with a skip list; recall also that these are only efficient if the index is extremely sparse and the number of terms is very high.

In the type of column where you're likely to do a query like where a = b, the number of possible bs is probably pretty small, and hence the index will be relatively dense. So it makes more sense to use bitmaps (like PostgreSQL does) and gain the speedup of bit-level parallelism than to store it as a skip list and deal with pointer-chasing.

I should note that even Lucene uses bitmaps when combining filters with queries, so we might equivalently ask why Lucene doesn't use Lucene's search. My guess is that bitmaps are smaller and therefore more likely to fit in memory.

To the best of my knowledge, this is not a huge performance gain, so you probably can't make a very strong argument for either bitmaps or skip lists in the general case. But if I had to guess why the PostgreSQL devs went the bitmap route, I think it would be this.