Difference-based expire

[joto]

Currently expire works independently for old and new geometries. Basically we look at all geometries being deleted from a table and all geometries being inserted and calculate the tiles for all of these geometries independently. (Note that changes to objects are handled as a delete plus insert inside osm2pgsql.) This is wasteful, because a small change, say a moved node, can trigger a much larger geometry change. Large (multi)polygons (think Greenland iceshelf) can be expired requiring re-rendering even if only a single node moved.

To improve this situation we need four things:

1. We need to know where a change is coming from: If a node in a way changed or a member in a relation, we don't need to regenerate the whole object, because the change is only to the geometry itself. But if the object itself changes, important tags might have changed which will mean we have to expire the whole thing.
2. Instead of doing the expire for the delete and later for the insert, we have to remember all geometries being deleted and inserted for each OSM object and do later processing on all of them together.
3. Decide whether to do a full expiry or a diff expiry based on the configuration, where the change originated and the actual geometries involved.
4. Calculate difference between geometries if needed and then calculcate the tiles to be expired.

1. Cause for change

Currently we figure out for every node in which ways and relations it is and for each way in which relations it is and mark them for processing in stage 1b. All output processing done in stage 1a needs full expire because it is based on a change of an object itself, when done in 1b we can consider diff expire because the change i
s based on a member object. This should be reasonably easy to implement.

2. Remembering geometries

We have to remember all geometries being deleted and inserted for each OSM object. We have to do this for each geometry column of each table. I have proof-of-concept code for this part already. Because more than
one row can be inserted in a table from a single object, we possibly have to keep a list of geometries here.

3. Deciding

Several issues go into the decision:

• A: Configuration: For each expire setting in the Lua config we should explictly enable diff-expire if we want it. We don't know what further processing is done and want to be backwards compatible.
• B: Is this a geometry change only? See (1), so this depends on the processing stage. In the future we can extend this further, if we can differentiate between tag changes and geometry changes in the object itself, ie. new node being added to way vs. way nodes being the same but tags changed. (Or even further, see Handling of Dependent Objects #2406).
• C: For deleted objects and for new objects nothing special needs to be done, just expire based on the deleted or new geometries, respectively.

4. Process geometries

• If the deleted and the new geometries are the same, we probably don't need to do anything. This can happend when, for instance, a node in a way changes tags, but the location didn't change. This will lead to the node being re-rendered but not the way.
• If the geometry changes type (from polygon to linestring or so), we can't tell much about whats going on.
• For single geometries we can calculate the symmetrical difference between deleted and inserted geometry and expire that.
• For multiple geometries deleted and/or inserted we probably have to expire based on the union of all changes.

All of the above are probably handled correctly by:

• Merging all geometries based on type, ie. all (multi)points together, all (multi)linestrings together, all (multi)polygons together.
• Calculating symmetrical differences for each type and then the expire tiles from that.

Other things

• I have not yet thought about how all of this is affected by or affects two-stage processing.
• See also Handling of Dependent Objects #2406
• See also Non moving node updates should not update related way/relation geometries #1046

[pnorman]

I'm thinking about this from the perspective of water, where you have a geometry for the area and another for a label point if named. A member node movement might result in no changes for the point and only a change in part of the polygon.

Should we look at columns? If a member node change can avoid expiring because the geometry and tags are the same that means a tag change that doesn't result in any DB column changes is also safe to not expire by the same logic.

I'm also not sure how this affects two-stage processing. In the water example you'd never use two-stage processing. I've mainly used two-stage for forming border linestrings. In a raster tile scenario those would never be safe to do a difference-based expire since the distance along the linestring matters so a change at the start can change the entire line rendering. In a vector tile scenario it would be safe.

[joto]

I'm thinking about this from the perspective of water, where you have a geometry for the area and another for a label point if named. A member node movement might result in no changes for the point and only a change in part of the polygon.

If you have several geometry columns they must be handled separately. So we do the expire calculations based on the geometries for each geometry column by itself. (But the expire configuration is per table, not per column, so this has to be kept in mind. Now that I am thinking about this, this might have been the wrong thing to do, we probably should have tied the expire configuration to the column.)

Should we look at columns? If a member node change can avoid expiring because the geometry and tags are the same that means a tag change that doesn't result in any DB column changes is also safe to not expire by the same logic.

That's a larger subject which I want to keep out of this issue to keep the next step manageable. Currently we only get the geometry from the old, soon to be deleted, row from the database and use that for expire. We could also get the rest of the data and do clever processing deciding whether we actually need to delete that row and then insert the same row again, but that's more complicated and needs some separate discussion, see issue #2406.

I'm also not sure how this affects two-stage processing....

You can always decide to have diff-expire or not based on your use case. I am seeing diff-expire as an optimization that's "off" by default. If you are sure that diff-expire is fine with your use-case and you are seeing performance problems, then you can enable it, otherwise just ignore it. So we are pushing this decision to the user/writer of the Lua-config.

We do have to think about what diff-expire actually does in two-stage processing so that we can document it and, possibly, avoid situations where it doesn't work as the users expects. I see at least one problem: In normal processing diff-expire should only trigger on changes in child-objects of the object in question, so a change in a node will trigger processing of the way and if the way itself did not change we can do diff-expire for the way, because we are sure only the geometry changed and not the tags. But for two-stage processing the second stage processes the ways (based on changes in relations), so we don't know whether tags changed (or tags where handed down from the relations) and we have to do full expire. So I think we have to completely disable diff-expire for two-stage processing. We can only do that better if we also look at the tags etc., see above.