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-2014, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/executor/nodeSort.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "executor/execdebug.h"
  19 #include "executor/nodeSort.h"
  20 #include "miscadmin.h"
  21 #include "utils/tuplesort.h"
  22
  23
  24 /* ----------------------------------------------------------------
  25  *              ExecSort
  26  *
  27  *              Sorts tuples from the outer subtree of the node using tuplesort,
  28  *              which saves the results in a temporary file or memory. After the
  29  *              initial call, returns a tuple from the file with each call.
  30  *
  31  *              Conditions:
  32  *                -- none.
  33  *
  34  *              Initial States:
  35  *                -- the outer child is prepared to return the first tuple.
  36  * ----------------------------------------------------------------
  37  */
  38 TupleTableSlot *
  39 ExecSort(SortState *node)
  40 {
  41         EState     *estate;
  42         ScanDirection dir;
  43         Tuplesortstate *tuplesortstate;
  44         TupleTableSlot *slot;
  45
  46         /*
  47          * get state info from node
  48          */
  49         SO1_printf("ExecSort: %s\n",
  50                            "entering routine");
  51
  52         estate = node->ss.ps.state;
  53         dir = estate->es_direction;
  54         tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
  55
  56         /*
  57          * If first time through, read all tuples from outer plan and pass them to
  58          * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
  59          */
  60
  61         if (!node->sort_Done)
  62         {
  63                 Sort       *plannode = (Sort *) node->ss.ps.plan;
  64                 PlanState  *outerNode;
  65                 TupleDesc       tupDesc;
  66
  67                 SO1_printf("ExecSort: %s\n",
  68                                    "sorting subplan");
  69
  70                 /*
  71                  * Want to scan subplan in the forward direction while creating the
  72                  * sorted data.
  73                  */
  74                 estate->es_direction = ForwardScanDirection;
  75
  76                 /*
  77                  * Initialize tuplesort module.
  78                  */
  79                 SO1_printf("ExecSort: %s\n",
  80                                    "calling tuplesort_begin");
  81
  82                 outerNode = outerPlanState(node);
  83                 tupDesc = ExecGetResultType(outerNode);
  84
  85                 tuplesortstate = tuplesort_begin_heap(tupDesc,
  86                                                                                           plannode->numCols,
  87                                                                                           plannode->sortColIdx,
  88                                                                                           plannode->sortOperators,
  89                                                                                           plannode->collations,
  90                                                                                           plannode->nullsFirst,
  91                                                                                           work_mem,
  92                                                                                           node->randomAccess);
  93                 if (node->bounded)
  94                         tuplesort_set_bound(tuplesortstate, node->bound);
  95                 node->tuplesortstate = (void *) tuplesortstate;
  96
  97                 /*
  98                  * Scan the subplan and feed all the tuples to tuplesort.
  99                  */
 100
 101                 for (;;)
 102                 {
 103                         slot = ExecProcNode(outerNode);
 104
 105                         if (TupIsNull(slot))
 106                                 break;
 107
 108                         tuplesort_puttupleslot(tuplesortstate, slot);
 109                 }
 110
 111                 /*
 112                  * Complete the sort.
 113                  */
 114                 tuplesort_performsort(tuplesortstate);
 115
 116                 /*
 117                  * restore to user specified direction
 118                  */
 119                 estate->es_direction = dir;
 120
 121                 /*
 122                  * finally set the sorted flag to true
 123                  */
 124                 node->sort_Done = true;
 125                 node->bounded_Done = node->bounded;
 126                 node->bound_Done = node->bound;
 127                 SO1_printf("ExecSort: %s\n", "sorting done");
 128         }
 129
 130         SO1_printf("ExecSort: %s\n",
 131                            "retrieving tuple from tuplesort");
 132
 133         /*
 134          * Get the first or next tuple from tuplesort. Returns NULL if no more
 135          * tuples.
 136          */
 137         slot = node->ss.ps.ps_ResultTupleSlot;
 138         (void) tuplesort_gettupleslot(tuplesortstate,
 139                                                                   ScanDirectionIsForward(dir),
 140                                                                   slot);
 141         return slot;
 142 }
 143
 144 /* ----------------------------------------------------------------
 145  *              ExecInitSort
 146  *
 147  *              Creates the run-time state information for the sort node
 148  *              produced by the planner and initializes its outer subtree.
 149  * ----------------------------------------------------------------
 150  */
 151 SortState *
 152 ExecInitSort(Sort *node, EState *estate, int eflags)
 153 {
 154         SortState  *sortstate;
 155
 156         SO1_printf("ExecInitSort: %s\n",
 157                            "initializing sort node");
 158
 159         /*
 160          * create state structure
 161          */
 162         sortstate = makeNode(SortState);
 163         sortstate->ss.ps.plan = (Plan *) node;
 164         sortstate->ss.ps.state = estate;
 165
 166         /*
 167          * We must have random access to the sort output to do backward scan or
 168          * mark/restore.  We also prefer to materialize the sort output if we
 169          * might be called on to rewind and replay it many times.
 170          */
 171         sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
 172                                                                                  EXEC_FLAG_BACKWARD |
 173                                                                                  EXEC_FLAG_MARK)) != 0;
 174
 175         sortstate->bounded = false;
 176         sortstate->sort_Done = false;
 177         sortstate->tuplesortstate = NULL;
 178
 179         /*
 180          * Miscellaneous initialization
 181          *
 182          * Sort nodes don't initialize their ExprContexts because they never call
 183          * ExecQual or ExecProject.
 184          */
 185
 186         /*
 187          * tuple table initialization
 188          *
 189          * sort nodes only return scan tuples from their sorted relation.
 190          */
 191         ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
 192         ExecInitScanTupleSlot(estate, &sortstate->ss);
 193
 194         /*
 195          * initialize child nodes
 196          *
 197          * We shield the child node from the need to support REWIND, BACKWARD, or
 198          * MARK/RESTORE.
 199          */
 200         eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
 201
 202         outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
 203
 204         /*
 205          * initialize tuple type.  no need to initialize projection info because
 206          * this node doesn't do projections.
 207          */
 208         ExecAssignResultTypeFromTL(&sortstate->ss.ps);
 209         ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
 210         sortstate->ss.ps.ps_ProjInfo = NULL;
 211
 212         SO1_printf("ExecInitSort: %s\n",
 213                            "sort node initialized");
 214
 215         return sortstate;
 216 }
 217
 218 /* ----------------------------------------------------------------
 219  *              ExecEndSort(node)
 220  * ----------------------------------------------------------------
 221  */
 222 void
 223 ExecEndSort(SortState *node)
 224 {
 225         SO1_printf("ExecEndSort: %s\n",
 226                            "shutting down sort node");
 227
 228         /*
 229          * clean out the tuple table
 230          */
 231         ExecClearTuple(node->ss.ss_ScanTupleSlot);
 232         /* must drop pointer to sort result tuple */
 233         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 234
 235         /*
 236          * Release tuplesort resources
 237          */
 238         if (node->tuplesortstate != NULL)
 239                 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
 240         node->tuplesortstate = NULL;
 241
 242         /*
 243          * shut down the subplan
 244          */
 245         ExecEndNode(outerPlanState(node));
 246
 247         SO1_printf("ExecEndSort: %s\n",
 248                            "sort node shutdown");
 249 }
 250
 251 /* ----------------------------------------------------------------
 252  *              ExecSortMarkPos
 253  *
 254  *              Calls tuplesort to save the current position in the sorted file.
 255  * ----------------------------------------------------------------
 256  */
 257 void
 258 ExecSortMarkPos(SortState *node)
 259 {
 260         /*
 261          * if we haven't sorted yet, just return
 262          */
 263         if (!node->sort_Done)
 264                 return;
 265
 266         tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
 267 }
 268
 269 /* ----------------------------------------------------------------
 270  *              ExecSortRestrPos
 271  *
 272  *              Calls tuplesort to restore the last saved sort file position.
 273  * ----------------------------------------------------------------
 274  */
 275 void
 276 ExecSortRestrPos(SortState *node)
 277 {
 278         /*
 279          * if we haven't sorted yet, just return.
 280          */
 281         if (!node->sort_Done)
 282                 return;
 283
 284         /*
 285          * restore the scan to the previously marked position
 286          */
 287         tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
 288 }
 289
 290 void
 291 ExecReScanSort(SortState *node)
 292 {
 293         /*
 294          * If we haven't sorted yet, just return. If outerplan's chgParam is not
 295          * NULL then it will be re-scanned by ExecProcNode, else no reason to
 296          * re-scan it at all.
 297          */
 298         if (!node->sort_Done)
 299                 return;
 300
 301         /* must drop pointer to sort result tuple */
 302         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 303
 304         /*
 305          * If subnode is to be rescanned then we forget previous sort results; we
 306          * have to re-read the subplan and re-sort.  Also must re-sort if the
 307          * bounded-sort parameters changed or we didn't select randomAccess.
 308          *
 309          * Otherwise we can just rewind and rescan the sorted output.
 310          */
 311         if (node->ss.ps.lefttree->chgParam != NULL ||
 312                 node->bounded != node->bounded_Done ||
 313                 node->bound != node->bound_Done ||
 314                 !node->randomAccess)
 315         {
 316                 node->sort_Done = false;
 317                 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
 318                 node->tuplesortstate = NULL;
 319
 320                 /*
 321                  * if chgParam of subnode is not null then plan will be re-scanned by
 322                  * first ExecProcNode.
 323                  */
 324                 if (node->ss.ps.lefttree->chgParam == NULL)
 325                         ExecReScan(node->ss.ps.lefttree);
 326         }
 327         else
 328                 tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
 329 }