Expired Tile List

[lukasmartinelli]

Hi @olt, great talking with you at FOSS4G 😀 I thought when I already talk about implementing dirty tile detection I should just do it. This will help us a lot in OSM2VectorTiles since then we can drop a lot of code that is built around detecting changes.

Supports emitting list of dirty tiles (like osm2pgsql and minjur suport it).

By adding the -tilelisttiles.txtparameter to thediff` command one is able to specify the file where the dirty tiles are written to.

• Dirty tile calculation (cover algorithms ported over and adapted from https://github.com/mapbox/tile-cover)
  • [x] Points
  • [x] Linestrings
  • [x] Polygons with multiple inner rings
• [x] Implement new tile expireor
• [x] Extend Expireor interface since there must be a distinction how points, linestrings and polygons are expired We keep the simple Expireor API for now
• [x] Implement NullObject expireor (to omit all the nil checks)
• [x] Ensure multiple go routines can write to the TileExpireor by using a Mutex
• [x] It is fast enough

What is still missing/problematic before we can merge this?

• [x] I am reprojecting from EPSG:3857 to EPSG:4326 for the algorithms to work but it is probably smarter to adapt the code There is already a perfect proj.MercToWgs function. Thanks for that.
• [x] I haven't figured out where we need to call the expireor to correctly expire polygons (in the relations writer). Could @olt give more hints here where we need to expire as well? Polygon expiration will either use a simple BBOX API or none at all.
• [x] Support multiple zoom levels (right now we only expire the max zoom level but it is easy to also mark the parents dirty)
• [x] Support specifying max zoom level (or zoom level range?) via CLI
• [ ] Big integration test comparing the outputs to the tile calculation we do in OSM2VectorTiles

@ImreSamu We've done some work together over at OSM2VectorTiles together to ensure that tile expiration works correctly? Want to jump in on this PR as well?

[olt]

Good to see you working on it. But please discuss any changes you like to make to the existing code. We already use the Expireor interface and changing this is not really an option.

Your change also expires all tiles inside linestrings and polygons. While this is "right", I don't think it's practical. Changing just one node on a admin boundary forces you to expire a whole state/country.

[lukasmartinelli]

Thanks for the feedback.

Your change also expires all tiles inside linestrings and polygons. While this is "right", I don't think it's practical. Changing just one node on a admin boundary forces you to expire a whole state/country.

I agree. What are your ideas for tile expiration?

Marking the enclosed area as invalid is the safe choice not the one resulting in the least tiles. What about making it configurable?

For country boundaries it only needs to change if attributes of the linestring have changed or the geometry within that tile. As long as the geometry and attribute of linestring within a tile "does not change" it doesn't need to be marked dirty. Same goes for polygons and their enclosed area. If only the shape of the polygon changed and not the attributes only the tiles affected by that must be marked dirty.

Good to see you working on it. But please discuss any changes you like to make to the existing code. We already use the Expireor interface and changing this is not really an option.

In order to do smarter and correct expiring the Expireor needs more information than the nodes to expire but we can keep the interface backwards compatible. Methods in the spirit of ExpireRelation or ExpireWay would also work. Depends a lot on the choices on how to do tile expiration.

What are your suggestions for the Expireor interface?

[olt]

I agree. What are your ideas for tile expiration?

Just using the affected coordinates. This is what we are doing and it works great (but we also expire by time, so that even in the worst case interiors of huge polygon are updated anyway after a few days).

Marking the enclosed area as invalid is the safe choice not the one resulting in the least tiles. What about making it configurable?

Yes, that would be an option.

For country boundaries it only needs to change if attributes of the linestring have changed or the geometry within that tile. As long as the geometry and attribute of linestring within a tile "does not change" it doesn't need to be marked dirty. Same goes for polygons and their enclosed area. If only the shape of the polygon changed and not the attributes only the tiles affected by that must be marked dirty.

You want to compare in which tile a geometry changed? This would make the expire handling much more complex. Please postpone this for a second pull requests.

What are your suggestions for the Expireor interface?

I just looked at osm2pgsql: They expire the complete BBOX of the polygon if it is smaller then 20km in either direction. Otherwise they use only the outline. I think this is a good compromise.

So maybe just extend the interface with ExpireBox? (That would be fine with me, I just don't want to have too much logic inside the Expireor).

[lukasmartinelli]

Rewrote history and remove changes on existing code.

You want to compare in which tile a geometry changed? This would make the expire handling much more complex. Please postpone this for a second pull requests.

Good idea. Let's add a first solid version and improve incrementally. That why you are also right with the interface design of Expireor.

So maybe just extend the interface with ExpireBox? (That would be fine with me, I just don't want to have too much logic inside the Expireor).

I worked around it in https://github.com/omniscale/imposm3/pull/117/commits/6827c559eedc9aa2c2e4c9c723a7786a12b573bb and get quite far without modifying Expireor.

So now we just expire points and if someone is using ExpireNodes we treat them as linestring. If you don't like the approach or type switches like these just tell me.

func ExpireNodes(expireor Expireor, nodes []element.Node) {
    switch expireor := expireor.(type) {
    default:
        for _, nd := range nodes {
            expireor.Expire(nd.Long, nd.Lat)
        }
    case *TileExpireor:
        expireor.ExpireLinestring(nodes)
    }
}

I just looked at osm2pgsql: They expire the complete BBOX of the polygon if it is smaller then 20km in either direction. Otherwise they use only the outline.

Good idea for polygons. But perhaps we should look at polygons in a second step since this requires changes to Expireor. I like the idea of the outline for huge polygons and full cover for small ones (like building which usually only affects one tile anyway).

Tile Expiration - Status Quo

So now we expire points as expected and if you call with ExpireNodes (is that ugly?) I treat the nodes as linestring or outer ring. So linestrings are fully matched and for polygons (the relation writer passes them as closed way to ExpireNodes as well) it is just the outline.

CLI Options

Please have your say here as well. I could also add another minzoom options so you can specify the range you want to expire.

./imposm3 diff -tilelist=./tiles.txt -maxzoom=14 -mapping example-mapping.yml -connection postgis://osm:osm@localhost:32780/osm ~/Projects/geometalab/osm2vectortiles/import/latest.osc.gz

[weskamm]

Great to see a solution coming up for this, i would really like to see this merged into imposm3. Can anyone give an update if this PR is still in progress or are there other plans / solutions?

[lukasmartinelli]

Great to see a solution coming up for this, i would really like to see this merged into imposm3. Can anyone give an update if this PR is still in progress or are there other plans / solutions?

Still want to do this. Just got to swamped with other things that prevented me from continueing further on this. Should be able to complete this before the end of 2016 (since we need it for OSM2VT).

[ImreSamu]

@weskamm

... are there other ... solutions?

If it is urgent for you

• the OSM2VT(osm2vectortiles) has a some SQL post-processing scrips to create the changed tiles list - but
  • this is 'hacker level' - and not easy to use for beginners.
  • and will be change

[weskamm]

Thanks for the update, think i will wait till you finished your implementation

[stirringhalo]

@lukasmartinelli Anything I can do here to help, like further testing?

[lukasmartinelli]

@lukasmartinelli Anything I can do here to help, like further testing?

@olt Since you were looking over the code, are there any remarks where we can improve, need to do more testing?

[olt]

Priorities do not align most of the time, but I do have some time to spent on this feature right now. I created a new pull request. It reuses code which I already had and works more similar to osm2pgsql (small polygons will expire the complete BBOX of the polygon, larger polygons will expire the outline).

I will close this PR. But nonetheless, your code identified some issues in the deleter/expireor and it was a big help in understanding some edge cases. Thanks!