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, 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:929
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,
int  workMem,
SortCoordinate  coordinate,
int  sortopt 
)

Definition at line 208 of file tuplesortvariants.c.

212 {
213  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
214  sortopt);
216  BTScanInsert indexScanKey;
217  MemoryContext oldcontext;
219  int i;
220 
221  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
222 
223  oldcontext = MemoryContextSwitchTo(base->maincontext);
225 
226 #ifdef TRACE_SORT
227  if (trace_sort)
228  elog(LOG,
229  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
231  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
232 #endif
233 
235 
236  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
237  false, /* no unique check */
238  base->nKeys,
239  workMem,
240  sortopt & TUPLESORT_RANDOMACCESS,
241  PARALLEL_SORT(coordinate));
242 
245  base->writetup = writetup_cluster;
246  base->readtup = readtup_cluster;
248  base->arg = arg;
249 
250  arg->indexInfo = BuildIndexInfo(indexRel);
251 
252  /*
253  * If we don't have a simple leading attribute, we don't currently
254  * initialize datum1, so disable optimizations that require it.
255  */
256  if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
257  base->haveDatum1 = false;
258  else
259  base->haveDatum1 = true;
260 
261  arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
262 
263  indexScanKey = _bt_mkscankey(indexRel, NULL);
264 
265  if (arg->indexInfo->ii_Expressions != NULL)
266  {
267  TupleTableSlot *slot;
268  ExprContext *econtext;
269 
270  /*
271  * We will need to use FormIndexDatum to evaluate the index
272  * expressions. To do that, we need an EState, as well as a
273  * TupleTableSlot to put the table tuples into. The econtext's
274  * scantuple has to point to that slot, too.
275  */
276  arg->estate = CreateExecutorState();
277  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
278  econtext = GetPerTupleExprContext(arg->estate);
279  econtext->ecxt_scantuple = slot;
280  }
281 
282  /* Prepare SortSupport data for each column */
283  base->sortKeys = (SortSupport) palloc0(base->nKeys *
284  sizeof(SortSupportData));
285 
286  for (i = 0; i < base->nKeys; i++)
287  {
288  SortSupport sortKey = base->sortKeys + i;
289  ScanKey scanKey = indexScanKey->scankeys + i;
290  int16 strategy;
291 
292  sortKey->ssup_cxt = CurrentMemoryContext;
293  sortKey->ssup_collation = scanKey->sk_collation;
294  sortKey->ssup_nulls_first =
295  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
296  sortKey->ssup_attno = scanKey->sk_attno;
297  /* Convey if abbreviation optimization is applicable in principle */
298  sortKey->abbreviate = (i == 0 && base->haveDatum1);
299 
300  Assert(sortKey->ssup_attno != 0);
301 
302  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
304 
305  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
306  }
307 
308  pfree(indexScanKey);
309 
310  MemoryContextSwitchTo(oldcontext);
311 
312  return state;
313 }
signed short int16
Definition: c.h:429
#define LOG
Definition: elog.h:31
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:84
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1238
EState * CreateExecutorState(void)
Definition: execUtils.c:92
#define GetPerTupleExprContext(estate)
Definition: executor.h:538
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2420
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1306
void * palloc0(Size size)
Definition: mcxt.c:1230
MemoryContext CurrentMemoryContext
Definition: mcxt.c:124
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1084
#define SK_BT_DESC
Definition: nbtree.h:1083
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:135
void * arg
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:507
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:520
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:792
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:247
Form_pg_class rd_rel
Definition: rel.h:110
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:318
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:931
#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 516 of file tuplesortvariants.c.

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

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

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

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

408 {
409  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
410  sortopt);
412  MemoryContext oldcontext;
414 
415  oldcontext = MemoryContextSwitchTo(base->maincontext);
417 
418 #ifdef TRACE_SORT
419  if (trace_sort)
420  elog(LOG,
421  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
422  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
423  high_mask,
424  low_mask,
425  max_buckets,
426  workMem,
427  sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
428 #endif
429 
430  base->nKeys = 1; /* Only one sort column, the hash code */
431 
434  base->writetup = writetup_index;
435  base->readtup = readtup_index;
436  base->haveDatum1 = true;
437  base->arg = arg;
438 
439  arg->index.heapRel = heapRel;
440  arg->index.indexRel = indexRel;
441 
442  arg->high_mask = high_mask;
443  arg->low_mask = low_mask;
444  arg->max_buckets = max_buckets;
445 
446  MemoryContextSwitchTo(oldcontext);
447 
448  return state;
449 }
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:376
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:747
size_t Size
Definition: c.h:541
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 863 of file tuplesortvariants.c.

