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

[CQF] Eliminate PathArr, given Traverse PathArr

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: None
    • Query Optimization
    • QO 2024-02-05, QO 2024-02-19, QO 2024-03-04, QO 2024-03-18, QO 2024-04-01

      If we have a predicate like (ComposeM PathArr (Traverse PathArr)), we should simplify it to just (Traverse PathArr). Traverse means "is or contains", so if a value "is-or-contains an array" then it must be an array. We can remove PathArr because it's implied by (Traverse PathArr).

      This will allow more predicates to be covered by an index.

      For example, here is a query that would benefit:

      db.c.find({a: {$elemMatch: {$elemMatch: {$eq: 2}}}})
      

      In other words: 'a' is an array, which contains an array, which contains 2.

      It becomes this ABT:

      Get a
      ComposeM
      |   PathArr
      Traverse
      ComposeM
      |   PathArr
      Traverse
      PathCompare Eq 2
      

      After relaxing the predicates we get this Sargable node:

      Get a Identity -> [ [], BinData )   # 'a' is an array
      Get a Traverse Identity -> [ [], BinData )  # 'a' is-or-contains an array
      Get a Traverse Traverse Identity -> [ 2, 2 ]  # 'a' is-or-contains something which is-or-contains 2
      

      A multikey index on {a: 1} can cover the second and third predicates, but not the first. But the second predicate implies the first, so we should just drop the first predicate, or mark it perfOnly.

      Index path: Get "a" Traverse id.

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            david.percy@mongodb.com David Percy
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated: