[SERVER-12735] Improve negation-related tree normalization during query canonicalization Created: 14/Feb/14  Updated: 06/Dec/22

Status: Backlog
Project: Core Server
Component/s: Querying
Affects Version/s: 2.5.5
Fix Version/s: None

Type: Improvement Priority: Minor - P4
Reporter: David Storch Assignee: Backlog - Query Optimization
Resolution: Unresolved Votes: 0
Labels: open_todo_in_code
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-13939 Unexpected behavior of query planner ... Closed
Assigned Teams:
Query Optimization
Backwards Compatibility: Fully Compatible
Participants:

 Description   

There are two cases that could be improved:

1) We do not remove negations of negations. Example:

> t.drop()
> t.ensureIndex({a: 1})
> t.find({a: {$not: {$not: {$gt: 1}}}})

This query parses to the match expression below:

$not
    $not
        a $gt 1.0

Since this has a negation of something that is not bounds-generating (more precisely, another negation), this query will not use the index. If instead the CanonicalQuery::normalizeTree function rewrote this tree to simply "a $gt 1.0", then it would do an index scan over (1, Infinity] rather than a collection scan.

In 2.4.8, a double-negation is not allowed at all:

> t.find({a: {$not: {$not: {$gt: 1}}}})
error: { "$err" : "invalid use of $not", "code" : 13034 }

Another option is for canonicalization to return an error if it finds a double negation.

2) Tree normalization does not pass through $elemMatch. Example:

> t.ensureIndex({a: 1})
> t.find({a: {$elemMatch: {b: {$not: {$gt: 1}}}}})

This parses to the match expression shown below:

a $elemMatch (obj)
    $not
        $and
            b $gt 1.0

Since normalization does not pass through the $elemMatch, we do not end up removing the single-child $and as we would elsewhere. In other words, the canonicalized tree should be

a $elemMatch (obj)
    $not
         b $gt 1.0


Generated at Thu Feb 08 03:29:27 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.