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

Bad query plans for $exists:true queries

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: Performance, Querying
    • None
    • Query Optimization

      Right now I don't think we are getting any advantage from using the index for $exists:true queries since we are always going to the row store. In fact, it is significantly slower because we are doing a bunch of point queries into the row store rather than using a (relatively) efficient collection scan. However, for covering indexes, we only need to go to the row store when the index says null to disambiguate missing fields from explicit null storage. For non-covering indexes we should probably just always use a collection scan because we need to go to the row store regardless of whether there is a match or not:

      > db.products.explain('executionStats').find({type: {$exists:true}}, {_id:0, type: 1})
      {
              "explainVersion" : "1",
              "queryPlanner" : {
                      "namespace" : "bestbuy.products",
                      "indexFilterSet" : false,
                      "parsedQuery" : {
                              "type" : {
                                      "$exists" : true
                              }
                      },
                      "maxIndexedOrSolutionsReached" : false,
                      "maxIndexedAndSolutionsReached" : false,
                      "maxScansToExplodeReached" : false,
                      "winningPlan" : {
                              "stage" : "PROJECTION_SIMPLE",
                              "transformBy" : {
                                      "_id" : 0,
                                      "type" : 1
                              },
                              "inputStage" : {
                                      "stage" : "FETCH",
                                      "filter" : {
                                              "type" : {
                                                      "$exists" : true
                                              }
                                      },
                                      "inputStage" : {
                                              "stage" : "IXSCAN",
                                              "keyPattern" : {
                                                      "type" : 1,
                                                      "customerReviewCount" : -1
                                              },
                                              "indexName" : "type_1_customerReviewCount_-1",
                                              "isMultiKey" : false,
                                              "multiKeyPaths" : {
                                                      "type" : [ ],
                                                      "customerReviewCount" : [ ]
                                              },
                                              "isUnique" : false,
                                              "isSparse" : false,
                                              "isPartial" : false,
                                              "indexVersion" : 2,
                                              "direction" : "forward",
                                              "indexBounds" : {
                                                      "type" : [
                                                              "[MinKey, MaxKey]"
                                                      ],
                                                      "customerReviewCount" : [
                                                              "[MaxKey, MinKey]"
                                                      ]
                                              }
                                      }
                              }
                      },
                      "rejectedPlans" : [
                              {
                                      "stage" : "PROJECTION_SIMPLE",
                                      "transformBy" : {
                                              "_id" : 0,
                                              "type" : 1
                                      },
                                      "inputStage" : {
                                              "stage" : "FETCH",
                                              "filter" : {
                                                      "type" : {
                                                              "$exists" : true
                                                      }
                                              },
                                              "inputStage" : {
                                                      "stage" : "IXSCAN",
                                                      "keyPattern" : {
                                                              "type" : 1,
                                                              "name" : 1
                                                      },
                                                      "indexName" : "type_1_name_1",
                                                      "isMultiKey" : false,
                                                      "multiKeyPaths" : {
                                                              "type" : [ ],
                                                              "name" : [ ]
                                                      },
                                                      "isUnique" : false,
                                                      "isSparse" : false,
                                                      "isPartial" : false,
                                                      "indexVersion" : 2,
                                                      "direction" : "forward",
                                                      "indexBounds" : {
                                                              "type" : [
                                                                      "[MinKey, MaxKey]"
                                                              ],
                                                              "name" : [
                                                                      "[MinKey, MaxKey]"
                                                              ]
                                                      }
                                              }
                                      }
                              },
                              {
                                      "stage" : "PROJECTION_SIMPLE",
                                      "transformBy" : {
                                              "_id" : 0,
                                              "type" : 1
                                      },
                                      "inputStage" : {
                                              "stage" : "FETCH",
                                              "filter" : {
                                                      "type" : {
                                                              "$exists" : true
                                                      }
                                              },
                                              "inputStage" : {
                                                      "stage" : "IXSCAN",
                                                      "keyPattern" : {
                                                              "type" : 1,
                                                              "subclass" : 1,
                                                              "genre" : 1,
                                                              "format" : 1
                                                      },
                                                      "indexName" : "type_1_subclass_1_genre_1_format_1",
                                                      "isMultiKey" : false,
                                                      "multiKeyPaths" : {
                                                              "type" : [ ],
                                                              "subclass" : [ ],
                                                              "genre" : [ ],
                                                              "format" : [ ]
                                                      },
                                                      "isUnique" : false,
                                                      "isSparse" : false,
                                                      "isPartial" : false,
                                                      "indexVersion" : 2,
                                                      "direction" : "forward",
                                                      "indexBounds" : {
                                                              "type" : [
                                                                      "[MinKey, MaxKey]"
                                                              ],
                                                              "subclass" : [
                                                                      "[MinKey, MaxKey]"
                                                              ],
                                                              "genre" : [
                                                                      "[MinKey, MaxKey]"
                                                              ],
                                                              "format" : [
                                                                      "[MinKey, MaxKey]"
                                                              ]
                                                      }
                                              }
                                      }
                              },
                              {
                                      "stage" : "PROJECTION_SIMPLE",
                                      "transformBy" : {
                                              "_id" : 0,
                                              "type" : 1
                                      },
                                      "inputStage" : {
                                              "stage" : "FETCH",
                                              "inputStage" : {
                                                      "stage" : "IXSCAN",
                                                      "keyPattern" : {
                                                              "$_path" : 1,
                                                              "type" : 1
                                                      },
                                                      "indexName" : "$**_1",
                                                      "isMultiKey" : false,
                                                      "multiKeyPaths" : {
                                                              "$_path" : [ ],
                                                              "type" : [ ]
                                                      },
                                                      "isUnique" : false,
                                                      "isSparse" : false,
                                                      "isPartial" : false,
                                                      "indexVersion" : 2,
                                                      "direction" : "forward",
                                                      "indexBounds" : {
                                                              "$_path" : [
                                                                      "[\"type\", \"type\"]",
                                                                      "[\"type.\", \"type/\")"
                                                              ],
                                                              "type" : [
                                                                      "[MinKey, MaxKey]"
                                                              ]
                                                      }
                                              }
                                      }
                              }
                      ]
              },
              "executionStats" : {
                      "executionSuccess" : true,
                      "nReturned" : 1901574,
                      "executionTimeMillis" : 3035,
                      "totalKeysExamined" : 1901574,
                      "totalDocsExamined" : 1901574,
                      "executionStages" : {
                              "stage" : "PROJECTION_SIMPLE",
                              "nReturned" : 1901574,
                              "executionTimeMillisEstimate" : 460,
                              "works" : 1901575,
                              "advanced" : 1901574,
                              "needTime" : 0,
                              "needYield" : 0,
                              "saveState" : 1901,
                              "restoreState" : 1901,
                              "isEOF" : 1,
                              "transformBy" : {
                                      "_id" : 0,
                                      "type" : 1
                              },
                              "inputStage" : {
                                      "stage" : "FETCH",
                                      "filter" : {
                                              "type" : {
                                                      "$exists" : true
                                              }
                                      },
                                      "nReturned" : 1901574,
                                      "executionTimeMillisEstimate" : 403,
                                      "works" : 1901575,
                                      "advanced" : 1901574,
                                      "needTime" : 0,
                                      "needYield" : 0,
                                      "saveState" : 1901,
                                      "restoreState" : 1901,
                                      "isEOF" : 1,
                                      "docsExamined" : 1901574,
                                      "alreadyHasObj" : 0,
                                      "inputStage" : {
                                              "stage" : "IXSCAN",
                                              "nReturned" : 1901574,
                                              "executionTimeMillisEstimate" : 141,
                                              "works" : 1901575,
                                              "advanced" : 1901574,
                                              "needTime" : 0,
                                              "needYield" : 0,
                                              "saveState" : 1901,
                                              "restoreState" : 1901,
                                              "isEOF" : 1,
                                              "keyPattern" : {
                                                      "type" : 1,
                                                      "customerReviewCount" : -1
                                              },
                                              "indexName" : "type_1_customerReviewCount_-1",
                                              "isMultiKey" : false,
                                              "multiKeyPaths" : {
                                                      "type" : [ ],
                                                      "customerReviewCount" : [ ]
                                              },
                                              "isUnique" : false,
                                              "isSparse" : false,
                                              "isPartial" : false,
                                              "indexVersion" : 2,
                                              "direction" : "forward",
                                              "indexBounds" : {
                                                      "type" : [
                                                              "[MinKey, MaxKey]"
                                                      ],
                                                      "customerReviewCount" : [
                                                              "[MaxKey, MinKey]"
                                                      ]
                                              },
                                              "keysExamined" : 1901574,
                                              "seeks" : 1,
                                              "dupsTested" : 0,
                                              "dupsDropped" : 0
                                      }
                              }
                      }
              },
              "command" : {
                      "find" : "products",
                      "filter" : {
                              "type" : {
                                      "$exists" : true
                              }
                      },
                      "projection" : {
                              "_id" : 0,
                              "type" : 1
                      },
                      "$db" : "bestbuy"
              },
              "serverInfo" : {
                      "host" : "ip-10-122-10-16",
                      "port" : 27017,
                      "version" : "4.9.0-alpha4-13-gbed3256",
                      "gitVersion" : "bed32560b4ef8df1eb6635c6d756119ab0e685a4"
              },
              "ok" : 1
      }
      

      Compare that to forcing a table scan:

      > db.products.explain('executionStats').find({type: {$exists:true}}, {_id:0, type: 1}).hint({$natural:1})
      {
              "explainVersion" : "1",
              "queryPlanner" : {
                      "namespace" : "bestbuy.products",
                      "indexFilterSet" : false,
                      "parsedQuery" : {
                              "type" : {
                                      "$exists" : true
                              }
                      },
                      "maxIndexedOrSolutionsReached" : false,
                      "maxIndexedAndSolutionsReached" : false,
                      "maxScansToExplodeReached" : false,
                      "winningPlan" : {
                              "stage" : "PROJECTION_SIMPLE",
                              "transformBy" : {
                                      "_id" : 0,
                                      "type" : 1
                              },
                              "inputStage" : {
                                      "stage" : "COLLSCAN",
                                      "filter" : {
                                              "type" : {
                                                      "$exists" : true
                                              }
                                      },
                                      "direction" : "forward"
                              }
                      },
                      "rejectedPlans" : [ ]
              },
              "executionStats" : {
                      "executionSuccess" : true,
                      "nReturned" : 1901574,
                      "executionTimeMillis" : 1454,
                      "totalKeysExamined" : 0,
                      "totalDocsExamined" : 1901574,
                      "executionStages" : {
                              "stage" : "PROJECTION_SIMPLE",
                              "nReturned" : 1901574,
                              "executionTimeMillisEstimate" : 135,
                              "works" : 1901576,
                              "advanced" : 1901574,
                              "needTime" : 1,
                              "needYield" : 0,
                              "saveState" : 1901,
                              "restoreState" : 1901,
                              "isEOF" : 1,
                              "transformBy" : {
                                      "_id" : 0,
                                      "type" : 1
                              },
                              "inputStage" : {
                                      "stage" : "COLLSCAN",
                                      "filter" : {
                                              "type" : {
                                                      "$exists" : true
                                              }
                                      },
                                      "nReturned" : 1901574,
                                      "executionTimeMillisEstimate" : 101,
                                      "works" : 1901576,
                                      "advanced" : 1901574,
                                      "needTime" : 1,
                                      "needYield" : 0,
                                      "saveState" : 1901,
                                      "restoreState" : 1901,
                                      "isEOF" : 1,
                                      "direction" : "forward",
                                      "docsExamined" : 1901574
                              }
                      }
              },
              "command" : {
                      "find" : "products",
                      "filter" : {
                              "type" : {
                                      "$exists" : true
                              }
                      },
                      "projection" : {
                              "_id" : 0,
                              "type" : 1
                      },
                      "hint" : {
                              "$natural" : 1
                      },
                      "$db" : "bestbuy"
              },
              "serverInfo" : {
                      "host" : "ip-10-122-10-16",
                      "port" : 27017,
                      "version" : "4.9.0-alpha4-13-gbed3256",
                      "gitVersion" : "bed32560b4ef8df1eb6635c6d756119ab0e685a4"
              },
              "ok" : 1
      }
      

      It takes 1.5s whereas using the index+fetch is 3s.

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            mathias@mongodb.com Mathias Stearn
            Votes:
            0 Vote for this issue
            Watchers:
            7 Start watching this issue

              Created:
              Updated: