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

      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
      |   PathArr
      |   PathArr
      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.

            backlog-query-optimization Backlog - Query Optimization
            david.percy@mongodb.com David Percy
            0 Vote for this issue
            3 Start watching this issue