[SERVER-13665] Index self-intersection for arrays with simple values only races off against simple index with first value Created: 20/Apr/14  Updated: 10/Dec/14  Resolved: 25/Apr/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.0
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Asya Kamsky Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
Operating System: ALL
Participants:

 Description   

Reproducer is a bit convoluted, but here are the steps:

for (p = 0; p < 10; p++) {
     var t = db.foo;
     t.drop();
     for ( i = 0; i < 10000; i++ ) {
         var a = [];
         for ( var j = 0; j < 10; j++ ) {
             a.push( Math.floor( Math.random() * 2000 ) );
             a.push( Math.floor( Math.random() * 20 ) );
        }
        t.insert( { x : a } );
     }
    t.ensureIndex( { x : 1 } );
    for (j=0;j<20;j++) {
           var foo = t.find( { x : { $all : [ j , j*10 ] } } ).explain();
           if (foo.cursor == "Complex Plan") throw "Got it with " +j; 
    }
}

Assuming you got "Got it" printed, you now have j to see result for explain(true) which shows something like:

db.foo.find({x:{$all:[ j,j*10]}}).explain(true)
{
	"cursor" : "Complex Plan",
	"n" : 15,
	"nscannedObjects" : 0,
	"nscanned" : 3925,
	"nscannedObjectsAllPlans" : 3925,
	"nscannedAllPlans" : 7851,
	"nYields" : 61,
	"nChunkSkips" : 0,
	"millis" : 17,
	"allPlans" : [
		{
			"cursor" : "Complex Plan",
			"n" : 15,
			"nscannedObjects" : 0,
			"nscanned" : 3925,
			"nChunkSkips" : 0
		},
		{
			"cursor" : "BtreeCursor x_1",
			"isMultiKey" : true,
			"n" : 15,
			"nscannedObjects" : 3925,
			"nscanned" : 3926,
			"scanAndOrder" : false,
			"indexOnly" : false,
			"nChunkSkips" : 0,
			"indexBounds" : {
				"x" : [
					[
						5,
						5
					]
				]
			}
		}
	],
	"server" : "Asyas-MacBook-Pro.local:27017",
	"filterSet" : false,
	"stats" : {
		"type" : "FETCH",
		"works" : 3926,
		"yields" : 61,
		"unyields" : 61,
		"invalidates" : 0,
		"advanced" : 15,
		"needTime" : 3909,
		"needFetch" : 0,
		"isEOF" : 1,
		"alreadyHasObj" : 0,
		"forcedFetches" : 0,
		"matchTested" : 0,
		"children" : [
			{
				"type" : "KEEP_MUTATIONS",
				"works" : 3925,
				"yields" : 61,
				"unyields" : 61,
				"invalidates" : 0,
				"advanced" : 15,
				"needTime" : 3909,
				"needFetch" : 0,
				"isEOF" : 1,
				"children" : [
					{
						"type" : "AND_SORTED",
						"works" : 3925,
						"yields" : 61,
						"unyields" : 61,
						"invalidates" : 0,
						"advanced" : 15,
						"needTime" : 3909,
						"needFetch" : 0,
						"isEOF" : 1,
						"flagged" : 0,
						"matchTested" : 0,
						"failedAnd_0" : 50,
						"failedAnd_1" : 35,
						"children" : [
							{
								"type" : "IXSCAN",
								"works" : 3874,
								"yields" : 61,
								"unyields" : 61,
								"invalidates" : 0,
								"advanced" : 3874,
								"needTime" : 0,
								"needFetch" : 0,
								"isEOF" : 0,
								"keyPattern" : "{ x: 1.0 }",
								"boundsVerbose" : "field #0['x']: [5.0, 5.0]",
								"isMultiKey" : 1,
								"yieldMovedCursor" : 0,
								"dupsTested" : 3874,
								"dupsDropped" : 0,
								"seenInvalidated" : 0,
								"matchTested" : 0,
								"keysExamined" : 3875,
								"children" : [ ]
							},
							{
								"type" : "IXSCAN",
								"works" : 51,
								"yields" : 61,
								"unyields" : 61,
								"invalidates" : 0,
								"advanced" : 50,
								"needTime" : 0,
								"needFetch" : 0,
								"isEOF" : 1,
								"keyPattern" : "{ x: 1.0 }",
								"boundsVerbose" : "field #0['x']: [50.0, 50.0]",
								"isMultiKey" : 1,
								"yieldMovedCursor" : 0,
								"dupsTested" : 50,
								"dupsDropped" : 0,
								"seenInvalidated" : 0,
								"matchTested" : 0,
								"keysExamined" : 50,
								"children" : [ ]
							}
						]
					}
				]
			}
		]
	}
}

This is racing off index intersection against index scan for first value of $all only (j in which case). If you switch the query to $all:[j*10,j ] you will now see the index scan win against index intersection.

This is a case of an $and query where position actually makes a difference to the query plan which I would not have expected. I would expect a race against intersection, index scan for only first value and index scan for only second value. (in case of more values, then as many of them as we allow for a single race-off).



 Comments   
Comment by David Storch [ 25/Apr/14 ]

Right now when we have multiple predicates over the same field of a compound index, we arbitrarily choose one of them in order to generate the index bounds, and the remaining predicates are affixed as filters. We just choose the first predicate, which is why there is order-dependent behavior from the query engine in the $all query. This was done by design, see the comments and code here:

https://github.com/mongodb/mongo/blob/03f1bce19b65d210af089d4e9e052dbab0317bce/src/mongo/db/query/plan_enumerator.cpp#L464-L489

We have decided that the behavior is okay as it currently stands. Closing as Works as Designed.

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