Performance issues with PostGIS ST_Intersects

Question

I have a couple of tables in PostGIS that are big (~4 million rows). The geometry columns in both the tables are indexed. But I find a huge difference in query times between ST_Within and ST_Intersects.

Here is a stripped version of the tables:

Table Trips:

• tripid
• startgeom (point)
• endgeom (point)

Table Paths:

• tripid
• geom(linestring)

These are the queries: (I have replaced the actual geometry value with a placeholder for privacy issues here)

Query 1:

explain analyse analyse select trips.tripid
from trips
where 
st_within(trips.start_geom, '<geometry value>');

Bitmap Heap Scan on trips  (cost=154.00..18002.83 rows=1476 width=33) (actual time=38.553..1998.805 rows=3872 loops=1)
 Recheck Cond: ('<geometry value>'::geometry ~ start_geom)
 Filter: _st_contains('<geometry value>'::geometry, start_geom)
 Rows Removed by Filter: 1028
 Heap Blocks: exact=4846
 ->  Bitmap Index Scan on trips_start_geom_idx  (cost=0.00..153.63 rows=4429 width=0) (actual time=37.375..37.376 rows=4900 loops=1)
       Index Cond: ('<geometry value>'::geometry ~ start_geom)
Planning time: 0.122 ms
Execution time: 2002.607 ms

Query 2:

explain analyse select paths.tripid
from paths
where st_intersects('<geometry value>', paths.geom);
st_intersects('<geometry>', paths.geom);

Bitmap Heap Scan on paths  (cost=37.99..3099.98 rows=245 width=29) (actual time=10443.387..301686.132 rows=240341 loops=1)
 Recheck Cond: ('<geometry>'::geometry && geom)
 Filter: _st_intersects('<geometry>'::geometry, geom)
 Rows Removed by Filter: 1060363
 Heap Blocks: exact=628044
 ->  Bitmap Index Scan on paths_geom_idx  (cost=0.00..37.93 rows=735 width=0) (actual time=10178.236..10178.238 rows=1300704 loops=1)
       Index Cond: ('<geometry value>'::geometry && geom)
Planning time: 0.195 ms
Execution time: 301951.620 ms

The geometry used in both the queries is a small polygon. But there is a huge difference in execution times: ~2s to ~300s. Any idea why this is?

Update: Both tables have the exact same number of rows (~4 million).

Update 2: Query times after st_subdivide.

Query 3:

select paths_subdivided.tripid
from paths_subdivided
where 
st_intersects('<geometry value>', paths_subdivided.geom);

Analysis before indexing:

Gather  (cost=1000.00..1698949.93 rows=504 width=28) (actual time=1.470..63191.646 rows=263736 loops=1)
  Workers Planned: 2
  Workers Launched: 2
  ->  Parallel Seq Scan on paths_subdivided  (cost=0.00..1697899.53 rows=210 width=28) (actual time=0.845..62986.318 rows=87912 loops=3)
        Filter: (('<geometry value>'::geometry && geom) AND _st_intersects('<geometry value>'::geometry, geom))
        Rows Removed by Filter: 1800743
Planning time: 1.519 ms
Execution time: 63393.985 ms

Analysis after indexing:

Bitmap Heap Scan on paths_subdivided  (cost=70.46..5578.92 rows=442 width=28) (actual time=624.927..311657.669 rows=263736 loops=1)
   Recheck Cond: ('<geometry value>'::geometry && geom)
   Rows Removed by Index Recheck: 1351624
   Filter: _st_intersects('<geometry value>'::geometry, geom)
   Rows Removed by Filter: 1005361
   Heap Blocks: exact=367315 lossy=332051
   ->  Bitmap Index Scan on paths_subdivided_geom_idx  (cost=0.00..70.35 rows=1325 width=0) (actual time=482.389..482.391 rows=1269097 loops=1)
         Index Cond: ('<geometry value>'::geometry && geom)
 Planning time: 0.404 ms
 Execution time: 311947.221 ms

Answer 1

The 2nd query, on the lines, shows that the bounding box intersection returned 1.3M rows, but the exact intersection then threw away 1M records and kept about 250 000.

Basically, the intersection operation is done on almost 33% of the table while at the end you only need 6%.

This indicates that either geometries are extremely large, and possibly have lots of vertex. You said the input polygon is small, so the line layer must be the problematic one.

You can try to segmentize and subdivide this line layer to end up with much smaller geometries, which will (should) make bounding box (indexed) intersection very fast.

You can see the example from the doc

SELECT ST_AsText(
         ST_Subdivide(
          ST_Segmentize('LINESTRING(0 0, 85 85)'::geography,1200000)::geometry,8));

or this article - albeit using only polygons - to get an insight of the potential performance gain

Answer 2

Do the same query on the same tables, that would be a fair comparison.

The st_intersects looks to be running against a line table, and the st_contains on points. That could be very different in execution time.