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-2020, 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  NULL,
97  node->randomAccess);
98  if (node->bounded)
99  tuplesort_set_bound(tuplesortstate, node->bound);
100  node->tuplesortstate = (void *) tuplesortstate;
101 
102  /*
103  * Scan the subplan and feed all the tuples to tuplesort.
104  */
105 
106  for (;;)
107  {
108  slot = ExecProcNode(outerNode);
109 
110  if (TupIsNull(slot))
111  break;
112 
113  tuplesort_puttupleslot(tuplesortstate, slot);
114  }
115 
116  /*
117  * Complete the sort.
118  */
119  tuplesort_performsort(tuplesortstate);
120 
121  /*
122  * restore to user specified direction
123  */
124  estate->es_direction = dir;
125 
126  /*
127  * finally set the sorted flag to true
128  */
129  node->sort_Done = true;
130  node->bounded_Done = node->bounded;
131  node->bound_Done = node->bound;
132  if (node->shared_info && node->am_worker)
133  {
135 
137  Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
139  tuplesort_get_stats(tuplesortstate, si);
140  }
141  SO1_printf("ExecSort: %s\n", "sorting done");
142  }
143 
144  SO1_printf("ExecSort: %s\n",
145  "retrieving tuple from tuplesort");
146 
147  /*
148  * Get the first or next tuple from tuplesort. Returns NULL if no more
149  * tuples. Note that we only rely on slot tuple remaining valid until the
150  * next fetch from the tuplesort.
151  */
152  slot = node->ss.ps.ps_ResultTupleSlot;
153  (void) tuplesort_gettupleslot(tuplesortstate,
155  false, slot, NULL);
156  return slot;
157 }
158 
159 /* ----------------------------------------------------------------
160  * ExecInitSort
161  *
162  * Creates the run-time state information for the sort node
163  * produced by the planner and initializes its outer subtree.
164  * ----------------------------------------------------------------
165  */
166 SortState *
167 ExecInitSort(Sort *node, EState *estate, int eflags)
168 {
169  SortState *sortstate;
170 
171  SO1_printf("ExecInitSort: %s\n",
172  "initializing sort node");
173 
174  /*
175  * create state structure
176  */
177  sortstate = makeNode(SortState);
178  sortstate->ss.ps.plan = (Plan *) node;
179  sortstate->ss.ps.state = estate;
180  sortstate->ss.ps.ExecProcNode = ExecSort;
181 
182  /*
183  * We must have random access to the sort output to do backward scan or
184  * mark/restore. We also prefer to materialize the sort output if we
185  * might be called on to rewind and replay it many times.
186  */
187  sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
189  EXEC_FLAG_MARK)) != 0;
190 
191  sortstate->bounded = false;
192  sortstate->sort_Done = false;
193  sortstate->tuplesortstate = NULL;
194 
195  /*
196  * Miscellaneous initialization
197  *
198  * Sort nodes don't initialize their ExprContexts because they never call
199  * ExecQual or ExecProject.
200  */
201 
202  /*
203  * initialize child nodes
204  *
205  * We shield the child node from the need to support REWIND, BACKWARD, or
206  * MARK/RESTORE.
207  */
209 
210  outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
211 
212  /*
213  * Initialize scan slot and type.
214  */
215  ExecCreateScanSlotFromOuterPlan(estate, &sortstate->ss, &TTSOpsVirtual);
216 
217  /*
218  * Initialize return slot and type. No need to initialize projection info
219  * because this node doesn't do projections.
220  */
222  sortstate->ss.ps.ps_ProjInfo = NULL;
223 
224  SO1_printf("ExecInitSort: %s\n",
225  "sort node initialized");
226 
227  return sortstate;
228 }
229 
230 /* ----------------------------------------------------------------
231  * ExecEndSort(node)
232  * ----------------------------------------------------------------
233  */
234 void
236 {
237  SO1_printf("ExecEndSort: %s\n",
238  "shutting down sort node");
239 
240  /*
241  * clean out the tuple table
242  */
244  /* must drop pointer to sort result tuple */
246 
247  /*
248  * Release tuplesort resources
249  */
250  if (node->tuplesortstate != NULL)
252  node->tuplesortstate = NULL;
253 
254  /*
255  * shut down the subplan
256  */
258 
259  SO1_printf("ExecEndSort: %s\n",
260  "sort node shutdown");
261 }
262 
263 /* ----------------------------------------------------------------
264  * ExecSortMarkPos
265  *
266  * Calls tuplesort to save the current position in the sorted file.
267  * ----------------------------------------------------------------
268  */
269 void
271 {
272  /*
273  * if we haven't sorted yet, just return
274  */
275  if (!node->sort_Done)
276  return;
277 
279 }
280 
281 /* ----------------------------------------------------------------
282  * ExecSortRestrPos
283  *
284  * Calls tuplesort to restore the last saved sort file position.
285  * ----------------------------------------------------------------
286  */
287 void
289 {
290  /*
291  * if we haven't sorted yet, just return.
292  */
293  if (!node->sort_Done)
294  return;
295 
296  /*
297  * restore the scan to the previously marked position
298  */
300 }
301 
302 void
304 {
306 
307  /*
308  * If we haven't sorted yet, just return. If outerplan's chgParam is not
309  * NULL then it will be re-scanned by ExecProcNode, else no reason to
310  * re-scan it at all.
311  */
312  if (!node->sort_Done)
313  return;
314 
315  /* must drop pointer to sort result tuple */
317 
318  /*
319  * If subnode is to be rescanned then we forget previous sort results; we
320  * have to re-read the subplan and re-sort. Also must re-sort if the
321  * bounded-sort parameters changed or we didn't select randomAccess.
322  *
323  * Otherwise we can just rewind and rescan the sorted output.
324  */
325  if (outerPlan->chgParam != NULL ||
326  node->bounded != node->bounded_Done ||
327  node->bound != node->bound_Done ||
328  !node->randomAccess)
329  {
330  node->sort_Done = false;
332  node->tuplesortstate = NULL;
333 
334  /*
335  * if chgParam of subnode is not null then plan will be re-scanned by
336  * first ExecProcNode.
337  */
338  if (outerPlan->chgParam == NULL)
339  ExecReScan(outerPlan);
340  }
341  else
343 }
344 
345 /* ----------------------------------------------------------------
346  * Parallel Query Support
347  * ----------------------------------------------------------------
348  */
349 
350 /* ----------------------------------------------------------------
351  * ExecSortEstimate
352  *
353  * Estimate space required to propagate sort statistics.
354  * ----------------------------------------------------------------
355  */
356 void
358 {
359  Size size;
360 
361  /* don't need this if not instrumenting or no workers */
362  if (!node->ss.ps.instrument || pcxt->nworkers == 0)
363  return;
364 
365  size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
366  size = add_size(size, offsetof(SharedSortInfo, sinstrument));
367  shm_toc_estimate_chunk(&pcxt->estimator, size);
368  shm_toc_estimate_keys(&pcxt->estimator, 1);
369 }
370 
371 /* ----------------------------------------------------------------
372  * ExecSortInitializeDSM
373  *
374  * Initialize DSM space for sort statistics.
375  * ----------------------------------------------------------------
376  */
377 void
379 {
380  Size size;
381 
382  /* don't need this if not instrumenting or no workers */
383  if (!node->ss.ps.instrument || pcxt->nworkers == 0)
384  return;
385 
386  size = offsetof(SharedSortInfo, sinstrument)
387  + pcxt->nworkers * sizeof(TuplesortInstrumentation);
388  node->shared_info = shm_toc_allocate(pcxt->toc, size);
389  /* ensure any unfilled slots will contain zeroes */
390  memset(node->shared_info, 0, size);
391  node->shared_info->num_workers = pcxt->nworkers;
392  shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
393  node->shared_info);
394 }
395 
396 /* ----------------------------------------------------------------
397  * ExecSortInitializeWorker
398  *
399  * Attach worker to DSM space for sort statistics.
400  * ----------------------------------------------------------------
401  */
402 void
404 {
405  node->shared_info =
406  shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
407  node->am_worker = true;
408 }
409 
410 /* ----------------------------------------------------------------
411  * ExecSortRetrieveInstrumentation
412  *
413  * Transfer sort statistics from DSM to private memory.
414  * ----------------------------------------------------------------
415  */
416 void
418 {
419  Size size;
420  SharedSortInfo *si;
421 
422  if (node->shared_info == NULL)
423  return;
424 
425  size = offsetof(SharedSortInfo, sinstrument)
427  si = palloc(size);
428  memcpy(si, node->shared_info, size);
429  node->shared_info = si;
430 }
SortState * ExecInitSort(Sort *node, EState *estate, int eflags)
Definition: nodeSort.c:167
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:2021
struct TuplesortInstrumentation TuplesortInstrumentation
void tuplesort_restorepos(Tuplesortstate *state)
Definition: tuplesort.c:3325
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:979
Instrumentation * instrument
Definition: execnodes.h:949
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:425
bool bounded_Done
Definition: execnodes.h:2018
#define ScanDirectionIsForward(direction)
Definition: sdir.h:55
void ExecSortEstimate(SortState *node, ParallelContext *pcxt)
Definition: nodeSort.c:357
#define castNode(_type_, nodeptr)
Definition: nodes.h:597
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:543
bool bounded
Definition: execnodes.h:2015
shm_toc_estimator estimator
Definition: parallel.h:42
void ExecSortInitializeWorker(SortState *node, ParallelWorkerContext *pwcxt)
Definition: nodeSort.c:403
int64 bound
Definition: execnodes.h:2016
void ExecReScan(PlanState *node)
Definition: execAmi.c:76
const TupleTableSlotOps TTSOpsVirtual
Definition: execTuples.c:83
int plan_node_id
Definition: plannodes.h:135
SharedSortInfo * shared_info
Definition: execnodes.h:2022
bool * nullsFirst
Definition: plannodes.h:774
TupleTableSlot * ss_ScanTupleSlot
Definition: execnodes.h:1331
bool am_worker
Definition: execnodes.h:2021
EState * state
Definition: execnodes.h:941
#define SO1_printf(s, p)
Definition: execdebug.h:93
#define shm_toc_estimate_chunk(e, sz)
Definition: shm_toc.h:51
void tuplesort_get_stats(Tuplesortstate *state, TuplesortInstrumentation *stats)
Definition: tuplesort.c:3359
Oid * sortOperators
Definition: plannodes.h:772
ScanDirection es_direction
Definition: execnodes.h:516
void ExecReScanSort(SortState *node)
Definition: nodeSort.c:303
Tuplesortstate * tuplesort_begin_heap(TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:878
PlanState ps
Definition: execnodes.h:1328
void * tuplesortstate
Definition: execnodes.h:2020
void ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
Definition: nodeSort.c:378
TupleTableSlot * ps_ResultTupleSlot
Definition: execnodes.h:977
static TupleTableSlot * ExecSort(PlanState *pstate)
Definition: nodeSort.c:40
void tuplesort_rescan(Tuplesortstate *state)
Definition: tuplesort.c:3258
void ExecEndSort(SortState *node)
Definition: nodeSort.c:235
#define EXEC_FLAG_BACKWARD
Definition: executor.h:58
#define outerPlanState(node)
Definition: execnodes.h:1033
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
Definition: tuplesort.c:2389
void tuplesort_set_bound(Tuplesortstate *state, int64 bound)
Definition: tuplesort.c:1315
void ExecSortMarkPos(SortState *node)
Definition: nodeSort.c:270
ScanDirection
Definition: sdir.h:22
int ParallelWorkerNumber
Definition: parallel.c:112
#define TupIsNull(slot)
Definition: tuptable.h:292
int64 bound_Done
Definition: execnodes.h:2019
ScanState ss
Definition: execnodes.h:2013
#define EXEC_FLAG_REWIND
Definition: executor.h:57
#define IsParallelWorker()
Definition: parallel.h:61
Bitmapset * chgParam
Definition: execnodes.h:971
#define outerPlan(node)
Definition: plannodes.h:166
int numCols
Definition: plannodes.h:770
Size mul_size(Size s1, Size s2)
Definition: shmem.c:515
ExecProcNodeMtd ExecProcNode
Definition: execnodes.h:945
Size add_size(Size s1, Size s2)
Definition: shmem.c:498
static TupleTableSlot * ExecProcNode(PlanState *node)
Definition: executor.h:239
int work_mem
Definition: globals.c:121
Plan * plan
Definition: execnodes.h:939
#define makeNode(_type_)
Definition: nodes.h:576
#define Assert(condition)
Definition: c.h:746
#define EXEC_FLAG_MARK
Definition: executor.h:59
void ExecSortRestrPos(SortState *node)
Definition: nodeSort.c:288
size_t Size
Definition: c.h:474
#define shm_toc_estimate_keys(e, cnt)
Definition: shm_toc.h:53
bool randomAccess
Definition: execnodes.h:2014
bool sort_Done
Definition: execnodes.h:2017
void ExecInitResultTupleSlotTL(PlanState *planstate, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1769
void * shm_toc_allocate(shm_toc *toc, Size nbytes)
Definition: shm_toc.c:88
TupleDesc ExecGetResultType(PlanState *planstate)
Definition: execUtils.c:489
AttrNumber * sortColIdx
Definition: plannodes.h:771
void shm_toc_insert(shm_toc *toc, uint64 key, void *address)
Definition: shm_toc.c:171
void * palloc(Size size)
Definition: mcxt.c:950
void tuplesort_markpos(Tuplesortstate *state)
Definition: tuplesort.c:3293
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
void ExecSortRetrieveInstrumentation(SortState *node)
Definition: nodeSort.c:417
void ExecCreateScanSlotFromOuterPlan(EState *estate, ScanState *scanstate, const TupleTableSlotOps *tts_ops)
Definition: execUtils.c:681
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1445
Oid * collations
Definition: plannodes.h:773
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:139
TuplesortInstrumentation sinstrument[FLEXIBLE_ARRAY_MEMBER]
Definition: execnodes.h:2004
const TupleTableSlotOps TTSOpsMinimalTuple
Definition: execTuples.c:85
void * shm_toc_lookup(shm_toc *toc, uint64 key, bool noError)
Definition: shm_toc.c:232
#define offsetof(type, field)
Definition: c.h:669
shm_toc * toc
Definition: parallel.h:45
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
Definition: tuplesort.c:1665