greenplumn CJoinOrder 源码

greenplumn CJoinOrder 代码

文件路径：/src/backend/gporca/libgpopt/include/gpopt/xforms/CJoinOrder.h

//---------------------------------------------------------------------------
//	Greenplum Database
//	Copyright (C) 2011 EMC Corp.
//
//	@filename:
//		CJoinOrder.h
//
//	@doc:
//		Join Order Generation
//---------------------------------------------------------------------------
#ifndef GPOPT_CJoinOrder_H
#define GPOPT_CJoinOrder_H

#include "gpos/base.h"
#include "gpos/io/IOstream.h"

#include "gpopt/operators/CExpression.h"
#include "gpopt/xforms/CXform.h"


// id for component created for relational nodes which are not
// the child of LOJ
#define NON_LOJ_DEFAULT_ID 0

namespace gpopt
{
using namespace gpos;

//---------------------------------------------------------------------------
//	@class:
//		CJoinOrder
//
//	@doc:
//		Helper class for creating compact join orders
//
//---------------------------------------------------------------------------
class CJoinOrder : public DbgPrintMixin<CJoinOrder>
{
public:
	enum EPosition
	{
		EpLeft = 0,	 // left child of LOJ
		EpRight,	 // right child of LOJ

		EpSentinel
	};

	//---------------------------------------------------------------------------
	//	@struct:
	//		SEdge
	//
	//	@doc:
	//		Struct to capture edge
	//
	//---------------------------------------------------------------------------
	struct SEdge : public CRefCount, public DbgPrintMixin<SEdge>
	{
		// cover of edge
		CBitSet *m_pbs;

		// associated conjunct
		CExpression *m_pexpr;

		// tracks if the associated join is a LOJ:
		// check the derived classes of CJoinOrder, but here is a high-level summary:
		// greedy, mincard: 0 means not an LOJ, 1 means this is an LOJ edge
		// DP: always 0
		// DPv2: 0 means inner join, >0: the index points to the entry in the array of ON predicates
		ULONG m_loj_num;

		// a flag to mark edge as used
		BOOL m_fUsed;

		// ctor
		SEdge(CMemoryPool *mp, CExpression *pexpr, ULONG loj_num);

		// dtor
		~SEdge() override;

		// print routine
		IOstream &OsPrint(IOstream &os) const;
	};


	//---------------------------------------------------------------------------
	//	@struct:
	//		SComponent
	//
	//	@doc:
	//		Struct to capture component
	//
	//---------------------------------------------------------------------------
	struct SComponent : public CRefCount, public DbgPrintMixin<SComponent>
	{
		// cover
		CBitSet *m_pbs;

		// set of edges associated with this component (stored as indexes into m_rgpedge array)
		CBitSet *m_edge_set;

		// associated expression
		CExpression *m_pexpr;

		// a flag to component edge as used
		BOOL m_fUsed;

		// for greedy and mincard:
		//
		// number indicating that this component contains
		// child of LOJ x, where x is a an incremental id
		// assigned to LOJ operators found in the NAry Join.
		// it is populated only if you choose to explore alternatives
		// to find a join order by evaluating joins of LOJ outer child
		// with other relational (non LOJ) operators in NAry tree.
		// Consider the below NAry join tree, which indicates the value
		// of m_parent_loj_id and m_position in {x, y} for the
		// component created for LOJ childs.
		// respectively
		//+--CLogicalNAryJoin
		//	|--CLogicalGet "t1"
		//	|--CLogicalLeftOuterJoin => LOJ 1
		//	|  |--CLogicalGet "t2" => {1, EpLeft}
		//	|  |--CLogicalGet "t3" => {1, EpRight}
		//	|  +--<Join Condition>
		//	+--<Join Condition>
		// For the above tree, outer child of LOJ can be combined to "t1",
		// i.e the resulting tree can be
		//	+--CLogicalLeftOuterJoin
		//		|--CLogicalInnerJoin => {1, EpLeft}, See note below.
		//		|	|--CLogicalGet "t1"
		//		|	|--CLogicalGet "t2"
		//		|	+--<Join Condition>
		//		|--CLogicalGet "t3" => {1, EpRight}
		//		+--<Join Condition>
		// Note: Component created for the join between t1 and t2 will have
		// m_parent_loj_id = 1 and m_position = EpLeft, as it
		// contains the left child of LOJ 1.
		// This helps to track that inner join between t1 and t2
		// must be the left child of LOJ with t3.
		//
		// for DPv2:
		//
		// We have n children, and some of them (other than the first) may be right children of
		// non-inner joins. These non-inner join right children are numbered 1 to j, and that
		// number is stored here in m_parent_loj_id. Example:
		// T0 join T1 join T2 left join T3 join T4 left join T5
		// The components for T0 ... T5 will have the following m_parent_loj_id values:
		// T0  T1  T2  T3  T4  T5
		//  0   0   0   1   0   2
		INT m_parent_loj_id;

