apache / apache/lucene

Improve RecursivePrefixTreeFilter's performance heuristic tunables [LUCENE-4418]

Open
#5,484 0 comments 0 reactions 1 assignee Claimed by @dsmiley View on GitHub
legacy-jira-priority:Minor module:spatial type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

RecursivePrefixTreeFilter recursively decomposes grid cells until it gets to a threshold grid level (e.g. 4 away from max levels), at which point it does a brute force scan because it's faster once the number of terms is smaller. So if max levels is 10, then if the threshold is 4 then it will switch to scanning at 6. Ideally, the filter would know exactly how many terms there are in that grid – i.e. given a hi & lo term, determine how many indexed terms are in-between without actually iterating to find out.

Instead, it could use the # docs that a grid cell has as a heuristic. It's not perfect but I think its much better because it's dynamic based on density of actual indexed data. It's not perfect because many documents could refer to the same indexed point, or few documents with multi-valued data could refer to many indexed points.

Before I do this, I need to re-invigorate my testing efforts so I can come up with a default threshold. And it's also dependent on things like query shape complexity.

---
Migrated from [LUCENE-4418](https://issues.apache.org/jira/browse/LUCENE-4418) by David Smiley (@dsmiley)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.