getValue does not handle layer with key duplicates

[xabbu42]

When decoding a layer with key duplicates, getValue throws "feature referenced out of range key". A layer SHOULD NOT contain key duplicates by the spec, but tiles generated by Postgis ST_AsMVT can contain them.

The pull request #53 fixes that issue. I'll add a pull request for another possible fix.

[xabbu42]

The fix in #56 changes the number of string comparisions from "log m" to "n", where m is the number of keys in the layer and n is the number of properties of the feature. My very uninformed guess would have been that the later (i.e. with #56 applied) is actually better for most cases, that is I would have guessed m to be large and n small.

The benchmark in the repository does not call getValue at all and therefore only contains the cost of creating keysMap, but not the benefit of using it. That is by the way also the reason for the benchmark results in #17.

[flippmoke]

@xabbu42 Just to make sure we are clear this is a case where there are duplicate in the Feature "tags" field or are there duplicate keys in the Layer "keys" field? If you could provide a clear example test in your PR to show the change in behavior that would be very helpful. My primary concern here is what this might do upstream from this library. The log m performance here is often important here for Mapbox GL which might want to quickly pull up a single value for a key in a rendering cycle. Additionally, if there are repeated keys you break lots of base assumptions about vector tile data as whole. What does this mean for the rendering library that expects every key to be unique?

@Algunenano do you know if this is something you could fix in STasMVT?

[Algunenano]

@Algunenano do you know if this is something you could fix in STasMVT?

If I understand what you are referring to, this happens when we generate the MVT in parallel. We decided that we could live breaking the SHOULD NOT and we merge the parts in a quick and dirty way, that is we add duplicate the keys and values to the final tile. This is faster but means a bigger tile.
However, even though there will be duplicated key names, a single feature will only have one of those as part of its properties. Otherwise it's a bug.

This behaviour could certainly be changed and force uniqueness (I could backport it to 2.5 if really necessary), but if people rely on it I'd expect it to be MUST NOT in the spec.

[xabbu42]

@xabbu42 Just to make sure we are clear this is a case where there are duplicate in the Feature "tags" field or are there duplicate keys in the Layer "keys" field? If you could provide a clear example test in your PR to show the change in behavior that would be very helpful.

Duplicate keys in the Layer "keys" field. I never worked with protobuf before and I'd rather generate a minimal example than just adding our real world tiles. But I will try to add a proper test.

The log m performance here is often important here for Mapbox GL which might want to quickly pull up a single value for a key in a rendering cycle.

So my assumption that the number of unique keys in a layer m is normally much larger than the number of tags for a single feature n is wrong? In that case I will look into a fix keeping the log m behavior.

Given the importance for Mapbox GL of getValue performance it seems that there is also some value in benchmarking getValue and revisiting #17?

[xabbu42]

This behaviour could certainly be changed and force uniqueness (I could backport it to 2.5 if really necessary), but if people rely on it I'd expect it to be MUST NOT in the spec.

In our experience the tiles work fine with mapbox-gl-js. We tried nothing else so far.

[xabbu42]

I added an example test in the PR.

I also got some average values for m and n in the real-world tiles from https://github.com/mapbox/mvt-fixtures/blob/master/REAL-WORLD.md. The results are as follows:

bangkok
 n: 5.28604
 m: 4.36615
chicago
 n: 6.99687
 m: 5.79463
nepal
 n: 3.87625
 m: 2.04286
norway
 n: 3.27397
 m: 2.00867
osm-qa-astana
 n: 85.9375
 m: 10.2805
osm-qa-montevideo
 n: 184
 m: 12.827
sanfrancisco
 n: 6.17647
 m: 5.13653
uruguay
 n: 3.92373
 m: 2.52305

so for the osm qa tiles the PR should be faster. For the others could be slightly slower depending on the number of getValue calls (as the PR also gets rid of the cost for generating the std::map in the first place).

[Algunenano]

In our experience the tiles work fine with mapbox-gl-js. We tried nothing else so far.

Our main renderer is CartoVL which works also on top of Mapbox GL and I haven't noticed any issue either.

@flippmoke Do you know of any other decoder that could be relying on the layer keys not being duplicated? Generating tiles in parallel was something that we introduced in Postgis 2.5 so it has only been in the wild for ~4 months, but this is the first case I know of where this has been an issue.

[flippmoke]

This is not an issue in PostGIS as per the VT spec, it does seem to be an issue with this current version of the library. But, I would highly encourage not to have duplicate keys in PostGIS results because of what this will do to VT sizes. Keys are often the largest part of the entire VT.

[Algunenano]

Thanks for the confirmation. I've created an issue in Postgis and I'll see if I can improve it for 3.0.

[smounir]

Hello ! do you have any exemple of a mvt tile with duplicated keys (to be sure to understand), because I have the same error on mapbox_gl SDK (android & ios) on just one tile (provided by postgis 2.4.4 St_AsMvt...) ! The same tile is rendered finely on mapbox_gl_js.

[xabbu42]

There is an example mvt tile in my pull request: https://raw.githubusercontent.com/mapbox/vector-tile/02dda367bc62811bd4e38c20253afd454afc05b6/test/test047.mvt

[smounir]

I think I understand why I didn't find the famous "duplicated keys" ! because I'm using the "mapbox-vector-tile" python library to decode the tile, and when I do so, the decode method do already the "clean" of the duplicated keys...
So the the decode of your tile will give:
{ "hello": { "extent": 4095, "features": [ { "geometry": [ [ 25, 4078 ] ], "id": 1, "properties": { "type": "lake" }, "type": 1 } ], "version": 2 } }
Normaly the tile contents a duplicated key "type" -> park and lake (in this case type park was deleted !)

[smounir]

After many investigations, I concluded that in some cases the ST_AsMvtGeom return some tile rows with NULL geoms. So when the mapbox_gl engine try to decode that kind of tile it delete the features without geom and it failed by raising a runtime_error("feature referenced out of range key") because of keymap_count <= tag_key as specified here.
To get around this issue we added a WHERE geom IS NOT NULL at the end of ST_AsMVT function.
I think the better way to fix this issue is that the ST_AsMvtGeom function should not return a NULL geoms.

[Algunenano]

To get around this issue we added a WHERE geom IS NOT NULL at the end of ST_AsMVT function.
I think the better way to fix this issue is that the ST_AsMvtGeom function should not return a NULL geoms.

By design, ST_AsMVTGeom can return NULL geometries but those won't be included in the tile when calling ST_AsMVT. That is normal and the expected behaviour; think of a small polygon seen in zoom 0, since it's too small it will disappear thus returning NULL is appropriate.

Now, if you tell me that ST_AsMVT can return a NULL geometry I'd need the Postgis release and query to verify, since that shouldn't be the case (and AFAIK impossible with protobuf). In any case, could you share the resulting MVT so we can check if it respects the spec?

[smounir]

@Algunenano The postgis version is 2.4.4 and postgresql version is 9.5.13.
Here is a query where I forced to add a row including a NULL geometry and it broke the tile :
WITH road_network AS ( SELECT ST_AsMvtGeom( geom, TileBBox(4, 7, 6, 3857), 2048, 256, true) AS geom, provider::TEXT as provider, style::TEXT as style FROM ((SELECT provider, style, (ST_Linemerge(ST_Collect(geom))) AS geom FROM map.road_network_5 WHERE ST_Intersects(geom, TileBBox(4, 7, 6, 3857)) GROUP BY provider, style ) UNION (SELECT 0 as provider, 'motorway' as style, NULL as geom FROM map.road_network_5) ) AS road_network) SELECT ST_AsMVT( tile_road_network, 'road_network', 2048, 'geom') FROM road_network AS tile_road_network
Please find the attached tile file.
null_geom_tile.zip

[Algunenano]

The postgis version is 2.4.4 and postgresql version is 9.5.13.

That is odd. As far as I know, the only way to get duplicated keys is through parallel plans, and neither Postgresql 9.5 nor Postgis 2.4 have that for MVT. In any case, I'd recommend you to update to 2.4.6 since there have been multiple bugfixes in both 2.4.5 and 2.4.6 around the MVT functions (NEWS).

On the other hand, I've checked the tile using node-mapnik and it passes its validity check.

It's true that the tile has duplicated keys:

  keys: "provider"
  keys: "style"
  keys: "provider"
  keys: "style"
  values {
    string_value: "1"
  }
  values {
    string_value: "motorway"
  }
  values {
    string_value: "motorway_sliproad"
  }
  values {
    string_value: "motorway_tunnel"
  }
  values {
    string_value: "motorway_sliproad_tunnel"
  }

But if you decode the features (I'm doing it with node-mapnik, geometries omitted since they are pretty big), they look normal:

[
{
        "type": 2,
        "properties": {
          "provider": "1",
          "style": "motorway"
        },
},
{
        "type": 2,
        "properties": {
          "provider": "1",
          "style": "motorway_sliproad"
        }
},
{
        "type": 2,
        "properties": {
          "provider": "1",
          "style": "motorway_sliproad"
        },
},
{
        "type": 2,
        "properties": {
          "provider": "1",
          "style": "motorway_tunnel"
        },
{
        "type": 2,
        "properties": {
          "provider": "1",
          "style": "motorway_sliproad_tunnel"
        },
}
]

As you can see the NULL geometry values don't appear in the final MVT (no "0" or "road_network" string_value's).

[simonmitchell]

Hi all, sorry to re-open this again! Could these duplicate keys be the cause of this crash we're seeing as described here: https://github.com/react-native-mapbox-gl/maps/issues/913

This issue is the only reference I can find online to the error: "feature referenced out of range key"

@Algunenano

Forgive me if it's not the case, a lot of the lingo in here is beyond my knowledge of vector tiles!

Edit: We've now confirmed the mvt file does seem to have duplicate keys (See attached screenshot) we'll be talking with our data provider to see if there's anything they can do about this!

[Algunenano]

As I mentioned before, the spec allows (but discourages) duplicate keys and Postgis is using that to avoid doing extra work when generating tiles in parallel.

This library is asumming as true something that isn't mandatory in the spec, but I don't know if that's the cause of your crash.

[BradThater]

I am trying to debug a very similar issue which appears related to this. This may not be the right forum, but is there a good tool for inspecting the raw content from a .pbf to validate if duplicate keys are being sent to mapbox and by extension vector-tile?

EDIT:
For those that may need to do this, I used the vt2geojson package to debug the raw data coming from the .pbf, I was able to inspect the raw layer feature _keys to find the duplicate keys and confirm this is causing vector-tile to throw the above error.