[SERVER-13687] Results of $near query on compound multi-key 2dsphere index not sorted by distance Created: 22/Apr/14  Updated: 11/Jul/16  Resolved: 01/May/14

Status: Closed
Project: Core Server
Component/s: Geo, Querying
Affects Version/s: 2.6.0
Fix Version/s: 2.6.2, 2.7.0

Type: Bug Priority: Major - P3
Reporter: Rick Huizinga Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: File address.json    
Issue Links:
Depends
Duplicate
is duplicated by SERVER-14264 Compound index on 2dsphere and dateti... Closed
Related
is related to SERVER-14723 Crash during query planning for geoNe... Closed
Tested
Operating System: ALL
Backport Completed:
Participants:

 Description   
Issue Status as of May 14, 2014

ISSUE SUMMARY
In the specific case where a compound 2dsphere index exists and is multi-key (at least one indexed value is an array), the wrong query plans can be generated for $near queries and lead to unexpected query results. For example, results returned by a $near query may no longer be sorted by distance.

USER IMPACT
Incorrect query plans can lead to unexpected behavior, specifically in the case of $near the user may get back incorrectly sorted documents from their query.

WORKAROUNDS
If possible, change the index to another compound field (in combination with the location) so it is no longer a multi-key index.

AFFECTED VERSIONS
Versions 2.6.0 and 2.6.1 are affected by this issue.

FIX VERSION
The fix is included in the 2.6.2 production release.

RESOLUTION DETAILS
The query plan enumerator now first assigns a mandatory predicate (e.g. $geonear), before assigning further predicates according to the usual rules of multi-key indexes.

Original description

I have been running a geospatial query using a compound index.

After upgrading to MongoDB 2.6, the order of the result set has changed such that the results are no longer being sorted by distance for the following query:

db.properties.find({ "address.uppercase": { $regex: "^14529" }, "address.location": { $near: { $geometry: { type: "Point", coordinates: [ -122.2103, 47.6154 ] }}}})

The index on the properties collection is configured as:

{ "address.uppercase": 1, "address.location": "2dsphere" }

In 2.4, the query returned all addresses where "address.uppercase" starts with "14529", ordered by the address distance from location [ -122.2103, 47.6154 ].

After upgrading to 2.6, the same query now returns all addresses ordered by "address.uppercase", effectively making it impossible to perform a geospatial $near query on a compound index.



 Comments   
