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