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

Certain candidate plans not generated for certain queries over compound index

    • Type: Icon: Bug Bug
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: Query Planning
    • None
    • Query Optimization
    • ALL

      For queries like this:

      db.example.find({first: "X", second: {$gt: "Y", $lt: "Z"}})
      

      If "second" is sometimes an array we cannot generate the bounds ("Y", "Z") without an $elemMatch clause. However, it seems we recognize we cannot "intersect" the bounds, but we don't generate the two alternatives we would without the predicate on "first". See these examples:

      // Only one alternative generated, expected two:
      {
      	"explainVersion" : "1",
      	"queryPlanner" : {
      		"namespace" : "test.example",
      		"indexFilterSet" : false,
      		"parsedQuery" : {
      			"$and" : [
      				{
      					"a" : {
      						"$eq" : 1
      					}
      				},
      				{
      					"b" : {
      						"$lt" : 5
      					}
      				},
      				{
      					"b" : {
      						"$gt" : 4
      					}
      				}
      			]
      		},
      		"queryHash" : "D57C76E4",
      		"planCacheKey" : "C15FE4FC",
      		"maxIndexedOrSolutionsReached" : false,
      		"maxIndexedAndSolutionsReached" : false,
      		"maxScansToExplodeReached" : false,
      		"winningPlan" : {
      			"stage" : "FETCH",
      			"filter" : {
      				"b" : {
      					"$gt" : 4
      				}
      			},
      			"inputStage" : {
      				"stage" : "IXSCAN",
      				"keyPattern" : {
      					"a" : 1,
      					"b" : 1
      				},
      				"indexName" : "a_1_b_1",
      				"isMultiKey" : true,
      				"multiKeyPaths" : {
      					"a" : [ ],
      					"b" : [
      						"b"
      					]
      				},
      				"isUnique" : false,
      				"isSparse" : false,
      				"isPartial" : false,
      				"indexVersion" : 2,
      				"direction" : "forward",
      				"indexBounds" : {
      					"a" : [
      						"[1.0, 1.0]"
      					],
      					"b" : [
      						"[-inf.0, 5.0)"
      						// Would expect to see another plan with [4, inf.0].
      					]
      				}
      			}
      		},
      		"rejectedPlans" : [ ]
      	},
      	"command" : {
      		"find" : "example",
      		"filter" : {
      			"a" : 1,
      			"b" : {
      				"$gt" : 4,
      				"$lt" : 5
      			}
      		},
      		"$db" : "test"
      	},
      	"serverInfo" : {
      		"host" : "franklinia",
      		"port" : 27017,
      		"version" : "5.0.0-alpha",
      		"gitVersion" : "unknown"
      	},
      	"serverParameters" : {
      		"internalQueryFacetBufferSizeBytes" : 104857600,
      		"internalQueryFacetMaxOutputDocSizeBytes" : 104857600,
      		"internalLookupStageIntermediateDocumentMaxSizeBytes" : 104857600,
      		"internalDocumentSourceGroupMaxMemoryBytes" : 104857600,
      		"internalQueryMaxBlockingSortMemoryUsageBytes" : 104857600,
      		"internalQueryProhibitBlockingMergeOnMongoS" : 0,
      		"internalQueryMaxAddToSetBytes" : 104857600,
      		"internalDocumentSourceSetWindowFieldsMaxMemoryBytes" : 104857600
      	},
      	"ok" : 1
      }
      
      // Positive example without a compound index:
      {
      	"explainVersion" : "1",
      	"queryPlanner" : {
      		"namespace" : "test.example2",
      		"indexFilterSet" : false,
      		"parsedQuery" : {
      			"$and" : [
      				{
      					"b" : {
      						"$lt" : 5
      					}
      				},
      				{
      					"b" : {
      						"$gt" : 4
      					}
      				}
      			]
      		},
      		"queryHash" : "A7B8F6B8",
      		"planCacheKey" : "A0A41213",
      		"maxIndexedOrSolutionsReached" : false,
      		"maxIndexedAndSolutionsReached" : false,
      		"maxScansToExplodeReached" : false,
      		"winningPlan" : {
      			"stage" : "FETCH",
      			"filter" : {
      				"b" : {
      					"$gt" : 4
      				}
      			},
      			"inputStage" : {
      				"stage" : "IXSCAN",
      				"keyPattern" : {
      					"b" : 1
      				},
      				"indexName" : "b_1",
      				"isMultiKey" : true,
      				"multiKeyPaths" : {
      					"b" : [
      						"b"
      					]
      				},
      				"isUnique" : false,
      				"isSparse" : false,
      				"isPartial" : false,
      				"indexVersion" : 2,
      				"direction" : "forward",
      				"indexBounds" : {
      					"b" : [
      						"[-inf.0, 5.0)"
      					]
      				}
      			}
      		},
      		"rejectedPlans" : [
      			{
      				"stage" : "FETCH",
      				"filter" : {
      					"b" : {
      						"$lt" : 5
      					}
      				},
      				"inputStage" : {
      					"stage" : "IXSCAN",
      					"keyPattern" : {
      						"b" : 1
      					},
      					"indexName" : "b_1",
      					"isMultiKey" : true,
      					"multiKeyPaths" : {
      						"b" : [
      							"b"
      						]
      					},
      					"isUnique" : false,
      					"isSparse" : false,
      					"isPartial" : false,
      					"indexVersion" : 2,
      					"direction" : "forward",
      					"indexBounds" : {
      						"b" : [
      							"(4.0, inf.0]"
      						]
      					}
      				}
      			}
      		]
      	},
      	"command" : {
      		"find" : "example2",
      		"filter" : {
      			"b" : {
      				"$gt" : 4,
      				"$lt" : 5
      			}
      		},
      		"$db" : "test"
      	},
      	"serverInfo" : {
      		"host" : "franklinia",
      		"port" : 27017,
      		"version" : "5.0.0-alpha",
      		"gitVersion" : "unknown"
      	},
      	"serverParameters" : {
      		"internalQueryFacetBufferSizeBytes" : 104857600,
      		"internalQueryFacetMaxOutputDocSizeBytes" : 104857600,
      		"internalLookupStageIntermediateDocumentMaxSizeBytes" : 104857600,
      		"internalDocumentSourceGroupMaxMemoryBytes" : 104857600,
      		"internalQueryMaxBlockingSortMemoryUsageBytes" : 104857600,
      		"internalQueryProhibitBlockingMergeOnMongoS" : 0,
      		"internalQueryMaxAddToSetBytes" : 104857600,
      		"internalDocumentSourceSetWindowFieldsMaxMemoryBytes" : 104857600
      	},
      	"ok" : 1
      }
      

      It looks to me like the problem is somewhere in the PlanEnumerator, although I haven't been able to pin down exactly where it is yet.

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            charlie.swanson@mongodb.com Charlie Swanson
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated: