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

Plans with differing performance can tie during plan ranking

    • Type: Icon: Bug Bug
    • Resolution: Done
    • Priority: Icon: Critical - P2 Critical - P2
    • 2.6.2, 2.7.1
    • Affects Version/s: 2.6.1, 2.7.0
    • Component/s: Querying
    • None
    • ALL

      Issue Status as of May 28, 2014

      ISSUE SUMMARY
      The query plan ranker chooses plans by "racing" them against each other and choosing the one that produces the most results in the least amount of work. When two or more query plans appear to be equally efficient, the query plan ranker chooses one plan arbitrarily and caches it for later use. This cached plan may be inefficient for subsequent queries using the same query shape but different values.

      For example, in a mailbox application with indexes on {sender: 1} and {status: 1}, and a query on {status: "unread", sender: "alice@example.com"} the plan for each of the two indices can return zero documents (assuming no unread emails and no emails from Alice), and therefore tie during plan ranking. If the plan ranker chooses to cache index {status: 1} for this query shape, a subsequent query for {status: "read", sender: "bob@example.com"} would scan through all read emails, a potentially very large number. The index on {sender: 1} is much more selective and would have only looked at emails from Bob, a much smaller subset of documents, making the query more efficient.

      USER IMPACT
      For collections with multiple indexes, depending on data distribution and choice of indexes, this bug may cause the wrong index to be cached and subsequently cause a scan of a large number of documents. For large data sets, this bug can have a serious impact on performance.

      There is a related issue, SERVER-14311, where an inferior plan may be picked for queries with potential impact on query performance.

      WORKAROUNDS
      Affected users are encouraged to use hint() to help the plan ranker choose the correct indexes. Alternatively, Index Filters can be set up to limit the choice of indexes for a given query shape.

      AFFECTED VERSIONS
      MongoDB production releases 2.6.0 and 2.6.1 are affected by this issue.

      FIX VERSION
      The fix is included in the 2.6.2 production release.

      RESOLUTION DETAILS
      Query plans are no longer cached if they tie in the query plan ranker.

      Original Description

      This is my query:

      {
      "type":"folder",
      "folder":/^((^|\/)[^\/\.][^\/]*)$/
      }

      As you can see the old mongo version took 4 seconds. The new version takes about 30 seconds. Sometimes on high server load it even takes a few minutes.

      2.4.x gave this explain:

      {
         "cursor": "BtreeCursor type_folder multi",
         "isMultiKey": false,
         "n": NumberInt(20),
         "nscannedObjects": NumberInt(20),
         "nscanned": NumberInt(2005419),
         "nscannedObjectsAllPlans": NumberInt(20),
         "nscannedAllPlans": NumberInt(2005419),
         "scanAndOrder": false,
         "indexOnly": false,
         "nYields": NumberInt(151),
         "nChunkSkips": NumberInt(0),
         "millis": NumberInt(4430),
         "indexBounds": {
           "type": [
             [
               "folder",
               "folder" 
            ] 
          ],
           "folder": [
             [
               "",
               [
                 
              ] 
            ],
             [
               "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
               "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
            ] 
          ] 
        },
         "allPlans": [
           {
             "cursor": "BtreeCursor type_folder multi",
             "n": NumberInt(20),
             "nscannedObjects": NumberInt(20),
             "nscanned": NumberInt(2005419),
             "indexBounds": {
               "type": [
                 [
                   "folder",
                   "folder" 
                ] 
              ],
               "folder": [
                 [
                   "",
                   [
                     
                  ] 
                ],
                 [
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
                ] 
              ] 
            } 
          } 
        ],
         "server": "kelvin:27017" 
      }
      

      2.6.0 gives this:

      {
         "cursor": "BtreeCursor type",
         "isMultiKey": false,
         "n": NumberInt(20),
         "nscannedObjects": NumberInt(2005419),
         "nscanned": NumberInt(2005419),
         "nscannedObjectsAllPlans": NumberInt(2005579),
         "nscannedAllPlans": NumberInt(14056061),
         "scanAndOrder": false,
         "indexOnly": false,
         "nYields": NumberInt(109671),
         "nChunkSkips": NumberInt(0),
         "millis": NumberInt(30821),
         "indexBounds": {
           "type": [
             [
               "folder",
               "folder" 
            ] 
          ] 
        },
         "allPlans": [
           {
             "cursor": "BtreeCursor type",
             "isMultiKey": false,
             "n": NumberInt(20),
             "nscannedObjects": NumberInt(2005419),
             "nscanned": NumberInt(2005419),
             "scanAndOrder": false,
             "indexOnly": false,
             "nChunkSkips": NumberInt(0),
             "indexBounds": {
               "type": [
                 [
                   "folder",
                   "folder" 
                ] 
              ] 
            } 
          },
           {
             "cursor": "BtreeCursor type_folder",
             "isMultiKey": false,
             "n": NumberInt(20),
             "nscannedObjects": NumberInt(20),
             "nscanned": NumberInt(2005419),
             "scanAndOrder": false,
             "indexOnly": false,
             "nChunkSkips": NumberInt(0),
             "indexBounds": {
               "type": [
                 [
                   "folder",
                   "folder" 
                ] 
              ],
               "folder": [
                 [
                   "",
                   [
                     
                  ] 
                ],
                 [
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
                ] 
              ] 
            } 
          },
           {
             "cursor": "BtreeCursor type_1_folder_1_geometry_2dsphere",
             "isMultiKey": false,
             "n": NumberInt(20),
             "nscannedObjects": NumberInt(20),
             "nscanned": NumberInt(2005419),
             "scanAndOrder": false,
             "indexOnly": false,
             "nChunkSkips": NumberInt(0),
             "indexBounds": {
               "type": [
                 [
                   "folder",
                   "folder" 
                ] 
              ],
               "folder": [
                 [
                   "",
                   [
                     
                  ] 
                ],
                 [
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
                ] 
              ],
               "geometry": [
                 [
                   {
                     "$minElement": NumberInt(1) 
                  },
                   {
                     "$maxElement": NumberInt(1) 
                  } 
                ] 
              ] 
            } 
          },
           {
             "cursor": "BtreeCursor folder_type_active",
             "isMultiKey": false,
             "n": NumberInt(20),
             "nscannedObjects": NumberInt(20),
             "nscanned": NumberInt(2023543),
             "scanAndOrder": false,
             "indexOnly": false,
             "nChunkSkips": NumberInt(0),
             "indexBounds": {
               "folder": [
                 [
                   "",
                   [
                     
                  ] 
                ],
                 [
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
                ] 
              ],
               "type": [
                 [
                   "folder",
                   "folder" 
                ] 
              ],
               "active": [
                 [
                   {
                     "$minElement": NumberInt(1) 
                  },
                   {
                     "$maxElement": NumberInt(1) 
                  } 
                ] 
              ] 
            } 
          },
           {
             "cursor": "BtreeCursor type_folder_timestamp_desc",
             "isMultiKey": false,
             "n": NumberInt(20),
             "nscannedObjects": NumberInt(20),
             "nscanned": NumberInt(2005419),
             "scanAndOrder": false,
             "indexOnly": false,
             "nChunkSkips": NumberInt(0),
             "indexBounds": {
               "type": [
                 [
                   "folder",
                   "folder" 
                ] 
              ],
               "folder": [
                 [
                   "",
                   [
                     
                  ] 
                ],
                 [
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
                ] 
              ],
               "timestamp": [
                 [
                   {
                     "$maxElement": NumberInt(1) 
                  },
                   {
                     "$minElement": NumberInt(1) 
                  } 
                ] 
              ] 
            } 
          },
           {
             "cursor": "BtreeCursor folder_filename_desc",
             "isMultiKey": false,
             "n": NumberInt(18),
             "nscannedObjects": NumberInt(78),
             "nscanned": NumberInt(2005421),
             "scanAndOrder": false,
             "indexOnly": false,
             "nChunkSkips": NumberInt(0),
             "indexBounds": {
               "folder": [
                 [
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
                ],
                 [
                   [
                     
                  ],
                   "" 
                ] 
              ],
               "filename": [
                 [
                   {
                     "$maxElement": NumberInt(1) 
                  },
                   {
                     "$minElement": NumberInt(1) 
                  } 
                ] 
              ] 
            } 
          },
           {
             "cursor": "BtreeCursor folder",
             "isMultiKey": false,
             "n": NumberInt(2),
             "nscannedObjects": NumberInt(2),
             "nscanned": NumberInt(2005421),
             "scanAndOrder": false,
             "indexOnly": false,
             "nChunkSkips": NumberInt(0),
             "indexBounds": {
               "folder": [
                 [
                   "",
                   [
                     
                  ] 
                ],
                 [
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/",
                   "/^((^|\\/)[^\\/\\.][^\\/]*)$/" 
                ] 
              ] 
            } 
          } 
        ],
         "server": "kelvin:27017",
         "filterSet": false,
         "stats": {
           "type": "KEEP_MUTATIONS",
           "works": NumberInt(2005421),
           "yields": NumberInt(109671),
           "unyields": NumberInt(109671),
           "invalidates": NumberInt(411),
           "advanced": NumberInt(20),
           "needTime": NumberInt(2005399),
           "needFetch": NumberInt(0),
           "isEOF": NumberInt(1),
           "children": [
             {
               "type": "FETCH",
               "works": NumberInt(2005420),
               "yields": NumberInt(109671),
               "unyields": NumberInt(109671),
               "invalidates": NumberInt(411),
               "advanced": NumberInt(20),
               "needTime": NumberInt(2005399),
               "needFetch": NumberInt(0),
               "isEOF": NumberInt(1),
               "alreadyHasObj": NumberInt(0),
               "forcedFetches": NumberInt(0),
               "matchTested": NumberInt(20),
               "children": [
                 {
                   "type": "IXSCAN",
                   "works": NumberInt(2005419),
                   "yields": NumberInt(109671),
                   "unyields": NumberInt(109671),
                   "invalidates": NumberInt(411),
                   "advanced": NumberInt(2005419),
                   "needTime": NumberInt(0),
                   "needFetch": NumberInt(0),
                   "isEOF": NumberInt(1),
                   "keyPattern": "{ type: 1 }",
                   "boundsVerbose": "field #0['type']: [\"folder\", \"folder\"]",
                   "isMultiKey": NumberInt(0),
                   "yieldMovedCursor": NumberInt(0),
                   "dupsTested": NumberInt(0),
                   "dupsDropped": NumberInt(0),
                   "seenInvalidated": NumberInt(0),
                   "matchTested": NumberInt(0),
                   "keysExamined": NumberInt(2005419),
                   "children": [
                     
                  ] 
                } 
              ] 
            } 
          ] 
        } 
      }
      

            Votes:
            1 Vote for this issue
            Watchers:
            23 Start watching this issue

              Created:
              Updated:
              Resolved: