Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nodeMergeAppend.c
4 : : * routines to handle MergeAppend nodes.
5 : : *
6 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/executor/nodeMergeAppend.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : /* INTERFACE ROUTINES
16 : : * ExecInitMergeAppend - initialize the MergeAppend node
17 : : * ExecMergeAppend - retrieve the next tuple from the node
18 : : * ExecEndMergeAppend - shut down the MergeAppend node
19 : : * ExecReScanMergeAppend - rescan the MergeAppend node
20 : : *
21 : : * NOTES
22 : : * A MergeAppend node contains a list of one or more subplans.
23 : : * These are each expected to deliver tuples that are sorted according
24 : : * to a common sort key. The MergeAppend node merges these streams
25 : : * to produce output sorted the same way.
26 : : *
27 : : * MergeAppend nodes don't make use of their left and right
28 : : * subtrees, rather they maintain a list of subplans so
29 : : * a typical MergeAppend node looks like this in the plan tree:
30 : : *
31 : : * ...
32 : : * /
33 : : * MergeAppend---+------+------+--- nil
34 : : * / \ | | |
35 : : * nil nil ... ... ...
36 : : * subplans
37 : : */
38 : :
39 : : #include "postgres.h"
40 : :
41 : : #include "executor/executor.h"
42 : : #include "executor/execPartition.h"
43 : : #include "executor/nodeMergeAppend.h"
44 : : #include "lib/binaryheap.h"
45 : : #include "miscadmin.h"
46 : :
47 : : /*
48 : : * We have one slot for each item in the heap array. We use SlotNumber
49 : : * to store slot indexes. This doesn't actually provide any formal
50 : : * type-safety, but it makes the code more self-documenting.
51 : : */
52 : : typedef int32 SlotNumber;
53 : :
54 : : static TupleTableSlot *ExecMergeAppend(PlanState *pstate);
55 : : static int heap_compare_slots(Datum a, Datum b, void *arg);
56 : :
57 : :
58 : : /* ----------------------------------------------------------------
59 : : * ExecInitMergeAppend
60 : : *
61 : : * Begin all of the subscans of the MergeAppend node.
62 : : * ----------------------------------------------------------------
63 : : */
64 : : MergeAppendState *
5441 tgl@sss.pgh.pa.us 65 :CBC 296 : ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
66 : : {
67 : 296 : MergeAppendState *mergestate = makeNode(MergeAppendState);
68 : : PlanState **mergeplanstates;
69 : : const TupleTableSlotOps *mergeops;
70 : : Bitmapset *validsubplans;
71 : : int nplans;
72 : : int i,
73 : : j;
74 : :
75 : : /* check for unsupported flags */
76 [ - + ]: 296 : Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
77 : :
78 : : /*
79 : : * create new MergeAppendState for our node
80 : : */
81 : 296 : mergestate->ps.plan = (Plan *) node;
82 : 296 : mergestate->ps.state = estate;
2973 andres@anarazel.de 83 : 296 : mergestate->ps.ExecProcNode = ExecMergeAppend;
84 : :
85 : : /* If run-time partition pruning is enabled, then set that up now */
219 amitlan@postgresql.o 86 [ + + ]: 296 : if (node->part_prune_index >= 0)
87 : : {
88 : : PartitionPruneState *prunestate;
89 : :
90 : : /*
91 : : * Set up pruning data structure. This also initializes the set of
92 : : * subplans to initialize (validsubplans) by taking into account the
93 : : * result of performing initial pruning if any.
94 : : */
218 95 : 33 : prunestate = ExecInitPartitionExecPruning(&mergestate->ps,
96 : 33 : list_length(node->mergeplans),
97 : : node->part_prune_index,
98 : : node->apprelids,
99 : : &validsubplans);
2606 heikki.linnakangas@i 100 : 33 : mergestate->ms_prune_state = prunestate;
1250 alvherre@alvh.no-ip. 101 : 33 : nplans = bms_num_members(validsubplans);
102 : :
103 : : /*
104 : : * When no run-time pruning is required and there's at least one
105 : : * subplan, we can fill ms_valid_subplans immediately, preventing
106 : : * later calls to ExecFindMatchingSubPlans.
107 : : */
2096 tgl@sss.pgh.pa.us 108 [ + + + + ]: 33 : if (!prunestate->do_exec_prune && nplans > 0)
2606 heikki.linnakangas@i 109 : 18 : mergestate->ms_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
110 : : }
111 : : else
112 : : {
113 : 263 : nplans = list_length(node->mergeplans);
114 : :
115 : : /*
116 : : * When run-time partition pruning is not enabled we can just mark all
117 : : * subplans as valid; they must also all be initialized.
118 : : */
2595 alvherre@alvh.no-ip. 119 [ - + ]: 263 : Assert(nplans > 0);
2606 heikki.linnakangas@i 120 : 263 : mergestate->ms_valid_subplans = validsubplans =
121 : 263 : bms_add_range(NULL, 0, nplans - 1);
122 : 263 : mergestate->ms_prune_state = NULL;
123 : : }
124 : :
125 : 296 : mergeplanstates = (PlanState **) palloc(nplans * sizeof(PlanState *));
5441 tgl@sss.pgh.pa.us 126 : 296 : mergestate->mergeplans = mergeplanstates;
127 : 296 : mergestate->ms_nplans = nplans;
128 : :
129 : 296 : mergestate->ms_slots = (TupleTableSlot **) palloc0(sizeof(TupleTableSlot *) * nplans);
513 msawada@postgresql.o 130 : 296 : mergestate->ms_heap = binaryheap_allocate(nplans, heap_compare_slots,
131 : : mergestate);
132 : :
133 : : /*
134 : : * call ExecInitNode on each of the valid plans to be executed and save
135 : : * the results into the mergeplanstates array.
136 : : */
2238 drowley@postgresql.o 137 : 296 : j = 0;
138 : 296 : i = -1;
139 [ + + ]: 1081 : while ((i = bms_next_member(validsubplans, i)) >= 0)
140 : : {
141 : 785 : Plan *initNode = (Plan *) list_nth(node->mergeplans, i);
142 : :
143 : 785 : mergeplanstates[j++] = ExecInitNode(initNode, estate, eflags);
144 : : }
145 : :
146 : : /*
147 : : * Initialize MergeAppend's result tuple type and slot. If the child
148 : : * plans all produce the same fixed slot type, we can use that slot type;
149 : : * otherwise make a virtual slot. (Note that the result slot itself is
150 : : * used only to return a null tuple at end of execution; real tuples are
151 : : * returned to the caller in the children's own result slots. What we are
152 : : * doing here is allowing the parent plan node to optimize if the
153 : : * MergeAppend will return only one kind of slot.)
154 : : */
261 tgl@sss.pgh.pa.us 155 : 296 : mergeops = ExecGetCommonSlotOps(mergeplanstates, j);
156 [ + + ]: 296 : if (mergeops != NULL)
157 : : {
158 : 225 : ExecInitResultTupleSlotTL(&mergestate->ps, mergeops);
159 : : }
160 : : else
161 : : {
162 : 71 : ExecInitResultTupleSlotTL(&mergestate->ps, &TTSOpsVirtual);
163 : : /* show that the output slot type is not fixed */
164 : 71 : mergestate->ps.resultopsset = true;
165 : 71 : mergestate->ps.resultopsfixed = false;
166 : : }
167 : :
168 : : /*
169 : : * Miscellaneous initialization
170 : : */
5441 171 : 296 : mergestate->ps.ps_ProjInfo = NULL;
172 : :
173 : : /*
174 : : * initialize sort-key information
175 : : */
176 : 296 : mergestate->ms_nkeys = node->numCols;
5022 177 : 296 : mergestate->ms_sortkeys = palloc0(sizeof(SortSupportData) * node->numCols);
178 : :
5441 179 [ + + ]: 644 : for (i = 0; i < node->numCols; i++)
180 : : {
4836 bruce@momjian.us 181 : 348 : SortSupport sortKey = mergestate->ms_sortkeys + i;
182 : :
5022 tgl@sss.pgh.pa.us 183 : 348 : sortKey->ssup_cxt = CurrentMemoryContext;
184 : 348 : sortKey->ssup_collation = node->collations[i];
185 : 348 : sortKey->ssup_nulls_first = node->nullsFirst[i];
186 : 348 : sortKey->ssup_attno = node->sortColIdx[i];
187 : :
188 : : /*
189 : : * It isn't feasible to perform abbreviated key conversion, since
190 : : * tuples are pulled into mergestate's binary heap as needed. It
191 : : * would likely be counter-productive to convert tuples into an
192 : : * abbreviated representation as they're pulled up, so opt out of that
193 : : * additional optimization entirely.
194 : : */
3883 rhaas@postgresql.org 195 : 348 : sortKey->abbreviate = false;
196 : :
5022 tgl@sss.pgh.pa.us 197 : 348 : PrepareSortSupportFromOrderingOp(node->sortOperators[i], sortKey);
198 : : }
199 : :
200 : : /*
201 : : * initialize to show we have not run the subplans yet
202 : : */
5441 203 : 296 : mergestate->ms_initialized = false;
204 : :
205 : 296 : return mergestate;
206 : : }
207 : :
208 : : /* ----------------------------------------------------------------
209 : : * ExecMergeAppend
210 : : *
211 : : * Handles iteration over multiple subplans.
212 : : * ----------------------------------------------------------------
213 : : */
214 : : static TupleTableSlot *
2973 andres@anarazel.de 215 : 82010 : ExecMergeAppend(PlanState *pstate)
216 : : {
217 : 82010 : MergeAppendState *node = castNode(MergeAppendState, pstate);
218 : : TupleTableSlot *result;
219 : : SlotNumber i;
220 : :
2965 221 [ - + ]: 82010 : CHECK_FOR_INTERRUPTS();
222 : :
5441 tgl@sss.pgh.pa.us 223 [ + + ]: 82010 : if (!node->ms_initialized)
224 : : {
225 : : /* Nothing to do if all subplans were pruned */
2096 226 [ + + ]: 143 : if (node->ms_nplans == 0)
2606 heikki.linnakangas@i 227 : 9 : return ExecClearTuple(node->ps.ps_ResultTupleSlot);
228 : :
229 : : /*
230 : : * If we've yet to determine the valid subplans then do so now. If
231 : : * run-time pruning is disabled then the valid subplans will always be
232 : : * set to all subplans.
233 : : */
234 [ + + ]: 134 : if (node->ms_valid_subplans == NULL)
235 : 6 : node->ms_valid_subplans =
211 amitlan@postgresql.o 236 : 6 : ExecFindMatchingSubPlans(node->ms_prune_state, false, NULL);
237 : :
238 : : /*
239 : : * First time through: pull the first tuple from each valid subplan,
240 : : * and set up the heap.
241 : : */
2606 heikki.linnakangas@i 242 : 134 : i = -1;
243 [ + + ]: 485 : while ((i = bms_next_member(node->ms_valid_subplans, i)) >= 0)
244 : : {
5441 tgl@sss.pgh.pa.us 245 : 351 : node->ms_slots[i] = ExecProcNode(node->mergeplans[i]);
246 [ + + + + ]: 351 : if (!TupIsNull(node->ms_slots[i]))
4664 rhaas@postgresql.org 247 : 301 : binaryheap_add_unordered(node->ms_heap, Int32GetDatum(i));
248 : : }
249 : 134 : binaryheap_build(node->ms_heap);
5441 tgl@sss.pgh.pa.us 250 : 134 : node->ms_initialized = true;
251 : : }
252 : : else
253 : : {
254 : : /*
255 : : * Otherwise, pull the next tuple from whichever subplan we returned
256 : : * from last time, and reinsert the subplan index into the heap,
257 : : * because it might now compare differently against the existing
258 : : * elements of the heap. (We could perhaps simplify the logic a bit
259 : : * by doing this before returning from the prior call, but it's better
260 : : * to not pull tuples until necessary.)
261 : : */
4664 rhaas@postgresql.org 262 : 81867 : i = DatumGetInt32(binaryheap_first(node->ms_heap));
5441 tgl@sss.pgh.pa.us 263 : 81867 : node->ms_slots[i] = ExecProcNode(node->mergeplans[i]);
264 [ + + + + ]: 81867 : if (!TupIsNull(node->ms_slots[i]))
4664 rhaas@postgresql.org 265 : 81659 : binaryheap_replace_first(node->ms_heap, Int32GetDatum(i));
266 : : else
267 : 208 : (void) binaryheap_remove_first(node->ms_heap);
268 : : }
269 : :
270 [ + + ]: 82001 : if (binaryheap_empty(node->ms_heap))
271 : : {
272 : : /* All the subplans are exhausted, and so is the heap */
5441 tgl@sss.pgh.pa.us 273 : 101 : result = ExecClearTuple(node->ps.ps_ResultTupleSlot);
274 : : }
275 : : else
276 : : {
4664 rhaas@postgresql.org 277 : 81900 : i = DatumGetInt32(binaryheap_first(node->ms_heap));
278 : 81900 : result = node->ms_slots[i];
279 : : }
280 : :
281 : 82001 : return result;
282 : : }
283 : :
284 : : /*
285 : : * Compare the tuples in the two given slots.
286 : : */
287 : : static int32
288 : 74755 : heap_compare_slots(Datum a, Datum b, void *arg)
289 : : {
290 : 74755 : MergeAppendState *node = (MergeAppendState *) arg;
291 : 74755 : SlotNumber slot1 = DatumGetInt32(a);
292 : 74755 : SlotNumber slot2 = DatumGetInt32(b);
293 : :
5441 tgl@sss.pgh.pa.us 294 : 74755 : TupleTableSlot *s1 = node->ms_slots[slot1];
295 : 74755 : TupleTableSlot *s2 = node->ms_slots[slot2];
296 : : int nkey;
297 : :
298 [ + - - + ]: 74755 : Assert(!TupIsNull(s1));
299 [ + - - + ]: 74755 : Assert(!TupIsNull(s2));
300 : :
301 [ + + ]: 99181 : for (nkey = 0; nkey < node->ms_nkeys; nkey++)
302 : : {
4836 bruce@momjian.us 303 : 74755 : SortSupport sortKey = node->ms_sortkeys + nkey;
5022 tgl@sss.pgh.pa.us 304 : 74755 : AttrNumber attno = sortKey->ssup_attno;
305 : : Datum datum1,
306 : : datum2;
307 : : bool isNull1,
308 : : isNull2;
309 : : int compare;
310 : :
5441 311 : 74755 : datum1 = slot_getattr(s1, attno, &isNull1);
312 : 74755 : datum2 = slot_getattr(s2, attno, &isNull2);
313 : :
5022 314 : 74755 : compare = ApplySortComparator(datum1, isNull1,
315 : : datum2, isNull2,
316 : : sortKey);
317 [ + + ]: 74755 : if (compare != 0)
318 : : {
2528 319 [ + + ]: 50329 : INVERT_COMPARE_RESULT(compare);
320 : 50329 : return compare;
321 : : }
322 : : }
5441 323 : 24426 : return 0;
324 : : }
325 : :
326 : : /* ----------------------------------------------------------------
327 : : * ExecEndMergeAppend
328 : : *
329 : : * Shuts down the subscans of the MergeAppend node.
330 : : *
331 : : * Returns nothing of interest.
332 : : * ----------------------------------------------------------------
333 : : */
334 : : void
335 : 296 : ExecEndMergeAppend(MergeAppendState *node)
336 : : {
337 : : PlanState **mergeplans;
338 : : int nplans;
339 : : int i;
340 : :
341 : : /*
342 : : * get information from the node
343 : : */
344 : 296 : mergeplans = node->mergeplans;
345 : 296 : nplans = node->ms_nplans;
346 : :
347 : : /*
348 : : * shut down each of the subscans
349 : : */
350 [ + + ]: 1081 : for (i = 0; i < nplans; i++)
351 : 785 : ExecEndNode(mergeplans[i]);
352 : 296 : }
353 : :
354 : : void
355 : 9 : ExecReScanMergeAppend(MergeAppendState *node)
356 : : {
357 : : int i;
358 : :
359 : : /*
360 : : * If any PARAM_EXEC Params used in pruning expressions have changed, then
361 : : * we'd better unset the valid subplans so that they are reselected for
362 : : * the new parameter values.
363 : : */
2606 heikki.linnakangas@i 364 [ - + - - ]: 9 : if (node->ms_prune_state &&
2606 heikki.linnakangas@i 365 :UBC 0 : bms_overlap(node->ps.chgParam,
366 : 0 : node->ms_prune_state->execparamids))
367 : : {
368 : 0 : bms_free(node->ms_valid_subplans);
369 : 0 : node->ms_valid_subplans = NULL;
370 : : }
371 : :
5441 tgl@sss.pgh.pa.us 372 [ + + ]:CBC 27 : for (i = 0; i < node->ms_nplans; i++)
373 : : {
374 : 18 : PlanState *subnode = node->mergeplans[i];
375 : :
376 : : /*
377 : : * ExecReScan doesn't know about my subplans, so I have to do
378 : : * changed-parameter signaling myself.
379 : : */
380 [ + - ]: 18 : if (node->ps.chgParam != NULL)
381 : 18 : UpdateChangedParamSet(subnode, node->ps.chgParam);
382 : :
383 : : /*
384 : : * If chgParam of subnode is not null then plan will be re-scanned by
385 : : * first ExecProcNode.
386 : : */
387 [ - + ]: 18 : if (subnode->chgParam == NULL)
5441 tgl@sss.pgh.pa.us 388 :UBC 0 : ExecReScan(subnode);
389 : : }
4390 tgl@sss.pgh.pa.us 390 :CBC 9 : binaryheap_reset(node->ms_heap);
5441 391 : 9 : node->ms_initialized = false;
392 : 9 : }
|
