WFS filter performance is slow for simple spatial queries

[posthumusb]

When using a filter in a WFS GetFeature request, spatial queries can be extremely slow when working with massive datasets. Currently every feature in a queried dataset is compared against regardless of the query type. This is understandable since it's the safest way to ensure it can handle each of the many permutations of possible query combinations.

However this is unnecessary when the filter contains only simple spatial queries (e.g. intersect with a polygon). Performance can be greatly boosted by using the bounding box of the filter expression's geometry instead of the entire map extent.

[posthumusb]

wfs filter patch to revision 12629

[posthumusb]

This patch addresses the bug using the following logic:

Use the entire map extent if:

1. any of the queries are not spatial.
2. the "not" operator is used to create an inverse spatial selection (not sure if this is even possible).
3. it's a spatial query used for selecting features outside of the query geometry (i.e. disjoint, dwithin, beyond)

Otherwise, use the query geometry's bounding box. If multiple geometries are supplied in the filter (using AND or OR operators, but not NOT), use the bounding box that contains all of these shapes.

[assefa]

Hi Brad,

Thanks for looking into this.

Quickly checking the patch (I have not tested it), would things like this also work:

filter = ((attribute_x = value_x) or (bbox_filter). In this specific case the user wants to query all the map and get all features that fit the attribute filter + all features that are in the specified bbox.

best regards

[posthumusb]

The patch only changes the bounding box for simple spatial queries. If it finds any attribute queries in the compound expression, it says "I give up" and uses the entire map extent. If it finds any spatial queries that require it to extend beyond the query bounding box (like a distance buffer), it uses the entire map extent. I can’t guarantee the patch covers 100% of these cases, but it should at least catch the vast majority of them. I tested quite a few different filters and it works as expected (so far).

Here’s one filter I tested with the patch that uses the ATTRIBUTE OR BBOX case you mentioned:

<ogc:Filter xmlns:ogc="http://www.opengis.net/ogc">
  <ogc:Or>
    <ogc:PropertyIsEqualTo>
      <ogc:PropertyName>NAME_EN</ogc:PropertyName>
      <ogc:Literal>Lake Winnipeg</ogc:Literal>
    </ogc:PropertyIsEqualTo>
    <ogc:BBOX>
      <ogc:PropertyName>msGeometry</ogc:PropertyName>
      <gml:Envelope xmlns:gml="http://www.opengis.net/gml" srsName="EPSG:26914">
        <gml:lowerCorner>353710.38766297 5435135.4030935</gml:lowerCorner>
        <gml:upperCorner>426999.93141984 5514510.3602309</gml:upperCorner>
      </gml:Envelope>
    </ogc:BBOX>
  </ogc:Or>
</ogc:Filter>

In this example, the bounding box isn’t near Lake Winnipeg, but since Lake Winnipeg is in the attribute query its features are returned along with those within the bounding box.

I can add more examples of filters I've tested if it will help.

[assefa]

Great Brad. If you have tested most of the common cases, that is good. If there are other examples, please just add them for reference purposes. I can apply the patch next week. At that time I will also do quick checks.

[posthumusb]

Testing the Intersect-Polygon-OR-Intersect-Bounding-Box filter below, it combined the bounding boxes of the polygon with the other bounding box and returned the features intersecting the polygon (and not the polygon's bounding box) and intersecting the second bounding box, as expected.

<ogc:Filter xmlns:ogc="http://www.opengis.net/ogc">
  <ogc:Or>
    <ogc:Intersect> 
      <ogc:PropertyName>Geometry</ogc:PropertyName>
        <gml:Polygon xmlns:gml="http://www.opengis.net/gml" srsName="EPSG:26914">
          <gml:outerBoundaryIs>
            <gml:LinearRing>
              <gml:coordinates>
                473800,5748600 
                464200,5727500 
                418000,5686500 
                409000,5774900 
                470600,5776200
              </gml:coordinates>
            </gml:LinearRing>
          </gml:outerBoundaryIs>
        /gml:Polygon>
      </ogc:Intersect>
      <ogc:BBOX>
      <ogc:PropertyName>msGeometry</ogc:PropertyName>
      <gml:Envelope xmlns:gml="http://www.opengis.net/gml" srsName="EPSG:26914">
        <gml:lowerCorner>618700 5565900</gml:lowerCorner>
        <gml:upperCorner>706500 5632600</gml:upperCorner>
      </gml:Envelope>
    </ogc:BBOX>
  </ogc:Or>
</ogc:Filter>