lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Grant Ingersoll <>
Subject Re: Flexible indexing (was: Re: [jira] Commented: (LUCENE-755) Payloads)
Date Sat, 10 Mar 2007 23:53:46 GMT
Hi Michael,

This is very good.  I know 662 is different, just wasn't sure if  
Nicolas patch was meant to be applied after 662, b/c I know we had  
discussed this before.

I do agree with you about planning this out, but I also know that  
patches seem to motivate people the best and provide a certain  
concreteness to it all.  I mostly started asking questions on these  
two issues b/c I wanted to spur some more discussion and see if we  
can get people motivated to move on it.

I was hoping that I would be able to apply each patch to two  
different checkouts so I could start seeing where the overlap is and  
how they could fit together (I also admit I was procrastinating on my  
ApacheCon talk...).  In the new, flexible world, the payloads  
implementation could be a separate implementation of the indexing or  
it could be part of the core/existing file format implementation.   
Sometimes I just need to get my hands on the code to get a real feel  
for what I feel is the best way to do it.

I agree about the XML storage for Index information.  We do that in  
our in-house wrapper around Lucene, storing info about the language,  
analyzer used, etc.  We may also want a binary index-level storage  
capability.  I know most people just create a single document usually  
to store binary info about the index, but an binary storage might be  
good too.

Part of me says to apply the Payloads patch now, as it provides a lot  
of bang for the buck and I think the FI is going to take a lot longer  
to hash out.  However, I know that it may pin us in or force us to  
change things for FI.  Ultimately, I would love to see both these  
features for the next release, but that isn't a requirement.  Also,  
on FI, I would love to see two different implementations of whatever  
API we choose before releasing it, as I always find two  
implementations of an Interface really work out the API details.


On Mar 10, 2007, at 6:27 PM, Michael Busch wrote:

> Hi Grant,
> LUCENE-662 contains different ideas:
> 1) introduction of an index format concept
> 2) extensibility of the store reader/writer
> 3) New: extensibility of the posting reader/writer
> IMO we should split this up, that way it will be easier to develop  
> smaller patches that focus on adding one particular feature.  
> However, it is important to plan the API, so that different patches  
> (like payloads) fit in. On the other hand it will be nearly  
> impossible to plan an API that is perfect and won't change anymore  
> without having the actual implementions. Therefore I suggest the  
> following steps:
> a) define the different work items of flexible indexing
> b) plan a API rougly that fits with all items
> c) develop the different items, commit them but with either  
> protected or as experimental marked APIs
> d) after all items are completed and committed (and hopefully  
> tested by some brave community members ;)) finalize the API and  
> remove experimental comments (or make public)
> Let's start with a):
> The following items come to my mind (please feel free to add/remove/ 
> complain):
> - Introduce index-level metadata. Preferable in XML format, so it  
> will be human readable. Later on, we can store information about  
> the index format in this file, like the codecs that are used to  
> store the data. We should also make this public, so that users can  
> store their own index metadata. (Remark: LUCENE-783 is also a neat  
> idea, we can write one xml parser for both items)
> - Introduce index format. Nicolas has already written a lot of code  
> in this regard! It will include different interfaces for the  
> different extension points (FieldsFormat, PostingFormat,  
> DictionaryFormat). We can use the xml file to store which actual  
> formats are used in the corresponding index.
> - Implement the different extensions. LUCENE-662 includes an  
> extensible FieldsWriter, LUCENE-755 the payloads feature. Doug and  
> Ning suggested already nice interfaces for PostingFormat and  
> DictionaryFormat in the payloads thread on java-dev.
> - Write standard implementations for the different formats. In the  
> wiki is already a list of desired posting formats.
> I suggest we should finalize this list first. Then I will add this  
> list to the wiki under Flexible indexing and gather information  
> from the different discussions on java-dev which I already  
> mentioned. Then we should discuss the different items of this list  
> in greater depth and plan the APIs (step b) ).  And then we're  
> already ready for step c) and the fun starts :-).
> Michael
> Grant Ingersoll wrote:
>> I think it makes the most sense to get flexible indexing in first,  
>> and then make payloads work with it.  On the other hand, payloads  
>> looked pretty straightforward to me, whereas FI is much more  
>> involved (or at least it feels that way).
>> As it is right now, I would like to at least review the two  
>> patches and start thinking about them in greater depth.  The  
>> payloads patch needs a little more work in that I want to  
>> integrate it with the Similarity class so people can customize  
>> their scoring.
>> -Grant
>> On Mar 10, 2007, at 9:30 AM, Nicolas Lalevée (JIRA) wrote:
>>>     [ 
>>> page=com.atlassian.jira.plugin.system.issuetabpanels:comment- 
>>> tabpanel#action_12479841 ]
>>> Nicolas Lalevée commented on LUCENE-755:
>>> ----------------------------------------
>>> Grant>
>>> The patch I have propsed here has no dependency on LUCENE-662, I  
>>> just "imported" some ideas from it and put them there. Since the  
>>> LUCENE-662 have involved, the patches will probably make  
>>> conflicts. The best to use here is Michael's one. I think it  
>>> won't conflit with LUCENE-662. And if both are intended to be  
>>> commited, then the best is to commit the both seperately and redo  
>>> the work I have done with the provided patch (I remember that it  
>>> was quite easy).
>>>> Payloads
>>>> --------
>>>>                 Key: LUCENE-755
>>>>                 URL: 
>>>> LUCENE-755
>>>>             Project: Lucene - Java
>>>>          Issue Type: New Feature
>>>>          Components: Index
>>>>            Reporter: Michael Busch
>>>>         Assigned To: Michael Busch
>>>>         Attachments: payload.patch, payloads.patch
>>>> This patch adds the possibility to store arbitrary metadata  
>>>> (payloads) together with each position of a term in its posting  
>>>> lists. A while ago this was discussed on the dev mailing list,  
>>>> where I proposed an initial design. This patch has a much  
>>>> improved design with modifications, that make this new feature  
>>>> easier to use and more efficient.
>>>> A payload is an array of bytes that can be stored inline in the  
>>>> ProxFile (.prx). Therefore this patch provides low-level APIs to  
>>>> simply store and retrieve byte arrays in the posting lists in an  
>>>> efficient way.
>>>> API and Usage
>>>> ------------------------------
>>>> The new class index.Payload is basically just a wrapper around a  
>>>> byte[] array together with int variables for offset and length.  
>>>> So a user does not have to create a byte array for every  
>>>> payload, but can rather allocate one array for all payloads of a  
>>>> document and provide offset and length information. This reduces  
>>>> object allocations on the application side.
>>>> In order to store payloads in the posting lists one has to  
>>>> provide a TokenStream or TokenFilter that produces Tokens with  
>>>> payloads. I added the following two methods to the Token class:
>>>>   /** Sets this Token's payload. */
>>>>   public void setPayload(Payload payload);
>>>>   /** Returns this Token's payload. */
>>>>   public Payload getPayload();
>>>> In order to retrieve the data from the index the interface  
>>>> TermPositions now offers two new methods:
>>>>   /** Returns the payload length of the current term position.
>>>>    *  This is invalid until {@link #nextPosition()} is called for
>>>>    *  the first time.
>>>>    *
>>>>    * @return length of the current payload in number of bytes
>>>>    */
>>>>   int getPayloadLength();
>>>>   /** Returns the payload data of the current term position.
>>>>    * This is invalid until {@link #nextPosition()} is called for
>>>>    * the first time.
>>>>    * This method must not be called more than once after each call
>>>>    * of {@link #nextPosition()}. However, payloads are loaded  
>>>> lazily,
>>>>    * so if the payload data for the current position is not needed,
>>>>    * this method may not be called at all for performance reasons.
>>>>    *
>>>>    * @param data the array into which the data of this payload  
>>>> is to be
>>>>    *             stored, if it is big enough; otherwise, a new  
>>>> byte[] array
>>>>    *             is allocated for this purpose.
>>>>    * @param offset the offset in the array into which the data  
>>>> of this payload
>>>>    *               is to be stored.
>>>>    * @return a byte[] array containing the data of this payload
>>>>    * @throws IOException
>>>>    */
>>>>   byte[] getPayload(byte[] data, int offset) throws IOException;
>>>> Furthermore, this patch indroduces the new method  
>>>> IndexOutput.writeBytes(byte[] b, int offset, int length). So far  
>>>> there was only a writeBytes()-method without an offset argument.
>>>> Implementation details
>>>> ------------------------------
>>>> - One field bit in FieldInfos is used to indicate if payloads  
>>>> are enabled for a field. The user does not have to enable  
>>>> payloads for a field, this is done automatically:
>>>>    * The DocumentWriter enables payloads for a field, if one ore  
>>>> more Tokens carry payloads.
>>>>    * The SegmentMerger enables payloads for a field during a  
>>>> merge, if payloads are enabled for that field in one or more  
>>>> segments.
>>>> - Backwards compatible: If payloads are not used, then the  
>>>> formats of the ProxFile and FreqFile don't change
>>>> - Payloads are stored inline in the posting list of a term in  
>>>> the ProxFile. A payload of a term occurrence is stored right  
>>>> after its PositionDelta.
>>>> - Same-length compression: If payloads are enabled for a field,  
>>>> then the PositionDelta is shifted one bit. The lowest bit is  
>>>> used to indicate whether the length of the following payload is  
>>>> stored explicitly. If not, i. e. the bit is false, then the  
>>>> payload has the same length as the payload of the previous term  
>>>> occurrence.
>>>> - In order to support skipping on the ProxFile the length of the  
>>>> payload at every skip point has to be known. Therefore the  
>>>> payload length is also stored in the skip list located in the  
>>>> FreqFile. Here the same-length compression is also used: The  
>>>> lowest bit of DocSkip is used to indicate if the payload length  
>>>> is stored for a SkipDatum or if the length is the same as in the  
>>>> last SkipDatum.
>>>> - Payloads are loaded lazily. When a user calls  
>>>> TermPositions.nextPosition() then only the position and the  
>>>> payload length is loaded from the ProxFile. If the user calls  
>>>> getPayload() then the payload is actually loaded. If getPayload 
>>>> () is not called before nextPosition() is called again, then the  
>>>> payload data is just skipped.
>>>> Changes of file formats
>>>> ------------------------------
>>>> - FieldInfos (.fnm)
>>>> The format of the .fnm file does not change. The only change is  
>>>> the use of the sixth lowest-order bit (0x20) of the FieldBits.  
>>>> If this bit is set, then payloads are enabled for the  
>>>> corresponding field.
>>>> - ProxFile (.prx)
>>>> ProxFile (.prx) -->  <TermPositions>^TermCount
>>>> TermPositions   --> <Positions>^DocFreq
>>>> Positions       --> <PositionDelta, Payload?>^Freq
>>>> Payload         --> <PayloadLength?, PayloadData>
>>>> PositionDelta   --> VInt
>>>> PayloadLength   --> VInt
>>>> PayloadData     --> byte^PayloadLength
>>>> For payloads disabled (unchanged):
>>>> PositionDelta is the difference between the position of the  
>>>> current occurrence in the document and the previous occurrence  
>>>> (or zero, if this is the first   occurrence in this document).
>>>> For Payloads enabled:
>>>> PositionDelta/2 is the difference between the position of the  
>>>> current occurrence in the document and the previous occurrence.  
>>>> If PositionDelta is odd, then PayloadLength is stored. If  
>>>> PositionDelta is even, then the length of the current payload  
>>>> equals the length of the previous payload and thus PayloadLength  
>>>> is omitted.
>>>> - FreqFile (.frq)
>>>> SkipDatum     --> DocSkip, PayloadLength?, FreqSkip, ProxSkip
>>>> PayloadLength --> VInt
>>>> For payloads disabled (unchanged):
>>>> DocSkip records the document number before every SkipInterval th  
>>>> document in TermFreqs. Document numbers are represented as  
>>>> differences from the previous value in the sequence.
>>>> For payloads enabled:
>>>> DocSkip/2 records the document number before every SkipInterval  
>>>> th  document in TermFreqs. If DocSkip is odd, then PayloadLength  
>>>> follows. If DocSkip is even, then the length of the payload at  
>>>> the current skip point equals the length of the payload at the  
>>>> last skip point and thus PayloadLength is omitted.
>>>> This encoding is space efficient for different use cases:
>>>>    * If only some fields of an index have payloads, then there's  
>>>> no space overhead for the fields with payloads disabled.
>>>>    * If the payloads of consecutive term positions have the same  
>>>> length, then the length only has to be stored once for every  
>>>> term. This should be a common case, because users probably use  
>>>> the same format for all payloads.
>>>>    * If only a few terms of a field have payloads, then we don't  
>>>> waste much space because we benefit again from the same-length- 
>>>> compression since we only have to store the length zero for the  
>>>> empty payloads once per term.
>>>> All unit tests pass.
>>> --This message is automatically generated by JIRA.
>>> -
>>> You can reply to this email to add a comment to the issue online.
>>> -------------------------------------------------------------------- 
>>> -
>>> To unsubscribe, e-mail:
>>> For additional commands, e-mail:
>> ------------------------------------------------------
>> Grant Ingersoll
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail:
>> For additional commands, e-mail:
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

Grant Ingersoll

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message