apache / apache/lucene

Explore other in-memory postinglist formats for realtime search [LUCENE-2346]

Open
#3,422 1 comment 0 reactions 0 assignees View on GitHub
legacy-jira-fix-version:6.0 legacy-jira-priority:Minor module:core/index type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

The current in-memory posting list format might not be optimal for searching. VInt decoding performance and the lack of skip lists would arguably be the biggest bottlenecks.

For #3388 we should investigate other formats.

Some ideas:
- PFOR or packed ints for posting slices?
- Maybe even int[] slices instead of byte slices? This would be great for search performance, but the additional memory overhead might not be acceptable.
- For realtime search it's usually desirable to evaluate the most recent documents first. So using backward pointers instead of forward pointers and having the postinglist pointer point to the most recent docID in a list is something to consider.
- Skipping: if we use fixed-length postings ([packed] ints) we can do binary search within a slice. We can also locate a pointer then without scanning and thus skip entire slices quickly. Is that sufficient or would we need more skipping layers, so that it's possible to skip directly to particular slices?

It would be awesome to find a format that doesn't slow down "normal" indexing, but is very efficient for in-memory searches. If we can't find such a fits-all format, we should have a separate indexing chain for real-time indexing.

---
Migrated from [LUCENE-2346](https://issues.apache.org/jira/browse/LUCENE-2346) by Michael Busch, updated May 09 2016
Linked issues:
- #3388

Contributor guide

Open the contributing guide

Research direction

Start by reading linked issue #3388 and locating the current in-memory posting-list implementation. Compare candidate formats against realtime search and normal indexing performance; done would require selecting and validating a format or concluding that a separate realtime indexing chain is needed.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.