[SERVER-9532] incorrect elemMatch bounds for multi key compound index Created: 01/May/13  Updated: 11/Jul/16  Resolved: 10/Feb/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.4.3
Fix Version/s: 2.6.0-rc0

Type: Bug Priority: Major - P3
Reporter: Dominik Gehl Assignee: David Storch
Resolution: Done Votes: 0
Labels: query_triage
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified
Environment:

Linux 64bit


Attachments: File server9532.js    
Operating System: ALL
Steps To Reproduce:

create index on aH.uid

> db.testing_ah_array_path_new.find({'aH.sm':'dominik','aH.uid':{'$gte':1, '$lte':1000}}).explain()
{
"cursor" : "BtreeCursor aH_uid_1",
"isMultiKey" : true,
"n" : 276,
"nscannedObjects" : 124565,
"nscanned" : 124565,
"nscannedObjectsAllPlans" : 124667,
"nscannedAllPlans" : 124667,
"scanAndOrder" : false,
"indexOnly" : false,
"nYields" : 1,
"nChunkSkips" : 0,
"millis" : 809,
"indexBounds" :

{ "aH.uid" : [ [ 1, 1.7976931348623157e+308 ] ] }

,
}

On the other hand, when changing the '$lte' and '$gte' order

> db.testing_ah_array_path_new.find({'aH.sm':'dominik','aH.uid':{'$lte':1000,'$gte':1}}).explain()
{
"cursor" : "BtreeCursor aH_uid_1",
"isMultiKey" : true,
"n" : 276,
"nscannedObjects" : 276,
"nscanned" : 276,
"nscannedObjectsAllPlans" : 378,
"nscannedAllPlans" : 378,
"scanAndOrder" : false,
"indexOnly" : false,
"nYields" : 0,
"nChunkSkips" : 0,
"millis" : 2,
"indexBounds" :

{ "aH.uid" : [ [ -1.7976931348623157e+308, 1000 ] ] }

,
}

In both cases, upper and lower bound should be shown as set to 1 and 1000 respectively by explain()

Participants:

 Description   

only the first of the '$lte' and '$gte' boundaries is actually used by the query optimizer. Order of '$lte' and '$gte therefore becomes crucial



 Comments   
Comment by Githook User [ 10/Feb/14 ]

Author:

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

Message: SERVER-12470 SERVER-12475 SERVER-9532 fix multikey index bounds for compound indices and elemMatch

The new query system multikey index bounds behavior now largely matches that of 2.4.
For a detailed description of the rules for building multikey index bounds, see
the long comment atop db/query/planner_access.h.
Branch: master
https://github.com/mongodb/mongo/commit/bbca96a512c580f13e044eeb7de15132fb3ce193

Comment by Benety Goh [ 30/Oct/13 ]

smoke test script to reproduce/illustrate issue

Comment by Dominik Gehl [ 08/May/13 ]

Reading through some more tickets, I found https://jira.mongodb.org/browse/SERVER-4155 and https://jira.mongodb.org/browse/SERVER-4180. So I started experimenting with the '$elemMatch' "solution"/workaround:

db.test.find({'uid':{'$elemMatch':{'$gte':2,'$lte':3}}}).explain()
{
    "cursor" : "BtreeCursor uid\_1",
    "isMultiKey" : true,
    "n" : 2,
    "nscannedObjects" : 2,
    "nscanned" : 2,
    "nscannedObjectsAllPlans" : 2,
    "nscannedAllPlans" : 2,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 0,
    "nChunkSkips" : 0,
    "millis" : 0,
    "indexBounds" : {
        "uid" : [
            [
                2,
                3
            ]
        ]
    },
}

So, that works for a simple index ... unfortunately though, when having a compound index, it doesn't work any more

> db.test.drop()
true
> db.test.insert({'aH':[{'s':'server','m':'mbox','uid':1}]})
> db.test.insert({'aH':[{'s':'server','m':'mbox','uid':2}]})
> db.test.insert({'aH':[{'s':'server','m':'mbox','uid':3}]})
> db.test.insert({'aH':[{'s':'server','m':'mbox','uid':4}]})
> db.test.ensureIndex({'aH.s':1,'aH.m':1,'aH.uid':1},{'unique':true});
 
