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.

Typedef Documentation

◆ Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 1 of file tuplesort.h.

◆ SortCoordinate

Definition at line 58 of file tuplesort.h.

◆ SortCoordinateData

◆ TuplesortInstrumentation

◆ Tuplesortstate

Definition at line 1 of file tuplesort.h.

Enumeration Type Documentation

◆ TuplesortMethod

Enumerator
SORT_TYPE_STILL_IN_PROGRESS 
SORT_TYPE_TOP_N_HEAPSORT 
SORT_TYPE_QUICKSORT 
SORT_TYPE_EXTERNAL_SORT 
SORT_TYPE_EXTERNAL_MERGE 

Definition at line 72 of file tuplesort.h.

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

◆ TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK 
SORT_SPACE_TYPE_MEMORY 

Definition at line 83 of file tuplesort.h.

84 {
TuplesortSpaceType
Definition: tuplesort.h:84
@ SORT_SPACE_TYPE_DISK
Definition: tuplesort.h:85
@ SORT_SPACE_TYPE_MEMORY
Definition: tuplesort.h:86

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 4523 of file tuplesort.c.

4524 {
4525  /* Attach to SharedFileSet */
4526  SharedFileSetAttach(&shared->fileset, seg);
4527 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:62
SharedFileSet fileset
Definition: tuplesort.c:505

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

◆ tuplesort_begin_cluster()

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

Definition at line 970 of file tuplesort.c.

974 {
975  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
976  randomAccess);
977  BTScanInsert indexScanKey;
978  MemoryContext oldcontext;
979  int i;
980 
981  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
982 
983  oldcontext = MemoryContextSwitchTo(state->maincontext);
984 
985 #ifdef TRACE_SORT
986  if (trace_sort)
987  elog(LOG,
988  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
990  workMem, randomAccess ? 't' : 'f');
991 #endif
992 
993  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
994 
995  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
996  false, /* no unique check */
997  state->nKeys,
998  workMem,
999  randomAccess,
1000  PARALLEL_SORT(state));
1001 
1002  state->comparetup = comparetup_cluster;
1003  state->copytup = copytup_cluster;
1004  state->writetup = writetup_cluster;
1005  state->readtup = readtup_cluster;
1006  state->abbrevNext = 10;
1007 
1008  state->indexInfo = BuildIndexInfo(indexRel);
1009 
1010  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
1011 
1012  indexScanKey = _bt_mkscankey(indexRel, NULL);
1013 
1014  if (state->indexInfo->ii_Expressions != NULL)
1015  {
1016  TupleTableSlot *slot;
1017  ExprContext *econtext;
1018 
1019  /*
1020  * We will need to use FormIndexDatum to evaluate the index
1021  * expressions. To do that, we need an EState, as well as a
1022  * TupleTableSlot to put the table tuples into. The econtext's
1023  * scantuple has to point to that slot, too.
1024  */
1025  state->estate = CreateExecutorState();
1026  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
1027  econtext = GetPerTupleExprContext(state->estate);
1028  econtext->ecxt_scantuple = slot;
1029  }
1030 
1031  /* Prepare SortSupport data for each column */
1032  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1033  sizeof(SortSupportData));
1034 
1035  for (i = 0; i < state->nKeys; i++)
1036  {
1037  SortSupport sortKey = state->sortKeys + i;
1038  ScanKey scanKey = indexScanKey->scankeys + i;
1039  int16 strategy;
1040 
1041  sortKey->ssup_cxt = CurrentMemoryContext;
1042  sortKey->ssup_collation = scanKey->sk_collation;
1043  sortKey->ssup_nulls_first =
1044  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1045  sortKey->ssup_attno = scanKey->sk_attno;
1046  /* Convey if abbreviation optimization is applicable in principle */
1047  sortKey->abbreviate = (i == 0);
1048 
1049  AssertState(sortKey->ssup_attno != 0);
1050 
1051  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1053 
1054  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1055  }
1056 
1057  pfree(indexScanKey);
1058 
1059  MemoryContextSwitchTo(oldcontext);
1060 
1061  return state;
1062 }
#define AssertState(condition)
Definition: c.h:807
signed short int16
Definition: c.h:428
#define LOG
Definition: elog.h:25
#define elog(elevel,...)
Definition: elog.h:218
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:84
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1238
EState * CreateExecutorState(void)
Definition: execUtils.c:90
#define GetPerTupleExprContext(estate)
Definition: executor.h:533
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2388
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1169
void * palloc0(Size size)
Definition: mcxt.c:1093
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1083
#define SK_BT_DESC
Definition: nbtree.h:1082
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:484
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:497
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:162
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:791
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:227
Form_pg_class rd_rel
Definition: rel.h:109
int sk_flags
Definition: skey.h:66
Oid sk_collation
Definition: skey.h:70
AttrNumber sk_attno
Definition: skey.h:67
AttrNumber ssup_attno
Definition: sortsupport.h:81
bool ssup_nulls_first
Definition: sortsupport.h:75
MemoryContext ssup_cxt
Definition: sortsupport.h:66
Definition: regguts.h:318
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:720
static void copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4005
#define PARALLEL_SORT(state)
Definition: tuplesort.c:129
#define CLUSTER_SORT
Definition: tuplesort.c:126
bool trace_sort
Definition: tuplesort.c:144
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.c:4098
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3894
static void writetup_cluster(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.c:4078

References _bt_mkscankey(), SortSupportData::abbreviate, Assert(), AssertState, BTGreaterStrategyNumber, BTLessStrategyNumber, BuildIndexInfo(), CLUSTER_SORT, comparetup_cluster(), copytup_cluster(), CreateExecutorState(), CurrentMemoryContext, ExprContext::ecxt_scantuple, elog, GetPerTupleExprContext, i, IndexRelationGetNumberOfKeyAttributes, LOG, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, readtup_cluster(), RelationGetNumberOfAttributes, BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TTSOpsHeapTuple, tuplesort_begin_common(), and writetup_cluster().

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_begin_datum()

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

Definition at line 1246 of file tuplesort.c.

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

References comparetup_datum(), copytup_datum(), CurrentMemoryContext, DATUM_SORT, elog, get_typlenbyval(), LOG, MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), readtup_datum(), trace_sort, tuplesort_begin_common(), and writetup_datum().

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

◆ tuplesort_begin_heap()

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

Definition at line 896 of file tuplesort.c.

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

References SortSupportData::abbreviate, AssertArg, comparetup_heap(), copytup_heap(), CurrentMemoryContext, elog, HEAP_SORT, i, LOG, MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), readtup_heap(), SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), and writetup_heap().

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

◆ tuplesort_begin_index_btree()

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

Definition at line 1065 of file tuplesort.c.

1071 {
1072  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1073  randomAccess);
1074  BTScanInsert indexScanKey;
1075  MemoryContext oldcontext;
1076  int i;
1077 
1078  oldcontext = MemoryContextSwitchTo(state->maincontext);
1079 
1080 #ifdef TRACE_SORT
1081  if (trace_sort)
1082  elog(LOG,
1083  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
1084  enforceUnique ? 't' : 'f',
1085  workMem, randomAccess ? 't' : 'f');
1086 #endif
1087 
1088  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1089 
1090  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
1091  enforceUnique,
1092  state->nKeys,
1093  workMem,
1094  randomAccess,
1095  PARALLEL_SORT(state));
1096 
1097  state->comparetup = comparetup_index_btree;
1098  state->copytup = copytup_index;
1099  state->writetup = writetup_index;
1100  state->readtup = readtup_index;
1101  state->abbrevNext = 10;
1102 
1103  state->heapRel = heapRel;
1104  state->indexRel = indexRel;
1105  state->enforceUnique = enforceUnique;
1106 
1107  indexScanKey = _bt_mkscankey(indexRel, NULL);
1108 
1109  /* Prepare SortSupport data for each column */
1110  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1111  sizeof(SortSupportData));
1112 
1113  for (i = 0; i < state->nKeys; i++)
1114  {
1115  SortSupport sortKey = state->sortKeys + i;
1116  ScanKey scanKey = indexScanKey->scankeys + i;
1117  int16 strategy;
1118 
1119  sortKey->ssup_cxt = CurrentMemoryContext;
1120  sortKey->ssup_collation = scanKey->sk_collation;
1121  sortKey->ssup_nulls_first =
1122  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1123  sortKey->ssup_attno = scanKey->sk_attno;
1124  /* Convey if abbreviation optimization is applicable in principle */
1125  sortKey->abbreviate = (i == 0);
1126 
1127  AssertState(sortKey->ssup_attno != 0);
1128 
1129  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1131 
1132  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1133  }
1134 
1135  pfree(indexScanKey);
1136 
1137  MemoryContextSwitchTo(oldcontext);
1138 
1139  return state;
1140 }
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4133
static void readtup_index(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.c:4347
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4321
#define INDEX_SORT
Definition: tuplesort.c:124
static void writetup_index(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.c:4328

References _bt_mkscankey(), SortSupportData::abbreviate, AssertState, BTGreaterStrategyNumber, BTLessStrategyNumber, comparetup_index_btree(), copytup_index(), CurrentMemoryContext, elog, i, INDEX_SORT, IndexRelationGetNumberOfKeyAttributes, LOG, MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), readtup_index(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), and writetup_index().

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

◆ tuplesort_begin_index_gist()

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

Definition at line 1189 of file tuplesort.c.

1194 {
1195  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1196  randomAccess);
1197  MemoryContext oldcontext;
1198  int i;
1199 
1200  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1201 
1202 #ifdef TRACE_SORT
1203  if (trace_sort)
1204  elog(LOG,
1205  "begin index sort: workMem = %d, randomAccess = %c",
1206  workMem, randomAccess ? 't' : 'f');
1207 #endif
1208 
1209  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1210 
1211  state->comparetup = comparetup_index_btree;
1212  state->copytup = copytup_index;
1213  state->writetup = writetup_index;
1214  state->readtup = readtup_index;
1215 
1216  state->heapRel = heapRel;
1217  state->indexRel = indexRel;
1218 
1219  /* Prepare SortSupport data for each column */
1220  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1221  sizeof(SortSupportData));
1222 
1223  for (i = 0; i < state->nKeys; i++)
1224  {
1225  SortSupport sortKey = state->sortKeys + i;
1226 
1227  sortKey->ssup_cxt = CurrentMemoryContext;
1228  sortKey->ssup_collation = indexRel->rd_indcollation[i];
1229  sortKey->ssup_nulls_first = false;
1230  sortKey->ssup_attno = i + 1;
1231  /* Convey if abbreviation optimization is applicable in principle */
1232  sortKey->abbreviate = (i == 0);
1233 
1234  AssertState(sortKey->ssup_attno != 0);
1235 
1236  /* Look for a sort support function */
1237  PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
1238  }
1239 
1240  MemoryContextSwitchTo(oldcontext);
1241 
1242  return state;
1243 }
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:189
Oid * rd_indcollation
Definition: rel.h:213

