[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.
nick at nickhill.co.uk
Wed Sep 20 12:37:07 BST 2006
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 ?
> dev mailing list
> dev at openstreetmap.org
More information about the dev