PostgreSQL Source Code  git master
nodeSort.c
Go to the documentation of this file.
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 *
41 {
42  SortState *node = castNode(SortState, pstate);
43  EState *estate;
44  ScanDirection dir;
45  Tuplesortstate *tuplesortstate;
46  TupleTableSlot *slot;
47 
49 
50  /*
51  * get state info from node
52  */
53  SO1_printf("ExecSort: %s\n",
54  "entering routine");
55 
56  estate = node->ss.ps.state;
57  dir = estate->es_direction;
58  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  if (!node->sort_Done)
66  {
67  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  */
79 
80  /*
81  * Initialize tuplesort module.
82  */
83  SO1_printf("ExecSort: %s\n",
84  "calling tuplesort_begin");
85 
86  outerNode = outerPlanState(node);
87  tupDesc = ExecGetResultType(outerNode);
88 
89  tuplesortstate = tuplesort_begin_heap(tupDesc,
90  plannode->numCols,
91  plannode->sortColIdx,
92  plannode->sortOperators,
93  plannode->collations,
94  plannode->nullsFirst,
95  work_mem,
96  node->randomAccess);
97  if (node->bounded)
98  tuplesort_set_bound(tuplesortstate, node->bound);
99  node->tuplesortstate = (void *) tuplesortstate;
100 
101  /*
102  * Scan the subplan and feed all the tuples to tuplesort.
103  */
104 
105  for (;;)
106  {
107  slot = ExecProcNode(outerNode);
108 
109  if (TupIsNull(slot))
110  break;
111 
112  tuplesort_puttupleslot(tuplesortstate, slot);
113  }
114 
115  /*
116  * Complete the sort.
117  */
118  tuplesort_performsort(tuplesortstate);
119 
120  /*
121  * restore to user specified direction
122  */
123  estate->es_direction = dir;
124 
125  /*
126  * finally set the sorted flag to true
127  */
128  node->sort_Done = true;
129  node->bounded_Done = node->bounded;
130  node->bound_Done = node->bound;
131  if (node->shared_info && node->am_worker)
132  {
134 
136  Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
138  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  slot = node->ss.ps.ps_ResultTupleSlot;
152  (void) tuplesort_gettupleslot(tuplesortstate,
154  false, slot, NULL);
155  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 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  sortstate = makeNode(SortState);
177  sortstate->ss.ps.plan = (Plan *) node;
178  sortstate->ss.ps.state = estate;
179  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  sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
188  EXEC_FLAG_MARK)) != 0;
189 
190  sortstate->bounded = false;
191  sortstate->sort_Done = false;
192  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  ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
207  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  */
216 
217  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  ExecAssignResultTypeFromTL(&sortstate->ss.ps);
224  ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
225  sortstate->ss.ps.ps_ProjInfo = NULL;
226 
227  SO1_printf("ExecInitSort: %s\n",
228  "sort node initialized");
229 
230  return sortstate;
231 }
232 
233 /* ----------------------------------------------------------------
234  * ExecEndSort(node)
235  * ----------------------------------------------------------------
236  */
237 void
239 {
240  SO1_printf("ExecEndSort: %s\n",
241  "shutting down sort node");
242 
243  /*
244  * clean out the tuple table
245  */
247  /* must drop pointer to sort result tuple */
249 
250  /*
251  * Release tuplesort resources
252  */
253  if (node->tuplesortstate != NULL)
255  node->tuplesortstate = NULL;
256 
257  /*
258  * shut down the subplan
259  */
261 
262  SO1_printf("ExecEndSort: %s\n",
263  "sort node shutdown");
264 }
265 
266 /* ----------------------------------------------------------------
267  * ExecSortMarkPos
268  *
269  * Calls tuplesort to save the current position in the sorted file.
270  * ----------------------------------------------------------------
271  */
272 void
274 {
275  /*
276  * if we haven't sorted yet, just return
277  */
278  if (!node->sort_Done)
279  return;
280 
282 }
283 
284 /* ----------------------------------------------------------------
285  * ExecSortRestrPos
286  *
287  * Calls tuplesort to restore the last saved sort file position.
288  * ----------------------------------------------------------------
289  */
290 void
292 {
293  /*
294  * if we haven't sorted yet, just return.
295  */
296  if (!node->sort_Done)
297  return;
298 
299  /*
300  * restore the scan to the previously marked position
301  */
303 }
304 
305 void
307 {
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  if (!node->sort_Done)
316  return;
317 
318  /* must drop pointer to sort result tuple */
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  if (outerPlan->chgParam != NULL ||
329  node->bounded != node->bounded_Done ||
330  node->bound != node->bound_Done ||
331  !node->randomAccess)
332  {
333  node->sort_Done = false;
335  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  if (outerPlan->chgParam == NULL)
342  ExecReScan(outerPlan);
343  }
344  else
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
361 {
362  Size size;
363 
364  /* don't need this if not instrumenting or no workers */
365  if (!node->ss.ps.instrument || pcxt->nworkers == 0)
366  return;
367 
368  size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
369  size = add_size(size, offsetof(SharedSortInfo, sinstrument));
370  shm_toc_estimate_chunk(&pcxt->estimator, size);
371  shm_toc_estimate_keys(&pcxt->estimator, 1);
372 }
373 
374 /* ----------------------------------------------------------------
375  * ExecSortInitializeDSM
376  *
377  * Initialize DSM space for sort statistics.
378  * ----------------------------------------------------------------
379  */
380 void
382 {
383  Size size;
384 
385  /* don't need this if not instrumenting or no workers */
386  if (!node->ss.ps.instrument || pcxt->nworkers == 0)
387  return;
388 
389  size = offsetof(SharedSortInfo, sinstrument)
390  + pcxt->nworkers * sizeof(TuplesortInstrumentation);
391  node->shared_info = shm_toc_allocate(pcxt->toc, size);
392  /* ensure any unfilled slots will contain zeroes */
393  memset(node->shared_info, 0, size);
394  node->shared_info->num_workers = pcxt->nworkers;
395  shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
396  node->shared_info);
397 }
398 
399 /* ----------------------------------------------------------------
400  * ExecSortReInitializeDSM
401  *
402  * Reset shared state before beginning a fresh scan.
403  * ----------------------------------------------------------------
404  */
405 void
407 {
408  /* If there's any instrumentation space, clear it for next time */
409  if (node->shared_info != NULL)
410  {
411  memset(node->shared_info->sinstrument, 0,
413  }
414 }
415 
416 /* ----------------------------------------------------------------
417  * ExecSortInitializeWorker
418  *
419  * Attach worker to DSM space for sort statistics.
420  * ----------------------------------------------------------------
421  */
422 void
424 {
425  node->shared_info =
426  shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
427  node->am_worker = true;
428 }
429 
430 /* ----------------------------------------------------------------
431  * ExecSortRetrieveInstrumentation
432  *
433  * Transfer sort statistics from DSM to private memory.
434  * ----------------------------------------------------------------
435  */
436 void
438 {
439  Size size;
440  SharedSortInfo *si;
441 
442  if (node->shared_info == NULL)
443  return;
444 
445  size = offsetof(SharedSortInfo, sinstrument)
447  si = palloc(size);
448  memcpy(si, node->shared_info, size);
449  node->shared_info = si;
450 }
SortState * ExecInitSort(Sort *node, EState *estate, int eflags)
Definition: nodeSort.c:166
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1656
struct TuplesortInstrumentation TuplesortInstrumentation
void ExecInitScanTupleSlot(EState *estate, ScanState *scanstate)
Definition: execTuples.c:842
void tuplesort_restorepos(Tuplesortstate *state)
Definition: tuplesort.c:2907
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:884
Instrumentation * instrument
Definition: execnodes.h:859
bool bounded_Done
Definition: execnodes.h:1767
#define ScanDirectionIsForward(direction)
Definition: sdir.h:55
void ExecSortEstimate(SortState *node, ParallelContext *pcxt)
Definition: nodeSort.c:360
#define castNode(_type_, nodeptr)
Definition: nodes.h:579
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:523
bool bounded
Definition: execnodes.h:1764
shm_toc_estimator estimator
Definition: parallel.h:41
void ExecSortInitializeWorker(SortState *node, ParallelWorkerContext *pwcxt)
Definition: nodeSort.c:423
int64 bound
Definition: execnodes.h:1765
void ExecReScan(PlanState *node)
Definition: execAmi.c:76
TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: execTuples.c:439
int plan_node_id
Definition: plannodes.h:143
SharedSortInfo * shared_info
Definition: execnodes.h:1771
bool * nullsFirst
Definition: plannodes.h:749
TupleTableSlot * ss_ScanTupleSlot
Definition: execnodes.h:1106
bool am_worker
Definition: execnodes.h:1770
EState * state
Definition: execnodes.h:851
#define SO1_printf(s, p)
Definition: execdebug.h:92
#define shm_toc_estimate_chunk(e, sz)
Definition: shm_toc.h:51
void tuplesort_get_stats(Tuplesortstate *state, TuplesortInstrumentation *stats)
Definition: tuplesort.c:2941
Oid * sortOperators
Definition: plannodes.h:747
ScanDirection es_direction
Definition: execnodes.h:428
void ExecAssignResultTypeFromTL(PlanState *planstate)
Definition: execUtils.c:447
void ExecReScanSort(SortState *node)
Definition: nodeSort.c:306
PlanState ps
Definition: execnodes.h:1103
void * tuplesortstate
Definition: execnodes.h:1769
void ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
Definition: nodeSort.c:381
TupleTableSlot * ps_ResultTupleSlot
Definition: execnodes.h:882
static TupleTableSlot * ExecSort(PlanState *pstate)
Definition: nodeSort.c:40
void ExecInitResultTupleSlot(EState *estate, PlanState *planstate)
Definition: execTuples.c:832
void tuplesort_rescan(Tuplesortstate *state)
Definition: tuplesort.c:2840
void ExecEndSort(SortState *node)
Definition: nodeSort.c:238
#define EXEC_FLAG_BACKWARD
Definition: executor.h:60
#define outerPlanState(node)
Definition: execnodes.h:895
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
Definition: tuplesort.c:1996
void tuplesort_set_bound(Tuplesortstate *state, int64 bound)
Definition: tuplesort.c:1060
void ExecSortMarkPos(SortState *node)
Definition: nodeSort.c:273
ScanDirection
Definition: sdir.h:22
void ExecSortReInitializeDSM(SortState *node, ParallelContext *pcxt)
Definition: nodeSort.c:406
int ParallelWorkerNumber
Definition: parallel.c:100
#define TupIsNull(slot)
Definition: tuptable.h:138
int64 bound_Done
Definition: execnodes.h:1768
ScanState ss
Definition: execnodes.h:1762
#define EXEC_FLAG_REWIND
Definition: executor.h:59
#define IsParallelWorker()
Definition: parallel.h:58
Bitmapset * chgParam
Definition: execnodes.h:877
#define outerPlan(node)
Definition: plannodes.h:174
int numCols
Definition: plannodes.h:745
Size mul_size(Size s1, Size s2)
Definition: shmem.c:492
ExecProcNodeMtd ExecProcNode
Definition: execnodes.h:855
Size add_size(Size s1, Size s2)
Definition: shmem.c:475
static TupleTableSlot * ExecProcNode(PlanState *node)
Definition: executor.h:236
int work_mem
Definition: globals.c:113
Plan * plan
Definition: execnodes.h:849
#define makeNode(_type_)
Definition: nodes.h:558
#define Assert(condition)
Definition: c.h:670
#define EXEC_FLAG_MARK
Definition: executor.h:61
void ExecSortRestrPos(SortState *node)
Definition: nodeSort.c:291
size_t Size
Definition: c.h:404
#define shm_toc_estimate_keys(e, cnt)
Definition: shm_toc.h:53
bool randomAccess
Definition: execnodes.h:1763
bool sort_Done
Definition: execnodes.h:1766
void * shm_toc_allocate(shm_toc *toc, Size nbytes)
Definition: shm_toc.c:88
TupleDesc ExecGetResultType(PlanState *planstate)
Definition: execUtils.c:476
AttrNumber * sortColIdx
Definition: plannodes.h:746
Tuplesortstate * tuplesort_begin_heap(TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, bool randomAccess)
Definition: tuplesort.c:693
void shm_toc_insert(shm_toc *toc, uint64 key, void *address)
Definition: shm_toc.c:171
void ExecAssignScanTypeFromOuterPlan(ScanState *scanstate)
Definition: execUtils.c:559
void * palloc(Size size)
Definition: mcxt.c:848
void tuplesort_markpos(Tuplesortstate *state)
Definition: tuplesort.c:2875
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
void ExecSortRetrieveInstrumentation(SortState *node)
Definition: nodeSort.c:437
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1104
Oid * collations
Definition: plannodes.h:748
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:139
TuplesortInstrumentation sinstrument[FLEXIBLE_ARRAY_MEMBER]
Definition: execnodes.h:1753
void * shm_toc_lookup(shm_toc *toc, uint64 key, bool noError)
Definition: shm_toc.c:232
#define offsetof(type, field)
Definition: c.h:593
shm_toc * toc
Definition: parallel.h:44
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
Definition: tuplesort.c:1301