SERVER-10471 multikey correctness, fix compound idxs, a few bug fixes

18 files changed, 415 insertions, 212 deletions

diff --git a/src/mongo/db/exec/index_scan.cpp b/src/mongo/db/exec/index_scan.cpp
index ff9490549e0..1305c861f46 100644
--- a/src/mongo/db/exec/index_scan.cpp
+++ b/src/mongo/db/exec/index_scan.cpp
@@ -201,7 +201,12 @@ namespace mongo {
 
         if (isEOF() || (NULL == _indexCursor.get())) { return; }
 
-        _indexCursor->restorePosition();
+        // We can have a valid position before we check isEOF(), restore the position, and then be
+        // EOF upon restore.
+        if (!_indexCursor->restorePosition().isOK() || _indexCursor->isEOF()) {
+            _hitEnd = true;
+            return;
+        }
 
         if (!_savedKey.binaryEqual(_indexCursor->getKey())
             || _savedLoc != _indexCursor->getValue()) {
diff --git a/src/mongo/db/exec/projection.cpp b/src/mongo/db/exec/projection.cpp
index e6f62f9f47a..542013fac38 100644
--- a/src/mongo/db/exec/projection.cpp
+++ b/src/mongo/db/exec/projection.cpp
@@ -54,7 +54,10 @@ namespace mongo {
         if (PlanStage::ADVANCED == status) {
             WorkingSetMember* member = _ws->get(id);
             Status status = ProjectionExecutor::apply(_projection, member);
-            if (!status.isOK()) { return PlanStage::FAILURE; }
+            if (!status.isOK()) {
+                warning() << "Couldn't execute projection: " << status.toString() << endl;
+                return PlanStage::FAILURE;
+            }
             *out = id;
         }
         else if (PlanStage::NEED_FETCH == status) {
diff --git a/src/mongo/db/exec/projection_executor.cpp b/src/mongo/db/exec/projection_executor.cpp
index fbf043d6b19..9af491e6a58 100644
--- a/src/mongo/db/exec/projection_executor.cpp
+++ b/src/mongo/db/exec/projection_executor.cpp
@@ -60,6 +60,10 @@ namespace mongo {
             // We only want stuff in _fields.
             const vector<string>& fields = proj->_includedFields;
             for (size_t i = 0; i < fields.size(); ++i) {
+                if ("_id" == fields[i]) {
+                    continue;
+                }
+
                 BSONElement elt;
                 // We can project a field that doesn't exist.  We just ignore it.
                 // UNITTEST 11738048
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index f11f40daf47..65aba387925 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -122,6 +122,32 @@ namespace mongo {
         }
     }
 
+    Status isValid(MatchExpression* root) {
+        // XXX: There can only be one NEAR.  If there is a NEAR, it must be either the root or the
+        // root must be an AND and its child must be a NEAR.
+
+        MatchExpression::MatchType type = root->matchType();
+
+        if (MatchExpression::GT == type || MatchExpression::GTE == type
+            || MatchExpression::LT == type || MatchExpression::LTE == type) {
+
+            ComparisonMatchExpression* cme = static_cast<ComparisonMatchExpression*>(root);
+            BSONElement data = cme->getData();
+            if (RegEx == data.type()) {
+                return Status(ErrorCodes::BadValue, "Can't have RegEx as arg to pred " + cme->toString());
+            }
+        }
+
+        for (size_t i = 0; i < root->numChildren(); ++i) {
+            Status s = isValid(root->getChild(i));
+            if (!s.isOK()) {
+                return s;
+            }
+        }
+
+        return Status::OK();
+    }
+
     Status CanonicalQuery::init(LiteParsedQuery* lpq) {
         _pq.reset(lpq);
 
@@ -131,6 +157,11 @@ namespace mongo {
 
         MatchExpression* root = swme.getValue();
         normalizeTree(root);
+        Status validStatus = isValid(root);
+        if (!validStatus.isOK()) {
+            return validStatus;
+        }
+
         _root.reset(root);
 
         if (!_pq->getProj().isEmpty()) {
diff --git a/src/mongo/db/query/index_bounds.h b/src/mongo/db/query/index_bounds.h
index e3d82066ee5..58ca8f0570c 100644
--- a/src/mongo/db/query/index_bounds.h
+++ b/src/mongo/db/query/index_bounds.h
@@ -60,44 +60,6 @@ namespace mongo {
         // For each indexed field, the values that the field is allowed to take on.
         vector<OrderedIntervalList> fields;
 
-        /**
-         * The provided oil is AND-related to the bounds.  If we have an existing oil over the
-         * field, intersect.  Otherwise, add it to the right location in 'fields'.
-         */
-        void joinAnd(const OrderedIntervalList& oil, const BSONObj& keyPattern) {
-            // cout << "merging oil " << oil.name << " with bounds: " << toString() << endl;
-            // Only disjoint OILs are handled right now.
-            for (size_t i = 0; i < fields.size(); ++i) {
-                if (oil.name == fields[i].name) {
-                    warning() << "Have not implemented OIL-OIL merging yet.";
-                    verify(0);
-                }
-            }
-
-            // Figure out our position in 'fields' from 'keyPattern'
-            size_t pos = 0;
-            BSONObjIterator it(keyPattern);
-            while (it.more() && it.next().fieldName() != oil.name) ++pos;
-            if (pos > fields.size()) {
-                fields.resize(pos);
-            }
-            else {
-                verify("" == fields[pos].name);
-            }
-
-            // XXX: must check later that we fill out adjacent fields.
-            fields[pos] = oil;
-        }
-
-        /**
-         * The provided oil is OR-related to the bounds.  If we have an existing oil over the
-         * field, find the union.  Otherwise, add it to the right location in 'fields'.
-         */
-        void joinOr(const OrderedIntervalList& oil, const BSONObj& keyPattern) {
-            // XXX XXX
-            verify(0);
-        }
-
         // Debugging check.
         // We must have as many fields the key pattern does.
         // The fields must be oriented in the direction we'd encounter them given the indexing
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index 3511cbe2428..0cb6e6ef382 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -103,6 +103,7 @@ namespace mongo {
             else {
                 verify(dataObj.isOwned());
                 interval = makePointInterval(dataObj);
+                // XXX: it's exact if the index isn't sparse
                 if (dataObj.firstElement().isNull()) {
                     exact = false;
                 }
diff --git a/src/mongo/db/query/index_entry.h b/src/mongo/db/query/index_entry.h
new file mode 100644
index 00000000000..59c3aa166e3
--- /dev/null
+++ b/src/mongo/db/query/index_entry.h
@@ -0,0 +1,56 @@
+/**
+ *    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.
+ */
+
+#pragma once
+
+#include <vector>
+
+#include "mongo/db/jsobj.h"
+
+namespace mongo {
+
+    /**
+     * This name sucks, but every name involving 'index' is used somewhere.
+     */
+    struct IndexEntry {
+        IndexEntry(BSONObj kp, bool mk, bool sp) : keyPattern(kp), multikey(mk), sparse(sp) { }
+
+        IndexEntry(const IndexEntry& other) {
+            keyPattern = other.keyPattern;
+            multikey = other.multikey;
+            sparse = other.sparse;
+        }
+
+        BSONObj keyPattern;
+
+        bool multikey;
+
+        bool sparse;
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/index_tag.cpp b/src/mongo/db/query/index_tag.cpp
index 42aca694651..f51bf8d9015 100644
--- a/src/mongo/db/query/index_tag.cpp
+++ b/src/mongo/db/query/index_tag.cpp
@@ -45,8 +45,11 @@ namespace mongo {
     bool TagComparison(const MatchExpression* lhs, const MatchExpression* rhs) {
         IndexTag* lhsTag = static_cast<IndexTag*>(lhs->getTag());
         size_t lhsValue = (NULL == lhsTag) ? IndexTag::kNoIndex : lhsTag->index;
+        size_t lhsPos = (NULL == lhsTag) ? IndexTag::kNoIndex : lhsTag->pos;
+
         IndexTag* rhsTag = static_cast<IndexTag*>(rhs->getTag());
         size_t rhsValue = (NULL == rhsTag) ? IndexTag::kNoIndex : rhsTag->index;
+        size_t rhsPos = (NULL == rhsTag) ? IndexTag::kNoIndex : rhsTag->pos;
 
         // First, order on indices.
         if (lhsValue != rhsValue) {
@@ -54,6 +57,11 @@ namespace mongo {
             return lhsValue < rhsValue;
         }
 
+        // Next, order so that the first field of a compound index appears first.
+        if (lhsPos != rhsPos) {
+            return lhsPos < rhsPos;
+        }
+
         // Next, order on fields.
         int cmp = lhs->path().compare(rhs->path());
         if (0 != cmp) {
diff --git a/src/mongo/db/query/index_tag.h b/src/mongo/db/query/index_tag.h
index 2912aca5218..2173adce9ff 100644
--- a/src/mongo/db/query/index_tag.h
+++ b/src/mongo/db/query/index_tag.h
@@ -21,7 +21,6 @@
 #include "mongo/bson/util/builder.h"
 #include "mongo/db/matcher/expression.h"
 
-
 namespace mongo {
 
     // output from enumerator to query planner
@@ -29,21 +28,25 @@ namespace mongo {
     public:
         static const size_t kNoIndex;
 
-        IndexTag() : index(kNoIndex) {}
-        IndexTag(size_t i) : index(i) { }
+        IndexTag() : index(kNoIndex), pos(0) {}
+        IndexTag(size_t i) : index(i), pos(0) { }
+        IndexTag(size_t i, size_t p) : index(i), pos(p) { }
 
         virtual ~IndexTag() { }
 
         virtual void debugString(StringBuilder* builder) const {
-            *builder << " || Selected Index #" << index;
+            *builder << " || Selected Index #" << index << " pos " << pos;
         }
 
         virtual MatchExpression::TagData* clone() const {
-            return new IndexTag(index);
+            return new IndexTag(index, pos);
         }
 
         // What index should we try to use for this leaf?
         size_t index;
+
+        // What position are we in the index?  (Compound.)
+        size_t pos;
     };
 
     // used internally
diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h
index 008536ec5ee..626a4cdd1a0 100644
--- a/src/mongo/db/query/indexability.h
+++ b/src/mongo/db/query/indexability.h
@@ -27,6 +27,7 @@ namespace mongo {
     public:
         /**
          * Is an index over me->path() useful?
+         * This is the same thing as being sargable, if you have a RDBMS background.
          */
         static bool nodeCanUseIndexOnOwnField(const MatchExpression* me) {
             if (me->path().empty()) {
@@ -52,6 +53,8 @@ namespace mongo {
 
         /**
          * This array operator doesn't have any children with fields and can use an index.
+         *
+         * Example: a: {$elemMatch: {$gte: 1, $lte: 1}}.
          */
         static bool arrayUsesIndexOnOwnField(const MatchExpression* me) {
             return me->isArray() && MatchExpression::ELEM_MATCH_VALUE == me->matchType();
@@ -60,6 +63,8 @@ namespace mongo {
         /**
          * Certain array operators require that the field for that operator is prepended
          * to all fields in that operator's children.
+         *
+         * Example: a: {$elemMatch: {b:1, c:1}}.
          */
         static bool arrayUsesIndexOnChildren(const MatchExpression* me) {
             return me->isArray() && (MatchExpression::ELEM_MATCH_OBJECT == me->matchType()
diff --git a/src/mongo/db/query/new_find.cpp b/src/mongo/db/query/new_find.cpp
index 724f7e8ef76..295ba4a9996 100644
--- a/src/mongo/db/query/new_find.cpp
+++ b/src/mongo/db/query/new_find.cpp
@@ -158,14 +158,25 @@ namespace mongo {
         }
 
         // If it's not NULL, we may have indices.
-        vector<BSONObj> indices;
+        vector<IndexEntry> indices;
         for (int i = 0; i < nsd->getCompletedIndexCount(); ++i) {
             auto_ptr<IndexDescriptor> desc(CatalogHack::getDescriptor(nsd, i));
-            indices.push_back(desc->keyPattern());
+            indices.push_back(IndexEntry(desc->keyPattern(), desc->isMultikey(), desc->isSparse()));
         }
 
         vector<QuerySolution*> solutions;
-        QueryPlanner::plan(*canonicalQuery, indices, &solutions);
+        size_t options = QueryPlanner::DEFAULT;
+        if (cmdLine.noTableScan) {
+            const string& ns = canonicalQuery->ns();
+            // There are certain cases where we ignore this restriction:
+            bool ignore = canonicalQuery->getQueryObj().isEmpty()
+                          || (string::npos != ns.find(".system."))
+                          || (0 == ns.find("local."));
+            if (!ignore) {
+                options |= QueryPlanner::NO_TABLE_SCAN;
+            }
+        }
+        QueryPlanner::plan(*canonicalQuery, indices, options, &solutions);
 
         /*
         for (size_t i = 0; i < solutions.size(); ++i) {
diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index 4bd3a9f7ecd..4a7d058b979 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -23,7 +23,7 @@
 
 namespace mongo {
 
-    PlanEnumerator::PlanEnumerator(MatchExpression* root, const vector<BSONObj>* indices)
+    PlanEnumerator::PlanEnumerator(MatchExpression* root, const vector<IndexEntry>* indices)
         : _root(root), _indices(indices) { }
 
     PlanEnumerator::~PlanEnumerator() {
@@ -54,14 +54,14 @@ namespace mongo {
         if (!_done) {
             // Tag with our first solution.
             tagMemo(_nodeToId[_root]);
-            checkCompound(_root);
+            checkCompound("", _root);
         }
 
         return Status::OK();
     }
 
     bool PlanEnumerator::isCompound(size_t idx) {
-        return (*_indices)[idx].nFields() > 1;
+        return (*_indices)[idx].keyPattern.nFields() > 1;
     }
 
     string PlanEnumerator::NodeSolution::toString() const {
@@ -116,9 +116,10 @@ namespace mongo {
      * This is very expensive if the involved indices/predicates are numerous but
      * I suspect that's rare.  TODO: revisit on perf pass.
      *
-     * TODO: Do we care about compound and with arrays modifying the path?
+     * TODO: We can save time by not bothering to do this if the index is multiKey.
+     * TODO: Perhaps this should be done by the planner??
      */
-    void PlanEnumerator::checkCompound(MatchExpression* node) {
+    void PlanEnumerator::checkCompound(string prefix, MatchExpression* node) {
         if (MatchExpression::AND == node->matchType()) {
             // Step 1: Find all compound indices.
             vector<MatchExpression*> assignedCompound;
@@ -153,17 +154,33 @@ namespace mongo {
             // TODO: This could be optimized a lot.
             for (size_t i = 0; i < assignedCompound.size(); ++i) {
                 IndexTag* childTag = static_cast<IndexTag*>(assignedCompound[i]->getTag());
-                BSONObj kp = (*_indices)[childTag->index];
+
+                // XXX: If we assign a compound index and it's on a multikey index, the planner may
+                // not be able to use the multikey for it, and then it may create a new index scan,
+                // and that new scan will be bogus.  For now don't assign, should fix planner to be
+                // more resilient.  once we figure out fully in what cases array operators can use
+                // compound indices, change this to deal with that.
+                //
+                // That is, we can only safely assign compound indices if the planner uses them as
+                // compound indices whenever we assign them.
+                if ((*_indices)[i].multikey) { continue; }
+
+                const BSONObj& kp = (*_indices)[childTag->index].keyPattern;
                 BSONObjIterator it(kp);
                 it.next();
+
+                size_t posInIdx = 0;
                 // we know isCompound is true so this should be true.
                 verify(it.more());
                 while (it.more()) {
                     BSONElement kpElt = it.next();
+                    ++posInIdx;
                     bool assignedField = false;
                     // Trying to pick an unassigned M.E.
                     for (size_t j = 0; j < unassigned.size(); ++j) {
-                        if (unassigned[j]->path() != kpElt.fieldName()) {
+                        // TODO: is this really required?  This seems really like it's just a
+                        // reiteration of the tagging process.
+                        if (prefix + unassigned[j]->path().toString() != kpElt.fieldName()) {
                             // We need to find a predicate over kpElt.fieldName().
                             continue;
                         }
@@ -180,7 +197,8 @@ namespace mongo {
                         if (std::find(soln->pred->notFirst.begin(), soln->pred->notFirst.end(), childTag->index) != soln->pred->notFirst.end()) {
                             cout << "compound-ing " << kp.toString() << " with node " << unassigned[j]->toString() << endl;
                             assignedField = true;
-                            unassigned[j]->setTag(new IndexTag(childTag->index));
+                            cout << "setting pos to " << posInIdx << endl;
+                            unassigned[j]->setTag(new IndexTag(childTag->index, posInIdx));
                             // We've picked something for this (index, field) tuple.  Don't pick anything else.
                             break;
                         }
@@ -195,9 +213,15 @@ namespace mongo {
             }
         }
 
+        if (Indexability::arrayUsesIndexOnChildren(node)) {
+            if (!node->path().empty()) {
+                prefix += node->path().toString() + ".";
+            }
+        }
+
         // Don't think the traversal order here matters.
         for (size_t i = 0; i < node->numChildren(); ++i) {
-            checkCompound(node->getChild(i));
+            checkCompound(prefix, node->getChild(i));
         }
     }
 
@@ -218,10 +242,7 @@ namespace mongo {
 
     bool PlanEnumerator::prepMemo(MatchExpression* node) {
         if (Indexability::arrayUsesIndexOnChildren(node)) {
-            // TODO: For 'node' to be indexed, do we require all children to be indexed or just one?
-            // Does this depend on the matchType?  Currently we're OK with just one, AND-style,
-            // because elemMatch is the case I'm thinking of.
-
+            // TODO: Fold into logical->AND branch below?
             AndSolution* andSolution = new AndSolution();
             for (size_t i = 0; i < node->numChildren(); ++i) {
                 if (prepMemo(node->getChild(i))) {
diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
index fb173825e05..a44efa0f543 100644
--- a/src/mongo/db/query/plan_enumerator.h
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -21,6 +21,7 @@
 #include "mongo/base/disallow_copying.h"
 #include "mongo/base/status.h"
 #include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/index_entry.h"
 #include "mongo/db/query/index_tag.h"
 
 namespace mongo {
@@ -39,7 +40,7 @@ namespace mongo {
          *
          * Does not take ownership of any arguments.  They must outlive any calls to getNext(...).
          */
-        PlanEnumerator(MatchExpression* root, const vector<BSONObj>* indices);
+        PlanEnumerator(MatchExpression* root, const vector<IndexEntry>* indices);
         ~PlanEnumerator();
 
         /**
@@ -72,7 +73,7 @@ namespace mongo {
         MatchExpression* _root;
 
         // Indices we're allowed to enumerate with.
-        const vector<BSONObj>* _indices;
+        const vector<IndexEntry>* _indices;
 
         //
         // Memoization strategy
@@ -96,7 +97,7 @@ namespace mongo {
          * If an assigned index is compound, checkCompound looks for predicates that are over fields
          * in the compound index.
          */
-        void checkCompound(MatchExpression* node);
+        void checkCompound(string prefix, MatchExpression* node);
 
         /**
          * Traverses the memo structure and annotates the tree with IndexTags for the chosen
diff --git a/src/mongo/db/query/projection_parser.cpp b/src/mongo/db/query/projection_parser.cpp
index 37d6804de21..0388928cb12 100644
--- a/src/mongo/db/query/projection_parser.cpp
+++ b/src/mongo/db/query/projection_parser.cpp
@@ -69,6 +69,10 @@ namespace mongo {
             }
         }
 
+        if (qp->_includedFields.size() > 0 && qp->_includeID) {
+            qp->_includedFields.push_back(string("_id"));
+        }
+
         *out = qp.release();
         return Status::OK();
     }
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 06f3ea4b6cc..45ed74259e5 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -76,10 +76,10 @@ namespace mongo {
 
     // static
     void QueryPlanner::findRelevantIndices(const unordered_set<string>& fields,
-                                           const vector<BSONObj>& allIndices,
-                                           vector<BSONObj>* out) {
+                                           const vector<IndexEntry>& allIndices,
+                                           vector<IndexEntry>* out) {
         for (size_t i = 0; i < allIndices.size(); ++i) {
-            BSONObjIterator it(allIndices[i]);
+            BSONObjIterator it(allIndices[i].keyPattern);
             verify(it.more());
             BSONElement elt = it.next();
             if (fields.end() != fields.find(elt.fieldName())) {
@@ -89,7 +89,7 @@ namespace mongo {
     }
 
     // static
-    bool QueryPlanner::compatible(const BSONElement& elt, MatchExpression* node) {
+    bool QueryPlanner::compatible(const BSONElement& elt, const IndexEntry& index, MatchExpression* node) {
         // XXX: CatalogHack::getAccessMethodName: do we have to worry about this?  when?
         string ixtype;
         if (String != elt.type()) {
@@ -135,7 +135,7 @@ namespace mongo {
 
     // static
     void QueryPlanner::rateIndices(MatchExpression* node, string prefix,
-                                   const vector<BSONObj>& indices) {
+                                   const vector<IndexEntry>& indices) {
         if (Indexability::nodeCanUseIndexOnOwnField(node)) {
             string fullPath = prefix + node->path().toString();
             verify(NULL == node->getTag());
@@ -144,14 +144,14 @@ namespace mongo {
 
             // TODO: This is slow, with all the string compares.
             for (size_t i = 0; i < indices.size(); ++i) {
-                BSONObjIterator it(indices[i]);
+                BSONObjIterator it(indices[i].keyPattern);
                 BSONElement elt = it.next();
-                if (elt.fieldName() == fullPath && compatible(elt, node)) {
+                if (elt.fieldName() == fullPath && compatible(elt, indices[i], node)) {
                     rt->first.push_back(i);
                 }
                 while (it.more()) {
                     elt = it.next();
-                    if (elt.fieldName() == fullPath && compatible(elt, node)) {
+                    if (elt.fieldName() == fullPath && compatible(elt, indices[i], node)) {
                         rt->notFirst.push_back(i);
                     }
                 }
@@ -207,27 +207,29 @@ namespace mongo {
                                                MatchExpression* expr,
                                                bool* exact) {
         cout << "making ixscan for " << expr->toString() << endl;
-        if (MatchExpression::ELEM_MATCH_VALUE == expr->matchType()) {
-            // Root is tagged with an index.  We have predicates over root's path.  Pick one
-            // to define the bounds.
-
-            // TODO: We could/should merge the bounds (possibly subject to various multikey
-            // etc.  restrictions).  For now we don't bother.
-            expr = expr->getChild(0);
-        }
 
         // Note that indexKeyPattern.firstElement().fieldName() may not equal expr->path() because
         // expr might be inside an array operator that provides a path prefix.
         IndexScanNode* isn = new IndexScanNode();
         isn->indexKeyPattern = indexKeyPattern;
         isn->bounds.fields.resize(indexKeyPattern.nFields());
-        IndexBoundsBuilder::translate(expr, indexKeyPattern.firstElement(),
-                                      &isn->bounds.fields[0], exact);
-
-        // TODO: I think this is valid but double check.
         if (MatchExpression::ELEM_MATCH_VALUE == expr->matchType()) {
+            // Root is tagged with an index.  We have predicates over root's path.  Pick one
+            // to define the bounds.
+
+            // TODO: We could/should merge the bounds (possibly subject to various multikey
+            // etc.  restrictions).  For now we don't bother.
+            IndexBoundsBuilder::translate(expr->getChild(0), indexKeyPattern.firstElement(),
+                                          &isn->bounds.fields[0], exact);
+            // TODO: I think this is valid but double check.
             *exact = false;
         }
+        else {
+            IndexBoundsBuilder::translate(expr, indexKeyPattern.firstElement(),
+                                          &isn->bounds.fields[0], exact);
+        }
+
+        cout << "bounds are " << isn->bounds.toString() << " exact " << *exact << endl;
 
         return isn;
     }
@@ -270,7 +272,7 @@ namespace mongo {
     // static
     bool QueryPlanner::processIndexScans(MatchExpression* root,
                                          bool inArrayOperator,
-                                         const vector<BSONObj>& indexKeyPatterns,
+                                         const vector<IndexEntry>& indices,
                                          vector<QuerySolutionNode*>* out) {
 
         bool isAnd = MatchExpression::AND == root->matchType();
@@ -280,6 +282,7 @@ namespace mongo {
 
         auto_ptr<IndexScanNode> currentScan;
         size_t currentIndexNumber = IndexTag::kNoIndex;
+        size_t nextIndexPos = 0;
         size_t curChild = 0;
 
         // This 'while' processes all IXSCANs, possibly merging scans by combining the bounds.  We
@@ -315,9 +318,11 @@ namespace mongo {
                     ++curChild;
                 }
 
+                // If inArrayOperator: takes ownership of child, which is OK, since we detached
+                // child from root.
                 QuerySolutionNode* childSolution = buildIndexedDataAccess(child,
                                                                           inArrayOperator,
-                                                                          indexKeyPatterns);
+                                                                          indices);
                 if (NULL == childSolution) { return false; }
                 out->push_back(childSolution);
                 continue;
@@ -328,15 +333,72 @@ namespace mongo {
 
             // If the child we're looking at uses a different index than the current index scan, add
             // the current index scan to the output as we're done with it.  The index scan created
-            // by the child then becomes our new current index scan.
+            // by the child then becomes our new current index scan.  Note that the current scan
+            // could be NULL, in which case we don't output it.  The rest of the logic is identical.
+            //
+            // If the child uses the same index as the current index scan, we may be able to merge
+            // the bounds for the two scans.  See the comments below for canMergeBounds and
+            // shouldMergeBounds.
+
+            // Is it remotely possible to merge the bounds?  We care about isAnd because bounds
+            // merging is currently totally unimplemented for ORs.
             //
-            // Note that the current scan could be NULL, in which case we don't output it.  The rest
-            // of the logic is identical.
+            // TODO: When more than one child of an AND clause can have an index, we'll have to fix
+            // the logic below to only merge when the merge is really filling out an additional
+            // field of a compound index.
             //
-            // TODO: We don't to merge bounds for OR yet, so each child of an OR is a new ixscan.
-            if (NULL == currentScan.get() || !isAnd || inArrayOperator || (currentIndexNumber != ixtag->index)) {
+            // TODO: Implement union of OILs to allow merging bounds for OR.
+            // TODO: Implement intersection of OILs to allow merging of bounds for AND.
+            bool canMergeBounds = (NULL != currentScan.get()) && (currentIndexNumber == ixtag->index) && isAnd;
+
+            // Is it semantically correct to merge bounds?
+            //
+            // If the index is NOT multikey, it's always semantically correct.
+            //
+            // If the index is multikey, there are three issues:
+            //
+            // 1. We can't intersect bounds even if the bounds are not on a compound index.
+            //    Example:
+            //    Let's say we have the document {a: [5, 7]}.
+            //    This document satisfies the query {$or: [ {a: 5}, {a: 7} ] }
+            //    For the index {a:1} we have the keys {"": 5} and {"": 7}.
+            //    Each child of the OR is tagged with the index {a: 1}
+            //    The interval for the {a: 5} branch is [5, 5].
+            //    The interval for the {a: 7} branch is [7, 7].
+            //    The intersection of the intervals is {}, which yields no results.
+            //
+            // 2. If we're using a compound index, we can only specify bounds for the first field.
+            //    Example:
+            //    Let's say we have the document {a: [ {b: 3}, {c: 4} ] }
+            //    This document satisfies the query {'a.b': 3, 'a.c': 4}.
+            //    For the index {'a.b': 1, 'a.c': 1} we have the keys {"": 3, "": null} and
+            //                                                        {"": null, "": 4}.
+            //    Let's use the aforementioned index to answer the query.
+            //    The bounds for 'a.b' are [3,3], and the bounds for 'a.c' are [4,4].
+            //    If we combine the bounds, we would only look at keys {"": 3, "":4 }.
+            //    Therefore we wouldn't look at the document's keys in the index.
+            //    Therefore we don't combine bounds.
+            //
+            // 3. There is an exception to (2), and that is when we're evaluating an $elemMatch.
+            //    Example:
+            //    Our query is a: {$elemMatch: {b:3, c:4}}.
+            //    Let's say that we have the index {'a.b': 1, 'a.c': 1} as in (2).
+            //    $elemMatch requires if a.b==3 and a.c==4, the predicates must be satisfied from
+            //    the same array entry.
+            //    If those values are both present in the same array, the index key for the
+            //    aforementioned index will be {"":3, "":4}
+            //    Therefore we can intersect bounds.
+            //
+            //    XXX: There is more to it than this.  See index13.js.
+
+            bool shouldMergeBounds = !indices[currentIndexNumber].multikey;
+
+            // XXX: commented out until cases in index13.js are resolved.
+            // bool shouldMergeBounds = !indices[currentIndexNumber].multikey || inArrayOperator;
+
+            if (!canMergeBounds || !shouldMergeBounds) {
                 if (NULL != currentScan.get()) {
-                    finishIndexScan(currentScan.get(), indexKeyPatterns[currentIndexNumber]);
+                    finishIndexScan(currentScan.get(), indices[currentIndexNumber].keyPattern);
                     out->push_back(currentScan.release());
                 }
                 else {
@@ -344,10 +406,12 @@ namespace mongo {
                 }
 
                 currentIndexNumber = ixtag->index;
+                nextIndexPos = 1;
 
                 bool exact = false;
-                currentScan.reset(makeIndexScan(indexKeyPatterns[currentIndexNumber],
+                currentScan.reset(makeIndexScan(indices[currentIndexNumber].keyPattern,
                                                 child, &exact));
+
                 if (exact && !inArrayOperator) {
                     // The bounds answer the predicate, and we can remove the expression from the
                     // root.  NOTE(opt): Erasing entry 0, 1, 2, ... could be kind of n^2, maybe
@@ -365,56 +429,30 @@ namespace mongo {
             else {
                 // The child uses the same index we're currently building a scan for.  Merge
                 // the bounds and filters.
-
-                // XXX XXX XXX: I don't think we can combine bounds on a compound index when they're
-                // over a multikey index.  To quote queryutil.cpp:
-
-                // Given a multikey index { 'a.b':1, 'a.c':1 } and query { 'a.b':3, 'a.c':3 } only
-                // the index field 'a.b' is constrained to the range [3, 3], while the index
-                // field 'a.c' is just constrained to be within minkey and maxkey.  This
-                // implementation ensures that the document { a:[ { b:3 }, { c:3 } ] }, which
-                // generates index keys { 'a.b':3, 'a.c':null } and { 'a.b':null and 'a.c':3 } will
-                // be retrieved for the query.
-                //
-                // However, if the query is instead { a:{ $elemMatch:{ b:3, c:3 } } } then the
-                // document { a:[ { b:3 }, { c:3 } ] } should not match the query and both index
-                // fields 'a.b' and 'a.c' are constrained to the range [3, 3].
-
-                // XXX: This only works when the child doesn't have any predicates over the same
-                // field.  To deal with that case, our bounds/interval merging would have to
-                // actually be implemented.  Right now, we rely on enumeration to not supply us with
-                // two plans that use the same index but are not compound.
-
-                verify(!inArrayOperator);
                 verify(currentIndexNumber == ixtag->index);
-
-                // First, make the bounds.
-                OrderedIntervalList oil(child->path().toString());
-
-                // TODO(opt): We can cache this as part of the index rating process, this is
-                // slow.
-                BSONObjIterator kpIt(indexKeyPatterns[currentIndexNumber]);
-                BSONElement elt = kpIt.next();
-                while (elt.fieldName() != oil.name) {
-                    verify(kpIt.more());
-                    elt = kpIt.next();
+                verify(ixtag->pos == nextIndexPos);
+
+                // Get the ixtag->pos-th element of indexKeyPatterns[currentIndexNumber].
+                // TODO: cache this instead/with ixtag->pos?
+                BSONObjIterator it(indices[currentIndexNumber].keyPattern);
+                BSONElement keyElt = it.next();
+                for (size_t i = 0; i < ixtag->pos; ++i) {
+                    verify(it.more());
+                    keyElt = it.next();
                 }
-                verify(!elt.eoo());
+                verify(!keyElt.eoo());
                 bool exact = false;
-                IndexBoundsBuilder::translate(child, elt, &oil, &exact);
 
                 //cout << "current bounds are " << currentScan->bounds.toString() << endl;
                 //cout << "node merging in " << child->toString() << endl;
+                //cout << "merging with field " << keyElt.toString(true, true) << endl;
                 //cout << "taking advantage of compound index "
-                //     << indexKeyPatterns[currentIndexNumber].toString() << endl;
+                     //<< indices[currentIndexNumber].keyPattern.toString() << endl;
 
-                // Merge the bounds with the existing.
-                if (isAnd) {
-                    currentScan->bounds.joinAnd(oil, indexKeyPatterns[currentIndexNumber]);
-                }
-                else {
-                    currentScan->bounds.joinOr(oil, indexKeyPatterns[currentIndexNumber]);
-                }
+                // We know at this point that the only case where we do this is compound indices so
+                // just short-cut and dump the bounds there.
+                verify(currentScan->bounds.fields[ixtag->pos].name.empty());
+                IndexBoundsBuilder::translate(child, keyElt, &currentScan->bounds.fields[ixtag->pos], &exact);
 
                 if (exact) {
                     root->getChildVector()->erase(root->getChildVector()->begin()
@@ -425,12 +463,14 @@ namespace mongo {
                     // We keep curChild in the AND for affixing later.
                     ++curChild;
                 }
+
+                ++nextIndexPos;
             }
         }
 
         // Output the scan we're done with, if it exists.
         if (NULL != currentScan.get()) {
-            finishIndexScan(currentScan.get(), indexKeyPatterns[currentIndexNumber]);
+            finishIndexScan(currentScan.get(), indices[currentIndexNumber].keyPattern);
             out->push_back(currentScan.release());
         }
 
@@ -440,9 +480,14 @@ namespace mongo {
     // static
     QuerySolutionNode* QueryPlanner::buildIndexedAnd(MatchExpression* root,
                                                      bool inArrayOperator,
-                                                     const vector<BSONObj>& indexKeyPatterns) {
+                                                     const vector<IndexEntry>& indices) {
+        auto_ptr<MatchExpression> autoRoot;
+        if (!inArrayOperator) {
+            autoRoot.reset(root);
+        }
+
         vector<QuerySolutionNode*> ixscanNodes;
-        if (!processIndexScans(root, inArrayOperator, indexKeyPatterns, &ixscanNodes)) {
+        if (!processIndexScans(root, inArrayOperator, indices, &ixscanNodes)) {
             return NULL;
         }
 
@@ -492,14 +537,15 @@ namespace mongo {
         // index, so we put a fetch with filter.
         if (root->numChildren() > 0) {
             FetchNode* fetch = new FetchNode();
-            fetch->filter.reset(root);
+            verify(NULL != autoRoot.get());
+            // Takes ownership.
+            fetch->filter.reset(autoRoot.release());
             // takes ownership
             fetch->child.reset(andResult);
             andResult = fetch;
         }
         else {
-            // root has no children, just get rid of it.
-            delete root;
+            // root has no children, let autoRoot get rid of it when it goes out of scope.
         }
 
         return andResult;
@@ -508,13 +554,15 @@ namespace mongo {
     // static
     QuerySolutionNode* QueryPlanner::buildIndexedOr(MatchExpression* root,
                                                     bool inArrayOperator,
-                                                    const vector<BSONObj>& indexKeyPatterns) {
+                                                    const vector<IndexEntry>& indices) {
+        auto_ptr<MatchExpression> autoRoot;
+        if (!inArrayOperator) {
+            autoRoot.reset(root);
+        }
+
         size_t expectedNumberScans = root->numChildren();
         vector<QuerySolutionNode*> ixscanNodes;
-        if (!processIndexScans(root, inArrayOperator, indexKeyPatterns, &ixscanNodes)) {
-            if (!inArrayOperator) {
-                delete root;
-            }
+        if (!processIndexScans(root, inArrayOperator, indices, &ixscanNodes)) {
             return NULL;
         }
 
@@ -523,9 +571,9 @@ namespace mongo {
         // be answered via an index.
         if (ixscanNodes.size() != expectedNumberScans || (!inArrayOperator && 0 != root->numChildren())) {
             warning() << "planner OR error, non-indexed child of OR.";
-            if (!inArrayOperator) {
-                delete root;
-            }
+            // We won't enumerate an OR without indices for each child, so this isn't an issue, even
+            // if we have an AND with an OR child -- we won't get here unless the OR is fully
+            // indexed.
             return NULL;
         }
 
@@ -545,7 +593,7 @@ namespace mongo {
             else {
                 haveSameSort = true;
                 for (size_t i = 1; i < ixscanNodes.size(); ++i) {
-                    if (0 == ixscanNodes[0]->getSort().woCompare(ixscanNodes[i]->getSort())) {
+                    if (0 != ixscanNodes[0]->getSort().woCompare(ixscanNodes[i]->getSort())) {
                         haveSameSort = false;
                         break;
                     }
@@ -566,10 +614,8 @@ namespace mongo {
         }
 
         // OR must have an index for each child, so we should have detached all children from
-        // 'root', and there's nothing useful to do with an empty or MatchExpression.
-        if (!inArrayOperator) {
-            delete root;
-        }
+        // 'root', and there's nothing useful to do with an empty or MatchExpression.  We let it die
+        // via autoRoot.
 
         return orResult;
     }
@@ -577,32 +623,31 @@ namespace mongo {
     // static
     QuerySolutionNode* QueryPlanner::buildIndexedDataAccess(MatchExpression* root,
                                                             bool inArrayOperator,
-                                                            const vector<BSONObj>& indexKeyPatterns) {
+                                                            const vector<IndexEntry>& indices) {
         if (root->isLogical()) {
             if (MatchExpression::AND == root->matchType()) {
                 // Takes ownership of root.
-                return buildIndexedAnd(root, inArrayOperator, indexKeyPatterns);
+                return buildIndexedAnd(root, inArrayOperator, indices);
             }
             else if (MatchExpression::OR == root->matchType()) {
                 // Takes ownership of root.
-                return buildIndexedOr(root, inArrayOperator, indexKeyPatterns);
+                return buildIndexedOr(root, inArrayOperator, indices);
             }
             else {
                 // Can't do anything with negated logical nodes index-wise.
-                if (!inArrayOperator) {
-                    delete root;
-                }
                 return NULL;
             }
         }
         else {
+            auto_ptr<MatchExpression> autoRoot;
+            if (!inArrayOperator) {
+                autoRoot.reset(root);
+            }
+
             // isArray or isLeaf is true.  Either way, it's over one field, and the bounds builder
             // deals with it.
             if (NULL == root->getTag()) {
                 // No index to use here, not in the context of logical operator, so we're SOL.
-                if (!inArrayOperator) {
-                    delete root;
-                }
                 return NULL;
             }
             else if (Indexability::nodeCanUseIndexOnOwnField(root)) {
@@ -611,9 +656,9 @@ namespace mongo {
 
                 bool exact = false;
                 auto_ptr<IndexScanNode> isn;
-                isn.reset(makeIndexScan(indexKeyPatterns[tag->index], root, &exact));
+                isn.reset(makeIndexScan(indices[tag->index].keyPattern, root, &exact));
 
-                finishIndexScan(isn.get(), indexKeyPatterns[tag->index]);
+                finishIndexScan(isn.get(), indices[tag->index].keyPattern);
 
                 if (inArrayOperator) {
                     return isn.release();
@@ -627,13 +672,11 @@ namespace mongo {
                 // predicate.
                 if (!exact) {
                     FetchNode* fetch = new FetchNode();
-                    fetch->filter.reset(root);
+                    verify(NULL != autoRoot.get());
+                    fetch->filter.reset(autoRoot.release());
                     fetch->child.reset(isn.release());
                     return fetch;
                 }
-                else {
-                    delete root;
-                }
 
                 return isn.release();
             }
@@ -645,7 +688,8 @@ namespace mongo {
                     auto_ptr<AndHashNode> ahn(new AndHashNode());
 
                     for (size_t i = 0; i < root->numChildren(); ++i) {
-                        QuerySolutionNode* node = buildIndexedDataAccess(root->getChild(i), true, indexKeyPatterns);
+                        QuerySolutionNode* node = buildIndexedDataAccess(root->getChild(i), true,
+                                                                         indices);
                         if (NULL != node) {
                             ahn->children.push_back(node);
                         }
@@ -669,7 +713,7 @@ namespace mongo {
                     verify(MatchExpression::ELEM_MATCH_OBJECT);
                     // The child is an AND.
                     verify(1 == root->numChildren());
-                    solution = buildIndexedDataAccess(root->getChild(0), true, indexKeyPatterns);
+                    solution = buildIndexedDataAccess(root->getChild(0), true, indices);
                     if (NULL == solution) { return NULL; }
                 }
 
@@ -677,16 +721,14 @@ namespace mongo {
                 if (inArrayOperator) { return solution; }
 
                 FetchNode* fetch = new FetchNode();
-                fetch->filter.reset(root);
+                // Takes ownership of 'root'.
+                verify(NULL != autoRoot.get());
+                fetch->filter.reset(autoRoot.release());
                 fetch->child.reset(solution);
                 return fetch;
             }
         }
 
-        if (!inArrayOperator) {
-            delete root;
-        }
-
         return NULL;
     }
 
@@ -826,10 +868,12 @@ namespace mongo {
     }
 
     // static
-    void QueryPlanner::plan(const CanonicalQuery& query, const vector<BSONObj>& indexKeyPatterns,
-                            vector<QuerySolution*>* out) {
+    void QueryPlanner::plan(const CanonicalQuery& query, const vector<IndexEntry>& indices,
+                            size_t options, vector<QuerySolution*>* out) {
         cout << "Begin planning.\nquery = " << query.toString() << endl;
 
+        bool canTableScan = !(options & QueryPlanner::NO_TABLE_SCAN);
+
         // XXX: If pq.hasOption(QueryOption_OplogReplay) use FindingStartCursor equivalent which
         // must be translated into stages.
 
@@ -838,7 +882,7 @@ namespace mongo {
         // could ask for a tailable cursor and it just tried to give you one.  Now, we fail if we
         // can't provide one.  Is this what we want?
         if (query.getParsed().hasOption(QueryOption_CursorTailable)) {
-            if (!hasNode(query.root(), MatchExpression::GEO_NEAR)) {
+            if (!hasNode(query.root(), MatchExpression::GEO_NEAR) && canTableScan) {
                 out->push_back(makeCollectionScan(query, true));
             }
             return;
@@ -850,7 +894,9 @@ namespace mongo {
             BSONElement natural = query.getParsed().getHint().getFieldDotted("$natural");
             if (!natural.eoo()) {
                 cout << "forcing a table scan due to hinted $natural\n";
-                out->push_back(makeCollectionScan(query, false));
+                if (canTableScan) {
+                    out->push_back(makeCollectionScan(query, false));
+                }
                 return;
             }
         }
@@ -867,13 +913,12 @@ namespace mongo {
                 return;
             }
             cout << "NOT/NOR in plan, just outtping a collscan\n";
-            out->push_back(makeCollectionScan(query, false));
+            if (canTableScan) {
+                out->push_back(makeCollectionScan(query, false));
+            }
             return;
         }
 
-        // XXX: There can only be one NEAR.  If there is a NEAR, it must be either the root or the
-        // root must be an AND and its child must be a NEAR.
-
         // Figure out what fields we care about.
         unordered_set<string> fields;
         getFields(query.root(), "", &fields);
@@ -884,7 +929,7 @@ namespace mongo {
         */
 
         // Filter our indices so we only look at indices that are over our predicates.
-        vector<BSONObj> relevantIndices;
+        vector<IndexEntry> relevantIndices;
 
         // Hints require us to only consider the hinted index.
         BSONObj hintIndex = query.getParsed().getHint();
@@ -893,9 +938,9 @@ namespace mongo {
         // plan.  If that fails, just scan the _id index.
         if (query.getParsed().isSnapshot()) {
             // Find the ID index in indexKeyPatterns.  It's our hint.
-            for (size_t i = 0; i < indexKeyPatterns.size(); ++i) {
-                if (isIdIndex(indexKeyPatterns[i])) {
-                    hintIndex = indexKeyPatterns[i];
+            for (size_t i = 0; i < indices.size(); ++i) {
+                if (isIdIndex(indices[i].keyPattern)) {
+                    hintIndex = indices[i].keyPattern;
                     break;
                 }
             }
@@ -903,10 +948,10 @@ namespace mongo {
 
         if (!hintIndex.isEmpty()) {
             bool hintValid = false;
-            for (size_t i = 0; i < indexKeyPatterns.size(); ++i) {
-                if (0 == indexKeyPatterns[i].woCompare(hintIndex)) {
+            for (size_t i = 0; i < indices.size(); ++i) {
+                if (0 == indices[i].keyPattern.woCompare(hintIndex)) {
                     relevantIndices.clear();
-                    relevantIndices.push_back(hintIndex);
+                    relevantIndices.push_back(indices[i]);
                     cout << "hint specified, restricting indices to " << hintIndex.toString() << endl;
                     hintValid = true;
                     break;
@@ -917,7 +962,7 @@ namespace mongo {
             }
         }
         else {
-            findRelevantIndices(fields, indexKeyPatterns, &relevantIndices);
+            findRelevantIndices(fields, indices, &relevantIndices);
         }
 
         // Figure out how useful each index is to each predicate.
@@ -987,6 +1032,8 @@ namespace mongo {
 
         // If a sort order is requested, there may be an index that provides it, even if that
         // index is not over any predicates in the query.
+        //
+        // XXX XXX: Can we do this even if the index is sparse?  Might we miss things?
         if (!query.getParsed().getSort().isEmpty()) {
             // See if we have a sort provided from an index already.
             bool usingIndexToSort = false;
@@ -999,8 +1046,8 @@ namespace mongo {
             }
 
             if (!usingIndexToSort) {
-                for (size_t i = 0; i < indexKeyPatterns.size(); ++i) {
-                    const BSONObj& kp = indexKeyPatterns[i];
+                for (size_t i = 0; i < indices.size(); ++i) {
+                    const BSONObj& kp = indices[i].keyPattern;
                     if (0 == kp.woCompare(query.getParsed().getSort())) {
                         IndexScanNode* isn = new IndexScanNode();
                         isn->indexKeyPattern = kp;
@@ -1031,7 +1078,8 @@ namespace mongo {
         }
 
         // TODO: Do we always want to offer a collscan solution?
-        if (!hasNode(query.root(), MatchExpression::GEO_NEAR)) {
+        // XXX: currently disabling the always-use-a-collscan in order to find more planner bugs.
+        if (!hasNode(query.root(), MatchExpression::GEO_NEAR) && 0 == out->size() && canTableScan) {
             QuerySolution* collscan = makeCollectionScan(query, false);
             out->push_back(collscan);
             cout << "Outputting a collscan\n";
diff --git a/src/mongo/db/query/query_planner.h b/src/mongo/db/query/query_planner.h
index 1d8d47091a2..2224c30f0e6 100644
--- a/src/mongo/db/query/query_planner.h
+++ b/src/mongo/db/query/query_planner.h
@@ -29,6 +29,7 @@
 #pragma once
 
 #include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/index_entry.h"
 #include "mongo/db/query/query_solution.h"
 
 namespace mongo {
@@ -39,6 +40,15 @@ namespace mongo {
      */
     class QueryPlanner {
     public:
+        enum Options {
+            // You probably want to set this.
+            DEFAULT = 0,
+
+            // Set this if you don't want a table scan.
+            // See http://docs.mongodb.org/manual/reference/parameters/
+            NO_TABLE_SCAN = 1,
+        };
+
         /**
          * Outputs a series of possible solutions for the provided 'query' into 'out'.  Uses the
          * provided indices to generate a solution.
@@ -46,7 +56,8 @@ namespace mongo {
          * Caller owns pointers in *out.
          */
         static void plan(const CanonicalQuery& query,
-                         const vector<BSONObj>& indexKeyPatterns,
+                         const vector<IndexEntry>& indices,
+                         size_t options,
                          vector<QuerySolution*>* out);
     private:
 
@@ -68,21 +79,21 @@ namespace mongo {
          * useful in answering the query.
          */
         static void findRelevantIndices(const unordered_set<string>& fields,
-                                        const vector<BSONObj>& allIndices,
-                                        vector<BSONObj>* out);
+                                        const vector<IndexEntry>& indices,
+                                        vector<IndexEntry>* out);
 
         /**
-         * Return true if the index key pattern field 'elt' can be used to answer the predicate
-         * 'node'.
+         * Return true if the index key pattern field 'elt' (which belongs to 'index') can be used
+         * to answer the predicate 'node'.
          *
          * For example, {field: "hashed"} can only be used with sets of equalities.
          *              {field: "2d"} can only be used with some geo predicates.
          *              {field: "2dsphere"} can only be used with some other geo predicates.
          */
-        static bool compatible(const BSONElement& elt, MatchExpression* node);
+        static bool compatible(const BSONElement& elt, const IndexEntry& index, MatchExpression* node);
 
         /**
-         * Determine how useful all of our relevant indices are to all predicates in the subtree
+         * Determine how useful all of our relevant 'indices' are to all predicates in the subtree
          * rooted at 'node'.  Affixes a RelevantTag to all predicate nodes which can use an index.
          *
          * 'prefix' is a path prefix that should be prepended to any path (certain array operators
@@ -97,7 +108,7 @@ namespace mongo {
          * original predicate by having an AND as a parent.
          */
         static void rateIndices(MatchExpression* node, string prefix,
-                                const vector<BSONObj>& indices);
+                                const vector<IndexEntry>& indices);
 
         //
         // Collection Scan Data Access method.
@@ -114,7 +125,7 @@ namespace mongo {
         // The inArrayOperator flag deserves some attention.  It is set when we're processing a child of
         // a MatchExpression::ALL or MatchExpression::ELEM_MATCH_OBJECT.
         //
-        // Behavior changes for all methods below that take it as an argument:
+        // When true, the following behavior changes for all methods below that take it as an argument:
         // 0. No deletion of MatchExpression(s).  In fact,
         // 1. No mutation of the MatchExpression at all.  We need the tree as-is in order to perform
         //    a filter on the entire tree.
@@ -129,21 +140,21 @@ namespace mongo {
          */
         static QuerySolutionNode* buildIndexedDataAccess(MatchExpression* root,
                                                          bool inArrayOperator,
-                                                         const vector<BSONObj>& indexKeyPatterns);
+                                                         const vector<IndexEntry>& indices);
 
         /**
          * Takes ownership of 'root'.
          */
         static QuerySolutionNode* buildIndexedAnd(MatchExpression* root,
                                                   bool inArrayOperator,
-                                                  const vector<BSONObj>& indexKeyPatterns);
+                                                  const vector<IndexEntry>& indices);
 
         /**
          * Takes ownership of 'root'.
          */
         static QuerySolutionNode* buildIndexedOr(MatchExpression* root,
                                                  bool inArrayOperator,
-                                                 const vector<BSONObj>& indexKeyPatterns);
+                                                 const vector<IndexEntry>& indices);
 
         /**
          * Helper used by buildIndexedAnd and buildIndexedOr.
@@ -160,7 +171,7 @@ namespace mongo {
          */
         static bool processIndexScans(MatchExpression* root,
                                       bool inArrayOperator,
-                                      const vector<BSONObj>& indexKeyPatterns,
+                                      const vector<IndexEntry>& indices,
                                       vector<QuerySolutionNode*>* out);
 
         //
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index b47e3106ada..c325cadd76d 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -59,7 +59,8 @@ namespace {
         //
 
         void setIndex(BSONObj keyPattern) {
-            keyPatterns.push_back(keyPattern);
+            // false means not multikey.
+            keyPatterns.push_back(IndexEntry(keyPattern, false));
         }
 
         //
@@ -162,7 +163,7 @@ namespace {
 
         BSONObj queryObj;
         CanonicalQuery* cq;
-        vector<BSONObj> keyPatterns;
+        vector<IndexEntry> keyPatterns;
         vector<QuerySolution*> solns;
     };
 
@@ -356,6 +357,26 @@ namespace {
         cout << indexedSolution->toString() << endl;
     }
 
+    TEST_F(SingleIndexTest, AndWithUnindexedOrChild) {
+        setIndex(BSON("a" << 1));
+        runQuery(fromjson("{a:20, $or: [{b:1}, {c:7}]}"));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+        QuerySolution* indexedSolution = NULL;
+        getPlanByType(STAGE_FETCH, &indexedSolution);
+        cout << indexedSolution->toString() << endl;
+    }
+
+
+    TEST_F(SingleIndexTest, AndWithOrWithOneIndex) {
+        setIndex(BSON("b" << 1));
+        setIndex(BSON("a" << 1));
+        runQuery(fromjson("{$or: [{b:1}, {c:7}], a:20}"));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+        QuerySolution* indexedSolution = NULL;
+        getPlanByType(STAGE_FETCH, &indexedSolution);
+        cout << indexedSolution->toString() << endl;
+    }
+
     //
     // Tree operations that require simple tree rewriting.
     //
@@ -520,6 +541,13 @@ namespace {
         ASSERT_EQUALS(getNumSolutions(), 2U);
     }
 
+    TEST_F(SingleIndexTest, ElemMatchCompoundTwoFields) {
+        setIndex(BSON("a.b" << 1 << "a.c" << 1));
+        runQuery(fromjson("{a : {$elemMatch: {b:1, c:1}}}"));
+        dumpSolutions();
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+    }
+
     // STOPPED HERE - need to hook up machinery for multiple indexed predicates
     //                second is not working (until the machinery is in place)
     //
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index a07d5fa725d..0d3845251ba 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -67,7 +67,7 @@ namespace mongo {
 
     void AndHashNode::appendToString(stringstream* ss, int indent) const {
         addIndent(ss, indent);
-        *ss << "AND_HASH";
+        *ss << "AND_HASH\n";
         if (NULL != filter) {
             addIndent(ss, indent + 1);
             *ss << " filter = " << filter->toString() << endl;
@@ -79,7 +79,8 @@ namespace mongo {
         addIndent(ss, indent + 1);
         *ss << "getSort = " << getSort().toString() << endl;
         for (size_t i = 0; i < children.size(); ++i) {
-            *ss << "Child " << i << ": ";
+            addIndent(ss, indent + 1);
+            *ss << "Child " << i << ":\n";
             children[i]->appendToString(ss, indent + 1);
         }
     }