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

$elemMatch over trailing field of a 2d index can miss results

    • Type: Icon: Bug Bug
    • Resolution: Fixed
    • Priority: Icon: Critical - P2 Critical - P2
    • 3.7.1
    • Affects Version/s: 2.6.12, 3.0.15, 3.2.17, 3.4.9, 3.5.13
    • Component/s: Querying
    • None
    • Fully Compatible
    • ALL
    • Hide
      db.c.drop();
      db.c.createIndex({a: "2d", "b.c": 1});
      db.c.insert({a: [0, 0], b: [{c: 1}, {c: 2}]});
      assert.eq(1, db.c.find({a: {$geoWithin: {$center: [[0, 0], 1]}}, b: {$elemMatch: {c: 1}}}).itcount());
      
      Show
      db.c.drop(); db.c.createIndex({a: "2d" , "b.c" : 1}); db.c.insert({a: [0, 0], b: [{c: 1}, {c: 2}]}); assert .eq(1, db.c.find({a: {$geoWithin: {$center: [[0, 0], 1]}}, b: {$elemMatch: {c: 1}}}).itcount());
    • Query 2017-11-13, Query 2017-12-04, Query 2017-12-18, Query 2018-01-01, Query 2018-01-15

      When indexing array fields, most indexes contain one key per element of the array, hence the terminology "multikey indexes" (documented here). However, compound "2d" indexes use a different format for the non-2d fields. Namely, all of the array elements are stored in a single key whose value is itself an array. Consider the following example:

      > db.c.drop()
      false
      > db.c.createIndex({a: "2d", "b.c": 1})
      {
      	"createdCollectionAutomatically" : true,
      	"numIndexesBefore" : 1,
      	"numIndexesAfter" : 2,
      	"ok" : 1
      }
      > db.c.insert({a: [0, 0], b: [{c: 1}, {c: 2}]})
      WriteResult({ "nInserted" : 1 })
      > db.c.find().hint({a: "2d", "b.c": 1}).returnKey()
      { "a" : BinData(128,"wAAAAAAAAAA="), "b.c" : [ 1, 2 ] }
      

      As you can see, the inserted document leads to just a single index key. The value of this index key for the "b.c" field is the array [1, 2].

      Because of this index format, predicates against the trailing fields of an index typically are not used to generate bounds against the index. A predicate like {"b.c": {$eq: 2}} would normally result in point lookup in the index for the value 2. However, this would incorrectly miss the above document, because the index key value is the entire array [1, 2]. Instead, the predicate is attached as a filter to the IXSCAN stage, as you can see from the explain of the query below:

      > db.c.find({a: {$geoWithin: {$center: [[0, 0], 1]}}, "b.c": {$eq: 2}}).explain()
      {
      	"queryPlanner" : {
      ...
      			"inputStage" : {
      				"stage" : "IXSCAN",
      				"filter" : {
      					"b.c" : {
      						"$eq" : 2
      					}
      				},
      				"keyPattern" : {
      					"a" : "2d",
      					"b.c" : 1
      				},
      				"indexName" : "a_2d_b.c_1",
      				"isMultiKey" : false,
      				"isUnique" : false,
      				"isSparse" : false,
      				"isPartial" : false,
      				"indexVersion" : 2,
      				"direction" : "forward",
      				"indexBounds" : {
      					"a" : [
      						"[BinData(128, 3FFF300000000000), BinData(128, 3FFF3FFFFFFFFFFF)]",
      						"[BinData(128, 3FFF400000000000), BinData(128, 3FFF7FFFFFFFFFFF)]",
      						"[BinData(128, 3FFF800000000000), BinData(128, 3FFFBFFFFFFFFFFF)]",
      						"[BinData(128, 3FFFC00000000000), BinData(128, 3FFFFFFFFFFFFFFF)]",
      						"[BinData(128, 6AAA000000000000), BinData(128, 6AAA3FFFFFFFFFFF)]",
      						"[BinData(128, 6AAA600000000000), BinData(128, 6AAA6FFFFFFFFFFF)]",
      						"[BinData(128, 6AAA800000000000), BinData(128, 6AAABFFFFFFFFFFF)]",
      						"[BinData(128, 6AAAC00000000000), BinData(128, 6AAAFFFFFFFFFFFF)]",
      						"[BinData(128, 9555000000000000), BinData(128, 95553FFFFFFFFFFF)]",
      						"[BinData(128, 9555400000000000), BinData(128, 95557FFFFFFFFFFF)]",
      						"[BinData(128, 9555900000000000), BinData(128, 95559FFFFFFFFFFF)]",
      						"[BinData(128, 9555C00000000000), BinData(128, 9555FFFFFFFFFFFF)]",
      						"[BinData(128, C000000000000000), BinData(128, C0003FFFFFFFFFFF)]",
      						"[BinData(128, C000400000000000), BinData(128, C0007FFFFFFFFFFF)]",
      						"[BinData(128, C000800000000000), BinData(128, C000BFFFFFFFFFFF)]",
      						"[BinData(128, C000C00000000000), BinData(128, C000CFFFFFFFFFFF)]"
      					],
      					"b.c" : [
      						"[MinKey, MaxKey]"
      					]
      				}
      			}
      		},
      		"rejectedPlans" : [ ]
      	},
      ...
      }
      

      When the predicate over the trailing field is an $elemMatch, however, the planner incorrectly generates bounds:

      > db.c.find({a: {$geoWithin: {$center: [[0, 0], 1]}}, b: {$elemMatch: {c: 1}}}).explain()
      {
      	"queryPlanner" : {
      ...
      			"inputStage" : {
      				"stage" : "IXSCAN",
      				"keyPattern" : {
      					"a" : "2d",
      					"b.c" : 1
      				},
      				"indexName" : "a_2d_b.c_1",
      				"isMultiKey" : false,
      				"isUnique" : false,
      				"isSparse" : false,
      				"isPartial" : false,
      				"indexVersion" : 2,
      				"direction" : "forward",
      				"indexBounds" : {
      					"a" : [
      						"[BinData(128, 3FFF300000000000), BinData(128, 3FFF3FFFFFFFFFFF)]",
      						"[BinData(128, 3FFF400000000000), BinData(128, 3FFF7FFFFFFFFFFF)]",
      						"[BinData(128, 3FFF800000000000), BinData(128, 3FFFBFFFFFFFFFFF)]",
      						"[BinData(128, 3FFFC00000000000), BinData(128, 3FFFFFFFFFFFFFFF)]",
      						"[BinData(128, 6AAA000000000000), BinData(128, 6AAA3FFFFFFFFFFF)]",
      						"[BinData(128, 6AAA600000000000), BinData(128, 6AAA6FFFFFFFFFFF)]",
      						"[BinData(128, 6AAA800000000000), BinData(128, 6AAABFFFFFFFFFFF)]",
      						"[BinData(128, 6AAAC00000000000), BinData(128, 6AAAFFFFFFFFFFFF)]",
      						"[BinData(128, 9555000000000000), BinData(128, 95553FFFFFFFFFFF)]",
      						"[BinData(128, 9555400000000000), BinData(128, 95557FFFFFFFFFFF)]",
      						"[BinData(128, 9555900000000000), BinData(128, 95559FFFFFFFFFFF)]",
      						"[BinData(128, 9555C00000000000), BinData(128, 9555FFFFFFFFFFFF)]",
      						"[BinData(128, C000000000000000), BinData(128, C0003FFFFFFFFFFF)]",
      						"[BinData(128, C000400000000000), BinData(128, C0007FFFFFFFFFFF)]",
      						"[BinData(128, C000800000000000), BinData(128, C000BFFFFFFFFFFF)]",
      						"[BinData(128, C000C00000000000), BinData(128, C000CFFFFFFFFFFF)]"
      					],
      					"b.c" : [
      						"[1.0, 1.0]"
      					]
      				}
      			}
      		},
      		"rejectedPlans" : [ ]
      	},
      ...
      }
      

      As a result, this query misses the matching document:

      > db.c.find({a: {$geoWithin: {$center: [[0, 0], 1]}}, b: {$elemMatch: {c: 1}}});
      // No results.
      

            Assignee:
            martin.neupauer@mongodb.com Martin Neupauer
            Reporter:
            david.storch@mongodb.com David Storch
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated:
              Resolved: