[SERVER-78587] Improve VM logicAnd/Or compileDirect to avoid quadratic behavior Created: 30/Jun/23  Updated: 29/Oct/23  Resolved: 21/Sep/23

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

Type: Improvement Priority: Major - P3
Reporter: Matt Boros Assignee: Matt Boros
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
depends on SERVER-80970 Improve perf for SBE local variables ... Closed
Problem/Incident
Related
related to SERVER-62509 Write tests to stress ABT and Bonsai Closed
is related to SERVER-71352 Investigate using linear builder-styl... Open
Assigned Teams:
Query Execution
Backwards Compatibility: Fully Compatible
Sprint: QE 2023-08-07, QE 2023-08-21, QE 2023-09-04, QE 2023-09-18, QE 2023-10-02
Participants:
Linked BF Score: 35

 Description   

For large $match queries of the form {$match: {a: 1, b: 1, ... }}, we have quadratic time behavior on the number of predicates in two places during compilation: #1 #2

The issue is in appending the code fragments for each clause. LHS appends "code", resizing the LHS vector. Then we assign LHS to "code", and get the next LHS. This LHS appends the new code, resizing once again, but to a larger size. The number of allocations is about the same as the number of clauses, but each allocation will be the size of the code we have so far. This results in an n^2 behavior on the number of clauses.

For the largest $match I can possibly make, compiling takes 30+ minutes. With a proof of concept to only append to one code fragment and allow a single vector to resize in the expected way (doubling each time), it takes a minute or less.



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

Author:

{'name': 'Matt Boros', 'email': 'matt.boros@mongodb.com', 'username': 'mattBoros'}

Message: SERVER-78587 Improve VM logicAnd/Or compileDirect to avoid quadratic behavior
Branch: master
https://github.com/mongodb/mongo/commit/1ed3f755d652b2d0a986139db257c5cbc76e9bfd

Comment by Matt Boros [ 12/Sep/23 ]

This now depends on SERVER-80970. Code was committed that broke some of the queries this test was supposed to uncomment in query_limits_test.js. This should be fixed in SERVER-80970.

Comment by Matt Boros [ 30/Jun/23 ]

Proof of concept for logicAnd: https://github.com/10gen/mongo/compare/master...fast-match-compile (this admittedly could be a bit cleaner, but it passes unit tests and jstests, and fixes the perf issue I've run into)

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