PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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 "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  */
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  */
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. Note that we only rely on slot tuple remaining valid until the
136  * next fetch from the tuplesort.
137  */
138  slot = node->ss.ps.ps_ResultTupleSlot;
139  (void) tuplesort_gettupleslot(tuplesortstate,
141  false, slot, NULL);
142  return slot;
143 }
144 
145 /* ----------------------------------------------------------------
146  * ExecInitSort
147  *
148  * Creates the run-time state information for the sort node
149  * produced by the planner and initializes its outer subtree.
150  * ----------------------------------------------------------------
151  */
152 SortState *
153 ExecInitSort(Sort *node, EState *estate, int eflags)
154 {
155  SortState *sortstate;
156 
157  SO1_printf("ExecInitSort: %s\n",
158  "initializing sort node");
159 
160  /*
161  * create state structure
162  */
163  sortstate = makeNode(SortState);
164  sortstate->ss.ps.plan = (Plan *) node;
165  sortstate->ss.ps.state = estate;
166 
167  /*
168  * We must have random access to the sort output to do backward scan or
169  * mark/restore. We also prefer to materialize the sort output if we
170  * might be called on to rewind and replay it many times.
171  */
172  sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
174  EXEC_FLAG_MARK)) != 0;
175 
176  sortstate->bounded = false;
177  sortstate->sort_Done = false;
178  sortstate->tuplesortstate = NULL;
179 
180  /*
181  * Miscellaneous initialization
182  *
183  * Sort nodes don't initialize their ExprContexts because they never call
184  * ExecQual or ExecProject.
185  */
186 
187  /*
188  * tuple table initialization
189  *
190  * sort nodes only return scan tuples from their sorted relation.
191  */
192  ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
193  ExecInitScanTupleSlot(estate, &sortstate->ss);
194 
195  /*
196  * initialize child nodes
197  *
198  * We shield the child node from the need to support REWIND, BACKWARD, or
199  * MARK/RESTORE.
200  */
202 
203  outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
204 
205  /*
206  * initialize tuple type. no need to initialize projection info because
207  * this node doesn't do projections.
208  */
209  ExecAssignResultTypeFromTL(&sortstate->ss.ps);
210  ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
211  sortstate->ss.ps.ps_ProjInfo = NULL;
212 
213  SO1_printf("ExecInitSort: %s\n",
214  "sort node initialized");
215 
216  return sortstate;
217 }
218 
219 /* ----------------------------------------------------------------
220  * ExecEndSort(node)
221  * ----------------------------------------------------------------
222  */
223 void
225 {
226  SO1_printf("ExecEndSort: %s\n",
227  "shutting down sort node");
228 
229  /*
230  * clean out the tuple table
231  */
233  /* must drop pointer to sort result tuple */
235 
236  /*
237  * Release tuplesort resources
238  */
239  if (node->tuplesortstate != NULL)
241  node->tuplesortstate = NULL;
242 
243  /*
244  * shut down the subplan
245  */
247 
248  SO1_printf("ExecEndSort: %s\n",
249  "sort node shutdown");
250 }
251 
252 /* ----------------------------------------------------------------
253  * ExecSortMarkPos
254  *
255  * Calls tuplesort to save the current position in the sorted file.
256  * ----------------------------------------------------------------
257  */
258 void
260 {
261  /*
262  * if we haven't sorted yet, just return
263  */
264  if (!node->sort_Done)
265  return;
266 
268 }
269 
270 /* ----------------------------------------------------------------
271  * ExecSortRestrPos
272  *
273  * Calls tuplesort to restore the last saved sort file position.
274  * ----------------------------------------------------------------
275  */
276 void
278 {
279  /*
280  * if we haven't sorted yet, just return.
281  */
282  if (!node->sort_Done)
283  return;
284 
285  /*
286  * restore the scan to the previously marked position
287  */
289 }
290 
291 void
293 {
295 
296  /*
297  * If we haven't sorted yet, just return. If outerplan's chgParam is not
298  * NULL then it will be re-scanned by ExecProcNode, else no reason to
299  * re-scan it at all.
300  */
301  if (!node->sort_Done)
302  return;
303 
304  /* must drop pointer to sort result tuple */
306 
307  /*
308  * If subnode is to be rescanned then we forget previous sort results; we
309  * have to re-read the subplan and re-sort. Also must re-sort if the
310  * bounded-sort parameters changed or we didn't select randomAccess.
311  *
312  * Otherwise we can just rewind and rescan the sorted output.
313  */
314  if (outerPlan->chgParam != NULL ||
315  node->bounded != node->bounded_Done ||
316  node->bound != node->bound_Done ||
317  !node->randomAccess)
318  {
319  node->sort_Done = false;
321  node->tuplesortstate = NULL;
322 
323  /*
324  * if chgParam of subnode is not null then plan will be re-scanned by
325  * first ExecProcNode.
326  */
327  if (outerPlan->chgParam == NULL)
328  ExecReScan(outerPlan);
329  }
330  else
332 }
SortState * ExecInitSort(Sort *node, EState *estate, int eflags)
Definition: nodeSort.c:153
TupleTableSlot * ExecProcNode(PlanState *node)
Definition: execProcnode.c:398
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1773
void ExecInitScanTupleSlot(EState *estate, ScanState *scanstate)
Definition: execTuples.c:842
void tuplesort_restorepos(Tuplesortstate *state)
Definition: tuplesort.c:3198
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:863
bool bounded_Done
Definition: execnodes.h:1725
#define ScanDirectionIsForward(direction)
Definition: sdir.h:55
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:654
bool bounded
Definition: execnodes.h:1722
int64 bound
Definition: execnodes.h:1723
void ExecReScan(PlanState *node)
Definition: execAmi.c:75
TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: execTuples.c:439
bool * nullsFirst
Definition: plannodes.h:749
TupleTableSlot * ss_ScanTupleSlot
Definition: execnodes.h:1082
EState * state
Definition: execnodes.h:834
#define SO1_printf(s, p)
Definition: execdebug.h:92
Oid * sortOperators
Definition: plannodes.h:747
ScanDirection es_direction
Definition: execnodes.h:428
void ExecAssignResultTypeFromTL(PlanState *planstate)
Definition: execUtils.c:440
void ExecReScanSort(SortState *node)
Definition: nodeSort.c:292
PlanState ps
Definition: execnodes.h:1079
void * tuplesortstate
Definition: execnodes.h:1727
TupleTableSlot * ps_ResultTupleSlot
Definition: execnodes.h:861
void ExecInitResultTupleSlot(EState *estate, PlanState *planstate)
Definition: execTuples.c:832
void tuplesort_rescan(Tuplesortstate *state)
Definition: tuplesort.c:3131
void ExecEndSort(SortState *node)
Definition: nodeSort.c:224
#define EXEC_FLAG_BACKWARD
Definition: executor.h:60
#define outerPlanState(node)
Definition: execnodes.h:874
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
Definition: tuplesort.c:2113
void tuplesort_set_bound(Tuplesortstate *state, int64 bound)
Definition: tuplesort.c:1123
void ExecSortMarkPos(SortState *node)
Definition: nodeSort.c:259
ScanDirection
Definition: sdir.h:22
#define TupIsNull(slot)
Definition: tuptable.h:138
int64 bound_Done
Definition: execnodes.h:1726
ScanState ss
Definition: execnodes.h:1720
#define EXEC_FLAG_REWIND
Definition: executor.h:59
Bitmapset * chgParam
Definition: execnodes.h:856
#define outerPlan(node)
Definition: plannodes.h:174
int numCols
Definition: plannodes.h:745
int work_mem
Definition: globals.c:113
Plan * plan
Definition: execnodes.h:832
#define makeNode(_type_)
Definition: nodes.h:557
#define NULL
Definition: c.h:229
#define EXEC_FLAG_MARK
Definition: executor.h:61
void ExecSortRestrPos(SortState *node)
Definition: nodeSort.c:277
bool randomAccess
Definition: execnodes.h:1721
bool sort_Done
Definition: execnodes.h:1724
TupleDesc ExecGetResultType(PlanState *planstate)
Definition: execUtils.c:469
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:756
void ExecAssignScanTypeFromOuterPlan(ScanState *scanstate)
Definition: execUtils.c:552
TupleTableSlot * ExecSort(SortState *node)
Definition: nodeSort.c:39
void tuplesort_markpos(Tuplesortstate *state)
Definition: tuplesort.c:3166
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1167
Oid * collations
Definition: plannodes.h:748
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:140
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
Definition: tuplesort.c:1364