Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-19999

$all with $elemMatch indexes first element regardless of predicate cardinality (regression)

XMLWordPrintableJSON

    • Type: Icon: Bug Bug
    • Resolution: Duplicate
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: 2.6.10, 3.0.0
    • Component/s: Querying
    • None
    • ALL
    • Hide
      1. 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).
      2. Build an index to be able to efficiently search for specific pairs, something like: 
        { "attr.k":1, "attr.v":1 }
      3. 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}}]}})
      4. 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).
    • QuInt A (10/12/15)

      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" : [ ]
                                        }
                                ]
                        }
                ]
        }
}

            Assignee:
            david.storch@mongodb.com David Storch
            Reporter:
            andrew.ryder@mongodb.com Andrew Ryder (Inactive)
            Votes:
            2 Vote for this issue
            Watchers:
            13 Start watching this issue

              Created:
              Updated:
              Resolved: