tuplesort.h File Reference

#include "access/brin_tuple.h"
#include "access/gin_tuple.h"
#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	TupleSortUseBumpTupleCxt(opt)   (((opt) & TUPLESORT_ALLOWBOUNDED) == 0)
#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, Size tuplen)
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_index_brin (int workMem, SortCoordinate coordinate, int sortopt)
Tuplesortstate *	tuplesort_begin_index_gin (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, const Datum *values, const bool *isnull)
void	tuplesort_putbrintuple (Tuplesortstate *state, BrinTuple *tuple, Size size)
void	tuplesort_putgintuple (Tuplesortstate *state, GinTuple *tuple, Size size)
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)
BrinTuple *	tuplesort_getbrintuple (Tuplesortstate *state, Size *len, bool forward)
GinTuple *	tuplesort_getgintuple (Tuplesortstate *state, Size *len, 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 263 of file tuplesort.h.

NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS   4

Definition at line 85 of file tuplesort.h.

PARALLEL_SORT

#define PARALLEL_SORT

(

coordinate

)

Value:

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

Definition at line 256 of file tuplesort.h.

TUPLESORT_ALLOWBOUNDED

#define TUPLESORT_ALLOWBOUNDED   (1 << 1)

Definition at line 100 of file tuplesort.h.

TUPLESORT_NONE

#define TUPLESORT_NONE   0

Definition at line 94 of file tuplesort.h.

TUPLESORT_RANDOMACCESS

#define TUPLESORT_RANDOMACCESS   (1 << 0)

Definition at line 97 of file tuplesort.h.

TuplesortstateGetPublic

#define TuplesortstateGetPublic

(

state

)

((TuplesortPublic *) state)

Definition at line 260 of file tuplesort.h.

TupleSortUseBumpTupleCxt

#define TupleSortUseBumpTupleCxt

(

opt

)

(((opt) & TUPLESORT_ALLOWBOUNDED) == 0)

Definition at line 109 of file tuplesort.h.

Typedef Documentation

Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 39 of file tuplesort.h.

SortCoordinate

typedef struct SortCoordinateData* SortCoordinate

Definition at line 62 of file tuplesort.h.

SortCoordinateData

typedef struct SortCoordinateData SortCoordinateData

SortTupleComparator

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

Definition at line 156 of file tuplesort.h.

TuplesortInstrumentation

typedef struct TuplesortInstrumentation TuplesortInstrumentation

Tuplesortstate

typedef struct Tuplesortstate Tuplesortstate

Definition at line 38 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 76 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 87 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 2961 of file tuplesort.c.

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

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _brin_parallel_build_main(), _bt_parallel_build_main(), and _gin_parallel_build_main().

tuplesort_begin_cluster()

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

Definition at line 251 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));
 
    if (trace_sort)
        elog(LOG,
             "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
             RelationGetNumberOfAttributes(indexRel),
             workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 
    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->comparetup_tiebreak = comparetup_cluster_tiebreak;
    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;
        bool        reverse;
 
        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);
 
        reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
 
        PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
    }
 
    pfree(indexScanKey);
 
    MemoryContextSwitchTo(oldcontext);
 
    return state;
}

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), BuildIndexInfo(), CLUSTER_SORT, TuplesortPublic::comparetup, comparetup_cluster(), comparetup_cluster_tiebreak(), TuplesortPublic::comparetup_tiebreak, 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 642 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));
 
    if (trace_sort)
        pg_rusage_init(&state->ru_start);
 
    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_brin(), tuplesort_begin_index_btree(), tuplesort_begin_index_gin(), 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 651 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));
 
    if (trace_sort)
        elog(LOG,
             "begin datum sort: workMem = %d, randomAccess = %c",
             workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 
    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->comparetup_tiebreak = comparetup_datum_tiebreak;
    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(), comparetup_datum_tiebreak(), TuplesortPublic::comparetup_tiebreak, 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 178 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);
 
    if (trace_sort)
        elog(LOG,
             "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
             nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 
    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->comparetup_tiebreak = comparetup_heap_tiebreak;
    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(), comparetup_heap_tiebreak(), TuplesortPublic::comparetup_tiebreak, 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_brin()

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

Definition at line 553 of file tuplesortvariants.c.

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   sortopt);
    TuplesortPublic *base = TuplesortstateGetPublic(state);
 
    if (trace_sort)
        elog(LOG,
             "begin index sort: workMem = %d, randomAccess = %c",
             workMem,
             sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 
    base->nKeys = 1;            /* Only one sort column, the block number */
 
    base->removeabbrev = removeabbrev_index_brin;
    base->comparetup = comparetup_index_brin;
    base->writetup = writetup_index_brin;
    base->readtup = readtup_index_brin;
    base->haveDatum1 = true;
    base->arg = NULL;
 
    return state;
}

References TuplesortPublic::arg, TuplesortPublic::comparetup, comparetup_index_brin(), elog, TuplesortPublic::haveDatum1, LOG, TuplesortPublic::nKeys, TuplesortPublic::readtup, readtup_index_brin(), TuplesortPublic::removeabbrev, removeabbrev_index_brin(), trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index_brin().

Referenced by _brin_parallel_scan_and_build(), and brinbuild().

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 357 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));
 
    if (trace_sort)
        elog(LOG,
             "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
             enforceUnique ? 't' : 'f',
             workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 
    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->comparetup_tiebreak = comparetup_index_btree_tiebreak;
    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;
        bool        reverse;
 
        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);
 
        reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
 
        PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
    }
 
    pfree(indexScanKey);
 
    MemoryContextSwitchTo(oldcontext);
 
    return state;
}

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_index_btree(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, 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_gin()

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

Definition at line 580 of file tuplesortvariants.c.

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   sortopt);
    TuplesortPublic *base = TuplesortstateGetPublic(state);
    MemoryContext oldcontext;
    int         i;
    TupleDesc   desc = RelationGetDescr(indexRel);
 
    oldcontext = MemoryContextSwitchTo(base->maincontext);
 
#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG,
             "begin index sort: workMem = %d, randomAccess = %c",
             workMem,
             sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
#endif
 
    /*
     * Multi-column GIN indexes expand the row into a separate index entry for
     * attribute, and that's what we write into the tuplesort. But we still
     * need to initialize sortsupport for all the attributes.
     */
    base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
 
    /* 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;
        Form_pg_attribute att = TupleDescAttr(desc, i);
        TypeCacheEntry *typentry;
 
        sortKey->ssup_cxt = CurrentMemoryContext;
        sortKey->ssup_collation = indexRel->rd_indcollation[i];
        sortKey->ssup_nulls_first = false;
        sortKey->ssup_attno = i + 1;
        sortKey->abbreviate = false;
 
        Assert(sortKey->ssup_attno != 0);
 
        if (!OidIsValid(sortKey->ssup_collation))
            sortKey->ssup_collation = DEFAULT_COLLATION_OID;
 
        /*
         * Look for a ordering for the index key data type, and then the sort
         * support function.
         */
        typentry = lookup_type_cache(att->atttypid, TYPECACHE_LT_OPR);
        PrepareSortSupportFromOrderingOp(typentry->lt_opr, sortKey);
    }
 
    base->removeabbrev = removeabbrev_index_gin;
    base->comparetup = comparetup_index_gin;
    base->writetup = writetup_index_gin;
    base->readtup = readtup_index_gin;
    base->haveDatum1 = false;
    base->arg = NULL;
 
    MemoryContextSwitchTo(oldcontext);
 
    return state;
}

