Avoid quadratic complexity in MatchProcessor Document->BSON conversion

XMLWordPrintableJSON

    • Type: Improvement
    • Resolution: Fixed
    • Priority: Major - P3
    • 8.2.0-rc0
    • Affects Version/s: None
    • Component/s: Query Execution
    • None
    • Query Execution
    • Fully Compatible
    • QE 2025-06-09
    • 0
    • None
    • 3
    • TBD
    • None
    • None
    • None
    • None
    • None
    • None
    • None
    • 0

      document_path_support::documentToBsonWithPaths(...) can have asymptotic quadratic runtime complexity:

      void documentToBsonWithPaths(const Document& input,
                                   const OrderedPathSet& paths,
                                   BSONObjBuilder* builder) {
          for (auto&& path : paths) {
              // getNestedField does not handle dotted paths correctly, so instead of retrieving the
              // entire path, we just extract the first element of the path.
              const auto prefix = FieldPath::extractFirstFieldFromDottedPath(path);
              if (!builder->hasField(prefix)) {
                  // Avoid adding the same prefix twice.
                  input.getField(prefix).addToBsonObj(builder, prefix);
              }
          }
      }
      

      The for loop iterates over all values in the paths set, and calls the BSONObjBuilder::hasField(...) function for all of them. That latter function iterates over all fields in the BSONObj until it either finds a field with the same name or iteration reaches the end. But if all items from paths are added to the BSONObjBuilder and all paths are unique, this will have number of paths * number of paths complexity.

      While a complete fix is not trivial, we can perform an optimization in case documentToBsonWithPaths is called with an initially empty BSONObjBuilder and we can guarantee that all paths have unique prefixes.

            Assignee:
            Jan Steemann
            Reporter:
            Jan Steemann
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated:
              Resolved: