ORCA优化器浅析——重要主流程概述

COptimizer::PdxlnOptimize
  |--CQueryContext *pqc = CQueryContext::PqcGenerate(mp, pexprTranslated, pdrgpul, pdrgpmdname, true /*fDeriveStats*/);
  |--CExpression *pexprPlan = PexprOptimize(mp, pqc, search_stage_array);
      |--CEngine eng(mp);
      |--eng.Init(pqc, search_stage_array);
      |--eng.Optimize();
          |--const ULONG ulJobs = std::min((ULONG) GPOPT_JOBS_CAP, (ULONG)(m_pmemo->UlpGroups() * GPOPT_JOBS_PER_GROUP));
          |--CJobFactory jf(m_mp, ulJobs);CScheduler sched(m_mp, ulJobs);CSchedulerContext sc;sc.Init(m_mp, &jf, &sched, this);
          |--const ULONG ulSearchStages = m_search_stage_array->Size();
          |--for (ULONG ul = 0; !FSearchTerminated() && ul < ulSearchStages; ul++)
               PssCurrent()->RestartTimer();
               COptimizationContext *poc = GPOS_NEW(m_mp) COptimizationContext(m_mp, PgroupRoot(), m_pqc->Prpp(), GPOS_NEW(m_mp) CReqdPropRelational(GPOS_NEW(m_mp) CColRefSet(m_mp)), GPOS_NEW(m_mp) IStatisticsArray(m_mp), m_ulCurrSearchStage);		
		       ScheduleMainJob(&sc, poc); // schedule main optimization job
               CScheduler::Run(&sc); // run optimization job
		       poc->Release();
		       // extract best plan found at the end of current search stage
		       CExpression *pexprPlan = m_pmemo->PexprExtractPlan(m_mp, m_pmemo->PgroupRoot(), m_pqc->Prpp(), m_search_stage_array->Size());
       		   PssCurrent()->SetBestExpr(pexprPlan);
		       FinalizeSearchStage();
      |--CExpression *pexprPlan = eng.PexprExtractPlan();
      |--(void) pexprPlan->PrppCompute(mp, pqc->Prpp());      
  |--pdxlnPlan = CreateDXLNode(mp, md_accessor, pexprPlan, pqc->PdrgPcr(), pdrgpmdname, ulHosts);

优化流程的重要函数如上所示，首先需要介绍一下最重要的类CSchedulerContext，如下图右上角所示，其包含三个重要成员：CJobFactory *m_pjf【生成CJOB任务类实例的工厂函数】、CScheduler *m_psched【调度器类用于调度任务类实例】、CEngine *m_peng【Optimization engine】。其次介绍一下CEngine类，其用于Optimization engine owns entire optimization workflow。如下图所示，其最重要的成员为CQueryContext *m_pqc【query context】、CSearchStageArray *m_search_stage_array【search strategy】、ULONG m_ulCurrSearchStage【index of current search stage】、CMemo *m_pmemo【memo table】、CExpression *m_pexprEnforcerPattern【pattern used for adding enforcers】。m_pexprEnforcerPattern在构造函数时被初始化为CExpression(mp, GPOS_NEW(mp) CPatternLeaf(mp))；m_pqc在Init函数被初始化为PdxlnOptimize调用CQueryContext::PqcGenerate创建的CQueryContext【Query specific information that optimizer receives as input representing the requirements that need to be satisfied by the final plan.】；m_search_stage_array被初始化为形参search_stage_array，如果形参为NULL，则初始化为CSearchStage::PdrgpssDefault(m_mp)。

ORCA支持多个搜索策略SearchStage，如下图所示，TimeThreshold配置该阶段策略的最大耗时、CostThreshold配置该阶段策略的最大成本。使用optimizer_search_strategy_path GUC配置如下文件的存放路径。

COptTasks::OptimizeTask函数会对搜索策略进行加载load search strategy，代码如下所示CSearchStageArray *search_strategy_arr = LoadSearchStrategy(mp, optimizer_search_strategy_path) 。默认情况下使用CSearchStage::PdrgpssDefault(m_mp)生成的策略exploration xforms（one stage with all xforms and no time/cost thresholds）。