Comment by Githook User [ 15/May/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13687 fix plan enumeration for compound multikey 2d or 2dsphere indices
Branch: v2.6
https://github.com/mongodb/mongo/commit/c2d90aad653b567be14798665e280b94525bb55d

Comment by Githook User [ 01/May/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13687 fix plan enumeration for compound multikey 2d or 2dsphere indices
Branch: master
https://github.com/mongodb/mongo/commit/4eb9988846e1e7d49ec26facd9a2ff6b89f8cdde

Comment by hari.khalsa@10gen.com [ 23/Apr/14 ]

Thanks sprybytes for reporting this bug and thanks to rassi@10gen.com for digging in and debugging. Apologies for the bug. We will be fixing it shortly.

Comment by J Rassi [ 23/Apr/14 ]

Thanks for the additional info. I see now that the issue manifests only if the index is multi-key (in this case, there's at least one document with multiple addresses), and now can reproduce with the following:

> db.properties.insert({_id: 0, a: 0, b: {type: "Point", coordinates: [0, 0]}})
WriteResult({ "nInserted" : 1 })
> db.properties.insert({_id: 1, a: 1, b: {type: "Point", coordinates: [1, 1]}})
WriteResult({ "nInserted" : 1 })
> db.properties.insert({_id: 2, a: 2, b: {type: "Point", coordinates: [2, 2]}})
WriteResult({ "nInserted" : 1 })
> db.properties.ensureIndex({a: 1, b: "2dsphere"})
{
	"createdCollectionAutomatically" : false,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
> db.properties.find({a: {$gte: 0}, b: {$near: {$geometry: {type: "Point", coordinates: [2, 2]}}}})
{ "_id" : 2, "a" : 2, "b" : { "type" : "Point", "coordinates" : [ 2, 2 ] } } // correct: sorted by distance
{ "_id" : 1, "a" : 1, "b" : { "type" : "Point", "coordinates" : [ 1, 1 ] } }
{ "_id" : 0, "a" : 0, "b" : { "type" : "Point", "coordinates" : [ 0, 0 ] } }
> db.properties.insert({a: ["multi", "key"], b: {type: "Point", coordinates: [-1, -1]}})
WriteResult({ "nInserted" : 1 }) // index is now multi-key
> db.properties.find({a: {$gte: 0}, b: {$near: {$geometry: {type: "Point", coordinates: [2, 2]}}}})
{ "_id" : 0, "a" : 0, "b" : { "type" : "Point", "coordinates" : [ 0, 0 ] } } // incorrect: not sorted by distance
{ "_id" : 1, "a" : 1, "b" : { "type" : "Point", "coordinates" : [ 1, 1 ] } }
{ "_id" : 2, "a" : 2, "b" : { "type" : "Point", "coordinates" : [ 2, 2 ] } }

I've updated the title of this issue accordingly. Thanks again for the report. Please watch this ticket for updates on the fix's progress.

Comment by Rick Huizinga [ 23/Apr/14 ]

Top 20 results for MongoDB 2.4.9 & 2.6.0 are below:

MongoDB 2.4.9

{ "_id" : ObjectId("533dd1d5a434d751c78bd609"), "address" : { "uppercase" : [ "14529 NE 5TH ST, BELLEVUE, WA 98007" ] } }
{ "_id" : ObjectId("533dd1cfa434d751c78b9b8a"), "address" : { "uppercase" : [ "14529 SE 50TH ST, BELLEVUE, WA 98006" ] } }
{ "_id" : ObjectId("533dd282a434d751c7925b80"), "address" : { "uppercase" : [ "14529 SE 79TH DR, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd1e8a434d751c78cace8"), "address" : { "uppercase" : [ "14529 SE 85TH ST, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd275a434d751c791cfc1"), "address" : { "uppercase" : [ "14529 92ND AVE NE, KENMORE, WA 98028" ] } }
{ "_id" : ObjectId("533dd248a434d751c7905b70"), "address" : { "uppercase" : [ "14529 114TH AVE NE, KIRKLAND, WA 98034" ] } }
{ "_id" : ObjectId("533dd20ea434d751c78e15dc"), "address" : { "uppercase" : [ "14529 31ST AVE NE, SHORELINE, WA 98155" ] } }
{ "_id" : ObjectId("533dd222a434d751c78ed95d"), "address" : { "uppercase" : [ "14529 22ND AVE NE, SHORELINE, WA 98155" ] } }
{ "_id" : ObjectId("533dd235a434d751c78fa014"), "address" : { "uppercase" : [ "14529 MERIDIAN AVE N, SHORELINE, WA 98133" ] } }
{ "_id" : ObjectId("533dd1e6a434d751c78c93ab"), "address" : { "uppercase" : [ "14529 WALLINGFORD AVE N, SHORELINE, WA 98133" ] } }
{ "_id" : ObjectId("533dd1b3a434d751c78a635f"), "address" : { "uppercase" : [ "14529 ASHWORTH AVE N, SHORELINE, WA 98133" ] } }
{ "_id" : ObjectId("533dd1e2a434d751c78c6ce4"), "address" : { "uppercase" : [ "14529 NE 180TH ST, WOODINVILLE, WA 98072" ] } }
{ "_id" : ObjectId("533dd1fea434d751c78d92e2"), "address" : { "uppercase" : [ "14529 144TH PL SE, RENTON, WA 98059", "14529 144TH PL SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd1b7a434d751c78a8bf1"), "address" : { "uppercase" : [ "14529 164TH PL SE, RENTON, WA 98059", "14529 164TH PL SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd1c7a434d751c78b419e"), "address" : { "uppercase" : [ "14529 165TH AVE SE, RENTON, WA 98059", "14529 165TH AVE SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd1c8a434d751c78b50b7"), "address" : { "uppercase" : [ "14529 166TH PL SE, RENTON, WA 98059", "14529 166TH PL SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd27da434d751c79220ee"), "address" : { "uppercase" : [ "14529 SE 167TH ST, RENTON, WA 98058" ] } }
{ "_id" : ObjectId("533dd27da434d751c79220f1"), "address" : { "uppercase" : [ "14529 SE FAIRWOOD BLVD, RENTON, WA 98058" ] } }
{ "_id" : ObjectId("533dd1c2a434d751c78b0f10"), "address" : { "uppercase" : [ "14529 233RD AVE SE, ISSAQUAH, WA 98027" ] } }
{ "_id" : ObjectId("533dd276a434d751c791d559"), "address" : { "uppercase" : [ "14529 270TH PL NE, DUVALL, WA 98019" ] } }

MongoDB 2.6.0

{ "_id" : ObjectId("533dd248a434d751c7905b70"), "address" : { "uppercase" : [ "14529 114TH AVE NE, KIRKLAND, WA 98034" ] } }
{ "_id" : ObjectId("533dd1fea434d751c78d92e2"), "address" : { "uppercase" : [ "14529 144TH PL SE, RENTON, WA 98059", "14529 144TH PL SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("5336a40ca434d751c787d808"), "address" : { "uppercase" : "14529 14TH AVE SE, MILL CREEK, WA 98012" } }
{ "_id" : ObjectId("533dd1b7a434d751c78a8bf1"), "address" : { "uppercase" : [ "14529 164TH PL SE, RENTON, WA 98059", "14529 164TH PL SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd1c7a434d751c78b419e"), "address" : { "uppercase" : [ "14529 165TH AVE SE, RENTON, WA 98059", "14529 165TH AVE SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("533dd1c8a434d751c78b50b7"), "address" : { "uppercase" : [ "14529 166TH PL SE, RENTON, WA 98059", "14529 166TH PL SE, NEWCASTLE, WA 98059" ] } }
{ "_id" : ObjectId("5336adc1a434d751c7891246"), "address" : { "uppercase" : "14529 17TH AVE W, LYNNWOOD, WA 98087" } }
{ "_id" : ObjectId("5336a4e0a434d751c787f46f"), "address" : { "uppercase" : "14529 21ST DR SE, MILL CREEK, WA 98012" } }
{ "_id" : ObjectId("533dd222a434d751c78ed95d"), "address" : { "uppercase" : [ "14529 22ND AVE NE, SHORELINE, WA 98155" ] } }
{ "_id" : ObjectId("533dd1c2a434d751c78b0f10"), "address" : { "uppercase" : [ "14529 233RD AVE SE, ISSAQUAH, WA 98027" ] } }
{ "_id" : ObjectId("5336a519a434d751c787faf4"), "address" : { "uppercase" : "14529 245TH DR SE, MONROE, WA 98272" } }
{ "_id" : ObjectId("53369f43a434d751c7873b4f"), "address" : { "uppercase" : "14529 254TH AVE SE, MONROE, WA 98272" } }
{ "_id" : ObjectId("5336af3fa434d751c7894653"), "address" : { "uppercase" : "14529 259TH AVE SE, MONROE, WA 98272" } }
{ "_id" : ObjectId("5336a2f3a434d751c787b443"), "address" : { "uppercase" : "14529 26TH DR SE, MILL CREEK, WA 98012" } }
{ "_id" : ObjectId("533dd276a434d751c791d559"), "address" : { "uppercase" : [ "14529 270TH PL NE, DUVALL, WA 98019" ] } }
{ "_id" : ObjectId("5336a284a434d751c787a892"), "address" : { "uppercase" : "14529 28TH DR SE, MILL CREEK, WA 98012" } }
{ "_id" : ObjectId("533dd20ea434d751c78e15dc"), "address" : { "uppercase" : [ "14529 31ST AVE NE, SHORELINE, WA 98155" ] } }
{ "_id" : ObjectId("5336ab3fa434d751c788c3e8"), "address" : { "uppercase" : "14529 38TH DR SE, MILL CREEK, WA 98012" } }
{ "_id" : ObjectId("5336aa38a434d751c788a46f"), "address" : { "uppercase" : "14529 42ND DR SE, SNOHOMISH, WA 98296" } }
{ "_id" : ObjectId("5336b056a434d751c789652a"), "address" : { "uppercase" : "14529 50TH ST NE, LAKE STEVENS, WA 98258" } }

Comment by Rick Huizinga [ 23/Apr/14 ]

Also confirmed that importing the same dataset into a fresh MongoDB 2.4.9 database with the same index and same query will return the results sorted on "address.location". Importing into a fresh MongoDB 2.6.0 database with the same index and same query will return the results sorted on "address.uppercase".

Comment by Rick Huizinga [ 23/Apr/14 ]

Hi Jason,

I have replicated this problem with the attached dataset (address.json). If you use mongoimport to import these documents into your "properties" collection, and re-run the query, you will see that the results are sorted by "address.uppercase" rather than "address.location".

You will also notice the different query.explain() results.

Comment by Rick Huizinga [ 23/Apr/14 ]

Dataset to replicate problem.

Comment by Rick Huizinga [ 22/Apr/14 ]

Thanks for investigating this Jason.

After seeing your test case, I attempted to create a simple test case on a new database to reproduce this problem, and it did not exhibit the problem. At the same time, my database, created in 2.4 and upgraded to 2.6, does exhibit the problem.

The part that I found interesting was that each database has VERY different explain() results even though the indexes are defined to be the same. For example, look at the different cursor types:

For the freshly created 2.6 database:

getIndexes()

[
        {
                "v" : 1,
                "key" : {
                        "_id" : 1
                },
                "name" : "_id_",
                "ns" : "test.properties"
        },
        {
                "v" : 1,
                "key" : {
                        "address.uppercase" : 1,
                        "address.location" : "2dsphere"
                },
                "name" : "address.uppercase_1_address.location_2dsphere",
                "ns" : "test.properties",
                "background" : true,
                "sparse" : true,
                "2dsphereIndexVersion" : 2
        }
]

db.properties.find(...).explain(true)

{
        "cursor" : "S2NearCursor",
        "isMultiKey" : false,
        "n" : 3,
        "nscannedObjects" : 38,
        "nscanned" : 38,
        "nscannedObjectsAllPlans" : 38,
        "nscannedAllPlans" : 38,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 1,
        "indexBounds" : {
 
        },
        "allPlans" : [
                {
                        "cursor" : "S2NearCursor",
                        "isMultiKey" : false,
                        "n" : 3,
                        "nscannedObjects" : 38,
                        "nscanned" : 38,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
 
                        }
                }
        ],
        "server" : "removed for security",
        "filterSet" : false,
        "stats" : {
                "type" : "GEO_NEAR_2DSPHERE",
                "works" : 38,
                "yields" : 0,
                "unyields" : 0,
                "invalidates" : 0,
                "advanced" : 3,
                "needTime" : 0,
                "needFetch" : 0,
                "isEOF" : 1,
                "children" : [ ]
        }
}

For my database, upgraded from 2.4:

db.properties.getIndexes()

[
        {
                "v" : 1,
                "key" : {
                        "_id" : 1
                },
                "ns" : "realvana.properties",
                "name" : "_id_"
        },
        {
                "v" : 1,
                "key" : {
                        "external_id" : 1
                },
                "ns" : "realvana.properties",
                "name" : "external_id_1",
                "background" : true
        },
        {
                "v" : 1,
                "key" : {
                        "address.uppercase" : 1,
                        "address.location" : "2dsphere"
                },
                "name" : "address.uppercase_1_address.location_2dsphere",
                "ns" : "realvana.properties",
                "background" : true,
                "sparse" : true,
                "2dsphereIndexVersion" : 2
        }
]

db.properties.find(...).explain(true)

{
        "cursor" : "BtreeCursor address.uppercase_1_address.location_2dsphere",
        "isMultiKey" : true,
        "n" : 44,
        "nscannedObjects" : 44,
        "nscanned" : 50,
        "nscannedObjectsAllPlans" : 44,
        "nscannedAllPlans" : 50,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "address.uppercase" : [
                        [
                                "14529",
                                "1452:"
                        ],
                        [
                                /^14529/,
                                /^14529/
                        ]
                ],
                "address.location" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "allPlans" : [
                {
                        "cursor" : "BtreeCursor address.uppercase_1_address.location_2dsphere",
                        "isMultiKey" : true,
                        "n" : 44,
                        "nscannedObjects" : 44,
                        "nscanned" : 50,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "address.uppercase" : [
                                        [
                                                "14529",
                                                "1452:"
                                        ],
                                        [
                                                /^14529/,
                                                /^14529/
                                        ]
                                ],
                                "address.location" : [
                                        [
                                                {
                                                        "$minElement" : 1
                                                },
                                                {
                                                        "$maxElement" : 1
                                                }
                                        ]
                                ]
                        }
                }
        ],
        "server" : "removed for security",
        "filterSet" : false,
        "stats" : {
                "type" : "KEEP_MUTATIONS",
                "works" : 50,
                "yields" : 0,
                "unyields" : 0,
                "invalidates" : 0,
                "advanced" : 44,
                "needTime" : 5,
                "needFetch" : 0,
                "isEOF" : 1,
                "children" : [
                        {
                                "type" : "FETCH",
                                "works" : 50,
                                "yields" : 0,
                                "unyields" : 0,
                                "invalidates" : 0,
                                "advanced" : 44,
                                "needTime" : 5,
                                "needFetch" : 0,
                                "isEOF" : 1,
                                "alreadyHasObj" : 0,
                                "forcedFetches" : 0,
                                "matchTested" : 44,
                                "children" : [
                                        {
                                                "type" : "IXSCAN",
                                                "works" : 49,
                                                "yields" : 0,
                                                "unyields" : 0,
                                                "invalidates" : 0,
                                                "advanced" : 44,
                                                "needTime" : 5,
                                                "needFetch" : 0,
                                                "isEOF" : 1,
                                                "keyPattern" : "{ address.uppercase: 1.0, address.location: \"2dsphere\" }",
                                                "boundsVerbose" : "field #0['address.uppercase']: [\"14529\", \"1452:\"), [/^14529/, /^14529/], field #1['address.location']: [MinKey, MaxKey]",
                                                "isMultiKey" : 1,
                                                "yieldMovedCursor" : 0,
                                                "dupsTested" : 49,
                                                "dupsDropped" : 5,
                                                "seenInvalidated" : 0,
                                                "matchTested" : 0,
                                                "keysExamined" : 50,
                                                "children" : [ ]
                                        }
                                ]
                        }
                ]
        }
}

I will attempt to create a test case to replicate this issue, but am hoping that you may be able to determine what is happening by quickly reviewing the explain() logs. It's puzzling to me that the explain() results are so different despite having the exact same index.

Comment by J Rassi [ 22/Apr/14 ]

Hi,

I can't reproduce this:

> db.version()
2.6.0
> db.properties.getIndexes()
[
	{
		"v" : 1,
		"key" : {
			"_id" : 1
		},
		"name" : "_id_",
		"ns" : "test.properties"
	},
	{
		"v" : 1,
		"key" : {
			"address.uppercase" : 1,
			"address.location" : "2dsphere"
		},
		"name" : "address.uppercase_1_address.location_2dsphere",
		"ns" : "test.properties",
		"2dsphereIndexVersion" : 2
	}
]
> db.properties.find({ "address.uppercase": { $regex: "^14529" }, "address.location": { $near: { $geometry: { type: "Point", coordinates: [ -122.2103, 47.6154 ] }}}})
{ "_id" : 2, "address" : { "uppercase" : "14529002", "location" : { "type" : "Point", "coordinates" : [ -122.2103, 47.6154 ] } } }
{ "_id" : 1, "address" : { "uppercase" : "14529001", "location" : { "type" : "Point", "coordinates" : [ -122.21, 47.615 ] } } }
{ "_id" : 0, "address" : { "uppercase" : "14529000", "location" : { "type" : "Point", "coordinates" : [ -122.21, 47.61 ] } } }

To further diagnose this issue, could you paste the output of running the following at the shell?

  • db.version()
  • db.properties.getIndexes()
  • db.properties.find({ "address.uppercase": { $regex: "^14529" }, "address.location": { $near: { $geometry: { type: "Point", coordinates: [ -122.2103, 47.6154 ] }}}})
  • db.properties.find({ "address.uppercase": { $regex: "^14529" }, "address.location": { $near: { $geometry: { type: "Point", coordinates: [ -122.2103, 47.6154 ] }}}}).explain(true)

As an aside, note also that this particular query doesn't make efficient use of this index (the query will scan documents that have a similar address to the requested address but are far away from the requested point).

~ Jason Rassi

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