[SERVER-75079] Simplify boolean expressions before feeding them to the optimizer Created: 21/Mar/23  Updated: 19/Dec/23  Resolved: 01/Dec/23

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

Type: Task Priority: Major - P3
Reporter: Alexander Ignatyev Assignee: Alexander Ignatyev
Resolution: Fixed Votes: 0
Labels: query-product-scope-2, query-product-urgency-1, query-product-value-1
Σ Remaining Estimate: Not Specified Remaining Estimate: Not Specified
Σ Time Spent: Not Specified Time Spent: Not Specified
Σ Original Estimate: Not Specified Original Estimate: Not Specified

Issue Links:
Duplicate
duplicates SERVER-22857 eliminate redundant conditions/clause... Closed
duplicates SERVER-31360 MatchExpression::getOptimizer() for $... Closed
Issue split
split to SERVER-81608 Enable fuzzer testing of boolean simp... Backlog
split to SERVER-81788 Optimize $elemMatch in the Boolean ex... Backlog
split to SERVER-81792 Optimize $exists and $ne: null in the... Backlog
split to SERVER-81846 Enable the Boolean Expression Simplif... Backlog
split to SERVER-81847 Enable the boolean expression simplif... Backlog
split to SERVER-82076 Remove enableSimplification flag from... Backlog
split to SERVER-82284 Factorize special index predicates in... Backlog
split to SERVER-82350 Consider moving MatchExpressions inst... Backlog
split to SERVER-76939 Implement Quine-McCluskey algorithm Closed
split to SERVER-76940 Implement Petrick's method Closed
split to SERVER-77343 Boolean simplification benchmark Closed
split to SERVER-77470 Optimize the Petrick's method impleme... Closed
split to SERVER-77670 Implement DNF converter for boolean e... Closed
split to SERVER-79018 Implement MatchExpression hasher Closed
split to SERVER-79314 Implement additional pipeline Express... Closed
split to SERVER-81139 Stop Boolean expression simplificatio... Closed
split to SERVER-81630 Enable Boolean expression simplifier Closed
split to SERVER-82176 Implement effective dynamic bitset fo... Closed
Related
related to SERVER-60373 Duplicate predicates in query plan fo... Closed
related to SERVER-78962 Check on feasibility to perform boole... Backlog
related to SERVER-35018 remove unnecessary FETCH from plan wh... Backlog
related to SERVER-22857 eliminate redundant conditions/clause... Closed
related to SERVER-31360 MatchExpression::getOptimizer() for $... Closed
is related to SERVER-76509 Enable booleanExpressionSimplifier fl... Closed
is related to SERVER-74879 [CQF] Boolean minimization for BoolEx... Open
Sub-Tasks:
Key
Summary
Type
Status
Assignee
SERVER-76938 Implement Quine-McCluskey algorithm Sub-task Closed Alexander Ignatyev  
Assigned Teams:
Query Optimization
Backwards Compatibility: Fully Compatible
Participants:

 Description   

As a part of a Skunkworks project we implemented a Boolean expression simplifier which demonstrated good results on some non-trivial Boolean expressions.

For example,
given the following indexes: {d: 1, b: 1}, {a: 1}

and the following query

{
    '$and': [
        {b: 0},
        {
            '$or': [
                {a: 0},
                {
                    '$and': [
                        {c: {'$in': [34, 45]}},
                        {c: {'$nin': [34, 45]}},
                    ]
                }
            ]
        },
    ]
};

the optimizer chose a full collection scan plan.

The boolean expression simplifier can simplify this filter just to the following one:

{a: 0, b: 0}

given this filter the optimizer chose much more effective index scan on {a: 1} plan.

The proposed in the Skunkworks project implementation does not depend on any optimizer and can be used for the classic one as well for the Bonsai. This ticket proposes to add the simplification for the classic optimizer. Then we can reuse the implementation of this ticket for the Bonsai: https://jira.mongodb.org/browse/SERVER-74879



 Comments   
Comment by Xiaochen Wu [ 13/Jul/23 ]

alexander.ignatyev@mongodb.com 

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