See bottom of description for potential security implications:

As seen in HELP-92631, we can end up spending multiple minutes (or potentially hours) trying to generate the query solution for a $jsonSchema query. By adding some timers to the plan enumeration code in QueryPlanner::plan() we can see that 99.99% of the time is spent hashing in hashTaggedMatchExpression() which can take several minutes depending on the level of nesting.

In a repro attached to the HELP ticket we see that 16 levels of nesting takes about 6-8mins to hash. Note this operation is uninterruptible as we don't checkForInterrupt() in the query planning code meaning that a query thread will essentially be stuck and unresponsive to killOp(). This could scale to hours with more nesting depth as the time doubles with each new level of nesting.{}{'a.b': {$_internalSchemaAllElemMatchFromIndex: [2, \{a: {$lt: 5}}]}}

The root cause of this is accidentally exponential behavior in MatchExpressionHashVisitor for several InternalSchema* visitors, e.g. visit(InternalSchemaObjectMatchExpression) and visit(InternalSchemaAllElemMatchFromIndexMatchExpression) explicitly re-hash their children via

combine(MatchExpressionHasher{}(child));

Each call to MatchExpressionHasher{}(child) spawns a new tree_walker::walk() over the subtree the outer walker (specified by the top level MatchExpressionHashVisitor) is already descending into. This essentially means that every InternalSchema* node doubles the work below it.

This turns a tree walk algorithm that is linear in the number of nodes into one that is exponential on the depth of nested InternalSchema* nodes.

Since the hash of the querySolution is not expected to be stable (and even changes between mongod restarts), I believe the cleanest solution would be to just remove the inner combine(child) calls from the affected visit(InternalSchema*) functions and only let the outer tree walk handle hashing the tree.

Security Implications:
There is some DoS potential where a malicious user on a shared tier who just needs read access to a target collection could send queries with many levels of $jsonSchema nesting (16 levels of nesting ~ 6-8mins of hashing work; doubles with each level of nesting added) to occupy the CPU since the hashing process is CPU-bound. It's unclear to me how CPU sharing works on shared tier but if there isn't a cap on # of threads/queries per tenant then there could be some visible latency/DoS for other users.

We also do not check for interrupts during the plan enumeration phase and as a result, a query that gets stuck in this hashing for many minutes cannot be interrupted via killOp().