Optimize IsWithin spatial RPT to use a point cache for false-positive removal [LUCENE-4869]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
#5709 implemented the "IsWithin" predicate for a RecursivePrefixTree based field. It's slow since it looks across the whole world to ensure it doesn't match docs with data anywhere outside the query shape. It can be configured to only look outside the query shape using a very small buffer distance, and that will filter out documents spanning the query shape boundary, but not indexed shapes comprised of multiple disjoint parts. The solution proposed here is to index a point per disjoint part in such a way that it can be easily retrieved (e.g. DocValues) and then a post-process of WithinPrefixTreeFilter would remove false-positives.
This isn't particularly hard/advanced but it requires some advances in some APIs that aren't quite there yet. Spatial4j's ShapeCollection (aka WKT GeometryCollection or Multi\*) needs to get released, it needs a vertex iterator. There needs to be code to read and write a set of points to a BinaryDocValues field (1/doc). And finally of course WithinPrefixTreeFilter needs to have a mode in which it uses the smallest buffer and then in the end checks the DocValues to remove false-postivies.
---
Migrated from [LUCENE-4869](https://issues.apache.org/jira/browse/LUCENE-4869) by David Smiley (@dsmiley), updated May 02 2013
Linked issues:
- #5709
- #5763
Contributor guide
Research direction
Start with WithinPrefixTreeFilter and the linked issues #5709 and #5763 to understand the existing IsWithin implementation. Review the proposed Spatial4j ShapeCollection vertex iterator and BinaryDocValues support for storing points per disjoint part. Done means the smallest-buffer mode removes false positives using the cached points.
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