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

Go to the source code of this file.

Data Structures

struct  SortCoordinateData
 
struct  TuplesortInstrumentation
 

Macros

#define NUM_TUPLESORTMETHODS   4
 

Typedefs

typedef struct Tuplesortstate Tuplesortstate
 
typedef struct Sharedsort Sharedsort
 
typedef struct SortCoordinateData SortCoordinateData
 
typedef struct SortCoordinateDataSortCoordinate
 
typedef struct TuplesortInstrumentation TuplesortInstrumentation
 

Enumerations

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

Functions

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

Macro Definition Documentation

◆ NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS   4

Definition at line 81 of file tuplesort.h.

Referenced by show_incremental_sort_group_info().

Typedef Documentation

◆ Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 35 of file tuplesort.h.

◆ SortCoordinate

Definition at line 58 of file tuplesort.h.

◆ SortCoordinateData

◆ TuplesortInstrumentation

◆ Tuplesortstate

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

◆ TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK 
SORT_SPACE_TYPE_MEMORY 

Definition at line 83 of file tuplesort.h.

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 4525 of file tuplesort.c.

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

4526 {
4527  /* Attach to SharedFileSet */
4528  SharedFileSetAttach(&shared->fileset, seg);
4529 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:94
SharedFileSet fileset
Definition: tuplesort.c:506

◆ tuplesort_begin_cluster()

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

Definition at line 952 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

956 {
957  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
958  randomAccess);
959  BTScanInsert indexScanKey;
960  MemoryContext oldcontext;
961  int i;
962 
963  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
964 
965  oldcontext = MemoryContextSwitchTo(state->maincontext);
966 
967 #ifdef TRACE_SORT
968  if (trace_sort)
969  elog(LOG,
970  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
972  workMem, randomAccess ? 't' : 'f');
973 #endif
974 
975  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
976 
977  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
978  false, /* no unique check */
979  state->nKeys,
980  workMem,
981  randomAccess,
982  PARALLEL_SORT(state));
983 
985  state->copytup = copytup_cluster;
986  state->writetup = writetup_cluster;
987  state->readtup = readtup_cluster;
988  state->abbrevNext = 10;
989 
990  state->indexInfo = BuildIndexInfo(indexRel);
991 
992  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
993 
994  indexScanKey = _bt_mkscankey(indexRel, NULL);
995 
996  if (state->indexInfo->ii_Expressions != NULL)
997  {
998  TupleTableSlot *slot;
999  ExprContext *econtext;
1000 
1001  /*
1002  * We will need to use FormIndexDatum to evaluate the index
1003  * expressions. To do that, we need an EState, as well as a
1004  * TupleTableSlot to put the table tuples into. The econtext's
1005  * scantuple has to point to that slot, too.
1006  */
1007  state->estate = CreateExecutorState();
1008  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
1009  econtext = GetPerTupleExprContext(state->estate);
1010  econtext->ecxt_scantuple = slot;
1011  }
1012 
1013  /* Prepare SortSupport data for each column */
1014  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1015  sizeof(SortSupportData));
1016 
1017  for (i = 0; i < state->nKeys; i++)
1018  {
1019  SortSupport sortKey = state->sortKeys + i;
1020  ScanKey scanKey = indexScanKey->scankeys + i;
1021  int16 strategy;
1022 
1023  sortKey->ssup_cxt = CurrentMemoryContext;
1024  sortKey->ssup_collation = scanKey->sk_collation;
1025  sortKey->ssup_nulls_first =
1026  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1027  sortKey->ssup_attno = scanKey->sk_attno;
1028  /* Convey if abbreviation optimization is applicable in principle */
1029  sortKey->abbreviate = (i == 0);
1030 
1031  AssertState(sortKey->ssup_attno != 0);
1032 
1033  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1035 
1036  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1037  }
1038 
1039  pfree(indexScanKey);
1040 
1041  MemoryContextSwitchTo(oldcontext);
1042 
1043  return state;
1044 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:354
bool ssup_nulls_first
Definition: sortsupport.h:75
static void writetup_cluster(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4062
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:741
int64 abbrevNext
Definition: tuplesort.c:444
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1208
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:462
EState * estate
Definition: tuplesort.c:452
SortSupport sortKeys
Definition: tuplesort.c:430
MemoryContext maincontext
Definition: tuplesort.c:260
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:283
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:275
#define CLUSTER_SORT
Definition: tuplesort.c:122
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3878
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2298
#define LOG
Definition: elog.h:26
Form_pg_class rd_rel
Definition: rel.h:109
static void copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3989
bool trace_sort
Definition: tuplesort.c:140
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
#define GetPerTupleExprContext(estate)
Definition: executor.h:507
void pfree(void *pointer)
Definition: mcxt.c:1056
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4086
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:301
IndexInfo * indexInfo
Definition: tuplesort.c:451
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:475
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:161
EState * CreateExecutorState(void)
Definition: execUtils.c:89
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:957
void * palloc0(Size size)
Definition: mcxt.c:980
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
int sk_flags
Definition: skey.h:66
List * ii_Expressions
Definition: execnodes.h:161
#define Assert(condition)
Definition: c.h:738
#define SK_BT_DESC
Definition: nbtree.h:956
Definition: regguts.h:298
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:226
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:666
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
Oid sk_collation
Definition: skey.h:70
#define elog(elevel,...)
Definition: elog.h:214
int i
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:84
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67
TupleDesc tupDesc
Definition: tuplesort.c:429

◆ tuplesort_begin_datum()

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

Definition at line 1171 of file tuplesort.c.

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

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

1174 {
1175  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1176  randomAccess);
1177  MemoryContext oldcontext;
1178  int16 typlen;
1179  bool typbyval;
1180 
1181  oldcontext = MemoryContextSwitchTo(state->maincontext);
1182 
1183 #ifdef TRACE_SORT
1184  if (trace_sort)
1185  elog(LOG,
1186  "begin datum sort: workMem = %d, randomAccess = %c",
1187  workMem, randomAccess ? 't' : 'f');
1188 #endif
1189 
1190  state->nKeys = 1; /* always a one-column sort */
1191 
1192  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
1193  false, /* no unique check */
1194  1,
1195  workMem,
1196  randomAccess,
1197  PARALLEL_SORT(state));
1198 
1199  state->comparetup = comparetup_datum;
1200  state->copytup = copytup_datum;
1201  state->writetup = writetup_datum;
1202  state->readtup = readtup_datum;
1203  state->abbrevNext = 10;
1204 
1205  state->datumType = datumType;
1206 
1207  /* lookup necessary attributes of the datum type */
1208  get_typlenbyval(datumType, &typlen, &typbyval);
1209  state->datumTypeLen = typlen;
1210  state->tuples = !typbyval;
1211 
1212  /* Prepare SortSupport data */
1213  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1214 
1216  state->sortKeys->ssup_collation = sortCollation;
1217  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1218 
1219  /*
1220  * Abbreviation is possible here only for by-reference types. In theory,
1221  * a pass-by-value datatype could have an abbreviated form that is cheaper
1222  * to compare. In a tuple sort, we could support that, because we can
1223  * always extract the original datum from the tuple as needed. Here, we
1224  * can't, because a datum sort only stores a single copy of the datum; the
1225  * "tuple" field of each SortTuple is NULL.
1226  */
1227  state->sortKeys->abbreviate = !typbyval;
1228 
1229  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1230 
1231  /*
1232  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1233  * tie-breaker comparisons may be required. Typically, the optimization
1234  * is only of value to pass-by-value types anyway, whereas abbreviated
1235  * keys are typically only of value to pass-by-reference types.
1236  */
1237  if (!state->sortKeys->abbrev_converter)
1238  state->onlyKey = state->sortKeys;
1239 
1240  MemoryContextSwitchTo(oldcontext);
1241 
1242  return state;
1243 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:354
bool ssup_nulls_first
Definition: sortsupport.h:75
int64 abbrevNext
Definition: tuplesort.c:444
SortSupport sortKeys
Definition: tuplesort.c:430
MemoryContext maincontext
Definition: tuplesort.c:260
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:283
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:275
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
#define DATUM_SORT
Definition: tuplesort.c:121
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4365
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:301
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4386
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4434
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
static void writetup_datum(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4393
void * palloc0(Size size)
Definition: mcxt.c:980
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:298
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2139
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
#define elog(elevel,...)
Definition: elog.h:214
SortSupport onlyKey
Definition: tuplesort.c:436

◆ tuplesort_begin_heap()

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

Definition at line 878 of file tuplesort.c.

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

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

883 {
884  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
885  randomAccess);
886  MemoryContext oldcontext;
887  int i;
888 
889  oldcontext = MemoryContextSwitchTo(state->maincontext);
890 
891  AssertArg(nkeys > 0);
892 
893 #ifdef TRACE_SORT
894  if (trace_sort)
895  elog(LOG,
896  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
897  nkeys, workMem, randomAccess ? 't' : 'f');
898 #endif
899 
900  state->nKeys = nkeys;
901 
902  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
903  false, /* no unique check */
904  nkeys,
905  workMem,
906  randomAccess,
907  PARALLEL_SORT(state));
908 
909  state->comparetup = comparetup_heap;
910  state->copytup = copytup_heap;
911  state->writetup = writetup_heap;
912  state->readtup = readtup_heap;
913 
914  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
915  state->abbrevNext = 10;
916 
917  /* Prepare SortSupport data for each column */
918  state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
919 
920  for (i = 0; i < nkeys; i++)
921  {
922  SortSupport sortKey = state->sortKeys + i;
923 
924  AssertArg(attNums[i] != 0);
925  AssertArg(sortOperators[i] != 0);
926 
927  sortKey->ssup_cxt = CurrentMemoryContext;
928  sortKey->ssup_collation = sortCollations[i];
929  sortKey->ssup_nulls_first = nullsFirstFlags[i];
930  sortKey->ssup_attno = attNums[i];
931  /* Convey if abbreviation optimization is applicable in principle */
932  sortKey->abbreviate = (i == 0);
933 
934  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
935  }
936 
937  /*
938  * The "onlyKey" optimization cannot be used with abbreviated keys, since
939  * tie-breaker comparisons may be required. Typically, the optimization
940  * is only of value to pass-by-value types anyway, whereas abbreviated
941  * keys are typically only of value to pass-by-reference types.
942  */
943  if (nkeys == 1 && !state->sortKeys->abbrev_converter)
944  state->onlyKey = state->sortKeys;
945 
946  MemoryContextSwitchTo(oldcontext);
947 
948  return state;
949 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
bool ssup_nulls_first
Definition: sortsupport.h:75
static int comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3679
int64 abbrevNext
Definition: tuplesort.c:444
SortSupport sortKeys
Definition: tuplesort.c:430
MemoryContext maincontext
Definition: tuplesort.c:260
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:283
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:275
#define LOG
Definition: elog.h:26
#define HEAP_SORT
Definition: tuplesort.c:119
bool trace_sort
Definition: tuplesort.c:140
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
static void writetup_heap(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:3819
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:301
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define AssertArg(condition)
Definition: c.h:740
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3741
void * palloc0(Size size)
Definition: mcxt.c:980
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:298
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3846
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
#define elog(elevel,...)
Definition: elog.h:214
int i
SortSupport onlyKey
Definition: tuplesort.c:436
TupleDesc tupDesc
Definition: tuplesort.c:429

◆ tuplesort_begin_index_btree()

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

Definition at line 1047 of file tuplesort.c.

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

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

1053 {
1054  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1055  randomAccess);
1056  BTScanInsert indexScanKey;
1057  MemoryContext oldcontext;
1058  int i;
1059 
1060  oldcontext = MemoryContextSwitchTo(state->maincontext);
1061 
1062 #ifdef TRACE_SORT
1063  if (trace_sort)
1064  elog(LOG,
1065  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
1066  enforceUnique ? 't' : 'f',
1067  workMem, randomAccess ? 't' : 'f');
1068 #endif
1069 
1070  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1071 
1072  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
1073  enforceUnique,
1074  state->nKeys,
1075  workMem,
1076  randomAccess,
1077  PARALLEL_SORT(state));
1078 
1080  state->copytup = copytup_index;
1081  state->writetup = writetup_index;
1082  state->readtup = readtup_index;
1083  state->abbrevNext = 10;
1084 
1085  state->heapRel = heapRel;
1086  state->indexRel = indexRel;
1087  state->enforceUnique = enforceUnique;
1088 
1089  indexScanKey = _bt_mkscankey(indexRel, NULL);
1090 
1091  /* Prepare SortSupport data for each column */
1092  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1093  sizeof(SortSupportData));
1094 
1095  for (i = 0; i < state->nKeys; i++)
1096  {
1097  SortSupport sortKey = state->sortKeys + i;
1098  ScanKey scanKey = indexScanKey->scankeys + i;
1099  int16 strategy;
1100 
1101  sortKey->ssup_cxt = CurrentMemoryContext;
1102  sortKey->ssup_collation = scanKey->sk_collation;
1103  sortKey->ssup_nulls_first =
1104  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1105  sortKey->ssup_attno = scanKey->sk_attno;
1106  /* Convey if abbreviation optimization is applicable in principle */
1107  sortKey->abbreviate = (i == 0);
1108 
1109  AssertState(sortKey->ssup_attno != 0);
1110 
1111  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1113 
1114  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1115  }
1116 
1117  pfree(indexScanKey);
1118 
1119  MemoryContextSwitchTo(oldcontext);
1120 
1121  return state;
1122 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:354
bool ssup_nulls_first
Definition: sortsupport.h:75
Relation heapRel
Definition: tuplesort.c:458
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:741
int64 abbrevNext
Definition: tuplesort.c:444
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4312
SortSupport sortKeys
Definition: tuplesort.c:430
MemoryContext maincontext
Definition: tuplesort.c:260
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:283
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:275
#define INDEX_SORT
Definition: tuplesort.c:120
#define LOG
Definition: elog.h:26
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4124
bool trace_sort
Definition: tuplesort.c:140
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
void pfree(void *pointer)
Definition: mcxt.c:1056
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4319
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:301
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4341
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:475
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:161
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:957
void * palloc0(Size size)
Definition: mcxt.c:980
Relation indexRel
Definition: tuplesort.c:459
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
int sk_flags
Definition: skey.h:66
#define SK_BT_DESC
Definition: nbtree.h:956
Definition: regguts.h:298
bool enforceUnique
Definition: tuplesort.c:462
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:666
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
Oid sk_collation
Definition: skey.h:70
#define elog(elevel,...)
Definition: elog.h:214
int i
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67

