4

I have been reading this blog by Paul Ramsey, and considering my own data.

https://blog.crunchydata.com/blog/the-many-spatial-indexes-of-postgis

I have a regular grid covering an area of the world. Then I have some polygons covering approximately the same area, but not quite. I want to just keep the grid cells that intersect with the polygons. Currently I build a GIST index on both geom columns and then run the below query:

SELECT      grid.geom
FROM        grid
LEFT JOIN LATERAL (
     SELECT     True t
     FROM   polygons p
     WHERE  ST_intersects(p.geom, grid.geom)
     LIMIT  1
     ) p ON True
WHERE       p.t is not null

However I find that as the size and resolution of my grid increases, the time to create the index on it gets longer and longer. By the time I am making a very detailed grid, the index alone can take a few minutes to create.

Would using a BRIN or SPGIST index on either the grid or polygon data possibly help?

I'm going to do some tests myself and report back.


Following suggestion, query changed to:

SELECT      grid.geom
FROM        grid
WHERE EXISTS (
     SELECT 1
     FROM   polygons p
     WHERE  ST_intersects(p.geom, grid.geom)
     )

Output of EXPLAIN ANALYZE

"Gather  (cost=1000.28..4433766893.83 rows=9053 width=32) (actual time=2.224..31027.880 rows=2188808 loops=1)"
"  Workers Planned: 2"
"  Workers Launched: 2"
"  ->  Nested Loop Semi Join  (cost=0.29..4433764988.53 rows=3772 width=32) (actual time=0.742..30505.265 rows=729603 loops=3)"
"        ->  Parallel Seq Scan on it_gu_2020_basegrid_lvl07_pre_filter grid  (cost=0.00..202313.32 rows=3771932 width=32) (actual time=0.028..879.302 rows=3017546 loops=3)"
"        ->  Index Scan using it_gu_2020_geom_idx on it_gu_2020 p  (cost=0.29..1176.12 rows=47 width=32) (actual time=0.009..0.009 rows=0 loops=9052637)"
"              Index Cond: (geom && grid.geom)"
"              Filter: st_intersects(geom, grid.geom)"
"              Rows Removed by Filter: 0"
"Planning Time: 32.093 ms"
"Execution Time: 31125.739 ms"

I now understand that using a GIST index on my grid is pointless. The query does not use it.

Any suggestions as to a different index that would help with this work?

enter image description here

enter image description here

enter image description here

11
  • 2
    Your query won't even use the index on grid - it sequentially traverses the grid table and uses the index on your polygons table, if present! Check (and add to the Q) the EXPLAIN ANALYZE output. Also, your query is highly inefficient; you want to use an WHERE EXISTS filter instead!
    – geozelot
    Oct 25, 2021 at 14:06
  • 3
    Similar idea than in your LATERAL - but potentially much faster: ... WHERE EXISTS (SELECT 1 FROM polygons AS p WHERE ST_Intersects(p.geom, g.geom)). This expression checks for existence of rows, and skips execution once it has found one. The 1 here is a cheap placeholder to have the query produce rows without content.
    – geozelot
    Oct 25, 2021 at 14:35
  • 2
    You see that it never uses the index on your grid table, but rather sequentially runs it using 2 worker processes (Parallel Seq Scan on it_gu_2020_basegrid_lvl07_pre_filter grid), and for each row looks up the index on your polygons (Index Scan using it_gu_2020_geom_idx on it_gu_2020 p).
    – geozelot
    Oct 25, 2021 at 15:03
  • 3
    Indexes and their usage patterns are an exhaustive and complex topic worth a week of diving into - and I won't start an answer. Here, however, I may dare to add a recommendation: in the case of a regular grid (i.e. data that has no overlaps, not even the bboxes in this case) you generally want to prefer GIST - except, when a) the data is highly dynamic and b) the generated index larger than the available RAM, BRIN starts to shine (note though, that a BRIN index is only ever going to work when your data is ordered by location - which you have to take care of yourself!)
    – geozelot
    Oct 25, 2021 at 15:21
  • 3
    Needless to say, here none of the above would have any effect. Once you start using your grid to some end, an index becomes important again. Use GIST - create once, don't care (much, for a while) about it. Especially BRIN needs quite some considerations to make it worth, even if it's super fast to create and update.
    – geozelot
    Oct 25, 2021 at 15:27

1 Answer 1

2

If the polygons are somewhat similar in size to the grid cells (as shown), it's hard to say a priori what approach is best. Here's some ideas about options to try:

  • BRIN indexes are very fast to construct, but may be sub-optimal for JOINs. You can build one (on the target table) by physically sorting the table by geometry order. This can be done by making a new table using SELECT * FROM tbl ORDER BY geom
  • Since the datasets are non-overlapping, an SP_GIST index might be more efficient than a regular GIST. But have to try it and see
  • Another thing to try is to flip the query around to scan the polygon table and query the grid table using ST_Intersects. This will use the built-in prepared geometry caching in ST_Intersects - but whether this is faster will depend on the nature of the data (will work better with relatively larger polygons). And this query will produce duplicate grid cell records, so will need to be de-duplicated with a DISTINCT.

It will be interesting to hear what approach provides the best performance.

1
  • Thanks. Running some tests today. Oct 26, 2021 at 13:16

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.