Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nodeIncrementalSort.c
4 : : * Routines to handle incremental 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 : : * IDENTIFICATION
10 : : * src/backend/executor/nodeIncrementalSort.c
11 : : *
12 : : * DESCRIPTION
13 : : *
14 : : * Incremental sort is an optimized variant of multikey sort for cases
15 : : * when the input is already sorted by a prefix of the sort keys. For
16 : : * example when a sort by (key1, key2 ... keyN) is requested, and the
17 : : * input is already sorted by (key1, key2 ... keyM), M < N, we can
18 : : * divide the input into groups where keys (key1, ... keyM) are equal,
19 : : * and only sort on the remaining columns.
20 : : *
21 : : * Consider the following example. We have input tuples consisting of
22 : : * two integers (X, Y) already presorted by X, while it's required to
23 : : * sort them by both X and Y. Let input tuples be following.
24 : : *
25 : : * (1, 5)
26 : : * (1, 2)
27 : : * (2, 9)
28 : : * (2, 1)
29 : : * (2, 5)
30 : : * (3, 3)
31 : : * (3, 7)
32 : : *
33 : : * An incremental sort algorithm would split the input into the following
34 : : * groups, which have equal X, and then sort them by Y individually:
35 : : *
36 : : * (1, 5) (1, 2)
37 : : * (2, 9) (2, 1) (2, 5)
38 : : * (3, 3) (3, 7)
39 : : *
40 : : * After sorting these groups and putting them altogether, we would get
41 : : * the following result which is sorted by X and Y, as requested:
42 : : *
43 : : * (1, 2)
44 : : * (1, 5)
45 : : * (2, 1)
46 : : * (2, 5)
47 : : * (2, 9)
48 : : * (3, 3)
49 : : * (3, 7)
50 : : *
51 : : * Incremental sort may be more efficient than plain sort, particularly
52 : : * on large datasets, as it reduces the amount of data to sort at once,
53 : : * making it more likely it fits into work_mem (eliminating the need to
54 : : * spill to disk). But the main advantage of incremental sort is that
55 : : * it can start producing rows early, before sorting the whole dataset,
56 : : * which is a significant benefit especially for queries with LIMIT.
57 : : *
58 : : * The algorithm we've implemented here is modified from the theoretical
59 : : * base described above by operating in two different modes:
60 : : * - Fetching a minimum number of tuples without checking prefix key
61 : : * group membership and sorting on all columns when safe.
62 : : * - Fetching all tuples for a single prefix key group and sorting on
63 : : * solely the unsorted columns.
64 : : * We always begin in the first mode, and employ a heuristic to switch
65 : : * into the second mode if we believe it's beneficial.
66 : : *
67 : : * Sorting incrementally can potentially use less memory, avoid fetching
68 : : * and sorting all tuples in the dataset, and begin returning tuples before
69 : : * the entire result set is available.
70 : : *
71 : : * The hybrid mode approach allows us to optimize for both very small
72 : : * groups (where the overhead of a new tuplesort is high) and very large
73 : : * groups (where we can lower cost by not having to sort on already sorted
74 : : * columns), albeit at some extra cost while switching between modes.
75 : : *
76 : : *-------------------------------------------------------------------------
77 : : */
78 : :
79 : : #include "postgres.h"
80 : :
81 : : #include "executor/executor.h"
82 : : #include "executor/nodeIncrementalSort.h"
83 : : #include "miscadmin.h"
84 : : #include "utils/lsyscache.h"
85 : : #include "utils/tuplesort.h"
86 : :
87 : : /*
88 : : * We need to store the instrumentation information in either local node's sort
89 : : * info or, for a parallel worker process, in the shared info (this avoids
90 : : * having to additionally memcpy the info from local memory to shared memory
91 : : * at each instrumentation call). This macro expands to choose the proper sort
92 : : * state and group info.
93 : : *
94 : : * Arguments:
95 : : * - node: type IncrementalSortState *
96 : : * - groupName: the token fullsort or prefixsort
97 : : */
98 : : #define INSTRUMENT_SORT_GROUP(node, groupName) \
99 : : do { \
100 : : if ((node)->ss.ps.instrument != NULL) \
101 : : { \
102 : : if ((node)->shared_info && (node)->am_worker) \
103 : : { \
104 : : Assert(IsParallelWorker()); \
105 : : Assert(ParallelWorkerNumber < (node)->shared_info->num_workers); \
106 : : instrumentSortedGroup(&(node)->shared_info->sinfo[ParallelWorkerNumber].groupName##GroupInfo, \
107 : : (node)->groupName##_state); \
108 : : } \
109 : : else \
110 : : { \
111 : : instrumentSortedGroup(&(node)->incsort_info.groupName##GroupInfo, \
112 : : (node)->groupName##_state); \
113 : : } \
114 : : } \
115 : : } while (0)
116 : :
117 : :
118 : : /* ----------------------------------------------------------------
119 : : * instrumentSortedGroup
120 : : *
121 : : * Because incremental sort processes (potentially many) sort batches, we need
122 : : * to capture tuplesort stats each time we finalize a sort state. This summary
123 : : * data is later used for EXPLAIN ANALYZE output.
124 : : * ----------------------------------------------------------------
125 : : */
126 : : static void
2334 tomas.vondra@postgre 127 :CBC 96 : instrumentSortedGroup(IncrementalSortGroupInfo *groupInfo,
128 : : Tuplesortstate *sortState)
129 : : {
130 : : TuplesortInstrumentation sort_instr;
131 : :
132 : 96 : groupInfo->groupCount++;
133 : :
134 : 96 : tuplesort_get_stats(sortState, &sort_instr);
135 : :
136 : : /* Calculate total and maximum memory and disk space used. */
137 [ - + - ]: 96 : switch (sort_instr.spaceType)
138 : : {
2334 tomas.vondra@postgre 139 :UBC 0 : case SORT_SPACE_TYPE_DISK:
140 : 0 : groupInfo->totalDiskSpaceUsed += sort_instr.spaceUsed;
141 [ # # ]: 0 : if (sort_instr.spaceUsed > groupInfo->maxDiskSpaceUsed)
142 : 0 : groupInfo->maxDiskSpaceUsed = sort_instr.spaceUsed;
143 : :
144 : 0 : break;
2334 tomas.vondra@postgre 145 :CBC 96 : case SORT_SPACE_TYPE_MEMORY:
146 : 96 : groupInfo->totalMemorySpaceUsed += sort_instr.spaceUsed;
147 [ + + ]: 96 : if (sort_instr.spaceUsed > groupInfo->maxMemorySpaceUsed)
148 : 36 : groupInfo->maxMemorySpaceUsed = sort_instr.spaceUsed;
149 : :
150 : 96 : break;
151 : : }
152 : :
153 : : /* Track each sort method we've used. */
154 : 96 : groupInfo->sortMethods |= sort_instr.sortMethod;
155 : 96 : }
156 : :
157 : : /* ----------------------------------------------------------------
158 : : * preparePresortedCols
159 : : *
160 : : * Prepare information for presorted_keys comparisons.
161 : : * ----------------------------------------------------------------
162 : : */
163 : : static void
164 : 414 : preparePresortedCols(IncrementalSortState *node)
165 : : {
166 : 414 : IncrementalSort *plannode = castNode(IncrementalSort, node->ss.ps.plan);
167 : :
10 michael@paquier.xyz 168 :GNC 414 : node->presorted_keys = palloc_array(PresortedKeyData, plannode->nPresortedCols);
169 : :
170 : : /* Pre-cache comparison functions for each pre-sorted key. */
2334 tomas.vondra@postgre 171 [ + + ]:CBC 832 : for (int i = 0; i < plannode->nPresortedCols; i++)
172 : : {
173 : : Oid equalityOp,
174 : : equalityFunc;
175 : : PresortedKeyData *key;
176 : :
177 : 418 : key = &node->presorted_keys[i];
178 : 418 : key->attno = plannode->sort.sortColIdx[i];
179 : :
180 : 418 : equalityOp = get_equality_op_for_ordering_op(plannode->sort.sortOperators[i],
181 : : NULL);
182 [ - + ]: 418 : if (!OidIsValid(equalityOp))
2334 tomas.vondra@postgre 183 [ # # ]:UBC 0 : elog(ERROR, "missing equality operator for ordering operator %u",
184 : : plannode->sort.sortOperators[i]);
185 : :
2334 tomas.vondra@postgre 186 :CBC 418 : equalityFunc = get_opcode(equalityOp);
187 [ - + ]: 418 : if (!OidIsValid(equalityFunc))
2334 tomas.vondra@postgre 188 [ # # ]:UBC 0 : elog(ERROR, "missing function for operator %u", equalityOp);
189 : :
190 : : /* Lookup the comparison function */
2334 tomas.vondra@postgre 191 :CBC 418 : fmgr_info_cxt(equalityFunc, &key->flinfo, CurrentMemoryContext);
192 : :
193 : : /* We can initialize the callinfo just once and re-use it */
194 : 418 : key->fcinfo = palloc0(SizeForFunctionCallInfo(2));
195 : 418 : InitFunctionCallInfoData(*key->fcinfo, &key->flinfo, 2,
196 : : plannode->sort.collations[i], NULL, NULL);
197 : 418 : key->fcinfo->args[0].isnull = false;
198 : 418 : key->fcinfo->args[1].isnull = false;
199 : : }
200 : 414 : }
201 : :
202 : : /* ----------------------------------------------------------------
203 : : * isCurrentGroup
204 : : *
205 : : * Check whether a given tuple belongs to the current sort group by comparing
206 : : * the presorted column values to the pivot tuple of the current group.
207 : : * ----------------------------------------------------------------
208 : : */
209 : : static bool
210 : 332416 : isCurrentGroup(IncrementalSortState *node, TupleTableSlot *pivot, TupleTableSlot *tuple)
211 : : {
212 : : int nPresortedCols;
213 : :
214 : 332416 : nPresortedCols = castNode(IncrementalSort, node->ss.ps.plan)->nPresortedCols;
215 : :
216 : : /*
217 : : * That the input is sorted by keys * (0, ... n) implies that the tail
218 : : * keys are more likely to change. Therefore we do our comparison starting
219 : : * from the last pre-sorted column to optimize for early detection of
220 : : * inequality and minimizing the number of function calls..
221 : : */
222 [ + + ]: 662870 : for (int i = nPresortedCols - 1; i >= 0; i--)
223 : : {
224 : : Datum datumA,
225 : : datumB,
226 : : result;
227 : : bool isnullA,
228 : : isnullB;
229 : 332416 : AttrNumber attno = node->presorted_keys[i].attno;
230 : : PresortedKeyData *key;
231 : :
232 : 332416 : datumA = slot_getattr(pivot, attno, &isnullA);
233 : 332416 : datumB = slot_getattr(tuple, attno, &isnullB);
234 : :
235 : : /* Special case for NULL-vs-NULL, else use standard comparison */
236 [ + - - + ]: 332416 : if (isnullA || isnullB)
237 : : {
2334 tomas.vondra@postgre 238 [ # # ]:UBC 0 : if (isnullA == isnullB)
239 : 0 : continue;
240 : : else
2334 tomas.vondra@postgre 241 :CBC 1962 : return false;
242 : : }
243 : :
244 : 332416 : key = &node->presorted_keys[i];
245 : :
246 : 332416 : key->fcinfo->args[0].value = datumA;
247 : 332416 : key->fcinfo->args[1].value = datumB;
248 : :
249 : : /* just for paranoia's sake, we reset isnull each time */
250 : 332416 : key->fcinfo->isnull = false;
251 : :
252 : 332416 : result = FunctionCallInvoke(key->fcinfo);
253 : :
254 : : /* Check for null result, since caller is clearly not expecting one */
255 [ - + ]: 332416 : if (key->fcinfo->isnull)
2334 tomas.vondra@postgre 256 [ # # ]:UBC 0 : elog(ERROR, "function %u returned NULL", key->flinfo.fn_oid);
257 : :
2334 tomas.vondra@postgre 258 [ + + ]:CBC 332416 : if (!DatumGetBool(result))
259 : 1962 : return false;
260 : : }
261 : 330454 : return true;
262 : : }
263 : :
264 : : /* ----------------------------------------------------------------
265 : : * switchToPresortedPrefixMode
266 : : *
267 : : * When we determine that we've likely encountered a large batch of tuples all
268 : : * having the same presorted prefix values, we want to optimize tuplesort by
269 : : * only sorting on unsorted suffix keys.
270 : : *
271 : : * The problem is that we've already accumulated several tuples in another
272 : : * tuplesort configured to sort by all columns (assuming that there may be
273 : : * more than one prefix key group). So to switch to presorted prefix mode we
274 : : * have to go back and look at all the tuples we've already accumulated to
275 : : * verify they're all part of the same prefix key group before sorting them
276 : : * solely by unsorted suffix keys.
277 : : *
278 : : * While it's likely that all tuples already fetched are all part of a single
279 : : * prefix group, we also have to handle the possibility that there is at least
280 : : * one different prefix key group before the large prefix key group.
281 : : * ----------------------------------------------------------------
282 : : */
283 : : static void
284 : 394 : switchToPresortedPrefixMode(PlanState *pstate)
285 : : {
286 : 394 : IncrementalSortState *node = castNode(IncrementalSortState, pstate);
287 : : ScanDirection dir;
288 : : int64 nTuples;
289 : : TupleDesc tupDesc;
290 : : PlanState *outerNode;
291 : 394 : IncrementalSort *plannode = castNode(IncrementalSort, node->ss.ps.plan);
292 : :
293 : 394 : dir = node->ss.ps.state->es_direction;
294 : 394 : outerNode = outerPlanState(node);
295 : 394 : tupDesc = ExecGetResultType(outerNode);
296 : :
297 : : /* Configure the prefix sort state the first time around. */
298 [ + + ]: 394 : if (node->prefixsort_state == NULL)
299 : : {
300 : : Tuplesortstate *prefixsort_state;
301 : 74 : int nPresortedCols = plannode->nPresortedCols;
302 : :
303 : : /*
304 : : * Optimize the sort by assuming the prefix columns are all equal and
305 : : * thus we only need to sort by any remaining columns.
306 : : */
307 : 74 : prefixsort_state = tuplesort_begin_heap(tupDesc,
308 : 74 : plannode->sort.numCols - nPresortedCols,
309 : 74 : &(plannode->sort.sortColIdx[nPresortedCols]),
310 : 74 : &(plannode->sort.sortOperators[nPresortedCols]),
311 : 74 : &(plannode->sort.collations[nPresortedCols]),
312 : 74 : &(plannode->sort.nullsFirst[nPresortedCols]),
313 : : work_mem,
314 : : NULL,
1606 drowley@postgresql.o 315 [ + + ]: 74 : node->bounded ? TUPLESORT_ALLOWBOUNDED : TUPLESORT_NONE);
2334 tomas.vondra@postgre 316 : 74 : node->prefixsort_state = prefixsort_state;
317 : : }
318 : : else
319 : : {
320 : : /* Next group of presorted data */
321 : 320 : tuplesort_reset(node->prefixsort_state);
322 : : }
323 : :
324 : : /*
325 : : * If the current node has a bound, then it's reasonably likely that a
326 : : * large prefix key group will benefit from bounded sort, so configure the
327 : : * tuplesort to allow for that optimization.
328 : : */
329 [ + + ]: 394 : if (node->bounded)
330 : : {
331 : 121 : tuplesort_set_bound(node->prefixsort_state,
332 : 121 : node->bound - node->bound_Done);
333 : : }
334 : :
335 : : /*
336 : : * Copy as many tuples as we can (i.e., in the same prefix key group) from
337 : : * the full sort state to the prefix sort state.
338 : : */
2019 tgl@sss.pgh.pa.us 339 [ + + ]: 16203 : for (nTuples = 0; nTuples < node->n_fullsort_remaining; nTuples++)
340 : : {
341 : : /*
342 : : * When we encounter multiple prefix key groups inside the full sort
343 : : * tuplesort we have to carry over the last read tuple into the next
344 : : * batch.
345 : : */
346 [ + + + - : 15954 : if (nTuples == 0 && !TupIsNull(node->transfer_tuple))
+ + ]
347 : : {
2334 tomas.vondra@postgre 348 : 145 : tuplesort_puttupleslot(node->prefixsort_state, node->transfer_tuple);
349 : : /* The carried over tuple is our new group pivot tuple. */
350 : 145 : ExecCopySlot(node->group_pivot, node->transfer_tuple);
351 : : }
352 : : else
353 : : {
354 : 15809 : tuplesort_gettupleslot(node->fullsort_state,
355 : : ScanDirectionIsForward(dir),
356 : : false, node->transfer_tuple, NULL);
357 : :
358 : : /*
359 : : * If this is our first time through the loop, then we need to
360 : : * save the first tuple we get as our new group pivot.
361 : : */
362 [ + - + + ]: 15809 : if (TupIsNull(node->group_pivot))
363 : 249 : ExecCopySlot(node->group_pivot, node->transfer_tuple);
364 : :
365 [ + + ]: 15809 : if (isCurrentGroup(node, node->group_pivot, node->transfer_tuple))
366 : : {
367 : 15664 : tuplesort_puttupleslot(node->prefixsort_state, node->transfer_tuple);
368 : : }
369 : : else
370 : : {
371 : : /*
372 : : * The tuple isn't part of the current batch so we need to
373 : : * carry it over into the next batch of tuples we transfer out
374 : : * of the full sort tuplesort into the presorted prefix
375 : : * tuplesort. We don't actually have to do anything special to
376 : : * save the tuple since we've already loaded it into the
377 : : * node->transfer_tuple slot, and, even though that slot
378 : : * points to memory inside the full sort tuplesort, we can't
379 : : * reset that tuplesort anyway until we've fully transferred
380 : : * out its tuples, so this reference is safe. We do need to
381 : : * reset the group pivot tuple though since we've finished the
382 : : * current prefix key group.
383 : : */
384 : 145 : ExecClearTuple(node->group_pivot);
385 : :
386 : : /* Break out of for-loop early */
387 : 145 : break;
388 : : }
389 : : }
390 : : }
391 : :
392 : : /*
393 : : * Track how many tuples remain in the full sort batch so that we know if
394 : : * we need to sort multiple prefix key groups before processing tuples
395 : : * remaining in the large single prefix key group we think we've
396 : : * encountered.
397 : : */
398 : 394 : node->n_fullsort_remaining -= nTuples;
399 : :
2019 tgl@sss.pgh.pa.us 400 [ + + ]: 394 : if (node->n_fullsort_remaining == 0)
401 : : {
402 : : /*
403 : : * We've found that all tuples remaining in the full sort batch are in
404 : : * the same prefix key group and moved all of those tuples into the
405 : : * presorted prefix tuplesort. We don't know that we've yet found the
406 : : * last tuple in the current prefix key group, so save our pivot
407 : : * comparison tuple and continue fetching tuples from the outer
408 : : * execution node to load into the presorted prefix tuplesort.
409 : : */
2334 tomas.vondra@postgre 410 : 249 : ExecCopySlot(node->group_pivot, node->transfer_tuple);
411 : 249 : node->execution_status = INCSORT_LOADPREFIXSORT;
412 : :
413 : : /*
414 : : * Make sure we clear the transfer tuple slot so that next time we
415 : : * encounter a large prefix key group we don't incorrectly assume we
416 : : * have a tuple carried over from the previous group.
417 : : */
418 : 249 : ExecClearTuple(node->transfer_tuple);
419 : : }
420 : : else
421 : : {
422 : : /*
423 : : * We finished a group but didn't consume all of the tuples from the
424 : : * full sort state, so we'll sort this batch, let the outer node read
425 : : * out all of those tuples, and then come back around to find another
426 : : * batch.
427 : : */
428 : 145 : tuplesort_performsort(node->prefixsort_state);
429 : :
2296 tgl@sss.pgh.pa.us 430 [ + + - + : 145 : INSTRUMENT_SORT_GROUP(node, prefixsort);
- - - - -
- ]
431 : :
2334 tomas.vondra@postgre 432 [ + + ]: 145 : if (node->bounded)
433 : : {
434 : : /*
435 : : * If the current node has a bound and we've already sorted n
436 : : * tuples, then the functional bound remaining is (original bound
437 : : * - n), so store the current number of processed tuples for use
438 : : * in configuring sorting bound.
439 : : */
440 : 80 : node->bound_Done = Min(node->bound, node->bound_Done + nTuples);
441 : : }
442 : :
443 : 145 : node->execution_status = INCSORT_READPREFIXSORT;
444 : : }
445 : 394 : }
446 : :
447 : : /*
448 : : * Sorting many small groups with tuplesort is inefficient. In order to
449 : : * cope with this problem we don't start a new group until the current one
450 : : * contains at least DEFAULT_MIN_GROUP_SIZE tuples (unfortunately this also
451 : : * means we can't assume small groups of tuples all have the same prefix keys.)
452 : : * When we have a bound that's less than DEFAULT_MIN_GROUP_SIZE we start looking
453 : : * for the new group as soon as we've met our bound to avoid fetching more
454 : : * tuples than we absolutely have to fetch.
455 : : */
456 : : #define DEFAULT_MIN_GROUP_SIZE 32
457 : :
458 : : /*
459 : : * While we've optimized for small prefix key groups by not starting our prefix
460 : : * key comparisons until we've reached a minimum number of tuples, we don't want
461 : : * that optimization to cause us to lose out on the benefits of being able to
462 : : * assume a large group of tuples is fully presorted by its prefix keys.
463 : : * Therefore we use the DEFAULT_MAX_FULL_SORT_GROUP_SIZE cutoff as a heuristic
464 : : * for determining when we believe we've encountered a large group, and, if we
465 : : * get to that point without finding a new prefix key group we transition to
466 : : * presorted prefix key mode.
467 : : */
468 : : #define DEFAULT_MAX_FULL_SORT_GROUP_SIZE (2 * DEFAULT_MIN_GROUP_SIZE)
469 : :
470 : : /* ----------------------------------------------------------------
471 : : * ExecIncrementalSort
472 : : *
473 : : * Assuming that outer subtree returns tuple presorted by some prefix
474 : : * of target sort columns, performs incremental sort.
475 : : *
476 : : * Conditions:
477 : : * -- none.
478 : : *
479 : : * Initial States:
480 : : * -- the outer child is prepared to return the first tuple.
481 : : * ----------------------------------------------------------------
482 : : */
483 : : static TupleTableSlot *
484 : 354330 : ExecIncrementalSort(PlanState *pstate)
485 : : {
486 : 354330 : IncrementalSortState *node = castNode(IncrementalSortState, pstate);
487 : : EState *estate;
488 : : ScanDirection dir;
489 : : Tuplesortstate *read_sortstate;
490 : : Tuplesortstate *fullsort_state;
491 : : TupleTableSlot *slot;
492 : 354330 : IncrementalSort *plannode = (IncrementalSort *) node->ss.ps.plan;
493 : : PlanState *outerNode;
494 : : TupleDesc tupDesc;
495 : 354330 : int64 nTuples = 0;
496 : : int64 minGroupSize;
497 : :
498 [ - + ]: 354330 : CHECK_FOR_INTERRUPTS();
499 : :
500 : 354330 : estate = node->ss.ps.state;
501 : 354330 : dir = estate->es_direction;
502 : 354330 : fullsort_state = node->fullsort_state;
503 : :
504 : : /*
505 : : * If a previous iteration has sorted a batch, then we need to check to
506 : : * see if there are any remaining tuples in that batch that we can return
507 : : * before moving on to other execution states.
508 : : */
509 [ + + ]: 354330 : if (node->execution_status == INCSORT_READFULLSORT
510 [ + + ]: 295075 : || node->execution_status == INCSORT_READPREFIXSORT)
511 : : {
512 : : /*
513 : : * Return next tuple from the current sorted group set if available.
514 : : */
515 : 707824 : read_sortstate = node->execution_status == INCSORT_READFULLSORT ?
516 [ + + ]: 353912 : fullsort_state : node->prefixsort_state;
517 : 353912 : slot = node->ss.ps.ps_ResultTupleSlot;
518 : :
519 : : /*
520 : : * We have to populate the slot from the tuplesort before checking
521 : : * outerNodeDone because it will set the slot to NULL if no more
522 : : * tuples remain. If the tuplesort is empty, but we don't have any
523 : : * more tuples available for sort from the outer node, then
524 : : * outerNodeDone will have been set so we'll return that now-empty
525 : : * slot to the caller.
526 : : */
527 [ + + ]: 353912 : if (tuplesort_gettupleslot(read_sortstate, ScanDirectionIsForward(dir),
528 [ + + ]: 2130 : false, slot, NULL) || node->outerNodeDone)
529 : :
530 : : /*
531 : : * Note: there isn't a good test case for the node->outerNodeDone
532 : : * check directly, but we need it for any plan where the outer
533 : : * node will fail when trying to fetch too many tuples.
534 : : */
535 : 352027 : return slot;
536 [ + + ]: 1885 : else if (node->n_fullsort_remaining > 0)
537 : : {
538 : : /*
539 : : * When we transition to presorted prefix mode, we might have
540 : : * accumulated at least one additional prefix key group in the
541 : : * full sort tuplesort. The first call to
542 : : * switchToPresortedPrefixMode() will have pulled the first one of
543 : : * those groups out, and we've returned those tuples to the parent
544 : : * node, but if at this point we still have tuples remaining in
545 : : * the full sort state (i.e., n_fullsort_remaining > 0), then we
546 : : * need to re-execute the prefix mode transition function to pull
547 : : * out the next prefix key group.
548 : : */
549 : 145 : switchToPresortedPrefixMode(pstate);
550 : : }
551 : : else
552 : : {
553 : : /*
554 : : * If we don't have any sorted tuples to read and we're not
555 : : * currently transitioning into presorted prefix sort mode, then
556 : : * it's time to start the process all over again by building a new
557 : : * group in the full sort state.
558 : : */
559 : 1740 : node->execution_status = INCSORT_LOADFULLSORT;
560 : : }
561 : : }
562 : :
563 : : /*
564 : : * Scan the subplan in the forward direction while creating the sorted
565 : : * data.
566 : : */
567 : 2303 : estate->es_direction = ForwardScanDirection;
568 : :
569 : 2303 : outerNode = outerPlanState(node);
570 : 2303 : tupDesc = ExecGetResultType(outerNode);
571 : :
572 : : /* Load tuples into the full sort state. */
573 [ + + ]: 2303 : if (node->execution_status == INCSORT_LOADFULLSORT)
574 : : {
575 : : /*
576 : : * Initialize sorting structures.
577 : : */
578 [ + + ]: 2158 : if (fullsort_state == NULL)
579 : : {
580 : : /*
581 : : * Initialize presorted column support structures for
582 : : * isCurrentGroup(). It's correct to do this along with the
583 : : * initial initialization for the full sort state (and not for the
584 : : * prefix sort state) since we always load the full sort state
585 : : * first.
586 : : */
587 : 414 : preparePresortedCols(node);
588 : :
589 : : /*
590 : : * Since we optimize small prefix key groups by accumulating a
591 : : * minimum number of tuples before sorting, we can't assume that a
592 : : * group of tuples all have the same prefix key values. Hence we
593 : : * setup the full sort tuplesort to sort by all requested sort
594 : : * keys.
595 : : */
596 : 414 : fullsort_state = tuplesort_begin_heap(tupDesc,
597 : : plannode->sort.numCols,
598 : : plannode->sort.sortColIdx,
599 : : plannode->sort.sortOperators,
600 : : plannode->sort.collations,
601 : : plannode->sort.nullsFirst,
602 : : work_mem,
603 : : NULL,
1606 drowley@postgresql.o 604 [ + + ]: 414 : node->bounded ?
605 : : TUPLESORT_ALLOWBOUNDED :
606 : : TUPLESORT_NONE);
2334 tomas.vondra@postgre 607 : 414 : node->fullsort_state = fullsort_state;
608 : : }
609 : : else
610 : : {
611 : : /* Reset sort for the next batch. */
612 : 1744 : tuplesort_reset(fullsort_state);
613 : : }
614 : :
615 : : /*
616 : : * Calculate the remaining tuples left if bounded and configure both
617 : : * bounded sort and the minimum group size accordingly.
618 : : */
619 [ + + ]: 2158 : if (node->bounded)
620 : : {
621 : 141 : int64 currentBound = node->bound - node->bound_Done;
622 : :
623 : : /*
624 : : * Bounded sort isn't likely to be a useful optimization for full
625 : : * sort mode since we limit full sort mode to a relatively small
626 : : * number of tuples and tuplesort doesn't switch over to top-n
627 : : * heap sort anyway unless it hits (2 * bound) tuples.
628 : : */
629 [ + + ]: 141 : if (currentBound < DEFAULT_MIN_GROUP_SIZE)
630 : 52 : tuplesort_set_bound(fullsort_state, currentBound);
631 : :
632 : 141 : minGroupSize = Min(DEFAULT_MIN_GROUP_SIZE, currentBound);
633 : : }
634 : : else
635 : 2017 : minGroupSize = DEFAULT_MIN_GROUP_SIZE;
636 : :
637 : : /*
638 : : * Because we have to read the next tuple to find out that we've
639 : : * encountered a new prefix key group, on subsequent groups we have to
640 : : * carry over that extra tuple and add it to the new group's sort here
641 : : * before we read any new tuples from the outer node.
642 : : */
643 [ + - + + ]: 2158 : if (!TupIsNull(node->group_pivot))
644 : : {
645 : 1740 : tuplesort_puttupleslot(fullsort_state, node->group_pivot);
646 : 1740 : nTuples++;
647 : :
648 : : /*
649 : : * We're in full sort mode accumulating a minimum number of tuples
650 : : * and not checking for prefix key equality yet, so we can't
651 : : * assume the group pivot tuple will remain the same -- unless
652 : : * we're using a minimum group size of 1, in which case the pivot
653 : : * is obviously still the pivot.
654 : : */
655 [ + + ]: 1740 : if (nTuples != minGroupSize)
656 : 1732 : ExecClearTuple(node->group_pivot);
657 : : }
658 : :
659 : :
660 : : /*
661 : : * Pull as many tuples from the outer node as possible given our
662 : : * current operating mode.
663 : : */
664 : : for (;;)
665 : : {
666 : 76497 : slot = ExecProcNode(outerNode);
667 : :
668 : : /*
669 : : * If the outer node can't provide us any more tuples, then we can
670 : : * sort the current group and return those tuples.
671 : : */
672 [ + + + + ]: 76497 : if (TupIsNull(slot))
673 : : {
674 : : /*
675 : : * We need to know later if the outer node has completed to be
676 : : * able to distinguish between being done with a batch and
677 : : * being done with the whole node.
678 : : */
679 : 288 : node->outerNodeDone = true;
680 : :
681 : 288 : tuplesort_performsort(fullsort_state);
682 : :
2296 tgl@sss.pgh.pa.us 683 [ - + - - : 288 : INSTRUMENT_SORT_GROUP(node, fullsort);
- - - - -
- ]
684 : :
2334 tomas.vondra@postgre 685 : 288 : node->execution_status = INCSORT_READFULLSORT;
686 : 288 : break;
687 : : }
688 : :
689 : : /* Accumulate the next group of presorted tuples. */
690 [ + + ]: 76209 : if (nTuples < minGroupSize)
691 : : {
692 : : /*
693 : : * If we haven't yet hit our target minimum group size, then
694 : : * we don't need to bother checking for inclusion in the
695 : : * current prefix group since at this point we'll assume that
696 : : * we'll full sort this batch to avoid a large number of very
697 : : * tiny (and thus inefficient) sorts.
698 : : */
699 : 59153 : tuplesort_puttupleslot(fullsort_state, slot);
700 : 59153 : nTuples++;
701 : :
702 : : /*
703 : : * If we've reached our minimum group size, then we need to
704 : : * store the most recent tuple as a pivot.
705 : : */
706 [ + + ]: 59153 : if (nTuples == minGroupSize)
707 : 1863 : ExecCopySlot(node->group_pivot, slot);
708 : : }
709 : : else
710 : : {
711 : : /*
712 : : * If we've already accumulated enough tuples to reach our
713 : : * minimum group size, then we need to compare any additional
714 : : * tuples to our pivot tuple to see if we reach the end of
715 : : * that prefix key group. Only after we find changed prefix
716 : : * keys can we guarantee sort stability of the tuples we've
717 : : * already accumulated.
718 : : */
719 [ + + ]: 17056 : if (isCurrentGroup(node, node->group_pivot, slot))
720 : : {
721 : : /*
722 : : * As long as the prefix keys match the pivot tuple then
723 : : * load the tuple into the tuplesort.
724 : : */
725 : 15435 : tuplesort_puttupleslot(fullsort_state, slot);
726 : 15435 : nTuples++;
727 : : }
728 : : else
729 : : {
730 : : /*
731 : : * Since the tuple we fetched isn't part of the current
732 : : * prefix key group we don't want to sort it as part of
733 : : * the current batch. Instead we use the group_pivot slot
734 : : * to carry it over to the next batch (even though we
735 : : * won't actually treat it as a group pivot).
736 : : */
737 : 1621 : ExecCopySlot(node->group_pivot, slot);
738 : :
739 [ + + ]: 1621 : if (node->bounded)
740 : : {
741 : : /*
742 : : * If the current node has a bound, and we've already
743 : : * sorted n tuples, then the functional bound
744 : : * remaining is (original bound - n), so store the
745 : : * current number of processed tuples for later use
746 : : * configuring the sort state's bound.
747 : : */
748 : 100 : node->bound_Done = Min(node->bound, node->bound_Done + nTuples);
749 : : }
750 : :
751 : : /*
752 : : * Once we find changed prefix keys we can complete the
753 : : * sort and transition modes to reading out the sorted
754 : : * tuples.
755 : : */
756 : 1621 : tuplesort_performsort(fullsort_state);
757 : :
2296 tgl@sss.pgh.pa.us 758 [ + + - + : 1621 : INSTRUMENT_SORT_GROUP(node, fullsort);
- - - - -
- ]
759 : :
2334 tomas.vondra@postgre 760 : 1621 : node->execution_status = INCSORT_READFULLSORT;
761 : 1621 : break;
762 : : }
763 : : }
764 : :
765 : : /*
766 : : * Unless we've already transitioned modes to reading from the
767 : : * full sort state, then we assume that having read at least
768 : : * DEFAULT_MAX_FULL_SORT_GROUP_SIZE tuples means it's likely we're
769 : : * processing a large group of tuples all having equal prefix keys
770 : : * (but haven't yet found the final tuple in that prefix key
771 : : * group), so we need to transition into presorted prefix mode.
772 : : */
773 [ + + ]: 74588 : if (nTuples > DEFAULT_MAX_FULL_SORT_GROUP_SIZE &&
774 [ + - ]: 249 : node->execution_status != INCSORT_READFULLSORT)
775 : : {
776 : : /*
777 : : * The group pivot we have stored has already been put into
778 : : * the tuplesort; we don't want to carry it over. Since we
779 : : * haven't yet found the end of the prefix key group, it might
780 : : * seem like we should keep this, but we don't actually know
781 : : * how many prefix key groups might be represented in the full
782 : : * sort state, so we'll let the mode transition function
783 : : * manage this state for us.
784 : : */
785 : 249 : ExecClearTuple(node->group_pivot);
786 : :
787 : : /*
788 : : * Unfortunately the tuplesort API doesn't include a way to
789 : : * retrieve tuples unless a sort has been performed, so we
790 : : * perform the sort even though we could just as easily rely
791 : : * on FIFO retrieval semantics when transferring them to the
792 : : * presorted prefix tuplesort.
793 : : */
794 : 249 : tuplesort_performsort(fullsort_state);
795 : :
2296 tgl@sss.pgh.pa.us 796 [ + + - + : 249 : INSTRUMENT_SORT_GROUP(node, fullsort);
- - - - -
- ]
797 : :
798 : : /*
799 : : * If the full sort tuplesort happened to switch into top-n
800 : : * heapsort mode then we will only be able to retrieve
801 : : * currentBound tuples (since the tuplesort will have only
802 : : * retained the top-n tuples). This is safe even though we
803 : : * haven't yet completed fetching the current prefix key group
804 : : * because the tuples we've "lost" already sorted "below" the
805 : : * retained ones, and we're already contractually guaranteed
806 : : * to not need any more than the currentBound tuples.
807 : : */
2334 tomas.vondra@postgre 808 [ + + ]: 249 : if (tuplesort_used_bound(node->fullsort_state))
809 : : {
810 : 8 : int64 currentBound = node->bound - node->bound_Done;
811 : :
812 : 8 : nTuples = Min(currentBound, nTuples);
813 : : }
814 : :
815 : : /*
816 : : * We might have multiple prefix key groups in the full sort
817 : : * state, so the mode transition function needs to know that
818 : : * it needs to move from the fullsort to presorted prefix
819 : : * sort.
820 : : */
821 : 249 : node->n_fullsort_remaining = nTuples;
822 : :
823 : : /* Transition the tuples to the presorted prefix tuplesort. */
824 : 249 : switchToPresortedPrefixMode(pstate);
825 : :
826 : : /*
827 : : * Since we know we had tuples to move to the presorted prefix
828 : : * tuplesort, we know that unless that transition has verified
829 : : * that all tuples belonged to the same prefix key group (in
830 : : * which case we can go straight to continuing to load tuples
831 : : * into that tuplesort), we should have a tuple to return
832 : : * here.
833 : : *
834 : : * Either way, the appropriate execution status should have
835 : : * been set by switchToPresortedPrefixMode(), so we can drop
836 : : * out of the loop here and let the appropriate path kick in.
837 : : */
838 : 249 : break;
839 : : }
840 : : }
841 : : }
842 : :
843 [ + + ]: 2303 : if (node->execution_status == INCSORT_LOADPREFIXSORT)
844 : : {
845 : : /*
846 : : * We only enter this state after the mode transition function has
847 : : * confirmed all remaining tuples from the full sort state have the
848 : : * same prefix and moved those tuples to the prefix sort state. That
849 : : * function has also set a group pivot tuple (which doesn't need to be
850 : : * carried over; it's already been put into the prefix sort state).
851 : : */
852 [ + - - + ]: 249 : Assert(!TupIsNull(node->group_pivot));
853 : :
854 : : /*
855 : : * Read tuples from the outer node and load them into the prefix sort
856 : : * state until we encounter a tuple whose prefix keys don't match the
857 : : * current group_pivot tuple, since we can't guarantee sort stability
858 : : * until we have all tuples matching those prefix keys.
859 : : */
860 : : for (;;)
861 : : {
862 : 299604 : slot = ExecProcNode(outerNode);
863 : :
864 : : /*
865 : : * If we've exhausted tuples from the outer node we're done
866 : : * loading the prefix sort state.
867 : : */
868 [ + + + + ]: 299604 : if (TupIsNull(slot))
869 : : {
870 : : /*
871 : : * We need to know later if the outer node has completed to be
872 : : * able to distinguish between being done with a batch and
873 : : * being done with the whole node.
874 : : */
875 : 53 : node->outerNodeDone = true;
876 : 53 : break;
877 : : }
878 : :
879 : : /*
880 : : * If the tuple's prefix keys match our pivot tuple, we're not
881 : : * done yet and can load it into the prefix sort state. If not, we
882 : : * don't want to sort it as part of the current batch. Instead we
883 : : * use the group_pivot slot to carry it over to the next batch
884 : : * (even though we won't actually treat it as a group pivot).
885 : : */
886 [ + + ]: 299551 : if (isCurrentGroup(node, node->group_pivot, slot))
887 : : {
888 : 299355 : tuplesort_puttupleslot(node->prefixsort_state, slot);
889 : 299355 : nTuples++;
890 : : }
891 : : else
892 : : {
893 : 196 : ExecCopySlot(node->group_pivot, slot);
894 : 196 : break;
895 : : }
896 : : }
897 : :
898 : : /*
899 : : * Perform the sort and begin returning the tuples to the parent plan
900 : : * node.
901 : : */
902 : 249 : tuplesort_performsort(node->prefixsort_state);
903 : :
2296 tgl@sss.pgh.pa.us 904 [ + + - + : 249 : INSTRUMENT_SORT_GROUP(node, prefixsort);
- - - - -
- ]
905 : :
2334 tomas.vondra@postgre 906 : 249 : node->execution_status = INCSORT_READPREFIXSORT;
907 : :
908 [ + + ]: 249 : if (node->bounded)
909 : : {
910 : : /*
911 : : * If the current node has a bound, and we've already sorted n
912 : : * tuples, then the functional bound remaining is (original bound
913 : : * - n), so store the current number of processed tuples for use
914 : : * in configuring sorting bound.
915 : : */
916 : 41 : node->bound_Done = Min(node->bound, node->bound_Done + nTuples);
917 : : }
918 : : }
919 : :
920 : : /* Restore to user specified direction. */
921 : 2303 : estate->es_direction = dir;
922 : :
923 : : /*
924 : : * Get the first or next tuple from tuplesort. Returns NULL if no more
925 : : * tuples.
926 : : */
927 : 4606 : read_sortstate = node->execution_status == INCSORT_READFULLSORT ?
928 [ + + ]: 2303 : fullsort_state : node->prefixsort_state;
929 : 2303 : slot = node->ss.ps.ps_ResultTupleSlot;
930 : 2303 : (void) tuplesort_gettupleslot(read_sortstate, ScanDirectionIsForward(dir),
931 : : false, slot, NULL);
932 : 2303 : return slot;
933 : : }
934 : :
935 : : /* ----------------------------------------------------------------
936 : : * ExecInitIncrementalSort
937 : : *
938 : : * Creates the run-time state information for the sort node
939 : : * produced by the planner and initializes its outer subtree.
940 : : * ----------------------------------------------------------------
941 : : */
942 : : IncrementalSortState *
943 : 650 : ExecInitIncrementalSort(IncrementalSort *node, EState *estate, int eflags)
944 : : {
945 : : IncrementalSortState *incrsortstate;
946 : :
947 : : /*
948 : : * Incremental sort can't be used with EXEC_FLAG_BACKWARD or
949 : : * EXEC_FLAG_MARK, because the current sort state contains only one sort
950 : : * batch rather than the full result set.
951 : : */
2301 952 [ - + ]: 650 : Assert((eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)) == 0);
953 : :
954 : : /* Initialize state structure. */
2334 955 : 650 : incrsortstate = makeNode(IncrementalSortState);
956 : 650 : incrsortstate->ss.ps.plan = (Plan *) node;
957 : 650 : incrsortstate->ss.ps.state = estate;
958 : 650 : incrsortstate->ss.ps.ExecProcNode = ExecIncrementalSort;
959 : :
960 : 650 : incrsortstate->execution_status = INCSORT_LOADFULLSORT;
961 : 650 : incrsortstate->bounded = false;
962 : 650 : incrsortstate->outerNodeDone = false;
963 : 650 : incrsortstate->bound_Done = 0;
964 : 650 : incrsortstate->fullsort_state = NULL;
965 : 650 : incrsortstate->prefixsort_state = NULL;
966 : 650 : incrsortstate->group_pivot = NULL;
967 : 650 : incrsortstate->transfer_tuple = NULL;
968 : 650 : incrsortstate->n_fullsort_remaining = 0;
969 : 650 : incrsortstate->presorted_keys = NULL;
970 : :
971 [ - + ]: 650 : if (incrsortstate->ss.ps.instrument != NULL)
972 : : {
2334 tomas.vondra@postgre 973 :UBC 0 : IncrementalSortGroupInfo *fullsortGroupInfo =
974 : : &incrsortstate->incsort_info.fullsortGroupInfo;
975 : 0 : IncrementalSortGroupInfo *prefixsortGroupInfo =
976 : : &incrsortstate->incsort_info.prefixsortGroupInfo;
977 : :
978 : 0 : fullsortGroupInfo->groupCount = 0;
979 : 0 : fullsortGroupInfo->maxDiskSpaceUsed = 0;
980 : 0 : fullsortGroupInfo->totalDiskSpaceUsed = 0;
981 : 0 : fullsortGroupInfo->maxMemorySpaceUsed = 0;
982 : 0 : fullsortGroupInfo->totalMemorySpaceUsed = 0;
983 : 0 : fullsortGroupInfo->sortMethods = 0;
984 : 0 : prefixsortGroupInfo->groupCount = 0;
985 : 0 : prefixsortGroupInfo->maxDiskSpaceUsed = 0;
986 : 0 : prefixsortGroupInfo->totalDiskSpaceUsed = 0;
987 : 0 : prefixsortGroupInfo->maxMemorySpaceUsed = 0;
988 : 0 : prefixsortGroupInfo->totalMemorySpaceUsed = 0;
989 : 0 : prefixsortGroupInfo->sortMethods = 0;
990 : : }
991 : :
992 : : /*
993 : : * Miscellaneous initialization
994 : : *
995 : : * Sort nodes don't initialize their ExprContexts because they never call
996 : : * ExecQual or ExecProject.
997 : : */
998 : :
999 : : /*
1000 : : * Initialize child nodes.
1001 : : *
1002 : : * Incremental sort does not support backwards scans and mark/restore, so
1003 : : * we don't bother removing the flags from eflags here. We allow passing a
1004 : : * REWIND flag, because although incremental sort can't use it, the child
1005 : : * nodes may be able to do something more useful.
1006 : : */
2334 tomas.vondra@postgre 1007 :CBC 650 : outerPlanState(incrsortstate) = ExecInitNode(outerPlan(node), estate, eflags);
1008 : :
1009 : : /*
1010 : : * Initialize scan slot and type.
1011 : : */
1012 : 650 : ExecCreateScanSlotFromOuterPlan(estate, &incrsortstate->ss, &TTSOpsMinimalTuple);
1013 : :
1014 : : /*
1015 : : * Initialize return slot and type. No need to initialize projection info
1016 : : * because we don't do any projections.
1017 : : */
1018 : 650 : ExecInitResultTupleSlotTL(&incrsortstate->ss.ps, &TTSOpsMinimalTuple);
1019 : 650 : incrsortstate->ss.ps.ps_ProjInfo = NULL;
1020 : :
1021 : : /*
1022 : : * Initialize standalone slots to store a tuple for pivot prefix keys and
1023 : : * for carrying over a tuple from one batch to the next.
1024 : : */
1025 : 650 : incrsortstate->group_pivot =
1026 : 650 : MakeSingleTupleTableSlot(ExecGetResultType(outerPlanState(incrsortstate)),
1027 : : &TTSOpsMinimalTuple);
1028 : 650 : incrsortstate->transfer_tuple =
1029 : 650 : MakeSingleTupleTableSlot(ExecGetResultType(outerPlanState(incrsortstate)),
1030 : : &TTSOpsMinimalTuple);
1031 : :
1032 : 650 : return incrsortstate;
1033 : : }
1034 : :
1035 : : /* ----------------------------------------------------------------
1036 : : * ExecEndIncrementalSort(node)
1037 : : * ----------------------------------------------------------------
1038 : : */
1039 : : void
1040 : 650 : ExecEndIncrementalSort(IncrementalSortState *node)
1041 : : {
1042 : 650 : ExecDropSingleTupleTableSlot(node->group_pivot);
1043 : 650 : ExecDropSingleTupleTableSlot(node->transfer_tuple);
1044 : :
1045 : : /*
1046 : : * Release tuplesort resources.
1047 : : */
1048 [ + + ]: 650 : if (node->fullsort_state != NULL)
1049 : : {
1050 : 414 : tuplesort_end(node->fullsort_state);
1051 : 414 : node->fullsort_state = NULL;
1052 : : }
1053 [ + + ]: 650 : if (node->prefixsort_state != NULL)
1054 : : {
1055 : 74 : tuplesort_end(node->prefixsort_state);
1056 : 74 : node->prefixsort_state = NULL;
1057 : : }
1058 : :
1059 : : /*
1060 : : * Shut down the subplan.
1061 : : */
1062 : 650 : ExecEndNode(outerPlanState(node));
1063 : 650 : }
1064 : :
1065 : : void
1066 : 8 : ExecReScanIncrementalSort(IncrementalSortState *node)
1067 : : {
1068 : 8 : PlanState *outerPlan = outerPlanState(node);
1069 : :
1070 : : /*
1071 : : * Incremental sort doesn't support efficient rescan even when parameters
1072 : : * haven't changed (e.g., rewind) because unlike regular sort we don't
1073 : : * store all tuples at once for the full sort.
1074 : : *
1075 : : * So even if EXEC_FLAG_REWIND is set we just reset all of our state and
1076 : : * re-execute the sort along with the child node. Incremental sort itself
1077 : : * can't do anything smarter, but maybe the child nodes can.
1078 : : *
1079 : : * In theory if we've only filled the full sort with one batch (and
1080 : : * haven't reset it for a new batch yet) then we could efficiently rewind,
1081 : : * but that seems a narrow enough case that it's not worth handling
1082 : : * specially at this time.
1083 : : */
1084 : :
1085 : : /* must drop pointer to sort result tuple */
1086 : 8 : ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
1087 : :
1088 [ + - ]: 8 : if (node->group_pivot != NULL)
1089 : 8 : ExecClearTuple(node->group_pivot);
1090 [ + - ]: 8 : if (node->transfer_tuple != NULL)
1091 : 8 : ExecClearTuple(node->transfer_tuple);
1092 : :
1093 : 8 : node->outerNodeDone = false;
1094 : 8 : node->n_fullsort_remaining = 0;
1095 : 8 : node->bound_Done = 0;
1096 : :
1097 : 8 : node->execution_status = INCSORT_LOADFULLSORT;
1098 : :
1099 : : /*
1100 : : * If we've set up either of the sort states yet, we need to reset them.
1101 : : * We could end them and null out the pointers, but there's no reason to
1102 : : * repay the setup cost, and because ExecIncrementalSort guards presorted
1103 : : * column functions by checking to see if the full sort state has been
1104 : : * initialized yet, setting the sort states to null here might actually
1105 : : * cause a leak.
1106 : : */
1107 [ + + ]: 8 : if (node->fullsort_state != NULL)
1108 : 4 : tuplesort_reset(node->fullsort_state);
1109 [ + + ]: 8 : if (node->prefixsort_state != NULL)
1110 : 4 : tuplesort_reset(node->prefixsort_state);
1111 : :
1112 : : /*
1113 : : * If chgParam of subnode is not null, then the plan will be re-scanned by
1114 : : * the first ExecProcNode.
1115 : : */
1116 [ + - ]: 8 : if (outerPlan->chgParam == NULL)
1117 : 8 : ExecReScan(outerPlan);
1118 : 8 : }
1119 : :
1120 : : /* ----------------------------------------------------------------
1121 : : * Parallel Query Support
1122 : : * ----------------------------------------------------------------
1123 : : */
1124 : :
1125 : : /* ----------------------------------------------------------------
1126 : : * ExecSortEstimate
1127 : : *
1128 : : * Estimate space required to propagate sort statistics.
1129 : : * ----------------------------------------------------------------
1130 : : */
1131 : : void
2334 tomas.vondra@postgre 1132 :UBC 0 : ExecIncrementalSortEstimate(IncrementalSortState *node, ParallelContext *pcxt)
1133 : : {
1134 : : Size size;
1135 : :
1136 : : /* don't need this if not instrumenting or no workers */
1137 [ # # # # ]: 0 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
1138 : 0 : return;
1139 : :
1140 : 0 : size = mul_size(pcxt->nworkers, sizeof(IncrementalSortInfo));
1141 : 0 : size = add_size(size, offsetof(SharedIncrementalSortInfo, sinfo));
1142 : 0 : shm_toc_estimate_chunk(&pcxt->estimator, size);
1143 : 0 : shm_toc_estimate_keys(&pcxt->estimator, 1);
1144 : : }
1145 : :
1146 : : /* ----------------------------------------------------------------
1147 : : * ExecSortInitializeDSM
1148 : : *
1149 : : * Initialize DSM space for sort statistics.
1150 : : * ----------------------------------------------------------------
1151 : : */
1152 : : void
1153 : 0 : ExecIncrementalSortInitializeDSM(IncrementalSortState *node, ParallelContext *pcxt)
1154 : : {
1155 : : Size size;
1156 : :
1157 : : /* don't need this if not instrumenting or no workers */
1158 [ # # # # ]: 0 : if (!node->ss.ps.instrument || pcxt->nworkers == 0)
1159 : 0 : return;
1160 : :
1161 : 0 : size = offsetof(SharedIncrementalSortInfo, sinfo)
1162 : 0 : + pcxt->nworkers * sizeof(IncrementalSortInfo);
1163 : 0 : node->shared_info = shm_toc_allocate(pcxt->toc, size);
1164 : : /* ensure any unfilled slots will contain zeroes */
1165 : 0 : memset(node->shared_info, 0, size);
1166 : 0 : node->shared_info->num_workers = pcxt->nworkers;
1167 : 0 : shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
1168 : 0 : node->shared_info);
1169 : : }
1170 : :
1171 : : /* ----------------------------------------------------------------
1172 : : * ExecSortInitializeWorker
1173 : : *
1174 : : * Attach worker to DSM space for sort statistics.
1175 : : * ----------------------------------------------------------------
1176 : : */
1177 : : void
1178 : 0 : ExecIncrementalSortInitializeWorker(IncrementalSortState *node, ParallelWorkerContext *pwcxt)
1179 : : {
1180 : 0 : node->shared_info =
1181 : 0 : shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
1182 : 0 : node->am_worker = true;
1183 : 0 : }
1184 : :
1185 : : /* ----------------------------------------------------------------
1186 : : * ExecSortRetrieveInstrumentation
1187 : : *
1188 : : * Transfer sort statistics from DSM to private memory.
1189 : : * ----------------------------------------------------------------
1190 : : */
1191 : : void
1192 : 0 : ExecIncrementalSortRetrieveInstrumentation(IncrementalSortState *node)
1193 : : {
1194 : : Size size;
1195 : : SharedIncrementalSortInfo *si;
1196 : :
1197 [ # # ]: 0 : if (node->shared_info == NULL)
1198 : 0 : return;
1199 : :
1200 : 0 : size = offsetof(SharedIncrementalSortInfo, sinfo)
1201 : 0 : + node->shared_info->num_workers * sizeof(IncrementalSortInfo);
1202 : 0 : si = palloc(size);
1203 : 0 : memcpy(si, node->shared_info, size);
1204 : 0 : node->shared_info = si;
1205 : : }
|
