id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc
20,Improved algorithm for ST_DWithin (also proposed ST_DFullyWithin ?),robe,,"

Implement better short-circuiting algorithm for ST_DWithin
ST_DWithin is currently implemented as 
  SELECT $1 && ST_Expand($2,$3) AND $2 && ST_Expand($1,$3) AND
  ST_Distance($1, $2) < $3

--This is wasteful because we don't need to calculate the full distance to
know that an object is within $3 distance of another.  We only need find
one point that is < $3 distance of the other.

--Proposed algorithm
Change to do 
  SELECT $1 &amp;&amp; ST_Expand($2,$3) AND $2 &amp;&amp; ST_Expand($1,$3) AND
  _ST_DWithin($1,$2,$3)

  Where _ST_DWithin($1,$2,$3)  would be an lwgeom function that would
  return true as soon as it
  finds a point that is < $3 distance.  

There is also some issue as to how ST_DWithin is defined as Paul Ramsey
mentioned - should it mean an object is fully within $3 distance of another
or only part of it need be.  Second proposition - create a ST_DFullyWithin

  SELECT $1 &amp;&amp; ST_Expand($2,$3) AND $2 &amp;&amp; ST_Expand($1,$3) AND
  _ST_DFullyWithin($1,$2,$3)

_ST_DFullyWithin  will be like _ST_DWithin  short-circuit and return false
as soon as you find 2
  points that are further away than $3.



",enhancement,closed,medium,,postgis,,fixed,,