References SortSupportData::abbreviate, AssertState, comparetup_index_btree(), copytup_index(), CurrentMemoryContext, elog, i, IndexRelationGetNumberOfKeyAttributes, LOG, MemoryContextSwitchTo(), palloc0(), PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, readtup_index(), SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), and writetup_index().

Referenced by gistbuild().

◆ tuplesort_begin_index_hash()

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

Definition at line 1143 of file tuplesort.c.

1151 {
1152  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1153  randomAccess);
1154  MemoryContext oldcontext;
1155 
1156  oldcontext = MemoryContextSwitchTo(state->maincontext);
1157 
1158 #ifdef TRACE_SORT
1159  if (trace_sort)
1160  elog(LOG,
1161  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
1162  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
1163  high_mask,
1164  low_mask,
1165  max_buckets,
1166  workMem, randomAccess ? 't' : 'f');
1167 #endif
1168 
1169  state->nKeys = 1; /* Only one sort column, the hash code */
1170 
1171  state->comparetup = comparetup_index_hash;
1172  state->copytup = copytup_index;
1173  state->writetup = writetup_index;
1174  state->readtup = readtup_index;
1175 
1176  state->heapRel = heapRel;
1177  state->indexRel = indexRel;
1178 
1179  state->high_mask = high_mask;
1180  state->low_mask = low_mask;
1181  state->max_buckets = max_buckets;
1182 
1183  MemoryContextSwitchTo(oldcontext);
1184 
1185  return state;
1186 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4266

References comparetup_index_hash(), copytup_index(), elog, LOG, MemoryContextSwitchTo(), readtup_index(), trace_sort, tuplesort_begin_common(), and writetup_index().

Referenced by _h_spoolinit().

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1467 of file tuplesort.c.

1468 {
1470 
1471  /*
1472  * Free the main memory context, including the Tuplesortstate struct
1473  * itself.
1474  */
1475  MemoryContextDelete(state->maincontext);
1476 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:218
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1390

References MemoryContextDelete(), and tuplesort_free().

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

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nworkers)

Definition at line 4479 of file tuplesort.c.

4480 {
4481  Size tapesSize;
4482 
4483  Assert(nWorkers > 0);
4484 
4485  /* Make sure that BufFile shared state is MAXALIGN'd */
4486  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4487  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4488 
4489  return tapesSize;
4490 }
#define MAXALIGN(LEN)
Definition: c.h:757
#define offsetof(type, field)
Definition: c.h:727
size_t Size
Definition: c.h:540
Size add_size(Size s1, Size s2)
Definition: shmem.c:502
Size mul_size(Size s1, Size s2)
Definition: shmem.c:519

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

Referenced by _bt_begin_parallel().

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 3323 of file tuplesort.c.

3325 {
3326  /*
3327  * Note: it might seem we should provide both memory and disk usage for a
3328  * disk-based sort. However, the current code doesn't track memory space
3329  * accurately once we have begun to return tuples to the caller (since we
3330  * don't account for pfree's the caller is expected to do), so we cannot
3331  * rely on availMem in a disk sort. This does not seem worth the overhead
3332  * to fix. Is it worth creating an API for the memory context code to
3333  * tell us how much is actually used in sortcontext?
3334  */
3336 
3337  if (state->isMaxSpaceDisk)
3339  else
3341  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
3342 
3343  switch (state->maxSpaceStatus)
3344  {
3345  case TSS_SORTEDINMEM:
3346  if (state->boundUsed)
3348  else
3350  break;
3351  case TSS_SORTEDONTAPE:
3353  break;
3354  case TSS_FINALMERGE:
3356  break;
3357  default:
3359  break;
3360  }
3361 }
TuplesortMethod sortMethod
Definition: tuplesort.h:91
TuplesortSpaceType spaceType
Definition: tuplesort.h:92
@ TSS_SORTEDONTAPE
Definition: tuplesort.c:218
@ TSS_SORTEDINMEM
Definition: tuplesort.c:217
@ TSS_FINALMERGE
Definition: tuplesort.c:219
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1484

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

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

◆ tuplesort_getdatum()

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

Definition at line 2494 of file tuplesort.c.

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 }
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
long val
Definition: informix.c:664
#define PointerGetDatum(X)
Definition: postgres.h:600
bool isnull1
Definition: tuplesort.c:185
void * tuple
Definition: tuplesort.c:183
Datum datum1
Definition: tuplesort.c:184
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2154

References SortTuple::datum1, datumCopy(), SortTuple::isnull1, MemoryContextSwitchTo(), PointerGetDatum, SortTuple::tuple, tuplesort_gettuple_common(), and val.

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

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2445 of file tuplesort.c.

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 }

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

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2465 of file tuplesort.c.

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 }

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

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

◆ tuplesort_gettupleslot()

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

Definition at line 2408 of file tuplesort.c.

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
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1439
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:425

References SortTuple::datum1, ExecClearTuple(), ExecStoreMinimalTuple(), heap_copy_minimal_tuple(), MemoryContextSwitchTo(), 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().

◆ tuplesort_initialize_shared()

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

Definition at line 4500 of file tuplesort.c.

4501 {
4502  int i;
4503 
4504  Assert(nWorkers > 0);
4505 
4506  SpinLockInit(&shared->mutex);
4507  shared->currentWorker = 0;
4508  shared->workersFinished = 0;
4509  SharedFileSetInit(&shared->fileset, seg);
4510  shared->nTapes = nWorkers;
4511  for (i = 0; i < nWorkers; i++)
4512  {
4513  shared->tapes[i].firstblocknumber = 0L;
4514  }
4515 }
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:44
#define SpinLockInit(lock)
Definition: spin.h:60
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:514
int workersFinished
Definition: tuplesort.c:502
int nTapes
Definition: tuplesort.c:508
slock_t mutex
Definition: tuplesort.c:491
int currentWorker
Definition: tuplesort.c:501
long firstblocknumber
Definition: logtape.h:54

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

