[SERVER-80165] [CQF] Avoid temporary tree in CNF/DNF conversion Created: 16/Aug/23 Updated: 17/Aug/23 |
|
| Status: | Backlog |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Task | Priority: | Major - P3 |
| Reporter: | David Percy | Assignee: | Backlog - Query Optimization |
| Resolution: | Unresolved | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Assigned Teams: |
Query Optimization
|
| Participants: |
| Description |
|
Currently the way we implement conversion from CNF to DNF works by building up a tree in place, something like this:
These intermediate trees can't use a BoolExpr Builder because we both read and write them. It would be better to find a way to insert directly to a Builder, so we can eliminate trivial terms more eagerly, and allocate less. This multiplication of expressions is really just one way to enumerate combinations of atoms. Given the expression (a0+a1).(b0+b1).(c0+c1), we have 3 choices with 2 options each, so the final expression has 8 terms. Each term makes a different choice of a0 vs a1, b0 vs b1, etc. The current algorithm is like a breadth-first search: it's maintaining a set of 1-atom terms, then growing it to all 2-atom term, etc, until we have the final set of complete terms. We could use a depth-first search instead:
This would use a single temp vector, or vector of indices, because it only considers one combination at a time. |