1 /*-------------------------------------------------------------------------
2 *
3 * nodeSort.c
4 * Routines to handle sorting of relations.
5 *
6 * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/executor/nodeSort.c
12 *
13 *-------------------------------------------------------------------------
14 */
15
16 #include "postgres.h"
17
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 * which saves the results in a temporary file or memory. After the
29 * initial call, returns a tuple from the file with each call.
30 *
31 * Conditions:
32 * -- none.
33 *
34 * Initial States:
35 * -- the outer child is prepared to return the first tuple.
36 * ----------------------------------------------------------------
37 */
38 TupleTableSlot *
ExecSort(SortState * node)39 ExecSort(SortState *node)
40 {
41 EState *estate;
42 ScanDirection dir;
43 Tuplesortstate *tuplesortstate;
44 TupleTableSlot *slot;
45
46 /*
47 * get state info from node
48 */
49 SO1_printf("ExecSort: %s\n",
50 "entering routine");
51
52 estate = node->ss.ps.state;
53 dir = estate->es_direction;
54 tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
55
56 /*
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.
59 */
60
61 if (!node->sort_Done)
62 {
63 Sort *plannode = (Sort *) node->ss.ps.plan;
64 PlanState *outerNode;
65 TupleDesc tupDesc;
66
67 SO1_printf("ExecSort: %s\n",
68 "sorting subplan");
69
70 /*
71 * Want to scan subplan in the forward direction while creating the
72 * sorted data.
73 */
74 estate->es_direction = ForwardScanDirection;
75
76 /*
77 * Initialize tuplesort module.
78 */
79 SO1_printf("ExecSort: %s\n",
80 "calling tuplesort_begin");
81
82 outerNode = outerPlanState(node);
83 tupDesc = ExecGetResultType(outerNode);
84
85 tuplesortstate = tuplesort_begin_heap(tupDesc,
86 plannode->numCols,
87 plannode->sortColIdx,
88 plannode->sortOperators,
89 plannode->collations,
90 plannode->nullsFirst,
91 work_mem,
92 node->randomAccess);
93 if (node->bounded)
94 tuplesort_set_bound(tuplesortstate, node->bound);
95 node->tuplesortstate = (void *) tuplesortstate;
96
97 /*
98 * Scan the subplan and feed all the tuples to tuplesort.
99 */
100
101 for (;;)
102 {
103 slot = ExecProcNode(outerNode);
104
105 if (TupIsNull(slot))
106 break;
107
108 tuplesort_puttupleslot(tuplesortstate, slot);
109 }
110
111 /*
112 * Complete the sort.
113 */
114 tuplesort_performsort(tuplesortstate);
115
116 /*
117 * restore to user specified direction
118 */
119 estate->es_direction = dir;
120
121 /*
122 * finally set the sorted flag to true
123 */
124 node->sort_Done = true;
125 node->bounded_Done = node->bounded;
126 node->bound_Done = node->bound;
127 SO1_printf("ExecSort: %s\n", "sorting done");
128 }
129
130 SO1_printf("ExecSort: %s\n",
131 "retrieving tuple from tuplesort");
132
133 /*
134 * Get the first or next tuple from tuplesort. Returns NULL if no more
135 * tuples.
136 */
137 slot = node->ss.ps.ps_ResultTupleSlot;
138 (void) tuplesort_gettupleslot(tuplesortstate,
139 ScanDirectionIsForward(dir),
140 slot, NULL);
141 return slot;
142 }
143
144 /* ----------------------------------------------------------------
145 * ExecInitSort
146 *
147 * Creates the run-time state information for the sort node
148 * produced by the planner and initializes its outer subtree.
149 * ----------------------------------------------------------------
150 */
151 SortState *
ExecInitSort(Sort * node,EState * estate,int eflags)152 ExecInitSort(Sort *node, EState *estate, int eflags)
153 {
154 SortState *sortstate;
155
156 SO1_printf("ExecInitSort: %s\n",
157 "initializing sort node");
158
159 /*
160 * create state structure
161 */
162 sortstate = makeNode(SortState);
163 sortstate->ss.ps.plan = (Plan *) node;
164 sortstate->ss.ps.state = estate;
165
166 /*
167 * We must have random access to the sort output to do backward scan or
168 * mark/restore. We also prefer to materialize the sort output if we
169 * might be called on to rewind and replay it many times.
170 */
171 sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
172 EXEC_FLAG_BACKWARD |
173 EXEC_FLAG_MARK)) != 0;
174
175 sortstate->bounded = false;
176 sortstate->sort_Done = false;
177 sortstate->tuplesortstate = NULL;
178
179 /*
180 * Miscellaneous initialization
181 *
182 * Sort nodes don't initialize their ExprContexts because they never call
183 * ExecQual or ExecProject.
184 */
185
186 /*
187 * tuple table initialization
188 *
189 * sort nodes only return scan tuples from their sorted relation.
190 */
191 ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
192 ExecInitScanTupleSlot(estate, &sortstate->ss);
193
194 /*
195 * initialize child nodes
196 *
197 * We shield the child node from the need to support REWIND, BACKWARD, or
198 * MARK/RESTORE.
199 */
200 eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
201
202 outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
203
204 /*
205 * initialize tuple type. no need to initialize projection info because
206 * this node doesn't do projections.
207 */
208 ExecAssignResultTypeFromTL(&sortstate->ss.ps);
209 ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
210 sortstate->ss.ps.ps_ProjInfo = NULL;
211
212 SO1_printf("ExecInitSort: %s\n",
213 "sort node initialized");
214
215 return sortstate;
216 }
217
218 /* ----------------------------------------------------------------
219 * ExecEndSort(node)
220 * ----------------------------------------------------------------
221 */
222 void
ExecEndSort(SortState * node)223 ExecEndSort(SortState *node)
224 {
225 SO1_printf("ExecEndSort: %s\n",
226 "shutting down sort node");
227
228 /*
229 * clean out the tuple table
230 */
231 ExecClearTuple(node->ss.ss_ScanTupleSlot);
232 /* must drop pointer to sort result tuple */
233 ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
234
235 /*
236 * Release tuplesort resources
237 */
238 if (node->tuplesortstate != NULL)
239 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
240 node->tuplesortstate = NULL;
241
242 /*
243 * shut down the subplan
244 */
245 ExecEndNode(outerPlanState(node));
246
247 SO1_printf("ExecEndSort: %s\n",
248 "sort node shutdown");
249 }
250
251 /* ----------------------------------------------------------------
252 * ExecSortMarkPos
253 *
254 * Calls tuplesort to save the current position in the sorted file.
255 * ----------------------------------------------------------------
256 */
257 void
ExecSortMarkPos(SortState * node)258 ExecSortMarkPos(SortState *node)
259 {
260 /*
261 * if we haven't sorted yet, just return
262 */
263 if (!node->sort_Done)
264 return;
265
266 tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
267 }
268
269 /* ----------------------------------------------------------------
270 * ExecSortRestrPos
271 *
272 * Calls tuplesort to restore the last saved sort file position.
273 * ----------------------------------------------------------------
274 */
275 void
ExecSortRestrPos(SortState * node)276 ExecSortRestrPos(SortState *node)
277 {
278 /*
279 * if we haven't sorted yet, just return.
280 */
281 if (!node->sort_Done)
282 return;
283
284 /*
285 * restore the scan to the previously marked position
286 */
287 tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
288 }
289
290 void
ExecReScanSort(SortState * node)291 ExecReScanSort(SortState *node)
292 {
293 PlanState *outerPlan = outerPlanState(node);
294
295 /*
296 * If we haven't sorted yet, just return. If outerplan's chgParam is not
297 * NULL then it will be re-scanned by ExecProcNode, else no reason to
298 * re-scan it at all.
299 */
300 if (!node->sort_Done)
301 return;
302
303 /* must drop pointer to sort result tuple */
304 ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
305
306 /*
307 * If subnode is to be rescanned then we forget previous sort results; we
308 * have to re-read the subplan and re-sort. Also must re-sort if the
309 * bounded-sort parameters changed or we didn't select randomAccess.
310 *
311 * Otherwise we can just rewind and rescan the sorted output.
312 */
313 if (outerPlan->chgParam != NULL ||
314 node->bounded != node->bounded_Done ||
315 node->bound != node->bound_Done ||
316 !node->randomAccess)
317 {
318 node->sort_Done = false;
319 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
320 node->tuplesortstate = NULL;
321
322 /*
323 * if chgParam of subnode is not null then plan will be re-scanned by
324 * first ExecProcNode.
325 */
326 if (outerPlan->chgParam == NULL)
327 ExecReScan(outerPlan);
328 }
329 else
330 tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
331 }
332