tuplesort.h File Reference

#include "access/itup.h"
#include "executor/tuptable.h"
#include "fmgr.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.

Typedefs
typedef struct Tuplesortstate	Tuplesortstate

Functions
Tuplesortstate *	tuplesort_begin_heap (TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, bool randomAccess)
Tuplesortstate *	tuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, bool randomAccess)
Tuplesortstate *	tuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, bool randomAccess)
Tuplesortstate *	tuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, bool randomAccess)
Tuplesortstate *	tuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, bool randomAccess)
void	tuplesort_set_bound (Tuplesortstate *state, int64 bound)
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_get_stats (Tuplesortstate *state, const char **sortMethod, const char **spaceType, long *spaceUsed)
int	tuplesort_merge_order (int64 allowedMem)
void	tuplesort_rescan (Tuplesortstate *state)
void	tuplesort_markpos (Tuplesortstate *state)
void	tuplesort_restorepos (Tuplesortstate *state)

Typedef Documentation

typedef struct Tuplesortstate Tuplesortstate

Definition at line 32 of file tuplesort.h.

Function Documentation

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

Definition at line 828 of file tuplesort.c.

References _bt_freeskey(), _bt_mkscankey_nodata(), SortSupportData::abbreviate, Tuplesortstate::abbrevNext, Assert, AssertState, BTGreaterStrategyNumber, BTLessStrategyNumber, BTREE_AM_OID, 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, LOG, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), Tuplesortstate::nKeys, NULL, palloc0(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, Tuplesortstate::readtup, readtup_cluster(), RelationGetNumberOfAttributes, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, Tuplesortstate::sortcontext, 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_cluster().

Referenced by copy_heap_data().

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

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

    oldcontext = MemoryContextSwitchTo(state->sortcontext);

#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 = RelationGetNumberOfAttributes(indexRel);

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

    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_nodata(indexRel);

    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);
        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 + 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);
    }

    _bt_freeskey(indexScanKey);

    MemoryContextSwitchTo(oldcontext);

    return state;
}

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

Definition at line 1038 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, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::onlyKey, palloc0(), PrepareSortSupportFromOrderingOp(), Tuplesortstate::readtup, readtup_datum(), Tuplesortstate::sortcontext, 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 initialize_aggregate(), ordered_set_startup(), and validate_index().

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

    oldcontext = MemoryContextSwitchTo(state->sortcontext);

#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);

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

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

Definition at line 756 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, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::onlyKey, palloc0(), PrepareSortSupportFromOrderingOp(), Tuplesortstate::readtup, readtup_heap(), Tuplesortstate::sortcontext, 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 ExecSort(), initialize_aggregate(), initialize_phase(), and ordered_set_startup().

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

    oldcontext = MemoryContextSwitchTo(state->sortcontext);

    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);

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

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

Definition at line 920 of file tuplesort.c.

References _bt_freeskey(), _bt_mkscankey_nodata(), 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, LOG, MemoryContextSwitchTo(), Tuplesortstate::nKeys, palloc0(), PrepareSortSupportFromIndexRel(), Tuplesortstate::readtup, readtup_index(), RelationGetNumberOfAttributes, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, 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 _bt_spoolinit().

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

    oldcontext = MemoryContextSwitchTo(state->sortcontext);

#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 = RelationGetNumberOfAttributes(indexRel);

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

    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_nodata(indexRel);
    state->nKeys = RelationGetNumberOfAttributes(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;
        ScanKey     scanKey = indexScanKey + 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);
    }

    _bt_freeskey(indexScanKey);

    MemoryContextSwitchTo(oldcontext);

    return state;
}

Tuplesortstate* tuplesort_begin_index_hash	(	Relation	heapRel,
		Relation	indexRel,
		uint32	high_mask,
		uint32	low_mask,
		uint32	max_buckets,
		int	workMem,
		bool	randomAccess
	)

Definition at line 995 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::max_buckets, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::readtup, readtup_index(), Tuplesortstate::sortcontext, trace_sort, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_index().

Referenced by _h_spoolinit().

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

    oldcontext = MemoryContextSwitchTo(state->sortcontext);

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

void tuplesort_end

(

Tuplesortstate *

state

)

Definition at line 1167 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, ExprContext::ecxt_scantuple, elog, Tuplesortstate::estate, ExecDropSingleTupleTableSlot(), FreeExecutorState(), GetPerTupleExprContext, LOG, LogicalTapeSetBlocks(), LogicalTapeSetClose(), MemoryContextDelete(), MemoryContextSwitchTo(), NULL, pg_rusage_show(), Tuplesortstate::ru_start, Tuplesortstate::sortcontext, Tuplesortstate::tapeset, and trace_sort.

Referenced by _bt_spooldestroy(), _h_spooldestroy(), copy_heap_data(), ExecEndAgg(), ExecEndSort(), ExecReScanAgg(), ExecReScanSort(), hypothetical_dense_rank_final(), hypothetical_rank_common(), initialize_aggregate(), initialize_phase(), ordered_set_shutdown(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), and validate_index().

{
    /* context swap probably not needed, but let's be safe */
    MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);

#ifdef TRACE_SORT
    long        spaceUsed;

    if (state->tapeset)
        spaceUsed = LogicalTapeSetBlocks(state->tapeset);
    else
        spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
#endif

    /*
     * Delete temporary "tape" files, if any.
     *
     * Note: want to include this in reported total cost of sort, hence need
     * for two #ifdef TRACE_SORT sections.
     */
    if (state->tapeset)
        LogicalTapeSetClose(state->tapeset);

