SERVER-10471 Fleshing out the new query planner / enumerator

21 files changed, 1555 insertions, 471 deletions

diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
index 33bd50b8bb9..6b765761ae8 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -87,7 +87,7 @@ namespace mongo {
         /**
          * Get the i-th child.
          */
-        virtual const MatchExpression* getChild( size_t i ) const { return NULL; }
+        virtual MatchExpression* getChild( size_t i ) const { return NULL; }
 
         /**
          * Get the path of the leaf.  Returns StringData() if there is no path (node is logical).
@@ -162,6 +162,7 @@ namespace mongo {
         public:
             virtual ~TagData() { }
             virtual void debugString(StringBuilder* builder) const = 0;
+            virtual TagData* clone() const = 0;
         };
 
         /**
@@ -169,6 +170,7 @@ namespace mongo {
          */
         void setTag(TagData* data) { _tagData.reset(data); }
         TagData* getTag() const { return _tagData.get(); }
+        virtual void resetTag() = 0;
 
         //
         // Debug information
@@ -211,6 +213,7 @@ namespace mongo {
             return other->matchType() == ATOMIC;
         }
 
+        virtual void resetTag() { setTag(NULL); }
     };
 
     class FalseMatchExpression : public MatchExpression {
@@ -235,6 +238,7 @@ namespace mongo {
             return other->matchType() == ALWAYS_FALSE;
         }
 
+        virtual void resetTag() { setTag(NULL); }
     };
 
 }
