LCOV - code coverage report
Current view: top level - src/backend/executor - nodeSort.c (source / functions) Hit Total Coverage
Test: PostgreSQL 16beta1 Lines: 128 131 97.7 %
Date: 2023-06-06 09:15:10 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-2023, 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             :  *      There are two distinct ways that this sort can be performed:
      33             :  *
      34             :  *      1) When the result is a single column we perform a Datum sort.
      35             :  *
      36             :  *      2) When the result contains multiple columns we perform a tuple sort.
      37             :  *
      38             :  *      We could do this by always performing a tuple sort, however sorting
      39             :  *      Datums only can be significantly faster than sorting tuples,
      40             :  *      especially when the Datums are of a pass-by-value type.
      41             :  *
      42             :  *      Conditions:
      43             :  *        -- none.
      44             :  *
      45             :  *      Initial States:
      46             :  *        -- the outer child is prepared to return the first tuple.
      47             :  * ----------------------------------------------------------------
      48             :  */
      49             : static TupleTableSlot *
      50     9749274 : ExecSort(PlanState *pstate)
      51             : {
      52     9749274 :     SortState  *node = castNode(SortState, pstate);
      53             :     EState     *estate;
      54             :     ScanDirection dir;
      55             :     Tuplesortstate *tuplesortstate;
      56             :     TupleTableSlot *slot;
      57             : 
      58     9749274 :     CHECK_FOR_INTERRUPTS();
      59             : 
      60             :     /*
      61             :      * get state info from node
      62             :      */
      63             :     SO1_printf("ExecSort: %s\n",
      64             :                "entering routine");
      65             : 
      66     9749274 :     estate = node->ss.ps.state;
      67     9749274 :     dir = estate->es_direction;
      68     9749274 :     tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
      69             : 
      70             :     /*
      71             :      * If first time through, read all tuples from outer plan and pass them to
      72             :      * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
      73             :      */
      74             : 
      75     9749274 :     if (!node->sort_Done)
      76             :     {
      77       80132 :         Sort       *plannode = (Sort *) node->ss.ps.plan;
      78             :         PlanState  *outerNode;
      79             :         TupleDesc   tupDesc;
      80       80132 :         int         tuplesortopts = TUPLESORT_NONE;
      81             : 
      82             :         SO1_printf("ExecSort: %s\n",
      83             :                    "sorting subplan");
      84             : 
      85             :         /*
      86             :          * Want to scan subplan in the forward direction while creating the
      87             :          * sorted data.
      88             :          */
      89       80132 :         estate->es_direction = ForwardScanDirection;
      90             : 
      91             :         /*
      92             :          * Initialize tuplesort module.
      93             :          */
      94             :         SO1_printf("ExecSort: %s\n",
      95             :                    "calling tuplesort_begin");
      96             : 
      97       80132 :         outerNode = outerPlanState(node);
      98       80132 :         tupDesc = ExecGetResultType(outerNode);
      99             : 
     100       80132 :         if (node->randomAccess)
     101        3682 :             tuplesortopts |= TUPLESORT_RANDOMACCESS;
     102       80132 :         if (node->bounded)
     103        1462 :             tuplesortopts |= TUPLESORT_ALLOWBOUNDED;
     104             : 
     105       80132 :         if (node->datumSort)
     106        4220 :             tuplesortstate = tuplesort_begin_datum(TupleDescAttr(tupDesc, 0)->atttypid,
     107        4220 :                                                    plannode->sortOperators[0],
     108        4220 :                                                    plannode->collations[0],
     109        4220 :                                                    plannode->nullsFirst[0],
     110             :                                                    work_mem,
     111             :                                                    NULL,
     112             :                                                    tuplesortopts);
     113             :         else
     114       75912 :             tuplesortstate = tuplesort_begin_heap(tupDesc,
     115             :                                                   plannode->numCols,
     116             :                                                   plannode->sortColIdx,
     117             :                                                   plannode->sortOperators,
     118             :                                                   plannode->collations,
     119             :                                                   plannode->nullsFirst,
     120             :                                                   work_mem,
     121             :                                                   NULL,
     122             :                                                   tuplesortopts);
     123       80120 :         if (node->bounded)
     124        1462 :             tuplesort_set_bound(tuplesortstate, node->bound);
     125       80120 :         node->tuplesortstate = (void *) tuplesortstate;
     126             : 
     127             :         /*
     128             :          * Scan the subplan and feed all the tuples to tuplesort using the
     129             :          * appropriate method based on the type of sort we're doing.
     130             :          */
     131       80120 :         if (node->datumSort)
     132             :         {
     133             :             for (;;)
     134             :             {
     135     1475798 :                 slot = ExecProcNode(outerNode);
     136             : 
     137     1475792 :                 if (TupIsNull(slot))
     138             :                     break;
     139     1471578 :                 slot_getsomeattrs(slot, 1);
     140     1471578 :                 tuplesort_putdatum(tuplesortstate,
     141     1471578 :                                    slot->tts_values[0],
     142     1471578 :                                    slot->tts_isnull[0]);
     143             :             }
     144             :         }
     145             :         else
     146             :         {
     147             :             for (;;)
     148             :             {
     149     9954000 :                 slot = ExecProcNode(outerNode);
     150             : 
     151     9954000 :                 if (TupIsNull(slot))
     152             :                     break;
     153     9878100 :                 tuplesort_puttupleslot(tuplesortstate, slot);
     154             :             }
     155             :         }
     156             : 
     157             :         /*
     158             :          * Complete the sort.
     159             :          */
     160       80114 :         tuplesort_performsort(tuplesortstate);
     161             : 
     162             :         /*
     163             :          * restore to user specified direction
     164             :          */
     165       80114 :         estate->es_direction = dir;
     166             : 
     167             :         /*
     168             :          * finally set the sorted flag to true
     169             :          */
     170       80114 :         node->sort_Done = true;
     171       80114 :         node->bounded_Done = node->bounded;
     172       80114 :         node->bound_Done = node->bound;
     173       80114 :         if (node->shared_info && node->am_worker)
     174             :         {
     175             :             TuplesortInstrumentation *si;
     176             : 
     177             :             Assert(IsParallelWorker());
     178             :             Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
     179          96 :             si = &node->shared_info->sinstrument[ParallelWorkerNumber];
     180          96 :             tuplesort_get_stats(tuplesortstate, si);
     181             :         }
     182             :         SO1_printf("ExecSort: %s\n", "sorting done");
     183             :     }
     184             : 
     185             :     SO1_printf("ExecSort: %s\n",
     186             :                "retrieving tuple from tuplesort");
     187             : 
     188     9749256 :     slot = node->ss.ps.ps_ResultTupleSlot;
     189             : 
     190             :     /*
     191             :      * Fetch the next sorted item from the appropriate tuplesort function. For
     192             :      * datum sorts we must manage the slot ourselves and leave it clear when
     193             :      * tuplesort_getdatum returns false to indicate there are no more datums.
     194             :      * For tuple sorts, tuplesort_gettupleslot manages the slot for us and
     195             :      * empties the slot when it runs out of tuples.
     196             :      */
     197     9749256 :     if (node->datumSort)
     198             :     {
     199     1185108 :         ExecClearTuple(slot);
     200     1185108 :         if (tuplesort_getdatum(tuplesortstate, ScanDirectionIsForward(dir),
     201             :                                false, &(slot->tts_values[0]),
     202             :                                &(slot->tts_isnull[0]), NULL))
     203     1181178 :             ExecStoreVirtualTuple(slot);
     204             :     }
     205             :     else
     206     8564148 :         (void) tuplesort_gettupleslot(tuplesortstate,
     207             :                                       ScanDirectionIsForward(dir),
     208             :                                       false, slot, NULL);
     209             : 
     210     9749256 :     return slot;
     211             : }
     212             : 
     213             : /* ----------------------------------------------------------------
     214             :  *      ExecInitSort
     215             :  *
     216             :  *      Creates the run-time state information for the sort node
     217             :  *      produced by the planner and initializes its outer subtree.
     218             :  * ----------------------------------------------------------------
     219             :  */
     220             : SortState *
     221       50562 : ExecInitSort(Sort *node, EState *estate, int eflags)
     222             : {
     223             :     SortState  *sortstate;
     224             :     TupleDesc   outerTupDesc;
     225             : 
     226             :     SO1_printf("ExecInitSort: %s\n",
     227             :                "initializing sort node");
     228             : 
     229             :     /*
     230             :      * create state structure
     231             :      */
     232       50562 :     sortstate = makeNode(SortState);
     233       50562 :     sortstate->ss.ps.plan = (Plan *) node;
     234       50562 :     sortstate->ss.ps.state = estate;
     235       50562 :     sortstate->ss.ps.ExecProcNode = ExecSort;
     236             : 
     237             :     /*
     238             :      * We must have random access to the sort output to do backward scan or
     239             :      * mark/restore.  We also prefer to materialize the sort output if we
     240             :      * might be called on to rewind and replay it many times.
     241             :      */
     242       50562 :     sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
     243             :                                          EXEC_FLAG_BACKWARD |
     244       50562 :                                          EXEC_FLAG_MARK)) != 0;
     245             : 
     246       50562 :     sortstate->bounded = false;
     247       50562 :     sortstate->sort_Done = false;
     248       50562 :     sortstate->tuplesortstate = NULL;
     249             : 
     250             :     /*
     251             :      * Miscellaneous initialization
     252             :      *
     253             :      * Sort nodes don't initialize their ExprContexts because they never call
     254             :      * ExecQual or ExecProject.
     255             :      */
     256             : 
     257             :     /*
     258             :      * initialize child nodes
     259             :      *
     260             :      * We shield the child node from the need to support REWIND, BACKWARD, or
     261             :      * MARK/RESTORE.
     262             :      */
     263       50562 :     eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
     264             : 
     265       50562 :     outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
     266             : 
     267             :     /*
     268             :      * Initialize scan slot and type.
     269             :      */
     270       50556 :     ExecCreateScanSlotFromOuterPlan(estate, &sortstate->ss, &TTSOpsVirtual);
     271             : 
     272             :     /*
     273             :      * Initialize return slot and type. No need to initialize projection info
     274             :      * because this node doesn't do projections.
     275             :      */
     276       50556 :     ExecInitResultTupleSlotTL(&sortstate->ss.ps, &TTSOpsMinimalTuple);
     277       50556 :     sortstate->ss.ps.ps_ProjInfo = NULL;
     278             : 
     279       50556 :     outerTupDesc = ExecGetResultType(outerPlanState(sortstate));
     280             : 
     281             :     /*
     282             :      * We perform a Datum sort when we're sorting just a single column,
     283             :      * otherwise we perform a tuple sort.
     284             :      */
     285       50556 :     if (outerTupDesc->natts == 1)
     286        6672 :         sortstate->datumSort = true;
     287             :     else
     288       43884 :         sortstate->datumSort = false;
     289             : 
     290             :     SO1_printf("ExecInitSort: %s\n",
     291             :                "sort node initialized");
     292             : 
     293       50556 :     return sortstate;
     294             : }
     295             : 
     296             : /* ----------------------------------------------------------------
     297             :  *      ExecEndSort(node)
     298             :  * ----------------------------------------------------------------
     299             :  */
     300             : void
     301       50484 : ExecEndSort(SortState *node)
     302             : {
     303             :     SO1_printf("ExecEndSort: %s\n",
     304             :                "shutting down sort node");
     305             : 
     306             :     /*
     307             :      * clean out the tuple table
     308             :      */
     309       50484 :     ExecClearTuple(node->ss.ss_ScanTupleSlot);
     310             :     /* must drop pointer to sort result tuple */
     311       50484 :     ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
     312             : 
     313             :     /*
     314             :      * Release tuplesort resources
     315             :      */
     316       50484 :     if (node->tuplesortstate != NULL)
     317       44302 :         tuplesort_end((Tuplesortstate *) node->tuplesortstate);
     318       50484 :     node->tuplesortstate = NULL;
     319             : 
     320             :     /*
     321             :      * shut down the subplan
     322             :      */
     323       50484 :     ExecEndNode(outerPlanState(node));
     324             : 
     325             :     SO1_printf("ExecEndSort: %s\n",
     326             :                "sort node shutdown");
     327       50484 : }
     328             : 
     329             : /* ----------------------------------------------------------------
     330             :  *      ExecSortMarkPos
     331             :  *
     332             :  *      Calls tuplesort to save the current position in the sorted file.
     333             :  * ----------------------------------------------------------------
     334             :  */
     335             : void
     336      569522 : ExecSortMarkPos(SortState *node)
     337             : {
     338             :     /*
     339             :      * if we haven't sorted yet, just return
     340             :      */
     341      569522 :     if (!node->sort_Done)
     342           0 :         return;
     343             : 
     344      569522 :     tuplesort_markpos((Tuplesortstate *) node->tuplesortstate);
     345             : }
     346             : 
     347             : /* ----------------------------------------------------------------
     348             :  *      ExecSortRestrPos
     349             :  *
     350             :  *      Calls tuplesort to restore the last saved sort file position.
     351             :  * ----------------------------------------------------------------
     352             :  */
     353             : void
     354       29208 : ExecSortRestrPos(SortState *node)
     355             : {
     356             :     /*
     357             :      * if we haven't sorted yet, just return.
     358             :      */
     359       29208 :     if (!node->sort_Done)
     360           0 :         return;
     361             : 
     362             :     /*
     363             :      * restore the scan to the previously marked position
     364             :      */
     365       29208 :     tuplesort_restorepos((Tuplesortstate *) node->tuplesortstate);
     366             : }
     367             : 
     368             : void
     369       36494 : ExecReScanSort(SortState *node)
     370             : {
     371       36494 :     PlanState  *outerPlan = outerPlanState(node);
     372             : 
     373             :     /*
     374             :      * If we haven't sorted yet, just return. If outerplan's chgParam is not
     375             :      * NULL then it will be re-scanned by ExecProcNode, else no reason to
     376             :      * re-scan it at all.
     377             :      */
     378       36494 :     if (!node->sort_Done)
     379         702 :         return;
     380             : 
     381             :     /* must drop pointer to sort result tuple */
     382       35792 :     ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
     383             : 
     384             :     /*
     385             :      * If subnode is to be rescanned then we forget previous sort results; we
     386             :      * have to re-read the subplan and re-sort.  Also must re-sort if the
     387             :      * bounded-sort parameters changed or we didn't select randomAccess.
     388             :      *
     389             :      * Otherwise we can just rewind and rescan the sorted output.
     390             :      */
     391       35792 :     if (outerPlan->chgParam != NULL ||
     392         448 :         node->bounded != node->bounded_Done ||
     393         448 :         node->bound != node->bound_Done ||
     394         394 :         !node->randomAccess)
     395             :     {
     396       35758 :         node->sort_Done = false;
     397       35758 :         tuplesort_end((Tuplesortstate *) node->tuplesortstate);
     398       35758 :         node->tuplesortstate = NULL;
     399             : 
     400             :         /*
     401             :          * if chgParam of subnode is not null then plan will be re-scanned by
     402             :          * first ExecProcNode.
     403             :          */
     404       35758 :         if (outerPlan->chgParam == NULL)
     405         414 :             ExecReScan(outerPlan);
     406             :     }
     407             :     else
     408          34 :         tuplesort_rescan((Tuplesortstate *) node->tuplesortstate);
     409             : }
     410             : 
     411             : /* ----------------------------------------------------------------
     412             :  *                      Parallel Query Support
     413             :  * ----------------------------------------------------------------
     414             :  */
     415             : 
     416             : /* ----------------------------------------------------------------
     417             :  *      ExecSortEstimate
     418             :  *
     419             :  *      Estimate space required to propagate sort statistics.
     420             :  * ----------------------------------------------------------------
     421             :  */
     422             : void
     423         140 : ExecSortEstimate(SortState *node, ParallelContext *pcxt)
     424             : {
     425             :     Size        size;
     426             : 
     427             :     /* don't need this if not instrumenting or no workers */
     428         140 :     if (!node->ss.ps.instrument || pcxt->nworkers == 0)
     429         128 :         return;
     430             : 
     431          12 :     size = mul_size(pcxt->nworkers, sizeof(TuplesortInstrumentation));
     432          12 :     size = add_size(size, offsetof(SharedSortInfo, sinstrument));
     433          12 :     shm_toc_estimate_chunk(&pcxt->estimator, size);
     434          12 :     shm_toc_estimate_keys(&pcxt->estimator, 1);
     435             : }
     436             : 
     437             : /* ----------------------------------------------------------------
     438             :  *      ExecSortInitializeDSM
     439             :  *
     440             :  *      Initialize DSM space for sort statistics.
     441             :  * ----------------------------------------------------------------
     442             :  */
     443             : void
     444         140 : ExecSortInitializeDSM(SortState *node, ParallelContext *pcxt)
     445             : {
     446             :     Size        size;
     447             : 
     448             :     /* don't need this if not instrumenting or no workers */
     449         140 :     if (!node->ss.ps.instrument || pcxt->nworkers == 0)
     450         128 :         return;
     451             : 
     452          12 :     size = offsetof(SharedSortInfo, sinstrument)
     453          12 :         + pcxt->nworkers * sizeof(TuplesortInstrumentation);
     454          12 :     node->shared_info = shm_toc_allocate(pcxt->toc, size);
     455             :     /* ensure any unfilled slots will contain zeroes */
     456          12 :     memset(node->shared_info, 0, size);
     457          12 :     node->shared_info->num_workers = pcxt->nworkers;
     458          12 :     shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
     459          12 :                    node->shared_info);
     460             : }
     461             : 
     462             : /* ----------------------------------------------------------------
     463             :  *      ExecSortInitializeWorker
     464             :  *
     465             :  *      Attach worker to DSM space for sort statistics.
     466             :  * ----------------------------------------------------------------
     467             :  */
     468             : void
     469         428 : ExecSortInitializeWorker(SortState *node, ParallelWorkerContext *pwcxt)
     470             : {
     471         428 :     node->shared_info =
     472         428 :         shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
     473         428 :     node->am_worker = true;
     474         428 : }
     475             : 
     476             : /* ----------------------------------------------------------------
     477             :  *      ExecSortRetrieveInstrumentation
     478             :  *
     479             :  *      Transfer sort statistics from DSM to private memory.
     480             :  * ----------------------------------------------------------------
     481             :  */
     482             : void
     483          12 : ExecSortRetrieveInstrumentation(SortState *node)
     484             : {
     485             :     Size        size;
     486             :     SharedSortInfo *si;
     487             : 
     488          12 :     if (node->shared_info == NULL)
     489           0 :         return;
     490             : 
     491          12 :     size = offsetof(SharedSortInfo, sinstrument)
     492          12 :         + node->shared_info->num_workers * sizeof(TuplesortInstrumentation);
     493          12 :     si = palloc(size);
     494          12 :     memcpy(si, node->shared_info, size);
     495          12 :     node->shared_info = si;
     496             : }

Generated by: LCOV version 1.14