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

[Tom Hughes]

In message <1182635383.29668.100.camel at localhost.localdomain>
          Jon Burgess <jburgess777 at googlemail.com> wrote:

> 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.

Exactly. I'm not saying it isn't possible, just that I don't think
it could be done efficiently enought to be useful.

Personally I've never seen a relational database execution plan
from any relational, be it MySQL, Postgres, Oracle, DB2 or anything
else that does what Martijn suggests.

What some will do is that if you have separate indexes on lat and
lon they will read them both then look for common records from both
to work out which records match. I doubt MySQL is that clever though.

> 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.

Unfortunately MySQL only does R-Tree indexes for MyISAM tables. At
least one of the ones we're talking about is InnoDB.

Tom

-- 
Tom Hughes (tom at compton.nu)
http://www.compton.nu/