nodeNestloop.c

/*-------------------------------------------------------------------------
 *
 * nodeNestloop.c
 *	  routines to support nest-loop joins
 *
 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/executor/nodeNestloop.c
 *
 *-------------------------------------------------------------------------
 */
/*
 *	 INTERFACE ROUTINES
 *		ExecNestLoop	 - process a nestloop join of two plans
 *		ExecInitNestLoop - initialize the join
 *		ExecEndNestLoop  - shut down the join
 */

#include "postgres.h"

#include "executor/execdebug.h"
#include "executor/nodeNestloop.h"
#include "miscadmin.h"
#include "utils/guc.h"
#include "utils/memutils.h"


/* ----------------------------------------------------------------
 *		ExecNestLoop(node)
 *
 * old comments
 *		Returns the tuple joined from inner and outer tuples which
 *		satisfies the qualification clause.
 *
 *		It scans the inner relation to join with current outer tuple.
 *
 *		If none is found, next tuple from the outer relation is retrieved
 *		and the inner relation is scanned from the beginning again to join
 *		with the outer tuple.
 *
 *		NULL is returned if all the remaining outer tuples are tried and
 *		all fail to join with the inner tuples.
 *
 *		NULL is also returned if there is no tuple from inner relation.
 *
 *		Conditions:
 *		  -- outerTuple contains current tuple from outer relation and
 *			 the right son(inner relation) maintains "cursor" at the tuple
 *			 returned previously.
 *				This is achieved by maintaining a scan position on the outer
 *				relation.
 *
 *		Initial States:
 *		  -- the outer child and the inner child
 *			   are prepared to return the first tuple.
 * ----------------------------------------------------------------
 */



#define BlockIsNil(block) \
		block == NIL
/* ----------------------------------------------------------------
 *		helper functions
 * ----------------------------------------------------------------
 */
List* 
LoadOuterBlock(int blockSize, PlanState* outerPlan, EState* estate, NestLoopState* node)  
{
	List* block = NIL;
	int i = 0;

	while (i < blockSize) 
	{
		TupleTableSlot *srcslot = ExecProcNode(outerPlan);

		if (TupIsNull(srcslot)) 
		{
			node->nl_isEnd = true;
			break;
		}

		TupleTableSlot *dstslot = ExecAllocTableSlot(&estate->es_tupleTable, srcslot->tts_tupleDescriptor, &TTSOpsVirtual);
		ExecCopySlot(dstslot, srcslot);

		block = lappend(block, dstslot);
		i++;
	}

	return block;

}

/* ----------------------------------------------------------------
 *		BlockNestedLoopJoin
 * ----------------------------------------------------------------
 */
