tuplesort.h File Reference

#include "access/itup.h"
#include "executor/instrument_node.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	SortTuple
struct	TuplesortPublic

Macros
#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 BrinTuple	BrinTuple
typedef struct GinTuple	GinTuple
typedef struct Tuplesortstate	Tuplesortstate
typedef struct Sharedsort	Sharedsort
typedef struct SortCoordinateData	SortCoordinateData
typedef struct SortCoordinateData *	SortCoordinate
typedef int(*	SortTupleComparator) (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)

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, const ItemPointerData *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 230 of file tuplesort.h.

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

PARALLEL_SORT

#define PARALLEL_SORT

(

coordinate

)

Value:

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

Definition at line 223 of file tuplesort.h.

                                                                          : \
                                     (coordinate)->isWorker ? 1 : 2)

TUPLESORT_ALLOWBOUNDED

#define TUPLESORT_ALLOWBOUNDED   (1 << 1)

Definition at line 73 of file tuplesort.h.

TUPLESORT_NONE

#define TUPLESORT_NONE   0

Definition at line 67 of file tuplesort.h.

TUPLESORT_RANDOMACCESS

#define TUPLESORT_RANDOMACCESS   (1 << 0)

Definition at line 70 of file tuplesort.h.

TuplesortstateGetPublic

#define TuplesortstateGetPublic

(

state

)

((TuplesortPublic *) state)

Definition at line 227 of file tuplesort.h.

TupleSortUseBumpTupleCxt

#define TupleSortUseBumpTupleCxt

(

opt

)

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

Definition at line 82 of file tuplesort.h.

Typedef Documentation

BrinTuple

typedef struct BrinTuple BrinTuple

Definition at line 33 of file tuplesort.h.

GinTuple

typedef struct GinTuple GinTuple

Definition at line 34 of file tuplesort.h.

Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 41 of file tuplesort.h.

SortCoordinate

typedef struct SortCoordinateData* SortCoordinate

Definition at line 64 of file tuplesort.h.

SortCoordinateData

typedef struct SortCoordinateData SortCoordinateData

SortTupleComparator

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

Definition at line 123 of file tuplesort.h.

Tuplesortstate

typedef struct Tuplesortstate Tuplesortstate

Definition at line 40 of file tuplesort.h.

Function Documentation

tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort *  shared, dsm_segment *  seg  )

extern

Definition at line 3269 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  )

extern

Definition at line 254 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 = palloc0_object(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(), arg, TuplesortPublic::arg, Assert, BuildIndexInfo(), CLUSTER_SORT, TuplesortPublic::comparetup, comparetup_cluster(), comparetup_cluster_tiebreak(), TuplesortPublic::comparetup_tiebreak, CreateExecutorState(), CurrentMemoryContext, ExprContext::ecxt_scantuple, elog, fb(), TuplesortPublic::freestate, freestate_cluster(), GetPerTupleExprContext, TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc0(), palloc0_object, PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, TuplesortPublic::readtup, readtup_cluster(), RelationGetNumberOfAttributes, TuplesortPublic::removeabbrev, removeabbrev_cluster(), SK_BT_DESC, SK_BT_NULLS_FIRST, TuplesortPublic::sortKeys, 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  )

extern

Definition at line 547 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 = palloc0_object(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;
 
    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, fb(), INITIAL_MEMTUPSIZE, Max, MemoryContextSwitchTo(), palloc0_object, pg_rusage_init(), 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  )

extern

Definition at line 669 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 = palloc_object(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 = palloc0_object(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, fb(), get_typlenbyval(), TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, TuplesortPublic::onlyKey, palloc0_object, palloc_object, 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 array_sort_internal(), 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  )

extern

Definition at line 181 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, TuplesortPublic::arg, Assert, TuplesortPublic::comparetup, comparetup_heap(), comparetup_heap_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog, fb(), 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, 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  )

extern

Definition at line 556 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, fb(), 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  )

