1 /*-------------------------------------------------------------------------
4 * Routines to handle sorting of relations.
6 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/executor/nodeSort.c,v 1.65 2009/04/02 20:59:10 momjian Exp $
13 *-------------------------------------------------------------------------
18 #include "executor/execdebug.h"
19 #include "executor/nodeSort.h"
20 #include "miscadmin.h"
21 #include "utils/tuplesort.h"
24 /* ----------------------------------------------------------------
27 * Sorts tuples from the outer subtree of the node using tuplesort,
28 * which saves the results in a temporary file or memory. After the
29 * initial call, returns a tuple from the file with each call.
35 * -- the outer child is prepared to return the first tuple.
36 * ----------------------------------------------------------------
39 ExecSort(SortState *node)
43 Tuplesortstate *tuplesortstate;
47 * get state info from node
49 SO1_printf("ExecSort: %s\n",
52 estate = node->ss.ps.state;
53 dir = estate->es_direction;
54 tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
57 * If first time through, read all tuples from outer plan and pass them to
58 * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
63 Sort *plannode = (Sort *) node->ss.ps.plan;
67 SO1_printf("ExecSort: %s\n",
71 * Want to scan subplan in the forward direction while creating the
74 estate->es_direction = ForwardScanDirection;
77 * Initialize tuplesort module.
79 SO1_printf("ExecSort: %s\n",
80 "calling tuplesort_begin");
82 outerNode = outerPlanState(node);
83 tupDesc = ExecGetResultType(outerNode);
85 tuplesortstate = tuplesort_begin_heap(tupDesc,
88 plannode->sortOperators,
93 tuplesort_set_bound(tuplesortstate, node->bound);
94 node->tuplesortstate = (void *) tuplesortstate;
97 * Scan the subplan and feed all the tuples to tuplesort.
102 slot = ExecProcNode(outerNode);
107 tuplesort_puttupleslot(tuplesortstate, slot);
113 tuplesort_performsort(tuplesortstate);
116 * restore to user specified direction
118 estate->es_direction = dir;
121 * finally set the sorted flag to true
123 node->sort_Done = true;
124 node->bounded_Done = node->bounded;
125 node->bound_Done = node->bound;
126 SO1_printf("ExecSort: %s\n", "sorting done");
129 SO1_printf("ExecSort: %s\n",
130 "retrieving tuple from tuplesort");
133 * Get the first or next tuple from tuplesort. Returns NULL if no more
136 slot = node->ss.ps.ps_ResultTupleSlot;
137 (void) tuplesort_gettupleslot(tuplesortstate,
138 ScanDirectionIsForward(dir),
143 /* ----------------------------------------------------------------
146 * Creates the run-time state information for the sort node
147 * produced by the planner and initializes its outer subtree.
148 * ----------------------------------------------------------------
151 ExecInitSort(Sort *node, EState *estate, int eflags)
153 SortState *sortstate;
155 SO1_printf("ExecInitSort: %s\n",
156 "initializing sort node");
159 * create state structure
161 sortstate = makeNode(SortState);
162 sortstate->ss.ps.plan = (Plan *) node;
163 sortstate->ss.ps.state = estate;
166 * We must have random access to the sort output to do backward scan or
167 * mark/restore. We also prefer to materialize the sort output if we
168 * might be called on to rewind and replay it many times.
170 sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
172 EXEC_FLAG_MARK)) != 0;
174 sortstate->bounded = false;
175 sortstate->sort_Done = false;
176 sortstate->tuplesortstate = NULL;
179 * Miscellaneous initialization
181 * Sort nodes don't initialize their ExprContexts because they never call
182 * ExecQual or ExecProject.
185 #define SORT_NSLOTS 2
188 * tuple table initialization
190 * sort nodes only return scan tuples from their sorted relation.
192 ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
193 ExecInitScanTupleSlot(estate, &sortstate->ss);
196 * initialize child nodes
198 * We shield the child node from the need to support REWIND, BACKWARD, or
201 eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
203 outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
206 * initialize tuple type. no need to initialize projection info because
207 * this node doesn't do projections.
209 ExecAssignResultTypeFromTL(&sortstate->ss.ps);
210 ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
211 sortstate->ss.ps.ps_ProjInfo = NULL;
213 SO1_printf("ExecInitSort: %s\n",
214 "sort node initialized");
220 ExecCountSlotsSort(Sort *node)
222 return ExecCountSlotsNode(outerPlan((Plan *) node)) +
223 ExecCountSlotsNode(innerPlan((Plan *) node)) +
227 /* ----------------------------------------------------------------
229 * ----------------------------------------------------------------
232 ExecEndSort(SortState *node)
234 SO1_printf("ExecEndSort: %s\n",
235 "shutting down sort node");
238 * clean out the tuple table
240 ExecClearTuple(node->ss.ss_ScanTupleSlot);
241 /* must drop pointer to sort result tuple */
242 ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
245 * Release tuplesort resources
247 if (node->tuplesortstate != NULL)
248 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
249 node->tuplesortstate = NULL;
252 * shut down the subplan
254 ExecEndNode(outerPlanState(node));
256 SO1_printf("ExecEndSort: %s\n",
257 "sort node shutdown");
260 /* ----------------------------------------------------------------
263 * Calls tuplesort to save the current position in the sorted file.
264 * ----------------------------------------------------------------
267 ExecSortMarkPos(SortState *node)
270 * if we haven't sorted yet, just return
272 if (!node->sort_Done)
275 tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
278 /* ----------------------------------------------------------------
281 * Calls tuplesort to restore the last saved sort file position.
282 * ----------------------------------------------------------------
285 ExecSortRestrPos(SortState *node)
288 * if we haven't sorted yet, just return.
290 if (!node->sort_Done)
294 * restore the scan to the previously marked position
296 tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
300 ExecReScanSort(SortState *node, ExprContext *exprCtxt)
303 * If we haven't sorted yet, just return. If outerplan' chgParam is not
304 * NULL then it will be re-scanned by ExecProcNode, else - no reason to
307 if (!node->sort_Done)
310 /* must drop pointer to sort result tuple */
311 ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
314 * If subnode is to be rescanned then we forget previous sort results; we
315 * have to re-read the subplan and re-sort. Also must re-sort if the
316 * bounded-sort parameters changed or we didn't select randomAccess.
318 * Otherwise we can just rewind and rescan the sorted output.
320 if (((PlanState *) node)->lefttree->chgParam != NULL ||
321 node->bounded != node->bounded_Done ||
322 node->bound != node->bound_Done ||
325 node->sort_Done = false;
326 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
327 node->tuplesortstate = NULL;
330 * if chgParam of subnode is not null then plan will be re-scanned by
331 * first ExecProcNode.
333 if (((PlanState *) node)->lefttree->chgParam == NULL)
334 ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
337 tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);