<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 20 July 2013 12:06, Paul Norman <span dir="ltr"><<a href="mailto:penorman@mac.com" target="_blank">penorman@mac.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
From: Brett Henderson [mailto:<a href="mailto:brett@bretth.com">brett@bretth.com</a>]<br>
Subject: Re: [osmosis-dev] Improving pgsnapshot<br>
<div class="im"><br>
> > Schema details:<br>
> ><br>
> > I want to add a nodes.ways bigint[] column to the nodes table and use it for<br>
> > node->ways lookups, then use the existing ways.nodes bigint[] column for<br>
> > way->nodes<br>
><br>
> What is the motivation for this? I'm guessing that performance is likely to<br>
> increase because we get to make better use of geo-spatial indexes ... It seems<br>
> like a good idea. I haven't had a look at the existing queries to determine<br>
> the impact of making this change.<br>
<br>
</div>I'm explaining this in a good amount of detail because it helps me to write<br>
it out for planning purposes, so you get one of my long technical emails :)<br>
<br>
I'll use the example of a map? query, but ignore relations. You can<br>
generalize this to almost any task that has to use way_nodes right now<br></blockquote><div><br></div><div>Do you have the linestring column available in your ways table? If so, I don't believe you need to touch the way_nodes table for map queries.<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
The way to do this query is:<br>
<br>
1. Add all nodes in the bounding box to a nodes list (nodes_from_bbox)<br>
<br>
2. Find all parent ways of those nodes and add them to a ways list<br>
(ways_from_nodes)<br></blockquote><div><br></div><div>If you have the linestring column available, you can query the ways table directly and avoid touching the way_nodes table. There should be no need to query for the parent ways of nodes. I might be missing something in your explanation though because you mention the linestring column further down in your email.<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
3. Add to the nodes list any child nodes of those ways where the child nodes<br>
are not already in the nodes list (nodes_from_way_nodes)<br></blockquote><div><br></div><div>Are you using the ways.nodes column here, or the way_nodes table?<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
4. Serialize the nodes in the nodes list and ways in the ways list<br>
<br>
See the cgimap code for details:<br>
<a href="https://github.com/pnorman/openstreetmap-cgimap/blob/gsoc13/src/api06/map_handler.cpp#L22-36" target="_blank">https://github.com/pnorman/openstreetmap-cgimap/blob/gsoc13/src/api06/map_handler.cpp#L22-36</a><br>
<a href="https://github.com/pnorman/openstreetmap-cgimap/blob/gsoc13/src/backend/pgsnapshot/snapshot_selection.cpp#L382-477" target="_blank">https://github.com/pnorman/openstreetmap-cgimap/blob/gsoc13/src/backend/pgsnapshot/snapshot_selection.cpp#L382-477</a><br>
<br>
A couple of points that might not be immediately obvious<br>
<br>
A. Because you need the full node/way row in 4 it is best to insert the<br>
entire way/node row into the temp tables in 1-3.<br>
<br>
B. The ways selected by 2 are a subset of those meeting ST_Intersects(bbox,way.linestring).<br></blockquote><div><br></div><div>So why not just use the above query instead of using 2?<br><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Point A is what matters the most.<br>
<br>
A nodes.parent_ways column would speed up 2, and not impact 1, 3 or 4.<br>
<br>
Before going into why, the typical indexes of relevance are:<br>
<br>
On way_nodes: "idx_way_nodes_node_id" btree (node_id) [52GB]<br>
<br>
On ways: "pk_ways" PRIMARY KEY, btree (id) [4.5GB]<br>
<br>
Currently, the best query plan for a sanely sized bbox involves<br>
<br>
- a sequential scan on tmp_nodes<br>
- index scanning using idx_way_nodes_node_id<br>
- sorting the resulting list of way_ids to remove duplicates<br>
- index scanning using pk_ways<br>
<br>
By *far* the slowest part is using idx_way_nodes_node_id.<br>
<br>
With my proposed parent_ways column the best query plan should be<br>
<br>
- a sequential scan on tmp_nodes<br>
- unnest(parent_ways)<br>
- sorting the resulting list of way_ids to remove duplicates<br>
- index scanning using pk_ways<br>
<br>
My initial tests show a ~10x increase in speed, but this may scale<br>
upwards on a large database<br></blockquote><div><br></div><div>I also found ~10x increase in speed when I added the ways.nodes column, although that was mainly due to being able to use only tables clustered by geo-spatial indexes. That allowed me to avoid hitting way_nodes in my queries.<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
The second reason is for one of space reasons.<br>
<br>
way_nodes is 240GB total, with 120GB data and 120GB indexes<br>
<br>
Adding a parent_ways column would add an estimated 66GB to the nodes<br>
table, bringing it from 194GB to 260GB, for a total DB size reduction<br>
of 174GB.<br></blockquote><div><br></div><div>That sounds great.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
The sole concern of mine is that by making the nodes table wider it<br>
increases sort memory requirements and decrease sequential scan speed.<br>
This could be addressed by instead making a node_ways table with<br>
columns (node_id bigint PRIMARY KEY, parent_ways bigint[])<br>
<br>
</blockquote></div>The problem with creating a separate table is that you'll no longer be able to cluster the table according to a geo-spatial index which kills IO throughput, at least on spinning disks.<br><br></div>
<div class="gmail_extra">I'm not sure I've followed everything in your email so my comments may not be accurate. If case it's useful, the Osmosis bounding box query implementation is in the following class in the iterateBoundingBox method. Note that it only creates three temporary tables containing the node, way and relation ids that are subsequently retrieved via joins back onto the nodes, ways and relations tables to retrieve the result data. Also note that it has three way query implementations that use either way.linestring column if available, or way.bbox column if available, or fallback to way_nodes query if neither column is available.<br>
<a href="https://github.com/brettch/osmosis/blob/master/osmosis-pgsnapshot/src/main/java/org/openstreetmap/osmosis/pgsnapshot/v0_6/impl/PostgreSqlDatasetContext.java">https://github.com/brettch/osmosis/blob/master/osmosis-pgsnapshot/src/main/java/org/openstreetmap/osmosis/pgsnapshot/v0_6/impl/PostgreSqlDatasetContext.java</a><br>
<br></div><div class="gmail_extra">Brett<br><br></div></div>