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
 

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, SORT_TYPE_QUICKSORT, SORT_TYPE_EXTERNAL_SORT,
  SORT_TYPE_EXTERNAL_MERGE
}
 
enum  TuplesortSpaceType { SORT_SPACE_TYPE_DISK, SORT_SPACE_TYPE_MEMORY }
 

Functions

Tuplesortstatetuplesort_begin_heap (TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, bool randomAccess)
 
Tuplesortstatetuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, bool randomAccess)
 
Tuplesortstatetuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, SortCoordinate coordinate, bool randomAccess)
 
Tuplesortstatetuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, bool randomAccess)
 
Tuplesortstatetuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, bool randomAccess)
 
void tuplesort_set_bound (Tuplesortstate *state, int64 bound)
 
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_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)
 

Typedef Documentation

◆ 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 65 of file tuplesort.h.

◆ TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK 
SORT_SPACE_TYPE_MEMORY 

Definition at line 74 of file tuplesort.h.

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 4414 of file tuplesort.c.

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

4415 {
4416  /* Attach to SharedFileSet */
4417  SharedFileSetAttach(&shared->fileset, seg);
4418 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:78
SharedFileSet fileset
Definition: tuplesort.c:488

◆ tuplesort_begin_cluster()

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

Definition at line 880 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, 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::sortcontext, Tuplesortstate::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TTSOpsVirtual, Tuplesortstate::tupDesc, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_cluster().

Referenced by heapam_relation_copy_for_cluster().

884 {
885  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
886  randomAccess);
887  BTScanInsert indexScanKey;
888  MemoryContext oldcontext;
889  int i;
890 
891  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
892 
893  oldcontext = MemoryContextSwitchTo(state->sortcontext);
894 
895 #ifdef TRACE_SORT
896  if (trace_sort)
897  elog(LOG,
898  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
900  workMem, randomAccess ? 't' : 'f');
901 #endif
902 
903  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
904 
905  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
906  false, /* no unique check */
907  state->nKeys,
908  workMem,
909  randomAccess,
910  PARALLEL_SORT(state));
911 
913  state->copytup = copytup_cluster;
914  state->writetup = writetup_cluster;
915  state->readtup = readtup_cluster;
916  state->abbrevNext = 10;
917 
918  state->indexInfo = BuildIndexInfo(indexRel);
919 
920  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
921 
922  indexScanKey = _bt_mkscankey(indexRel, NULL);
923 
924  if (state->indexInfo->ii_Expressions != NULL)
925  {
926  TupleTableSlot *slot;
927  ExprContext *econtext;
928 
929  /*
930  * We will need to use FormIndexDatum to evaluate the index
931  * expressions. To do that, we need an EState, as well as a
932  * TupleTableSlot to put the table tuples into. The econtext's
933  * scantuple has to point to that slot, too.
934  */
935  state->estate = CreateExecutorState();
936  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsVirtual);
937  econtext = GetPerTupleExprContext(state->estate);
938  econtext->ecxt_scantuple = slot;
939  }
940 
941  /* Prepare SortSupport data for each column */
942  state->sortKeys = (SortSupport) palloc0(state->nKeys *
943  sizeof(SortSupportData));
944 
945  for (i = 0; i < state->nKeys; i++)
946  {
947  SortSupport sortKey = state->sortKeys + i;
948  ScanKey scanKey = indexScanKey->scankeys + i;
949  int16 strategy;
950 
951  sortKey->ssup_cxt = CurrentMemoryContext;
952  sortKey->ssup_collation = scanKey->sk_collation;
953  sortKey->ssup_nulls_first =
954  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
955  sortKey->ssup_attno = scanKey->sk_attno;
956  /* Convey if abbreviation optimization is applicable in principle */
957  sortKey->abbreviate = (i == 0);
958 
959  AssertState(sortKey->ssup_attno != 0);
960 
961  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
963 
964  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
965  }
966 
967  pfree(indexScanKey);
968 
969  MemoryContextSwitchTo(oldcontext);
970 
971  return state;
972 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:345
bool ssup_nulls_first
Definition: sortsupport.h:75
static void writetup_cluster(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:3892
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:735
int64 abbrevNext
Definition: tuplesort.c:426
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:85
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1203
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:422
EState * estate
Definition: tuplesort.c:434
SortSupport sortKeys
Definition: tuplesort.c:412
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:265
const TupleTableSlotOps TTSOpsVirtual
Definition: execTuples.c:84
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:257
#define CLUSTER_SORT
Definition: tuplesort.c:122
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3708
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2230
#define LOG
Definition: elog.h:26
Form_pg_class rd_rel
Definition: rel.h:83
static void copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3819
bool trace_sort
Definition: tuplesort.c:130
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
#define GetPerTupleExprContext(estate)
Definition: executor.h:501
void pfree(void *pointer)
Definition: mcxt.c:1031
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3916
MemoryContext sortcontext
Definition: tuplesort.c:244
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:283
IndexInfo * indexInfo
Definition: tuplesort.c:433
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:435
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:161
EState * CreateExecutorState(void)
Definition: execUtils.c:88
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:681
void * palloc0(Size size)
Definition: mcxt.c:955
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:275
int sk_flags
Definition: skey.h:66
List * ii_Expressions
Definition: execnodes.h:160
#define Assert(condition)
Definition: c.h:732
#define SK_BT_DESC
Definition: nbtree.h:680
Definition: regguts.h:298
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:224
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:477
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
Oid sk_collation
Definition: skey.h:70
#define elog(elevel,...)
Definition: elog.h:226
int i
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67
TupleDesc tupDesc
Definition: tuplesort.c:411

◆ tuplesort_begin_datum()

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

Definition at line 1099 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, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::onlyKey, palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), Tuplesortstate::readtup, readtup_datum(), Tuplesortstate::sortcontext, 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().

1102 {
1103  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1104  randomAccess);
1105  MemoryContext oldcontext;
1106  int16 typlen;
1107  bool typbyval;
1108 
1109  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1110 
1111 #ifdef TRACE_SORT
1112  if (trace_sort)
1113  elog(LOG,
1114  "begin datum sort: workMem = %d, randomAccess = %c",
1115  workMem, randomAccess ? 't' : 'f');
1116 #endif
1117 
1118  state->nKeys = 1; /* always a one-column sort */
1119 
1120  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
1121  false, /* no unique check */
1122  1,
1123  workMem,
1124  randomAccess,
1125  PARALLEL_SORT(state));
1126 
1127  state->comparetup = comparetup_datum;
1128  state->copytup = copytup_datum;
1129  state->writetup = writetup_datum;
1130  state->readtup = readtup_datum;
1131  state->abbrevNext = 10;
1132 
1133  state->datumType = datumType;
1134 
1135  /* lookup necessary attributes of the datum type */
1136  get_typlenbyval(datumType, &typlen, &typbyval);
1137  state->datumTypeLen = typlen;
1138  state->tuples = !typbyval;
1139 
1140  /* Prepare SortSupport data */
1141  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1142 
1144  state->sortKeys->ssup_collation = sortCollation;
1145  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1146 
1147  /*
1148  * Abbreviation is possible here only for by-reference types. In theory,
1149  * a pass-by-value datatype could have an abbreviated form that is cheaper
1150  * to compare. In a tuple sort, we could support that, because we can
1151  * always extract the original datum from the tuple as needed. Here, we
1152  * can't, because a datum sort only stores a single copy of the datum; the
1153  * "tuple" field of each SortTuple is NULL.
1154  */
1155  state->sortKeys->abbreviate = !typbyval;
1156 
1157  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1158 
1159  /*
1160  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1161  * tie-breaker comparisons may be required. Typically, the optimization
1162  * is only of value to pass-by-value types anyway, whereas abbreviated
1163  * keys are typically only of value to pass-by-reference types.
1164  */
1165  if (!state->sortKeys->abbrev_converter)
1166  state->onlyKey = state->sortKeys;
1167 
1168  MemoryContextSwitchTo(oldcontext);
1169 
1170  return state;
1171 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:345
bool ssup_nulls_first
Definition: sortsupport.h:75
int64 abbrevNext
Definition: tuplesort.c:426
SortSupport sortKeys
Definition: tuplesort.c:412
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:265
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:257
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
#define DATUM_SORT
Definition: tuplesort.c:121
MemoryContext sortcontext
Definition: tuplesort.c:244
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4254
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:283
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4275
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4323
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:4282
void * palloc0(Size size)
Definition: mcxt.c:955
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:275
Definition: regguts.h:298
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2029
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
#define elog(elevel,...)
Definition: elog.h:226
SortSupport onlyKey
Definition: tuplesort.c:418

◆ 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 806 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, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::onlyKey, palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), Tuplesortstate::readtup, readtup_heap(), Tuplesortstate::sortcontext, 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 ExecSort(), initialize_aggregate(), initialize_phase(), and ordered_set_startup().

