Details
-
Task
-
Status: Open
-
Major - P3
-
Resolution: Unresolved
-
None
-
None
-
None
-
Query Optimization
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
Attachments
Issue Links
- is related to
-
SERVER-76509 Enable booleanExpressionSimplifier flag for Bonsai integration tests
-
- Open
-
-
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-22857 eliminate redundant conditions/clauses from query
-
- Backlog
-
-
SERVER-35018 remove unnecessary FETCH from plan when fetch tests condition that's implied by indexed condition
-
- Backlog
-
-
SERVER-31360 MatchExpression::getOptimizer() for $or/$and should collapse equivalent clauses
-
- Backlog
-
- split to
-
SERVER-77343 Boolean simplification benchmark
-
- Open
-
-
SERVER-81139 Stop Boolean expression simplification if it explodes the expression in size
-
- Open
-
-
SERVER-76939 Implement Quine-McCluskey algorithm
-
- Closed
-
-
SERVER-76940 Implement Petrick's method
-
- 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
-