apache / apache/lucene

Ways to implement prefetching in BKD trees

Open
#15,197 4 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

I see that Lucene has added prefetching https://github.com/apache/lucene/issues/13179 in number of data structures to decouple search concurrency with IO concurrency.

In the linked issue, there is an unchecked item on prefetching support to points. I want to know if lucene is thinking of adding prefetching support to BKD trees in near future.

I was also exploring the ways to achieve this. At a high level, I was thinking that for range queries, point-lookup etc we can traverse the BKD tree in same fashion as we do. But instead of visiting leaf nodes (kdd files). We can call prefetch on matching leaf nodes file pointers. Iterator can also save the matching leaf nodes during traversal.
Once the traversal of BKD tree is complete, we can actually make a call to visit doc IDs or doc Values from the matching leaf nodes. Hopefully they may be prefetched by this time.

Opensearch uses similar variation of BKD tree traversal for range queries with an exception of early termination i.e if the matching doc id count becomes greater than equal to the size parameter requested in the query we stop the traversal.
For such use cases to support early termination, I was thinking of adding a vInt to inner nodes (kdi files) that denotes the total number of documents below that node.

Let me know if this make sense or what does community feel about this.

Contributor guide

Open the contributing guide

Research direction

Read linked issue #13179 and review the current BKD traversal described for range queries and point lookups, including the kdd and kdi files. Done would be a concrete, community-agreed approach for prefetching matching leaf nodes and handling early termination, or a documented decision not to pursue it.

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
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.