[PostGIS] #5828: Performace issue in ST_DFullyWithin

[PostGIS]

#5828: Performace issue in ST_DFullyWithin
---------------------+---------------------------
 Reporter:  nbvfgh   |      Owner:  pramsey
     Type:  defect   |     Status:  new
 Priority:  blocker  |  Milestone:  PostGIS 3.6.0
Component:  postgis  |    Version:  3.5.x
 Keywords:           |
---------------------+---------------------------
 **The premise of this issue is that ST_DFullyWithin(A, B, R) and
 ST_MaxDistance(ST_ClosestPoint(A, B), B) <= R are equivalent.**

 {{{
 EXPLAIN ANALYZE SELECT ST_Contains(ST_Buffer(a, 2), a_translate)
 FROM (SELECT ST_GeomFromText('POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))') AS a,
   ST_GeomFromText('POLYGON ((1 1, 1 2, 2 2, 2 1, 1 1))') AS a_translate);
 -- Execution Time: 0.017 ms

 EXPLAIN ANALYZE SELECT ST_MaxDistance(ST_ClosestPoint(a, a_translate),
 a_translate) <= 2
 FROM (SELECT ST_GeomFromText('POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))') AS a,
   ST_GeomFromText('POLYGON ((1 1, 1 2, 2 2, 2 1, 1 1))') AS a_translate);
 -- Execution Time: 0.005 ms
 }}}
 We found that the running time of ST_DFullyWithin is several times that of
 the equivalent query.
 To eliminate the impact of randomness, we conducted the following
 experiments：
 {{{
 DO $$
 DECLARE
     start_time TIMESTAMP;
     end_time TIMESTAMP;
     i INTEGER;
 BEGIN
     start_time := clock_timestamp();

     FOR i IN 1..10000 LOOP
         PERFORM ST_Contains(ST_Buffer(a, i), a_translate)
 FROM (SELECT ST_GeomFromText('POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))') AS a,
   ST_GeomFromText('POLYGON ((1 1, 1 2, 2 2, 2 1, 1 1))') AS a_translate);
     END LOOP;

     end_time := clock_timestamp();
     RAISE NOTICE 'Total execution time for 10000 runs: %', end_time -
 start_time;
 END $$;
 -- Total execution time for 10000 runs: 00:00:00.585733

 DO $$
 DECLARE
     start_time TIMESTAMP;
     end_time TIMESTAMP;
     i INTEGER;
 BEGIN
     start_time := clock_timestamp();

     FOR i IN 1..10000 LOOP
         PERFORM ST_MaxDistance(ST_ClosestPoint(a, a_translate),
 a_translate) <= i
 FROM (SELECT ST_GeomFromText('POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))') AS a,
   ST_GeomFromText('POLYGON ((1 1, 1 2, 2 2, 2 1, 1 1))') AS a_translate);
     END LOOP;

     end_time := clock_timestamp();
     RAISE NOTICE 'Total execution time for 10000 runs: %', end_time -
 start_time;
 END $$;
 -- Total execution time for 10000 runs: 00:00:00.016847
 }}}

 ST_MaxDistance(ST_ClosestPoint(A, B), B) <= R indeed runs more than almost
 4 times faster than ST_DFullyWithin(A, B, R) in this case.
 I know that the current implementation of ST_DFullyWithin(A, B, R) is
 ST_Contains (ST_Buffer (A, R), B), if the equivalence relationship I
 proposed holds, I believe there will be a significant improvement in the
 performance of this function.
-- 
Ticket URL: <https://trac.osgeo.org/postgis/ticket/5828>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.