-
Type: Task
-
Resolution: Fixed
-
Priority: Major - P3
-
Affects Version/s: None
-
Component/s: None
-
Query Optimization
-
Fully Compatible
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
- duplicates
-
SERVER-22857 eliminate redundant conditions/clauses from query
- Closed
-
SERVER-31360 MatchExpression::getOptimizer() for $or/$and should collapse equivalent clauses
- Closed
- is related to
-
SERVER-76509 Enable booleanExpressionSimplifier flag for Bonsai integration tests
- Closed
-
SERVER-74879 [CQF] Boolean minimization for BoolExpr based on Quine-McCluskey simplification
- Open
- related to
-
SERVER-60373 Duplicate predicates in query plan for time-series collection
- Closed
-
SERVER-78962 Check on feasibility to perform boolean simplification before parameterization
- Backlog
-
SERVER-35018 remove unnecessary FETCH from plan when fetch tests condition that's implied by indexed condition
- Backlog
-
SERVER-22857 eliminate redundant conditions/clauses from query
- Closed
-
SERVER-31360 MatchExpression::getOptimizer() for $or/$and should collapse equivalent clauses
- Closed
- split to
-
SERVER-81608 Enable fuzzer testing of boolean simplifier
- Backlog
-
SERVER-81788 Optimize $elemMatch in the Boolean expression simplifier
- Backlog
-
SERVER-81792 Optimize $exists and $ne: null in the boolean expression simplifier
- Backlog
-
SERVER-81846 Enable the Boolean Expression Simplifier in change streams
- Backlog
-
SERVER-81847 Enable the boolean expression simplifier for index partial filters
- Backlog
-
SERVER-82076 Remove enableSimplification flag from MatchExpression flags
- Backlog
-
SERVER-82284 Factorize special index predicates in the simplifier
- Backlog
-
SERVER-82350 Consider moving MatchExpressions instead of always cloning them
- Backlog
-
SERVER-76939 Implement Quine-McCluskey algorithm
- Closed
-
SERVER-76940 Implement Petrick's method
- Closed
-
SERVER-77343 Boolean simplification benchmark
- Closed
-
SERVER-77470 Optimize the Petrick's method implementation.
- Closed
-
SERVER-77670 Implement DNF converter for boolean expressions
- Closed
-
SERVER-79018 Implement MatchExpression hasher
- Closed
-
SERVER-79314 Implement additional pipeline Expression unit tests
- Closed
-
SERVER-81139 Stop Boolean expression simplification if it explodes the expression in size
- Closed
-
SERVER-81630 Enable Boolean expression simplifier
- Closed
-
SERVER-82176 Implement effective dynamic bitset for the boolean simplifier
- Closed