tuplesort.h File Reference

#include "access/itup.h"
#include "executor/tuptable.h"
#include "storage/dsm.h"
#include "utils/relcache.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

Macros
#define	NUM_TUPLESORTMETHODS   4

Typedefs
typedef struct Tuplesortstate	Tuplesortstate
typedef struct Sharedsort	Sharedsort
typedef struct SortCoordinateData	SortCoordinateData
typedef struct SortCoordinateData *	SortCoordinate
typedef struct TuplesortInstrumentation	TuplesortInstrumentation

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_heap (TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, bool randomAccess)
Tuplesortstate *	tuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, bool randomAccess)
Tuplesortstate *	tuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, SortCoordinate coordinate, bool randomAccess)
Tuplesortstate *	tuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, bool randomAccess)
Tuplesortstate *	tuplesort_begin_index_gist (Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, bool randomAccess)
Tuplesortstate *	tuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, bool randomAccess)
void	tuplesort_set_bound (Tuplesortstate *state, int64 bound)
bool	tuplesort_used_bound (Tuplesortstate *state)
void	tuplesort_puttupleslot (Tuplesortstate *state, TupleTableSlot *slot)
void	tuplesort_putheaptuple (Tuplesortstate *state, HeapTuple tup)
void	tuplesort_putindextuplevalues (Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
void	tuplesort_putdatum (Tuplesortstate *state, Datum val, bool isNull)
void	tuplesort_performsort (Tuplesortstate *state)
bool	tuplesort_gettupleslot (Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
HeapTuple	tuplesort_getheaptuple (Tuplesortstate *state, bool forward)
IndexTuple	tuplesort_getindextuple (Tuplesortstate *state, bool forward)
bool	tuplesort_getdatum (Tuplesortstate *state, bool forward, Datum *val, bool *isNull, Datum *abbrev)
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)

Macro Definition Documentation

NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS   4

Definition at line 81 of file tuplesort.h.

Referenced by show_incremental_sort_group_info().

Typedef Documentation

Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 35 of file tuplesort.h.

SortCoordinate

typedef struct SortCoordinateData* SortCoordinate

Definition at line 58 of file tuplesort.h.

SortCoordinateData

typedef struct SortCoordinateData SortCoordinateData

TuplesortInstrumentation

typedef struct TuplesortInstrumentation TuplesortInstrumentation

Tuplesortstate

typedef struct Tuplesortstate Tuplesortstate

Definition at line 34 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 72 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 83 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 4601 of file tuplesort.c.

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

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

tuplesort_begin_cluster()

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

Definition at line 971 of file tuplesort.c.

References _bt_mkscankey(), SortSupportData::abbreviate, Tuplesortstate::abbrevNext, Assert, AssertState, BTGreaterStrategyNumber, BTLessStrategyNumber, BuildIndexInfo(), CLUSTER_SORT, Tuplesortstate::comparetup, comparetup_cluster(), Tuplesortstate::copytup, copytup_cluster(), CreateExecutorState(), CurrentMemoryContext, ExprContext::ecxt_scantuple, elog, Tuplesortstate::estate, GetPerTupleExprContext, i, IndexInfo::ii_Expressions, Tuplesortstate::indexInfo, IndexRelationGetNumberOfKeyAttributes, LOG, Tuplesortstate::maincontext, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), Tuplesortstate::nKeys, palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, Tuplesortstate::readtup, readtup_cluster(), RelationGetNumberOfAttributes, BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, Tuplesortstate::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TTSOpsHeapTuple, Tuplesortstate::tupDesc, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_cluster().

Referenced by heapam_relation_copy_for_cluster().

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   randomAccess);
    BTScanInsert indexScanKey;
    MemoryContext oldcontext;
    int         i;

    Assert(indexRel->rd_rel->relam == BTREE_AM_OID);

    oldcontext = MemoryContextSwitchTo(state->maincontext);

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG,
             "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
             RelationGetNumberOfAttributes(indexRel),
             workMem, randomAccess ? 't' : 'f');
#endif

    state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);

    TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
                                false,  /* no unique check */
                                state->nKeys,
                                workMem,
                                randomAccess,
                                PARALLEL_SORT(state));

    state->comparetup = comparetup_cluster;
    state->copytup = copytup_cluster;
    state->writetup = writetup_cluster;
    state->readtup = readtup_cluster;
    state->abbrevNext = 10;

    state->indexInfo = BuildIndexInfo(indexRel);

    state->tupDesc = tupDesc;   /* assume we need not copy tupDesc */

    indexScanKey = _bt_mkscankey(indexRel, NULL);

    if (state->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.
         */
        state->estate = CreateExecutorState();
        slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
        econtext = GetPerTupleExprContext(state->estate);
        econtext->ecxt_scantuple = slot;
    }

    /* Prepare SortSupport data for each column */
    state->sortKeys = (SortSupport) palloc0(state->nKeys *
                                            sizeof(SortSupportData));

    for (i = 0; i < state->nKeys; i++)
    {
        SortSupport sortKey = state->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);

        AssertState(sortKey->ssup_attno != 0);

        strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
            BTGreaterStrategyNumber : BTLessStrategyNumber;

        PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
    }

    pfree(indexScanKey);

    MemoryContextSwitchTo(oldcontext);

    return state;
}

tuplesort_begin_datum()

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

Definition at line 1247 of file tuplesort.c.

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, Tuplesortstate::abbrevNext, Tuplesortstate::comparetup, comparetup_datum(), Tuplesortstate::copytup, copytup_datum(), CurrentMemoryContext, DATUM_SORT, Tuplesortstate::datumType, Tuplesortstate::datumTypeLen, elog, get_typlenbyval(), LOG, Tuplesortstate::maincontext, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::onlyKey, palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), Tuplesortstate::readtup, readtup_datum(), Tuplesortstate::sortKeys, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, Tuplesortstate::tuples, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_datum().

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

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   randomAccess);
    MemoryContext oldcontext;
    int16       typlen;
    bool        typbyval;

    oldcontext = MemoryContextSwitchTo(state->maincontext);

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG,
             "begin datum sort: workMem = %d, randomAccess = %c",
             workMem, randomAccess ? 't' : 'f');
#endif

    state->nKeys = 1;           /* always a one-column sort */

    TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
                                false,  /* no unique check */
                                1,
                                workMem,
                                randomAccess,
                                PARALLEL_SORT(state));

    state->comparetup = comparetup_datum;
    state->copytup = copytup_datum;
    state->writetup = writetup_datum;
    state->readtup = readtup_datum;
    state->abbrevNext = 10;

    state->datumType = datumType;

    /* lookup necessary attributes of the datum type */
    get_typlenbyval(datumType, &typlen, &typbyval);
    state->datumTypeLen = typlen;
    state->tuples = !typbyval;

    /* Prepare SortSupport data */
    state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));

    state->sortKeys->ssup_cxt = CurrentMemoryContext;
    state->sortKeys->ssup_collation = sortCollation;
    state->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.
     */
    state->sortKeys->abbreviate = !typbyval;

    PrepareSortSupportFromOrderingOp(sortOperator, state->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 (!state->sortKeys->abbrev_converter)
        state->onlyKey = state->sortKeys;

    MemoryContextSwitchTo(oldcontext);

    return state;
}

tuplesort_begin_heap()

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

Definition at line 897 of file tuplesort.c.

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, Tuplesortstate::abbrevNext, AssertArg, Tuplesortstate::comparetup, comparetup_heap(), Tuplesortstate::copytup, copytup_heap(), CurrentMemoryContext, elog, HEAP_SORT, i, LOG, Tuplesortstate::maincontext, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::onlyKey, palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), Tuplesortstate::readtup, readtup_heap(), Tuplesortstate::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, Tuplesortstate::tupDesc, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_heap().

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

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   randomAccess);
    MemoryContext oldcontext;
    int         i;

    oldcontext = MemoryContextSwitchTo(state->maincontext);

    AssertArg(nkeys > 0);

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG,
             "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
             nkeys, workMem, randomAccess ? 't' : 'f');
