[SERVER-74879] [CQF] Boolean minimization for BoolExpr based on Quine-McCluskey simplification Created: 15/Mar/23 Updated: 16/Aug/23 |
|
| Status: | Open |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | Svilen Mihaylov (Inactive) | Assignee: | Backlog - Query Optimization |
| Resolution: | Unresolved | Votes: | 0 |
| Labels: | bonsai-onboarding, plan-quality | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||||||||||
| Assigned Teams: |
Query Optimization
|
||||||||||||||||||||||||
| Participants: | |||||||||||||||||||||||||
| Description |
|
Implement a boolean expression minimizer for bool expr trees. One way to achieve that is to minimize a bool expr tree when it is constructed by the builder (say when .finish() is called). This will allow a more optimal and minimized representation of the boolean tree, which may not conform neither to DNF nor CNF. This can be used to support more efficient index and fetch rewrites.
Note this is a more general version of the "local" simplification to be achieved via |
| Comments |
| Comment by Steve Tarzia [ 05/May/23 ] |
|
Note that we should not proceed with work here until we discuss and understand the overlap with the in-flight work in |
| Comment by Timour Katchaounov [ 21/Mar/23 ] |
|
Svilen, could you please clarify - is this Jira about implementing a simplification for the cases covered by the Quine–McCluskey algorithm? If no, then what it is about exactly? If yes, then why not reuse the implementation from the above Skunkworks project. Is there a design that describes the simplifications envisioned here? |