[SERVER-16011] Query does not use index in some $gte/$lt conditions in array attribute Created: 07/Nov/14  Updated: 10/Dec/14  Resolved: 07/Nov/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.5
Fix Version/s: None

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

Operating System: Linux
Participants:

 Description   

I have made a test and saw that on some cases the index isnt used when i am using $gte / $lt operators in an array attribute.

My documents looks like this:

{
   "_id": 34000,
   "attr": [
     { "k": "attr1", "s": 1, "v": 4 },
     { "k": "attr2", "s": 0, "v": [3] },
     { "k": "attr3", "s": 1, "v": 649 }
  ] 
}

attr3:v is random number 1 ~ 1200

Created Index:

db.collection.ensureIndex({"attr.k": 1, "attr.s": 1, "attr.v": 1});

Quering trough documents

Case 1:

db.collection.find({"attr":{"$all":[{"$elemMatch":{"k":"attr2","s":0,"v":3}},{"$elemMatch":{"k":"attr1","s":1,"v":{"$in":[2,4]}}},{"$elemMatch":{"k":"attr3","s":1,"v":{"$gte":100,"$lt":1100}}}]}}).limit(1).explain(true);

Here is the output of explain:

{
        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
        "isMultiKey" : true,
        "n" : 1,
        "nscannedObjects" : 3,
        "nscanned" : 3,
        "nscannedObjectsAllPlans" : 9,
        "nscannedAllPlans" : 9,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "attr.k" : [
                        [
                                "attr2",
                                "attr2"
                        ]
                ],
                "attr.s" : [
                        [
                                0,
                                0
                        ]
                ],
                "attr.v" : [
                        [
                                3,
                                3
                        ]
                ]
        },
        "allPlans" : [
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 1,
                        "nscannedObjects" : 3,
                        "nscanned" : 3,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "attr2",
                                                "attr2"
                                        ]
                                ],
                                "attr.s" : [
                                        [
                                                0,
                                                0
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                3,
                                                3
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 1,
                        "nscannedObjects" : 3,
                        "nscanned" : 3,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "attr1",
                                                "attr1"
                                        ]
                                ],
                                "attr.s" : [
                                        [
                                                1,
                                                1
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                2,
                                                2
                                        ],
                                        [
                                                4,
                                                4
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 0,
                        "nscannedObjects" : 3,
                        "nscanned" : 3,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "attr3",
                                                "attr3"
                                        ]
                                ],
                                "attr.s" : [
                                        [
                                                1,
                                                1
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                -Infinity,
                                                1100
                                        ]
                                ]
                        }
                }
        ],
        "server" : "elastica:27017",
        "filterSet" : false,
        "stats" : {
                "type" : "LIMIT",
                "works" : 3,
                "yields" : 0,
                "unyields" : 0,
                "invalidates" : 0,
                "advanced" : 1,
                "needTime" : 2,
                "needFetch" : 0,
                "isEOF" : 1,
                "children" : [
                        {
                                "type" : "KEEP_MUTATIONS",
                                "works" : 3,
                                "yields" : 0,
                                "unyields" : 0,
                                "invalidates" : 0,
                                "advanced" : 1,
                                "needTime" : 2,
                                "needFetch" : 0,
                                "isEOF" : 0,
                                "children" : [
                                        {
                                                "type" : "FETCH",
                                                "works" : 3,
                                                "yields" : 0,
                                                "unyields" : 0,
                                                "invalidates" : 0,
                                                "advanced" : 1,
                                                "needTime" : 2,
                                                "needFetch" : 0,
                                                "isEOF" : 0,
                                                "alreadyHasObj" : 0,
                                                "forcedFetches" : 0,
                                                "matchTested" : 1,
                                                "children" : [
                                                        {
                                                                "type" : "IXSCAN",
                                                                "works" : 3,
                                                                "yields" : 0,
                                                                "unyields" : 0,
                                                                "invalidates" : 0,
                                                                "advanced" : 3,
                                                                "needTime" : 0,
                                                                "needFetch" : 0,
                                                                "isEOF" : 0,
                                                                "keyPattern" : "{ attr.k: 1.0, attr.s: 1.0, attr.v: 1.0 }",
                                                                "isMultiKey" : 1,
                                                                "boundsVerbose" : "field #0['attr.k']: [\"attr2\", \"attr2\"], field #1['attr.s']: [0.0, 0.0], field #2['attr.v']: [3.0, 3.0]",
                                                                "yieldMovedCursor" : 0,
                                                                "dupsTested" : 3,
                                                                "dupsDropped" : 0,
                                                                "seenInvalidated" : 0,
                                                                "matchTested" : 0,
                                                                "keysExamined" : 3,
                                                                "children" : [ ]
                                                        }
                                                ]
                                        }
                                ]
                        }
                ]
        }
}

Case 2 (now i am going to increase $gte value)

db.collection.find({"attr":{"$all":[{"$elemMatch":{"k":"attr2","s":0,"v":3}},{"$elemMatch":{"k":"attr1","s":1,"v":{"$in":[2,4]}}},{"$elemMatch":{"k":"attr3","s":1,"v":{"$gte":1000,"$lt":1100}}}]}}).limit(1).explain(true);

And this is what i get from explain:

