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

Generated at Thu Feb 08 06:50:14 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.