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

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

4583 {
4584  /* Attach to SharedFileSet */
4585  SharedFileSetAttach(&shared->fileset, seg);
4586 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
SharedFileSet fileset
Definition: tuplesort.c:506

◆ tuplesort_begin_cluster()

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

Definition at line 952 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

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

◆ tuplesort_begin_datum()

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

Definition at line 1228 of file tuplesort.c.

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

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

1231 {
1232  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1233  randomAccess);
1234  MemoryContext oldcontext;
1235  int16 typlen;
1236  bool typbyval;
1237 
1238  oldcontext = MemoryContextSwitchTo(state->maincontext);
1239 
1240 #ifdef TRACE_SORT
1241  if (trace_sort)
1242  elog(LOG,
1243  "begin datum sort: workMem = %d, randomAccess = %c",
1244  workMem, randomAccess ? 't' : 'f');
1245 #endif
1246 
1247  state->nKeys = 1; /* always a one-column sort */
1248 
1249  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
1250  false, /* no unique check */
1251  1,
1252  workMem,
1253  randomAccess,
1254  PARALLEL_SORT(state));
1255 
1256  state->comparetup = comparetup_datum;
1257  state->copytup = copytup_datum;
1258  state->writetup = writetup_datum;
1259  state->readtup = readtup_datum;
1260  state->abbrevNext = 10;
1261 
1262  state->datumType = datumType;
1263 
1264  /* lookup necessary attributes of the datum type */
1265  get_typlenbyval(datumType, &typlen, &typbyval);
1266  state->datumTypeLen = typlen;
1267  state->tuples = !typbyval;
1268 
1269  /* Prepare SortSupport data */
1270  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1271 
1273  state->sortKeys->ssup_collation = sortCollation;
1274  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1275 
1276  /*
1277  * Abbreviation is possible here only for by-reference types. In theory,
1278  * a pass-by-value datatype could have an abbreviated form that is cheaper
1279  * to compare. In a tuple sort, we could support that, because we can
1280  * always extract the original datum from the tuple as needed. Here, we
1281  * can't, because a datum sort only stores a single copy of the datum; the
1282  * "tuple" field of each SortTuple is NULL.
1283  */
1284  state->sortKeys->abbreviate = !typbyval;
1285 
1286  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1287 
1288  /*
1289  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1290  * tie-breaker comparisons may be required. Typically, the optimization
1291  * is only of value to pass-by-value types anyway, whereas abbreviated
1292  * keys are typically only of value to pass-by-reference types.
1293  */
1294  if (!state->sortKeys->abbrev_converter)
1295  state->onlyKey = state->sortKeys;
1296 
1297  MemoryContextSwitchTo(oldcontext);
1298 
1299  return state;
1300 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:361
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:4422
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:4443
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4491
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
static void writetup_datum(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4450
void * palloc0(Size size)
Definition: mcxt.c:981
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:298
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2139
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
#define elog(elevel,...)
Definition: elog.h:214
SortSupport onlyKey
Definition: tuplesort.c:436

◆ tuplesort_begin_heap()

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

Definition at line 878 of file tuplesort.c.

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

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

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

◆ tuplesort_begin_index_btree()

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

Definition at line 1047 of file tuplesort.c.

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

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

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

◆ tuplesort_begin_index_gist()

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

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

1176 {
1177  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1178  randomAccess);
1179  MemoryContext oldcontext;
1180  int i;
1181 
1182  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1183 
1184 #ifdef TRACE_SORT
1185  if (trace_sort)
1186  elog(LOG,
1187  "begin index sort: workMem = %d, randomAccess = %c",
1188  workMem, randomAccess ? 't' : 'f');
1189 #endif
1190 
1191  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1192 
1194  state->copytup = copytup_index;
1195  state->writetup = writetup_index;
1196  state->readtup = readtup_index;
1197 
1198  state->heapRel = heapRel;
1199  state->indexRel = indexRel;
1200 
1201  /* Prepare SortSupport data for each column */
1202  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1203  sizeof(SortSupportData));
1204 
1205  for (i = 0; i < state->nKeys; i++)
1206  {
1207  SortSupport sortKey = state->sortKeys + i;
1208 
1209  sortKey->ssup_cxt = CurrentMemoryContext;
1210  sortKey->ssup_collation = indexRel->rd_indcollation[i];
1211  sortKey->ssup_nulls_first = false;
1212  sortKey->ssup_attno = i + 1;
1213  /* Convey if abbreviation optimization is applicable in principle */
1214  sortKey->abbreviate = (i == 0);
1215 
1216  AssertState(sortKey->ssup_attno != 0);
1217 
1218  /* Look for a sort support function */
1219  PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
1220  }
1221 
1222  MemoryContextSwitchTo(oldcontext);
1223 
1224  return state;
1225 }
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:748
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4369
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:4181
bool trace_sort
Definition: tuplesort.c:140
Oid * rd_indcollation
Definition: rel.h:199
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:4376
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:4398
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:475
void * palloc0(Size size)
Definition: mcxt.c:981
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:298
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
#define elog(elevel,...)
Definition: elog.h:214
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 1125 of file tuplesort.c.

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