Referenced by _bt_begin_parallel().

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

Definition at line 3259 of file tuplesort.c.

3260 {
3261  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3262 
3263  Assert(state->randomAccess);
3264 
3265  switch (state->status)
3266  {
3267  case TSS_SORTEDINMEM:
3268  state->markpos_offset = state->current;
3269  state->markpos_eof = state->eof_reached;
3270  break;
3271  case TSS_SORTEDONTAPE:
3272  LogicalTapeTell(state->result_tape,
3273  &state->markpos_block,
3274  &state->markpos_offset);
3275  state->markpos_eof = state->eof_reached;
3276  break;
3277  default:
3278  elog(ERROR, "invalid tuplesort state");
3279  break;
3280  }
3281 
3282  MemoryContextSwitchTo(oldcontext);
3283 }
#define ERROR
Definition: elog.h:33
void LogicalTapeTell(LogicalTape *lt, long *blocknum, int *offset)
Definition: logtape.c:1171

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

Referenced by ExecSortMarkPos().

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2602 of file tuplesort.c.

2603 {
2604  int mOrder;
2605 
2606  /*----------
2607  * In the merge phase, we need buffer space for each input and output tape.
2608  * Each pass in the balanced merge algorithm reads from M input tapes, and
2609  * writes to N output tapes. Each tape consumes TAPE_BUFFER_OVERHEAD bytes
2610  * of memory. In addition to that, we want MERGE_BUFFER_SIZE workspace per
2611  * input tape.
2612  *
2613  * totalMem = M * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE) +
2614  * N * TAPE_BUFFER_OVERHEAD
2615  *
2616  * Except for the last and next-to-last merge passes, where there can be
2617  * fewer tapes left to process, M = N. We choose M so that we have the
2618  * desired amount of memory available for the input buffers
2619  * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE), given the total memory
2620  * available for the tape buffers (allowedMem).
2621  *
2622  * Note: you might be thinking we need to account for the memtuples[]
2623  * array in this calculation, but we effectively treat that as part of the
2624  * MERGE_BUFFER_SIZE workspace.
2625  *----------
2626  */
2627  mOrder = allowedMem /
2629 
2630  /*
2631  * Even in minimum memory, use at least a MINORDER merge. On the other
2632  * hand, even when we have lots of memory, do not use more than a MAXORDER
2633  * merge. Tapes are pretty cheap, but they're not entirely free. Each
2634  * additional tape reduces the amount of memory available to build runs,
2635  * which in turn can cause the same sort to need more runs, which makes
2636  * merging slower even if it can still be done in a single pass. Also,
2637  * high order merges are quite slow due to CPU cache effects; it can be
2638  * faster to pay the I/O cost of a multi-pass merge than to perform a
2639  * single merge pass across many hundreds of tapes.
2640  */
2641  mOrder = Max(mOrder, MINORDER);
2642  mOrder = Min(mOrder, MAXORDER);
2643 
2644  return mOrder;
2645 }
#define Min(x, y)
Definition: c.h:986
#define Max(x, y)
Definition: c.h:980
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:236
#define MAXORDER
Definition: tuplesort.c:235
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:237
#define MINORDER
Definition: tuplesort.c:234

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

Referenced by cost_tuplesort(), and inittapes().

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

Definition at line 3367 of file tuplesort.c.

3368 {
3369  switch (m)
3370  {
3372  return "still in progress";
3374  return "top-N heapsort";
3375  case SORT_TYPE_QUICKSORT:
3376  return "quicksort";
3378  return "external sort";
3380  return "external merge";
3381  }
3382 
3383  return "unknown";
3384 }

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

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

Definition at line 2043 of file tuplesort.c.

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

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

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

◆ tuplesort_putdatum()

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

Definition at line 1808 of file tuplesort.c.

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

References consider_abort_common(), SortTuple::datum1, datumCopy(), DatumGetPointer, GetMemoryChunkSpace(), i, SortTuple::isnull1, MemoryContextSwitchTo(), PointerGetDatum, puttuple_common(), SortTuple::tuple, USEMEM, and val.

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

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 1709 of file tuplesort.c.

