PostgreSQL Source Code  git master
tuplesort.h File Reference
#include "access/itup.h"
#include "executor/tuptable.h"
#include "fmgr.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 36 of file tuplesort.h.

◆ SortCoordinate

Definition at line 59 of file tuplesort.h.

◆ SortCoordinateData

◆ TuplesortInstrumentation

◆ Tuplesortstate

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

◆ TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK 
SORT_SPACE_TYPE_MEMORY 

Definition at line 75 of file tuplesort.h.

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 4407 of file tuplesort.c.

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

4408 {
4409  /* Attach to SharedFileSet */
4410  SharedFileSetAttach(&shared->fileset, seg);
4411 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:76
SharedFileSet fileset
Definition: tuplesort.c:490

◆ 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_freeskey(), _bt_mkscankey_nodata(), 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, PrepareSortSupportFromIndexRel(), RelationData::rd_rel, Tuplesortstate::readtup, readtup_cluster(), RelationGetNumberOfAttributes, 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, Tuplesortstate::tupDesc, tuplesort_begin_common(), Tuplesortstate::writetup, and writetup_cluster().

Referenced by copy_heap_data().

884 {
885  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
886  randomAccess);
887  ScanKey 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_nodata(indexRel);
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);
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 + 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  _bt_freeskey(indexScanKey);
968 
969  MemoryContextSwitchTo(oldcontext);
970 
971  return state;
972 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:312
bool ssup_nulls_first
Definition: sortsupport.h:75
ScanKey _bt_mkscankey_nodata(Relation rel)
Definition: nbtutils.c:126
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:702
int64 abbrevNext
Definition: tuplesort.c:428
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:413
EState * estate
Definition: tuplesort.c:436
SortSupport sortKeys
Definition: tuplesort.c:414
void _bt_freeskey(ScanKey skey)
Definition: nbtutils.c:166
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:267
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:259
#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:1745
#define LOG
Definition: elog.h:26
Form_pg_class rd_rel
Definition: rel.h:84
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:489
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3916
MemoryContext sortcontext
Definition: tuplesort.c:246
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:285
IndexInfo * indexInfo
Definition: tuplesort.c:435
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:426
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc)
Definition: execTuples.c:232
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:160
EState * CreateExecutorState(void)
Definition: execUtils.c:80
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:490
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:277
int sk_flags
Definition: skey.h:66
List * ii_Expressions
Definition: execnodes.h:154
#define Assert(condition)
Definition: c.h:699
#define SK_BT_DESC
Definition: nbtree.h:489
Definition: regguts.h:298
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:218
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
Oid sk_collation
Definition: skey.h:70
int i
#define elog
Definition: elog.h:219
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67
TupleDesc tupDesc
Definition: tuplesort.c:413

