tuplesort.h File Reference

#include "access/brin_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_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_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)
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 262 of file tuplesort.h.

NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS   4

Definition at line 84 of file tuplesort.h.

PARALLEL_SORT

#define PARALLEL_SORT

(

coordinate

)

Value:

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

Definition at line 255 of file tuplesort.h.

TUPLESORT_ALLOWBOUNDED

#define TUPLESORT_ALLOWBOUNDED   (1 << 1)

Definition at line 99 of file tuplesort.h.

TUPLESORT_NONE

#define TUPLESORT_NONE   0

Definition at line 93 of file tuplesort.h.

TUPLESORT_RANDOMACCESS

#define TUPLESORT_RANDOMACCESS   (1 << 0)

Definition at line 96 of file tuplesort.h.

TuplesortstateGetPublic

#define TuplesortstateGetPublic

(

state

)

((TuplesortPublic *) state)

Definition at line 259 of file tuplesort.h.

TupleSortUseBumpTupleCxt

#define TupleSortUseBumpTupleCxt

(

opt

)

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

Definition at line 108 of file tuplesort.h.

Typedef Documentation

Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 1 of file tuplesort.h.

SortCoordinate

typedef struct SortCoordinateData* SortCoordinate

Definition at line 61 of file tuplesort.h.

SortCoordinateData

typedef struct SortCoordinateData SortCoordinateData

SortTupleComparator

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

Definition at line 155 of file tuplesort.h.

TuplesortInstrumentation

typedef struct TuplesortInstrumentation TuplesortInstrumentation

Tuplesortstate

typedef struct Tuplesortstate Tuplesortstate

Definition at line 1 of file tuplesort.h.

Enumeration Type Documentation

TuplesortMethod

enum TuplesortMethod

Enumerator
SORT_TYPE_STILL_IN_PROGRESS
SORT_TYPE_TOP_N_HEAPSORT
SORT_TYPE_QUICKSORT
SORT_TYPE_EXTERNAL_SORT
SORT_TYPE_EXTERNAL_MERGE

Definition at line 75 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 86 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(), and _bt_parallel_build_main().

tuplesort_begin_cluster()

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

Definition at line 241 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;
        int16       strategy;
 
        sortKey->ssup_cxt = CurrentMemoryContext;
        sortKey->ssup_collation = scanKey->sk_collation;
        sortKey->ssup_nulls_first =
            (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
        sortKey->ssup_attno = scanKey->sk_attno;
        /* Convey if abbreviation optimization is applicable in principle */
        sortKey->abbreviate = (i == 0 && base->haveDatum1);
 
        Assert(sortKey->ssup_attno != 0);
 
        strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
            BTGreaterStrategyNumber : BTLessStrategyNumber;
 
        PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
    }
 
    pfree(indexScanKey);
 
    MemoryContextSwitchTo(oldcontext);
 
    return state;
}

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert, BTGreaterStrategyNumber, BTLessStrategyNumber, BuildIndexInfo(), CLUSTER_SORT, TuplesortPublic::comparetup, comparetup_cluster(), 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_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 572 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 168 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 545 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 348 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;
        int16       strategy;
 
        sortKey->ssup_cxt = CurrentMemoryContext;
        sortKey->ssup_collation = scanKey->sk_collation;
        sortKey->ssup_nulls_first =
            (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
        sortKey->ssup_attno = scanKey->sk_attno;
        /* Convey if abbreviation optimization is applicable in principle */
        sortKey->abbreviate = (i == 0 && base->haveDatum1);
 
        Assert(sortKey->ssup_attno != 0);
 
        strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
            BTGreaterStrategyNumber : BTLessStrategyNumber;
 
        PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
    }
 
    pfree(indexScanKey);
 
    MemoryContextSwitchTo(oldcontext);
 
    return state;
}

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert, BTGreaterStrategyNumber, BTLessStrategyNumber, TuplesortPublic::comparetup, comparetup_index_btree(), 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_gist()

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

Definition at line 482 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 431 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(), _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(), and _bt_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 956 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 1004 of file tuplesortvariants.c.

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

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

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

tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 914 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 935 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_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 876 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(), and _bt_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(), _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 774 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(), size, 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 812 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_putheaptuple()

void tuplesort_putheaptuple	(	Tuplesortstate *	state,
		HeapTuple	tup
	)

Definition at line 695 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 738 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_putheaptuple(), tuplesort_putindextuplevalues(), and tuplesort_puttupleslot().

tuplesort_puttupleslot()

void tuplesort_puttupleslot	(	Tuplesortstate *	state,
		TupleTableSlot *	slot
	)

Definition at line 655 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(), and readtup_index_brin().

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().