[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.
Nigel Magnay
nigel.magnay at gmail.com
Wed Sep 20 13:06:07 BST 2006
On 20/09/06, Nicola Ranaldo <ranaldo at unina.it> wrote:
>
>
> > According to the docs there : "A B-tree index on spatial values will be
> > useful for exact-value lookups, but not for range scans." - so using
> that
> > for lat/lon addressing is likely to be bad.
>
> a b-tree index, not an r-tree index!
> howewer i suggest to take a look at postgresql r-indexes and spatial
> operators, they are a lot more advanced of the same in mysql.
> Howewer the speedup is irrilevant as tile data are sparse in the db, and
> to
> recollect them you get a lot of page faults.
We have to be careful here - steve said that applying MySQL spatial indexes
to the existing lat,lon lookups didn't make it better, which isn't a
surprise. Adding them to a tile address may (or may not - I'd have thought a
B-Tree might actually be ideal, but you never know till you actually try)
speed it up.
To compact them you have to take the tile data near, in the same db pages.
> There are different solutions, howewer the simpler is to put all the tiles
> data in a single tuple, using arrays or a blob with a bitpacked format.
There's nothing to stop you having a caching implementation, that had simply
(TILE_ID, OSM_DATA_XML). Whenever a read request comes through, it's stored
also in the caching database; whenever a write occurs, delete the row from
all touched tiles.
Tiles splitting or aggretation should be done where data is more or less
> then
> specified values (db block size?). A special table could be used to mark
> dirty bouding boxes. Whit this approach tiles size are not fixed and my
> vary
> upon density of objects, and you may reach the desidered precision without
> limits. A second id->tile index should be used to retrieve data by-id.
You have to be careful. Quadtiles aren't fixed in size, but the smaller you
make them, the more often you'll have to store the fact that a line segment
or area has crossed a tile. By the time you get to 64 bits you've got about
+/- 1cm, so that's probably as far as you need go. I would guess that tiles
of about 32-bit, or 600m, would be a good starting point, stored to an item
precision of 64-bits.
You also don't need an id->tile index, because the tile ID "is" the ID -
Nodes are (by definition) in the tile because of their address.
We actually could bin both the nodes and the segments table, and have 3
tables. 1 for 'ordered nodes and ways' (aka ways, segments), 1 for tile
traversals, and 1/2 for metadata (node metadata, way metadata). This would
be really simple.
About zoom levels, this is an old question i repeated different times on the
> list, we need different things here, a good model to establish wath
> objects
> are to be drawn at each zoom level, how they should be drawn, and
> different
> db layers to collapse them. A motorway should be drawn at very different
> zoom
> levels, so when you display an entire country you can have still a lot of
> segments/nodes to display. A special layer data should collapse all
> segments
> ending in the same minumum drawing unit (you should imagine it as a
> pixel),
> in a unique object, this as needed at different zoom ranges. So when you
> display data with zoom between 0 and 2 you query a table, when you display
> data with zoom between 3 and 4 you query another table and so on. Editing
> will be permitted only on the base layer, and api should propagate updates
> to
> upper layers. Some popular PDA softwares display this in real-time, and i
> suppose they use similiar techniques.
I think that's down to deciding upon which items you want in the query - so,
instead of saying "give me all of tile xyz", you need to be able to say
"give me tile xyz, where the "ways" match the following attributes")
regards
>
> Niko
>
>
>
>
>
>
>
>
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20060920/f439cadc/attachment.html>
More information about the dev
mailing list