lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Paul Elschot <paul.elsc...@xs4all.nl>
Subject Re: constant scoring queries
Date Thu, 19 May 2005 07:39:52 GMT
On Wednesday 18 May 2005 23:06, Yonik Seeley wrote:
> > > > contains(docid) and exists(docid) cannot be efficiently implemented
> > > > on a VInt based compact filter, so I'd prefer to leave these out.
> > >
> > > exists() on a BitSet is much faster than next() though...
> > 
> > Yes, but the point is to iterate to the next document based in information
> > from RAM and to be able to skipTo() on the index instead of reading it
> > sequentially.
> 
> Well, yes, that's one point to filters (and probably the main use). 
> Another that we are using is to enable fast intersection of two
> filters you already have in memory.
> 
> 
> > > I use a power-of-two hash table with a load factor of .75.  So putting
> > > 500 docs in my hashset would take up 1024 slots at 4 bytes per slot
> > > (4k).
> > 
> > So about 8 bytes per doc. A SortedVIntList normally has 1 byte per doc,
> > and never more than 4 bytes per doc (as long as doc numbers are int).
> 
> It depends on your platform and what tradeoffs you want too... our
> production boxes all have 16G RAM.
> 
> > > Hashes also have big speed advantage over BitSets for iterating over
> > > all docs or taking intersection sizes.  The hash also has fast random
> > > access that docNrSkipper doesn't have.
> > 
> > Can it take determine the intersection size faster than iterating over
> > both sets with an intersecting merge?
> 
> In many cases, yes.
> Consider the example of taking the intersection since of a small set
> with a large.  You need fast random access (or a fast skip) on the
> large set.

Well, a weak spot in the SortVIntList is that it does not have a fast skip.
This forces the skipTo method in the posted filtered query to use
a linear search.
More inspiration from the Lucene index data structures could be used
to build in the forwarding information to allow a faster skipTo
on the compact filter itself. The linear search is here:
http://issues.apache.org/bugzilla/show_bug.cgi?id=32921
in the nextDocNr(docNr) method of the DocNrSkipper returned
from SortedVIntList.getDocNrSkipper() .

Regards,
Paul Elschot.


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message