#include "access/itup.h"
#include "executor/tuptable.h"
#include "storage/dsm.h"
#include "utils/logtape.h"
#include "utils/relcache.h"
#include "utils/sortsupport.h"

Include dependency graph for tuplesort.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	SortCoordinateData

struct	TuplesortInstrumentation

struct	SortTuple

struct	TuplesortPublic

Macros
#define	NUM_TUPLESORTMETHODS 4

#define	TUPLESORT_NONE 0

#define	TUPLESORT_RANDOMACCESS (1 << 0)

#define	TUPLESORT_ALLOWBOUNDED (1 << 1)

#define	PARALLEL_SORT(coordinate)

#define	TuplesortstateGetPublic(state) ((TuplesortPublic *) state)

#define	LogicalTapeReadExact(tape, ptr, len)

Typedefs
typedef struct Tuplesortstate	Tuplesortstate

typedef struct Sharedsort	Sharedsort

typedef struct SortCoordinateData	SortCoordinateData

typedef struct SortCoordinateData *	SortCoordinate

typedef struct TuplesortInstrumentation	TuplesortInstrumentation

typedef int(*	SortTupleComparator) (const SortTuple a, const SortTuple b, Tuplesortstate *state)

Enumerations
enum	TuplesortMethod { SORT_TYPE_STILL_IN_PROGRESS = 0 , SORT_TYPE_TOP_N_HEAPSORT = 1 << 0 , SORT_TYPE_QUICKSORT = 1 << 1 , SORT_TYPE_EXTERNAL_SORT = 1 << 2 , SORT_TYPE_EXTERNAL_MERGE = 1 << 3 }

enum	TuplesortSpaceType { SORT_SPACE_TYPE_DISK , SORT_SPACE_TYPE_MEMORY }

Functions
Tuplesortstate *	tuplesort_begin_common (int workMem, SortCoordinate coordinate, int sortopt)

void	tuplesort_set_bound (Tuplesortstate *state, int64 bound)

bool	tuplesort_used_bound (Tuplesortstate *state)

void	tuplesort_puttuple_common (Tuplesortstate state, SortTuple tuple, bool useAbbrev)

void	tuplesort_performsort (Tuplesortstate *state)

bool	tuplesort_gettuple_common (Tuplesortstate state, bool forward, SortTuple stup)

bool	tuplesort_skiptuples (Tuplesortstate *state, int64 ntuples, bool forward)

void	tuplesort_end (Tuplesortstate *state)

void	tuplesort_reset (Tuplesortstate *state)

void	tuplesort_get_stats (Tuplesortstate state, TuplesortInstrumentation stats)

const char *	tuplesort_method_name (TuplesortMethod m)

const char *	tuplesort_space_type_name (TuplesortSpaceType t)

int	tuplesort_merge_order (int64 allowedMem)

Size	tuplesort_estimate_shared (int nWorkers)

void	tuplesort_initialize_shared (Sharedsort shared, int nWorkers, dsm_segment seg)

void	tuplesort_attach_shared (Sharedsort shared, dsm_segment seg)

void	tuplesort_rescan (Tuplesortstate *state)

void	tuplesort_markpos (Tuplesortstate *state)

void	tuplesort_restorepos (Tuplesortstate *state)

void *	tuplesort_readtup_alloc (Tuplesortstate *state, Size tuplen)

Tuplesortstate *	tuplesort_begin_heap (TupleDesc tupDesc, int nkeys, AttrNumber attNums, Oid sortOperators, Oid sortCollations, bool nullsFirstFlags, int workMem, SortCoordinate coordinate, int sortopt)

Tuplesortstate *	tuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)

Tuplesortstate *	tuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, bool uniqueNullsNotDistinct, int workMem, SortCoordinate coordinate, int sortopt)

Tuplesortstate *	tuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, int sortopt)

Tuplesortstate *	tuplesort_begin_index_gist (Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)

Tuplesortstate *	tuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, int sortopt)

void	tuplesort_puttupleslot (Tuplesortstate state, TupleTableSlot slot)

void	tuplesort_putheaptuple (Tuplesortstate *state, HeapTuple tup)

void	tuplesort_putindextuplevalues (Tuplesortstate state, Relation rel, ItemPointer self, Datum values, bool *isnull)

void	tuplesort_putdatum (Tuplesortstate *state, Datum val, bool isNull)

bool	tuplesort_gettupleslot (Tuplesortstate state, bool forward, bool copy, TupleTableSlot slot, Datum *abbrev)

HeapTuple	tuplesort_getheaptuple (Tuplesortstate *state, bool forward)

IndexTuple	tuplesort_getindextuple (Tuplesortstate *state, bool forward)

bool	tuplesort_getdatum (Tuplesortstate state, bool forward, bool copy, Datum val, bool isNull, Datum abbrev)

Macro Definition Documentation

◆ LogicalTapeReadExact

#define LogicalTapeReadExact	(	tape,
		ptr,
		len
	)

Value:

    do { \
        if (LogicalTapeRead(tape, ptr, len) != (size_t) (len)) \
            elog(ERROR, "unexpected end of data"); \
    } while(0)

Definition at line 244 of file tuplesort.h.

◆ NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS 4

Definition at line 83 of file tuplesort.h.

◆ PARALLEL_SORT

#define PARALLEL_SORT ( coordinate )

Value:

                                     (coordinate == NULL || \
                                     (coordinate)->sharedsort == NULL ? 0 : \
                                     (coordinate)->isWorker ? 1 : 2)

Definition at line 237 of file tuplesort.h.

◆ TUPLESORT_ALLOWBOUNDED

#define TUPLESORT_ALLOWBOUNDED (1 << 1)

Definition at line 98 of file tuplesort.h.

◆ TUPLESORT_NONE

#define TUPLESORT_NONE 0

Definition at line 92 of file tuplesort.h.

◆ TUPLESORT_RANDOMACCESS

#define TUPLESORT_RANDOMACCESS (1 << 0)

Definition at line 95 of file tuplesort.h.

◆ TuplesortstateGetPublic

#define TuplesortstateGetPublic ( state ) ((TuplesortPublic *) state)

Definition at line 241 of file tuplesort.h.

Typedef Documentation

◆ Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 1 of file tuplesort.h.

◆ SortCoordinate

typedef struct SortCoordinateData* SortCoordinate

Definition at line 60 of file tuplesort.h.

◆ SortCoordinateData

typedef struct SortCoordinateData SortCoordinateData

◆ SortTupleComparator

typedef int(* SortTupleComparator) (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)

Definition at line 144 of file tuplesort.h.

◆ TuplesortInstrumentation

typedef struct TuplesortInstrumentation TuplesortInstrumentation

◆ Tuplesortstate

typedef struct Tuplesortstate Tuplesortstate

Definition at line 1 of file tuplesort.h.

Enumeration Type Documentation

◆ TuplesortMethod

enum TuplesortMethod

Enumerator
SORT_TYPE_STILL_IN_PROGRESS
SORT_TYPE_TOP_N_HEAPSORT
SORT_TYPE_QUICKSORT
SORT_TYPE_EXTERNAL_SORT
SORT_TYPE_EXTERNAL_MERGE

Definition at line 74 of file tuplesort.h.

 {
     SORT_TYPE_STILL_IN_PROGRESS = 0,
     SORT_TYPE_TOP_N_HEAPSORT = 1 << 0,
     SORT_TYPE_QUICKSORT = 1 << 1,
     SORT_TYPE_EXTERNAL_SORT = 1 << 2,
     SORT_TYPE_EXTERNAL_MERGE = 1 << 3
 } TuplesortMethod;

◆ TuplesortSpaceType

enum TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK
SORT_SPACE_TYPE_MEMORY

Definition at line 85 of file tuplesort.h.

 {
     SORT_SPACE_TYPE_DISK,
     SORT_SPACE_TYPE_MEMORY
 } TuplesortSpaceType;

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared	(	Sharedsort *	shared,
		dsm_segment *	seg
	)

Definition at line 2999 of file tuplesort.c.

 {
     /* Attach to SharedFileSet */
     SharedFileSetAttach(&shared->fileset, seg);
 }

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

◆ tuplesort_begin_cluster()

Tuplesortstate* tuplesort_begin_cluster	(	TupleDesc	tupDesc,
		Relation	indexRel,
		int	workMem,
		SortCoordinate	coordinate,
		int	sortopt
	)

Definition at line 208 of file tuplesortvariants.c.

 {
     Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                    sortopt);
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     BTScanInsert indexScanKey;
     MemoryContext oldcontext;
     TuplesortClusterArg *arg;
     int         i;
  
     Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
  
     oldcontext = MemoryContextSwitchTo(base->maincontext);
     arg = (TuplesortClusterArg *) palloc0(sizeof(TuplesortClusterArg));
  
 #ifdef TRACE_SORT
     if (trace_sort)
         elog(LOG,
              "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
              RelationGetNumberOfAttributes(indexRel),
              workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 #endif
  
     base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
  
     TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
                                 false,  /* no unique check */
                                 base->nKeys,
                                 workMem,
                                 sortopt & TUPLESORT_RANDOMACCESS,
                                 PARALLEL_SORT(coordinate));
  
     base->removeabbrev = removeabbrev_cluster;
     base->comparetup = comparetup_cluster;
     base->writetup = writetup_cluster;
     base->readtup = readtup_cluster;
     base->freestate = freestate_cluster;
     base->arg = arg;
  
     arg->indexInfo = BuildIndexInfo(indexRel);
  
     /*
      * If we don't have a simple leading attribute, we don't currently
      * initialize datum1, so disable optimizations that require it.
      */
     if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
         base->haveDatum1 = false;
     else
         base->haveDatum1 = true;
  
     arg->tupDesc = tupDesc;     /* assume we need not copy tupDesc */
  
     indexScanKey = _bt_mkscankey(indexRel, NULL);
  
     if (arg->indexInfo->ii_Expressions != NULL)
     {
         TupleTableSlot *slot;
         ExprContext *econtext;
  
         /*
          * We will need to use FormIndexDatum to evaluate the index
          * expressions.  To do that, we need an EState, as well as a
          * TupleTableSlot to put the table tuples into.  The econtext's
          * scantuple has to point to that slot, too.
          */
         arg->estate = CreateExecutorState();
         slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
         econtext = GetPerTupleExprContext(arg->estate);
         econtext->ecxt_scantuple = slot;
     }
  
     /* Prepare SortSupport data for each column */
     base->sortKeys = (SortSupport) palloc0(base->nKeys *
                                            sizeof(SortSupportData));
  
     for (i = 0; i < base->nKeys; i++)
     {
         SortSupport sortKey = base->sortKeys + i;
         ScanKey     scanKey = indexScanKey->scankeys + i;
         int16       strategy;
  
         sortKey->ssup_cxt = CurrentMemoryContext;
         sortKey->ssup_collation = scanKey->sk_collation;
         sortKey->ssup_nulls_first =
             (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
         sortKey->ssup_attno = scanKey->sk_attno;
         /* Convey if abbreviation optimization is applicable in principle */
         sortKey->abbreviate = (i == 0 && base->haveDatum1);
  
         Assert(sortKey->ssup_attno != 0);
  
         strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
             BTGreaterStrategyNumber : BTLessStrategyNumber;
  
         PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
     }
  
     pfree(indexScanKey);
  
     MemoryContextSwitchTo(oldcontext);
  
     return state;
 }

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), BTGreaterStrategyNumber, BTLessStrategyNumber, BuildIndexInfo(), CLUSTER_SORT, TuplesortPublic::comparetup, comparetup_cluster(), CreateExecutorState(), CurrentMemoryContext, ExprContext::ecxt_scantuple, elog(), TuplesortPublic::freestate, freestate_cluster(), GetPerTupleExprContext, TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, TuplesortPublic::readtup, readtup_cluster(), RelationGetNumberOfAttributes, TuplesortPublic::removeabbrev, removeabbrev_cluster(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TTSOpsHeapTuple, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_cluster().

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_begin_common()

Tuplesortstate* tuplesort_begin_common	(	int	workMem,
		SortCoordinate	coordinate,
		int	sortopt
	)

Definition at line 646 of file tuplesort.c.

 {
     Tuplesortstate *state;
     MemoryContext maincontext;
     MemoryContext sortcontext;
     MemoryContext oldcontext;
  
     /* See leader_takeover_tapes() remarks on random access support */
     if (coordinate && (sortopt & TUPLESORT_RANDOMACCESS))
         elog(ERROR, "random access disallowed under parallel sort");
  
     /*
      * Memory context surviving tuplesort_reset.  This memory context holds
      * data which is useful to keep while sorting multiple similar batches.
      */
     maincontext = AllocSetContextCreate(CurrentMemoryContext,
                                         "TupleSort main",
                                         ALLOCSET_DEFAULT_SIZES);
  
     /*
      * Create a working memory context for one sort operation.  The content of
      * this context is deleted by tuplesort_reset.
      */
     sortcontext = AllocSetContextCreate(maincontext,
                                         "TupleSort sort",
                                         ALLOCSET_DEFAULT_SIZES);
  
     /*
      * Additionally a working memory context for tuples is setup in
      * tuplesort_begin_batch.
      */
  
     /*
      * Make the Tuplesortstate within the per-sortstate context.  This way, we
      * don't need a separate pfree() operation for it at shutdown.
      */
     oldcontext = MemoryContextSwitchTo(maincontext);
  
     state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));
  
 #ifdef TRACE_SORT
     if (trace_sort)
         pg_rusage_init(&state->ru_start);
 #endif
  
     state->base.sortopt = sortopt;
     state->base.tuples = true;
     state->abbrevNext = 10;
  
     /*
      * workMem is forced to be at least 64KB, the current minimum valid value
      * for the work_mem GUC.  This is a defense against parallel sort callers
      * that divide out memory among many workers in a way that leaves each
      * with very little memory.
      */
     state->allowedMem = Max(workMem, 64) * (int64) 1024;
     state->base.sortcontext = sortcontext;
     state->base.maincontext = maincontext;
  
     /*
      * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
      * see comments in grow_memtuples().
      */
     state->memtupsize = INITIAL_MEMTUPSIZE;
     state->memtuples = NULL;
  
     /*
      * After all of the other non-parallel-related state, we setup all of the
      * state needed for each batch.
      */
     tuplesort_begin_batch(state);
  
     /*
      * Initialize parallel-related state based on coordination information
      * from caller
      */
     if (!coordinate)
     {
         /* Serial sort */
         state->shared = NULL;
         state->worker = -1;
         state->nParticipants = -1;
     }
     else if (coordinate->isWorker)
     {
         /* Parallel worker produces exactly one final run from all input */
         state->shared = coordinate->sharedsort;
         state->worker = worker_get_identifier(state);
         state->nParticipants = -1;
     }
     else
     {
         /* Parallel leader state only used for final merge */
         state->shared = coordinate->sharedsort;
         state->worker = -1;
         state->nParticipants = coordinate->nParticipants;
         Assert(state->nParticipants >= 1);
     }
  
     MemoryContextSwitchTo(oldcontext);
  
     return state;
 }

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), CurrentMemoryContext, elog(), ERROR, INITIAL_MEMTUPSIZE, SortCoordinateData::isWorker, Max, MemoryContextSwitchTo(), SortCoordinateData::nParticipants, palloc0(), pg_rusage_init(), SortCoordinateData::sharedsort, trace_sort, tuplesort_begin_batch(), TUPLESORT_RANDOMACCESS, and worker_get_identifier().

Referenced by tuplesort_begin_cluster(), tuplesort_begin_datum(), tuplesort_begin_heap(), tuplesort_begin_index_btree(), tuplesort_begin_index_gist(), and tuplesort_begin_index_hash().

◆ tuplesort_begin_datum()

Tuplesortstate* tuplesort_begin_datum	(	Oid	datumType,
		Oid	sortOperator,
		Oid	sortCollation,
		bool	nullsFirstFlag,
		int	workMem,
		SortCoordinate	coordinate,
		int	sortopt
	)

Definition at line 516 of file tuplesortvariants.c.

 {
     Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                    sortopt);
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     TuplesortDatumArg *arg;
     MemoryContext oldcontext;
     int16       typlen;
     bool        typbyval;
  
     oldcontext = MemoryContextSwitchTo(base->maincontext);
     arg = (TuplesortDatumArg *) palloc(sizeof(TuplesortDatumArg));
  
 #ifdef TRACE_SORT
     if (trace_sort)
         elog(LOG,
              "begin datum sort: workMem = %d, randomAccess = %c",
              workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 #endif
  
     base->nKeys = 1;            /* always a one-column sort */
  
     TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
                                 false,  /* no unique check */
                                 1,
                                 workMem,
                                 sortopt & TUPLESORT_RANDOMACCESS,
                                 PARALLEL_SORT(coordinate));
  
     base->removeabbrev = removeabbrev_datum;
     base->comparetup = comparetup_datum;
     base->writetup = writetup_datum;
     base->readtup = readtup_datum;
     base->haveDatum1 = true;
     base->arg = arg;
  
     arg->datumType = datumType;
  
     /* lookup necessary attributes of the datum type */
     get_typlenbyval(datumType, &typlen, &typbyval);
     arg->datumTypeLen = typlen;
     base->tuples = !typbyval;
  
     /* Prepare SortSupport data */
     base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
  
     base->sortKeys->ssup_cxt = CurrentMemoryContext;
     base->sortKeys->ssup_collation = sortCollation;
     base->sortKeys->ssup_nulls_first = nullsFirstFlag;
  
     /*
      * Abbreviation is possible here only for by-reference types.  In theory,
      * a pass-by-value datatype could have an abbreviated form that is cheaper
      * to compare.  In a tuple sort, we could support that, because we can
      * always extract the original datum from the tuple as needed.  Here, we
      * can't, because a datum sort only stores a single copy of the datum; the
      * "tuple" field of each SortTuple is NULL.
      */
     base->sortKeys->abbreviate = !typbyval;
  
     PrepareSortSupportFromOrderingOp(sortOperator, base->sortKeys);
  
     /*
      * The "onlyKey" optimization cannot be used with abbreviated keys, since
      * tie-breaker comparisons may be required.  Typically, the optimization
      * is only of value to pass-by-value types anyway, whereas abbreviated
      * keys are typically only of value to pass-by-reference types.
      */
     if (!base->sortKeys->abbrev_converter)
         base->onlyKey = base->sortKeys;
  
     MemoryContextSwitchTo(oldcontext);
  
     return state;
 }

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, arg, TuplesortPublic::arg, TuplesortPublic::comparetup, comparetup_datum(), CurrentMemoryContext, DATUM_SORT, elog(), get_typlenbyval(), TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, TuplesortPublic::onlyKey, palloc(), palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), TuplesortPublic::readtup, readtup_datum(), TuplesortPublic::removeabbrev, removeabbrev_datum(), TuplesortPublic::sortKeys, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TuplesortPublic::tuples, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_datum().

Referenced by ExecSort(), initialize_aggregate(), ordered_set_startup(), and validate_index().

◆ tuplesort_begin_heap()

Tuplesortstate* tuplesort_begin_heap	(	TupleDesc	tupDesc,
		int	nkeys,
		AttrNumber *	attNums,
		Oid *	sortOperators,
		Oid *	sortCollations,
		bool *	nullsFirstFlags,
		int	workMem,
		SortCoordinate	coordinate,
		int	sortopt
	)

Definition at line 134 of file tuplesortvariants.c.

 {
     Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                    sortopt);
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext;
     int         i;
  
     oldcontext = MemoryContextSwitchTo(base->maincontext);
  
     Assert(nkeys > 0);
  
 #ifdef TRACE_SORT
     if (trace_sort)
         elog(LOG,
              "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
              nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 #endif
  
     base->nKeys = nkeys;
  
     TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
                                 false,  /* no unique check */
                                 nkeys,
                                 workMem,
                                 sortopt & TUPLESORT_RANDOMACCESS,
                                 PARALLEL_SORT(coordinate));
  
     base->removeabbrev = removeabbrev_heap;
     base->comparetup = comparetup_heap;
     base->writetup = writetup_heap;
     base->readtup = readtup_heap;
     base->haveDatum1 = true;
     base->arg = tupDesc;        /* assume we need not copy tupDesc */
  
     /* Prepare SortSupport data for each column */
     base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
  
     for (i = 0; i < nkeys; i++)
     {
         SortSupport sortKey = base->sortKeys + i;
  
         Assert(attNums[i] != 0);
         Assert(sortOperators[i] != 0);
  
         sortKey->ssup_cxt = CurrentMemoryContext;
         sortKey->ssup_collation = sortCollations[i];
         sortKey->ssup_nulls_first = nullsFirstFlags[i];
         sortKey->ssup_attno = attNums[i];
         /* Convey if abbreviation optimization is applicable in principle */
         sortKey->abbreviate = (i == 0 && base->haveDatum1);
  
         PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
     }
  
     /*
      * The "onlyKey" optimization cannot be used with abbreviated keys, since
      * tie-breaker comparisons may be required.  Typically, the optimization
      * is only of value to pass-by-value types anyway, whereas abbreviated
      * keys are typically only of value to pass-by-reference types.
      */
     if (nkeys == 1 && !base->sortKeys->abbrev_converter)
         base->onlyKey = base->sortKeys;
  
     MemoryContextSwitchTo(oldcontext);
  
     return state;
 }

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_heap(), CurrentMemoryContext, elog(), TuplesortPublic::haveDatum1, HEAP_SORT, i, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, TuplesortPublic::onlyKey, palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), TuplesortPublic::readtup, readtup_heap(), TuplesortPublic::removeabbrev, removeabbrev_heap(), TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_heap().

Referenced by ExecIncrementalSort(), ExecSort(), initialize_aggregate(), initialize_phase(), ordered_set_startup(), and switchToPresortedPrefixMode().

◆ tuplesort_begin_index_btree()

Tuplesortstate* tuplesort_begin_index_btree	(	Relation	heapRel,
		Relation	indexRel,
		bool	enforceUnique,
		bool	uniqueNullsNotDistinct,
		int	workMem,
		SortCoordinate	coordinate,
		int	sortopt
	)

Definition at line 316 of file tuplesortvariants.c.

 {
     Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                    sortopt);
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     BTScanInsert indexScanKey;
     TuplesortIndexBTreeArg *arg;
     MemoryContext oldcontext;
     int         i;
  
     oldcontext = MemoryContextSwitchTo(base->maincontext);
     arg = (TuplesortIndexBTreeArg *) palloc(sizeof(TuplesortIndexBTreeArg));
  
 #ifdef TRACE_SORT
     if (trace_sort)
         elog(LOG,
              "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
              enforceUnique ? 't' : 'f',
              workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 #endif
  
     base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
  
     TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
                                 enforceUnique,
                                 base->nKeys,
                                 workMem,
                                 sortopt & TUPLESORT_RANDOMACCESS,
                                 PARALLEL_SORT(coordinate));
  
     base->removeabbrev = removeabbrev_index;
     base->comparetup = comparetup_index_btree;
     base->writetup = writetup_index;
     base->readtup = readtup_index;
     base->haveDatum1 = true;
     base->arg = arg;
  
     arg->index.heapRel = heapRel;
     arg->index.indexRel = indexRel;
     arg->enforceUnique = enforceUnique;
     arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
  
     indexScanKey = _bt_mkscankey(indexRel, NULL);
  
     /* Prepare SortSupport data for each column */
     base->sortKeys = (SortSupport) palloc0(base->nKeys *
                                            sizeof(SortSupportData));
  
     for (i = 0; i < base->nKeys; i++)
     {
         SortSupport sortKey = base->sortKeys + i;
         ScanKey     scanKey = indexScanKey->scankeys + i;
         int16       strategy;
  
         sortKey->ssup_cxt = CurrentMemoryContext;
         sortKey->ssup_collation = scanKey->sk_collation;
         sortKey->ssup_nulls_first =
             (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
         sortKey->ssup_attno = scanKey->sk_attno;
         /* Convey if abbreviation optimization is applicable in principle */
         sortKey->abbreviate = (i == 0 && base->haveDatum1);
  
         Assert(sortKey->ssup_attno != 0);
  
         strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
             BTGreaterStrategyNumber : BTLessStrategyNumber;
  
         PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
     }
  
     pfree(indexScanKey);
  
     MemoryContextSwitchTo(oldcontext);
  
     return state;
 }

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), BTGreaterStrategyNumber, BTLessStrategyNumber, TuplesortPublic::comparetup, comparetup_index_btree(), CurrentMemoryContext, elog(), TuplesortPublic::haveDatum1, i, INDEX_SORT, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

◆ tuplesort_begin_index_gist()

Tuplesortstate* tuplesort_begin_index_gist	(	Relation	heapRel,
		Relation	indexRel,
		int	workMem,
		SortCoordinate	coordinate,
		int	sortopt
	)

Definition at line 452 of file tuplesortvariants.c.

 {
     Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                    sortopt);
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext;
     TuplesortIndexBTreeArg *arg;
     int         i;
  
     oldcontext = MemoryContextSwitchTo(base->maincontext);
     arg = (TuplesortIndexBTreeArg *) palloc(sizeof(TuplesortIndexBTreeArg));
  
 #ifdef TRACE_SORT
     if (trace_sort)
         elog(LOG,
              "begin index sort: workMem = %d, randomAccess = %c",
              workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 #endif
  
     base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
  
     base->removeabbrev = removeabbrev_index;
     base->comparetup = comparetup_index_btree;
     base->writetup = writetup_index;
     base->readtup = readtup_index;
     base->haveDatum1 = true;
     base->arg = arg;
  
     arg->index.heapRel = heapRel;
     arg->index.indexRel = indexRel;
     arg->enforceUnique = false;
     arg->uniqueNullsNotDistinct = false;
  
     /* Prepare SortSupport data for each column */
     base->sortKeys = (SortSupport) palloc0(base->nKeys *
                                            sizeof(SortSupportData));
  
     for (i = 0; i < base->nKeys; i++)
     {
         SortSupport sortKey = base->sortKeys + i;
  
         sortKey->ssup_cxt = CurrentMemoryContext;
         sortKey->ssup_collation = indexRel->rd_indcollation[i];
         sortKey->ssup_nulls_first = false;
         sortKey->ssup_attno = i + 1;
         /* Convey if abbreviation optimization is applicable in principle */
         sortKey->abbreviate = (i == 0 && base->haveDatum1);
  
         Assert(sortKey->ssup_attno != 0);
  
         /* Look for a sort support function */
         PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
     }
  
     MemoryContextSwitchTo(oldcontext);
  
     return state;
 }

References SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_index_btree(), CurrentMemoryContext, elog(), TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), palloc0(), PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by gistbuild().

◆ tuplesort_begin_index_hash()

