lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Nicolas Lalevée <nicolas.lale...@anyware-tech.com>
Subject Re: Per-document Payloads (was: Re: lucene indexing and merge process)
Date Sat, 20 Oct 2007 11:25:41 GMT
Le samedi 20 octobre 2007, Michael Busch a écrit :
> John Wang wrote:
> >      I can tried to get some numbers for leading an int[] array vs
> > FieldCache.getInts().
>
> I've had a similar performance problem when I used the FieldCache. The
> loading performance is apparently so slow, because each value is stored
> as a term in the dictionary. For loading the cache it is necessary to
> iterate over all terms for the field in the dictionary. And for each
> term it's posting list is opened to check which documents have that value.
>
> If you store unique docIds, then there are no two documents that share
> the same value. That means, that each value gets its own entry in the
> dictionary and to load each value it is necessary to perform two random
> I/O seeks (one for term lookup + one to open the posting list).
>
> In my app it took for a big index several minutes to fill the cache like
> that.
>
> To speed things up I did essentially what Ning suggested. Now I store
> the values as payloads in the posting list of an artificial term. To
> fill my cache it's only necessary to perform a couple of I/O seeks for
> opening the posting list of the specific term, then it is just a
> sequential scan to load all values. With this approach the time for
> filling the cache went down from minutes to seconds!
>
> Now this approach is already much better than the current field cache
> implementation, but it still can be improved. In fact, we already have a
> mechanism for doing that: the norms. Norms are stored with a fixed size,
> which means both random access and sequential scan are optimal. Norms
> are also cached in memory, and filling that cache is much faster
> compared to the current FieldCache approach.
>
> I was therefore thinking about adding per-document payloads to Lucene
> (we can also call it document-metadata). The API could look like this:
>
> Document d = new Document();
> byte[] uidValue = ...
> d.addMetadata("uid", uidValue);
>
> And on the retrieval side all values could either be loaded into the
> field cache, or, if the index is too big, a new API can be used:
>
> IndexReader reader = IndexReader.open(...);
> DocumentMetadataIterator it = reader.metadataIterator("uid");
>
> where DocumentMetadataIterator is an interface similar to TermDocs:
>
> interface DocumentMetadataIterator {
>   void seek(String name);
>   boolean next();
>   boolean skipTo(int doc);
>
>   int doc();
>   byte[] getMetadata();
> }
>
> The next question would be how to store the per-doc payloads (PDP). If
> all values have the same length (as the unique docIds), then we should
> store them as efficiently as possible, like the norms. However, we still
> want to offer the flexibility of having variable-length values. For this
> case we could use a new data structure similar to our posting list.
>
> PDPList               --> FixedLengthPDPList | <VariableLengthPDPList,
> SkipList>
> FixedLengthPDPList    --> <Payload>^SegSize
> VariableLengthPDPList --> <DocDelta, PayloadLength?, Payload>
> Payload               --> Byte^PayloadLength
> PayloadLength         --> VInt
> SkipList              --> see frq.file
>
> Because we don't have global field semantics Lucene should automatically
> pick the "right" data structure. This could work like this: When the
> DocumentsWriter writes a segment it checks whether all values of a PDP
> have the same length. If yes, it stores them as FixedLengthPDPList, if
> not, then as VariableLengthPDPList.
> When the SegmentMerger merges two or more segments it checks if all
> segments have a FixedLengthPDPList with the same length for a PDP. If
> not, it writes a VariableLengthPDPList to the new segment.
>
> I think this would be a nice new feature for Lucene. We could then have
> user-defined and Lucene-specific PDPs. For example, norms would be in
> the latter category (this way we would get rid of the special code for
> norms, as they could be handled as PDPs). It would also be easy to add
> new features in the future, like splitting the norms into two values: a
> norm and a boost value.
>
> OK lot's of thoughts, I'm sure I'll get lot's of comments too ... ;)

lot's thoughts, that makes me think of LUCENE-662 ;)

Nicolas

