[SERVER-82773] Use only inclusive bounds for intervals in the optimizer Created: 03/Nov/23 Updated: 09/Nov/23 |
|
| Status: | Backlog |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Task | Priority: | Major - P3 |
| Reporter: | William Qian | Assignee: | Backlog - Query Optimization |
| Resolution: | Unresolved | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Assigned Teams: |
Query Optimization
|
| Participants: |
| Description |
|
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)]. |
| Comments |
| Comment by William Qian [ 06/Nov/23 ] |
|
Let's keep it open for now until we decide whether/when/how to address this. Otherwise, we'll probably just forget. |
| Comment by Matt Boros [ 06/Nov/23 ] |
|
Agreed, should this be closed then? |
| Comment by William Qian [ 06/Nov/23 ] |
|
Oops yes those are meant to be intersections. Thanks for catching that. It's likely that this would be an optimization that works only for certain types. But since numbers and strings are incredibly common, this could still be fairly useful. Svilen's suggestion of parameterizing inclusivity and exclusivity would resolve this concern better. |
| Comment by Matt Boros [ 06/Nov/23 ] |
|
Would this require a way to increment or decrement a BSON value? How would we decrement BSON empty array [] for example, which would be a BSON object.
The union example isn't completely accurate because unioning needs two primary intervals in case the input intervals don't overlap. So it'd be primary1 U primary2 U aux1 U aux2. If we make it intersection it would make sense to me. |
| Comment by William Qian [ 06/Nov/23 ] |
|
An alternative suggested by svilen.mihaylov@mongodb.com is parameterized inclusion/exclusion. |