# Sliced Time and Space

Published: 2018-06-02

### Table of content

Speedup by Lists
Grouping by key
Comparing Diffs
All versions

I am later with this blog post than I like, and I am sorry for that. While I prepared this blog post, I have found (and fixed ) two further bugs - what use have examples if the engine does not work? The bugs are now fixed and the fixes deployed.

Back to this blog post: From the last post still open is grouping by keys. This will fill the larger part of this blog post. The remaining part covers a block statement to filter diffs by custom criteria and two statements that allow to see all versions of an object in one go.

## Speedup by Lists

We have already seen in the group section of the last post how to make a statistic about the usage of the various values of a key:

```[out:csv(nodes,ways,rels,key,value)];
area[name="Grenoble"];
{
make stat value=_.val,
nodes=count(nodes),ways=count(ways),rels=count(relations);
out;
}
```

Can we also just list values of addr:street for which no street of the same name exists? A naive approach:

```[timeout:900]
[out:csv(nodes,ways,rels,value)];
area[name="Grenoble"]->.a;
{
way(area.a)[highway](if:t["name"]==_.val)->.samename;
if (samename.count(ways) == 0)
{
make stat value=_.val,
nodes=count(nodes),ways=count(ways),rels=count(relations);
out;
}
}
```

This is painfully slow. Thus we need a better solution. The first step is to understand what happens: The new lines are lines 7 and 8. In line 7 the query gets all ways within the area that have a tag highway and where the tag name is equal to the value in question. Then in line 8 we check if we have ways found or not.

The problem is the query inside the loop. We are looping about 1500 times, thus the query in line 7 is going to read the same 10 or so blocks 1500 times. Even if the delay of the disk is as low as 10 milliseconds then we already need 150 seconds for that part of the loop.

How to get rid of the request? We can do the disk activity beforehand and just do computations within the loop:

```[out:csv(nodes,ways,rels,value)];
area[name="Grenoble"]->.a;
way(area.a)[highway];
make stat name=set(t["name"])->.all;
{
if (!lrs_in(_.val, all.u(t["name"])))
{
make stat value=_.val,
nodes=count(nodes),ways=count(ways),rels=count(relations);
out;
}
}
```

This uses the new feature lrs_in in line 8. The lrs_in evaluator checks whether its first argument is contained in the list constituted by the second argument. We supply that list of interesting values by compiling the list of all street names in Grenoble in line 4. Thus, the condition in line 8 gets true exactly if the particular value of addr:street is not found in the list of street names.

A lot of the entries point to wrongly filled addr:street tags. Can we show the affected objects to fix them later on? Yes:

```area[name="Grenoble"]->.a;
way(area.a)[highway];
make stat name=set(t["name"])->.all;
{
if (!lrs_in(_.val, all.u(t["name"])))
{
out center;
}
}
```

In line 9 we simply output the group of this loop with out center. This needs OSM or JSON format, hence we need to omit the declarator line to choose CSV as output format.

## Grouping by key

Did you ever want to have your own custom Taginfo? Taginfo is a service that show you which tags are used how often and, roughly, where. Because it precomputes the data, it is the preferred tool for global statistics. However, sometimes you would like to get Taginfo-like statistics just for your city. Or a bounding box of your choice. Or a bunch of objects of your choice. This is what we want to build in this section.

The most important tool for this is that you can group by keys. We make a statistic like before, this time about which key is used how often:

```[out:csv(nodes,ways,rels,key)];
area[name="Grenoble"]->.a;
nwr(area.a);
for (keys())
{
make stat key=_.val,
nodes=count(nodes),ways=count(ways),rels=count(relations);
out;
}
```

Syntactically, this is quite similar to grouping by an arbitrary criterion as done before: The relevant evaluator is keys in line 4. Opposed to other evaluators, it is not expected that the loop sets are pairwise disjoint: If an object has multiple tags then it will appear in every loop that belongs to one of its tags.

As an exercise, the same query with a named variable i for the loop set. We ultimately want to get a handle on each value of each tag, and we need to nest loops for that purpose:

```[out:csv(nodes,ways,rels,key)];
area[name="Grenoble"]->.a;
nwr(area.a);
for->.i(keys())
{
make stat key=i.val,
nodes=i.count(nodes),ways=i.count(ways),
rels=i.count(relations);
out;
}
```

Note that the named variable i appears in quite a lot of places:

• in the for loop
• to refer to the value of this loop, i.val
• in the statistical evaluator count to ensure that we count the right set

A first attempt to nest loops:

```[out:csv(nodes,ways,rels,key,value)];
area[name="Grenoble"]->.a;
nwr(area.a);
for->.i(keys())
{
make stat key=i.val,
nodes=i.count(nodes),ways=i.count(ways),
rels=i.count(relations);
out;

for.i(t[i.val])
{
make stat key=i.val,value=_.val,
nodes=count(nodes),ways=count(ways),rels=count(relations);
out;
}
}
```

Lines 1 to 8 are the same as before. Line 10 is the nested for statement. Here, we use i as the input variable. In particular, we need in line 10 the expression i.val to choose the right key to evaulate for tag values. Lines 12 to 14 are then again the block to build statistics. Please note that we now use again count without prefix because we want to count elements in the default set _.

The approach works from a technical point of view, although the runtime is about one minute. The bigger problem is that the list is of little use due to its sheer size.

We can overcome this with an if statement at the key level. This does not split up keys if they appear less than a 100 times:

```[out:csv(nodes,ways,rels,key,value)];
area[name="Grenoble"]->.a;
nwr(area.a);
for->.i(keys())
{
if (i.count(nodes)+i.count(ways)+i.count(relations) < 100)
{
make stat key=i.val,
nodes=i.count(nodes),ways=i.count(ways),
rels=i.count(relations);
out;
}
else
{
for.i(t[i.val])
{
make stat key=i.val,value=_.val,
nodes=count(nodes),ways=count(ways),rels=count(relations);
out;
}
}
}
```

Or we can filter the values to show. Given that we have a lot of identifiers around, this reduces the number of lines far better than collating keys. Show only values that appear 100 times or more often:

```[out:csv(nodes,ways,rels,key,value,users)];
area[name="Grenoble"]->.a;
nwr(area.a);
for->.i(keys())
{
make stat key=i.val,
nodes=i.count(nodes),ways=i.count(ways),
rels=i.count(relations);
out;

for.i(t[i.val])
{
if (count(nodes)+count(ways)+count(relations) >= 100)
{
make stat key=i.val,value=_.val,
nodes=count(nodes),ways=count(ways),
relations=count(relations);
out;
}
}
}
```

Whether a tag is well-accepted can be judged by number of different users that have used the tag. For the moment being, this means the user that has last touched the object. We just list them for each tag:

```[out:csv(nodes,ways,relations,key,value,users)];
area[name="Grenoble"]->.a;
nwr(area.a);
for->.i(keys())
{
for.i(t[i.val])
{
if (count(nodes)+count(ways)+count(relations) >= 100)
{
make stat key=i.val,value=_.val,users=set(user()),
nodes=count(nodes),ways=count(ways),
relations=count(relations);
out;
}
}
}
```

The new thing here is the evaluator user in line 10. This evaluator returns for a given object the user name of the user that last touched the object. The list is made as usual with the set aggregator.

A tag that draws attention this way is genus. While I have no idea what the purpose of the tag is, it has high usage numbers with a short list of users. Let us explore what this tag is combined with. Remember, this section is all about Taginfo-like statisitcs over a custom selection:

```[out:csv(nodes,ways,relations,key,value,users)];
area[name="Grenoble"]->.a;
nwr(area.a)[genus];
for->.i(keys())
{
make stat key=i.val,users=set(user()),
nodes=i.count(nodes),ways=i.count(ways),
relations=i.count(relations);
out;

for.i(t[i.val])
{
make stat key=i.val,value=_.val,users=set(user()),
nodes=count(nodes),ways=count(ways),
relations=count(relations);
out;
}
}
```

## Comparing Diffs

The standard way to use delta queries so far is to have an ordinary query and to get the delta between the two results as result. Beyond that, people have asked for two different things:

• Get only objects that have changed in a specific manner
• Get extra data that depends on the result but should not go through the delta mechanism

Enhancing the out statement to somehow cover that sounded insane - it is more than complex enough already. Instead there is a new block statement that can be used as a simple statement as well and that satisfies most aspects of these two wishes.

Let us start with an example: we want only those objects that have changed their value of the public_transport tag:

```[adiff:"2018-04-01T00:00:00Z","2018-05-01T00:00:00Z"];
area[name="Grenoble"]->.a;
node(area.a)[public_transport];
compare(delta:t["public_transport"]);
out meta;
```

Line 1 is the usual adiff declaration to turn on delta mode between the two dates 2018-04-01 and 2018-05-01. Lines 2 and 3 constitute the standard query for nodes inside Grenoble. Deltas for ways and relations are of course possible as well, but relations are horribly slow at the moment.

The long term solution to this is to move to something more helpful than relations. There are talks (Jochen's and mine) about that on the upcoming SotM. The medium term solution is to refactor the database layout, but this is a developer year or more effort and will thus happen at earliest within a year.

Line 4 is the new statement, compare. It consists in this variant of the keyword compare and an evaluator after the keyword delta: in parentheses. This means that compare keeps only elements that have changed their value of the public_transport tag.

Other evaluators are possible as well. This includes all the other properties of the objects or combinations of them.

A particular interesting use case is existence. We use a constant expression as a quick hack for that purpose:

```[adiff:"2018-04-01T00:00:00Z","2018-05-01T00:00:00Z"];
area[name="Grenoble"]->.a;
node(area.a)[public_transport];
compare(delta:1);
out meta;
```

For a nonexisiting object, the expression will always evaluate to the empty string. For any existing object, the expression evaluates to 1. Hence, every object that has been deleted and every object that has been created will appear in the delta. This is admittedly a quick hack. This is also the rationale for the delta keyword. Once I understand what use cases are behind the request for created objects only resp. deleted objects only, I can implement compelling semantics and make that accessible under a different keyword. The problem on the table is what should happen to objects that continue to exist but have fallen out of the scope of the query. A similar problem applies to created objects.

The other desire is to get extra data along the delta mode. As an example we want to list for each changed stop the bus routes that call there. This cannot be done within the normal delta mode because that would eliminate inevitably unchanged bus routes. Compare can solve this problem as follows:

```[adiff:"2018-04-01T00:00:00Z","2018-05-01T00:00:00Z"];
area[name="Grenoble"]->.a;
node(area.a)[public_transport];
compare(delta:t["public_transport"])
{
rel(bn)[type=route];
out;
}
out meta;
```

The compare statement is followed by a block of statements. These statements are executed twice; the total execution order is as follows:

• First pass is the complete outer query for the old timestamp.
• Then the outer query is executed up the compare statement for the new timestamp.
• The delta is computed.
• The block after the compare statement is executed for the old timestamp with the old objects of the delta in the default variable.
• The block after the compare statement is executed for the new timestamp with the new objects of the delta in the default variable.
• The rest of the outer query for the new timestamp is executed.

For that reason, it is not possible to transfer any information from inside the block to the outer block. You should output it from inside the inner block.

The output from the inner block has a new pair of actions, show_initial for the first run and show_final for the second run. This avoids confusion with the existing actions, delete, modify, and create.

Of course, you could also omit the restriction to changed public transport tags:

```[adiff:"2018-04-01T00:00:00Z","2018-05-01T00:00:00Z"];
area[name="Grenoble"]->.a;
node(area.a)[public_transport];
compare
{
rel(bn);
out;
}
out meta;
```

## All versions

Another desire has been to deliver all version of a given object. This is not on the mission statement for Overpass API: First, it does not make much sense because the geometry of a way or relation can change without a new version. Second, Overpass API is designed around time slices and not object's life cycles. Nonetheless, I have implemented a pair of functions that allows at least the baseline functionality:

```timeline(way,100);
for (t["created"])
{
retro (_.val)
{
way(100);
out meta;
}
}
```

The timeline statement line 1 creates a bunch of derived objects where each object represents a perticular version. The loop in line 2 then loops over these objects. The retro statement in line 4 then sets the time slice of the request within its block to the timestamp the evaluator returns. This is one version for each version of the object.