PostgreSQL Source Code git master
tuplesort.h File Reference
#include "access/brin_tuple.h"
#include "access/gin_tuple.h"
#include "access/itup.h"
#include "executor/tuptable.h"
#include "storage/dsm.h"
#include "utils/logtape.h"
#include "utils/relcache.h"
#include "utils/sortsupport.h"
Include dependency graph for tuplesort.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  SortCoordinateData
 
struct  TuplesortInstrumentation
 
struct  SortTuple
 
struct  TuplesortPublic
 

Macros

#define NUM_TUPLESORTMETHODS   4
 
#define TUPLESORT_NONE   0
 
#define TUPLESORT_RANDOMACCESS   (1 << 0)
 
#define TUPLESORT_ALLOWBOUNDED   (1 << 1)
 
#define TupleSortUseBumpTupleCxt(opt)   (((opt) & TUPLESORT_ALLOWBOUNDED) == 0)
 
#define PARALLEL_SORT(coordinate)
 
#define TuplesortstateGetPublic(state)   ((TuplesortPublic *) state)
 
#define LogicalTapeReadExact(tape, ptr, len)
 

Typedefs

typedef struct Tuplesortstate Tuplesortstate
 
typedef struct Sharedsort Sharedsort
 
typedef struct SortCoordinateData SortCoordinateData
 
typedef struct SortCoordinateDataSortCoordinate
 
typedef struct TuplesortInstrumentation TuplesortInstrumentation
 