Referenced by _h_spoolinit().

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

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

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

1446 {
1447  tuplesort_free(state);
1448 
1449  /*
1450  * Free the main memory context, including the Tuplesortstate struct
1451  * itself.
1452  */
1454 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:212
MemoryContext maincontext
Definition: tuplesort.c:260
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1372

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nworkers)

Definition at line 4538 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

4539 {
4540  Size tapesSize;
4541 
4542  Assert(nWorkers > 0);
4543 
4544  /* Make sure that BufFile shared state is MAXALIGN'd */
4545  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4546  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4547 
4548  return tapesSize;
4549 }
Size mul_size(Size s1, Size s2)
Definition: shmem.c:515
Size add_size(Size s1, Size s2)
Definition: shmem.c:498
#define Assert(condition)
Definition: c.h:745
size_t Size
Definition: c.h:473
#define MAXALIGN(LEN)
Definition: c.h:698
#define offsetof(type, field)
Definition: c.h:668

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

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

3361 {
3362  /*
3363  * Note: it might seem we should provide both memory and disk usage for a
3364  * disk-based sort. However, the current code doesn't track memory space
3365  * accurately once we have begun to return tuples to the caller (since we
3366  * don't account for pfree's the caller is expected to do), so we cannot
3367  * rely on availMem in a disk sort. This does not seem worth the overhead
3368  * to fix. Is it worth creating an API for the memory context code to
3369  * tell us how much is actually used in sortcontext?
3370  */
3371  tuplesort_updatemax(state);
3372 
3373  if (state->isMaxSpaceDisk)
3375  else
3377  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
3378 
3379  switch (state->maxSpaceStatus)
3380  {
3381  case TSS_SORTEDINMEM:
3382  if (state->boundUsed)
3384  else
3386  break;
3387  case TSS_SORTEDONTAPE:
3389  break;
3390  case TSS_FINALMERGE:
3392  break;
3393  default:
3395  break;
3396  }
3397 }
bool isMaxSpaceDisk
Definition: tuplesort.c:256
int64 maxSpace
Definition: tuplesort.c:254
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1462
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 2475 of file tuplesort.c.

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

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

2477 {
2478  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2479  SortTuple stup;
2480 
2481  if (!tuplesort_gettuple_common(state, forward, &stup))
2482  {
2483  MemoryContextSwitchTo(oldcontext);
2484  return false;
2485  }
2486 
2487  /* Ensure we copy into caller's memory context */
2488  MemoryContextSwitchTo(oldcontext);
2489 
2490  /* Record abbreviated key for caller */
2491  if (state->sortKeys->abbrev_converter && abbrev)
2492  *abbrev = stup.datum1;
2493 
2494  if (stup.isnull1 || !state->tuples)
2495  {
2496  *val = stup.datum1;
2497  *isNull = stup.isnull1;
2498  }
2499  else
2500  {
2501  /* use stup.tuple because stup.datum1 may be an abbreviation */
2502  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2503  *isNull = false;
2504  }
2505 
2506  return true;
2507 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2132
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 2426 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

2427 {
2428  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2429  SortTuple stup;
2430 
2431  if (!tuplesort_gettuple_common(state, forward, &stup))
2432  stup.tuple = NULL;
2433 
2434  MemoryContextSwitchTo(oldcontext);
2435 
2436  return stup.tuple;
2437 }
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:2132

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2446 of file tuplesort.c.

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

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

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

◆ tuplesort_gettupleslot()

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

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

2391 {
2392  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2393  SortTuple stup;
2394 
2395  if (!tuplesort_gettuple_common(state, forward, &stup))
2396  stup.tuple = NULL;
2397 
2398  MemoryContextSwitchTo(oldcontext);
2399 
2400  if (stup.tuple)
2401  {
2402  /* Record abbreviated key for caller */
2403  if (state->sortKeys->abbrev_converter && abbrev)
2404  *abbrev = stup.datum1;
2405 
2406  if (copy)
2408 
2409  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
2410  return true;
2411  }
2412  else
2413  {
2414  ExecClearTuple(slot);
2415  return false;
2416  }
2417 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1416
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:425
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1439
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2132

◆ tuplesort_initialize_shared()

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

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

4560 {
4561  int i;
4562 
4563  Assert(nWorkers > 0);
4564 
4565  SpinLockInit(&shared->mutex);
4566  shared->currentWorker = 0;
4567  shared->workersFinished = 0;
4568  SharedFileSetInit(&shared->fileset, seg);
4569  shared->nTapes = nWorkers;
4570  for (i = 0; i < nWorkers; i++)
4571  {
4572  shared->tapes[i].firstblocknumber = 0L;
4573  }
4574 }
slock_t mutex
Definition: tuplesort.c:492
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:64
#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:745
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 3293 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().

3294 {
3295  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3296 
3297  Assert(state->randomAccess);
3298 
3299  switch (state->status)
3300  {
3301  case TSS_SORTEDINMEM:
3302  state->markpos_offset = state->current;
3303  state->markpos_eof = state->eof_reached;
3304  break;
3305  case TSS_SORTEDONTAPE:
3306  LogicalTapeTell(state->tapeset,
3307  state->result_tape,
3308  &state->markpos_block,
3309  &state->markpos_offset);
3310  state->markpos_eof = state->eof_reached;
3311  break;
3312  default:
3313  elog(ERROR, "invalid tuplesort state");
3314  break;
3315  }
3316 
3317  MemoryContextSwitchTo(oldcontext);
3318 }
TupSortStatus status
Definition: tuplesort.c:242
bool randomAccess
Definition: tuplesort.c:244
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:402
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
void LogicalTapeTell(LogicalTapeSet *lts, int tapenum, long *blocknum, int *offset)
Definition: logtape.c:1245
#define Assert(condition)
Definition: c.h:745
long markpos_block
Definition: tuplesort.c:401
bool eof_reached
Definition: tuplesort.c:398
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:214

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2583 of file tuplesort.c.

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

Referenced by cost_tuplesort(), and inittapes().

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

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

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

3404 {
3405  switch (m)
3406  {
3408  return "still in progress";
3410  return "top-N heapsort";
3411  case SORT_TYPE_QUICKSORT:
3412  return "quicksort";
3414  return "external sort";
3416  return "external merge";
3417  }
3418 
3419  return "unknown";
3420 }

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

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

2022 {
2023  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2024 
2025 #ifdef TRACE_SORT
2026  if (trace_sort)
2027  elog(LOG, "performsort of worker %d starting: %s",
2028  state->worker, pg_rusage_show(&state->ru_start));
2029 #endif
2030 
2031  switch (state->status)
2032  {
2033  case TSS_INITIAL:
2034 
2035  /*
2036  * We were able to accumulate all the tuples within the allowed
2037  * amount of memory, or leader to take over worker tapes
2038  */
2039  if (SERIAL(state))
2040  {
2041  /* Just qsort 'em and we're done */
2042  tuplesort_sort_memtuples(state);
2043  state->status = TSS_SORTEDINMEM;
2044  }
2045  else if (WORKER(state))
2046  {
2047  /*
2048  * Parallel workers must still dump out tuples to tape. No
2049  * merge is required to produce single output run, though.
2050  */
2051  inittapes(state, false);
2052  dumptuples(state, true);
2053  worker_nomergeruns(state);
2054  state->status = TSS_SORTEDONTAPE;
2055  }
2056  else
2057  {
2058  /*
2059  * Leader will take over worker tapes and merge worker runs.
2060  * Note that mergeruns sets the correct state->status.
2061  */
2062  leader_takeover_tapes(state);
2063  mergeruns(state);
2064  }
2065  state->current = 0;
2066  state->eof_reached = false;
2067  state->markpos_block = 0L;
2068  state->markpos_offset = 0;
2069  state->markpos_eof = false;
2070  break;
2071 
2072  case TSS_BOUNDED:
2073 
2074  /*
2075  * We were able to accumulate all the tuples required for output
2076  * in memory, using a heap to eliminate excess tuples. Now we
2077  * have to transform the heap to a properly-sorted array.
2078  */
2079  sort_bounded_heap(state);
2080  state->current = 0;
2081  state->eof_reached = false;
2082  state->markpos_offset = 0;
2083  state->markpos_eof = false;
2084  state->status = TSS_SORTEDINMEM;
2085  break;
2086 
2087  case TSS_BUILDRUNS:
2088 
2089  /*
2090  * Finish tape-based sort. First, flush all tuples remaining in
2091  * memory out to tape; then merge until we have a single remaining
2092  * run (or, if !randomAccess and !WORKER(), one run per tape).
2093  * Note that mergeruns sets the correct state->status.
2094  */
2095  dumptuples(state, true);
2096  mergeruns(state);
2097  state->eof_reached = false;
2098  state->markpos_block = 0L;
2099  state->markpos_offset = 0;
2100  state->markpos_eof = false;
2101  break;
2102 
2103  default:
2104  elog(ERROR, "invalid tuplesort state");
2105  break;
2106  }
2107 
2108 #ifdef TRACE_SORT
2109  if (trace_sort)
2110  {
2111  if (state->status == TSS_FINALMERGE)
2112  elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
2113  state->worker, state->activeTapes,
2114  pg_rusage_show(&state->ru_start));
2115  else
2116  elog(LOG, "performsort of worker %d done: %s",
2117  state->worker, pg_rusage_show(&state->ru_start));
2118  }
2119 #endif
2120 
2121  MemoryContextSwitchTo(oldcontext);
2122 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:3155
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:3496
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:2623
#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:2792
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define WORKER(state)
Definition: tuplesort.c:549
long markpos_block
Definition: tuplesort.c:401
bool eof_reached
Definition: tuplesort.c:398
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3536
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:4689
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:214
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:4668

◆ tuplesort_putdatum()

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

Definition at line 1786 of file tuplesort.c.

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

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

1787 {
1788  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1789  SortTuple stup;
1790 
1791  /*
1792  * Pass-by-value types or null values are just stored directly in
1793  * stup.datum1 (and stup.tuple is not used and set to NULL).
1794  *
1795  * Non-null pass-by-reference values need to be copied into memory we
1796  * control, and possibly abbreviated. The copied value is pointed to by
1797  * stup.tuple and is treated as the canonical copy (e.g. to return via
1798  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
1799  * abbreviated value if abbreviation is happening, otherwise it's
1800  * identical to stup.tuple.
1801  */
1802 
1803  if (isNull || !state->tuples)
1804  {
1805  /*
1806  * Set datum1 to zeroed representation for NULLs (to be consistent,
1807  * and to support cheap inequality tests for NULL abbreviated keys).
1808  */
1809  stup.datum1 = !isNull ? val : (Datum) 0;
1810  stup.isnull1 = isNull;
1811  stup.tuple = NULL; /* no separate storage */
1813  }
1814  else
1815  {
1816  Datum original = datumCopy(val, false, state->datumTypeLen);
1817 
1818  stup.isnull1 = false;
1819  stup.tuple = DatumGetPointer(original);
1820  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1822 
1823  if (!state->sortKeys->abbrev_converter)
1824  {
1825  stup.datum1 = original;
1826  }
1827  else if (!consider_abort_common(state))
1828  {
1829  /* Store abbreviated key representation */
1830  stup.datum1 = state->sortKeys->abbrev_converter(original,
1831  state->sortKeys);
1832  }
1833  else
1834  {
1835  /* Abort abbreviation */
1836  int i;
1837 
1838  stup.datum1 = original;
1839 
1840  /*
1841  * Set state to be consistent with never trying abbreviation.
1842  *
1843  * Alter datum1 representation in already-copied tuples, so as to
1844  * ensure a consistent representation (current tuple was just
1845  * handled). It does not matter if some dumped tuples are already
1846  * sorted on tape, since serialized tuples lack abbreviated keys
1847  * (TSS_BUILDRUNS state prevents control reaching here in any
1848  * case).
1849  */
1850  for (i = 0; i < state->memtupcount; i++)
1851  {
1852  SortTuple *mtup = &state->memtuples[i];
1853 
1854  mtup->datum1 = PointerGetDatum(mtup->tuple);
1855  }
1856  }
1857  }
1858 
1859  puttuple_common(state, &stup);
1860 
1861  MemoryContextSwitchTo(oldcontext);
1862 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:428
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1977
MemoryContext sortcontext
Definition: tuplesort.c:262
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:131
uintptr_t Datum
Definition: postgres.h:367
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1868
#define DatumGetPointer(X)
Definition: postgres.h:549
MemoryContext tuplecontext
Definition: tuplesort.c:263
#define USEMEM(state, amt)
Definition: tuplesort.c:546
int i
long val
Definition: informix.c:664
SortTuple * memtuples
Definition: tuplesort.c:311

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 1687 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

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 *) tup);
1697 
1698  puttuple_common(state, &stup);
1699 
1700  MemoryContextSwitchTo(oldcontext);
1701 }
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:1868

◆ tuplesort_putindextuplevalues()

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

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

1711 {
1712  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1713  SortTuple stup;
1714  Datum original;
1715  IndexTuple tuple;
1716 
1717  stup.tuple = index_form_tuple(RelationGetDescr(rel), values, isnull);
1718  tuple = ((IndexTuple) stup.tuple);
1719  tuple->t_tid = *self;
1720  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1721  /* set up first-column key value */
1722  original = index_getattr(tuple,
1723  1,
1724  RelationGetDescr(state->indexRel),
1725  &stup.isnull1);
1726 
1728 
1729  if (!state->sortKeys || !state->sortKeys->abbrev_converter || stup.isnull1)
1730  {
1731  /*
1732  * Store ordinary Datum representation, or NULL value. If there is a
1733  * converter it won't expect NULL values, and cost model is not
1734  * required to account for NULL, so in that case we avoid calling
1735  * converter and just set datum1 to zeroed representation (to be
1736  * consistent, and to support cheap inequality tests for NULL
1737  * abbreviated keys).
1738  */
1739  stup.datum1 = original;
1740  }
1741  else if (!consider_abort_common(state))
1742  {
1743  /* Store abbreviated key representation */
1744  stup.datum1 = state->sortKeys->abbrev_converter(original,
1745  state->sortKeys);
1746  }
1747  else
1748  {
1749  /* Abort abbreviation */
1750  int i;
1751 
1752  stup.datum1 = original;
1753 
1754  /*
1755  * Set state to be consistent with never trying abbreviation.
1756  *
1757  * Alter datum1 representation in already-copied tuples, so as to
1758  * ensure a consistent representation (current tuple was just
1759  * handled). It does not matter if some dumped tuples are already
1760  * sorted on tape, since serialized tuples lack abbreviated keys
1761  * (TSS_BUILDRUNS state prevents control reaching here in any case).
1762  */
1763  for (i = 0; i < state->memtupcount; i++)
1764  {
1765  SortTuple *mtup = &state->memtuples[i];
1766 
1767  tuple = mtup->tuple;
1768  mtup->datum1 = index_getattr(tuple,
1769  1,
1770  RelationGetDescr(state->indexRel),
1771  &mtup->isnull1);
1772  }
1773  }
1774 
1775  puttuple_common(state, &stup);
1776 
1777  MemoryContextSwitchTo(oldcontext);
1778 }
#define RelationGetDescr(relation)
Definition: rel.h:482
SortSupport sortKeys
Definition: tuplesort.c:430
ItemPointerData t_tid
Definition: itup.h:37
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:428
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:1977
MemoryContext sortcontext
Definition: tuplesort.c:262
IndexTupleData * IndexTuple
Definition: itup.h:53
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
Relation indexRel
Definition: tuplesort.c:459
uintptr_t Datum
Definition: postgres.h:367
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1868
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static Datum values[MAXATTR]
Definition: bootstrap.c:165
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 1665 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().

