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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeSort.c
   4  *        Routines to handle sorting of relations.
   5  *
   6  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/executor/nodeSort.c,v 1.43 2003/05/05 17:57:47 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "executor/execdebug.h"
  19 #include "executor/nodeSort.h"
  20 #include "utils/tuplesort.h"
  21
  22 /* ----------------------------------------------------------------
  23  *              ExtractSortKeys
  24  *
  25  *              Extract the sorting key information from the plan node.
  26  *
  27  *              Returns two palloc'd arrays, one of sort operator OIDs and
  28  *              one of attribute numbers.
  29  * ----------------------------------------------------------------
  30  */
  31 static void
  32 ExtractSortKeys(Sort *sortnode,
  33                                 Oid **sortOperators,
  34                                 AttrNumber **attNums)
  35 {
  36         List       *targetList;
  37         int                     keycount;
  38         Oid                *sortOps;
  39         AttrNumber *attNos;
  40         List       *tl;
  41
  42         /*
  43          * get information from the node
  44          */
  45         targetList = sortnode->plan.targetlist;
  46         keycount = sortnode->keycount;
  47
  48         /*
  49          * first allocate space for results
  50          */
  51         if (keycount <= 0)
  52                 elog(ERROR, "ExtractSortKeys: keycount <= 0");
  53         sortOps = (Oid *) palloc0(keycount * sizeof(Oid));
  54         *sortOperators = sortOps;
  55         attNos = (AttrNumber *) palloc0(keycount * sizeof(AttrNumber));
  56         *attNums = attNos;
  57
  58         /*
  59          * extract info from the resdom nodes in the target list
  60          */
  61         foreach(tl, targetList)
  62         {
  63                 TargetEntry *target = (TargetEntry *) lfirst(tl);
  64                 Resdom     *resdom = target->resdom;
  65                 Index           reskey = resdom->reskey;
  66
  67                 if (reskey > 0)                 /* ignore TLEs that are not sort keys */
  68                 {
  69                         Assert(reskey <= keycount);
  70                         sortOps[reskey - 1] = resdom->reskeyop;
  71                         attNos[reskey - 1] = resdom->resno;
  72                 }
  73         }
  74 }
  75
  76 /* ----------------------------------------------------------------
  77  *              ExecSort
  78  *
  79  *              Sorts tuples from the outer subtree of the node using tuplesort,
  80  *              which saves the results in a temporary file or memory. After the
  81  *              initial call, returns a tuple from the file with each call.
  82  *
  83  *              Conditions:
  84  *                -- none.
  85  *
  86  *              Initial States:
  87  *                -- the outer child is prepared to return the first tuple.
  88  * ----------------------------------------------------------------
  89  */
  90 TupleTableSlot *
  91 ExecSort(SortState *node)
  92 {
  93         EState     *estate;
  94         ScanDirection dir;
  95         Tuplesortstate *tuplesortstate;
  96         HeapTuple       heapTuple;
  97         TupleTableSlot *slot;
  98         bool            should_free;
  99
 100         /*
 101          * get state info from node
 102          */
 103         SO1_printf("ExecSort: %s\n",
 104                            "entering routine");
 105
 106         estate = node->ss.ps.state;
 107         dir = estate->es_direction;
 108         tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
 109
 110         /*
 111          * If first time through, read all tuples from outer plan and pass
 112          * them to tuplesort.c. Subsequent calls just fetch tuples from
 113          * tuplesort.
 114          */
 115
 116         if (!node->sort_Done)
 117         {
 118                 Sort       *plannode = (Sort *) node->ss.ps.plan;
 119                 PlanState  *outerNode;
 120                 TupleDesc       tupDesc;
 121                 Oid                *sortOperators;
 122                 AttrNumber *attNums;
 123
 124                 SO1_printf("ExecSort: %s\n",
 125                                    "sorting subplan");
 126
 127                 /*
 128                  * Want to scan subplan in the forward direction while creating
 129                  * the sorted data.
 130                  */
 131                 estate->es_direction = ForwardScanDirection;
 132
 133                 /*
 134                  * Initialize tuplesort module.
 135                  */
 136                 SO1_printf("ExecSort: %s\n",
 137                                    "calling tuplesort_begin");
 138
 139                 outerNode = outerPlanState(node);
 140                 tupDesc = ExecGetResultType(outerNode);
 141
 142                 ExtractSortKeys(plannode, &sortOperators, &attNums);
 143
 144                 tuplesortstate = tuplesort_begin_heap(tupDesc, plannode->keycount,
 145                                                                                           sortOperators, attNums,
 146                                                                                           true /* randomAccess */ );
 147                 node->tuplesortstate = (void *) tuplesortstate;
 148
 149                 pfree(sortOperators);
 150                 pfree(attNums);
 151
 152                 /*
 153                  * Scan the subplan and feed all the tuples to tuplesort.
 154                  */
 155
 156                 for (;;)
 157                 {
 158                         slot = ExecProcNode(outerNode);
 159
 160                         if (TupIsNull(slot))
 161                                 break;
 162
 163                         tuplesort_puttuple(tuplesortstate, (void *) slot->val);
 164                 }
 165
 166                 /*
 167                  * Complete the sort.
 168                  */
 169                 tuplesort_performsort(tuplesortstate);
 170
 171                 /*
 172                  * restore to user specified direction
 173                  */
 174                 estate->es_direction = dir;
 175
 176                 /*
 177                  * finally set the sorted flag to true
 178                  */
 179                 node->sort_Done = true;
 180                 SO1_printf("ExecSort: %s\n", "sorting done");
 181         }
 182
 183         SO1_printf("ExecSort: %s\n",
 184                            "retrieving tuple from tuplesort");
 185
 186         /*
 187          * Get the first or next tuple from tuplesort. Returns NULL if no more
 188          * tuples.
 189          */
 190         heapTuple = tuplesort_getheaptuple(tuplesortstate,
 191                                                                            ScanDirectionIsForward(dir),
 192                                                                            &should_free);
 193
 194         slot = node->ss.ps.ps_ResultTupleSlot;
 195         return ExecStoreTuple(heapTuple, slot, InvalidBuffer, should_free);
 196 }
 197
 198 /* ----------------------------------------------------------------
 199  *              ExecInitSort
 200  *
 201  *              Creates the run-time state information for the sort node
 202  *              produced by the planner and initailizes its outer subtree.
 203  * ----------------------------------------------------------------
 204  */
 205 SortState *
 206 ExecInitSort(Sort *node, EState *estate)
 207 {
 208         SortState  *sortstate;
 209
 210         SO1_printf("ExecInitSort: %s\n",
 211                            "initializing sort node");
 212
 213         /*
 214          * create state structure
 215          */
 216         sortstate = makeNode(SortState);
 217         sortstate->ss.ps.plan = (Plan *) node;
 218         sortstate->ss.ps.state = estate;
 219
 220         sortstate->sort_Done = false;
 221         sortstate->tuplesortstate = NULL;
 222
 223         /*
 224          * Miscellaneous initialization
 225          *
 226          * Sort nodes don't initialize their ExprContexts because they never call
 227          * ExecQual or ExecProject.
 228          */
 229
 230 #define SORT_NSLOTS 2
 231
 232         /*
 233          * tuple table initialization
 234          *
 235          * sort nodes only return scan tuples from their sorted relation.
 236          */
 237         ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
 238         ExecInitScanTupleSlot(estate, &sortstate->ss);
 239
 240         /*
 241          * initializes child nodes
 242          */
 243         outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate);
 244
 245         /*
 246          * initialize tuple type.  no need to initialize projection info
 247          * because this node doesn't do projections.
 248          */
 249         ExecAssignResultTypeFromOuterPlan(&sortstate->ss.ps);
 250         ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
 251         sortstate->ss.ps.ps_ProjInfo = NULL;
 252
 253         SO1_printf("ExecInitSort: %s\n",
 254                            "sort node initialized");
 255
 256         return sortstate;
 257 }
 258
 259 int
 260 ExecCountSlotsSort(Sort *node)
 261 {
 262         return ExecCountSlotsNode(outerPlan((Plan *) node)) +
 263                 ExecCountSlotsNode(innerPlan((Plan *) node)) +
 264                 SORT_NSLOTS;
 265 }
 266
 267 /* ----------------------------------------------------------------
 268  *              ExecEndSort(node)
 269  * ----------------------------------------------------------------
 270  */
 271 void
 272 ExecEndSort(SortState *node)
 273 {
 274         SO1_printf("ExecEndSort: %s\n",
 275                            "shutting down sort node");
 276
 277         /*
 278          * clean out the tuple table
 279          */
 280         ExecClearTuple(node->ss.ss_ScanTupleSlot);
 281
 282         /*
 283          * Release tuplesort resources
 284          */
 285         if (node->tuplesortstate != NULL)
 286                 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
 287         node->tuplesortstate = NULL;
 288
 289         /*
 290          * shut down the subplan
 291          */
 292         ExecEndNode(outerPlanState(node));
 293
 294         SO1_printf("ExecEndSort: %s\n",
 295                            "sort node shutdown");
 296 }
 297
 298 /* ----------------------------------------------------------------
 299  *              ExecSortMarkPos
 300  *
 301  *              Calls tuplesort to save the current position in the sorted file.
 302  * ----------------------------------------------------------------
 303  */
 304 void
 305 ExecSortMarkPos(SortState *node)
 306 {
 307         /*
 308          * if we haven't sorted yet, just return
 309          */
 310         if (!node->sort_Done)
 311                 return;
 312
 313         tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
 314 }
 315
 316 /* ----------------------------------------------------------------
 317  *              ExecSortRestrPos
 318  *
 319  *              Calls tuplesort to restore the last saved sort file position.
 320  * ----------------------------------------------------------------
 321  */
 322 void
 323 ExecSortRestrPos(SortState *node)
 324 {
 325         /*
 326          * if we haven't sorted yet, just return.
 327          */
 328         if (!node->sort_Done)
 329                 return;
 330
 331         /*
 332          * restore the scan to the previously marked position
 333          */
 334         tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
 335 }
 336
 337 void
 338 ExecReScanSort(SortState *node, ExprContext *exprCtxt)
 339 {
 340         /*
 341          * If we haven't sorted yet, just return. If outerplan' chgParam is
 342          * not NULL then it will be re-scanned by ExecProcNode, else - no
 343          * reason to re-scan it at all.
 344          */
 345         if (!node->sort_Done)
 346                 return;
 347
 348         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 349
 350         /*
 351          * If subnode is to be rescanned then we forget previous sort results;
 352          * we have to re-read the subplan and re-sort.
 353          *
 354          * Otherwise we can just rewind and rescan the sorted output.
 355          */
 356         if (((PlanState *) node)->lefttree->chgParam != NULL)
 357         {
 358                 node->sort_Done = false;
 359                 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
 360                 node->tuplesortstate = NULL;
 361         }
 362         else
 363                 tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
 364 }