Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nodeRecursiveunion.c
4 : : * routines to handle RecursiveUnion nodes.
5 : : *
6 : : * To implement UNION (without ALL), we need a hashtable that stores tuples
7 : : * already seen. The hash key is computed from the grouping columns.
8 : : *
9 : : *
10 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
11 : : * Portions Copyright (c) 1994, Regents of the University of California
12 : : *
13 : : *
14 : : * IDENTIFICATION
15 : : * src/backend/executor/nodeRecursiveunion.c
16 : : *
17 : : *-------------------------------------------------------------------------
18 : : */
19 : : #include "postgres.h"
20 : :
21 : : #include "executor/executor.h"
22 : : #include "executor/nodeRecursiveunion.h"
23 : : #include "miscadmin.h"
24 : : #include "utils/memutils.h"
25 : :
26 : :
27 : :
28 : : /*
29 : : * Initialize the hash table to empty.
30 : : */
31 : : static void
6279 tgl@sss.pgh.pa.us 32 :CBC 193 : build_hash_table(RecursiveUnionState *rustate)
33 : : {
6032 bruce@momjian.us 34 : 193 : RecursiveUnion *node = (RecursiveUnion *) rustate->ps.plan;
2861 andres@anarazel.de 35 : 193 : TupleDesc desc = ExecGetResultType(outerPlanState(rustate));
36 : :
6279 tgl@sss.pgh.pa.us 37 [ - + ]: 193 : Assert(node->numCols > 0);
38 : :
39 : : /*
40 : : * If both child plans deliver the same fixed tuple slot type, we can tell
41 : : * BuildTupleHashTable to expect that slot type as input. Otherwise,
42 : : * we'll pass NULL denoting that any slot type is possible.
43 : : */
362 44 : 193 : rustate->hashtable = BuildTupleHashTable(&rustate->ps,
45 : : desc,
46 : : ExecGetCommonChildSlotOps(&rustate->ps),
47 : : node->numCols,
48 : : node->dupColIdx,
49 : 193 : rustate->eqfuncoids,
50 : : rustate->hashfunctions,
51 : : node->dupCollations,
52 : : node->numGroups,
53 : : 0,
54 : 193 : rustate->ps.state->es_query_cxt,
55 : : rustate->tuplesContext,
56 : : rustate->tempContext,
57 : : false);
6279 58 : 193 : }
59 : :
60 : :
61 : : /* ----------------------------------------------------------------
62 : : * ExecRecursiveUnion(node)
63 : : *
64 : : * Scans the recursive query sequentially and returns the next
65 : : * qualifying tuple.
66 : : *
67 : : * 1. evaluate non recursive term and assign the result to RT
68 : : *
69 : : * 2. execute recursive terms
70 : : *
71 : : * 2.1 WT := RT
72 : : * 2.2 while WT is not empty repeat 2.3 to 2.6. if WT is empty returns RT
73 : : * 2.3 replace the name of recursive term with WT
74 : : * 2.4 evaluate the recursive term and store into WT
75 : : * 2.5 append WT to RT
76 : : * 2.6 go back to 2.2
77 : : * ----------------------------------------------------------------
78 : : */
79 : : static TupleTableSlot *
3074 andres@anarazel.de 80 : 36123 : ExecRecursiveUnion(PlanState *pstate)
81 : : {
82 : 36123 : RecursiveUnionState *node = castNode(RecursiveUnionState, pstate);
6282 tgl@sss.pgh.pa.us 83 : 36123 : PlanState *outerPlan = outerPlanState(node);
84 : 36123 : PlanState *innerPlan = innerPlanState(node);
85 : 36123 : RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan;
86 : : TupleTableSlot *slot;
87 : : bool isnew;
88 : :
3066 andres@anarazel.de 89 [ - + ]: 36123 : CHECK_FOR_INTERRUPTS();
90 : :
91 : : /* 1. Evaluate non-recursive term */
6282 tgl@sss.pgh.pa.us 92 [ + + ]: 36123 : if (!node->recursing)
93 : : {
94 : : for (;;)
95 : : {
6279 96 : 11552 : slot = ExecProcNode(outerPlan);
97 [ + + + + ]: 11552 : if (TupIsNull(slot))
98 : : break;
99 [ + + ]: 11105 : if (plan->numCols > 0)
100 : : {
101 : : /* Find or build hashtable entry for this tuple's group */
1969 jdavis@postgresql.or 102 : 261 : LookupTupleHashEntry(node->hashtable, slot, &isnew, NULL);
103 : : /* Must reset temp context after each hashtable lookup */
6279 tgl@sss.pgh.pa.us 104 : 261 : MemoryContextReset(node->tempContext);
105 : : /* Ignore tuple if already seen */
106 [ + + ]: 261 : if (!isnew)
107 : 9 : continue;
108 : : }
109 : : /* Each non-duplicate tuple goes to the working table ... */
6282 110 : 11096 : tuplestore_puttupleslot(node->working_table, slot);
111 : : /* ... and to the caller */
112 : 11096 : return slot;
113 : : }
114 : 447 : node->recursing = true;
115 : : }
116 : :
117 : : /* 2. Execute recursive term */
118 : : for (;;)
119 : : {
6279 120 : 28350 : slot = ExecProcNode(innerPlan);
121 [ + + + + ]: 28350 : if (TupIsNull(slot))
122 : 3284 : {
123 : : Tuplestorestate *swaptemp;
124 : :
125 : : /* Done if there's nothing in the intermediate table */
126 [ + + ]: 3710 : if (node->intermediate_empty)
127 : 426 : break;
128 : :
129 : : /*
130 : : * Now we let the intermediate table become the work table. We
131 : : * need a fresh intermediate table, so delete the tuples from the
132 : : * current working table and use that as the new intermediate
133 : : * table. This saves a round of free/malloc from creating a new
134 : : * tuple store.
135 : : */
453 drowley@postgresql.o 136 : 3284 : tuplestore_clear(node->working_table);
137 : :
138 : 3284 : swaptemp = node->working_table;
6279 tgl@sss.pgh.pa.us 139 : 3284 : node->working_table = node->intermediate_table;
453 drowley@postgresql.o 140 : 3284 : node->intermediate_table = swaptemp;
141 : :
142 : : /* mark the intermediate table as empty */
6279 tgl@sss.pgh.pa.us 143 : 3284 : node->intermediate_empty = true;
144 : :
145 : : /* reset the recursive term */
146 : 3284 : innerPlan->chgParam = bms_add_member(innerPlan->chgParam,
147 : : plan->wtParam);
148 : :
149 : : /* and continue fetching from recursive term */
150 : 3284 : continue;
151 : : }
152 : :
153 [ + + ]: 24640 : if (plan->numCols > 0)
154 : : {
155 : : /* Find or build hashtable entry for this tuple's group */
1969 jdavis@postgresql.or 156 : 462 : LookupTupleHashEntry(node->hashtable, slot, &isnew, NULL);
157 : : /* Must reset temp context after each hashtable lookup */
6279 tgl@sss.pgh.pa.us 158 : 462 : MemoryContextReset(node->tempContext);
159 : : /* Ignore tuple if already seen */
160 [ + + ]: 462 : if (!isnew)
161 : 39 : continue;
162 : : }
163 : :
164 : : /* Else, tuple is good; stash it in intermediate table ... */
6032 bruce@momjian.us 165 : 24601 : node->intermediate_empty = false;
166 : 24601 : tuplestore_puttupleslot(node->intermediate_table, slot);
167 : : /* ... and return it */
6279 tgl@sss.pgh.pa.us 168 : 24601 : return slot;
169 : : }
170 : :
171 : 426 : return NULL;
172 : : }
173 : :
174 : : /* ----------------------------------------------------------------
175 : : * ExecInitRecursiveUnion
176 : : * ----------------------------------------------------------------
177 : : */
178 : : RecursiveUnionState *
6282 179 : 471 : ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags)
180 : : {
181 : : RecursiveUnionState *rustate;
182 : : ParamExecData *prmdata;
183 : :
184 : : /* check for unsupported flags */
185 [ - + ]: 471 : Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
186 : :
187 : : /*
188 : : * create state structure
189 : : */
190 : 471 : rustate = makeNode(RecursiveUnionState);
191 : 471 : rustate->ps.plan = (Plan *) node;
192 : 471 : rustate->ps.state = estate;
3074 andres@anarazel.de 193 : 471 : rustate->ps.ExecProcNode = ExecRecursiveUnion;
194 : :
2861 195 : 471 : rustate->eqfuncoids = NULL;
6279 tgl@sss.pgh.pa.us 196 : 471 : rustate->hashfunctions = NULL;
197 : 471 : rustate->hashtable = NULL;
198 : 471 : rustate->tempContext = NULL;
47 tgl@sss.pgh.pa.us 199 :GNC 471 : rustate->tuplesContext = NULL;
200 : :
201 : : /* initialize processing state */
6282 tgl@sss.pgh.pa.us 202 :CBC 471 : rustate->recursing = false;
203 : 471 : rustate->intermediate_empty = true;
204 : 471 : rustate->working_table = tuplestore_begin_heap(false, false, work_mem);
205 : 471 : rustate->intermediate_table = tuplestore_begin_heap(false, false, work_mem);
206 : :
207 : : /*
208 : : * If hashing, we need a per-tuple memory context for comparisons, and a
209 : : * longer-lived context to store the hash table. The table can't just be
210 : : * kept in the per-query context because we want to be able to throw it
211 : : * away when rescanning. We can use a BumpContext to save storage,
212 : : * because we will have no need to delete individual table entries.
213 : : */
6279 214 [ + + ]: 471 : if (node->numCols > 0)
215 : : {
216 : 193 : rustate->tempContext =
217 : 193 : AllocSetContextCreate(CurrentMemoryContext,
218 : : "RecursiveUnion",
219 : : ALLOCSET_DEFAULT_SIZES);
47 tgl@sss.pgh.pa.us 220 :GNC 193 : rustate->tuplesContext =
221 : 193 : BumpContextCreate(CurrentMemoryContext,
222 : : "RecursiveUnion hashed tuples",
223 : : ALLOCSET_DEFAULT_SIZES);
224 : : }
225 : :
226 : : /*
227 : : * Make the state structure available to descendant WorkTableScan nodes
228 : : * via the Param slot reserved for it.
229 : : */
6282 tgl@sss.pgh.pa.us 230 :CBC 471 : prmdata = &(estate->es_param_exec_vals[node->wtParam]);
231 [ - + ]: 471 : Assert(prmdata->execPlan == NULL);
232 : 471 : prmdata->value = PointerGetDatum(rustate);
233 : 471 : prmdata->isnull = false;
234 : :
235 : : /*
236 : : * Miscellaneous initialization
237 : : *
238 : : * RecursiveUnion plans don't have expression contexts because they never
239 : : * call ExecQual or ExecProject.
240 : : */
241 [ - + ]: 471 : Assert(node->plan.qual == NIL);
242 : :
243 : : /*
244 : : * RecursiveUnion nodes still have Result slots, which hold pointers to
245 : : * tuples, so we have to initialize them.
246 : : */
2594 andres@anarazel.de 247 : 471 : ExecInitResultTypeTL(&rustate->ps);
248 : :
249 : : /*
250 : : * Initialize result tuple type. (Note: we have to set up the result type
251 : : * before initializing child nodes, because nodeWorktablescan.c expects it
252 : : * to be valid.)
253 : : */
6282 tgl@sss.pgh.pa.us 254 : 471 : rustate->ps.ps_ProjInfo = NULL;
255 : :
256 : : /*
257 : : * initialize child nodes
258 : : */
259 : 471 : outerPlanState(rustate) = ExecInitNode(outerPlan(node), estate, eflags);
260 : 471 : innerPlanState(rustate) = ExecInitNode(innerPlan(node), estate, eflags);
261 : :
262 : : /*
263 : : * If hashing, precompute fmgr lookup data for inner loop, and create the
264 : : * hash table.
265 : : */
6279 266 [ + + ]: 471 : if (node->numCols > 0)
267 : : {
268 : 193 : execTuplesHashPrepare(node->numCols,
269 : 193 : node->dupOperators,
270 : : &rustate->eqfuncoids,
271 : : &rustate->hashfunctions);
272 : 193 : build_hash_table(rustate);
273 : : }
274 : :
6282 275 : 471 : return rustate;
276 : : }
277 : :
278 : : /* ----------------------------------------------------------------
279 : : * ExecEndRecursiveUnion
280 : : *
281 : : * frees any storage allocated through C routines.
282 : : * ----------------------------------------------------------------
283 : : */
284 : : void
285 : 471 : ExecEndRecursiveUnion(RecursiveUnionState *node)
286 : : {
287 : : /* Release tuplestores */
288 : 471 : tuplestore_end(node->working_table);
289 : 471 : tuplestore_end(node->intermediate_table);
290 : :
291 : : /* free subsidiary stuff including hashtable data */
6279 292 [ + + ]: 471 : if (node->tempContext)
293 : 193 : MemoryContextDelete(node->tempContext);
47 tgl@sss.pgh.pa.us 294 [ + + ]:GNC 471 : if (node->tuplesContext)
295 : 193 : MemoryContextDelete(node->tuplesContext);
296 : :
297 : : /*
298 : : * close down subplans
299 : : */
6282 tgl@sss.pgh.pa.us 300 :CBC 471 : ExecEndNode(outerPlanState(node));
301 : 471 : ExecEndNode(innerPlanState(node));
302 : 471 : }
303 : :
304 : : /* ----------------------------------------------------------------
305 : : * ExecReScanRecursiveUnion
306 : : *
307 : : * Rescans the relation.
308 : : * ----------------------------------------------------------------
309 : : */
310 : : void
5636 311 : 6 : ExecReScanRecursiveUnion(RecursiveUnionState *node)
312 : : {
6282 313 : 6 : PlanState *outerPlan = outerPlanState(node);
314 : 6 : PlanState *innerPlan = innerPlanState(node);
315 : 6 : RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan;
316 : :
317 : : /*
318 : : * Set recursive term's chgParam to tell it that we'll modify the working
319 : : * table and therefore it has to rescan.
320 : : */
321 : 6 : innerPlan->chgParam = bms_add_member(innerPlan->chgParam, plan->wtParam);
322 : :
323 : : /*
324 : : * if chgParam of subnode is not null then plan will be re-scanned by
325 : : * first ExecProcNode. Because of above, we only have to do this to the
326 : : * non-recursive term.
327 : : */
328 [ - + ]: 6 : if (outerPlan->chgParam == NULL)
5636 tgl@sss.pgh.pa.us 329 :UBC 0 : ExecReScan(outerPlan);
330 : :
331 : : /* Empty hashtable if needed */
6279 tgl@sss.pgh.pa.us 332 [ + - ]:CBC 6 : if (plan->numCols > 0)
2502 andres@anarazel.de 333 : 6 : ResetTupleHashTable(node->hashtable);
334 : :
335 : : /* reset processing state */
6282 tgl@sss.pgh.pa.us 336 : 6 : node->recursing = false;
337 : 6 : node->intermediate_empty = true;
338 : 6 : tuplestore_clear(node->working_table);
339 : 6 : tuplestore_clear(node->intermediate_table);
340 : 6 : }
|
