[postgis-users] PostGIS GiST index in 3D

[Mark Cave-Ayland]

> -----Original Message-----
> From: postgis-users-bounces at postgis.refractions.net [mailto:postgis-users-
> bounces at postgis.refractions.net] On Behalf Of Bernhard Reimar Hoefle
> Sent: 08 June 2006 10:11
> To: postgis-users at postgis.refractions.net
> Cc: Oleg Bartunov
> Subject: [postgis-users] PostGIS GiST index in 3D
> 
> Hi!
> I'm not a specialist in database indices, therefore the question and some
> naive
> thoughts:
> 
> I was looking at lwgeom_gist.c. It uses box1.ymin, box1.ymax, box1.xmax.
> ... and
> so on for the index search.
> 
> How much effort would it be to extend the index with the 3rd coordinate?
> That
> means 3D geometry columns would be indexed with their 3D bounding box and
> if
> index searchs are performed with 3D boxes it uses also the z coordinate to
> speed-up the query.
> 
> I know there is the possibility to search in 2D and then check the z
> coordinate
> (>,<) but I think if you work with for example many 3D points it's quite
> slow.
> 
> To avoid a large overhead with storing the z coordinate for each bounding
> box in
> each index level would it be possible to store for example z only in the
> higher
> levels and not for every feature? That would increase the speed of the
> index
> search in 3D point clouds and avoid a 50% overhead.
> 
> I hope to get some answers and more clearance on that topic.
> 
> Thanks,
> Bernhard


Hi Bernhard,

As far as I can tell, there are several tasks to accomplish to add 3D
indices in PostGIS. The greatest difficulty is likely to be optimizing index
creation so it isn't too slow, since the PickSplit() and Union() methods
will need to be extended to work in 3 dimensions and I suspect these
algorithms won't scale linearly.

I'd suggest creating a new operator class such as gist3d_geometry_ops
contained within a separate file so that users have a choice as to whether
to build a 2D or 3D index.

Other places that would need to changed is to expand the heap operators so
that they use the Z coordinate, devise a BOX3DFLOAT4 type to be stored
within the 3D index, extend lwgeom_estimate.c to handle 3 dimensional
estimates, and check all casts to ensure that 3D geoms aren't accidentally
converted to 2D geoms where they shouldn't.

In short, I can't see any reason why 3D indices couldn't be added, but given
the amount of time it would require I suspect it would require someone to
sponsor a developer to work on it.


Kind regards,

Mark.

------------------------
WebBased Ltd
17 Research Way
Plymouth
PL6 8BT

T: +44 (0)1752 797131
F: +44 (0)1752 791023

http://www.webbased.co.uk   
http://www.infomapper.com
http://www.swtc.co.uk  

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.