Problem with geo functions

[sde-melo]

What version of Dgraph are you using?

1.1.0 and 1.0.17

Have you tried reproducing the issue with the latest release?

Yes

What is the hardware spec (RAM, OS)?

Docker image run on an Ubuntu VM on Windows

Steps to reproduce the issue (command/config used to run Dgraph).

I encounter a problem with geo functions. My queries return some results which they should not.

Here are my test set:

{
  set {
    _:a <name> "A" .
    _:a <loc> "{'type': 'Polygon', 'coordinates': [[[ 2.57080078125, 51.04139389812637 ], [ -4.89990234375, 48.45835188280866 ], [ -1.9335937499999998, 43.34116005412307 ], [ 3.3837890625, 42.261049162113856 ], [ 7.536621093749999, 43.8186748554532 ], [ 8.173828125, 49.009050809382046 ], [ 2.57080078125, 51.04139389812637 ]]]}"^^<geo:geojson> .
    
    _:b <name> "B" .
    _:b <loc> "{'type': 'Polygon', 'coordinates': [[[ 138.25195312499997, -10.40137755454354 ], [ 111.533203125, -24.926294766395582 ], [ 116.3671875, -35.532226227703376 ], [ 149.501953125, -38.13455657705412 ], [ 154.072265625, -26.588527147308614 ], [ 138.25195312499997, -10.40137755454354 ]]] }"^^<geo:geojson> .
    
    _:c <name> "C" .
    _:c <loc> "{'type': 'Polygon', 'coordinates': [[[105.701,-10.511],[105.683,-10.474],[105.645,-10.466],[105.629,-10.437],[105.655,-10.415],[105.715,-10.384],[105.737,-10.384],[105.751,-10.394],[105.752,-10.484],[105.736,-10.505],[105.701,-10.511],[105.701,-10.511]]]}"^^<geo:geojson> .
  }
}

and my query:

{
  node(func: contains(loc, [2.5, 46.0])) {
    uid
    name
    loc
  }
}

Expected behaviour and actual result.

I have tried in Dgraph 1.0.17 and 1.1.0 for the same results: this query returns polygons A and C instead of polygon A only as I am expecting.

[danielmai]

This is also reproducible on master (2827adf). Somehow the index is being generated where the s2 cell matches both these polygons.

So we're on the same page about what the query means, here's a geographical map of the data:

So, the query point is in France, which Polygon A definitely contains. It's not contained in Polygon B from Mainland Australia, nor contained in Polygon C on Christmas Island. It's definitely curious why the query returns back A and C.

I resorted to Jaeger and the dgraph debug tool to see what's happening.

I looked at the query trace in Jaeger. This shows which s2 cell tokens are used for the search criteria when the query processes contains(loc, [2.5, 46.0]):

Here's the part that shows the tokens:

"Number of uids: 12. args.srcFn: &{tokens:[c/47fc c/47f9 c/47f9c c/47f9f c/47f9e4 c/47f9e3 c/47f9e34 c/47f9e31 c/47f9e304 c/47f9e305 c/47f9e3054 c/47f9e3055] geoQuery:0xc02dd85050 intersectDest:false ineqValue:{Tid:0 Value:<nil>} eqTokens:[] ineqValueToken: n:12 threshold:0 uidPresent:0 fname:contains fnType:4 regex:<nil> isFuncAtRoot:false isStringFn:false atype:6}"

The trace shows these tokens were used for the query: tokens:[c/47fc c/47f9 c/47f9c c/47f9f c/47f9e4 c/47f9e3 c/47f9e34 c/47f9e31 c/47f9e304 c/47f9e305 c/47f9e3054 c/47f9e3055].

Then I used dgraph debug to inspect the index for each of the tokens. In this case, c/47fc is the only match.

$ dgraph debug -p=./p 2>/dev/null | grep c/47fc
{i} {v.ok} attr: loc term: [5] c/47fc  key: 0000036c6f63020005632f34376663 item: [45, b0100] ts: 10
$ dgraph debug -p=./p --lookup 0000036c6f63020005632f34376663 2>/dev/null
[Decoder]: Using assembly version of decoder
Opening DB: ./p
Min commit: 1. Max commit: 10, w.r.t 18446744073709551615
 Key: 0000036c6f63020005632f34383063 Length: 2 Is multi-part list? false Uid: 2 Op: 1
 Uid: 3 Op: 1

This shows that Uid: 2 (polygon "C") and Uid: 3 (polygon "A") are the nodes matched for the cover cell 47fc, which looks to be part of France only.

At first glance, it looks like this entry is wrong. I'm not familiar enough with the geo indexing to know if there are further processing steps that happen after fetching this index entry with uids 0x2, 0x3.

[sde-melo]

Thanks @danielmai!
If that helps, I first tried after importing all countries (from this shapefile: https://hub.arcgis.com/datasets/UIA::uia-world-countries-boundaries), and the same query returned 114 results!

[sde-melo]

Hi, sorry I have just noticed that in polygon C the last point appears twice. There is no problem if I removed one.

[sde-melo]

Ok, the other problems were related to multipolygons being processed as simple polygons (I am importing from a shapefile). I don't know if you want to support these weird cases.

[danielmai]

I see, nice catch. It'll be helpful to run a geojson validator over your data to make sure it's formatted correctly.

In terms of indexing, Dgraph currently supports Point, Polygon and MultiPolygon types. So, if you're ok with polygons, then that should work. Dgraph can store other types of geojson data too, but they won't be indexed.

[danielmai]

Seems like this issue can be closed now. Please re-open it if you're still having the same issue.