You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucy.apache.org by Marvin Humphrey <ma...@rectangular.com> on 2008/09/20 04:51:17 UTC
Posting codecs
[This is a continuation of a thread from the KinoSearch mailing list
entitled "Queries with large number of hits."]
On Sep 19, 2008, at 11:25 AM, Nathan Kurz wrote:
> Thanks for your quick research and improvements, Marvin. You prompted
> me to run a few quick tests as well:
>
> kinosearch_instream/perl$ search "the OR and OR of OR for" (ten times)
> kinosearch_instream/perl$ opreport -alt2 */KinoSearch.so
> CPU: CPU with timer interrupt, speed 0 MHz (estimated)
> Profiling through timer interrupt
> samples cum. samples % cum. % symbol name
> 190 190 23.8394 23.8394 kino_InStream_read_c32
> 112 302 14.0527 37.8921 kino_ScorePost_read_record
> 68 370 8.5320 46.4241 kino_ScorerDocQ_top_next
> 55 425 6.9009 53.3250 kino_TermScorer_next
> 51 476 6.3990 59.7240 kino_InStream_read_u8
> 45 521 5.6462 65.3701 kino_SegPList_next
> 31 552 3.8896 69.2597 __i686.get_pc_thunk.bx
> 30 582 3.7641 73.0238 advance_after_current
> 29 611 3.6386 76.6625 anonymous symbol from
> section .plt
> 25 636 3.1368 79.7992 kino_MemMan_wrapped_realloc
> 22 658 2.7604 82.5596 kino_ScorePostScorer_tally
> 17 675 2.1330 84.6926 kino_ORScorer_tally
>
> "opannotate --source */KinoSearch.so" is also useful to glance at, as
> is adding the '-c' flag to opreport to see where the calls are coming
> from and where the functions are spending their time internally.
> The main thing that jumped out is that the function call to
> Instream_read_c32 is killing us. I don't see any way to have this
> remain a per-int function call and still get good performance.
Let's set a goal of implementing PForDelta, and figure out how to get
there from here.
> You need to figure out some to decode the entire posting with fewer
> function calls, and this is where the bulk of them are coming from.
> I'd suggest having the Store level return an undecoded raw posting,
> and let the Posting class decode the parts it wants. That way the
> VByte code can be macros that work on a local buffer in a tight loop.
It's a little tricky to give anything other than the InStream object
itself direct access to the raw buffer. It's inevitable that the
bytes that form a compressed integer will straddle a buffer boundary
from time to time. InStream_read_c32 takes this into account by
calling refill() when necessary, but how do you factor that in when
working externally? MathUtils.h already has DECODE_C32 and ENCODE_C32
macros and they're pretty gnarly, even though they assume that the
buffer they're pointed at holds all the needed bytes.
Alternatively, if you decide to guarantee that any time you supply a
buffer to an outsider that it has all the necessary bytes for the C32,
the cost of scanning the stream to find the end of the record bites you.
Another theoretical possibility would be to store the size of each
undecoded posting in the index, perhaps as a prepended C32 -- similar
to how string data is stored. However, that would take extra space
and extra time to decode, and would be prohibitively expensive for
simple Posting formats like MatchPosting.
> The second thing that jumps out is that decompressing VBytes is
> expensive. P4Delta might be a significant advantage, or perhaps there
> are ways to optimize the decompression with the existing scheme.
In that study, compressed integers fared the worst of all the
competitors. We'll still need them for lots of other things, but
let's try to get PForDelta happening in the postings data.
> The last thing (sort of a non-thing) is that to my surprise the
> double/triple buffering of the Posting data doesn't seem to have much
> of a negative effect. I still think it's worth trying to avoid this,
> but it's barely on the current radar.
The double/triple buffering may not cause a slowdown, but it's worth
going with mmap for the backing buffer on InStream simply for memory
footprint. Since all index files are read-only once committed, they
can be shared. That means if you have multiple processes with
multiple IndexReaders all reading the same file, they can all
effectively use the same backing buffer, and we'll let the OS manage
page swapping.
> Did you also recreate an index without the position information, or
> are these times based on just skipping over the position info in the
> index?
I recreated the index, using a new Schema -- there was no other
choice. MatchPosting as presently implemented expects to see
<doc,freq> for each posting. (It really ought to be just <doc>, but I
hacked it so we could get these tests going.) If you give it
ScorePosting data <doc,freq,boost,positions>, it will misinterpret the
boost and positions as the next docs's data, get out of sync, return
wrong results, and possibly crash with an EOF error.
Marvin Humphrey
Rectangular Research
http://www.rectangular.com/
Re: Posting codecs
Posted by Nathan Kurz <na...@verse.com>.
On Fri, Oct 3, 2008 at 11:49 AM, Marvin Humphrey <ma...@rectangular.com> wrote:
> Here's an alternate implementation of ScorePosting's read method. (Note that
> the DECODE_C32 macro from MathUtils advances the pointer supplied to it.)
The code looks like it should give significantly better performance
than the current approach. And yes, a guarantee to be able to read to
the end of single posting should give most of the performance
benefits.
> while (num_prox--) {
> position += DECODE_32(buf);
> *positions++ = position;
> }
I think there are going to be better ways of doing this once we don't
have to check buffer bounds. I mentioned earlier that was looking at
a branchless way to decode VBytes. I don't have working code yet, and
it's not going to be truly branchless, but I'm pretty certain there is
room for big speedup by treating the VBytes in a byte-aligned manner.
The basic algorithm is to read several bytes, make a mask byte from
the high bits that are set, and then use the mask as a switch into a
jump table to handle the pattern of bytes encoded. It should make it
as fast as the S9/S16 code described in the PForDelta paper, and I
think we can make it even faster with a little MMX/SSE optimization.
Thus the loop above would be replaced with something like:
vbyte_read_block(&buf, num_prox, &positions);
Perhaps you could convert the loop into an inline function of this
signature to make a switch like this easier in the future?
> (Later, we'll go further and minimize processor decision branching using
> PForDelta.)
What is your anticipated path for doing this? Would you subclass
ScorePost as VByteScorePost and PForDeltaScorePost? And what would
the mechanism be to ensure that the correct one is used?
Nathan Kurz
nate@verse.com
Re: Posting codecs
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Sep 29, 2008, at 1:47 PM, Nathan Kurz wrote:
> I would try very hard to avoid doing buffer bounds checking.
The only place where we're really going to care about the performance issue of
buffer bounds checking is in the posting lists, since that's where the rubber
hits the road at search-time.
The first goal should be to avoid per-int or per-byte bounds checking, as
happens right now in InStream_Read_C32(). (Later, we'll go further and
minimize processor decision branching using PForDelta.)
I said before that we couldn't know the know the maximum length of a
ScorePosting in its current implementation, but we can sort of know it in
stages. Before we start reading, we know that the maximum space that the doc
num, freq, and boost at the top can take up is 11 bytes:
doc num => C32, max 5 bytes
freq => C32, max 5 bytes
boost => 1 byte
Once we know freq, we know the maximum number of bytes that the positions could
occupy.
positions => freq * C32_MAX_BYTES
To take advantage of this knowledge, we can add an argument to our buffer getter.
/** Get the InStream's buffer. Check to see whether <code>request</code>
* bytes are already in the buffer. If not, fill the buffer with either
* <code>request</code> bytes or the number of bytes remaining before EOF,
* whichever is smaller.
*
* @param request Advisory byte size request.
* @return Pointer to the InStream's internal buffer.
*/
char*
Buf(InStream *self, size_t request);
Here's an alternate implementation of ScorePosting's read method. (Note that
the DECODE_C32 macro from MathUtils advances the pointer supplied to it.)
void
ScorePost_read_record(ScorePosting *self, InStream *instream)
{
u32_t num_prox;
u32_t position = 0;
u32_t *positions;
const size_t max_start_bytes = (C32_MAX_BYTES * 2) + 1;
char *buf = InStream_Buf(self->instream, max_start_bytes);
const u32_t doc_code = DECODE_32(buf);
const u32_t doc_delta = doc_code >> 1;
/* Apply delta doc and retrieve freq. */
self->doc_num += doc_delta;
if (doc_code & 1)
self->freq = 1;
else
self->freq = DECODE_32(buf);
/* Decode boost/norm byte. */
self->weight = self->sim->norm_decoder[ *(u8_t*)buf ];
buf++;
/* Read positions. */
num_prox = self->freq;
buf = InStream_Buf(self->instream, num_prox * C32_MAX_BYTES);
if (num_prox > self->prox_cap) {
self->prox = REALLOCATE(self->prox, num_prox, u32_t);
self->prox_cap = num_prox;
}
positions = self->prox;
while (num_prox--) {
position += DECODE_32(buf);
*positions++ = position;
}
InStream_Advance_Buf(self->instream, buf);
}
The last method invoked, InStream_Advance_Buf(), is a setter which checks to
see whether the supplied pointer indicates a "read past EOF" error.
We're going to be changing the way that Postings are read, but the principle of
splicing in periodic buffer checking instead of needing it for every int read
still applies.
Marvin Humphrey
Rectangular Research
http://www.rectangular.com/
Re: Posting codecs
Posted by Nathan Kurz <na...@verse.com>.
On Sat, Sep 27, 2008 at 3:14 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
>> The downside is that each Scorer remains tied to particular index
>> format. Long-term I still think this is disastrous, but in the short
>> term it's not that bad.
>
> Can you please elaborate on what you see as the downsides?
I could be wrong about this, but I'll start here, as this question
relates closely to my motivations.
In the time I was trying to make use of KinoSearch, I found it very
difficult to experiment with new scoring systems and new index
formats. Each time I wanted to try something new (positional scoring
instead of TF/IDF, or reading posting lists from SQLite) it felt like
I had reinvent the whole wheel. Despite the layers of abstraction,
there are still a lot of cross-dependencies.
Currently, each posting class is tied to the internal binary format of
the index in use. And the low level scorers (like PhraseScorer)
presume a binary layout of the Posting. Creating a new index format
involves either involves creating a whole bunch of classes, or
understanding the interactions of the existing classes well enough to
maintain full compatibility. Despite considerable time spent, I still
don't feel like I understand these interactions.
Worse, my own uses of KinoSearch are likely to include custom scorers
interacting with custom indexes. It's highly unlikely that anyone
else is going to have exactly the same needs. But it seems reasonably
likely that others would be interested in just the scoring approach,
or just the index format. I think development might go much faster if
these two could be decoupled.
The goal would be to make it possible to write a new index format as a
single class and to have the existing scorers just keep working.
Conversely, I want to have my (theoretical) custom scorers keep
working even though the underlying index format changes. I want it to
be possible to use others' components piece by piece without having to
replace the whole Scorer/Posting/InStream/etc complex, and to make it
possible for others to use and test my components without having to
use my whole system.
I don't think this is possible with the current approach, and I fear
this will hinder future development and developers. This could be
just evidence of my own limitations, though. Perhaps I just need
better examples of how to accomplish these things with the current
system. Thus my suggestions for adding parallel support for P4Delta
compression, reading Lucene indexes directly, and non-TF/IDF
positional scoring. I'm hoping that either you'll show the way to do
this effectively, or realize the need for architectural changes to
allow this.
Nathan Kurz
nate@verse.com
Re: Posting codecs
Posted by Nathan Kurz <na...@verse.com>.
On Sat, Sep 27, 2008 at 3:14 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
> What if the index is large enough that it we exceed the system's addressable
> space?
Sadly, I haven't considered this problem at all. I just naively
thought it wasn't going to be a problem. And for my own uses, I think
this is true: I've been looking at systems that fit in RAM running on
a 64-bit OS. Either of these conditions alone should make it that
addressable space is the first limit one hits. But yes, if you have a
32-bit OS with a <4GB address space and a large index, you could run
up against this limit pretty quickly.
Perhaps not as quickly as you'd presume, though. The way I was
looking at it, it's not the total size of the index that matters, only
the total size of the posting lists involved in the query. I was
thinking to mmap() each posting list independently. Even so, with no
stop-words and a sufficiently complex query, you could probably run
out of address space with a <10GB index.
My first instinct would be to ignore the problem, and declare 32-bit
systems as suitable for development, testing, and small-scale home
use only. My alternative instinct (perhaps no less unreasonable)
would be to limit index segments to 4GB on 32-bit systems, and
map/unmap on a per-segment basis.
In my mind, once we need to load from disk a subset of index larger
than addressable space, we've already given up on performance and are
just trying to slog through without undue embarrassment. I'm sure
there are use-cases where this is not the case, however.
I would try very hard to avoid doing buffer bounds checking. The code
will be so much simpler and faster if it is not done. If it truly
needs to be done, I would figure out a way to encapsulate it within
the index reader, and just guarantee to the higher levels that they
can read through to end of the current posting without overstepping
bounds.
> Also, many posting formats won't have a theoretical maximum length. The
> current implementation of ScorePosting doesn't for instance, because there's no
> ceiling on the number of positions.
True, but I'd hope it's reasonable to require that the collectiive
postings being used to score an individual document can fit into
addressable memory, if not physical memory? While there is no
theoretical limit on the length of a posting, imposing a practical
limit here seems reasonable.
> We should ape Lucene and give PostingList a Bulk_Read() method, which gets
> called by the TermScorer subclass.
I still don't think this would be a win, at least not for any postings
that include position information. If you read in a large enough list
to have significant avoidance of function overhead, you'll just blow
your L1 or L2 cache. For match-only postings there might be a sweet
spot, but I think the real win will still be from making it very fast
to fill a single posting from the raw index.
Nathan Kurz
nate@verse.com
Re: Posting codecs
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Sep 26, 2008, at 12:30 AM, Nathan Kurz wrote:
> The first step would be to switch InStream to using mmap() instead of
> its user level buffering. This looks surprisingly easy, presuming we
> are allowed to ignore Windows' compatibility, or at least Windows'
> performance.
Windows has MapViewOfFile. If that allows us to duplicate the stuff we can do
with mmap on Unixen, great. If not, we can fall back to the current
implementation of reading into a malloc'd buffer.
> The second step would then be to expose InStream->buf,
I'm warming to the idea of exposing the raw buffer. It's actually a pretty
flexible approach -- better than, say, exposing a FILE*.
I think we'd want InStream to expose two pointers: the current buffer pointer,
and the end of the buffer.
> probably via an accessor so that EOF can be reported.
It would be bad to expose InStream->buf directly, thereby freezing the layout
of the InStream struct up to that member, but since we're trying to cut down on
function call overhead, the cost of the accessor is a bit of a bummer. As an
alternative, we might consider using a static inline functions and a variation
on the inside-out technique we use for method calls.
extern size_t Kino_InStream_Buf_MEMBER_OFFSET;
static CHY_INLINE char**
Kino_InStream_Raw_Buf(kino_InStream *self)
{
char *const byteself = (char*)self;
char *const buf = byteself + Kino_InStream_Buf_MEMBER_OFFSET;
return &buf;
}
Since that's a static inline function, there's no function call overhead. Of
course we can't go back and change the behavior of the function call later like
we could with a traditional accessor, and we're committing to having a real
char* buf member in the InStream struct. However, we're not committing that
"buf" will be located at a fixed offset within the InStream struct -- only that
there will be a variable named Kino_InStream_Buf_MEMBER_OFFSET which will tell
you where that offset is. Thus the layout of InStream can stay private.
InStream_Raw_Buf_End() would be implemented nearly the same way, but would
return a char* instead of a char**:
extern size_t Kino_InStream_Buf_End_MEMBER_OFFSET;
static CHY_INLINE char*
Kino_InStream_Raw_Buf_End(kino_InStream *self)
{
char *const byteself = (char*)self;
char *const buf_end = byteself + Kino_InStream_Buf_End_MEMBER_OFFSET;
return buf;
}
I think we should leave it up to the caller to ensure that InStream->buf never
advances beyond InStream->buf_end and that refill() get called when necessary.
> but once we are using mmap we shouldn't ever need to call refill().
What if the index is large enough that it we exceed the system's addressable
space? I think we have to mmap using the system page size. Which means that
to avoid overruns we'll have to track our position within the file and call
refill() every once in a while.
> There would need to be some implied rules, such as never go beyond the
> current Posting.
We might be able to kick in an optimization if we can determine that the buffer
has bytes left exceeding the maximum length of the current posting format: we'd
branch to code that doesn't do bounds checking and never calls refill.
There's a downside to that, though. Code that does bounds checking will throw
meaningful exceptions as soon as an overrun occurs. Code that doesn't do
bounds checking will cause memory errors, with unpredictable consequences.
Also, many posting formats won't have a theoretical maximum length. The
current implementation of ScorePosting doesn't for instance, because there's no
ceiling on the number of positions.
> The third step is to change ScorePost->read_record to decode the
> VBytes directly from the raw buffer, or perhaps better, to create a
> FastScorePost subclass that does this. InStream->seek() is called
> after the buffer is read to update Instream->buf and assert() any
> reads that go to far.
We should ape Lucene and give PostingList a Bulk_Read() method, which gets
called by the TermScorer subclass.
> The nice part about this approach is that we should get a nice
> speed-up for the common use cases while requiring very few API
> changes. Old scorers et al can still continue as they did before, and
> new ones can change over gradually.
>
> The downside is that each Scorer remains tied to particular index
> format. Long-term I still think this is disastrous, but in the short
> term it's not that bad.
Can you please elaborate on what you see as the downsides?
> But perhaps we can delay solving this problem until you get P4Delta ready to
> go.
The hard part about implementing PForDelta is that it involves block read/write
of integers. KS isn't set up to do that, either at index-time or search-time.
Whether InStream is refills its buffer using mmap() or read() is a completely
separate problem, though -- so let's get mmap() taken care of first.
Marvin Humphrey
Rectangular Research
http://www.rectangular.com/
Re: Posting codecs
Posted by Nathan Kurz <na...@verse.com>.
I started looking at the code a bit, trying to figure out a more
incremental way of approaching this. I now think there might be room
for one, although as always my urge to boil oceans is hard to
suppress.
The first step would be to switch InStream to using mmap() instead of
its user level buffering. This looks surprisingly easy, presuming we
are allowed to ignore Windows' compatibility, or at least Windows'
performance.
The second step would then be to expose InStream->buf, probably via
an accessor so that EOF can be reported. I said I wasn't intending
to expose the raw buffer, but once we are using mmap we shouldn't
ever need to call refill(). There would need to be some implied
rules, such as never go beyond the current Posting.
The third step is to change ScorePost->read_record to decode the
VBytes directly from the raw buffer, or perhaps better, to create a
FastScorePost subclass that does this. InStream->seek() is called
after the buffer is read to update Instream->buf and assert() any
reads that go to far.
The nice part about this approach is that we should get a nice
speed-up for the common use cases while requiring very few API
changes. Old scorers et al can still continue as they did before, and
new ones can change over gradually.
The downside is that each Scorer remains tied to particular index
format. Long-term I still think this is disastrous, but in the short
term it's not that bad. But perhaps we can delay solving this problem
until you get P4Delta ready to go.
Sound plausible?
Nathan Kurz
nate@verse.com
On Mon, Sep 22, 2008 at 12:35 AM, Nathan Kurz <na...@verse.com> wrote:
> On Fri, Sep 19, 2008 at 8:51 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
>> Let's set a goal of implementing PForDelta, and figure out how to get there
>> from here.
>
> Sure, that seems like a fine goal. I'm not sure if you meant it this
> way, but I think it would be great to add support for PForDelta to the
> existing VByte support rather than just replacing it. While PForDelta
> might fully replace VByte eventually, it would be good to design an
> architecture that allows for multiple file formats, so that tricks
> like using Lucene index files directly are theoretically possible, and
> so that the path for creating custom file formats is better tested.
>
>>> You need to figure out some to decode the entire posting with fewer
>>> function calls, and this is where the bulk of them are coming from.
>>> I'd suggest having the Store level return an undecoded raw posting,
>>> and let the Posting class decode the parts it wants. That way the
>>> VByte code can be macros that work on a local buffer in a tight loop.
>>
>> It's a little tricky to give anything other than the InStream object itself
>> direct access to the raw buffer. It's inevitable that the bytes that form a
>> compressed integer will straddle a buffer boundary from time to time.
>
> OK. I wasn't hoping to give access to the raw buffer, but to a cooked
> one guaranteed to contain the entire posting. But I'd forgotten that
> the size of the compressed posting isn't known in advance! The
> important part, though, is that the entire posting be decompressed in
> a tight loop with minimal function call overhead. So instead of my
> first suggestion, can we have the Store return a fully decoded
> Posting?
>
> More fully fleshed out (up to partially-informed), I'd like for a
> system that looks something like this:
>
> 1) Scorer->init creates a template Posting which is passed to the
> Store for approval. Store initializes itself and answers
> affirmatively if it can handle the particular flavor of Posting
> proposed. For example, Store->init_posting(PositionPosting) might be
> refused by a Store than only handles MatchPostings due to index
> limitations. Alternatively, a Store managing an index that has
> position information available might re-wire itself to use a faster
> method to fill a MatchPosting than a full PositionPosting.
>
> 2) Scoring loop starts and Scorer calls
> Store->fill_posting(PositionPosting, min_doc_number) . This is
> analogous to Scorer->SkipTo(), but decodes the entire posting from the
> index in a single pass. The Posting has nominal control over its own
> fields (resizes its own position buffer, for example) but the Store is
> allowed to write data directly to the struct and the Scorer reads
> fields directly from them.
>
> My goals here are to have a system that dramatically speeds up the the
> reads from the index, makes it possible for existing Scorers to work
> with new index formats, and allows for easy creation of custom Scorers
> for use with custom indexes. My guess is that a move to this system
> would give an immediate 2x speedup, while making it easier to add
> custom features and future optimizations. I think the main downside
> is that it violates most people's conception of a standard Object
> Oriented Model. Personally, my main doubts are about the
> initialization/negotiation phase --- perhaps there is some better way
> to do this?
>
> And I apologize for my ad hoc terminology. It's partly that I'm not
> familiar with the proper Kinosearch terminology, and partly that the
> levels that are there don't quite map up with my mental model. What I
> want is for the Posting to be an intermediary between the Scorer and
> the Store, where the Posting has a known data layout and only the
> Store knows about the index internals, be it using VByte or PForDelta.
> I'd be happy to call the Store an Index, apart from the confusion
> between the file and the class, but I'm not comfortable viewing it as
> a Stream. Is there a more standard way to express this?
>
>>> The last thing (sort of a non-thing) is that to my surprise the
>>> double/triple buffering of the Posting data doesn't seem to have much
>>> of a negative effect. I still think it's worth trying to avoid this,
>>> but it's barely on the current radar.
>>
>> The double/triple buffering may not cause a slowdown, but it's worth going
>> with mmap for the backing buffer on InStream simply for memory footprint.
>> Since all index files are read-only once committed, they can be shared.
>> That means if you have multiple processes with multiple IndexReaders all
>> reading the same file, they can all effectively use the same backing buffer,
>> and we'll let the OS manage page swapping.
>
> I agree that there a multiple other reasons for using mmap here. I
> definitely want a design that makes it easy to drop in mmap versions
> of the index readers for all the reasons that you specify. I'm also
> hoping that we can make the rest of the search process efficient
> enough that the savings of moving to single buffering does become
> worthwhile. But we have a ways to go until that is the case: maybe a
> 8x speedup from the recent baseline before it starts to be a limiting
> factor? I'm optimistic that this level of speedup is possible,
> though.
>
> Nathan Kurz
> nate@verse.com
>
Lucy File Format
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Mon, Sep 22, 2008 at 12:35:53AM -0600, Nathan Kurz wrote:
>> Let's set a goal of implementing PForDelta, and figure out how to get there
>> from here.
>
> Sure, that seems like a fine goal. I'm not sure if you meant it this
> way, but I think it would be great to add support for PForDelta to the
> existing VByte support rather than just replacing it. While PForDelta
> might fully replace VByte eventually, it would be good to design an
> architecture that allows for multiple file formats, so that tricks
> like using Lucene index files directly are theoretically possible,
Supporting the Lucene index file format would be very costly -- it's complex,
fragile, opaque, and a moving target. It is not designed for interchange; the
spec doc is a post hoc description of what Lucene does rather than the product
of a goal-oriented design process. It contains no human readable or editable
components, making it difficult to debug or spelunk. It gets updated
frequently to accommodate minor optimizations, the rationale being that Lucene
is a low-level component of many other projects and the widespread trickle-down
performance benefits justify the increased maintentance costs and complexity.
Instead, we should strive to spec out a better index format ourselves.
* Human readable metadata.
* More files but simpler binary formats.
* Global field semantics.
* Explicit mechanisms for extensibility.
It would be easier to write some Lucene contrib modules to support a
well-designed Lucy format than to chase Lucene's format with C code. And if
we nail it and write a really good spec, we may be able to persuade the Java
Lucene community to come to us.
I'll add a new directory in SVN, trunk/devel/file_format, where we can put the
spec documents. For now, HTML is probably best; we can switch to XML to
facilitate transforms once the spec starts to mature. I'll also fire up JIRA
issues for discussing each section as it gets added.
Here's a provisional TOC:
1. Conventions
2. Overview
3. Virtual File System (VFS)
4. Segment Files
5. Schema
6. Primitives
7. File Format Details
a. snapshot
b. write.lock
c. schema
d. segment metadata
e. compound file
f. document storage
g. lexicon
h. postings
8. Extensibility
We can kick things off with the VFS section, since I've already written a draft.
Marvin Humphrey
Rectangular Research
http://www.rectangular.com/
Re: Posting codecs
Posted by Nathan Kurz <na...@verse.com>.
On Fri, Sep 19, 2008 at 8:51 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
> Let's set a goal of implementing PForDelta, and figure out how to get there
> from here.
Sure, that seems like a fine goal. I'm not sure if you meant it this
way, but I think it would be great to add support for PForDelta to the
existing VByte support rather than just replacing it. While PForDelta
might fully replace VByte eventually, it would be good to design an
architecture that allows for multiple file formats, so that tricks
like using Lucene index files directly are theoretically possible, and
so that the path for creating custom file formats is better tested.
>> You need to figure out some to decode the entire posting with fewer
>> function calls, and this is where the bulk of them are coming from.
>> I'd suggest having the Store level return an undecoded raw posting,
>> and let the Posting class decode the parts it wants. That way the
>> VByte code can be macros that work on a local buffer in a tight loop.
>
> It's a little tricky to give anything other than the InStream object itself
> direct access to the raw buffer. It's inevitable that the bytes that form a
> compressed integer will straddle a buffer boundary from time to time.
OK. I wasn't hoping to give access to the raw buffer, but to a cooked
one guaranteed to contain the entire posting. But I'd forgotten that
the size of the compressed posting isn't known in advance! The
important part, though, is that the entire posting be decompressed in
a tight loop with minimal function call overhead. So instead of my
first suggestion, can we have the Store return a fully decoded
Posting?
More fully fleshed out (up to partially-informed), I'd like for a
system that looks something like this:
1) Scorer->init creates a template Posting which is passed to the
Store for approval. Store initializes itself and answers
affirmatively if it can handle the particular flavor of Posting
proposed. For example, Store->init_posting(PositionPosting) might be
refused by a Store than only handles MatchPostings due to index
limitations. Alternatively, a Store managing an index that has
position information available might re-wire itself to use a faster
method to fill a MatchPosting than a full PositionPosting.
2) Scoring loop starts and Scorer calls
Store->fill_posting(PositionPosting, min_doc_number) . This is
analogous to Scorer->SkipTo(), but decodes the entire posting from the
index in a single pass. The Posting has nominal control over its own
fields (resizes its own position buffer, for example) but the Store is
allowed to write data directly to the struct and the Scorer reads
fields directly from them.
My goals here are to have a system that dramatically speeds up the the
reads from the index, makes it possible for existing Scorers to work
with new index formats, and allows for easy creation of custom Scorers
for use with custom indexes. My guess is that a move to this system
would give an immediate 2x speedup, while making it easier to add
custom features and future optimizations. I think the main downside
is that it violates most people's conception of a standard Object
Oriented Model. Personally, my main doubts are about the
initialization/negotiation phase --- perhaps there is some better way
to do this?
And I apologize for my ad hoc terminology. It's partly that I'm not
familiar with the proper Kinosearch terminology, and partly that the
levels that are there don't quite map up with my mental model. What I
want is for the Posting to be an intermediary between the Scorer and
the Store, where the Posting has a known data layout and only the
Store knows about the index internals, be it using VByte or PForDelta.
I'd be happy to call the Store an Index, apart from the confusion
between the file and the class, but I'm not comfortable viewing it as
a Stream. Is there a more standard way to express this?
>> The last thing (sort of a non-thing) is that to my surprise the
>> double/triple buffering of the Posting data doesn't seem to have much
>> of a negative effect. I still think it's worth trying to avoid this,
>> but it's barely on the current radar.
>
> The double/triple buffering may not cause a slowdown, but it's worth going
> with mmap for the backing buffer on InStream simply for memory footprint.
> Since all index files are read-only once committed, they can be shared.
> That means if you have multiple processes with multiple IndexReaders all
> reading the same file, they can all effectively use the same backing buffer,
> and we'll let the OS manage page swapping.
I agree that there a multiple other reasons for using mmap here. I
definitely want a design that makes it easy to drop in mmap versions
of the index readers for all the reasons that you specify. I'm also
hoping that we can make the rest of the search process efficient
enough that the savings of moving to single buffering does become
worthwhile. But we have a ways to go until that is the case: maybe a
8x speedup from the recent baseline before it starts to be a limiting
factor? I'm optimistic that this level of speedup is possible,
though.
Nathan Kurz
nate@verse.com