SERVER-30649: Check whether each expression inside of $elemMatch is compatible with a given index

(cherry picked from commit 625d3c1b287170390622055fb29bda7ee12e7b67)

2 files changed, 174 insertions, 101 deletions

diff --git a/jstests/core/existsa.js b/jstests/core/existsa.js
index e9430b489a3..d98fd3f2d68 100644
--- a/jstests/core/existsa.js
+++ b/jstests/core/existsa.js
@@ -1,101 +1,111 @@
-// Sparse indexes are disallowed for $exists:false queries.  SERVER-3918
-
-t = db.jstests_existsa;
-t.drop();
-
-t.save({});
-t.save({a: 1});
-t.save({a: {x: 1}, b: 1});
-
-/** Configure testing of an index { <indexKeyField>:1 }. */
-function setIndex(_indexKeyField) {
-    indexKeyField = _indexKeyField;
-    indexKeySpec = {};
-    indexKeySpec[indexKeyField] = 1;
-    t.ensureIndex(indexKeySpec, {sparse: true});
-}
-setIndex('a');
-
-/** @return count when hinting the index to use. */
-function hintedCount(query) {
-    return t.find(query).hint(indexKeySpec).itcount();
-}
-
-/** The query field does not exist and the sparse index is not used without a hint. */
-function assertMissing(query, expectedMissing, expectedIndexedMissing) {
-    expectedMissing = expectedMissing || 1;
-    expectedIndexedMissing = expectedIndexedMissing || 0;
-    assert.eq(expectedMissing, t.count(query));
-    // We also shouldn't get a different count depending on whether
-    // an index is used or not.
-    assert.eq(expectedIndexedMissing, hintedCount(query));
-}
-
-/** The query field exists and the sparse index is used without a hint. */
-function assertExists(query, expectedExists) {
-    expectedExists = expectedExists || 2;
-    assert.eq(expectedExists, t.count(query));
-    // An $exists:true predicate generates no index filters.  Add another predicate on the index key
-    // to trigger use of the index.
-    andClause = {};
-    andClause[indexKeyField] = {$ne: null};
-    Object.extend(query, {$and: [andClause]});
-    assert.eq(expectedExists, t.count(query));
-    assert.eq(expectedExists, hintedCount(query));
-}
-
-/** The query field exists and the sparse index is not used without a hint. */
-function assertExistsUnindexed(query, expectedExists) {
-    expectedExists = expectedExists || 2;
-    assert.eq(expectedExists, t.count(query));
-    // Even with another predicate on the index key, the sparse index is disallowed.
-    andClause = {};
-    andClause[indexKeyField] = {$ne: null};
-    Object.extend(query, {$and: [andClause]});
-    assert.eq(expectedExists, t.count(query));
-    assert.eq(expectedExists, hintedCount(query));
-}
-
-// $exists:false queries match the proper number of documents and disallow the sparse index.
-assertMissing({a: {$exists: false}});
-assertMissing({a: {$not: {$exists: true}}});
-assertMissing({$and: [{a: {$exists: false}}]});
-assertMissing({$or: [{a: {$exists: false}}]});
-assertMissing({$nor: [{a: {$exists: true}}]});
-assertMissing({'a.x': {$exists: false}}, 2, 1);
-
-// Currently a sparse index is disallowed even if the $exists:false query is on a different field.
-assertMissing({b: {$exists: false}}, 2, 1);
-assertMissing({b: {$exists: false}, a: {$ne: 6}}, 2, 1);
-assertMissing({b: {$not: {$exists: true}}}, 2, 1);
-
-// Top level $exists:true queries match the proper number of documents
-// and use the sparse index on { a : 1 }.
-assertExists({a: {$exists: true}});
-
-// Nested $exists queries match the proper number of documents and disallow the sparse index.
-assertExistsUnindexed({$nor: [{a: {$exists: false}}]});
-assertExistsUnindexed({$nor: [{'a.x': {$exists: false}}]}, 1);
-assertExistsUnindexed({a: {$not: {$exists: false}}});
-
-// Nested $exists queries disallow the sparse index in some cases where it is not strictly
-// necessary to do so.  (Descriptive tests.)
-assertExistsUnindexed({$nor: [{b: {$exists: false}}]}, 1);  // Unindexed field.
-assertExists({$or: [{a: {$exists: true}}]});                // $exists:true not $exists:false.
-
-// Behavior is similar with $elemMatch.
-t.drop();
-t.save({a: [{}]});
-t.save({a: [{b: 1}]});
-t.save({a: [{b: 1}]});
-setIndex('a.b');
-
-assertMissing({a: {$elemMatch: {b: {$exists: false}}}});
-// A $elemMatch predicate is treated as nested, and the index should be used for $exists:true.
-assertExists({a: {$elemMatch: {b: {$exists: true}}}});
-
-// A non sparse index will not be disallowed.
-t.drop();
-t.save({});
-t.ensureIndex({a: 1});
-assert.eq(1, t.find({a: {$exists: false}}).itcount());
+/**
+ * Tests that sparse indexes are disallowed for $exists:false queries.
+ */
+(function() {
+    "use strict";
+
+    const coll = db.jstests_existsa;
+    coll.drop();
+
+    assert.writeOK(coll.insert({}));
+    assert.writeOK(coll.insert({a: 1}));
+    assert.writeOK(coll.insert({a: {x: 1}, b: 1}));
+
+    let indexKeySpec = {};
+    let indexKeyField = '';
+
+    /** Configure testing of an index { <indexKeyField>:1 }. */
+    function setIndex(_indexKeyField) {
+        indexKeyField = _indexKeyField;
+        indexKeySpec = {};
+        indexKeySpec[indexKeyField] = 1;
+        coll.ensureIndex(indexKeySpec, {sparse: true});
+    }
+    setIndex('a');
+
+    /** @return count when hinting the index to use. */
+    function hintedCount(query) {
+        return coll.find(query).hint(indexKeySpec).itcount();
+    }
+
+    /** The query field does not exist and the sparse index is not used without a hint. */
+    function assertMissing(query, expectedMissing = 1, expectedIndexedMissing = 0) {
+        assert.eq(expectedMissing, coll.count(query));
+        // We also shouldn't get a different count depending on whether
+        // an index is used or not.
+        assert.eq(expectedIndexedMissing, hintedCount(query));
+    }
+
+    /** The query field exists and the sparse index is used without a hint. */
+    function assertExists(query, expectedExists = 2) {
+        assert.eq(expectedExists, coll.count(query));
+        // An $exists:true predicate generates no index filters. Add another predicate on the index
+        // key to trigger use of the index.
+        let andClause = {};
+        andClause[indexKeyField] = {$ne: null};
+        Object.extend(query, {$and: [andClause]});
+        assert.eq(expectedExists, coll.count(query));
+        assert.eq(expectedExists, hintedCount(query));
+    }
+
+    /** The query field exists and the sparse index is not used without a hint. */
+    function assertExistsUnindexed(query, expectedExists = 2) {
+        assert.eq(expectedExists, coll.count(query));
+        // Even with another predicate on the index key, the sparse index is disallowed.
+        let andClause = {};
+        andClause[indexKeyField] = {$ne: null};
+        Object.extend(query, {$and: [andClause]});
+        assert.eq(expectedExists, coll.count(query));
+        assert.eq(expectedExists, hintedCount(query));
+    }
+
+    // $exists:false queries match the proper number of documents and disallow the sparse index.
+    assertMissing({a: {$exists: false}});
+    assertMissing({a: {$not: {$exists: true}}});
+    assertMissing({$and: [{a: {$exists: false}}]});
+    assertMissing({$or: [{a: {$exists: false}}]});
+    assertMissing({$nor: [{a: {$exists: true}}]});
+    assertMissing({'a.x': {$exists: false}}, 2, 1);
+
+    // Currently a sparse index is disallowed even if the $exists:false query is on a different
+    // field.
+    assertMissing({b: {$exists: false}}, 2, 1);
+    assertMissing({b: {$exists: false}, a: {$ne: 6}}, 2, 1);
+    assertMissing({b: {$not: {$exists: true}}}, 2, 1);
+
+    // Top level $exists:true queries match the proper number of documents
+    // and use the sparse index on { a : 1 }.
+    assertExists({a: {$exists: true}});
+
+    // Nested $exists queries match the proper number of documents and disallow the sparse index.
+    assertExistsUnindexed({$nor: [{a: {$exists: false}}]});
+    assertExistsUnindexed({$nor: [{'a.x': {$exists: false}}]}, 1);
+    assertExistsUnindexed({a: {$not: {$exists: false}}});
+
+    // Nested $exists queries disallow the sparse index in some cases where it is not strictly
+    // necessary to do so.  (Descriptive tests.)
+    assertExistsUnindexed({$nor: [{b: {$exists: false}}]}, 1);  // Unindexed field.
+    assertExists({$or: [{a: {$exists: true}}]});                // $exists:true not $exists:false.
+
+    // Behavior is similar with $elemMatch.
+    coll.drop();
+    assert.writeOK(coll.insert({a: [{}]}));
+    assert.writeOK(coll.insert({a: [{b: 1}]}));
+    assert.writeOK(coll.insert({a: [{b: [1]}]}));
+    setIndex('a.b');
+
+    assertMissing({a: {$elemMatch: {b: {$exists: false}}}});
+
+    // A $elemMatch predicate is treated as nested, and the index should be used for $exists:true.
+    assertExists({a: {$elemMatch: {b: {$exists: true}}}});
+
+    // A $not within $elemMatch should not attempt to use a sparse index for $exists:false.
+    assertExistsUnindexed({'a.b': {$elemMatch: {$not: {$exists: false}}}}, 1);
+    assertExistsUnindexed({'a.b': {$elemMatch: {$gt: 0, $not: {$exists: false}}}}, 1);
+
+    // A non sparse index will not be disallowed.
+    coll.drop();
+    assert.writeOK(coll.insert({}));
+    coll.ensureIndex({a: 1});
+    assert.eq(1, coll.find({a: {$exists: false}}).itcount());
+})();
diff --git a/jstests/core/index_elemmatch2.js b/jstests/core/index_elemmatch2.js
new file mode 100644
index 00000000000..ecd24035284
--- /dev/null
+++ b/jstests/core/index_elemmatch2.js
@@ -0,0 +1,63 @@
+/**
+ * Test that queries containing $elemMatch correctly use an index if each child expression is
+ * compatible with the index.
+ */
+(function() {
+    "use strict";
+
+    load("jstests/libs/analyze_plan.js");
+
+    const coll = db.elemMatch_index;
+    coll.drop();
+
+    assert.writeOK(coll.insert({a: 1}));
+    assert.writeOK(coll.insert({a: [{}]}));
+    assert.writeOK(coll.insert({a: [1, null]}));
+    assert.writeOK(coll.insert({a: [{type: "Point", coordinates: [0, 0]}]}));
+
+    assert.commandWorked(coll.createIndex({a: 1}, {sparse: true}));
+
+    function assertIndexResults(coll, query, useIndex, nReturned) {
+        const explainPlan = coll.find(query).explain("executionStats");
+        assert.eq(isIxscan(explainPlan.queryPlanner.winningPlan), useIndex);
+        assert.eq(explainPlan.executionStats.nReturned, nReturned);
+    }
+
+    assertIndexResults(coll, {a: {$elemMatch: {$exists: false}}}, false, 0);
+
+    // An $elemMatch predicate is treated as nested, and the index should be used for $exists:true.
+    assertIndexResults(coll, {a: {$elemMatch: {$exists: true}}}, true, 3);
+
+    // $not within $elemMatch should not attempt to use a sparse index for $exists:false.
+    assertIndexResults(coll, {a: {$elemMatch: {$not: {$exists: false}}}}, false, 3);
+    assertIndexResults(coll, {a: {$elemMatch: {$gt: 0, $not: {$exists: false}}}}, false, 1);
+
+    // $geo within $elemMatch should not attempt to use a non-geo index.
+    assertIndexResults(
+        coll,
+        {
+          a: {
+              $elemMatch: {
+                  $geoWithin: {
+                      $geometry:
+                          {type: "Polygon", coordinates: [[[0, 0], [0, 1], [1, 0], [0, 0]]]}
+                  }
+              }
+          }
+        },
+        false,
+        1);
+
+    // $in with a null value within $elemMatch should use a sparse index.
+    assertIndexResults(coll, {a: {$elemMatch: {$in: [null]}}}, true, 1);
+
+    // $eq with a null value within $elemMatch should use a sparse index.
+    assertIndexResults(coll, {a: {$elemMatch: {$eq: null}}}, true, 1);
+
+    // A negated regex within $elemMatch should not use an index, sparse or not.
+    assertIndexResults(coll, {a: {$elemMatch: {$not: {$in: [/^a/]}}}}, false, 3);
+
+    coll.dropIndexes();
+    assert.commandWorked(coll.createIndex({a: 1}));
+    assertIndexResults(coll, {a: {$elemMatch: {$not: {$in: [/^a/]}}}}, false, 3);
+})();