src/backend/gpopt/translate/CQueryMutators.cpp

/*
 * 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.
 */

//---------------------------------------------------------------------------
//	@filename:
//		CQueryMutators.cpp
//
//	@doc:
//		Implementation of methods used during translating a GPDB Query object into a
//		DXL Tree
//
//	@owner:
//		raghav
//
//	@test:
//
//---------------------------------------------------------------------------

#include "postgres.h"

#include "nodes/plannodes.h"
#include "nodes/parsenodes.h"
#include "nodes/makefuncs.h"
#include "optimizer/walkers.h"

#include "gpopt/base/CUtils.h"
#include "gpopt/mdcache/CMDAccessor.h"
#include "gpopt/mdcache/CMDAccessorUtils.h"
#include "gpopt/translate/CQueryMutators.h"
#include "gpopt/translate/CTranslatorDXLToPlStmt.h"

#include "naucrates/md/IMDScalarOp.h"
#include "naucrates/md/IMDAggregate.h"
#include "naucrates/md/IMDTypeBool.h"

#include "gpopt/gpdbwrappers.h"

using namespace gpdxl;
using namespace gpmd;

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::FNeedsPrLNormalization
//
//	@doc:
//		Is the group by project list flat (contains only aggregates
//		and grouping columns)
//---------------------------------------------------------------------------
BOOL
CQueryMutators::FNeedsPrLNormalization
	(
	const Query *pquery
	)
{
	if (!pquery->hasAggs && NULL == pquery->groupClause)
	{
		return false;
	}

	SContextTLWalker ctxTLWalker(pquery->targetList, pquery->groupClause);

	const ULONG ulArity = gpdb::UlListLength(pquery->targetList);
	for (ULONG ul = 0; ul < ulArity; ul++)
	{
		TargetEntry *pte  = (TargetEntry*) gpdb::PvListNth(pquery->targetList, ul);

		if (FNeedsToFallback((Node *) pte->expr, &ctxTLWalker))
		{
			// TODO: raghav, Oct 14 2013, remove temporary fix (revert exception to assert) to avoid crash during algebrization
			GPOS_RAISE(gpdxl::ExmaDXL, gpdxl::ExmiQuery2DXLError, GPOS_WSZ_LIT("No attribute"));
		}

		// Normalize when there is an expression that is neither used for grouping
		// nor is an aggregate function
		if (!IsA(pte->expr, PercentileExpr) && !IsA(pte->expr, Aggref) && !IsA(pte->expr, GroupingFunc) && !CTranslatorUtils::FGroupingColumn( (Node*) pte->expr, pquery->groupClause, pquery->targetList))
		{
			return true;
		}
	}

	return false;
}


//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::FNeedsToFallback
//
//	@doc:
//		Fall back when the target list refers to a attribute which algebrizer
//		at this point cannot resolve
//---------------------------------------------------------------------------
BOOL
CQueryMutators::FNeedsToFallback
	(
	Node *pnode,
	void *pvCtx
	)
{
	if (NULL == pnode)
	{
		return false;
	}

	if (IsA(pnode, Const) || IsA(pnode, Aggref) || IsA(pnode, PercentileExpr) || IsA(pnode, GroupingFunc) || IsA(pnode, SubLink))
	{
		return false;
	}

	SContextTLWalker *pctx = (SContextTLWalker *) pvCtx;

	TargetEntry *pteFound = gpdb::PteMember(pnode, pctx->m_plTE);
	if (NULL != pteFound && CTranslatorUtils::FGroupingColumn( (Node *) pteFound->expr, pctx->m_groupClause, pctx->m_plTE))
	{
		return false;
	}

	if (IsA(pnode, SubLink))
	{
		return false;
	}

	if (IsA(pnode, Var))
	{
		Var *pvar = (Var *) pnode;
		if (0 == pvar->varlevelsup)
		{
			// if we reach a Var that was not a grouping column then there is an equivalent column
			// which the algebrizer at this point cannot resolve
			// example: consider two table r(a,b) and s(c,d) and the following query
			// SELECT a from r LEFT JOIN s on (r.a = s.c) group by r.a
			// In the query object, generated by the parse, the output columns refer to the output of
			// the left outer join while the grouping column refers to the base table column.
			// While r.a and a are equivalent, the algebrizer at this point cannot detect this.
			// Therefore, we fall back.
			return true;
		}

		return false;
	}

	return gpdb::FWalkExpressionTree(pnode, (PfFallback) CQueryMutators::FNeedsToFallback, pvCtx);
}


