Uncompressed vs Subdivided: which one offers better PostGIS INTERSECTS performance?

In my PostGIS I have a point table (roughly 51 millions rows) and a multipolygon table. I need to find a polygon label/ID for every single point in my point table (roughly 51 millions rows) in PostGIS. So this is considered as point-in-polygon query (with ST_INTERSECTS).

This article suggests that using external storage for geometries significantly improves point-in-polygon queries. Here, geometries in external storage are not compressed hence the performance improvement; but there's potential extra storage size penalty (which is acceptable).

Another way to improve such query is using ST_SUBDIVIDE as explained here. This way, the polygons are divided into rectangular pieces. Point-in-polygon queries, both hit and miss, are improved.

Question:

1. Uncompressed vs Subdivided, generally which one is more preferable in terms of performance?
2. If this is rather case-specific, what are the considerations?

Yes I can implement both in a polygon (or multipolygon) table. But when I choose to use small number for max_vertices (a param in ST_SUBDIVIDE), the geometries won't be big enough to bleed to be uncompressed.

polygon complexity:

• count = 319 rows
• min = 97 vertex
• median = 3,942 vertex
• max = 217,436 vertex
• stdev = 22,921.20793 vertex
• average = 10,458.48903 vertex
• 37 out of 319 have Npoints < 512, so these won't be toasted.

So i made a test using 4 variations for the polygon table:

1. Conventional
2. Uncompressed (but not subdivided)
3. Subdivided (with max vertice= 64, the 319 explodes to 109,574 rows )
4. Subdivided (with max vertice= 512, the 319 explodes to 19,512 rows )

I tested EXPLAIN ANALYZE with a portion (±500k rows) of my point table (total 51 millions of rows) against those 4 variations. This is to get the 'Execution time'.

EXPLAIN ANALYZE
WITH poi AS (
SELECT  id, geom
FROM    point
WHERE   kpr_id = '430'
)
SELECT  p.id, b.id_polygon
FROM    poi p, polygon b
WHERE   ST_INTERSECTS(b.geom, p.geom) --both geom are indexed
IS TRUE;

Interestingly, their Execution time are:

1. Conventional: 9 minutes
2. Uncompressed (but not subdivided) : 10 minutes
3. Subdivided (with max vertice= 64) : 8.9 hours (!)
4. Subdivided (with max vertice= 512) : 1.7 hours

So it seems that using external (to get uncompressed geometry) does not improve performance. ST_Subdivide even gets worse execution time.

Below is the Explain analyze result (with polygon variation #3, subdivided):

Nested Loop  (cost=467106.10..15291893745.32 rows=18183694 width=15) (actual time=8217729.613..32306920.503 rows=526095 loops=1)
Join Filter: (((b.geom && p.geom) AND _st_intersects(b.geom, p.geom)) IS TRUE)
Rows Removed by Join Filter: 57645807435
CTE poi
->  Bitmap Heap Scan on point  (cost=5958.78..467106.10 rows=497847 width=36) (actual time=587.892..14814.902 rows=526095 loops=1)
Recheck Cond: ((kpr_id)::text = '430'::text)
Rows Removed by Index Recheck: 1942446
Heap Blocks: exact=105737 lossy=67782
->  Bitmap Index Scan on point_kpr_id_idx  (cost=0.00..5834.32 rows=497847 width=0) (actual time=547.728..547.728 rows=526095 loops=1)
Index Cond: ((kpr_id)::text = '4303130000'::text)
->  Seq Scan on polygon b  (cost=0.00..11434.74 rows=109574 width=594) (actual time=5.819..1415.867 rows=109574 loops=1)
->  CTE Scan on poi p  (cost=0.00..9956.94 rows=497847 width=36) (actual time=0.016..97.227 rows=526095 loops=109574)
Planning time: 0.415 ms
Execution time: 32306984.195 ms --this is 8,9 hours(!)

And below is all Execution time for all 4 polygon variations with each CTE and non-CTE queries. • Interesting question and thanks for bringing the EXTERNAL key word to my attention. I think this is one of the cases where the best approach will depend so much on one's use case. For point in polygon, it is easy to see how ST_Subdivide could speed things up, but for polygon/polygon intersection, it might even take longer. As for EXTERNAL, have you checked how many of your polygons are too big and need to be toasted? I often have to run queries that can take days, intersections of millions of rows vs millions of rows, and I would definitely happy use more space to save time. – John Powell May 9 at 7:55
• How complicated your polygons are? Do they have tens or tens of thousands vertices? – user30184 May 9 at 8:25
• Well, more to the point, is ST_NPoints(geom) > 512, as this is the point where TOAST comes into play. – John Powell May 9 at 8:36
• I would say that ST_Subdivide should help and because it does not seem to do it you may do some part of the analysis in sub.optimal way. Compare your workflow and results with this SpatiaLite document gaia-gis.it/spatialite-3.0.0-BETA1/WorldBorders.pdf. – user30184 May 13 at 8:42
• To be clear, you created a new column with ST_Subdivide(geom) and spatially indexed it, because your numbers make little sense. I can imagine plenty of situations where ST_Subdivide would not make much difference (as well as costing time and space in its own right), but once in place, it is hard to see how it could perform an order of magnitude worse than your "conventional" case. – John Powell May 13 at 11:35