811 {
812  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
813  randomAccess);
814  MemoryContext oldcontext;
815  int i;
816 
817  oldcontext = MemoryContextSwitchTo(state->sortcontext);
818 
819  AssertArg(nkeys > 0);
820 
821 #ifdef TRACE_SORT
822  if (trace_sort)
823  elog(LOG,
824  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
825  nkeys, workMem, randomAccess ? 't' : 'f');
826 #endif
827 
828  state->nKeys = nkeys;
829 
830  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
831  false, /* no unique check */
832  nkeys,
833  workMem,
834  randomAccess,
835  PARALLEL_SORT(state));
836 
837  state->comparetup = comparetup_heap;
838  state->copytup = copytup_heap;
839  state->writetup = writetup_heap;
840  state->readtup = readtup_heap;
841 
842  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
843  state->abbrevNext = 10;
844 
845  /* Prepare SortSupport data for each column */
846  state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
847 
848  for (i = 0; i < nkeys; i++)
849  {
850  SortSupport sortKey = state->sortKeys + i;
851 
852  AssertArg(attNums[i] != 0);
853  AssertArg(sortOperators[i] != 0);
854 
855  sortKey->ssup_cxt = CurrentMemoryContext;
856  sortKey->ssup_collation = sortCollations[i];
857  sortKey->ssup_nulls_first = nullsFirstFlags[i];
858  sortKey->ssup_attno = attNums[i];
859  /* Convey if abbreviation optimization is applicable in principle */
860  sortKey->abbreviate = (i == 0);
861 
862  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
863  }
864 
865  /*
866  * The "onlyKey" optimization cannot be used with abbreviated keys, since
867  * tie-breaker comparisons may be required. Typically, the optimization
868  * is only of value to pass-by-value types anyway, whereas abbreviated
869  * keys are typically only of value to pass-by-reference types.
870  */
871  if (nkeys == 1 && !state->sortKeys->abbrev_converter)
872  state->onlyKey = state->sortKeys;
873 
874  MemoryContextSwitchTo(oldcontext);
875 
876  return state;
877 }
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:3509
int64 abbrevNext
Definition: tuplesort.c:426
SortSupport sortKeys
Definition: tuplesort.c:412
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:265
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:257
#define LOG
Definition: elog.h:26
#define HEAP_SORT
Definition: tuplesort.c:119
bool trace_sort
Definition: tuplesort.c:130
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
MemoryContext sortcontext
Definition: tuplesort.c:244
static void writetup_heap(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:3649
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:283
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define AssertArg(condition)
Definition: c.h:734
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3571
void * palloc0(Size size)
Definition: mcxt.c:955
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:275
Definition: regguts.h:298
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3676
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
#define elog(elevel,...)
Definition: elog.h:226
int i
SortSupport onlyKey
Definition: tuplesort.c:418
TupleDesc tupDesc
Definition: tuplesort.c:411

◆ tuplesort_begin_index_btree()

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

Definition at line 975 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, 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::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 _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

981 {
982  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
983  randomAccess);
984  BTScanInsert indexScanKey;
985  MemoryContext oldcontext;
986  int i;
987 
988  oldcontext = MemoryContextSwitchTo(state->sortcontext);
989 
990 #ifdef TRACE_SORT
991  if (trace_sort)
992  elog(LOG,
993  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
994  enforceUnique ? 't' : 'f',
995  workMem, randomAccess ? 't' : 'f');
996 #endif
997 
998  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
999 
1000  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
1001  enforceUnique,
1002  state->nKeys,
1003  workMem,
1004  randomAccess,
1005  PARALLEL_SORT(state));
1006 
1008  state->copytup = copytup_index;
1009  state->writetup = writetup_index;
1010  state->readtup = readtup_index;
1011  state->abbrevNext = 10;
1012 
1013  state->heapRel = heapRel;
1014  state->indexRel = indexRel;
1015  state->enforceUnique = enforceUnique;
1016 
1017  indexScanKey = _bt_mkscankey(indexRel, NULL);
1018 
1019  /* Prepare SortSupport data for each column */
1020  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1021  sizeof(SortSupportData));
1022 
1023  for (i = 0; i < state->nKeys; i++)
1024  {
1025  SortSupport sortKey = state->sortKeys + i;
1026  ScanKey scanKey = indexScanKey->scankeys + i;
1027  int16 strategy;
1028 
1029  sortKey->ssup_cxt = CurrentMemoryContext;
1030  sortKey->ssup_collation = scanKey->sk_collation;
1031  sortKey->ssup_nulls_first =
1032  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1033  sortKey->ssup_attno = scanKey->sk_attno;
1034  /* Convey if abbreviation optimization is applicable in principle */
1035  sortKey->abbreviate = (i == 0);
1036 
1037  AssertState(sortKey->ssup_attno != 0);
1038 
1039  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1041 
1042  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1043  }
1044 
1045  pfree(indexScanKey);
1046 
1047  MemoryContextSwitchTo(oldcontext);
1048 
1049  return state;
1050 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:345
bool ssup_nulls_first
Definition: sortsupport.h:75
Relation heapRel
Definition: tuplesort.c:440
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:735
int64 abbrevNext
Definition: tuplesort.c:426
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:85
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4142
SortSupport sortKeys
Definition: tuplesort.c:412
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:265
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:257
#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:3954
bool trace_sort
Definition: tuplesort.c:130
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
void pfree(void *pointer)
Definition: mcxt.c:1031
MemoryContext sortcontext
Definition: tuplesort.c:244
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4208
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:283
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4230
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:435
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:161
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:681
void * palloc0(Size size)
Definition: mcxt.c:955
Relation indexRel
Definition: tuplesort.c:441
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:275
int sk_flags
Definition: skey.h:66
#define SK_BT_DESC
Definition: nbtree.h:680
Definition: regguts.h:298
bool enforceUnique
Definition: tuplesort.c:444
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:477
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
Oid sk_collation
Definition: skey.h:70
#define elog(elevel,...)
Definition: elog.h:226
int i
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67

◆ tuplesort_begin_index_hash()

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

Definition at line 1053 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::max_buckets, MemoryContextSwitchTo(), Tuplesortstate::nKeys, Tuplesortstate::readtup, readtup_index(), Tuplesortstate::sortcontext, trace_sort, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_index().

Referenced by _h_spoolinit().

1061 {
1062  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1063  randomAccess);
1064  MemoryContext oldcontext;
1065 
1066  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1067 
1068 #ifdef TRACE_SORT
1069  if (trace_sort)
1070  elog(LOG,
1071  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
1072  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
1073  high_mask,
1074  low_mask,
1075  max_buckets,
1076  workMem, randomAccess ? 't' : 'f');
1077 #endif
1078 
1079  state->nKeys = 1; /* Only one sort column, the hash code */
1080 
1082  state->copytup = copytup_index;
1083  state->writetup = writetup_index;
1084  state->readtup = readtup_index;
1085 
1086  state->heapRel = heapRel;
1087  state->indexRel = indexRel;
1088 
1089  state->high_mask = high_mask;
1090  state->low_mask = low_mask;
1091  state->max_buckets = max_buckets;
1092 
1093  MemoryContextSwitchTo(oldcontext);
1094 
1095  return state;
1096 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4087
Relation heapRel
Definition: tuplesort.c:440
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4142
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:265
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:257
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
MemoryContext sortcontext
Definition: tuplesort.c:244
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4208
uint32 high_mask
Definition: tuplesort.c:447
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:283
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4230
Relation indexRel
Definition: tuplesort.c:441
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:275
Definition: regguts.h:298
uint32 max_buckets
Definition: tuplesort.c:449
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
#define elog(elevel,...)
Definition: elog.h:226
uint32 low_mask
Definition: tuplesort.c:448

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1236 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, ExprContext::ecxt_scantuple, elog, Tuplesortstate::estate, ExecDropSingleTupleTableSlot(), FreeExecutorState(), GetPerTupleExprContext, LOG, LogicalTapeSetBlocks(), LogicalTapeSetClose(), MemoryContextDelete(), MemoryContextSwitchTo(), pg_rusage_show(), Tuplesortstate::ru_start, SERIAL, Tuplesortstate::sortcontext, Tuplesortstate::tapeset, trace_sort, and Tuplesortstate::worker.

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

1237 {
1238  /* context swap probably not needed, but let's be safe */
1239  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1240 
1241 #ifdef TRACE_SORT
1242  long spaceUsed;
1243 
1244  if (state->tapeset)
1245  spaceUsed = LogicalTapeSetBlocks(state->tapeset);
1246  else
1247  spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
1248 #endif
1249 
1250  /*
1251  * Delete temporary "tape" files, if any.
1252  *
1253  * Note: want to include this in reported total cost of sort, hence need
1254  * for two #ifdef TRACE_SORT sections.
1255  */
1256  if (state->tapeset)
1257  LogicalTapeSetClose(state->tapeset);
1258 
1259 #ifdef TRACE_SORT
1260  if (trace_sort)
1261  {
1262  if (state->tapeset)
1263  elog(LOG, "%s of worker %d ended, %ld disk blocks used: %s",
1264  SERIAL(state) ? "external sort" : "parallel external sort",
1265  state->worker, spaceUsed, pg_rusage_show(&state->ru_start));
1266  else
1267  elog(LOG, "%s of worker %d ended, %ld KB used: %s",
1268  SERIAL(state) ? "internal sort" : "unperformed parallel sort",
1269  state->worker, spaceUsed, pg_rusage_show(&state->ru_start));
1270  }
1271 
1272  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
1273 #else
1274 
1275  /*
1276  * If you disabled TRACE_SORT, you can still probe sort__done, but you
1277  * ain't getting space-used stats.
1278  */
1279  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, 0L);
1280 #endif
1281 
1282  /* Free any execution state created for CLUSTER case */
1283  if (state->estate != NULL)
1284  {
1285  ExprContext *econtext = GetPerTupleExprContext(state->estate);
1286 
1288  FreeExecutorState(state->estate);
1289  }
1290 
1291  MemoryContextSwitchTo(oldcontext);
1292 
1293  /*
1294  * Free the per-sort memory context, thereby releasing all working memory,
1295  * including the Tuplesortstate struct itself.
1296  */
1298 }
int64 availMem
Definition: tuplesort.c:240
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
PGRUsage ru_start
Definition: tuplesort.c:463
#define SERIAL(state)
Definition: tuplesort.c:530
EState * estate
Definition: tuplesort.c:434
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
void FreeExecutorState(EState *estate)
Definition: execUtils.c:190
#define GetPerTupleExprContext(estate)
Definition: executor.h:501
MemoryContext sortcontext
Definition: tuplesort.c:244
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1219
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
int64 allowedMem
Definition: tuplesort.c:241
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:224
#define elog(elevel,...)
Definition: elog.h:226
void LogicalTapeSetClose(LogicalTapeSet *lts)
Definition: logtape.c:584
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:1082

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nworkers)

Definition at line 4370 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

4371 {
4372  Size tapesSize;
4373 
4374  Assert(nWorkers > 0);
4375 
4376  /* Make sure that BufFile shared state is MAXALIGN'd */
4377  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4378  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4379 
4380  return tapesSize;
4381 }
Size mul_size(Size s1, Size s2)
Definition: shmem.c:492
Size add_size(Size s1, Size s2)
Definition: shmem.c:475
#define Assert(condition)
Definition: c.h:732
size_t Size
Definition: c.h:466
#define MAXALIGN(LEN)
Definition: c.h:685
#define offsetof(type, field)
Definition: c.h:655

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 3129 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, Tuplesortstate::boundUsed, LogicalTapeSetBlocks(), 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, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_FINALMERGE, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

Referenced by ExecSort(), and show_sort_info().

3131 {
3132  /*
3133  * Note: it might seem we should provide both memory and disk usage for a
3134  * disk-based sort. However, the current code doesn't track memory space
3135  * accurately once we have begun to return tuples to the caller (since we
3136  * don't account for pfree's the caller is expected to do), so we cannot
3137  * rely on availMem in a disk sort. This does not seem worth the overhead
3138  * to fix. Is it worth creating an API for the memory context code to
3139  * tell us how much is actually used in sortcontext?
3140  */
3141  if (state->tapeset)
3142  {
3144  stats->spaceUsed = LogicalTapeSetBlocks(state->tapeset) * (BLCKSZ / 1024);
3145  }
3146  else
3147  {
3149  stats->spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
3150  }
3151 
3152  switch (state->status)
3153  {
3154  case TSS_SORTEDINMEM:
3155  if (state->boundUsed)
3157  else
3159  break;
3160  case TSS_SORTEDONTAPE:
3162  break;
3163  case TSS_FINALMERGE:
3165  break;
3166  default:
3168  break;
3169  }
3170 }
int64 availMem
Definition: tuplesort.c:240
TupSortStatus status
Definition: tuplesort.c:232
TuplesortMethod sortMethod
Definition: tuplesort.h:82
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
int64 allowedMem
Definition: tuplesort.c:241
TuplesortSpaceType spaceType
Definition: tuplesort.h:83
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:1082

◆ tuplesort_getdatum()

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

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

