[SERVER-78354] [CQF] Implement transport infrastructure using iteration rather than recursion Created: 22/Jun/23  Updated: 13/Nov/23  Resolved: 26/Sep/23

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

Type: Task Priority: Major - P3
Reporter: Matt Boros Assignee: David Percy
Resolution: Fixed Votes: 0
Labels: auto-reverted
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
depends on SERVER-78353 [CQF] Investigate reference tracker s... Closed
Problem/Incident
Related
is related to SERVER-83191 Make algebra::transport faster Open
Assigned Teams:
Query Optimization
Backwards Compatibility: Fully Compatible
Sprint: QO 2023-09-04, QO 2023-09-18, QO 2023-10-02
Participants:
Linked BF Score: 105

 Description   

SERVER-78353 describes a stack overflow in the reference tracker, due to the transport infrastructure recursively navigating a deep tree. One solution to this problem would be to make the transport code iterative rather than recursive, using an explicit stack to walk the tree. This should not require any changes to code that uses the transport infrastructure. I expect only operator.h will change.

This is also expected to improve reference tracker performance.



 Comments   
Comment by Githook User [ 26/Sep/23 ]

Author:

{'name': 'David Percy', 'email': 'david.percy@mongodb.com', 'username': 'dpercy'}

Message: SERVER-78354 Implement algebra::transport with iteration and explicit stacks

Changes the implementation of algebra::transport to use an explicit
stack (a vector) to visit each node in a PolyValue / Operator tree,
and another stack to hold each child node's result.

The goal is to handle trees of any depth, not limited by the size of the
call stack. Putting the explicit stacks in the implementation of
algebra::transport means you can still think recursively when writing a
particular transporter.
Branch: master
https://github.com/mongodb/mongo/commit/9d8a2ff53a7592ca2a3e416dca577905d4d941b8

Comment by xgen-buildbaron-user [ 21/Sep/23 ]

Ticket re-opened due to revert. stitch_support_create_lib began a consistent failure of stitch_support_create_lib

Comment by Githook User [ 21/Sep/23 ]

Author:

{'name': 'auto-revert-processor', 'email': 'dev-prod-dag@mongodb.com', 'username': ''}

Message: Revert "SERVER-78354 Implement algebra::transport with iteration and explicit stacks"

This reverts commit 6483fb8378cb2130160a1acfa46d5d50bac27dfc.
Branch: master
https://github.com/mongodb/mongo/commit/be6b22a285da9fa4f689cd75994bded2000e793e

Comment by Githook User [ 21/Sep/23 ]

Author:

{'name': 'David Percy', 'email': 'david.percy@mongodb.com', 'username': 'dpercy'}

Message: SERVER-78354 Implement algebra::transport with iteration and explicit stacks

Changes the implementation of algebra::transport to use an explicit
stack (a vector) to visit each node in a PolyValue / Operator tree,
and another stack to hold each child node's result.

The goal is to handle trees of any depth, not limited by the size of the
call stack. Putting the explicit stacks in the implementation of
algebra::transport means you can still think recursively when writing a
particular transporter.
Branch: master
https://github.com/mongodb/mongo/commit/6483fb8378cb2130160a1acfa46d5d50bac27dfc

Comment by Matt Boros [ 22/Jun/23 ]

Unsure which project to assign this to. It seems necessary for correctness, but will also likely improve performance. My understanding is that the performance investigation has focused on the reference tracker recently.

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