Loading...

Type: Bug
Resolution: Duplicate
Priority: Major - P3
Fix Version/s: None
Affects Version/s: 2.6.10, 3.0.0
Component/s: Querying
Labels:
None

Operating System:
ALL
Steps To Reproduce:
Hide

Generate a database with documents containing a key/value array form, eg.

{ attr: [ { k: "low", v: 1 }, { k: "high", v: 1000 } ] }

Make sure there are two key/values, one with a high cardinality and one with a very low cardinality - in my example I use simply "high" and "low" to denote these conditions of the value ranges.

In my examples below there were 50,000 documents, "low" has a range of 10 (~5000 docs per bucket), while high has a range of 10000 (~5 docs per bucket).

Build an index to be able to efficiently search for specific pairs, something like:

{ "attr.k":1, "attr.v":1 }

Run a query that would be much faster if the second predicate was used:

db.kv.find({attr:{$all:[{$elemMatch: {k: "low", v: 1}}, {$elemMatch: {k: "high", v: 1}}]}})

Compare runtimes and explain outputs for server versions 2.6.0 (up to 2.6.9) versus 2.6.10 onwards (including 3.0).
Show
Generate a database with documents containing a key/value array form, eg. { attr: [ { k: "low" , v: 1 }, { k: "high" , v: 1000 } ] } Make sure there are two key/values, one with a high cardinality and one with a very low cardinality - in my example I use simply "high" and "low" to denote these conditions of the value ranges. In my examples below there were 50,000 documents, "low" has a range of 10 (~5000 docs per bucket), while high has a range of 10000 (~5 docs per bucket). Build an index to be able to efficiently search for specific pairs, something like: { "attr.k" :1, "attr.v" :1 } Run a query that would be much faster if the second predicate was used: db.kv.find({attr:{$all:[{$elemMatch: {k: "low" , v: 1}}, {$elemMatch: {k: "high" , v: 1}}]}}) Compare runtimes and explain outputs for server versions 2.6.0 (up to 2.6.9) versus 2.6.10 onwards (including 3.0).
Sprint:
QuInt A (10/12/15)
Confidence Status:
None
Work Order:
3

Aha! Reference:
None
Tracking Level:
None
Risk Status:
None
Exec Notes:
None
Goal Name:
None
Goal Link:
None

The pattern of using key/value attributes and querying using $all and $elemMatch used to work really efficiently even when the cardinality of values for specific keys was not known. Since 2.6.10 and 3.0.* this pattern now only uses the first predicate regardless.

~~SERVER-16256~~ appears to have introduced this new behavior, essentially returning it to 2.4.* status.

Shown below are two explain(true) outputs, the first is what is seen when run on 2.6.0 -> 2.6.9... notice there are 2 possible plans in the allPlans list:

>db.kv.find({attr:{$all:[{$elemMatch: {k: "low", v: 1}}, {$elemMatch: {k: "high", v: 1024}}]}}).explain(true);
{
        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
        "isMultiKey" : true,
        "n" : 2,
        "nscannedObjects" : 6,
        "nscanned" : 6,
        "nscannedObjectsAllPlans" : 17,
        "nscannedAllPlans" : 17,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 8,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "attr.k" : [
                        [
                                "high",
                                "high"
                        ]
                ],
                "attr.v" : [
                        [
                                1024,
                                1024
                        ]
                ]
        },
        "allPlans" : [
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 2,
                        "nscannedObjects" : 6,
                        "nscanned" : 6,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "high",
                                                "high"
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                1024,
                                                1024
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 0,
                        "nscannedObjects" : 11,
                        "nscanned" : 11,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "low",
                                                "low"
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                1,
                                                1
                                        ]
                                ]
                        }
                }
        ],
        "server" : "Boomtime:27017",
        "filterSet" : false,
        "stats" : {
                "type" : "KEEP_MUTATIONS",
                "works" : 14,
                "yields" : 8,
                "unyields" : 8,
                "invalidates" : 0,
                "advanced" : 2,
                "needTime" : 4,
                "needFetch" : 6,
                "isEOF" : 1,
                "children" : [
                        {
                                "type" : "FETCH",
                                "works" : 13,
                                "yields" : 8,
                                "unyields" : 8,
                                "invalidates" : 0,
                                "advanced" : 2,
                                "needTime" : 4,
                                "needFetch" : 6,
                                "isEOF" : 1,
                                "alreadyHasObj" : 0,
                                "forcedFetches" : 0,
                                "matchTested" : 2,
                                "children" : [
                                        {
                                                "type" : "IXSCAN",
                                                "works" : 7,
                                                "yields" : 8,
                                                "unyields" : 8,
                                                "invalidates" : 0,
                                                "advanced" : 6,
                                                "needTime" : 0,
                                                "needFetch" : 0,
                                                "isEOF" : 1,
                                                "keyPattern" : "{ attr.k: 1.0, attr.v: 1.0 }",
                                                "isMultiKey" : 1,
                                                "boundsVerbose" : "field #0['attr.k']: [\"high\", \"high\"], field #1['attr.v']: [1024.0, 1024.0]",
                                                "yieldMovedCursor" : 0,
                                                "dupsTested" : 6,
                                                "dupsDropped" : 0,
                                                "seenInvalidated" : 0,
                                                "matchTested" : 0,
                                                "keysExamined" : 6,
                                                "children" : [ ]
                                        }
                                ]
                        }
                ]
        }
}