1666 {
1667  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1668  SortTuple stup;
1669 
1670  /*
1671  * Copy the given tuple into memory we control, and decrease availMem.
1672  * Then call the common code.
1673  */
1674  COPYTUP(state, &stup, (void *) slot);
1675 
1676  puttuple_common(state, &stup);
1677 
1678  MemoryContextSwitchTo(oldcontext);
1679 }
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:1868

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

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

3259 {
3260  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3261 
3262  Assert(state->randomAccess);
3263 
3264  switch (state->status)
3265  {
3266  case TSS_SORTEDINMEM:
3267  state->current = 0;
3268  state->eof_reached = false;
3269  state->markpos_offset = 0;
3270  state->markpos_eof = false;
3271  break;
3272  case TSS_SORTEDONTAPE:
3274  state->result_tape,
3275  0);
3276  state->eof_reached = false;
3277  state->markpos_block = 0L;
3278  state->markpos_offset = 0;
3279  state->markpos_eof = false;
3280  break;
3281  default:
3282  elog(ERROR, "invalid tuplesort state");
3283  break;
3284  }
3285 
3286  MemoryContextSwitchTo(oldcontext);
3287 }
TupSortStatus status
Definition: tuplesort.c:242
bool randomAccess
Definition: tuplesort.c:244
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:402
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define Assert(condition)
Definition: c.h:745
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:214

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate state)

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

