[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.

[Nick Hill]

Hello Raphael

I have performed tests a few months ago, separately to Steve. My results 
correspond that current geometric indexing schemes perform very poorly 
when applied to point data types.

My tests indicate spatial indexes cause more page faults than b-tree 
indexes where they store large numbers pf point types. When compared to 
the current scheme, You don't need so much brute force searching/ cpu 
power but the reduction in CPU load is not necessarily compensated for 
by the increased I/O load from page faults. Benefits of spatial indexes 
for points theoretically melt away when we use b-tree with interleaved 
data or use partitioned databases.

The smallest data type the spatial index will use is a float bounding 
box. This requires 32 bytes per point (or possibly more as the object 
type is generally specified in the data column). This compares 
unfavourably to an int representation which gives a 1cm resolution with 
only 8 bytes.

If we have an interleaved scheme as previously mentioned, we would 
likely have all the benefits the spatial index can provide for the point 
type, with all the benefits the b-tree provides, with the reduced memory 
footprint and processing advantages integers provide.

When thinking about how we will likely want to use polygon data, and 
have polygon property inheritance, geometric indexes become necessary. 
In which case, points for segments and ways should perhaps remain 
indexed by b-trees, interleaved where suitable. Polygons stored 
separately in a geometric index database. From my current standpoint, 
such a scheme would be nirvana. Combining all the projected 
functionality we'll need in the foreseeable future with computational 
efficiency and moderate simplicity.





Raphaël Jacquot wrote:
> Nick Hill wrote:
>> I see a need for two additional dimensions to the underlying data 

> how about using this first ?
> 
> http://dev.mysql.com/doc/refman/5.1/en/creating-spatial-indexes.html
> 
> 
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
>