Hello,
I’m currently writing my master thesis about the the geo functionalities of Elasticsearch. I’m testing the geo querys and compare them to PostGIS. For this purpose I’m trying to understand how this querys work. I’m trying to figure it out from the source code but it’s sometimes a bit difficult. So I wrote down how I understood the algorithms for the querys and some questions that I still have. It would really help me if you take the time to read and answer my post and I think it will be informative for others too.
Geo Bounding Box Query
Uses LatLonPoint.newBoxQuery() → newBoxInternal() → PointRangeQuery()
So at search time, the BKD-tree is recursed based on whether each of left or right child overlap with the query shape, and once a leaf block is reached, all documents in that leaf block are collected if the cell is fully enclosed by the query shape.
And if the cell just intersects the box, all 1024 points will be checked against the box one by one ?
Geo Distance Query
LatLonPoint.newDistanceQuery() → LatLonPointDistanceQuery()
-
creates bounding box from distance and center point (Rectangle.fromPointDistance())
-
going down the search tree, if a subtree is outside the bounding box discard it (Relation compare())
-
if a subtree is inside the bounding box or intersects, check if it’s inside or outside the circle (GeoUtilsrelate())
-
If it crosses the circle check points in leaf if inside or outside
Geo Polygon Query
LatLonPoint.newPolygonQuery() → LaLonPointInPolygonQuery()
So here at first you calculate a bounding box from min/max lat/lon of the polygon and discard subtrees outside of the bounding box.
The other Subtrees/ cells are tested against the Query Polygon.
Therefor you use Polygon2D to create a 2d kd-tree out of the polygon:
// each component/hole is a node in an augmented 2d kd-tree: we alternate splitting between latitude/longitude,
// and pull up max values for both dimensions to each parent node (regardless of split).
And as I understand you use this kd-Tree to test the cells of the bkd-tree that are inside the bounding box if they are inside the polygon, as seen here
This algorithm really is hard for me to understand in detail.
Geohash grid Aggregation
A Geohash grid is created and every document gets checked in which bucket (Geohash) it belongs.
Geo Distance Aggregation
Here the documents get sorted into buckets based on their distance to the origin point.
Is there some kind of preselection if there is no bucket without an upper distance limit or will the distance be calculated for every document ?
Geo Distance Sorting
If sorting descending, distances from origin to every point gets calculated and then sorted.
If sorting ascending, a bounding box from the min competitive distance is build to preselect points to sort.
This is already discussed here
Geo Centroid Aggregation
Here the moving average for latitude and longitude are calculated.
Geo Bounds Aggregation
Minimum and maximum for latitude and longitude is calculated.
So if I understand this correctly, the functionalities of the bkd-Tree are only used for Geo Bounding Box Query, Geo Distance Query, Geo Polygon Query and ascending Geo Distance Sorting ?