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_index_gist (Relation heapRel, Relation indexRel, 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 4601 of file tuplesort.c.

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

4602 {
4603  /* Attach to SharedFileSet */
4604  SharedFileSetAttach(&shared->fileset, seg);
4605 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:62
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 971 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().

975 {
976  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
977  randomAccess);
978  BTScanInsert indexScanKey;
979  MemoryContext oldcontext;
980  int i;
981 
982  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
983 
984  oldcontext = MemoryContextSwitchTo(state->maincontext);
985 
986 #ifdef TRACE_SORT
987  if (trace_sort)
988  elog(LOG,
989  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
991  workMem, randomAccess ? 't' : 'f');
992 #endif
993 
994  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
995 
996  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
997  false, /* no unique check */
998  state->nKeys,
999  workMem,
1000  randomAccess,
1001  PARALLEL_SORT(state));
1002 
1003  state->comparetup = comparetup_cluster;
1004  state->copytup = copytup_cluster;
1005  state->writetup = writetup_cluster;
1006  state->readtup = readtup_cluster;
1007  state->abbrevNext = 10;
1008 
1009  state->indexInfo = BuildIndexInfo(indexRel);
1010 
1011  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
1012 
1013  indexScanKey = _bt_mkscankey(indexRel, NULL);
1014 
1015  if (state->indexInfo->ii_Expressions != NULL)
1016  {
1017  TupleTableSlot *slot;
1018  ExprContext *econtext;
1019 
1020  /*
1021  * We will need to use FormIndexDatum to evaluate the index
1022  * expressions. To do that, we need an EState, as well as a
1023  * TupleTableSlot to put the table tuples into. The econtext's
1024  * scantuple has to point to that slot, too.
1025  */
1026  state->estate = CreateExecutorState();
1027  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
1028  econtext = GetPerTupleExprContext(state->estate);
1029  econtext->ecxt_scantuple = slot;
1030  }
1031 
1032  /* Prepare SortSupport data for each column */
1033  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1034  sizeof(SortSupportData));
1035 
1036  for (i = 0; i < state->nKeys; i++)
1037  {
1038  SortSupport sortKey = state->sortKeys + i;
1039  ScanKey scanKey = indexScanKey->scankeys + i;
1040  int16 strategy;
1041 
1042  sortKey->ssup_cxt = CurrentMemoryContext;
1043  sortKey->ssup_collation = scanKey->sk_collation;
1044  sortKey->ssup_nulls_first =
1045  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1046  sortKey->ssup_attno = scanKey->sk_attno;
1047  /* Convey if abbreviation optimization is applicable in principle */
1048  sortKey->abbreviate = (i == 0);
1049 
1050  AssertState(sortKey->ssup_attno != 0);
1051 
1052  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1054 
1055  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1056  }
1057 
1058  pfree(indexScanKey);
1059 
1060  MemoryContextSwitchTo(oldcontext);
1061 
1062  return state;
1063 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:428
bool ssup_nulls_first
Definition: sortsupport.h:75
static void writetup_cluster(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4138
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:807
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:1238
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:483
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:3954
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2378
#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:4065
bool trace_sort
Definition: tuplesort.c:140
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
#define GetPerTupleExprContext(estate)
Definition: executor.h:533
void pfree(void *pointer)
Definition: mcxt.c:1169
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4162
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:42
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:496
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:162
EState * CreateExecutorState(void)
Definition: execUtils.c:90
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1083
void * palloc0(Size size)
Definition: mcxt.c:1093
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:804
#define SK_BT_DESC
Definition: nbtree.h:1082
Definition: regguts.h:317
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:226
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:791
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:721
Oid sk_collation
Definition: skey.h:70
#define elog(elevel,...)
Definition: elog.h:232
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 1247 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 ExecSort(), initialize_aggregate(), ordered_set_startup(), and validate_index().

1250 {
1251  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1252  randomAccess);
1253  MemoryContext oldcontext;
1254  int16 typlen;
1255  bool typbyval;
1256 
1257  oldcontext = MemoryContextSwitchTo(state->maincontext);
1258 
1259 #ifdef TRACE_SORT
1260  if (trace_sort)
1261  elog(LOG,
1262  "begin datum sort: workMem = %d, randomAccess = %c",
1263  workMem, randomAccess ? 't' : 'f');
1264 #endif
1265 
1266  state->nKeys = 1; /* always a one-column sort */
1267 
1268  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
1269  false, /* no unique check */
1270  1,
1271  workMem,
1272  randomAccess,
1273  PARALLEL_SORT(state));
1274 
1275  state->comparetup = comparetup_datum;
1276  state->copytup = copytup_datum;
1277  state->writetup = writetup_datum;
1278  state->readtup = readtup_datum;
1279  state->abbrevNext = 10;
1280 
1281  state->datumType = datumType;
1282 
1283  /* lookup necessary attributes of the datum type */
1284  get_typlenbyval(datumType, &typlen, &typbyval);
1285  state->datumTypeLen = typlen;
1286  state->tuples = !typbyval;
1287 
1288  /* Prepare SortSupport data */
1289  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1290 
1292  state->sortKeys->ssup_collation = sortCollation;
1293  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1294 
1295  /*
1296  * Abbreviation is possible here only for by-reference types. In theory,
1297  * a pass-by-value datatype could have an abbreviated form that is cheaper
1298  * to compare. In a tuple sort, we could support that, because we can
1299  * always extract the original datum from the tuple as needed. Here, we
1300  * can't, because a datum sort only stores a single copy of the datum; the
1301  * "tuple" field of each SortTuple is NULL.
1302  */
1303  state->sortKeys->abbreviate = !typbyval;
1304 
1305  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1306 
1307  /*
1308  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1309  * tie-breaker comparisons may be required. Typically, the optimization
1310  * is only of value to pass-by-value types anyway, whereas abbreviated
1311  * keys are typically only of value to pass-by-reference types.
1312  */
1313  if (!state->sortKeys->abbrev_converter)
1314  state->onlyKey = state->sortKeys;
1315 
1316  MemoryContextSwitchTo(oldcontext);
1317 
1318  return state;
1319 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:428
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:135
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:4441
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:4462
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4510
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
static void writetup_datum(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4469
void * palloc0(Size size)
Definition: mcxt.c:1093
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:317
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2198
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:721
#define elog(elevel,...)
Definition: elog.h:232
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 897 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().

902 {
903  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
904  randomAccess);
905  MemoryContext oldcontext;
906  int i;
907 
908  oldcontext = MemoryContextSwitchTo(state->maincontext);
909 
910  AssertArg(nkeys > 0);
911 
912 #ifdef TRACE_SORT
913  if (trace_sort)
914  elog(LOG,
915  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
916  nkeys, workMem, randomAccess ? 't' : 'f');
917 #endif
918 
919  state->nKeys = nkeys;
920 
921  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
922  false, /* no unique check */
923  nkeys,
924  workMem,
925  randomAccess,
926  PARALLEL_SORT(state));
927 
928  state->comparetup = comparetup_heap;
929  state->copytup = copytup_heap;
930  state->writetup = writetup_heap;
931  state->readtup = readtup_heap;
932 
933  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
934  state->abbrevNext = 10;
935 
936  /* Prepare SortSupport data for each column */
937  state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
938 
939  for (i = 0; i < nkeys; i++)
940  {
941  SortSupport sortKey = state->sortKeys + i;
942 
943  AssertArg(attNums[i] != 0);
944  AssertArg(sortOperators[i] != 0);
945 
946  sortKey->ssup_cxt = CurrentMemoryContext;
947  sortKey->ssup_collation = sortCollations[i];
948  sortKey->ssup_nulls_first = nullsFirstFlags[i];
949  sortKey->ssup_attno = attNums[i];
950  /* Convey if abbreviation optimization is applicable in principle */
951  sortKey->abbreviate = (i == 0);
952 
953  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
954  }
955 
956  /*
957  * The "onlyKey" optimization cannot be used with abbreviated keys, since
958  * tie-breaker comparisons may be required. Typically, the optimization
959  * is only of value to pass-by-value types anyway, whereas abbreviated
960  * keys are typically only of value to pass-by-reference types.
961  */
962  if (nkeys == 1 && !state->sortKeys->abbrev_converter)
963  state->onlyKey = state->sortKeys;
964 
965  MemoryContextSwitchTo(oldcontext);
966 
967  return state;
968 }
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:3755
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:135
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:3895
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:42
#define AssertArg(condition)
Definition: c.h:806
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3817
void * palloc0(Size size)
Definition: mcxt.c:1093
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:317
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3922
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:721
#define elog(elevel,...)
Definition: elog.h:232
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 1066 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().