//---------------------------------------------------------------------------
//	@function:
//		CSearchStage::PdrgpssDefault
//	@doc:
//		Generate default search strategy; one stage with all xforms and no time/cost thresholds
//---------------------------------------------------------------------------
CSearchStageArray *CSearchStage::PdrgpssDefault(CMemoryPool *mp){
	CXformSet *xform_set = GPOS_NEW(mp) CXformSet(mp);
	xform_set->Union(CXformFactory::Pxff()->PxfsExploration());
	CSearchStageArray *search_stage_array = GPOS_NEW(mp) CSearchStageArray(mp);
	search_stage_array->Append(GPOS_NEW(mp) CSearchStage(xform_set));
	return search_stage_array;
}

CSearchStage类是search_stage_array的元素，m_time_threshold、m_cost_threshold和m_xforms是上述流程中提取出来的信息。m_pexprBest用于存放当前search stage的最佳执行计划，m_costBest用于存放当前search stage的最佳执行计划的COST。

class CSearchStage {
private:	
	CXformSet *m_xforms; // set of xforms to be applied during stage	
	ULONG m_time_threshold; // time threshold in milliseconds	
	CCost m_cost_threshold; // cost threshold
	
	CExpression *m_pexprBest; // best plan found at the end of search stage	
	CCost m_costBest; // cost of best plan found
	
	CTimerUser m_timer; // elapsed time
public:	
	CSearchStage(CXformSet *xform_set, ULONG ulTimeThreshold = gpos::ulong_max, CCost costThreshold = CCost(0.0)); // ctor	
	virtual ~CSearchStage(); // dtor
	
	void RestartTimer() { // restart timer if time threshold is not default indicating don't timeout Restart() is a costly method, so avoid calling unnecessarily
		if (m_time_threshold != gpos::ulong_max) m_timer.Restart();
	}

	// is search stage timed-out?
	// if threshold is gpos::ulong_max, its the default and we need not time out
	// ElapsedMS() is a costly method, so avoid calling unnecesarily
	BOOL FTimedOut() const{
		if (m_time_threshold == gpos::ulong_max)return false;
		return m_timer.ElapsedMS() > m_time_threshold;
	}
	
	ULONG UlElapsedTime() const { // return elapsed time (in millseconds) since timer was last restarted
		return m_timer.ElapsedMS();
	}

	BOOL FAchievedReqdCost() const{
		return (NULL != m_pexprBest && m_costBest <= m_cost_threshold);
	}

	void SetBestExpr(CExpression *pexpr); // set best plan found at the end of search stage
	static CSearchStageArray *PdrgpssDefault(CMemoryPool *mp); // generate default search strategy
};

for循环的判定条件实现的情景是当满足以下任何条件时，阶段终止: (1)发现成本低于成本阈值的计划，(2)超时发生，或(3)转换规则子集用尽。 FSearchTerminated函数的实现是NULL!=PssPrevious() && PssPrevious()->FAchieveReqdCost() // NULL != m_pexprBest && m_costBest <= m_cost_threshold，用于达到发现成本低于成本阈值的计划时终止其他策略的执行。PssPrevious函数返回上一步search stage，即(*m_search_stage_array)[m_ulCurrSearchStage - 1].

const ULONG ulSearchStages = m_search_stage_array->Size();
for (ULONG ul = 0; !FSearchTerminated() && ul < ulSearchStages; ul++)
  PssCurrent()->RestartTimer(); // (*m_search_stage_array)[m_ulCurrSearchStage]->RestartTimer()
  ...  
  CExpression *pexprPlan = m_pmemo->PexprExtractPlan(m_mp, m_pmemo->PgroupRoot(), m_pqc->Prpp(), m_search_stage_array->Size()); // extract best plan found at the end of current search stage
  PssCurrent()->SetBestExpr(pexprPlan);  
  FinalizeSearchStage(); // m_ulCurrSearchStage++; m_pmemo->ResetGroupStates();
}

在CJob相关子类中实现了状态机类CJobStateMachine，其执行函数FRun，会在执行时检查当前search stage是否已经超时。这也对应了第二种情况，即超时发生。