References SortSupportData::abbreviate, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_index_gin(), CurrentMemoryContext, elog, TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, lookup_type_cache(), TypeCacheEntry::lt_opr, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, OidIsValid, palloc0(), PrepareSortSupportFromOrderingOp(), RelationData::rd_indcollation, TuplesortPublic::readtup, readtup_index_gin(), RelationGetDescr, TuplesortPublic::removeabbrev, removeabbrev_index_gin(), TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TupleDescAttr(), tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TYPECACHE_LT_OPR, TuplesortPublic::writetup, and writetup_index_gin().

Referenced by _gin_parallel_scan_and_build(), and ginbuild().

tuplesort_begin_index_gist()

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

Definition at line 490 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));
 
    if (trace_sort)
        elog(LOG,
             "begin index sort: workMem = %d, randomAccess = %c",
             workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
 
    base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
 
    base->removeabbrev = removeabbrev_index;
    base->comparetup = comparetup_index_btree;
    base->comparetup_tiebreak = comparetup_index_btree_tiebreak;
    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(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, 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 439 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));
 
    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');
 
    base->nKeys = 1;            /* Only one sort column, the hash code */
 
    base->removeabbrev = removeabbrev_index;
    base->comparetup = comparetup_index_hash;
    base->comparetup_tiebreak = comparetup_index_hash_tiebreak;
    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(), comparetup_index_hash_tiebreak(), TuplesortPublic::comparetup_tiebreak, 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 951 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 _brin_parallel_merge(), _brin_parallel_scan_and_build(), _bt_parallel_scan_and_sort(), _bt_spooldestroy(), _gin_parallel_merge(), _gin_parallel_scan_and_build(), _gin_process_worker_data(), _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 2917 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 _brin_begin_parallel(), _bt_begin_parallel(), and _gin_begin_parallel().

tuplesort_get_stats()

void tuplesort_get_stats	(	Tuplesortstate *	state,
		TuplesortInstrumentation *	stats
	)

Definition at line 2499 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_getbrintuple()

BrinTuple * tuplesort_getbrintuple	(	Tuplesortstate *	state,
		Size *	len,
		bool	forward
	)

Definition at line 1066 of file tuplesortvariants.c.

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

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

Referenced by _brin_parallel_merge().

tuplesort_getdatum()

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

Definition at line 1137 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_getgintuple()

GinTuple * tuplesort_getgintuple	(	Tuplesortstate *	state,
		Size *	len,
		bool	forward
	)

Definition at line 1089 of file tuplesortvariants.c.

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

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

Referenced by _gin_parallel_merge(), and _gin_process_worker_data().

tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 1024 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 1045 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 1470 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_getbrintuple(), tuplesort_getdatum(), tuplesort_getgintuple(), 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 986 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 2938 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 _brin_begin_parallel(), _bt_begin_parallel(), and _gin_begin_parallel().

tuplesort_markpos()

void tuplesort_markpos

(

Tuplesortstate *

state

)

Definition at line 2435 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 1778 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 2543 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 1363 of file tuplesort.c.

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
 
    if (trace_sort)
        elog(LOG, "performsort of worker %d starting: %s",
             state->worker, pg_rusage_show(&state->ru_start));
 
    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. Note
             * that sort_bounded_heap sets the correct state->status.
             */
            sort_bounded_heap(state);
            state->current = 0;
            state->eof_reached = false;
            state->markpos_offset = 0;
            state->markpos_eof = false;
            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;
    }
 
    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));
    }
 
    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 _brin_parallel_merge(), _brin_parallel_scan_and_build(), _bt_leafbuild(), _bt_parallel_scan_and_sort(), _gin_parallel_merge(), _gin_parallel_scan_and_build(), _gin_process_worker_data(), _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_putbrintuple()

void tuplesort_putbrintuple	(	Tuplesortstate *	state,
		BrinTuple *	tuple,
		Size	size
	)

Definition at line 853 of file tuplesortvariants.c.

