[ https://issues.apache.org/jira/browse/LUCENE-2082?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12781027#action_12781027 ]
Michael McCandless commented on LUCENE-2082: -------------------------------------------- This sounds like a neat idea! For building up a new index (no deletions) it ought to be a sizable performance gain. I just committed changes on the flex branch to make it possible for codecs to override merging... > Performance improvement for merging posting lists > ------------------------------------------------- > > Key: LUCENE-2082 > URL: https://issues.apache.org/jira/browse/LUCENE-2082 > Project: Lucene - Java > Issue Type: Improvement > Components: Index > Reporter: Michael Busch > Priority: Minor > Fix For: 3.1 > > > A while ago I had an idea about how to improve the merge performance > for posting lists. This is currently by far the most expensive part of > segment merging due to all the VInt de-/encoding. Not sure if an idea > for improving this was already mentioned in the past? > So the basic idea is it to perform a raw copy of as much posting data > as possible. The reason why this is difficult is that we have to > remove deleted documents. But often the fraction of deleted docs in a > segment is rather low (<10%?), so it's likely that there are quite > long consecutive sections without any deletions. > To find these sections we could use the skip lists. Basically at any > point during the merge we would find the skip entry before the next > deleted doc. All entries to this point can be copied without > de-/encoding of the VInts. Then for the section that has deleted docs > we perform the "normal" way of merging to remove the deletes. Then we > check again with the skip lists if we can raw copy the next section. > To make this work there are a few different necessary changes: > 1) Currently the multilevel skiplist reader/writer can only deal with > fixed-size > skips (16 on the lowest level). It would be an easy change to allow > variable-size skips, but then the MultiLevelSkipListReader can't > return numSkippedDocs anymore, which SegmentTermDocs needs -> change 2) > 2) Store the last docID in which a term occurred in the term > dictionary. This would also be beneficial for other use cases. By > doing that the SegmentTermDocs#next(), #read() and #skipTo() know when > the end of the postinglist is reached. Currently they have to track > the df, which is why after a skip it's important to take the > numSkippedDocs into account. > 3) Change the merging algorithm according to my description above. It's > important to create a new skiplist entry at the beginning of every > block that is copied in raw mode, because its next skip entry's values > are deltas from the beginning of the block. Also the very first posting, and > that one only, needs to be decoded/encoded to make sure that the > payload length is explicitly written (i.e. must not depend on the > previous length). Also such a skip entry has to be created at the > beginning of each source segment's posting list. With change 2) we don't > have to worry about the positions of the skip entries. And having a few > extra skip entries in merged segments won't hurt much. > If a segment has no deletions at all this will avoid any > decoding/encoding of VInts (best case). I think it will also work > great for segments with a rather low amount of deletions. We should > probably then have a threshold: if the number of deletes exceeds this > threshold we should fall back to old style merging. > I haven't implemented any of this, so there might be complications I > haven't thought about. Please let me know if you can think of reasons > why this wouldn't work or if you think more changes are necessary. > I will probably not have time to work on this soon, but I wanted to > open this issue to not forget about it :). Anyone should feel free to > take this! > Btw: I think the flex-indexing branch would be a great place to try this > out as a new codec. This would also be good to figure out what APIs > are needed to make merging fully flexible as well. -- 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: java-dev-unsubscr...@lucene.apache.org For additional commands, e-mail: java-dev-h...@lucene.apache.org