[SERVER-35921] Index scan uses incorrect bounds for MinKey and MaxKey Created: 29/Jun/18  Updated: 29/Oct/23  Resolved: 05/Aug/19

Status: Closed
Project: Core Server
Component/s: Index Maintenance, Querying
Affects Version/s: None
Fix Version/s: 4.3.1, 4.2.9, 4.0.21

Type: Bug Priority: Major - P3
Reporter: Minji Kim Assignee: Mikhail Ivkov (Inactive)
Resolution: Fixed Votes: 0
Labels: open_todo_in_code, query-44-grooming
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Problem/Incident
Related
is related to SERVER-47042 Disable min_max_key.js test prior to 4.4 Closed
Backwards Compatibility: Minor Change
Operating System: ALL
Backport Requested:
v4.2, v4.0
Sprint: Query 2019-08-12
Participants:
Linked BF Score: 49

 Description   

The document {a: MinKey} should not match the query {a: { $gt: MinKey }}. However when there is an index present, MinKey is considered in the bounds for the index scan.

> db.test_min_max.find()
{ "_id" : "a_max_key", "a" : { "$maxKey" : 1 } }
{ "_id" : "a_min_key", "a" : { "$minKey" : 1 } }
{ "_id" : "a_null", "a" : null }
{ "_id" : "a_number", "a" : 4 }
{ "_id" : "a_subobject", "a" : { "b" : "hi" } }
{ "_id" : "a_undefined", "a" : undefined }
{ "_id" : "a_string", "a" : "hello" }
> db.test_min_max.find({a: {$gt: MinKey}})
{ "_id" : "a_min_key", "a" : { "$minKey" : 1 } } . // THIS IS WRONG
{ "_id" : "a_undefined", "a" : undefined }
{ "_id" : "a_null", "a" : null }
{ "_id" : "a_number", "a" : 4 }
{ "_id" : "a_string", "a" : "hello" }
{ "_id" : "a_subobject", "a" : { "b" : "hi" } }
{ "_id" : "a_max_key", "a" : { "$maxKey" : 1 } }
> db.test_min_max.find({a: {$gt: MinKey}}).explain()
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.test_min_max",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"a" : {
				"$gt" : { "$minKey" : 1 }
			}
		},
		"winningPlan" : {
			"stage" : "FETCH",
			"inputStage" : {
				"stage" : "IXSCAN",
				"keyPattern" : {
					"a" : 4
				},
				"indexName" : "a_4",
				"isMultiKey" : false,
				"multiKeyPaths" : {
					"a" : [ ]
				},
				"isUnique" : false,
				"isSparse" : false,
				"isPartial" : false,
				"indexVersion" : 2,
				"direction" : "forward",
				"indexBounds" : {
					"a" : [
						"[MinKey, MaxKey]" . // THIS IS WRONG
					]
				}
			}
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "franklinia",
		"port" : 27017,
		"version" : "0.0.0",
		"gitVersion" : "unknown"
	},
	"ok" : 1
}



 Comments   
Comment by Githook User [ 14/Aug/20 ]

Author:

{'name': 'Misha Ivkov', 'email': 'misha.ivkov@10gen.com'}

Message: SERVER-35921 Make IXSCAN use the proper MinKey/MaxKey bounds on LT and GT

(cherry picked from commit b1285a2acb60cbf7c268cb5499fbf5d674d490b2)
(cherry picked from commit b315dcfc8145c6b898b21916bef4bec18e95ac54)
Branch: v4.0
https://github.com/mongodb/mongo/commit/d3470d48166e9897e9d9817340db9f11f70a55e4

Comment by Githook User [ 15/Jul/20 ]

Author:

{'name': 'Misha Ivkov', 'email': 'misha.ivkov@10gen.com'}

Message: SERVER-35921 Make IXSCAN use the proper MinKey/MaxKey bounds on LT and GT

(cherry picked from commit b1285a2acb60cbf7c268cb5499fbf5d674d490b2)
Branch: v4.2
https://github.com/mongodb/mongo/commit/fc829bb485654a6325f358b2642aab34a9bc2543

Comment by Githook User [ 22/Nov/19 ]

Author:

{'email': 'david.storch@mongodb.com', 'name': 'David Storch', 'username': 'dstorch'}

Message: SERVER-44793 Tag index_bounds_maxkey.js as 'requires_fcv_44'.

This tests behavior which was implemented under
SERVER-35921.
Branch: master
https://github.com/mongodb/mongo/commit/f30d13a1c36d13c09ffa07cfc61c4a38e2dd34c7

Comment by Githook User [ 22/Nov/19 ]

Author:

{'name': 'David Percy', 'username': 'dpercy', 'email': 'david.percy@mongodb.com'}

Message: SERVER-44799 Mark SERVER-35921 as backports_required_for_multiversion_tests
Branch: master
https://github.com/mongodb/mongo/commit/147b4b3ac239be4e8e31febaf659e8c17e7c8300

Comment by Githook User [ 05/Aug/19 ]

Author:

{'name': 'Misha Ivkov', 'email': 'misha.ivkov@10gen.com', 'username': 'mivkov'}

Message: SERVER-35921 Make IXSCAN use the proper MinKey/MaxKey bounds on LT and GT
Branch: master
https://github.com/mongodb/mongo/commit/b1285a2acb60cbf7c268cb5499fbf5d674d490b2

Comment by Charlie Swanson [ 02/Jul/18 ]

This looks to be a bug in the IndexBoundsBuilder:

index_bounds_builder.cpp

    } else if (MatchExpression::GT == expr->matchType()) {
        const GTMatchExpression* node = static_cast<const GTMatchExpression*>(expr);
        BSONElement dataElt = node->getData();
 
        // Everything is > MinKey.
        if (MinKey == dataElt.type()) {
            oilOut->intervals.push_back(allValues());
            *tightnessOut =
                index.collator ? IndexBoundsBuilder::INEXACT_FETCH : IndexBoundsBuilder::EXACT;
            return;
        }

There's a similar flaw in the LT/MaxKey case which forgets that MaxKey >= MaxKey.

Generated at Thu Feb 08 04:41:28 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.