lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael Busch <busch...@gmail.com>
Subject Per-document Payloads (was: Re: lucene indexing and merge process)
Date Fri, 19 Oct 2007 22:53:47 GMT
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 ... ;)

- 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


Mime
View raw message