[SERVER-79403] Avoid implementing stacks of EvaluationNode as stacks of SBE project operators Created: 27/Jul/23  Updated: 08/Dec/23  Resolved: 08/Dec/23

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 7.3.0-rc0

Type: Improvement Priority: Major - P3
Reporter: Anton Korshunov Assignee: Milena Ivanova
Resolution: Fixed Votes: 0
Labels: M2
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
is duplicated by SERVER-72681 Investigate perf of new optimizer pla... Closed
Related
is related to SERVER-79012 Push top-level field extraction into ... Closed
Assigned Teams:
Query Optimization
Backwards Compatibility: Fully Compatible
Sprint: QO 2023-09-04, QO 2023-09-18, QO 2023-10-02, QO 2023-10-16, QO 2023-10-30, QO 2023-11-13, QO 2023-11-27, QO 2023-12-11
Participants:

 Description   

Currently in Bonsai each projection is implemented as a separate EvaluationNode. We have an existing optimisation which tries to convert each projection into a SargableNode, and push it down into collection/index scan. However, if the projections contains residual expressions, we may end up with a physical plan containing a stack of EvaluationNodes, which eventually will be lowered into a stack of SBE project operators. We will need to investigate performance overhead of having a stack of projections in an SBE plan and try to optimize it by merging the EvalNodes into a single evaluation node (a new type of an ABT node) with combined projections.



 Comments   
Comment by Githook User [ 07/Dec/23 ]

Author:

{'name': 'Milena Ivanova', 'email': 'milena.ivanova@mongodb.com', 'username': 'mivanova3'}

Message: SERVER-79403 Merge independent evaluation nodes into single sbe project stage

GitOrigin-RevId: 8c6086c3dc36dc1228db74a42897f7d6bf196fcf
Branch: master
https://github.com/mongodb/mongo/commit/c91bf1a47caa8f3ae34ce7b7e3bb0f381007101a

Comment by Milena Ivanova [ 24/Nov/23 ]

Local tests with mongo-perf, measurement ops_per_sec:

Test query Master Bonsai MergeEval Bonsai Improvement %
Queries.ProjectNoExpressions_CollScan_LS 2.2073 2.2352 1.2
Queries.ProjectNoExpressions_CollScan_LL 1.7816 1.8373 3.1
Queries.ProjectNoExpressions_CollScan_LLR 3.7253 3.8125 2.3

 

Comment by Milena Ivanova [ 26/Oct/23 ]

Performance of the prototype implementing the physical MultiEvalNode and a post-memo rewrite, master branch from 24.10:

1M collection MultiEval
time(ms)
Master
time(ms)
Improvement
(ms)
1 projection 1143 1234 89
2 projections 1605 1685 80
3 projections 2097 2231 134
4 projections 2628 2759 131

Using the executionTimeMillisEstimate measurement for each SBE stage, the measured times only for projection stages are as follows:
 

1M collection MultiEval
time(ms)
Master
time(ms)
Improvement
(ms)
1 projection 9 9 0
2 projections 25 32 7
3 projections 36 42 6
4 projections 67 79 12

Notice, that the overall improvement of the query execution time in the prototype is bigger than the improvement seen only in the merged projection stages.

Comment by Milena Ivanova [ 22/Aug/23 ]

As a first step of this task I ran a benchmark evaluation comparing a stack of SBE projection stages as currently created from Bonsai with a single SBE projection combining the computation of the same expressions.

  • The benchmark used collections with documents with multiple nested fields:

{_id: i, a: { b: i * 5, c: "xx", d: 1.234}, k: {l: "LLL", m:"MMM"}, x: {y: {z: "xyz".repeat(3)}}, p: { q: 5, r: 4.567}}

The collection sizes were 10K, 100K, and 1M documents.

  • Queries:

Q1. db.coll.find({}, {f1: "$a.b", f2: “$k.l” })

Q2. db.coll.find({}, {f1: "$a.b", f2: “$k.l”, f3: “$p.q"})

Q3. db.coll.find({}, {f1: "$a.b", f2: “$k.l”, f3: “$p.q”, f4: “$x.y"})

  • Query plans for Q2:

Current Bonsai:

 

[4] project [s9 =
    let [ …
]
[3] project [s8 = traverseP(s5, lambda(l101.0) { getField(move(l101.0), "q") }, Nothing)]
[2] project [s7 = traverseP(s4, lambda(l101.0) { getField(move(l101.0), "l") }, Nothing)]
[1] project [s6 = traverseP(s3, lambda(l101.0) { getField(move(l101.0), "b") }, Nothing)]
[0] scan s2 none none none none none none none lowPriority [s3 = a, s4 = k, s5 = p] @"0d8e75b3-1b15-4b9f-b56b-0be56f463e11" true false

 

 

Modified query plan with a projection stage with multiple expressions:

 

[4] project [s9 =
    let [ …
]
[1] project [s6 = traverseP(s3, lambda(l101.0) { getField(move(l101.0), "b") }, Nothing), s7 = traverseP(s4, lambda(l101.0) { getField(move(l101.0), "l") }, Nothing), s8 = traverseP(s5, lambda(l101.0) { getField(move(l101.0), "q") }, Nothing)]
[0] scan s2 none none none none none none none lowPriority [s3 = a, s4 = k, s5 = p] @"0d8e75b3-1b15-4b9f-b56b-0be56f463e11" true false

 

 

Each query was run 12 times and the average time taken excluding the the smallest and the largest values.

The projection time excludes the top-level projection with the let expression and considers only projections extracting the subfields.

100K documents collection Average Exec Time (ms) Stage times (ms) Projection time (ms) Improvement
Q1. Bonsai 170 Project0 149            
Project1 55                
Project2 41               
Scan 35
20  
Bonsai with combined projections 162 Project0 135          
Project1 44                    
Scan 31
13 7
Q2. Bonsai 221 Project0 200
Project1 64
Project2 53
Project3 43
Scan 37
27  
Q2. Bonsai with combined projections 211 Project0 187
Project1 52
Scan 30
22 5
Q3. Bonsai 279 Project0 254                                            
Project1 86                                           
Project2 71                                             
Project3 58   
Project4 54    
Scan 42
44  
Q3. Bonsai with combined projections 264 Project0 232                                                 
Project1 66                                               
Scan 39
27 17

 

1M documents collection Average Exec Time (ms) Stage times (ms) Projection time (ms) Improvement
Q1. Bonsai 1695 Project0 1517         
Project1 549            
Project2 442   
Scan 380
169  
Bonsai with combined projections 1659 Project0 1470                                               
Project1 531              
Scan 380
151 18
Q2. Bonsai 2191 Project0 1984
Project1 639
Project2 559
Project3 469
Scan 399
240  
Q2. Bonsai with combined projections 2185 Project0 1994
Project1 634
Scan 404
230 10
Q3. Bonsai 2765 Project0 2548             
Project1 756              
Project2 672                 
Project3 590               
Project4 480          
Scan 391
365  
Q3. Bonsai with combined projections 2744 Project0 2514           
Project1 708  
Scan 413
295 70
Generated at Thu Feb 08 06:40:53 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.