Tuplesortstate* tuplesort_begin_index_hash	(	Relation	heapRel,
		Relation	indexRel,
		uint32	high_mask,
		uint32	low_mask,
		uint32	max_buckets,
		int	workMem,
		SortCoordinate	coordinate,
		int	sortopt
	)

Definition at line 400 of file tuplesortvariants.c.

 {
     Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                    sortopt);
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext;
     TuplesortIndexHashArg *arg;
  
     oldcontext = MemoryContextSwitchTo(base->maincontext);
     arg = (TuplesortIndexHashArg *) palloc(sizeof(TuplesortIndexHashArg));
  
 #ifdef TRACE_SORT
     if (trace_sort)
         elog(LOG,
              "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
              "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
              high_mask,
              low_mask,
              max_buckets,
              workMem,
              sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 #endif
  
     base->nKeys = 1;            /* Only one sort column, the hash code */
  
     base->removeabbrev = removeabbrev_index;
     base->comparetup = comparetup_index_hash;
     base->writetup = writetup_index;
     base->readtup = readtup_index;
     base->haveDatum1 = true;
     base->arg = arg;
  
     arg->index.heapRel = heapRel;
     arg->index.indexRel = indexRel;
  
     arg->high_mask = high_mask;
     arg->low_mask = low_mask;
     arg->max_buckets = max_buckets;
  
     MemoryContextSwitchTo(oldcontext);
  
     return state;
 }

References arg, TuplesortPublic::arg, TuplesortPublic::comparetup, comparetup_index_hash(), elog(), TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by _h_spoolinit().

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate * state )

Definition at line 972 of file tuplesort.c.

 {
     tuplesort_free(state);
  
     /*
      * Free the main memory context, including the Tuplesortstate struct
      * itself.
      */
     MemoryContextDelete(state->base.maincontext);
 }

References MemoryContextDelete(), and tuplesort_free().

Referenced by _bt_parallel_scan_and_sort(), _bt_spooldestroy(), _h_spooldestroy(), ExecEndAgg(), ExecEndIncrementalSort(), ExecEndSort(), ExecReScanAgg(), ExecReScanSort(), gistbuild(), heapam_relation_copy_for_cluster(), initialize_aggregate(), initialize_phase(), ordered_set_shutdown(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), and validate_index().

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int nWorkers )

Definition at line 2955 of file tuplesort.c.

 {
     Size        tapesSize;
  
     Assert(nWorkers > 0);
  
     /* Make sure that BufFile shared state is MAXALIGN'd */
     tapesSize = mul_size(sizeof(TapeShare), nWorkers);
     tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
  
     return tapesSize;
 }

References add_size(), Assert(), MAXALIGN, and mul_size().

Referenced by _bt_begin_parallel().

◆ tuplesort_get_stats()

void tuplesort_get_stats	(	Tuplesortstate *	state,
		TuplesortInstrumentation *	stats
	)

Definition at line 2537 of file tuplesort.c.

 {
     /*
      * Note: it might seem we should provide both memory and disk usage for a
      * disk-based sort.  However, the current code doesn't track memory space
      * accurately once we have begun to return tuples to the caller (since we
      * don't account for pfree's the caller is expected to do), so we cannot
      * rely on availMem in a disk sort.  This does not seem worth the overhead
      * to fix.  Is it worth creating an API for the memory context code to
      * tell us how much is actually used in sortcontext?
      */
     tuplesort_updatemax(state);
  
     if (state->isMaxSpaceDisk)
         stats->spaceType = SORT_SPACE_TYPE_DISK;
     else
         stats->spaceType = SORT_SPACE_TYPE_MEMORY;
     stats->spaceUsed = (state->maxSpace + 1023) / 1024;
  
     switch (state->maxSpaceStatus)
     {
         case TSS_SORTEDINMEM:
             if (state->boundUsed)
                 stats->sortMethod = SORT_TYPE_TOP_N_HEAPSORT;
             else
                 stats->sortMethod = SORT_TYPE_QUICKSORT;
             break;
         case TSS_SORTEDONTAPE:
             stats->sortMethod = SORT_TYPE_EXTERNAL_SORT;
             break;
         case TSS_FINALMERGE:
             stats->sortMethod = SORT_TYPE_EXTERNAL_MERGE;
             break;
         default:
             stats->sortMethod = SORT_TYPE_STILL_IN_PROGRESS;
             break;
     }
 }

References SORT_SPACE_TYPE_DISK, SORT_SPACE_TYPE_MEMORY, SORT_TYPE_EXTERNAL_MERGE, SORT_TYPE_EXTERNAL_SORT, SORT_TYPE_QUICKSORT, SORT_TYPE_STILL_IN_PROGRESS, SORT_TYPE_TOP_N_HEAPSORT, TuplesortInstrumentation::sortMethod, TuplesortInstrumentation::spaceType, TuplesortInstrumentation::spaceUsed, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and tuplesort_updatemax().

Referenced by ExecSort(), instrumentSortedGroup(), and show_sort_info().

◆ tuplesort_getdatum()

bool tuplesort_getdatum	(	Tuplesortstate *	state,
		bool	forward,
		bool	copy,
		Datum *	val,
		bool *	isNull,
		Datum *	abbrev
	)

Definition at line 863 of file tuplesortvariants.c.

 {
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
     TuplesortDatumArg *arg = (TuplesortDatumArg *) base->arg;
     SortTuple   stup;
  
     if (!tuplesort_gettuple_common(state, forward, &stup))
     {
         MemoryContextSwitchTo(oldcontext);
         return false;
     }
  
     /* Ensure we copy into caller's memory context */
     MemoryContextSwitchTo(oldcontext);
  
     /* Record abbreviated key for caller */
     if (base->sortKeys->abbrev_converter && abbrev)
         *abbrev = stup.datum1;
  
     if (stup.isnull1 || !base->tuples)
     {
         *val = stup.datum1;
         *isNull = stup.isnull1;
     }
     else
     {
         /* use stup.tuple because stup.datum1 may be an abbreviation */
         if (copy)
             *val = datumCopy(PointerGetDatum(stup.tuple), false,
                              arg->datumTypeLen);
         else
             *val = PointerGetDatum(stup.tuple);
         *isNull = false;
     }
  
     return true;
 }

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, datumCopy(), if(), MemoryContextSwitchTo(), PointerGetDatum(), TuplesortPublic::sortcontext, TuplesortPublic::sortKeys, TuplesortPublic::tuples, tuplesort_gettuple_common(), TuplesortstateGetPublic, and val.

Referenced by ExecSort(), heapam_index_validate_scan(), mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), percentile_disc_multi_final(), and process_ordered_aggregate_single().

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 802 of file tuplesortvariants.c.

 {
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
     SortTuple   stup;
  
     if (!tuplesort_gettuple_common(state, forward, &stup))
         stup.tuple = NULL;
  
     MemoryContextSwitchTo(oldcontext);
  
     return stup.tuple;
 }

References MemoryContextSwitchTo(), TuplesortPublic::sortcontext, SortTuple::tuple, tuplesort_gettuple_common(), and TuplesortstateGetPublic.

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 823 of file tuplesortvariants.c.

 {
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
     SortTuple   stup;
  
     if (!tuplesort_gettuple_common(state, forward, &stup))
         stup.tuple = NULL;
  
     MemoryContextSwitchTo(oldcontext);
  
     return (IndexTuple) stup.tuple;
 }

References MemoryContextSwitchTo(), TuplesortPublic::sortcontext, SortTuple::tuple, tuplesort_gettuple_common(), and TuplesortstateGetPublic.

Referenced by _bt_load(), _h_indexbuild(), and gist_indexsortbuild().

◆ tuplesort_gettuple_common()

bool tuplesort_gettuple_common	(	Tuplesortstate *	state,
		bool	forward,
		SortTuple *	stup
	)

