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/executor.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 : 7535267 : ExecSort(PlanState *pstate)
51 : : {
52 : 7535267 : SortState *node = castNode(SortState, pstate);
53 : : EState *estate;
54 : : ScanDirection dir;
55 : : Tuplesortstate *tuplesortstate;
56 : : TupleTableSlot *slot;
57 : :
58 [ + + ]: 7535267 : CHECK_FOR_INTERRUPTS();
59 : :
60 : : /*
61 : : * get state info from node
62 : : */
63 : 7535267 : estate = node->ss.ps.state;
64 : 7535267 : dir = estate->es_direction;
65 : 7535267 : tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
66 : :
67 : : /*
68 : : * If first time through, read all tuples from outer plan and pass them to
69 : : * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
70 : : */
71 : :
72 [ + + ]: 7535267 : if (!node->sort_Done)
73 : : {
74 : 75143 : Sort *plannode = (Sort *) node->ss.ps.plan;
75 : : PlanState *outerNode;
76 : : TupleDesc tupDesc;
77 : 75143 : int tuplesortopts = TUPLESORT_NONE;
78 : :
79 : : /*
80 : : * Want to scan subplan in the forward direction while creating the
81 : : * sorted data.
82 : : */
83 : 75143 : estate->es_direction = ForwardScanDirection;
84 : :
85 : : /*
86 : : * Initialize tuplesort module.
87 : : */
88 : 75143 : outerNode = outerPlanState(node);
89 : 75143 : tupDesc = ExecGetResultType(outerNode);
90 : :
91 [ + + ]: 75143 : if (node->randomAccess)
92 : 3677 : tuplesortopts |= TUPLESORT_RANDOMACCESS;
93 [ + + ]: 75143 : if (node->bounded)
94 : 633 : tuplesortopts |= TUPLESORT_ALLOWBOUNDED;
95 : :
96 [ + + ]: 75143 : if (node->datumSort)
97 : 5846 : tuplesortstate = tuplesort_begin_datum(TupleDescAttr(tupDesc, 0)->atttypid,
98 : 5846 : plannode->sortOperators[0],
99 : 5846 : plannode->collations[0],
100 : 5846 : plannode->nullsFirst[0],
101 : : work_mem,
102 : : NULL,
103 : : tuplesortopts);
104 : : else
105 : 69297 : tuplesortstate = tuplesort_begin_heap(tupDesc,
106 : : plannode->numCols,
107 : : plannode->sortColIdx,
108 : : plannode->sortOperators,
109 : : plannode->collations,
110 : : plannode->nullsFirst,
111 : : work_mem,
112 : : NULL,
113 : : tuplesortopts);
114 [ + + ]: 75135 : if (node->bounded)
115 : 633 : tuplesort_set_bound(tuplesortstate, node->bound);
116 : 75135 : node->tuplesortstate = tuplesortstate;
117 : :
118 : : /*
119 : : * Scan the subplan and feed all the tuples to tuplesort using the
120 : : * appropriate method based on the type of sort we're doing.
121 : : */
122 [ + + ]: 75135 : if (node->datumSort)
123 : : {
124 : : for (;;)
125 : : {
126 : 1031972 : slot = ExecProcNode(outerNode);
127 : :
128 [ + + + + ]: 1031962 : if (TupIsNull(slot))
129 : : break;
130 : 1026126 : slot_getsomeattrs(slot, 1);
131 : 1026126 : tuplesort_putdatum(tuplesortstate,
132 : 1026126 : slot->tts_values[0],
133 : 1026126 : slot->tts_isnull[0]);
134 : : }
135 : : }
136 : : else
137 : : {
138 : : for (;;)
139 : : {
140 : 7240232 : slot = ExecProcNode(outerNode);
141 : :
142 [ + + + + ]: 7240231 : if (TupIsNull(slot))
143 : : break;
144 : 7170943 : tuplesort_puttupleslot(tuplesortstate, slot);
145 : : }
146 : : }
147 : :
148 : : /*
149 : : * Complete the sort.
150 : : */
151 : 75124 : tuplesort_performsort(tuplesortstate);
152 : :
153 : : /*
154 : : * restore to user specified direction
155 : : */
156 : 75124 : estate->es_direction = dir;
157 : :
158 : : /*
159 : : * finally set the sorted flag to true
160 : : */
161 : 75124 : node->sort_Done = true;
162 : 75124 : node->bounded_Done = node->bounded;
163 : 75124 : node->bound_Done = node->bound;
164 [ + + + + ]: 75124 : if (node->shared_info && node->am_worker)
165 : : {
166 : : TuplesortInstrumentation *si;
167 : :
168 : : Assert(IsParallelWorker());
169 : : Assert(ParallelWorkerNumber < node->shared_info->num_workers);
170 : 64 : si = &node->shared_info->sinstrument[ParallelWorkerNumber];
171 : 64 : tuplesort_get_stats(tuplesortstate, si);
172 : : }
173 : : }
174 : :
175 : 7535248 : slot = node->ss.ps.ps_ResultTupleSlot;
176 : :
177 : : /*
178 : : * Fetch the next sorted item from the appropriate tuplesort function. For
179 : : * datum sorts we must manage the slot ourselves and leave it clear when
180 : : * tuplesort_getdatum returns false to indicate there are no more datums.
181 : : * For tuple sorts, tuplesort_gettupleslot manages the slot for us and
182 : : * empties the slot when it runs out of tuples.
183 : : */
184 [ + + ]: 7535248 : if (node->datumSort)
185 : : {
186 : 833782 : ExecClearTuple(slot);
187 [ + + ]: 833782 : if (tuplesort_getdatum(tuplesortstate, ScanDirectionIsForward(dir),
188 : : false, &(slot->tts_values[0]),
189 : : &(slot->tts_isnull[0]), NULL))
190 : 828170 : ExecStoreVirtualTuple(slot);
191 : : }
192 : : else
193 : 6701466 : (void) tuplesort_gettupleslot(tuplesortstate,
194 : : ScanDirectionIsForward(dir),
195 : : false, slot, NULL);
196 : :
197 : 7535248 : return slot;
198 : : }
199 : :
200 : : /* ----------------------------------------------------------------
201 : : * ExecInitSort
202 : : *
203 : : * Creates the run-time state information for the sort node
204 : : * produced by the planner and initializes its outer subtree.
205 : : * ----------------------------------------------------------------
206 : : */
207 : : SortState *
208 : 53683 : ExecInitSort(Sort *node, EState *estate, int eflags)
209 : : {
210 : : SortState *sortstate;
211 : : TupleDesc outerTupDesc;
212 : :
213 : : /*
214 : : * create state structure
215 : : */
216 : 53683 : sortstate = makeNode(SortState);
217 : 53683 : sortstate->ss.ps.plan = (Plan *) node;
218 : 53683 : sortstate->ss.ps.state = estate;
219 : 53683 : sortstate->ss.ps.ExecProcNode = ExecSort;
220 : :
221 : : /*
222 : : * We must have random access to the sort output to do backward scan or
223 : : * mark/restore. We also prefer to materialize the sort output if we
224 : : * might be called on to rewind and replay it many times.
225 : : */
226 : 53683 : sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
227 : : EXEC_FLAG_BACKWARD |
228 : 53683 : EXEC_FLAG_MARK)) != 0;
229 : :
230 : 53683 : sortstate->bounded = false;
231 : 53683 : sortstate->sort_Done = false;
232 : 53683 : sortstate->tuplesortstate = NULL;
233 : :
234 : : /*
235 : : * Miscellaneous initialization
236 : : *
237 : : * Sort nodes don't initialize their ExprContexts because they never call
238 : : * ExecQual or ExecProject.
239 : : */
240 : :
241 : : /*
242 : : * initialize child nodes
243 : : *
244 : : * We shield the child node from the need to support REWIND, BACKWARD, or
245 : : * MARK/RESTORE.
246 : : */
247 : 53683 : eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
248 : :
249 : 53683 : outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
250 : :
251 : : /*
252 : : * Initialize scan slot and type.
253 : : */
254 : 53679 : ExecCreateScanSlotFromOuterPlan(estate, &sortstate->ss, &TTSOpsVirtual);
255 : :
256 : : /*
257 : : * Initialize return slot and type. No need to initialize projection info
258 : : * because this node doesn't do projections.
259 : : */
260 : 53679 : ExecInitResultTupleSlotTL(&sortstate->ss.ps, &TTSOpsMinimalTuple);
261 : 53679 : sortstate->ss.ps.ps_ProjInfo = NULL;
262 : :
263 : 53679 : outerTupDesc = ExecGetResultType(outerPlanState(sortstate));
264 : :
265 : : /*
266 : : * We perform a Datum sort when we're sorting just a single column by a
267 : : * single key, otherwise we perform a tuple sort. You might think that
268 : : * only 1 sort key would be relevant if there's only 1 output column since
269 : : * all keys must be on that column, but the sort keys may differ in
270 : : * collation, and if the first key's collation is nondeterministic then
271 : : * ignoring subsequent keys could lead to an incorrect sort order.
272 : : */
273 [ + + + - ]: 53679 : if (outerTupDesc->natts == 1 && node->numCols == 1)
274 : 8321 : sortstate->datumSort = true;
275 : : else
276 : 45358 : sortstate->datumSort = false;
277 : :
278 : 53679 : return sortstate;
279 : : }
280 : :
281 : : /* ----------------------------------------------------------------
282 : : * ExecEndSort(node)
283 : : * ----------------------------------------------------------------
284 : : */
285 : : void
286 : 53564 : ExecEndSort(SortState *node)
287 : : {
288 : : /*
289 : : * Release tuplesort resources
290 : : */
291 [ + + ]: 53564 : if (node->tuplesortstate != NULL)
292 : 47235 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
293 : 53564 : node->tuplesortstate = NULL;
294 : :
295 : : /*
296 : : * shut down the subplan
297 : : */
298 : 53564 : ExecEndNode(outerPlanState(node));
299 : 53564 : }
300 : :
301 : : /* ----------------------------------------------------------------
302 : : * ExecSortMarkPos
303 : : *
304 : : * Calls tuplesort to save the current position in the sorted file.
305 : : * ----------------------------------------------------------------
306 : : */
307 : : void
308 : 357760 : ExecSortMarkPos(SortState *node)
309 : : {
310 : : /*
311 : : * if we haven't sorted yet, just return
312 : : */
313 [ - + ]: 357760 : if (!node->sort_Done)
314 : 0 : return;
315 : :
316 : 357760 : tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
317 : : }
318 : :
319 : : /* ----------------------------------------------------------------
320 : : * ExecSortRestrPos
321 : : *
322 : : * Calls tuplesort to restore the last saved sort file position.
323 : : * ----------------------------------------------------------------
324 : : */
325 : : void
326 : 28306 : ExecSortRestrPos(SortState *node)
327 : : {
328 : : /*
329 : : * if we haven't sorted yet, just return.
330 : : */
331 [ - + ]: 28306 : if (!node->sort_Done)
332 : 0 : return;
333 : :
334 : : /*
335 : : * restore the scan to the previously marked position
336 : : */
337 : 28306 : tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
338 : : }
339 : :
340 : : void
341 : 28413 : ExecReScanSort(SortState *node)
342 : : {
343 : 28413 : PlanState *outerPlan = outerPlanState(node);
344 : :
345 : : /*
346 : : * If we haven't sorted yet, just return. If outerplan's chgParam is not
347 : : * NULL then it will be re-scanned by ExecProcNode, else no reason to
348 : : * re-scan it at all.
349 : : */
350 [ + + ]: 28413 : if (!node->sort_Done)
351 : 598 : return;
352 : :
353 : : /* must drop pointer to sort result tuple */
354 : 27815 : ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
355 : :
356 : : /*
357 : : * If subnode is to be rescanned then we forget previous sort results; we
358 : : * have to re-read the subplan and re-sort. Also must re-sort if the
359 : : * bounded-sort parameters changed or we didn't select randomAccess.
360 : : *
361 : : * Otherwise we can just rewind and rescan the sorted output.
362 : : */
363 [ + + ]: 27815 : if (outerPlan->chgParam != NULL ||
364 [ + - ]: 540 : node->bounded != node->bounded_Done ||
365 [ + + ]: 540 : node->bound != node->bound_Done ||
366 [ + + ]: 504 : !node->randomAccess)
367 : : {
368 : 27793 : node->sort_Done = false;
369 : 27793 : tuplesort_end((Tuplesortstate *) node->tuplesortstate);
370 : 27793 : node->tuplesortstate = NULL;
371 : :
372 : : /*
373 : : * if chgParam of subnode is not null then plan will be re-scanned by
374 : : * first ExecProcNode.
375 : : */
376 [ + + ]: 27793 : if (outerPlan->chgParam == NULL)
377 : 518 : ExecReScan(outerPlan);
378 : : }
379 : : else
380 : 22 : tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
381 : : }
382 : :
383 : : /* ----------------------------------------------------------------
384 : : * Parallel Query Support
385 : : * ----------------------------------------------------------------
386 : : */
387 : :
388 : : /* ----------------------------------------------------------------
389 : : * ExecSortEstimate
390 : : *
391 : : * Estimate space required to propagate sort statistics.
392 : : * ----------------------------------------------------------------
393 : : */
394 : : void
395 : 110 : ExecSortEstimate(SortState *node, ParallelContext *pcxt)
396 : : {
397 : : Size size;
398 : :
399 : : /* don't need this if not instrumenting or no workers */
400 [ + + - + ]: 110 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
401 : 102 : return;
402 : :
403 : 8 : size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
404 : 8 : size = add_size(size, offsetof(SharedSortInfo, sinstrument));
405 : 8 : shm_toc_estimate_chunk(&pcxt->estimator, size);
406 : 8 : shm_toc_estimate_keys(&pcxt->estimator, 1);
407 : : }
408 : :
409 : : /* ----------------------------------------------------------------
410 : : * ExecSortInitializeDSM
411 : : *
412 : : * Initialize DSM space for sort statistics.
413 : : * ----------------------------------------------------------------
414 : : */
415 : : void
416 : 110 : ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
417 : : {
418 : : Size size;
419 : :
420 : : /* don't need this if not instrumenting or no workers */
421 [ + + - + ]: 110 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
422 : 102 : return;
423 : :
424 : 8 : size = offsetof(SharedSortInfo, sinstrument)
425 : 8 : + pcxt->nworkers * sizeof(TuplesortInstrumentation);
426 : 8 : node->shared_info = shm_toc_allocate(pcxt->toc, size);
427 : : /* ensure any unfilled slots will contain zeroes */
428 : 8 : memset(node->shared_info, 0, size);
429 : 8 : node->shared_info->num_workers = pcxt->nworkers;
430 : 8 : shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
431 : 8 : node->shared_info);
432 : : }
433 : :
434 : : /* ----------------------------------------------------------------
435 : : * ExecSortInitializeWorker
436 : : *
437 : : * Attach worker to DSM space for sort statistics.
438 : : * ----------------------------------------------------------------
439 : : */
440 : : void
441 : 315 : ExecSortInitializeWorker(SortState *node, ParallelWorkerContext *pwcxt)
442 : : {
443 : 315 : node->shared_info =
444 : 315 : shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
445 : 315 : node->am_worker = true;
446 : 315 : }
447 : :
448 : : /* ----------------------------------------------------------------
449 : : * ExecSortRetrieveInstrumentation
450 : : *
451 : : * Transfer sort statistics from DSM to private memory.
452 : : * ----------------------------------------------------------------
453 : : */
454 : : void
455 : 8 : ExecSortRetrieveInstrumentation(SortState *node)
456 : : {
457 : : Size size;
458 : : SharedSortInfo *si;
459 : :
460 [ - + ]: 8 : if (node->shared_info == NULL)
461 : 0 : return;
462 : :
463 : 8 : size = offsetof(SharedSortInfo, sinstrument)
464 : 8 : + node->shared_info->num_workers * sizeof(TuplesortInstrumentation);
465 : 8 : si = palloc(size);
466 : 8 : memcpy(si, node->shared_info, size);
467 : 8 : node->shared_info = si;
468 : : }
|