◆ 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(), typbyval, typlen, 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 is 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:312
bool ssup_nulls_first
Definition: sortsupport.h:75
int16 typlen
Definition: pg_type.h:55
int64 abbrevNext
Definition: tuplesort.c:428
SortSupport sortKeys
Definition: tuplesort.c:414
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:267
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:133
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:259
#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:246
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4247
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:285
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4268
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4316
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
static void writetup_datum(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4275
void * palloc0(Size size)
Definition: mcxt.c:955
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:277
Definition: regguts.h:298
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2005
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
SortSupport onlyKey
Definition: tuplesort.c:420
#define elog
Definition: elog.h:219
bool typbyval
Definition: pg_type.h:65

◆ 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:428
SortSupport sortKeys
Definition: tuplesort.c:414
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:267
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:133
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:259
#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:246
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:285
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define AssertArg(condition)
Definition: c.h:701
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:277
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
int i
SortSupport onlyKey
Definition: tuplesort.c:420
#define elog
Definition: elog.h:219
TupleDesc tupDesc
Definition: tuplesort.c:413

◆ 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_freeskey(), _bt_mkscankey_nodata(), 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, PrepareSortSupportFromIndexRel(), Tuplesortstate::readtup, readtup_index(), 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  ScanKey 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_nodata(indexRel);
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 + 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  _bt_freeskey(indexScanKey);
1046 
1047  MemoryContextSwitchTo(oldcontext);
1048 
1049  return state;
1050 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:312
bool ssup_nulls_first
Definition: sortsupport.h:75
ScanKey _bt_mkscankey_nodata(Relation rel)
Definition: nbtutils.c:126
Relation heapRel
Definition: tuplesort.c:442
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:702
int64 abbrevNext
Definition: tuplesort.c:428
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4135
SortSupport sortKeys
Definition: tuplesort.c:414
void _bt_freeskey(ScanKey skey)
Definition: nbtutils.c:166
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:267
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:259
#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
MemoryContext sortcontext
Definition: tuplesort.c:246
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4201
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:285
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4223
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:426
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:160
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:490
void * palloc0(Size size)
Definition: mcxt.c:955
Relation indexRel
Definition: tuplesort.c:443
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:277
int sk_flags
Definition: skey.h:66
#define SK_BT_DESC
Definition: nbtree.h:489
Definition: regguts.h:298
bool enforceUnique
Definition: tuplesort.c:446
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
Oid sk_collation
Definition: skey.h:70
int i
#define elog
Definition: elog.h:219
#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:4083
Relation heapRel
Definition: tuplesort.c:442
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4135
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:267
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:259
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
MemoryContext sortcontext
Definition: tuplesort.c:246
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4201
uint32 high_mask
Definition: tuplesort.c:449
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:285
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4223
Relation indexRel
Definition: tuplesort.c:443
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:277
Definition: regguts.h:298
uint32 max_buckets
Definition: tuplesort.c:451
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:681
uint32 low_mask
Definition: tuplesort.c:450
#define elog
Definition: elog.h:219

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1235 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(), copy_heap_data(), ExecEndAgg(), ExecEndSort(), ExecReScanAgg(), ExecReScanSort(), initialize_aggregate(), initialize_phase(), ordered_set_shutdown(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), and validate_index().

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

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nworkers)

Definition at line 4363 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

4364 {
4365  Size tapesSize;
4366 
4367  Assert(nWorkers > 0);
4368 
4369  /* Make sure that BufFile shared state is MAXALIGN'd */
4370  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4371  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4372 
4373  return tapesSize;
4374 }
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:699
size_t Size
Definition: c.h:433
#define MAXALIGN(LEN)
Definition: c.h:652
#define offsetof(type, field)
Definition: c.h:622

◆ 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:242
TupSortStatus status
Definition: tuplesort.c:234
TuplesortMethod sortMethod
Definition: tuplesort.h:83
LogicalTapeSet * tapeset
Definition: tuplesort.c:248
int64 allowedMem
Definition: tuplesort.c:243
TuplesortSpaceType spaceType
Definition: tuplesort.h:84
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:1086

◆ tuplesort_getdatum()

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

Definition at line 2244 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 mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), percentile_disc_multi_final(), process_ordered_aggregate_single(), and validate_index_heapscan().

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

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2195 of file tuplesort.c.

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

Referenced by copy_heap_data().

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

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2215 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

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

◆ tuplesort_gettupleslot()

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

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