1072 {
1073  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1074  randomAccess);
1075  BTScanInsert indexScanKey;
1076  MemoryContext oldcontext;
1077  int i;
1078 
1079  oldcontext = MemoryContextSwitchTo(state->maincontext);
1080 
1081 #ifdef TRACE_SORT
1082  if (trace_sort)
1083  elog(LOG,
1084  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
1085  enforceUnique ? 't' : 'f',
1086  workMem, randomAccess ? 't' : 'f');
1087 #endif
1088 
1089  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1090 
1091  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
1092  enforceUnique,
1093  state->nKeys,
1094  workMem,
1095  randomAccess,
1096  PARALLEL_SORT(state));
1097 
1099  state->copytup = copytup_index;
1100  state->writetup = writetup_index;
1101  state->readtup = readtup_index;
1102  state->abbrevNext = 10;
1103 
1104  state->heapRel = heapRel;
1105  state->indexRel = indexRel;
1106  state->enforceUnique = enforceUnique;
1107 
1108  indexScanKey = _bt_mkscankey(indexRel, NULL);
1109 
1110  /* Prepare SortSupport data for each column */
1111  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1112  sizeof(SortSupportData));
1113 
1114  for (i = 0; i < state->nKeys; i++)
1115  {
1116  SortSupport sortKey = state->sortKeys + i;
1117  ScanKey scanKey = indexScanKey->scankeys + i;
1118  int16 strategy;
1119 
1120  sortKey->ssup_cxt = CurrentMemoryContext;
1121  sortKey->ssup_collation = scanKey->sk_collation;
1122  sortKey->ssup_nulls_first =
1123  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1124  sortKey->ssup_attno = scanKey->sk_attno;
1125  /* Convey if abbreviation optimization is applicable in principle */
1126  sortKey->abbreviate = (i == 0);
1127 
1128  AssertState(sortKey->ssup_attno != 0);
1129 
1130  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1132 
1133  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1134  }
1135 
1136  pfree(indexScanKey);
1137 
1138  MemoryContextSwitchTo(oldcontext);
1139 
1140  return state;
1141 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:428
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:807
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:4388
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:4200
bool trace_sort
Definition: tuplesort.c:140
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
void pfree(void *pointer)
Definition: mcxt.c:1169
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4395
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:4417
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:496
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:162
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1083
void * palloc0(Size size)
Definition: mcxt.c:1093
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:1082
Definition: regguts.h:317
bool enforceUnique
Definition: tuplesort.c:462
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:791
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:721
Oid sk_collation
Definition: skey.h:70
#define elog(elevel,...)
Definition: elog.h:232
int i
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67

