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

Generated by: LCOV version 1.14