SERVER-12557 allow exists queries to use an index

Signed-off-by: Matt Kangas <matt.kangas@mongodb.com>

4 files changed, 149 insertions, 4 deletions

diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index eefaf2a44e7..59df9828b53 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -254,7 +254,22 @@ namespace mongo {
             *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
         }
         else if (MatchExpression::NOT == expr->matchType()) {
-            if (Indexability::nodeCanUseIndexOnOwnField(expr->getChild(0))) {
+            MatchExpression* child = expr->getChild(0);
+
+            // If we have a NOT -> EXISTS, we must handle separately.
+            if (MatchExpression::EXISTS == child->matchType()) {
+                // We should never try to use a sparse index for $exists:false.
+                invariant(!index.sparse);
+                BSONObjBuilder bob;
+                bob.appendNull("");
+                bob.appendNull("");
+                BSONObj dataObj = bob.obj();
+                oilOut->intervals.push_back(makeRangeInterval(dataObj, true, true));
+                
+                *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
+                return;
+            }
+            else if (Indexability::nodeCanUseIndexOnOwnField(child)) {
                 // We have a NOT of a bounds-generating expression. Get the
                 // bounds of the NOT's child and then complement them.
                 translate(expr->getChild(0), elt, index, oilOut, tightnessOut);
@@ -270,6 +285,43 @@ namespace mongo {
                 *tightnessOut = INEXACT_FETCH;
             }
         }
+        else if (MatchExpression::EXISTS == expr->matchType()) {
+            // We only handle the {$exists:true} case, as {$exists:false}
+            // will have been translated to {$not:{ $exists:true }}.
+            //
+            // Documents with a missing value are stored *as if* they were
+            // explicitly given the value 'null'.  Given:
+            //    X = { b : 1 }
+            //    Y = { a : null, b : 1 }
+            // X and Y look identical from within a standard index on { a : 1 }.
+            // HOWEVER a sparse index on { a : 1 } will treat X and Y differently,
+            // storing Y and not storing X.
+            //
+            // We can safely use an index in the following cases:
+            // {a:{ $exists:true }} - normal index helps, but we must still fetch
+            // {a:{ $exists:true }} - sparse index is exact
+            // {a:{ $exists:false }} - normal index requires a fetch
+            // {a:{ $exists:false }} - sparse indexes cannot be used at all.
+            //
+            // Noted in SERVER-12869, in case this ever changes some day.
+            if (index.sparse) {
+                oilOut->intervals.push_back(allValues());
+                // A sparse, compound index on { a:1, b:1 } will include entries
+                // for all of the following documents:
+                //    { a:1 }, { b:1 }, { a:1, b:1 }
+                // So we must use INEXACT bounds in this case.
+                if ( 1 < index.keyPattern.nFields() ) {
+                    *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
+                }
+                else {
+                    *tightnessOut = IndexBoundsBuilder::EXACT;
+                }
+            }
+            else {
+                oilOut->intervals.push_back(allValues());
+                *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
+            }
+        }
         else if (MatchExpression::EQ == expr->matchType()) {
             const EqualityMatchExpression* node = static_cast<const EqualityMatchExpression*>(expr);
             translateEquality(node->getData(), isHashed, oilOut, tightnessOut);
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index 4be2f4dea22..1420e48b69c 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -457,6 +457,59 @@ namespace {
     }
 
     //
+    // $exists tests
+    //
+
+    TEST(IndexBoundsBuilderTest, ExistsTrue) {
+        IndexEntry testIndex = IndexEntry(BSONObj());
+        BSONObj obj = fromjson("{a: {$exists: true}}");
+        auto_ptr<MatchExpression> expr(parseMatchExpression(obj));
+        BSONElement elt = obj.firstElement();
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(oil.intervals.size(), 1U);
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                      oil.intervals[0].compare(IndexBoundsBuilder::allValues()));
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+    }
+
+    TEST(IndexBoundsBuilderTest, ExistsFalse) {
+        IndexEntry testIndex = IndexEntry(BSONObj());
+        BSONObj obj = fromjson("{a: {$exists: false}}");
+        auto_ptr<MatchExpression> expr(parseMatchExpression(obj));
+        BSONElement elt = obj.firstElement();
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(oil.intervals.size(), 1U);
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare(
+            Interval(fromjson("{'': null, '': null}"), true, true)));
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+    }
+
+    TEST(IndexBoundsBuilderTest, ExistsTrueSparse) {
+        IndexEntry testIndex = IndexEntry(BSONObj(),
+                                          false,
+                                          true,
+                                          "exists_true_sparse",
+                                          BSONObj());
+        BSONObj obj = fromjson("{a: {$exists: true}}");
+        auto_ptr<MatchExpression> expr(parseMatchExpression(obj));
+        BSONElement elt = obj.firstElement();
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(oil.intervals.size(), 1U);
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                      oil.intervals[0].compare(IndexBoundsBuilder::allValues()));
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+    }
+
+    //
     // Union tests
     //
 
diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h
index 6f25bda0469..0085e05e5a2 100644
--- a/src/mongo/db/query/indexability.h
+++ b/src/mongo/db/query/indexability.h
@@ -61,6 +61,7 @@ namespace mongo {
                    || me->matchType() == MatchExpression::TYPE_OPERATOR
                    || me->matchType() == MatchExpression::GEO
                    || me->matchType() == MatchExpression::GEO_NEAR
+                   || me->matchType() == MatchExpression::EXISTS
                    || me->matchType() == MatchExpression::TEXT;
         }
 
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 6ad01f502bd..705428a53e4 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -451,7 +451,7 @@ namespace {
     TEST_F(QueryPlannerTest, ExistsTrue) {
         addIndex(BSON("x" << 1));
 
-        runQuery(fromjson("{x: 1, y: {$exists: true}}"));
+        runQuery(fromjson("{x: {$exists: true}}"));
 
         assertNumSolutions(2U);
         assertSolutionExists("{cscan: {dir: 1}}");
@@ -461,7 +461,7 @@ namespace {
     TEST_F(QueryPlannerTest, ExistsFalse) {
         addIndex(BSON("x" << 1));
 
-        runQuery(fromjson("{x: 1, y: {$exists: false}}"));
+        runQuery(fromjson("{x: {$exists: false}}"));
 
         assertNumSolutions(2U);
         assertSolutionExists("{cscan: {dir: 1}}");
@@ -471,7 +471,7 @@ namespace {
     TEST_F(QueryPlannerTest, ExistsTrueSparseIndex) {
         addIndex(BSON("x" << 1), false, true);
 
-        runQuery(fromjson("{x: 1, y: {$exists: true}}"));
+        runQuery(fromjson("{x: {$exists: true}}"));
 
         assertNumSolutions(2U);
         assertSolutionExists("{cscan: {dir: 1}}");
@@ -481,6 +481,45 @@ namespace {
     TEST_F(QueryPlannerTest, ExistsFalseSparseIndex) {
         addIndex(BSON("x" << 1), false, true);
 
+        runQuery(fromjson("{x: {$exists: false}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+    }
+
+    TEST_F(QueryPlannerTest, ExistsTrueOnUnindexedField) {
+        addIndex(BSON("x" << 1));
+
+        runQuery(fromjson("{x: 1, y: {$exists: true}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, ExistsFalseOnUnindexedField) {
+        addIndex(BSON("x" << 1));
+
+        runQuery(fromjson("{x: 1, y: {$exists: false}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, ExistsTrueSparseIndexOnOtherField) {
+        addIndex(BSON("x" << 1), false, true);
+
+        runQuery(fromjson("{x: 1, y: {$exists: true}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, ExistsFalseSparseIndexOnOtherField) {
+        addIndex(BSON("x" << 1), false, true);
+
         runQuery(fromjson("{x: 1, y: {$exists: false}}"));
 
         assertNumSolutions(2U);