{
    SortTuple   stup;
    BrinSortTuple *bstup;
    TuplesortPublic *base = TuplesortstateGetPublic(state);
    MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
    Size        tuplen;
 
    /* allocate space for the whole BRIN sort tuple */
    bstup = palloc(BRINSORTTUPLE_SIZE(size));
 
    bstup->tuplen = size;
    memcpy(&bstup->tuple, tuple, size);
 
    stup.tuple = bstup;
    stup.datum1 = tuple->bt_blkno;
    stup.isnull1 = false;
 
    /* GetMemoryChunkSpace is not supported for bump contexts */
    if (TupleSortUseBumpTupleCxt(base->sortopt))
        tuplen = MAXALIGN(BRINSORTTUPLE_SIZE(size));
    else
        tuplen = GetMemoryChunkSpace(bstup);
 
    tuplesort_puttuple_common(state, &stup,
                              base->sortKeys &&
                              base->sortKeys->abbrev_converter &&
                              !stup.isnull1, tuplen);
 
    MemoryContextSwitchTo(oldcontext);
}

References SortSupportData::abbrev_converter, BRINSORTTUPLE_SIZE, BrinTuple::bt_blkno, SortTuple::datum1, GetMemoryChunkSpace(), SortTuple::isnull1, MAXALIGN, MemoryContextSwitchTo(), palloc(), TuplesortPublic::sortKeys, TuplesortPublic::sortopt, BrinSortTuple::tuple, SortTuple::tuple, TuplesortPublic::tuplecontext, BrinSortTuple::tuplen, tuplesort_puttuple_common(), TuplesortstateGetPublic, and TupleSortUseBumpTupleCxt.

Referenced by form_and_spill_tuple().

tuplesort_putdatum()

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

Definition at line 922 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, 0);
 
    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_putgintuple()

void tuplesort_putgintuple	(	Tuplesortstate *	state,
		GinTuple *	tuple,
		Size	size
	)

Definition at line 886 of file tuplesortvariants.c.

{
    SortTuple   stup;
    GinTuple   *ctup;
    TuplesortPublic *base = TuplesortstateGetPublic(state);
    MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
    Size        tuplen;
 
    /* copy the GinTuple into the right memory context */
    ctup = palloc(size);
    memcpy(ctup, tuple, size);
 
    stup.tuple = ctup;
    stup.datum1 = (Datum) 0;
    stup.isnull1 = false;
 
    /* GetMemoryChunkSpace is not supported for bump contexts */
    if (TupleSortUseBumpTupleCxt(base->sortopt))
        tuplen = MAXALIGN(size);
    else
        tuplen = GetMemoryChunkSpace(ctup);
 
    tuplesort_puttuple_common(state, &stup,
                              base->sortKeys &&
                              base->sortKeys->abbrev_converter &&
                              !stup.isnull1, tuplen);
 
    MemoryContextSwitchTo(oldcontext);
}

References SortSupportData::abbrev_converter, SortTuple::datum1, GetMemoryChunkSpace(), SortTuple::isnull1, MAXALIGN, MemoryContextSwitchTo(), palloc(), TuplesortPublic::sortKeys, TuplesortPublic::sortopt, SortTuple::tuple, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), TuplesortstateGetPublic, and TupleSortUseBumpTupleCxt.

Referenced by _gin_process_worker_data(), and ginFlushBuildState().

tuplesort_putheaptuple()

void tuplesort_putheaptuple	(	Tuplesortstate *	state,
		HeapTuple	tup
	)

Definition at line 774 of file tuplesortvariants.c.

