[SERVER-47994] Fix for numerical overflow in GeoHash Created: 06/May/20  Updated: 29/Oct/23  Resolved: 18/May/20

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 4.3.6
Fix Version/s: 4.0.19, 3.6.19, 4.2.8, 4.4.0-rc7, 4.7.0

Type: Bug Priority: Major - P3
Reporter: Svilen Mihaylov (Inactive) Assignee: Svilen Mihaylov (Inactive)
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Depends
Gantt Dependency
has to be done after SERVER-48086 Update commit hash parsing rules for ... Closed
Problem/Incident
Related
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v4.4, v4.2, v4.0, v3.6
Sprint: Query 2020-05-18, Query 2020-06-01
Participants:
Linked BF Score: 18

 Description   

Proposed title: Geo 2D index bounds validation

Issue Status as of May 29, 2020

ISSUE SUMMARY

Earlier versions allowed invalid values for the min and max parameters for 2d indexes.

  • min or max could be infinities or NaNs.
  • min and max could be finite but too close together, leading to NaNs or infinities during index retrieval.

USER IMPACT

  • The index may have invalid keys, and could return in incorrect query results

RECOVERY STEPS

  • Before upgrading, drop 2d indexes.
  • Upgrade to one of fixed versions (below)
  • If necessary, re-create the 2d index with corrected values for the min and max parameters.

AFFECTED VERSIONS
This issue affects all supported versions at or prior to 4.4.

FIX VERSION
The fix will be included in 4.5.1, 4.0.19, 3.6.19, 4.4.0-rc7, 4.2.8



 Comments   
Comment by Githook User [ 21/May/20 ]

Author:

{'name': 'Svilen Mihaylov', 'email': 'svilen.mihaylov@mongodb.com', 'username': 'smihaylov-mongodb'}

Message: SERVER-47994 Fix for numerical overflow in GeoHash
Branch: v3.6
https://github.com/mongodb/mongo/commit/15e384e1938cb8c64dae29f4a02d9da9defecd7f

Comment by Githook User [ 21/May/20 ]

Author:

{'name': 'Svilen Mihaylov', 'email': 'svilen.mihaylov@mongodb.com', 'username': 'smihaylov-mongodb'}

Message: SERVER-47994 Fix for numerical overflow in GeoHash
Branch: v4.0
https://github.com/mongodb/mongo/commit/995ef38f871ccd7001b9f6e2ab5428b86d50ff2b

Comment by David Storch [ 20/May/20 ]

This issue can result in broken 2d indexes if the min and max are +/-infinity or NaN, or if min and max are very close together. Here's a simple example where min is provided as NaN:

> db.c.drop()
> db.c.createIndex({a: "2d"}, {min: NaN, max: 10})
{
	"createdCollectionAutomatically" : true,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
> db.c.insert({a: [0, 0]})
WriteResult({
	"nInserted" : 0,
	"writeError" : {
		"code" : 13027,
		"errmsg" : "point not in interval of [ nan, 10 ] :: caused by :: { _id: ObjectId('5ec54b6b26cfe2152d49b0e6'), a: [ 0.0, 0.0 ] }"
	}
})

It is a bug that such indexes can be created in the first place, although subsequent insertions of coordinate pairs will fail since they do not fall within the nonsensical interval of [NaN, 10]. A more severe problem occurs when min or max are infinite. Here's an example where min is set to -Infinity:

> db.c.drop()
true
> db.c.createIndex({a: "2d"}, {min: -Infinity, max: 10})
{
	"createdCollectionAutomatically" : true,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
> db.c.insert({a: [0, 0]})
WriteResult({ "nInserted" : 1 })
> db.c.find({a: {$near: [0, 0]}})
// No results returned!

In this case, the insert of coordinate pair data succeeds, but subsequent queries using the index fail to return results due to the corrupt index. Finally, a corrupt index can result if min and max are very close together. This is because the internal geo hash computation relies on a scaling factor so that values on [min, max] are mapped to [0, (max-min) * scaling]. The scaling factor is defined as numBuckets / (max - min), which can result in overflow.

I suspect that there are very few users which actually have such invalid 2d indexes in the wild, since real use cases are unlikely to involve infinities, nans, and very tiny ranges of doubles. Users who are affected, however, should upgrade to a version containing the fix, drop any invalid 2d indexes, and rebuild indexes with legal parameters.

CC svilen.mihaylov

Comment by Githook User [ 18/May/20 ]

Author:

{'name': 'Svilen Mihaylov', 'email': 'svilen.mihaylov@mongodb.com', 'username': 'smihaylov-mongodb'}

Message: SERVER-47994 Fix for numerical overflow in GeoHash (part 2)
Branch: master
https://github.com/mongodb/mongo/commit/cbd23d40077b148f94ba74fef49198b287e51747

Comment by Githook User [ 15/May/20 ]

Author:

{'name': 'Svilen Mihaylov', 'email': 'svilen.mihaylov@mongodb.com', 'username': 'smihaylov-mongodb'}

Message: SERVER-47994 Fix for numerical overflow in GeoHash
Branch: v4.4
https://github.com/mongodb/mongo/commit/fa4d0d743d7bcab49978e3fe198bcacc4657b97a

Comment by Githook User [ 15/May/20 ]

Author:

{'name': 'Svilen Mihaylov', 'email': 'svilen.mihaylov@mongodb.com', 'username': 'smihaylov-mongodb'}

Message: SERVER-47994 Fix for numerical overflow in GeoHash
Branch: master
https://github.com/mongodb/mongo/commit/2c0306062f074fb35c0554e577401227a45ad811

Comment by Svilen Mihaylov (Inactive) [ 06/May/20 ]

https://mongodbcr.appspot.com/592320012/

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