#endif

    state->nKeys = nkeys;

    TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
                                false,  /* no unique check */
                                nkeys,
                                workMem,
                                randomAccess,
                                PARALLEL_SORT(state));

    state->comparetup = comparetup_heap;
    state->copytup = copytup_heap;
    state->writetup = writetup_heap;
    state->readtup = readtup_heap;

    state->tupDesc = tupDesc;   /* assume we need not copy tupDesc */
    state->abbrevNext = 10;

    /* Prepare SortSupport data for each column */
    state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));

    for (i = 0; i < nkeys; i++)
    {
        SortSupport sortKey = state->sortKeys + i;

        AssertArg(attNums[i] != 0);
        AssertArg(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);

        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 && !state->sortKeys->abbrev_converter)
        state->onlyKey = state->sortKeys;

    MemoryContextSwitchTo(oldcontext);

    return state;
}

tuplesort_begin_index_btree()

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

Definition at line 1066 of file tuplesort.c.

References _bt_mkscankey(), SortSupportData::abbreviate, Tuplesortstate::abbrevNext, AssertState, BTGreaterStrategyNumber, BTLessStrategyNumber, Tuplesortstate::comparetup, comparetup_index_btree(), Tuplesortstate::copytup, copytup_index(), CurrentMemoryContext, elog, Tuplesortstate::enforceUnique, Tuplesortstate::heapRel, i, INDEX_SORT, Tuplesortstate::indexRel, IndexRelationGetNumberOfKeyAttributes, LOG, Tuplesortstate::maincontext, MemoryContextSwitchTo(), Tuplesortstate::nKeys, palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), Tuplesortstate::readtup, readtup_index(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, Tuplesortstate::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_index().

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   randomAccess);
    BTScanInsert indexScanKey;
    MemoryContext oldcontext;
    int         i;

    oldcontext = MemoryContextSwitchTo(state->maincontext);

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG,
             "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
             enforceUnique ? 't' : 'f',
             workMem, randomAccess ? 't' : 'f');
#endif

    state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);

    TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
                                enforceUnique,
                                state->nKeys,
                                workMem,
                                randomAccess,
                                PARALLEL_SORT(state));

    state->comparetup = comparetup_index_btree;
    state->copytup = copytup_index;
    state->writetup = writetup_index;
    state->readtup = readtup_index;
    state->abbrevNext = 10;

    state->heapRel = heapRel;
    state->indexRel = indexRel;
    state->enforceUnique = enforceUnique;

    indexScanKey = _bt_mkscankey(indexRel, NULL);

    /* Prepare SortSupport data for each column */
    state->sortKeys = (SortSupport) palloc0(state->nKeys *
                                            sizeof(SortSupportData));

    for (i = 0; i < state->nKeys; i++)
    {
        SortSupport sortKey = state->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);

        AssertState(sortKey->ssup_attno != 0);

        strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
            BTGreaterStrategyNumber : BTLessStrategyNumber;

        PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
    }

    pfree(indexScanKey);

    MemoryContextSwitchTo(oldcontext);

    return state;
}

tuplesort_begin_index_gist()

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

Definition at line 1190 of file tuplesort.c.

References SortSupportData::abbreviate, AssertState, Tuplesortstate::comparetup, comparetup_index_btree(), Tuplesortstate::copytup, copytup_index(), CurrentMemoryContext, elog, Tuplesortstate::heapRel, i, Tuplesortstate::indexRel, IndexRelationGetNumberOfKeyAttributes, LOG, MemoryContextSwitchTo(), Tuplesortstate::nKeys, palloc0(), PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, Tuplesortstate::readtup, readtup_index(), Tuplesortstate::sortcontext, Tuplesortstate::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_index().

