[SERVER-19129] S2 sometimes returns empty coverings Created: 25/Jun/15  Updated: 06/Dec/22  Resolved: 02/Aug/19

Status: Closed
Project: Core Server
Component/s: Geo
Affects Version/s: 3.0.4
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Kevin Albertson Assignee: Backlog - Query Team (Inactive)
Resolution: Done Votes: 0
Labels: query-44-grooming
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: Text File s2_covering_unit_test.patch    
Assigned Teams:
Query
Operating System: ALL
Steps To Reproduce:

To see the effects of this, you can run the following:

db.phantom.insert({loc: {type: "Point", coordinates: [106.6331,10.7395]}})
db.phantom.createIndex({loc: "2dsphere"}, {coarsestIndexedLevel: 26, finestIndexedLevel: 30})
// returns nothing
db.phantom.find({loc: {$near: {$geometry: {type:"Point", coordinates:[106.6331,10.7395]}, $maxDistance:.05}}})
// but with *smaller* maxDistance, we get our point back
db.phantom.find({loc: {$near: {$geometry: {type:"Point", coordinates:[106.6331,10.7395]}, $maxDistance:.001}}})

Additionally, attached is a patch including a unit test to reproduce this bug with just the S2 functions. Compile it with:
scons -j4 build/opt/mongo/db/geo/s2_covering_test
Run with:
build/opt/mongo/db/geo/s2_covering_test

Participants:

 Description   

Some very specific $near queries with small (but not negligible) $maxDistance values will unexpectedly return empty results. So far this can only be reproduced in the shell by manually setting the coarsestIndexedLevel and finestIndexedLevel.

Ultimately, this is caused by S2 returning empty coverings for S2Cap regions. The root of this problem seems to be caused by floating point error in the S2Cap::Contains method.

For a full S2Cap (entire sphere) S2Cap::Contains will return false on some points along/near the negative axis. The expected behavior is to return true for any point or geometry, since it is the full sphere.



 Comments   
Comment by David Storch [ 02/Aug/19 ]

Per discussion with kevin.albertson, I'm going to close this ticket. It's possible there are other manifestations of a similar problem, but this particular case has been fixed.

Comment by Kevin Albertson [ 13/Aug/15 ]

We have added a workaround which avoids the case of the occurrence in this ticket. The annulus regions in geo near are represented as an intersection of the outer cap and the complement of the inner cap (the hole of the annulus). In the first interval, since the inner cap has a radius 0 its complement should be the full sphere. However, S2 may still say that a point is not in the inner cap complement in degenerate cases. Therefore, we removed the inner cap complement on the first interval, fixing this case.

Comment by Kevin Albertson [ 17/Jul/15 ]

Similar behavior was found when working on SERVER-18921. $near queries centered on an indexed point would sometimes not return the indexed point. This was caused by the same behavior exhibited here. S2 will incorrectly classify vertices as being outside of the full S2 cap region on/near the negative axis.

Comment by Kevin Albertson [ 02/Jul/15 ]

milkie Yes it does.

Comment by Eric Milkie [ 02/Jul/15 ]

I'm curious, does the test fail in the same way when compiled with gcc, clang, and Visual Studio?

Generated at Thu Feb 08 03:49:56 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.