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

Improve $project parsing to avoid quadratic behavior

    • Type: Icon: Improvement Improvement
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • 7.1.0-rc0
    • Affects Version/s: None
    • Component/s: None
    • None
    • Query Optimization
    • Fully Compatible
    • QE 2023-07-24, QE 2023-08-07, QE 2023-08-21
    • 35

      ProjectionPathASTNode getChild performs a linear search through a vector of field names to find the correct child. Because of this search, we see n^2 behavior on the number of fields in the $project. As we add children to this node in addNodeAtPathHelper, we also call getChild to search through everything we've added so far.

      ProjectionPathASTNode could use a map instead of a vector to avoid this behavior.

      This ticket should also involve performance testing with a map. If we see a regression, we could consider using a map when there are >50 (or some N) elements.

        1. screenshot-1.png
          screenshot-1.png
          34 kB
        2. figure_with_fix.png
          figure_with_fix.png
          32 kB

            Assignee:
            matt.boros@mongodb.com Matt Boros
            Reporter:
            matt.boros@mongodb.com Matt Boros
            Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

              Created:
              Updated:
              Resolved: