[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:
Depends
depends on SERVER-71346 Add support for labels in vm::CodeFra... Closed
Related
related to SERVER-78587 Improve VM logicAnd/Or compileDirect ... Closed
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:

 

vm::CodeFragment compileDirect(CompileCtx& ctx) {
  vm::CodeFragment code;
  code.append ...
  return code;
}

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:

struct CompileCtx {
    vm::CodeFragment* code;
}; 
 
void compileDirect(CompileCtx& ctx) {
 ctx.code->append ...
}

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.

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