On Monday 19 January 2009 11:32:17 Michael McCandless wrote: > > Paul Elschot wrote: > > > Since this started by thinking out loud, I'd like to continue doing > > that. > > I've been thinking about how to add a decent skipTo() to something > > that > > compresses better than an (Open)BitSet, and this turns out to be an > > integer set implemented as a B plus tree (all leafs on the same > > level) of > > only integers with key/data compression by a frame of reference for > > every node (see LUCENE-1410). > > Sounds great! With flexible indexing (LUCENE-1458, which I'm needing > to get back to & finish...) you could experiment with these sorts of > changes to the postings format by implementing your own codec.
I'll take a look there. > > > For example, how close is the current lucene code base to implementing > > a b plus tree for the doc ids of a single term? > > I'm not sure this is a good fit -- B+ trees are great at > insertion/deletion of entries, but we never do that with our postings > (they are write once). > > Though if the set operations are substantially > faster (??) than the doc-at-a-time iteration Lucene does today, then > maybe it is compelling? But we'd have to change up how AND/OR queries > work to translate into these set operations. The idea is to implement a DocIdSetIterator on top of this, with the usual next() and skipTo(), so it should fit in the current lucene framework. > > How valuable are transaction semantics for such an integer set? It is > > tempting to try and implement such an integer set by starting from the > > ground up, but I don't have any practical programming experience with > > transaction semantics, so it may be better to start from something > > that > > has transactions right from the start. > > If we use this to store/access deleted docs in RAM, then transactions > are very important for realtime search. With LUCENE-1314 > (IndexReader.clone) a cloned reader carries over the deletes from the > original reader but must "copy on write" as soon as a new deletion is > made. With BitVector for deleted docs, this operation is very costly. > But if we used B+ tree (or something similar) in RAM to hold the > deleted docs, and that lets us incrementally copy-on-write only the > nodes/blocks affected by the changes, that would be very useful. The one referenced by Eks Dev would be a good starting point for that, it's basically a binary tree of BitSets of at most 1024 bits at the leafs. > It could also be useful for storing deleted docs in the index, ie, > this is an alternative to tombstones, in which case its transactional > support would be good, to avoid writing an entire BitVector when only > a few additional docs became deleted, during commit. This would fit > nicely with Lucene's already transactional index storage, ie rather > than storing the "deletion generation" (an int) that we store today, > we'd store some reference into the B+ tree indicating the > "commit point" to use for deletions. > > But I think this usage (changing how deletions are stored on disk) is > less compelling than changing how deletions are stored/used in RAM. Thanks, Paul Elschot
