[OSM-dev] Database Schema (was Re: [OSM-talk] Oh dear - planet has duplicate id's)

Jon Burgess jburgess777 at googlemail.com
Sat Jun 23 22:49:43 BST 2007


On Sat, 2007-06-23 at 23:14 +0200, Martijn van Oosterhout wrote:
> On 6/23/07, Tom Hughes <tom at compton.nu> wrote:
> > A BTree index can't be used to do that, at least not sensibly. How
> > would you decide which ranges of keys to read? You can't because you
> > can't enumerate the latitudes which are in the range - especially
> > when it is a floating point field.
> 
> I know it sounds lame but: postgresql can do it.

> > In general you can only do a range match like that on the final
> > component of a key - leading components need to be subject to an
> > equality match (either directly or because you are somehow able
> > to enumerate the values which fit a criteria on that component).
> 
> It's simple, At the first level of the index you find all the keys
> that are between (a,b) and then for each of those you find the second
> level key that's between (c,d). Now, I can understand if the way MySQL
> does it it won't work, but you can't claim that all B-Tree indexes are
> limited that way... Your index just needs to be done hierarchically,
> such that you can scan the keys for the first level without having
> trawl through all the other levels.
> 

There are likely to be thousands of discrete floating point values in
the range (a,b) which all need to be checked individually, this is still
pretty inefficient especially since the data is likely to be scattered
over multiple disk sectors.

PostgreSQL does do this efficiently but only by using R-Tree indexes.
MySQL supports these for spatial types too since 4.1. The MySQL spatial
support is fairly limited but should be sufficient for the simple
bounding box queries used by the map API.


> I'll see if I can get them to document it, because it's not how I read
> their documentation.
> 
> Have a nice day,





More information about the dev mailing list