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