◆ tuplesort_begin_index_gist()

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

Definition at line 1190 of file tuplesort.c.

References SortSupportData::abbreviate, AssertState, Tuplesortstate::comparetup, comparetup_index_btree(), Tuplesortstate::copytup, copytup_index(), CurrentMemoryContext, elog, Tuplesortstate::heapRel, i, Tuplesortstate::indexRel, IndexRelationGetNumberOfKeyAttributes, LOG, MemoryContextSwitchTo(), Tuplesortstate::nKeys, palloc0(), PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, Tuplesortstate::readtup, readtup_index(), Tuplesortstate::sortcontext, Tuplesortstate::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_index().

Referenced by gistbuild().

1195 {
1196  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1197  randomAccess);
1198  MemoryContext oldcontext;
1199  int i;
1200 
1201  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1202 
1203 #ifdef TRACE_SORT
1204  if (trace_sort)
1205  elog(LOG,
1206  "begin index sort: workMem = %d, randomAccess = %c",
1207  workMem, randomAccess ? 't' : 'f');
1208 #endif
1209 
1210  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1211 
1213  state->copytup = copytup_index;
1214  state->writetup = writetup_index;
1215  state->readtup = readtup_index;
1216 
1217  state->heapRel = heapRel;
1218  state->indexRel = indexRel;
1219 
1220  /* Prepare SortSupport data for each column */
1221  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1222  sizeof(SortSupportData));
1223 
1224  for (i = 0; i < state->nKeys; i++)
1225  {
1226  SortSupport sortKey = state->sortKeys + i;
1227 
1228  sortKey->ssup_cxt = CurrentMemoryContext;
1229  sortKey->ssup_collation = indexRel->rd_indcollation[i];
1230  sortKey->ssup_nulls_first = false;
1231  sortKey->ssup_attno = i + 1;
1232  /* Convey if abbreviation optimization is applicable in principle */
1233  sortKey->abbreviate = (i == 0);
1234 
1235  AssertState(sortKey->ssup_attno != 0);
1236 
1237  /* Look for a sort support function */
1238  PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
1239  }
1240 
1241  MemoryContextSwitchTo(oldcontext);
1242 
1243  return state;
1244 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
bool ssup_nulls_first
Definition: sortsupport.h:75
Relation heapRel
Definition: tuplesort.c:458
#define AssertState(condition)
Definition: c.h:807
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4388
SortSupport sortKeys
Definition: tuplesort.c:430
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
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4200
bool trace_sort
Definition: tuplesort.c:140
Oid * rd_indcollation
Definition: rel.h:212
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:189
MemoryContext sortcontext
Definition: tuplesort.c:262
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4395
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:4417
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:496
void * palloc0(Size size)
Definition: mcxt.c:1093
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
Definition: regguts.h:317
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:721
#define elog(elevel,...)
Definition: elog.h:232
int i

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

