[SERVER-68434] Equality to null can incorrectly use a cached partial ixscan which does not cover the predicate Created: 29/Jul/22  Updated: 29/Oct/23  Resolved: 10/Feb/23

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: 6.0.0-rc13
Fix Version/s: 5.0.15, 7.0.0-rc0, 6.0.5, 4.2.25, 4.4.20

Type: Bug Priority: Major - P3
Reporter: Nicholas Zolnierz Assignee: Nicholas Zolnierz
Resolution: Fixed Votes: 0
Labels: query-director-triage
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Depends
Duplicate
is duplicated by SERVER-71489 tassert tripped when using a cached i... Closed
is duplicated by SERVER-72753 Incorrect usage of plan cache entry f... Closed
Related
is related to SERVER-71489 tassert tripped when using a cached i... Closed
is related to SERVER-74207 Add partial_index_logical.js to backp... Closed
Assigned Teams:
Query Optimization
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v6.0, v5.0, v4.4, v4.2
Steps To Reproduce:

(function() {
"use strict";
 
load("jstests/aggregation/extras/utils.js");  // documentEq
 
db.test.drop();
 
const indexList = [
    {"num": 1, },
    {"num": -1},
];
 
const indexOptions = [
    {partialFilterExpression: {$or: [{"num": {$exists: true}}, {"num": {$type: 'number'}}]}},
    {}, 
];
 
const documentList = [
    {_id: 0},
    {_id: 1, num: null},
];
 
assert.commandWorked(db.test.insert(documentList));
 
for (let i = 0; i < indexList.length; i++) {
    db.test.createIndex(indexList[i], indexOptions[i]);
}
 
// Run the first query a few times to ensure an entry is active in the cache.
for (let i = 0; i < 10; i++) {
    assert.eq(db.test.find({num: 5}).itcount(), 0);
}
 
// Now run with eq to null and expect it not to use the cached plan because of the partial filter.
/** THIS FAILS */
assert.eq(2, db.test.find({num: null}).itcount(), db.test.aggregate([{$planCacheStats: {}}]).toArray());
 
})();

Sprint: QO 2023-02-06, QO 2023-02-20
Participants:
Linked BF Score: 16

 Description   

Given an index with a partial filter containing a $or and one branch being {<path>: {$exists: true}}. If a plan cache entry gets created (and is active) for a parameterized query such as {<path>: {$eq: 5}}, then a subsequent query of the form {<path>: {$eq: null}} will incorrectly use the cached plan even though $eq with null does not satisfy the $exists filter since it also matches missing. The $or is significant as I was not able to reproduce this with a single $exists partial index filter.

Attached is a minimal repro script. Note that I verified this happens on 6.0 and master, but not on 5.0. 



 Comments   
Comment by Githook User [ 16/Feb/23 ]

Author:

{'name': 'Nicholas Zolnierz', 'email': 'nicholas.zolnierz@mongodb.com', 'username': 'nzolnierzmdb'}

Message: SERVER-68434 Fix plan cache key encoding to account for $or in partial index expression

(cherry picked from commit f15f2bf8958557b4e8fccc6e8e1c7c8c5834d209)
(cherry picked from commit d19b8c60309c3a660a968ae8cf074aef92e1266d)
(cherry picked from commit 65dc21eabcdc2bbf952418b6d4988a199c980d43)
Branch: v4.2
https://github.com/mongodb/mongo/commit/f92c25b160937a960a4bedc066ebcfe20dd35d09

Comment by Githook User [ 16/Feb/23 ]

Author:

{'name': 'Nicholas Zolnierz', 'email': 'nicholas.zolnierz@mongodb.com', 'username': 'nzolnierzmdb'}

Message: SERVER-68434 Fix plan cache key encoding to account for $or in partial index expression

(cherry picked from commit f15f2bf8958557b4e8fccc6e8e1c7c8c5834d209)
(cherry picked from commit d19b8c60309c3a660a968ae8cf074aef92e1266d)
Branch: v4.4
https://github.com/mongodb/mongo/commit/65dc21eabcdc2bbf952418b6d4988a199c980d43

Comment by Githook User [ 14/Feb/23 ]

Author:

{'name': 'Nicholas Zolnierz', 'email': 'nicholas.zolnierz@mongodb.com', 'username': 'nzolnierzmdb'}

Message: SERVER-68434 Fix plan cache key encoding to account for $or in partial index expression

(cherry picked from commit f15f2bf8958557b4e8fccc6e8e1c7c8c5834d209)
Branch: v6.0
https://github.com/mongodb/mongo/commit/38ebd8f31027ac6ef6c593971356abb7c08b486e

Comment by Githook User [ 14/Feb/23 ]

Author:

{'name': 'Nicholas Zolnierz', 'email': 'nicholas.zolnierz@mongodb.com', 'username': 'nzolnierzmdb'}

Message: SERVER-68434 Fix plan cache key encoding to account for $or in partial index expression

(cherry picked from commit f15f2bf8958557b4e8fccc6e8e1c7c8c5834d209)
Branch: v5.0
https://github.com/mongodb/mongo/commit/d19b8c60309c3a660a968ae8cf074aef92e1266d

Comment by Nicholas Zolnierz [ 10/Feb/23 ]

The commit description is lacking a ton of details, so I'll attempt to summarize here for future readers.

tl;dr The gist of the problem described by this ticket as well as a few of the linked tickets revolves around the way in which the plan cache key encodes the discriminator for partial indexes. If the discriminator is wrong (e.g. <0> even though the filter is eligible to use the index), then there's a chance that a new query of the same shape but different parameters incorrectly uses the cached plan.

 
The current logic for plan cache key encoding of partial indexes is to compare the leaf predicates of the incoming query to the leaf predicates of the partial filter if they operate on the same path. Discriminators on the same path are logically AND'ed together to get a final boolean result. This happens to work for most cases, however queries with combinations of disjunctions and/or conjunctions can incorrectly indicate that a match expression is not compatible (discriminator = <0>). For instance, a query such as

 

{a: {$eq: 5}} 

 

against a partial filter expression of 

{$or: [{a: 5}, {a: "not five"}]}

will compare the incoming match expression against each leaf of the $or. The results are AND'ed, and because of the {a: "not five"} expression, the final discriminator is "<0>". This of course is wrong and the query planner can (and likely will) choose to use the partial index. 

 

As for the fix, the approach taken was to move the discriminator for partial index expressions to be "global". The intent is that these discriminators do not act on a certain path; instead they operate against the entire incoming match expression. So for the above case, we will not shred apart the partial filter (nor the incoming query) and will compare the $or holistically to the incoming {a: {$eq: 5}} filter. Since one branch of the $or fully covers the incoming filter, it is safe to say that the query is a strict subset of what is contained in the partial index and the discriminator will be set to "(1)". Note that the "(" and ")" separators are new and as used to designate global discriminators.

 

 

Comment by Githook User [ 10/Feb/23 ]

Author:

{'name': 'Nicholas Zolnierz', 'email': 'nicholas.zolnierz@mongodb.com', 'username': 'nzolnierzmdb'}

Message: SERVER-68434 Fix plan cache key encoding to account for $or in partial index expression
Branch: master
https://github.com/mongodb/mongo/commit/f15f2bf8958557b4e8fccc6e8e1c7c8c5834d209

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