lossy index

[Ed McNierney]

Crystal -

Steve's description is very good; while the GiST index is extremely helpful, it is not "deterministic" (I'm sure there's a fancy database term that's more accurate) like other indexes.  What's being indexed is NOT the geometry itself, but the bounding box of the geometry, so it's not the same as indexing the actual data like you would with a text or numeric field.

For all cases there the actual geometry of object A intersects the actual geometry of B, their bounding boxes will also intersect, so the query (A && B) will all objects that actually intersect.  It will also, however, return objects which do NOT intersect themselves, but whose bounding boxes intersect - think of two diagonal parallel line segments.  The test INTERSECTS(A, B) is a much more time-consuming operation than the VERY fast (A && B) test, so it is much faster to use (A && B) followed by INTERSECTS(A, B) in that order.  The first test will be executed first and will discard all objects whose bounding boxes do not intersect.  This is a "trivial rejection" test, quickly tossing out the objects that can't possibly intersect.  The more complex INTERSECTS(A, B) test is then performed only on the subset of objects that passes the first test, and will toss out any false positives where the bounding boxes intersect but the objects themselves do not.

     - Ed

Ed McNierney
Chief Mapmaker
Demand Media / TopoZone.com
73 Princeton Street, Suite 305
North Chelmsford, MA  01863
Phone: 978-251-4242, Fax: 978-251-1396
ed at topozone.com



-----Original Message-----
From: UMN MapServer Users List [mailto:MAPSERVER-USERS at LISTS.UMN.EDU] On Behalf Of Stephen Woodbridge
Sent: Sunday, September 09, 2007 2:36 PM
To: MAPSERVER-USERS at LISTS.UMN.EDU
Subject: Re: [UMN_MAPSERVER-USERS] lossy index

Crystal Li wrote:
> Hi All,
>  
> Would any one explain lossy indexes for me? in PostGIS Manual it talked 
> about GiST indexes are assumed to be lossy.Thanks.
>  
> Crystal

I believe that this relates to the fact the gist indexes are based on 
the bbox of the geometry, so that they loose the precise nature of the 
geometry in favor of the faster bbox representation.

So the use of gist indexes is  a && b means that a might interact with b 
and a moer precide test is needed to confirm that. So you see typical 
queries doing:

   where a && b and intersects(a,b)

HTH,
   -Steve