Referenced by gistbuild().

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   randomAccess);
    MemoryContext oldcontext;
    int         i;

    oldcontext = MemoryContextSwitchTo(state->sortcontext);

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG,
             "begin index sort: workMem = %d, randomAccess = %c",
             workMem, randomAccess ? 't' : 'f');
#endif

    state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);

    state->comparetup = comparetup_index_btree;
    state->copytup = copytup_index;
    state->writetup = writetup_index;
    state->readtup = readtup_index;

    state->heapRel = heapRel;
    state->indexRel = indexRel;

    /* Prepare SortSupport data for each column */
    state->sortKeys = (SortSupport) palloc0(state->nKeys *
                                            sizeof(SortSupportData));

    for (i = 0; i < state->nKeys; i++)
    {
        SortSupport sortKey = state->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);

        AssertState(sortKey->ssup_attno != 0);

        /* Look for a sort support function */
        PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
    }

    MemoryContextSwitchTo(oldcontext);

    return state;
}

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,
		bool	randomAccess
	)

Definition at line 1144 of file tuplesort.c.

References Tuplesortstate::comparetup, comparetup_index_hash(), Tuplesortstate::copytup, copytup_index(), elog, Tuplesortstate::heapRel, Tuplesortstate::high_mask, Tuplesortstate::indexRel, LOG, Tuplesortstate::low_mask, Tuplesortstate::maincontext, Tuplesortstate::max_buckets, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::readtup, readtup_index(), trace_sort, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_index().

Referenced by _h_spoolinit().

{
    Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
                                                   randomAccess);
    MemoryContext oldcontext;

    oldcontext = MemoryContextSwitchTo(state->maincontext);

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG,
             "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
             "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
             high_mask,
             low_mask,
             max_buckets,
             workMem, randomAccess ? 't' : 'f');
#endif

    state->nKeys = 1;           /* Only one sort column, the hash code */

    state->comparetup = comparetup_index_hash;
    state->copytup = copytup_index;
    state->writetup = writetup_index;
    state->readtup = readtup_index;

    state->heapRel = heapRel;
    state->indexRel = indexRel;

    state->high_mask = high_mask;
    state->low_mask = low_mask;
    state->max_buckets = max_buckets;

    MemoryContextSwitchTo(oldcontext);

    return state;
}

tuplesort_end()

void tuplesort_end

(

Tuplesortstate *

state

)

Definition at line 1464 of file tuplesort.c.

References Tuplesortstate::maincontext, MemoryContextDelete(), and tuplesort_free().

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

{
    tuplesort_free(state);

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

tuplesort_estimate_shared()

Size tuplesort_estimate_shared

(

int

nworkers

)

Definition at line 4557 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

{
    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;
}

tuplesort_get_stats()

void tuplesort_get_stats	(	Tuplesortstate *	state,
		TuplesortInstrumentation *	stats
	)

Definition at line 3378 of file tuplesort.c.

References Tuplesortstate::boundUsed, Tuplesortstate::isMaxSpaceDisk, Tuplesortstate::maxSpace, Tuplesortstate::maxSpaceStatus, 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().

{
    /*
     * 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;
    }
}

tuplesort_getdatum()

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

Definition at line 2494 of file tuplesort.c.

References SortSupportData::abbrev_converter, SortTuple::datum1, datumCopy(), Tuplesortstate::datumTypeLen, SortTuple::isnull1, MemoryContextSwitchTo(), PointerGetDatum, Tuplesortstate::sortcontext, Tuplesortstate::sortKeys, SortTuple::tuple, Tuplesortstate::tuples, and tuplesort_gettuple_common().

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
    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 (state->sortKeys->abbrev_converter && abbrev)
        *abbrev = stup.datum1;

    if (stup.isnull1 || !state->tuples)
    {
        *val = stup.datum1;
        *isNull = stup.isnull1;
    }
    else
    {
        /* use stup.tuple because stup.datum1 may be an abbreviation */
        *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
        *isNull = false;
    }

    return true;
}

tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 2445 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
    SortTuple   stup;

    if (!tuplesort_gettuple_common(state, forward, &stup))
        stup.tuple = NULL;

    MemoryContextSwitchTo(oldcontext);

    return stup.tuple;
}

tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 2465 of file tuplesort.c.

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

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
    SortTuple   stup;

    if (!tuplesort_gettuple_common(state, forward, &stup))
        stup.tuple = NULL;

    MemoryContextSwitchTo(oldcontext);

    return (IndexTuple) stup.tuple;
}

tuplesort_gettupleslot()

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

Definition at line 2408 of file tuplesort.c.

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

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
    SortTuple   stup;

    if (!tuplesort_gettuple_common(state, forward, &stup))
        stup.tuple = NULL;

    MemoryContextSwitchTo(oldcontext);

    if (stup.tuple)
    {
        /* Record abbreviated key for caller */
        if (state->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;
    }
}

tuplesort_initialize_shared()

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

Definition at line 4578 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

{
    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;
    }
}

tuplesort_markpos()

void tuplesort_markpos

(

Tuplesortstate *

state

)

Definition at line 3312 of file tuplesort.c.

References Assert, Tuplesortstate::current, elog, Tuplesortstate::eof_reached, ERROR, LogicalTapeTell(), Tuplesortstate::markpos_block, Tuplesortstate::markpos_eof, Tuplesortstate::markpos_offset, MemoryContextSwitchTo(), Tuplesortstate::randomAccess, Tuplesortstate::result_tape, Tuplesortstate::sortcontext, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

Referenced by ExecSortMarkPos().

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);

    Assert(state->randomAccess);

    switch (state->status)
    {
        case TSS_SORTEDINMEM:
            state->markpos_offset = state->current;
            state->markpos_eof = state->eof_reached;
            break;
        case TSS_SORTEDONTAPE:
            LogicalTapeTell(state->tapeset,
                            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);
}

tuplesort_merge_order()

int tuplesort_merge_order

(

int64

allowedMem

)

Definition at line 2602 of file tuplesort.c.

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

Referenced by cost_tuplesort(), and inittapes().

{
    int         mOrder;

    /*
     * We need one tape for each merge input, plus another one for the output,
     * and each of these tapes needs buffer space.  In addition we want
     * MERGE_BUFFER_SIZE workspace per input tape (but the output tape doesn't
     * count).
     *
     * 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 - TAPE_BUFFER_OVERHEAD) /
        (MERGE_BUFFER_SIZE + TAPE_BUFFER_OVERHEAD);

    /*
     * 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 polyphase merge than to perform a
     * single merge pass across many hundreds of tapes.
     */
    mOrder = Max(mOrder, MINORDER);
    mOrder = Min(mOrder, MAXORDER);

    return mOrder;
}

tuplesort_method_name()

const char* tuplesort_method_name

(

TuplesortMethod

m

)

Definition at line 3422 of file tuplesort.c.

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

{
    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";
}

tuplesort_performsort()

void tuplesort_performsort

(

Tuplesortstate *

state

)

Definition at line 2040 of file tuplesort.c.

References Tuplesortstate::activeTapes, Tuplesortstate::current, dumptuples(), elog, Tuplesortstate::eof_reached, ERROR, inittapes(), leader_takeover_tapes(), LOG, Tuplesortstate::markpos_block, Tuplesortstate::markpos_eof, Tuplesortstate::markpos_offset, MemoryContextSwitchTo(), mergeruns(), pg_rusage_show(), Tuplesortstate::ru_start, SERIAL, sort_bounded_heap(), Tuplesortstate::sortcontext, Tuplesortstate::status, trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_FINALMERGE, TSS_INITIAL, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, tuplesort_sort_memtuples(), Tuplesortstate::worker, WORKER, and worker_nomergeruns().

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG, "performsort of worker %d starting: %s",
             state->worker, pg_rusage_show(&state->ru_start));
