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.
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.
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.
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.
Mike
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: java-dev-h...@lucene.apache.org
