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