2160 {
2161  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2162  SortTuple stup;
2163 
2164  if (!tuplesort_gettuple_common(state, forward, &stup))
2165  stup.tuple = NULL;
2166 
2167  MemoryContextSwitchTo(oldcontext);
2168 
2169  if (stup.tuple)
2170  {
2171  /* Record abbreviated key for caller */
2172  if (state->sortKeys->abbrev_converter && abbrev)
2173  *abbrev = stup.datum1;
2174 
2175  if (copy)
2177 
2178  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
2179  return true;
2180  }
2181  else
2182  {
2183  ExecClearTuple(slot);
2184  return false;
2185  }
2186 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:420
SortSupport sortKeys
Definition: tuplesort.c:414
TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: execTuples.c:475
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:172
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1880
void * tuple
Definition: tuplesort.c:171
MemoryContext sortcontext
Definition: tuplesort.c:246
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1901

◆ tuplesort_initialize_shared()

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

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

4385 {
4386  int i;
4387 
4388  Assert(nWorkers > 0);
4389 
4390  SpinLockInit(&shared->mutex);
4391  shared->currentWorker = 0;
4392  shared->workersFinished = 0;
4393  SharedFileSetInit(&shared->fileset, seg);
4394  shared->nTapes = nWorkers;
4395  for (i = 0; i < nWorkers; i++)
4396  {
4397  shared->tapes[i].firstblocknumber = 0L;
4398  }
4399 }
slock_t mutex
Definition: tuplesort.c:476
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:47
#define SpinLockInit(lock)
Definition: spin.h:60
long firstblocknumber
Definition: logtape.h:50
int workersFinished
Definition: tuplesort.c:487
int nTapes
Definition: tuplesort.c:493
#define Assert(condition)
Definition: c.h:699
int i
int currentWorker
Definition: tuplesort.c:486
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:499
SharedFileSet fileset
Definition: tuplesort.c:490

◆ 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:234
bool randomAccess
Definition: tuplesort.c:236
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:386
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:246
LogicalTapeSet * tapeset
Definition: tuplesort.c:248
void LogicalTapeTell(LogicalTapeSet *lts, int tapenum, long *blocknum, int *offset)
Definition: logtape.c:1066
#define Assert(condition)
Definition: c.h:699
long markpos_block
Definition: tuplesort.c:385
bool eof_reached
Definition: tuplesort.c:382
bool markpos_eof
Definition: tuplesort.c:387
#define elog
Definition: elog.h:219

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2352 of file tuplesort.c.

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

Referenced by cost_sort(), and inittapes().

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

◆ 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 1790 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(), copy_heap_data(), ExecSort(), 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().

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

◆ tuplesort_putdatum()

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

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

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

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 1456 of file tuplesort.c.

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

Referenced by copy_heap_data().

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

◆ tuplesort_putindextuplevalues()

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

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

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

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

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

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

◆ 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:234
bool randomAccess
Definition: tuplesort.c:236
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:386
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:246
LogicalTapeSet * tapeset
Definition: tuplesort.c:248
#define Assert(condition)
Definition: c.h:699
long markpos_block
Definition: tuplesort.c:385
bool eof_reached
Definition: tuplesort.c:382
void LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Definition: logtape.c:713
bool markpos_eof
Definition: tuplesort.c:387
#define elog
Definition: elog.h:219

◆ 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:234
bool randomAccess
Definition: tuplesort.c:236
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:386
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:246
LogicalTapeSet * tapeset
Definition: tuplesort.c:248
#define Assert(condition)
Definition: c.h:699
long markpos_block
Definition: tuplesort.c:385
bool eof_reached
Definition: tuplesort.c:382
bool markpos_eof
Definition: tuplesort.c:387
void LogicalTapeSeek(LogicalTapeSet *lts, int tapenum, long blocknum, int offset)
Definition: logtape.c:1035
#define elog
Definition: elog.h:219

◆ 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);
1190  Assert(state->memtupcount == 0);
1191  Assert(!state->bounded);
1192  Assert(!WORKER(state));
1193 
1194 #ifdef DEBUG_BOUNDED_SORT
1195  /* Honor GUC setting that disables the feature (for easy testing) */
1196  if (!optimize_bounded_sort)
1197  return;
1198 #endif
1199 
1200  /* Parallel leader ignores hint */
1201  if (LEADER(state))
1202  return;
1203 
1204  /* We want to be able to compute bound * 2, so limit the setting */
1205  if (bound > (int64) (INT_MAX / 2))
1206  return;
1207 
1208  state->bounded = true;
1209  state->bound = (int) bound;
1210 
1211  /*
1212  * Bounded sorts are not an effective target for abbreviated key
1213  * optimization. Disable by setting state to be consistent with no
1214  * abbreviation support.
1215  */
1216  state->sortKeys->abbrev_converter = NULL;
1217  if (state->sortKeys->abbrev_full_comparator)
1219 
1220  /* Not strictly necessary, but be tidy */
1221  state->sortKeys->abbrev_abort = NULL;
1222  state->sortKeys->abbrev_full_comparator = NULL;
1223 }
TupSortStatus status
Definition: tuplesort.c:234
SortSupport sortKeys
Definition: tuplesort.c:414
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:107
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:192
#define LEADER(state)
Definition: tuplesort.c:534
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define WORKER(state)
Definition: tuplesort.c:533
#define Assert(condition)
Definition: c.h:699
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:183

◆ tuplesort_skiptuples()

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

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

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

◆ 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:699