1152 {
1153  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1154  randomAccess);
1155  MemoryContext oldcontext;
1156 
1157  oldcontext = MemoryContextSwitchTo(state->maincontext);
1158 
1159 #ifdef TRACE_SORT
1160  if (trace_sort)
1161  elog(LOG,
1162  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
1163  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
1164  high_mask,
1165  low_mask,
1166  max_buckets,
1167  workMem, randomAccess ? 't' : 'f');
1168 #endif
1169 
1170  state->nKeys = 1; /* Only one sort column, the hash code */
1171 
1173  state->copytup = copytup_index;
1174  state->writetup = writetup_index;
1175  state->readtup = readtup_index;
1176 
1177  state->heapRel = heapRel;
1178  state->indexRel = indexRel;
1179 
1180  state->high_mask = high_mask;
1181  state->low_mask = low_mask;
1182  state->max_buckets = max_buckets;
1183 
1184  MemoryContextSwitchTo(oldcontext);
1185 
1186  return state;
1187 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4333
Relation heapRel
Definition: tuplesort.c:458
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4388
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:4395
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:4417
Relation indexRel
Definition: tuplesort.c:459
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:317
uint32 max_buckets
Definition: tuplesort.c:467
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:721
#define elog(elevel,...)
Definition: elog.h:232
uint32 low_mask
Definition: tuplesort.c:466

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1464 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(), gistbuild(), heapam_relation_copy_for_cluster(), initialize_aggregate(), initialize_phase(), ordered_set_shutdown(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), and validate_index().

1465 {
1466  tuplesort_free(state);
1467 
1468  /*
1469  * Free the main memory context, including the Tuplesortstate struct
1470  * itself.
1471  */
1473 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:218
MemoryContext maincontext
Definition: tuplesort.c:260
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1391

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nworkers)

Definition at line 4557 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

4558 {
4559  Size tapesSize;
4560 
4561  Assert(nWorkers > 0);
4562 
4563  /* Make sure that BufFile shared state is MAXALIGN'd */
4564  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4565  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4566 
4567  return tapesSize;
4568 }
Size mul_size(Size s1, Size s2)
Definition: shmem.c:519
Size add_size(Size s1, Size s2)
Definition: shmem.c:502
#define Assert(condition)
Definition: c.h:804
size_t Size
Definition: c.h:540
#define MAXALIGN(LEN)
Definition: c.h:757
#define offsetof(type, field)
Definition: c.h:727

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

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

3380 {
3381  /*
3382  * Note: it might seem we should provide both memory and disk usage for a
3383  * disk-based sort. However, the current code doesn't track memory space
3384  * accurately once we have begun to return tuples to the caller (since we
3385  * don't account for pfree's the caller is expected to do), so we cannot
3386  * rely on availMem in a disk sort. This does not seem worth the overhead
3387  * to fix. Is it worth creating an API for the memory context code to
3388  * tell us how much is actually used in sortcontext?
3389  */
3390  tuplesort_updatemax(state);
3391 
3392  if (state->isMaxSpaceDisk)
3394  else
3396  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
3397 
3398  switch (state->maxSpaceStatus)
3399  {
3400  case TSS_SORTEDINMEM:
3401  if (state->boundUsed)
3403  else
3405  break;
3406  case TSS_SORTEDONTAPE:
3408  break;
3409  case TSS_FINALMERGE:
3411  break;
3412  default:
3414  break;
3415  }
3416 }
bool isMaxSpaceDisk
Definition: tuplesort.c:256
int64 maxSpace
Definition: tuplesort.c:254
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1481
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 2494 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 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().

2496 {
2497  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2498  SortTuple stup;
2499 
2500  if (!tuplesort_gettuple_common(state, forward, &stup))
2501  {
2502  MemoryContextSwitchTo(oldcontext);
2503  return false;
2504  }
2505 
2506  /* Ensure we copy into caller's memory context */
2507  MemoryContextSwitchTo(oldcontext);
2508 
2509  /* Record abbreviated key for caller */
2510  if (state->sortKeys->abbrev_converter && abbrev)
2511  *abbrev = stup.datum1;
2512 
2513  if (stup.isnull1 || !state->tuples)
2514  {
2515  *val = stup.datum1;
2516  *isNull = stup.isnull1;
2517  }
2518  else
2519  {
2520  /* use stup.tuple because stup.datum1 may be an abbreviation */
2521  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2522  *isNull = false;
2523  }
2524 
2525  return true;
2526 }
#define PointerGetDatum(X)
Definition: postgres.h:600
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:2151
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 2445 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

2446 {
2447  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2448  SortTuple stup;
2449 
2450  if (!tuplesort_gettuple_common(state, forward, &stup))
2451  stup.tuple = NULL;
2452 
2453  MemoryContextSwitchTo(oldcontext);
2454 
2455  return stup.tuple;
2456 }
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:2151

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2465 of file tuplesort.c.

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

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

2466 {
2467  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2468  SortTuple stup;
2469 
2470  if (!tuplesort_gettuple_common(state, forward, &stup))
2471  stup.tuple = NULL;
2472 
2473  MemoryContextSwitchTo(oldcontext);
2474 
2475  return (IndexTuple) stup.tuple;
2476 }
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:2151

◆ tuplesort_gettupleslot()

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

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

