SERVER-17656: First pass implementation of partial indexes

18 files changed, 780 insertions, 12 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index 98d37861b2a..833834c735c 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -194,6 +194,14 @@ env.Library('expressions',
                      '$BUILD_DIR/third_party/shim_pcrecpp'
                      ] )
 
+env.Library('expression_algo',
+            ['db/matcher/expression_algo.cpp'],
+            LIBDEPS=['expressions'])
+
+env.CppUnitTest('expression_algo_test',
+            ['db/matcher/expression_algo_test.cpp'],
+            LIBDEPS=['expression_algo'])
+
 env.Library('expressions_geo',
             ['db/matcher/expression_geo.cpp',
              'db/matcher/expression_parser_geo.cpp'],
diff --git a/src/mongo/db/catalog/collection.cpp b/src/mongo/db/catalog/collection.cpp
index 9f4095c589d..2940e9c7c9b 100644
--- a/src/mongo/db/catalog/collection.cpp
+++ b/src/mongo/db/catalog/collection.cpp
@@ -330,7 +330,8 @@ namespace mongo {
             IndexCatalog::IndexIterator ii = _indexCatalog.getIndexIterator( txn, true );
             while ( ii.more() ) {
                 IndexDescriptor* descriptor = ii.next();
-                IndexAccessMethod* iam = _indexCatalog.getIndex( descriptor );
+                IndexCatalogEntry* entry = ii.catalogEntry(descriptor);
+                IndexAccessMethod* iam = ii.accessMethod( descriptor );
 
                 InsertDeleteOptions options;
                 options.logIfError = false;
@@ -344,7 +345,8 @@ namespace mongo {
                                                  objNew,
                                                  oldLocation,
                                                  options,
-                                                 updateTicket);
+                                                 updateTicket,
+                                                 entry->getFilterExpression());
                 if ( !ret.isOK() ) {
                     return StatusWith<RecordId>( ret );
                 }
@@ -395,7 +397,7 @@ namespace mongo {
             IndexCatalog::IndexIterator ii = _indexCatalog.getIndexIterator( txn, true );
             while ( ii.more() ) {
                 IndexDescriptor* descriptor = ii.next();
-                IndexAccessMethod* iam = _indexCatalog.getIndex( descriptor );
+                IndexAccessMethod* iam = ii.accessMethod(descriptor);
 
                 int64_t updatedKeys;
                 Status ret = iam->update(
@@ -434,6 +436,7 @@ namespace mongo {
                                                   const Snapshotted<RecordData>& oldRec,
                                                   const char* damageSource,
                                                   const mutablebson::DamageVector& damages ) {
+
         dassert(txn->lockState()->isCollectionLockedForMode(ns().toString(), MODE_IX));
         invariant(oldRec.snapshotId() == txn->recoveryUnit()->getSnapshotId());
 
diff --git a/src/mongo/db/catalog/collection_info_cache.cpp b/src/mongo/db/catalog/collection_info_cache.cpp
index a4c0975af68..96ef192ec65 100644
--- a/src/mongo/db/catalog/collection_info_cache.cpp
+++ b/src/mongo/db/catalog/collection_info_cache.cpp
@@ -40,10 +40,10 @@
 #include "mongo/db/index/index_descriptor.h"
 #include "mongo/db/index_legacy.h"
 #include "mongo/db/query/plan_cache.h"
+#include "mongo/db/query/planner_ixselect.h"
 #include "mongo/util/debug_util.h"
 #include "mongo/util/log.h"
 
-
 namespace mongo {
 
     CollectionInfoCache::CollectionInfoCache( Collection* collection )
@@ -108,6 +108,17 @@ namespace mongo {
                     _indexedPaths.addPathComponent(ftsSpec.languageOverrideField());
                 }
             }
+
+            // handle filtered indexes
+            const IndexCatalogEntry* entry = i.catalogEntry(descriptor);
+            const MatchExpression* filter = entry->getFilterExpression();
+            if (filter) {
+                unordered_set<std::string> paths;
+                QueryPlannerIXSelect::getFields(filter, "", &paths);
+                for (auto it = paths.begin(); it != paths.end(); ++it) {
+                    _indexedPaths.addPath(*it);
+                }
+            }
         }
 
         _keysComputed = true;
diff --git a/src/mongo/db/catalog/index_catalog.cpp b/src/mongo/db/catalog/index_catalog.cpp
index 2c3c5853a93..cc8748cd279 100644
--- a/src/mongo/db/catalog/index_catalog.cpp
+++ b/src/mongo/db/catalog/index_catalog.cpp
@@ -54,6 +54,7 @@
 #include "mongo/db/index_names.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/keypattern.h"
+#include "mongo/db/matcher/expression.h"
 #include "mongo/db/ops/delete.h"
 #include "mongo/db/query/internal_plans.h"
 #include "mongo/db/repl/replication_coordinator_global.h"
@@ -449,6 +450,39 @@ namespace {
         entry->setIsReady( true );
     }
 
+    namespace {
+        // While technically recursive, only current possible with 2 levels.
+        Status _checkValidFilterExpressions(MatchExpression* expression, int level = 0) {
+            if (!expression)
+                return Status::OK();
+
+            switch(expression->matchType()) {
+            case MatchExpression::AND:
+                if (level > 0)
+                    return Status(ErrorCodes::BadValue,
+                                  "$and only supported in filter at top level");
+                for (size_t i = 0; i < expression->numChildren(); i++) {
+                    Status status = _checkValidFilterExpressions(expression->getChild(i),
+                                                                 level + 1 );
+                    if (!status.isOK())
+                        return status;
+                }
+                return Status::OK();
+            case MatchExpression::EQ:
+            case MatchExpression::LT:
+            case MatchExpression::LTE:
+            case MatchExpression::GT:
+            case MatchExpression::GTE:
+            case MatchExpression::EXISTS:
+            case MatchExpression::TYPE_OPERATOR:
+                return Status::OK();
+            default:
+                return Status(ErrorCodes::BadValue,
+                              str::stream() << "unsupported expression in filtered index: "
+                              << expression->toString());
+            }
+        }
+    }
 
     Status IndexCatalog::_isSpecOk( const BSONObj& spec ) const {
 
@@ -542,6 +576,26 @@ namespace {
             }
         }
 
+        // Ensure if there is a filter, its valid.
+        BSONElement filterElement = spec.getField("filter");
+        if ( filterElement.type() ) {
+            if ( filterElement.type() != Object ) {
+                return Status(ErrorCodes::BadValue,
+                              "'filter' for an index has to be a document");
+            }
+            StatusWithMatchExpression res = MatchExpressionParser::parse( filterElement.Obj() );
+            if ( !res.isOK() ) {
+                return res.getStatus();
+            }
+
+            Status status = _checkValidFilterExpressions(res.getValue());
+            if (!status.isOK()) {
+                return status;
+            }
+        }
+
+        // --- only storage engine checks allowed below this ----
+
         BSONElement storageEngineElement = spec.getField("storageEngine");
         if (storageEngineElement.eoo()) {
             return Status::OK();
@@ -924,11 +978,16 @@ namespace {
         return _prev->descriptor();
     }
 
-    IndexAccessMethod* IndexCatalog::IndexIterator::accessMethod( IndexDescriptor* desc ) {
+    IndexAccessMethod* IndexCatalog::IndexIterator::accessMethod( const IndexDescriptor* desc ) {
         invariant( desc == _prev->descriptor() );
         return _prev->accessMethod();
     }
 
+    IndexCatalogEntry* IndexCatalog::IndexIterator::catalogEntry( const IndexDescriptor* desc ) {
+        invariant( desc == _prev->descriptor() );
+        return _prev;
+    }
+
     void IndexCatalog::IndexIterator::_advance() {
         _next = NULL;
 
@@ -1084,6 +1143,11 @@ namespace {
                                       IndexCatalogEntry* index,
                                       const BSONObj& obj,
                                       const RecordId &loc ) {
+        const MatchExpression* filter = index->getFilterExpression();
+        if ( filter && !filter->matchesBSON( obj ) ) {
+            return Status::OK();
+        }
+
         InsertDeleteOptions options;
         options.logIfError = false;
         options.dupsAllowed = isDupsAllowed( index->descriptor() );
diff --git a/src/mongo/db/catalog/index_catalog.h b/src/mongo/db/catalog/index_catalog.h
index f71e094d9aa..38efeb28567 100644
--- a/src/mongo/db/catalog/index_catalog.h
+++ b/src/mongo/db/catalog/index_catalog.h
@@ -143,7 +143,11 @@ namespace mongo {
             IndexDescriptor* next();
 
             // returns the access method for the last return IndexDescriptor
-            IndexAccessMethod* accessMethod( IndexDescriptor* desc );
+            IndexAccessMethod* accessMethod( const IndexDescriptor* desc );
+
+            // returns the IndexCatalogEntry for the last return IndexDescriptor
+            IndexCatalogEntry* catalogEntry( const IndexDescriptor* desc );
+
         private:
             IndexIterator( OperationContext* txn,
                            const IndexCatalog* cat,
diff --git a/src/mongo/db/catalog/index_catalog_entry.cpp b/src/mongo/db/catalog/index_catalog_entry.cpp
index dba5f12bbf9..7ad596f0f50 100644
--- a/src/mongo/db/catalog/index_catalog_entry.cpp
+++ b/src/mongo/db/catalog/index_catalog_entry.cpp
@@ -40,6 +40,8 @@
 #include "mongo/db/index/index_access_method.h"
 #include "mongo/db/index/index_descriptor.h"
 #include "mongo/db/global_environment_experiment.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/operation_context.h"
 #include "mongo/util/file_allocator.h"
 #include "mongo/util/log.h"
@@ -99,6 +101,19 @@ namespace mongo {
         _isReady = _catalogIsReady( txn );
         _head = _catalogHead( txn );
         _isMultikey = _catalogIsMultikey( txn );
+
+        BSONElement filterElement = _descriptor->getInfoElement("filter");
+        if ( filterElement.type() ) {
+            invariant( filterElement.isABSONObj() );
+            BSONObj filter = filterElement.Obj();
+            StatusWithMatchExpression res = MatchExpressionParser::parse( filter );
+            // this should be checked in create, so can blow up here
+            invariantOK( res.getStatus() );
+            _filterExpression.reset( res.getValue() );
+            LOG(2) << "have filter expression for "
+                   << _ns << " " << _descriptor->indexName()
+                   << " " << filter;
+        }
     }
 
     const RecordId& IndexCatalogEntry::head( OperationContext* txn ) const {
diff --git a/src/mongo/db/catalog/index_catalog_entry.h b/src/mongo/db/catalog/index_catalog_entry.h
index 73a9bbea7b7..770aec496e2 100644
--- a/src/mongo/db/catalog/index_catalog_entry.h
+++ b/src/mongo/db/catalog/index_catalog_entry.h
@@ -43,6 +43,7 @@ namespace mongo {
     class HeadManager;
     class IndexAccessMethod;
     class IndexDescriptor;
+    class MatchExpression;
     class OperationContext;
 
     class IndexCatalogEntry {
@@ -68,6 +69,8 @@ namespace mongo {
 
         const Ordering& ordering() const { return _ordering; }
 
+        const MatchExpression* getFilterExpression() const { return _filterExpression.get(); }
+
         /// ---------------------
 
         const RecordId& head( OperationContext* txn ) const;
@@ -110,6 +113,7 @@ namespace mongo {
 
         // Owned here.
         HeadManager* _headManager;
+        boost::scoped_ptr<MatchExpression> _filterExpression;
 
         // cached stuff
 
diff --git a/src/mongo/db/catalog/index_create.cpp b/src/mongo/db/catalog/index_create.cpp
index ac39d01e027..658978eb1bd 100644
--- a/src/mongo/db/catalog/index_create.cpp
+++ b/src/mongo/db/catalog/index_create.cpp
@@ -203,6 +203,8 @@ namespace mongo {
             if (index.bulk)
                 log() << "\t building index using bulk method";
 
+            index.filterExpression = index.block->getEntry()->getFilterExpression();
+
             // TODO SERVER-14888 Suppress this in cases we don't want to audit.
             audit::logCreateIndex(_txn->getClient(), &info, descriptor->indexName(), ns);
 
@@ -335,6 +337,12 @@ namespace mongo {
 
     Status MultiIndexBlock::insert(const BSONObj& doc, const RecordId& loc) {
         for ( size_t i = 0; i < _indexes.size(); i++ ) {
+
+            if ( _indexes[i].filterExpression &&
+                 !_indexes[i].filterExpression->matchesBSON(doc) ) {
+                continue;
+            }
+
             int64_t unused;
             Status idxStatus(ErrorCodes::InternalError, "");
             if (_indexes[i].bulk) {
diff --git a/src/mongo/db/catalog/index_create.h b/src/mongo/db/catalog/index_create.h
index 5e346e16f6b..9c0b11ed02a 100644
--- a/src/mongo/db/catalog/index_create.h
+++ b/src/mongo/db/catalog/index_create.h
@@ -206,11 +206,13 @@ namespace mongo {
                 , real(std::move(other.real))
                 , bulk(std::move(other.bulk))
                 , options(std::move(other.options))
+                , filterExpression(std::move(other.filterExpression))
             {}
 
             IndexToBuild& operator= (IndexToBuild&& other) {
                 block = std::move(other.block);
                 real = std::move(other.real);
+                filterExpression = std::move(other.filterExpression);
                 bulk = std::move(other.bulk);
                 options = std::move(other.options);
                 return *this;
@@ -220,6 +222,7 @@ namespace mongo {
             std::unique_ptr<IndexCatalog::IndexBuildBlock> block;
 
             IndexAccessMethod* real = NULL; // owned elsewhere
+            const MatchExpression* filterExpression; // might be NULL, owned elsewhere
             std::unique_ptr<IndexAccessMethod::BulkBuilder> bulk;
 
             InsertDeleteOptions options;
diff --git a/src/mongo/db/index/index_access_method.cpp b/src/mongo/db/index/index_access_method.cpp
index ad8f7c8f06f..0b76b407339 100644
--- a/src/mongo/db/index/index_access_method.cpp
+++ b/src/mongo/db/index/index_access_method.cpp
@@ -275,10 +275,13 @@ namespace mongo {
                                              const BSONObj &to,
                                              const RecordId &record,
                                              const InsertDeleteOptions &options,
-                                             UpdateTicket* ticket) {
+                                             UpdateTicket* ticket,
+                                             const MatchExpression* indexFilter) {
 
-        getKeys(from, &ticket->oldKeys);
-        getKeys(to, &ticket->newKeys);
+        if (indexFilter == NULL || indexFilter->matchesBSON(from))
+            getKeys(from, &ticket->oldKeys);
+        if (indexFilter == NULL || indexFilter->matchesBSON(to))
+            getKeys(to, &ticket->newKeys);
         ticket->loc = record;
         ticket->dupsAllowed = options.dupsAllowed;
 
diff --git a/src/mongo/db/index/index_access_method.h b/src/mongo/db/index/index_access_method.h
index 19361a398de..fea0c8e4a10 100644
--- a/src/mongo/db/index/index_access_method.h
+++ b/src/mongo/db/index/index_access_method.h
@@ -42,6 +42,7 @@
 namespace mongo {
 
     class BSONObjBuilder;
+    class MatchExpression;
     class UpdateTicket;
     struct InsertDeleteOptions;
 
@@ -105,7 +106,8 @@ namespace mongo {
                               const BSONObj& to,
                               const RecordId& loc,
                               const InsertDeleteOptions& options,
-                              UpdateTicket* ticket);
+                              UpdateTicket* ticket,
+                              const MatchExpression* indexFilter);
 
         /**
          * Perform a validated update.  The keys for the 'from' object will be removed, and the keys
diff --git a/src/mongo/db/matcher/expression_algo.cpp b/src/mongo/db/matcher/expression_algo.cpp
new file mode 100644
index 00000000000..9268db2dd00
--- /dev/null
+++ b/src/mongo/db/matcher/expression_algo.cpp
@@ -0,0 +1,291 @@
+// expression_algo.cpp
+
+/**
+ *    Copyright (C) 2015 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kDefault
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+#include "mongo/util/log.h"
+
+//#define DDD(x) log() << x
+#define DDD(x)
+
+namespace mongo {
+    namespace {
+
+        bool _pathMatches(const LeafMatchExpression* left,
+                          const MatchExpression* bar) {
+            invariant(left);
+            invariant(bar);
+            const LeafMatchExpression* right = dynamic_cast<const LeafMatchExpression*>(bar);
+            if (!right)
+                return false;
+
+            return left->path() == right->path();
+        }
+
+        bool _typeAndPathCompatable(const ComparisonMatchExpression* left,
+                                    const ComparisonMatchExpression* right) {
+            if (!_pathMatches(left, right))
+                return false;
+
+            if (left->getData().canonicalType() != right->getData().canonicalType())
+                return false;
+
+            return true;
+        }
+
+
+        bool _isRedundantEQHelp(const ComparisonMatchExpression* left,
+                                const MatchExpression* bar,
+                                bool isLessThan,
+                                bool equalOk) {
+            const ComparisonMatchExpression* right =
+                dynamic_cast<const ComparisonMatchExpression*>(bar);
+            invariant(right);
+
+            if (!_typeAndPathCompatable(left, right))
+                return false;
+
+            int cmp = left->getData().woCompare(right->getData(), false);
+            if (isLessThan) {
+                if (cmp < 0)
+                    return true;
+                if (cmp == 0)
+                    return equalOk;
+                return false;
+            }
+
+            if (cmp > 0)
+                return true;
+            if (cmp == 0)
+                return equalOk;
+            return false;
+        }
+
+        /**
+         * @param foo is a literal something that has to match exactly
+         * @return if the expression bar guarantees returning any document matching foo
+         */
+        bool isRedundantEQ(const MatchExpression* foo,
+                           const MatchExpression* bar) {
+            const ComparisonMatchExpression* equal =
+                dynamic_cast<const ComparisonMatchExpression*>(foo);
+            invariant(equal);
+
+            DDD("isRedundantEQ");
+
+            switch(bar->matchType()) {
+            case MatchExpression::EQ:
+                // would be handled elsewhere
+                return false;
+
+            case MatchExpression::LT:
+                return _isRedundantEQHelp(equal, bar, true, false);
+            case MatchExpression::LTE:
+                return _isRedundantEQHelp(equal, bar, true, true);
+
+            case MatchExpression::GT:
+                return _isRedundantEQHelp(equal, bar, false, false);
+            case MatchExpression::GTE:
+                return _isRedundantEQHelp(equal, bar, false, true);
+
+            case MatchExpression::EXISTS: {
+                switch (equal->getData().type()) {
+                case jstNULL:
+                case Undefined:
+                case EOO:
+                    return false;
+                default:
+                    return _pathMatches(equal, bar);
+                }
+            }
+
+            default:
+                return false;
+            }
+        }
+
+        bool isRedundantLT(const MatchExpression* foo,
+                           const MatchExpression* bar,
+                           bool equalOk) {
+            const ComparisonMatchExpression* left =
+                dynamic_cast<const ComparisonMatchExpression*>(foo);
+            invariant(left);
+
+
+            if(bar->matchType() == MatchExpression::LT ||
+               bar->matchType() == MatchExpression::LTE ) {
+
+                const ComparisonMatchExpression* right =
+                    dynamic_cast<const ComparisonMatchExpression*>(bar);
+                invariant(right);
+
+                if (!_typeAndPathCompatable(left, right))
+                    return false;
+
+                int cmp = left->getData().woCompare(right->getData(), false);
+                if (cmp == 0) {
+                    if(bar->matchType() == MatchExpression::LTE)
+                        return true;
+                    if(!equalOk)
+                        return true;
+                    return false;
+                }
+                return cmp < 0;
+            }
+            else if(bar->matchType() == MatchExpression::EXISTS) {
+                return _pathMatches(left, bar);
+            }
+
+            return false;
+        }
+
+        bool isRedundantGT(const MatchExpression* foo,
+                           const MatchExpression* bar,
+                           bool equalOk) {
+            const ComparisonMatchExpression* left =
+                dynamic_cast<const ComparisonMatchExpression*>(foo);
+            invariant(left);
+
+
+            if(bar->matchType() == MatchExpression::GT ||
+               bar->matchType() == MatchExpression::GTE ) {
+
+                const ComparisonMatchExpression* right =
+                    dynamic_cast<const ComparisonMatchExpression*>(bar);
+                invariant(right);
+
+                if (!_typeAndPathCompatable(left, right))
+                    return false;
+
+                int cmp = left->getData().woCompare(right->getData(), false);
+                if (cmp == 0) {
+                    if(bar->matchType() == MatchExpression::GTE)
+                        return true;
+                    if(!equalOk)
+                        return true;
+                    return false;
+                }
+                return cmp > 0;
+            }
+            else if(bar->matchType() == MatchExpression::EXISTS) {
+                return _pathMatches(left, bar);
+            }
+
+            return false;
+        }
+
+    }
+
+
+
+    namespace expression {
+
+        bool isClauseRedundant(const MatchExpression* foo,
+                               const MatchExpression* bar) {
+
+            if (bar == NULL ||
+                foo == bar) {
+                return true;
+            }
+            if (foo == NULL) {
+                return false;
+            }
+
+
+            DDD("isClauseRedundant\n"
+                << "foo: " << foo->toString()
+                << "bar: " << bar->toString());
+
+            if (foo->equivalent(bar)) {
+                DDD("t equivalent!");
+                return true;
+            }
+
+            switch(foo->matchType()) {
+            case MatchExpression::AND: {
+                for (size_t i = 0; i < foo->numChildren(); i++ ) {
+                    if(isClauseRedundant(foo->getChild(i), bar)) {
+                        return true;
+                    }
+                }
+
+                if (bar->matchType() == MatchExpression::AND) {
+                    // everything in bar has to appear in foo
+                    for (size_t i = 0; i < bar->numChildren(); i++ ) {
+                        if(!isClauseRedundant(foo, bar->getChild(i))) {
+                            return false;
+                        }
+                    }
+                    return true;
+                }
+
+                return false;
+            }
+            case MatchExpression::OR: {
+                // TODO: $or each clause has to be redundant
+                return false;
+            }
+
+            case MatchExpression::EQ:
+                return isRedundantEQ(foo, bar);
+
+            case MatchExpression::LT:
+                return isRedundantLT(foo, bar, false);
+            case MatchExpression::LTE:
+                return isRedundantLT(foo, bar, true);
+
+            case MatchExpression::GT:
+                return isRedundantGT(foo, bar, false);
+            case MatchExpression::GTE:
+                return isRedundantGT(foo, bar, true);
+
+            case MatchExpression::TYPE_OPERATOR: {
+                if (bar->matchType() != MatchExpression::EXISTS) {
+                    return false;
+                }
+
+                const TypeMatchExpression* a = dynamic_cast<const TypeMatchExpression*>(foo);
+                const ExistsMatchExpression* b = dynamic_cast<const ExistsMatchExpression*>(bar);
+
+                return a->path() == b->path();
+            }
+
+            default:
+                return false;
+            }
+
+            return false;
+        }
+    }
+}
diff --git a/src/mongo/db/matcher/expression_algo.h b/src/mongo/db/matcher/expression_algo.h
new file mode 100644
index 00000000000..8e3b7bd701c
--- /dev/null
+++ b/src/mongo/db/matcher/expression_algo.h
@@ -0,0 +1,50 @@
+// expression_algo.h
+
+/**
+ *    Copyright (C) 2015 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+namespace mongo {
+
+    class MatchExpression;
+
+    namespace expression {
+        /**
+         * In filtered index case, a is the query, b is the filter.
+         * @return If 'b' cannot reduce the set of returned documents that would
+         *         be returned with 'a' as the only filter.
+         *         Everything that matches a also must match b.
+         *         The document set returned by applying a is a subset of the document
+         *         set returned by applying b.
+         * Examples:
+         *    a: { x : 5 } b: { x : { $lte : 5 } } = true
+         *    a: { x : { $lte : 5 } b: { x : 5 } = false
+         */
+        bool isClauseRedundant(const MatchExpression* a,
+                               const MatchExpression* b);
+    }
+}
diff --git a/src/mongo/db/matcher/expression_algo_test.cpp b/src/mongo/db/matcher/expression_algo_test.cpp
new file mode 100644
index 00000000000..65309c0d3a3
--- /dev/null
+++ b/src/mongo/db/matcher/expression_algo_test.cpp
@@ -0,0 +1,278 @@
+// expression_algo_test.cpp
+
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/unittest/unittest.h"
+
+#include <boost/scoped_ptr.hpp>
+
+#include "mongo/db/jsobj.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_algo.h"
+#include "mongo/db/matcher/expression_parser.h"
+
+#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kDefault
+#include "mongo/util/log.h"
+
+namespace mongo {
+
+    using boost::scoped_ptr;
+
+    /**
+     * A MatchExpression does not hold the memory for BSONElements.
+     * So using this we can tie the life cycle of a MatchExpression to its data.
+     */
+    struct Parsed {
+        Parsed(const char* str) {
+            obj = fromjson(str);
+            _parse();
+        }
+
+        Parsed(const BSONObj& o)
+            : obj(o) {
+            _parse();
+        }
+
+        void _parse() {
+            StatusWithMatchExpression result = MatchExpressionParser::parse(obj);
+            if (!result.isOK()) {
+                log() << "failed to parse expression: " << obj;
+                invariant(false);
+            }
+            exp.reset(result.getValue());
+        }
+
+        const MatchExpression* get() const { return exp.get(); }
+
+        BSONObj obj;
+        scoped_ptr<MatchExpression> exp;
+    };
+
+    TEST(ExpressionAlgoRedundant, Equal1) {
+        Parsed foo("{ x : 5 }");
+        Parsed bar1("{ x : 5 }");
+        Parsed bar2("{ x : 6 }");
+        Parsed bar3("{ a : 5 }");
+        ASSERT_TRUE(expression::isClauseRedundant(foo.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar3.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, AndEqual1) {
+        Parsed foo("{ a : 3, x : 5 }");
+        Parsed bar1("{ x : 5 }");
+        Parsed bar2("{ x : 6 }");
+        Parsed bar3("{ a : 5 }");
+        ASSERT_TRUE(expression::isClauseRedundant(foo.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar3.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(bar1.get(), foo.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, DifferentTypes1) {
+        // Comparison of different canonical types is not redundant.
+        Parsed foo("{x: {$gt: \"a\"}}");
+        Parsed bar("{x: {$gt: 1}}");
+        ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(bar.get(), foo.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, DifferentTypes2) {
+        Parsed foo("{x: null}");
+        Parsed bar("{x: {$exists: true}}");
+        ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, PointToRange) {
+        Parsed foo1("{ x : 4 }");
+        Parsed foo2("{ x : 5 }");
+        Parsed foo3("{ a : 4 }");
+        Parsed foo4("{ x : 6 }");
+        Parsed foo5("{ a : 6 }");
+
+        Parsed bar1("{ x : { $lte : 5 } }");
+        Parsed bar2("{ x : { $lt : 5 } }");
+        Parsed bar3("{ x : { $gte : 5 } }");
+        Parsed bar4("{ x : { $gt : 5 } }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar1.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(bar1.get(), foo1.get()));
+
+        ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo2.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar2.get()));
+
+        ASSERT_FALSE(expression::isClauseRedundant(foo1.get(), bar3.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar3.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar3.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo4.get(), bar3.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar3.get()));
+
+        ASSERT_FALSE(expression::isClauseRedundant(foo1.get(), bar4.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo2.get(), bar4.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar4.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo4.get(), bar4.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar4.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, LessThanToLessThan) {
+        Parsed foo1("{ x : { $lte : 4 } }");
+        Parsed foo2("{ x : { $lt : 5 } }");
+        Parsed foo3("{ x : { $lte : 5 } }");
+        Parsed foo4("{ x : { $lte : 6 } }");
+        Parsed foo5("{ a : { $lte : 4 } }");
+
+        Parsed bar1("{ x : { $lte : 5 } }");
+        Parsed bar2("{ x : { $lt : 5 } }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar1.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar1.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo3.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar1.get()));
+
+        ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar2.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar2.get()));
+
+    }
+
+    TEST(ExpressionAlgoRedundant, GreaterThanToGreaterThan) {
+        Parsed foo1("{ x : { $gte : 6 } }");
+        Parsed foo2("{ x : { $gt : 5 } }");
+        Parsed foo3("{ x : { $gte : 5 } }");
+        Parsed foo4("{ x : { $gte : 4 } }");
+        Parsed foo5("{ a : { $gte : 6 } }");
+
+        Parsed bar1("{ x : { $gte : 5 } }");
+        Parsed bar2("{ x : { $gt : 5 } }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar1.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar1.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo3.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar1.get()));
+
+        ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar2.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar2.get()));
+
+    }
+
+    TEST(ExpressionAlgoRedundant, Exists1) {
+        Parsed a("{a : { $exists : 1 } }");
+        Parsed b("{b : { $exists : 1 } }");
+        Parsed ab("{a : { $exists : 1 }, b : { $exists: 1 } }");
+        Parsed abc("{a : { $exists : 1 }, b : { $exists: 1 }, c : 5 }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(a.get(), a.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(a.get(), b.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(b.get(), a.get()));
+
+        ASSERT_TRUE(expression::isClauseRedundant(ab.get(), a.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(ab.get(), b.get()));
+
+        ASSERT_TRUE(expression::isClauseRedundant(abc.get(), a.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(abc.get(), b.get()));
+
+        ASSERT_TRUE(expression::isClauseRedundant(abc.get(), ab.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(ab.get(), abc.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, Exists2) {
+        Parsed filter("{a : { $exists : 1 } }");
+        Parsed query1("{a : 1}");
+        Parsed query2("{a : { $gt : 4 } }");
+        Parsed query3("{a : { $lt : 4 } }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(query1.get(), filter.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(query2.get(), filter.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(query3.get(), filter.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, Exists3) {
+        Parsed filter("{a : { $exists : 1 } }");
+        Parsed query1("{a : { $type : 5 } }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(query1.get(), filter.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, Exists4) {
+        Parsed filter("{a : { $exists : 1 } }");
+        Parsed query1("{b : { $type : 5 } }");
+
+        ASSERT_FALSE(expression::isClauseRedundant(query1.get(), filter.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, Type1) {
+        Parsed a("{a : { $type : 4 } }");
+        Parsed a2("{a : { $type : 4 } }");
+        Parsed b("{a : { $type : 7 } }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(a.get(), a2.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(a.get(), b.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, Subset1) {
+        Parsed filter("{ a : 5, b : 6 }");
+        Parsed query("{ a : 5, b : 6, c : 7 }");
+
+        ASSERT_TRUE(expression::isClauseRedundant(query.get(), filter.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query.get()));
+    }
+
+    TEST(ExpressionAlgoRedundant, Subset2) {
+        Parsed filter("{ a : { $gt : 5 }, b : { $gt : 6 } }");
+        Parsed query1("{ a : { $gt : 5 }, b : { $gt : 6 }, c : { $gt : 7 } }");
+        Parsed query2("{ a : 10, b : 10, c : 10 }");
+
+        ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get()));
+        ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query2.get()));
+
+        ASSERT_TRUE(expression::isClauseRedundant(query1.get(), filter.get()));
+        ASSERT_TRUE(expression::isClauseRedundant(query2.get(), filter.get()));
+
+    }
+
+}
+
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index f62c56c9756..11d985b5cda 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -47,6 +47,7 @@ env.Library(
     LIBDEPS=[
         "query_planner",
         "query_planner_test_lib",
+        "$BUILD_DIR/mongo/expression_algo",
         "$BUILD_DIR/mongo/db/exec/exec"
     ],
 )
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp
index ab2ed9b3e22..7a17b0ca610 100644
--- a/src/mongo/db/query/get_executor.cpp
+++ b/src/mongo/db/query/get_executor.cpp
@@ -51,6 +51,7 @@
 #include "mongo/db/exec/subplan.h"
 #include "mongo/db/exec/update.h"
 #include "mongo/db/global_environment_experiment.h"
+#include "mongo/db/matcher/expression_algo.h"
 #include "mongo/db/ops/update_lifecycle.h"
 #include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/explain.h"
@@ -111,6 +112,20 @@ namespace mongo {
     namespace {
         // The body is below in the "count hack" section but getExecutor calls it.
         bool turnIxscanIntoCount(QuerySolution* soln);
+
+        bool filteredIndexBad(const MatchExpression* filter, CanonicalQuery* query) {
+            if (!filter)
+                return false;
+
+            MatchExpression* queryPredicates = query->root();
+            if (!queryPredicates) {
+                // Index is filtered, but query has none.
+                // Impossible to use index.
+                return true;
+            }
+
+            return !expression::isClauseRedundant(queryPredicates, filter);
+        }
     }  // namespace
 
 
@@ -123,6 +138,12 @@ namespace mongo {
                                                                                          false);
         while (ii.more()) {
             const IndexDescriptor* desc = ii.next();
+
+            IndexCatalogEntry* ice = ii.catalogEntry(desc);
+            if (filteredIndexBad(ice->getFilterExpression(), canonicalQuery)) {
+                continue;
+            }
+
             plannerParams->indices.push_back(IndexEntry(desc->keyPattern(),
                                                         desc->getAccessMethodName(),
                                                         desc->isMultikey(txn),
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 635517453db..c99743b4ca4 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -72,7 +72,7 @@ namespace mongo {
     }
 
     // static
-    void QueryPlannerIXSelect::getFields(MatchExpression* node,
+    void QueryPlannerIXSelect::getFields(const MatchExpression* node,
                                          string prefix,
                                          unordered_set<string>* out) {
         // Do not traverse tree beyond a NOR negation node
diff --git a/src/mongo/db/query/planner_ixselect.h b/src/mongo/db/query/planner_ixselect.h
index 486ce4a42e5..ad5912222a1 100644
--- a/src/mongo/db/query/planner_ixselect.h
+++ b/src/mongo/db/query/planner_ixselect.h
@@ -46,7 +46,9 @@ namespace mongo {
          * The 'prefix' argument is a path prefix to be prepended to any fields mentioned in
          * predicates encountered.  Some array operators specify a path prefix.
          */
-        static void getFields(MatchExpression* node, std::string prefix, unordered_set<std::string>* out);
+        static void getFields(const MatchExpression* node,
+                              std::string prefix,
+                              unordered_set<std::string>* out);
 
         /**
          * Find all indices prefixed by fields we have predicates over.  Only these indices are