1710 {
1711  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1712  SortTuple stup;
1713 
1714  /*
1715  * Copy the given tuple into memory we control, and decrease availMem.
1716  * Then call the common code.
1717  */
1718  COPYTUP(state, &stup, (void *) tup);
1719 
1720  puttuple_common(state, &stup);
1721 
1722  MemoryContextSwitchTo(oldcontext);
1723 }
#define COPYTUP(state, stup, tup)
Definition: tuplesort.c:541

References COPYTUP, MemoryContextSwitchTo(), and puttuple_common().

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_putindextuplevalues()

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

Definition at line 1730 of file tuplesort.c.

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

References consider_abort_common(), SortTuple::datum1, GetMemoryChunkSpace(), i, index_form_tuple(), index_getattr, SortTuple::isnull1, MemoryContextSwitchTo(), puttuple_common(), RelationGetDescr, IndexTupleData::t_tid, SortTuple::tuple, USEMEM, and values.

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

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

Definition at line 1687 of file tuplesort.c.

1688 {
1689  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1690  SortTuple stup;
1691 
1692  /*
1693  * Copy the given tuple into memory we control, and decrease availMem.
1694  * Then call the common code.
1695  */
1696  COPYTUP(state, &stup, (void *) slot);
1697 
1698  puttuple_common(state, &stup);
1699 
1700  MemoryContextSwitchTo(oldcontext);
1701 }

References COPYTUP, MemoryContextSwitchTo(), and puttuple_common().

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

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

Definition at line 3226 of file tuplesort.c.

3227 {
3228  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3229 
3230  Assert(state->randomAccess);
3231 
3232  switch (state->status)
3233  {
3234  case TSS_SORTEDINMEM:
3235  state->current = 0;
3236  state->eof_reached = false;
3237  state->markpos_offset = 0;
3238  state->markpos_eof = false;
3239  break;
3240  case TSS_SORTEDONTAPE:
3241  LogicalTapeRewindForRead(state->result_tape, 0);
3242  state->eof_reached = false;
3243  state->markpos_block = 0L;
3244  state->markpos_offset = 0;
3245  state->markpos_eof = false;
3246  break;
3247  default:
3248  elog(ERROR, "invalid tuplesort state");
3249  break;
3250  }
3251 
3252  MemoryContextSwitchTo(oldcontext);
3253 }
void LogicalTapeRewindForRead(LogicalTape *lt, size_t buffer_size)
Definition: logtape.c:855

References Assert(), elog, ERROR, LogicalTapeRewindForRead(), MemoryContextSwitchTo(), 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().

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate state)

Definition at line 1535 of file tuplesort.c.

1536 {
1539 
1540  /*
1541  * After we've freed up per-batch memory, re-setup all of the state common
1542  * to both the first batch and any subsequent batch.
1543  */
1545 
1546  state->lastReturnedTuple = NULL;
1547  state->slabMemoryBegin = NULL;
1548  state->slabMemoryEnd = NULL;
1549  state->slabFreeHead = NULL;
1550 }
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:832

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

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

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

Definition at line 3290 of file tuplesort.c.

3291 {
3292  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3293 
3294  Assert(state->randomAccess);
3295 
3296  switch (state->status)
3297  {
3298  case TSS_SORTEDINMEM:
3299  state->current = state->markpos_offset;
3300  state->eof_reached = state->markpos_eof;
3301  break;
3302  case TSS_SORTEDONTAPE:
3303  LogicalTapeSeek(state->result_tape,
3304  state->markpos_block,
3305  state->markpos_offset);
3306  state->eof_reached = state->markpos_eof;
3307  break;
3308  default:
3309  elog(ERROR, "invalid tuplesort state");
3310  break;
3311  }
3312 
3313  MemoryContextSwitchTo(oldcontext);
3314 }
void LogicalTapeSeek(LogicalTape *lt, long blocknum, int offset)
Definition: logtape.c:1142

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

Referenced by ExecSortRestrPos().

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

Definition at line 1333 of file tuplesort.c.

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

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

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

◆ tuplesort_skiptuples()

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

Definition at line 2534 of file tuplesort.c.

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 }
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:120

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

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

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType  t)

Definition at line 3390 of file tuplesort.c.

3391 {
3393  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
3394 }

References Assert(), SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate state)

Definition at line 1379 of file tuplesort.c.

1380 {
1381  return state->boundUsed;
1382 }

Referenced by ExecIncrementalSort().