#endif

    switch (state->status)
    {
        case TSS_INITIAL:

            /*
             * We were able to accumulate all the tuples within the allowed
             * amount of memory, or leader to take over worker tapes
             */
            if (SERIAL(state))
            {
                /* Just qsort 'em and we're done */
                tuplesort_sort_memtuples(state);
                state->status = TSS_SORTEDINMEM;
            }
            else if (WORKER(state))
            {
                /*
                 * Parallel workers must still dump out tuples to tape.  No
                 * merge is required to produce single output run, though.
                 */
                inittapes(state, false);
                dumptuples(state, true);
                worker_nomergeruns(state);
                state->status = TSS_SORTEDONTAPE;
            }
            else
            {
                /*
                 * Leader will take over worker tapes and merge worker runs.
                 * Note that mergeruns sets the correct state->status.
                 */
                leader_takeover_tapes(state);
                mergeruns(state);
            }
            state->current = 0;
            state->eof_reached = false;
            state->markpos_block = 0L;
            state->markpos_offset = 0;
            state->markpos_eof = false;
            break;

        case TSS_BOUNDED:

            /*
             * We were able to accumulate all the tuples required for output
             * in memory, using a heap to eliminate excess tuples.  Now we
             * have to transform the heap to a properly-sorted array.
             */
            sort_bounded_heap(state);
            state->current = 0;
            state->eof_reached = false;
            state->markpos_offset = 0;
            state->markpos_eof = false;
            state->status = TSS_SORTEDINMEM;
            break;

        case TSS_BUILDRUNS:

            /*
             * Finish tape-based sort.  First, flush all tuples remaining in
             * memory out to tape; then merge until we have a single remaining
             * run (or, if !randomAccess and !WORKER(), one run per tape).
             * Note that mergeruns sets the correct state->status.
             */
            dumptuples(state, true);
            mergeruns(state);
            state->eof_reached = false;
            state->markpos_block = 0L;
            state->markpos_offset = 0;
            state->markpos_eof = false;
            break;

        default:
            elog(ERROR, "invalid tuplesort state");
            break;
    }

#ifdef TRACE_SORT
    if (trace_sort)
    {
        if (state->status == TSS_FINALMERGE)
            elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
                 state->worker, state->activeTapes,
                 pg_rusage_show(&state->ru_start));
        else
            elog(LOG, "performsort of worker %d done: %s",
                 state->worker, pg_rusage_show(&state->ru_start));
    }
#endif

    MemoryContextSwitchTo(oldcontext);
}

tuplesort_putdatum()

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

Definition at line 1805 of file tuplesort.c.

References SortSupportData::abbrev_converter, consider_abort_common(), SortTuple::datum1, datumCopy(), DatumGetPointer, Tuplesortstate::datumTypeLen, GetMemoryChunkSpace(), i, SortTuple::isnull1, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, PointerGetDatum, puttuple_common(), Tuplesortstate::sortcontext, Tuplesortstate::sortKeys, SortTuple::tuple, Tuplesortstate::tuplecontext, Tuplesortstate::tuples, USEMEM, and val.

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
    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 || !state->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 */
        MemoryContextSwitchTo(state->sortcontext);
    }
    else
    {
        Datum       original = datumCopy(val, false, state->datumTypeLen);

        stup.isnull1 = false;
        stup.tuple = DatumGetPointer(original);
        USEMEM(state, GetMemoryChunkSpace(stup.tuple));
        MemoryContextSwitchTo(state->sortcontext);

        if (!state->sortKeys->abbrev_converter)
        {
            stup.datum1 = original;
        }
        else if (!consider_abort_common(state))
        {
            /* Store abbreviated key representation */
            stup.datum1 = state->sortKeys->abbrev_converter(original,
                                                            state->sortKeys);
        }
        else
        {
            /* Abort abbreviation */
            int         i;

            stup.datum1 = original;

            /*
             * 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).
             */
            for (i = 0; i < state->memtupcount; i++)
            {
                SortTuple  *mtup = &state->memtuples[i];

                mtup->datum1 = PointerGetDatum(mtup->tuple);
            }
        }
    }

    puttuple_common(state, &stup);

    MemoryContextSwitchTo(oldcontext);
}

