[postgis-users] ST_Intersection very slow

[Rémi Cura]

Hey,
I highjack this interesting discussion, sorry =)

If you have one single massive Polygon (no multi).
You can generate a point table (keeping path of course) with ST_DumpPoints.

Then you construct an index on this table.
Then you perform your Intersection with indexed points, which will be very
fast.
Then you reconstruct parts of polygon.
It will require some advanced to very advanced SQL (like windows function)
to make it work tough.

I think it would be faster than other alternatives, because basicaly it
amounts to using the optimized R-Tree index on points, vs a custom and
non-otpimized Quad tree index on polygon.
Moreover when using a recusrive strategy, you end up computing the same
think a lot with geos.

Cheers,
Rémi-C

2015-02-24 23:10 GMT+01:00 Mark Wynter <mark at dimensionaledge.com>:

>
> > Thanks Mark.  I will indeed do the st_dump, but I don't think it will
> help much (very few multis).  I think the tiling will help a lot.  What I
> wonder, though, is how long it will take to tile?  Afterall, it's still an
> st_intersection operation to tile each geometry against each tile.
>
> I’ve almost finished writing the tutorial - where I address many of these
> points.    The variables that affect performance are:
> * how you’ve written your ST_Intersection query
> * multi vs. non-multi
> * size and complexity of geoms
> * no. available CPUs (for parallelisation)
> * tile batch size - important!!!
>
> All strategies in combination may be necessary if your queries are taking
> forever.
>
> For the demonstration dataset (a multi polygon representing whole of
> Australia), my tutorial tiling query incorporates ST_Intersection and
> ST_Difference subqueries to produce tiled features representing land and
> water.
> I achieved a 49x reduction in the query time to tile the whole of
> Australia, starting with a single multi polygon.
>
> The more complex the query, the more significant this time saving is in
> absolute terms.
>
> > Is there a quad tree type tiling algorithm in a function?  If I do 256 x
> 256 tiles, doing it all at once would be 65536 operations of
> st_intersection(complex_geom, square).  With a quad tree I'll only have 4
> operations of st_intersection(complex_geom, square), and then 16 of
> (a_little_less_complex_geom, square), and then 64 of
> (even_less_complex_geom, square) and so on, for 8 nests.  The last one will
> still be 65536 operations, but the complex geoms should be a lot simpler by
> the time I get down to that level.  What do you think, is this worth
> trying?  Or is intersecting with a square fairly simple regardless of how
> complex the other geometry is?
>
> I do have a SQL quadgrid tiling function - where a cell divides
> recursively subject to a maximum number of levels or “value thresholds” -
> but I’m not sure if that’s the right approach.
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20150224/86f56263/attachment.html>