LCOV - code coverage report
Current view: top level - src/backend/executor - nodeSort.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 104 107 97.2 %
Date: 2020-06-05 19:06:29 Functions: 10 10 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * nodeSort.c
       4             :  *    Routines to handle sorting of relations.
       5             :  *
       6             :  * Portions Copyright (c) 1996-2020, 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 "access/parallel.h"
      19             : #include "executor/execdebug.h"
      20             : #include "executor/nodeSort.h"
      21             : #include "miscadmin.h"
      22             : #include "utils/tuplesort.h"
      23             : 
      24             : 
      25             : /* ----------------------------------------------------------------
      26             :  *      ExecSort
      27             :  *
      28             :  *      Sorts tuples from the outer subtree of the node using tuplesort,
      29             :  *      which saves the results in a temporary file or memory. After the
      30             :  *      initial call, returns a tuple from the file with each call.
      31             :  *
      32             :  *      Conditions:
      33             :  *        -- none.
      34             :  *
      35             :  *      Initial States:
      36             :  *        -- the outer child is prepared to return the first tuple.
      37             :  * ----------------------------------------------------------------
      38             :  */
      39             : static TupleTableSlot *
      40     6150624 : ExecSort(PlanState *pstate)
      41             : {
      42     6150624 :     SortState  *node = castNode(SortState, pstate);
      43             :     EState     *estate;
      44             :     ScanDirection dir;
      45             :     Tuplesortstate *tuplesortstate;
      46             :     TupleTableSlot *slot;
      47             : 
      48     6150624 :     CHECK_FOR_INTERRUPTS();
      49             : 
      50             :     /*
      51             :      * get state info from node
      52             :      */
      53             :     SO1_printf("ExecSort: %s\n",
      54             :                "entering routine");
      55             : 
      56     6150624 :     estate = node->ss.ps.state;
      57     6150624 :     dir = estate->es_direction;
      58     6150624 :     tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
      59             : 
      60             :     /*
      61             :      * If first time through, read all tuples from outer plan and pass them to
      62             :      * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
      63             :      */
      64             : 
      65     6150624 :     if (!node->sort_Done)
      66             :     {
      67       46960 :         Sort       *plannode = (Sort *) node->ss.ps.plan;
      68             :         PlanState  *outerNode;
      69             :         TupleDesc   tupDesc;
      70             : 
      71             :         SO1_printf("ExecSort: %s\n",
      72             :                    "sorting subplan");
      73             : 
      74             :         /*
      75             :          * Want to scan subplan in the forward direction while creating the
      76             :          * sorted data.
      77             :          */
      78       46960 :         estate->es_direction = ForwardScanDirection;
      79             : 
      80             :         /*
      81             :          * Initialize tuplesort module.
      82             :          */
      83             :         SO1_printf("ExecSort: %s\n",
      84             :                    "calling tuplesort_begin");
      85             : 
      86       46960 :         outerNode = outerPlanState(node);
      87       46960 :         tupDesc = ExecGetResultType(outerNode);
      88             : 
      89       46960 :         tuplesortstate = tuplesort_begin_heap(tupDesc,
      90             :                                               plannode->numCols,
      91             :                                               plannode->sortColIdx,
      92             :                                               plannode->sortOperators,
      93             :                                               plannode->collations,
      94             :                                               plannode->nullsFirst,
      95             :                                               work_mem,
      96             :                                               NULL,
      97       46960 :                                               node->randomAccess);
      98       46956 :         if (node->bounded)
      99         974 :             tuplesort_set_bound(tuplesortstate, node->bound);
     100       46956 :         node->tuplesortstate = (void *) tuplesortstate;
     101             : 
     102             :         /*
     103             :          * Scan the subplan and feed all the tuples to tuplesort.
     104             :          */
     105             : 
     106             :         for (;;)
     107             :         {
     108     7405520 :             slot = ExecProcNode(outerNode);
     109             : 
     110     7405512 :             if (TupIsNull(slot))
     111             :                 break;
     112             : 
     113     7358564 :             tuplesort_puttupleslot(tuplesortstate, slot);
     114             :         }
     115             : 
     116             :         /*
     117             :          * Complete the sort.
     118             :          */
     119       46948 :         tuplesort_performsort(tuplesortstate);
     120             : 
     121             :         /*
     122             :          * restore to user specified direction
     123             :          */
     124       46948 :         estate->es_direction = dir;
     125             : 
     126             :         /*
     127             :          * finally set the sorted flag to true
     128             :          */
     129       46948 :         node->sort_Done = true;
     130       46948 :         node->bounded_Done = node->bounded;
     131       46948 :         node->bound_Done = node->bound;
     132       46948 :         if (node->shared_info && node->am_worker)
     133             :         {
     134             :             TuplesortInstrumentation *si;
     135             : 
     136             :             Assert(IsParallelWorker());
     137             :             Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
     138          64 :             si = &node->shared_info->sinstrument[ParallelWorkerNumber];
     139          64 :             tuplesort_get_stats(tuplesortstate, si);
     140             :         }
     141             :         SO1_printf("ExecSort: %s\n", "sorting done");
     142             :     }
     143             : 
     144             :     SO1_printf("ExecSort: %s\n",
     145             :                "retrieving tuple from tuplesort");
     146             : 
     147             :     /*
     148             :      * Get the first or next tuple from tuplesort. Returns NULL if no more
     149             :      * tuples.  Note that we only rely on slot tuple remaining valid until the
     150             :      * next fetch from the tuplesort.
     151             :      */
     152     6150612 :     slot = node->ss.ps.ps_ResultTupleSlot;
     153     6150612 :     (void) tuplesort_gettupleslot(tuplesortstate,
     154             :                                   ScanDirectionIsForward(dir),
     155             :                                   false, slot, NULL);
     156     6150612 :     return slot;
     157             : }
     158             : 
     159             : /* ----------------------------------------------------------------
     160             :  *      ExecInitSort
     161             :  *
     162             :  *      Creates the run-time state information for the sort node
     163             :  *      produced by the planner and initializes its outer subtree.
     164             :  * ----------------------------------------------------------------
     165             :  */
     166             : SortState *
     167       35408 : ExecInitSort(Sort *node, EState *estate, int eflags)
     168             : {
     169             :     SortState  *sortstate;
     170             : 
     171             :     SO1_printf("ExecInitSort: %s\n",
     172             :                "initializing sort node");
     173             : 
     174             :     /*
     175             :      * create state structure
     176             :      */
     177       35408 :     sortstate = makeNode(SortState);
     178       35408 :     sortstate->ss.ps.plan = (Plan *) node;
     179       35408 :     sortstate->ss.ps.state = estate;
     180       35408 :     sortstate->ss.ps.ExecProcNode = ExecSort;
     181             : 
     182             :     /*
     183             :      * We must have random access to the sort output to do backward scan or
     184             :      * mark/restore.  We also prefer to materialize the sort output if we
     185             :      * might be called on to rewind and replay it many times.
     186             :      */
     187       70816 :     sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
     188             :                                          EXEC_FLAG_BACKWARD |
     189       35408 :                                          EXEC_FLAG_MARK)) != 0;
     190             : 
     191       35408 :     sortstate->bounded = false;
     192       35408 :     sortstate->sort_Done = false;
     193       35408 :     sortstate->tuplesortstate = NULL;
     194             : 
     195             :     /*
     196             :      * Miscellaneous initialization
     197             :      *
     198             :      * Sort nodes don't initialize their ExprContexts because they never call
     199             :      * ExecQual or ExecProject.
     200             :      */
     201             : 
     202             :     /*
     203             :      * initialize child nodes
     204             :      *
     205             :      * We shield the child node from the need to support REWIND, BACKWARD, or
     206             :      * MARK/RESTORE.
     207             :      */
     208       35408 :     eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
     209             : 
     210       35408 :     outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
     211             : 
     212             :     /*
     213             :      * Initialize scan slot and type.
     214             :      */
     215       35404 :     ExecCreateScanSlotFromOuterPlan(estate, &sortstate->ss, &TTSOpsVirtual);
     216             : 
     217             :     /*
     218             :      * Initialize return slot and type. No need to initialize projection info
     219             :      * because this node doesn't do projections.
     220             :      */
     221       35404 :     ExecInitResultTupleSlotTL(&sortstate->ss.ps, &TTSOpsMinimalTuple);
     222       35404 :     sortstate->ss.ps.ps_ProjInfo = NULL;
     223             : 
     224             :     SO1_printf("ExecInitSort: %s\n",
     225             :                "sort node initialized");
     226             : 
     227       35404 :     return sortstate;
     228             : }
     229             : 
     230             : /* ----------------------------------------------------------------
     231             :  *      ExecEndSort(node)
     232             :  * ----------------------------------------------------------------
     233             :  */
     234             : void
     235       35354 : ExecEndSort(SortState *node)
     236             : {
     237             :     SO1_printf("ExecEndSort: %s\n",
     238             :                "shutting down sort node");
     239             : 
     240             :     /*
     241             :      * clean out the tuple table
     242             :      */
     243       35354 :     ExecClearTuple(node->ss.ss_ScanTupleSlot);
     244             :     /* must drop pointer to sort result tuple */
     245       35354 :     ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
     246             : 
     247             :     /*
     248             :      * Release tuplesort resources
     249             :      */
     250       35354 :     if (node->tuplesortstate != NULL)
     251       31462 :         tuplesort_end((Tuplesortstate *) node->tuplesortstate);
     252       35354 :     node->tuplesortstate = NULL;
     253             : 
     254             :     /*
     255             :      * shut down the subplan
     256             :      */
     257       35354 :     ExecEndNode(outerPlanState(node));
     258             : 
     259             :     SO1_printf("ExecEndSort: %s\n",
     260             :                "sort node shutdown");
     261       35354 : }
     262             : 
     263             : /* ----------------------------------------------------------------
     264             :  *      ExecSortMarkPos
     265             :  *
     266             :  *      Calls tuplesort to save the current position in the sorted file.
     267             :  * ----------------------------------------------------------------
     268             :  */
     269             : void
     270      346614 : ExecSortMarkPos(SortState *node)
     271             : {
     272             :     /*
     273             :      * if we haven't sorted yet, just return
     274             :      */
     275      346614 :     if (!node->sort_Done)
     276           0 :         return;
     277             : 
     278      346614 :     tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
     279             : }
     280             : 
     281             : /* ----------------------------------------------------------------
     282             :  *      ExecSortRestrPos
     283             :  *
     284             :  *      Calls tuplesort to restore the last saved sort file position.
     285             :  * ----------------------------------------------------------------
     286             :  */
     287             : void
     288       16090 : ExecSortRestrPos(SortState *node)
     289             : {
     290             :     /*
     291             :      * if we haven't sorted yet, just return.
     292             :      */
     293       16090 :     if (!node->sort_Done)
     294           0 :         return;
     295             : 
     296             :     /*
     297             :      * restore the scan to the previously marked position
     298             :      */
     299       16090 :     tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
     300             : }
     301             : 
     302             : void
     303       20818 : ExecReScanSort(SortState *node)
     304             : {
     305       20818 :     PlanState  *outerPlan = outerPlanState(node);
     306             : 
     307             :     /*
     308             :      * If we haven't sorted yet, just return. If outerplan's chgParam is not
     309             :      * NULL then it will be re-scanned by ExecProcNode, else no reason to
     310             :      * re-scan it at all.
     311             :      */
     312       20818 :     if (!node->sort_Done)
     313        5342 :         return;
     314             : 
     315             :     /* must drop pointer to sort result tuple */
     316       15476 :     ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
     317             : 
     318             :     /*
     319             :      * If subnode is to be rescanned then we forget previous sort results; we
     320             :      * have to re-read the subplan and re-sort.  Also must re-sort if the
     321             :      * bounded-sort parameters changed or we didn't select randomAccess.
     322             :      *
     323             :      * Otherwise we can just rewind and rescan the sorted output.
     324             :      */
     325       15476 :     if (outerPlan->chgParam != NULL ||
     326         116 :         node->bounded != node->bounded_Done ||
     327         116 :         node->bound != node->bound_Done ||
     328          80 :         !node->randomAccess)
     329             :     {
     330       15448 :         node->sort_Done = false;
     331       15448 :         tuplesort_end((Tuplesortstate *) node->tuplesortstate);
     332       15448 :         node->tuplesortstate = NULL;
     333             : 
     334             :         /*
     335             :          * if chgParam of subnode is not null then plan will be re-scanned by
     336             :          * first ExecProcNode.
     337             :          */
     338       15536 :         if (outerPlan->chgParam == NULL)
     339          88 :             ExecReScan(outerPlan);
     340             :     }
     341             :     else
     342          28 :         tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
     343             : }
     344             : 
     345             : /* ----------------------------------------------------------------
     346             :  *                      Parallel Query Support
     347             :  * ----------------------------------------------------------------
     348             :  */
     349             : 
     350             : /* ----------------------------------------------------------------
     351             :  *      ExecSortEstimate
     352             :  *
     353             :  *      Estimate space required to propagate sort statistics.
     354             :  * ----------------------------------------------------------------
     355             :  */
     356             : void
     357          94 : ExecSortEstimate(SortState *node, ParallelContext *pcxt)
     358             : {
     359             :     Size        size;
     360             : 
     361             :     /* don't need this if not instrumenting or no workers */
     362          94 :     if (!node->ss.ps.instrument || pcxt->nworkers == 0)
     363          86 :         return;
     364             : 
     365           8 :     size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
     366           8 :     size = add_size(size, offsetof(SharedSortInfo, sinstrument));
     367           8 :     shm_toc_estimate_chunk(&pcxt->estimator, size);
     368           8 :     shm_toc_estimate_keys(&pcxt->estimator, 1);
     369             : }
     370             : 
     371             : /* ----------------------------------------------------------------
     372             :  *      ExecSortInitializeDSM
     373             :  *
     374             :  *      Initialize DSM space for sort statistics.
     375             :  * ----------------------------------------------------------------
     376             :  */
     377             : void
     378          94 : ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
     379             : {
     380             :     Size        size;
     381             : 
     382             :     /* don't need this if not instrumenting or no workers */
     383          94 :     if (!node->ss.ps.instrument || pcxt->nworkers == 0)
     384          86 :         return;
     385             : 
     386           8 :     size = offsetof(SharedSortInfo, sinstrument)
     387           8 :         + pcxt->nworkers * sizeof(TuplesortInstrumentation);
     388           8 :     node->shared_info = shm_toc_allocate(pcxt->toc, size);
     389             :     /* ensure any unfilled slots will contain zeroes */
     390           8 :     memset(node->shared_info, 0, size);
     391           8 :     node->shared_info->num_workers = pcxt->nworkers;
     392           8 :     shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
     393           8 :                    node->shared_info);
     394             : }
     395             : 
     396             : /* ----------------------------------------------------------------
     397             :  *      ExecSortInitializeWorker
     398             :  *
     399             :  *      Attach worker to DSM space for sort statistics.
     400             :  * ----------------------------------------------------------------
     401             :  */
     402             : void
     403         286 : ExecSortInitializeWorker(SortState *node, ParallelWorkerContext *pwcxt)
     404             : {
     405         286 :     node->shared_info =
     406         286 :         shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
     407         286 :     node->am_worker = true;
     408         286 : }
     409             : 
     410             : /* ----------------------------------------------------------------
     411             :  *      ExecSortRetrieveInstrumentation
     412             :  *
     413             :  *      Transfer sort statistics from DSM to private memory.
     414             :  * ----------------------------------------------------------------
     415             :  */
     416             : void
     417           8 : ExecSortRetrieveInstrumentation(SortState *node)
     418             : {
     419             :     Size        size;
     420             :     SharedSortInfo *si;
     421             : 
     422           8 :     if (node->shared_info == NULL)
     423           0 :         return;
     424             : 
     425           8 :     size = offsetof(SharedSortInfo, sinstrument)
     426           8 :         + node->shared_info->num_workers * sizeof(TuplesortInstrumentation);
     427           8 :     si = palloc(size);
     428           8 :     memcpy(si, node->shared_info, size);
     429           8 :     node->shared_info = si;
     430             : }

Generated by: LCOV version 1.13