2410 {
2411  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2412  SortTuple stup;
2413 
2414  if (!tuplesort_gettuple_common(state, forward, &stup))
2415  stup.tuple = NULL;
2416 
2417  MemoryContextSwitchTo(oldcontext);
2418 
2419  if (stup.tuple)
2420  {
2421  /* Record abbreviated key for caller */
2422  if (state->sortKeys->abbrev_converter && abbrev)
2423  *abbrev = stup.datum1;
2424 
2425  if (copy)
2427 
2428  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
2429  return true;
2430  }
2431  else
2432  {
2433  ExecClearTuple(slot);
2434  return false;
2435  }
2436 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1446
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:2151

◆ tuplesort_initialize_shared()

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

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

4579 {
4580  int i;
4581 
4582  Assert(nWorkers > 0);
4583 
4584  SpinLockInit(&shared->mutex);
4585  shared->currentWorker = 0;
4586  shared->workersFinished = 0;
4587  SharedFileSetInit(&shared->fileset, seg);
4588  shared->nTapes = nWorkers;
4589  for (i = 0; i < nWorkers; i++)
4590  {
4591  shared->tapes[i].firstblocknumber = 0L;
4592  }
4593 }
slock_t mutex
Definition: tuplesort.c:492
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:44
#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:804
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 3312 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().

3313 {
3314  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3315 
3316  Assert(state->randomAccess);
3317 
3318  switch (state->status)
3319  {
3320  case TSS_SORTEDINMEM:
3321  state->markpos_offset = state->current;
3322  state->markpos_eof = state->eof_reached;
3323  break;
3324  case TSS_SORTEDONTAPE:
3325  LogicalTapeTell(state->tapeset,
3326  state->result_tape,
3327  &state->markpos_block,
3328  &state->markpos_offset);
3329  state->markpos_eof = state->eof_reached;
3330  break;
3331  default:
3332  elog(ERROR, "invalid tuplesort state");
3333  break;
3334  }
3335 
3336  MemoryContextSwitchTo(oldcontext);
3337 }
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:46
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:1245
#define Assert(condition)
Definition: c.h:804
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:232

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2602 of file tuplesort.c.

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

Referenced by cost_tuplesort(), and inittapes().

2603 {
2604  int mOrder;
2605 
2606  /*
2607  * We need one tape for each merge input, plus another one for the output,
2608  * and each of these tapes needs buffer space. In addition we want
2609  * MERGE_BUFFER_SIZE workspace per input tape (but the output tape doesn't
2610  * count).
2611  *
2612  * Note: you might be thinking we need to account for the memtuples[]
2613  * array in this calculation, but we effectively treat that as part of the
2614  * MERGE_BUFFER_SIZE workspace.
2615  */
2616  mOrder = (allowedMem - TAPE_BUFFER_OVERHEAD) /
2618 
2619  /*
2620  * Even in minimum memory, use at least a MINORDER merge. On the other
2621  * hand, even when we have lots of memory, do not use more than a MAXORDER
2622  * merge. Tapes are pretty cheap, but they're not entirely free. Each
2623  * additional tape reduces the amount of memory available to build runs,
2624  * which in turn can cause the same sort to need more runs, which makes
2625  * merging slower even if it can still be done in a single pass. Also,
2626  * high order merges are quite slow due to CPU cache effects; it can be
2627  * faster to pay the I/O cost of a polyphase merge than to perform a
2628  * single merge pass across many hundreds of tapes.
2629  */
2630  mOrder = Max(mOrder, MINORDER);
2631  mOrder = Min(mOrder, MAXORDER);
2632 
2633  return mOrder;
2634 }
#define Min(x, y)
Definition: c.h:986
#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:980
#define MAXORDER
Definition: tuplesort.c:230

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

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

3423 {
3424  switch (m)
3425  {
3427  return "still in progress";
3429  return "top-N heapsort";
3430  case SORT_TYPE_QUICKSORT:
3431  return "quicksort";
3433  return "external sort";
3435  return "external merge";
3436  }
3437 
3438  return "unknown";
3439 }

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

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

2041 {
2042  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2043 
2044 #ifdef TRACE_SORT
2045  if (trace_sort)
2046  elog(LOG, "performsort of worker %d starting: %s",
2047  state->worker, pg_rusage_show(&state->ru_start));
2048 #endif
2049 
2050  switch (state->status)
2051  {
2052  case TSS_INITIAL:
2053 
2054  /*
2055  * We were able to accumulate all the tuples within the allowed
2056  * amount of memory, or leader to take over worker tapes
2057  */
2058  if (SERIAL(state))
2059  {
2060  /* Just qsort 'em and we're done */
2061  tuplesort_sort_memtuples(state);
2062  state->status = TSS_SORTEDINMEM;
2063  }
2064  else if (WORKER(state))
2065  {
2066  /*
2067  * Parallel workers must still dump out tuples to tape. No
2068  * merge is required to produce single output run, though.
2069  */
2070  inittapes(state, false);
2071  dumptuples(state, true);
2072  worker_nomergeruns(state);
2073  state->status = TSS_SORTEDONTAPE;
2074  }
2075  else
2076  {
2077  /*
2078  * Leader will take over worker tapes and merge worker runs.
2079  * Note that mergeruns sets the correct state->status.
2080  */
2081  leader_takeover_tapes(state);
2082  mergeruns(state);
2083  }
2084  state->current = 0;
2085  state->eof_reached = false;
2086  state->markpos_block = 0L;
2087  state->markpos_offset = 0;
2088  state->markpos_eof = false;
2089  break;
2090 
2091  case TSS_BOUNDED:
2092 
2093  /*
2094  * We were able to accumulate all the tuples required for output
2095  * in memory, using a heap to eliminate excess tuples. Now we
2096  * have to transform the heap to a properly-sorted array.
2097  */
2098  sort_bounded_heap(state);
2099  state->current = 0;
2100  state->eof_reached = false;
2101  state->markpos_offset = 0;
2102  state->markpos_eof = false;
2103  state->status = TSS_SORTEDINMEM;
2104  break;
2105 
2106  case TSS_BUILDRUNS:
2107 
2108  /*
2109  * Finish tape-based sort. First, flush all tuples remaining in
2110  * memory out to tape; then merge until we have a single remaining
2111  * run (or, if !randomAccess and !WORKER(), one run per tape).
2112  * Note that mergeruns sets the correct state->status.
2113  */
2114  dumptuples(state, true);
2115  mergeruns(state);
2116  state->eof_reached = false;
2117  state->markpos_block = 0L;
2118  state->markpos_offset = 0;
2119  state->markpos_eof = false;
2120  break;
2121 
2122  default:
2123  elog(ERROR, "invalid tuplesort state");
2124  break;
2125  }
2126 
2127 #ifdef TRACE_SORT
2128  if (trace_sort)
2129  {
2130  if (state->status == TSS_FINALMERGE)
2131  elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
2132  state->worker, state->activeTapes,
2133  pg_rusage_show(&state->ru_start));
2134  else
2135  elog(LOG, "performsort of worker %d done: %s",
2136  state->worker, pg_rusage_show(&state->ru_start));
2137  }
2138 #endif
2139 
2140  MemoryContextSwitchTo(oldcontext);
2141 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:3174
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:3515
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:2642
#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:2811
#define ERROR
Definition: elog.h:46
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:3555
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:4708
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:232
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:4687

◆ tuplesort_putdatum()

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

Definition at line 1805 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(), ExecSort(), ordered_set_transition(), and validate_index_callback().

1806 {
1807  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1808  SortTuple stup;
1809 
1810  /*
1811  * Pass-by-value types or null values are just stored directly in
1812  * stup.datum1 (and stup.tuple is not used and set to NULL).
1813  *
1814  * Non-null pass-by-reference values need to be copied into memory we
1815  * control, and possibly abbreviated. The copied value is pointed to by
1816  * stup.tuple and is treated as the canonical copy (e.g. to return via
1817  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
1818  * abbreviated value if abbreviation is happening, otherwise it's
1819  * identical to stup.tuple.
1820  */
1821 
1822  if (isNull || !state->tuples)
1823  {
1824  /*
1825  * Set datum1 to zeroed representation for NULLs (to be consistent,
1826  * and to support cheap inequality tests for NULL abbreviated keys).
1827  */
1828  stup.datum1 = !isNull ? val : (Datum) 0;
1829  stup.isnull1 = isNull;
1830  stup.tuple = NULL; /* no separate storage */
1832  }
1833  else
1834  {
1835  Datum original = datumCopy(val, false, state->datumTypeLen);
1836 
1837  stup.isnull1 = false;
1838  stup.tuple = DatumGetPointer(original);
1839  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1841 
1842  if (!state->sortKeys->abbrev_converter)
1843  {
1844  stup.datum1 = original;
1845  }
1846  else if (!consider_abort_common(state))
1847  {
1848  /* Store abbreviated key representation */
1849  stup.datum1 = state->sortKeys->abbrev_converter(original,
1850  state->sortKeys);
1851  }
1852  else
1853  {
1854  /* Abort abbreviation */
1855  int i;
1856 
1857  stup.datum1 = original;
1858 
1859  /*
1860  * Set state to be consistent with never trying abbreviation.
1861  *
1862  * Alter datum1 representation in already-copied tuples, so as to
1863  * ensure a consistent representation (current tuple was just
1864  * handled). It does not matter if some dumped tuples are already
1865  * sorted on tape, since serialized tuples lack abbreviated keys
1866  * (TSS_BUILDRUNS state prevents control reaching here in any
1867  * case).
1868  */
1869  for (i = 0; i < state->memtupcount; i++)
1870  {
1871  SortTuple *mtup = &state->memtuples[i];
1872 
1873  mtup->datum1 = PointerGetDatum(mtup->tuple);
1874  }
1875  }
1876  }
1877 
1878  puttuple_common(state, &stup);
1879 
1880  MemoryContextSwitchTo(oldcontext);
1881 }
#define PointerGetDatum(X)
Definition: postgres.h:600
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:434
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1996
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:411
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1887
#define DatumGetPointer(X)
Definition: postgres.h:593
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 1706 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

1707 {
1708  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1709  SortTuple stup;
1710 
1711  /*
1712  * Copy the given tuple into memory we control, and decrease availMem.
1713  * Then call the common code.
1714  */
1715  COPYTUP(state, &stup, (void *) tup);
1716 
1717  puttuple_common(state, &stup);
1718 
1719  MemoryContextSwitchTo(oldcontext);
1720 }
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:1887

◆ tuplesort_putindextuplevalues()

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

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

1730 {
1731  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1732  SortTuple stup;
1733  Datum original;
1734  IndexTuple tuple;
1735 
1736  stup.tuple = index_form_tuple(RelationGetDescr(rel), values, isnull);
1737  tuple = ((IndexTuple) stup.tuple);
1738  tuple->t_tid = *self;
1739  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1740  /* set up first-column key value */
1741  original = index_getattr(tuple,
1742  1,
1743  RelationGetDescr(state->indexRel),
1744  &stup.isnull1);
1745 
1747 
1748  if (!state->sortKeys || !state->sortKeys->abbrev_converter || stup.isnull1)
1749  {
1750  /*
1751  * Store ordinary Datum representation, or NULL value. If there is a
1752  * converter it won't expect NULL values, and cost model is not
1753  * required to account for NULL, so in that case we avoid calling
1754  * converter and just set datum1 to zeroed representation (to be
1755  * consistent, and to support cheap inequality tests for NULL
1756  * abbreviated keys).
1757  */
1758  stup.datum1 = original;
1759  }
1760  else if (!consider_abort_common(state))
1761  {
1762  /* Store abbreviated key representation */
1763  stup.datum1 = state->sortKeys->abbrev_converter(original,
1764  state->sortKeys);
1765  }
1766  else
1767  {
1768  /* Abort abbreviation */
1769  int i;
1770 
1771  stup.datum1 = original;
1772 
1773  /*
1774  * Set state to be consistent with never trying abbreviation.
1775  *
1776  * Alter datum1 representation in already-copied tuples, so as to
1777  * ensure a consistent representation (current tuple was just
1778  * handled). It does not matter if some dumped tuples are already
1779  * sorted on tape, since serialized tuples lack abbreviated keys
1780  * (TSS_BUILDRUNS state prevents control reaching here in any case).
1781  */
1782  for (i = 0; i < state->memtupcount; i++)
1783  {
1784  SortTuple *mtup = &state->memtuples[i];
1785 
1786  tuple = mtup->tuple;
1787  mtup->datum1 = index_getattr(tuple,
1788  1,
1789  RelationGetDescr(state->indexRel),
1790  &mtup->isnull1);
1791  }
1792  }
1793 
1794  puttuple_common(state, &stup);
1795 
1796  MemoryContextSwitchTo(oldcontext);
1797 }
#define RelationGetDescr(relation)
Definition: rel.h:503
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:434
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:1996
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:411
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1887
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static Datum values[MAXATTR]
Definition: bootstrap.c:156
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 1684 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().

1685 {
1686  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1687  SortTuple stup;
1688 
1689  /*
1690  * Copy the given tuple into memory we control, and decrease availMem.
1691  * Then call the common code.
1692  */
1693  COPYTUP(state, &stup, (void *) slot);
1694 
1695  puttuple_common(state, &stup);
1696 
1697  MemoryContextSwitchTo(oldcontext);
1698 }
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:1887

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

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

3278 {
3279  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3280 
3281  Assert(state->randomAccess);
3282 
3283  switch (state->status)
3284  {
3285  case TSS_SORTEDINMEM:
3286  state->current = 0;
3287  state->eof_reached = false;
3288  state->markpos_offset = 0;
3289  state->markpos_eof = false;
3290  break;
3291  case TSS_SORTEDONTAPE:
3293  state->result_tape,
3294  0);
3295  state->eof_reached = false;
3296  state->markpos_block = 0L;
3297  state->markpos_offset = 0;
3298  state->markpos_eof = false;
3299  break;
3300  default:
3301  elog(ERROR, "invalid tuplesort state");
3302  break;
3303  }
3304 
3305  MemoryContextSwitchTo(oldcontext);
3306 }
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:46
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define Assert(condition)
Definition: c.h:804
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:863
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:232

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate state)

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

