Prepared geometry support for ST_DWithin

[robe]

In some cases, despite what we tell people, doing an

ST_Intersects(geom1, ST_Buffer(geom2,radius)) 

is sometimes faster than ST_DWithin(geom1,geom2, radius)

Granted ST_DWithin is more accurate.

I'll come up with a small self-standing example to demonstrate the point. The one I have currently is kind of hefty.

But basic assumption is if you have a fairly large constant geometry then ST_Intersects(ST_Buffer..) often out performs ST_DWithin. I assume this is because ST_Intersects takes advantage of prepared geometries and ST_DWithin does not.

[pramsey]

This is my distance rect-tree improvement, which is still sitting half-done, taunting me… it scares me too, since distance is only 95% of what people do all the time. Mucking with it is scary.

[robe]

I take it this ain't going to happen anytime soon. Okay for me to push?

[pramsey]

In 16393:

Edge tree index on geometries makes distance calculations on large geometries
go much faster. Needs to be used selectively and potentially with a caching
component for maximum effect. Test it out using _ST_DistanceRectTree(geom, geom)
for now.
References #2614

[pramsey]

In 16410:

Add cache support for rect_node trees and expose for testing
in _ST_DistanceRectTreeCached(geom, geom).
References #2614

[robe]

Milestone renamed

[strk]

For the record: GEOS-3.10 (2021-10-20) added GEOSDistanceWithin and GEOSPreparedDistanceWithin and I know they are both much faster than the current lwgeom_mindist2d_tolerance implementation ( see ​https://trac.osgeo.org/postgis/ticket/3587#comment:45 )

[strk]

Still for the record: GEOSDistanceWithin is also faster when I force the use of the so called "fast" distance calculation in PostGIS, for the case of a large ring compared against a ring inside of it.

[pramsey]

Note you cannot test one gnarly case and call all things faster. At a minimum, point/point distance will be worse, because of the marshalling cost for GEOS. Also true no doubt of all kinds of small feature→small feature cases. Great care is required to muck with the distance functions because they drive so many of the use cases.