tuplesort_putheaptuple()

void tuplesort_putheaptuple	(	Tuplesortstate *	state,
		HeapTuple	tup
	)

Definition at line 1706 of file tuplesort.c.

References COPYTUP, MemoryContextSwitchTo(), puttuple_common(), and Tuplesortstate::sortcontext.

Referenced by heapam_relation_copy_for_cluster().

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
    SortTuple   stup;

    /*
     * Copy the given tuple into memory we control, and decrease availMem.
     * Then call the common code.
     */
    COPYTUP(state, &stup, (void *) tup);

    puttuple_common(state, &stup);

    MemoryContextSwitchTo(oldcontext);
}

tuplesort_putindextuplevalues()

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

Definition at line 1727 of file tuplesort.c.

References SortSupportData::abbrev_converter, consider_abort_common(), SortTuple::datum1, GetMemoryChunkSpace(), i, index_form_tuple(), index_getattr, Tuplesortstate::indexRel, SortTuple::isnull1, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, puttuple_common(), RelationGetDescr, Tuplesortstate::sortcontext, Tuplesortstate::sortKeys, IndexTupleData::t_tid, SortTuple::tuple, Tuplesortstate::tuplecontext, and USEMEM.

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
    SortTuple   stup;
    Datum       original;
    IndexTuple  tuple;

    stup.tuple = index_form_tuple(RelationGetDescr(rel), values, isnull);
    tuple = ((IndexTuple) stup.tuple);
    tuple->t_tid = *self;
    USEMEM(state, GetMemoryChunkSpace(stup.tuple));
    /* set up first-column key value */
    original = index_getattr(tuple,
                             1,
                             RelationGetDescr(state->indexRel),
                             &stup.isnull1);

    MemoryContextSwitchTo(state->sortcontext);

    if (!state->sortKeys || !state->sortKeys->abbrev_converter || stup.isnull1)
    {
        /*
         * Store 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).
         */
        stup.datum1 = original;
    }
    else if (!consider_abort_common(state))
    {
        /* Store abbreviated key representation */
        stup.datum1 = state->sortKeys->abbrev_converter(original,
                                                        state->sortKeys);
    }
    else
    {
        /* Abort abbreviation */
        int         i;

        stup.datum1 = original;

        /*
         * 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).
         */
        for (i = 0; i < state->memtupcount; i++)
        {
            SortTuple  *mtup = &state->memtuples[i];

            tuple = mtup->tuple;
            mtup->datum1 = index_getattr(tuple,
                                         1,
                                         RelationGetDescr(state->indexRel),
                                         &mtup->isnull1);
        }
    }

    puttuple_common(state, &stup);

    MemoryContextSwitchTo(oldcontext);
}

tuplesort_puttupleslot()

void tuplesort_puttupleslot	(	Tuplesortstate *	state,
		TupleTableSlot *	slot
	)

Definition at line 1684 of file tuplesort.c.

References COPYTUP, MemoryContextSwitchTo(), puttuple_common(), and Tuplesortstate::sortcontext.

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
    SortTuple   stup;

    /*
     * Copy the given tuple into memory we control, and decrease availMem.
     * Then call the common code.
     */
    COPYTUP(state, &stup, (void *) slot);

    puttuple_common(state, &stup);

    MemoryContextSwitchTo(oldcontext);
}

