Difference-based expire #2454

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