865 {
867  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
869  SortTuple stup;
870 
871  if (!tuplesort_gettuple_common(state, forward, &stup))
872  {
873  MemoryContextSwitchTo(oldcontext);
874  return false;
875  }
876 
877  /* Ensure we copy into caller's memory context */
878  MemoryContextSwitchTo(oldcontext);
879 
880  /* Record abbreviated key for caller */
881  if (base->sortKeys->abbrev_converter && abbrev)
882  *abbrev = stup.datum1;
883 
884  if (stup.isnull1 || !base->tuples)
885  {
886  *val = stup.datum1;
887  *isNull = stup.isnull1;
888  }
889  else
890  {
891  /* use stup.tuple because stup.datum1 may be an abbreviation */
892  if (copy)
893  *val = datumCopy(PointerGetDatum(stup.tuple), false,
894  arg->datumTypeLen);
895  else
896  *val = PointerGetDatum(stup.tuple);
897  *isNull = false;
898  }
899 
900  return true;
901 }
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:670
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 802 of file tuplesortvariants.c.

803 {
805  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
806  SortTuple stup;
807 
808  if (!tuplesort_gettuple_common(state, forward, &stup))
809  stup.tuple = NULL;
810 
811  MemoryContextSwitchTo(oldcontext);
812 
813  return stup.tuple;
814 }
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 823 of file tuplesortvariants.c.

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

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:1063
void LogicalTapeClose(LogicalTape *lt)
Definition: logtape.c:734
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 764 of file tuplesortvariants.c.

766 {
768  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
769  SortTuple stup;
770 
771  if (!tuplesort_gettuple_common(state, forward, &stup))
772  stup.tuple = NULL;
773 
774  MemoryContextSwitchTo(oldcontext);
775 
776  if (stup.tuple)
777  {
778  /* Record abbreviated key for caller */
779  if (base->sortKeys->abbrev_converter && abbrev)
780  *abbrev = stup.datum1;
781 
782  if (copy)
784 
785  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
786  return true;
787  }
788  else
789  {
790  ExecClearTuple(slot);
791  return false;
792  }
793 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1446
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:1163

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:937
#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.
1442  */
1444  state->current = 0;
1445  state->eof_reached = false;
1446  state->markpos_offset = 0;
1447  state->markpos_eof = false;
1448  state->status = TSS_SORTEDINMEM;
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 700 of file tuplesortvariants.c.

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

634 {
635  SortTuple stup;
639 
640  /* copy the tuple into sort storage */
641  tup = heap_copytuple(tup);
642  stup.tuple = (void *) tup;
643 
644  /*
645  * set up first-column key value, and potentially abbreviate, if it's a
646  * simple column
647  */
648  if (base->haveDatum1)
649  {
650  stup.datum1 = heap_getattr(tup,
651  arg->indexInfo->ii_IndexAttrNumbers[0],
652  arg->tupDesc,
653  &stup.isnull1);
654  }
655 
657  base->haveDatum1 &&
658  base->sortKeys->abbrev_converter &&
659  !stup.isnull1);
660 
661  MemoryContextSwitchTo(oldcontext);
662 }
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:788
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 669 of file tuplesortvariants.c.

672 {
673  SortTuple stup;
674  IndexTuple tuple;
677 
679  isnull, base->tuplecontext);
680  tuple = ((IndexTuple) stup.tuple);
681  tuple->t_tid = *self;
682  /* set up first-column key value */
683  stup.datum1 = index_getattr(tuple,
684  1,
685  RelationGetDescr(arg->indexRel),
686  &stup.isnull1);
687 
689  base->sortKeys &&
690  base->sortKeys->abbrev_converter &&
691  !stup.isnull1);
692 }
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:527
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:603
#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 600 of file tuplesortvariants.c.

601 {
604  TupleDesc tupDesc = (TupleDesc) base->arg;
605  SortTuple stup;
606  MinimalTuple tuple;
607  HeapTupleData htup;
608 
609  /* copy the tuple into sort storage */
610  tuple = ExecCopySlotMinimalTuple(slot);
611  stup.tuple = (void *) tuple;
612  /* set up first-column key value */
613  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
614  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
615  stup.datum1 = heap_getattr(&htup,
616  base->sortKeys[0].ssup_attno,
617  tupDesc,
618  &stup.isnull1);
619 
621  base->sortKeys->abbrev_converter &&
622  !stup.isnull1);
623 
624  MemoryContextSwitchTo(oldcontext);
625 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:613
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:994
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:847

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:1134

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