diff options
| -rw-r--r-- | src/mongo/db/pipeline/expression.cpp | 183 | ||||
| -rw-r--r-- | src/mongo/db/pipeline/expression.h | 40 | ||||
| -rw-r--r-- | src/mongo/dbtests/expressiontests.cpp | 51 |
3 files changed, 99 insertions, 175 deletions
diff --git a/src/mongo/db/pipeline/expression.cpp b/src/mongo/db/pipeline/expression.cpp index f5b98e6853d..a004fdedcb1 100644 --- a/src/mongo/db/pipeline/expression.cpp +++ b/src/mongo/db/pipeline/expression.cpp @@ -234,10 +234,14 @@ namespace mongo { return pExpression; } +namespace { + typedef intrusive_ptr<ExpressionNary> (*ExpressionFactory)(void); struct OpDesc { + intrusive_ptr<ExpressionNary> create() const { return pFactory(); } + const char *pName; - intrusive_ptr<ExpressionNary> (*pFactory)(void); + ExpressionFactory pFactory; unsigned flag; static const unsigned FIXED_COUNT = 0x0001; @@ -303,6 +307,13 @@ namespace mongo { static const size_t NOp = sizeof(OpTable)/sizeof(OpTable[0]); + const OpDesc* lookupExpression(const char* name) { + OpDesc key; + key.pName = name; + return static_cast<const OpDesc *>(bsearch(&key, OpTable, NOp, sizeof(OpDesc), OpDescCmp)); + } +} + intrusive_ptr<Expression> Expression::parseExpression(BSONElement exprElement) { /* look for the specified operator */ const char* opName = exprElement.fieldName(); @@ -317,16 +328,12 @@ namespace mongo { return ExpressionMap::parse(exprElement); } - OpDesc key; - key.pName = opName; - const OpDesc *pOp = (const OpDesc *)bsearch( - &key, OpTable, NOp, sizeof(OpDesc), OpDescCmp); - - uassert(15999, str::stream() << "invalid operator '" << - opName << "'", pOp); + const OpDesc* pOp = lookupExpression(opName); + uassert(15999, str::stream() << "invalid operator '" << opName << "'", + pOp); /* make the expression node */ - intrusive_ptr<ExpressionNary> pExpression((*pOp->pFactory)()); + intrusive_ptr<ExpressionNary> pExpression = pOp->create(); /* add the operands to the expression node */ BSONType elementType = exprElement.type(); @@ -467,10 +474,6 @@ namespace mongo { return "$add"; } - intrusive_ptr<ExpressionNary> (*ExpressionAdd::getFactory() const)() { - return ExpressionAdd::create; - } - /* ------------------------- ExpressionAll -------------------------- */ intrusive_ptr<ExpressionNary> ExpressionAll::create() { @@ -586,9 +589,6 @@ namespace mongo { verify(false && "unimplemented"); } - intrusive_ptr<ExpressionNary> (*ExpressionAnd::getFactory() const)() { - return ExpressionAnd::create; - } /* ------------------------- ExpressionAny -------------------------- */ @@ -2050,10 +2050,6 @@ namespace mongo { return "$multiply"; } - intrusive_ptr<ExpressionNary> (*ExpressionMultiply::getFactory() const)() { - return ExpressionMultiply::create; - } - /* ------------------------- ExpressionHour ----------------------------- */ intrusive_ptr<ExpressionNary> ExpressionHour::create() { @@ -2094,9 +2090,10 @@ namespace mongo { /* ------------------------ ExpressionNary ----------------------------- */ intrusive_ptr<Expression> ExpressionNary::optimize() { - unsigned constCount = 0; // count of constant operands - unsigned stringCount = 0; // count of constant string operands const size_t n = vpOperand.size(); + + // optimize sub-expressions and count constants + unsigned constCount = 0; for(size_t i = 0; i < n; ++i) { intrusive_ptr<Expression> pNew(vpOperand[i]->optimize()); @@ -2104,12 +2101,8 @@ namespace mongo { vpOperand[i] = pNew; /* check to see if the result was a constant */ - const ExpressionConstant *pConst = - dynamic_cast<ExpressionConstant *>(pNew.get()); - if (pConst) { - ++constCount; - if (pConst->getValue().getType() == String) - ++stringCount; + if (dynamic_cast<ExpressionConstant *>(pNew.get())) { + constCount++; } } @@ -2127,100 +2120,58 @@ namespace mongo { } /* - If there are any strings, we can't re-arrange anything, so stop - now. - - LATER: we could concatenate adjacent strings as a special case. - */ - if (stringCount) - return intrusive_ptr<Expression>(this); - - /* - If there's no more than one constant, then we can't do any - constant folding, so don't bother going any further. - */ - if (constCount <= 1) - return intrusive_ptr<Expression>(this); - - /* If the operator isn't commutative or associative, there's nothing more we can do. We test that by seeing if we can get a factory; if we can, we can use it to construct a temporary expression which we'll evaluate to collapse as many constants as we can down to a single one. */ - intrusive_ptr<ExpressionNary> (*const pFactory)() = getFactory(); - if (!pFactory) - return intrusive_ptr<Expression>(this); - - /* - Create a new Expression that will be the replacement for this one. - We actually create two: one to hold constant expressions, and - one to hold non-constants. Once we've got these, we evaluate - the constant expression to produce a single value, as above. - We then add this operand to the end of the non-constant expression, - and return that. - */ - intrusive_ptr<ExpressionNary> pNew((*pFactory)()); - intrusive_ptr<ExpressionNary> pConst((*pFactory)()); - for(size_t i = 0; i < n; ++i) { - intrusive_ptr<Expression> pE(vpOperand[i]); - if (dynamic_cast<ExpressionConstant *>(pE.get())) - pConst->addOperand(pE); + if (!isAssociativeAndCommutative()) + return this; + + // Process vpOperand to split it into constant and nonconstant vectors. + // This can leave vpOperand in an invalid state that is cleaned up after the loop. + ExpressionVector constExprs; + ExpressionVector nonConstExprs; + for(size_t i = 0; i < vpOperand.size(); ++i) { // NOTE: vpOperand grows in loop + intrusive_ptr<Expression> expr = vpOperand[i]; + if (dynamic_cast<ExpressionConstant*>(expr.get())) { + constExprs.push_back(expr); + } else { - /* - If the child operand is the same type as this, then we can - extract its operands and inline them here because we already - know this is commutative and associative because it has a - factory. We can detect sameness of the child operator by - checking for equality of the factory - - Note we don't have to do this recursively, because we - called optimize() on all the children first thing in - this call to optimize(). - */ - ExpressionNary *pNary = - dynamic_cast<ExpressionNary *>(pE.get()); - if (!pNary) - pNew->addOperand(pE); + /* If the child operand is the same type as this, then we can + * extract its operands and inline them here because we know + * this is commutative and associative. We detect sameness of + * the child operator by checking for equality of the opNames + */ + ExpressionNary* nary = dynamic_cast<ExpressionNary*>(expr.get()); + if (!nary || !str::equals(nary->getOpName(), getOpName())) { + nonConstExprs.push_back(expr); + } else { - intrusive_ptr<ExpressionNary> (*const pChildFactory)() = - pNary->getFactory(); - if (pChildFactory != pFactory) - pNew->addOperand(pE); - else { - /* same factory, so flatten */ - size_t nChild = pNary->vpOperand.size(); - for(size_t iChild = 0; iChild < nChild; ++iChild) { - intrusive_ptr<Expression> pCE( - pNary->vpOperand[iChild]); - if (dynamic_cast<ExpressionConstant *>(pCE.get())) - pConst->addOperand(pCE); - else - pNew->addOperand(pCE); - } - } + // same expression, so flatten by adding to vpOperand which + // will be processed later in this loop. + vpOperand.insert(vpOperand.end(), + nary->vpOperand.begin(), + nary->vpOperand.end()); } } } - /* - If there was only one constant, add it to the end of the expression - operand vector. - */ - if (pConst->vpOperand.size() == 1) - pNew->addOperand(pConst->vpOperand[0]); - else if (pConst->vpOperand.size() > 1) { - /* - If there was more than one constant, collapse all the constants - together before adding the result to the end of the expression - operand vector. - */ - Value pResult(pConst->evaluateInternal(Variables())); - pNew->addOperand(ExpressionConstant::create(pResult)); + // collapse all constant expressions (if any) + Value constValue; + if (!constExprs.empty()) { + vpOperand = constExprs; + constValue = evaluateInternal(Variables()); } - return pNew; + // now set the final expression list with constant (if any) at the end + vpOperand = nonConstExprs; + if (!constExprs.empty()) { + vpOperand.push_back(ExpressionConstant::create(constValue)); + } + + return this; } void ExpressionNary::addDependencies(set<string>& deps, vector<string>* path) const { @@ -2234,10 +2185,6 @@ namespace mongo { vpOperand.push_back(pExpression); } - intrusive_ptr<ExpressionNary> (*ExpressionNary::getFactory() const)() { - return NULL; - } - Value ExpressionNary::serialize() const { const size_t nOperand = vpOperand.size(); vector<Value> array; @@ -2318,10 +2265,6 @@ namespace mongo { pBuilder->append("$or", opArray.done()); } - intrusive_ptr<ExpressionNary> (*ExpressionOr::getFactory() const)() { - return ExpressionOr::create; - } - intrusive_ptr<Expression> ExpressionOr::optimize() { /* optimize the disjunction as much as possible */ intrusive_ptr<Expression> pE(ExpressionNary::optimize()); @@ -2534,10 +2477,6 @@ namespace mongo { return "$setIntersection"; } - intrusive_ptr<ExpressionNary> (*ExpressionSetIntersection::getFactory() const)() { - return ExpressionSetIntersection::create; - } - /* ----------------------- ExpressionSetIsSubset ---------------------------- */ intrusive_ptr<ExpressionNary> ExpressionSetIsSubset::create() { @@ -2605,10 +2544,6 @@ namespace mongo { return "$setUnion"; } - intrusive_ptr<ExpressionNary> (*ExpressionSetUnion::getFactory() const)() { - return ExpressionSetUnion::create; - } - /* ----------------------- ExpressionStrcasecmp ---------------------------- */ intrusive_ptr<ExpressionNary> ExpressionStrcasecmp::create() { diff --git a/src/mongo/db/pipeline/expression.h b/src/mongo/db/pipeline/expression.h index 9b68c4a2ddf..b7b47fd4d4d 100644 --- a/src/mongo/db/pipeline/expression.h +++ b/src/mongo/db/pipeline/expression.h @@ -230,23 +230,8 @@ namespace mongo { */ virtual void addOperand(const intrusive_ptr<Expression> &pExpression); - /* - Return a factory function that will make Expression nodes of - the same type as this. This will be used to create constant - expressions for constant folding for optimize(). Only return - a factory function if this operator is both associative and - commutative. The default implementation returns NULL; optimize() - will recognize that and stop. - - Note that ExpressionNary::optimize() promises that if it uses this - to fold constants, then if optimize() returns an ExpressionNary, - any remaining constant will be the last one in vpOperand. Derived - classes may take advantage of this to do further optimizations in - their optimize(). - - @returns pointer to a factory function or NULL - */ - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)(); + // TODO split this into two functions + virtual bool isAssociativeAndCommutative() const { return false; } /* Get the name of the operator. @@ -270,10 +255,7 @@ namespace mongo { // virtuals from Expression virtual Value evaluateInternal(const Variables& vars) const; virtual const char *getOpName() const; - - // virtuals from ExpressionNary - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)(); - + virtual bool isAssociativeAndCommutative() const { return true; } /* Create an expression that finds the sum of n operands. @@ -305,9 +287,7 @@ namespace mongo { virtual Value evaluateInternal(const Variables& vars) const; virtual const char *getOpName() const; virtual void toMatcherBson(BSONObjBuilder *pBuilder) const; - - // virtuals from ExpressionNary - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)(); + virtual bool isAssociativeAndCommutative() const { return true; } /* Create an expression that finds the conjunction of n operands. @@ -752,9 +732,7 @@ namespace mongo { // virtuals from Expression virtual Value evaluateInternal(const Variables& vars) const; virtual const char *getOpName() const; - - // virtuals from ExpressionNary - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)(); + virtual bool isAssociativeAndCommutative() const { return true; } /* Create an expression that finds the product of n operands. @@ -929,9 +907,7 @@ namespace mongo { virtual Value evaluateInternal(const Variables& vars) const; virtual const char *getOpName() const; virtual void toMatcherBson(BSONObjBuilder *pBuilder) const; - - // virtuals from ExpressionNary - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)(); + virtual bool isAssociativeAndCommutative() const { return true; } /* Create an expression that finds the conjunction of n operands. @@ -998,7 +974,7 @@ namespace mongo { // virtuals from ExpressionNary virtual Value evaluateInternal(const Variables& vars) const; virtual const char *getOpName() const; - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)(); + virtual bool isAssociativeAndCommutative() const { return true; } static intrusive_ptr<ExpressionNary> create(); @@ -1029,7 +1005,7 @@ namespace mongo { // virtual intrusive_ptr<Expression> optimize(); virtual Value evaluateInternal(const Variables& vars) const; virtual const char *getOpName() const; - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)(); + virtual bool isAssociativeAndCommutative() const { return true; } static intrusive_ptr<ExpressionNary> create(); diff --git a/src/mongo/dbtests/expressiontests.cpp b/src/mongo/dbtests/expressiontests.cpp index 8a908572c81..0c40eb3f5a3 100644 --- a/src/mongo/dbtests/expressiontests.cpp +++ b/src/mongo/dbtests/expressiontests.cpp @@ -403,9 +403,16 @@ namespace ExpressionTests { BSONObj spec() { return BSON( "$and" << BSON_ARRAY( "$a" ) ); } }; - /** An expression beginning with a single constant is not optimized. SERVER-6192 */ - class ConstantNonConstant : public NoOptimizeBase { + /** An expression beginning with a single constant is optimized. */ + class ConstantNonConstantTrue : public OptimizeBase { BSONObj spec() { return BSON( "$and" << BSON_ARRAY( 1 << "$a" ) ); } + BSONObj expectedOptimized() { return BSON( "$and" << BSON_ARRAY( "$a" ) ); } + // note: using $and as serialization of ExpressionCoerceToBool rather than ExpressionAnd + }; + + class ConstantNonConstantFalse : public OptimizeBase { + BSONObj spec() { return BSON( "$and" << BSON_ARRAY( 0 << "$a" ) ); } + BSONObj expectedOptimized() { return BSON( "$const" << false ); } }; /** An expression with a field path and '1'. */ @@ -1361,14 +1368,14 @@ namespace ExpressionTests { return Value( values ); } virtual const char* getOpName() const { return "$testable"; } - virtual intrusive_ptr<ExpressionNary> (*getFactory() const)() { - return _haveFactory ? factory : NULL; + virtual bool isAssociativeAndCommutative() const { + return _isAssociativeAndCommutative; } - static intrusive_ptr<Testable> create( bool haveFactory = false ) { - return new Testable( haveFactory ); + static intrusive_ptr<Testable> create( bool associativeAndCommutative = false ) { + return new Testable(associativeAndCommutative); } static intrusive_ptr<ExpressionNary> factory() { - return new Testable( true ); + return new Testable(true); } static intrusive_ptr<Testable> createFromOperands( const BSONArray& operands, bool haveFactory = false ) { @@ -1385,10 +1392,10 @@ namespace ExpressionTests { } private: - Testable( bool haveFactory ) : - _haveFactory( haveFactory ) { - } - bool _haveFactory; + Testable(bool isAssociativeAndCommutative) + : _isAssociativeAndCommutative(isAssociativeAndCommutative) + {} + bool _isAssociativeAndCommutative; }; /** Adding operands to the expression. */ @@ -1531,8 +1538,6 @@ namespace ExpressionTests { intrusive_ptr<Testable> testable = Testable::createFromOperands( BSON_ARRAY( 55 << 66 << "$path" ), true ); intrusive_ptr<Expression> optimized = testable->optimize(); - // Optimization generates a new expression. - ASSERT( testable != optimized ); // The constant expressions are evaluated separately and placed at the end. ASSERT_EQUALS( constify( BSON( "$testable" << BSON_ARRAY( "$path" << BSON_ARRAY( 55 << 66 ) ) ) ), @@ -1557,7 +1562,6 @@ namespace ExpressionTests { ( Testable::createFromOperands ( BSON_ARRAY( 99 << 100 << "$another_path" ), true ) ); intrusive_ptr<Expression> optimized = testable->optimize(); - ASSERT( testable != optimized ); ASSERT_EQUALS ( constify( BSON( "$testable" << BSON_ARRAY( // non constant parts @@ -1582,7 +1586,6 @@ namespace ExpressionTests { ( Testable::createFromOperands( BSON_ARRAY( 5 << 6 << "$c" ), true ) ); top->addOperand( nested ); intrusive_ptr<Expression> optimized = top->optimize(); - ASSERT( top != optimized ); ASSERT_EQUALS ( constify( BSON( "$testable" << BSON_ARRAY( "$a" << "$b" << "$c" << @@ -2458,9 +2461,17 @@ namespace ExpressionTests { BSONObj spec() { return BSON( "$or" << BSON_ARRAY( "$a" ) ); } }; - /** An expression beginning with a single constant is not optimized. SERVER-6192 */ - class ConstantNonConstant : public NoOptimizeBase { + /** An expression beginning with a single constant is optimized. */ + class ConstantNonConstantTrue : public OptimizeBase { BSONObj spec() { return BSON( "$or" << BSON_ARRAY( 1 << "$a" ) ); } + BSONObj expectedOptimized() { return BSON( "$const" << true ); } + }; + + /** An expression beginning with a single constant is optimized. */ + class ConstantNonConstantFalse : public OptimizeBase { + BSONObj spec() { return BSON( "$or" << BSON_ARRAY( 0 << "$a" ) ); } + BSONObj expectedOptimized() { return BSON( "$and" << BSON_ARRAY("$a") ); } + // note: using $and as serialization of ExpressionCoerceToBool rather than ExpressionAnd }; /** An expression with a field path and '1'. */ @@ -3562,7 +3573,8 @@ namespace ExpressionTests { add<And::FieldPath>(); add<And::OptimizeConstantExpression>(); add<And::NonConstant>(); - add<And::ConstantNonConstant>(); + add<And::ConstantNonConstantTrue>(); + add<And::ConstantNonConstantFalse>(); add<And::NonConstantOne>(); add<And::NonConstantZero>(); add<And::NonConstantNonConstantOne>(); @@ -3742,7 +3754,8 @@ namespace ExpressionTests { add<Or::FieldPath>(); add<Or::OptimizeConstantExpression>(); add<Or::NonConstant>(); - add<Or::ConstantNonConstant>(); + add<Or::ConstantNonConstantTrue>(); + add<Or::ConstantNonConstantFalse>(); add<Or::NonConstantOne>(); add<Or::NonConstantZero>(); add<Or::NonConstantNonConstantOne>(); |