Definition at line 1496 of file tuplesort.c.

 {
     unsigned int tuplen;
     size_t      nmoved;
  
     Assert(!WORKER(state));
  
     switch (state->status)
     {
         case TSS_SORTEDINMEM:
             Assert(forward || state->base.sortopt & TUPLESORT_RANDOMACCESS);
             Assert(!state->slabAllocatorUsed);
             if (forward)
             {
                 if (state->current < state->memtupcount)
                 {
                     *stup = state->memtuples[state->current++];
                     return true;
                 }
                 state->eof_reached = true;
  
                 /*
                  * Complain if caller tries to retrieve more tuples than
                  * originally asked for in a bounded sort.  This is because
                  * returning EOF here might be the wrong thing.
                  */
                 if (state->bounded && state->current >= state->bound)
                     elog(ERROR, "retrieved too many tuples in a bounded sort");
  
                 return false;
             }
             else
             {
                 if (state->current <= 0)
                     return false;
  
                 /*
                  * if all tuples are fetched already then we return last
                  * tuple, else - tuple before last returned.
                  */
                 if (state->eof_reached)
                     state->eof_reached = false;
                 else
                 {
                     state->current--;   /* last returned tuple */
                     if (state->current <= 0)
                         return false;
                 }
                 *stup = state->memtuples[state->current - 1];
                 return true;
             }
             break;
  
         case TSS_SORTEDONTAPE:
             Assert(forward || state->base.sortopt & TUPLESORT_RANDOMACCESS);
             Assert(state->slabAllocatorUsed);
  
             /*
              * The slot that held the tuple that we returned in previous
              * gettuple call can now be reused.
              */
             if (state->lastReturnedTuple)
             {
                 RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
                 state->lastReturnedTuple = NULL;
             }
  
             if (forward)
             {
                 if (state->eof_reached)
                     return false;
  
                 if ((tuplen = getlen(state->result_tape, true)) != 0)
                 {
                     READTUP(state, stup, state->result_tape, tuplen);
  
                     /*
                      * Remember the tuple we return, so that we can recycle
                      * its memory on next call.  (This can be NULL, in the
                      * !state->tuples case).
                      */
                     state->lastReturnedTuple = stup->tuple;
  
                     return true;
                 }
                 else
                 {
                     state->eof_reached = true;
                     return false;
                 }
             }
  
             /*
              * Backward.
              *
              * if all tuples are fetched already then we return last tuple,
              * else - tuple before last returned.
              */
             if (state->eof_reached)
             {
                 /*
                  * Seek position is pointing just past the zero tuplen at the
                  * end of file; back up to fetch last tuple's ending length
                  * word.  If seek fails we must have a completely empty file.
                  */
                 nmoved = LogicalTapeBackspace(state->result_tape,
                                               2 * sizeof(unsigned int));
                 if (nmoved == 0)
                     return false;
                 else if (nmoved != 2 * sizeof(unsigned int))
                     elog(ERROR, "unexpected tape position");
                 state->eof_reached = false;
             }
             else
             {
                 /*
                  * Back up and fetch previously-returned tuple's ending length
                  * word.  If seek fails, assume we are at start of file.
                  */
                 nmoved = LogicalTapeBackspace(state->result_tape,
                                               sizeof(unsigned int));
                 if (nmoved == 0)
                     return false;
                 else if (nmoved != sizeof(unsigned int))
                     elog(ERROR, "unexpected tape position");
                 tuplen = getlen(state->result_tape, false);
  
                 /*
                  * Back up to get ending length word of tuple before it.
                  */
                 nmoved = LogicalTapeBackspace(state->result_tape,
                                               tuplen + 2 * sizeof(unsigned int));
                 if (nmoved == tuplen + sizeof(unsigned int))
                 {
                     /*
                      * We backed up over the previous tuple, but there was no
                      * ending length word before it.  That means that the prev
                      * tuple is the first tuple in the file.  It is now the
                      * next to read in forward direction (not obviously right,
                      * but that is what in-memory case does).
                      */
                     return false;
                 }
                 else if (nmoved != tuplen + 2 * sizeof(unsigned int))
                     elog(ERROR, "bogus tuple length in backward scan");
             }
  
             tuplen = getlen(state->result_tape, false);
  
             /*
              * Now we have the length of the prior tuple, back up and read it.
              * Note: READTUP expects we are positioned after the initial
              * length word of the tuple, so back up to that point.
              */
             nmoved = LogicalTapeBackspace(state->result_tape,
                                           tuplen);
             if (nmoved != tuplen)
                 elog(ERROR, "bogus tuple length in backward scan");
             READTUP(state, stup, state->result_tape, tuplen);
  
             /*
              * Remember the tuple we return, so that we can recycle its memory
              * on next call. (This can be NULL, in the Datum case).
              */
             state->lastReturnedTuple = stup->tuple;
  
             return true;
  
         case TSS_FINALMERGE:
             Assert(forward);
             /* We are managing memory ourselves, with the slab allocator. */
             Assert(state->slabAllocatorUsed);
  
             /*
              * The slab slot holding the tuple that we returned in previous
              * gettuple call can now be reused.
              */
             if (state->lastReturnedTuple)
             {
                 RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
                 state->lastReturnedTuple = NULL;
             }
  
             /*
              * This code should match the inner loop of mergeonerun().
              */
             if (state->memtupcount > 0)
             {
                 int         srcTapeIndex = state->memtuples[0].srctape;
                 LogicalTape *srcTape = state->inputTapes[srcTapeIndex];
                 SortTuple   newtup;
  
                 *stup = state->memtuples[0];
  
                 /*
                  * Remember the tuple we return, so that we can recycle its
                  * memory on next call. (This can be NULL, in the Datum case).
                  */
                 state->lastReturnedTuple = stup->tuple;
  
                 /*
                  * Pull next tuple from tape, and replace the returned tuple
                  * at top of the heap with it.
                  */
                 if (!mergereadnext(state, srcTape, &newtup))
                 {
                     /*
                      * If no more data, we've reached end of run on this tape.
                      * Remove the top node from the heap.
                      */
                     tuplesort_heap_delete_top(state);
                     state->nInputRuns--;
  
                     /*
                      * Close the tape.  It'd go away at the end of the sort
                      * anyway, but better to release the memory early.
                      */
                     LogicalTapeClose(srcTape);
                     return true;
                 }
                 newtup.srctape = srcTapeIndex;
                 tuplesort_heap_replace_top(state, &newtup);
                 return true;
             }
             return false;
  
         default:
             elog(ERROR, "invalid tuplesort state");
             return false;       /* keep compiler quiet */
     }
 }

References Assert(), elog(), ERROR, getlen(), LogicalTapeBackspace(), LogicalTapeClose(), mergereadnext(), READTUP, RELEASE_SLAB_SLOT, SortTuple::srctape, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, SortTuple::tuple, tuplesort_heap_delete_top(), tuplesort_heap_replace_top(), TUPLESORT_RANDOMACCESS, and WORKER.

Referenced by tuplesort_getdatum(), tuplesort_getheaptuple(), tuplesort_getindextuple(), tuplesort_gettupleslot(), and tuplesort_skiptuples().

◆ tuplesort_gettupleslot()

bool tuplesort_gettupleslot	(	Tuplesortstate *	state,
		bool	forward,
		bool	copy,
		TupleTableSlot *	slot,
		Datum *	abbrev
	)

Definition at line 764 of file tuplesortvariants.c.

 {
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
     SortTuple   stup;
  
     if (!tuplesort_gettuple_common(state, forward, &stup))
         stup.tuple = NULL;
  
     MemoryContextSwitchTo(oldcontext);
  
     if (stup.tuple)
     {
         /* Record abbreviated key for caller */
         if (base->sortKeys->abbrev_converter && abbrev)
             *abbrev = stup.datum1;
  
         if (copy)
             stup.tuple = heap_copy_minimal_tuple((MinimalTuple) stup.tuple);
  
         ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
         return true;
     }
     else
     {
         ExecClearTuple(slot);
         return false;
     }
 }

References SortSupportData::abbrev_converter, SortTuple::datum1, ExecClearTuple(), ExecStoreMinimalTuple(), heap_copy_minimal_tuple(), MemoryContextSwitchTo(), TuplesortPublic::sortcontext, TuplesortPublic::sortKeys, SortTuple::tuple, tuplesort_gettuple_common(), and TuplesortstateGetPublic.

Referenced by ExecIncrementalSort(), ExecSort(), fetch_input_tuple(), hypothetical_dense_rank_final(), hypothetical_rank_common(), process_ordered_aggregate_multi(), and switchToPresortedPrefixMode().

◆ tuplesort_initialize_shared()

void tuplesort_initialize_shared	(	Sharedsort *	shared,
		int	nWorkers,
		dsm_segment *	seg
	)

Definition at line 2976 of file tuplesort.c.

 {
     int         i;
  
     Assert(nWorkers > 0);
  
     SpinLockInit(&shared->mutex);
     shared->currentWorker = 0;
     shared->workersFinished = 0;
     SharedFileSetInit(&shared->fileset, seg);
     shared->nTapes = nWorkers;
     for (i = 0; i < nWorkers; i++)
     {
         shared->tapes[i].firstblocknumber = 0L;
     }
 }

References Assert(), Sharedsort::currentWorker, Sharedsort::fileset, TapeShare::firstblocknumber, i, Sharedsort::mutex, Sharedsort::nTapes, SharedFileSetInit(), SpinLockInit, Sharedsort::tapes, and Sharedsort::workersFinished.

Referenced by _bt_begin_parallel().

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate * state )

Definition at line 2473 of file tuplesort.c.

 {
     MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
  
     Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
  
     switch (state->status)
     {
         case TSS_SORTEDINMEM:
             state->markpos_offset = state->current;
             state->markpos_eof = state->eof_reached;
             break;
         case TSS_SORTEDONTAPE:
             LogicalTapeTell(state->result_tape,
                             &state->markpos_block,
                             &state->markpos_offset);
             state->markpos_eof = state->eof_reached;
             break;
         default:
             elog(ERROR, "invalid tuplesort state");
             break;
     }
  
     MemoryContextSwitchTo(oldcontext);
 }