{
        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
        "isMultiKey" : true,
        "n" : 0,
        "nscannedObjects" : 34000,
        "nscanned" : 34000,
        "nscannedObjectsAllPlans" : 54400,
        "nscannedAllPlans" : 54400,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 424,
        "nChunkSkips" : 0,
        "millis" : 410,
        "indexBounds" : {
                "attr.k" : [
                        [
                                "attr2",
                                "attr2"
                        ]
                ],
                "attr.s" : [
                        [
                                0,
                                0
                        ]
                ],
                "attr.v" : [
                        [
                                3,
                                3
                        ]
                ]
        },
        "allPlans" : [
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 0,
                        "nscannedObjects" : 34000,
                        "nscanned" : 34000,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "attr2",
                                                "attr2"
                                        ]
                                ],
                                "attr.s" : [
                                        [
                                                0,
                                                0
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                3,
                                                3
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 0,
                        "nscannedObjects" : 10200,
                        "nscanned" : 10200,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "attr1",
                                                "attr1"
                                        ]
                                ],
                                "attr.s" : [
                                        [
                                                1,
                                                1
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                2,
                                                2
                                        ],
                                        [
                                                4,
                                                4
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.s_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 0,
                        "nscannedObjects" : 10200,
                        "nscanned" : 10200,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "attr3",
                                                "attr3"
                                        ]
                                ],
                                "attr.s" : [
                                        [
                                                1,
                                                1
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                -Infinity,
                                                1100
                                        ]
                                ]
                        }
                }
        ],
        "server" : "elastica:27017",
        "filterSet" : false,
        "stats" : {
                "type" : "LIMIT",
                "works" : 34001,
                "yields" : 424,
                "unyields" : 424,
                "invalidates" : 0,
                "advanced" : 0,
                "needTime" : 34000,
                "needFetch" : 0,
                "isEOF" : 1,
                "children" : [
                        {
                                "type" : "KEEP_MUTATIONS",
                                "works" : 34001,
                                "yields" : 424,
                                "unyields" : 424,
                                "invalidates" : 0,
                                "advanced" : 0,
                                "needTime" : 34000,
                                "needFetch" : 0,
                                "isEOF" : 1,
                                "children" : [
                                        {
                                                "type" : "FETCH",
                                                "works" : 34001,
                                                "yields" : 424,
                                                "unyields" : 424,
                                                "invalidates" : 0,
                                                "advanced" : 0,
                                                "needTime" : 34000,
                                                "needFetch" : 0,
                                                "isEOF" : 1,
                                                "alreadyHasObj" : 0,
                                                "forcedFetches" : 0,
                                                "matchTested" : 0,
                                                "children" : [
                                                        {
                                                                "type" : "IXSCAN",
                                                                "works" : 34001,
                                                                "yields" : 424,
                                                                "unyields" : 424,
                                                                "invalidates" : 0,
                                                                "advanced" : 34000,
                                                                "needTime" : 0,
                                                                "needFetch" : 0,
                                                                "isEOF" : 1,
                                                                "keyPattern" : "{ attr.k: 1.0, attr.s: 1.0, attr.v: 1.0 }",
                                                                "isMultiKey" : 1,
                                                                "boundsVerbose" : "field #0['attr.k']: [\"attr2\", \"attr2\"], field #1['attr.s']: [0.0, 0.0], field #2['attr.v']: [3.0, 3.0]",
                                                                "yieldMovedCursor" : 0,
                                                                "dupsTested" : 34000,
                                                                "dupsDropped" : 0,
                                                                "seenInvalidated" : 0,
                                                                "matchTested" : 0,
                                                                "keysExamined" : 34000,
                                                                "children" : [ ]
                                                        }
                                                ]
                                        }
                                ]
                        }
                ]
        }
}

Now if i compare this two explain outputs i see two things:
1. nscanned attributes are completely different 3, 34000
2. attr.v of attr3 shows -Infinity:

"attr.v" : [
    [
        -Infinity,
        1100
    ]
]

Records in database: 34000
MongoDB version: 2.6.5
OS: Ubuntu 12.04



 Comments   
Comment by David Storch [ 07/Nov/14 ]

Hi bogdanus,

Thanks for filing this bug report. It looks to me like the system is working as designed in this case. Read on for an explanation of why.

nscanned attributes are completely different 3, 34000

First, please note that both queries are executed using the same query plan. Namely, the plan is an index scan over index {"attr.k": 1, "attr.s": 1, "attr.v": 1}. The system is scanning all index keys where attr.k is "attr2", attr.s is 1, and attr.v is 3. It then fetches the keyed documents, and filters them by the entire predicate. So now the question is, if both queries are using the same query plan, how come there is such a large difference in nscanned?

The reason is that both queries have .limit(1). This means that as soon as the query engine finds a single matching document, it will stop scanning the index and return that document to the user. For the query with $gte: 100, a matching document is found and returned very quickly. On the other hand, the query with $gte: 1000 has no matching documents. This means that the system has to scan all matching index keys and filter the corresponding documents in order to discover that there are no matches. Unlike the first query, it does not get to bail out early after finding a match.

attr.v of attr3 shows -Infinity:

Explain indeed shows -Infinity for the index bounds of the attr.v field. However, note that this is in the allPlans section of the explain. These are the index bounds for one of the candidate query plans which was evaluated by the query optimizer, but ultimately not chosen as the winner. Note that there are three query plans evaluated, one which indexes by the first $elemMatch,

{"$elemMatch":{"k":"attr2","s":0,"v":3}}

one which indexes by the second $elemMatch,

{"$elemMatch":{"k":"attr1","s":1,"v":{"$in":[2,4]}}}

and one which indexes by the third

{"$elemMatch":{"k":"attr3","s":1,"v":{"$gte":100,"$lt":1100}}}

The bounds you are referring to are for the third plan, which has both $gte and $lt predicates over the attr.v field. Although the bounds may look odd, they are actually correct. I will not go into detail here about why these bounds are correct, as we have a detailed page in our documentation on this subject: see http://docs.mongodb.org/manual/core/multikey-index-bounds/.

I hope that this adequately addresses your concerns.

Best,
Dave

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