nodeSort.c 7.92 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * nodeSort.c
4
 *	  Routines to handle sorting of relations.
5
 *
6
 * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
7
 * Portions Copyright (c) 1994, Regents of the University of California
8 9 10
 *
 *
 * IDENTIFICATION
11
 *	  $PostgreSQL: pgsql/src/backend/executor/nodeSort.c,v 1.57 2006/06/27 16:53:02 tgl Exp $
12 13 14
 *
 *-------------------------------------------------------------------------
 */
15

Bruce Momjian's avatar
Bruce Momjian committed
16
#include "postgres.h"
17

Bruce Momjian's avatar
Bruce Momjian committed
18
#include "executor/execdebug.h"
19
#include "executor/nodeSort.h"
20
#include "miscadmin.h"
21
#include "utils/tuplesort.h"
22 23 24


/* ----------------------------------------------------------------
25
 *		ExecSort
26
 *
27
 *		Sorts tuples from the outer subtree of the node using tuplesort,
28 29 30 31 32 33 34 35
 *		which saves the results in a temporary file or memory. After the
 *		initial call, returns a tuple from the file with each call.
 *
 *		Conditions:
 *		  -- none.
 *
 *		Initial States:
 *		  -- the outer child is prepared to return the first tuple.
36 37 38
 * ----------------------------------------------------------------
 */
TupleTableSlot *
39
ExecSort(SortState *node)
40
{
41 42
	EState	   *estate;
	ScanDirection dir;
43
	Tuplesortstate *tuplesortstate;
44 45
	TupleTableSlot *slot;

46 47
	/*
	 * get state info from node
48
	 */
49 50 51
	SO1_printf("ExecSort: %s\n",
			   "entering routine");

52
	estate = node->ss.ps.state;
53
	dir = estate->es_direction;
54
	tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
55

56
	/*
57 58
	 * If first time through, read all tuples from outer plan and pass them to
	 * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
59
	 */
60

61
	if (!node->sort_Done)
62
	{
63 64
		Sort	   *plannode = (Sort *) node->ss.ps.plan;
		PlanState  *outerNode;
65 66
		TupleDesc	tupDesc;

67
		SO1_printf("ExecSort: %s\n",
68
				   "sorting subplan");
69 70

		/*
71 72
		 * Want to scan subplan in the forward direction while creating the
		 * sorted data.
73 74 75
		 */
		estate->es_direction = ForwardScanDirection;

76 77
		/*
		 * Initialize tuplesort module.
78
		 */
79 80
		SO1_printf("ExecSort: %s\n",
				   "calling tuplesort_begin");
81

82
		outerNode = outerPlanState(node);
83
		tupDesc = ExecGetResultType(outerNode);
84

85 86 87 88
		tuplesortstate = tuplesort_begin_heap(tupDesc,
											  plannode->numCols,
											  plannode->sortOperators,
											  plannode->sortColIdx,
89
											  work_mem,
90
											  node->randomAccess);
91
		node->tuplesortstate = (void *) tuplesortstate;
92

93 94
		/*
		 * Scan the subplan and feed all the tuples to tuplesort.
95 96 97
		 */

		for (;;)
98
		{
99
			slot = ExecProcNode(outerNode);
100 101 102 103

			if (TupIsNull(slot))
				break;

104
			tuplesort_puttupleslot(tuplesortstate, slot);
105 106
		}

107 108
		/*
		 * Complete the sort.
109 110 111
		 */
		tuplesort_performsort(tuplesortstate);

112 113
		/*
		 * restore to user specified direction
114 115
		 */
		estate->es_direction = dir;
116

117 118
		/*
		 * finally set the sorted flag to true
119
		 */
120
		node->sort_Done = true;
121
		SO1_printf("ExecSort: %s\n", "sorting done");
122 123 124
	}

	SO1_printf("ExecSort: %s\n",
125
			   "retrieving tuple from tuplesort");
126

127 128 129
	/*
	 * Get the first or next tuple from tuplesort. Returns NULL if no more
	 * tuples.
130
	 */
131
	slot = node->ss.ps.ps_ResultTupleSlot;
132 133 134 135
	(void) tuplesort_gettupleslot(tuplesortstate,
								  ScanDirectionIsForward(dir),
								  slot);
	return slot;
136 137 138
}

/* ----------------------------------------------------------------
139
 *		ExecInitSort
140
 *
141
 *		Creates the run-time state information for the sort node
142
 *		produced by the planner and initializes its outer subtree.
143 144
 * ----------------------------------------------------------------
 */
145
SortState *
146
ExecInitSort(Sort *node, EState *estate, int eflags)
147
{
148
	SortState  *sortstate;
149 150 151 152

	SO1_printf("ExecInitSort: %s\n",
			   "initializing sort node");

153
	/*
154 155 156
	 * create state structure
	 */
	sortstate = makeNode(SortState);
157 158 159
	sortstate->ss.ps.plan = (Plan *) node;
	sortstate->ss.ps.state = estate;

160 161 162 163 164 165 166 167 168
	/*
	 * We must have random access to the sort output to do backward scan
	 * or mark/restore.  We also prefer to materialize the sort output
	 * if we might be called on to rewind and replay it many times.
	 */
	sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
										 EXEC_FLAG_BACKWARD |
										 EXEC_FLAG_MARK)) != 0;