#ifdef TRACE_SORT
    if (trace_sort)
    {
        if (state->tapeset)
            elog(LOG, "external sort ended, %ld disk blocks used: %s",
                 spaceUsed, pg_rusage_show(&state->ru_start));
        else
            elog(LOG, "internal sort ended, %ld KB used: %s",
                 spaceUsed, pg_rusage_show(&state->ru_start));
    }

    TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
#else

    /*
     * If you disabled TRACE_SORT, you can still probe sort__done, but you
     * ain't getting space-used stats.
     */
    TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, 0L);
#endif

    /* Free any execution state created for CLUSTER case */
    if (state->estate != NULL)
    {
        ExprContext *econtext = GetPerTupleExprContext(state->estate);

        ExecDropSingleTupleTableSlot(econtext->ecxt_scantuple);
        FreeExecutorState(state->estate);
    }

    MemoryContextSwitchTo(oldcontext);

    /*
     * Free the per-sort memory context, thereby releasing all working memory,
     * including the Tuplesortstate struct itself.
     */
    MemoryContextDelete(state->sortcontext);
}

void tuplesort_get_stats	(	Tuplesortstate *	state,
		const char **	sortMethod,
		const char **	spaceType,
		long *	spaceUsed
	)

Definition at line 3233 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, Tuplesortstate::boundUsed, LogicalTapeSetBlocks(), Tuplesortstate::status, Tuplesortstate::tapeset, TSS_FINALMERGE, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

Referenced by 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?
     */
    if (state->tapeset)
    {
        *spaceType = "Disk";
        *spaceUsed = LogicalTapeSetBlocks(state->tapeset) * (BLCKSZ / 1024);
    }
    else
    {
        *spaceType = "Memory";
        *spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
    }

    switch (state->status)
    {
        case TSS_SORTEDINMEM:
            if (state->boundUsed)
                *sortMethod = "top-N heapsort";
            else
                *sortMethod = "quicksort";
            break;
        case TSS_SORTEDONTAPE:
            *sortMethod = "external sort";
            break;
        case TSS_FINALMERGE:
            *sortMethod = "external merge";
            break;
        default:
            *sortMethod = "still in progress";
            break;
    }
}

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

Definition at line 2199 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 mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), percentile_disc_multi_final(), process_ordered_aggregate_single(), and validate_index_heapscan().

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

    if (!tuplesort_gettuple_common(state, forward, &stup))
    {
        MemoryContextSwitchTo(oldcontext);
        return false;
    }

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

    MemoryContextSwitchTo(oldcontext);

    return true;
}

HeapTuple tuplesort_getheaptuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 2150 of file tuplesort.c.

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

Referenced by copy_heap_data().

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

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

    MemoryContextSwitchTo(oldcontext);

    return stup.tuple;
}

IndexTuple tuplesort_getindextuple	(	Tuplesortstate *	state,
		bool	forward
	)

Definition at line 2170 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

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

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

    MemoryContextSwitchTo(oldcontext);

    return (IndexTuple) stup.tuple;
}

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

Definition at line 2113 of file tuplesort.c.

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

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

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

void tuplesort_markpos

(

Tuplesortstate *

state

)

Definition at line 3166 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);
}

int tuplesort_merge_order

(

int64

allowedMem

)

Definition at line 2305 of file tuplesort.c.

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

Referenced by cost_sort(), 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;
}

void tuplesort_performsort

(

Tuplesortstate *

state

)

Definition at line 1773 of file tuplesort.c.

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

Referenced by _bt_leafbuild(), _h_indexbuild(), copy_heap_data(), ExecSort(), 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(), and validate_index().

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

#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG, "performsort starting: %s",
             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.  Just qsort 'em and we're done.
             */
            tuplesort_sort_memtuples(state);
            state->current = 0;
            state->eof_reached = false;
            state->markpos_offset = 0;
            state->markpos_eof = false;
            state->status = TSS_SORTEDINMEM;
            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, 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 done (except %d-way final merge): %s",
                 state->activeTapes,
                 pg_rusage_show(&state->ru_start));
        else
            elog(LOG, "performsort done: %s",
                 pg_rusage_show(&state->ru_start));
    }
#endif

    MemoryContextSwitchTo(oldcontext);
}

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

Definition at line 1485 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, NULL, PointerGetDatum, puttuple_common(), Tuplesortstate::sortcontext, Tuplesortstate::sortKeys, SortTuple::tuple, Tuplesortstate::tuplecontext, Tuplesortstate::tuples, and USEMEM.

Referenced by advance_aggregates(), 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);
}

void tuplesort_putheaptuple	(	Tuplesortstate *	state,
		HeapTuple	tup
	)

Definition at line 1386 of file tuplesort.c.

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

Referenced by copy_heap_data().

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

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

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

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

void tuplesort_puttupleslot	(	Tuplesortstate *	state,
		TupleTableSlot *	slot
	)

Definition at line 1364 of file tuplesort.c.

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

Referenced by advance_aggregates(), ExecSort(), fetch_input_tuple(), hypothetical_dense_rank_final(), hypothetical_rank_common(), and ordered_set_transition_multi().

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

void tuplesort_rescan

(

Tuplesortstate *

state

)

Definition at line 3131 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().

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

void tuplesort_restorepos

(

Tuplesortstate *

state

)

Definition at line 3198 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);
}

void tuplesort_set_bound	(	Tuplesortstate *	state,
		int64	bound
	)

Definition at line 1123 of file tuplesort.c.

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

Referenced by ExecSort().

{
    /* Assert we're called before loading any tuples */
    Assert(state->status == TSS_INITIAL);
    Assert(state->memtupcount == 0);
    Assert(!state->bounded);

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

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

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

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);

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