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

[Nick Hill]

Nick Hill wrote:

> So I propose that if we should use a quad-tree principle, it would be on 
> the basis of coding complexity comparison, computing requirement, data 
> locality in database (areas on the hard drive roughly corresponding to 
> localities in real world) and whether the easier selection of larger 
> areas is justifiable.
> 

Developing this still further, we will want to have a scalable map which 
operates over a wide range of zooms. At close zoom levels, fie features 
are selected and shown. At lower zoom levels, large lakes and parks, A, 
B, Motorways and rail lines shown. At lower level, A, Motorway and 
intercity rail network shown. Lower level, Motorways and intercity 
lines. Lowest zooms, very large features such as huge inland lakes. All 
zooms, country outlines.

By using a quad-tree style tile to represent the 16 
most-significant-bits of objects lat and lon (32 bits), the selection of 
areas on a regional and country scale would be made simpler and less DB 
intensive.

To achieve this sort of scalability, we would need a table with 
basically 3 fields. Quadtree-style tile 32 bit (with interleaved 
lat/lon), Object zoom value (the maximum zoom level an object will 
remain visible at) and reference to object.

There is a problem where large scale views of an area will constantly be 
invalidated by small changes in the area, despite those changes not 
affecting objects visible at the current zoom level.

For example, you may view the whole London area A-road network. From one 
view to the next, the whole lot will be invalidated from tiny changes to 
minor roads, which are not visible at your zoom level.

This is where the variable bitmask and zoom level become one of the same 
thing.

If a feature with a zoom value of 0 is modified, only the smallest 
invalidation tile has it's timestamp updated and the tile location 
written to the invalidation table.

If a feature with zoom value 1 is modified or created, exactly the same 
happens for 0. After that update, the last 2 bits of the quad-tree tile 
are set to 0 and an entry is put into/timestamp updated for zoom level 1.

If a feature with zoom value 2 is modified or created, exactly the same 
happens for 0 and for 1. After those updates, the last 4 bits of the 
quad-tree tile are set to 0 and an entry is put into/timestamp updated 
for zoom level 2.

and so on.

This way, a tile is only invalidated if an object which will show at 
that zoom level is changed.

The table has a primary key based on invalidation tile and zoom level. 
Inserts to the table are set to update on duplicate so only the freshest 
time stamp for an area is kept.

I wonder if tomorrow I will understand what I have just written?