>
> - Michael
>
> > Thanks
> >
> > -John
> >
> > On 10/19/07, Michael McCandless <lucene@mikemccandless.com> wrote:
> >> It seems like there are (at least) two angles here for getting better
> >> performance from FieldCache:
> >>
> >>   1) Be incremental: with reopen() we should only have to update a
> >>      subset of the array in the FieldCache, according to the changed
> >>      segments.  This is what Hoss is working on and Mark was referring
> >>      to and I think it's very important!
> >>
> >>   2) Parsing is slow (?): I'm guessing one of the reasons that John
> >>      added the _X.udt file was because it's much faster to load an
> >>      array of already-parsed ints than to ask FieldCache to populate
> >>      itself.
> >>
> >> Even if we do #1, I think #2 could be a big win (in addition)?  John
> >> do you have any numbers of how much faster it is to load the array of
> >> ints from the _X.udt file vs having FieldCache populate itself?
> >>
> >> Also on the original question of "can we open up SegmentReader,
> >> FieldsWriter, etc.", I think that's a good idea?  At least we can make
> >> things protected instead of private/final?
> >>
> >> Mike
> >>
> >> "Ning Li" <ning.li.li@gmail.com> wrote:
> >>> I see what you mean by 2) now. What Mark said should work for you when
> >>> it's done.
> >>>
> >>> Cheers,
> >>> Ning
> >>>
> >>> On 10/18/07, John Wang <john.wang@gmail.com> wrote:
> >>>> Hi Ning:
> >>>>     That is essentially what field cache does. Doing this for each
> >>
> >> docid in
> >>
> >>>> the result set will be slow if the result set is large. But loading
it
> >>
> >> in
> >>
> >>>> memory when opening index can also be slow if the index is large and
> >>
> >> updates
> >>
> >>>> often.
> >>>>
> >>>> Thanks
> >>>>
> >>>> -John
> >>>>
> >>>> On 10/18/07, Ning Li <ning.li.li@gmail.com> wrote:
> >>>>> Make all documents have a term, say "ID:UID", and for each document,
> >>>>> store its UID in the term's payload. You can read off this posting
> >>>>> list to create your array. Will this work for you, John?
> >>>>>
> >>>>> Cheers,
> >>>>> Ning
> >>>>>
> >>>>> On 10/18/07, Erik Hatcher <erik@ehatchersolutions.com> wrote:
> >>>>>> Forwarding this to java-dev per request.  Seems like the best
> >>
> >> place
> >>
> >>>>>> to discuss this topic.
> >>>>>>
> >>>>>>         Erik
> >>>>>>
> >>>>>> Begin forwarded message:
> >>>>>>> From: "John Wang" <john.wang@gmail.com>
> >>>>>>> Date: October 17, 2007 5:43:29 PM EDT
> >>>>>>> To: erik@ehatchersolutions.com
> >>>>>>> Subject: lucene indexing and merge process
> >>>>>>>
> >>>>>>> Hi Erik:
> >>>>>>>
> >>>>>>>     We are revamping our search system here at LinekdIn.
And we
> >>
> >> are
> >>
> >>>>>>> using Lucene.
> >>>>>>>
> >>>>>>>     One issue we ran across is that we store an UID in Lucene
> >>
> >> which
> >>
> >>>>>>> we map to the DB storage. So given a docid, to lookup its
UID,
> >>
> >> we
> >>
> >>>>>>> have the following solutions:
> >>>>>>>
> >>>>>>> 1) Index it as a Stored field and get it from reader.document(very
> >>>>>>> slow if recall is large)
> >>>>>>> 2) Load/Warmup the FieldCache (for large corpus, loading
up the
> >>>>>>> indexreader can be slow)
> >>>>>>> 3) construct it using the FieldCache and persist it on disk
> >>>>>>> everytime the index changes. (not suitable for real time
> >>
> >> indexing,
> >>
> >>>>>>> e.g. this process will degrade as # of documents get large)
> >>>>>>>
> >>>>>>>     None of the above solutions turn out to be adequate
for our
> >>>>>>> requirements.
> >>>>>>>
> >>>>>>>      What we end up doing is to modify Lucene code by changing
> >>>>>>> SegmentReader,DocumentWriter,and FieldWriter classes by
taking
> >>>>>>> advantage of the Lucene Segment/merge process. E.g:
> >>>>>>>
> >>>>>>>      For each segment, we store a .udt file, which is an
int[]
> >>>>>>> array, (by changing the FieldWriter class)
> >>>>>>>
> >>>>>>>      And SegmentReader will load the .udt file into an array.
> >>>>>>>
> >>>>>>>      And merge happens seemlessly.
> >>>>>>>
> >>>>>>>      Because the tight encapsulation around these classes,
e.g.
> >>>>>>> private and final methods, it is very difficult to extend
Lucene
> >>>>>>> while avoiding branch into our own version. Is there a way
we
> >>
> >> can
> >>
> >>>>>>> open up and make these classes extensible? We'd be happy
to
> >>>>>>> contribute what we have done.
> >>>>>>>
> >>>>>>>      I guess to tackle the problem from a different angle:
is
> >>
> >> there
> >>
> >>>>>>> a way to incorporate FieldCache into the segments (it is
> >>
> >> strictly
> >>
> >>>>>>> in memory now), and build disk versions while indexing.
> >>>>>>>
> >>>>>>>
> >>>>>>>      Hope I am making sense.
> >>>>>>>
> >>>>>>>     I did not send this out to the mailing list because
I wasn't
> >>>>>>> sure if this is a dev question or an user question, feel
free to
> >>>>>>> either forward it to the right mailing list or let me know
and I
> >>>>>>> can forward it.
> >>>>>>>
> >>>>>>>
> >>>>>>> Thanks
> >>>>>>>
> >>>>>>> -John
> >>
> >> ---------------------------------------------------------------------
> >>
> >>>>>> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> >>>>>> For additional commands, e-mail: java-dev-help@lucene.apache.org
> >>
> >> ---------------------------------------------------------------------
> >>
> >>>>> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> >>>>> For additional commands, e-mail: java-dev-help@lucene.apache.org
> >>>
> >>> ---------------------------------------------------------------------
> >>> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> >>> For additional commands, e-mail: java-dev-help@lucene.apache.org
> >>
> >> ---------------------------------------------------------------------
> >> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> >> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org



---------------------------------------------------------------------
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