2247 {
2248  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2249  SortTuple stup;
2250 
2251  if (!tuplesort_gettuple_common(state, forward, &stup))
2252  {
2253  MemoryContextSwitchTo(oldcontext);
2254  return false;
2255  }
2256 
2257  /* Ensure we copy into caller's memory context */
2258  MemoryContextSwitchTo(oldcontext);
2259 
2260  /* Record abbreviated key for caller */
2261  if (state->sortKeys->abbrev_converter && abbrev)
2262  *abbrev = stup.datum1;
2263 
2264  if (stup.isnull1 || !state->tuples)
2265  {
2266  *val = stup.datum1;
2267  *isNull = stup.isnull1;
2268  }
2269  else
2270  {
2271  /* use stup.tuple because stup.datum1 may be an abbreviation */
2272  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2273  *isNull = false;
2274  }
2275 
2276  return true;
2277 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:412
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:170
bool isnull1
Definition: tuplesort.c:171
void * tuple
Definition: tuplesort.c:169
MemoryContext sortcontext
Definition: tuplesort.c:244
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:1902
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:130
long val
Definition: informix.c:684

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2196 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

2197 {
2198  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2199  SortTuple stup;
2200 
2201  if (!tuplesort_gettuple_common(state, forward, &stup))
2202  stup.tuple = NULL;
2203 
2204  MemoryContextSwitchTo(oldcontext);
2205 
2206  return stup.tuple;
2207 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:169
MemoryContext sortcontext
Definition: tuplesort.c:244
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1902

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2216 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

2217 {
2218  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2219  SortTuple stup;
2220 
2221  if (!tuplesort_gettuple_common(state, forward, &stup))
2222  stup.tuple = NULL;
2223 
2224  MemoryContextSwitchTo(oldcontext);
2225 
2226  return (IndexTuple) stup.tuple;
2227 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:169
MemoryContext sortcontext
Definition: tuplesort.c:244
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1902

◆ tuplesort_gettupleslot()

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

Definition at line 2159 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 ExecSort(), fetch_input_tuple(), hypothetical_dense_rank_final(), hypothetical_rank_common(), and process_ordered_aggregate_multi().

2161 {
2162  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2163  SortTuple stup;
2164 
2165  if (!tuplesort_gettuple_common(state, forward, &stup))
2166  stup.tuple = NULL;
2167 
2168  MemoryContextSwitchTo(oldcontext);
2169 
2170  if (stup.tuple)
2171  {
2172  /* Record abbreviated key for caller */
2173  if (state->sortKeys->abbrev_converter && abbrev)
2174  *abbrev = stup.datum1;
2175 
2176  if (copy)
2178 
2179  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
2180  return true;
2181  }
2182  else
2183  {
2184  ExecClearTuple(slot);
2185  return false;
2186  }
2187 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1411
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:426
SortSupport sortKeys
Definition: tuplesort.c:412
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:170
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1439
void * tuple
Definition: tuplesort.c:169
MemoryContext sortcontext
Definition: tuplesort.c:244
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:1902

◆ tuplesort_initialize_shared()

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

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

4392 {
4393  int i;
4394 
4395  Assert(nWorkers > 0);
4396 
4397  SpinLockInit(&shared->mutex);
4398  shared->currentWorker = 0;
4399  shared->workersFinished = 0;
4400  SharedFileSetInit(&shared->fileset, seg);
4401  shared->nTapes = nWorkers;
4402  for (i = 0; i < nWorkers; i++)
4403  {
4404  shared->tapes[i].firstblocknumber = 0L;
4405  }
4406 }
slock_t mutex
Definition: tuplesort.c:474
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:49
#define SpinLockInit(lock)
Definition: spin.h:60
long firstblocknumber
Definition: logtape.h:50
int workersFinished
Definition: tuplesort.c:485
int nTapes
Definition: tuplesort.c:491
#define Assert(condition)
Definition: c.h:732
int i
int currentWorker
Definition: tuplesort.c:484
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:497
SharedFileSet fileset
Definition: tuplesort.c:488

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

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

3064 {
3065  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3066 
3067  Assert(state->randomAccess);
3068 
3069  switch (state->status)
3070  {
3071  case TSS_SORTEDINMEM:
3072  state->markpos_offset = state->current;
3073  state->markpos_eof = state->eof_reached;
3074  break;
3075  case TSS_SORTEDONTAPE:
3076  LogicalTapeTell(state->tapeset,
3077  state->result_tape,
3078  &state->markpos_block,
3079  &state->markpos_offset);
3080  state->markpos_eof = state->eof_reached;
3081  break;
3082  default:
3083  elog(ERROR, "invalid tuplesort state");
3084  break;
3085  }
3086 
3087  MemoryContextSwitchTo(oldcontext);
3088 }
TupSortStatus status
Definition: tuplesort.c:232
bool randomAccess
Definition: tuplesort.c:234
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:384
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:244
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
void LogicalTapeTell(LogicalTapeSet *lts, int tapenum, long *blocknum, int *offset)
Definition: logtape.c:1062
#define Assert(condition)
Definition: c.h:732
long markpos_block
Definition: tuplesort.c:383
bool eof_reached
Definition: tuplesort.c:380
bool markpos_eof
Definition: tuplesort.c:385
#define elog(elevel,...)
Definition: elog.h:226

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2353 of file tuplesort.c.

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

Referenced by cost_sort(), and inittapes().

2354 {
2355  int mOrder;
2356 
2357  /*
2358  * We need one tape for each merge input, plus another one for the output,
2359  * and each of these tapes needs buffer space. In addition we want
2360  * MERGE_BUFFER_SIZE workspace per input tape (but the output tape doesn't
2361  * count).
2362  *
2363  * Note: you might be thinking we need to account for the memtuples[]
2364  * array in this calculation, but we effectively treat that as part of the
2365  * MERGE_BUFFER_SIZE workspace.
2366  */
2367  mOrder = (allowedMem - TAPE_BUFFER_OVERHEAD) /
2369 
2370  /*
2371  * Even in minimum memory, use at least a MINORDER merge. On the other
2372  * hand, even when we have lots of memory, do not use more than a MAXORDER
2373  * merge. Tapes are pretty cheap, but they're not entirely free. Each
2374  * additional tape reduces the amount of memory available to build runs,
2375  * which in turn can cause the same sort to need more runs, which makes
2376  * merging slower even if it can still be done in a single pass. Also,
2377  * high order merges are quite slow due to CPU cache effects; it can be
2378  * faster to pay the I/O cost of a polyphase merge than to perform a
2379  * single merge pass across many hundreds of tapes.
2380  */
2381  mOrder = Max(mOrder, MINORDER);
2382  mOrder = Min(mOrder, MAXORDER);
2383 
2384  return mOrder;
2385 }
#define Min(x, y)
Definition: c.h:904
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:221
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:222
#define MINORDER
Definition: tuplesort.c:219
#define Max(x, y)
Definition: c.h:898
#define MAXORDER
Definition: tuplesort.c:220

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

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

3177 {
3178  switch (m)
3179  {
3181  return "still in progress";
3183  return "top-N heapsort";
3184  case SORT_TYPE_QUICKSORT:
3185  return "quicksort";
3187  return "external sort";
3189  return "external merge";
3190  }
3191 
3192  return "unknown";
3193 }

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

Definition at line 1791 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(), ExecSort(), heapam_relation_copy_for_cluster(), hypothetical_dense_rank_final(), hypothetical_rank_common(), initialize_phase(), mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), percentile_disc_multi_final(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), and validate_index().

1792 {
1793  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1794 
1795 #ifdef TRACE_SORT
1796  if (trace_sort)
1797  elog(LOG, "performsort of worker %d starting: %s",
1798  state->worker, pg_rusage_show(&state->ru_start));
1799 #endif
1800 
1801  switch (state->status)
1802  {
1803  case TSS_INITIAL:
1804 
1805  /*
1806  * We were able to accumulate all the tuples within the allowed
1807  * amount of memory, or leader to take over worker tapes
1808  */
1809  if (SERIAL(state))
1810  {
1811  /* Just qsort 'em and we're done */
1812  tuplesort_sort_memtuples(state);
1813  state->status = TSS_SORTEDINMEM;
1814  }
1815  else if (WORKER(state))
1816  {
1817  /*
1818  * Parallel workers must still dump out tuples to tape. No
1819  * merge is required to produce single output run, though.
1820  */
1821  inittapes(state, false);
1822  dumptuples(state, true);
1823  worker_nomergeruns(state);
1824  state->status = TSS_SORTEDONTAPE;
1825  }
1826  else
1827  {
1828  /*
1829  * Leader will take over worker tapes and merge worker runs.
1830  * Note that mergeruns sets the correct state->status.
1831  */
1832  leader_takeover_tapes(state);
1833  mergeruns(state);
1834  }
1835  state->current = 0;
1836  state->eof_reached = false;
1837  state->markpos_block = 0L;
1838  state->markpos_offset = 0;
1839  state->markpos_eof = false;
1840  break;
1841 
1842  case TSS_BOUNDED:
1843 
1844  /*
1845  * We were able to accumulate all the tuples required for output
1846  * in memory, using a heap to eliminate excess tuples. Now we
1847  * have to transform the heap to a properly-sorted array.
1848  */
1849  sort_bounded_heap(state);
1850  state->current = 0;
1851  state->eof_reached = false;
1852  state->markpos_offset = 0;
1853  state->markpos_eof = false;
1854  state->status = TSS_SORTEDINMEM;
1855  break;
1856 
1857  case TSS_BUILDRUNS:
1858 
1859  /*
1860  * Finish tape-based sort. First, flush all tuples remaining in
1861  * memory out to tape; then merge until we have a single remaining
1862  * run (or, if !randomAccess and !WORKER(), one run per tape).
1863  * Note that mergeruns sets the correct state->status.
1864  */
1865  dumptuples(state, true);
1866  mergeruns(state);
1867  state->eof_reached = false;
1868  state->markpos_block = 0L;
1869  state->markpos_offset = 0;
1870  state->markpos_eof = false;
1871  break;
1872 
1873  default:
1874  elog(ERROR, "invalid tuplesort state");
1875  break;
1876  }
1877 
1878 #ifdef TRACE_SORT
1879  if (trace_sort)
1880  {
1881  if (state->status == TSS_FINALMERGE)
1882  elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
1883  state->worker, state->activeTapes,
1884  pg_rusage_show(&state->ru_start));
1885  else
1886  elog(LOG, "performsort of worker %d done: %s",
1887  state->worker, pg_rusage_show(&state->ru_start));
1888  }
1889 #endif
1890 
1891  MemoryContextSwitchTo(oldcontext);
1892 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2925
TupSortStatus status
Definition: tuplesort.c:232
PGRUsage ru_start
Definition: tuplesort.c:463
#define SERIAL(state)
Definition: tuplesort.c:530
static void sort_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3269
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:2393
#define LOG
Definition: elog.h:26
int markpos_offset
Definition: tuplesort.c:384
bool trace_sort
Definition: tuplesort.c:130
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2562
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:244
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define WORKER(state)
Definition: tuplesort.c:531
long markpos_block
Definition: tuplesort.c:383
bool eof_reached
Definition: tuplesort.c:380
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3309
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:4521
bool markpos_eof
Definition: tuplesort.c:385
#define elog(elevel,...)
Definition: elog.h:226
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:4500

◆ tuplesort_putdatum()

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

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

1557 {
1558  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1559  SortTuple stup;
1560 
1561  /*
1562  * Pass-by-value types or null values are just stored directly in
1563  * stup.datum1 (and stup.tuple is not used and set to NULL).
1564  *
1565  * Non-null pass-by-reference values need to be copied into memory we
1566  * control, and possibly abbreviated. The copied value is pointed to by
1567  * stup.tuple and is treated as the canonical copy (e.g. to return via
1568  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
1569  * abbreviated value if abbreviation is happening, otherwise it's
1570  * identical to stup.tuple.
1571  */
1572 
1573  if (isNull || !state->tuples)
1574  {
1575  /*
1576  * Set datum1 to zeroed representation for NULLs (to be consistent,
1577  * and to support cheap inequality tests for NULL abbreviated keys).
1578  */
1579  stup.datum1 = !isNull ? val : (Datum) 0;
1580  stup.isnull1 = isNull;
1581  stup.tuple = NULL; /* no separate storage */
1583  }
1584  else
1585  {
1586  Datum original = datumCopy(val, false, state->datumTypeLen);
1587 
1588  stup.isnull1 = false;
1589  stup.tuple = DatumGetPointer(original);
1590  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1592 
1593  if (!state->sortKeys->abbrev_converter)
1594  {
1595  stup.datum1 = original;
1596  }
1597  else if (!consider_abort_common(state))
1598  {
1599  /* Store abbreviated key representation */
1600  stup.datum1 = state->sortKeys->abbrev_converter(original,
1601  state->sortKeys);
1602  }
1603  else
1604  {
1605  /* Abort abbreviation */
1606  int i;
1607 
1608  stup.datum1 = original;
1609 
1610  /*
1611  * Set state to be consistent with never trying abbreviation.
1612  *
1613  * Alter datum1 representation in already-copied tuples, so as to
1614  * ensure a consistent representation (current tuple was just
1615  * handled). It does not matter if some dumped tuples are already
1616  * sorted on tape, since serialized tuples lack abbreviated keys
1617  * (TSS_BUILDRUNS state prevents control reaching here in any
1618  * case).
1619  */
1620  for (i = 0; i < state->memtupcount; i++)
1621  {
1622  SortTuple *mtup = &state->memtuples[i];
1623 
1624  mtup->datum1 = PointerGetDatum(mtup->tuple);
1625  }
1626  }
1627  }
1628 
1629  puttuple_common(state, &stup);
1630 
1631  MemoryContextSwitchTo(oldcontext);
1632 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:412
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:170
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:171
void * tuple
Definition: tuplesort.c:169
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1747
MemoryContext sortcontext
Definition: tuplesort.c:244
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:130
uintptr_t Datum
Definition: postgres.h:367
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1638
#define DatumGetPointer(X)
Definition: postgres.h:549
MemoryContext tuplecontext
Definition: tuplesort.c:245
#define USEMEM(state, amt)
Definition: tuplesort.c:528
int i
long val
Definition: informix.c:684
SortTuple * memtuples
Definition: tuplesort.c:293

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 1457 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

1458 {
1459  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1460  SortTuple stup;
1461 
1462  /*
1463  * Copy the given tuple into memory we control, and decrease availMem.
1464  * Then call the common code.
1465  */
1466  COPYTUP(state, &stup, (void *) tup);
1467 
1468  puttuple_common(state, &stup);
1469 
1470  MemoryContextSwitchTo(oldcontext);
1471 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
MemoryContext sortcontext
Definition: tuplesort.c:244
#define COPYTUP(state, stup, tup)
Definition: tuplesort.c:524
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1638

◆ tuplesort_putindextuplevalues()

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

Definition at line 1478 of file tuplesort.c.

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

Referenced by _bt_spool(), and _h_spool().

1481 {
1482  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1483  SortTuple stup;
1484  Datum original;
1485  IndexTuple tuple;
1486 
1487  stup.tuple = index_form_tuple(RelationGetDescr(rel), values, isnull);
1488  tuple = ((IndexTuple) stup.tuple);
1489  tuple->t_tid = *self;
1490  USEMEM(state, GetMemoryChunkSpace(stup.tuple));
1491  /* set up first-column key value */
1492  original = index_getattr(tuple,
1493  1,
1494  RelationGetDescr(state->indexRel),
1495  &stup.isnull1);
1496 
1498 
1499  if (!state->sortKeys || !state->sortKeys->abbrev_converter || stup.isnull1)
1500  {
1501  /*
1502  * Store ordinary Datum representation, or NULL value. If there is a
1503  * converter it won't expect NULL values, and cost model is not
1504  * required to account for NULL, so in that case we avoid calling
1505  * converter and just set datum1 to zeroed representation (to be
1506  * consistent, and to support cheap inequality tests for NULL
1507  * abbreviated keys).
1508  */
1509  stup.datum1 = original;
1510  }
1511  else if (!consider_abort_common(state))
1512  {
1513  /* Store abbreviated key representation */
1514  stup.datum1 = state->sortKeys->abbrev_converter(original,
1515  state->sortKeys);
1516  }
1517  else
1518  {
1519  /* Abort abbreviation */
1520  int i;
1521 
1522  stup.datum1 = original;
1523 
1524  /*
1525  * Set state to be consistent with never trying abbreviation.
1526  *
1527  * Alter datum1 representation in already-copied tuples, so as to
1528  * ensure a consistent representation (current tuple was just
1529  * handled). It does not matter if some dumped tuples are already
1530  * sorted on tape, since serialized tuples lack abbreviated keys
1531  * (TSS_BUILDRUNS state prevents control reaching here in any case).
1532  */
1533  for (i = 0; i < state->memtupcount; i++)
1534  {
1535  SortTuple *mtup = &state->memtuples[i];
1536 
1537  tuple = mtup->tuple;
1538  mtup->datum1 = index_getattr(tuple,
1539  1,
1540  RelationGetDescr(state->indexRel),
1541  &mtup->isnull1);
1542  }
1543  }
1544 
1545  puttuple_common(state, &stup);
1546 
1547  MemoryContextSwitchTo(oldcontext);
1548 }
#define RelationGetDescr(relation)
Definition: rel.h:442
SortSupport sortKeys
Definition: tuplesort.c:412
ItemPointerData t_tid
Definition: itup.h:37
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:170
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:171
IndexTuple index_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:47
void * tuple
Definition: tuplesort.c:169
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1747
MemoryContext sortcontext
Definition: tuplesort.c:244
IndexTupleData * IndexTuple
Definition: itup.h:53
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
Relation indexRel
Definition: tuplesort.c:441
uintptr_t Datum
Definition: postgres.h:367
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1638
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static Datum values[MAXATTR]
Definition: bootstrap.c:167
MemoryContext tuplecontext
Definition: tuplesort.c:245
#define USEMEM(state, amt)
Definition: tuplesort.c:528
int i
SortTuple * memtuples
Definition: tuplesort.c:293

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

Definition at line 1435 of file tuplesort.c.

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

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

1436 {
1437  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1438  SortTuple stup;
1439 
1440  /*
1441  * Copy the given tuple into memory we control, and decrease availMem.
1442  * Then call the common code.
1443  */
1444  COPYTUP(state, &stup, (void *) slot);
1445 
1446  puttuple_common(state, &stup);
1447 
1448  MemoryContextSwitchTo(oldcontext);
1449 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
MemoryContext sortcontext
Definition: tuplesort.c:244
#define COPYTUP(state, stup, tup)
Definition: tuplesort.c:524
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:1638

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

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

3029 {
3030  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3031 
3032  Assert(state->randomAccess);
3033 
3034  switch (state->status)
3035  {
3036  case TSS_SORTEDINMEM:
3037  state->current = 0;
3038  state->eof_reached = false;
3039  state->markpos_offset = 0;
3040  state->markpos_eof = false;
3041  break;
3042  case TSS_SORTEDONTAPE:
3044  state->result_tape,
3045  0);
3046  state->eof_reached = false;
3047  state->markpos_block = 0L;
3048  state->markpos_offset = 0;
3049  state->markpos_eof = false;
3050  break;
3051  default:
3052  elog(ERROR, "invalid tuplesort state");
3053  break;
3054  }
3055 
3056  MemoryContextSwitchTo(oldcontext);
3057 }
TupSortStatus status
Definition: tuplesort.c:232
bool randomAccess
Definition: tuplesort.c:234
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:384
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:244
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
#define Assert(condition)
Definition: c.h:732
long markpos_block
Definition: tuplesort.c:383
bool eof_reached
Definition: tuplesort.c:380
void LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Definition: logtape.c:709
bool markpos_eof
Definition: tuplesort.c:385
#define elog(elevel,...)
Definition: elog.h:226

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

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

3096 {
3097  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3098 
3099  Assert(state->randomAccess);
3100 
3101  switch (state->status)
3102  {
3103  case TSS_SORTEDINMEM:
3104  state->current = state->markpos_offset;
3105  state->eof_reached = state->markpos_eof;
3106  break;
3107  case TSS_SORTEDONTAPE:
3108  LogicalTapeSeek(state->tapeset,
3109  state->result_tape,
3110  state->markpos_block,
3111  state->markpos_offset);
3112  state->eof_reached = state->markpos_eof;
3113  break;
3114  default:
3115  elog(ERROR, "invalid tuplesort state");
3116  break;
3117  }
3118 
3119  MemoryContextSwitchTo(oldcontext);
3120 }
TupSortStatus status
Definition: tuplesort.c:232
bool randomAccess
Definition: tuplesort.c:234
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:384
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:244
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
#define Assert(condition)
Definition: c.h:732
long markpos_block
Definition: tuplesort.c:383
bool eof_reached
Definition: tuplesort.c:380
bool markpos_eof
Definition: tuplesort.c:385
#define elog(elevel,...)
Definition: elog.h:226
void LogicalTapeSeek(LogicalTapeSet *lts, int tapenum, long blocknum, int offset)
Definition: logtape.c:1031

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

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

1187 {
1188  /* Assert we're called before loading any tuples */
1189  Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
1190  /* Can't set the bound twice, either */
1191  Assert(!state->bounded);
1192  /* Also, this shouldn't be called in a parallel worker */
1193  Assert(!WORKER(state));
1194 
1195  /* Parallel leader allows but ignores hint */
1196  if (LEADER(state))
1197  return;
1198 
1199 #ifdef DEBUG_BOUNDED_SORT
1200  /* Honor GUC setting that disables the feature (for easy testing) */
1201  if (!optimize_bounded_sort)
1202  return;
1203 #endif
1204 
1205  /* We want to be able to compute bound * 2, so limit the setting */
1206  if (bound > (int64) (INT_MAX / 2))
1207  return;
1208 
1209  state->bounded = true;
1210  state->bound = (int) bound;
1211 
1212  /*
1213  * Bounded sorts are not an effective target for abbreviated key
1214  * optimization. Disable by setting state to be consistent with no
1215  * abbreviation support.
1216  */
1217  state->sortKeys->abbrev_converter = NULL;
1218  if (state->sortKeys->abbrev_full_comparator)
1220 
1221  /* Not strictly necessary, but be tidy */
1222  state->sortKeys->abbrev_abort = NULL;
1223  state->sortKeys->abbrev_full_comparator = NULL;
1224 }
TupSortStatus status
Definition: tuplesort.c:232
SortSupport sortKeys
Definition: tuplesort.c:412
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:532
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define WORKER(state)
Definition: tuplesort.c:531
#define Assert(condition)
Definition: c.h:732
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 2285 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().

2286 {
2287  MemoryContext oldcontext;
2288 
2289  /*
2290  * We don't actually support backwards skip yet, because no callers need
2291  * it. The API is designed to allow for that later, though.
2292  */
2293  Assert(forward);
2294  Assert(ntuples >= 0);
2295  Assert(!WORKER(state));
2296 
2297  switch (state->status)
2298  {
2299  case TSS_SORTEDINMEM:
2300  if (state->memtupcount - state->current >= ntuples)
2301  {
2302  state->current += ntuples;
2303  return true;
2304  }
2305  state->current = state->memtupcount;
2306  state->eof_reached = true;
2307 
2308  /*
2309  * Complain if caller tries to retrieve more tuples than
2310  * originally asked for in a bounded sort. This is because
2311  * returning EOF here might be the wrong thing.
2312  */
2313  if (state->bounded && state->current >= state->bound)
2314  elog(ERROR, "retrieved too many tuples in a bounded sort");
2315 
2316  return false;
2317 
2318  case TSS_SORTEDONTAPE:
2319  case TSS_FINALMERGE:
2320 
2321  /*
2322  * We could probably optimize these cases better, but for now it's
2323  * not worth the trouble.
2324  */
2325  oldcontext = MemoryContextSwitchTo(state->sortcontext);
2326  while (ntuples-- > 0)
2327  {
2328  SortTuple stup;
2329 
2330  if (!tuplesort_gettuple_common(state, forward, &stup))
2331  {
2332  MemoryContextSwitchTo(oldcontext);
2333  return false;
2334  }
2336  }
2337  MemoryContextSwitchTo(oldcontext);
2338  return true;
2339 
2340  default:
2341  elog(ERROR, "invalid tuplesort state");
2342  return false; /* keep compiler quiet */
2343  }
2344 }
TupSortStatus status
Definition: tuplesort.c:232
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:244
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1902
#define WORKER(state)
Definition: tuplesort.c:531
#define Assert(condition)
Definition: c.h:732
bool eof_reached
Definition: tuplesort.c:380
#define elog(elevel,...)
Definition: elog.h:226
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType  t)

Definition at line 3199 of file tuplesort.c.

References Assert, SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_sort_info().

3200 {
3202  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
3203 }
#define Assert(condition)
Definition: c.h:732