[SERVER-21120] Improve performance of $geoWithin query for complex multi-polgyon Created: 26/Oct/15  Updated: 06/Dec/22

Status: Backlog
Project: Core Server
Component/s: Geo
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Minor - P4
Reporter: Siyuan Zhou Assignee: Backlog - Query Optimization
Resolution: Unresolved Votes: 1
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: PDF File single-query.pdf    
Issue Links:
Related
related to SERVER-20843 $geoIntersects performs poorly on pol... Backlog
related to SERVER-15455 Search inner covering first for geoWi... Backlog
Assigned Teams:
Query Optimization
Participants:
Case:

 Description   

The containment check of point in multi-polygon can be more efficient.

1. The containment check of a point will be checked with each polygon in the multi-polygon. In most use cases where polygons in the multi-polygon don't overlap, at most one polygon contains the point, so the containment check with other polygons are unnecessary.

2. Point in polygon check tests whether the cell of a point intersects the polygon for points on edges and vertices, which is expensive. We can use a small cap instead of the cell, if it's faster. Alternatively, if $geoWithin only considers the inner of a polygon excluding the edges and vertices, a simple point-in-polygon check would be sufficient. The third approach is to expand the polygon by a tiny margin/buffer somehow, which is equivalent with the first approach.

3. For the special case of points, if the cell of a point is contained by a polygon, it must be contained by the polygon (with exceptions of points on edges / vertices probably). This suggests something like "covered" query is possible for points in polygon, saving the filter in FETCH stage. Inner covering, as opposite to outer covering, of a polygon can make a tight IXSCAN possible for large portion of the polygon. This optimization can also be implemented at a higher level in matcher.

4. Investigate better ways to leverage S2EdgeIndex for containment check, as the polygon will be check against for each point. Its efficiency and the tradeoff of edge index build should be justified.


Generated at Thu Feb 08 03:56:22 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.