//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PqueryNormalizeGrpByPrL
//
//	@doc:
// 		Flatten expressions in project list to contain only aggregates and
//		grouping columns
//		ORGINAL QUERY:
//			SELECT * from r where r.a > (SELECT max(c) + min(d) FROM t where r.b = t.e)
// 		NEW QUERY:
//			SELECT * from r where r.a > (SELECT x1+x2 as x3
//										 FROM (SELECT max(c) as x2, min(d) as x2
//											   FROM t where r.b = t.e) t2)
//---------------------------------------------------------------------------
Query *
CQueryMutators::PqueryNormalizeGrpByPrL
	(
	IMemoryPool *pmp,
	CMDAccessor *pmda,
	const Query *pquery
	)
{
	Query *pqueryCopy = (Query *) gpdb::PvCopyObject(const_cast<Query*>(pquery));

	if (!FNeedsPrLNormalization(pqueryCopy))
	{
		return pqueryCopy;
	}

	Query *pqueryNew = PqueryConvertToDerivedTable(pqueryCopy, false /*fFixTargetList*/, true /*fFixHavingQual*/);
	gpdb::GPDBFree(pqueryCopy);

	GPOS_ASSERT(1 == gpdb::UlListLength(pqueryNew->rtable));
	Query *pqueryDrdTbl = (Query *) ((RangeTblEntry *) gpdb::PvListNth(pqueryNew->rtable, 0))->subquery;
	SContextGrpbyPlMutator ctxGbPrLMutator(pmp, pmda, pqueryDrdTbl, NULL);
	List *plTEcopy = (List*) gpdb::PvCopyObject(pqueryDrdTbl->targetList);
	ListCell *plc = NULL;

	// first normalize grouping columns
	ForEach (plc, plTEcopy)
	{
		TargetEntry *pte  = (TargetEntry*) lfirst(plc);
		GPOS_ASSERT(NULL != pte);

		if (CTranslatorUtils::FGroupingColumn(pte, pqueryDrdTbl->groupClause))
		{
			pte->expr = (Expr*) PnodeFixGrpCol( (Node*) pte->expr, pte, &ctxGbPrLMutator);
		}
	}

	plc = NULL;
	// normalize remaining project elements
	ForEach (plc, plTEcopy)
	{
		TargetEntry *pte  = (TargetEntry*) lfirst(plc);
		GPOS_ASSERT(NULL != pte);

		BOOL fGroupingCol = CTranslatorUtils::FGroupingColumn(pte, pqueryDrdTbl->groupClause);
		if (!fGroupingCol)
		{
			pte->expr = (Expr*) PnodeGrpbyPrLMutator( (Node*) pte->expr, &ctxGbPrLMutator);
			GPOS_ASSERT
				(
				(!IsA(pte->expr, Aggref) && !IsA(pte->expr, PercentileExpr)) && !IsA(pte->expr, GroupingFunc) &&
				"New target list entry should not contain any Aggrefs or PercentileExpr"
				);
		}
	}

	pqueryDrdTbl->targetList = ctxGbPrLMutator.m_plTENewGroupByQuery;
	pqueryNew->targetList = plTEcopy;

	ReassignSortClause(pqueryNew, pqueryDrdTbl);

	return pqueryNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeIncrementLevelsupMutator
//
//	@doc:
//		Increment any the query levels up of any outer reference by one
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeIncrementLevelsupMutator
	(
	Node *pnode,
	void *pvCtx
	)
{
	if (NULL == pnode)
	{
		return NULL;
	}

	SContextIncLevelsupMutator *pctxIncLvlMutator = (SContextIncLevelsupMutator *) pvCtx;

	if (IsA(pnode, Var))
	{
		Var *pvar = (Var *) gpdb::PvCopyObject(pnode);

		// Consider the following use case:
		//	ORGINAL QUERY:
		//		SELECT * from r where r.a > (SELECT max(c) + min(d)
		//									 FROM t where r.b = t.e)
		// NEW QUERY:
		//		SELECT * from r where r.a > (SELECT x1+x2 as x3
		//									 FROM (SELECT max(c) as x2, min(d) as x2
		//										   FROM t where r.b = t.e) t2)
		//
		// In such a scenario, we need increment the levels up for the
		// correlation variable r.b in the subquery by 1.

		if (pvar->varlevelsup > pctxIncLvlMutator->m_ulCurrLevelsUp)
		{
			pvar->varlevelsup++;
			return (Node *) pvar;
		}
		return (Node *) pvar;
	}

	if (IsA(pnode, CommonTableExpr))
	{
		CommonTableExpr *pcte = (CommonTableExpr *) gpdb::PvCopyObject(pnode);
		GPOS_ASSERT(IsA(pcte->ctequery, Query));

		Query *pqueryCte = (Query *) pcte->ctequery;

		pctxIncLvlMutator->m_ulCurrLevelsUp++;
		pcte->ctequery = PnodeIncrementLevelsupMutator((Node *) pqueryCte, pctxIncLvlMutator);
		pctxIncLvlMutator->m_ulCurrLevelsUp--;

		gpdb::GPDBFree(pqueryCte);

		return (Node *) pcte;
	}

	if (IsA(pnode, SubLink))
	{
		SubLink *psublink = (SubLink *) gpdb::PvCopyObject(pnode);
		GPOS_ASSERT(IsA(psublink->subselect, Query));

		Query *pquerySublink = (Query *) psublink->subselect;

		pctxIncLvlMutator->m_ulCurrLevelsUp++;
		psublink->subselect = PnodeIncrementLevelsupMutator( (Node *) pquerySublink, pctxIncLvlMutator);
		pctxIncLvlMutator->m_ulCurrLevelsUp--;
		gpdb::GPDBFree(pquerySublink);

		return (Node *) psublink;
	}

	if (IsA(pnode, TargetEntry) && 0 == pctxIncLvlMutator->m_ulCurrLevelsUp && !pctxIncLvlMutator->m_fFixTargetListTopLevel)
	{
		return (Node *) gpdb::PvCopyObject(pnode);
	}

	// recurse into query structure
	if (IsA(pnode, Query))
	{
		Query *pquery = gpdb::PqueryMutateQueryTree
								(
								(Query *) pnode,
								(Pfnode) CQueryMutators::PnodeIncrementLevelsupMutator,
								pctxIncLvlMutator,
								1 // flag -- do not mutate range table entries
								);

		// fix the outer reference in derived table entries
		List *plRtable = pquery->rtable;
		ListCell *plc = NULL;
		ForEach (plc, plRtable)
		{
			RangeTblEntry *prte = (RangeTblEntry *) lfirst(plc);

			if (RTE_SUBQUERY == prte->rtekind)
			{
				Query *pquerySubquery = prte->subquery;
				// since we did not walk inside derived tables
				pctxIncLvlMutator->m_ulCurrLevelsUp++;
				prte->subquery = (Query *) PnodeIncrementLevelsupMutator( (Node *) pquerySubquery, pctxIncLvlMutator);
				pctxIncLvlMutator->m_ulCurrLevelsUp--;
				gpdb::GPDBFree(pquerySubquery);
			}
		}

		return (Node *) pquery;
	}

	return gpdb::PnodeMutateExpressionTree(pnode, (Pfnode) CQueryMutators::PnodeIncrementLevelsupMutator, pvCtx);
}


//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeFixCTELevelsupMutator
//
//	@doc:
//		Increment any the query levels up of any CTE range table reference by one
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeFixCTELevelsupMutator
	(
	Node *pnode,
	void *pvCtx
	)
{
	if (NULL == pnode)
	{
		return NULL;
	}

	SContextIncLevelsupMutator *pctxinclvlmutator = (SContextIncLevelsupMutator *) pvCtx;

	// recurse into query structure
	if (IsA(pnode, Query))
	{
		Query *pquery = gpdb::PqueryMutateQueryTree
								(
								(Query *) pnode,
								(Pfnode) CQueryMutators::PnodeFixCTELevelsupMutator,
								pvCtx,
								1 // flag -- do not mutate range table entries
								);

		List *plRtable = pquery->rtable;
		ListCell *plc = NULL;
		ForEach (plc, plRtable)
		{
			RangeTblEntry *prte = (RangeTblEntry *) lfirst(plc);
			if (RTE_CTE == prte->rtekind  && FNeedsLevelsUpCorrection(pctxinclvlmutator, prte->ctelevelsup))
			{
				// fix the levels up for CTE range table entry when needed
				// the walker in GPDB does not walk range table entries of type CTE
				prte->ctelevelsup++;
			}

			if (RTE_SUBQUERY == prte->rtekind)
			{
				Query *pquerySubquery = prte->subquery;
				// since we did not walk inside derived tables
				pctxinclvlmutator->m_ulCurrLevelsUp++;
				prte->subquery = (Query *) PnodeFixCTELevelsupMutator( (Node *) pquerySubquery, pctxinclvlmutator);
				pctxinclvlmutator->m_ulCurrLevelsUp--;
				gpdb::GPDBFree(pquerySubquery);
			}
		}

		return (Node *) pquery;
	}

	if (IsA(pnode, CommonTableExpr))
	{
		CommonTableExpr *pcte = (CommonTableExpr *) gpdb::PvCopyObject(pnode);
		GPOS_ASSERT(IsA(pcte->ctequery, Query));

		Query *pqueryCte = (Query *) pcte->ctequery;
		pcte->ctequery = NULL;

		pctxinclvlmutator->m_ulCurrLevelsUp++;
		pcte->ctequery = PnodeFixCTELevelsupMutator((Node *) pqueryCte, pctxinclvlmutator);
		pctxinclvlmutator->m_ulCurrLevelsUp--;

		gpdb::GPDBFree(pqueryCte);

		return (Node *) pcte;
	}

	// recurse into a query attached to sublink
	if (IsA(pnode, SubLink))
	{
		SubLink *psublink = (SubLink *) gpdb::PvCopyObject(pnode);
		GPOS_ASSERT(IsA(psublink->subselect, Query));

		Query *pquerySublink = (Query *) psublink->subselect;
		psublink->subselect = NULL;

		pctxinclvlmutator->m_ulCurrLevelsUp++;
		psublink->subselect = PnodeFixCTELevelsupMutator((Node *) pquerySublink, pctxinclvlmutator);
		pctxinclvlmutator->m_ulCurrLevelsUp--;

		gpdb::GPDBFree(pquerySublink);

		return (Node *) psublink;
	}

	return gpdb::PnodeMutateExpressionTree(pnode, (Pfnode) CQueryMutators::PnodeFixCTELevelsupMutator, pctxinclvlmutator);
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::FCorrectCTELevelsup
//
//	@doc:
//		Check if the cte levels up is the expected query level
//---------------------------------------------------------------------------
BOOL
CQueryMutators::FNeedsLevelsUpCorrection
	(
	SContextIncLevelsupMutator *pctxinclvlmutator,
	Index idxCtelevelsup
	)
{
	// when converting the query to derived table, all references to cte defined at the current level
	// or above needs to be incremented
	return idxCtelevelsup >= pctxinclvlmutator->m_ulCurrLevelsUp;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeGrpbyPrLMutator
//
//	@doc:
// 		Traverse the project list of a groupby operator and extract all aggregate
//		functions in an arbitrarily complex project element
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeGrpbyPrLMutator
	(
	Node *pnode,
	void *pctx
	)
{
	if (NULL == pnode)
	{
		return NULL;
	}

	if (IsA(pnode, Const))
	{
		return (Node *) gpdb::PvCopyObject(pnode);
	}

	SContextGrpbyPlMutator *pctxGrpByMutator = (SContextGrpbyPlMutator *) pctx;

	if (IsA(pnode, Var) && pctxGrpByMutator->m_fAggregateArg)
	{
		// if we are mutating an aggregate argument do nothing since the aggregate will be place in the derived table's target list
		// fix any outer references in the grouping column expression or arguments of an aggregate
		return (Node *) PvarOuterReferenceIncrLevelsUp((Var*) pnode);
	}
	
	// if we find an aggregate or precentile expression then insert into the new derived table
	// and refer to it in the top-level query

	if (IsA(pnode, Aggref))
	{
		Aggref *paggrefOld = (Aggref*) pnode;
		Aggref *paggref = PaggrefFlatCopy(paggrefOld);
		paggref->agglevelsup = paggrefOld->agglevelsup;

		List *plArgsNew = NIL;
		ListCell *plc = NULL;

		BOOL fAggregate = pctxGrpByMutator->m_fAggregateArg;
		pctxGrpByMutator->m_fAggregateArg = true;

		ForEach (plc, paggrefOld->args)
		{
			Node *pnodeArg = (Node *) gpdb::PvCopyObject((Node*) lfirst(plc));
			GPOS_ASSERT(NULL != pnodeArg);
			// traverse each argument and fix levels up when needed
			plArgsNew = gpdb::PlAppendElement
						(
						plArgsNew,
						gpdb::PnodeMutateQueryOrExpressionTree
							(
							pnodeArg,
							(Pfnode) CQueryMutators::PnodeGrpbyPrLMutator,
							(void *) pctx,
							0 // flags -- mutate into cte-lists
							)
						);
		}
		pctxGrpByMutator->m_fAggregateArg = fAggregate;
		paggref->args = plArgsNew;

		const ULONG ulAttno = gpdb::UlListLength(pctxGrpByMutator->m_plTENewGroupByQuery) + 1;
		TargetEntry *pte = PteAggregateOrPercentileExpr(pctxGrpByMutator->m_pmp, pctxGrpByMutator->m_pmda, (Node *) paggref, ulAttno);

		// Add a new target entry to the query
		pctxGrpByMutator->m_plTENewGroupByQuery = gpdb::PlAppendElement(pctxGrpByMutator->m_plTENewGroupByQuery, pte);

		Var *pvarNew = gpdb::PvarMakeVar
						(
						1, // varno
						(AttrNumber) ulAttno,
						gpdb::OidExprType(pnode),
						gpdb::IExprTypeMod(pnode),
						0 // query levelsup
						);

		return (Node*) pvarNew;
	}

	if (IsA(pnode, PercentileExpr) || IsA(pnode, GroupingFunc))
	{
		Node *pnodeCopy = (Node *) gpdb::PvCopyObject(pnode);

		const ULONG ulAttno = gpdb::UlListLength(pctxGrpByMutator->m_plTENewGroupByQuery) + 1;
		TargetEntry *pte = PteAggregateOrPercentileExpr(pctxGrpByMutator->m_pmp, pctxGrpByMutator->m_pmda, pnodeCopy, ulAttno);

		// Add a new target entry to the query
		pctxGrpByMutator->m_plTENewGroupByQuery = gpdb::PlAppendElement(pctxGrpByMutator->m_plTENewGroupByQuery, pte);

		Var *pvarNew = gpdb::PvarMakeVar
								(
								1, // varno
								(AttrNumber) ulAttno,
								gpdb::OidExprType(pnode),
								gpdb::IExprTypeMod(pnode),
								0 // query levelsup
								);

		return (Node*) pvarNew;
	}

	if (!pctxGrpByMutator->m_fAggregateArg)
	{
		// if we find a target entry in the new derived table then return the appropriate var
		// else investigate it to see if it needs to be added to the new derived table

		TargetEntry *pteFound = gpdb::PteMember(pnode, pctxGrpByMutator->m_plTENewGroupByQuery);

		if (NULL != pteFound)
		{
			pteFound->resjunk = false;
			Var *pvarNew = gpdb::PvarMakeVar
					(
							1, // varno
							pteFound->resno,
							gpdb::OidExprType((Node*) pteFound->expr),
							gpdb::IExprTypeMod( (Node*) pteFound->expr),
							0 // query levelsup
					);

			return (Node*) pvarNew;
		}

		// if it is grouping column then we have already added it to the derived table
		// so merely refer to it in the top-level query
		TargetEntry *pteFoundNewDrvdTable = gpdb::PteMember(pnode, pctxGrpByMutator->m_plTENewGroupByQuery);
		if (NULL != pteFoundNewDrvdTable)
		{
			return (Node *) gpdb::PvarMakeVar
							(
							1, // varno
							(AttrNumber) pteFoundNewDrvdTable->resno,
							gpdb::OidExprType( (Node*) pteFoundNewDrvdTable->expr),
							gpdb::IExprTypeMod( (Node*) pteFoundNewDrvdTable->expr),
							0 // query levelsup
							);
		}
	}

	// do not traverse into sub queries as they will be inserted into top-level query as is
	if (IsA(pnode, SubLink))
	{
		return (Node *) gpdb::PvCopyObject(pnode);
	}

	return gpdb::PnodeMutateExpressionTree(pnode, (Pfnode) CQueryMutators::PnodeGrpbyPrLMutator, pctx);
}


//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeGrpColMutator
//
//	@doc:
// 		Mutate the grouping columns, fix levels up when necessary
//
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeGrpColMutator
	(
	Node *pnode,
	void *pctx
	)
{
	if (NULL == pnode)
	{
		return NULL;
	}

	if (IsA(pnode, Const))
	{
		return (Node *) gpdb::PvCopyObject(pnode);
	}

	SContextGrpbyPlMutator *pctxGrpByMutator = (SContextGrpbyPlMutator *) pctx;

	if (IsA(pnode, Var))
	{
		Var *pvarCopy = (Var *) gpdb::PvCopyObject(pnode);

		if (pvarCopy->varlevelsup > pctxGrpByMutator->m_ulCurrLevelsUp)
		{
			pvarCopy->varlevelsup++;
		}

		return (Node *) pvarCopy;
	}

	if (IsA(pnode, Aggref))
	{
		// merely fix the arguments of an aggregate
		Aggref *paggrefOld = (Aggref*) pnode;
		Aggref *paggref = PaggrefFlatCopy(paggrefOld);
		paggref->agglevelsup = paggrefOld->agglevelsup;

		List *plArgsNew = NIL;
		ListCell *plc = NULL;

		BOOL fAggregate = pctxGrpByMutator->m_fAggregateArg;
		pctxGrpByMutator->m_fAggregateArg = true;

		ForEach (plc, paggrefOld->args)
		{
			Node *pnodeArg = (Node *) gpdb::PvCopyObject((Node*) lfirst(plc));
			GPOS_ASSERT(NULL != pnodeArg);
			// traverse each argument and fix levels up when needed
			plArgsNew = gpdb::PlAppendElement
						(
						plArgsNew,
						gpdb::PnodeMutateQueryOrExpressionTree
							(
							pnodeArg,
							(Pfnode) CQueryMutators::PnodeGrpColMutator,
							(void *) pctxGrpByMutator,
							0 // flags -- mutate into cte-lists
							)
						);
		}
		pctxGrpByMutator->m_fAggregateArg = fAggregate;
		paggref->args = plArgsNew;

		return (Node*) paggref;
	}

	if (IsA(pnode, PercentileExpr) || IsA(pnode, GroupingFunc))
	{
		return (Node *) gpdb::PvCopyObject(pnode);
	}

	if (IsA(pnode, SubLink))
	{
		SubLink *psublinkOld = (SubLink *) pnode;

		SubLink *psublinkNew = MakeNode(SubLink);
		psublinkNew->subLinkType = psublinkOld->subLinkType;
		psublinkNew->location = psublinkOld->location;
		psublinkNew->operName = (List *) gpdb::PvCopyObject(psublinkOld->operName);

		psublinkNew->testexpr =	gpdb::PnodeMutateQueryOrExpressionTree
										(
										psublinkOld->testexpr,
										(Pfnode) CQueryMutators::PnodeGrpColMutator,
										(void *) pctxGrpByMutator,
										0 // flags -- mutate into cte-lists
										);
		pctxGrpByMutator->m_ulCurrLevelsUp++;

		GPOS_ASSERT(IsA(psublinkOld->subselect, Query));

		psublinkNew->subselect = gpdb::PnodeMutateQueryOrExpressionTree
										(
										psublinkOld->subselect,
										(Pfnode) CQueryMutators::PnodeGrpColMutator,
										(void *) pctxGrpByMutator,
										0 // flags -- mutate into cte-lists
										);

		pctxGrpByMutator->m_ulCurrLevelsUp--;

		return (Node *) psublinkNew;
	}

	if (IsA(pnode, CommonTableExpr))
	{
		CommonTableExpr *pcte = (CommonTableExpr *) gpdb::PvCopyObject(pnode);
		pctxGrpByMutator->m_ulCurrLevelsUp++;

		GPOS_ASSERT(IsA(pcte->ctequery, Query));

		pcte->ctequery = gpdb::PnodeMutateQueryOrExpressionTree
									(
									pcte->ctequery,
									(Pfnode) CQueryMutators::PnodeGrpColMutator,
									(void *) pctxGrpByMutator,
									0 // flags --- mutate into cte-lists
									);

		pctxGrpByMutator->m_ulCurrLevelsUp--;
		return (Node *) pcte;
	}

	// recurse into query structure
	if (IsA(pnode, Query))
	{
		Query *pquery = gpdb::PqueryMutateQueryTree
								(
								(Query *) pnode,
								(Pfnode) CQueryMutators::PnodeGrpColMutator,
								pctxGrpByMutator,
								1 // flag -- do not mutate range table entries
								);

		// fix the outer reference in derived table entries
		List *plRtable = pquery->rtable;
		ListCell *plc = NULL;
		ForEach (plc, plRtable)
		{
			RangeTblEntry *prte = (RangeTblEntry *) lfirst(plc);

			if (RTE_SUBQUERY == prte->rtekind)
			{
				Query *pquerySubquery = prte->subquery;
				// since we did not walk inside derived tables
				pctxGrpByMutator->m_ulCurrLevelsUp++;
				prte->subquery = (Query *) PnodeGrpColMutator( (Node *) pquerySubquery, pctxGrpByMutator);
				pctxGrpByMutator->m_ulCurrLevelsUp--;
				gpdb::GPDBFree(pquerySubquery);
			}
		}

		return (Node *) pquery;
	}

	return gpdb::PnodeMutateExpressionTree(pnode, (Pfnode) CQueryMutators::PnodeGrpColMutator, pctx);
}


//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeFixGrpCol
//
//	@doc:
// 		Mutate the grouping columns, fix levels up when necessary
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeFixGrpCol
	(
	Node *pnode,
	TargetEntry *pteOriginal,
	SContextGrpbyPlMutator *pctx
	)
{
	GPOS_ASSERT(NULL != pnode);

	ULONG ulArity = gpdb::UlListLength(pctx->m_plTENewGroupByQuery) + 1;

	// fix any outer references in the grouping column expression
	Node *pnodeExpr = (Node *) PnodeGrpColMutator( pnode, pctx);

	CHAR* szName = CQueryMutators::SzTEName(pteOriginal,pctx->m_pquery);
	TargetEntry *pteNew = gpdb::PteMakeTargetEntry((Expr*) pnodeExpr, (AttrNumber) ulArity, szName, false /*resjunk */);

	pteNew->ressortgroupref = pteOriginal->ressortgroupref;
	pteNew->resjunk = false;

	pctx->m_plTENewGroupByQuery = gpdb::PlAppendElement(pctx->m_plTENewGroupByQuery, pteNew);

	Var *pvarNew = gpdb::PvarMakeVar
			(
					1, // varno
					(AttrNumber) ulArity,
					gpdb::OidExprType( (Node*) pteOriginal->expr),
					gpdb::IExprTypeMod( (Node*) pteOriginal->expr),
					0 // query levelsup
			);

	return (Node*) pvarNew;
}


//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PteAggregateOrPercentileExpr
//
//	@doc:
// 		Return a target entry for an aggregate or percentile expression
//---------------------------------------------------------------------------
TargetEntry *
CQueryMutators::PteAggregateOrPercentileExpr
	(
	IMemoryPool *pmp,
	CMDAccessor *pmda,
	Node *pnode,
	ULONG ulAttno
	)
{
	GPOS_ASSERT(IsA(pnode, PercentileExpr) || IsA(pnode, Aggref) || IsA(pnode, GroupingFunc));

	// get the function/aggregate name
	CHAR *szName = NULL;
	if (IsA(pnode, PercentileExpr))
	{
		PercentileExpr *ppercentile = (PercentileExpr*) pnode;

		if (PERC_MEDIAN == ppercentile->perckind)
		{
			szName = CTranslatorUtils::SzFromWsz(GPOS_WSZ_LIT("Median"));
		}
		else if (PERC_CONT == ppercentile->perckind)
		{
			szName = CTranslatorUtils::SzFromWsz(GPOS_WSZ_LIT("Cont"));
		}
		else
		{
			GPOS_ASSERT(PERC_DISC == ppercentile->perckind);
			szName = CTranslatorUtils::SzFromWsz(GPOS_WSZ_LIT("Disc"));
		}
	}
	else if (IsA(pnode, GroupingFunc))
	{
		szName = CTranslatorUtils::SzFromWsz(GPOS_WSZ_LIT("grouping"));
	}
	else
	{
		Aggref *paggref = (Aggref*) pnode;

		CMDIdGPDB *pmdidAgg = CTranslatorUtils::PmdidWithVersion(pmp, paggref->aggfnoid);
		const IMDAggregate *pmdagg = pmda->Pmdagg(pmdidAgg);
		pmdidAgg->Release();

		const CWStringConst *pstr = pmdagg->Mdname().Pstr();
		szName = CTranslatorUtils::SzFromWsz(pstr->Wsz());
	}
	GPOS_ASSERT(NULL != szName);

	return gpdb::PteMakeTargetEntry((Expr*) pnode, (AttrNumber) ulAttno, szName, false);
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeHavingQualMutator
//
//	@doc:
// 		This mutator function checks to see if the current node is an AggRef
//		or a correlated variable from the derived table.
//		If it is an Aggref:
//			Then replaces it with the appropriate attribute from the top-level query.
//		If it is a correlated Var:
//			Then replaces it with a attribute from the top-level query.
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeHavingQualMutator
	(
	Node *pnode,
	void *pctx
	)
{
	if (NULL == pnode)
	{
		return NULL;
	}

	if (IsA(pnode, Const))
	{
		return (Node *) gpdb::PvCopyObject(pnode);
	}

	SContextHavingQualMutator *pctxHavingQualMutator = (SContextHavingQualMutator *) pctx;

	// check to see if the node is in the target list of the derived table.
	// check if we have the corresponding pte entry in derived tables target list
	if (0 == pctxHavingQualMutator->m_ulCurrLevelsUp)
	{
		if (IsA(pnode, Var) && pctxHavingQualMutator->m_fAggregateArg)
		{
			// fix outer references used in the aggregates
			return (Node *) PvarOuterReferenceIncrLevelsUp((Var*) pnode);
		}

		// check if an entry already exists, if so no need for duplicate
		Node *pnodeFound = PnodeFind(pnode, pctxHavingQualMutator);
		if (NULL != pnodeFound)
		{
			return pnodeFound;
		}

		if (IsA(pnode, PercentileExpr) || IsA(pnode, GroupingFunc))
		{
			// create a new entry in the derived table and return its corresponding var
			Node *pnodeCopy = (Node*) gpdb::PvCopyObject(pnode);
			return (Node *) PvarInsertIntoDerivedTable(pnodeCopy, pctxHavingQualMutator);
		}
	}

	if (IsA(pnode, Aggref))
	{
		Aggref *paggrefOld = (Aggref *) pnode;
		if (paggrefOld->agglevelsup == pctxHavingQualMutator->m_ulCurrLevelsUp)
		{
			Aggref *paggrefNew = PaggrefFlatCopy(paggrefOld);
			
			BOOL fAggregateOld = pctxHavingQualMutator->m_fAggregateArg;
			ULONG ulAggregateLevelUp = pctxHavingQualMutator->m_ulAggregateLevelUp;

			pctxHavingQualMutator->m_fAggregateArg = true;
			pctxHavingQualMutator->m_ulAggregateLevelUp = paggrefOld->agglevelsup;

			List *plargsNew = NIL;
			ListCell *plc = NULL;

			ForEach (plc, paggrefOld->args)
			{
				Node *pnodeArg = (Node*) lfirst(plc);
				GPOS_ASSERT(NULL != pnodeArg);
				// traverse each argument and fix levels up when needed
				plargsNew = gpdb::PlAppendElement
									(
									plargsNew,
									gpdb::PnodeMutateQueryOrExpressionTree
											(
											pnodeArg,
											(Pfnode) CQueryMutators::PnodeHavingQualMutator,
											(void *) pctxHavingQualMutator,
											0 // mutate into cte-lists
											)
									);
			}
			paggrefNew->args = plargsNew;
			pctxHavingQualMutator->m_fAggregateArg = fAggregateOld;
			pctxHavingQualMutator->m_ulAggregateLevelUp = ulAggregateLevelUp;

			// check if an entry already exists, if so no need for duplicate
			Node *pnodeFound = PnodeFind((Node*) paggrefNew, pctxHavingQualMutator);
			if (NULL != pnodeFound)
			{
				return pnodeFound;
			}

			// create a new entry in the derived table and return its corresponding var
			return (Node *) PvarInsertIntoDerivedTable((Node *) paggrefNew, pctxHavingQualMutator);
		}
	}

	if (IsA(pnode, Var))
	{
		Var *pvar = (Var *) gpdb::PvCopyObject(pnode);
		if (pvar->varlevelsup == pctxHavingQualMutator->m_ulCurrLevelsUp)
		{
			// process outer references
			if (pvar->varlevelsup == pctxHavingQualMutator->m_ulAggregateLevelUp)
			{
				// an argument of an outer aggregate
				pvar->varlevelsup = 0;

				return (Node *) pvar;
			}

			pvar->varlevelsup = 0;
			TargetEntry *pteFound = gpdb::PteMember( (Node*) pvar, pctxHavingQualMutator->m_plTENewGroupByQuery);

			if (NULL == pteFound)
			{
				// Consider two table r(a,b) and s(c,d) and the following query
				// SELECT 1 from r LEFT JOIN s on (r.a = s.c) group by r.a having count(*) > a
				// The having clause refers to the output of the left outer join while the
				// grouping column refers to the base table column.
				// While r.a and a are equivalent, the algebrizer at this point cannot detect this.
				// Therefore, pteFound will be NULL and we fall back.

				pctxHavingQualMutator->m_fFallbackToPlanner = true;
				return NULL;
			}

			pvar->varlevelsup = pctxHavingQualMutator->m_ulCurrLevelsUp;
			pvar->varno = 1;
			pvar->varattno = pteFound->resno;
			pteFound->resjunk = false;

			return (Node*) pvar;
		}
		return (Node *) pvar;
	}

	if (IsA(pnode, CommonTableExpr))
	{
		CommonTableExpr *pcte = (CommonTableExpr *) gpdb::PvCopyObject(pnode);
		pctxHavingQualMutator->m_ulCurrLevelsUp++;

		GPOS_ASSERT(IsA(pcte->ctequery, Query));

		pcte->ctequery = gpdb::PnodeMutateQueryOrExpressionTree
									(
									pcte->ctequery,
									(Pfnode) CQueryMutators::PnodeHavingQualMutator,
									(void *) pctxHavingQualMutator,
									0 // flags --- mutate into cte-lists
									);

		pctxHavingQualMutator->m_ulCurrLevelsUp--;
		return (Node *) pcte;
	}

	if (IsA(pnode, SubLink))
	{
		SubLink *psublinkOld = (SubLink *) pnode;

		SubLink *psublinkNew = MakeNode(SubLink);
		psublinkNew->subLinkType = psublinkOld->subLinkType;
		psublinkNew->location = psublinkOld->location;
		psublinkNew->operName = (List *) gpdb::PvCopyObject(psublinkOld->operName);

		psublinkNew->testexpr =	gpdb::PnodeMutateQueryOrExpressionTree
										(
										psublinkOld->testexpr,
										(Pfnode) CQueryMutators::PnodeHavingQualMutator,
										(void *) pctxHavingQualMutator,
										0 // flags -- mutate into cte-lists
										);
		pctxHavingQualMutator->m_ulCurrLevelsUp++;

		GPOS_ASSERT(IsA(psublinkOld->subselect, Query));

		psublinkNew->subselect = gpdb::PnodeMutateQueryOrExpressionTree
										(
										psublinkOld->subselect,
										(Pfnode) CQueryMutators::PnodeHavingQualMutator,
										(void *) pctxHavingQualMutator,
										0 // flags -- mutate into cte-lists
										);

		pctxHavingQualMutator->m_ulCurrLevelsUp--;

		return (Node *) psublinkNew;
	}
	
	return gpdb::PnodeMutateExpressionTree(pnode, (Pfnode) CQueryMutators::PnodeHavingQualMutator, pctxHavingQualMutator);
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PvarInsertIntoDerivedTable
//
//	@doc:
//		Create a new entry in the derived table and return its corresponding var
//---------------------------------------------------------------------------
Var *
CQueryMutators::PvarInsertIntoDerivedTable
	(
	Node *pnode,
	SContextHavingQualMutator *context
	)
{
	GPOS_ASSERT(NULL != pnode);
	GPOS_ASSERT(NULL != context);
	GPOS_ASSERT(IsA(pnode, PercentileExpr) || IsA(pnode, Aggref) || IsA(pnode, GroupingFunc));

	const ULONG ulAttno = gpdb::UlListLength(context->m_plTENewGroupByQuery) + 1;
	TargetEntry *pte = PteAggregateOrPercentileExpr(context->m_pmp, context->m_pmda, (Node *) pnode, ulAttno);
	context->m_plTENewGroupByQuery = gpdb::PlAppendElement(context->m_plTENewGroupByQuery, pte);

	Var *pvarNew = gpdb::PvarMakeVar
					(
					1, // varno
					ulAttno,
					gpdb::OidExprType((Node*) pnode),
					gpdb::IExprTypeMod((Node*) pnode),
					context->m_ulCurrLevelsUp
					);

	return pvarNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeFind
//
//	@doc:
//		Check if a matching entry already exists in the list of target
//		entries, if yes return its corresponding var, otherwise return NULL
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeFind
	(
	Node *pnode,
	SContextHavingQualMutator *context
	)
{
	GPOS_ASSERT(NULL != pnode);
	GPOS_ASSERT(NULL != context);
	
	TargetEntry *pteFound = gpdb::PteMember(pnode, context->m_plTENewGroupByQuery);
	if (NULL != pteFound)
	{
		gpdb::GPDBFree(pnode);
		Var *pvarNew = gpdb::PvarMakeVar
						(
						1, // varno
						pteFound->resno,
						gpdb::OidExprType( (Node*) pteFound->expr),
						gpdb::IExprTypeMod( (Node*) pteFound->expr),
						context->m_ulCurrLevelsUp
						);

		pteFound->resjunk = false;
		return (Node*) pvarNew;
	}

	return NULL;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PaggrefFlatCopy
//
//	@doc:
//		Make a copy of the aggref (minus the arguments)
//---------------------------------------------------------------------------
Aggref *
CQueryMutators::PaggrefFlatCopy
	(
	Aggref *paggrefOld
	)
{
	Aggref *paggrefNew = MakeNode(Aggref);

	paggrefNew->aggfnoid = paggrefOld->aggfnoid;
	paggrefNew->aggdistinct = paggrefOld->aggdistinct;
	paggrefNew->agglevelsup = 0;
	paggrefNew->location = paggrefOld->location;
	paggrefNew->aggtype = paggrefOld->aggtype;
	paggrefNew->aggstage = paggrefOld->aggstage;
	paggrefNew->aggstar = paggrefOld->aggstar;

	return paggrefNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PvarOuterReferenceIncrLevelsUp
//
//	@doc:
//		Increment the levels up of outer references
//---------------------------------------------------------------------------
Var *
CQueryMutators::PvarOuterReferenceIncrLevelsUp
	(
	Var *pvar
	)
{
	GPOS_ASSERT(NULL != pvar);

	Var *pvarCopy = (Var *) gpdb::PvCopyObject(pvar);
	if (0 != pvarCopy->varlevelsup)
	{
		pvarCopy->varlevelsup++;
	}

	return pvarCopy;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PqueryNormalizeHaving
//
//	@doc:
//		Pull up having qual into a select and fix correlated references
//		to the top-level query
//---------------------------------------------------------------------------
Query *
CQueryMutators::PqueryNormalizeHaving
	(
	IMemoryPool *pmp,
	CMDAccessor *pmda,
	const Query *pquery
	)
{
	Query *pqueryCopy = (Query *) gpdb::PvCopyObject(const_cast<Query*>(pquery));

	if (NULL == pquery->havingQual)
	{
		return pqueryCopy;
	}

	Query *pqueryNew = PqueryConvertToDerivedTable(pqueryCopy, true /*fFixTargetList*/, false /*fFixHavingQual*/);
	gpdb::GPDBFree(pqueryCopy);

	RangeTblEntry *prte = ((RangeTblEntry *) gpdb::PvListNth(pqueryNew->rtable, 0));
	Query *pqueryDrdTbl = (Query *) prte->subquery;

	// Add all necessary target list entries of subquery
	// into the target list of the RTE as well as the new top most query
	ListCell *plc = NULL;
	ULONG ulTECount = 1;
	ForEach (plc, pqueryDrdTbl->targetList)
	{
		TargetEntry *pte  = (TargetEntry*) lfirst(plc);
		GPOS_ASSERT(NULL != pte);

		// Add to the target lists:
		// 	(1) All grouping / sorting columns even if they do not appear in the subquery output (resjunked)
		//	(2) All non-resjunked target list entries
		if (CTranslatorUtils::FGroupingColumn(pte, pqueryDrdTbl->groupClause) ||
			CTranslatorUtils::FSortingColumn(pte, pqueryDrdTbl->sortClause) || !pte->resjunk)
		{
			TargetEntry *pteNew = Pte(pte, ulTECount);
			pqueryNew->targetList = gpdb::PlAppendElement(pqueryNew->targetList, pteNew);
			// Ensure that such target entries is not suppressed in the target list of the RTE
			// and has a name
			pte->resname = SzTEName(pte, pqueryDrdTbl);
			pte->resjunk = false;
			pteNew->ressortgroupref = pte->ressortgroupref;

			ulTECount++;
		}
	}

	SContextHavingQualMutator ctxHavingQualMutator(pmp, pmda, ulTECount, pqueryDrdTbl->targetList);

	// fix outer references in the qual
	pqueryNew->jointree->quals = PnodeHavingQualMutator(pqueryDrdTbl->havingQual, &ctxHavingQualMutator);

	if (ctxHavingQualMutator.m_fFallbackToPlanner)
	{
		// TODO: raghav, Oct 14 2013, remove temporary fix (revert exception to assert) to avoid crash during algebrization
		GPOS_RAISE(gpdxl::ExmaDXL, gpdxl::ExmiQuery2DXLError, GPOS_WSZ_LIT("No attribute"));
	}

	pqueryDrdTbl->havingQual = NULL;

	ReassignSortClause(pqueryNew, prte->subquery);

	if (!prte->subquery->hasAggs && NIL == prte->subquery->groupClause)
	{
		// if the derived table has no grouping columns or aggregates then the
		// subquery is equivalent to select XXXX FROM CONST-TABLE 
		// (where XXXX is the original subquery's target list)

		Query *pqueryNewSubquery = MakeNode(Query);

		pqueryNewSubquery->commandType = CMD_SELECT;
		pqueryNewSubquery->targetList = NIL;

		pqueryNewSubquery->hasAggs = false;
		pqueryNewSubquery->hasWindFuncs = false;
		pqueryNewSubquery->hasSubLinks = false;

		ListCell *plc = NULL;
		ForEach (plc, prte->subquery->targetList)
		{
			TargetEntry *pte  = (TargetEntry*) lfirst(plc);
			GPOS_ASSERT(NULL != pte);

			GPOS_ASSERT(!pte->resjunk);
			
			pqueryNewSubquery->targetList =  gpdb::PlAppendElement
													(
													pqueryNewSubquery->targetList,
													(TargetEntry *) gpdb::PvCopyObject(const_cast<TargetEntry*>(pte))
													);
		}

		gpdb::GPDBFree(prte->subquery);

		prte->subquery = pqueryNewSubquery;
		prte->subquery->jointree = MakeNode(FromExpr);
		prte->subquery->groupClause = NIL;
		prte->subquery->sortClause = NIL;
		prte->subquery->windowClause = NIL;
	}

	return pqueryNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PqueryNormalize
//
//	@doc:
//		Normalize queries with having and group by clauses
//---------------------------------------------------------------------------
Query *
CQueryMutators::PqueryNormalize
	(
	IMemoryPool *pmp,
	CMDAccessor *pmda,
	const Query *pquery,
	ULONG ulQueryLevel
	)
{
	// flatten join alias vars defined at the current level of the query
	Query *pqueryResolveJoinVarReferences = gpdb::PqueryFlattenJoinAliasVar(const_cast<Query*>(pquery), ulQueryLevel);

	// eliminate distinct clause
	Query *pqueryEliminateDistinct = CQueryMutators::PqueryEliminateDistinctClause(pqueryResolveJoinVarReferences);
	GPOS_ASSERT(NULL == pqueryEliminateDistinct->distinctClause);
	gpdb::GPDBFree(pqueryResolveJoinVarReferences);

	// fix window frame edge boundary
	Query *pqueryFixedWindowFrameEdge = CQueryMutators::PqueryFixWindowFrameEdgeBoundary(pqueryEliminateDistinct);
	gpdb::GPDBFree(pqueryEliminateDistinct);

	// normalize window operator's project list
	Query *pqueryWindowPlNormalized = CQueryMutators::PqueryNormalizeWindowPrL(pmp, pmda, pqueryFixedWindowFrameEdge);
	gpdb::GPDBFree(pqueryFixedWindowFrameEdge);

	// pull-up having quals into a select
	Query *pqueryHavingNormalized = CQueryMutators::PqueryNormalizeHaving(pmp, pmda, pqueryWindowPlNormalized);
	GPOS_ASSERT(NULL == pqueryHavingNormalized->havingQual);
	gpdb::GPDBFree(pqueryWindowPlNormalized);

	// normalize the group by project list
	Query *pqueryNew = CQueryMutators::PqueryNormalizeGrpByPrL(pmp, pmda, pqueryHavingNormalized);
	gpdb::GPDBFree(pqueryHavingNormalized);

	return pqueryNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::Pte
//
//	@doc:
//		Given an Target list entry in the derived table, create a new
//		TargetEntry to be added to the top level query. This function allocates
//		memory
//---------------------------------------------------------------------------
TargetEntry *
CQueryMutators::Pte
	(
	TargetEntry *pteOld,
	ULONG ulVarAttno
	)
{
	Var *pvarNew = gpdb::PvarMakeVar
							(
							1,
							(AttrNumber) ulVarAttno,
							gpdb::OidExprType( (Node*) pteOld->expr),
							gpdb::IExprTypeMod( (Node*) pteOld->expr),
							0 // query levelsup
							);

	TargetEntry *pteNew = gpdb::PteMakeTargetEntry((Expr*) pvarNew, (AttrNumber) ulVarAttno, pteOld->resname, pteOld->resjunk);

	return pteNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::SzTEName
//
//	@doc:
//		Return the column name of the target list entry
//---------------------------------------------------------------------------
CHAR *
CQueryMutators::SzTEName
	(
	TargetEntry *pte,
	Query *pquery
	)
{
	if (NULL != pte->resname)
	{
		return pte->resname;
	}

	// Since a resjunked target list entry will not have a column name create a dummy column name
	CWStringConst strUnnamedCol(GPOS_WSZ_LIT("?column?"));

	return CTranslatorUtils::SzFromWsz(strUnnamedCol.Wsz());
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PqueryConvertToDerivedTable
//
//	@doc:
//		Converts query into a derived table and return the new top-level query
//---------------------------------------------------------------------------
Query *
CQueryMutators::PqueryConvertToDerivedTable
	(
	const Query *pquery,
	BOOL fFixTargetList,
	BOOL fFixHavingQual
	)
{
	Query *pqueryCopy = (Query *) gpdb::PvCopyObject(const_cast<Query*>(pquery));

	// fix any outer references
	SContextIncLevelsupMutator ctxIncLvlMutator(0, fFixTargetList);

	Node *pnodeHavingQual = NULL;
	if (!fFixHavingQual)
	{
		pnodeHavingQual = pqueryCopy->havingQual;
		pqueryCopy->havingQual = NULL;
	}

	// fix outer references
	Query *pqueryDrvd = (Query *) PnodeIncrementLevelsupMutator((Node*) pqueryCopy, &ctxIncLvlMutator);
	gpdb::GPDBFree(pqueryCopy);

	// fix the CTE levels up -- while the old query is converted into a derived table, its cte list
	// is re-assigned to the new top-level query. The references to the ctes listed in the old query
	// as well as those listed before the current query level are accordingly adjusted in the new
	// derived table.
	List *plCteOriginal = pqueryDrvd->cteList;
	pqueryDrvd->cteList = NIL;

	SContextIncLevelsupMutator ctxinclvlmutator(0 /*starting level */, fFixTargetList);

	Query *pqueryDrvdNew  = (Query *) PnodeFixCTELevelsupMutator( (Node *) pqueryDrvd, &ctxinclvlmutator);
	gpdb::GPDBFree(pqueryDrvd);
	pqueryDrvd = pqueryDrvdNew;

	// create a range table entry for the query node
	RangeTblEntry *prte = MakeNode(RangeTblEntry);
	prte->rtekind = RTE_SUBQUERY;

	prte->subquery = pqueryDrvd;
	prte->inFromCl = true;
	prte->subquery->cteList = NIL;

	if (NULL != pnodeHavingQual)
	{
		pqueryDrvd->havingQual = pnodeHavingQual;
	}

	// create a new range table reference for the new RTE
	RangeTblRef *prtref = MakeNode(RangeTblRef);
	prtref->rtindex = 1;

	// intoClause, if not null, must be set on the top query, not on the derived table
	IntoClause *origIntoClause = pqueryDrvd->intoClause;
	pqueryDrvd->intoClause = NULL;
	struct GpPolicy* origIntoPolicy = pqueryDrvd->intoPolicy;
	pqueryDrvd->intoPolicy = NULL;

	// create a new top-level query with the new RTE in its from clause
	Query *pqueryNew = MakeNode(Query);
	pqueryNew->cteList = plCteOriginal;
	pqueryNew->hasAggs = false;
	pqueryNew->rtable = gpdb::PlAppendElement(pqueryNew->rtable, prte);
	pqueryNew->intoClause = origIntoClause;
	pqueryNew->intoPolicy = origIntoPolicy;

	FromExpr *pfromexpr = MakeNode(FromExpr);
	pfromexpr->quals = NULL;
	pfromexpr->fromlist = gpdb::PlAppendElement(pfromexpr->fromlist, prtref);

	pqueryNew->jointree = pfromexpr;
	pqueryNew->commandType = CMD_SELECT;

	GPOS_ASSERT(1 == gpdb::UlListLength(pqueryNew->rtable));
	return pqueryNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PqueryEliminateDistinctClause
//
//	@doc:
//		Eliminate distinct columns by translating it into a grouping columns
//---------------------------------------------------------------------------
Query *
CQueryMutators::PqueryEliminateDistinctClause
	(
	const Query *pquery
	)
{
	if (0 == gpdb::UlListLength(pquery->distinctClause))
	{
		return (Query*) gpdb::PvCopyObject(const_cast<Query*>(pquery));
	}

	// create a derived table out of the previous query
	Query *pqueryNew = PqueryConvertToDerivedTable(pquery, true /*fFixTargetList*/, true /*fFixHavingQual*/);

	GPOS_ASSERT(1 == gpdb::UlListLength(pqueryNew->rtable));
	Query *pqueryDrdTbl = (Query *) ((RangeTblEntry *) gpdb::PvListNth(pqueryNew->rtable, 0))->subquery;

	ReassignSortClause(pqueryNew, pqueryDrdTbl);

	pqueryNew->targetList = NIL;
	List *plTE = pqueryDrdTbl->targetList;
	ListCell *plc = NULL;

	// build the project list of the new top-level query
	ForEach (plc, plTE)
	{
		ULONG ulResNo = gpdb::UlListLength(pqueryNew->targetList) + 1;
		TargetEntry *pte  = (TargetEntry*) lfirst(plc);
		GPOS_ASSERT(NULL != pte);

		if (!pte->resjunk)
		{
			// create a new target entry that points to the corresponding entry in the derived table
			Var *pvarNew = gpdb::PvarMakeVar
									(
									1,
									pte->resno,
									gpdb::OidExprType((Node*) pte->expr),
									gpdb::IExprTypeMod((Node*) pte->expr),
									0 // query levels up
									);
			TargetEntry *pteNew= gpdb::PteMakeTargetEntry((Expr*) pvarNew, (AttrNumber) ulResNo, pte->resname, false);

			pteNew->ressortgroupref =  pte->ressortgroupref;
			pqueryNew->targetList = gpdb::PlAppendElement(pqueryNew->targetList, pteNew);
		}

		if (0 < pte->ressortgroupref &&
			!CTranslatorUtils::FGroupingColumn(pte, pqueryDrdTbl->groupClause) &&
			!CTranslatorUtils::FWindowSpec(pte, pqueryDrdTbl->windowClause))
		{
			// initialize the ressortgroupref of target entries not used in the grouping clause
			 pte->ressortgroupref = 0;
		}
	}

	if (gpdb::UlListLength(pqueryNew->targetList) != gpdb::UlListLength(pquery->distinctClause))
	{
		GPOS_RAISE(gpdxl::ExmaDXL, gpdxl::ExmiQuery2DXLUnsupportedFeature, GPOS_WSZ_LIT("DISTINCT operation on a subset of target list columns"));
	}

	ListCell *plcDistinctCl = NULL;
	ForEach (plcDistinctCl, pquery->distinctClause)
	{
		SortClause *psortcl  = (SortClause*) lfirst(plcDistinctCl);
		GPOS_ASSERT(NULL != psortcl);

		GroupClause *pgrpcl = MakeNode(GroupClause);
		pgrpcl->tleSortGroupRef = psortcl->tleSortGroupRef;
		pgrpcl->sortop = psortcl->sortop;
		pqueryNew->groupClause = gpdb::PlAppendElement(pqueryNew->groupClause, pgrpcl);
	}
	pqueryNew->distinctClause = NIL;
	pqueryDrdTbl->distinctClause = NIL;

	return pqueryNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::FNeedsWindowPrLNormalization
//
//	@doc:
//		Check whether the window operator's project list only contains
//		window functions and columns used in the window specification
//---------------------------------------------------------------------------
BOOL
CQueryMutators::FNeedsWindowPrLNormalization
	(
	const Query *pquery
	)
{
	if (!pquery->hasWindFuncs)
	{
		return false;
	}

	const ULONG ulArity = gpdb::UlListLength(pquery->targetList);
	for (ULONG ul = 0; ul < ulArity; ul++)
	{
		TargetEntry *pte  = (TargetEntry*) gpdb::PvListNth(pquery->targetList, ul);

		if (!CTranslatorUtils::FWindowSpec( (Node *) pte->expr, pquery->windowClause, pquery->targetList) && !IsA(pte->expr, WindowRef) && !IsA(pte->expr, Var))
		{
			// computed columns in the target list that is not
			// used in the order by or partition by of the window specification(s)
			return true;
		}
	}

	return false;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PqueryFixWindowFrameEdgeBoundary
//
//	@doc:
//		Fix window frame edge boundary when its value is defined by a subquery
//---------------------------------------------------------------------------
Query *
CQueryMutators::PqueryFixWindowFrameEdgeBoundary
	(
	const Query *pquery
	)
{
	Query *pqueryNew = (Query *) gpdb::PvCopyObject(const_cast<Query*>(pquery));

	List *plWindowClause = pqueryNew->windowClause;
	ListCell *plcWindowCl = NULL;
	ForEach (plcWindowCl, plWindowClause)
	{
		WindowSpec *pwindowspec = (WindowSpec*) lfirst(plcWindowCl);
		if (NULL != pwindowspec->frame)
		{
			WindowFrame *pwindowframe = pwindowspec->frame;
			if (NULL != pwindowframe->lead->val && IsA(pwindowframe->lead->val, SubLink))
			{
				if (WINDOW_BOUND_PRECEDING == pwindowframe->lead->kind)
				{
					pwindowframe->lead->kind = WINDOW_DELAYED_BOUND_PRECEDING;
				}
				else
				{
					GPOS_ASSERT(WINDOW_BOUND_FOLLOWING == pwindowframe->lead->kind);
					pwindowframe->lead->kind = WINDOW_DELAYED_BOUND_FOLLOWING;
				}
			}

			if (NULL != pwindowframe->trail->val && IsA(pwindowframe->trail->val, SubLink))
			{
				if (WINDOW_BOUND_PRECEDING == pwindowframe->trail->kind)
				{
					pwindowframe->trail->kind = WINDOW_DELAYED_BOUND_PRECEDING;
				}
				else
				{
					GPOS_ASSERT(WINDOW_BOUND_FOLLOWING == pwindowframe->trail->kind);
					pwindowframe->trail->kind = WINDOW_DELAYED_BOUND_FOLLOWING;
				}
			}
		}
	}

	return pqueryNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PqueryNormalizeWindowPrL
//
//	@doc:
// 		Flatten expressions in project list to contain only window functions and
//		columns used in the window specification
//
//		ORGINAL QUERY:
//			SELECT row_number() over() + rank() over(partition by a+b order by a-b) from foo
//
// 		NEW QUERY:
//			SELECT rn+rk from (SELECT row_number() over() as rn rank() over(partition by a+b order by a-b) as rk FROM foo) foo_new
//---------------------------------------------------------------------------
Query *
CQueryMutators::PqueryNormalizeWindowPrL
	(
	IMemoryPool *pmp,
	CMDAccessor *pmda,
	const Query *pquery
	)
{
	Query *pqueryCopy = (Query *) gpdb::PvCopyObject(const_cast<Query*>(pquery));

	if (!FNeedsWindowPrLNormalization(pquery))
	{
		return pqueryCopy;
	}

	// we do not fix target list of the derived table since we will be mutating it below
	// to ensure that it does not have operations with window function
	Query *pqueryNew = PqueryConvertToDerivedTable(pqueryCopy, false /*fFixTargetList*/, true /*fFixHavingQual*/);
	gpdb::GPDBFree(pqueryCopy);

	GPOS_ASSERT(1 == gpdb::UlListLength(pqueryNew->rtable));
	Query *pqueryDrdTbl = (Query *) ((RangeTblEntry *) gpdb::PvListNth(pqueryNew->rtable, 0))->subquery;

	SContextGrpbyPlMutator ctxWindowPrLMutator(pmp, pmda, pqueryDrdTbl, NULL);
	ListCell *plc = NULL;
	List *plTE = pqueryDrdTbl->targetList;
	ForEach (plc, plTE)
	{
		TargetEntry *pte  = (TargetEntry*) lfirst(plc);
		const ULONG ulResNoNew = gpdb::UlListLength(pqueryNew->targetList) + 1;

		if (CTranslatorUtils::FWindowSpec(pte, pquery->windowClause))
		{
			// insert the target list entry used in the window specification as is
			TargetEntry *pteNew = (TargetEntry *) gpdb::PvCopyObject(pte);
			pteNew->resno = gpdb::UlListLength(ctxWindowPrLMutator.m_plTENewGroupByQuery) + 1;
			ctxWindowPrLMutator.m_plTENewGroupByQuery = gpdb::PlAppendElement(ctxWindowPrLMutator.m_plTENewGroupByQuery, pteNew);

			if (!pte->resjunk || CTranslatorUtils::FSortingColumn(pte, pquery->sortClause))
			{
				// if the target list entry used in the window specification is present
				// in the query output then add it to the target list of the new top level query
				Var *pvarNew = gpdb::PvarMakeVar
										(
										1,
										pteNew->resno,
										gpdb::OidExprType((Node*) pte->expr),
										gpdb::IExprTypeMod((Node*) pte->expr),
										0 // query levels up
										);
				TargetEntry *pteNewCopy = gpdb::PteMakeTargetEntry((Expr*) pvarNew, ulResNoNew, pte->resname, pte->resjunk);

				// Copy the resortgroupref and resjunk information for the top-level target list entry
				// Set target list entry of the derived table to be non-resjunked
				pteNewCopy->resjunk = pteNew->resjunk;
				pteNewCopy->ressortgroupref = pteNew->ressortgroupref;
				pteNew->resjunk = false;

				pqueryNew->targetList = gpdb::PlAppendElement(pqueryNew->targetList, pteNewCopy);
			}
		}
		else
		{
			// normalize target list entry
			ctxWindowPrLMutator.m_ulRessortgroupref = pte->ressortgroupref;
			Expr *pexprNew = (Expr*) PnodeWindowPrLMutator( (Node*) pte->expr, &ctxWindowPrLMutator);
			TargetEntry *pteNew = gpdb::PteMakeTargetEntry(pexprNew, ulResNoNew, pte->resname, pte->resjunk);
			pteNew->ressortgroupref = pte->ressortgroupref;
			pqueryNew->targetList = gpdb::PlAppendElement(pqueryNew->targetList, pteNew);
		}
	}
	pqueryDrdTbl->targetList = ctxWindowPrLMutator.m_plTENewGroupByQuery;

	GPOS_ASSERT(gpdb::UlListLength(pqueryNew->targetList) <= gpdb::UlListLength(pquery->targetList));

	pqueryNew->hasWindFuncs = false;
	ReassignSortClause(pqueryNew, pqueryDrdTbl);

	return pqueryNew;
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::PnodeWindowPrLMutator
//
//	@doc:
// 		Traverse the project list of extract all window functions in an
//		arbitrarily complex project element
//---------------------------------------------------------------------------
Node *
CQueryMutators::PnodeWindowPrLMutator
	(
	Node *pnode,
	void *pctx
	)
{
	if (NULL == pnode)
	{
		return NULL;
	}

	// do not traverse into sub queries as they will be inserted are inserted into
	// top-level query as is
	if (IsA(pnode, SubLink))
	{
		return (Node *) gpdb::PvCopyObject(pnode);
	}

	SContextGrpbyPlMutator *pctxWindowPrLMutator = (SContextGrpbyPlMutator *) pctx;
	const ULONG ulResNo = gpdb::UlListLength(pctxWindowPrLMutator->m_plTENewGroupByQuery) + 1;

	if (IsA(pnode, WindowRef))
	{
		// insert window operator into the derived table
        // and refer to it in the top-level query's target list
		WindowRef *pwindowref = (WindowRef*) gpdb::PvCopyObject(pnode);

		// get the function name and add it to the target list
		CMDIdGPDB *pmdidFunc = CTranslatorUtils::PmdidWithVersion(pctxWindowPrLMutator->m_pmp, pwindowref->winfnoid);
		const CWStringConst *pstr = CMDAccessorUtils::PstrWindowFuncName(pctxWindowPrLMutator->m_pmda, pmdidFunc);
		pmdidFunc->Release();

		TargetEntry *pte = gpdb::PteMakeTargetEntry
								(
								(Expr*) gpdb::PvCopyObject(pnode),
								(AttrNumber) ulResNo,
								CTranslatorUtils::SzFromWsz(pstr->Wsz()),
								false /* resjunk */
								);
		pctxWindowPrLMutator->m_plTENewGroupByQuery = gpdb::PlAppendElement(pctxWindowPrLMutator->m_plTENewGroupByQuery, pte);

		// return a variable referring to the new derived table's corresponding target list entry
		Var *pvarNew = gpdb::PvarMakeVar
								(
								1,
								(AttrNumber) ulResNo,
								gpdb::OidExprType(pnode),
								gpdb::IExprTypeMod(pnode),
								0 // query levelsup
								);

		return (Node*) pvarNew;
	}

	if (IsA(pnode, Var))
	{
		Var *pvarNew = NULL;

		TargetEntry *pteFound = gpdb::PteMember(pnode, pctxWindowPrLMutator->m_plTENewGroupByQuery);
		if (NULL == pteFound)
		{
			// insert target entry into the target list of the derived table
			CWStringConst strUnnamedCol(GPOS_WSZ_LIT("?column?"));
			TargetEntry *pte = gpdb::PteMakeTargetEntry
									(
									(Expr*) gpdb::PvCopyObject(pnode),
									(AttrNumber) ulResNo,
									CTranslatorUtils::SzFromWsz(strUnnamedCol.Wsz()),
									false /* resjunk */
									);
			pctxWindowPrLMutator->m_plTENewGroupByQuery = gpdb::PlAppendElement(pctxWindowPrLMutator->m_plTENewGroupByQuery, pte);

			pvarNew = gpdb::PvarMakeVar
								(
								1,
								(AttrNumber) ulResNo,
								gpdb::OidExprType(pnode),
								gpdb::IExprTypeMod(pnode),
								0 // query levelsup
								);
		}
		else
		{
			pteFound->resjunk = false; // ensure that the derived target list is not resjunked
			pvarNew = gpdb::PvarMakeVar
								(
								1,
								pteFound->resno,
								gpdb::OidExprType(pnode),
								gpdb::IExprTypeMod(pnode),
								0 // query levelsup
								);
		}

		return (Node*) pvarNew;
	}

	return gpdb::PnodeMutateExpressionTree(pnode, (Pfnode) CQueryMutators::PnodeWindowPrLMutator, pctx);
}

//---------------------------------------------------------------------------
//	@function:
//		CQueryMutators::ReassignSortClause
//
//	@doc:
//		Reassign the sorting clause from the derived table to the new top-level query
//---------------------------------------------------------------------------
void
CQueryMutators::ReassignSortClause
	(
	Query *pqueryNew,
	Query *pqueryDrdTbl
	)
{
	pqueryNew->sortClause = pqueryDrdTbl->sortClause;
	pqueryNew->limitOffset = pqueryDrdTbl->limitOffset;
	pqueryNew->limitCount = pqueryDrdTbl->limitCount;
	pqueryDrdTbl->sortClause = NULL;
	pqueryDrdTbl->limitOffset = NULL;
	pqueryDrdTbl->limitCount = NULL;
}

// EOF