		// enum indicating that this component contains left or
		// right child of the LOJ
		// (used for greedy and mincard, not used for DPv2)
		EPosition m_position;

		// ctor
		SComponent(CMemoryPool *mp, CExpression *expr,
				   INT parent_loj_id = NON_LOJ_DEFAULT_ID,
				   EPosition position = EpSentinel);

		// ctor
		SComponent(CExpression *expr, CBitSet *pbs, CBitSet *edge_set,
				   INT parent_loj_id = NON_LOJ_DEFAULT_ID,
				   EPosition position = EpSentinel);

		// dtor
		~SComponent() override;

		// get parent loj id
		INT
		ParentLojId() const
		{
			return m_parent_loj_id;
		}

		// what is or must be the position of this component with
		// respect to parent LOJ
		EPosition
		Position() const
		{
			return m_position;
		}

		// print routine
		IOstream &OsPrint(IOstream &os) const;
	};

protected:
	// memory pool
	CMemoryPool *m_mp;

	// edges
	SEdge **m_rgpedge;

	// number of edges
	ULONG m_ulEdges;

	// components
	SComponent **m_rgpcomp;

	// number of components
	ULONG m_ulComps;

	// should we include loj childs for evaluating
	// join order
	BOOL m_include_loj_childs;

	// compute cover of each edge
	void ComputeEdgeCover();

	// combine the two given components using applicable edges
	SComponent *PcompCombine(SComponent *comp1, SComponent *comp2);

	// derive stats on a given component
	virtual void DeriveStats(CExpression *pexpr);

	// mark edges used by expression
	void MarkUsedEdges(SComponent *comp);

	// add component to to component array
	void AddComponent(CMemoryPool *mp, CExpression *expr, INT loj_id,
					  EPosition position, INT comp_num);

private:
public:
	CJoinOrder(const CJoinOrder &) = delete;

	// ctor used in MinCard, Greedy and DP xforms
	CJoinOrder(CMemoryPool *mp, CExpressionArray *pdrgpexprComponents,
			   CExpressionArray *pdrgpexprConjuncts,
			   BOOL include_outer_join_childs);

	// ctor used in CXformExpandNAryJoinDPv2
	CJoinOrder(CMemoryPool *mp, CExpressionArray *pdrgpexprComponents,
			   CExpressionArray *innerJoinPredConjuncts,
			   CExpressionArray *onPreds, ULongPtrArray *childPredIndexes);

	// dtor
	virtual ~CJoinOrder();

	// print function
	IOstream &OsPrint(IOstream &) const;

	// is this a valid join combination
	static BOOL IsValidJoinCombination(SComponent *comp1, SComponent *comp2);

	// are these childs of the same LOJ
	static BOOL IsChildOfSameLOJ(SComponent *comp1, SComponent *comp2);

	virtual CXform::EXformId
	EOriginXForm() const
	{
		return CXform::ExfSentinel;
	}

};	// class CJoinOrder

}  // namespace gpopt

#endif	// !GPOPT_CJoinOrder_H

// EOF

相关信息

greenplumn 源码目录

相关文章

greenplumn CDecorrelator 源码

greenplumn CJoinOrderDP 源码

greenplumn CJoinOrderDPv2 源码

greenplumn CJoinOrderGreedy 源码

greenplumn CJoinOrderMinCard 源码

greenplumn CSubqueryHandler 源码

greenplumn CXform 源码

greenplumn CXformAntiSemiJoinAntiSemiJoinNotInSwap 源码

greenplumn CXformAntiSemiJoinAntiSemiJoinSwap 源码

greenplumn CXformAntiSemiJoinInnerJoinSwap 源码