1514 {
1515  tuplesort_updatemax(state);
1516  tuplesort_free(state);
1517 
1518  /*
1519  * After we've freed up per-batch memory, re-setup all of the state common
1520  * to both the first batch and any subsequent batch.
1521  */
1522  tuplesort_begin_batch(state);
1523 
1524  state->lastReturnedTuple = NULL;
1525  state->slabMemoryBegin = NULL;
1526  state->slabMemoryEnd = NULL;
1527  state->slabFreeHead = NULL;
1528 }
char * slabMemoryEnd
Definition: tuplesort.c:346
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1462
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:814
void * lastReturnedTuple
Definition: tuplesort.c:358
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1372
char * slabMemoryBegin
Definition: tuplesort.c:345
SlabSlot * slabFreeHead
Definition: tuplesort.c:347

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

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

3326 {
3327  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3328 
3329  Assert(state->randomAccess);
3330 
3331  switch (state->status)
3332  {
3333  case TSS_SORTEDINMEM:
3334  state->current = state->markpos_offset;
3335  state->eof_reached = state->markpos_eof;
3336  break;
3337  case TSS_SORTEDONTAPE:
3338  LogicalTapeSeek(state->tapeset,
3339  state->result_tape,
3340  state->markpos_block,
3341  state->markpos_offset);
3342  state->eof_reached = state->markpos_eof;
3343  break;
3344  default:
3345  elog(ERROR, "invalid tuplesort state");
3346  break;
3347  }
3348 
3349  MemoryContextSwitchTo(oldcontext);
3350 }
TupSortStatus status
Definition: tuplesort.c:242
bool randomAccess
Definition: tuplesort.c:244
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:402
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define Assert(condition)
Definition: c.h:745
long markpos_block
Definition: tuplesort.c:401
bool eof_reached
Definition: tuplesort.c:398
bool markpos_eof
Definition: tuplesort.c:403
#define elog(elevel,...)
Definition: elog.h:214
void LogicalTapeSeek(LogicalTapeSet *lts, int tapenum, long blocknum, int offset)
Definition: logtape.c:1211

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

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

1316 {
1317  /* Assert we're called before loading any tuples */
1318  Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
1319  /* Can't set the bound twice, either */
1320  Assert(!state->bounded);
1321  /* Also, this shouldn't be called in a parallel worker */
1322  Assert(!WORKER(state));
1323 
1324  /* Parallel leader allows but ignores hint */
1325  if (LEADER(state))
1326  return;
1327 
1328 #ifdef DEBUG_BOUNDED_SORT
1329  /* Honor GUC setting that disables the feature (for easy testing) */
1330  if (!optimize_bounded_sort)
1331  return;
1332 #endif
1333 
1334  /* We want to be able to compute bound * 2, so limit the setting */
1335  if (bound > (int64) (INT_MAX / 2))
1336  return;
1337 
1338  state->bounded = true;
1339  state->bound = (int) bound;
1340 
1341  /*
1342  * Bounded sorts are not an effective target for abbreviated key
1343  * optimization. Disable by setting state to be consistent with no
1344  * abbreviation support.
1345  */
1346  state->sortKeys->abbrev_converter = NULL;
1347  if (state->sortKeys->abbrev_full_comparator)
1349 
1350  /* Not strictly necessary, but be tidy */
1351  state->sortKeys->abbrev_abort = NULL;
1352  state->sortKeys->abbrev_full_comparator = NULL;
1353 }
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:745
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 2515 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().

2516 {
2517  MemoryContext oldcontext;
2518 
2519  /*
2520  * We don't actually support backwards skip yet, because no callers need
2521  * it. The API is designed to allow for that later, though.
2522  */
2523  Assert(forward);
2524  Assert(ntuples >= 0);
2525  Assert(!WORKER(state));
2526 
2527  switch (state->status)
2528  {
2529  case TSS_SORTEDINMEM:
2530  if (state->memtupcount - state->current >= ntuples)
2531  {
2532  state->current += ntuples;
2533  return true;
2534  }
2535  state->current = state->memtupcount;
2536  state->eof_reached = true;
2537 
2538  /*
2539  * Complain if caller tries to retrieve more tuples than
2540  * originally asked for in a bounded sort. This is because
2541  * returning EOF here might be the wrong thing.
2542  */
2543  if (state->bounded && state->current >= state->bound)
2544  elog(ERROR, "retrieved too many tuples in a bounded sort");
2545 
2546  return false;
2547 
2548  case TSS_SORTEDONTAPE:
2549  case TSS_FINALMERGE:
2550 
2551  /*
2552  * We could probably optimize these cases better, but for now it's
2553  * not worth the trouble.
2554  */
2555  oldcontext = MemoryContextSwitchTo(state->sortcontext);
2556  while (ntuples-- > 0)
2557  {
2558  SortTuple stup;
2559 
2560  if (!tuplesort_gettuple_common(state, forward, &stup))
2561  {
2562  MemoryContextSwitchTo(oldcontext);
2563  return false;
2564  }
2566  }
2567  MemoryContextSwitchTo(oldcontext);
2568  return true;
2569 
2570  default:
2571  elog(ERROR, "invalid tuplesort state");
2572  return false; /* keep compiler quiet */
2573  }
2574 }
TupSortStatus status
Definition: tuplesort.c:242
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2132
#define WORKER(state)
Definition: tuplesort.c:549
#define Assert(condition)
Definition: c.h:745
bool eof_reached
Definition: tuplesort.c:398
#define elog(elevel,...)
Definition: elog.h:214
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType  t)

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

3427 {
3429  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
3430 }
#define Assert(condition)
Definition: c.h:745

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate state)

Definition at line 1361 of file tuplesort.c.

References Tuplesortstate::boundUsed.

Referenced by ExecIncrementalSort().

1362 {
1363  return state->boundUsed;
1364 }