References Assert(), elog(), ERROR, LogicalTapeTell(), MemoryContextSwitchTo(), TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and TUPLESORT_RANDOMACCESS.

Referenced by ExecSortMarkPos().

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64 allowedMem )

Definition at line 1804 of file tuplesort.c.

 {
     int         mOrder;
  
     /*----------
      * In the merge phase, we need buffer space for each input and output tape.
      * Each pass in the balanced merge algorithm reads from M input tapes, and
      * writes to N output tapes.  Each tape consumes TAPE_BUFFER_OVERHEAD bytes
      * of memory.  In addition to that, we want MERGE_BUFFER_SIZE workspace per
      * input tape.
      *
      * totalMem = M * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE) +
      *            N * TAPE_BUFFER_OVERHEAD
      *
      * Except for the last and next-to-last merge passes, where there can be
      * fewer tapes left to process, M = N.  We choose M so that we have the
      * desired amount of memory available for the input buffers
      * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE), given the total memory
      * available for the tape buffers (allowedMem).
      *
      * Note: you might be thinking we need to account for the memtuples[]
      * array in this calculation, but we effectively treat that as part of the
      * MERGE_BUFFER_SIZE workspace.
      *----------
      */
     mOrder = allowedMem /
         (2 * TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE);
  
     /*
      * Even in minimum memory, use at least a MINORDER merge.  On the other
      * hand, even when we have lots of memory, do not use more than a MAXORDER
      * merge.  Tapes are pretty cheap, but they're not entirely free.  Each
      * additional tape reduces the amount of memory available to build runs,
      * which in turn can cause the same sort to need more runs, which makes
      * merging slower even if it can still be done in a single pass.  Also,
      * high order merges are quite slow due to CPU cache effects; it can be
      * faster to pay the I/O cost of a multi-pass merge than to perform a
      * single merge pass across many hundreds of tapes.
      */
     mOrder = Max(mOrder, MINORDER);
     mOrder = Min(mOrder, MAXORDER);
  
     return mOrder;
 }

References Max, MAXORDER, MERGE_BUFFER_SIZE, Min, MINORDER, and TAPE_BUFFER_OVERHEAD.

Referenced by cost_tuplesort(), and inittapes().

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod m )

Definition at line 2581 of file tuplesort.c.

 {
     switch (m)
     {
         case SORT_TYPE_STILL_IN_PROGRESS:
             return "still in progress";
         case SORT_TYPE_TOP_N_HEAPSORT:
             return "top-N heapsort";
         case SORT_TYPE_QUICKSORT:
             return "quicksort";
         case SORT_TYPE_EXTERNAL_SORT:
             return "external sort";
         case SORT_TYPE_EXTERNAL_MERGE:
             return "external merge";
     }
  
     return "unknown";
 }

References SORT_TYPE_EXTERNAL_MERGE, SORT_TYPE_EXTERNAL_SORT, SORT_TYPE_QUICKSORT, SORT_TYPE_STILL_IN_PROGRESS, and SORT_TYPE_TOP_N_HEAPSORT.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate * state )

Definition at line 1385 of file tuplesort.c.

 {
     MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
  
 #ifdef TRACE_SORT
     if (trace_sort)
         elog(LOG, "performsort of worker %d starting: %s",
              state->worker, pg_rusage_show(&state->ru_start));
 #endif
  
     switch (state->status)
     {
         case TSS_INITIAL:
  
             /*
              * We were able to accumulate all the tuples within the allowed
              * amount of memory, or leader to take over worker tapes
              */
             if (SERIAL(state))
             {
                 /* Just qsort 'em and we're done */
                 tuplesort_sort_memtuples(state);
                 state->status = TSS_SORTEDINMEM;
             }
             else if (WORKER(state))
             {
                 /*
                  * Parallel workers must still dump out tuples to tape.  No
                  * merge is required to produce single output run, though.
                  */
                 inittapes(state, false);
                 dumptuples(state, true);
                 worker_nomergeruns(state);
                 state->status = TSS_SORTEDONTAPE;
             }
             else
             {
                 /*
                  * Leader will take over worker tapes and merge worker runs.
                  * Note that mergeruns sets the correct state->status.
                  */
                 leader_takeover_tapes(state);
                 mergeruns(state);
             }
             state->current = 0;
             state->eof_reached = false;
             state->markpos_block = 0L;
             state->markpos_offset = 0;
             state->markpos_eof = false;
             break;
  
         case TSS_BOUNDED:
  
             /*
              * We were able to accumulate all the tuples required for output
              * in memory, using a heap to eliminate excess tuples.  Now we
              * have to transform the heap to a properly-sorted array.
              */
             sort_bounded_heap(state);
             state->current = 0;
             state->eof_reached = false;
             state->markpos_offset = 0;
             state->markpos_eof = false;
             state->status = TSS_SORTEDINMEM;
             break;
  
         case TSS_BUILDRUNS:
  
             /*
              * Finish tape-based sort.  First, flush all tuples remaining in
              * memory out to tape; then merge until we have a single remaining
              * run (or, if !randomAccess and !WORKER(), one run per tape).
              * Note that mergeruns sets the correct state->status.
              */
             dumptuples(state, true);
             mergeruns(state);
             state->eof_reached = false;
             state->markpos_block = 0L;
             state->markpos_offset = 0;
             state->markpos_eof = false;
             break;
  
         default:
             elog(ERROR, "invalid tuplesort state");
             break;
     }
  
 #ifdef TRACE_SORT
     if (trace_sort)
     {
         if (state->status == TSS_FINALMERGE)
             elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
                  state->worker, state->nInputTapes,
                  pg_rusage_show(&state->ru_start));
         else
             elog(LOG, "performsort of worker %d done: %s",
                  state->worker, pg_rusage_show(&state->ru_start));
     }
 #endif
  
     MemoryContextSwitchTo(oldcontext);
 }

References dumptuples(), elog(), ERROR, inittapes(), leader_takeover_tapes(), LOG, MemoryContextSwitchTo(), mergeruns(), pg_rusage_show(), SERIAL, sort_bounded_heap(), trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_FINALMERGE, TSS_INITIAL, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, tuplesort_sort_memtuples(), WORKER, and worker_nomergeruns().

Referenced by _bt_leafbuild(), _bt_parallel_scan_and_sort(), _h_indexbuild(), ExecIncrementalSort(), ExecSort(), gistbuild(), heapam_relation_copy_for_cluster(), hypothetical_dense_rank_final(), hypothetical_rank_common(), initialize_phase(), mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), percentile_disc_multi_final(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), switchToPresortedPrefixMode(), and validate_index().

◆ tuplesort_putdatum()

void tuplesort_putdatum	(	Tuplesortstate *	state,
		Datum	val,
		bool	isNull
	)

Definition at line 700 of file tuplesortvariants.c.

 {
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
     TuplesortDatumArg *arg = (TuplesortDatumArg *) base->arg;
     SortTuple   stup;
  
     /*
      * Pass-by-value types or null values are just stored directly in
      * stup.datum1 (and stup.tuple is not used and set to NULL).
      *
      * Non-null pass-by-reference values need to be copied into memory we
      * control, and possibly abbreviated. The copied value is pointed to by
      * stup.tuple and is treated as the canonical copy (e.g. to return via
      * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
      * abbreviated value if abbreviation is happening, otherwise it's
      * identical to stup.tuple.
      */
  
     if (isNull || !base->tuples)
     {
         /*
          * Set datum1 to zeroed representation for NULLs (to be consistent,
          * and to support cheap inequality tests for NULL abbreviated keys).
          */
         stup.datum1 = !isNull ? val : (Datum) 0;
         stup.isnull1 = isNull;
         stup.tuple = NULL;      /* no separate storage */
     }
     else
     {
         stup.isnull1 = false;
         stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
         stup.tuple = DatumGetPointer(stup.datum1);
     }
  
     tuplesort_puttuple_common(state, &stup,
                               base->tuples &&
                               base->sortKeys->abbrev_converter && !isNull);
  
     MemoryContextSwitchTo(oldcontext);
 }

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, datumCopy(), DatumGetPointer(), if(), MemoryContextSwitchTo(), TuplesortPublic::sortKeys, TuplesortPublic::tuplecontext, TuplesortPublic::tuples, tuplesort_puttuple_common(), TuplesortstateGetPublic, and val.

Referenced by ExecEvalAggOrderedTransDatum(), ExecSort(), ordered_set_transition(), and validate_index_callback().

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple	(	Tuplesortstate *	state,
		HeapTuple	tup
	)

Definition at line 633 of file tuplesortvariants.c.

 {
     SortTuple   stup;
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
     TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
  
     /* copy the tuple into sort storage */
     tup = heap_copytuple(tup);
     stup.tuple = (void *) tup;
  
     /*
      * set up first-column key value, and potentially abbreviate, if it's a
      * simple column
      */
     if (base->haveDatum1)
     {
         stup.datum1 = heap_getattr(tup,
                                    arg->indexInfo->ii_IndexAttrNumbers[0],
                                    arg->tupDesc,
                                    &stup.isnull1);
     }
  
     tuplesort_puttuple_common(state, &stup,
                               base->haveDatum1 &&
                               base->sortKeys->abbrev_converter &&
                               !stup.isnull1);
  
     MemoryContextSwitchTo(oldcontext);
 }

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, SortTuple::datum1, TuplesortPublic::haveDatum1, heap_copytuple(), heap_getattr(), SortTuple::isnull1, MemoryContextSwitchTo(), TuplesortPublic::sortKeys, SortTuple::tuple, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), and TuplesortstateGetPublic.

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_putindextuplevalues()

