apache / apache/lucene

Doc values based block join implementation [LUCENE-7304]

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

Description

At query time the block join relies on a bitset for finding the previous parent doc during advancing the doc id iterator. On large indices these bitsets can consume large amounts of jvm heap space. Also typically due the nature how these bitsets are set, the 'FixedBitSet' implementation is used.

The idea I had was to replace the bitset usage by a numeric doc values field that stores offsets. Each child doc stores how many docids it is from its parent doc and each parent stores how many docids it is apart from its first child. At query time this information can be used to perform the block join.

I think another benefit of this approach is that external tools can now easily determine if a doc is part of a block of documents and perhaps this also helps index time sorting?

---
Migrated from [LUCENE-7304](https://issues.apache.org/jira/browse/LUCENE-7304) by Martijn van Groningen (@martijnvg), updated Jun 22 2017
Attachments: [LUCENE_7304.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-7304/LUCENE_7304.patch) (versions: 2), [LUCENE-5092-20140313.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-7304/LUCENE-5092-20140313.patch), [LUCENE-7304.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-7304/LUCENE-7304.patch) (versions: 2), [LUCENE-7304-20160531.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-7304/LUCENE-7304-20160531.patch), [LUCENE-7304-20160606.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-7304/LUCENE-7304-20160606.patch)

Contributor guide

Open the contributing guide

Research direction

Start by reading the block join query-time implementation that uses a bitset to find the previous parent document, then review the linked LUCENE-7304 patches for the proposed numeric doc values approach. Verify how child and parent offsets would support block joins and preserve existing behavior; the archived patches are the only implementation references named here.

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
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.