LCOV - code coverage report
Current view: top level - src/backend/executor - nodeRecursiveunion.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 99 100 99.0 %
Date: 2024-02-28 06:10:54 Functions: 5 5 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14