Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-21120

Improve performance of $geoWithin query for complex multi-polgyon

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Minor - P4 Minor - P4
    • None
    • Affects Version/s: None
    • Component/s: Geo
    • None
    • Query Optimization

      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.

        1. single-query.pdf
          20 kB
          Siyuan Zhou

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            siyuan.zhou@mongodb.com Siyuan Zhou
            Votes:
            1 Vote for this issue
            Watchers:
            12 Start watching this issue

              Created:
              Updated: