granicus.if.org Git - postgresql/blob - src/backend/executor/nodeRecursiveunion.c

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