static TupleTableSlot *
ExecNestLoop(PlanState *pstate)
{

	// 当前结点的状态
	NestLoopState *node = castNode(NestLoopState, pstate);
	// 包含join的类型等信息
	NestLoop   *nl;
	// innerplan的执行状态结点
	PlanState  *innerPlan;
	// outerplan的执行状态结点
	PlanState  *outerPlan;
	// outer plan输出的元组
	TupleTableSlot *outerTupleSlot;
	// inner plan输出的元组
	TupleTableSlot *innerTupleSlot;
	// join 条件 
	ExprState  *joinqual;
	// 额外的过滤条件 如 where a = 1
	ExprState  *otherqual;
	// 当前的表达式上下文
	ExprContext *econtext;
	// 每次循环访问一个NestLoopParam
	ListCell   *lc;
	// 获取执行状态
	EState *estate;

	CHECK_FOR_INTERRUPTS();

	/*
	 * get information from the node
	 */
	ENL1_printf("getting info from node");

	nl = (NestLoop *) node->js.ps.plan;
	joinqual = node->js.joinqual;
	otherqual = node->js.ps.qual;
	outerPlan = outerPlanState(node);
	innerPlan = innerPlanState(node);
	econtext = node->js.ps.ps_ExprContext;
	estate = node->js.ps.state;


	/*
	 * Reset per-tuple memory context to free any expression evaluation
	 * storage allocated in the previous tuple cycle.
	 */
	ResetExprContext(econtext);

	/*
	 * Ok, everything is setup for the join so now loop until we return a
	 * qualifying join tuple.
	 */
	ENL1_printf("entering main loop");

	for (;;)
	{
		// 加载新的块
		if (node->nl_NeedNewBlock) 
		{
			// 释放块空间
			if (!BlockIsNil(node->nl_OuterBlock))
			{
				list_free(node->nl_OuterBlock);
			}

			// 上一个块没有加载完，说明outer tuples都已经遍历过了
			if (node->nl_isEnd) 
			{
				ENL1_printf("no outer tuple, ending join");
				return NULL;
			}
			// 需要加载新的块
			List *outerBlock = LoadOuterBlock(node->blockSize, outerPlan, estate, node);

			// 发生在blocksize恰好能整除元组数的时候
			if (BlockIsNil(outerBlock)) 
			{
				ENL1_printf("no outer tuple, ending join");
				return NULL;
			}

			node->nl_OuterBlock = outerBlock;
			node->nl_NeedNewBlock = false;
			node->cursor = list_head(node->nl_OuterBlock);
			
			// 需要重置innerscan，从头重新开始
			ExecReScan(innerPlan);
		}

		if (node->nl_NeedNewInner)
		{
			innerTupleSlot = ExecProcNode(innerPlan);
			// inner tuple全都扫过一遍了，需要新的block，直接进入下一次循环
			if (TupIsNull(innerTupleSlot)) 
			{
				node->nl_NeedNewBlock = true;
				node->nl_NeedNewInner = true;
				continue;
			}
			econtext->ecxt_innertuple = innerTupleSlot;
			node->nl_NeedNewInner = false;
			// 重置游标
			node->cursor = list_head(node->nl_OuterBlock);
		}

		// 获取当前的outer tuple
		if (node->cursor) 
		{
			outerTupleSlot = (TupleTableSlot *) lfirst(node->cursor);
			node->cursor = lnext(node->cursor);
			econtext->ecxt_outertuple = outerTupleSlot;
		} 
		else 
		{
			// 说明当前块已经遍历完了，需要加载下一个inner tuple
			node->nl_NeedNewInner = true;
			node->cursor = NULL;
			continue;
		}
		
		if (ExecQual(joinqual, econtext))
		{
			if (otherqual == NULL || ExecQual(otherqual, econtext))
			{
				return ExecProject(node->js.ps.ps_ProjInfo);
			}
			else 
			{
				InstrCountFiltered2(node, 1);
			}
		}
		else 
		{
			InstrCountFiltered1(node, 1);
		}
		/*
		 * Tuple fails qual, so free per-tuple memory and try again.
		 */
		ResetExprContext(econtext);

		ENL1_printf("qualification failed, looping");
	}
}

/* ----------------------------------------------------------------
 *		ExecInitNestLoop
 * ----------------------------------------------------------------
 */
