BKD-based geo shapes

[jpountz]

Explanation

LatLonShape indexes shapes by decomposing them into a triangular mesh and indexing each triangle as a 7 dimension point in the BKD Tree (POINTS codec). Below is a graphic demonstrating this decomposition on several US state's political boundaries.

This provides a spatial accuracy of ~1e-6 decimal degrees. Whereas accuracy for the legacy inverted index approach (Prefix Trees) depended on the tree_levels, precision, and distance_err_pct parameters.

TODO

• LUCENE-8396 Add building blocks in Lucene to index polygons and query them for intersection via bounding boxes.
• LUCENE-8440 Add indexing support for points, lines and envelopes
• LUCENE-8396 Add indexing support for polygons
• LUCENE-8435 Add INTERSECT querying support by arbitrary shapes.
• LUCENE-8447 Add support for the DISJOINT relation (MUST_NOT clause?)
• LUCENE-8447 Add support for the WITHIN relation (doable by visiting all triangles, might belong in Elasticsearch due to bad performance)
• LUCENE-8555 Add dateline crossing support to Bounding Box queries
• LUCENE-8554 Add linestring queries
• Add support for MultiPoint Queries to new BKD geo_shape indexing approach #37318 Add support for MultiPoint queries
• Add support for distance queries on shape queries #53468 Add geo_shape buffer query support
• [Geo] Integrate Lucene's LatLonShape (BKD Backed GeoShapes) as default geo_shape indexing approach #35320 Add point shape queries
• [Geo] Integrate Lucene's LatLonShape (BKD Backed GeoShapes) as default geo_shape indexing approach #35320 Add GEOMETRYCOLLECTION queries
• Distance from [lon,lat] to geo_shape #13351, Add support for distance queries on geo_shape queries #53466 Add support for geo_distance queries (target 7.x release)
• Add support for distance queries on shape queries #53468 Add support for distance queries on shape field types
• Doc values support for geo shapes. #37206 Add doc_value and aggregation support for geo_shape (target 7.x release)
• LUCENE-8581 Change LatLonShape.Triangle encoding to use 4 BYTES per dimension instead of 8 (target 7.0.0 release)
• LUCENE-8581 Change LatLonShape.Triangle encoding to identify boundary edges (needed for CONTAINS relation) (target 7.0.0 release)
• LUCENE-8620 Add support for the CONTAINS query relation (target 7.x release)
• [Geo] Integrate Lucene's LatLonShape (BKD Backed GeoShapes) as default geo_shape indexing approach #35320 Add an option to index geo_shape fields with BKD trees in 6.x
• disallow creating geo_shape mappings with deprecated parameters #70850 Deprecate Prefix Tree indexing approach in 8.0
• Remove Prefix Tree indexing approach in 9.0
• Enable geo_shape queries on geo_point field types #48928 Add geo_shape query parity for geo_point field types

[elasticmachine]

Pinging @elastic/es-search-aggs

[jpountz]

Add indexing support for points, lines and envelopes

We were discussing geo-shapes with Nick earlier today and I realized that we had been living on different assumptions regarding this item. There are two ways that it could be achieved:

1. either by tessellating those into triangles as well, points would be a triangle that has the 3 same vertices, and lines would be a flat triangle that has twice the same vertex
2. or by indexing points, lines, envelopes and polygons in different fields and join results at search time

Both would work, I suspect 1 would be a bit more space-intensive but simpler. Query speed would likely depend on the ratio of indexed shapes that are polygons?

Add an option to index geo_shape fields with BKD trees in 6.x

@nknize suggested that we could add support for this work in a new geo field (#16749) instead of reusing the existing geo_shape field and tell users to migrate their geo_shape fields to it. It would make the transition easier for us since we want this new field to have minimal configuration, it would also help be less surprising to users as this new field makes very different trade-offs and we might not be able to support everything that geo_shape supports today (eg. CONTAINS).

Another part of that discussion was whether geo_point should be folded into that field as well. I think we shouldn't do it, at least not now, because geo points are a very common use-case and having a specialized field allows for optimizations that wouldn't be possible with a field that has to support any shapes.

@nknize What do you think?

[floggle]

Is there an ETA for CONTAINS support? The ticket gives ES 7.0 and we're already at 7.2. It's mandatory for use-case so I'm stuck using the slow old indexing.

[jpountz]

It is being worked on but there is no ETA at this point.

[iverase]

@jpountz in #77856 we moved PrefixTree builders to a module together with the Spatial4j/JTS dependency, are we ok to close this issue?

[jpountz]

+1 to close