The second explain is what is seen for the same query on 2.6.10+ (including all of 3.0). Notice that there is now only 1 plan considered, based exclusively on the first item in the $all array:

17:46:50@test>db.kv.find({attr:{$all:[{$elemMatch: {k: "low", v: 1}}, {$elemMatch: {k: "high", v: 1024}}]}}).explain(true);
{
        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
        "isMultiKey" : true,
        "n" : 2,
        "nscannedObjects" : 5138,
        "nscanned" : 5138,
        "nscannedObjectsAllPlans" : 5138,
        "nscannedAllPlans" : 5138,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 174,
        "nChunkSkips" : 0,
        "millis" : 26,
        "indexBounds" : {
                "attr.k" : [
                        [
                                "low",
                                "low"
                        ]
                ],
                "attr.v" : [
                        [
                                1,
                                1
                        ]
                ]
        },
        "allPlans" : [
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 2,
                        "nscannedObjects" : 5138,
                        "nscanned" : 5138,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "low",
                                                "low"
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                1,
                                                1
                                        ]
                                ]
                        }
                }
        ],
        "server" : "Boomtime:27017",
        "filterSet" : false,
        "stats" : {
                "type" : "KEEP_MUTATIONS",
                "works" : 5313,
                "yields" : 174,
                "unyields" : 174,
                "invalidates" : 0,
                "advanced" : 2,
                "needTime" : 5136,
                "needFetch" : 174,
                "isEOF" : 1,
                "children" : [
                        {
                                "type" : "FETCH",
                                "works" : 5313,
                                "yields" : 174,
                                "unyields" : 174,
                                "invalidates" : 0,
                                "advanced" : 2,
                                "needTime" : 5136,
                                "needFetch" : 174,
                                "isEOF" : 1,
                                "alreadyHasObj" : 0,
                                "forcedFetches" : 0,
                                "matchTested" : 2,
                                "children" : [
                                        {
                                                "type" : "IXSCAN",
                                                "works" : 5139,
                                                "yields" : 174,
                                                "unyields" : 174,
                                                "invalidates" : 0,
                                                "advanced" : 5138,
                                                "needTime" : 0,
                                                "needFetch" : 0,
                                                "isEOF" : 1,
                                                "keyPattern" : "{ attr.k: 1.0, attr.v: 1.0 }",
                                                "isMultiKey" : 1,
                                                "boundsVerbose" : "field #0['attr.k']: [\"low\", \"low\"], field #1['attr.v']: [1.0, 1.0]",
                                                "yieldMovedCursor" : 0,
                                                "dupsTested" : 5138,
                                                "dupsDropped" : 0,
                                                "seenInvalidated" : 0,
                                                "matchTested" : 0,
                                                "keysExamined" : 5138,
                                                "children" : [ ]
                                        }
                                ]
                        }
                ]
        }
}

duplicates

SERVER-16042 Optimise $all/$and to select smallest subset as initial index bounds

Closed

is related to

SERVER-16256 $all clause with elemMatch uses wider bounds than needed

Closed

Details

Description

Attachments

Issue Links

Activity

People

Dates