[LUCENE-4932] DirectPostingsFormat can minimize binary searching in seek's

• Type: Improvement
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Component/s: core/codecs
• Lucene Fields: New
• Assignee: Unassigned
• Reporter: David Smiley
• Created: 13/Apr/13 17:03
• Updated: 28/Aug/22 13:44

Description

I was looking at the DirectPostingsFormat to see exactly what it's doing when you I seekExact(). It does a plain binary search every time, even if I've positioned the state well into size of the array. A comment (probably left by mikemccand) shows that he too knows this could be done smarter:

        // TODO: we should use the skip pointers; should be
        // faster than bin search; we should also hold
        // & reuse current state so seeking forwards is
        // faster

This issue represents resolving that TODO so it's isn't forgotten.

For inspiration about solving this in a smarter way, see Solr's SortedIntDocSet which avoids binary search using an approach that could be borrowed for this codec.