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

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

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Duplicate
    • Affects Version/s: 2.6.10, 3.0.0
    • Fix Version/s: None
    • Component/s: Querying
    • Labels:
      None
    • Operating System:
      ALL
    • Steps To Reproduce:
      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).
    • Sprint:
      QuInt A (10/12/15)

      Description

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

        Attachments

          Issue Links

            Activity

              People

              • Votes:
                2 Vote for this issue
                Watchers:
                14 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: