[SERVER-71656] [CQF] Intersection of DNF intervals can be incorrect Created: 28/Nov/22  Updated: 29/Oct/23  Resolved: 09/Jan/23

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 6.3.0-rc0

Type: Bug Priority: Major - P3
Reporter: Matt Boros Assignee: Matt Boros
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Assigned Teams:
Query Optimization
Backwards Compatibility: Fully Compatible
Operating System: ALL
Sprint: QO 2023-01-09, QO 2023-01-23
Participants:

 Description   

Intersecting DNF intervals can sometimes lead to less strict bounds than expected. If we call intersectDNFIntervals with the following:

{
    {
        {=Variable [a]}
     ^ 
        {(Variable [b], Variable [c])}
    }
}

The result** is

{
    {
        [b >= a ? MaxKey : a, min(max(a,b), min(a,c))]
    }
 U 
    {
        [max(max(a,b), min(a,c)), c <= a ? MinKey : a]
    }
 U 
    {
        (max(a,b), min(a,c))
    }
}

If we have a=3, b=0, and c=3 then our original interval is [3,3] ^ (0, 3) = nothing. The result from intersectDNFIntervals is

{
    {
        [3, 3]
    }
 U 
    {
        nothing
    }
 U 
    {
        nothing
    }
}

which is [3,3]. This error seems to come from an auxiliary interval.

**
In reality the explain printed out is below, but its hard to read so I decoded it into min/max and ternary

{
    {
        {[(If  [] BinaryOp [Gte] Variable [b] Variable [a] Const [maxKey] Variable [a] ), (If  [] BinaryOp [Lte] (If  [] BinaryOp [Gte] Variable [a] Variable [b] Variable [a] Variable [b] ) (If  [] BinaryOp [Lte] Variable [a] Variable [c] Variable [a] Variable [c] ) (If  [] BinaryOp [Gte] Variable [a] Variable [b] Variable [a] Variable [b] ) (If  [] BinaryOp [Lte] Variable [a] Variable [c] Variable [a] Variable [c] ) )]}
    }
 U 
    {
        {[(If  [] BinaryOp [Gte] (If  [] BinaryOp [Gte] Variable [a] Variable [b] Variable [a] Variable [b] ) (If  [] BinaryOp [Lte] Variable [a] Variable [c] Variable [a] Variable [c] ) (If  [] BinaryOp [Gte] Variable [a] Variable [b] Variable [a] Variable [b] ) (If  [] BinaryOp [Lte] Variable [a] Variable [c] Variable [a] Variable [c] ) ), (If  [] BinaryOp [Lte] Variable [c] Variable [a] Const [minKey] Variable [a] )]}
    }
 U 
    {
        {((If  [] BinaryOp [Gte] Variable [a] Variable [b] Variable [a] Variable [b] ), (If  [] BinaryOp [Lte] Variable [a] Variable [c] Variable [a] Variable [c] ))}
    }
}



 Comments   
Comment by Githook User [ 09/Jan/23 ]

Author:

{'name': 'Matt Boros', 'email': 'matt.boros@mongodb.com', 'username': 'mattBoros'}

Message: SERVER-71656 Add additional conditions to auxiliary intervals during interval intersection
Branch: master
https://github.com/mongodb/mongo/commit/4a307daa1f6af15a48d8e12b38e10f16dec9664d

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