1533 {
1534  tuplesort_updatemax(state);
1535  tuplesort_free(state);
1536 
1537  /*
1538  * After we've freed up per-batch memory, re-setup all of the state common
1539  * to both the first batch and any subsequent batch.
1540  */
1541  tuplesort_begin_batch(state);
1542 
1543  state->lastReturnedTuple = NULL;
1544  state->slabMemoryBegin = NULL;
1545  state->slabMemoryEnd = NULL;
1546  state->slabFreeHead = NULL;
1547 }
char * slabMemoryEnd
Definition: tuplesort.c:346
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1481
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:833
void * lastReturnedTuple
Definition: tuplesort.c:358
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1391
char * slabMemoryBegin
Definition: tuplesort.c:345
SlabSlot * slabFreeHead
Definition: tuplesort.c:347

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

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

3345 {
3346  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3347 
3348  Assert(state->randomAccess);
3349 
3350  switch (state->status)
3351  {
3352  case TSS_SORTEDINMEM:
3353  state->current = state->markpos_offset;
3354  state->eof_reached = state->markpos_eof;
3355  break;
3356  case TSS_SORTEDONTAPE:
3357  LogicalTapeSeek(state->tapeset,
3358  state->result_tape,
3359  state->markpos_block,
3360  state->markpos_offset);
3361  state->eof_reached = state->markpos_eof;
3362  break;
3363  default:
3364  elog(ERROR, "invalid tuplesort state");
3365  break;
3366  }
3367 
3368  MemoryContextSwitchTo(oldcontext);
3369 }
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:46
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define Assert(condition)
Definition: c.h:804
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:232
void LogicalTapeSeek(LogicalTapeSet *lts, int tapenum, long blocknum, int offset)
Definition: logtape.c:1211

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

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