◆ tuplesort_begin_index_hash()

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

Definition at line 1125 of file tuplesort.c.

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

Referenced by _h_spoolinit().

1133 {
1134  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1135  randomAccess);
1136  MemoryContext oldcontext;
1137 
1138  oldcontext = MemoryContextSwitchTo(state->maincontext);
1139 
1140 #ifdef TRACE_SORT
1141  if (trace_sort)
1142  elog(LOG,
1143  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
1144  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
1145  high_mask,
1146  low_mask,
1147  max_buckets,
1148  workMem, randomAccess ? 't' : 'f');
1149 #endif
1150 
1151  state->nKeys = 1; /* Only one sort column, the hash code */
1152 
1154  state->copytup = copytup_index;
1155  state->writetup = writetup_index;
1156  state->readtup = readtup_index;
1157 
1158  state->heapRel = heapRel;
1159  state->indexRel = indexRel;
1160 
1161  state->high_mask = high_mask;
1162  state->low_mask = low_mask;
1163  state->max_buckets = max_buckets;
1164 
1165  MemoryContextSwitchTo(oldcontext);
1166 
1167  return state;
1168 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4257
Relation heapRel
Definition: tuplesort.c:458
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4312
MemoryContext maincontext
Definition: tuplesort.c:260
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:283
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:275
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4319
uint32 high_mask
Definition: tuplesort.c:465
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:301
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4341
Relation indexRel
Definition: tuplesort.c:459
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:298
uint32 max_buckets
Definition: tuplesort.c:467
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
#define elog(elevel,...)
Definition: elog.h:214
uint32 low_mask
Definition: tuplesort.c:466

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1388 of file tuplesort.c.

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

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

1389 {
1390  tuplesort_free(state);
1391 
1392  /*
1393  * Free the main memory context, including the Tuplesortstate struct
1394  * itself.
1395  */
1397 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
MemoryContext maincontext
Definition: tuplesort.c:260
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1315

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nworkers)

Definition at line 4481 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

4482 {
4483  Size tapesSize;
4484 
4485  Assert(nWorkers > 0);
4486 
4487  /* Make sure that BufFile shared state is MAXALIGN'd */
4488  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4489  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4490 
4491  return tapesSize;
4492 }
Size mul_size(Size s1, Size s2)
Definition: shmem.c:515
Size add_size(Size s1, Size s2)
Definition: shmem.c:498
#define Assert(condition)
Definition: c.h:738
size_t Size
Definition: c.h:466
#define MAXALIGN(LEN)
Definition: c.h:691
#define offsetof(type, field)
Definition: c.h:661

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 3302 of file tuplesort.c.

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

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

3304 {
3305  /*
3306  * Note: it might seem we should provide both memory and disk usage for a
3307  * disk-based sort. However, the current code doesn't track memory space
3308  * accurately once we have begun to return tuples to the caller (since we
3309  * don't account for pfree's the caller is expected to do), so we cannot
3310  * rely on availMem in a disk sort. This does not seem worth the overhead
3311  * to fix. Is it worth creating an API for the memory context code to
3312  * tell us how much is actually used in sortcontext?
3313  */
3314  tuplesort_updatemax(state);
3315 
3316  if (state->isMaxSpaceDisk)
3318  else
3320  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
3321 
3322  switch (state->maxSpaceStatus)
3323  {
3324  case TSS_SORTEDINMEM:
3325  if (state->boundUsed)
3327  else
3329  break;
3330  case TSS_SORTEDONTAPE:
3332  break;
3333  case TSS_FINALMERGE:
3335  break;
3336  default:
3338  break;
3339  }
3340 }
bool isMaxSpaceDisk
Definition: tuplesort.c:256
int64 maxSpace
Definition: tuplesort.c:254
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1405
TupSortStatus maxSpaceStatus
Definition: tuplesort.c:259
TuplesortMethod sortMethod
Definition: tuplesort.h:91
TuplesortSpaceType spaceType
Definition: tuplesort.h:92

