Line data Source code
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 "access/parallel.h"
19 : #include "executor/execdebug.h"
20 : #include "executor/nodeSort.h"
21 : #include "miscadmin.h"
22 : #include "utils/tuplesort.h"
23 :
24 :
25 : /* ----------------------------------------------------------------
26 : * ExecSort
27 : *
28 : * Sorts tuples from the outer subtree of the node using tuplesort,
29 : * which saves the results in a temporary file or memory. After the
30 : * initial call, returns a tuple from the file with each call.
31 : *
32 : * Conditions:
33 : * -- none.
34 : *
35 : * Initial States:
36 : * -- the outer child is prepared to return the first tuple.
37 : * ----------------------------------------------------------------
38 : */
39 : static TupleTableSlot *
40 262028 : ExecSort(PlanState *pstate)
41 : {
42 262028 : SortState *node = castNode(SortState, pstate);
43 : EState *estate;
44 : ScanDirection dir;
45 : Tuplesortstate *tuplesortstate;
46 : TupleTableSlot *slot;
47 :
48 262028 : CHECK_FOR_INTERRUPTS();
49 :
50 : /*
51 : * get state info from node
52 : */
53 : SO1_printf("ExecSort: %s\n",
54 : "entering routine");
55 :
56 262028 : estate = node->ss.ps.state;
57 262028 : dir = estate->es_direction;
58 262028 : tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
59 :
60 : /*
61 : * If first time through, read all tuples from outer plan and pass them to
62 : * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
63 : */
64 :
65 262028 : if (!node->sort_Done)
66 : {
67 2696 : Sort *plannode = (Sort *) node->ss.ps.plan;
68 : PlanState *outerNode;
69 : TupleDesc tupDesc;
70 :
71 : SO1_printf("ExecSort: %s\n",
72 : "sorting subplan");
73 :
74 : /*
75 : * Want to scan subplan in the forward direction while creating the
76 : * sorted data.
77 : */
78 2696 : estate->es_direction = ForwardScanDirection;
79 :
80 : /*
81 : * Initialize tuplesort module.
82 : */
83 : SO1_printf("ExecSort: %s\n",
84 : "calling tuplesort_begin");
85 :
86 2696 : outerNode = outerPlanState(node);
87 2696 : tupDesc = ExecGetResultType(outerNode);
88 :
89 2696 : tuplesortstate = tuplesort_begin_heap(tupDesc,
90 : plannode->numCols,
91 : plannode->sortColIdx,
92 : plannode->sortOperators,
93 : plannode->collations,
94 : plannode->nullsFirst,
95 : work_mem,
96 2696 : node->randomAccess);
97 2695 : if (node->bounded)
98 97 : tuplesort_set_bound(tuplesortstate, node->bound);
99 2695 : node->tuplesortstate = (void *) tuplesortstate;
100 :
101 : /*
102 : * Scan the subplan and feed all the tuples to tuplesort.
103 : */
104 :
105 : for (;;)
106 : {
107 301038 : slot = ExecProcNode(outerNode);
108 :
109 301038 : if (TupIsNull(slot))
110 : break;
111 :
112 298343 : tuplesort_puttupleslot(tuplesortstate, slot);
113 298343 : }
114 :
115 : /*
116 : * Complete the sort.
117 : */
118 2695 : tuplesort_performsort(tuplesortstate);
119 :
120 : /*
121 : * restore to user specified direction
122 : */
123 2695 : estate->es_direction = dir;
124 :
125 : /*
126 : * finally set the sorted flag to true
127 : */
128 2695 : node->sort_Done = true;
129 2695 : node->bounded_Done = node->bounded;
130 2695 : node->bound_Done = node->bound;
131 2695 : if (node->shared_info && node->am_worker)
132 : {
133 : TuplesortInstrumentation *si;
134 :
135 0 : Assert(IsParallelWorker());
136 0 : Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
137 0 : si = &node->shared_info->sinstrument[ParallelWorkerNumber];
138 0 : tuplesort_get_stats(tuplesortstate, si);
139 : }
140 : SO1_printf("ExecSort: %s\n", "sorting done");
141 : }
142 :
143 : SO1_printf("ExecSort: %s\n",
144 : "retrieving tuple from tuplesort");
145 :
146 : /*
147 : * Get the first or next tuple from tuplesort. Returns NULL if no more
148 : * tuples. Note that we only rely on slot tuple remaining valid until the
149 : * next fetch from the tuplesort.
150 : */
151 262027 : slot = node->ss.ps.ps_ResultTupleSlot;
152 262027 : (void) tuplesort_gettupleslot(tuplesortstate,
153 : ScanDirectionIsForward(dir),
154 : false, slot, NULL);
155 262027 : return slot;
156 : }
157 :
158 : /* ----------------------------------------------------------------
159 : * ExecInitSort
160 : *
161 : * Creates the run-time state information for the sort node
162 : * produced by the planner and initializes its outer subtree.
163 : * ----------------------------------------------------------------
164 : */
165 : SortState *
166 2867 : ExecInitSort(Sort *node, EState *estate, int eflags)
167 : {
168 : SortState *sortstate;
169 :
170 : SO1_printf("ExecInitSort: %s\n",
171 : "initializing sort node");
172 :
173 : /*
174 : * create state structure
175 : */
176 2867 : sortstate = makeNode(SortState);
177 2867 : sortstate->ss.ps.plan = (Plan *) node;
178 2867 : sortstate->ss.ps.state = estate;
179 2867 : sortstate->ss.ps.ExecProcNode = ExecSort;
180 :
181 : /*
182 : * We must have random access to the sort output to do backward scan or
183 : * mark/restore. We also prefer to materialize the sort output if we
184 : * might be called on to rewind and replay it many times.
185 : */
186 5734 : sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
187 : EXEC_FLAG_BACKWARD |
188 2867 : EXEC_FLAG_MARK)) != 0;
189 :
190 2867 : sortstate->bounded = false;
191 2867 : sortstate->sort_Done = false;
192 2867 : sortstate->tuplesortstate = NULL;
193 :
194 : /*
195 : * Miscellaneous initialization
196 : *
197 : * Sort nodes don't initialize their ExprContexts because they never call
198 : * ExecQual or ExecProject.
199 : */
200 :
201 : /*
202 : * tuple table initialization
203 : *
204 : * sort nodes only return scan tuples from their sorted relation.
205 : */
206 2867 : ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
207 2867 : ExecInitScanTupleSlot(estate, &sortstate->ss);
208 :
209 : /*
210 : * initialize child nodes
211 : *
212 : * We shield the child node from the need to support REWIND, BACKWARD, or
213 : * MARK/RESTORE.
214 : */
215 2867 : eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
216 :
217 2867 : outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
218 :
219 : /*
220 : * initialize tuple type. no need to initialize projection info because
221 : * this node doesn't do projections.
222 : */
223 2866 : ExecAssignResultTypeFromTL(&sortstate->ss.ps);
224 2866 : ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
225 2866 : sortstate->ss.ps.ps_ProjInfo = NULL;
226 :
227 : SO1_printf("ExecInitSort: %s\n",
228 : "sort node initialized");
229 :
230 2866 : return sortstate;
231 : }
232 :
233 : /* ----------------------------------------------------------------
234 : * ExecEndSort(node)
235 : * ----------------------------------------------------------------
236 : */
237 : void
238 2863 : ExecEndSort(SortState *node)
239 : {
240 : SO1_printf("ExecEndSort: %s\n",
241 : "shutting down sort node");
242 :
243 : /*
244 : * clean out the tuple table
245 : */
246 2863 : ExecClearTuple(node->ss.ss_ScanTupleSlot);
247 : /* must drop pointer to sort result tuple */
248 2863 : ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
249 :
250 : /*
251 : * Release tuplesort resources
252 : */
253 2863 : if (node->tuplesortstate != NULL)
254 2589 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
255 2863 : node->tuplesortstate = NULL;
256 :
257 : /*
258 : * shut down the subplan
259 : */
260 2863 : ExecEndNode(outerPlanState(node));
261 :
262 : SO1_printf("ExecEndSort: %s\n",
263 : "sort node shutdown");
264 2863 : }
265 :
266 : /* ----------------------------------------------------------------
267 : * ExecSortMarkPos
268 : *
269 : * Calls tuplesort to save the current position in the sorted file.
270 : * ----------------------------------------------------------------
271 : */
272 : void
273 26367 : ExecSortMarkPos(SortState *node)
274 : {
275 : /*
276 : * if we haven't sorted yet, just return
277 : */
278 26367 : if (!node->sort_Done)
279 26367 : return;
280 :
281 26367 : tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
282 : }
283 :
284 : /* ----------------------------------------------------------------
285 : * ExecSortRestrPos
286 : *
287 : * Calls tuplesort to restore the last saved sort file position.
288 : * ----------------------------------------------------------------
289 : */
290 : void
291 1325 : ExecSortRestrPos(SortState *node)
292 : {
293 : /*
294 : * if we haven't sorted yet, just return.
295 : */
296 1325 : if (!node->sort_Done)
297 1325 : return;
298 :
299 : /*
300 : * restore the scan to the previously marked position
301 : */
302 1325 : tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
303 : }
304 :
305 : void
306 136 : ExecReScanSort(SortState *node)
307 : {
308 136 : PlanState *outerPlan = outerPlanState(node);
309 :
310 : /*
311 : * If we haven't sorted yet, just return. If outerplan's chgParam is not
312 : * NULL then it will be re-scanned by ExecProcNode, else no reason to
313 : * re-scan it at all.
314 : */
315 136 : if (!node->sort_Done)
316 168 : return;
317 :
318 : /* must drop pointer to sort result tuple */
319 104 : ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
320 :
321 : /*
322 : * If subnode is to be rescanned then we forget previous sort results; we
323 : * have to re-read the subplan and re-sort. Also must re-sort if the
324 : * bounded-sort parameters changed or we didn't select randomAccess.
325 : *
326 : * Otherwise we can just rewind and rescan the sorted output.
327 : */
328 126 : if (outerPlan->chgParam != NULL ||
329 44 : node->bounded != node->bounded_Done ||
330 35 : node->bound != node->bound_Done ||
331 13 : !node->randomAccess)
332 : {
333 104 : node->sort_Done = false;
334 104 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
335 104 : node->tuplesortstate = NULL;
336 :
337 : /*
338 : * if chgParam of subnode is not null then plan will be re-scanned by
339 : * first ExecProcNode.
340 : */
341 208 : if (outerPlan->chgParam == NULL)
342 22 : ExecReScan(outerPlan);
343 : }
344 : else
345 0 : tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
346 : }
347 :
348 : /* ----------------------------------------------------------------
349 : * Parallel Query Support
350 : * ----------------------------------------------------------------
351 : */
352 :
353 : /* ----------------------------------------------------------------
354 : * ExecSortEstimate
355 : *
356 : * Estimate space required to propagate sort statistics.
357 : * ----------------------------------------------------------------
358 : */
359 : void
360 5 : ExecSortEstimate(SortState *node, ParallelContext *pcxt)
361 : {
362 : Size size;
363 :
364 : /* don't need this if not instrumenting or no workers */
365 5 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
366 10 : return;
367 :
368 0 : size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
369 0 : size = add_size(size, offsetof(SharedSortInfo, sinstrument));
370 0 : shm_toc_estimate_chunk(&pcxt->estimator, size);
371 0 : shm_toc_estimate_keys(&pcxt->estimator, 1);
372 : }
373 :
374 : /* ----------------------------------------------------------------
375 : * ExecSortInitializeDSM
376 : *
377 : * Initialize DSM space for sort statistics.
378 : * ----------------------------------------------------------------
379 : */
380 : void
381 5 : ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
382 : {
383 : Size size;
384 :
385 : /* don't need this if not instrumenting or no workers */
386 5 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
387 10 : return;
388 :
389 0 : size = offsetof(SharedSortInfo, sinstrument)
390 0 : + pcxt->nworkers * sizeof(TuplesortInstrumentation);
391 0 : node->shared_info = shm_toc_allocate(pcxt->toc, size);
392 : /* ensure any unfilled slots will contain zeroes */
393 0 : memset(node->shared_info, 0, size);
394 0 : node->shared_info->num_workers = pcxt->nworkers;
395 0 : shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
396 0 : node->shared_info);
397 : }
398 :
399 : /* ----------------------------------------------------------------
400 : * ExecSortReInitializeDSM
401 : *
402 : * Reset shared state before beginning a fresh scan.
403 : * ----------------------------------------------------------------
404 : */
405 : void
406 2 : ExecSortReInitializeDSM(SortState *node, ParallelContext *pcxt)
407 : {
408 : /* If there's any instrumentation space, clear it for next time */
409 2 : if (node->shared_info != NULL)
410 : {
411 0 : memset(node->shared_info->sinstrument, 0,
412 0 : node->shared_info->num_workers * sizeof(TuplesortInstrumentation));
413 : }
414 2 : }
415 :
416 : /* ----------------------------------------------------------------
417 : * ExecSortInitializeWorker
418 : *
419 : * Attach worker to DSM space for sort statistics.
420 : * ----------------------------------------------------------------
421 : */
422 : void
423 21 : ExecSortInitializeWorker(SortState *node, shm_toc *toc)
424 : {
425 21 : node->shared_info =
426 21 : shm_toc_lookup(toc, node->ss.ps.plan->plan_node_id, true);
427 21 : node->am_worker = true;
428 21 : }
429 :
430 : /* ----------------------------------------------------------------
431 : * ExecSortRetrieveInstrumentation
432 : *
433 : * Transfer sort statistics from DSM to private memory.
434 : * ----------------------------------------------------------------
435 : */
436 : void
437 0 : ExecSortRetrieveInstrumentation(SortState *node)
438 : {
439 : Size size;
440 : SharedSortInfo *si;
441 :
442 0 : if (node->shared_info == NULL)
443 0 : return;
444 :
445 0 : size = offsetof(SharedSortInfo, sinstrument)
446 0 : + node->shared_info->num_workers * sizeof(TuplesortInstrumentation);
447 0 : si = palloc(size);
448 0 : memcpy(si, node->shared_info, size);
449 0 : node->shared_info = si;
450 : }
|
