Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-13665

Index self-intersection for arrays with simple values only races off against simple index with first value

    XMLWordPrintableJSON

Details

    • Icon: Bug Bug
    • Resolution: Done
    • Icon: Major - P3 Major - P3
    • None
    • 2.6.0
    • Querying
    • None
    • ALL

    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).

      Attachments

        Activity

          People

            david.storch@mongodb.com David Storch
            asya.kamsky@mongodb.com Asya Kamsky
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: