PostgreSQL Source Code  git master
tuplesort.h File Reference
#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 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)
 
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, Relation heaprel, 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_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, Datum *values, bool *isnull)
 
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)
 
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 244 of file tuplesort.h.

◆ NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS   4

Definition at line 83 of file tuplesort.h.

◆ PARALLEL_SORT

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

Definition at line 237 of file tuplesort.h.

◆ TUPLESORT_ALLOWBOUNDED

#define TUPLESORT_ALLOWBOUNDED   (1 << 1)

Definition at line 98 of file tuplesort.h.

◆ TUPLESORT_NONE

#define TUPLESORT_NONE   0

Definition at line 92 of file tuplesort.h.

◆ TUPLESORT_RANDOMACCESS

#define TUPLESORT_RANDOMACCESS   (1 << 0)

Definition at line 95 of file tuplesort.h.

◆ TuplesortstateGetPublic

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

Definition at line 241 of file tuplesort.h.

Typedef Documentation

◆ Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 1 of file tuplesort.h.

◆ SortCoordinate

Definition at line 60 of file tuplesort.h.

◆ SortCoordinateData

◆ SortTupleComparator

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

Definition at line 144 of file tuplesort.h.

◆ TuplesortInstrumentation

◆ Tuplesortstate

Definition at line 1 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 74 of file tuplesort.h.

75 {
77  SORT_TYPE_TOP_N_HEAPSORT = 1 << 0,
78  SORT_TYPE_QUICKSORT = 1 << 1,
79  SORT_TYPE_EXTERNAL_SORT = 1 << 2,
TuplesortMethod
Definition: tuplesort.h:75
@ SORT_TYPE_EXTERNAL_SORT
Definition: tuplesort.h:79
@ SORT_TYPE_TOP_N_HEAPSORT
Definition: tuplesort.h:77
@ SORT_TYPE_QUICKSORT
Definition: tuplesort.h:78
@ SORT_TYPE_STILL_IN_PROGRESS
Definition: tuplesort.h:76
@ SORT_TYPE_EXTERNAL_MERGE
Definition: tuplesort.h:80

◆ TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK 
SORT_SPACE_TYPE_MEMORY 

Definition at line 85 of file tuplesort.h.

86 {
TuplesortSpaceType
Definition: tuplesort.h:86
@ SORT_SPACE_TYPE_DISK
Definition: tuplesort.h:87
@ SORT_SPACE_TYPE_MEMORY
Definition: tuplesort.h:88

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 2999 of file tuplesort.c.

3000 {
3001  /* Attach to SharedFileSet */
3002  SharedFileSetAttach(&shared->fileset, seg);
3003 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:62
SharedFileSet fileset
Definition: tuplesort.c:361

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

◆ tuplesort_begin_cluster()

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

Definition at line 208 of file tuplesortvariants.c.

213 {
214  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
215  sortopt);
217  BTScanInsert indexScanKey;
218  MemoryContext oldcontext;
220  int i;
221 
222  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
223 
224  oldcontext = MemoryContextSwitchTo(base->maincontext);
226 
227 #ifdef TRACE_SORT
228  if (trace_sort)
229  elog(LOG,
230  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
232  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
233 #endif
234 
236 
237  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
238  false, /* no unique check */
239  base->nKeys,
240  workMem,
241  sortopt & TUPLESORT_RANDOMACCESS,
242  PARALLEL_SORT(coordinate));
243 
246  base->writetup = writetup_cluster;
247  base->readtup = readtup_cluster;
249  base->arg = arg;
250 
251  arg->indexInfo = BuildIndexInfo(indexRel);
252 
253  /*
254  * If we don't have a simple leading attribute, we don't currently
255  * initialize datum1, so disable optimizations that require it.
256  */
257  if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
258  base->haveDatum1 = false;
259  else
260  base->haveDatum1 = true;
261 
262  arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
263 
264  indexScanKey = _bt_mkscankey(indexRel, heaprel, NULL);
265 
266  if (arg->indexInfo->ii_Expressions != NULL)
267  {
268  TupleTableSlot *slot;
269  ExprContext *econtext;
270 
271  /*
272  * We will need to use FormIndexDatum to evaluate the index
273  * expressions. To do that, we need an EState, as well as a
274  * TupleTableSlot to put the table tuples into. The econtext's
275  * scantuple has to point to that slot, too.
276  */
277  arg->estate = CreateExecutorState();
278  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
279  econtext = GetPerTupleExprContext(arg->estate);
280  econtext->ecxt_scantuple = slot;
281  }
282 
283  /* Prepare SortSupport data for each column */
284  base->sortKeys = (SortSupport) palloc0(base->nKeys *
285  sizeof(SortSupportData));
286 
287  for (i = 0; i < base->nKeys; i++)
288  {
289  SortSupport sortKey = base->sortKeys + i;
290  ScanKey scanKey = indexScanKey->scankeys + i;
291  int16 strategy;
292 
293  sortKey->ssup_cxt = CurrentMemoryContext;
294  sortKey->ssup_collation = scanKey->sk_collation;
295  sortKey->ssup_nulls_first =
296  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
297  sortKey->ssup_attno = scanKey->sk_attno;
298  /* Convey if abbreviation optimization is applicable in principle */
299  sortKey->abbreviate = (i == 0 && base->haveDatum1);
300 
301  Assert(sortKey->ssup_attno != 0);
302 
303  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
305 
306  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
307  }
308 
309  pfree(indexScanKey);
310 
311  MemoryContextSwitchTo(oldcontext);
312 
313  return state;
314 }
signed short int16
Definition: c.h:477
#define LOG
Definition: elog.h:31
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:84
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1239
EState * CreateExecutorState(void)
Definition: execUtils.c:93
#define GetPerTupleExprContext(estate)
Definition: executor.h:549
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2430
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1456
void * palloc0(Size size)
Definition: mcxt.c:1257
MemoryContext CurrentMemoryContext
Definition: mcxt.c:135
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1087
#define SK_BT_DESC
Definition: nbtree.h:1086
BTScanInsert _bt_mkscankey(Relation rel, Relation heaprel, IndexTuple itup)
Definition: nbtutils.c:90
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
void * arg
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:510
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:523
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:162
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:795
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:249
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:200
void(* writetup)(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.h:176
void(* removeabbrev)(Tuplesortstate *state, SortTuple *stups, int count)
Definition: tuplesort.h:169
void(* freestate)(Tuplesortstate *state)
Definition: tuplesort.h:194
void(* readtup)(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.h:185
SortTupleComparator comparetup
Definition: tuplesort.h:163
SortSupport sortKeys
Definition: tuplesort.h:217
Definition: regguts.h:323
Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
Definition: tuplesort.c:646
bool trace_sort
Definition: tuplesort.c:127
#define PARALLEL_SORT(coordinate)
Definition: tuplesort.h:237
#define TUPLESORT_RANDOMACCESS
Definition: tuplesort.h:95
#define TuplesortstateGetPublic(state)
Definition: tuplesort.h:241
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(), BTGreaterStrategyNumber, BTLessStrategyNumber, BuildIndexInfo(), CLUSTER_SORT, TuplesortPublic::comparetup, comparetup_cluster(), 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 646 of file tuplesort.c.

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

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_btree(), tuplesort_begin_index_gist(), and tuplesort_begin_index_hash().

◆ tuplesort_begin_datum()

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

Definition at line 517 of file tuplesortvariants.c.

520 {
521  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
522  sortopt);
525  MemoryContext oldcontext;
526  int16 typlen;
527  bool typbyval;
528 
529  oldcontext = MemoryContextSwitchTo(base->maincontext);
531 
532 #ifdef TRACE_SORT
533  if (trace_sort)
534  elog(LOG,
535  "begin datum sort: workMem = %d, randomAccess = %c",
536  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
537 #endif
538 
539  base->nKeys = 1; /* always a one-column sort */
540 
541  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
542  false, /* no unique check */
543  1,
544  workMem,
545  sortopt & TUPLESORT_RANDOMACCESS,
546  PARALLEL_SORT(coordinate));
547 
550  base->writetup = writetup_datum;
551  base->readtup = readtup_datum;
552  base->haveDatum1 = true;
553  base->arg = arg;
554 
555  arg->datumType = datumType;
556 
557  /* lookup necessary attributes of the datum type */
558  get_typlenbyval(datumType, &typlen, &typbyval);
559  arg->datumTypeLen = typlen;
560  base->tuples = !typbyval;
561 
562  /* Prepare SortSupport data */
563  base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
564 
566  base->sortKeys->ssup_collation = sortCollation;
567  base->sortKeys->ssup_nulls_first = nullsFirstFlag;
568 
569  /*
570  * Abbreviation is possible here only for by-reference types. In theory,
571  * a pass-by-value datatype could have an abbreviated form that is cheaper
572  * to compare. In a tuple sort, we could support that, because we can
573  * always extract the original datum from the tuple as needed. Here, we
574  * can't, because a datum sort only stores a single copy of the datum; the
575  * "tuple" field of each SortTuple is NULL.
576  */
577  base->sortKeys->abbreviate = !typbyval;
578 
579  PrepareSortSupportFromOrderingOp(sortOperator, base->sortKeys);
580 
581  /*
582  * The "onlyKey" optimization cannot be used with abbreviated keys, since
583  * tie-breaker comparisons may be required. Typically, the optimization
584  * is only of value to pass-by-value types anyway, whereas abbreviated
585  * keys are typically only of value to pass-by-reference types.
586  */
587  if (!base->sortKeys->abbrev_converter)
588  base->onlyKey = base->sortKeys;
589 
590  MemoryContextSwitchTo(oldcontext);
591 
592  return state;
593 }
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2209
void * palloc(Size size)
Definition: mcxt.c:1226
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:135
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
SortSupport onlyKey
Definition: tuplesort.h:227
static void removeabbrev_datum(Tuplesortstate *state, SortTuple *stups, int count)
static int comparetup_datum(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(), 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 134 of file tuplesortvariants.c.

139 {
140  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
141  sortopt);
143  MemoryContext oldcontext;
144  int i;
145 
146  oldcontext = MemoryContextSwitchTo(base->maincontext);
147 
148  Assert(nkeys > 0);
149 
150 #ifdef TRACE_SORT
151  if (trace_sort)
152  elog(LOG,
153  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
154  nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
155 #endif
156 
157  base->nKeys = nkeys;
158 
159  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
160  false, /* no unique check */
161  nkeys,
162  workMem,
163  sortopt & TUPLESORT_RANDOMACCESS,
164  PARALLEL_SORT(coordinate));
165 
167  base->comparetup = comparetup_heap;
168  base->writetup = writetup_heap;
169  base->readtup = readtup_heap;
170  base->haveDatum1 = true;
171  base->arg = tupDesc; /* assume we need not copy tupDesc */
172 
173  /* Prepare SortSupport data for each column */
174  base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
175 
176  for (i = 0; i < nkeys; i++)
177  {
178  SortSupport sortKey = base->sortKeys + i;
179 
180  Assert(attNums[i] != 0);
181  Assert(sortOperators[i] != 0);
182 
183  sortKey->ssup_cxt = CurrentMemoryContext;
184  sortKey->ssup_collation = sortCollations[i];
185  sortKey->ssup_nulls_first = nullsFirstFlags[i];
186  sortKey->ssup_attno = attNums[i];
187  /* Convey if abbreviation optimization is applicable in principle */
188  sortKey->abbreviate = (i == 0 && base->haveDatum1);
189 
190  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
191  }
192 
193  /*
194  * The "onlyKey" optimization cannot be used with abbreviated keys, since
195  * tie-breaker comparisons may be required. Typically, the optimization
196  * is only of value to pass-by-value types anyway, whereas abbreviated
197  * keys are typically only of value to pass-by-reference types.
198  */
199  if (nkeys == 1 && !base->sortKeys->abbrev_converter)
200  base->onlyKey = base->sortKeys;
201 
202  MemoryContextSwitchTo(oldcontext);
203 
204  return state;
205 }
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 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(), 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_btree()

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

Definition at line 317 of file tuplesortvariants.c.

324 {
325  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
326  sortopt);
328  BTScanInsert indexScanKey;
330  MemoryContext oldcontext;
331  int i;
332 
333  oldcontext = MemoryContextSwitchTo(base->maincontext);
335 
336 #ifdef TRACE_SORT
337  if (trace_sort)
338  elog(LOG,
339  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
340  enforceUnique ? 't' : 'f',
341  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
342 #endif
343 
345 
346  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
347  enforceUnique,
348  base->nKeys,
349  workMem,
350  sortopt & TUPLESORT_RANDOMACCESS,
351  PARALLEL_SORT(coordinate));
352 
355  base->writetup = writetup_index;
356  base->readtup = readtup_index;
357  base->haveDatum1 = true;
358  base->arg = arg;
359 
360  arg->index.heapRel = heapRel;
361  arg->index.indexRel = indexRel;
362  arg->enforceUnique = enforceUnique;
363  arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
364 
365  indexScanKey = _bt_mkscankey(indexRel, heapRel, NULL);
366 
367  /* Prepare SortSupport data for each column */
368  base->sortKeys = (SortSupport) palloc0(base->nKeys *
369  sizeof(SortSupportData));
370 
371  for (i = 0; i < base->nKeys; i++)
372  {
373  SortSupport sortKey = base->sortKeys + i;
374  ScanKey scanKey = indexScanKey->scankeys + i;
375  int16 strategy;
376 
377  sortKey->ssup_cxt = CurrentMemoryContext;
378  sortKey->ssup_collation = scanKey->sk_collation;
379  sortKey->ssup_nulls_first =
380  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
381  sortKey->ssup_attno = scanKey->sk_attno;
382  /* Convey if abbreviation optimization is applicable in principle */
383  sortKey->abbreviate = (i == 0 && base->haveDatum1);
384 
385  Assert(sortKey->ssup_attno != 0);
386 
387  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
389 
390  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
391  }
392 
393  pfree(indexScanKey);
394 
395  MemoryContextSwitchTo(oldcontext);
396 
397  return state;
398 }
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(), BTGreaterStrategyNumber, BTLessStrategyNumber, TuplesortPublic::comparetup, comparetup_index_btree(), CurrentMemoryContext, elog(), TuplesortPublic::haveDatum1, i, INDEX_SORT, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

◆ tuplesort_begin_index_gist()

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

Definition at line 453 of file tuplesortvariants.c.

458 {
459  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
460  sortopt);
462  MemoryContext oldcontext;
464  int i;
465 
466  oldcontext = MemoryContextSwitchTo(base->maincontext);
468 
469 #ifdef TRACE_SORT
470  if (trace_sort)
471  elog(LOG,
472  "begin index sort: workMem = %d, randomAccess = %c",
473  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
474 #endif
475 
477 
480  base->writetup = writetup_index;
481  base->readtup = readtup_index;
482  base->haveDatum1 = true;
483  base->arg = arg;
484 
485  arg->index.heapRel = heapRel;
486  arg->index.indexRel = indexRel;
487  arg->enforceUnique = false;
488  arg->uniqueNullsNotDistinct = false;
489 
490  /* Prepare SortSupport data for each column */
491  base->sortKeys = (SortSupport) palloc0(base->nKeys *
492  sizeof(SortSupportData));
493 
494  for (i = 0; i < base->nKeys; i++)
495  {
496  SortSupport sortKey = base->sortKeys + i;
497 
498  sortKey->ssup_cxt = CurrentMemoryContext;
499  sortKey->ssup_collation = indexRel->rd_indcollation[i];
500  sortKey->ssup_nulls_first = false;
501  sortKey->ssup_attno = i + 1;
502  /* Convey if abbreviation optimization is applicable in principle */
503  sortKey->abbreviate = (i == 0 && base->haveDatum1);
504 
505  Assert(sortKey->ssup_attno != 0);
506 
507  /* Look for a sort support function */
508  PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
509  }
510 
511  MemoryContextSwitchTo(oldcontext);
512 
513  return state;
514 }
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:189
Oid * rd_indcollation
Definition: rel.h:216

References SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_index_btree(), 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 401 of file tuplesortvariants.c.

409 {
410  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
411  sortopt);
413  MemoryContext oldcontext;
415 
416  oldcontext = MemoryContextSwitchTo(base->maincontext);
418 
419 #ifdef TRACE_SORT
420  if (trace_sort)
421  elog(LOG,
422  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
423  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
424  high_mask,
425  low_mask,
426  max_buckets,
427  workMem,
428  sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
429 #endif
430 
431  base->nKeys = 1; /* Only one sort column, the hash code */
432 
435  base->writetup = writetup_index;
436  base->readtup = readtup_index;
437  base->haveDatum1 = true;
438  base->arg = arg;
439 
440  arg->index.heapRel = heapRel;
441  arg->index.indexRel = indexRel;
442 
443  arg->high_mask = high_mask;
444  arg->low_mask = low_mask;
445  arg->max_buckets = max_buckets;
446 
447  MemoryContextSwitchTo(oldcontext);
448 
449  return state;
450 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)

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

Referenced by _h_spoolinit().

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 972 of file tuplesort.c.

973 {
975 
976  /*
977  * Free the main memory context, including the Tuplesortstate struct
978  * itself.
979  */
980  MemoryContextDelete(state->base.maincontext);
981 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:403
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:903

References MemoryContextDelete(), and tuplesort_free().

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

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nWorkers)

Definition at line 2955 of file tuplesort.c.

2956 {
2957  Size tapesSize;
2958 
2959  Assert(nWorkers > 0);
2960 
2961  /* Make sure that BufFile shared state is MAXALIGN'd */
2962  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
2963  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
2964 
2965  return tapesSize;
2966 }
#define MAXALIGN(LEN)
Definition: c.h:795
size_t Size
Definition: c.h:589
Size add_size(Size s1, Size s2)
Definition: shmem.c:502
Size mul_size(Size s1, Size s2)
Definition: shmem.c:519

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

Referenced by _bt_begin_parallel().

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 2537 of file tuplesort.c.

2539 {
2540  /*
2541  * Note: it might seem we should provide both memory and disk usage for a
2542  * disk-based sort. However, the current code doesn't track memory space
2543  * accurately once we have begun to return tuples to the caller (since we
2544  * don't account for pfree's the caller is expected to do), so we cannot
2545  * rely on availMem in a disk sort. This does not seem worth the overhead
2546  * to fix. Is it worth creating an API for the memory context code to
2547  * tell us how much is actually used in sortcontext?
2548  */
2550 
2551  if (state->isMaxSpaceDisk)
2553  else
2555  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
2556 
2557  switch (state->maxSpaceStatus)
2558  {
2559  case TSS_SORTEDINMEM:
2560  if (state->boundUsed)
2562  else
2564  break;
2565  case TSS_SORTEDONTAPE:
2567  break;
2568  case TSS_FINALMERGE:
2570  break;
2571  default:
2573  break;
2574  }
2575 }
TuplesortMethod sortMethod
Definition: tuplesort.h:102
TuplesortSpaceType spaceType
Definition: tuplesort.h:103
@ TSS_SORTEDONTAPE
Definition: tuplesort.c:164
@ TSS_SORTEDINMEM
Definition: tuplesort.c:163
@ TSS_FINALMERGE
Definition: tuplesort.c:165
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:989

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

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

Definition at line 864 of file tuplesortvariants.c.

866 {
868  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
870  SortTuple stup;
871 
872  if (!tuplesort_gettuple_common(state, forward, &stup))
873  {
874  MemoryContextSwitchTo(oldcontext);
875  return false;
876  }
877 
878  /* Ensure we copy into caller's memory context */
879  MemoryContextSwitchTo(oldcontext);
880 
881  /* Record abbreviated key for caller */
882  if (base->sortKeys->abbrev_converter && abbrev)
883  *abbrev = stup.datum1;
884 
885  if (stup.isnull1 || !base->tuples)
886  {
887  *val = stup.datum1;
888  *isNull = stup.isnull1;
889  }
890  else
891  {
892  /* use stup.tuple because stup.datum1 may be an abbreviation */
893  if (copy)
894  *val = datumCopy(PointerGetDatum(stup.tuple), false,
895  arg->datumTypeLen);
896  else
897  *val = PointerGetDatum(stup.tuple);
898  *isNull = false;
899  }
900 
901  return true;
902 }
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
long val
Definition: informix.c:664
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
MemoryContext sortcontext
Definition: tuplesort.h:202
bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1496

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

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

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 803 of file tuplesortvariants.c.

804 {
806  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
807  SortTuple stup;
808 
809  if (!tuplesort_gettuple_common(state, forward, &stup))
810  stup.tuple = NULL;
811 
812  MemoryContextSwitchTo(oldcontext);
813 
814  return stup.tuple;
815 }
void * tuple
Definition: tuplesort.h:138

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 824 of file tuplesortvariants.c.

825 {
827  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
828  SortTuple stup;
829 
830  if (!tuplesort_gettuple_common(state, forward, &stup))
831  stup.tuple = NULL;
832 
833  MemoryContextSwitchTo(oldcontext);
834 
835  return (IndexTuple) stup.tuple;
836 }

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 1496 of file tuplesort.c.

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

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_getdatum(), tuplesort_getheaptuple(), tuplesort_getindextuple(), tuplesort_gettupleslot(), and tuplesort_skiptuples().

◆ tuplesort_gettupleslot()

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

Definition at line 765 of file tuplesortvariants.c.

767 {
769  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
770  SortTuple stup;
771 
772  if (!tuplesort_gettuple_common(state, forward, &stup))
773  stup.tuple = NULL;
774 
775  MemoryContextSwitchTo(oldcontext);
776 
777  if (stup.tuple)
778  {
779  /* Record abbreviated key for caller */
780  if (base->sortKeys->abbrev_converter && abbrev)
781  *abbrev = stup.datum1;
782 
783  if (copy)
785 
786  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
787  return true;
788  }
789  else
790  {
791  ExecClearTuple(slot);
792  return false;
793  }
794 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1447
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1439
Datum datum1
Definition: tuplesort.h:139
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:433

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 2976 of file tuplesort.c.

2977 {
2978  int i;
2979 
2980  Assert(nWorkers > 0);
2981 
2982  SpinLockInit(&shared->mutex);
2983  shared->currentWorker = 0;
2984  shared->workersFinished = 0;
2985  SharedFileSetInit(&shared->fileset, seg);
2986  shared->nTapes = nWorkers;
2987  for (i = 0; i < nWorkers; i++)
2988  {
2989  shared->tapes[i].firstblocknumber = 0L;
2990  }
2991 }
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:44
#define SpinLockInit(lock)
Definition: spin.h:60
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:370
int workersFinished
Definition: tuplesort.c:358
int nTapes
Definition: tuplesort.c:364
slock_t mutex
Definition: tuplesort.c:347
int currentWorker
Definition: tuplesort.c:357
long 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 _bt_begin_parallel().

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

Definition at line 2473 of file tuplesort.c.

2474 {
2475  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2476 
2477  Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2478 
2479  switch (state->status)
2480  {
2481  case TSS_SORTEDINMEM:
2482  state->markpos_offset = state->current;
2483  state->markpos_eof = state->eof_reached;
2484  break;
2485  case TSS_SORTEDONTAPE:
2486  LogicalTapeTell(state->result_tape,
2487  &state->markpos_block,
2488  &state->markpos_offset);
2489  state->markpos_eof = state->eof_reached;
2490  break;
2491  default:
2492  elog(ERROR, "invalid tuplesort state");
2493  break;
2494  }
2495 
2496  MemoryContextSwitchTo(oldcontext);
2497 }
void LogicalTapeTell(LogicalTape *lt, long *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 1804 of file tuplesort.c.

1805 {
1806  int mOrder;
1807 
1808  /*----------
1809  * In the merge phase, we need buffer space for each input and output tape.
1810  * Each pass in the balanced merge algorithm reads from M input tapes, and
1811  * writes to N output tapes. Each tape consumes TAPE_BUFFER_OVERHEAD bytes
1812  * of memory. In addition to that, we want MERGE_BUFFER_SIZE workspace per
1813  * input tape.
1814  *
1815  * totalMem = M * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE) +
1816  * N * TAPE_BUFFER_OVERHEAD
1817  *
1818  * Except for the last and next-to-last merge passes, where there can be
1819  * fewer tapes left to process, M = N. We choose M so that we have the
1820  * desired amount of memory available for the input buffers
1821  * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE), given the total memory
1822  * available for the tape buffers (allowedMem).
1823  *
1824  * Note: you might be thinking we need to account for the memtuples[]
1825  * array in this calculation, but we effectively treat that as part of the
1826  * MERGE_BUFFER_SIZE workspace.
1827  *----------
1828  */
1829  mOrder = allowedMem /
1831 
1832  /*
1833  * Even in minimum memory, use at least a MINORDER merge. On the other
1834  * hand, even when we have lots of memory, do not use more than a MAXORDER
1835  * merge. Tapes are pretty cheap, but they're not entirely free. Each
1836  * additional tape reduces the amount of memory available to build runs,
1837  * which in turn can cause the same sort to need more runs, which makes
1838  * merging slower even if it can still be done in a single pass. Also,
1839  * high order merges are quite slow due to CPU cache effects; it can be
1840  * faster to pay the I/O cost of a multi-pass merge than to perform a
1841  * single merge pass across many hundreds of tapes.
1842  */
1843  mOrder = Max(mOrder, MINORDER);
1844  mOrder = Min(mOrder, MAXORDER);
1845 
1846  return mOrder;
1847 }
#define Min(x, y)
Definition: c.h:988
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:182
#define MAXORDER
Definition: tuplesort.c:181
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:183
#define MINORDER
Definition: tuplesort.c:180

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 2581 of file tuplesort.c.

2582 {
2583  switch (m)
2584  {
2586  return "still in progress";
2588  return "top-N heapsort";
2589  case SORT_TYPE_QUICKSORT:
2590  return "quicksort";
2592  return "external sort";
2594  return "external merge";
2595  }
2596 
2597  return "unknown";
2598 }

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 1385 of file tuplesort.c.

1386 {
1387  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1388 
1389 #ifdef TRACE_SORT
1390  if (trace_sort)
1391  elog(LOG, "performsort of worker %d starting: %s",
1392  state->worker, pg_rusage_show(&state->ru_start));
1393 #endif
1394 
1395  switch (state->status)
1396  {
1397  case TSS_INITIAL:
1398 
1399  /*
1400  * We were able to accumulate all the tuples within the allowed
1401  * amount of memory, or leader to take over worker tapes
1402  */
1403  if (SERIAL(state))
1404  {
1405  /* Just qsort 'em and we're done */
1407  state->status = TSS_SORTEDINMEM;
1408  }
1409  else if (WORKER(state))
1410  {
1411  /*
1412  * Parallel workers must still dump out tuples to tape. No
1413  * merge is required to produce single output run, though.
1414  */
1415  inittapes(state, false);
1416  dumptuples(state, true);
1418  state->status = TSS_SORTEDONTAPE;
1419  }
1420  else
1421  {
1422  /*
1423  * Leader will take over worker tapes and merge worker runs.
1424  * Note that mergeruns sets the correct state->status.
1425  */
1427  mergeruns(state);
1428  }
1429  state->current = 0;
1430  state->eof_reached = false;
1431  state->markpos_block = 0L;
1432  state->markpos_offset = 0;
1433  state->markpos_eof = false;
1434  break;
1435 
1436  case TSS_BOUNDED:
1437 
1438  /*
1439  * We were able to accumulate all the tuples required for output
1440  * in memory, using a heap to eliminate excess tuples. Now we
1441  * have to transform the heap to a properly-sorted array. Note
1442  * that sort_bounded_heap sets the correct state->status.
1443  */
1445  state->current = 0;
1446  state->eof_reached = false;
1447  state->markpos_offset = 0;
1448  state->markpos_eof = false;
1449  break;
1450 
1451  case TSS_BUILDRUNS:
1452 
1453  /*
1454  * Finish tape-based sort. First, flush all tuples remaining in
1455  * memory out to tape; then merge until we have a single remaining
1456  * run (or, if !randomAccess and !WORKER(), one run per tape).
1457  * Note that mergeruns sets the correct state->status.
1458  */
1459  dumptuples(state, true);
1460  mergeruns(state);
1461  state->eof_reached = false;
1462  state->markpos_block = 0L;
1463  state->markpos_offset = 0;
1464  state->markpos_eof = false;
1465  break;
1466 
1467  default:
1468  elog(ERROR, "invalid tuplesort state");
1469  break;
1470  }
1471 
1472 #ifdef TRACE_SORT
1473  if (trace_sort)
1474  {
1475  if (state->status == TSS_FINALMERGE)
1476  elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
1477  state->worker, state->nInputTapes,
1478  pg_rusage_show(&state->ru_start));
1479  else
1480  elog(LOG, "performsort of worker %d done: %s",
1481  state->worker, pg_rusage_show(&state->ru_start));
1482  }
1483 #endif
1484 
1485  MemoryContextSwitchTo(oldcontext);
1486 }
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define SERIAL(state)
Definition: tuplesort.c:404
static void sort_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:2674
@ TSS_INITIAL
Definition: tuplesort.c:160
@ TSS_BUILDRUNS
Definition: tuplesort.c:162
@ TSS_BOUNDED
Definition: tuplesort.c:161
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:3107
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:2714
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:1891
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:3085
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2045
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2339

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 _bt_leafbuild(), _bt_parallel_scan_and_sort(), _h_indexbuild(), ExecIncrementalSort(), ExecSort(), gistbuild(), heapam_relation_copy_for_cluster(), hypothetical_dense_rank_final(), hypothetical_rank_common(), initialize_phase(), mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), percentile_disc_multi_final(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), switchToPresortedPrefixMode(), and validate_index().

◆ tuplesort_putdatum()

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

Definition at line 701 of file tuplesortvariants.c.

702 {
706  SortTuple stup;
707 
708  /*
709  * Pass-by-value types or null values are just stored directly in
710  * stup.datum1 (and stup.tuple is not used and set to NULL).
711  *
712  * Non-null pass-by-reference values need to be copied into memory we
713  * control, and possibly abbreviated. The copied value is pointed to by
714  * stup.tuple and is treated as the canonical copy (e.g. to return via
715  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
716  * abbreviated value if abbreviation is happening, otherwise it's
717  * identical to stup.tuple.
718  */
719 
720  if (isNull || !base->tuples)
721  {
722  /*
723  * Set datum1 to zeroed representation for NULLs (to be consistent,
724  * and to support cheap inequality tests for NULL abbreviated keys).
725  */
726  stup.datum1 = !isNull ? val : (Datum) 0;
727  stup.isnull1 = isNull;
728  stup.tuple = NULL; /* no separate storage */
729  }
730  else
731  {
732  stup.isnull1 = false;
733  stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
734  stup.tuple = DatumGetPointer(stup.datum1);
735  }
736 
738  base->tuples &&
739  base->sortKeys->abbrev_converter && !isNull);
740 
741  MemoryContextSwitchTo(oldcontext);
742 }
uintptr_t Datum
Definition: postgres.h:64
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
MemoryContext tuplecontext
Definition: tuplesort.h:203
void tuplesort_puttuple_common(Tuplesortstate *state, SortTuple *tuple, bool useAbbrev)
Definition: tuplesort.c:1190

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

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

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 634 of file tuplesortvariants.c.

635 {
636  SortTuple stup;
640 
641  /* copy the tuple into sort storage */
642  tup = heap_copytuple(tup);
643  stup.tuple = (void *) tup;
644 
645  /*
646  * set up first-column key value, and potentially abbreviate, if it's a
647  * simple column
648  */
649  if (base->haveDatum1)
650  {
651  stup.datum1 = heap_getattr(tup,
652  arg->indexInfo->ii_IndexAttrNumbers[0],
653  arg->tupDesc,
654  &stup.isnull1);
655  }
656 
658  base->haveDatum1 &&
659  base->sortKeys->abbrev_converter &&
660  !stup.isnull1);
661 
662  MemoryContextSwitchTo(oldcontext);
663 }
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:680
static Datum heap_getattr(HeapTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: htup_details.h:792
bool isnull1
Definition: tuplesort.h:140

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, SortTuple::datum1, TuplesortPublic::haveDatum1, heap_copytuple(), heap_getattr(), SortTuple::isnull1, MemoryContextSwitchTo(), TuplesortPublic::sortKeys, SortTuple::tuple, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), and TuplesortstateGetPublic.

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_putindextuplevalues()

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