◆ tuplesort_getdatum()

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

Definition at line 2418 of file tuplesort.c.

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

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

2420 {
2421  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2422  SortTuple stup;
2423 
2424  if (!tuplesort_gettuple_common(state, forward, &stup))
2425  {
2426  MemoryContextSwitchTo(oldcontext);
2427  return false;
2428  }
2429 
2430  /* Ensure we copy into caller's memory context */
2431  MemoryContextSwitchTo(oldcontext);
2432 
2433  /* Record abbreviated key for caller */
2434  if (state->sortKeys->abbrev_converter && abbrev)
2435  *abbrev = stup.datum1;
2436 
2437  if (stup.isnull1 || !state->tuples)
2438  {
2439  *val = stup.datum1;
2440  *isNull = stup.isnull1;
2441  }
2442  else
2443  {
2444  /* use stup.tuple because stup.datum1 may be an abbreviation */
2445  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2446  *isNull = false;
2447  }
2448 
2449  return true;
2450 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:131
long val
Definition: informix.c:664

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2369 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

2370 {
2371  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2372  SortTuple stup;
2373 
2374  if (!tuplesort_gettuple_common(state, forward, &stup))
2375  stup.tuple = NULL;
2376 
2377  MemoryContextSwitchTo(oldcontext);
2378 
2379  return stup.tuple;
2380 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2389 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

2390 {
2391  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2392  SortTuple stup;
2393 
2394  if (!tuplesort_gettuple_common(state, forward, &stup))
2395  stup.tuple = NULL;
2396 
2397  MemoryContextSwitchTo(oldcontext);
2398 
2399  return (IndexTuple) stup.tuple;
2400 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075

◆ tuplesort_gettupleslot()

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

Definition at line 2332 of file tuplesort.c.

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

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

2334 {
2335  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2336  SortTuple stup;
2337 
2338  if (!tuplesort_gettuple_common(state, forward, &stup))
2339  stup.tuple = NULL;
2340 
2341  MemoryContextSwitchTo(oldcontext);
2342 
2343  if (stup.tuple)
2344  {
2345  /* Record abbreviated key for caller */
2346  if (state->sortKeys->abbrev_converter && abbrev)
2347  *abbrev = stup.datum1;
2348 
2349  if (copy)
2351 
2352  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
2353  return true;
2354  }
2355  else
2356  {
2357  ExecClearTuple(slot);
2358  return false;
2359  }
2360 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1416
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:425
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1439
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075

◆ tuplesort_initialize_shared()

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

Definition at line 4502 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

4503 {
4504  int i;
4505 
4506  Assert(nWorkers > 0);
4507 
4508  SpinLockInit(&shared->mutex);
4509  shared->currentWorker = 0;
4510  shared->workersFinished = 0;
4511  SharedFileSetInit(&shared->fileset, seg);
4512  shared->nTapes = nWorkers;
4513  for (i = 0; i < nWorkers; i++)
4514  {
4515  shared->tapes[i].firstblocknumber = 0L;
4516  }
4517 }
slock_t mutex
Definition: tuplesort.c:492
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:49
#define SpinLockInit(lock)
Definition: spin.h:60
long firstblocknumber
Definition: logtape.h:50
int workersFinished
Definition: tuplesort.c:503
int nTapes
Definition: tuplesort.c:509
#define Assert(condition)
Definition: c.h:738
int i
int currentWorker
Definition: tuplesort.c:502
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:515
SharedFileSet fileset
Definition: tuplesort.c:506

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

Definition at line 3236 of file tuplesort.c.

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

Referenced by ExecSortMarkPos().

3237 {
3238  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3239 
3240  Assert(state->randomAccess);
3241 
3242  switch (state->status)
3243  {
3244  case TSS_SORTEDINMEM:
3245  state->markpos_offset = state->current;
3246  state->markpos_eof = state->eof_reached;
3247  break;
3248  case TSS_SORTEDONTAPE:
3249  LogicalTapeTell(state->tapeset,
3250  state->result_tape,
3251  &state->markpos_block,
3252  &state->markpos_offset);
3253  state->markpos_eof = state->eof_reached;
3254  break;
3255  default:
3256  elog(ERROR, "invalid tuplesort state");
3257  break;
3258  }
3259 
3260  MemoryContextSwitchTo(oldcontext);
3261 }
TupSortStatus status
Definition: tuplesort.c:242
bool randomAccess
Definition: tuplesort.c:244
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:402
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
void LogicalTapeTell(LogicalTapeSet *lts, int tapenum, long *blocknum, int *offset)
Definition: logtape.c:1231
#define Assert(condition)
Definition: c.h:738
long markpos_block
Definition: tuplesort.c:401
bool eof_reached
Definition: tuplesort.c:398
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:214

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2526 of file tuplesort.c.

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

Referenced by cost_tuplesort(), and inittapes().

2527 {
2528  int mOrder;
2529 
2530  /*
2531  * We need one tape for each merge input, plus another one for the output,
2532  * and each of these tapes needs buffer space. In addition we want
2533  * MERGE_BUFFER_SIZE workspace per input tape (but the output tape doesn't
2534  * count).
2535  *
2536  * Note: you might be thinking we need to account for the memtuples[]
2537  * array in this calculation, but we effectively treat that as part of the
2538  * MERGE_BUFFER_SIZE workspace.
2539  */
2540  mOrder = (allowedMem - TAPE_BUFFER_OVERHEAD) /
2542 
2543  /*
2544  * Even in minimum memory, use at least a MINORDER merge. On the other
2545  * hand, even when we have lots of memory, do not use more than a MAXORDER
2546  * merge. Tapes are pretty cheap, but they're not entirely free. Each
2547  * additional tape reduces the amount of memory available to build runs,
2548  * which in turn can cause the same sort to need more runs, which makes
2549  * merging slower even if it can still be done in a single pass. Also,
2550  * high order merges are quite slow due to CPU cache effects; it can be
2551  * faster to pay the I/O cost of a polyphase merge than to perform a
2552  * single merge pass across many hundreds of tapes.
2553  */
2554  mOrder = Max(mOrder, MINORDER);
2555  mOrder = Min(mOrder, MAXORDER);
2556 
2557  return mOrder;
2558 }
#define Min(x, y)
Definition: c.h:920
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:231
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:232
#define MINORDER
Definition: tuplesort.c:229
#define Max(x, y)
Definition: c.h:914
#define MAXORDER
Definition: tuplesort.c:230

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

Definition at line 3346 of file tuplesort.c.

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

Referenced by show_incremental_sort_group_info(), and show_sort_info().

3347 {
3348  switch (m)
3349  {
3351  return "still in progress";
3353  return "top-N heapsort";
3354  case SORT_TYPE_QUICKSORT:
3355  return "quicksort";
3357  return "external sort";
3359  return "external merge";
3360  }
3361 
3362  return "unknown";
3363 }

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

Definition at line 1964 of file tuplesort.c.

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

Referenced by _bt_leafbuild(), _bt_parallel_scan_and_sort(), _h_indexbuild(), ExecIncrementalSort(), ExecSort(), 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().

1965 {
1966  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1967 
1968 #ifdef TRACE_SORT
1969  if (trace_sort)
1970  elog(LOG, "performsort of worker %d starting: %s",
1971  state->worker, pg_rusage_show(&state->ru_start));
1972 #endif
1973 
1974  switch (state->status)
1975  {
1976  case TSS_INITIAL:
1977 
1978  /*
1979  * We were able to accumulate all the tuples within the allowed
1980  * amount of memory, or leader to take over worker tapes
1981  */
1982  if (SERIAL(state))
1983  {
1984  /* Just qsort 'em and we're done */
1985  tuplesort_sort_memtuples(state);
1986  state->status = TSS_SORTEDINMEM;
1987  }
1988  else if (WORKER(state))
1989  {
1990  /*
1991  * Parallel workers must still dump out tuples to tape. No
1992  * merge is required to produce single output run, though.
1993  */
1994  inittapes(state, false);
1995  dumptuples(state, true);
1996  worker_nomergeruns(state);
1997  state->status = TSS_SORTEDONTAPE;
1998  }
1999  else
2000  {
2001  /*
2002  * Leader will take over worker tapes and merge worker runs.
2003  * Note that mergeruns sets the correct state->status.
2004  */
2005  leader_takeover_tapes(state);
2006  mergeruns(state);
2007  }
2008  state->current = 0;
2009  state->eof_reached = false;
2010  state->markpos_block = 0L;
2011  state->markpos_offset = 0;
2012  state->markpos_eof = false;
2013  break;
2014 
2015  case TSS_BOUNDED:
2016 
2017  /*
2018  * We were able to accumulate all the tuples required for output
2019  * in memory, using a heap to eliminate excess tuples. Now we
2020  * have to transform the heap to a properly-sorted array.
2021  */
2022  sort_bounded_heap(state);
2023  state->current = 0;
2024  state->eof_reached = false;
2025  state->markpos_offset = 0;
2026  state->markpos_eof = false;
2027  state->status = TSS_SORTEDINMEM;
2028  break;
2029 
2030  case TSS_BUILDRUNS:
2031 
2032  /*
2033  * Finish tape-based sort. First, flush all tuples remaining in
2034  * memory out to tape; then merge until we have a single remaining
2035  * run (or, if !randomAccess and !WORKER(), one run per tape).
2036  * Note that mergeruns sets the correct state->status.
2037  */
2038  dumptuples(state, true);
2039  mergeruns(state);
2040  state->eof_reached = false;
2041  state->markpos_block = 0L;
2042  state->markpos_offset = 0;
2043  state->markpos_eof = false;
2044  break;
2045 
2046  default:
2047  elog(ERROR, "invalid tuplesort state");
2048  break;
2049  }
2050 
2051 #ifdef TRACE_SORT
2052  if (trace_sort)
2053  {
2054  if (state->status == TSS_FINALMERGE)
2055  elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
2056  state->worker, state->activeTapes,
2057  pg_rusage_show(&state->ru_start));
2058  else
2059  elog(LOG, "performsort of worker %d done: %s",
2060  state->worker, pg_rusage_show(&state->ru_start));
2061  }
2062 #endif
2063 
2064  MemoryContextSwitchTo(oldcontext);
2065 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:3098
TupSortStatus status
Definition: tuplesort.c:242
PGRUsage ru_start
Definition: tuplesort.c:481
#define SERIAL(state)
Definition: tuplesort.c:548
static void sort_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3439
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:2566
#define LOG
Definition: elog.h:26
int markpos_offset
Definition: tuplesort.c:402
bool trace_sort
Definition: tuplesort.c:140
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2735
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define WORKER(state)
Definition: tuplesort.c:549
long markpos_block
Definition: tuplesort.c:401
bool eof_reached
Definition: tuplesort.c:398
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3479
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:4632
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:214
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:4611

◆ tuplesort_putdatum()

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

Definition at line 1729 of file tuplesort.c.

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

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

1730 {
1731  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1732  SortTuple stup;
1733 
1734  /*
1735  * Pass-by-value types or null values are just stored directly in
1736  * stup.datum1 (and stup.tuple is not used and set to NULL).
1737  *
1738  * Non-null pass-by-reference values need to be copied into memory we
1739  * control, and possibly abbreviated. The copied value is pointed to by
1740  * stup.tuple and is treated as the canonical copy (e.g. to return via
1741  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
1742  * abbreviated value if abbreviation is happening, otherwise it's
1743  * identical to stup.tuple.
1744  */
1745 
1746  if (isNull || !state->tuples)
1747  {
1748  /*
1749  * Set datum1 to zeroed representation for NULLs (to be consistent,
1750  * and to support cheap inequality tests for NULL abbreviated keys).
1751  */
1752  stup.datum1 = !isNull ? val : (Datum) 0;
1753  stup.isnull1 = isNull;
1754  stup.tuple = NULL; /* no separate storage */
1756  }
1757  else
1758  {
1759  Datum original = datumCopy(val, false, state->datumTypeLen);
1760 
1761  stup.isnull1 = false;
1762  stup.tuple = DatumGetPointer(original);
1763  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1765 
1766  if (!state->sortKeys->abbrev_converter)
1767  {
1768  stup.datum1 = original;
1769  }
1770  else if (!consider_abort_common(state))
1771  {
1772  /* Store abbreviated key representation */
1773  stup.datum1 = state->sortKeys->abbrev_converter(original,
1774  state->sortKeys);
1775  }
1776  else
1777  {
1778  /* Abort abbreviation */
1779  int i;
1780 
1781  stup.datum1 = original;
1782 
1783  /*
1784  * Set state to be consistent with never trying abbreviation.
1785  *
1786  * Alter datum1 representation in already-copied tuples, so as to
1787  * ensure a consistent representation (current tuple was just
1788  * handled). It does not matter if some dumped tuples are already
1789  * sorted on tape, since serialized tuples lack abbreviated keys
1790  * (TSS_BUILDRUNS state prevents control reaching here in any
1791  * case).
1792  */
1793  for (i = 0; i < state->memtupcount; i++)
1794  {
1795  SortTuple *mtup = &state->memtuples[i];
1796 
1797  mtup->datum1 = PointerGetDatum(mtup->tuple);
1798  }
1799  }
1800  }
1801 
1802  puttuple_common(state, &stup);
1803 
1804  MemoryContextSwitchTo(oldcontext);
1805 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1920
MemoryContext sortcontext
Definition: tuplesort.c:262
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:131
uintptr_t Datum
Definition: postgres.h:367
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1811
#define DatumGetPointer(X)
Definition: postgres.h:549
MemoryContext tuplecontext
Definition: tuplesort.c:263
#define USEMEM(state, amt)
Definition: tuplesort.c:546
int i
long val
Definition: informix.c:664
SortTuple * memtuples
Definition: tuplesort.c:311

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 1630 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

1631 {
1632  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1633  SortTuple stup;
1634 
1635  /*
1636  * Copy the given tuple into memory we control, and decrease availMem.
1637  * Then call the common code.
1638  */
1639  COPYTUP(state, &stup, (void *) tup);
1640 
1641  puttuple_common(state, &stup);
1642 
1643  MemoryContextSwitchTo(oldcontext);
1644 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
MemoryContext sortcontext
Definition: tuplesort.c:262
#define COPYTUP(state, stup, tup)
Definition: tuplesort.c:542
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1811

◆ tuplesort_putindextuplevalues()

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

Definition at line 1651 of file tuplesort.c.

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

Referenced by _bt_spool(), and _h_spool().

1654 {
1655  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1656  SortTuple stup;
1657  Datum original;
1658  IndexTuple tuple;
1659 
1660  stup.tuple = index_form_tuple(RelationGetDescr(rel), values, isnull);
1661  tuple = ((IndexTuple) stup.tuple);
1662  tuple->t_tid = *self;
1663  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1664  /* set up first-column key value */
1665  original = index_getattr(tuple,
1666  1,
1667  RelationGetDescr(state->indexRel),
1668  &stup.isnull1);
1669 
1671 
1672  if (!state->sortKeys || !state->sortKeys->abbrev_converter || stup.isnull1)
1673  {
1674  /*
1675  * Store ordinary Datum representation, or NULL value. If there is a
1676  * converter it won't expect NULL values, and cost model is not
1677  * required to account for NULL, so in that case we avoid calling
1678  * converter and just set datum1 to zeroed representation (to be
1679  * consistent, and to support cheap inequality tests for NULL
1680  * abbreviated keys).
1681  */
1682  stup.datum1 = original;
1683  }
1684  else if (!consider_abort_common(state))
1685  {
1686  /* Store abbreviated key representation */
1687  stup.datum1 = state->sortKeys->abbrev_converter(original,
1688  state->sortKeys);
1689  }
1690  else
1691  {
1692  /* Abort abbreviation */
1693  int i;
1694 
1695  stup.datum1 = original;
1696 
1697  /*
1698  * Set state to be consistent with never trying abbreviation.
1699  *
1700  * Alter datum1 representation in already-copied tuples, so as to
1701  * ensure a consistent representation (current tuple was just
1702  * handled). It does not matter if some dumped tuples are already
1703  * sorted on tape, since serialized tuples lack abbreviated keys
1704  * (TSS_BUILDRUNS state prevents control reaching here in any case).
1705  */
1706  for (i = 0; i < state->memtupcount; i++)
1707  {
1708  SortTuple *mtup = &state->memtuples[i];
1709 
1710  tuple = mtup->tuple;
1711  mtup->datum1 = index_getattr(tuple,
1712  1,
1713  RelationGetDescr(state->indexRel),
1714  &mtup->isnull1);
1715  }
1716  }
1717 
1718  puttuple_common(state, &stup);
1719 
1720  MemoryContextSwitchTo(oldcontext);
1721 }
#define RelationGetDescr(relation)
Definition: rel.h:482
SortSupport sortKeys
Definition: tuplesort.c:430
ItemPointerData t_tid
Definition: itup.h:37
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:181
IndexTuple index_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:47
void * tuple
Definition: tuplesort.c:179
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1920
MemoryContext sortcontext
Definition: tuplesort.c:262
IndexTupleData * IndexTuple
Definition: itup.h:53
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
Relation indexRel
Definition: tuplesort.c:459
uintptr_t Datum
Definition: postgres.h:367
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1811
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static Datum values[MAXATTR]
Definition: bootstrap.c:167
MemoryContext tuplecontext
Definition: tuplesort.c:263
#define USEMEM(state, amt)
Definition: tuplesort.c:546
int i
SortTuple * memtuples
Definition: tuplesort.c:311

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

Definition at line 1608 of file tuplesort.c.

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

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

1609 {
1610  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1611  SortTuple stup;
1612 
1613  /*
1614  * Copy the given tuple into memory we control, and decrease availMem.
1615  * Then call the common code.
1616  */
1617  COPYTUP(state, &stup, (void *) slot);
1618 
1619  puttuple_common(state, &stup);
1620 
1621  MemoryContextSwitchTo(oldcontext);
1622 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
MemoryContext sortcontext
Definition: tuplesort.c:262
#define COPYTUP(state, stup, tup)
Definition: tuplesort.c:542
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1811

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

Definition at line 3201 of file tuplesort.c.

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

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

3202 {
3203  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3204 
3205  Assert(state->randomAccess);
3206 
3207  switch (state->status)
3208  {
3209  case TSS_SORTEDINMEM:
3210  state->current = 0;
3211  state->eof_reached = false;
3212  state->markpos_offset = 0;
3213  state->markpos_eof = false;
3214  break;
3215  case TSS_SORTEDONTAPE:
3217  state->result_tape,
3218  0);
3219  state->eof_reached = false;
3220  state->markpos_block = 0L;
3221  state->markpos_offset = 0;
3222  state->markpos_eof = false;
3223  break;
3224  default:
3225  elog(ERROR, "invalid tuplesort state");
3226  break;
3227  }
3228 
3229  MemoryContextSwitchTo(oldcontext);
3230 }
TupSortStatus status
Definition: tuplesort.c:242
bool randomAccess
Definition: tuplesort.c:244
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:402
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define Assert(condition)
Definition: c.h:738
long markpos_block
Definition: tuplesort.c:401
bool eof_reached
Definition: tuplesort.c:398
void LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Definition: logtape.c:849
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:214

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate state)

Definition at line 1456 of file tuplesort.c.

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

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

1457 {
1458  tuplesort_updatemax(state);
1459  tuplesort_free(state);
1460 
1461  /*
1462  * After we've freed up per-batch memory, re-setup all of the state common
1463  * to both the first batch and any subsequent batch.
1464  */
1465  tuplesort_begin_batch(state);
1466 
1467  state->lastReturnedTuple = NULL;
1468  state->slabMemoryBegin = NULL;
1469  state->slabMemoryEnd = NULL;
1470  state->slabFreeHead = NULL;
1471 }
char * slabMemoryEnd
Definition: tuplesort.c:346
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1405
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:814
void * lastReturnedTuple
Definition: tuplesort.c:358
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1315
char * slabMemoryBegin
Definition: tuplesort.c:345
SlabSlot * slabFreeHead
Definition: tuplesort.c:347

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

Definition at line 3268 of file tuplesort.c.

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

Referenced by ExecSortRestrPos().

3269 {
3270  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3271 
3272  Assert(state->randomAccess);
3273 
3274  switch (state->status)
3275  {
3276  case TSS_SORTEDINMEM:
3277  state->current = state->markpos_offset;
3278  state->eof_reached = state->markpos_eof;
3279  break;
3280  case TSS_SORTEDONTAPE:
3281  LogicalTapeSeek(state->tapeset,
3282  state->result_tape,
3283  state->markpos_block,
3284  state->markpos_offset);
3285  state->eof_reached = state->markpos_eof;
3286  break;
3287  default:
3288  elog(ERROR, "invalid tuplesort state");
3289  break;
3290  }
3291 
3292  MemoryContextSwitchTo(oldcontext);
3293 }
TupSortStatus status
Definition: tuplesort.c:242
bool randomAccess
Definition: tuplesort.c:244
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:402
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define Assert(condition)
Definition: c.h:738
long markpos_block
Definition: tuplesort.c:401
bool eof_reached
Definition: tuplesort.c:398
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:214
void LogicalTapeSeek(LogicalTapeSet *lts, int tapenum, long blocknum, int offset)
Definition: logtape.c:1197

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

Definition at line 1258 of file tuplesort.c.

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

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

1259 {
1260  /* Assert we're called before loading any tuples */
1261  Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
1262  /* Can't set the bound twice, either */
1263  Assert(!state->bounded);
1264  /* Also, this shouldn't be called in a parallel worker */
1265  Assert(!WORKER(state));
1266 
1267  /* Parallel leader allows but ignores hint */
1268  if (LEADER(state))
1269  return;
1270 
1271 #ifdef DEBUG_BOUNDED_SORT
1272  /* Honor GUC setting that disables the feature (for easy testing) */
1273  if (!optimize_bounded_sort)
1274  return;
1275 #endif
1276 
1277  /* We want to be able to compute bound * 2, so limit the setting */
1278  if (bound > (int64) (INT_MAX / 2))
1279  return;
1280 
1281  state->bounded = true;
1282  state->bound = (int) bound;
1283 
1284  /*
1285  * Bounded sorts are not an effective target for abbreviated key
1286  * optimization. Disable by setting state to be consistent with no
1287  * abbreviation support.
1288  */
1289  state->sortKeys->abbrev_converter = NULL;
1290  if (state->sortKeys->abbrev_full_comparator)
1292 
1293  /* Not strictly necessary, but be tidy */
1294  state->sortKeys->abbrev_abort = NULL;
1295  state->sortKeys->abbrev_full_comparator = NULL;
1296 }
TupSortStatus status
Definition: tuplesort.c:242
SortSupport sortKeys
Definition: tuplesort.c:430
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
#define LEADER(state)
Definition: tuplesort.c:550
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define WORKER(state)
Definition: tuplesort.c:549
#define Assert(condition)
Definition: c.h:738
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182

◆ tuplesort_skiptuples()

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

Definition at line 2458 of file tuplesort.c.

References Assert, Tuplesortstate::bound, Tuplesortstate::bounded, CHECK_FOR_INTERRUPTS, Tuplesortstate::current, elog, Tuplesortstate::eof_reached, ERROR, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::sortcontext, Tuplesortstate::status, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, tuplesort_gettuple_common(), and WORKER.

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

2459 {
2460  MemoryContext oldcontext;
2461 
2462  /*
2463  * We don't actually support backwards skip yet, because no callers need
2464  * it. The API is designed to allow for that later, though.
2465  */
2466  Assert(forward);
2467  Assert(ntuples >= 0);
2468  Assert(!WORKER(state));
2469 
2470  switch (state->status)
2471  {
2472  case TSS_SORTEDINMEM:
2473  if (state->memtupcount - state->current >= ntuples)
2474  {
2475  state->current += ntuples;
2476  return true;
2477  }
2478  state->current = state->memtupcount;
2479  state->eof_reached = true;
2480 
2481  /*
2482  * Complain if caller tries to retrieve more tuples than
2483  * originally asked for in a bounded sort. This is because
2484  * returning EOF here might be the wrong thing.
2485  */
2486  if (state->bounded && state->current >= state->bound)
2487  elog(ERROR, "retrieved too many tuples in a bounded sort");
2488 
2489  return false;
2490 
2491  case TSS_SORTEDONTAPE:
2492  case TSS_FINALMERGE:
2493 
2494  /*
2495  * We could probably optimize these cases better, but for now it's
2496  * not worth the trouble.
2497  */
2498  oldcontext = MemoryContextSwitchTo(state->sortcontext);
2499  while (ntuples-- > 0)
2500  {
2501  SortTuple stup;
2502 
2503  if (!tuplesort_gettuple_common(state, forward, &stup))
2504  {
2505  MemoryContextSwitchTo(oldcontext);
2506  return false;
2507  }
2509  }
2510  MemoryContextSwitchTo(oldcontext);
2511  return true;
2512 
2513  default:
2514  elog(ERROR, "invalid tuplesort state");
2515  return false; /* keep compiler quiet */
2516  }
2517 }
TupSortStatus status
Definition: tuplesort.c:242
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075
#define WORKER(state)
Definition: tuplesort.c:549
#define Assert(condition)
Definition: c.h:738
bool eof_reached
Definition: tuplesort.c:398
#define elog(elevel,...)
Definition: elog.h:214
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType  t)

Definition at line 3369 of file tuplesort.c.

References Assert, SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

3370 {
3372  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
3373 }
#define Assert(condition)
Definition: c.h:738

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate state)

Definition at line 1304 of file tuplesort.c.

References Tuplesortstate::boundUsed.

Referenced by ExecIncrementalSort().

1305 {
1306  return state->boundUsed;
1307 }