diff --git a/src/mongo/db/matcher/expression_array.cpp b/src/mongo/db/matcher/expression_array.cpp
index f0a09eba206..33c6814d6ce 100644
--- a/src/mongo/db/matcher/expression_array.cpp
+++ b/src/mongo/db/matcher/expression_array.cpp
@@ -93,7 +93,7 @@ namespace mongo {
 
     // -------
 
-    Status ElemMatchObjectMatchExpression::init( const StringData& path, const MatchExpression* sub ) {
+    Status ElemMatchObjectMatchExpression::init( const StringData& path, MatchExpression* sub ) {
         _sub.reset( sub );
         return initPath( path );
     }
@@ -129,7 +129,7 @@ namespace mongo {
         _subs.clear();
     }
 
-    Status ElemMatchValueMatchExpression::init( const StringData& path, const MatchExpression* sub ) {
+    Status ElemMatchValueMatchExpression::init( const StringData& path, MatchExpression* sub ) {
         init( path );
         add( sub );
         return Status::OK();
@@ -140,7 +140,7 @@ namespace mongo {
     }
 
 
-    void ElemMatchValueMatchExpression::add( const MatchExpression* sub ) {
+    void ElemMatchValueMatchExpression::add( MatchExpression* sub ) {
         verify( sub );
         _subs.push_back( sub );
     }
@@ -192,7 +192,7 @@ namespace mongo {
         return s;
     }
 
-    void AllElemMatchOp::add( const ArrayMatchingMatchExpression* expr ) {
+    void AllElemMatchOp::add( ArrayMatchingMatchExpression* expr ) {
         verify( expr );
         _list.push_back( expr );
     }
diff --git a/src/mongo/db/matcher/expression_array.h b/src/mongo/db/matcher/expression_array.h
index 922db8ed2be..dbc06e46059 100644
--- a/src/mongo/db/matcher/expression_array.h
+++ b/src/mongo/db/matcher/expression_array.h
@@ -62,6 +62,9 @@ namespace mongo {
         bool equivalent( const MatchExpression* other ) const;
 
         const StringData path() const { return _path; }
+
+        virtual void resetTag() { setTag(NULL); }
+
     private:
         StringData _path;
         ElementPath _elementPath;
@@ -70,7 +73,7 @@ namespace mongo {
     class ElemMatchObjectMatchExpression : public ArrayMatchingMatchExpression {
     public:
         ElemMatchObjectMatchExpression() : ArrayMatchingMatchExpression( ELEM_MATCH_OBJECT ){}
-        Status init( const StringData& path, const MatchExpression* sub );
+        Status init( const StringData& path, MatchExpression* sub );
 
         bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const;
 
@@ -83,10 +86,10 @@ namespace mongo {
         virtual void debugString( StringBuilder& debug, int level ) const;
 
         virtual size_t numChildren() const { return 1; }
-        virtual const MatchExpression* getChild( size_t i ) const { return _sub.get(); }
+        virtual MatchExpression* getChild( size_t i ) const { return _sub.get(); }
 
     private:
-        boost::scoped_ptr<const MatchExpression> _sub;
+        boost::scoped_ptr<MatchExpression> _sub;
     };
 
     class ElemMatchValueMatchExpression : public ArrayMatchingMatchExpression {
@@ -95,8 +98,8 @@ namespace mongo {
         virtual ~ElemMatchValueMatchExpression();
 
         Status init( const StringData& path );
-        Status init( const StringData& path, const MatchExpression* sub );
-        void add( const MatchExpression* sub );
+        Status init( const StringData& path, MatchExpression* sub );
+        void add( MatchExpression* sub );
 
         bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const;
 
@@ -112,12 +115,12 @@ namespace mongo {
         virtual void debugString( StringBuilder& debug, int level ) const;
 
         virtual size_t numChildren() const { return _subs.size(); }
-        virtual const MatchExpression* getChild( size_t i ) const { return _subs[i]; }
+        virtual MatchExpression* getChild( size_t i ) const { return _subs[i]; }
 
     private:
         bool _arrayElementMatchesAll( const BSONElement& e ) const;
 
-        std::vector< const MatchExpression* > _subs;
+        std::vector<MatchExpression*> _subs;
     };
 
     class SizeMatchExpression : public ArrayMatchingMatchExpression {
@@ -152,13 +155,13 @@ namespace mongo {
         virtual ~AllElemMatchOp();
 
         Status init( const StringData& path );
-        void add( const ArrayMatchingMatchExpression* expr );
+        void add( ArrayMatchingMatchExpression* expr );
 
         virtual MatchExpression* shallowClone() const {
             AllElemMatchOp* e = new AllElemMatchOp();
             e->init(path());
             for (size_t i = 0; i < _list.size(); ++i) {
-                e->add(reinterpret_cast<const ArrayMatchingMatchExpression*>(
+                e->add(reinterpret_cast<ArrayMatchingMatchExpression*>(
                     _list[i]->shallowClone()));
             }
             return e;
@@ -176,16 +179,18 @@ namespace mongo {
         virtual bool equivalent( const MatchExpression* other ) const;
 
         virtual size_t numChildren() const { return _list.size(); }
-        virtual const ArrayMatchingMatchExpression* getChild( size_t i ) const { return _list[i]; }
+        virtual ArrayMatchingMatchExpression* getChild( size_t i ) const { return _list[i]; }
 
         const StringData path() const { return _path; }
 
+        virtual void resetTag() { setTag(NULL); }
+
     private:
         bool _allMatch( const BSONObj& anArray ) const;
 
         StringData _path;
         ElementPath _elementPath;
-        std::vector< const ArrayMatchingMatchExpression* > _list;
+        std::vector<ArrayMatchingMatchExpression*> _list;
     };
 
 }
diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp
index 75b73326ee6..a25373a408f 100644
--- a/src/mongo/db/matcher/expression_leaf.cpp
+++ b/src/mongo/db/matcher/expression_leaf.cpp
@@ -487,6 +487,9 @@ namespace mongo {
     LeafMatchExpression* InMatchExpression::shallowClone() const {
         InMatchExpression* next = new InMatchExpression();
         copyTo( next );
+        if ( getTag() ) {
+            next->setTag(getTag()->clone());
+        }
         return next;
     }
 
diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h
index e969263d05c..0bb381dd889 100644
--- a/src/mongo/db/matcher/expression_leaf.h
+++ b/src/mongo/db/matcher/expression_leaf.h
@@ -67,6 +67,8 @@ namespace mongo {
 
         virtual const StringData path() const { return _path; }
 
+        virtual void resetTag() { setTag(NULL); }
+
     protected:
         Status initPath( const StringData& path );
 
@@ -110,6 +112,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             ComparisonMatchExpression* e = new EqualityMatchExpression();
             e->init( path(), _rhs  );
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
     };
@@ -120,6 +125,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             ComparisonMatchExpression* e = new LTEMatchExpression();
             e->init( path(), _rhs  );
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
@@ -131,6 +139,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             ComparisonMatchExpression* e = new LTMatchExpression();
             e->init( path(), _rhs  );
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
@@ -142,6 +153,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             ComparisonMatchExpression* e = new GTMatchExpression();
             e->init( path(), _rhs  );
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
@@ -153,6 +167,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             ComparisonMatchExpression* e = new GTEMatchExpression();
             e->init( path(), _rhs  );
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
@@ -179,6 +196,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             RegexMatchExpression* e = new RegexMatchExpression();
             e->init( path(), _regex, _flags );
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
@@ -206,6 +226,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             ModMatchExpression* m = new ModMatchExpression();
             m->init( path(), _divisor, _remainder );
+            if ( getTag() ) {
+                m->setTag(getTag()->clone());
+            }
             return m;
         }
 
@@ -232,6 +255,9 @@ namespace mongo {
         virtual LeafMatchExpression* shallowClone() const {
             ExistsMatchExpression* e = new ExistsMatchExpression();
             e->init( path() );
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
@@ -323,6 +349,9 @@ namespace mongo {
         virtual MatchExpression* shallowClone() const {
             TypeMatchExpression* e = new TypeMatchExpression();
             e->init(_path, _type);
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
@@ -341,6 +370,8 @@ namespace mongo {
 
         virtual const StringData path() const { return _path; }
 
+        virtual void resetTag() { setTag(NULL); }
+
     private:
         bool _matches( const StringData& path,
                        const MatchableDocument* doc,
diff --git a/src/mongo/db/matcher/expression_tree.h b/src/mongo/db/matcher/expression_tree.h
index 29f0c520811..5536b96d436 100644
--- a/src/mongo/db/matcher/expression_tree.h
+++ b/src/mongo/db/matcher/expression_tree.h
@@ -57,7 +57,7 @@ namespace mongo {
         void clearAndRelease() { _expressions.clear(); }
 
         virtual size_t numChildren() const { return _expressions.size(); }
-        virtual const MatchExpression* getChild( size_t i ) const { return _expressions[i]; }
+        virtual MatchExpression* getChild( size_t i ) const { return _expressions[i]; }
 
         bool equivalent( const MatchExpression* other ) const;
 
@@ -81,10 +81,20 @@ namespace mongo {
             for (size_t i = 0; i < numChildren(); ++i) {
                 self->add(getChild(i)->shallowClone());
             }
+            if ( getTag() ) {
+                self->setTag(getTag()->clone());
+            }
             return self;
         }
 
         virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+
+        virtual void resetTag() {
+            setTag(NULL);
+            for (size_t i = 0; i < numChildren(); ++i) {
+                getChild(i)->resetTag();
+            }
+        }
     };
 
     class OrMatchExpression : public ListOfMatchExpression {
@@ -100,10 +110,20 @@ namespace mongo {
             for (size_t i = 0; i < numChildren(); ++i) {
                 self->add(getChild(i)->shallowClone());
             }
+            if ( getTag() ) {
+                self->setTag(getTag()->clone());
+            }
             return self;
         }
 
         virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+
+        virtual void resetTag() {
+            setTag(NULL);
+            for (size_t i = 0; i < numChildren(); ++i) {
+                getChild(i)->resetTag();
+            }
+        }
     };
 
     class NorMatchExpression : public ListOfMatchExpression {
@@ -119,10 +139,20 @@ namespace mongo {
             for (size_t i = 0; i < numChildren(); ++i) {
                 self->add(getChild(i)->shallowClone());
             }
+            if ( getTag() ) {
+                self->setTag(getTag()->clone());
+            }
             return self;
         }
 
         virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+
+        virtual void resetTag() {
+            setTag(NULL);
+            for (size_t i = 0; i < numChildren(); ++i) {
+                getChild(i)->resetTag();
+            }
+        }
     };
 
     class NotMatchExpression : public MatchExpression {
@@ -141,6 +171,9 @@ namespace mongo {
             NotMatchExpression* self = new NotMatchExpression();
             MatchExpression* child = _exp->shallowClone();
             self->init(child);
+            if ( getTag() ) {
+                self->setTag(getTag()->clone());
+            }
             return self;
         }
 
@@ -159,6 +192,10 @@ namespace mongo {
         virtual size_t numChildren() const { return 1; }
         virtual MatchExpression* getChild( size_t i ) const { return _exp.get(); }
 
+        virtual void resetTag() {
+            setTag( NULL );
+            _exp->resetTag();
+        }
 
     private:
         boost::scoped_ptr<MatchExpression> _exp;
diff --git a/src/mongo/db/matcher/expression_where.cpp b/src/mongo/db/matcher/expression_where.cpp
index a439ed4fe60..6a1bad81c91 100644
--- a/src/mongo/db/matcher/expression_where.cpp
+++ b/src/mongo/db/matcher/expression_where.cpp
@@ -56,12 +56,18 @@ namespace mongo {
         virtual MatchExpression* shallowClone() const {
             WhereMatchExpression* e = new WhereMatchExpression();
             e->init(_ns, _code, _userScope);
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
             return e;
         }
 
         virtual void debugString( StringBuilder& debug, int level = 0 ) const;
 
         virtual bool equivalent( const MatchExpression* other ) const ;
+
+        virtual void resetTag() { setTag(NULL); }
+
     private:
         string _ns;
         string _code;
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index 665700567d3..14ae82418e7 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -3,15 +3,16 @@
 Import("env")
 
 env.StaticLibrary(
-    target = 'query_planner',
-    source = [
+    target='query_planner',
+    source=[
         "canonical_query.cpp",
         "index_bounds_builder.cpp",
         "lite_parsed_query.cpp",
+        "plan_enumerator.cpp",
         "query_planner.cpp",
         # "query_projection.cpp",
     ],
-    LIBDEPS = [
+    LIBDEPS=[
         "index_bounds",
         "$BUILD_DIR/mongo/bson",
         "$BUILD_DIR/mongo/expressions",
@@ -20,45 +21,66 @@ env.StaticLibrary(
 )
 
 env.StaticLibrary(
-    target = 'query',
-    source = [
+    target='query',
+    source=[
         "multi_plan_runner.cpp",
         "new_find.cpp",
         "plan_ranker.cpp",
         "stage_builder.cpp",
     ],
-    LIBDEPS = [
+    LIBDEPS=[
         "query_planner",
         "$BUILD_DIR/mongo/db/exec/exec"
     ],
 )
 
 env.StaticLibrary(
-    target = "index_bounds",
-    source = [
+    target="index_bounds",
+    source=[
         "index_bounds.cpp",
+        "interval.cpp",
     ],
-    LIBDEPS = [
+    LIBDEPS=[
         "$BUILD_DIR/mongo/bson",
     ],
 )
 
 env.CppUnitTest(
-    target = "index_bounds_test",
-    source = [
+    target="index_bounds_test",
+    source=[
         "index_bounds_test.cpp"
     ],
-    LIBDEPS = [
+    LIBDEPS=[
         "index_bounds",
     ],
 )
 
 env.CppUnitTest(
-    target = "query_planner_test",
-    source = [
+    target="interval_test",
+    source=[
+        "interval_test.cpp"
+    ],
+    LIBDEPS=[
+        "index_bounds",
+    ],
+)
+
+env.CppUnitTest(
+    target="query_planner_test",
+    source=[
         "query_planner_test.cpp"
     ],
-    LIBDEPS = [
+    LIBDEPS=[
+        "query_planner",
+    ],
+)
+
+env.CppUnitTest(
+    target="plan_enumerator_test",
+    source=[
+        "plan_enumerator_test.cpp"
+    ],
+    LIBDEPS=[
         "query_planner",
     ],
 )
diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp
index 89f5b097de5..bd2ded64e00 100644
--- a/src/mongo/db/query/index_bounds.cpp
+++ b/src/mongo/db/query/index_bounds.cpp
@@ -28,20 +28,41 @@
 
 #include "mongo/db/query/index_bounds.h"
 
-namespace {
+namespace mongo {
 
-    // Return a value in the set {-1, 0, 1} to represent the sign of parameter i.
-    int sgn(int i) {
-        if (i == 0)
-            return 0;
-        return i > 0 ? 1 : -1;
-    }
+    namespace {
 
-}  // namespace
+        // Return a value in the set {-1, 0, 1} to represent the sign of parameter i.
+        int sgn(int i) {
+            if (i == 0)
+                return 0;
+            return i > 0 ? 1 : -1;
+        }
 
-namespace mongo {
+    }  // namespace
 
     // For debugging.
+    size_t IndexBounds::size() const {
+        return fields.size();
+    }
+
+    string IndexBounds::getFieldName(size_t i) const {
+        return i < size() ? fields[i].name : "";
+    }
+
+    size_t IndexBounds::getNumIntervals(size_t i) const {
+        return i < size() ? fields[i].intervals.size() : 0;
+    }
+
+    Interval IndexBounds::getInterval(size_t i, size_t j) const {
+        if (i < size() && j < fields[i].intervals.size()) {
+            return fields[i].intervals[j];
+        }
+        else {
+            return Interval();
+        }
+    }
+
     string IndexBounds::toString() const {
         stringstream ss;
         for (size_t i = 0; i < fields.size(); ++i) {
diff --git a/src/mongo/db/query/index_bounds.h b/src/mongo/db/query/index_bounds.h
index a5185fdf7e2..a7a126c31e8 100644
--- a/src/mongo/db/query/index_bounds.h
+++ b/src/mongo/db/query/index_bounds.h
@@ -32,28 +32,11 @@
 #include <vector>
 
 #include "mongo/db/jsobj.h"
+#include "mongo/db/query/interval.h"
 
 namespace mongo {
 
     /**
-     * A range of values for one field.
-     */
-    struct Interval {
-        // Start and End must be ordered according to the index order.
-        BSONElement start;
-        bool startInclusive;
-
-        BSONElement end;
-        bool endInclusive;
-
-        // No BSONValue means we have to keep a BSONObj and pointers (BSONElement) into it.
-        // 'start' may not point at the first field in _intervalData.
-        // 'end' may not point at the last field in _intervalData.
-        // 'start' and 'end' may point at the same field.
-        BSONObj _intervalData;
-    };
-
-    /**
      * An ordered list of intervals for one field.
      */
     struct OrderedIntervalList {
@@ -74,8 +57,6 @@ namespace mongo {
         // For each indexed field, the values that the field is allowed to take on.
         vector<OrderedIntervalList> fields;
 
-        string toString() const;
-
         // 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
@@ -87,6 +68,13 @@ namespace mongo {
         // We can traverse this backwards if indexed descending.
         bool isValidFor(const BSONObj& keyPattern, int direction);
 
+        // Methods below used for debugging purpose only. Do not use outside testing code.
+        size_t size() const;
+        std::string getFieldName(size_t i) const;
+        size_t getNumIntervals(size_t i) const;
+        Interval getInterval(size_t i, size_t j) const;
+        std::string toString() const;
+
         // TODO: KILL THIS?
         // We need this for legacy non-index indices (2d/2dsphere) that take a BSONObj and don't
         // deal with the kind of absurd Btree-only behavior of IndexBoundsChecker.
diff --git a/src/mongo/db/query/index_bounds_test.cpp b/src/mongo/db/query/index_bounds_test.cpp
index c6d1400bc6c..72a24bb9ecb 100644
--- a/src/mongo/db/query/index_bounds_test.cpp
+++ b/src/mongo/db/query/index_bounds_test.cpp
@@ -40,24 +40,13 @@ using namespace mongo;
 
 namespace {
 
-    Interval makeInterval(const BSONObj& obj, bool startInclusive, bool endInclusive) {
-        Interval i;
-        i._intervalData = obj.getOwned();
-        BSONObjIterator it(i._intervalData);
-        i.start = it.next();
-        i.end = it.next();
-        i.startInclusive = startInclusive;
-        i.endInclusive = endInclusive;
-        return i;
-    }
-
     //
     // Validation
     //
 
     TEST(IndexBoundsTest, ValidBasic) {
         OrderedIntervalList list("foo");
-        list.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
+        list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
         IndexBounds bounds;
         bounds.fields.push_back(list);
 
@@ -75,13 +64,13 @@ namespace {
 
     TEST(IndexBoundsTest, ValidTwoFields) {
         OrderedIntervalList list("foo");
-        list.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
+        list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
         IndexBounds bounds;
         bounds.fields.push_back(list);
 
         // Let's add another field
         OrderedIntervalList otherList("bar");
-        otherList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 3), true, true));
+        otherList.intervals.push_back(Interval(BSON("" << 0 << "" << 3), true, true));
         bounds.fields.push_back(otherList);
 
         // These are OK.
@@ -100,8 +89,8 @@ namespace {
     TEST(IndexBoundsTest, ValidIntervalsInOrder) {
         OrderedIntervalList list("foo");
         // Whether navigated forward or backward, there's no valid ordering for these two intervals.
-        list.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
-        list.intervals.push_back(makeInterval(BSON("" << 0 << "" << 5), true, true));
+        list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
+        list.intervals.push_back(Interval(BSON("" << 0 << "" << 5), true, true));
         IndexBounds bounds;
         bounds.fields.push_back(list);
         ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1));
@@ -113,8 +102,8 @@ namespace {
     TEST(IndexBoundsTest, ValidNoOverlappingIntervals) {
         OrderedIntervalList list("foo");
         // overlapping intervals not allowed.
-        list.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
-        list.intervals.push_back(makeInterval(BSON("" << 19 << "" << 25), true, true));
+        list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
+        list.intervals.push_back(Interval(BSON("" << 19 << "" << 25), true, true));
         IndexBounds bounds;
         bounds.fields.push_back(list);
         ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1));
@@ -122,8 +111,8 @@ namespace {
 
     TEST(IndexBoundsTest, ValidOverlapOnlyWhenBothOpen) {
         OrderedIntervalList list("foo");
-        list.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, false));
-        list.intervals.push_back(makeInterval(BSON("" << 20 << "" << 25), false, true));
+        list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, false));
+        list.intervals.push_back(Interval(BSON("" << 20 << "" << 25), false, true));
         IndexBounds bounds;
         bounds.fields.push_back(list);
         ASSERT(bounds.isValidFor(BSON("foo" << 1), 1));
@@ -135,10 +124,10 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, StartKey) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
 
         OrderedIntervalList barList("bar");
-        barList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 5), false, false));
+        barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
@@ -158,11 +147,11 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, CheckEnd) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
-        fooList.intervals.push_back(makeInterval(BSON("" << 21 << "" << 30), true, false));
+        fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false));
 
         OrderedIntervalList barList("bar");
-        barList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 5), false, false));
+        barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
@@ -219,11 +208,11 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, MoveIntervalForwardToNextInterval) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
-        fooList.intervals.push_back(makeInterval(BSON("" << 21 << "" << 30), true, false));
+        fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false));
 
         OrderedIntervalList barList("bar");
-        barList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 5), false, false));
+        barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
@@ -263,10 +252,10 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, MoveIntervalForwardManyIntervals) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
-        fooList.intervals.push_back(makeInterval(BSON("" << 21 << "" << 30), true, false));
-        fooList.intervals.push_back(makeInterval(BSON("" << 31 << "" << 40), true, false));
-        fooList.intervals.push_back(makeInterval(BSON("" << 41 << "" << 50), true, false));
+        fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false));
+        fooList.intervals.push_back(Interval(BSON("" << 31 << "" << 40), true, false));
+        fooList.intervals.push_back(Interval(BSON("" << 41 << "" << 50), true, false));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
@@ -298,10 +287,10 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, SimpleCheckKey) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 7 << "" << 20), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true));
 
         OrderedIntervalList barList("bar");
-        barList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 5), false, true));
+        barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, true));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
@@ -365,11 +354,11 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, FirstKeyMovedIsOKSecondKeyMustMove) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 9), true, true));
-        fooList.intervals.push_back(makeInterval(BSON("" << 10 << "" << 20), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 0 << "" << 9), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 10 << "" << 20), true, true));
 
         OrderedIntervalList barList("bar");
-        barList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 5), false, true));
+        barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, true));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
@@ -406,10 +395,10 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, SimpleCheckKeyBackwards) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 20 << "" << 7), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 20 << "" << 7), true, true));
 
         OrderedIntervalList barList("bar");