> db.test.find({'aH':{'$elemMatch':{'s':'server','m':'mbox','uid':{'$gte':2,'$lte':3}}}}).explain()
{
    "cursor" : "BtreeCursor aH.s\_1_aH.m\_1_aH.uid\_1",
    "isMultiKey" : false,
    "n" : 2,
    "nscannedObjects" : 2,
    "nscanned" : 2,
    "nscannedObjectsAllPlans" : 2,
    "nscannedAllPlans" : 2,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 0,
    "nChunkSkips" : 0,
    "millis" : 0,
    "indexBounds" : {
        "aH.s" : [
            [
                "server",
                "server"
            ]
        ],
        "aH.m" : [
            [
                "mbox",
                "mbox"
            ]
        ],
        "aH.uid" : [
            [
                2,
                3
            ]
        ]
    },
}
> db.test.insert({'aH':[{'s':'server','m':'mbox','uid':5},{'s':'server','m':'mbox','uid':6}]})
> db.test.find({'aH':{'$elemMatch':{'s':'server','m':'mbox','uid':{'$gte':2,'$lte':3}}}}).explain()
{
    "cursor" : "BtreeCursor aH.s\_1_aH.m\_1_aH.uid\_1",
    "isMultiKey" : true,
    "n" : 2,
    "nscannedObjects" : 5,
    "nscanned" : 5,
    "nscannedObjectsAllPlans" : 5,
    "nscannedAllPlans" : 5,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 0,
    "nChunkSkips" : 0,
    "millis" : 0,
    "indexBounds" : {
        "aH.s" : [
            [
                "server",
                "server"
            ]
        ],
        "aH.m" : [
            [
                "mbox",
                "mbox"
            ]
        ],
        "aH.uid" : [
            [
                2,
                1.7976931348623157e+308
            ]
        ]
    },
}
> db.test.find({'aH':{'$elemMatch':{'s':'server','m':'mbox','uid':{'$elemMatch':{'$gte':2,'$lte':3}}}}}).explain()
{
    "cursor" : "BtreeCursor aH.s\_1_aH.m\_1_aH.uid\_1",
    "isMultiKey" : true,
    "n" : 0,
    "nscannedObjects" : 2,
    "nscanned" : 2,
    "nscannedObjectsAllPlans" : 2,
    "nscannedAllPlans" : 2,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 0,
    "nChunkSkips" : 0,
    "millis" : 0,
    "indexBounds" : {
        "aH.s" : [
            [
                "server",
                "server"
            ]
        ],
        "aH.m" : [
            [
                "mbox",
                "mbox"
            ]
        ],
        "aH.uid" : [
            [
                2,
                3
            ]
        ]
    },
}

Comment by Dominik Gehl [ 02/May/13 ]

Some more details on the specifics and also easy steps to reproduce:

> db.test.drop()
true
> db.test.insert({'uid':[1]})
> db.test.insert({'uid':[2]})
> db.test.insert({'uid':[3]})
> db.test.insert({'uid':[4]})
 
> db.test.ensureIndex({'uid':1},{'unique':true});
> db.test.find({'uid':{'$gte':2,'$lte':3}}).explain()
{
	"cursor" : "BtreeCursor uid_1",
	"isMultiKey" : false,
	"n" : 2,
	"nscannedObjects" : 2,
	"nscanned" : 2,
	"nscannedObjectsAllPlans" : 2,
	"nscannedAllPlans" : 2,
	"scanAndOrder" : false,
	"indexOnly" : false,
	"nYields" : 0,
	"nChunkSkips" : 0,
	"millis" : 0,
	"indexBounds" : {
		"uid" : [
			[
				2,
				3
			]
		]
	},
}
> db.test.insert({'uid':[5,6]})
> db.test.find({'uid':{'$gte':2,'$lte':3}}).explain()
{
	"cursor" : "BtreeCursor uid_1",
	"isMultiKey" : true,
	"n" : 2,
	"nscannedObjects" : 5,
	"nscanned" : 5,
	"nscannedObjectsAllPlans" : 5,
	"nscannedAllPlans" : 5,
	"scanAndOrder" : false,
	"indexOnly" : false,
	"nYields" : 0,
	"nChunkSkips" : 0,
	"millis" : 0,
	"indexBounds" : {
		"uid" : [
			[
				2,
				1.7976931348623157e+308
			]
		]
	},
}

So the problem happens as soon as at least two values are inserted into uid for one document. The index then becomes a multi-key index and the indexBounds are calculated differently

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