extern

Definition at line 360 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 = palloc_object(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(), arg, TuplesortPublic::arg, Assert, TuplesortPublic::comparetup, comparetup_index_btree(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog, fb(), TuplesortPublic::haveDatum1, i, INDEX_SORT, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc0(), palloc_object, PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), SK_BT_DESC, SK_BT_NULLS_FIRST, TuplesortPublic::sortKeys, 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  )

extern

Definition at line 583 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);
        Oid         cmpFunc;
 
        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;
 
        /*
         * If the compare proc isn't specified in the opclass definition, look
         * up the index key type's default btree comparator.
         */
        cmpFunc = index_getprocid(indexRel, i + 1, GIN_COMPARE_PROC);
        if (cmpFunc == InvalidOid)
        {
            TypeCacheEntry *typentry;
 
            typentry = lookup_type_cache(att->atttypid,
                                         TYPECACHE_CMP_PROC_FINFO);
            if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
                ereport(ERROR,
                        (errcode(ERRCODE_UNDEFINED_FUNCTION),
                         errmsg("could not identify a comparison function for type %s",
                                format_type_be(att->atttypid))));
 
            cmpFunc = typentry->cmp_proc_finfo.fn_oid;
        }
 
        PrepareSortSupportComparisonShim(cmpFunc, 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 TuplesortPublic::arg, Assert, TypeCacheEntry::cmp_proc_finfo, TuplesortPublic::comparetup, comparetup_index_gin(), CurrentMemoryContext, elog, ereport, errcode(), errmsg, ERROR, fb(), FmgrInfo::fn_oid, format_type_be(), GIN_COMPARE_PROC, TuplesortPublic::haveDatum1, i, index_getprocid(), IndexRelationGetNumberOfKeyAttributes, InvalidOid, LOG, lookup_type_cache(), TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, OidIsValid, palloc0(), PrepareSortSupportComparisonShim(), RelationData::rd_indcollation, TuplesortPublic::readtup, readtup_index_gin(), RelationGetDescr, TuplesortPublic::removeabbrev, removeabbrev_index_gin(), TuplesortPublic::sortKeys, trace_sort, TupleDescAttr(), tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TYPECACHE_CMP_PROC_FINFO, 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  )

extern

Definition at line 493 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 = palloc_object(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 arg, TuplesortPublic::arg, Assert, TuplesortPublic::comparetup, comparetup_index_btree(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog, fb(), TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc0(), palloc_object, PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), TuplesortPublic::sortKeys, SortSupportData::ssup_cxt, 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  )

extern

Definition at line 442 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 = palloc_object(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, fb(), TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc_object, 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 )

extern

Definition at line 848 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(), array_sort_internal(), 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 )

extern

Definition at line 3225 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, fb(), 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  )

extern

Definition at line 2396 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  )

extern

Definition at line 1084 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 fb(), len, MemoryContextSwitchTo(), TuplesortPublic::sortcontext, BrinSortTuple::tuple, 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  )

extern

Definition at line 1154 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(), fb(), MemoryContextSwitchTo(), PointerGetDatum, TuplesortPublic::sortcontext, TuplesortPublic::sortKeys, TuplesortPublic::tuples, tuplesort_gettuple_common(), TuplesortstateGetPublic, and val.

Referenced by array_sort_internal(), 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  )

extern

Definition at line 1107 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 NULL;
 
    tup = (GinTuple *) stup.tuple;
 
    *len = tup->tuplen;
 
    return tup;
}

References fb(), len, MemoryContextSwitchTo(), TuplesortPublic::sortcontext, tuplesort_gettuple_common(), and TuplesortstateGetPublic.

Referenced by _gin_parallel_merge(), and _gin_process_worker_data().

tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate *  state, bool  forward  )

extern

Definition at line 1042 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 fb(), 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  )

extern

Definition at line 1063 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 fb(), 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  )

extern