1335 {
1336  /* Assert we're called before loading any tuples */
1337  Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
1338  /* Can't set the bound twice, either */
1339  Assert(!state->bounded);
1340  /* Also, this shouldn't be called in a parallel worker */
1341  Assert(!WORKER(state));
1342 
1343  /* Parallel leader allows but ignores hint */
1344  if (LEADER(state))
1345  return;
1346 
1347 #ifdef DEBUG_BOUNDED_SORT
1348  /* Honor GUC setting that disables the feature (for easy testing) */
1349  if (!optimize_bounded_sort)
1350  return;
1351 #endif
1352 
1353  /* We want to be able to compute bound * 2, so limit the setting */
1354  if (bound > (int64) (INT_MAX / 2))
1355  return;
1356 
1357  state->bounded = true;
1358  state->bound = (int) bound;
1359 
1360  /*
1361  * Bounded sorts are not an effective target for abbreviated key
1362  * optimization. Disable by setting state to be consistent with no
1363  * abbreviation support.
1364  */
1365  state->sortKeys->abbrev_converter = NULL;
1366  if (state->sortKeys->abbrev_full_comparator)
1368 
1369  /* Not strictly necessary, but be tidy */
1370  state->sortKeys->abbrev_abort = NULL;
1371  state->sortKeys->abbrev_full_comparator = NULL;
1372 }
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:804
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 2534 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().

