I have a big query that I am looking to optimize. I am matching millions (expanding daily) of rows with Points against a mostly read-only table of (tens of thousands of) areas with (Multi)Polygons. The areas table contains 3 or more layers of overlapping areas of decreasing size (think country -> county -> municipality) in addition to user-defined areas that may overlap arbitrarily. Most of these polygons are made up of <300 points, some of 5-30 thousand points.

In the query I am joining positions with areas to aggregate an array of area UUIDs SELECT positions.id, array_agg(areas.uuid) ... to back a materialized view. I would like to refresh this materialized view about every fifteen minutes, but currently the query takes a couple of minutes to finish. I have managed a 2x orders of magnitude speedup by creating a materialized view of areas with subdivided geometry, but I am worried that this too will slow down over time.

My idea to speed this up even further is as follows: Pre-compute a table of all overlapping areas with the UUID array populated, like in the image below, so that each point will only ever be contained by ONE polygon with the UUIDs already aggregated. This will probably also benefit from subdivision.

polygons split and grouped on overlap

Is this likely to result in a good speedup? How would I construct this query?

This question seems to be almost exactly what I am asking, but I lack the expertise to account for holes and MultiPolygons. Additionally I tried to correlate the resulting geometry collection with my areas to aggregate UUIDs and am not getting the results I expect:

WITH geometry AS (
    SELECT (ST_Dump(ST_Polygonize(geom))).geom AS geom FROM (
        SELECT ST_Union(geom) AS geom FROM (
            SELECT ST_ExteriorRing(geography::geometry) AS geom FROM areas
        ) AS noded_lines
    ) AS polygons

SELECT array_agg(areas.uuid) id, ST_AsText(geom)
FROM geometry
-- geom should be contained by at least one area
INNER JOIN areas ON ST_Contains(geom, areas.geography::geometry)

This query returns just 37 rows, where each of the aggregated UUID arrays only contain one entry. This is obviously incorrect for 800+ areas where I know for a fact every split polygon should be contained within at least 3 areas.

I'll go for the simple subdivision to get decent speedup for now, but I would very much like to try this optimization if it can be made to work. If only for my own sanity.

  • Does the polygons table change as well as the points table?
    – dr_jts
    Nov 25 at 17:28
  • After some consideration there will be two tables. One table of 14k complex polygons that (practically) never change, another table of ~200 somewhat simpler (and growing) user-defined polygons. Both tables change rarely enough that I can happily spend time pre-computing more efficient lookup structures.
    – Goddesen
    Nov 25 at 18:22
  • Can you avoid recomputing data for points which haven't changed? Such as cache the results for points against the complex polygon table?
    – dr_jts
    Nov 25 at 19:44
  • Yes, I am considering going in that direction. It does however make future migrations more cumbersome.
    – Goddesen
    Nov 26 at 8:16

From the doc of ST_Polygonize, you should try to use ST_Node before calling it, notably to create points where there is intersection between the lines.

Also, for query performance there is a lot to look at:

  • First, be sure to have proper indexes, to do ANALYZE on your tables, and look at EXPLAIN to be sure your request uses indexes and does what you want to do and doesn't have useless steps.
  • Secondly, you probably need to parallelize requests at some point. Some request are processed natively in parallel for most steps in the latest postgres versions, but sometime you still have some bottlenecks. Try to look at your CPU usage to see if there is something to gain here. If there is, you can launch multiple queries in parallel to treat parts of your points, preferably by geographic group (for exemple by geohash) so you will have all the points of a same zone treated at the same time and you can have slight cache performance improvments because all the polygons that you need for a point are already loaded by the previous points (not sure but can help if your ref table is above your cache size).
  • Lastly, you can tweak your db parameters to use best your server power. You can take a look at an old answer of mine if you don't know what parameter to use: ST_DWithin exponentially slow. Cannot find what I am doing wrong
  • Addressing your points: - I have ran ANALYZE after every change. EXPLAIN shows some very hot inner loops hitting the index on position.geolocation or areas.geography, depending on variations in the query. - Since this query is building a materialized I'm sure how this would work in a split fashion? The query currently uses 3 threads for 60s. - This point baffles me. I have tuned my db some, but your HW numbers are WAY higher than my current setup of 4 CPUs, 16GB RAM. Is this just the kind of power you need for efficient GIS queries? Am I underestimating the hardware needs?
    – Goddesen
    Nov 26 at 16:07
  • Furthermore, I have put everything not gathered from positions into a subselect which is joined into the positions query. As far as I can tell the only thing happening in the position lookup part is the position -> area join.
    – Goddesen
    Nov 26 at 16:12
  • The power of your db should be enough for most needs, I was just saying that it's something to look at to be sure the material is used properly (the defaults values are often really small). For better understanding, maybe you can share you request and EXPLAIN ANALYZE, maybe the problem is elsewhere. Nov 29 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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