[Tile-serving] [openstreetmap/osm2pgsql] Way node index using shifted node ids (#1275)

[Jochen Topf]

OSM ways have a locality property that we can use to reduce the size of
the index looking up ways a node is in: they are often made up of
sequential node ids. If node N is contained in the way, then there is a
good chance that N+1, N+2, ... are contained in it as well. Thus, if we
group nearby nodes and create an index from node groups to ways, the
index will be significantly smaller. The drawback is that a lookup in
such an index returns false positives, i.e. ways that do not contain the
node of interest. So the smaller index is paid for with a performance
loss for updates.

"Grouping" the ids happens by shifting the id a few bits to the right.
How many exactly can be configured with the
OSM2PGSQL_WAY_NODE_INDEX_ID_SHIFT environment variable.

This commit sets the default shift for the node ids to 0, i.e. no shift,
so it is completely backwards compatible. Users can set a different
shift using the environment. See docs/bucket-index.md for details.

Setting the shift to something like 4 or 5 can significantly reduce the
disk space needed (saves something like 200 GB on a full planet), but
it costs some performance on updates (they are about 30% slower).

This is an improved version of
https://github.com/openstreetmap/osm2pgsql/pull/1058
You can view, comment on, or merge this pull request online at:

  https://github.com/openstreetmap/osm2pgsql/pull/1275

-- Commit Summary --

  * Way node index using shifted node ids

-- File Changes --

    A docs/bucket-index.md (81)
    M src/middle-pgsql.cpp (60)
    M src/options.cpp (37)
    M src/options.hpp (15)

-- Patch Links --

https://github.com/openstreetmap/osm2pgsql/pull/1275.patch
https://github.com/openstreetmap/osm2pgsql/pull/1275.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/openstreetmap/osm2pgsql/pull/1275
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/tile-serving/attachments/20200923/9682d0d2/attachment.htm>