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

Remove nested loop joins from $Filter.limit SBE traverse stage

    XMLWordPrintableJSON

Details

    • Icon: Improvement Improvement
    • Resolution: Unresolved
    • Icon: Major - P3 Major - P3
    • None
    • None
    • None
    • None
    • Query Execution

    Description

      Solution proposed by Anton:

      Data flow for this expression can be presented as follows:

      <main-tree>
      This is the eval frame sitting on top of the evalStack when we start processing the $filter expression. This <main-tree> is used as an input to the entire expression (the input argument). So, the input argument can be evaluated on the same eval frame.

      <cond-tree>
      Implements a filter predicate. It needs to be evaluated in its own frame since the evaluation should diverge from the main data flow - that is, for each element in an input array we will have to execute this <cond-tree>, so the array element will become the input to this tree.

      So, putting it together we have:

      traverse inSlot outSlot innerSlot
      from
      project inSlot = <something>
      <main-tree>
      in
      <cond-tree>
      Now, lets add the limit argument. It can be a complex expression on its own, but its evaluation doesn't change the data flow. What I mean by that is, we don't have to short-circuit while evaluating the limit argument, and we don't have to create a new evaluation context like we do for the cond argument. We can simply evaluate it sequentially right after the input argument. In other words, it can be evaluated on the same eval frame as the input argument itself.

      traverse inSlot outSlot innerSlot {}

      {getArraySize(outSlot) >= limitSlot}

      from
      project limitSlot = <something>
      <limit-tree>
      project inSlot = <something>
      <main-tree>
      in
      <cond-tree>
      Now, there is one caveat here.

      The limit argument is being processed last, after the cond argument. The latter adds its own eval frame on the eval stack, so limit expressions would be evaluated against the <cond-tree> frame rather than <main-tree>. To deal with it we will have to pop the <cond-tree> frame off the stack (in in-visitor) and store it in FilterExprFrame, process limit against the main-tree frame, and then in $filter post-visitor grab the cond frame form theFilterExprFrame, rather than from the eval frame.

      Of course this all can be avoided if we evaluate the cond argument last, but I absolutely don't want to change the order of the $filter arguments depending on the presence of this optional limit. Optionals should always go last.

      Attachments

        Activity

          People

            backlog-query-execution Backlog - Query Execution
            maddie.zechar@mongodb.com Maddie Zechar
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

              Created:
              Updated: