[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:
Depends
depends on SERVER-73827 [CQF] Extend BoolExpr builder to acce... Closed
depends on SERVER-73828 [CQF] Extend BoolExpr visitConjuncts/... Closed
Related
related to SERVER-73827 [CQF] Extend BoolExpr builder to acce... Closed
related to SERVER-75079 Simplify boolean expressions before f... Closed
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 
SERVER-73827



 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 SERVER-75079.

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?

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