Definition at line 1367 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, fb(), getlen(), LogicalTapeBackspace(), LogicalTapeClose(), mergereadnext(), READTUP, RELEASE_SLAB_SLOT, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, 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  )

extern

Definition at line 1004 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, 0);
 
        ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
        return true;
    }
    else
    {
        ExecClearTuple(slot);
        return false;
    }
}

References SortSupportData::abbrev_converter, ExecClearTuple(), ExecStoreMinimalTuple(), fb(), 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  )

extern

Definition at line 3246 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, fb(), 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 )

extern

Definition at line 2332 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 )

extern

Definition at line 1675 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 fb(), 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 )

extern

Definition at line 2440 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 )

extern

Definition at line 1260 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))
            {
                /* Sort in memory 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, fb(), 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(), array_sort_internal(), 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  )

extern

Definition at line 871 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 = UInt32GetDatum(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, fb(), GetMemoryChunkSpace(), MAXALIGN, memcpy(), MemoryContextSwitchTo(), palloc(), TuplesortPublic::sortKeys, TuplesortPublic::sortopt, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), TuplesortstateGetPublic, TupleSortUseBumpTupleCxt, and UInt32GetDatum().

Referenced by form_and_spill_tuple().

tuplesort_putdatum()

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

extern

Definition at line 940 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, SortTuple::datum1, datumCopy(), DatumGetPointer(), fb(), MemoryContextSwitchTo(), TuplesortPublic::sortKeys, TuplesortPublic::tuplecontext, TuplesortPublic::tuples, tuplesort_puttuple_common(), TuplesortstateGetPublic, and val.

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

tuplesort_putgintuple()

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

extern

Definition at line 904 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, fb(), GetMemoryChunkSpace(), MAXALIGN, memcpy(), MemoryContextSwitchTo(), palloc(), TuplesortPublic::sortKeys, TuplesortPublic::sortopt, 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  )

extern

Definition at line 792 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, fb(), GetMemoryChunkSpace(), TuplesortPublic::haveDatum1, heap_copytuple(), heap_getattr(), HEAPTUPLESIZE, MAXALIGN, MemoryContextSwitchTo(), TuplesortPublic::sortKeys, TuplesortPublic::sortopt, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), TuplesortstateGetPublic, and TupleSortUseBumpTupleCxt.

Referenced by heapam_relation_copy_for_cluster().

tuplesort_putindextuplevalues()

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

extern

Definition at line 835 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, fb(), GetMemoryChunkSpace(), index_form_tuple_context(), index_getattr(), INDEX_SIZE_MASK, MAXALIGN, RelationGetDescr, TuplesortPublic::sortKeys, TuplesortPublic::sortopt, IndexTupleData::t_info, IndexTupleData::t_tid, 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  )

extern

Definition at line 1066 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, fb(), 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  )

extern

Definition at line 752 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(), fb(), GetMemoryChunkSpace(), heap_getattr(), MAXALIGN, MemoryContextSwitchTo(), MINIMAL_TUPLE_OFFSET, TuplesortPublic::sortKeys, TuplesortPublic::sortopt, SortSupportData::ssup_attno, HeapTupleData::t_data, HeapTupleData::t_len, 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  )

extern

Definition at line 3191 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 )

extern

Definition at line 2299 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, fb(), 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 )

extern

Definition at line 916 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 fb(), tuplesort_begin_batch(), tuplesort_free(), and tuplesort_updatemax().

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

tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate *  state )

extern

Definition at line 2363 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  )

extern

Definition at line 735 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, fb(), LEADER, TSS_INITIAL, TUPLESORT_ALLOWBOUNDED, and WORKER.

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

tuplesort_skiptuples()

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

extern

Definition at line 1607 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, fb(), 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 )

extern

Definition at line 2463 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 )

extern

Definition at line 783 of file tuplesort.c.

{
    return state->boundUsed;
}

Referenced by ExecIncrementalSort().