[OSM-dev] Spatial vs. multi-column indexes for points

Florian Lohoff flo at rfc822.org
Sun Sep 14 11:25:20 BST 2008

On Fri, Sep 12, 2008 at 04:50:00PM +0200, Andreas Kalsch wrote:
> Subject: Re: [OSM-dev] Spatial vs. multi-column indexes for points

> Thanks!
> And this really outperforms a simple query like "... latitude between
> y1 and y2 and longitude between x1 and x2" ?

This would either need a combined multi-column index or be expensive
because 2 seperated indexes and a merge of the results which the
database will probably do as a full_seq_scan.

> I will use 2^24 tiles as length. It looks like "tiles_for_area" goes
> through all tiles which are in the bounding box. So if I have an area
> with e.g. 5x5 kilometers, it will loop through 2000x2000 = 4 Million
> tiles. And so the SQL for this are will be quite big, won't it?

IIRC it uses the top most 16 bit of lat and lon and shifts them together
in an int32. As lat lon bits get shifted in round-robin you have most
likely a very good distribution and a very efficient index on lat and

For the query bbox=8.3426546875,51.88222734375,8.4305453125,51.92617265625

it results in this:

	tile BETWEEN 3496212715 AND 3496212719 OR tile BETWEEN 3496212728 AND
	3496212735 OR tile BETWEEN 3496212904 AND 3496212911 OR tile BETWEEN
	3496212920 AND 3496212927 OR tile BETWEEN 3496212968 AND 3496212971 OR
	tile BETWEEN 3496213059 AND 3496213063 OR tile BETWEEN 3496213067 AND
	3496213087 OR tile BETWEEN 3496213091 AND 3496213095 OR tile BETWEEN
	3496213099 AND 3496213119 OR tile BETWEEN 3496213187 AND 3496213191 OR
	tile BETWEEN 3496213195 AND 3496213215 OR tile BETWEEN 3496213219 AND
	3496213223 OR tile BETWEEN 3496213232 AND 3496213241 OR tile BETWEEN
	3496213248 AND 3496213315 OR tile BETWEEN 3496213320 AND 3496213323 OR
	tile BETWEEN 3496213344 AND 3496213347 OR tile BETWEEN 3496213352 AND
	3496213355 OR tile BETWEEN 3496213376 AND 3496213417 OR tile BETWEEN
	3496213424 AND 3496213433 OR tile BETWEEN 3496213440 AND 3496213443 OR
	tile BETWEEN 3496213448 AND 3496213451 OR tile BETWEEN 3496213472 AND
	3496213475 OR tile IN (3496212713,3496213057,3496213065,3496213089,

Anyway - postgres/postgis is faster than mysql and i prefer postgres
anyway so i'd not have to deal with this.

Florian Lohoff                  flo at rfc822.org             +49-171-2280134
	Those who would give up a little freedom to get a little 
          security shall soon have neither - Benjamin Franklin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20080914/59814e5f/attachment.pgp>

More information about the dev mailing list