3

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
1
  • I still haven't been able to fix this. I have tried different levels of segmentation and subdivision. But there hasn't been a significant improvement in performance. Any ideas? Commented Jun 7, 2021 at 15:33

2 Answers 2

4

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

10
  • Adding up to this: ST_Within pre-filters candidates using index driven bbox containment exclusion (~), while ST_Intersects excludes by bbox intersection - depending on your spatial distribution, and with geometries other than POINT, the latter can easily be responsible for the computational check on 1M not-filtered geometries! Try running WHERE <polygon_geom> ~ <line_geom> AND ST_Intersects(<polygon_geom>, <line_geom>) for a speed (only) comparison.
    – geozelot
    Commented Mar 15, 2021 at 19:35
  • I have to add: using that operator/function combo does not make much sense, but might help understand the impact of index exclusion and the actual computational spatial relation check.
    – geozelot
    Commented Mar 15, 2021 at 19:45
  • Thanks @JGH. I created a subdivided table for paths and ran the query. There was a remarkable improvement in performance - ( Execution time: 66215.027 ms). But weirdly, I thought I would try creating an index on the geom column to see if it would be faster, but it only regressed to its earlier slow performance. Is that because of the bounding box issue you had mentioned? Also, with no index, the query analyser says that it used 2 workers and did a parallel seq scan. Would increasing the workers speed this up? Commented Mar 16, 2021 at 10:31
  • @geozelot, I tried the <polygon_geom> ~ <line_geom> query and there was a very slight improvement in execution time (Execution time: 284503.733 ms). Commented Mar 16, 2021 at 10:33
  • @sridharraman no, it should be much faster with a spatial index on the subdivided geometries! Make sure you have also run an analyze on the table after having created the index.
    – JGH
    Commented Mar 16, 2021 at 11:59
0

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.

1
  • 1
    >> Do the same query on the same tables, that would be a fair comparison. I will try that. But the problem is that I need to run queries on the table with the linestring geometries. Could there be such a big difference in performance? I will try your suggestion and get back to you. Commented Mar 15, 2021 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.