-        barList.intervals.push_back(makeInterval(BSON("" << 5 << "" << 0), true, false));
+        barList.intervals.push_back(Interval(BSON("" << 5 << "" << 0), true, false));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
@@ -476,11 +465,11 @@ namespace {
 
     TEST(IndexBoundsCheckerTest, CheckEndBackwards) {
         OrderedIntervalList fooList("foo");
-        fooList.intervals.push_back(makeInterval(BSON("" << 30 << "" << 21), true, true));
-        fooList.intervals.push_back(makeInterval(BSON("" << 20 << "" << 7), true, false));
+        fooList.intervals.push_back(Interval(BSON("" << 30 << "" << 21), true, true));
+        fooList.intervals.push_back(Interval(BSON("" << 20 << "" << 7), true, false));
 
         OrderedIntervalList barList("bar");
-        barList.intervals.push_back(makeInterval(BSON("" << 0 << "" << 5), false, false));
+        barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false));
 
         IndexBounds bounds;
         bounds.fields.push_back(fooList);
diff --git a/src/mongo/db/query/index_tag.h b/src/mongo/db/query/index_tag.h
new file mode 100644
index 00000000000..ee8791c38ba
--- /dev/null
+++ b/src/mongo/db/query/index_tag.h
@@ -0,0 +1,44 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/bson/util/builder.h"
+#include "mongo/db/matcher/expression.h"
+
+namespace mongo {
+
+    // XXX
+    class IndexTag : public MatchExpression::TagData {
+    public:
+
+        IndexTag(size_t i) : index(i) { }
+
+        virtual ~IndexTag() { }
+
+        virtual void debugString(StringBuilder* builder) const {
+            *builder << " || Selected Index #" << index;
+        }
+
+        virtual MatchExpression::TagData* clone() const {
+            return new IndexTag(index);
+        }
+
+        // What index should we try to use for this leaf?
+        size_t index;
+    };
+
+} // namespace mongo
diff --git a/src/mongo/db/query/interval.cpp b/src/mongo/db/query/interval.cpp
new file mode 100644
index 00000000000..9bf0cc51a8f
--- /dev/null
+++ b/src/mongo/db/query/interval.cpp
@@ -0,0 +1,239 @@
+/**
+ *    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/>.
+ */
+
+#include "mongo/db/query/interval.h"
+
+namespace mongo {
+
+    namespace {
+
+        /** Returns true if lhs and rhs intersection is not empty */
+        bool intersects(const Interval& lhs, const Interval& rhs) {
+            int res = lhs.start.woCompare(rhs.end, false);
+            if (res > 0) {
+                return false;
+            }
+            else if (res == 0 && (!lhs.startInclusive || !rhs.endInclusive)) {
+                return false;
+            }
+
+            res = rhs.start.woCompare(lhs.end, false);
+            if (res > 0) {
+                return false;
+            }
+            else if (res == 0 && (!rhs.startInclusive || !lhs.endInclusive)) {
+                return false;
+            }
+
+            return true;
+        }
+
+        /** Returns true if lhs and rhs represent the same interval */
+        bool exact(const Interval& lhs, const Interval& rhs) {
+            if (lhs.startInclusive != rhs.startInclusive) {
+                return false;
+            }
+
+            if (lhs.endInclusive != rhs.endInclusive) {
+                return false;
+            }
+
+            int res = lhs.start.woCompare(rhs.start, false);
+            if (res != 0) {
+                return false;
+            }
+
+            res = lhs.end.woCompare(rhs.end, false);
+            if (res != 0) {
+                return false;
+            }
+
+            return true;
+        }
+
+        /** Returns true if lhs is fully withing rhs */
+        bool within(const Interval& lhs, const Interval& rhs) {
+            int res = lhs.start.woCompare(rhs.start, false);
+            if (res < 0) {
+                return false;
+            }
+            else if (res == 0 && lhs.startInclusive && !rhs.startInclusive) {
+                return false;
+            }
+
+            res = lhs.end.woCompare(rhs.end, false);
+            if (res > 0) {
+                return false;
+            }
+            else if (res == 0 && lhs.endInclusive && !rhs.endInclusive) {
+                return false;
+            }
+
+            return true;
+        }
+
+        /** Returns true if the start of lhs comes before the start of rhs */
+        bool precedes(const Interval& lhs, const Interval& rhs) {
+            int res = lhs.start.woCompare(rhs.start, false);
+            if (res < 0) {
+                return true;
+            }
+            else if (res == 0 && lhs.startInclusive && !rhs.startInclusive) {
+                return true;
+            }
+            return false;
+        }
+
+    } // unnamed namespace
+
+    Interval:: Interval()
+        : _intervalData(BSONObj())
+        , start(BSONElement())
+        , startInclusive(false)
+        , end(BSONElement())
+        , endInclusive(false) {
+    }
+
+    Interval::Interval(BSONObj base, bool si, bool ei) {
+        init(base, si, ei);
+    }
+
+    void Interval::init(BSONObj base, bool si, bool ei) {
+        dassert(base.nFields() >= 2);
+
+        _intervalData = base.getOwned();
+        BSONObjIterator it(_intervalData);
+        start = it.next();
+        end = it.next();
+        startInclusive = si;
+        endInclusive = ei;
+    }
+
+    bool Interval::isEmpty() const {
+        return _intervalData.nFields() == 0;
+    }
+
+    // TODO: shortcut number of comparisons
+    Interval::IntervalComparison Interval::compare(const Interval& other) const {
+
+        //
+        // Intersect cases
+        //
+
+        if (intersects(*this, other)) {
+            if (exact(*this, other)) {
+                return INTERVAL_EQUALS;
+            }
+            if (within(*this, other)) {
+                return INTERVAL_WITHIN;
+            }
+            if (within(other, *this)) {
+                return INTERVAL_CONTAINS;
+            }
+            if (precedes(*this, other)) {
+                    return INTERVAL_OVERLAPS_BEFORE;
+            }
+            return INTERVAL_OVERLAPS_AFTER;
+        }
+
+        //
+        // Non-intersect cases
+        //
+
+        if (precedes(*this, other)) {
+            return INTERVAL_PRECEDES;
+        }
+        return INTERVAL_SUCCEDS;
+    }
+
+    void Interval::intersect(const Interval& other, IntervalComparison cmp) {
+        if (cmp == INTERVAL_UNKNOWN) {
+            cmp = this->compare(other);
+        }
+
+        BSONObjBuilder builder;
+        switch (cmp) {
+
+        case INTERVAL_EQUALS:
+        case INTERVAL_WITHIN:
+            break;
+
+        case INTERVAL_CONTAINS:
+            builder.append(other.start);
+            builder.append(other.end);
+            init(builder.obj(), other.startInclusive, other.endInclusive);
+            break;
+
+        case INTERVAL_OVERLAPS_AFTER:
+            builder.append(start);
+            builder.append(other.end);
+            init(builder.obj(), startInclusive, other.endInclusive);
+            break;
+
+        case INTERVAL_OVERLAPS_BEFORE:
+            builder.append(other.start);
+            builder.append(end);
+            init(builder.obj(), other.startInclusive, endInclusive);
+            break;
+
+        case INTERVAL_PRECEDES:
+        case INTERVAL_SUCCEDS:
+            *this = Interval();
+            break;
+
+        default:
+            dassert(false);
+        }
+    }
+
+    void Interval::combine(const Interval& other, IntervalComparison cmp) {
+        if (cmp == INTERVAL_UNKNOWN) {
+            cmp = this->compare(other);
+        }
+
+        BSONObjBuilder builder;
+        switch (cmp) {
+
+        case INTERVAL_EQUALS:
+        case INTERVAL_CONTAINS:
+            break;
+
+        case INTERVAL_WITHIN:
+            builder.append(other.start);
+            builder.append(other.end);
+            init(builder.obj(), other.startInclusive, other.endInclusive);
+            break;
+
+        case INTERVAL_OVERLAPS_AFTER:
+        case INTERVAL_SUCCEDS:
+            builder.append(other.start);
+            builder.append(end);
+            init(builder.obj(), other.startInclusive, endInclusive);
+            break;
+
+        case INTERVAL_OVERLAPS_BEFORE:
+        case INTERVAL_PRECEDES:
+            builder.append(start);
+            builder.append(other.end);
+            init(builder.obj(), startInclusive, other.endInclusive);
+            break;
+
+        default:
+            dassert(false);
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/query/interval.h b/src/mongo/db/query/interval.h
new file mode 100644
index 00000000000..f726748773b
--- /dev/null
+++ b/src/mongo/db/query/interval.h
@@ -0,0 +1,92 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/db/jsobj.h"
+
+namespace mongo {
+
+    /** A range of values for one field. */
+    struct Interval {
+
+        // No BSONValue means we have to keep a BSONObj and pointers (BSONElement) into it.
+        // 'start' may not point at the first field in _intervalData.
+        // 'end' may not point at the last field in _intervalData.
+        // 'start' and 'end' may point at the same field.
+        BSONObj _intervalData;
+
+        // Start and End must be ordered according to the index order.
+        BSONElement start;
+        bool startInclusive;
+
+        BSONElement end;
+        bool endInclusive;
+
+        /** Creates an empty interval */
+        Interval();
+
+        /**
+         * Creates an interval that starts at the first field of 'base' and ends at the second
+         * field of 'base'. (In other words, 'base' is a bsonobj with at least two elements, of
+         * which we don't care about field names.)
+         *
+         * The interval's extremities are closed or not depending on whether
+         * 'start'/'endIncluded' are true or not.
+         */
+        Interval(BSONObj base, bool startIncluded, bool endInclued);
+
+        /** Sets the current interval to the given values (see constructor) */
+        void init(BSONObj base, bool startIncluded, bool endIncluded);
+
+        /** Returns true if an empty-constructed interval hasn't been init()-ialized yet */
+        bool isEmpty() const;
+
+        /** Returns how 'this' compares to 'other' */
+        enum IntervalComparison {
+            // There is some intersection.
+            INTERVAL_EQUALS,
+            INTERVAL_CONTAINS,
+            INTERVAL_WITHIN,
+            INTERVAL_OVERLAPS_BEFORE,
+            INTERVAL_OVERLAPS_AFTER,
+
+            // There is no intersection.
+            INTERVAL_PRECEDES,
+            INTERVAL_SUCCEDS,
+
+            INTERVAL_UNKNOWN
+        };
+        IntervalComparison compare(const Interval& other) const;
+
+        /**
+         * Updates 'this' with the intersection of 'this' and 'other'. If 'this' and 'other'
+         * have been compare()d before, that result can be optionally passed in 'cmp'
+         */
+        void intersect(const Interval& other, IntervalComparison cmp = INTERVAL_UNKNOWN);
+
+        /**
+         * Updates 'this" with the union of 'this' and 'other'. If 'this' and 'other' have
+         * been compare()d before, that result can be optionaly passed in 'cmp'.
+         */
+        void combine(const Interval& other, IntervalComparison cmp = INTERVAL_UNKNOWN);
+    };
+
+    inline bool operator==(const Interval& lhs, const Interval& rhs) {
+        return lhs.compare(rhs) == Interval::INTERVAL_EQUALS;
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/query/interval_test.cpp b/src/mongo/db/query/interval_test.cpp
new file mode 100644
index 00000000000..9118b327d0f
--- /dev/null
+++ b/src/mongo/db/query/interval_test.cpp
@@ -0,0 +1,273 @@
+/**
+ *    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/>.
+ */
+
+#include "mongo/db/query/interval.h"
+
+#include "mongo/db/jsobj.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+    using mongo::BSONObj;
+    using mongo::Interval;
+
+    //
+    // Comparison
+    //
+
+    TEST(Comparison, Equality) {
+        Interval a(BSON("" << 0 << "" << 10), true, true);
+        ASSERT_EQUALS(a.compare(a), Interval::INTERVAL_EQUALS);
+
+        Interval b(BSON("" << 0 << "" << 10), true, false);
+        ASSERT_NOT_EQUALS(a.compare(b), Interval::INTERVAL_EQUALS);
+
+        Interval c(BSON("" << 0 << "" << 10), false, true);
+        ASSERT_NOT_EQUALS(a.compare(c), Interval::INTERVAL_EQUALS);
+
+        Interval d(BSON("" << 0 << "" << 11), true, true);
+        ASSERT_NOT_EQUALS(a.compare(d), Interval::INTERVAL_EQUALS);
+
+        Interval e(BSON("" << 1 << "" << 10), true, true);
+        ASSERT_NOT_EQUALS(a.compare(e), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Comparison, Contains) {
+        Interval a(BSON("" << 0 << "" << 10), true, true);
+        Interval b(BSON("" << 1 << "" << 9), true, true);
+        ASSERT_EQUALS(a.compare(b), Interval::INTERVAL_CONTAINS);
+
+        Interval c(BSON("" << 0 << "" << 10), true, false);
+        ASSERT_EQUALS(a.compare(c), Interval::INTERVAL_CONTAINS);
+
+        Interval d(BSON("" << 0 << "" << 10), false, true);
+        ASSERT_EQUALS(a.compare(d), Interval::INTERVAL_CONTAINS);
+
+        Interval e(BSON("" << 0 << "" << 11), false, true);
+        ASSERT_NOT_EQUALS(a.compare(e), Interval::INTERVAL_CONTAINS);
+    }
+
+    TEST(Comparison, Within) {
+        Interval a(BSON("" << 0 << "" << 10), true, true);
+        ASSERT_NOT_EQUALS(a.compare(a), Interval::INTERVAL_WITHIN);
+
+        Interval b(BSON("" << 1 << "" << 9), true, true);
+        ASSERT_EQUALS(b.compare(a), Interval::INTERVAL_WITHIN);
+
+        Interval c(BSON("" << 0 << "" << 10), true, false);
+        ASSERT_EQUALS(c.compare(a), Interval::INTERVAL_WITHIN);
+
+        Interval d(BSON("" << 0 << "" << 10), false, true);
+        ASSERT_EQUALS(d.compare(a), Interval::INTERVAL_WITHIN);
+
+        Interval e(BSON("" << 0 << "" << 11), false, true);
+        ASSERT_NOT_EQUALS(e.compare(a), Interval::INTERVAL_CONTAINS);
+    }
+
+    TEST(Comparison, OverlapsBefore) {
+        Interval a(BSON("" << 1 << "" << 9), true, false);
+        ASSERT_NOT_EQUALS(a.compare(a), Interval::INTERVAL_OVERLAPS_BEFORE);
+
+        Interval b(BSON("" << 1 << "" << 9), false, true);
+        ASSERT_EQUALS(a.compare(b), Interval::INTERVAL_OVERLAPS_BEFORE);
+
+        Interval c(BSON("" << 1 << "" << 9), false, false);
+        ASSERT_NOT_EQUALS(a.compare(c), Interval::INTERVAL_OVERLAPS_BEFORE);
+
+        Interval d(BSON("" << 2 << "" << 10), true, true);
+        ASSERT_EQUALS(a.compare(d), Interval::INTERVAL_OVERLAPS_BEFORE);
+
+        Interval e(BSON("" << 0 << "" << 9), true, false);
+        ASSERT_NOT_EQUALS(a.compare(e), Interval::INTERVAL_OVERLAPS_BEFORE);
+
+        Interval f(BSON("" << 0 << "" << 8), true, false);
+        ASSERT_NOT_EQUALS(a.compare(f), Interval::INTERVAL_OVERLAPS_BEFORE);
+    }
+
+    TEST(Comparison, OverlapsAfter) {
+        Interval a(BSON("" << 1 << "" << 9), false, true);
+        ASSERT_NOT_EQUALS(a.compare(a), Interval::INTERVAL_OVERLAPS_AFTER);
+
+        Interval b(BSON("" << 1 << "" << 9), true, false);
+        ASSERT_EQUALS(a.compare(b), Interval::INTERVAL_OVERLAPS_AFTER);
+
+        Interval c(BSON("" << 1 << "" << 9), true, true);
+        ASSERT_NOT_EQUALS(a.compare(c), Interval::INTERVAL_OVERLAPS_AFTER);
+
+        Interval d(BSON("" << 2 << "" << 10), true, true);
+        ASSERT_NOT_EQUALS(a.compare(d), Interval::INTERVAL_OVERLAPS_AFTER);
+
+        Interval e(BSON("" << 0 << "" << 9), true, false);
+        ASSERT_EQUALS(a.compare(e), Interval::INTERVAL_OVERLAPS_AFTER);
+    }
+
+    TEST(Comparison, Precedes) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        ASSERT_NOT_EQUALS(a.compare(a), Interval::INTERVAL_PRECEDES);
+
+        Interval b(BSON("" << 0 << "" << 10), true, true);
+        ASSERT_NOT_EQUALS(b.compare(a), Interval::INTERVAL_PRECEDES);
+
+        Interval c(BSON("" << 0 << "" << 10), true, false);
+        ASSERT_EQUALS(c.compare(a), Interval::INTERVAL_PRECEDES);
+
+        Interval d(BSON("" << 0 << "" << 9), true, true);
+        ASSERT_EQUALS(d.compare(a), Interval::INTERVAL_PRECEDES);
+
+        Interval e(BSON("" << 5 << "" << 15), true, true);
+        ASSERT_NOT_EQUALS(e.compare(a), Interval::INTERVAL_PRECEDES);
+
+        Interval f(BSON("" << 5 << "" << 20), true, false);
+        ASSERT_NOT_EQUALS(f.compare(a), Interval::INTERVAL_PRECEDES);
+    }
+
+    TEST(Comparison, Succeds) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        ASSERT_NOT_EQUALS(a.compare(a), Interval::INTERVAL_SUCCEDS);
+
+        Interval b(BSON("" << 20 << "" << 30), true, true);
+        ASSERT_NOT_EQUALS(b.compare(a), Interval::INTERVAL_SUCCEDS);
+
+        Interval c(BSON("" << 20 << "" << 30), false, true);
+        ASSERT_EQUALS(c.compare(a), Interval::INTERVAL_SUCCEDS);
+
+        Interval d(BSON("" << 21 << "" << 30), true, true);
+        ASSERT_EQUALS(d.compare(a), Interval::INTERVAL_SUCCEDS);
+
+        Interval e(BSON("" << 15 << "" << 30), true, true);
+        ASSERT_NOT_EQUALS(e.compare(a), Interval::INTERVAL_SUCCEDS);
+    }
+
+    //
+    // intersection
+    //
+
+    TEST(Intersection, Equals) {
+        BSONObj itv = BSON("" << 10 << "" << 20);
+        Interval a(itv, true, true);
+        a.intersect(a);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Intersection, Contains) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        BSONObj itv = BSON("" << 11 << "" << 19);
+        Interval b(itv, true, true);
+        a.intersect(b);
+        ASSERT_EQUALS(a.compare(b), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Intersection, Within) {
+        BSONObj itv = BSON("" << 10 << "" << 20);
+        Interval a(itv, true, true);
+        Interval b(BSON("" << 9 << "" << 21), true, true);
+        a.intersect(b);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Intersection, OverlapsBefore) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 15 << "" << 25), true, true);
+        a.intersect(b);
+
+        BSONObj itv = BSON("" << 15 << "" << 20);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Intersection, OverlapsAfter) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 5 << "" << 15), true, true);
+        a.intersect(b);
+
+        BSONObj itv = BSON("" << 10 << "" << 15);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Intersection, Procedes) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 0 << "" << 5), true, true);
+        a.intersect(b);
+
+        ASSERT_TRUE(a.isEmpty());
+    }
+
+    TEST(Intersection, Succeds) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 25 << "" << 30), true, true);
+        a.intersect(b);
+
+        ASSERT_TRUE(a.isEmpty());
+    }
+
+    //
+    // combine (union)
+    //
+
+    TEST(Union, Equals) {
+        BSONObj itv = BSON("" << 10 << "" << 20);
+        Interval a(itv, true, true);
+        a.combine(a);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Union, Contains) {
+        BSONObj itv = BSON("" << 10 << "" << 20);
+        Interval a(itv, true, true);
+        Interval b(BSON("" << 11 << "" << 19), true, true);
+        a.combine(b);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Union, Within) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 9 << "" << 21), true, true);
+        a.combine(b);
+        ASSERT_EQUALS(a.compare(b), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Union, OverlapsBefore) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 15 << "" << 25), true, true);
+        a.combine(b);
+        BSONObj itv = BSON("" << 10 << "" << 25);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Union, OverlapsAfter) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 5 << "" << 15), true, true);
+        a.combine(b);
+        BSONObj itv = BSON("" << 5 << "" << 20);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Union, Precedes) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 20 << "" << 30), true, true);
+        a.combine(b);
+        BSONObj itv = BSON("" << 10 << "" << 30);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+    TEST(Union, Succeds) {
+        Interval a(BSON("" << 10 << "" << 20), true, true);
+        Interval b(BSON("" << 0 << "" << 5), true, true);
+        a.combine(b);
+        BSONObj itv = BSON("" << 0 << "" << 20);
+        ASSERT_EQUALS(a.compare(Interval(itv, true, true)), Interval::INTERVAL_EQUALS);
+    }
+
+} // unnamed namespace
diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
new file mode 100644
index 00000000000..dcc7aebb3f0
--- /dev/null
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -0,0 +1,85 @@
+/**
+ *    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/>.
+ */
+
+#include "mongo/db/query/plan_enumerator.h"
+
+#include <set>
+
+#include "mongo/db/query/index_tag.h"
+
+namespace mongo {
+
+    PlanEnumerator::PlanEnumerator(MatchExpression* root,
+                                   const PredicateMap* pm,
+                                   const vector<BSONObj>* indices)
+        : _root(root)
+        , _pm(*pm)
+        , _indices(*indices) {}
+
+    Status PlanEnumerator::init() {
+        if (_pm.size() == 0) {
+            return Status(ErrorCodes::BadValue, "Cannot enumerate query without predicates map");
+        }
+
+        if (_indices.size() == 0) {
+            return Status(ErrorCodes::BadValue, "Cannot enumerate indexed plans with no indices");
+        }
+
+        // See "navigation state" assumptions on this class's header.
+        const set<RelevantIndex>& indexes = _pm.begin()->second.relevant;
+        const vector<MatchExpression*>& nodes = _pm.begin()->second.nodes;
+        IndexInfo indexInfo;
+        indexInfo.index = indexes.begin()->index;
+        indexInfo.node = *nodes.begin();
+        _indexes.push_back(indexInfo);
+
+        // Prepare to return the first plan.
+        _iter = 0;
+
+        return Status::OK();
+    }
+
+    bool PlanEnumerator::getNext(MatchExpression** tree) {
+        dassert(_indexes.size());
+
+        // If we have used all indices that are useful in any number predicates, there's
+        // nothing left to do.
+        if (_iter == _indexes.size()) {
+            return false;
+        }
+
+        // Annotate in the output tree, which nodes could use the index we're currently
+        // working with here.
+        int indexNum = _indexes[_iter].index;
+        while (_iter < _indexes.size() && _indexes[_iter].index == indexNum) {
+
+            IndexTag* indexTag = new IndexTag(indexNum);
+            MatchExpression* node = _indexes[_iter].node;
+            node->setTag(indexTag);
+
+            ++_iter;
+        }
+
+        // XXX put the tree back the way it was.
+        // XXX if we're not really manipulating the clone this is wasted work.
+        MatchExpression* ret = _root->shallowClone();
+        _root->resetTag();
+
+        *tree = ret;
+        return true;
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
new file mode 100644
index 00000000000..730343e4a5a
--- /dev/null
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -0,0 +1,105 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include <vector>
+
+#include "mongo/base/disallow_copying.h"
+#include "mongo/base/status.h"
+#include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/predicate_map.h"
+
+namespace mongo {
+
+    /**
+     * Provides elements from the power set of possible indices to use.  Uses the available
+     * predicate information to make better decisions about what indices are best.
+     *
+     * TODO: Use stats about indices.
+     */
+    class PlanEnumerator {
+        MONGO_DISALLOW_COPYING(PlanEnumerator);
+    public:
+        /**
+         * Constructs an enumerator for the query specified in 'root', given that the predicates
+         * that can be solved using indices are listed at 'pm', and the index patterns
+         * mentioned there are described by 'indices'.
+         *
+         * Does not take ownership of any arguments.  They must outlive any calls to getNext(...).
+         */
+        PlanEnumerator(MatchExpression* root,
+                       const PredicateMap* pm,
+                       const vector<BSONObj>* indices);
+
+        /**
+         * Returns OK and performs a sanity check on the input parameters and prepares the
+         * internal state so that getNext() can be called. Returns an error status with a
+         * description if the sanity check failed.
+         */
+        Status init();
+
+        /**
+         * Outputs a possible plan.  Leaves in the plan are tagged with an index to use.
+         * Returns true if a plan was outputted, false if no more plans will be outputted.
+         *
+         * 'tree' is set to point to the query tree.  A QuerySolution is built from this tree.
+         * Caller owns the pointer.  Note that 'tree' itself points into data owned by the
+         * provided CanonicalQuery.
+         *
+         * Nodes in 'tree' are tagged with indices that should be used to answer the tagged nodes.
+         * Only nodes that have a field name (isLogical() == false) will be tagged.
+         */
+        bool getNext(MatchExpression** tree);
+
+    private:
+        // Match expression we're planning for. Not owned by us.
+        MatchExpression* _root;
+
+        // A map from a field name into the nodes of the match expression that can be solved
+        // using indices (and which ones). Not owned by us.
+        const PredicateMap& _pm;
+
+        // Index pattern of the indices mentined in '_pm'. Not owned by us.
+        const std::vector<BSONObj>& _indices;
+
+        //
+        // navigation state (work in progress)
+        //
+        // We intend to enumerate, initially, solely based on the distinct index access
+        // patterns that a query would accept. The enumeration state, below, will change as we
+        // progress toward that goal. For now, we simplify by imposing the following
+        // assumptions
+        //
+        // + Each index can help only one predicate in a query
+        // + There is only one index that can help a query
+        //
+        // TODO: Relax the above
+        //
+
+        // List of all the useful indices and which node in the match expression each of them
+        // applies to.
+        struct IndexInfo{
+            int index;
+            MatchExpression* node;
+        };
+        vector<IndexInfo> _indexes;
+
+        // Iterator over _indices. Points to the next index to be used when getNext is called.
+        size_t _iter;
+    };
+
+} // namespace mongo
diff --git a/src/mongo/db/query/plan_enumerator_test.cpp b/src/mongo/db/query/plan_enumerator_test.cpp
new file mode 100644
index 00000000000..0ea2be5f0ce
--- /dev/null
+++ b/src/mongo/db/query/plan_enumerator_test.cpp
@@ -0,0 +1,91 @@
+/**
+ *    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/>.
+ */
+
+#include "mongo/db/query/plan_enumerator.h"
+
+#include <boost/scoped_ptr.hpp>
+#include <vector>
+
+#include "mongo/db/jsobj.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_parser.h"
+#include "mongo/db/query/index_tag.h"
+#include "mongo/db/query/predicate_map.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+    using boost::scoped_ptr;
+    using mongo::BSONObj;
+    using mongo::fromjson;
+    using mongo::IndexTag;
+    using mongo::MatchExpression;
+    using mongo::MatchExpressionParser;
+    using mongo::PlanEnumerator;
+    using mongo::PredicateInfo;
+    using mongo::PredicateMap;
+    using mongo::RelevantIndex;
+    using mongo::StatusWithMatchExpression;
+    using std::vector;
+
+    /**
+     * XXX Test plan
+     *
+     * We'd like to test how the enumerator behaves when it picks one index at a time. We'll
+     * start the progression of tests going over increasingly complex queries in which that
+     * index can apply (sometimes more than onece).  We check whether the enumerator produces
+     * as many plans as we expected and whether the annotations (IndexTag's) were done
+     * correctly.
+     *
+     * Tricky part here is how to make this test useful in the long term. It is likely that
+     * we'll change the order in which plans are produced (e.g., try to get to the good
+     * plans faster) and we wouldn't like to destabilize the tests in here as we do so.
+     *
+     * XXX
+     */
+
+    TEST(SingleIndex, OnePredicate) {
+        BSONObj filter = fromjson("{a:99}");
+        StatusWithMatchExpression swme = MatchExpressionParser::parse(filter);
+        ASSERT_TRUE(swme.isOK());
+        MatchExpression* root = swme.getValue();
+
+        // Build a predicate map where an index {a:1} is relevant for the node 'a' EQ 99.
+        vector<BSONObj> indexKeyPatterns;
+        indexKeyPatterns.push_back(fromjson("{a:1}"));
+        scoped_ptr<PredicateMap> pm (new PredicateMap);
+        RelevantIndex ri(0, RelevantIndex::FIRST);
+        PredicateInfo pred(root);
+        pm->insert(std::make_pair("a", pred));
+
+        // Check that the enumerator takes a single predicate predicate map.
+        PlanEnumerator enumerator(root, pm.get(), &indexKeyPatterns);
+        ASSERT_OK(enumerator.init());
+
+        // The only possible plan is one where the relevant index is used to the equality node.
+        MatchExpression* annotated;
+        ASSERT_TRUE(enumerator.getNext(&annotated));
+        IndexTag* indexTag = static_cast<IndexTag*>(annotated->getTag());
+        ASSERT_NOT_EQUALS(indexTag, static_cast<IndexTag*>(NULL));
+        ASSERT_EQUALS(indexTag->index, 0U);
+        delete annotated;
+
+        // There's no other possible plan.
+        ASSERT_FALSE(enumerator.getNext(&annotated));
+    }
+
+} // unnamed namespace
diff --git a/src/mongo/db/query/predicate_map.h b/src/mongo/db/query/predicate_map.h
new file mode 100644
index 00000000000..99094d8d5f9
--- /dev/null
+++ b/src/mongo/db/query/predicate_map.h
@@ -0,0 +1,77 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include <set>
+#include <vector>
+
+#include "mongo/db/matcher/expression.h"
+
+namespace mongo {
+
+    /**
+     * Describes an index that could be used to answer a predicate.
+     */
+    struct RelevantIndex {
+
+        enum Relevance {
+            // Is the index prefixed by the predicate's field?  If so it can be used.
+            FIRST,
+
+            // Is the predicate's field in the index but not as a prefix?  If so, the index might be
+            // able to be used, if there is another predicate that prefixes the index.
+            NOT_FIRST,
+        };
+
+        RelevantIndex(int i, Relevance r) : index(i), relevance(r) { }
+
+        // To allow insertion into a set and sorting by something.
+        bool operator<(const RelevantIndex& other) const {
+            // We're only ever comparing these inside of a predicate.  A predicate should only be
+            // tagged for an index once.  This of course assumes that values are only indexed once
+            // in an index.
+            verify(other.index != index);
+            return index < other.index;
+        }
+
+        // What index is relevant?
+        int index;
+
+        // How useful is it?
+        Relevance relevance;
+    };
+
+    /**
+     * Caches information about the predicates we're trying to plan for.
+     */
+    struct PredicateInfo {
+
+        PredicateInfo(MatchExpression* node) {
+            nodes.push_back(node);
+        }
+
+        // Any relevant indices.  Ordered by index no.
+        set<RelevantIndex> relevant;
+
+        // Which nodes is this expression 'path matchType *' found in?  Not owned here.
+        vector<MatchExpression*> nodes;
+    };
+
+    // This is a multimap because the same field name can easily appear more than once in a query.
+    typedef map<string, PredicateInfo> PredicateMap;
+
+} // namespace mongo
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 73eb55db257..4d5eac4ab53 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -28,72 +28,41 @@
 
 #include "mongo/db/query/query_planner.h"
 
+#include <map>
+#include <set>
+#include <stack>
+#include <vector>
+
 // For QueryOption_foobar
 #include "mongo/client/dbclientinterface.h"
 #include "mongo/db/matcher/expression_array.h"
 #include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/index_bounds_builder.h"
+#include "mongo/db/query/index_tag.h"
+#include "mongo/db/query/plan_enumerator.h"
+#include "mongo/db/query/predicate_map.h"
 #include "mongo/db/query/query_solution.h"
 
 namespace mongo {
 
     /**
-     * Describes an index that could be used to answer a predicate.
-     */
-    struct RelevantIndex {
-        enum Relevance {
-            // Is the index prefixed by the predicate's field?  If so it can be used.
-            FIRST,
-
-            // Is the predicate's field in the index but not as a prefix?  If so, the index might be
-            // able to be used, if there is another predicate that prefixes the index.
-            NOT_FIRST,
-        };
-
-        RelevantIndex(int i, Relevance r) : index(i), relevance(r) { }
-
-        // What index is relevant?
-        int index;
-
-        // How useful is it?
-        Relevance relevance;
-
-        // To allow insertion into a set and sorting by something.
-        bool operator<(const RelevantIndex& other) const {
-            // We're only ever comparing these inside of a predicate.  A predicate should only be
-            // tagged for an index once.  This of course assumes that values are only indexed once
-            // in an index.
-            verify(other.index != index);
-            return index < other.index;
-        }
-    };
-
-    /**
-     * Caches information about the predicates we're trying to plan for.
-     */
-    struct PredicateInfo {
-        PredicateInfo(MatchExpression::MatchType t) : type(t) { }
-
-        // The type of the predicate.  See db/matcher/expression.h
-        MatchExpression::MatchType type;
-
-        // Any relevant indices.  Ordered by index no.
-        set<RelevantIndex> relevant;
-    };
-
-    // This is a multimap because the same field name can easily appear more than once in a query.
-    typedef multimap<string, PredicateInfo> PredicateMap;
-
-    /**
      * Scan the parse tree, adding all predicates to the provided map.
      */
-    void makePredicateMap(const MatchExpression* node, PredicateMap* out) {
+    void makePredicateMap(MatchExpression* node, PredicateMap* out) {
         StringData path = node->path();
 
+        // If we've seen this path before, link 'node' into that bunch.
+        // Otherwise, create a new entry <path, node> in the predicate map.
         if (!path.empty()) {
-            // XXX: make sure the (path, pred) pair isn't in there already?
-            out->insert(std::make_pair(path.toString(), PredicateInfo(node->matchType())));
+            PredicateMap::iterator it = out->lower_bound(path.toString());
+            if (it != out->end()) {
+                vector<MatchExpression*>& nodes = it->second.nodes;
+                nodes.push_back(node);
+            }
+            else {
+                out->insert(std::make_pair(path.toString(), node));
+            }
         }
 
         // XXX XXX XXX XXX
@@ -150,8 +119,15 @@ namespace mongo {
     }
 
     bool hasPredicate(const PredicateMap& pm, MatchExpression::MatchType type) {
-        for (PredicateMap::const_iterator i = pm.begin(); i != pm.end(); ++i) {
-            if (i->second.type == type) { return true; }
+        for (PredicateMap::const_iterator itMap = pm.begin(); itMap != pm.end(); ++itMap) {
+            const vector<MatchExpression*>& nodes = itMap->second.nodes;
+            for (vector<MatchExpression*>::const_iterator itVec = nodes.begin();
+                 itVec != nodes.end();
+                 ++itVec) {
+                if ((*itVec)->matchType() == type) {
+                    return true;
+                }
+            }
         }
         return false;
     }
@@ -181,147 +157,98 @@ namespace mongo {
         return soln.release();
     }
 
-    /**
-     * Provides elements from the power set of possible indices to use.  Uses the available
-     * predicate information to make better decisions about what indices are best.
-     *
-     * TODO: Use stats about indices.
-     * TODO: Use predicate information.
-     */
-    class PlanEnumerator {
-    public:
-        class OutputTag : public MatchExpression::TagData {
-        public:
-            OutputTag(size_t i) : index(i) { }
-            virtual ~OutputTag() { }
-            virtual void debugString(StringBuilder* builder) const {
-                *builder << " || Selected Index #" << index;
-            }
-            // What index should we try to use for this leaf?
-            size_t index;
-        };
-
-        /**
-         * Internal tag used to explore what indices to use for a leaf node.
-         */
-        class EnumeratorTag : public MatchExpression::TagData {
-        public:
-            EnumeratorTag(const PredicateInfo* p) : pred(p), nextIndexToUse(0) { }
-
-            virtual ~EnumeratorTag() { }
-
-            virtual void debugString(StringBuilder* builder) const {
-                *builder << " || Relevant Indices:";
-
-                for (set<RelevantIndex>::const_iterator it = pred->relevant.begin();
-                     it != pred->relevant.end(); ++it) {
-
-                    *builder << " #" << it->index << " ";
-                    if (RelevantIndex::FIRST == it->relevance) {
-                        *builder << "[prefix]";
-                    }
-                    else {
-                        verify(RelevantIndex::NOT_FIRST == it->relevance);
-                        *builder << "[not-prefix]";
-                    }
-                }
-            }
-
-            // Not owned here.
-            const PredicateInfo* pred;
-            size_t nextIndexToUse;
-        };
-
-        // TODO: This is inefficient.  We could create the tagged tree as part of the PredicateMap
-        // construction.
-        void tag(MatchExpression* node) {
-            StringData path = node->path();
+    // TODO: Document when this settles
+    struct FilterInfo {
+        MatchExpression* filterNode;
+        size_t currChild;
+        FilterInfo(MatchExpression* f, int c) : filterNode(f), currChild(c) {}
+    };
 
-            if (!path.empty()) {
+    // TODO: Document when this settles
+    QuerySolution* makeIndexedPath(const CanonicalQuery& query,
+                                   const vector<BSONObj>& indexKeyPatterns,
+                                   MatchExpression* filter) {
 
-                for (PredicateMap::const_iterator it = _pm.find(path.toString()); _pm.end() != it;
-                     ++it) {
+        auto_ptr<QuerySolution> soln(new QuerySolution());
 
-                    if (it->second.type == node->matchType()) {
-                        EnumeratorTag* td = new EnumeratorTag(&it->second);
-                        node->setTag(td);
-                        _taggedLeaves.push_back(node);
-                        break;
-                    }
+        // We'll build a tree of solutions nodes as we traverse the filter. For
+        // now, we're not generating multi-index solutions, so we can hold on to a
+        // single node here.
+        IndexScanNode* isn = new IndexScanNode();
+
+        // We'll do a post order traversal of the filter, which is a n-ary tree. We descend the
+        // tree keeping track of which child is next to visit.
+        std::stack<FilterInfo> filterNodes;
+        FilterInfo rootFilter(filter, 0);
+        filterNodes.push(rootFilter);
+
+        while (!filterNodes.empty()) {
+
+            FilterInfo& fi = filterNodes.top();
+            MatchExpression* filterNode = fi.filterNode;
+            size_t& currChild = fi.currChild;
+            if (filterNode->numChildren() == currChild) {
+
+                // Visit leaf or node. If we find an index tag, we compute the bounds and
+                // fill up the index information on the current IXScan node.
+                IndexTag* indexTag = static_cast<IndexTag*>(filterNode->getTag());
+                bool exactBounds = false;
+                if (indexTag != NULL) {
+
+                    isn->indexKeyPattern = indexKeyPatterns[indexTag->index];
+
+                    // We assume that this is in the same direction of the index. We may later
+                    // change our minds if the query requires sorting in the opposite
+                    // direction. But, right now, the direction of traversal is not in
+                    // question.
+                    isn->direction = 1;
+
+                    // TODO: handle combining oils if this is not the first predicate we'eve
+                    // seen for this field.
+                    // TODO: handle compound indexes
+                    OrderedIntervalList oil(filterNode->path().toString());
+                    IndexBoundsBuilder::translate(
+                        static_cast<LeafMatchExpression*>(filterNode),
+                        isn->indexKeyPattern.firstElement(),
+                        &oil,
+                        &exactBounds);
+
+                    // TODO: union or intersect oils
+                    // It can be the case that this is not the first "oil" for a given
+                    // field. That is, there are several predicates agains a same field which
+                    // happens to have a useful index. In that case, we may need to combine
+                    // oils in a "larger" bound to accomodate all the predicates.
+                    vector<OrderedIntervalList>& fields = isn->bounds.fields;
+                    fields.push_back(oil);
                 }
-            }
 
-            // XXX XXX XXX XXX
-            // XXX Do we do this if the node is logical, or if it's array, or both?
-            // XXX XXX XXX XXX
-            for (size_t i = 0; i < node->numChildren(); ++i) {
-                tag(const_cast<MatchExpression*>(node->getChild(i)));
+                // TODO: possibly trim redundant MatchExpressions nodes
+                // It can be the case that the bounds for a query will only return exact
+                // results (as opposed to just limiting the index range in which the results
+                // lie). When results are exact, we don't need to retest them and thus such
+                // nodes can be eliminated from the filter.  Note that some non-leaf nodes
+                // (e.g. and's, or's) may be left with single children and can therefore be
+                // eliminated as well.
+                isn->filter = filterNode;
+
+                // TODO: Multiple IXScans nodes in a solution
+                // If this is not the first index tag found, then we add another IXScan node to
+                // the queryNodes stack and start using $or and $ands in the filter expession
+                // to tie the IXScan together into a tree of QuerySolutionNode's.
+
+                filterNodes.pop();
             }
-        }
-
-        vector<MatchExpression*> _taggedLeaves;
-
-        /**
-         * Does not take ownership of any arguments.  They must outlive any calls to getNext(...).
-         */
-        PlanEnumerator(const CanonicalQuery* cq, const PredicateMap* pm,
-                       const vector<BSONObj>* indices)
-            : _cq(*cq), _pm(*pm), _indices(*indices) {
-
-            // Copy the query tree.
-            // TODO: have a MatchExpression::copy function(?)
-            StatusWithMatchExpression swme = MatchExpressionParser::parse(cq->getQueryObj());
-            verify(swme.isOK());
-            _taggedTree.reset(swme.getValue());
-
-            // Walk the query tree and tag with possible indices
-            tag(_taggedTree.get());
-
-            for (size_t i = 0; i < indices->size(); ++i) {
-                cout << "Index #" << i << ": " << (*indices)[i].toString() << endl;
+            else {
+                // Continue the traversal.
+                FilterInfo fiChild(filterNode->getChild(currChild), 0);
+                filterNodes.push(fiChild);
+                currChild++;
             }
-
-            cout << "Tagged tree: " << _taggedTree->toString() << endl;
-        }
-
-        /**
-         * Outputs a possible plan.  Leaves in the plan are tagged with an index to use.
-         * Returns true if a plan was outputted, false if no more plans will be outputted.
-         *
-         * 'tree' is set to point to the query tree.  A QuerySolution is built from this tree.
-         * Caller owns the pointer.  Note that 'tree' itself points into data owned by the provided
-         * CanonicalQuery.
-         *
-         * Nodes in 'tree' are tagged with indices that should be used to answer the tagged nodes.
-         * Only nodes that have a field name (isLogical() == false) will be tagged.
-         */
-        bool getNext(MatchExpression** tree) {
-            // TODO: ALBERTO
-
-            // Clone tree
-            // MatchExpression* ret = _taggedTree->shallowClone();
-
-            // Walk over cloned tree and tagged tree.  Select indices out of tagged tree and mark
-            // the cloned tree.
-
-            // *tree = ret;
-            // return true;
-
-            return false;
         }
 
-    private:
-        // Not owned by us.
-        const CanonicalQuery& _cq;
-
-        // Not owned by us.
-        const PredicateMap& _pm;
-
-        // Not owned by us.
-        const vector<BSONObj>& _indices;
-
-        scoped_ptr<MatchExpression> _taggedTree;
-    };
+        soln->root.reset(isn);
+        return soln.release();
+    }
 
     // static
     void QueryPlanner::plan(const CanonicalQuery& query, const vector<BSONObj>& indexKeyPatterns,
@@ -367,8 +294,11 @@ namespace mongo {
         vector<BSONObj> relevantIndices;
         findRelevantIndices(predicates, indexKeyPatterns, &relevantIndices);
 
-        // No indices, no work to do.
-        if (0 == relevantIndices.size()) { return; }
+        // No indices, no work to do other than emitting the collection scan plan.
+        if (0 == relevantIndices.size()) {
+            out->push_back(makeCollectionScan(query, false));
+            return;
+        }
 
         // Figure out how useful each index is to each predicate.
         rateIndices(relevantIndices, &predicates);
@@ -377,22 +307,24 @@ namespace mongo {
         // Planner Section 2: Use predicate/index data to output sets of indices that we can use.
         //
 
-        PlanEnumerator isp(&query, &predicates, &relevantIndices);
+        PlanEnumerator isp(query.root(), &predicates, &relevantIndices);
+        isp.init();
 
         MatchExpression* rawTree;
         while (isp.getNext(&rawTree)) {
-            QuerySolutionNode* solutionRoot = NULL;
 
             //
             // Planner Section 3: Logical Rewrite.  Use the index selection and the tree structure
             // to try to rewrite the tree.  TODO: Do this for real.  We treat the tree as static.
             //
 
+            QuerySolution* soln = makeIndexedPath(query, indexKeyPatterns, rawTree);
 
             //
             // Planner Section 4: Covering.  If we're projecting, See if we get any covering from
             // this plan.  If not, add a fetch.
             //
+
             if (!query.getParsed().getProj().isEmpty()) {
                 warning() << "Can't deal with proj yet" << endl;
             }
@@ -401,9 +333,10 @@ namespace mongo {
             }
 
             //
-            // Planner Section 5: Sort.  If we're sorting, see if the plan gives us a sort for free.
-            // If not, add a sort.
+            // Planner Section 5: Sort.  If we're sorting, see if the plan gives us a sort for
+            // free.  If not, add a sort.
             //
+
             if (!query.getParsed().getSort().isEmpty()) {
             }
             else {
@@ -416,10 +349,8 @@ namespace mongo {
             // TODO: Validate.
             //
 
-            if (NULL != solutionRoot) {
-                QuerySolution* qs = new QuerySolution();
-                qs->root.reset(solutionRoot);
-                out->push_back(qs);
+            if (NULL != soln) {
+                out->push_back(soln);
             }
         }
 
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 4d083ea893c..3f19ce812b2 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -30,11 +30,11 @@
  * This file contains tests for mongo/db/query/query_planner.cpp
  */
 
+#include "mongo/db/jsobj.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/query/query_planner.h"
 #include "mongo/db/query/query_solution.h"
-#include "mongo/db/matcher/expression_parser.h"
-#include "mongo/db/json.h"
-#include "mongo/db/jsobj.h"
 #include "mongo/unittest/unittest.h"
 #include "mongo/util/assert_util.h"
 
@@ -42,225 +42,266 @@ using namespace mongo;
 
 namespace {
 
-    // TODO: ALBERTO
-    bool albertoWasHere = false;
-
     static const char* ns = "somebogusns";
 
-    //
-    // Equality
-    //
+    class SingleIndexTest : public mongo::unittest::Test {
+    protected:
+        void tearDown() {
+            delete cq;
 
-    // Test the most basic index-using functionality.
-    TEST(QueryPlannerTest, EqualityIndexScan) {
-        // Get the canonical query.
-        BSONObj queryObj = BSON("x" << 5);
-        CanonicalQuery* cq;
-        ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK());
-
-        // This is our index.  It's the simplest index we can use.
-        vector<BSONObj> indices;
-        indices.push_back(BSON("x" << 1));
-
-        // If we can't get this right...
-        vector<QuerySolution*> solns;
-        QueryPlanner::plan(*cq, indices, &solns);
-
-        if (albertoWasHere) {
-            ASSERT_EQUALS(size_t(2), solns.size());
-
-            IndexScanNode* ixnode;
-            if (STAGE_IXSCAN == solns[0]->root->getType()) {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[0]->root.get());
+            for (vector<QuerySolution*>::iterator it = solns.begin(); it != solns.end(); ++it) {
+                delete *it;
             }
-            else {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[0]->root->getType());
-                ASSERT_EQUALS(STAGE_IXSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[1]->root.get());
-            }
-
-            cout << ixnode->bounds.toString() << endl;
-            // TODO: Check bounds.
         }
-    }
 
-    TEST(QueryPlannerTest, EqualityIndexScanWithTrailingFields) {
-        BSONObj queryObj = BSON("x" << 5);
+        //
+        // Build up test.
+        //
 
-        CanonicalQuery* cq;
-        ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK());
+        void setIndex(BSONObj keyPattern) {
+            keyPatterns.push_back(keyPattern);
+        }
 
-        vector<BSONObj> indices;
-        indices.push_back(BSON("x" << 1 << "y" << 1));
+        //
+        // Execute planner.
+        //
 
-        vector<QuerySolution*> solns;
-        QueryPlanner::plan(*cq, indices, &solns);
+        void runQuery(BSONObj query) {
+            queryObj = query.getOwned();
+            ASSERT_OK(CanonicalQuery::canonicalize(ns, queryObj, &cq));
+            QueryPlanner::plan(*cq, keyPatterns, &solns);
+            ASSERT_GREATER_THAN(solns.size(), 0U);;
+        }
 
-        if (albertoWasHere) {
-            // Available index is prefixed by our equality, use it.
-            ASSERT_EQUALS(size_t(2), solns.size());
+        //
+        // Introspect solutions.
+        //
 
-            IndexScanNode* ixnode;
-            if (STAGE_IXSCAN == solns[0]->root->getType()) {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[0]->root.get());
-            }
-            else {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[0]->root->getType());
-                ASSERT_EQUALS(STAGE_IXSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[1]->root.get());
-            }
+        size_t getNumSolutions() const {
+            return solns.size();
+        }
 
-            cout << ixnode->bounds.toString() << endl;
-            // TODO: Check bounds.
+        void getPlanByType(StageType stageType, QuerySolution** soln) const {
+            size_t found = 0;
+            for (vector<QuerySolution*>::const_iterator it = solns.begin();
+                 it != solns.end();
+                 ++it) {
+                if ((*it)->root->getType() == stageType) {
+                    *soln = *it;
+                    found++;
+                }
+            }
+            ASSERT_EQUALS(found, 1U);
         }
-    }
 
-    // TODO: Check compound indices.
-    // TODO: Check diff. index directions for ranges below.
+        // { 'field': [ [min, max, startInclusive, endInclusive], ... ], 'field': ... }
+        void boundsEqual(BSONObj boundsObj, IndexBounds bounds) const {
+            ASSERT_EQUALS(static_cast<int>(bounds.size()), boundsObj.nFields());
 
-    //
-    // <
-    //
+            size_t i = 0;
+            BSONObjIterator iti(boundsObj);
+            while (iti.more()) {
 
-    TEST(QueryPlannerTest, LessThan) {
-        BSONObj queryObj = BSON("x" << BSON("$lt" << 5));
+                BSONElement field = iti.next();
+                ASSERT_EQUALS(field.type(), Array);
+                ASSERT_EQUALS(static_cast<int>(bounds.getNumIntervals(i)),
+                              field.embeddedObject().nFields());
 
-        CanonicalQuery* cq;
-        ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK());
+                size_t j = 0;
+                BSONObjIterator itj(field.embeddedObject());
+                while (itj.more()) {
 
-        vector<BSONObj> indices;
-        indices.push_back(BSON("x" << 1));
+                    BSONElement intervalElem = itj.next();
+                    ASSERT_EQUALS(intervalElem.type(), Array);
+                    BSONObj intervalObj = intervalElem.embeddedObject();
+                    ASSERT_EQUALS(intervalObj.nFields(), 4);
 
-        vector<QuerySolution*> solns;
-        QueryPlanner::plan(*cq, indices, &solns);
+                    Interval interval(intervalObj, intervalObj[2].Bool(), intervalObj[3].Bool());
+                    ASSERT_EQUALS(interval.compare(bounds.getInterval(i,j)),
+                                  Interval::INTERVAL_EQUALS);
 
-        if (albertoWasHere) {
-            // Available index is prefixed by our equality, use it.
-            ASSERT_EQUALS(size_t(2), solns.size());
+                    j++;
+                }
 
-            IndexScanNode* ixnode;
-            if (STAGE_IXSCAN == solns[0]->root->getType()) {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[0]->root.get());
+                i++;
             }
-            else {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[0]->root->getType());
-                ASSERT_EQUALS(STAGE_IXSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[1]->root.get());
-            }
-
-            cout << ixnode->bounds.toString() << endl;
-            // TODO: Check bounds.
         }
-    }
+
+        BSONObj queryObj;
+        CanonicalQuery* cq;
+        vector<BSONObj> keyPatterns;
+        vector<QuerySolution*> solns;
+    };
 
     //
-    // <=
+    // Equality
     //
 
-    TEST(QueryPlannerTest, LessThanEqual) {
-        BSONObj queryObj = BSON("x" << BSON("$lte" << 5));
+    TEST_F(SingleIndexTest, EqualityIndexScan) {
+        setIndex(BSON("x" << 1));
+        runQuery(BSON("x" << 5));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
 
-        CanonicalQuery* cq;
-        ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK());
+        QuerySolution* collScanSolution;
+        getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+        // TODO check filter
 
-        vector<BSONObj> indices;
-        indices.push_back(BSON("x" << 1));
+        QuerySolution* indexedSolution;
+        getPlanByType(STAGE_IXSCAN, &indexedSolution);
+        IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+        boundsEqual(fromjson("{x: [ [5, 5, true, true] ] }"), ixNode->bounds);
+        // TODO check filter
+    }
 
-        vector<QuerySolution*> solns;
-        QueryPlanner::plan(*cq, indices, &solns);
+    TEST_F(SingleIndexTest, EqualityIndexScanWithTrailingFields) {
+        setIndex(BSON("x" << 1 << "y" << 1));
+        runQuery(BSON("x" << 5));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
 
-        if (albertoWasHere) {
-            // Available index is prefixed by our equality, use it.
-            ASSERT_EQUALS(size_t(2), solns.size());
+        QuerySolution* collScanSolution;
+        getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+        // TODO check filter
 
-            IndexScanNode* ixnode;
-            if (STAGE_IXSCAN == solns[0]->root->getType()) {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[0]->root.get());
-            }
-            else {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[0]->root->getType());
-                ASSERT_EQUALS(STAGE_IXSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[1]->root.get());
-            }
-            cout << ixnode->bounds.toString() << endl;
-            // TODO: Check bounds.
-        }
+        QuerySolution* indexedSolution;
+        getPlanByType(STAGE_IXSCAN, &indexedSolution);
+        IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+        boundsEqual(fromjson("{x: [ [5, 5, true, true] ] }"), ixNode->bounds);
+        // TODO check filter
     }
 
+    // TODO: Check compound indices.
+    // TODO: Check diff. index directions for ranges below.
+
     //
-    // >
+    // <
     //
 
-    TEST(QueryPlannerTest, GreaterThan) {
-        BSONObj queryObj = BSON("x" << BSON("$gt" << 5));
-
-        CanonicalQuery* cq;
-        ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK());
-
-        vector<BSONObj> indices;
-        indices.push_back(BSON("x" << 1));
+    TEST_F(SingleIndexTest, LessThan) {
+        setIndex(BSON("x" << 1));
+        runQuery(BSON("x" << BSON("$lt" << 5)));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+
+        QuerySolution* collScanSolution;
+        getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+        // TODO check filter
+
+        QuerySolution* indexedSolution;
+        getPlanByType(STAGE_IXSCAN, &indexedSolution);
+        IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+        BSONObj bounds = BSON("x" << BSON_ARRAY(BSON_ARRAY(MINKEY << 5 << true << false)));
+        boundsEqual(bounds, ixNode->bounds);
+        // todo check filter
+    }
 
-        vector<QuerySolution*> solns;
-        QueryPlanner::plan(*cq, indices, &solns);
+    //
+    // <=
+    //
 
-        if (albertoWasHere) {
-            // Available index is prefixed by our equality, use it.
-            ASSERT_EQUALS(size_t(2), solns.size());
+    TEST_F(SingleIndexTest, LessThanEqual) {
+        setIndex(BSON("x" << 1));
+        runQuery(BSON("x" << BSON("$lte" << 5)));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+
+        QuerySolution* collScanSolution;
+        getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+        // TODO check filter
+
+        QuerySolution* indexedSolution;
+        getPlanByType(STAGE_IXSCAN, &indexedSolution);
+        IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+        BSONObj bounds = BSON("x" << BSON_ARRAY(BSON_ARRAY(MINKEY << 5 << true << true)));
+        boundsEqual(bounds, ixNode->bounds);
+        // todo check filter
+    }
 
-            IndexScanNode* ixnode;
-            if (STAGE_IXSCAN == solns[0]->root->getType()) {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[0]->root.get());
-            }
-            else {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[0]->root->getType());
-                ASSERT_EQUALS(STAGE_IXSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[1]->root.get());
-            }
+    //
+    // >
+    //
 
-            cout << ixnode->bounds.toString() << endl;
-            // TODO: Check bounds.
-        }
+    TEST_F(SingleIndexTest, GreaterThan) {
+        setIndex(BSON("x" << 1));
+        runQuery(BSON("x" << BSON("$gt" << 5)));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+
+        QuerySolution* collScanSolution;
+        getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+        // TODO check filter
+
+        QuerySolution* indexedSolution;
+        getPlanByType(STAGE_IXSCAN, &indexedSolution);
+        IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+        BSONObj bounds = BSON("x" << BSON_ARRAY(BSON_ARRAY(5 << MAXKEY << false << true)));
+        boundsEqual(bounds, ixNode->bounds);
+        // todo check filter
     }
 
     //
     // >=
     //
 
-    TEST(QueryPlannerTest, GreaterThanEqual) {
-        BSONObj queryObj = BSON("x" << BSON("$gte" << 5));
-
-        CanonicalQuery* cq;
-        ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK());
-
-        vector<BSONObj> indices;
-        indices.push_back(BSON("x" << 1));
-
-        vector<QuerySolution*> solns;
-        QueryPlanner::plan(*cq, indices, &solns);
-
-        if (albertoWasHere) {
-            // Available index is prefixed by our equality, use it.
-            ASSERT_EQUALS(size_t(2), solns.size());
+    TEST_F(SingleIndexTest, GreaterThanEqual) {
+        setIndex(BSON("x" << 1));
+        runQuery(BSON("x" << BSON("$gte" << 5)));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+
+        QuerySolution* collScanSolution;
+        getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+        // TODO check filter
+
+        QuerySolution* indexedSolution;
+        getPlanByType(STAGE_IXSCAN, &indexedSolution);
+        IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+        BSONObj bounds = BSON("x" << BSON_ARRAY(BSON_ARRAY(5 << MAXKEY << true << true)));
+        boundsEqual(bounds, ixNode->bounds);
+        // todo check filter
+    }
 
-            IndexScanNode* ixnode;
-            if (STAGE_IXSCAN == solns[0]->root->getType()) {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[0]->root.get());
-            }
-            else {
-                ASSERT_EQUALS(STAGE_COLLSCAN, solns[0]->root->getType());
-                ASSERT_EQUALS(STAGE_IXSCAN, solns[1]->root->getType());
-                ixnode = static_cast<IndexScanNode*>(solns[1]->root.get());
-            }
+    //
+    // tree operations
+    //
 
-            cout << ixnode->bounds.toString() << endl;
-            // TODO: Check bounds.
-        }
-    }
+    // STOPPED HERE - need to hook up machinery for multiple indexed predicates
+    //                first test is segfaulting
+    //                second is not working (until the machinery is in place)
+    //
+    // TEST_F(SingleIndexTest, TwoPredicatesAnding) {
+    //     setIndex(BSON("x" << 1));
+    //     runQuery(fromjson("{$and: [ {$gt: 1}, {$lt: 3} ] }"));
+    //     ASSERT_EQUALS(getNumSolutions(), 2U);
+
+    //     QuerySolution* collScanSolution;
+    //     getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+    //     // TODO check filter
+
+    //     QuerySolution* indexedSolution;
+    //     getPlanByType(STAGE_IXSCAN, &indexedSolution);
+    //     IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+    //     boundsEqual(fromjson("{x: [ [1, 3, false, false] ] }"), ixNode->bounds);
+    //     // TODO check filter
+    // }
+
+    // TEST_F(SingleIndexTest, TwoPredicatesOring) {
+    //     setIndex(BSON("x" << 1));
+    //     runQuery(fromjson("{$or: [ {a: 1}, {a: 2} ] }"));
+    //     ASSERT_EQUALS(getNumSolutions(), 2U);
+
+    //     QuerySolution* collScanSolution;
+    //     getPlanByType(STAGE_COLLSCAN, &collScanSolution);
+    //     // TODO check filter
+
+    //     BSONObj boundsObj =
+    //         fromjson("{x:"
+    //                  "   ["
+    //                  "     [1, 1, true, true],"
+    //                  "     [2, 2, true, true],"
+    //                  "   ]"
+    //                  "}");
+
+    //     QuerySolution* indexedSolution;
+    //     getPlanByType(STAGE_IXSCAN, &indexedSolution);
+    //     IndexScanNode* ixNode = static_cast<IndexScanNode*>(indexedSolution->root.get());
+    //     boundsEqual(boundsObj, ixNode->bounds);
+    //     // TODO check filter
+    //}
 
 }  // namespace