169 170
	sortstate->sort_Done = false;
	sortstate->tuplesortstate = NULL;
171

172 173
	/*
	 * Miscellaneous initialization
174
	 *
175 176
	 * Sort nodes don't initialize their ExprContexts because they never call
	 * ExecQual or ExecProject.
177 178
	 */

179
#define SORT_NSLOTS 2
180 181 182

	/*
	 * tuple table initialization
183
	 *
184
	 * sort nodes only return scan tuples from their sorted relation.
185
	 */
186 187
	ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
	ExecInitScanTupleSlot(estate, &sortstate->ss);
188

189
	/*
190 191 192 193
	 * initialize child nodes
	 *
	 * We shield the child node from the need to support REWIND, BACKWARD,
	 * or MARK/RESTORE.
194
	 */
195 196 197
	eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);

	outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
198

199
	/*
200 201
	 * initialize tuple type.  no need to initialize projection info because
	 * this node doesn't do projections.
202
	 */
203
	ExecAssignResultTypeFromTL(&sortstate->ss.ps);
204 205
	ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
	sortstate->ss.ps.ps_ProjInfo = NULL;
206 207 208 209

	SO1_printf("ExecInitSort: %s\n",
			   "sort node initialized");

210
	return sortstate;
211 212 213
}

int
214
ExecCountSlotsSort(Sort *node)
215
{
216
	return ExecCountSlotsNode(outerPlan((Plan *) node)) +
217 218
		ExecCountSlotsNode(innerPlan((Plan *) node)) +
		SORT_NSLOTS;
219 220 221
}

/* ----------------------------------------------------------------
222
 *		ExecEndSort(node)
223 224 225
 * ----------------------------------------------------------------
 */
void
226
ExecEndSort(SortState *node)
227
{
228 229 230
	SO1_printf("ExecEndSort: %s\n",
			   "shutting down sort node");

231
	/*
232
	 * clean out the tuple table
233
	 */
234
	ExecClearTuple(node->ss.ss_ScanTupleSlot);
235 236
	/* must drop pointer to sort result tuple */
	ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
237

238 239
	/*
	 * Release tuplesort resources
240
	 */
241 242 243
	if (node->tuplesortstate != NULL)
		tuplesort_end((Tuplesortstate *) node->tuplesortstate);
	node->tuplesortstate = NULL;
244

245 246 247 248 249
	/*
	 * shut down the subplan
	 */
	ExecEndNode(outerPlanState(node));

250 251 252
	SO1_printf("ExecEndSort: %s\n",
			   "sort node shutdown");
}
253 254

/* ----------------------------------------------------------------
255
 *		ExecSortMarkPos
256
 *
257
 *		Calls tuplesort to save the current position in the sorted file.
258 259 260
 * ----------------------------------------------------------------
 */
void
261
ExecSortMarkPos(SortState *node)
262
{
263 264
	/*
	 * if we haven't sorted yet, just return
265
	 */
266
	if (!node->sort_Done)
267 268
		return;

269
	tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
270 271 272
}

/* ----------------------------------------------------------------
273
 *		ExecSortRestrPos
274
 *
275
 *		Calls tuplesort to restore the last saved sort file position.
276 277 278
 * ----------------------------------------------------------------
 */
void
279
ExecSortRestrPos(SortState *node)
280
{
281 282
	/*
	 * if we haven't sorted yet, just return.
283
	 */
284
	if (!node->sort_Done)
285 286
		return;

287 288
	/*
	 * restore the scan to the previously marked position
289
	 */
290
	tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
291
}
292 293

void
294
ExecReScanSort(SortState *node, ExprContext *exprCtxt)
295 296
{
	/*
297 298 299
	 * If we haven't sorted yet, just return. If outerplan' chgParam is not
	 * NULL then it will be re-scanned by ExecProcNode, else - no reason to
	 * re-scan it at all.
300
	 */
301
	if (!node->sort_Done)
302
		return;
303

304
	/* must drop pointer to sort result tuple */
305
	ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
306

307
	/*
308 309
	 * If subnode is to be rescanned then we forget previous sort results; we
	 * have to re-read the subplan and re-sort.
310 311
	 *
	 * Otherwise we can just rewind and rescan the sorted output.
312
	 */
313 314
	if (((PlanState *) node)->lefttree->chgParam != NULL ||
		!node->randomAccess)
315
	{
316 317 318
		node->sort_Done = false;
		tuplesort_end((Tuplesortstate *) node->tuplesortstate);
		node->tuplesortstate = NULL;
319 320 321 322 323 324
		/*
		 * if chgParam of subnode is not null then plan will be re-scanned by
		 * first ExecProcNode.
		 */
		if (((PlanState *) node)->lefttree->chgParam == NULL)
			ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
325 326
	}
	else
327
		tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
328
}