diff options
Diffstat (limited to 'src')
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 |