2535 {
2536  MemoryContext oldcontext;
2537 
2538  /*
2539  * We don't actually support backwards skip yet, because no callers need
2540  * it. The API is designed to allow for that later, though.
2541  */
2542  Assert(forward);
2543  Assert(ntuples >= 0);
2544  Assert(!WORKER(state));
2545 
2546  switch (state->status)
2547  {
2548  case TSS_SORTEDINMEM:
2549  if (state->memtupcount - state->current >= ntuples)
2550  {
2551  state->current += ntuples;
2552  return true;
2553  }
2554  state->current = state->memtupcount;
2555  state->eof_reached = true;
2556 
2557  /*
2558  * Complain if caller tries to retrieve more tuples than
2559  * originally asked for in a bounded sort. This is because
2560  * returning EOF here might be the wrong thing.
2561  */
2562  if (state->bounded && state->current >= state->bound)
2563  elog(ERROR, "retrieved too many tuples in a bounded sort");
2564 
2565  return false;
2566 
2567  case TSS_SORTEDONTAPE:
2568  case TSS_FINALMERGE:
2569 
2570  /*
2571  * We could probably optimize these cases better, but for now it's
2572  * not worth the trouble.
2573  */
2574  oldcontext = MemoryContextSwitchTo(state->sortcontext);
2575  while (ntuples-- > 0)
2576  {
2577  SortTuple stup;
2578 
2579  if (!tuplesort_gettuple_common(state, forward, &stup))
2580  {
2581  MemoryContextSwitchTo(oldcontext);
2582  return false;
2583  }
2585  }
2586  MemoryContextSwitchTo(oldcontext);
2587  return true;
2588 
2589  default:
2590  elog(ERROR, "invalid tuplesort state");
2591  return false; /* keep compiler quiet */
2592  }
2593 }
TupSortStatus status
Definition: tuplesort.c:242
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define ERROR
Definition: elog.h:46
MemoryContext sortcontext
Definition: tuplesort.c:262
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2151
#define WORKER(state)
Definition: tuplesort.c:549
#define Assert(condition)
Definition: c.h:804
bool eof_reached
Definition: tuplesort.c:398
#define elog(elevel,...)
Definition: elog.h:232
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:120

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType  t)

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

3446 {
3448  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
3449 }
#define Assert(condition)
Definition: c.h:804

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate state)

Definition at line 1380 of file tuplesort.c.

References Tuplesortstate::boundUsed.

Referenced by ExecIncrementalSort().

1381 {
1382  return state->boundUsed;
1383 }