[OSM-dev] Lite OSM backend

[Nicola Ranaldo]

> If the page isn't in memory, it will take around 7 milliseconds to
> fetch. If the node table is pre-sorted on the first 16 bits of integer
> lat/lon prior to processing, the nodes for a 655m x 655m area (at the
> equator, smaller near the poles) will be in the same page. You'll have a
> 7ms page fault on the node table every 655 meters.

Yes, i did some experimentation with r-tree index and postgres as it has a 
very nice set of geometric operators. The main problem is not in seeking the 
index but in retrieving data as they ar not ordered in the db pages. It's 
sufficient a big map query to invalidate the cache of the entire db resulting 
in a huge disk access for subsequent query. So, as you suggest in your 
excellent analisys, the backend has to be "clustered" on spatial information. 
I do not know if actual free SQL implementation permits this (for a server 
side reengineering), howewer this could be emulated using a very simple 
database schema with two columns, the first with spatial information 
(indexed), and the second with a a variable field storing all the geometric 
objects and their tags with a compact encoding. On clients and embedded 
devices not using a full featured sql server the sorted binary file is a very 
good idea.

> There is a balance between size of tile and size of index. If you index
> on the first 16 bits of both lat and lon, you will have 655x655m tiles.
> But an index to point to all these tiles could be very large.

Wath's about using a variable size tile? we can merge adiacents tiles when 
contains small data in a bigger tile, and split them when it grows over a 
limit (the page size?).

	Niko