[SERVER-78260] Contained $or rewrite optimization incorrectly lifts a negation predicate outside an $elemMatch leading to missing query results Created: 20/Jun/23 Updated: 29/Oct/23 Resolved: 23/Aug/23 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Query Planning |
| Affects Version/s: | None |
| Fix Version/s: | 7.1.0-rc0 |
| Type: | Bug | Priority: | Major - P3 |
| Reporter: | David Storch | Assignee: | Svilen Mihaylov (Inactive) |
| Resolution: | Fixed | Votes: | 0 |
| Labels: | auto-reverted | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||
| Assigned Teams: |
Query Optimization
|
||||||||||||||||
| Backwards Compatibility: | Minor Change | ||||||||||||||||
| Operating System: | ALL | ||||||||||||||||
| Sprint: | QO 2023-07-10, QO 2023-07-24, QO 2023-08-07, QO 2023-08-21, QO 2023-09-04 | ||||||||||||||||
| Participants: | |||||||||||||||||
| Linked BF Score: | 158 | ||||||||||||||||
| Description |
|
In MQL, negation predicates behave differently depending on whether or not they are within an $elemMatch. Let's consider the behavior of the predicate {a: {$ne: 1}}. Here is an example of this predicate used inside an $elemMatch:
The semantics of this query are that the document matches if any array element matches the "a != 1" predicate. Let's compare this to a similar query with no $elemMatch using the same example data:
This query finds documents where all array elements match the "a != 1" predicate. In slightly more technical terms, the former query applies the logical negation inside the implicit array traversal whereas the latter applies the negation outside the implicit array traversal. This means that one cannot perform either of the following query rewrites:
I found a case where we are essentially doing the rewrite that I've notated as "Rewrite 2" above, leading to missing query results. Here's a simple repro script:
The problem relates to the so-called "contained $or pushdown" rewrite. Specifically, we have logic to rewrite a predicate like so:
We have a version of this rewrite that can lift a predicate out of an $elemMatch object before pushing it into the OR. That looks something like this:
Doing this "lifting" is not correct if the predicate is a negation such as $ne given the array traversal semantics described above! In the repro script the example query is:
When the script fails it dumps the plan:
Let's focus our attention on the first child of the OR stage:
You'll notice that the filter associated with the FETCH stage is the $ne predicate that was lifted outside the $elemMatch object. That is an incorrect transformation of the input query which can cause the plan to miss query results. A final note: The repro script I've provided actually exposes two separate bugs related to contained $or pushdown and $elemMatch as of this writing. The first is related ticket |
| Comments |
| Comment by Githook User [ 23/Aug/23 ] |
|
Author: {'name': 'Svilen Mihaylov', 'email': 'svilen.mihaylov@mongodb.com', 'username': 'svilen-mihaylov'}Message: |
| Comment by xgen-buildbaron-user [ 22/Aug/23 ] |
|
Ticket re-opened due to revert. causally_consistent_jscore_passthrough_auth began a consistent failure of jstests/core/query/elemmatch/elemmatch_ne.js |
| Comment by Githook User [ 22/Aug/23 ] |
|
Author: {'name': 'auto-revert-processor', 'email': 'dev-prod-dag@mongodb.com', 'username': ''}Message: Revert " This reverts commit d46c53c38a3090c04e261c91e3312edfd0a72b8f. |
| Comment by Githook User [ 21/Aug/23 ] |
|
Author: {'name': 'Svilen Mihaylov', 'email': 'svilen.mihaylov@mongodb.com', 'username': 'svilen-mihaylov'}Message: |