NestLoopState *
ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
{
	NestLoopState *nlstate;

	/* check for unsupported flags */
	Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));

	NL1_printf("ExecInitNestLoop: %s\n",
			   "initializing node");

	/*
	 * create state structure
	 */
	nlstate = makeNode(NestLoopState);
	nlstate->js.ps.plan = (Plan *) node;
	nlstate->js.ps.state = estate;
	nlstate->js.ps.ExecProcNode = ExecNestLoop;

	/*
	 * Miscellaneous initialization
	 *
	 * create expression context for node
	 */
	ExecAssignExprContext(estate, &nlstate->js.ps);

	/*
	 * initialize child nodes
	 *
	 * If we have no parameters to pass into the inner rel from the outer,
	 * tell the inner child that cheap rescans would be good.  If we do have
	 * such parameters, then there is no point in REWIND support at all in the
	 * inner child, because it will always be rescanned with fresh parameter
	 * values.
	 */
	outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
	if (node->nestParams == NIL)
		eflags |= EXEC_FLAG_REWIND;
	else
		eflags &= ~EXEC_FLAG_REWIND;
	innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);

	/*
	 * Initialize result slot, type and projection.
	 */
	ExecInitResultTupleSlotTL(&nlstate->js.ps, &TTSOpsVirtual);
	ExecAssignProjectionInfo(&nlstate->js.ps, NULL);

	/*
	 * initialize child expressions
	 */
	nlstate->js.ps.qual =
		ExecInitQual(node->join.plan.qual, (PlanState *) nlstate);
	nlstate->js.jointype = node->join.jointype;
	nlstate->js.joinqual =
		ExecInitQual(node->join.joinqual, (PlanState *) nlstate);

	/*
	 * detect whether we need only consider the first matching inner tuple
	 */
	nlstate->js.single_match = (node->join.inner_unique ||
								node->join.jointype == JOIN_SEMI);

	/* set up null tuples for outer joins, if needed */
	switch (node->join.jointype)
	{
		case JOIN_INNER:
		case JOIN_SEMI:
			break;
		case JOIN_LEFT:
		case JOIN_ANTI:
			nlstate->nl_NullInnerTupleSlot =
				ExecInitNullTupleSlot(estate,
									  ExecGetResultType(innerPlanState(nlstate)),
									  &TTSOpsVirtual);
			break;
		default:
			elog(ERROR, "unrecognized join type: %d",
				 (int) node->join.jointype);
	}

	/*
	 * finally, wipe the current outer tuple clean.
	 */
	nlstate->nl_NeedNewOuter = true;
	nlstate->nl_MatchedOuter = false;

	// 初始化结点状态
	nlstate->nl_NeedNewInner = true;
	nlstate->blockSize = bnlj_block_size;
	nlstate->nl_OuterBlock = NIL;
	nlstate->nl_NeedNewBlock = true;
	nlstate->cursor = NULL;
	nlstate->nl_isEnd = false;

	NL1_printf("ExecInitNestLoop: %s\n",
			   "node initialized");

	return nlstate;
}


/* ----------------------------------------------------------------
 *		ExecEndNestLoop
 *
 *		closes down scans and frees allocated storage
 * ----------------------------------------------------------------
 */
void
ExecEndNestLoop(NestLoopState *node)
{
	NL1_printf("ExecEndNestLoop: %s\n",
			   "ending node processing");

	/*
	 * Free the exprcontext
	 */
	ExecFreeExprContext(&node->js.ps);

	/*
	 * clean out the tuple table
	 */
	ExecClearTuple(node->js.ps.ps_ResultTupleSlot);

	/*
	 * close down subplans
	 */
	ExecEndNode(outerPlanState(node));
	ExecEndNode(innerPlanState(node));


	NL1_printf("ExecEndNestLoop: %s\n",
			   "node processing ended");

}

/* ----------------------------------------------------------------
 *		ExecReScanNestLoop
 * ----------------------------------------------------------------
 */
void
ExecReScanNestLoop(NestLoopState *node)
{
	PlanState  *outerPlan = outerPlanState(node);

	/*
	 * If outerPlan->chgParam is not null then plan will be automatically
	 * re-scanned by first ExecProcNode.
	 */
	if (outerPlan->chgParam == NULL)
		ExecReScan(outerPlan);

	/*
	 * innerPlan is re-scanned for each new outer tuple and MUST NOT be
	 * re-scanned from here or you'll get troubles from inner index scans when
	 * outer Vars are used as run-time keys...
	 */
	node->nl_NeedNewOuter = true;
	node->nl_MatchedOuter = false;

	// 重置node状态
	node->nl_isEnd = false;
	node->nl_NeedNewBlock = true;
	node->nl_NeedNewInner = true;
	node->nl_OuterBlock = NIL;
	node->cursor = NULL;
	node->blockSize = bnlj_block_size;
}