void tuplesort_putindextuplevalues	(	Tuplesortstate *	state,
		Relation	rel,
		ItemPointer	self,
		Datum *	values,
		bool *	isnull
	)

Definition at line 669 of file tuplesortvariants.c.

 {
     SortTuple   stup;
     IndexTuple  tuple;
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     TuplesortIndexArg *arg = (TuplesortIndexArg *) base->arg;
  
     stup.tuple = index_form_tuple_context(RelationGetDescr(rel), values,
                                           isnull, base->tuplecontext);
     tuple = ((IndexTuple) stup.tuple);
     tuple->t_tid = *self;
     /* set up first-column key value */
     stup.datum1 = index_getattr(tuple,
                                 1,
                                 RelationGetDescr(arg->indexRel),
                                 &stup.isnull1);
  
     tuplesort_puttuple_common(state, &stup,
                               base->sortKeys &&
                               base->sortKeys->abbrev_converter &&
                               !stup.isnull1);
 }

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, SortTuple::datum1, index_form_tuple_context(), index_getattr(), SortTuple::isnull1, RelationGetDescr, TuplesortPublic::sortKeys, IndexTupleData::t_tid, SortTuple::tuple, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), TuplesortstateGetPublic, and values.

Referenced by _bt_spool(), _h_spool(), and gistSortedBuildCallback().

◆ tuplesort_puttuple_common()

void tuplesort_puttuple_common	(	Tuplesortstate *	state,
		SortTuple *	tuple,
		bool	useAbbrev
	)

Definition at line 1190 of file tuplesort.c.

 {
     MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
  
     Assert(!LEADER(state));
  
     /* Count the size of the out-of-line data */
     if (tuple->tuple != NULL)
         USEMEM(state, GetMemoryChunkSpace(tuple->tuple));
  
     if (!useAbbrev)
     {
         /*
          * Leave ordinary Datum representation, or NULL value.  If there is a
          * converter it won't expect NULL values, and cost model is not
          * required to account for NULL, so in that case we avoid calling
          * converter and just set datum1 to zeroed representation (to be
          * consistent, and to support cheap inequality tests for NULL
          * abbreviated keys).
          */
     }
     else if (!consider_abort_common(state))
     {
         /* Store abbreviated key representation */
         tuple->datum1 = state->base.sortKeys->abbrev_converter(tuple->datum1,
                                                                state->base.sortKeys);
     }
     else
     {
         /*
          * Set state to be consistent with never trying abbreviation.
          *
          * Alter datum1 representation in already-copied tuples, so as to
          * ensure a consistent representation (current tuple was just
          * handled).  It does not matter if some dumped tuples are already
          * sorted on tape, since serialized tuples lack abbreviated keys
          * (TSS_BUILDRUNS state prevents control reaching here in any case).
          */
         REMOVEABBREV(state, state->memtuples, state->memtupcount);
     }
  
     switch (state->status)
     {
         case TSS_INITIAL:
  
             /*
              * Save the tuple into the unsorted array.  First, grow the array
              * as needed.  Note that we try to grow the array when there is
              * still one free slot remaining --- if we fail, there'll still be
              * room to store the incoming tuple, and then we'll switch to
              * tape-based operation.
              */
             if (state->memtupcount >= state->memtupsize - 1)
             {
                 (void) grow_memtuples(state);
                 Assert(state->memtupcount < state->memtupsize);
             }
             state->memtuples[state->memtupcount++] = *tuple;
  
             /*
              * Check if it's time to switch over to a bounded heapsort. We do
              * so if the input tuple count exceeds twice the desired tuple
              * count (this is a heuristic for where heapsort becomes cheaper
              * than a quicksort), or if we've just filled workMem and have
              * enough tuples to meet the bound.
              *
              * Note that once we enter TSS_BOUNDED state we will always try to
              * complete the sort that way.  In the worst case, if later input
              * tuples are larger than earlier ones, this might cause us to
              * exceed workMem significantly.
              */
             if (state->bounded &&
                 (state->memtupcount > state->bound * 2 ||
                  (state->memtupcount > state->bound && LACKMEM(state))))
             {
 #ifdef TRACE_SORT
                 if (trace_sort)
                     elog(LOG, "switching to bounded heapsort at %d tuples: %s",
                          state->memtupcount,
                          pg_rusage_show(&state->ru_start));
 #endif
                 make_bounded_heap(state);
                 MemoryContextSwitchTo(oldcontext);
                 return;
             }
  
             /*
              * Done if we still fit in available memory and have array slots.
              */
             if (state->memtupcount < state->memtupsize && !LACKMEM(state))
             {
                 MemoryContextSwitchTo(oldcontext);
                 return;
             }
  
             /*
              * Nope; time to switch to tape-based operation.
              */
             inittapes(state, true);
  
             /*
              * Dump all tuples.
              */
             dumptuples(state, false);
             break;
  
         case TSS_BOUNDED:
  
             /*
              * We don't want to grow the array here, so check whether the new
              * tuple can be discarded before putting it in.  This should be a
              * good speed optimization, too, since when there are many more
              * input tuples than the bound, most input tuples can be discarded
              * with just this one comparison.  Note that because we currently
              * have the sort direction reversed, we must check for <= not >=.
              */
             if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
             {
                 /* new tuple <= top of the heap, so we can discard it */
                 free_sort_tuple(state, tuple);
                 CHECK_FOR_INTERRUPTS();
             }
             else
             {
                 /* discard top of heap, replacing it with the new tuple */
                 free_sort_tuple(state, &state->memtuples[0]);
                 tuplesort_heap_replace_top(state, tuple);
             }
             break;
  
         case TSS_BUILDRUNS:
  
             /*
              * Save the tuple into the unsorted array (there must be space)
              */
             state->memtuples[state->memtupcount++] = *tuple;
  
             /*
              * If we are over the memory limit, dump all tuples.
              */
             dumptuples(state, false);
             break;
  
         default:
             elog(ERROR, "invalid tuplesort state");
             break;
     }
     MemoryContextSwitchTo(oldcontext);
 }

References Assert(), CHECK_FOR_INTERRUPTS, COMPARETUP, consider_abort_common(), SortTuple::datum1, dumptuples(), elog(), ERROR, free_sort_tuple(), GetMemoryChunkSpace(), grow_memtuples(), inittapes(), LACKMEM, LEADER, LOG, make_bounded_heap(), MemoryContextSwitchTo(), pg_rusage_show(), REMOVEABBREV, trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_INITIAL, SortTuple::tuple, tuplesort_heap_replace_top(), and USEMEM.

Referenced by tuplesort_putdatum(), tuplesort_putheaptuple(), tuplesort_putindextuplevalues(), and tuplesort_puttupleslot().

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot	(	Tuplesortstate *	state,
		TupleTableSlot *	slot
	)

Definition at line 600 of file tuplesortvariants.c.

 {
     TuplesortPublic *base = TuplesortstateGetPublic(state);
     MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
     TupleDesc   tupDesc = (TupleDesc) base->arg;
     SortTuple   stup;
     MinimalTuple tuple;
     HeapTupleData htup;
  
     /* copy the tuple into sort storage */
     tuple = ExecCopySlotMinimalTuple(slot);
     stup.tuple = (void *) tuple;
     /* set up first-column key value */
     htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
     htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
     stup.datum1 = heap_getattr(&htup,
                                base->sortKeys[0].ssup_attno,
                                tupDesc,
                                &stup.isnull1);
  
     tuplesort_puttuple_common(state, &stup,
                               base->sortKeys->abbrev_converter &&
                               !stup.isnull1);
  
     MemoryContextSwitchTo(oldcontext);
 }

References SortSupportData::abbrev_converter, TuplesortPublic::arg, ExecCopySlotMinimalTuple(), heap_getattr(), MemoryContextSwitchTo(), MINIMAL_TUPLE_OFFSET, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, MinimalTupleData::t_len, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), and TuplesortstateGetPublic.

Referenced by ExecEvalAggOrderedTransTuple(), ExecIncrementalSort(), ExecSort(), fetch_input_tuple(), hypothetical_dense_rank_final(), hypothetical_rank_common(), ordered_set_transition_multi(), and switchToPresortedPrefixMode().

◆ tuplesort_readtup_alloc()

void* tuplesort_readtup_alloc	(	Tuplesortstate *	state,
		Size	tuplen
	)