Definition at line 670 of file tuplesortvariants.c.

673 {
674  SortTuple stup;
675  IndexTuple tuple;
678 
680  isnull, base->tuplecontext);
681  tuple = ((IndexTuple) stup.tuple);
682  tuple->t_tid = *self;
683  /* set up first-column key value */
684  stup.datum1 = index_getattr(tuple,
685  1,
686  RelationGetDescr(arg->indexRel),
687  &stup.isnull1);
688 
690  base->sortKeys &&
691  base->sortKeys->abbrev_converter &&
692  !stup.isnull1);
693 }
static Datum values[MAXATTR]
Definition: bootstrap.c:156
IndexTuple index_form_tuple_context(TupleDesc tupleDescriptor, Datum *values, 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:117
#define RelationGetDescr(relation)
Definition: rel.h:530
ItemPointerData t_tid
Definition: itup.h:37

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

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

◆ tuplesort_puttuple_common()

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

Definition at line 1190 of file tuplesort.c.

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

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

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

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

Definition at line 601 of file tuplesortvariants.c.

602 {
605  TupleDesc tupDesc = (TupleDesc) base->arg;
606  SortTuple stup;
607  MinimalTuple tuple;
608  HeapTupleData htup;
609 
610  /* copy the tuple into sort storage */
611  tuple = ExecCopySlotMinimalTuple(slot);
612  stup.tuple = (void *) tuple;
613  /* set up first-column key value */
614  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
615  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
616  stup.datum1 = heap_getattr(&htup,
617  base->sortKeys[0].ssup_attno,
618  tupDesc,
619  &stup.isnull1);
620 
622  base->sortKeys->abbrev_converter &&
623  !stup.isnull1);
624 
625  MemoryContextSwitchTo(oldcontext);
626 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:617
struct TupleDescData * TupleDesc
Definition: tupdesc.h:89
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:471

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

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 2921 of file tuplesort.c.

2922 {
2923  SlabSlot *buf;
2924 
2925  /*
2926  * We pre-allocate enough slots in the slab arena that we should never run
2927  * out.
2928  */
2929  Assert(state->slabFreeHead);
2930 
2931  if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
2932  return MemoryContextAlloc(state->base.sortcontext, tuplen);
2933  else
2934  {
2935  buf = state->slabFreeHead;
2936  /* Reuse this slot */
2937  state->slabFreeHead = buf->nextfree;
2938 
2939  return buf;
2940  }
2941 }
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1021
static char * buf
Definition: pg_test_fsync.c:67
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:146

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

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

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

Definition at line 2440 of file tuplesort.c.

2441 {
2442  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2443 
2444  Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2445 
2446  switch (state->status)
2447  {
2448  case TSS_SORTEDINMEM:
2449  state->current = 0;
2450  state->eof_reached = false;
2451  state->markpos_offset = 0;
2452  state->markpos_eof = false;
2453  break;
2454  case TSS_SORTEDONTAPE:
2455  LogicalTapeRewindForRead(state->result_tape, 0);
2456  state->eof_reached = false;
2457  state->markpos_block = 0L;
2458  state->markpos_offset = 0;
2459  state->markpos_eof = false;
2460  break;
2461  default:
2462  elog(ERROR, "invalid tuplesort state");
2463  break;
2464  }
2465 
2466  MemoryContextSwitchTo(oldcontext);
2467 }
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 1040 of file tuplesort.c.

1041 {
1044 
1045  /*
1046  * After we've freed up per-batch memory, re-setup all of the state common
1047  * to both the first batch and any subsequent batch.
1048  */
1050 
1051  state->lastReturnedTuple = NULL;
1052  state->slabMemoryBegin = NULL;
1053  state->slabMemoryEnd = NULL;
1054  state->slabFreeHead = NULL;
1055 }

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 2504 of file tuplesort.c.

2505 {
2506  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2507 
2508  Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2509 
2510  switch (state->status)
2511  {
2512  case TSS_SORTEDINMEM:
2513  state->current = state->markpos_offset;
2514  state->eof_reached = state->markpos_eof;
2515  break;
2516  case TSS_SORTEDONTAPE:
2517  LogicalTapeSeek(state->result_tape,
2518  state->markpos_block,
2519  state->markpos_offset);
2520  state->eof_reached = state->markpos_eof;
2521  break;
2522  default:
2523  elog(ERROR, "invalid tuplesort state");
2524  break;
2525  }
2526 
2527  MemoryContextSwitchTo(oldcontext);
2528 }
void LogicalTapeSeek(LogicalTape *lt, long 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 844 of file tuplesort.c.

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

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 1736 of file tuplesort.c.

1737 {
1738  MemoryContext oldcontext;
1739 
1740  /*
1741  * We don't actually support backwards skip yet, because no callers need
1742  * it. The API is designed to allow for that later, though.
1743  */
1744  Assert(forward);
1745  Assert(ntuples >= 0);
1746  Assert(!WORKER(state));
1747 
1748  switch (state->status)
1749  {
1750  case TSS_SORTEDINMEM:
1751  if (state->memtupcount - state->current >= ntuples)
1752  {
1753  state->current += ntuples;
1754  return true;
1755  }
1756  state->current = state->memtupcount;
1757  state->eof_reached = true;
1758 
1759  /*
1760  * Complain if caller tries to retrieve more tuples than
1761  * originally asked for in a bounded sort. This is because
1762  * returning EOF here might be the wrong thing.
1763  */
1764  if (state->bounded && state->current >= state->bound)
1765  elog(ERROR, "retrieved too many tuples in a bounded sort");
1766 
1767  return false;
1768 
1769  case TSS_SORTEDONTAPE:
1770  case TSS_FINALMERGE:
1771 
1772  /*
1773  * We could probably optimize these cases better, but for now it's
1774  * not worth the trouble.
1775  */
1776  oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1777  while (ntuples-- > 0)
1778  {
1779  SortTuple stup;
1780 
1781  if (!tuplesort_gettuple_common(state, forward, &stup))
1782  {
1783  MemoryContextSwitchTo(oldcontext);
1784  return false;
1785  }
1787  }
1788  MemoryContextSwitchTo(oldcontext);
1789  return true;
1790 
1791  default:
1792  elog(ERROR, "invalid tuplesort state");
1793  return false; /* keep compiler quiet */
1794  }
1795 }

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 2604 of file tuplesort.c.

2605 {
2607  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
2608 }

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 892 of file tuplesort.c.

893 {
894  return state->boundUsed;
895 }

Referenced by ExecIncrementalSort().