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

Use only inclusive bounds for intervals in the optimizer

    • Type: Icon: Task Task
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: None
    • None
    • Query Optimization

      An intersecting bound is currently optimized by rewriting the intersection as only the overlapping interval. For example, [1, 5][2, 6] => [2, 5].

      When variables are involved, this gets trickier, especially if there's a mix of open (exclusive) and closed (inclusive) bounds. For example, [a, b] ∧ (c, d). We end up representing this as something like (max(a, c), min(b, d)) U aux(a) U aux(b), where the aux are just point-intervals to represent inclusion for when a > c or b < d.

      Using aux values results in a complex-looking query. Instead, we should consider normalizing all bounds to one type of bound. Since our universes are finite, it makes sense to normalize on closed bounds, and convert all open bounds into closed bounds. For example, using e to represent "epsilon," the above intersection can be written as [max(a, c+e), min(b, d-e)].

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            william.qian@mongodb.com William Qian
            Votes:
            0 Vote for this issue
            Watchers:
            9 Start watching this issue

              Created:
              Updated: