Improving the performance of STIntersects

Question

Table T_PIN has 300,000 pins and T_POLYGON has 36,000 polygons. T_PIN has this index:

CREATE SPATIAL INDEX [T_PIN_COORD] ON [dbo].[T_PIN]
(
[Coord]
)USING  GEOGRAPHY_GRID 
WITH (GRIDS =(LEVEL_1 = HIGH,LEVEL_2 = HIGH,LEVEL_3 = HIGH,LEVEL_4 = HIGH), 
CELLS_PER_OBJECT = 128, PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, 
SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, 
ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)
ON [PRIMARY];

T_POLYGON has:

CREATE SPATIAL INDEX [T_POLYGON_COORD] ON [dbo].[T_POLYGON]
(
[COORD]
)USING  GEOGRAPHY_GRID 
WITH (GRIDS =(LEVEL_1 = HIGH,LEVEL_2 = HIGH,LEVEL_3 = HIGH,LEVEL_4 = HIGH), 
CELLS_PER_OBJECT = 128, PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF,
SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, 
ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) 
ON [PRIMARY];

A query to find the intersection of T_PIN and T_POLYGON takes more than 45 minutes to execute:

SELECT COUNT(*)
FROM T_PIN 
INNER JOIN T_POLYGON
    ON T_PIN.Coord.STIntersects(T_POLYGON.COORD) = 1;

The result is 4,438,318 rows.

How can I accelerate this query?

Answer 1

Firstly, check whether a spatial index is being used by looking at the query execution plan and see if there is a Clustered Index Seek (Spatial) item.

Assuming it is being used, you could try adding a secondary/simplified filter based on a bounding box with simplified polygons to check for first. Matches against these simplified polygons could then be run through the primary filter to get the final results.

1) Add a new geography and geometry column to the [dbo].[T_POLYGON] table:

ALTER TABLE [dbo].[T_POLYGON] ADD SimplePolysGeom geometry;
ALTER TABLE [dbo].[T_POLYGON] ADD SimplePolysGeog geography;

2) Create the bounding box polygons (this involves an initial conversion to geometry to take advantage of STEnvelope()):

UPDATE [dbo].[T_POLYGON] SET SimplePolysGeom = geometry::STGeomFromWKB(
    COORD.STAsBinary(), COORD.STSrid).STEnvelope();

UPDATE [dbo].[T_POLYGON] SET SimplePolysGeog = geography::STGeomFromWKB(
    SimplePolysGeom.STAsBinary(), SimplePolysGeom.STSrid);

3) Create a spatial index on the simplified geography column

4) Get the intersections against this simplified geography column, then filter again on the matching geography data types. Roughly, something like this:

;WITH cte AS
(
   SELECT pinID, polygonID FROM T_PIN INNER JOIN T_POLYGON
    ON T_PIN.Coord.STIntersects(T_POLYGON.SimplePolysGeog ) = 1
)
SELECT COUNT(*)
FROM T_PIN 
INNER JOIN T_POLYGON
    ON T_PIN.Coord.STIntersects(T_POLYGON.COORD) = 1
    AND T_PIN.pinID IN (SELECT pinID FROM cte)
    AND T_POLYGON.polygonID IN (SELECT polygonID FROM cte)

EDIT: you can replace (1) and (2) with this computed, persisted column. credit to Paul White for the suggestion.

ALTER TABLE [dbo].[T_POLYGON] ADD SimplePolysGeog AS  ([geography]::STGeomFromWKB([geometry]::STGeomFromWKB([COORD].[STAsBinary](),[COORD].[STSrid]).STEnvelope().STAsBinary(),(4326))) PERSISTED

Answer 2

Queries like this often take a long time because of the complexity of the polygons. I've seen complex coastlines (for example) take ages to test points that are near their boundaries, having to zoom many levels to find whether a point is inside or outside.

...so you could try .Reduce()'ing the polygons, to see if that helps.

And for more about that function, look at http://msdn.microsoft.com/en-us/library/cc627410.aspx

Answer 3

According to Microsoft docs, spatial indexes will be used with geography types on the following methods when they appear at the beginning of a comparison predicate with a WHERE clause:

• STIntersects
• STDistance
• STEquals

Only geometry types' methods (restricted list) will trigger use of spatial index in JOIN ... ON, so change your code to use WHERE geog1.STIntersects(geog2) = 1 and that should improve speed.

I also recommend taking advice in g2server's answer and add the following for filtering and add spatial index on it

ALTER TABLE [dbo].[T_POLYGON] ADD SimplePolysGeog AS
     ([geography]::STGeomFromWKB([geometry]::STGeomFromWKB([COORD].[STAsBinary](),
                                                           [COORD].[STSrid])
                 .STEnvelope().STAsBinary(),(4326))) PERSISTED

you could then have a query like the following (i wrote this post quickly and have not yet tested, this is just something to try because I saw that your query and the highest posted answers use JOIN ON spatial op = 1 which will not use a spatial index):

SELECT   
     (SELECT p2.polygon_id
      FROM   T_Polygon p2
      WHERE  p2.coords.STIntersects(t.coords) = 1),
     t.pin_id
FROM     T_PIN t
WHERE    
     (SELECT t.coords.STIntersects(p.coords)
      FROM   T_POLYGON p
      WHERE  t.coords.STIntersects(p.SimplePolysGeog) = 1) = 1

FYI: The above does not work if SimplePolysGeog end up overlapping (as in a pin can be in two simplified geogs, just ran this on people in precincts in a state and since normal polys share boundary, the bounding boxes overlapped), so in most use cases, it will throw an error that subquery returned more than one result.

From MS Docs' Spatial Indexes Overview:

Geography Methods Supported by Spatial Indexes

Under certain conditions, spatial indexes support the following set-oriented geography methods: STIntersects(),STEquals(), and STDistance(). To be supported by a spatial index, these methods must be used within the WHERE clause of a query, and they must occur within a predicate of the following general form:

geography1.method_name(geography2)comparison_operatorvalid_number

To return a non-null result, geography1 and geography2 must have the same Spatial Reference Identifier (SRID). Otherwise, the method returns NULL.

Spatial indexes support the following predicate forms:

• geography1.STIntersects(geography2)= 1

• geography1.STEquals(geography2)= 1

• geography1.STDistance(geography2) < number

• geography1.STDistance(geography2) <= number

Queries that use Spatial Indexes

Spatial indexes are only supported in queries that include an indexed spatial operator in the WHERE clause. For example syntax such as:

[spatial object].SpatialMethod([reference spatial object]) [ = | < ] [const literal or variable]

The query optimizer understands the commutativity of spatial operations (that @a.STIntersects(@b) = @b.STInterestcs(@a) ). However, the spatial index will not be used if the beginning of a comparison does not contain the spatial operator (for example WHERE 1 = spatial op will not use the spatial index). To use the spatial index, rewrite the comparison (for example WHERE spatial op = 1).

...

The following query will work if SimplePolysGeogs overlap:

;WITH cte AS
(
   SELECT T_PIN.PIN_ID, 
          T_POLYGON.POLYGON_ID, 
          T_POLYGON.COORD 
   FROM T_PIN 
   INNER JOIN T_POLYGON
   ON T_PIN.COORD.STIntersects(T_POLYGON.SimplePolysGeog) = 1
)

SELECT COUNT(*)
FROM T_PIN 
INNER JOIN cte
ON T_PIN_PIN_ID = cte.PIN_ID
where cte.[COORD].STIntersects(T_PIN.COORD) = 1