{
    SortTuple   stup;
    TuplesortPublic *base = TuplesortstateGetPublic(state);
    MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
    TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
    Size        tuplen;
 
    /* copy the tuple into sort storage */
    tup = heap_copytuple(tup);
    stup.tuple = 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);
    }
 
    /* GetMemoryChunkSpace is not supported for bump contexts */
    if (TupleSortUseBumpTupleCxt(base->sortopt))
        tuplen = MAXALIGN(HEAPTUPLESIZE + tup->t_len);
    else
        tuplen = GetMemoryChunkSpace(tup);
 
    tuplesort_puttuple_common(state, &stup,
                              base->haveDatum1 &&
                              base->sortKeys->abbrev_converter &&
                              !stup.isnull1, tuplen);
 
    MemoryContextSwitchTo(oldcontext);
}

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, SortTuple::datum1, GetMemoryChunkSpace(), TuplesortPublic::haveDatum1, heap_copytuple(), heap_getattr(), HEAPTUPLESIZE, SortTuple::isnull1, MAXALIGN, MemoryContextSwitchTo(), TuplesortPublic::sortKeys, TuplesortPublic::sortopt, HeapTupleData::t_len, SortTuple::tuple, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), TuplesortstateGetPublic, and TupleSortUseBumpTupleCxt.

Referenced by heapam_relation_copy_for_cluster().

tuplesort_putindextuplevalues()

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

Definition at line 817 of file tuplesortvariants.c.

{
    SortTuple   stup;
    IndexTuple  tuple;
    TuplesortPublic *base = TuplesortstateGetPublic(state);
    TuplesortIndexArg *arg = (TuplesortIndexArg *) base->arg;
    Size        tuplen;
 
    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);
 
    /* GetMemoryChunkSpace is not supported for bump contexts */
    if (TupleSortUseBumpTupleCxt(base->sortopt))
        tuplen = MAXALIGN(tuple->t_info & INDEX_SIZE_MASK);
    else
        tuplen = GetMemoryChunkSpace(tuple);
 
    tuplesort_puttuple_common(state, &stup,
                              base->sortKeys &&
                              base->sortKeys->abbrev_converter &&
                              !stup.isnull1, tuplen);
}

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

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

tuplesort_puttuple_common()

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

Definition at line 1169 of file tuplesort.c.

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
 
    Assert(!LEADER(state));
 
    /* account for the memory used for this tuple */
    USEMEM(state, tuplen);
    state->tupleMem += tuplen;
 
    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))))
            {
                if (trace_sort)
                    elog(LOG, "switching to bounded heapsort at %d tuples: %s",
                         state->memtupcount,
                         pg_rusage_show(&state->ru_start));
                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(), grow_memtuples(), inittapes(), LACKMEM, LEADER, LOG, make_bounded_heap(), MemoryContextSwitchTo(), pg_rusage_show(), REMOVEABBREV, trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_INITIAL, tuplesort_heap_replace_top(), and USEMEM.

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

tuplesort_puttupleslot()

void tuplesort_puttupleslot	(	Tuplesortstate *	state,
		TupleTableSlot *	slot
	)

Definition at line 734 of file tuplesortvariants.c.

{
    TuplesortPublic *base = TuplesortstateGetPublic(state);
    MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
    TupleDesc   tupDesc = (TupleDesc) base->arg;
    SortTuple   stup;
    MinimalTuple tuple;
    HeapTupleData htup;
    Size        tuplen;
 
    /* copy the tuple into sort storage */
    tuple = ExecCopySlotMinimalTuple(slot);
    stup.tuple = 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);
 
    /* GetMemoryChunkSpace is not supported for bump contexts */
    if (TupleSortUseBumpTupleCxt(base->sortopt))
        tuplen = MAXALIGN(tuple->t_len);
    else
        tuplen = GetMemoryChunkSpace(tuple);
 
    tuplesort_puttuple_common(state, &stup,
                              base->sortKeys->abbrev_converter &&
                              !stup.isnull1, tuplen);
 
    MemoryContextSwitchTo(oldcontext);
}

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

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 2883 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(), readtup_index(), readtup_index_brin(), and readtup_index_gin().

tuplesort_rescan()

void tuplesort_rescan

(

Tuplesortstate *

state

)

Definition at line 2402 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 1019 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 2466 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 838 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 1710 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 2566 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 886 of file tuplesort.c.

{
    return state->boundUsed;
}

Referenced by ExecIncrementalSort().