Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nodeSort.c
4 : : * Routines to handle sorting of relations.
5 : : *
6 : : * Portions Copyright (c) 1996-2024, 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 : : * There are two distinct ways that this sort can be performed:
33 : : *
34 : : * 1) When the result is a single column we perform a Datum sort.
35 : : *
36 : : * 2) When the result contains multiple columns we perform a tuple sort.
37 : : *
38 : : * We could do this by always performing a tuple sort, however sorting
39 : : * Datums only can be significantly faster than sorting tuples,
40 : : * especially when the Datums are of a pass-by-value type.
41 : : *
42 : : * Conditions:
43 : : * -- none.
44 : : *
45 : : * Initial States:
46 : : * -- the outer child is prepared to return the first tuple.
47 : : * ----------------------------------------------------------------
48 : : */
49 : : static TupleTableSlot *
2463 andres@anarazel.de 50 :CBC 5327898 : ExecSort(PlanState *pstate)
51 : : {
52 : 5327898 : SortState *node = castNode(SortState, pstate);
53 : : EState *estate;
54 : : ScanDirection dir;
55 : : Tuplesortstate *tuplesortstate;
56 : : TupleTableSlot *slot;
57 : :
2455 58 [ + + ]: 5327898 : CHECK_FOR_INTERRUPTS();
59 : :
60 : : /*
61 : : * get state info from node
62 : : */
63 : : SO1_printf("ExecSort: %s\n",
64 : : "entering routine");
65 : :
7801 tgl@sss.pgh.pa.us 66 : 5327898 : estate = node->ss.ps.state;
9716 bruce@momjian.us 67 : 5327898 : dir = estate->es_direction;
7801 tgl@sss.pgh.pa.us 68 : 5327898 : tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
69 : :
70 : : /*
71 : : * If first time through, read all tuples from outer plan and pass them to
72 : : * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
73 : : */
74 : :
75 [ + + ]: 5327898 : if (!node->sort_Done)
76 : : {
77 : 47701 : Sort *plannode = (Sort *) node->ss.ps.plan;
78 : : PlanState *outerNode;
79 : : TupleDesc tupDesc;
741 drowley@postgresql.o 80 : 47701 : int tuplesortopts = TUPLESORT_NONE;
81 : :
82 : : SO1_printf("ExecSort: %s\n",
83 : : "sorting subplan");
84 : :
85 : : /*
86 : : * Want to scan subplan in the forward direction while creating the
87 : : * sorted data.
88 : : */
9716 bruce@momjian.us 89 : 47701 : estate->es_direction = ForwardScanDirection;
90 : :
91 : : /*
92 : : * Initialize tuplesort module.
93 : : */
94 : : SO1_printf("ExecSort: %s\n",
95 : : "calling tuplesort_begin");
96 : :
7801 tgl@sss.pgh.pa.us 97 : 47701 : outerNode = outerPlanState(node);
7650 98 : 47701 : tupDesc = ExecGetResultType(outerNode);
99 : :
741 drowley@postgresql.o 100 [ + + ]: 47701 : if (node->randomAccess)
101 : 2289 : tuplesortopts |= TUPLESORT_RANDOMACCESS;
102 [ + + ]: 47701 : if (node->bounded)
103 : 468 : tuplesortopts |= TUPLESORT_ALLOWBOUNDED;
104 : :
997 105 [ + + ]: 47701 : if (node->datumSort)
106 : 2249 : tuplesortstate = tuplesort_begin_datum(TupleDescAttr(tupDesc, 0)->atttypid,
107 : 2249 : plannode->sortOperators[0],
108 : 2249 : plannode->collations[0],
109 : 2249 : plannode->nullsFirst[0],
110 : : work_mem,
111 : : NULL,
112 : : tuplesortopts);
113 : : else
114 : 45452 : tuplesortstate = tuplesort_begin_heap(tupDesc,
115 : : plannode->numCols,
116 : : plannode->sortColIdx,
117 : : plannode->sortOperators,
118 : : plannode->collations,
119 : : plannode->nullsFirst,
120 : : work_mem,
121 : : NULL,
122 : : tuplesortopts);
6190 tgl@sss.pgh.pa.us 123 [ + + ]: 47695 : if (node->bounded)
124 : 468 : tuplesort_set_bound(tuplesortstate, node->bound);
7801 125 : 47695 : node->tuplesortstate = (void *) tuplesortstate;
126 : :
127 : : /*
128 : : * Scan the subplan and feed all the tuples to tuplesort using the
129 : : * appropriate method based on the type of sort we're doing.
130 : : */
997 drowley@postgresql.o 131 [ + + ]: 47695 : if (node->datumSort)
132 : : {
133 : : for (;;)
134 : : {
135 : 737835 : slot = ExecProcNode(outerNode);
136 : :
137 [ + + + + ]: 737833 : if (TupIsNull(slot))
138 : : break;
139 : 735586 : slot_getsomeattrs(slot, 1);
140 : 735586 : tuplesort_putdatum(tuplesortstate,
141 : 735586 : slot->tts_values[0],
142 : 735586 : slot->tts_isnull[0]);
143 : : }
144 : : }
145 : : else
146 : : {
147 : : for (;;)
148 : : {
149 : 5430729 : slot = ExecProcNode(outerNode);
150 : :
151 [ + + + + ]: 5430729 : if (TupIsNull(slot))
152 : : break;
153 : 5385283 : tuplesort_puttupleslot(tuplesortstate, slot);
154 : : }
155 : : }
156 : :
157 : : /*
158 : : * Complete the sort.
159 : : */
8946 tgl@sss.pgh.pa.us 160 : 47693 : tuplesort_performsort(tuplesortstate);
161 : :
162 : : /*
163 : : * restore to user specified direction
164 : : */
9716 bruce@momjian.us 165 : 47693 : estate->es_direction = dir;
166 : :
167 : : /*
168 : : * finally set the sorted flag to true
169 : : */
7801 tgl@sss.pgh.pa.us 170 : 47693 : node->sort_Done = true;
6190 171 : 47693 : node->bounded_Done = node->bounded;
172 : 47693 : node->bound_Done = node->bound;
2420 rhaas@postgresql.org 173 [ + + + + ]: 47693 : if (node->shared_info && node->am_worker)
174 : : {
175 : : TuplesortInstrumentation *si;
176 : :
177 [ - + ]: 48 : Assert(IsParallelWorker());
178 [ - + ]: 48 : Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
179 : 48 : si = &node->shared_info->sinstrument[ParallelWorkerNumber];
180 : 48 : tuplesort_get_stats(tuplesortstate, si);
181 : : }
182 : : SO1_printf("ExecSort: %s\n", "sorting done");
183 : : }
184 : :
185 : : SO1_printf("ExecSort: %s\n",
186 : : "retrieving tuple from tuplesort");
187 : :
997 drowley@postgresql.o 188 : 5327890 : slot = node->ss.ps.ps_ResultTupleSlot;
189 : :
190 : : /*
191 : : * Fetch the next sorted item from the appropriate tuplesort function. For
192 : : * datum sorts we must manage the slot ourselves and leave it clear when
193 : : * tuplesort_getdatum returns false to indicate there are no more datums.
194 : : * For tuple sorts, tuplesort_gettupleslot manages the slot for us and
195 : : * empties the slot when it runs out of tuples.
196 : : */
197 [ + + ]: 5327890 : if (node->datumSort)
198 : : {
199 : 600128 : ExecClearTuple(slot);
200 [ + + ]: 600128 : if (tuplesort_getdatum(tuplesortstate, ScanDirectionIsForward(dir),
201 : : false, &(slot->tts_values[0]),
202 : : &(slot->tts_isnull[0]), NULL))
203 : 598008 : ExecStoreVirtualTuple(slot);
204 : : }
205 : : else
206 : 4727762 : (void) tuplesort_gettupleslot(tuplesortstate,
207 : : ScanDirectionIsForward(dir),
208 : : false, slot, NULL);
209 : :
6501 tgl@sss.pgh.pa.us 210 : 5327890 : return slot;
211 : : }
212 : :
213 : : /* ----------------------------------------------------------------
214 : : * ExecInitSort
215 : : *
216 : : * Creates the run-time state information for the sort node
217 : : * produced by the planner and initializes its outer subtree.
218 : : * ----------------------------------------------------------------
219 : : */
220 : : SortState *
6620 221 : 30899 : ExecInitSort(Sort *node, EState *estate, int eflags)
222 : : {
223 : : SortState *sortstate;
224 : : TupleDesc outerTupDesc;
225 : :
226 : : SO1_printf("ExecInitSort: %s\n",
227 : : "initializing sort node");
228 : :
229 : : /*
230 : : * create state structure
231 : : */
9716 bruce@momjian.us 232 : 30899 : sortstate = makeNode(SortState);
7801 tgl@sss.pgh.pa.us 233 : 30899 : sortstate->ss.ps.plan = (Plan *) node;
234 : 30899 : sortstate->ss.ps.state = estate;
2463 andres@anarazel.de 235 : 30899 : sortstate->ss.ps.ExecProcNode = ExecSort;
236 : :
237 : : /*
238 : : * We must have random access to the sort output to do backward scan or
239 : : * mark/restore. We also prefer to materialize the sort output if we
240 : : * might be called on to rewind and replay it many times.
241 : : */
6620 tgl@sss.pgh.pa.us 242 : 30899 : sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
243 : : EXEC_FLAG_BACKWARD |
244 : 30899 : EXEC_FLAG_MARK)) != 0;
245 : :
6190 246 : 30899 : sortstate->bounded = false;
8946 247 : 30899 : sortstate->sort_Done = false;
248 : 30899 : sortstate->tuplesortstate = NULL;
249 : :
250 : : /*
251 : : * Miscellaneous initialization
252 : : *
253 : : * Sort nodes don't initialize their ExprContexts because they never call
254 : : * ExecQual or ExecProject.
255 : : */
256 : :
257 : : /*
258 : : * initialize child nodes
259 : : *
260 : : * We shield the child node from the need to support REWIND, BACKWARD, or
261 : : * MARK/RESTORE.
262 : : */
6620 263 : 30899 : eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
264 : :
265 : 30899 : outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
266 : :
267 : : /*
268 : : * Initialize scan slot and type.
269 : : */
1977 andres@anarazel.de 270 : 30896 : ExecCreateScanSlotFromOuterPlan(estate, &sortstate->ss, &TTSOpsVirtual);
271 : :
272 : : /*
273 : : * Initialize return slot and type. No need to initialize projection info
274 : : * because this node doesn't do projections.
275 : : */
276 : 30896 : ExecInitResultTupleSlotTL(&sortstate->ss.ps, &TTSOpsMinimalTuple);
7801 tgl@sss.pgh.pa.us 277 : 30896 : sortstate->ss.ps.ps_ProjInfo = NULL;
278 : :
563 drowley@postgresql.o 279 : 30896 : outerTupDesc = ExecGetResultType(outerPlanState(sortstate));
280 : :
281 : : /*
282 : : * We perform a Datum sort when we're sorting just a single column,
283 : : * otherwise we perform a tuple sort.
284 : : */
534 285 [ + + ]: 30896 : if (outerTupDesc->natts == 1)
997 286 : 3715 : sortstate->datumSort = true;
287 : : else
288 : 27181 : sortstate->datumSort = false;
289 : :
290 : : SO1_printf("ExecInitSort: %s\n",
291 : : "sort node initialized");
292 : :
7801 tgl@sss.pgh.pa.us 293 : 30896 : return sortstate;
294 : : }
295 : :
296 : : /* ----------------------------------------------------------------
297 : : * ExecEndSort(node)
298 : : * ----------------------------------------------------------------
299 : : */
300 : : void
301 : 30824 : ExecEndSort(SortState *node)
302 : : {
303 : : SO1_printf("ExecEndSort: %s\n",
304 : : "shutting down sort node");
305 : :
306 : : /*
307 : : * Release tuplesort resources
308 : : */
309 [ + + ]: 30824 : if (node->tuplesortstate != NULL)
310 : 27215 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
311 : 30824 : node->tuplesortstate = NULL;
312 : :
313 : : /*
314 : : * shut down the subplan
315 : : */
7791 316 : 30824 : ExecEndNode(outerPlanState(node));
317 : :
318 : : SO1_printf("ExecEndSort: %s\n",
319 : : "sort node shutdown");
9716 bruce@momjian.us 320 : 30824 : }
321 : :
322 : : /* ----------------------------------------------------------------
323 : : * ExecSortMarkPos
324 : : *
325 : : * Calls tuplesort to save the current position in the sorted file.
326 : : * ----------------------------------------------------------------
327 : : */
328 : : void
7801 tgl@sss.pgh.pa.us 329 : 289805 : ExecSortMarkPos(SortState *node)
330 : : {
331 : : /*
332 : : * if we haven't sorted yet, just return
333 : : */
334 [ - + ]: 289805 : if (!node->sort_Done)
9716 bruce@momjian.us 335 :UBC 0 : return;
336 : :
7801 tgl@sss.pgh.pa.us 337 :CBC 289805 : tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
338 : : }
339 : :
340 : : /* ----------------------------------------------------------------
341 : : * ExecSortRestrPos
342 : : *
343 : : * Calls tuplesort to restore the last saved sort file position.
344 : : * ----------------------------------------------------------------
345 : : */
346 : : void
347 : 15975 : ExecSortRestrPos(SortState *node)
348 : : {
349 : : /*
350 : : * if we haven't sorted yet, just return.
351 : : */
352 [ - + ]: 15975 : if (!node->sort_Done)
9716 bruce@momjian.us 353 :UBC 0 : return;
354 : :
355 : : /*
356 : : * restore the scan to the previously marked position
357 : : */
7801 tgl@sss.pgh.pa.us 358 :CBC 15975 : tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
359 : : }
360 : :
361 : : void
5025 362 : 20882 : ExecReScanSort(SortState *node)
363 : : {
3249 bruce@momjian.us 364 : 20882 : PlanState *outerPlan = outerPlanState(node);
365 : :
366 : : /*
367 : : * If we haven't sorted yet, just return. If outerplan's chgParam is not
368 : : * NULL then it will be re-scanned by ExecProcNode, else no reason to
369 : : * re-scan it at all.
370 : : */
7801 tgl@sss.pgh.pa.us 371 [ + + ]: 20882 : if (!node->sort_Done)
9547 vadim4o@yahoo.com 372 : 451 : return;
373 : :
374 : : /* must drop pointer to sort result tuple */
7801 tgl@sss.pgh.pa.us 375 : 20431 : ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
376 : :
377 : : /*
378 : : * If subnode is to be rescanned then we forget previous sort results; we
379 : : * have to re-read the subplan and re-sort. Also must re-sort if the
380 : : * bounded-sort parameters changed or we didn't select randomAccess.
381 : : *
382 : : * Otherwise we can just rewind and rescan the sorted output.
383 : : */
3268 rhaas@postgresql.org 384 [ + + ]: 20431 : if (outerPlan->chgParam != NULL ||
6190 tgl@sss.pgh.pa.us 385 [ + - ]: 248 : node->bounded != node->bounded_Done ||
386 [ + + ]: 248 : node->bound != node->bound_Done ||
6620 387 [ + + ]: 221 : !node->randomAccess)
388 : : {
7801 389 : 20414 : node->sort_Done = false;
390 : 20414 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
391 : 20414 : node->tuplesortstate = NULL;
392 : :
393 : : /*
394 : : * if chgParam of subnode is not null then plan will be re-scanned by
395 : : * first ExecProcNode.
396 : : */
3268 rhaas@postgresql.org 397 [ + + ]: 20414 : if (outerPlan->chgParam == NULL)
398 : 231 : ExecReScan(outerPlan);
399 : : }
400 : : else
7801 tgl@sss.pgh.pa.us 401 : 17 : tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
402 : : }
403 : :
404 : : /* ----------------------------------------------------------------
405 : : * Parallel Query Support
406 : : * ----------------------------------------------------------------
407 : : */
408 : :
409 : : /* ----------------------------------------------------------------
410 : : * ExecSortEstimate
411 : : *
412 : : * Estimate space required to propagate sort statistics.
413 : : * ----------------------------------------------------------------
414 : : */
415 : : void
2420 rhaas@postgresql.org 416 : 76 : ExecSortEstimate(SortState *node, ParallelContext *pcxt)
417 : : {
418 : : Size size;
419 : :
420 : : /* don't need this if not instrumenting or no workers */
421 [ + + - + ]: 76 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
422 : 70 : return;
423 : :
424 : 6 : size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
425 : 6 : size = add_size(size, offsetof(SharedSortInfo, sinstrument));
426 : 6 : shm_toc_estimate_chunk(&pcxt->estimator, size);
427 : 6 : shm_toc_estimate_keys(&pcxt->estimator, 1);
428 : : }
429 : :
430 : : /* ----------------------------------------------------------------
431 : : * ExecSortInitializeDSM
432 : : *
433 : : * Initialize DSM space for sort statistics.
434 : : * ----------------------------------------------------------------
435 : : */
436 : : void
437 : 76 : ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
438 : : {
439 : : Size size;
440 : :
441 : : /* don't need this if not instrumenting or no workers */
442 [ + + - + ]: 76 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
443 : 70 : return;
444 : :
445 : 6 : size = offsetof(SharedSortInfo, sinstrument)
446 : 6 : + pcxt->nworkers * sizeof(TuplesortInstrumentation);
447 : 6 : node->shared_info = shm_toc_allocate(pcxt->toc, size);
448 : : /* ensure any unfilled slots will contain zeroes */
449 : 6 : memset(node->shared_info, 0, size);
450 : 6 : node->shared_info->num_workers = pcxt->nworkers;
451 : 6 : shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
452 : 6 : node->shared_info);
453 : : }
454 : :
455 : : /* ----------------------------------------------------------------
456 : : * ExecSortInitializeWorker
457 : : *
458 : : * Attach worker to DSM space for sort statistics.
459 : : * ----------------------------------------------------------------
460 : : */
461 : : void
2341 andres@anarazel.de 462 : 226 : ExecSortInitializeWorker(SortState *node, ParallelWorkerContext *pwcxt)
463 : : {
2420 rhaas@postgresql.org 464 : 226 : node->shared_info =
2341 andres@anarazel.de 465 : 226 : shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
2420 rhaas@postgresql.org 466 : 226 : node->am_worker = true;
467 : 226 : }
468 : :
469 : : /* ----------------------------------------------------------------
470 : : * ExecSortRetrieveInstrumentation
471 : : *
472 : : * Transfer sort statistics from DSM to private memory.
473 : : * ----------------------------------------------------------------
474 : : */
475 : : void
476 : 6 : ExecSortRetrieveInstrumentation(SortState *node)
477 : : {
478 : : Size size;
479 : : SharedSortInfo *si;
480 : :
481 [ - + ]: 6 : if (node->shared_info == NULL)
2420 rhaas@postgresql.org 482 :UBC 0 : return;
483 : :
2420 rhaas@postgresql.org 484 :CBC 6 : size = offsetof(SharedSortInfo, sinstrument)
485 : 6 : + node->shared_info->num_workers * sizeof(TuplesortInstrumentation);
486 : 6 : si = palloc(size);
487 : 6 : memcpy(si, node->shared_info, size);
488 : 6 : node->shared_info = si;
489 : : }
|
