apache / apache/lucene

Implement random access seeks in IndexedDISI (DocValues) [LUCENE-9051]

Open
#10,093 4 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

In #10047 we have a use case for random-access seeking in DocValues, which currently only support forward-only iteration (with efficient skipping). One idea there was to write an entirely new format to cover these cases. While looking into that, I noticed that our current DocValues addressing implementation, `IndexedDISI`, already has a pretty good basis for providing random accesses. I worked up a patch that does that; we already have the ability to jump to a block, thanks to the jump-tables added last year by @tokee; the patch uses that, and/or rewinds the iteration within current block as needed.

I did a very simple performance test, comparing forward-only iteration with random seeks, and in my test I saw no difference, but that can't be right, so I wonder if we have a more thorough performance test of DocValues somwhere that I could repurpose. Probably I'll go back and dig into the issue where we added the jump tables - I seem to recall some testing was done then.

Aside from performance testing the implementation, there is the question should we alter our API guarantees in this way. This might be controversial, I don't know the history or all the reasoning behind the way it is today. We provide `advanceExact` and some implementations support docids going backwards, others don't.  `AssertingNumericDocValues.advanceExact` does  enforce forward-iteration (in tests); what would the consequence be of relaxing that? We'd then open ourselves up to requiring all DV impls to support random access. Are there other impls to worry about though? I'm not sure. I'd appreciate y'all's input on this one.

---
Migrated from [LUCENE-9051](https://issues.apache.org/jira/browse/LUCENE-9051) by Michael Sokolov (@msokolov), updated Nov 19 2019

Contributor guide

Open the contributing guide

Research direction

Start with the IndexedDISI and DocValues entry points, then review the jump-table work referenced in the issue and the forward-iteration checks in AssertingNumericDocValues. Compare the proposed random-seek behavior with the performance testing mentioned in the issue and inspect the use case in #10047. Done requires an agreed API direction, coverage of affected DocValues implementations, and evidence from performance tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.