tuplesort_rescan()

void tuplesort_rescan

(

Tuplesortstate *

state

)

Definition at line 3277 of file tuplesort.c.

References Assert, Tuplesortstate::current, elog, Tuplesortstate::eof_reached, ERROR, LogicalTapeRewindForRead(), Tuplesortstate::markpos_block, Tuplesortstate::markpos_eof, Tuplesortstate::markpos_offset, MemoryContextSwitchTo(), Tuplesortstate::randomAccess, Tuplesortstate::result_tape, Tuplesortstate::sortcontext, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

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

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);

    Assert(state->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->tapeset,
                                     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);
}

tuplesort_reset()

void tuplesort_reset

(

Tuplesortstate *

state

)

Definition at line 1532 of file tuplesort.c.

References Tuplesortstate::lastReturnedTuple, Tuplesortstate::slabFreeHead, Tuplesortstate::slabMemoryBegin, Tuplesortstate::slabMemoryEnd, tuplesort_begin_batch(), tuplesort_free(), and tuplesort_updatemax().

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

{
    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;
}

tuplesort_restorepos()

void tuplesort_restorepos

(

Tuplesortstate *

state

)

Definition at line 3344 of file tuplesort.c.

References Assert, Tuplesortstate::current, elog, Tuplesortstate::eof_reached, ERROR, LogicalTapeSeek(), Tuplesortstate::markpos_block, Tuplesortstate::markpos_eof, Tuplesortstate::markpos_offset, MemoryContextSwitchTo(), Tuplesortstate::randomAccess, Tuplesortstate::result_tape, Tuplesortstate::sortcontext, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

Referenced by ExecSortRestrPos().

{
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);

    Assert(state->randomAccess);

    switch (state->status)
    {
        case TSS_SORTEDINMEM:
            state->current = state->markpos_offset;
            state->eof_reached = state->markpos_eof;
            break;
        case TSS_SORTEDONTAPE:
            LogicalTapeSeek(state->tapeset,
                            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);
}

tuplesort_set_bound()

void tuplesort_set_bound	(	Tuplesortstate *	state,
		int64	bound
	)

Definition at line 1334 of file tuplesort.c.

References SortSupportData::abbrev_abort, SortSupportData::abbrev_converter, SortSupportData::abbrev_full_comparator, Assert, Tuplesortstate::bound, Tuplesortstate::bounded, SortSupportData::comparator, LEADER, Tuplesortstate::memtupcount, Tuplesortstate::sortKeys, Tuplesortstate::status, TSS_INITIAL, and WORKER.

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

{
    /* Assert we're called before loading any tuples */
    Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
    /* 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->sortKeys->abbrev_converter = NULL;
    if (state->sortKeys->abbrev_full_comparator)
        state->sortKeys->comparator = state->sortKeys->abbrev_full_comparator;

    /* Not strictly necessary, but be tidy */
    state->sortKeys->abbrev_abort = NULL;
    state->sortKeys->abbrev_full_comparator = NULL;
}

tuplesort_skiptuples()

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

Definition at line 2534 of file tuplesort.c.

References Assert, Tuplesortstate::bound, Tuplesortstate::bounded, CHECK_FOR_INTERRUPTS, Tuplesortstate::current, elog, Tuplesortstate::eof_reached, ERROR, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::sortcontext, Tuplesortstate::status, 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().

{
    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->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 */
    }
}

tuplesort_space_type_name()

const char* tuplesort_space_type_name

(

TuplesortSpaceType

t

)

Definition at line 3445 of file tuplesort.c.

References Assert, SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

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

tuplesort_used_bound()

bool tuplesort_used_bound

(

Tuplesortstate *

state

)

Definition at line 1380 of file tuplesort.c.

References Tuplesortstate::boundUsed.

Referenced by ExecIncrementalSort().

{
    return state->boundUsed;
}