[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: |
|
||||||||||||||||||||||||
| 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: |
| Comment by Matt Boros [ 12/Sep/23 ] |
|
This now depends on |
| 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) |