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

Index bounds in backward direction causes unionize to fail in collapseQuerySolution

    • Type: Icon: Bug Bug
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • 8.1.0-rc0
    • Affects Version/s: None
    • Component/s: None
    • Query Optimization
    • Fully Compatible
    • ALL
    • v8.0
    • QO 2024-10-14

      Reproduction

      The issue can be reproduced locally with unit test. The shard key pattern in the incident was {_userId: 1, type: 1, time: 1}.

      To reproduce:

      Root Cause

      The user's query requests sorting by

      {time: -1}

      , resulting in an index bounds in backward direction. See a simplified query plan:

      "winningPlan" : {
        "stage" : "LIMIT",
        "limitAmount" : 1,
        "inputStage" : {
          "stage" : "FETCH",
          "inputStage" : {
            "stage" : "SORT_MERGE",
            "sortPattern" : { "time" : -1 },
            "inputStages" : [
              {
                "stage" : "IXSCAN",
                "direction" : "backward",
                "indexBounds" : {
                  "_userId" : [
                    "[\"6ba576a-1139-407e-8f6b-11c3967c7fb2\", \"6ba576a-1139-407e-8f6b-11c3967c7fb2\"]"
                  ],
                  "type" : [
                    "[\"cbg\", \"cbg\"]"
                  ],
                  "time" : [
                    "[new Date(1665051622688), new Date(1664965222688)]"
                  ]
                }
              },
              {
                "stage" : "IXSCAN",
                "direction" : "backward",
                "indexBounds" : {
                  "_userId" : [
                    "[\"6ba576a-1139-407e-8f6b-11c3967c7fb2\", \"6ba576a-1139-407e-8f6b-11c3967c7fb2\"]"
                  ],
                  "type" : [
                    "[\"smbg\", \"smbg\"]"
                  ],
                  "time" : [
                    "[new Date(1665051622688), new Date(1664965222688)]"
                  ]
              }
             ]
          }
        }
      }
      

      collapseQuerySolution() assumes the IndexBounds is always ascending and attempts to unionize() them without forwardizing them. In a debug build, such a issue should have violated an invariant check in intersects() but not in a release build. So we only see this issue until it tripped the invariant check in unionize().

      Plan of Attack

      Forwardizing before unionizing them may address the bug. In the other call sites, the direction of index bounds evolves as below:

      1. IndexBoundsBuilder builds IndexBounds in ascending direction
      2. QueryPlannerAccess::finishLeadNode aligns IndexBounds with key pattern. The direction becomes forward. But it may have intervals in descending order.
      3. QueryPlannerAccess::buildIndexedOr may reverse the direction to backward.

      Since: a shard key pattern is always ascending, we may rely on the direction of a IXSCAN node to tell if we need to reverse the index bound in collapseQuerySolution.

            Assignee:
            chii.huang@mongodb.com Chi-I Huang
            Reporter:
            chii.huang@mongodb.com Chi-I Huang
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated:
              Resolved: