lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Robert Muir (JIRA)" <>
Subject [jira] [Commented] (LUCENE-7147) Improve disjoint check for geo distance query traversal
Date Tue, 29 Mar 2016 12:09:25 GMT


Robert Muir commented on LUCENE-7147:

I will rephrase it a bit.

for these spatial queries we don't want to run lots of per-document haversin checks. so its
important to categorize "rectangles" (subtrees) as "completely OUTSIDE of query range" so
that we don't have to inspect any points in them.

does not matter if its GeoPointField impl (which makes a tree out of the term dictionary)
or LatLonPoint impl (which uses BKD tree). in either cases it acts like a 2D tree and subtrees
are "rectangles".

Today, we only return "completely OUTSIDE of query range" if the incoming "rectangle" is completely
outside of circle's bounding box (!) This is very coarse: it means all the points in "BOUNDING_BOX
MINUS CIRCLE" (imagine the corner areas of the bounding box: these are large areas and not
relevant), we are slowly inspecting them one by one. Now with the patch, generally speaking
we only do the slow inspection for areas crossing the actual edge of the circle, versus a
much larger area.

> Improve disjoint check for geo distance query traversal
> -------------------------------------------------------
>                 Key: LUCENE-7147
>                 URL:
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Ryan Ernst
>         Attachments: LUCENE-7147.patch
> When doing geo distance queries, it is important to avoid traversing subtrees which do
not contain any relevant points. We currently have checks which compare the bbox of the query
to the bounds of the subtree. However, it is possible for a subtree to overlap the bbox, but
still not intersect the query. This issue is to improve that check to avoid unnecessary traversals.

This message was sent by Atlassian JIRA

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message