[postgis-users] Re: Re bug with GIST indexes

[Mark Cave-Ayland]

Hi Dave,

Sorry about the late reply, it's been a busy week here! OK, back to
business....

> -----Original Message-----
> From: postgis-users-bounces at postgis.refractions.net 
> [mailto:postgis-users-bounces at postgis.refractions.net] On 
> Behalf Of David Blasby
> Sent: 17 March 2003 17:45
> To: Mark Cave-Ayland; postgis-users at postgis.refractions.net
> Subject: Re: [postgis-users] Re: Re bug with GIST indexes
> 
 > I'd love to find out more about this, its really powerfull to have 
> something like:
> 
> SELECT * FROM <table>  WHERE distance(table.geom, <geom>) < 100
> 
> automagically turned into something like this that will use the index:
> 
> SELECT * FROM <table> WHERE distance(table.geom, <geom>) < 100 AND 
> table.geom && expand_bbox(<geom>,100)

I've just been browsing through the postgres documentation and came
across the 'create rule' command. I haven't looked into this in much
detail, but I'm guessing this isn't flexible enough for PostGIS? Another
possible approach with 7.3 could be to make distance() a simple set
returning function that extracts the bounding boxes of the geometries
before executing an indexable query with the && operator. It would then
be a case of simply squirting the indexable query through SPI and
returning the results back to the user.

> >Yes, this would make sense. However, what is the support for 
> PostGIS 3D 
> >spaces like? Should the BOX3D be deprecated for BOX2D? It 
> doesn't look 
> >difficult to extend the R-Tree code into 3 dimensions if 
> people would 
> >want to use spatially indexed 3D queries.... But looks like 
> JTS doesn't 
> >do 3D :(
> >  
> >
> Yes - this is unfortunate that JTS doesnt really much is 3D 
> space.  Most 
> GIS is actually 2.5D anyways (like JTS).  To
> have full 3d support, you need to be able to define volumes 
> instead of 
> polygons (areas) - this is really advanced stuff!
> 
> For example, imagine a square in 3d, on the XY plane.  Now 
> take one of 
> the corners and move its vertex straight up.  The
> resulting shape is very difficult to describe!

I guess what I'm trying to say is would 3D indexing be useful to anyone?
It wouldn't be too difficult to change everything to think in terms of
volumes as opposed to areas from what I can see.

> >Hmmm, I see what you mean.... But this is actually the 
> beginning of a 
> >very cunning plan. How about modifying Compress() to convert 
> geometries 
> >to BOX2Ds by taking their bounding box, and modifying 
> Decompress() to 
> >convert BOX2Ds back into BBOXONLY geometries?
> >
> >This then would mean that the index entries would be stored 
> on the disk 
> >as BOX2Ds taking minimal space, while it would still be possible for 
> >the
> >Consistent() routines to call functions that take two geometries as a
> >parameter, plus it gets rid of the problem above where you would be
> >storing excess information if you were directly storing the GEOMETRY
> >type. The only thing I can see here is that every BOX2D 
> would still need
> >to have a constant SRID stored on disk which seems wrong 
> given that the
> >value will be constant for every index... Is there no way we could
> >extract this information from the geometry_columns table given the
> >information in the GiST entry structure? But I guess this would slow
> >things down a bit?
> >  
> >
> Ah - I see where you're comming from!
> An alternative would be to have all the consistent() functions take 
> BOX2Ds, and have the
> geometry implementations convert the geometry to BOX2D and call the 
> BOX2D versions.
> I say this because the its very likely that the bbox_inside() 
> functions 
> will be called much more
> often from the index than directly.  It seems like a fair 
> amout of work to:
>     1. pull BOX2D from index
>     2. ensure SRID match
>     3.  convert BOX2D -> GEOMETRY
>     4.  hand off to GEOMETRY bbox function
> 
> Instead of
>    1. pull BOX2D from index
>    2. ensure SRID match
>    3. hand-off to BOX2D function

If we must have a SRID in the index then this is probably the way to go.
But as you comment below, it is an absolute waste of space.....

> It does suck to have to put the SRID in every BOX2D when its 
> completely 
> redundant.  To bad you couldnt
> have meta-information stored at the top level of the index so 
> you could 
> verify a SRID match before the
> index search even begins to traverse.

OK, I've had one more cunning idea: let's say we keep the existing index
using BOXes without a SRID but we rewrite the indexes to use BOX2D (or
BOX3D if you want 3D spatial indexing). It looks as if it should be
possible to extract the pointer to the geometry from the GISTENTRY
structure in Decompress() implying that we could access the SRID from
the index routines. However, since R-Trees only store data in leaf
nodes, we only have to do this for leaf nodes; otherwise we can blindly
return a SRID of -1 which could help speed some things up.

Then we create a cast from geometry to BOX2D and have a single copy of
the spatial operators in PostGIS that work on the BOX2D type. This can
check the SRID and throw an error if it mismatches, plus it keeps it to
one consistent routine for one spatial operators. I have no idea how to
access the record information given a key from the GISTENTRY structure,
but I will try posting the problem to one of the pgsql lists to see if
anyone can come up with anything.

> I think its a bit risky to try to put the information in the 
> geometry_columns table.  
> I know I have a bee-in-my-bonnet about auto-rewriting queries, but:
> 
> SELECT * FROM table WHERE table.geom && <geom>
> 
> converted to:
> 
> SELECT * FROM table WHERE table.geom && <geom> and 
> assert_consistent_srid('table',<geom>)
> 
> where assert_consistent_srid() would verify that the geometry_columns 
> entry's srid is the same as the <geom> SRID.  Of course, what 
> do you do 
> if there is no entry in the geometry_columns table?

Then again, doesn't not having a geometry_columns table break a lot of
things in PostGIS anyway?


Cheers,

Mark.



---

Mark Cave-Ayland
Webbased Ltd.
Tamar Science Park
Derriford
Plymouth
PL6 8BX
England

Tel: +44 (0)1752 764445
Fax: +44 (0)1752 764446


This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender. You
should not copy it or use it for any purpose nor disclose or distribute
its contents to any other person.