[SERVER-78635] [CQF] Refactor PartialSchemaReqConverter to avoid quadratic behavior Created: 03/Jul/23  Updated: 06/Oct/23  Resolved: 03/Oct/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: Duplicate Votes: 0
Labels: M9
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
duplicates SERVER-80735 [CQF] Lazy simplification Backlog
Related
related to SERVER-62509 Write tests to stress ABT and Bonsai Closed
related to SERVER-81822 Complete TODO listed in SERVER-78635 Closed
Assigned Teams:
Query Optimization
Participants:

 Description   

There are a few operations in PartialSchemaReqConverter that are unnecessarily quadratic on the number of PSR entries.

#1
This loop in intersectPartialSchemaReq iterates through every entry in the PSR DNF, looking for an existing requirement that meets the condition newKey.projectionName == existingReq.boundProjectionName. Instead of searching through the entire structure, PSR can hold a map of Requirement Bound Projection -> Atom Node::reference_type

#2
Every time we call add in intersectPartialSchemaReq, the PSR renormalizes, which involves resorting and deduplicating the entire structure. We could either normalize after converting to PSR, or insert into the structure in a way that keeps it in a normalized state. If the PSR is normalized later on in optimization, we could avoid normalizing altogether.

These are the first solutions I thought of, it's possible a larger refactor might be more ideal.


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