[SERVER-78631] [CQF] Replace linear search in BoolExpr::Builder Created: 03/Jul/23  Updated: 27/Oct/23  Resolved: 07/Aug/23

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

Type: Improvement Priority: Major - P3
Reporter: Matt Boros Assignee: Backlog - Query Optimization
Resolution: Gone away Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-62509 Write tests to stress ABT and Bonsai Closed
is related to SERVER-73827 [CQF] Extend BoolExpr builder to acce... Closed
Assigned Teams:
Query Optimization
Participants:

 Description   

The BoolExpr::Builder linearly searches through nodes to deduplication while building. For large expressions this is inefficient. We could instead hold a set data type of nodes.

This was an issue for large $match of the form

{$match: {a: 1, b: 2, c: 3, ...}}

As part of this ticket, we should run performance tests to see if adding an extra set to the builder slows down smaller queries.



 Comments   
Comment by Matt Boros [ 07/Aug/23 ]

Fixed by SERVER-73827

Comment by Matt Boros [ 19/Jul/23 ]

In SERVER-78580 we had the idea of creating a generic map structure that internally uses a vector for small N, and then switches over to map at a certain threshold. We've found a few cases where this could be ideal (this ticket is one of them).

This structure didn't fit cleanly into the SERVER-78580 scope because of additional restrictions that the parsing structure has. Hopefully we can create this structure in this ticket. Here was what I had so far before realizing this wouldn't work for 78580: https://github.com/10gen/mongo/compare/master...vector-map-structure

Comment by Matt Boros [ 03/Jul/23 ]

This is a neatly scoped task that would be well suited for Bonsai onboarding or an intern.

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