src/backend/executor/nodeSort.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeSort.c
   4  *        Routines to handle sorting of relations.
   5  *
   6  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL$
  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->nullsFirst,
  90                                                                                           work_mem,
  91                                                                                           node->randomAccess);
  92                 if (node->bounded)
  93                         tuplesort_set_bound(tuplesortstate, node->bound);
  94                 node->tuplesortstate = (void *) tuplesortstate;
  95
  96                 /*
  97                  * Scan the subplan and feed all the tuples to tuplesort.
  98                  */
  99
 100                 for (;;)
 101                 {
 102                         slot = ExecProcNode(outerNode);
 103
 104                         if (TupIsNull(slot))
 105                                 break;
 106
 107                         tuplesort_puttupleslot(tuplesortstate, slot);
 108                 }
 109
 110                 /*
 111                  * Complete the sort.
 112                  */
 113                 tuplesort_performsort(tuplesortstate);
 114
 115                 /*
 116                  * restore to user specified direction
 117                  */
 118                 estate->es_direction = dir;
 119
 120                 /*
 121                  * finally set the sorted flag to true
 122                  */
 123                 node->sort_Done = true;
 124                 node->bounded_Done = node->bounded;
 125                 node->bound_Done = node->bound;
 126                 SO1_printf("ExecSort: %s\n", "sorting done");
 127         }
 128
 129         SO1_printf("ExecSort: %s\n",
 130                            "retrieving tuple from tuplesort");
 131
 132         /*
 133          * Get the first or next tuple from tuplesort. Returns NULL if no more
 134          * tuples.
 135          */
 136         slot = node->ss.ps.ps_ResultTupleSlot;
 137         (void) tuplesort_gettupleslot(tuplesortstate,
 138                                                                   ScanDirectionIsForward(dir),
 139                                                                   slot);
 140         return slot;
 141 }
 142
 143 /* ----------------------------------------------------------------
 144  *              ExecInitSort
 145  *
 146  *              Creates the run-time state information for the sort node
 147  *              produced by the planner and initializes its outer subtree.
 148  * ----------------------------------------------------------------
 149  */
 150 SortState *
 151 ExecInitSort(Sort *node, EState *estate, int eflags)
 152 {
 153         SortState  *sortstate;
 154
 155         SO1_printf("ExecInitSort: %s\n",
 156                            "initializing sort node");
 157
 158         /*
 159          * create state structure
 160          */
 161         sortstate = makeNode(SortState);
 162         sortstate->ss.ps.plan = (Plan *) node;
 163         sortstate->ss.ps.state = estate;
 164
 165         /*
 166          * We must have random access to the sort output to do backward scan or
 167          * mark/restore.  We also prefer to materialize the sort output if we
 168          * might be called on to rewind and replay it many times.
 169          */
 170         sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
 171                                                                                  EXEC_FLAG_BACKWARD |
 172                                                                                  EXEC_FLAG_MARK)) != 0;
 173
 174         sortstate->bounded = false;
 175         sortstate->sort_Done = false;
 176         sortstate->tuplesortstate = NULL;
 177
 178         /*
 179          * Miscellaneous initialization
 180          *
 181          * Sort nodes don't initialize their ExprContexts because they never call
 182          * ExecQual or ExecProject.
 183          */
 184
 185 #define SORT_NSLOTS 2
 186
 187         /*
 188          * tuple table initialization
 189          *
 190          * sort nodes only return scan tuples from their sorted relation.
 191          */
 192         ExecInitResultTupleSlot(estate, &sortstate->ss.ps);
 193         ExecInitScanTupleSlot(estate, &sortstate->ss);
 194
 195         /*
 196          * initialize child nodes
 197          *
 198          * We shield the child node from the need to support REWIND, BACKWARD, or
 199          * MARK/RESTORE.
 200          */
 201         eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
 202
 203         outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
 204
 205         /*
 206          * initialize tuple type.  no need to initialize projection info because
 207          * this node doesn't do projections.
 208          */
 209         ExecAssignResultTypeFromTL(&sortstate->ss.ps);
 210         ExecAssignScanTypeFromOuterPlan(&sortstate->ss);
 211         sortstate->ss.ps.ps_ProjInfo = NULL;
 212
 213         SO1_printf("ExecInitSort: %s\n",
 214                            "sort node initialized");
 215
 216         return sortstate;
 217 }
 218
 219 int
 220 ExecCountSlotsSort(Sort *node)
 221 {
 222         return ExecCountSlotsNode(outerPlan((Plan *) node)) +
 223                 ExecCountSlotsNode(innerPlan((Plan *) node)) +
 224                 SORT_NSLOTS;
 225 }
 226
 227 /* ----------------------------------------------------------------
 228  *              ExecEndSort(node)
 229  * ----------------------------------------------------------------
 230  */
 231 void
 232 ExecEndSort(SortState *node)
 233 {
 234         SO1_printf("ExecEndSort: %s\n",
 235                            "shutting down sort node");
 236
 237         /*
 238          * clean out the tuple table
 239          */
 240         ExecClearTuple(node->ss.ss_ScanTupleSlot);
 241         /* must drop pointer to sort result tuple */
 242         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 243
 244         /*
 245          * Release tuplesort resources
 246          */
 247         if (node->tuplesortstate != NULL)
 248                 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
 249         node->tuplesortstate = NULL;
 250
 251         /*
 252          * shut down the subplan
 253          */
 254         ExecEndNode(outerPlanState(node));
 255
 256         SO1_printf("ExecEndSort: %s\n",
 257                            "sort node shutdown");
 258 }
 259
 260 /* ----------------------------------------------------------------
 261  *              ExecSortMarkPos
 262  *
 263  *              Calls tuplesort to save the current position in the sorted file.
 264  * ----------------------------------------------------------------
 265  */
 266 void
 267 ExecSortMarkPos(SortState *node)
 268 {
 269         /*
 270          * if we haven't sorted yet, just return
 271          */
 272         if (!node->sort_Done)
 273                 return;
 274
 275         tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
 276 }
 277
 278 /* ----------------------------------------------------------------
 279  *              ExecSortRestrPos
 280  *
 281  *              Calls tuplesort to restore the last saved sort file position.
 282  * ----------------------------------------------------------------
 283  */
 284 void
 285 ExecSortRestrPos(SortState *node)
 286 {
 287         /*
 288          * if we haven't sorted yet, just return.
 289          */
 290         if (!node->sort_Done)
 291                 return;
 292
 293         /*
 294          * restore the scan to the previously marked position
 295          */
 296         tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
 297 }
 298
 299 void
 300 ExecReScanSort(SortState *node, ExprContext *exprCtxt)
 301 {
 302         /*
 303          * If we haven't sorted yet, just return. If outerplan' chgParam is not
 304          * NULL then it will be re-scanned by ExecProcNode, else - no reason to
 305          * re-scan it at all.
 306          */
 307         if (!node->sort_Done)
 308                 return;
 309
 310         /* must drop pointer to sort result tuple */
 311         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 312
 313         /*
 314          * If subnode is to be rescanned then we forget previous sort results; we
 315          * have to re-read the subplan and re-sort.  Also must re-sort if the
 316          * bounded-sort parameters changed or we didn't select randomAccess.
 317          *
 318          * Otherwise we can just rewind and rescan the sorted output.
 319          */
 320         if (((PlanState *) node)->lefttree->chgParam != NULL ||
 321                 node->bounded != node->bounded_Done ||
 322                 node->bound != node->bound_Done ||
 323                 !node->randomAccess)
 324         {
 325                 node->sort_Done = false;
 326                 tuplesort_end((Tuplesortstate *) node->tuplesortstate);
 327                 node->tuplesortstate = NULL;
 328
 329                 /*
 330                  * if chgParam of subnode is not null then plan will be re-scanned by
 331                  * first ExecProcNode.
 332                  */
 333                 if (((PlanState *) node)->lefttree->chgParam == NULL)
 334                         ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
 335         }
 336         else
 337                 tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
 338 }