[SERVER-71352] Investigate using linear builder-style compilation of EExpression Created: 14/Nov/22 Updated: 11/Jul/23 |
|
| Status: | Open |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Task | Priority: | Major - P3 |
| Reporter: | Anna Wawrzyniak | Assignee: | Backlog - Query Execution |
| Resolution: | Unresolved | Votes: | 0 |
| Labels: | pm2697-m4 | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||
| Assigned Teams: |
Query Execution
|
||||||||||||||||
| Sprint: | QE 2023-05-15, QE 2023-05-29, QE 2023-06-12, QE 2023-06-26, QE 2023-07-10 | ||||||||||||||||
| Participants: | |||||||||||||||||
| Story Points: | 10 | ||||||||||||||||
| Description |
|
Current compilation of EExpression that relies on following pattern:
this results in O(N*D) complexity, where N is size of expression and D is depth of tree.
Instead, use linear compilation that uses the following pattern:
in most cases to achieve O(N). In complex cases, the compileDirect may still allowed to use separate vm::CodeFragments if needed.
|
| Comments |
| Comment by David Storch [ 16/Mar/23 ] |
|
anna.wawrzyniak@mongodb.com we only have one more sprint remaining before we intend to wrap up the SBE perf project, so we thought it would make sense to have you take another look at this. There may not be time to implement it now, but perhaps you could figure out the complexity/estimate the potential perf benefits? |
| Comment by Mihai Andrei [ 15/Feb/23 ] |
|
Sending this to the backlog as this isn't critical to getting SBE shipped in 7.0. Also note that a solution like https://jira.mongodb.org/browse/SERVER-69774 would mitigate this entirely because caching the result of compilation would amortize the cost of compilation. |