Definition at line 2921 of file tuplesort.c.

 {
     SlabSlot   *buf;
  
     /*
      * We pre-allocate enough slots in the slab arena that we should never run
      * out.
      */
     Assert(state->slabFreeHead);
  
     if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
         return MemoryContextAlloc(state->base.sortcontext, tuplen);
     else
     {
         buf = state->slabFreeHead;
         /* Reuse this slot */
         state->slabFreeHead = buf->nextfree;
  
         return buf;
     }
 }

References Assert(), buf, MemoryContextAlloc(), and SLAB_SLOT_SIZE.

Referenced by readtup_cluster(), readtup_datum(), readtup_heap(), and readtup_index().

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate * state )

Definition at line 2440 of file tuplesort.c.

 {
     MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
  
     Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
  
     switch (state->status)
     {
         case TSS_SORTEDINMEM:
             state->current = 0;
             state->eof_reached = false;
             state->markpos_offset = 0;
             state->markpos_eof = false;
             break;
         case TSS_SORTEDONTAPE:
             LogicalTapeRewindForRead(state->result_tape, 0);
             state->eof_reached = false;
             state->markpos_block = 0L;
             state->markpos_offset = 0;
             state->markpos_eof = false;
             break;
         default:
             elog(ERROR, "invalid tuplesort state");
             break;
     }
  
     MemoryContextSwitchTo(oldcontext);
 }

References Assert(), elog(), ERROR, LogicalTapeRewindForRead(), MemoryContextSwitchTo(), TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and TUPLESORT_RANDOMACCESS.

Referenced by ExecReScanSort(), mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), and percentile_disc_multi_final().

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate * state )

Definition at line 1040 of file tuplesort.c.

 {
     tuplesort_updatemax(state);
     tuplesort_free(state);
  
     /*
      * After we've freed up per-batch memory, re-setup all of the state common
      * to both the first batch and any subsequent batch.
      */
     tuplesort_begin_batch(state);
  
     state->lastReturnedTuple = NULL;
     state->slabMemoryBegin = NULL;
     state->slabMemoryEnd = NULL;
     state->slabFreeHead = NULL;
 }

References tuplesort_begin_batch(), tuplesort_free(), and tuplesort_updatemax().

Referenced by ExecIncrementalSort(), ExecReScanIncrementalSort(), and switchToPresortedPrefixMode().

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate * state )

Definition at line 2504 of file tuplesort.c.

 {
     MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
  
     Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
  
     switch (state->status)
     {
         case TSS_SORTEDINMEM:
             state->current = state->markpos_offset;
             state->eof_reached = state->markpos_eof;
             break;
         case TSS_SORTEDONTAPE:
             LogicalTapeSeek(state->result_tape,
                             state->markpos_block,
                             state->markpos_offset);
             state->eof_reached = state->markpos_eof;
             break;
         default:
             elog(ERROR, "invalid tuplesort state");
             break;
     }
  
     MemoryContextSwitchTo(oldcontext);
 }

References Assert(), elog(), ERROR, LogicalTapeSeek(), MemoryContextSwitchTo(), TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and TUPLESORT_RANDOMACCESS.

Referenced by ExecSortRestrPos().

◆ tuplesort_set_bound()

void tuplesort_set_bound	(	Tuplesortstate *	state,
		int64	bound
	)

Definition at line 844 of file tuplesort.c.

 {
     /* Assert we're called before loading any tuples */
     Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
     /* Assert we allow bounded sorts */
     Assert(state->base.sortopt & TUPLESORT_ALLOWBOUNDED);
     /* Can't set the bound twice, either */
     Assert(!state->bounded);
     /* Also, this shouldn't be called in a parallel worker */
     Assert(!WORKER(state));
  
     /* Parallel leader allows but ignores hint */
     if (LEADER(state))
         return;
  
 #ifdef DEBUG_BOUNDED_SORT
     /* Honor GUC setting that disables the feature (for easy testing) */
     if (!optimize_bounded_sort)
         return;
 #endif
  
     /* We want to be able to compute bound * 2, so limit the setting */
     if (bound > (int64) (INT_MAX / 2))
         return;
  
     state->bounded = true;
     state->bound = (int) bound;
  
     /*
      * Bounded sorts are not an effective target for abbreviated key
      * optimization.  Disable by setting state to be consistent with no
      * abbreviation support.
      */
     state->base.sortKeys->abbrev_converter = NULL;
     if (state->base.sortKeys->abbrev_full_comparator)
         state->base.sortKeys->comparator = state->base.sortKeys->abbrev_full_comparator;
  
     /* Not strictly necessary, but be tidy */
     state->base.sortKeys->abbrev_abort = NULL;
     state->base.sortKeys->abbrev_full_comparator = NULL;
 }

References Assert(), LEADER, TSS_INITIAL, TUPLESORT_ALLOWBOUNDED, and WORKER.

Referenced by ExecIncrementalSort(), ExecSort(), and switchToPresortedPrefixMode().

◆ tuplesort_skiptuples()

bool tuplesort_skiptuples	(	Tuplesortstate *	state,
		int64	ntuples,
		bool	forward
	)

Definition at line 1736 of file tuplesort.c.

 {
     MemoryContext oldcontext;
  
     /*
      * We don't actually support backwards skip yet, because no callers need
      * it.  The API is designed to allow for that later, though.
      */
     Assert(forward);
     Assert(ntuples >= 0);
     Assert(!WORKER(state));
  
     switch (state->status)
     {
         case TSS_SORTEDINMEM:
             if (state->memtupcount - state->current >= ntuples)
             {
                 state->current += ntuples;
                 return true;
             }
             state->current = state->memtupcount;
             state->eof_reached = true;
  
             /*
              * Complain if caller tries to retrieve more tuples than
              * originally asked for in a bounded sort.  This is because
              * returning EOF here might be the wrong thing.
              */
             if (state->bounded && state->current >= state->bound)
                 elog(ERROR, "retrieved too many tuples in a bounded sort");
  
             return false;
  
         case TSS_SORTEDONTAPE:
         case TSS_FINALMERGE:
  
             /*
              * We could probably optimize these cases better, but for now it's
              * not worth the trouble.
              */
             oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
             while (ntuples-- > 0)
             {
                 SortTuple   stup;
  
                 if (!tuplesort_gettuple_common(state, forward, &stup))
                 {
                     MemoryContextSwitchTo(oldcontext);
                     return false;
                 }
                 CHECK_FOR_INTERRUPTS();
             }
             MemoryContextSwitchTo(oldcontext);
             return true;
  
         default:
             elog(ERROR, "invalid tuplesort state");
             return false;       /* keep compiler quiet */
     }
 }

References Assert(), CHECK_FOR_INTERRUPTS, elog(), ERROR, MemoryContextSwitchTo(), TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, tuplesort_gettuple_common(), and WORKER.

Referenced by percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), and percentile_disc_multi_final().

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType t )

Definition at line 2604 of file tuplesort.c.

 {
     Assert(t == SORT_SPACE_TYPE_DISK || t == SORT_SPACE_TYPE_MEMORY);
     return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
 }

References Assert(), SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate * state )

Definition at line 892 of file tuplesort.c.

 {
     return state->boundUsed;
 }

Referenced by ExecIncrementalSort().

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ LogicalTapeReadExact

◆ NUM_TUPLESORTMETHODS

◆ PARALLEL_SORT

◆ TUPLESORT_ALLOWBOUNDED

◆ TUPLESORT_NONE

◆ TUPLESORT_RANDOMACCESS

◆ TuplesortstateGetPublic

Typedef Documentation

◆ Sharedsort

◆ SortCoordinate

◆ SortCoordinateData

◆ SortTupleComparator

◆ TuplesortInstrumentation

◆ Tuplesortstate

Enumeration Type Documentation

◆ TuplesortMethod

◆ TuplesortSpaceType

Function Documentation

◆ tuplesort_attach_shared()

◆ tuplesort_begin_cluster()

◆ tuplesort_begin_common()

◆ tuplesort_begin_datum()

◆ tuplesort_begin_heap()

◆ tuplesort_begin_index_btree()

◆ tuplesort_begin_index_gist()

◆ tuplesort_begin_index_hash()

◆ tuplesort_end()

◆ tuplesort_estimate_shared()

◆ tuplesort_get_stats()

◆ tuplesort_getdatum()

◆ tuplesort_getheaptuple()

◆ tuplesort_getindextuple()

◆ tuplesort_gettuple_common()

◆ tuplesort_gettupleslot()

◆ tuplesort_initialize_shared()

◆ tuplesort_markpos()

◆ tuplesort_merge_order()

◆ tuplesort_method_name()

◆ tuplesort_performsort()

◆ tuplesort_putdatum()

◆ tuplesort_putheaptuple()

◆ tuplesort_putindextuplevalues()

◆ tuplesort_puttuple_common()

◆ tuplesort_puttupleslot()

◆ tuplesort_readtup_alloc()

◆ tuplesort_rescan()

◆ tuplesort_reset()

◆ tuplesort_restorepos()

◆ tuplesort_set_bound()

◆ tuplesort_skiptuples()

◆ tuplesort_space_type_name()

◆ tuplesort_used_bound()