Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nodeSort.c
4 : : * Routines to handle sorting of relations.
5 : : *
6 : : * Portions Copyright (c) 1996-2026, 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 *
50 : 926835 : ExecSort(PlanState *pstate)
51 : : {
52 : 926835 : SortState *node = castNode(SortState, pstate);
53 : 926835 : EState *estate;
54 : 926835 : ScanDirection dir;
55 : 926835 : Tuplesortstate *tuplesortstate;
56 : 926835 : TupleTableSlot *slot;
57 : :
58 [ + + ]: 926835 : CHECK_FOR_INTERRUPTS();
59 : :
60 : : /*
61 : : * get state info from node
62 : : */
63 : : SO1_printf("ExecSort: %s\n",
64 : : "entering routine");
65 : :
66 : 926835 : estate = node->ss.ps.state;
67 : 926835 : dir = estate->es_direction;
68 : 926835 : 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 [ + + ]: 926835 : if (!node->sort_Done)
76 : : {
77 : 8611 : Sort *plannode = (Sort *) node->ss.ps.plan;
78 : 8611 : PlanState *outerNode;
79 : 8611 : TupleDesc tupDesc;
80 : 8611 : 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 : : */
89 : 8611 : estate->es_direction = ForwardScanDirection;
90 : :
91 : : /*
92 : : * Initialize tuplesort module.
93 : : */
94 : : SO1_printf("ExecSort: %s\n",
95 : : "calling tuplesort_begin");
96 : :
97 : 8611 : outerNode = outerPlanState(node);
98 : 8611 : tupDesc = ExecGetResultType(outerNode);
99 : :
100 [ + + ]: 8611 : if (node->randomAccess)
101 : 382 : tuplesortopts |= TUPLESORT_RANDOMACCESS;
102 [ + + ]: 8611 : if (node->bounded)
103 : 120 : tuplesortopts |= TUPLESORT_ALLOWBOUNDED;
104 : :
105 [ + + ]: 8611 : if (node->datumSort)
106 : 1122 : tuplesortstate = tuplesort_begin_datum(TupleDescAttr(tupDesc, 0)->atttypid,
107 : 561 : plannode->sortOperators[0],
108 : 561 : plannode->collations[0],
109 : 561 : plannode->nullsFirst[0],
110 : 561 : work_mem,
111 : : NULL,
112 : 561 : tuplesortopts);
113 : : else
114 : 16100 : tuplesortstate = tuplesort_begin_heap(tupDesc,
115 : 8050 : plannode->numCols,
116 : 8050 : plannode->sortColIdx,
117 : 8050 : plannode->sortOperators,
118 : 8050 : plannode->collations,
119 : 8050 : plannode->nullsFirst,
120 : 8050 : work_mem,
121 : : NULL,
122 : 8050 : tuplesortopts);
123 [ + + ]: 8611 : if (node->bounded)
124 : 120 : tuplesort_set_bound(tuplesortstate, node->bound);
125 : 8611 : node->tuplesortstate = 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 : : */
131 [ + + ]: 8611 : if (node->datumSort)
132 : : {
133 : 236778 : for (;;)
134 : : {
135 : 236778 : slot = ExecProcNode(outerNode);
136 : :
137 [ + + + + ]: 236778 : if (TupIsNull(slot))
138 : 563 : break;
139 : 236215 : slot_getsomeattrs(slot, 1);
140 : 472430 : tuplesort_putdatum(tuplesortstate,
141 : 236215 : slot->tts_values[0],
142 : 236215 : slot->tts_isnull[0]);
143 : : }
144 : 563 : }
145 : : else
146 : : {
147 : 892772 : for (;;)
148 : : {
149 : 892772 : slot = ExecProcNode(outerNode);
150 : :
151 [ + + + + ]: 892772 : if (TupIsNull(slot))
152 : 8048 : break;
153 : 884724 : tuplesort_puttupleslot(tuplesortstate, slot);
154 : : }
155 : : }
156 : :
157 : : /*
158 : : * Complete the sort.
159 : : */
160 : 8611 : tuplesort_performsort(tuplesortstate);
161 : :
162 : : /*
163 : : * restore to user specified direction
164 : : */
165 : 8611 : estate->es_direction = dir;
166 : :
167 : : /*
168 : : * finally set the sorted flag to true
169 : : */
170 : 8611 : node->sort_Done = true;
171 : 8611 : node->bounded_Done = node->bounded;
172 : 8611 : node->bound_Done = node->bound;
173 [ + + + + ]: 8611 : if (node->shared_info && node->am_worker)
174 : : {
175 : 16 : TuplesortInstrumentation *si;
176 : :
177 [ + - ]: 16 : Assert(IsParallelWorker());
178 [ + - ]: 16 : Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
179 : 16 : si = &node->shared_info->sinstrument[ParallelWorkerNumber];
180 : 16 : tuplesort_get_stats(tuplesortstate, si);
181 : 16 : }
182 : : SO1_printf("ExecSort: %s\n", "sorting done");
183 : 8611 : }
184 : :
185 : : SO1_printf("ExecSort: %s\n",
186 : : "retrieving tuple from tuplesort");
187 : :
188 : 926835 : 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 [ + + ]: 926835 : if (node->datumSort)
198 : : {
199 : 187044 : ExecClearTuple(slot);
200 [ + + + + ]: 374088 : if (tuplesort_getdatum(tuplesortstate, ScanDirectionIsForward(dir),
201 : 187044 : false, &(slot->tts_values[0]),
202 : 187044 : &(slot->tts_isnull[0]), NULL))
203 : 186507 : ExecStoreVirtualTuple(slot);
204 : 187044 : }
205 : : else
206 : 1479582 : (void) tuplesort_gettupleslot(tuplesortstate,
207 : 739791 : ScanDirectionIsForward(dir),
208 : 739791 : false, slot, NULL);
209 : :
210 : 1853670 : return slot;
211 : 926835 : }
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 *
221 : 9455 : ExecInitSort(Sort *node, EState *estate, int eflags)
222 : : {
223 : 9455 : SortState *sortstate;
224 : 9455 : TupleDesc outerTupDesc;
225 : :
226 : : SO1_printf("ExecInitSort: %s\n",
227 : : "initializing sort node");
228 : :
229 : : /*
230 : : * create state structure
231 : : */
232 : 9455 : sortstate = makeNode(SortState);
233 : 9455 : sortstate->ss.ps.plan = (Plan *) node;
234 : 9455 : sortstate->ss.ps.state = estate;
235 : 9455 : 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 : : */
242 : 18910 : sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
243 : : EXEC_FLAG_BACKWARD |
244 : 9455 : EXEC_FLAG_MARK)) != 0;
245 : :
246 : 9455 : sortstate->bounded = false;
247 : 9455 : sortstate->sort_Done = false;
248 : 9455 : 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 : : */
263 : 9455 : eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
264 : :
265 : 9455 : outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
266 : :
267 : : /*
268 : : * Initialize scan slot and type.
269 : : */
270 : 9455 : 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 : 9455 : ExecInitResultTupleSlotTL(&sortstate->ss.ps, &TTSOpsMinimalTuple);
277 : 9455 : sortstate->ss.ps.ps_ProjInfo = NULL;
278 : :
279 : 9455 : 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 : : */
285 [ + + ]: 9455 : if (outerTupDesc->natts == 1)
286 : 1179 : sortstate->datumSort = true;
287 : : else
288 : 8276 : sortstate->datumSort = false;
289 : :
290 : : SO1_printf("ExecInitSort: %s\n",
291 : : "sort node initialized");
292 : :
293 : 18910 : return sortstate;
294 : 9455 : }
295 : :
296 : : /* ----------------------------------------------------------------
297 : : * ExecEndSort(node)
298 : : * ----------------------------------------------------------------
299 : : */
300 : : void
301 : 9429 : ExecEndSort(SortState *node)
302 : : {
303 : : SO1_printf("ExecEndSort: %s\n",
304 : : "shutting down sort node");
305 : :
306 : : /*
307 : : * Release tuplesort resources
308 : : */
309 [ + + ]: 9429 : if (node->tuplesortstate != NULL)
310 : 8222 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
311 : 9429 : node->tuplesortstate = NULL;
312 : :
313 : : /*
314 : : * shut down the subplan
315 : : */
316 : 9429 : ExecEndNode(outerPlanState(node));
317 : :
318 : : SO1_printf("ExecEndSort: %s\n",
319 : : "sort node shutdown");
320 : 9429 : }
321 : :
322 : : /* ----------------------------------------------------------------
323 : : * ExecSortMarkPos
324 : : *
325 : : * Calls tuplesort to save the current position in the sorted file.
326 : : * ----------------------------------------------------------------
327 : : */
328 : : void
329 : 93465 : ExecSortMarkPos(SortState *node)
330 : : {
331 : : /*
332 : : * if we haven't sorted yet, just return
333 : : */
334 [ - + ]: 93465 : if (!node->sort_Done)
335 : 0 : return;
336 : :
337 : 93465 : tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
338 : 93465 : }
339 : :
340 : : /* ----------------------------------------------------------------
341 : : * ExecSortRestrPos
342 : : *
343 : : * Calls tuplesort to restore the last saved sort file position.
344 : : * ----------------------------------------------------------------
345 : : */
346 : : void
347 : 4886 : ExecSortRestrPos(SortState *node)
348 : : {
349 : : /*
350 : : * if we haven't sorted yet, just return.
351 : : */
352 [ - + ]: 4886 : if (!node->sort_Done)
353 : 0 : return;
354 : :
355 : : /*
356 : : * restore the scan to the previously marked position
357 : : */
358 : 4886 : tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
359 : 4886 : }
360 : :
361 : : void
362 : 423 : ExecReScanSort(SortState *node)
363 : : {
364 : 423 : 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 : : */
371 [ + + ]: 423 : if (!node->sort_Done)
372 : 55 : return;
373 : :
374 : : /* must drop pointer to sort result tuple */
375 : 368 : 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 : : */
384 [ + + ]: 368 : if (outerPlan->chgParam != NULL ||
385 [ + - ]: 62 : node->bounded != node->bounded_Done ||
386 [ + + + + ]: 62 : node->bound != node->bound_Done ||
387 : 53 : !node->randomAccess)
388 : : {
389 : 367 : node->sort_Done = false;
390 : 367 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
391 : 367 : node->tuplesortstate = NULL;
392 : :
393 : : /*
394 : : * if chgParam of subnode is not null then plan will be re-scanned by
395 : : * first ExecProcNode.
396 : : */
397 [ + + ]: 367 : if (outerPlan->chgParam == NULL)
398 : 61 : ExecReScan(outerPlan);
399 : 367 : }
400 : : else
401 : 1 : tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
402 [ - + ]: 423 : }
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
416 : 26 : ExecSortEstimate(SortState *node, ParallelContext *pcxt)
417 : : {
418 : 26 : Size size;
419 : :
420 : : /* don't need this if not instrumenting or no workers */
421 [ + + - + ]: 26 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
422 : 24 : return;
423 : :
424 : 2 : size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
425 : 2 : size = add_size(size, offsetof(SharedSortInfo, sinstrument));
426 : 2 : shm_toc_estimate_chunk(&pcxt->estimator, size);
427 : 2 : shm_toc_estimate_keys(&pcxt->estimator, 1);
428 [ - + ]: 26 : }
429 : :
430 : : /* ----------------------------------------------------------------
431 : : * ExecSortInitializeDSM
432 : : *
433 : : * Initialize DSM space for sort statistics.
434 : : * ----------------------------------------------------------------
435 : : */
436 : : void
437 : 26 : ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
438 : : {
439 : 26 : Size size;
440 : :
441 : : /* don't need this if not instrumenting or no workers */
442 [ + + - + ]: 26 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
443 : 24 : return;
444 : :
445 : 2 : size = offsetof(SharedSortInfo, sinstrument)
446 : 2 : + pcxt->nworkers * sizeof(TuplesortInstrumentation);
447 : 2 : node->shared_info = shm_toc_allocate(pcxt->toc, size);
448 : : /* ensure any unfilled slots will contain zeroes */
449 : 2 : memset(node->shared_info, 0, size);
450 : 2 : node->shared_info->num_workers = pcxt->nworkers;
451 : 4 : shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
452 : 2 : node->shared_info);
453 [ - + ]: 26 : }
454 : :
455 : : /* ----------------------------------------------------------------
456 : : * ExecSortInitializeWorker
457 : : *
458 : : * Attach worker to DSM space for sort statistics.
459 : : * ----------------------------------------------------------------
460 : : */
461 : : void
462 : 77 : ExecSortInitializeWorker(SortState *node, ParallelWorkerContext *pwcxt)
463 : : {
464 : 77 : node->shared_info =
465 : 77 : shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
466 : 77 : node->am_worker = true;
467 : 77 : }
468 : :
469 : : /* ----------------------------------------------------------------
470 : : * ExecSortRetrieveInstrumentation
471 : : *
472 : : * Transfer sort statistics from DSM to private memory.
473 : : * ----------------------------------------------------------------
474 : : */
475 : : void
476 : 2 : ExecSortRetrieveInstrumentation(SortState *node)
477 : : {
478 : 2 : Size size;
479 : 2 : SharedSortInfo *si;
480 : :
481 [ + - ]: 2 : if (node->shared_info == NULL)
482 : 0 : return;
483 : :
484 : 2 : size = offsetof(SharedSortInfo, sinstrument)
485 : 2 : + node->shared_info->num_workers * sizeof(TuplesortInstrumentation);
486 : 2 : si = palloc(size);
487 : 2 : memcpy(si, node->shared_info, size);
488 : 2 : node->shared_info = si;
489 [ - + ]: 2 : }
|
