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

[CQF] Refactor PartialSchemaReqConverter to avoid quadratic behavior

    XMLWordPrintableJSON

Details

    • Icon: Improvement Improvement
    • Resolution: Duplicate
    • Icon: Major - P3 Major - P3
    • None
    • None
    • None
    • Query Optimization

    Description

      There are a few operations in PartialSchemaReqConverter that are unnecessarily quadratic on the number of PSR entries.

      #1
      This loop in intersectPartialSchemaReq iterates through every entry in the PSR DNF, looking for an existing requirement that meets the condition newKey.projectionName == existingReq.boundProjectionName. Instead of searching through the entire structure, PSR can hold a map of Requirement Bound Projection -> Atom Node::reference_type

      #2
      Every time we call add in intersectPartialSchemaReq, the PSR renormalizes, which involves resorting and deduplicating the entire structure. We could either normalize after converting to PSR, or insert into the structure in a way that keeps it in a normalized state. If the PSR is normalized later on in optimization, we could avoid normalizing altogether.

      These are the first solutions I thought of, it's possible a larger refactor might be more ideal.

      Attachments

        Activity

          People

            backlog-query-optimization Backlog - Query Optimization
            matt.boros@mongodb.com Matt Boros
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: