[postgis-tickets] [PostGIS] #3548: Slow queries with ST_DWithin and geography columns

[PostGIS]

#3548: Slow queries with ST_DWithin and geography columns
----------------------------------+---------------------------
 Reporter:  rdallasgray           |      Owner:  pramsey
     Type:  defect                |     Status:  new
 Priority:  medium                |  Milestone:  PostGIS 2.2.3
Component:  postgis               |    Version:  2.1.x
 Keywords:  ST_DWithin geography  |
----------------------------------+---------------------------
 We noticed that a query to find points within a given distance of a line
 was running slowly. The points have SRID 4326 and are recorded with an
 indexed geography column.

 The culprit appears to be the filter step where `_st_dwithin` is run
 against each of the records returned by the index.

 We were able to work around the issue by introducing a second ST_DWithin
 condition which runs against an indexed geometry column (again SRID 4326).
 We set the distance parameter for this in a rough conversion of metres to
 degrees, allowing a large buffer to ensure we include all candidate
 points. This narrowed the field sufficiently and the query is now ~300%
 faster.

 Interestingly, the order of the two ST_DWithin queries matters. If we run
 the geographic query first, we have poor performance. If we run the
 geometric query first, we have the better performance.

 Attached are redacted queries and explain results.

 === QUERY 1 ===

 {{{
 SELECT COUNT(*) FROM "locations"
 WHERE (ST_DWithin(
   ST_SetSRID(ST_MakeLine(
   ARRAY[
     ST_MakePoint(2.1736, 41.38518) <... redacted, approx 200 points>
 ST_MakePoint(73.31681999999995, 55.05574999999999)
   ]
 )
 , 4326)::geography,
   locations.geog,
   5000,
   false
 )
 );
 }}}

 === EXPLAIN 1 ===

 {{{
  Aggregate  (cost=2.76..2.77 rows=1 width=0) (actual
 time=6501.755..6501.757 rows=1 loops=1)
    Buffers: shared hit=15542
    ->  Index Scan using index_locations_on_geog on locations
 (cost=0.28..2.76 rows=1 width=0) (actual time=8.016..6499.419 rows=1121
 loops=1)
          Index Cond: (geog && '01<...>40'::geography)
          Filter: (('01<...>40'::geography && _st_expand(geog, 5000::double
 precision)) AND _st_dwithin('01<...>40'::geography, geog, 5000::double
 precision, false))
          Rows Removed by Filter: 19213
          Buffers: shared hit=15542
  Total runtime: 6502.081 ms
 }}}

 === QUERY 2 ===

 {{{
 SELECT COUNT(*) FROM "locations"
 WHERE (ST_DWithin(
   ST_SetSRID(ST_MakeLine(
   ARRAY[
   ST_MakePoint(2.1736, 41.38518) <... redacted, approx 200 points>
 ST_MakePoint(73.31681999999995, 55.05574999999999)
   ]
 )
 , 4326)::geography,
   locations.geog,
   5000,
   false
 )
 AND (ST_DWithin(
   ST_SetSRID(ST_MakeLine(
   ARRAY[
   ST_MakePoint(2.1736, 41.38518) <... redacted, approx 200 points>
 ST_MakePoint(73.31681999999995, 55.05574999999999)
   ]
 )
 , 4326),
   locations.geom,
   0.26
 )
 )
 );
 }}}

 === EXPLAIN 2 ===

 {{{
  Aggregate  (cost=3.02..3.02 rows=1 width=0) (actual
 time=5976.269..5976.270 rows=1 loops=1)
    Buffers: shared hit=15468
    ->  Index Scan using index_locations_on_geog on locations
 (cost=0.28..3.01 rows=1 width=0) (actual time=5.942..5973.619 rows=1121
 loops=1)
          Index Cond: (geog && '01<...>40'::geography)
          Filter: ((geom &&
 '0103000020E6100000010000000500000075029A081B9EFE3F800EF3E50590444075029A081B9EFE3F8FC151F2EA484C406DEB6E9EEA6452408FC151F2EA484C406DEB6E9EEA645240800EF3E50590444075029A081B9EFE3F800EF3E505904440'::geometry)
 AND ('01<...>40'::geography && _st_expand(geog, 5000::double precision))
 AND ('01<...>40'::geometry && st_expand(geom, 0.26::double precision)) AND
 _st_dwithin('01<...>40'::geography, geog, 5000::double precision, false)
 AND _st_dwithin('01<...>40'::geometry, geom, 0.26::double precision))
          Rows Removed by Filter: 19213
          Buffers: shared hit=15468
  Total runtime: 5976.354 ms
 }}}

 === QUERY 3 ===

 {{{
 SELECT COUNT(*) FROM "locations"
 WHERE (ST_DWithin(
   ST_SetSRID(ST_MakeLine(
   ARRAY[
     ST_MakePoint(2.1736, 41.38518) <... redacted, approx 200 points>
 ST_MakePoint(73.31681999999995, 55.05574999999999)
   ]
 )
 , 4326),
   locations.geom,
   0.26
 )
 )
 AND (ST_DWithin(
   ST_SetSRID(ST_MakeLine(
   ARRAY[
     ST_MakePoint(2.1736, 41.38518) <... redacted, approx 200 points>
 ST_MakePoint(73.31681999999995, 55.05574999999999)
   ]
 )
 , 4326)::geography,
   locations.geog,
   5000,
   false
 )
 );
 }}}

 === EXPLAIN 3 ===

 {{{
  Aggregate  (cost=3.02..3.02 rows=1 width=0) (actual
 time=1308.285..1308.287 rows=1 loops=1)
    Buffers: shared hit=15468
    ->  Index Scan using index_locations_on_geog on locations
 (cost=0.28..3.01 rows=1 width=0) (actual time=1.917..1306.076 rows=1121
 loops=1)
          Index Cond: (geog && '01...40'::geography)
          Filter: ((geom &&
 '0103000020E6100000010000000500000075029A081B9EFE3F800EF3E50590444075029A081B9EFE3F8FC151F2EA484C406DEB6E9EEA6452408FC151F2EA484C406DEB6E9EEA645240800EF3E50590444075029A081B9EFE3F800EF3E505904440'::geometry)
 AND ('01...40'::geometry && st_expand(geom, 0.26::double precision)) AND
 ('01...40'::geography && _st_expand(geog, 5000::double precision)) AND
 _st_dwithin('01...40'::geometry, geom, 0.26::double precision) AND
 _st_dwithin('01...40'::geography, geog, 5000::double precision, false))
          Rows Removed by Filter: 19213
          Buffers: shared hit=15468
  Total runtime: 1308.386 ms
 }}}

--
Ticket URL: <https://trac.osgeo.org/postgis/ticket/3548>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.