typedef int(* SortTupleComparator) (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 

Enumerations

enum  TuplesortMethod {
  SORT_TYPE_STILL_IN_PROGRESS = 0 , SORT_TYPE_TOP_N_HEAPSORT = 1 << 0 , SORT_TYPE_QUICKSORT = 1 << 1 , SORT_TYPE_EXTERNAL_SORT = 1 << 2 ,
  SORT_TYPE_EXTERNAL_MERGE = 1 << 3
}
 
enum  TuplesortSpaceType { SORT_SPACE_TYPE_DISK , SORT_SPACE_TYPE_MEMORY }
 

Functions

Tuplesortstatetuplesort_begin_common (int workMem, SortCoordinate coordinate, int sortopt)
 
void tuplesort_set_bound (Tuplesortstate *state, int64 bound)
 
bool tuplesort_used_bound (Tuplesortstate *state)
 
void tuplesort_puttuple_common (Tuplesortstate *state, SortTuple *tuple, bool useAbbrev, Size tuplen)
 
void tuplesort_performsort (Tuplesortstate *state)
 
bool tuplesort_gettuple_common (Tuplesortstate *state, bool forward, SortTuple *stup)
 
bool tuplesort_skiptuples (Tuplesortstate *state, int64 ntuples, bool forward)
 
void tuplesort_end (Tuplesortstate *state)
 
void tuplesort_reset (Tuplesortstate *state)
 
void tuplesort_get_stats (Tuplesortstate *state, TuplesortInstrumentation *stats)
 
const char * tuplesort_method_name (TuplesortMethod m)
 
const char * tuplesort_space_type_name (TuplesortSpaceType t)
 
int tuplesort_merge_order (int64 allowedMem)
 
Size tuplesort_estimate_shared (int nWorkers)
 
void tuplesort_initialize_shared (Sharedsort *shared, int nWorkers, dsm_segment *seg)
 
void tuplesort_attach_shared (Sharedsort *shared, dsm_segment *seg)
 
void tuplesort_rescan (Tuplesortstate *state)
 
void tuplesort_markpos (Tuplesortstate *state)
 
void tuplesort_restorepos (Tuplesortstate *state)
 
void * tuplesort_readtup_alloc (Tuplesortstate *state, Size tuplen)
 
Tuplesortstatetuplesort_begin_heap (TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, bool uniqueNullsNotDistinct, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_gist (Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_brin (int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_gin (Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, int sortopt)
 
void tuplesort_puttupleslot (Tuplesortstate *state, TupleTableSlot *slot)
 
void tuplesort_putheaptuple (Tuplesortstate *state, HeapTuple tup)
 
void tuplesort_putindextuplevalues (Tuplesortstate *state, Relation rel, ItemPointer self, const Datum *values, const bool *isnull)
 
void tuplesort_putbrintuple (Tuplesortstate *state, BrinTuple *tuple, Size size)
 
void tuplesort_putgintuple (Tuplesortstate *state, GinTuple *tuple, Size size)
 
void tuplesort_putdatum (Tuplesortstate *state, Datum val, bool isNull)
 
bool tuplesort_gettupleslot (Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
 
HeapTuple tuplesort_getheaptuple (Tuplesortstate *state, bool forward)
 
IndexTuple tuplesort_getindextuple (Tuplesortstate *state, bool forward)
 
BrinTupletuplesort_getbrintuple (Tuplesortstate *state, Size *len, bool forward)
 
GinTupletuplesort_getgintuple (Tuplesortstate *state, Size *len, bool forward)
 
bool tuplesort_getdatum (Tuplesortstate *state, bool forward, bool copy, Datum *val, bool *isNull, Datum *abbrev)
 

Macro Definition Documentation

◆ LogicalTapeReadExact

#define LogicalTapeReadExact (   tape,
  ptr,
  len 
)
Value:
do { \
if (LogicalTapeRead(tape, ptr, len) != (size_t) (len)) \
elog(ERROR, "unexpected end of data"); \
} while(0)
#define ERROR
Definition: elog.h:39
size_t LogicalTapeRead(LogicalTape *lt, void *ptr, size_t size)
Definition: logtape.c:928
const void size_t len

Definition at line 263 of file tuplesort.h.

◆ NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS   4

Definition at line 85 of file tuplesort.h.

◆ PARALLEL_SORT

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

Definition at line 256 of file tuplesort.h.

◆ TUPLESORT_ALLOWBOUNDED

#define TUPLESORT_ALLOWBOUNDED   (1 << 1)

Definition at line 100 of file tuplesort.h.

◆ TUPLESORT_NONE

#define TUPLESORT_NONE   0

Definition at line 94 of file tuplesort.h.

◆ TUPLESORT_RANDOMACCESS

#define TUPLESORT_RANDOMACCESS   (1 << 0)

Definition at line 97 of file tuplesort.h.

◆ TuplesortstateGetPublic

#define TuplesortstateGetPublic (   state)    ((TuplesortPublic *) state)

Definition at line 260 of file tuplesort.h.

◆ TupleSortUseBumpTupleCxt

#define TupleSortUseBumpTupleCxt (   opt)    (((opt) & TUPLESORT_ALLOWBOUNDED) == 0)

Definition at line 109 of file tuplesort.h.

Typedef Documentation

◆ Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 39 of file tuplesort.h.

◆ SortCoordinate

Definition at line 62 of file tuplesort.h.

◆ SortCoordinateData

◆ SortTupleComparator

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

Definition at line 156 of file tuplesort.h.

◆ TuplesortInstrumentation

◆ Tuplesortstate

Definition at line 38 of file tuplesort.h.

Enumeration Type Documentation

◆ TuplesortMethod

Enumerator
SORT_TYPE_STILL_IN_PROGRESS 
SORT_TYPE_TOP_N_HEAPSORT 
SORT_TYPE_QUICKSORT 
SORT_TYPE_EXTERNAL_SORT 
SORT_TYPE_EXTERNAL_MERGE 

Definition at line 76 of file tuplesort.h.

77{
80 SORT_TYPE_QUICKSORT = 1 << 1,
TuplesortMethod
Definition: tuplesort.h:77
@ SORT_TYPE_EXTERNAL_SORT
Definition: tuplesort.h:81
@ SORT_TYPE_TOP_N_HEAPSORT
Definition: tuplesort.h:79
@ SORT_TYPE_QUICKSORT
Definition: tuplesort.h:80
@ SORT_TYPE_STILL_IN_PROGRESS
Definition: tuplesort.h:78
@ SORT_TYPE_EXTERNAL_MERGE
Definition: tuplesort.h:82

◆ TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK 
SORT_SPACE_TYPE_MEMORY 

Definition at line 87 of file tuplesort.h.

88{
TuplesortSpaceType
Definition: tuplesort.h:88
@ SORT_SPACE_TYPE_DISK
Definition: tuplesort.h:89
@ SORT_SPACE_TYPE_MEMORY
Definition: tuplesort.h:90

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 2961 of file tuplesort.c.

2962{
2963 /* Attach to SharedFileSet */
2964 SharedFileSetAttach(&shared->fileset, seg);
2965}
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:56
SharedFileSet fileset
Definition: tuplesort.c:360

References Sharedsort::fileset, and SharedFileSetAttach().

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

◆ tuplesort_begin_cluster()

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

Definition at line 251 of file tuplesortvariants.c.

255{
256 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
257 sortopt);
259 BTScanInsert indexScanKey;
260 MemoryContext oldcontext;
262 int i;
263
264 Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
265
266 oldcontext = MemoryContextSwitchTo(base->maincontext);
268
269 if (trace_sort)
270 elog(LOG,
271 "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
273 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
274
276
277 TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
278 false, /* no unique check */
279 base->nKeys,
280 workMem,
281 sortopt & TUPLESORT_RANDOMACCESS,
282 PARALLEL_SORT(coordinate));
283
288 base->readtup = readtup_cluster;
290 base->arg = arg;
291
292 arg->indexInfo = BuildIndexInfo(indexRel);
293
294 /*
295 * If we don't have a simple leading attribute, we don't currently
296 * initialize datum1, so disable optimizations that require it.
297 */
298 if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
299 base->haveDatum1 = false;
300 else
301 base->haveDatum1 = true;
302
303 arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
304
305 indexScanKey = _bt_mkscankey(indexRel, NULL);
306
307 if (arg->indexInfo->ii_Expressions != NULL)
308 {
309 TupleTableSlot *slot;
310 ExprContext *econtext;
311
312 /*
313 * We will need to use FormIndexDatum to evaluate the index
314 * expressions. To do that, we need an EState, as well as a
315 * TupleTableSlot to put the table tuples into. The econtext's
316 * scantuple has to point to that slot, too.
317 */
318 arg->estate = CreateExecutorState();
320 econtext = GetPerTupleExprContext(arg->estate);
321 econtext->ecxt_scantuple = slot;
322 }
323
324 /* Prepare SortSupport data for each column */
325 base->sortKeys = (SortSupport) palloc0(base->nKeys *
326 sizeof(SortSupportData));
327
328 for (i = 0; i < base->nKeys; i++)
329 {
330 SortSupport sortKey = base->sortKeys + i;
331 ScanKey scanKey = indexScanKey->scankeys + i;
332 bool reverse;
333
335 sortKey->ssup_collation = scanKey->sk_collation;
336 sortKey->ssup_nulls_first =
337 (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
338 sortKey->ssup_attno = scanKey->sk_attno;
339 /* Convey if abbreviation optimization is applicable in principle */
340 sortKey->abbreviate = (i == 0 && base->haveDatum1);
341
342 Assert(sortKey->ssup_attno != 0);
343
344 reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
345
346 PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
347 }
348
349 pfree(indexScanKey);
350
351 MemoryContextSwitchTo(oldcontext);
352
353 return state;
354}
#define LOG
Definition: elog.h:31
#define elog(elevel,...)
Definition: elog.h:225
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1425
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:85
EState * CreateExecutorState(void)
Definition: execUtils.c:88
#define GetPerTupleExprContext(estate)
Definition: executor.h:637
Assert(PointerIsAligned(start, uint64))
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2428
int i
Definition: isn.c:74
void pfree(void *pointer)
Definition: mcxt.c:1524
void * palloc0(Size size)
Definition: mcxt.c:1347
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1124
#define SK_BT_DESC
Definition: nbtree.h:1123
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:82
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
void * arg
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:519
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:532
void PrepareSortSupportFromIndexRel(Relation indexRel, bool reverse, SortSupport ssup)
Definition: sortsupport.c:161
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:798
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:268
Form_pg_class rd_rel
Definition: rel.h:111
int sk_flags
Definition: skey.h:66
Oid sk_collation
Definition: skey.h:70
AttrNumber sk_attno
Definition: skey.h:67
AttrNumber ssup_attno
Definition: sortsupport.h:81
bool ssup_nulls_first
Definition: sortsupport.h:75
MemoryContext ssup_cxt
Definition: sortsupport.h:66
MemoryContext maincontext
Definition: tuplesort.h:219
void(* writetup)(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.h:195
void(* removeabbrev)(Tuplesortstate *state, SortTuple *stups, int count)
Definition: tuplesort.h:188
void(* freestate)(Tuplesortstate *state)
Definition: tuplesort.h:213
void(* readtup)(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.h:204
SortTupleComparator comparetup
Definition: tuplesort.h:175
SortSupport sortKeys
Definition: tuplesort.h:236
SortTupleComparator comparetup_tiebreak
Definition: tuplesort.h:182
Definition: regguts.h:323
Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
Definition: tuplesort.c:642
bool trace_sort
Definition: tuplesort.c:124
#define PARALLEL_SORT(coordinate)
Definition: tuplesort.h:256
#define TUPLESORT_RANDOMACCESS
Definition: tuplesort.h:97
#define TuplesortstateGetPublic(state)
Definition: tuplesort.h:260
static int comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int tuplen)
#define CLUSTER_SORT
static void freestate_cluster(Tuplesortstate *state)
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void writetup_cluster(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static void removeabbrev_cluster(Tuplesortstate *state, SortTuple *stups, int count)

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), BuildIndexInfo(), CLUSTER_SORT, TuplesortPublic::comparetup, comparetup_cluster(), comparetup_cluster_tiebreak(), TuplesortPublic::comparetup_tiebreak, CreateExecutorState(), CurrentMemoryContext, ExprContext::ecxt_scantuple, elog, TuplesortPublic::freestate, freestate_cluster(), GetPerTupleExprContext, TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, TuplesortPublic::readtup, readtup_cluster(), RelationGetNumberOfAttributes, TuplesortPublic::removeabbrev, removeabbrev_cluster(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TTSOpsHeapTuple, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_cluster().

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_begin_common()

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

Definition at line 642 of file tuplesort.c.

643{
645 MemoryContext maincontext;
646 MemoryContext sortcontext;
647 MemoryContext oldcontext;
648
649 /* See leader_takeover_tapes() remarks on random access support */
650 if (coordinate && (sortopt & TUPLESORT_RANDOMACCESS))
651 elog(ERROR, "random access disallowed under parallel sort");
652
653 /*
654 * Memory context surviving tuplesort_reset. This memory context holds
655 * data which is useful to keep while sorting multiple similar batches.
656 */
658 "TupleSort main",
660
661 /*
662 * Create a working memory context for one sort operation. The content of
663 * this context is deleted by tuplesort_reset.
664 */
665 sortcontext = AllocSetContextCreate(maincontext,
666 "TupleSort sort",
668
669 /*
670 * Additionally a working memory context for tuples is setup in
671 * tuplesort_begin_batch.
672 */
673
674 /*
675 * Make the Tuplesortstate within the per-sortstate context. This way, we
676 * don't need a separate pfree() operation for it at shutdown.
677 */
678 oldcontext = MemoryContextSwitchTo(maincontext);
679
681
682 if (trace_sort)
683 pg_rusage_init(&state->ru_start);
684
685 state->base.sortopt = sortopt;
686 state->base.tuples = true;
687 state->abbrevNext = 10;
688
689 /*
690 * workMem is forced to be at least 64KB, the current minimum valid value
691 * for the work_mem GUC. This is a defense against parallel sort callers
692 * that divide out memory among many workers in a way that leaves each
693 * with very little memory.
694 */
695 state->allowedMem = Max(workMem, 64) * (int64) 1024;
696 state->base.sortcontext = sortcontext;
697 state->base.maincontext = maincontext;
698
699 /*
700 * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
701 * see comments in grow_memtuples().
702 */
703 state->memtupsize = INITIAL_MEMTUPSIZE;
704 state->memtuples = NULL;
705
706 /*
707 * After all of the other non-parallel-related state, we setup all of the
708 * state needed for each batch.
709 */
711
712 /*
713 * Initialize parallel-related state based on coordination information
714 * from caller
715 */
716 if (!coordinate)
717 {
718 /* Serial sort */
719 state->shared = NULL;
720 state->worker = -1;
721 state->nParticipants = -1;
722 }
723 else if (coordinate->isWorker)
724 {
725 /* Parallel worker produces exactly one final run from all input */
726 state->shared = coordinate->sharedsort;
728 state->nParticipants = -1;
729 }
730 else
731 {
732 /* Parallel leader state only used for final merge */
733 state->shared = coordinate->sharedsort;
734 state->worker = -1;
735 state->nParticipants = coordinate->nParticipants;
736 Assert(state->nParticipants >= 1);
737 }
738
739 MemoryContextSwitchTo(oldcontext);
740
741 return state;
742}
#define Max(x, y)
Definition: c.h:969
int64_t int64
Definition: c.h:499
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:160
void pg_rusage_init(PGRUsage *ru0)
Definition: pg_rusage.c:27
Sharedsort * sharedsort
Definition: tuplesort.h:59
#define INITIAL_MEMTUPSIZE
Definition: tuplesort.c:120
static int worker_get_identifier(Tuplesortstate *state)
Definition: tuplesort.c:2981
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:752

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), CurrentMemoryContext, elog, ERROR, INITIAL_MEMTUPSIZE, SortCoordinateData::isWorker, Max, MemoryContextSwitchTo(), SortCoordinateData::nParticipants, palloc0(), pg_rusage_init(), SortCoordinateData::sharedsort, trace_sort, tuplesort_begin_batch(), TUPLESORT_RANDOMACCESS, and worker_get_identifier().

Referenced by tuplesort_begin_cluster(), tuplesort_begin_datum(), tuplesort_begin_heap(), tuplesort_begin_index_brin(), tuplesort_begin_index_btree(), tuplesort_begin_index_gin(), tuplesort_begin_index_gist(), and tuplesort_begin_index_hash().

◆ tuplesort_begin_datum()

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

Definition at line 651 of file tuplesortvariants.c.

654{
655 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
656 sortopt);
659 MemoryContext oldcontext;
660 int16 typlen;
661 bool typbyval;
662
663 oldcontext = MemoryContextSwitchTo(base->maincontext);
665
666 if (trace_sort)
667 elog(LOG,
668 "begin datum sort: workMem = %d, randomAccess = %c",
669 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
670
671 base->nKeys = 1; /* always a one-column sort */
672
673 TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
674 false, /* no unique check */
675 1,
676 workMem,
677 sortopt & TUPLESORT_RANDOMACCESS,
678 PARALLEL_SORT(coordinate));
679
683 base->writetup = writetup_datum;
684 base->readtup = readtup_datum;
685 base->haveDatum1 = true;
686 base->arg = arg;
687
688 arg->datumType = datumType;
689
690 /* lookup necessary attributes of the datum type */
691 get_typlenbyval(datumType, &typlen, &typbyval);
692 arg->datumTypeLen = typlen;
693 base->tuples = !typbyval;
694
695 /* Prepare SortSupport data */
696 base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
697
699 base->sortKeys->ssup_collation = sortCollation;
700 base->sortKeys->ssup_nulls_first = nullsFirstFlag;
701
702 /*
703 * Abbreviation is possible here only for by-reference types. In theory,
704 * a pass-by-value datatype could have an abbreviated form that is cheaper
705 * to compare. In a tuple sort, we could support that, because we can
706 * always extract the original datum from the tuple as needed. Here, we
707 * can't, because a datum sort only stores a single copy of the datum; the
708 * "tuple" field of each SortTuple is NULL.
709 */
710 base->sortKeys->abbreviate = !typbyval;
711
712 PrepareSortSupportFromOrderingOp(sortOperator, base->sortKeys);
713
714 /*
715 * The "onlyKey" optimization cannot be used with abbreviated keys, since
716 * tie-breaker comparisons may be required. Typically, the optimization
717 * is only of value to pass-by-value types anyway, whereas abbreviated
718 * keys are typically only of value to pass-by-reference types.
719 */
720 if (!base->sortKeys->abbrev_converter)
721 base->onlyKey = base->sortKeys;
722
723 MemoryContextSwitchTo(oldcontext);
724
725 return state;
726}
int16_t int16
Definition: c.h:497
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2334
void * palloc(Size size)
Definition: mcxt.c:1317
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
SortSupport onlyKey
Definition: tuplesort.h:246
static void removeabbrev_datum(Tuplesortstate *state, SortTuple *stups, int count)
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static int comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static void writetup_datum(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
#define DATUM_SORT

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, arg, TuplesortPublic::arg, TuplesortPublic::comparetup, comparetup_datum(), comparetup_datum_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, DATUM_SORT, elog, get_typlenbyval(), TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, TuplesortPublic::onlyKey, palloc(), palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), TuplesortPublic::readtup, readtup_datum(), TuplesortPublic::removeabbrev, removeabbrev_datum(), TuplesortPublic::sortKeys, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TuplesortPublic::tuples, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_datum().

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

◆ tuplesort_begin_heap()

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

Definition at line 178 of file tuplesortvariants.c.

183{
184 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
185 sortopt);
187 MemoryContext oldcontext;
188 int i;
189
190 oldcontext = MemoryContextSwitchTo(base->maincontext);
191
192 Assert(nkeys > 0);
193
194 if (trace_sort)
195 elog(LOG,
196 "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
197 nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
198
199 base->nKeys = nkeys;
200
201 TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
202 false, /* no unique check */
203 nkeys,
204 workMem,
205 sortopt & TUPLESORT_RANDOMACCESS,
206 PARALLEL_SORT(coordinate));
207
211 base->writetup = writetup_heap;
212 base->readtup = readtup_heap;
213 base->haveDatum1 = true;
214 base->arg = tupDesc; /* assume we need not copy tupDesc */
215
216 /* Prepare SortSupport data for each column */
217 base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
218
219 for (i = 0; i < nkeys; i++)
220 {
221 SortSupport sortKey = base->sortKeys + i;
222
223 Assert(attNums[i] != 0);
224 Assert(sortOperators[i] != 0);
225
227 sortKey->ssup_collation = sortCollations[i];
228 sortKey->ssup_nulls_first = nullsFirstFlags[i];
229 sortKey->ssup_attno = attNums[i];
230 /* Convey if abbreviation optimization is applicable in principle */
231 sortKey->abbreviate = (i == 0 && base->haveDatum1);
232
233 PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
234 }
235
236 /*
237 * The "onlyKey" optimization cannot be used with abbreviated keys, since
238 * tie-breaker comparisons may be required. Typically, the optimization
239 * is only of value to pass-by-value types anyway, whereas abbreviated
240 * keys are typically only of value to pass-by-reference types.
241 */
242 if (nkeys == 1 && !base->sortKeys->abbrev_converter)
243 base->onlyKey = base->sortKeys;
244
245 MemoryContextSwitchTo(oldcontext);
246
247 return state;
248}
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static int comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void writetup_heap(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static int comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void removeabbrev_heap(Tuplesortstate *state, SortTuple *stups, int count)
#define HEAP_SORT

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_heap(), comparetup_heap_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog, TuplesortPublic::haveDatum1, HEAP_SORT, i, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, TuplesortPublic::onlyKey, palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), TuplesortPublic::readtup, readtup_heap(), TuplesortPublic::removeabbrev, removeabbrev_heap(), TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_heap().

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

◆ tuplesort_begin_index_brin()

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

Definition at line 553 of file tuplesortvariants.c.

556{
557 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
558 sortopt);
560
561 if (trace_sort)
562 elog(LOG,
563 "begin index sort: workMem = %d, randomAccess = %c",
564 workMem,
565 sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
566
567 base->nKeys = 1; /* Only one sort column, the block number */
568
573 base->haveDatum1 = true;
574 base->arg = NULL;
575
576 return state;
577}
static void writetup_index_brin(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static void removeabbrev_index_brin(Tuplesortstate *state, SortTuple *stups, int count)
static void readtup_index_brin(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static int comparetup_index_brin(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)

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

Referenced by _brin_parallel_scan_and_build(), and brinbuild().

◆ tuplesort_begin_index_btree()

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

Definition at line 357 of file tuplesortvariants.c.

364{
365 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
366 sortopt);
368 BTScanInsert indexScanKey;
370 MemoryContext oldcontext;
371 int i;
372
373 oldcontext = MemoryContextSwitchTo(base->maincontext);
375
376 if (trace_sort)
377 elog(LOG,
378 "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
379 enforceUnique ? 't' : 'f',
380 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
381
383
384 TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
385 enforceUnique,
386 base->nKeys,
387 workMem,
388 sortopt & TUPLESORT_RANDOMACCESS,
389 PARALLEL_SORT(coordinate));
390
394 base->writetup = writetup_index;
395 base->readtup = readtup_index;
396 base->haveDatum1 = true;
397 base->arg = arg;
398
399 arg->index.heapRel = heapRel;
400 arg->index.indexRel = indexRel;
401 arg->enforceUnique = enforceUnique;
402 arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
403
404 indexScanKey = _bt_mkscankey(indexRel, NULL);
405
406 /* Prepare SortSupport data for each column */
407 base->sortKeys = (SortSupport) palloc0(base->nKeys *
408 sizeof(SortSupportData));
409
410 for (i = 0; i < base->nKeys; i++)
411 {
412 SortSupport sortKey = base->sortKeys + i;
413 ScanKey scanKey = indexScanKey->scankeys + i;
414 bool reverse;
415
417 sortKey->ssup_collation = scanKey->sk_collation;
418 sortKey->ssup_nulls_first =
419 (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
420 sortKey->ssup_attno = scanKey->sk_attno;
421 /* Convey if abbreviation optimization is applicable in principle */
422 sortKey->abbreviate = (i == 0 && base->haveDatum1);
423
424 Assert(sortKey->ssup_attno != 0);
425
426 reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
427
428 PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
429 }
430
431 pfree(indexScanKey);
432
433 MemoryContextSwitchTo(oldcontext);
434
435 return state;
436}
static int comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_index(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static void removeabbrev_index(Tuplesortstate *state, SortTuple *stups, int count)
#define INDEX_SORT
static void writetup_index(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_index_btree(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog, TuplesortPublic::haveDatum1, i, INDEX_SORT, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

◆ tuplesort_begin_index_gin()

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

Definition at line 580 of file tuplesortvariants.c.

584{
585 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
586 sortopt);
588 MemoryContext oldcontext;
589 int i;
590 TupleDesc desc = RelationGetDescr(indexRel);
591
592 oldcontext = MemoryContextSwitchTo(base->maincontext);
593
594#ifdef TRACE_SORT
595 if (trace_sort)
596 elog(LOG,
597 "begin index sort: workMem = %d, randomAccess = %c",
598 workMem,
599 sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
600#endif
601
602 /*
603 * Multi-column GIN indexes expand the row into a separate index entry for
604 * attribute, and that's what we write into the tuplesort. But we still
605 * need to initialize sortsupport for all the attributes.
606 */
608
609 /* Prepare SortSupport data for each column */
610 base->sortKeys = (SortSupport) palloc0(base->nKeys *
611 sizeof(SortSupportData));
612
613 for (i = 0; i < base->nKeys; i++)
614 {
615 SortSupport sortKey = base->sortKeys + i;
616 Form_pg_attribute att = TupleDescAttr(desc, i);
617 TypeCacheEntry *typentry;
618
620 sortKey->ssup_collation = indexRel->rd_indcollation[i];
621 sortKey->ssup_nulls_first = false;
622 sortKey->ssup_attno = i + 1;
623 sortKey->abbreviate = false;
624
625 Assert(sortKey->ssup_attno != 0);
626
627 if (!OidIsValid(sortKey->ssup_collation))
628 sortKey->ssup_collation = DEFAULT_COLLATION_OID;
629
630 /*
631 * Look for a ordering for the index key data type, and then the sort
632 * support function.
633 */
634 typentry = lookup_type_cache(att->atttypid, TYPECACHE_LT_OPR);
635 PrepareSortSupportFromOrderingOp(typentry->lt_opr, sortKey);
636 }
637
642 base->haveDatum1 = false;
643 base->arg = NULL;
644
645 MemoryContextSwitchTo(oldcontext);
646
647 return state;
648}
#define OidIsValid(objectId)
Definition: c.h:746
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:200
#define RelationGetDescr(relation)
Definition: rel.h:539
Oid * rd_indcollation
Definition: rel.h:217
static FormData_pg_attribute * TupleDescAttr(TupleDesc tupdesc, int i)
Definition: tupdesc.h:154
static void writetup_index_gin(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static void readtup_index_gin(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static void removeabbrev_index_gin(Tuplesortstate *state, SortTuple *stups, int count)
static int comparetup_index_gin(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:386
#define TYPECACHE_LT_OPR
Definition: typcache.h:138

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

Referenced by _gin_parallel_scan_and_build(), and ginbuild().

◆ tuplesort_begin_index_gist()

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

Definition at line 490 of file tuplesortvariants.c.

495{
496 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
497 sortopt);
499 MemoryContext oldcontext;
501 int i;
502
503 oldcontext = MemoryContextSwitchTo(base->maincontext);
505
506 if (trace_sort)
507 elog(LOG,
508 "begin index sort: workMem = %d, randomAccess = %c",
509 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
510
512
516 base->writetup = writetup_index;
517 base->readtup = readtup_index;
518 base->haveDatum1 = true;
519 base->arg = arg;
520
521 arg->index.heapRel = heapRel;
522 arg->index.indexRel = indexRel;
523 arg->enforceUnique = false;
524 arg->uniqueNullsNotDistinct = false;
525
526 /* Prepare SortSupport data for each column */
527 base->sortKeys = (SortSupport) palloc0(base->nKeys *
528 sizeof(SortSupportData));
529
530 for (i = 0; i < base->nKeys; i++)
531 {
532 SortSupport sortKey = base->sortKeys + i;
533
535 sortKey->ssup_collation = indexRel->rd_indcollation[i];
536 sortKey->ssup_nulls_first = false;
537 sortKey->ssup_attno = i + 1;
538 /* Convey if abbreviation optimization is applicable in principle */
539 sortKey->abbreviate = (i == 0 && base->haveDatum1);
540
541 Assert(sortKey->ssup_attno != 0);
542
543 /* Look for a sort support function */
544 PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
545 }
546
547 MemoryContextSwitchTo(oldcontext);
548
549 return state;
550}
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:185

References SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_index_btree(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog, TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), palloc0(), PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by gistbuild().

◆ tuplesort_begin_index_hash()

Tuplesortstate * tuplesort_begin_index_hash ( Relation  heapRel,
Relation  indexRel,
uint32  high_mask,
uint32  low_mask,
uint32  max_buckets,
int  workMem,
SortCoordinate  coordinate,
int  sortopt 
)

Definition at line 439 of file tuplesortvariants.c.

447{
448 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
449 sortopt);
451 MemoryContext oldcontext;
453
454 oldcontext = MemoryContextSwitchTo(base->maincontext);
456
457 if (trace_sort)
458 elog(LOG,
459 "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
460 "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
461 high_mask,
462 low_mask,
463 max_buckets,
464 workMem,
465 sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
466
467 base->nKeys = 1; /* Only one sort column, the hash code */
468
472 base->writetup = writetup_index;
473 base->readtup = readtup_index;
474 base->haveDatum1 = true;
475 base->arg = arg;
476
477 arg->index.heapRel = heapRel;
478 arg->index.indexRel = indexRel;
479
480 arg->high_mask = high_mask;
481 arg->low_mask = low_mask;
482 arg->max_buckets = max_buckets;
483
484 MemoryContextSwitchTo(oldcontext);
485
486 return state;
487}
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static int comparetup_index_hash_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)

References arg, TuplesortPublic::arg, TuplesortPublic::comparetup, comparetup_index_hash(), comparetup_index_hash_tiebreak(), TuplesortPublic::comparetup_tiebreak, elog, TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by _h_spoolinit().

◆ tuplesort_end()

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nWorkers)

Definition at line 2917 of file tuplesort.c.

2918{
2919 Size tapesSize;
2920
2921 Assert(nWorkers > 0);
2922
2923 /* Make sure that BufFile shared state is MAXALIGN'd */
2924 tapesSize = mul_size(sizeof(TapeShare), nWorkers);
2925 tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
2926
2927 return tapesSize;
2928}
#define MAXALIGN(LEN)
Definition: c.h:782
size_t Size
Definition: c.h:576
Size add_size(Size s1, Size s2)
Definition: shmem.c:488
Size mul_size(Size s1, Size s2)
Definition: shmem.c:505

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

Referenced by _brin_begin_parallel(), _bt_begin_parallel(), and _gin_begin_parallel().

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 2499 of file tuplesort.c.

2501{
2502 /*
2503 * Note: it might seem we should provide both memory and disk usage for a
2504 * disk-based sort. However, the current code doesn't track memory space
2505 * accurately once we have begun to return tuples to the caller (since we
2506 * don't account for pfree's the caller is expected to do), so we cannot
2507 * rely on availMem in a disk sort. This does not seem worth the overhead
2508 * to fix. Is it worth creating an API for the memory context code to
2509 * tell us how much is actually used in sortcontext?
2510 */
2512
2513 if (state->isMaxSpaceDisk)
2515 else
2517 stats->spaceUsed = (state->maxSpace + 1023) / 1024;
2518
2519 switch (state->maxSpaceStatus)
2520 {
2521 case TSS_SORTEDINMEM:
2522 if (state->boundUsed)
2524 else
2526 break;
2527 case TSS_SORTEDONTAPE:
2529 break;
2530 case TSS_FINALMERGE:
2532 break;
2533 default:
2535 break;
2536 }
2537}
TuplesortMethod sortMethod
Definition: tuplesort.h:113
TuplesortSpaceType spaceType
Definition: tuplesort.h:114
@ TSS_SORTEDONTAPE
Definition: tuplesort.c:160
@ TSS_SORTEDINMEM
Definition: tuplesort.c:159
@ TSS_FINALMERGE
Definition: tuplesort.c:161
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:968

References SORT_SPACE_TYPE_DISK, SORT_SPACE_TYPE_MEMORY, SORT_TYPE_EXTERNAL_MERGE, SORT_TYPE_EXTERNAL_SORT, SORT_TYPE_QUICKSORT, SORT_TYPE_STILL_IN_PROGRESS, SORT_TYPE_TOP_N_HEAPSORT, TuplesortInstrumentation::sortMethod, TuplesortInstrumentation::spaceType, TuplesortInstrumentation::spaceUsed, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and tuplesort_updatemax().

Referenced by ExecSort(), instrumentSortedGroup(), and show_sort_info().

◆ tuplesort_getbrintuple()

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

Definition at line 1066 of file tuplesortvariants.c.

1067{
1070 SortTuple stup;
1071 BrinSortTuple *btup;
1072
1073 if (!tuplesort_gettuple_common(state, forward, &stup))
1074 stup.tuple = NULL;
1075
1076 MemoryContextSwitchTo(oldcontext);
1077
1078 if (!stup.tuple)
1079 return NULL;
1080
1081 btup = (BrinSortTuple *) stup.tuple;
1082
1083 *len = btup->tuplen;
1084
1085 return &btup->tuple;
1086}
void * tuple
Definition: tuplesort.h:150
MemoryContext sortcontext
Definition: tuplesort.h:221
bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1470

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

Referenced by _brin_parallel_merge().

◆ tuplesort_getdatum()

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

Definition at line 1137 of file tuplesortvariants.c.

1139{
1143 SortTuple stup;
1144
1145 if (!tuplesort_gettuple_common(state, forward, &stup))
1146 {
1147 MemoryContextSwitchTo(oldcontext);
1148 return false;
1149 }
1150
1151 /* Ensure we copy into caller's memory context */
1152 MemoryContextSwitchTo(oldcontext);
1153
1154 /* Record abbreviated key for caller */
1155 if (base->sortKeys->abbrev_converter && abbrev)
1156 *abbrev = stup.datum1;
1157
1158 if (stup.isnull1 || !base->tuples)
1159 {
1160 *val = stup.datum1;
1161 *isNull = stup.isnull1;
1162 }
1163 else
1164 {
1165 /* use stup.tuple because stup.datum1 may be an abbreviation */
1166 if (copy)
1167 *val = datumCopy(PointerGetDatum(stup.tuple), false,
1168 arg->datumTypeLen);
1169 else
1170 *val = PointerGetDatum(stup.tuple);
1171 *isNull = false;
1172 }
1173
1174 return true;
1175}
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
long val
Definition: informix.c:689
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:78
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:327

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

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

◆ tuplesort_getgintuple()

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

Definition at line 1089 of file tuplesortvariants.c.

1090{
1093 SortTuple stup;
1094 GinTuple *tup;
1095
1096 if (!tuplesort_gettuple_common(state, forward, &stup))
1097 stup.tuple = NULL;
1098
1099 MemoryContextSwitchTo(oldcontext);
1100
1101 if (!stup.tuple)
1102 return false;
1103
1104 tup = (GinTuple *) stup.tuple;
1105
1106 *len = tup->tuplen;
1107
1108 return tup;
1109}
int tuplen
Definition: gin_tuple.h:22

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

Referenced by _gin_parallel_merge(), and _gin_process_worker_data().

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 1024 of file tuplesortvariants.c.

1025{
1028 SortTuple stup;
1029
1030 if (!tuplesort_gettuple_common(state, forward, &stup))
1031 stup.tuple = NULL;
1032
1033 MemoryContextSwitchTo(oldcontext);
1034
1035 return stup.tuple;
1036}

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

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 1045 of file tuplesortvariants.c.

1046{
1049 SortTuple stup;
1050
1051 if (!tuplesort_gettuple_common(state, forward, &stup))
1052 stup.tuple = NULL;
1053
1054 MemoryContextSwitchTo(oldcontext);
1055
1056 return (IndexTuple) stup.tuple;
1057}

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

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

◆ tuplesort_gettuple_common()

bool tuplesort_gettuple_common ( Tuplesortstate state,
bool  forward,
SortTuple stup 
)

Definition at line 1470 of file tuplesort.c.

1472{
1473 unsigned int tuplen;
1474 size_t nmoved;
1475
1476 Assert(!WORKER(state));
1477
1478 switch (state->status)
1479 {
1480 case TSS_SORTEDINMEM:
1481 Assert(forward || state->base.sortopt & TUPLESORT_RANDOMACCESS);
1482 Assert(!state->slabAllocatorUsed);
1483 if (forward)
1484 {
1485 if (state->current < state->memtupcount)
1486 {
1487 *stup = state->memtuples[state->current++];
1488 return true;
1489 }
1490 state->eof_reached = true;
1491
1492 /*
1493 * Complain if caller tries to retrieve more tuples than
1494 * originally asked for in a bounded sort. This is because
1495 * returning EOF here might be the wrong thing.
1496 */
1497 if (state->bounded && state->current >= state->bound)
1498 elog(ERROR, "retrieved too many tuples in a bounded sort");
1499
1500 return false;
1501 }
1502 else
1503 {
1504 if (state->current <= 0)
1505 return false;
1506
1507 /*
1508 * if all tuples are fetched already then we return last
1509 * tuple, else - tuple before last returned.
1510 */
1511 if (state->eof_reached)
1512 state->eof_reached = false;
1513 else
1514 {
1515 state->current--; /* last returned tuple */
1516 if (state->current <= 0)
1517 return false;
1518 }
1519 *stup = state->memtuples[state->current - 1];
1520 return true;
1521 }
1522 break;
1523
1524 case TSS_SORTEDONTAPE:
1525 Assert(forward || state->base.sortopt & TUPLESORT_RANDOMACCESS);
1526 Assert(state->slabAllocatorUsed);
1527
1528 /*
1529 * The slot that held the tuple that we returned in previous
1530 * gettuple call can now be reused.
1531 */
1532 if (state->lastReturnedTuple)
1533 {
1534 RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1535 state->lastReturnedTuple = NULL;
1536 }
1537
1538 if (forward)
1539 {
1540 if (state->eof_reached)
1541 return false;
1542
1543 if ((tuplen = getlen(state->result_tape, true)) != 0)
1544 {
1545 READTUP(state, stup, state->result_tape, tuplen);
1546
1547 /*
1548 * Remember the tuple we return, so that we can recycle
1549 * its memory on next call. (This can be NULL, in the
1550 * !state->tuples case).
1551 */
1552 state->lastReturnedTuple = stup->tuple;
1553
1554 return true;
1555 }
1556 else
1557 {
1558 state->eof_reached = true;
1559 return false;
1560 }
1561 }
1562
1563 /*
1564 * Backward.
1565 *
1566 * if all tuples are fetched already then we return last tuple,
1567 * else - tuple before last returned.
1568 */
1569 if (state->eof_reached)
1570 {
1571 /*
1572 * Seek position is pointing just past the zero tuplen at the
1573 * end of file; back up to fetch last tuple's ending length
1574 * word. If seek fails we must have a completely empty file.
1575 */
1576 nmoved = LogicalTapeBackspace(state->result_tape,
1577 2 * sizeof(unsigned int));
1578 if (nmoved == 0)
1579 return false;
1580 else if (nmoved != 2 * sizeof(unsigned int))
1581 elog(ERROR, "unexpected tape position");
1582 state->eof_reached = false;
1583 }
1584 else
1585 {
1586 /*
1587 * Back up and fetch previously-returned tuple's ending length
1588 * word. If seek fails, assume we are at start of file.
1589 */
1590 nmoved = LogicalTapeBackspace(state->result_tape,
1591 sizeof(unsigned int));
1592 if (nmoved == 0)
1593 return false;
1594 else if (nmoved != sizeof(unsigned int))
1595 elog(ERROR, "unexpected tape position");
1596 tuplen = getlen(state->result_tape, false);
1597
1598 /*
1599 * Back up to get ending length word of tuple before it.
1600 */
1601 nmoved = LogicalTapeBackspace(state->result_tape,
1602 tuplen + 2 * sizeof(unsigned int));
1603 if (nmoved == tuplen + sizeof(unsigned int))
1604 {
1605 /*
1606 * We backed up over the previous tuple, but there was no
1607 * ending length word before it. That means that the prev
1608 * tuple is the first tuple in the file. It is now the
1609 * next to read in forward direction (not obviously right,
1610 * but that is what in-memory case does).
1611 */
1612 return false;
1613 }
1614 else if (nmoved != tuplen + 2 * sizeof(unsigned int))
1615 elog(ERROR, "bogus tuple length in backward scan");
1616 }
1617
1618 tuplen = getlen(state->result_tape, false);
1619
1620 /*
1621 * Now we have the length of the prior tuple, back up and read it.
1622 * Note: READTUP expects we are positioned after the initial
1623 * length word of the tuple, so back up to that point.
1624 */
1625 nmoved = LogicalTapeBackspace(state->result_tape,
1626 tuplen);
1627 if (nmoved != tuplen)
1628 elog(ERROR, "bogus tuple length in backward scan");
1629 READTUP(state, stup, state->result_tape, tuplen);
1630
1631 /*
1632 * Remember the tuple we return, so that we can recycle its memory
1633 * on next call. (This can be NULL, in the Datum case).
1634 */
1635 state->lastReturnedTuple = stup->tuple;
1636
1637 return true;
1638
1639 case TSS_FINALMERGE:
1640 Assert(forward);
1641 /* We are managing memory ourselves, with the slab allocator. */
1642 Assert(state->slabAllocatorUsed);
1643
1644 /*
1645 * The slab slot holding the tuple that we returned in previous
1646 * gettuple call can now be reused.
1647 */
1648 if (state->lastReturnedTuple)
1649 {
1650 RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1651 state->lastReturnedTuple = NULL;
1652 }
1653
1654 /*
1655 * This code should match the inner loop of mergeonerun().
1656 */
1657 if (state->memtupcount > 0)
1658 {
1659 int srcTapeIndex = state->memtuples[0].srctape;
1660 LogicalTape *srcTape = state->inputTapes[srcTapeIndex];
1661 SortTuple newtup;
1662
1663 *stup = state->memtuples[0];
1664
1665 /*
1666 * Remember the tuple we return, so that we can recycle its
1667 * memory on next call. (This can be NULL, in the Datum case).
1668 */
1669 state->lastReturnedTuple = stup->tuple;
1670
1671 /*
1672 * Pull next tuple from tape, and replace the returned tuple
1673 * at top of the heap with it.
1674 */
1675 if (!mergereadnext(state, srcTape, &newtup))
1676 {
1677 /*
1678 * If no more data, we've reached end of run on this tape.
1679 * Remove the top node from the heap.
1680 */
1682 state->nInputRuns--;
1683
1684 /*
1685 * Close the tape. It'd go away at the end of the sort
1686 * anyway, but better to release the memory early.
1687 */
1688 LogicalTapeClose(srcTape);
1689 return true;
1690 }
1691 newtup.srctape = srcTapeIndex;
1693 return true;
1694 }
1695 return false;
1696
1697 default:
1698 elog(ERROR, "invalid tuplesort state");
1699 return false; /* keep compiler quiet */
1700 }
1701}
size_t LogicalTapeBackspace(LogicalTape *lt, size_t size)
Definition: logtape.c:1062
void LogicalTapeClose(LogicalTape *lt)
Definition: logtape.c:733
int srctape
Definition: tuplesort.h:153
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:2774
static unsigned int getlen(LogicalTape *tape, bool eofOK)
Definition: tuplesort.c:2856
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:398
#define WORKER(state)
Definition: tuplesort.c:404
static bool mergereadnext(Tuplesortstate *state, LogicalTape *srcTape, SortTuple *stup)
Definition: tuplesort.c:2288
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:383
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:2798

References Assert(), elog, ERROR, getlen(), LogicalTapeBackspace(), LogicalTapeClose(), mergereadnext(), READTUP, RELEASE_SLAB_SLOT, SortTuple::srctape, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, SortTuple::tuple, tuplesort_heap_delete_top(), tuplesort_heap_replace_top(), TUPLESORT_RANDOMACCESS, and WORKER.

Referenced by tuplesort_getbrintuple(), tuplesort_getdatum(), tuplesort_getgintuple(), tuplesort_getheaptuple(), tuplesort_getindextuple(), tuplesort_gettupleslot(), and tuplesort_skiptuples().

◆ tuplesort_gettupleslot()

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

Definition at line 986 of file tuplesortvariants.c.

988{
991 SortTuple stup;
992
993 if (!tuplesort_gettuple_common(state, forward, &stup))
994 stup.tuple = NULL;
995
996 MemoryContextSwitchTo(oldcontext);
997
998 if (stup.tuple)
999 {
1000 /* Record abbreviated key for caller */
1001 if (base->sortKeys->abbrev_converter && abbrev)
1002 *abbrev = stup.datum1;
1003
1004 if (copy)
1006
1007 ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
1008 return true;
1009 }
1010 else
1011 {
1012 ExecClearTuple(slot);
1013 return false;
1014 }
1015}
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1633
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1536
Datum datum1
Definition: tuplesort.h:151
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:454

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

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

◆ tuplesort_initialize_shared()

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

Definition at line 2938 of file tuplesort.c.

2939{
2940 int i;
2941
2942 Assert(nWorkers > 0);
2943
2944 SpinLockInit(&shared->mutex);
2945 shared->currentWorker = 0;
2946 shared->workersFinished = 0;
2947 SharedFileSetInit(&shared->fileset, seg);
2948 shared->nTapes = nWorkers;
2949 for (i = 0; i < nWorkers; i++)
2950 {
2951 shared->tapes[i].firstblocknumber = 0L;
2952 }
2953}
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:38
#define SpinLockInit(lock)
Definition: spin.h:57
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:369
int workersFinished
Definition: tuplesort.c:357
int nTapes
Definition: tuplesort.c:363
slock_t mutex
Definition: tuplesort.c:346
int currentWorker
Definition: tuplesort.c:356
int64 firstblocknumber
Definition: logtape.h:54

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

Referenced by _brin_begin_parallel(), _bt_begin_parallel(), and _gin_begin_parallel().

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

Definition at line 2435 of file tuplesort.c.

2436{
2437 MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2438
2439 Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2440
2441 switch (state->status)
2442 {
2443 case TSS_SORTEDINMEM:
2444 state->markpos_offset = state->current;
2445 state->markpos_eof = state->eof_reached;
2446 break;
2447 case TSS_SORTEDONTAPE:
2448 LogicalTapeTell(state->result_tape,
2449 &state->markpos_block,
2450 &state->markpos_offset);
2451 state->markpos_eof = state->eof_reached;
2452 break;
2453 default:
2454 elog(ERROR, "invalid tuplesort state");
2455 break;
2456 }
2457
2458 MemoryContextSwitchTo(oldcontext);
2459}
void LogicalTapeTell(LogicalTape *lt, int64 *blocknum, int *offset)
Definition: logtape.c:1162

References Assert(), elog, ERROR, LogicalTapeTell(), MemoryContextSwitchTo(), TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and TUPLESORT_RANDOMACCESS.

Referenced by ExecSortMarkPos().

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 1778 of file tuplesort.c.

1779{
1780 int mOrder;
1781
1782 /*----------
1783 * In the merge phase, we need buffer space for each input and output tape.
1784 * Each pass in the balanced merge algorithm reads from M input tapes, and
1785 * writes to N output tapes. Each tape consumes TAPE_BUFFER_OVERHEAD bytes
1786 * of memory. In addition to that, we want MERGE_BUFFER_SIZE workspace per
1787 * input tape.
1788 *
1789 * totalMem = M * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE) +
1790 * N * TAPE_BUFFER_OVERHEAD
1791 *
1792 * Except for the last and next-to-last merge passes, where there can be
1793 * fewer tapes left to process, M = N. We choose M so that we have the
1794 * desired amount of memory available for the input buffers
1795 * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE), given the total memory
1796 * available for the tape buffers (allowedMem).
1797 *
1798 * Note: you might be thinking we need to account for the memtuples[]
1799 * array in this calculation, but we effectively treat that as part of the
1800 * MERGE_BUFFER_SIZE workspace.
1801 *----------
1802 */
1803 mOrder = allowedMem /
1805
1806 /*
1807 * Even in minimum memory, use at least a MINORDER merge. On the other
1808 * hand, even when we have lots of memory, do not use more than a MAXORDER
1809 * merge. Tapes are pretty cheap, but they're not entirely free. Each
1810 * additional tape reduces the amount of memory available to build runs,
1811 * which in turn can cause the same sort to need more runs, which makes
1812 * merging slower even if it can still be done in a single pass. Also,
1813 * high order merges are quite slow due to CPU cache effects; it can be
1814 * faster to pay the I/O cost of a multi-pass merge than to perform a
1815 * single merge pass across many hundreds of tapes.
1816 */
1817 mOrder = Max(mOrder, MINORDER);
1818 mOrder = Min(mOrder, MAXORDER);
1819
1820 return mOrder;
1821}
#define Min(x, y)
Definition: c.h:975
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:178
#define MAXORDER
Definition: tuplesort.c:177
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:179
#define MINORDER
Definition: tuplesort.c:176

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

Referenced by cost_tuplesort(), and inittapes().

◆ tuplesort_method_name()

const char * tuplesort_method_name ( TuplesortMethod  m)

Definition at line 2543 of file tuplesort.c.

2544{
2545 switch (m)
2546 {
2548 return "still in progress";
2550 return "top-N heapsort";
2552 return "quicksort";
2554 return "external sort";
2556 return "external merge";
2557 }
2558
2559 return "unknown";
2560}

References SORT_TYPE_EXTERNAL_MERGE, SORT_TYPE_EXTERNAL_SORT, SORT_TYPE_QUICKSORT, SORT_TYPE_STILL_IN_PROGRESS, and SORT_TYPE_TOP_N_HEAPSORT.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

Definition at line 1363 of file tuplesort.c.

1364{
1365 MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1366
1367 if (trace_sort)
1368 elog(LOG, "performsort of worker %d starting: %s",
1369 state->worker, pg_rusage_show(&state->ru_start));
1370
1371 switch (state->status)
1372 {
1373 case TSS_INITIAL:
1374
1375 /*
1376 * We were able to accumulate all the tuples within the allowed
1377 * amount of memory, or leader to take over worker tapes
1378 */
1379 if (SERIAL(state))
1380 {
1381 /* Just qsort 'em and we're done */
1383 state->status = TSS_SORTEDINMEM;
1384 }
1385 else if (WORKER(state))
1386 {
1387 /*
1388 * Parallel workers must still dump out tuples to tape. No
1389 * merge is required to produce single output run, though.
1390 */
1391 inittapes(state, false);
1392 dumptuples(state, true);
1394 state->status = TSS_SORTEDONTAPE;
1395 }
1396 else
1397 {
1398 /*
1399 * Leader will take over worker tapes and merge worker runs.
1400 * Note that mergeruns sets the correct state->status.
1401 */
1404 }
1405 state->current = 0;
1406 state->eof_reached = false;
1407 state->markpos_block = 0L;
1408 state->markpos_offset = 0;
1409 state->markpos_eof = false;
1410 break;
1411
1412 case TSS_BOUNDED:
1413
1414 /*
1415 * We were able to accumulate all the tuples required for output
1416 * in memory, using a heap to eliminate excess tuples. Now we
1417 * have to transform the heap to a properly-sorted array. Note
1418 * that sort_bounded_heap sets the correct state->status.
1419 */
1421 state->current = 0;
1422 state->eof_reached = false;
1423 state->markpos_offset = 0;
1424 state->markpos_eof = false;
1425 break;
1426
1427 case TSS_BUILDRUNS:
1428
1429 /*
1430 * Finish tape-based sort. First, flush all tuples remaining in
1431 * memory out to tape; then merge until we have a single remaining
1432 * run (or, if !randomAccess and !WORKER(), one run per tape).
1433 * Note that mergeruns sets the correct state->status.
1434 */
1435 dumptuples(state, true);
1437 state->eof_reached = false;
1438 state->markpos_block = 0L;
1439 state->markpos_offset = 0;
1440 state->markpos_eof = false;
1441 break;
1442
1443 default:
1444 elog(ERROR, "invalid tuplesort state");
1445 break;
1446 }
1447
1448 if (trace_sort)
1449 {
1450 if (state->status == TSS_FINALMERGE)
1451 elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
1452 state->worker, state->nInputTapes,
1453 pg_rusage_show(&state->ru_start));
1454 else
1455 elog(LOG, "performsort of worker %d done: %s",
1456 state->worker, pg_rusage_show(&state->ru_start));
1457 }
1458
1459 MemoryContextSwitchTo(oldcontext);
1460}
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define SERIAL(state)
Definition: tuplesort.c:403
static void sort_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:2636
@ TSS_INITIAL
Definition: tuplesort.c:156
@ TSS_BUILDRUNS
Definition: tuplesort.c:158
@ TSS_BOUNDED
Definition: tuplesort.c:157
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:3069
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:2676
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:1865
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:3047
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2017
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2307

References dumptuples(), elog, ERROR, inittapes(), leader_takeover_tapes(), LOG, MemoryContextSwitchTo(), mergeruns(), pg_rusage_show(), SERIAL, sort_bounded_heap(), trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_FINALMERGE, TSS_INITIAL, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, tuplesort_sort_memtuples(), WORKER, and worker_nomergeruns().

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

◆ tuplesort_putbrintuple()

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

Definition at line 853 of file tuplesortvariants.c.

854{
855 SortTuple stup;
856 BrinSortTuple *bstup;
859 Size tuplen;
860
861 /* allocate space for the whole BRIN sort tuple */
862 bstup = palloc(BRINSORTTUPLE_SIZE(size));
863
864 bstup->tuplen = size;
865 memcpy(&bstup->tuple, tuple, size);
866
867 stup.tuple = bstup;
868 stup.datum1 = tuple->bt_blkno;
869 stup.isnull1 = false;
870
871 /* GetMemoryChunkSpace is not supported for bump contexts */
873 tuplen = MAXALIGN(BRINSORTTUPLE_SIZE(size));
874 else
875 tuplen = GetMemoryChunkSpace(bstup);
876
878 base->sortKeys &&
879 base->sortKeys->abbrev_converter &&
880 !stup.isnull1, tuplen);
881
882 MemoryContextSwitchTo(oldcontext);
883}
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:721
BlockNumber bt_blkno
Definition: brin_tuple.h:66
bool isnull1
Definition: tuplesort.h:152
MemoryContext tuplecontext
Definition: tuplesort.h:222
void tuplesort_puttuple_common(Tuplesortstate *state, SortTuple *tuple, bool useAbbrev, Size tuplen)
Definition: tuplesort.c:1169
#define TupleSortUseBumpTupleCxt(opt)
Definition: tuplesort.h:109
#define BRINSORTTUPLE_SIZE(len)

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

Referenced by form_and_spill_tuple().

◆ tuplesort_putdatum()

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

Definition at line 922 of file tuplesortvariants.c.

923{
927 SortTuple stup;
928
929 /*
930 * Pass-by-value types or null values are just stored directly in
931 * stup.datum1 (and stup.tuple is not used and set to NULL).
932 *
933 * Non-null pass-by-reference values need to be copied into memory we
934 * control, and possibly abbreviated. The copied value is pointed to by
935 * stup.tuple and is treated as the canonical copy (e.g. to return via
936 * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
937 * abbreviated value if abbreviation is happening, otherwise it's
938 * identical to stup.tuple.
939 */
940
941 if (isNull || !base->tuples)
942 {
943 /*
944 * Set datum1 to zeroed representation for NULLs (to be consistent,
945 * and to support cheap inequality tests for NULL abbreviated keys).
946 */
947 stup.datum1 = !isNull ? val : (Datum) 0;
948 stup.isnull1 = isNull;
949 stup.tuple = NULL; /* no separate storage */
950 }
951 else
952 {
953 stup.isnull1 = false;
954 stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
955 stup.tuple = DatumGetPointer(stup.datum1);
956 }
957
959 base->tuples &&
960 base->sortKeys->abbrev_converter && !isNull, 0);
961
962 MemoryContextSwitchTo(oldcontext);
963}
uintptr_t Datum
Definition: postgres.h:69
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:317

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, datumCopy(), DatumGetPointer(), if(), MemoryContextSwitchTo(), TuplesortPublic::sortKeys, TuplesortPublic::tuplecontext, TuplesortPublic::tuples, tuplesort_puttuple_common(), TuplesortstateGetPublic, and val.

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

◆ tuplesort_putgintuple()

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

Definition at line 886 of file tuplesortvariants.c.

887{
888 SortTuple stup;
889 GinTuple *ctup;
892 Size tuplen;
893
894 /* copy the GinTuple into the right memory context */
895 ctup = palloc(size);
896 memcpy(ctup, tuple, size);
897
898 stup.tuple = ctup;
899 stup.datum1 = (Datum) 0;
900 stup.isnull1 = false;
901
902 /* GetMemoryChunkSpace is not supported for bump contexts */
904 tuplen = MAXALIGN(size);
905 else
906 tuplen = GetMemoryChunkSpace(ctup);
907
909 base->sortKeys &&
910 base->sortKeys->abbrev_converter &&
911 !stup.isnull1, tuplen);
912
913 MemoryContextSwitchTo(oldcontext);
914}

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

Referenced by _gin_process_worker_data(), and ginFlushBuildState().

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 774 of file tuplesortvariants.c.

775{
776 SortTuple stup;
780 Size tuplen;
781
782 /* copy the tuple into sort storage */
783 tup = heap_copytuple(tup);
784 stup.tuple = tup;
785
786 /*
787 * set up first-column key value, and potentially abbreviate, if it's a
788 * simple column
789 */
790 if (base->haveDatum1)
791 {
792 stup.datum1 = heap_getattr(tup,
793 arg->indexInfo->ii_IndexAttrNumbers[0],
794 arg->tupDesc,
795 &stup.isnull1);
796 }
797
798 /* GetMemoryChunkSpace is not supported for bump contexts */
800 tuplen = MAXALIGN(HEAPTUPLESIZE + tup->t_len);
801 else
802 tuplen = GetMemoryChunkSpace(tup);
803
805 base->haveDatum1 &&
806 base->sortKeys->abbrev_converter &&
807 !stup.isnull1, tuplen);
808
809 MemoryContextSwitchTo(oldcontext);
810}
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:778
#define HEAPTUPLESIZE
Definition: htup.h:73
static Datum heap_getattr(HeapTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: htup_details.h:903
uint32 t_len
Definition: htup.h:64

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

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_putindextuplevalues()

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

Definition at line 817 of file tuplesortvariants.c.

820{
821 SortTuple stup;
822 IndexTuple tuple;
825 Size tuplen;
826
828 isnull, base->tuplecontext);
829 tuple = ((IndexTuple) stup.tuple);
830 tuple->t_tid = *self;
831 /* set up first-column key value */
832 stup.datum1 = index_getattr(tuple,
833 1,
834 RelationGetDescr(arg->indexRel),
835 &stup.isnull1);
836
837 /* GetMemoryChunkSpace is not supported for bump contexts */
839 tuplen = MAXALIGN(tuple->t_info & INDEX_SIZE_MASK);
840 else
841 tuplen = GetMemoryChunkSpace(tuple);
842
844 base->sortKeys &&
845 base->sortKeys->abbrev_converter &&
846 !stup.isnull1, tuplen);
847}
static Datum values[MAXATTR]
Definition: bootstrap.c:151
IndexTuple index_form_tuple_context(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull, MemoryContext context)
Definition: indextuple.c:65
IndexTupleData * IndexTuple
Definition: itup.h:53
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: itup.h:131
#define INDEX_SIZE_MASK
Definition: itup.h:65
ItemPointerData t_tid
Definition: itup.h:37
unsigned short t_info
Definition: itup.h:49

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

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

◆ tuplesort_puttuple_common()

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

Definition at line 1169 of file tuplesort.c.

1171{
1172 MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1173
1174 Assert(!LEADER(state));
1175
1176 /* account for the memory used for this tuple */
1177 USEMEM(state, tuplen);
1178 state->tupleMem += tuplen;
1179
1180 if (!useAbbrev)
1181 {
1182 /*
1183 * Leave ordinary Datum representation, or NULL value. If there is a
1184 * converter it won't expect NULL values, and cost model is not
1185 * required to account for NULL, so in that case we avoid calling
1186 * converter and just set datum1 to zeroed representation (to be
1187 * consistent, and to support cheap inequality tests for NULL
1188 * abbreviated keys).
1189 */
1190 }
1191 else if (!consider_abort_common(state))
1192 {
1193 /* Store abbreviated key representation */
1194 tuple->datum1 = state->base.sortKeys->abbrev_converter(tuple->datum1,
1195 state->base.sortKeys);
1196 }
1197 else
1198 {
1199 /*
1200 * Set state to be consistent with never trying abbreviation.
1201 *
1202 * Alter datum1 representation in already-copied tuples, so as to
1203 * ensure a consistent representation (current tuple was just
1204 * handled). It does not matter if some dumped tuples are already
1205 * sorted on tape, since serialized tuples lack abbreviated keys
1206 * (TSS_BUILDRUNS state prevents control reaching here in any case).
1207 */
1208 REMOVEABBREV(state, state->memtuples, state->memtupcount);
1209 }
1210
1211 switch (state->status)
1212 {
1213 case TSS_INITIAL:
1214
1215 /*
1216 * Save the tuple into the unsorted array. First, grow the array
1217 * as needed. Note that we try to grow the array when there is
1218 * still one free slot remaining --- if we fail, there'll still be
1219 * room to store the incoming tuple, and then we'll switch to
1220 * tape-based operation.
1221 */
1222 if (state->memtupcount >= state->memtupsize - 1)
1223 {
1224 (void) grow_memtuples(state);
1225 Assert(state->memtupcount < state->memtupsize);
1226 }
1227 state->memtuples[state->memtupcount++] = *tuple;
1228
1229 /*
1230 * Check if it's time to switch over to a bounded heapsort. We do
1231 * so if the input tuple count exceeds twice the desired tuple
1232 * count (this is a heuristic for where heapsort becomes cheaper
1233 * than a quicksort), or if we've just filled workMem and have
1234 * enough tuples to meet the bound.
1235 *
1236 * Note that once we enter TSS_BOUNDED state we will always try to
1237 * complete the sort that way. In the worst case, if later input
1238 * tuples are larger than earlier ones, this might cause us to
1239 * exceed workMem significantly.
1240 */
1241 if (state->bounded &&
1242 (state->memtupcount > state->bound * 2 ||
1243 (state->memtupcount > state->bound && LACKMEM(state))))
1244 {
1245 if (trace_sort)
1246 elog(LOG, "switching to bounded heapsort at %d tuples: %s",
1247 state->memtupcount,
1248 pg_rusage_show(&state->ru_start));
1250 MemoryContextSwitchTo(oldcontext);
1251 return;
1252 }
1253
1254 /*
1255 * Done if we still fit in available memory and have array slots.
1256 */
1257 if (state->memtupcount < state->memtupsize && !LACKMEM(state))
1258 {
1259 MemoryContextSwitchTo(oldcontext);
1260 return;
1261 }
1262
1263 /*
1264 * Nope; time to switch to tape-based operation.
1265 */
1266 inittapes(state, true);
1267
1268 /*
1269 * Dump all tuples.
1270 */
1271 dumptuples(state, false);
1272 break;
1273
1274 case TSS_BOUNDED:
1275
1276 /*
1277 * We don't want to grow the array here, so check whether the new
1278 * tuple can be discarded before putting it in. This should be a
1279 * good speed optimization, too, since when there are many more
1280 * input tuples than the bound, most input tuples can be discarded
1281 * with just this one comparison. Note that because we currently
1282 * have the sort direction reversed, we must check for <= not >=.
1283 */
1284 if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
1285 {
1286 /* new tuple <= top of the heap, so we can discard it */
1287 free_sort_tuple(state, tuple);
1289 }
1290 else
1291 {
1292 /* discard top of heap, replacing it with the new tuple */
1293 free_sort_tuple(state, &state->memtuples[0]);
1295 }
1296 break;
1297
1298 case TSS_BUILDRUNS:
1299
1300 /*
1301 * Save the tuple into the unsorted array (there must be space)
1302 */
1303 state->memtuples[state->memtupcount++] = *tuple;
1304
1305 /*
1306 * If we are over the memory limit, dump all tuples.
1307 */
1308 dumptuples(state, false);
1309 break;
1310
1311 default:
1312 elog(ERROR, "invalid tuplesort state");
1313 break;
1314 }
1315 MemoryContextSwitchTo(oldcontext);
1316}
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:396
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:3128
#define REMOVEABBREV(state, stup, count)
Definition: tuplesort.c:395
#define LACKMEM(state)
Definition: tuplesort.c:400
#define USEMEM(state, amt)
Definition: tuplesort.c:401
static bool grow_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:1052
static void make_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:2587
#define LEADER(state)
Definition: tuplesort.c:405
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1319

References Assert(), CHECK_FOR_INTERRUPTS, COMPARETUP, consider_abort_common(), SortTuple::datum1, dumptuples(), elog, ERROR, free_sort_tuple(), grow_memtuples(), inittapes(), LACKMEM, LEADER, LOG, make_bounded_heap(), MemoryContextSwitchTo(), pg_rusage_show(), REMOVEABBREV, trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_INITIAL, tuplesort_heap_replace_top(), and USEMEM.

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

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

Definition at line 734 of file tuplesortvariants.c.

735{
738 TupleDesc tupDesc = (TupleDesc) base->arg;
739 SortTuple stup;
740 MinimalTuple tuple;
741 HeapTupleData htup;
742 Size tuplen;
743
744 /* copy the tuple into sort storage */
745 tuple = ExecCopySlotMinimalTuple(slot);
746 stup.tuple = tuple;
747 /* set up first-column key value */
748 htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
749 htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
750 stup.datum1 = heap_getattr(&htup,
751 base->sortKeys[0].ssup_attno,
752 tupDesc,
753 &stup.isnull1);
754
755 /* GetMemoryChunkSpace is not supported for bump contexts */
757 tuplen = MAXALIGN(tuple->t_len);
758 else
759 tuplen = GetMemoryChunkSpace(tuple);
760
762 base->sortKeys->abbrev_converter &&
763 !stup.isnull1, tuplen);
764
765 MemoryContextSwitchTo(oldcontext);
766}
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:669
struct TupleDescData * TupleDesc
Definition: tupdesc.h:139
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:492

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

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

◆ tuplesort_readtup_alloc()

void * tuplesort_readtup_alloc ( Tuplesortstate state,
Size  tuplen 
)

Definition at line 2883 of file tuplesort.c.

2884{
2885 SlabSlot *buf;
2886
2887 /*
2888 * We pre-allocate enough slots in the slab arena that we should never run
2889 * out.
2890 */
2891 Assert(state->slabFreeHead);
2892
2893 if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
2894 return MemoryContextAlloc(state->base.sortcontext, tuplen);
2895 else
2896 {
2897 buf = state->slabFreeHead;
2898 /* Reuse this slot */
2899 state->slabFreeHead = buf->nextfree;
2900
2901 return buf;
2902 }
2903}
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1181
static char * buf
Definition: pg_test_fsync.c:72
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:142

References Assert(), buf, MemoryContextAlloc(), and SLAB_SLOT_SIZE.

Referenced by readtup_cluster(), readtup_datum(), readtup_heap(), readtup_index(), readtup_index_brin(), and readtup_index_gin().

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

Definition at line 2402 of file tuplesort.c.

2403{
2404 MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2405
2406 Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2407
2408 switch (state->status)
2409 {
2410 case TSS_SORTEDINMEM:
2411 state->current = 0;
2412 state->eof_reached = false;
2413 state->markpos_offset = 0;
2414 state->markpos_eof = false;
2415 break;
2416 case TSS_SORTEDONTAPE:
2417 LogicalTapeRewindForRead(state->result_tape, 0);
2418 state->eof_reached = false;
2419 state->markpos_block = 0L;
2420 state->markpos_offset = 0;
2421 state->markpos_eof = false;
2422 break;
2423 default:
2424 elog(ERROR, "invalid tuplesort state");
2425 break;
2426 }
2427
2428 MemoryContextSwitchTo(oldcontext);
2429}
void LogicalTapeRewindForRead(LogicalTape *lt, size_t buffer_size)
Definition: logtape.c:846

References Assert(), elog, ERROR, LogicalTapeRewindForRead(), MemoryContextSwitchTo(), TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and TUPLESORT_RANDOMACCESS.

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

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate state)

Definition at line 1019 of file tuplesort.c.

1020{
1023
1024 /*
1025 * After we've freed up per-batch memory, re-setup all of the state common
1026 * to both the first batch and any subsequent batch.
1027 */
1029
1030 state->lastReturnedTuple = NULL;
1031 state->slabMemoryBegin = NULL;
1032 state->slabMemoryEnd = NULL;
1033 state->slabFreeHead = NULL;
1034}

References tuplesort_begin_batch(), tuplesort_free(), and tuplesort_updatemax().

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

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

Definition at line 2466 of file tuplesort.c.

2467{
2468 MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2469
2470 Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2471
2472 switch (state->status)
2473 {
2474 case TSS_SORTEDINMEM:
2475 state->current = state->markpos_offset;
2476 state->eof_reached = state->markpos_eof;
2477 break;
2478 case TSS_SORTEDONTAPE:
2479 LogicalTapeSeek(state->result_tape,
2480 state->markpos_block,
2481 state->markpos_offset);
2482 state->eof_reached = state->markpos_eof;
2483 break;
2484 default:
2485 elog(ERROR, "invalid tuplesort state");
2486 break;
2487 }
2488
2489 MemoryContextSwitchTo(oldcontext);
2490}
void LogicalTapeSeek(LogicalTape *lt, int64 blocknum, int offset)
Definition: logtape.c:1133

References Assert(), elog, ERROR, LogicalTapeSeek(), MemoryContextSwitchTo(), TSS_SORTEDINMEM, TSS_SORTEDONTAPE, and TUPLESORT_RANDOMACCESS.

Referenced by ExecSortRestrPos().

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

Definition at line 838 of file tuplesort.c.

839{
840 /* Assert we're called before loading any tuples */
841 Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
842 /* Assert we allow bounded sorts */
843 Assert(state->base.sortopt & TUPLESORT_ALLOWBOUNDED);
844 /* Can't set the bound twice, either */
845 Assert(!state->bounded);
846 /* Also, this shouldn't be called in a parallel worker */
848
849 /* Parallel leader allows but ignores hint */
850 if (LEADER(state))
851 return;
852
853#ifdef DEBUG_BOUNDED_SORT
854 /* Honor GUC setting that disables the feature (for easy testing) */
855 if (!optimize_bounded_sort)
856 return;
857#endif
858
859 /* We want to be able to compute bound * 2, so limit the setting */
860 if (bound > (int64) (INT_MAX / 2))
861 return;
862
863 state->bounded = true;
864 state->bound = (int) bound;
865
866 /*
867 * Bounded sorts are not an effective target for abbreviated key
868 * optimization. Disable by setting state to be consistent with no
869 * abbreviation support.
870 */
871 state->base.sortKeys->abbrev_converter = NULL;
872 if (state->base.sortKeys->abbrev_full_comparator)
873 state->base.sortKeys->comparator = state->base.sortKeys->abbrev_full_comparator;
874
875 /* Not strictly necessary, but be tidy */
876 state->base.sortKeys->abbrev_abort = NULL;
877 state->base.sortKeys->abbrev_full_comparator = NULL;
878}
#define TUPLESORT_ALLOWBOUNDED
Definition: tuplesort.h:100

References Assert(), LEADER, TSS_INITIAL, TUPLESORT_ALLOWBOUNDED, and WORKER.

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

◆ tuplesort_skiptuples()

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

Definition at line 1710 of file tuplesort.c.

1711{
1712 MemoryContext oldcontext;
1713
1714 /*
1715 * We don't actually support backwards skip yet, because no callers need
1716 * it. The API is designed to allow for that later, though.
1717 */
1718 Assert(forward);
1719 Assert(ntuples >= 0);
1720 Assert(!WORKER(state));
1721
1722 switch (state->status)
1723 {
1724 case TSS_SORTEDINMEM:
1725 if (state->memtupcount - state->current >= ntuples)
1726 {
1727 state->current += ntuples;
1728 return true;
1729 }
1730 state->current = state->memtupcount;
1731 state->eof_reached = true;
1732
1733 /*
1734 * Complain if caller tries to retrieve more tuples than
1735 * originally asked for in a bounded sort. This is because
1736 * returning EOF here might be the wrong thing.
1737 */
1738 if (state->bounded && state->current >= state->bound)
1739 elog(ERROR, "retrieved too many tuples in a bounded sort");
1740
1741 return false;
1742
1743 case TSS_SORTEDONTAPE:
1744 case TSS_FINALMERGE:
1745
1746 /*
1747 * We could probably optimize these cases better, but for now it's
1748 * not worth the trouble.
1749 */
1750 oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1751 while (ntuples-- > 0)
1752 {
1753 SortTuple stup;
1754
1755 if (!tuplesort_gettuple_common(state, forward, &stup))
1756 {
1757 MemoryContextSwitchTo(oldcontext);
1758 return false;
1759 }
1761 }
1762 MemoryContextSwitchTo(oldcontext);
1763 return true;
1764
1765 default:
1766 elog(ERROR, "invalid tuplesort state");
1767 return false; /* keep compiler quiet */
1768 }
1769}

References Assert(), CHECK_FOR_INTERRUPTS, elog, ERROR, MemoryContextSwitchTo(), TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, tuplesort_gettuple_common(), and WORKER.

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

◆ tuplesort_space_type_name()

const char * tuplesort_space_type_name ( TuplesortSpaceType  t)

Definition at line 2566 of file tuplesort.c.

2567{
2569 return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
2570}

References Assert(), SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate state)

Definition at line 886 of file tuplesort.c.

887{
888 return state->boundUsed;
889}

Referenced by ExecIncrementalSort().