core/sql/optimizer/Rule.cpp - trafodion - Git at Google

 /**********************************************************************
 // @@@ START COPYRIGHT @@@
 //
 // Licensed to the Apache Software Foundation (ASF) under one
 // or more contributor license agreements.  See the NOTICE file
 // distributed with this work for additional information
 // regarding copyright ownership.  The ASF licenses this file
 // to you under the Apache License, Version 2.0 (the
 // "License"); you may not use this file except in compliance
 // with the License.  You may obtain a copy of the License at
 //
 //   http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing,
 // software distributed under the License is distributed on an
 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 // KIND, either express or implied.  See the License for the
 // specific language governing permissions and limitations
 // under the License.
 //
 // @@@ END COPYRIGHT @@@
 **********************************************************************/
 /* -*-C++-*-
 ******************************************************************************
 *
 * File:         Rule.C
 * Description:  Cascades optimization rules
 *
 * Created:      9/14/94
 * Language:     C++
 *
 *
 *
 *
 ******************************************************************************
 */

 // -----------------------------------------------------------------------

 #include "Sqlcomp.h"
 #include "TransRule.h"
 #include "ImplRule.h"
 #include "opt.h"
 #include "EstLogProp.h"
 #include "DefaultConstants.h"
 #include "CmpContext.h"


 // -----------------------------------------------------------------------
 // Reinitialize the rule set *in place*:  to be used only if an exception is
 // caught in opt.cpp -- the exception (assertion) needs to unbind all rules
 // (context heap) from the memo (statement heap, about to be deleted).
 // -----------------------------------------------------------------------
 void ReinitRuleSet(RuleSet* rules)
 {
   if (rules)
     {
       Lng32 ruleCnt = rules->getCountOfRules();
       while (ruleCnt--)
         {
 	  Rule *rule = rules->rule(ruleCnt);
       if (rule->getSubstitute())
 	    rule->getSubstitute()->releaseBindingTree(TRUE/*moribundMemo*/);
 	}
     }
 }

 /* ============================================================ */

 /*
   Rules
   =====
   both transformation and implementation rules -- By default, a rule
   is a simple rule, meaning that the substitute given in the rule
   sufficiently represents the transformed expression after cut
   operators in the rule have been bound to proper children.
   */

 Rule::Rule (const char * name, RelExpr * pattern, RelExpr * substitute)
 {
   if (name == NULL)
 // all current rules have name, which is a good practice
     name_ = "no user name";
   else
     name_ = name;

   pattern_ = pattern;
   substitute_ = substitute;

   prepare();

   // a pattern can't have a tree node as its top node
   if (pattern_)
     CMPASSERT(NOT pattern_->isSubtreeOp());

 } // Rule::Rule

 // Rules are created once and never deleted
 Rule::~Rule ()
 {
   delete pattern_;
   delete substitute_;
 } // Rule::~Rule

 // print methods are for debugging
 void Rule::print (FILE * f, const char * prefix, const char * suffix)
 {
   fprintf (f, "%sRule \"%s\" :\n",
 	   prefix, name_);
   pattern_ -> print (f, "  Pattern    = ", "");
   substitute_ -> print (f, "  Substitute = ", "");
   fprintf (f, "%s\n", suffix);
 } // Rule::print

 NABoolean Rule::isImplementationRule() const
 {
   // by default, assume that a copy of the substitute is returned
   return (substitute_->isPhysical());
 }

 NABoolean Rule::isTransformationRule() const
 {
   // by default, assume that a rule is not both transformation and
   // implementation rule
   return NOT isImplementationRule();
 }

 NABoolean Rule::isEnforcerRule() const
 {
   // For enforcer rules, the pattern is always a cutOp meaning that
   // it is always applicable.  Enforcer rules are useful for generating
   // physical operators which enforces desired physical properties.
   return (pattern_ && pattern_->isCutOp());
 }

 NABoolean Rule::isContextSensitive() const
 {
   // By default, consider implementation rules (which include
   // enforcer rules) to be context-sensitive.
   return isImplementationRule();
 }

 NABoolean Rule::isPassSensitive() const
 {
   // By default, assume the rule is not pass sensitive
   return FALSE;
 }

 NABoolean Rule::isPatternSensitive() const
 {
   // By default, assume the rule is not pattern sensitive
   return FALSE;
 }

 NABoolean Rule::canBePruned(RelExpr * expr) const
 {
   // By default, any rule can be pruned unless otherwise defined
   // in its own implementation of the function.
   // This function is only called after a successfull topMatch()
   // i.e. within the processing of an ApplyRuleTask.
   // The purpose of this function is to protect some rule-expr
   // pairs from heuristic or randem pruning.
   return TRUE;
 }

 NABoolean Rule::topMatch(RelExpr * relExpr,
 			 Context *)
 {
   // default implementation should not be invoked for expression-
   // insensitive rules (like enforcer rules).
   CMPASSERT(relExpr != NULL);

   return relExpr->patternMatch(*pattern_);
 }


 RelExpr * Rule::nextSubstitute (RelExpr * before,
 				Context *,
 				RuleSubstituteMemory *& /*memory*/)
 {
   RelExpr *result;

   // the default implementation of a rule fires only once, therefore
   // no RuleSubstituteMemory is allocated

   // build the result expression from the rule's pattern, the skeleton
   // of the rule result, and the original expression "before".
   result = substitute_->copyTree(CmpCommon::statementHeap());

   // now set the group attributes of the result's top node
   result->setGroupAttr(before->getGroupAttr());

   // now set the isinBlockStmt flag for all nodes in the tree.
   result->setBlockStmtRecursively(before->isinBlockStmt());

   return result;
 } // Rule::nextSubstitute

 Guidance * Rule::guidanceForExploringSubstitute (Guidance *)
 {
   return ( NULL );
 } // Rule::guidanceForExploringSubstitute

 Guidance * Rule::guidanceForOptimizingSubstitute (Guidance *,
 			                          Context *)
 {
   return ( NULL );
 } // Rule::guidanceForOptimizingSubstitute

 Guidance * Rule::guidanceForExploringChild(Guidance *,
 					   Context *,
 					   Lng32)
 {
   return ( NULL );
 } // Rule::guidanceForExploringChild

 Guidance * Rule::guidanceForOptimizingChild(Guidance *,
 					    Context *,
 					    Lng32)
 {
   return ( NULL );
 } // Rule::guidanceForOptimizingChild

 Int32 Rule::promiseForExploration (RelExpr * expr,
 				   RelExpr *,
 				   Guidance *)
 {
   // by default, explore in exhaustive search
   // (only transformation rules are used for exploration)
   /*if (expr && CURRSTMT_OPTDEFAULTS->pruneByOptDefaults(this, expr))
     return 0;*/
   return ( DefaultTransRulePromise );
 } // Rule::promiseForExploration

 Int32 Rule::promiseForOptimization (RelExpr * expr,
 				    Guidance *,
 				    Context *)
 {
   /*if (expr && CURRSTMT_OPTDEFAULTS->pruneByOptDefaults(this, expr))
     return 0;*/

   if (isImplementationRule())
     {
       return DefaultImplRulePromise;
     }
   else
     {
       return DefaultTransRulePromise;
     }
 } // Rule::promiseForOptimization

 void Rule::prepare()
 {
   // an array to hold pointers for cuts of the pattern, ordered by index
   // (most rules should get by with 4 cuts and 4 wildcards)
   ARRAY(CutOp *) cuts(HEAP, 4);
   ARRAY(WildCardOp *) wildcards(HEAP, 4);

   // fill the "cuts" array
   if (pattern_)
     (void *) checkAndBindPattern(pattern_,cuts,wildcards,FALSE);

   // now replace all cut nodes in the substitute by the corresponding
   // cut nodes of the pattern
   if (substitute_)
     substitute_ = checkAndBindPattern(substitute_,cuts,wildcards,TRUE);

 } // Rule::prepare

 RelExpr * Rule::checkAndBindPattern(RelExpr * patt,
 				    ARRAY(CutOp *) & cuts,
 				    ARRAY(WildCardOp *) & wildcards,
 				    NABoolean isSubstitute)
 {
   RelExpr *result = patt;

   if (patt->isCutOp())
     {
       CutOp *acut = (CutOp *) patt;
       Int32 ix = acut->getIndex();

       if (!isSubstitute)
 	{
 	  if (cuts.used(ix))
 	    // error, a cut index occurs twice in the pattern
 	    ABORT("encountered pattern with duplicate cut nodes");
 	  else
 	    cuts.insertAt(ix,acut);
 	}
       else
 	{
 	  // this is a substitute, replace the cut node with the
 	  // corresponding cut node from the pattern (both pattern and
 	  // substitute then point to the same cut node)
 	  if (NOT cuts.used(ix))
 	    ABORT("cut in substitute doesn't match the pattern");

 	  result = cuts[ix];
 	  delete patt;
 	  patt = result;
 	}
     } // pattern is a cut
   else
     if (patt->isWildcard())
       {
 	WildCardOp *wild = (WildCardOp *) patt;
 	Int32 designator = wild->getDesignator();

 	if (!isSubstitute)
 	  {
 	    // fill in the appropriate entry of the wildcards array

 	    if (wildcards.used(designator))
 	      // error, a wildcard index occurs twice in the pattern
 	      ABORT("pattern with duplicate wildcard designators");
 	    else
 	      wildcards.insertAt(designator,wild);
 	  }
 	else
 	  {
 	    if (NOT wildcards.used(designator))
 	      ABORT("wildcard in substitute has an invalid designator");

 	    // this is a substitute, associate the wildcard node in the
 	    // substitute with the wildcard node in the pattern
 	    wild->setCorrespondingNode(wildcards[designator]);

 	    // unlike cut nodes, wildcards are NOT shared
 	    // between the pattern and the substitute
 	  }
       } // pattern is a wildcard

   // recurse

   Int32 arity = patt->getArity();

   for (Lng32 i = 0; i < arity; i++)
     {
       result->child(i) = checkAndBindPattern(patt->child(i)->castToRelExpr(),
 					     cuts,
 					     wildcards,
 					     isSubstitute);
     }

   return result;

 } // Rule::checkAndBindPattern

 // Can this rule potentially generate the specified pattern?
 // NOTE: This method must be defined for those rules that specifies
 // multiple substitutes, or those rules for which the substitute is
 // not a true indication of the substitute expression.
 NABoolean Rule::canMatchPattern (const RelExpr * pattern) const

 {
   return substitute_->getOperator().match(pattern->getOperator());
 }

 // -----------------------------------------------------------------------
 // methods for class RuleSubset
 // -----------------------------------------------------------------------

 RuleSubset::RuleSubset(CollHeap* h) :
   SUBARRAY(Rule *)(&GlobalRuleSet->allRules_,h) {}

 RuleSubset::RuleSubset (const RuleSubset & orig, CollHeap * h) :
   SUBARRAY(Rule *)(orig,h) {}


 // -----------------------------------------------------------------------
 // methods for class RuleSet
 // -----------------------------------------------------------------------

 RuleSet::RuleSet(Int32 approxNumRules, CollHeap* h) :
   allRules_(h, approxNumRules),
   passNRules_(h),
   oldRules_(&allRules_,h),
   transRules_(&allRules_,h),
   implRules_(&allRules_,h),
   enforcerRules_(&allRules_,h),
   contextSensitiveRules_(&allRules_,h),
   passSensitiveRules_(&allRules_,h),
   patternSensitiveRules_(&allRules_,h),
   ruleApplCount_(0)
 {
   initializeCurrentPassNumber();
   setTotalPasses();  // set the total number of optimization passes

   initializeAllPasses();
 }

 // Rules are created once and never deleted
 RuleSet::~RuleSet()
 {
   for (Lng32 i = 0; i < (Lng32)allRules_.entries(); i++)
     delete allRules_[i];
   for (Lng32 i = 0; i < (Lng32)passNRules_.entries(); i++)
     delete passNRules_[i];
 }

 void RuleSet::insert(Rule * r)
 {
   Lng32 num = r->ruleNumber_ = allRules_.entries();
   allRules_.insertAt(num,r);

   if (num >= MAX_RULE_COUNT)
     ABORT("Increase max number of rules in Rule.h");

   if (r->isImplementationRule())
     implRules_ += num;

   if (r->isTransformationRule())
     transRules_ += num;

   if (r->isEnforcerRule())
     enforcerRules_ += num;

   if (r->isContextSensitive())
     contextSensitiveRules_ += num;

   if (r->isPassSensitive())
     passSensitiveRules_ += num;

   if (r->isPatternSensitive())
     patternSensitiveRules_ += num;
 }

 void RuleSet::setTotalPasses()
 {
   NAString value(CmpCommon::statementHeap());
   // Only do the first pass if the optimization level is MINIMUM or
   // if the query complexity is greater than that for 32 regular joins
   // (2^32 = INT_MAX), and the join order is not fixed by the user.
   // This is because we assume that performing more than 32 joins will
   // consume too many resources and take too long, even at MEDIUM opt.
   // level.
   // limit increase to 40 way join i.e. (40 * 2 ^ 39)
   if (!CURRENTSTMT &&
       (CmpCommon::getDefault(OPTIMIZATION_LEVEL) == DF_MINIMUM))
   {
     totalPasses_ = 1;
   }
   else if (!CURRENTSTMT)
   {
     totalPasses_ = MAX_NUM_OF_PASSES;
   }
   else if ((CURRSTMT_OPTDEFAULTS->optLevel() == OptDefaults::MINIMUM) OR
       ((CURRSTMT_OPTDEFAULTS->getQueryComplexity() > 3e13) AND
        NOT CURRSTMT_OPTDEFAULTS->joinOrderByUser()))
   {
     totalPasses_ = 1;
   }
   else
   {
     totalPasses_ = MAX_NUM_OF_PASSES;
   }

   //---------------------------------------------------------
   // Optimization Level = 0 (minimum level) is the same as
   //                      optimization pass 1 today.
   // For now, all other optimization levels equate to full
   // optimization level today (i.e. optimization pass 2).
   //---------------------------------------------------------
 }

 void RuleSet::enable(NAUnsigned ruleNo, Lng32 fromPass, Lng32 toPassIncl)
 {
   CMPASSERT(
     fromPass >= getFirstPassNumber() AND toPassIncl >= getFirstPassNumber());

   if (fromPass <= MAX_NUM_OF_PASSES AND toPassIncl <=  MAX_NUM_OF_PASSES)
     for (Lng32 i = fromPass; i <= toPassIncl; i++)
       *(passNRules_[i]) += ruleNo;
 }

 void RuleSet::disable(NAUnsigned ruleNo, Lng32 fromPass, Lng32 toPassIncl)
 {
   CMPASSERT(
     fromPass >= getFirstPassNumber() AND toPassIncl >= getFirstPassNumber());

   if (fromPass <= MAX_NUM_OF_PASSES AND toPassIncl <=  MAX_NUM_OF_PASSES)
     for (Lng32 i = fromPass; i <= toPassIncl; i++)
       *(passNRules_[i]) -= ruleNo;
 }

 void RuleSet::initializeAllPasses()
 {
   Lng32 index;
   for (index = 0; index < getFirstPassNumber(); index++)
     passNRules_.insertAt(index,NULL);
   for (index = getFirstPassNumber(); index <= MAX_NUM_OF_PASSES; index++)
     passNRules_.insertAt(index,
 			 new(CmpCommon::contextHeap())
 			 RuleSubset(&allRules_, CmpCommon::contextHeap()));
 }

 void  RuleSet::initializeFirstPass()
 {
   ruleApplCount_ = 0;
   initializeCurrentPassNumber();
   oldRules_.clear();

   // In the case that optimization_level has been reset dynamically
   // via the CONTROL QUERY DEFAULT statement, reset the total pass count.
   setTotalPasses();
 }

 // this is called by the old optimization driver i.e. RelExpr::optimize
 // the new optimization driver is method RelExpr::optimize2
 NABoolean RuleSet::nextPass()
 {
   if (NOT inLastPass())
     {
       incrementCurrentPassNumber();
       oldRules_ += *applicableRules();
       return TRUE;
     }
   else
     return FALSE;
 }

 void RuleSet::setCurrentPassNumber(Lng32 passNumber)
 {
   currentPass_ = passNumber;
   oldRules_ += *applicableRules();
 }
 // -----------------------------------------------------------------------
 // methods for class RuleSubstituteMemory
 // -----------------------------------------------------------------------
 RuleSubstituteMemory::~RuleSubstituteMemory() {}

 RelExpr * RuleSubstituteMemory::getNextSubstitute()
 {
   RelExpr * result;

   if (NOT getFirst(result))
     result = NULL;

   return result;
 }

 // -----------------------------------------------------------------------
 // methods for RulesPerContext
 // -----------------------------------------------------------------------
 RulesPerContext::RulesPerContext (const Context * const context,CollHeap* h)
                 : context_(context)
                 , triedRules_(h)
 {
   triedRules_.clear();  // start with a clear bitmap
 }

 // -----------------------------------------------------------------------
 // methods for RulesPerContextList
 // -----------------------------------------------------------------------

 // Get the Rules that have been applied to this context
 const RuleSubset & RulesPerContextList::getTriedRules(const Context* const context) const
 {
   for (Lng32 i= 0; i< (Lng32)entries(); i++)
   {
     const Context* const other = (*this)[i]->getContext();
     if (context == other)
       return (*this)[i]->getTriedRules();
   }
   RuleSubset* emptyRuleSubset =
     new(CmpCommon::statementHeap()) RuleSubset(CmpCommon::statementHeap());
   emptyRuleSubset->clear();
   return *emptyRuleSubset;
 }

 // Has the provided rule been applied already for the given context?
 NABoolean RulesPerContextList::applied (const Context * const context,
 					NAUnsigned ruleNumber) const
 {
   Lng32 i = 0;
   while (i < (Lng32)entries())
   {
     const Context* const other = (*this)[i]->getContext();
     if (context == other)
       return ((*this)[i]->getTriedRules().contains (ruleNumber));
     else
       i++;
   }
   return FALSE;
 }

 // not called anywhere in the code
 //
 // Has the provided rule been applied in any prior context which has the
 // provided set of input logical properties?
 NABoolean RulesPerContextList::applied (const EstLogPropSharedPtr& inputLogProp,
 					NAUnsigned ruleNumber) const
 {
   Lng32 i = 0;
   while (i < (Lng32)entries())
   {
     if ((*this)[i]->getContext() != NULL AND
 	(*this)[i]->getContext()->getInputLogProp()->compareEstLogProp(inputLogProp) == SAME)
       return ((*this)[i]->getTriedRules().contains (ruleNumber));
     else
       i++;
   }
   return FALSE;
 }

 void RulesPerContextList::addRule (const Context* const context,
 				   NAUnsigned ruleNumber)
 {
   Lng32 i = 0;
   while (i < (Lng32)entries())
   {
     if (context == (*this)[i]->getContext())
     {
       // mark this rule as already applied for this context
       (*this)[i]->triedRules() += ruleNumber;
       return;
     }
     else
       i++;
   }

   // context not found?  Create a new entry for this context.

   RulesPerContext *newEntry = new (CmpCommon::statementHeap())
          RulesPerContext (context,(CmpCommon::statementHeap()));
   newEntry->triedRules() += ruleNumber;

   // insert this new structure at the head of the list
   insertAt (0, newEntry);
 }

 // method is not called anywhere
 void RulesPerContextList::removeRule (const Context* const context,
 				   NAUnsigned ruleNumber)
 {
   Lng32 i = 0;
   while (i < (Lng32)entries())
   { // is this enough? Do we need to check for the SAME context here?
     if (context == (*this)[i]->getContext())
     {
       // remove this rule from already applied for this context
       (*this)[i]->triedRules() -= ruleNumber;
       return;
     }
     else
       i++;
   }
 }

 // -----------------------------------------------------------------------
 // methods for class Guidance
 // -----------------------------------------------------------------------

 Guidance::~Guidance() {}

 const RuleSubset * Guidance::applicableRules()
 {
   // default implementation, return all applicable rules
   return GlobalRuleSet->applicableRules();
 }
	/**********************************************************************
	// @@@ START COPYRIGHT @@@
	//
	// Licensed to the Apache Software Foundation (ASF) under one
	// or more contributor license agreements. See the NOTICE file
	// distributed with this work for additional information
	// regarding copyright ownership. The ASF licenses this file
	// to you under the Apache License, Version 2.0 (the
	// "License"); you may not use this file except in compliance
	// with the License. You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing,
	// software distributed under the License is distributed on an
	// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	// KIND, either express or implied. See the License for the
	// specific language governing permissions and limitations
	// under the License.
	//
	// @@@ END COPYRIGHT @@@
	**********************************************************************/
	/* --C++--
	******************************************************************************
	*
	* File: Rule.C
	* Description: Cascades optimization rules
	*
	* Created: 9/14/94
	* Language: C++
	*
	*
	*
	*
	******************************************************************************
	*/

	// -----------------------------------------------------------------------

	#include "Sqlcomp.h"
	#include "TransRule.h"
	#include "ImplRule.h"
	#include "opt.h"
	#include "EstLogProp.h"
	#include "DefaultConstants.h"
	#include "CmpContext.h"


	// -----------------------------------------------------------------------
	// Reinitialize the rule set in place: to be used only if an exception is
	// caught in opt.cpp -- the exception (assertion) needs to unbind all rules
	// (context heap) from the memo (statement heap, about to be deleted).
	// -----------------------------------------------------------------------
	void ReinitRuleSet(RuleSet* rules)
	{
	if (rules)
	{
	Lng32 ruleCnt = rules->getCountOfRules();
	while (ruleCnt--)
	{
	Rule *rule = rules->rule(ruleCnt);
	if (rule->getSubstitute())
	rule->getSubstitute()->releaseBindingTree(TRUE/moribundMemo/);
	}
	}
	}

	/* ============================================================ */

	/*
	Rules
	=====
	both transformation and implementation rules -- By default, a rule
	is a simple rule, meaning that the substitute given in the rule
	sufficiently represents the transformed expression after cut
	operators in the rule have been bound to proper children.
	*/

	Rule::Rule (const char * name, RelExpr * pattern, RelExpr * substitute)
	{
	if (name == NULL)
	// all current rules have name, which is a good practice
	name_ = "no user name";
	else
	name_ = name;

	pattern_ = pattern;
	substitute_ = substitute;

	prepare();

	// a pattern can't have a tree node as its top node
	if (pattern_)
	CMPASSERT(NOT pattern_->isSubtreeOp());

	} // Rule::Rule

	// Rules are created once and never deleted
	Rule::~Rule ()
	{
	delete pattern_;
	delete substitute_;
	} // Rule::~Rule

	// print methods are for debugging
	void Rule::print (FILE * f, const char * prefix, const char * suffix)
	{
	fprintf (f, "%sRule \"%s\" :\n",
	prefix, name_);
	pattern_ -> print (f, " Pattern = ", "");
	substitute_ -> print (f, " Substitute = ", "");
	fprintf (f, "%s\n", suffix);
	} // Rule::print

	NABoolean Rule::isImplementationRule() const
	{
	// by default, assume that a copy of the substitute is returned
	return (substitute_->isPhysical());
	}

	NABoolean Rule::isTransformationRule() const
	{
	// by default, assume that a rule is not both transformation and
	// implementation rule
	return NOT isImplementationRule();
	}

	NABoolean Rule::isEnforcerRule() const
	{
	// For enforcer rules, the pattern is always a cutOp meaning that
	// it is always applicable. Enforcer rules are useful for generating
	// physical operators which enforces desired physical properties.
	return (pattern_ && pattern_->isCutOp());
	}

	NABoolean Rule::isContextSensitive() const
	{
	// By default, consider implementation rules (which include
	// enforcer rules) to be context-sensitive.
	return isImplementationRule();
	}

	NABoolean Rule::isPassSensitive() const
	{
	// By default, assume the rule is not pass sensitive
	return FALSE;
	}

	NABoolean Rule::isPatternSensitive() const
	{
	// By default, assume the rule is not pattern sensitive
	return FALSE;
	}

	NABoolean Rule::canBePruned(RelExpr * expr) const
	{
	// By default, any rule can be pruned unless otherwise defined
	// in its own implementation of the function.
	// This function is only called after a successfull topMatch()
	// i.e. within the processing of an ApplyRuleTask.
	// The purpose of this function is to protect some rule-expr
	// pairs from heuristic or randem pruning.
	return TRUE;
	}

	NABoolean Rule::topMatch(RelExpr * relExpr,
	Context *)
	{
	// default implementation should not be invoked for expression-
	// insensitive rules (like enforcer rules).
	CMPASSERT(relExpr != NULL);

	return relExpr->patternMatch(*pattern_);
	}


	RelExpr * Rule::nextSubstitute (RelExpr * before,
	Context *,
	RuleSubstituteMemory & /memory*/)
	{
	RelExpr *result;

	// the default implementation of a rule fires only once, therefore
	// no RuleSubstituteMemory is allocated

	// build the result expression from the rule's pattern, the skeleton
	// of the rule result, and the original expression "before".
	result = substitute_->copyTree(CmpCommon::statementHeap());

	// now set the group attributes of the result's top node
	result->setGroupAttr(before->getGroupAttr());

	// now set the isinBlockStmt flag for all nodes in the tree.
	result->setBlockStmtRecursively(before->isinBlockStmt());

	return result;
	} // Rule::nextSubstitute

	Guidance * Rule::guidanceForExploringSubstitute (Guidance *)
	{
	return ( NULL );
	} // Rule::guidanceForExploringSubstitute

	Guidance * Rule::guidanceForOptimizingSubstitute (Guidance *,
	Context *)
	{
	return ( NULL );
	} // Rule::guidanceForOptimizingSubstitute

	Guidance * Rule::guidanceForExploringChild(Guidance *,
	Context *,
	Lng32)
	{
	return ( NULL );
	} // Rule::guidanceForExploringChild

	Guidance * Rule::guidanceForOptimizingChild(Guidance *,
	Context *,
	Lng32)
	{
	return ( NULL );
	} // Rule::guidanceForOptimizingChild

	Int32 Rule::promiseForExploration (RelExpr * expr,
	RelExpr *,
	Guidance *)
	{
	// by default, explore in exhaustive search
	// (only transformation rules are used for exploration)
	/*if (expr && CURRSTMT_OPTDEFAULTS->pruneByOptDefaults(this, expr))
	return 0;*/
	return ( DefaultTransRulePromise );
	} // Rule::promiseForExploration

	Int32 Rule::promiseForOptimization (RelExpr * expr,
	Guidance *,
	Context *)
	{
	/*if (expr && CURRSTMT_OPTDEFAULTS->pruneByOptDefaults(this, expr))
	return 0;*/

	if (isImplementationRule())
	{
	return DefaultImplRulePromise;
	}
	else
	{
	return DefaultTransRulePromise;
	}
	} // Rule::promiseForOptimization

	void Rule::prepare()
	{
	// an array to hold pointers for cuts of the pattern, ordered by index
	// (most rules should get by with 4 cuts and 4 wildcards)
	ARRAY(CutOp *) cuts(HEAP, 4);
	ARRAY(WildCardOp *) wildcards(HEAP, 4);

	// fill the "cuts" array
	if (pattern_)
	(void *) checkAndBindPattern(pattern_,cuts,wildcards,FALSE);

	// now replace all cut nodes in the substitute by the corresponding
	// cut nodes of the pattern
	if (substitute_)
	substitute_ = checkAndBindPattern(substitute_,cuts,wildcards,TRUE);

	} // Rule::prepare

	RelExpr * Rule::checkAndBindPattern(RelExpr * patt,
	ARRAY(CutOp *) & cuts,
	ARRAY(WildCardOp *) & wildcards,
	NABoolean isSubstitute)
	{
	RelExpr *result = patt;

	if (patt->isCutOp())
	{
	CutOp acut = (CutOp ) patt;
	Int32 ix = acut->getIndex();

	if (!isSubstitute)
	{
	if (cuts.used(ix))
	// error, a cut index occurs twice in the pattern
	ABORT("encountered pattern with duplicate cut nodes");
	else
	cuts.insertAt(ix,acut);
	}
	else
	{
	// this is a substitute, replace the cut node with the
	// corresponding cut node from the pattern (both pattern and
	// substitute then point to the same cut node)
	if (NOT cuts.used(ix))
	ABORT("cut in substitute doesn't match the pattern");

	result = cuts[ix];
	delete patt;
	patt = result;
	}
	} // pattern is a cut
	else
	if (patt->isWildcard())
	{
	WildCardOp wild = (WildCardOp ) patt;
	Int32 designator = wild->getDesignator();

	if (!isSubstitute)
	{
	// fill in the appropriate entry of the wildcards array

	if (wildcards.used(designator))
	// error, a wildcard index occurs twice in the pattern
	ABORT("pattern with duplicate wildcard designators");
	else
	wildcards.insertAt(designator,wild);
	}
	else
	{
	if (NOT wildcards.used(designator))
	ABORT("wildcard in substitute has an invalid designator");

	// this is a substitute, associate the wildcard node in the
	// substitute with the wildcard node in the pattern
	wild->setCorrespondingNode(wildcards[designator]);

	// unlike cut nodes, wildcards are NOT shared
	// between the pattern and the substitute
	}
	} // pattern is a wildcard

	// recurse

	Int32 arity = patt->getArity();

	for (Lng32 i = 0; i < arity; i++)
	{
	result->child(i) = checkAndBindPattern(patt->child(i)->castToRelExpr(),
	cuts,
	wildcards,
	isSubstitute);
	}

	return result;

	} // Rule::checkAndBindPattern

	// Can this rule potentially generate the specified pattern?
	// NOTE: This method must be defined for those rules that specifies
	// multiple substitutes, or those rules for which the substitute is
	// not a true indication of the substitute expression.
	NABoolean Rule::canMatchPattern (const RelExpr * pattern) const

	{
	return substitute_->getOperator().match(pattern->getOperator());
	}

	// -----------------------------------------------------------------------
	// methods for class RuleSubset
	// -----------------------------------------------------------------------

	RuleSubset::RuleSubset(CollHeap* h) :
	SUBARRAY(Rule *)(&GlobalRuleSet->allRules_,h) {}

	RuleSubset::RuleSubset (const RuleSubset & orig, CollHeap * h) :
	SUBARRAY(Rule *)(orig,h) {}


	// -----------------------------------------------------------------------
	// methods for class RuleSet
	// -----------------------------------------------------------------------

	RuleSet::RuleSet(Int32 approxNumRules, CollHeap* h) :
	allRules_(h, approxNumRules),
	passNRules_(h),
	oldRules_(&allRules_,h),
	transRules_(&allRules_,h),
	implRules_(&allRules_,h),
	enforcerRules_(&allRules_,h),
	contextSensitiveRules_(&allRules_,h),
	passSensitiveRules_(&allRules_,h),
	patternSensitiveRules_(&allRules_,h),
	ruleApplCount_(0)
	{
	initializeCurrentPassNumber();
	setTotalPasses(); // set the total number of optimization passes

	initializeAllPasses();
	}

	// Rules are created once and never deleted
	RuleSet::~RuleSet()
	{
	for (Lng32 i = 0; i < (Lng32)allRules_.entries(); i++)
	delete allRules_[i];
	for (Lng32 i = 0; i < (Lng32)passNRules_.entries(); i++)
	delete passNRules_[i];
	}

	void RuleSet::insert(Rule * r)
	{
	Lng32 num = r->ruleNumber_ = allRules_.entries();
	allRules_.insertAt(num,r);

	if (num >= MAX_RULE_COUNT)
	ABORT("Increase max number of rules in Rule.h");

	if (r->isImplementationRule())
	implRules_ += num;

	if (r->isTransformationRule())
	transRules_ += num;

	if (r->isEnforcerRule())
	enforcerRules_ += num;

	if (r->isContextSensitive())
	contextSensitiveRules_ += num;

	if (r->isPassSensitive())
	passSensitiveRules_ += num;

	if (r->isPatternSensitive())
	patternSensitiveRules_ += num;
	}

	void RuleSet::setTotalPasses()
	{
	NAString value(CmpCommon::statementHeap());
	// Only do the first pass if the optimization level is MINIMUM or
	// if the query complexity is greater than that for 32 regular joins
	// (2^32 = INT_MAX), and the join order is not fixed by the user.
	// This is because we assume that performing more than 32 joins will
	// consume too many resources and take too long, even at MEDIUM opt.
	// level.
	// limit increase to 40 way join i.e. (40 * 2 ^ 39)
	if (!CURRENTSTMT &&
	(CmpCommon::getDefault(OPTIMIZATION_LEVEL) == DF_MINIMUM))
	{
	totalPasses_ = 1;
	}
	else if (!CURRENTSTMT)
	{
	totalPasses_ = MAX_NUM_OF_PASSES;
	}
	else if ((CURRSTMT_OPTDEFAULTS->optLevel() == OptDefaults::MINIMUM) OR
	((CURRSTMT_OPTDEFAULTS->getQueryComplexity() > 3e13) AND
	NOT CURRSTMT_OPTDEFAULTS->joinOrderByUser()))
	{
	totalPasses_ = 1;
	}
	else
	{
	totalPasses_ = MAX_NUM_OF_PASSES;
	}

	//---------------------------------------------------------
	// Optimization Level = 0 (minimum level) is the same as
	// optimization pass 1 today.
	// For now, all other optimization levels equate to full
	// optimization level today (i.e. optimization pass 2).
	//---------------------------------------------------------
	}

	void RuleSet::enable(NAUnsigned ruleNo, Lng32 fromPass, Lng32 toPassIncl)
	{
	CMPASSERT(
	fromPass >= getFirstPassNumber() AND toPassIncl >= getFirstPassNumber());

	if (fromPass <= MAX_NUM_OF_PASSES AND toPassIncl <= MAX_NUM_OF_PASSES)
	for (Lng32 i = fromPass; i <= toPassIncl; i++)
	*(passNRules_[i]) += ruleNo;
	}

	void RuleSet::disable(NAUnsigned ruleNo, Lng32 fromPass, Lng32 toPassIncl)
	{
	CMPASSERT(
	fromPass >= getFirstPassNumber() AND toPassIncl >= getFirstPassNumber());

	if (fromPass <= MAX_NUM_OF_PASSES AND toPassIncl <= MAX_NUM_OF_PASSES)
	for (Lng32 i = fromPass; i <= toPassIncl; i++)
	*(passNRules_[i]) -= ruleNo;
	}

	void RuleSet::initializeAllPasses()
	{
	Lng32 index;
	for (index = 0; index < getFirstPassNumber(); index++)
	passNRules_.insertAt(index,NULL);
	for (index = getFirstPassNumber(); index <= MAX_NUM_OF_PASSES; index++)
	passNRules_.insertAt(index,
	new(CmpCommon::contextHeap())
	RuleSubset(&allRules_, CmpCommon::contextHeap()));
	}

	void RuleSet::initializeFirstPass()
	{
	ruleApplCount_ = 0;
	initializeCurrentPassNumber();
	oldRules_.clear();

	// In the case that optimization_level has been reset dynamically
	// via the CONTROL QUERY DEFAULT statement, reset the total pass count.
	setTotalPasses();
	}

	// this is called by the old optimization driver i.e. RelExpr::optimize
	// the new optimization driver is method RelExpr::optimize2
	NABoolean RuleSet::nextPass()
	{
	if (NOT inLastPass())
	{
	incrementCurrentPassNumber();
	oldRules_ += *applicableRules();
	return TRUE;
	}
	else
	return FALSE;
	}

	void RuleSet::setCurrentPassNumber(Lng32 passNumber)
	{
	currentPass_ = passNumber;
	oldRules_ += *applicableRules();
	}
	// -----------------------------------------------------------------------
	// methods for class RuleSubstituteMemory
	// -----------------------------------------------------------------------
	RuleSubstituteMemory::~RuleSubstituteMemory() {}

	RelExpr * RuleSubstituteMemory::getNextSubstitute()
	{
	RelExpr * result;

	if (NOT getFirst(result))
	result = NULL;

	return result;
	}

	// -----------------------------------------------------------------------
	// methods for RulesPerContext
	// -----------------------------------------------------------------------
	RulesPerContext::RulesPerContext (const Context * const context,CollHeap* h)
	: context_(context)
	, triedRules_(h)
	{
	triedRules_.clear(); // start with a clear bitmap
	}

	// -----------------------------------------------------------------------
	// methods for RulesPerContextList
	// -----------------------------------------------------------------------

	// Get the Rules that have been applied to this context
	const RuleSubset & RulesPerContextList::getTriedRules(const Context* const context) const
	{
	for (Lng32 i= 0; i< (Lng32)entries(); i++)
	{
	const Context* const other = (*this)[i]->getContext();
	if (context == other)
	return (*this)[i]->getTriedRules();
	}
	RuleSubset* emptyRuleSubset =
	new(CmpCommon::statementHeap()) RuleSubset(CmpCommon::statementHeap());
	emptyRuleSubset->clear();
	return *emptyRuleSubset;
	}

	// Has the provided rule been applied already for the given context?
	NABoolean RulesPerContextList::applied (const Context * const context,
	NAUnsigned ruleNumber) const
	{
	Lng32 i = 0;
	while (i < (Lng32)entries())
	{
	const Context* const other = (*this)[i]->getContext();
	if (context == other)
	return ((*this)[i]->getTriedRules().contains (ruleNumber));
	else
	i++;
	}
	return FALSE;
	}

	// not called anywhere in the code
	//
	// Has the provided rule been applied in any prior context which has the
	// provided set of input logical properties?
	NABoolean RulesPerContextList::applied (const EstLogPropSharedPtr& inputLogProp,
	NAUnsigned ruleNumber) const
	{
	Lng32 i = 0;
	while (i < (Lng32)entries())
	{
	if ((*this)[i]->getContext() != NULL AND
	(*this)[i]->getContext()->getInputLogProp()->compareEstLogProp(inputLogProp) == SAME)
	return ((*this)[i]->getTriedRules().contains (ruleNumber));
	else
	i++;
	}
	return FALSE;
	}

	void RulesPerContextList::addRule (const Context* const context,
	NAUnsigned ruleNumber)
	{
	Lng32 i = 0;
	while (i < (Lng32)entries())
	{
	if (context == (*this)[i]->getContext())
	{
	// mark this rule as already applied for this context
	(*this)[i]->triedRules() += ruleNumber;
	return;
	}
	else
	i++;
	}

	// context not found? Create a new entry for this context.

	RulesPerContext *newEntry = new (CmpCommon::statementHeap())
	RulesPerContext (context,(CmpCommon::statementHeap()));
	newEntry->triedRules() += ruleNumber;

	// insert this new structure at the head of the list
	insertAt (0, newEntry);
	}

	// method is not called anywhere
	void RulesPerContextList::removeRule (const Context* const context,
	NAUnsigned ruleNumber)
	{
	Lng32 i = 0;
	while (i < (Lng32)entries())
	{ // is this enough? Do we need to check for the SAME context here?
	if (context == (*this)[i]->getContext())
	{
	// remove this rule from already applied for this context
	(*this)[i]->triedRules() -= ruleNumber;
	return;
	}
	else
	i++;
	}
	}

	// -----------------------------------------------------------------------
	// methods for class Guidance
	// -----------------------------------------------------------------------

	Guidance::~Guidance() {}

	const RuleSubset * Guidance::applicableRules()
	{
	// default implementation, return all applicable rules
	return GlobalRuleSet->applicableRules();
	}