PostgreSQL Source Code  git master
tuplesort.h File Reference
#include "access/itup.h"
#include "executor/tuptable.h"
#include "storage/dsm.h"
#include "utils/logtape.h"
#include "utils/relcache.h"
#include "utils/sortsupport.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
 
struct  SortTuple
 
struct  TuplesortPublic
 

Macros

#define NUM_TUPLESORTMETHODS   4
 
#define TUPLESORT_NONE   0
 
#define TUPLESORT_RANDOMACCESS   (1 << 0)
 
#define TUPLESORT_ALLOWBOUNDED   (1 << 1)
 
#define PARALLEL_SORT(coordinate)
 
#define TuplesortstateGetPublic(state)   ((TuplesortPublic *) state)
 
#define LogicalTapeReadExact(tape, ptr, len)
 

Typedefs

typedef struct Tuplesortstate Tuplesortstate
 
typedef struct Sharedsort Sharedsort
 
typedef struct SortCoordinateData SortCoordinateData
 
typedef struct SortCoordinateDataSortCoordinate
 
typedef struct TuplesortInstrumentation TuplesortInstrumentation
 
typedef int(* SortTupleComparator) (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 

Enumerations

enum  TuplesortMethod {
  SORT_TYPE_STILL_IN_PROGRESS = 0 , SORT_TYPE_TOP_N_HEAPSORT = 1 << 0 , SORT_TYPE_QUICKSORT = 1 << 1 , SORT_TYPE_EXTERNAL_SORT = 1 << 2 ,
  SORT_TYPE_EXTERNAL_MERGE = 1 << 3
}
 
enum  TuplesortSpaceType { SORT_SPACE_TYPE_DISK , SORT_SPACE_TYPE_MEMORY }
 

Functions

Tuplesortstatetuplesort_begin_common (int workMem, SortCoordinate coordinate, int sortopt)
 
void tuplesort_set_bound (Tuplesortstate *state, int64 bound)
 
bool tuplesort_used_bound (Tuplesortstate *state)
 
void tuplesort_puttuple_common (Tuplesortstate *state, SortTuple *tuple, bool useAbbrev)
 
void tuplesort_performsort (Tuplesortstate *state)
 
bool tuplesort_gettuple_common (Tuplesortstate *state, bool forward, SortTuple *stup)
 
bool tuplesort_skiptuples (Tuplesortstate *state, int64 ntuples, bool forward)
 
void tuplesort_end (Tuplesortstate *state)
 
void tuplesort_reset (Tuplesortstate *state)
 
void tuplesort_get_stats (Tuplesortstate *state, TuplesortInstrumentation *stats)
 
const char * tuplesort_method_name (TuplesortMethod m)
 
const char * tuplesort_space_type_name (TuplesortSpaceType t)
 
int tuplesort_merge_order (int64 allowedMem)
 
Size tuplesort_estimate_shared (int nWorkers)
 
void tuplesort_initialize_shared (Sharedsort *shared, int nWorkers, dsm_segment *seg)
 
void tuplesort_attach_shared (Sharedsort *shared, dsm_segment *seg)
 
void tuplesort_rescan (Tuplesortstate *state)
 
void tuplesort_markpos (Tuplesortstate *state)
 
void tuplesort_restorepos (Tuplesortstate *state)
 
void * tuplesort_readtup_alloc (Tuplesortstate *state, Size tuplen)
 
Tuplesortstatetuplesort_begin_heap (TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, bool uniqueNullsNotDistinct, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_gist (Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, int sortopt)
 
void tuplesort_puttupleslot (Tuplesortstate *state, TupleTableSlot *slot)
 
void tuplesort_putheaptuple (Tuplesortstate *state, HeapTuple tup)
 
void tuplesort_putindextuplevalues (Tuplesortstate *state, Relation rel, ItemPointer self, const Datum *values, const bool *isnull)
 
void tuplesort_putdatum (Tuplesortstate *state, Datum val, bool isNull)
 
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, bool copy, Datum *val, bool *isNull, Datum *abbrev)
 

Macro Definition Documentation

◆ LogicalTapeReadExact

#define LogicalTapeReadExact (   tape,
  ptr,
  len 
)
Value:
do { \
if (LogicalTapeRead(tape, ptr, len) != (size_t) (len)) \
elog(ERROR, "unexpected end of data"); \
} while(0)
#define ERROR
Definition: elog.h:39
size_t LogicalTapeRead(LogicalTape *lt, void *ptr, size_t size)
Definition: logtape.c:928
const void size_t len

Definition at line 251 of file tuplesort.h.

◆ NUM_TUPLESORTMETHODS

#define NUM_TUPLESORTMETHODS   4

Definition at line 83 of file tuplesort.h.

◆ PARALLEL_SORT

#define PARALLEL_SORT (   coordinate)
Value:
(coordinate == NULL || \
(coordinate)->sharedsort == NULL ? 0 : \
(coordinate)->isWorker ? 1 : 2)

Definition at line 244 of file tuplesort.h.

◆ TUPLESORT_ALLOWBOUNDED

#define TUPLESORT_ALLOWBOUNDED   (1 << 1)

Definition at line 98 of file tuplesort.h.

◆ TUPLESORT_NONE

#define TUPLESORT_NONE   0

Definition at line 92 of file tuplesort.h.

◆ TUPLESORT_RANDOMACCESS

#define TUPLESORT_RANDOMACCESS   (1 << 0)

Definition at line 95 of file tuplesort.h.

◆ TuplesortstateGetPublic

#define TuplesortstateGetPublic (   state)    ((TuplesortPublic *) state)

Definition at line 248 of file tuplesort.h.

Typedef Documentation

◆ Sharedsort

typedef struct Sharedsort Sharedsort

Definition at line 1 of file tuplesort.h.

◆ SortCoordinate

Definition at line 60 of file tuplesort.h.

◆ SortCoordinateData

◆ SortTupleComparator

typedef int(* SortTupleComparator) (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)

Definition at line 144 of file tuplesort.h.

◆ TuplesortInstrumentation

◆ Tuplesortstate

Definition at line 1 of file tuplesort.h.

Enumeration Type Documentation

◆ TuplesortMethod

Enumerator
SORT_TYPE_STILL_IN_PROGRESS 
SORT_TYPE_TOP_N_HEAPSORT 
SORT_TYPE_QUICKSORT 
SORT_TYPE_EXTERNAL_SORT 
SORT_TYPE_EXTERNAL_MERGE 

Definition at line 74 of file tuplesort.h.

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

◆ TuplesortSpaceType

Enumerator
SORT_SPACE_TYPE_DISK 
SORT_SPACE_TYPE_MEMORY 

Definition at line 85 of file tuplesort.h.

86 {
TuplesortSpaceType
Definition: tuplesort.h:86
@ SORT_SPACE_TYPE_DISK
Definition: tuplesort.h:87
@ SORT_SPACE_TYPE_MEMORY
Definition: tuplesort.h:88

Function Documentation

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 2996 of file tuplesort.c.

2997 {
2998  /* Attach to SharedFileSet */
2999  SharedFileSetAttach(&shared->fileset, seg);
3000 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:62
SharedFileSet fileset
Definition: tuplesort.c:361

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

◆ tuplesort_begin_cluster()

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

Definition at line 219 of file tuplesortvariants.c.

223 {
224  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
225  sortopt);
227  BTScanInsert indexScanKey;
228  MemoryContext oldcontext;
230  int i;
231 
232  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
233 
234  oldcontext = MemoryContextSwitchTo(base->maincontext);
236 
237 #ifdef TRACE_SORT
238  if (trace_sort)
239  elog(LOG,
240  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
242  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
243 #endif
244 
246 
247  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
248  false, /* no unique check */
249  base->nKeys,
250  workMem,
251  sortopt & TUPLESORT_RANDOMACCESS,
252  PARALLEL_SORT(coordinate));
253 
257  base->writetup = writetup_cluster;
258  base->readtup = readtup_cluster;
260  base->arg = arg;
261 
262  arg->indexInfo = BuildIndexInfo(indexRel);
263 
264  /*
265  * If we don't have a simple leading attribute, we don't currently
266  * initialize datum1, so disable optimizations that require it.
267  */
268  if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
269  base->haveDatum1 = false;
270  else
271  base->haveDatum1 = true;
272 
273  arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
274 
275  indexScanKey = _bt_mkscankey(indexRel, NULL);
276 
277  if (arg->indexInfo->ii_Expressions != NULL)
278  {
279  TupleTableSlot *slot;
280  ExprContext *econtext;
281 
282  /*
283  * We will need to use FormIndexDatum to evaluate the index
284  * expressions. To do that, we need an EState, as well as a
285  * TupleTableSlot to put the table tuples into. The econtext's
286  * scantuple has to point to that slot, too.
287  */
288  arg->estate = CreateExecutorState();
289  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
290  econtext = GetPerTupleExprContext(arg->estate);
291  econtext->ecxt_scantuple = slot;
292  }
293 
294  /* Prepare SortSupport data for each column */
295  base->sortKeys = (SortSupport) palloc0(base->nKeys *
296  sizeof(SortSupportData));
297 
298  for (i = 0; i < base->nKeys; i++)
299  {
300  SortSupport sortKey = base->sortKeys + i;
301  ScanKey scanKey = indexScanKey->scankeys + i;
302  int16 strategy;
303 
304  sortKey->ssup_cxt = CurrentMemoryContext;
305  sortKey->ssup_collation = scanKey->sk_collation;
306  sortKey->ssup_nulls_first =
307  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
308  sortKey->ssup_attno = scanKey->sk_attno;
309  /* Convey if abbreviation optimization is applicable in principle */
310  sortKey->abbreviate = (i == 0 && base->haveDatum1);
311 
312  Assert(sortKey->ssup_attno != 0);
313 
314  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
316 
317  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
318  }
319 
320  pfree(indexScanKey);
321 
322  MemoryContextSwitchTo(oldcontext);
323 
324  return state;
325 }
signed short int16
Definition: c.h:482
#define LOG
Definition: elog.h:31
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:84
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1239
EState * CreateExecutorState(void)
Definition: execUtils.c:93
#define GetPerTupleExprContext(estate)
Definition: executor.h:549
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2425
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1456
void * palloc0(Size size)
Definition: mcxt.c:1257
MemoryContext CurrentMemoryContext
Definition: mcxt.c:135
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1095
#define SK_BT_DESC
Definition: nbtree.h:1094
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
void * arg
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:510
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:523
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:162
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:798
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:248
Form_pg_class rd_rel
Definition: rel.h:111
int sk_flags
Definition: skey.h:66
Oid sk_collation
Definition: skey.h:70
AttrNumber sk_attno
Definition: skey.h:67
AttrNumber ssup_attno
Definition: sortsupport.h:81
bool ssup_nulls_first
Definition: sortsupport.h:75
MemoryContext ssup_cxt
Definition: sortsupport.h:66
MemoryContext maincontext
Definition: tuplesort.h:207
void(* writetup)(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.h:183
void(* removeabbrev)(Tuplesortstate *state, SortTuple *stups, int count)
Definition: tuplesort.h:176
void(* freestate)(Tuplesortstate *state)
Definition: tuplesort.h:201
void(* readtup)(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.h:192
SortTupleComparator comparetup
Definition: tuplesort.h:163
SortSupport sortKeys
Definition: tuplesort.h:224
SortTupleComparator comparetup_tiebreak
Definition: tuplesort.h:170
Definition: regguts.h:323
Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
Definition: tuplesort.c:643
bool trace_sort
Definition: tuplesort.c:127
#define PARALLEL_SORT(coordinate)
Definition: tuplesort.h:244
#define TUPLESORT_RANDOMACCESS
Definition: tuplesort.h:95
#define TuplesortstateGetPublic(state)
Definition: tuplesort.h:248
static int comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int tuplen)
#define CLUSTER_SORT
static void freestate_cluster(Tuplesortstate *state)
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void writetup_cluster(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static void removeabbrev_cluster(Tuplesortstate *state, SortTuple *stups, int count)

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), BTGreaterStrategyNumber, BTLessStrategyNumber, BuildIndexInfo(), CLUSTER_SORT, TuplesortPublic::comparetup, comparetup_cluster(), comparetup_cluster_tiebreak(), TuplesortPublic::comparetup_tiebreak, CreateExecutorState(), CurrentMemoryContext, ExprContext::ecxt_scantuple, elog(), TuplesortPublic::freestate, freestate_cluster(), GetPerTupleExprContext, TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, TuplesortPublic::readtup, readtup_cluster(), RelationGetNumberOfAttributes, TuplesortPublic::removeabbrev, removeabbrev_cluster(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TTSOpsHeapTuple, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_cluster().

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_begin_common()

Tuplesortstate* tuplesort_begin_common ( int  workMem,
SortCoordinate  coordinate,
int  sortopt 
)

Definition at line 643 of file tuplesort.c.

644 {
646  MemoryContext maincontext;
647  MemoryContext sortcontext;
648  MemoryContext oldcontext;
649 
650  /* See leader_takeover_tapes() remarks on random access support */
651  if (coordinate && (sortopt & TUPLESORT_RANDOMACCESS))
652  elog(ERROR, "random access disallowed under parallel sort");
653 
654  /*
655  * Memory context surviving tuplesort_reset. This memory context holds
656  * data which is useful to keep while sorting multiple similar batches.
657  */
659  "TupleSort main",
661 
662  /*
663  * Create a working memory context for one sort operation. The content of
664  * this context is deleted by tuplesort_reset.
665  */
666  sortcontext = AllocSetContextCreate(maincontext,
667  "TupleSort sort",
669 
670  /*
671  * Additionally a working memory context for tuples is setup in
672  * tuplesort_begin_batch.
673  */
674 
675  /*
676  * Make the Tuplesortstate within the per-sortstate context. This way, we
677  * don't need a separate pfree() operation for it at shutdown.
678  */
679  oldcontext = MemoryContextSwitchTo(maincontext);
680 
682 
683 #ifdef TRACE_SORT
684  if (trace_sort)
685  pg_rusage_init(&state->ru_start);
686 #endif
687 
688  state->base.sortopt = sortopt;
689  state->base.tuples = true;
690  state->abbrevNext = 10;
691 
692  /*
693  * workMem is forced to be at least 64KB, the current minimum valid value
694  * for the work_mem GUC. This is a defense against parallel sort callers
695  * that divide out memory among many workers in a way that leaves each
696  * with very little memory.
697  */
698  state->allowedMem = Max(workMem, 64) * (int64) 1024;
699  state->base.sortcontext = sortcontext;
700  state->base.maincontext = maincontext;
701 
702  /*
703  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
704  * see comments in grow_memtuples().
705  */
706  state->memtupsize = INITIAL_MEMTUPSIZE;
707  state->memtuples = NULL;
708 
709  /*
710  * After all of the other non-parallel-related state, we setup all of the
711  * state needed for each batch.
712  */
714 
715  /*
716  * Initialize parallel-related state based on coordination information
717  * from caller
718  */
719  if (!coordinate)
720  {
721  /* Serial sort */
722  state->shared = NULL;
723  state->worker = -1;
724  state->nParticipants = -1;
725  }
726  else if (coordinate->isWorker)
727  {
728  /* Parallel worker produces exactly one final run from all input */
729  state->shared = coordinate->sharedsort;
730  state->worker = worker_get_identifier(state);
731  state->nParticipants = -1;
732  }
733  else
734  {
735  /* Parallel leader state only used for final merge */
736  state->shared = coordinate->sharedsort;
737  state->worker = -1;
738  state->nParticipants = coordinate->nParticipants;
739  Assert(state->nParticipants >= 1);
740  }
741 
742  MemoryContextSwitchTo(oldcontext);
743 
744  return state;
745 }
#define Max(x, y)
Definition: c.h:987
#define AllocSetContextCreate
Definition: memutils.h:126
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:150
void pg_rusage_init(PGRUsage *ru0)
Definition: pg_rusage.c:27
Sharedsort * sharedsort
Definition: tuplesort.h:57
#define INITIAL_MEMTUPSIZE
Definition: tuplesort.c:122
static int worker_get_identifier(Tuplesortstate *state)
Definition: tuplesort.c:3016
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:755

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), CurrentMemoryContext, elog(), ERROR, INITIAL_MEMTUPSIZE, SortCoordinateData::isWorker, Max, MemoryContextSwitchTo(), SortCoordinateData::nParticipants, palloc0(), pg_rusage_init(), SortCoordinateData::sharedsort, trace_sort, tuplesort_begin_batch(), TUPLESORT_RANDOMACCESS, and worker_get_identifier().

Referenced by tuplesort_begin_cluster(), tuplesort_begin_datum(), tuplesort_begin_heap(), tuplesort_begin_index_btree(), tuplesort_begin_index_gist(), and tuplesort_begin_index_hash().

◆ tuplesort_begin_datum()

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

Definition at line 531 of file tuplesortvariants.c.

534 {
535  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
536  sortopt);
539  MemoryContext oldcontext;
540  int16 typlen;
541  bool typbyval;
542 
543  oldcontext = MemoryContextSwitchTo(base->maincontext);
545 
546 #ifdef TRACE_SORT
547  if (trace_sort)
548  elog(LOG,
549  "begin datum sort: workMem = %d, randomAccess = %c",
550  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
551 #endif
552 
553  base->nKeys = 1; /* always a one-column sort */
554 
555  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
556  false, /* no unique check */
557  1,
558  workMem,
559  sortopt & TUPLESORT_RANDOMACCESS,
560  PARALLEL_SORT(coordinate));
561 
565  base->writetup = writetup_datum;
566  base->readtup = readtup_datum;
567  base->haveDatum1 = true;
568  base->arg = arg;
569 
570  arg->datumType = datumType;
571 
572  /* lookup necessary attributes of the datum type */
573  get_typlenbyval(datumType, &typlen, &typbyval);
574  arg->datumTypeLen = typlen;
575  base->tuples = !typbyval;
576 
577  /* Prepare SortSupport data */
578  base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
579 
581  base->sortKeys->ssup_collation = sortCollation;
582  base->sortKeys->ssup_nulls_first = nullsFirstFlag;
583 
584  /*
585  * Abbreviation is possible here only for by-reference types. In theory,
586  * a pass-by-value datatype could have an abbreviated form that is cheaper
587  * to compare. In a tuple sort, we could support that, because we can
588  * always extract the original datum from the tuple as needed. Here, we
589  * can't, because a datum sort only stores a single copy of the datum; the
590  * "tuple" field of each SortTuple is NULL.
591  */
592  base->sortKeys->abbreviate = !typbyval;
593 
594  PrepareSortSupportFromOrderingOp(sortOperator, base->sortKeys);
595 
596  /*
597  * The "onlyKey" optimization cannot be used with abbreviated keys, since
598  * tie-breaker comparisons may be required. Typically, the optimization
599  * is only of value to pass-by-value types anyway, whereas abbreviated
600  * keys are typically only of value to pass-by-reference types.
601  */
602  if (!base->sortKeys->abbrev_converter)
603  base->onlyKey = base->sortKeys;
604 
605  MemoryContextSwitchTo(oldcontext);
606 
607  return state;
608 }
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2233
void * palloc(Size size)
Definition: mcxt.c:1226
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:135
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
SortSupport onlyKey
Definition: tuplesort.h:234
static void removeabbrev_datum(Tuplesortstate *state, SortTuple *stups, int count)
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static int comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static void writetup_datum(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
#define DATUM_SORT

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, arg, TuplesortPublic::arg, TuplesortPublic::comparetup, comparetup_datum(), comparetup_datum_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, DATUM_SORT, elog(), get_typlenbyval(), TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, TuplesortPublic::onlyKey, palloc(), palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), TuplesortPublic::readtup, readtup_datum(), TuplesortPublic::removeabbrev, removeabbrev_datum(), TuplesortPublic::sortKeys, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TuplesortPublic::tuples, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_datum().

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

◆ tuplesort_begin_heap()

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

Definition at line 144 of file tuplesortvariants.c.

149 {
150  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
151  sortopt);
153  MemoryContext oldcontext;
154  int i;
155 
156  oldcontext = MemoryContextSwitchTo(base->maincontext);
157 
158  Assert(nkeys > 0);
159 
160 #ifdef TRACE_SORT
161  if (trace_sort)
162  elog(LOG,
163  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
164  nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
165 #endif
166 
167  base->nKeys = nkeys;
168 
169  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
170  false, /* no unique check */
171  nkeys,
172  workMem,
173  sortopt & TUPLESORT_RANDOMACCESS,
174  PARALLEL_SORT(coordinate));
175 
177  base->comparetup = comparetup_heap;
179  base->writetup = writetup_heap;
180  base->readtup = readtup_heap;
181  base->haveDatum1 = true;
182  base->arg = tupDesc; /* assume we need not copy tupDesc */
183 
184  /* Prepare SortSupport data for each column */
185  base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
186 
187  for (i = 0; i < nkeys; i++)
188  {
189  SortSupport sortKey = base->sortKeys + i;
190 
191  Assert(attNums[i] != 0);
192  Assert(sortOperators[i] != 0);
193 
194  sortKey->ssup_cxt = CurrentMemoryContext;
195  sortKey->ssup_collation = sortCollations[i];
196  sortKey->ssup_nulls_first = nullsFirstFlags[i];
197  sortKey->ssup_attno = attNums[i];
198  /* Convey if abbreviation optimization is applicable in principle */
199  sortKey->abbreviate = (i == 0 && base->haveDatum1);
200 
201  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
202  }
203 
204  /*
205  * The "onlyKey" optimization cannot be used with abbreviated keys, since
206  * tie-breaker comparisons may be required. Typically, the optimization
207  * is only of value to pass-by-value types anyway, whereas abbreviated
208  * keys are typically only of value to pass-by-reference types.
209  */
210  if (nkeys == 1 && !base->sortKeys->abbrev_converter)
211  base->onlyKey = base->sortKeys;
212 
213  MemoryContextSwitchTo(oldcontext);
214 
215  return state;
216 }
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static int comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void writetup_heap(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static int comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void removeabbrev_heap(Tuplesortstate *state, SortTuple *stups, int count)
#define HEAP_SORT

References SortSupportData::abbrev_converter, SortSupportData::abbreviate, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_heap(), comparetup_heap_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog(), TuplesortPublic::haveDatum1, HEAP_SORT, i, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, TuplesortPublic::onlyKey, palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), TuplesortPublic::readtup, readtup_heap(), TuplesortPublic::removeabbrev, removeabbrev_heap(), TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_heap().

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

◆ tuplesort_begin_index_btree()

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

Definition at line 328 of file tuplesortvariants.c.

335 {
336  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
337  sortopt);
339  BTScanInsert indexScanKey;
341  MemoryContext oldcontext;
342  int i;
343 
344  oldcontext = MemoryContextSwitchTo(base->maincontext);
346 
347 #ifdef TRACE_SORT
348  if (trace_sort)
349  elog(LOG,
350  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
351  enforceUnique ? 't' : 'f',
352  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
353 #endif
354 
356 
357  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
358  enforceUnique,
359  base->nKeys,
360  workMem,
361  sortopt & TUPLESORT_RANDOMACCESS,
362  PARALLEL_SORT(coordinate));
363 
367  base->writetup = writetup_index;
368  base->readtup = readtup_index;
369  base->haveDatum1 = true;
370  base->arg = arg;
371 
372  arg->index.heapRel = heapRel;
373  arg->index.indexRel = indexRel;
374  arg->enforceUnique = enforceUnique;
375  arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
376 
377  indexScanKey = _bt_mkscankey(indexRel, NULL);
378 
379  /* Prepare SortSupport data for each column */
380  base->sortKeys = (SortSupport) palloc0(base->nKeys *
381  sizeof(SortSupportData));
382 
383  for (i = 0; i < base->nKeys; i++)
384  {
385  SortSupport sortKey = base->sortKeys + i;
386  ScanKey scanKey = indexScanKey->scankeys + i;
387  int16 strategy;
388 
389  sortKey->ssup_cxt = CurrentMemoryContext;
390  sortKey->ssup_collation = scanKey->sk_collation;
391  sortKey->ssup_nulls_first =
392  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
393  sortKey->ssup_attno = scanKey->sk_attno;
394  /* Convey if abbreviation optimization is applicable in principle */
395  sortKey->abbreviate = (i == 0 && base->haveDatum1);
396 
397  Assert(sortKey->ssup_attno != 0);
398 
399  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
401 
402  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
403  }
404 
405  pfree(indexScanKey);
406 
407  MemoryContextSwitchTo(oldcontext);
408 
409  return state;
410 }
static int comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_index(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static void removeabbrev_index(Tuplesortstate *state, SortTuple *stups, int count)
#define INDEX_SORT
static void writetup_index(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)

References _bt_mkscankey(), SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), BTGreaterStrategyNumber, BTLessStrategyNumber, TuplesortPublic::comparetup, comparetup_index_btree(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog(), TuplesortPublic::haveDatum1, i, INDEX_SORT, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

◆ tuplesort_begin_index_gist()

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

Definition at line 466 of file tuplesortvariants.c.

471 {
472  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
473  sortopt);
475  MemoryContext oldcontext;
477  int i;
478 
479  oldcontext = MemoryContextSwitchTo(base->maincontext);
481 
482 #ifdef TRACE_SORT
483  if (trace_sort)
484  elog(LOG,
485  "begin index sort: workMem = %d, randomAccess = %c",
486  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
487 #endif
488 
490 
494  base->writetup = writetup_index;
495  base->readtup = readtup_index;
496  base->haveDatum1 = true;
497  base->arg = arg;
498 
499  arg->index.heapRel = heapRel;
500  arg->index.indexRel = indexRel;
501  arg->enforceUnique = false;
502  arg->uniqueNullsNotDistinct = false;
503 
504  /* Prepare SortSupport data for each column */
505  base->sortKeys = (SortSupport) palloc0(base->nKeys *
506  sizeof(SortSupportData));
507 
508  for (i = 0; i < base->nKeys; i++)
509  {
510  SortSupport sortKey = base->sortKeys + i;
511 
512  sortKey->ssup_cxt = CurrentMemoryContext;
513  sortKey->ssup_collation = indexRel->rd_indcollation[i];
514  sortKey->ssup_nulls_first = false;
515  sortKey->ssup_attno = i + 1;
516  /* Convey if abbreviation optimization is applicable in principle */
517  sortKey->abbreviate = (i == 0 && base->haveDatum1);
518 
519  Assert(sortKey->ssup_attno != 0);
520 
521  /* Look for a sort support function */
522  PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
523  }
524 
525  MemoryContextSwitchTo(oldcontext);
526 
527  return state;
528 }
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:189
Oid * rd_indcollation
Definition: rel.h:216

References SortSupportData::abbreviate, arg, TuplesortPublic::arg, Assert(), TuplesortPublic::comparetup, comparetup_index_btree(), comparetup_index_btree_tiebreak(), TuplesortPublic::comparetup_tiebreak, CurrentMemoryContext, elog(), TuplesortPublic::haveDatum1, i, IndexRelationGetNumberOfKeyAttributes, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), palloc0(), PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), TuplesortPublic::sortKeys, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by gistbuild().

◆ tuplesort_begin_index_hash()

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

Definition at line 413 of file tuplesortvariants.c.

421 {
422  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
423  sortopt);
425  MemoryContext oldcontext;
427 
428  oldcontext = MemoryContextSwitchTo(base->maincontext);
430 
431 #ifdef TRACE_SORT
432  if (trace_sort)
433  elog(LOG,
434  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
435  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
436  high_mask,
437  low_mask,
438  max_buckets,
439  workMem,
440  sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
441 #endif
442 
443  base->nKeys = 1; /* Only one sort column, the hash code */
444 
448  base->writetup = writetup_index;
449  base->readtup = readtup_index;
450  base->haveDatum1 = true;
451  base->arg = arg;
452 
453  arg->index.heapRel = heapRel;
454  arg->index.indexRel = indexRel;
455 
456  arg->high_mask = high_mask;
457  arg->low_mask = low_mask;
458  arg->max_buckets = max_buckets;
459 
460  MemoryContextSwitchTo(oldcontext);
461 
462  return state;
463 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static int comparetup_index_hash_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)

References arg, TuplesortPublic::arg, TuplesortPublic::comparetup, comparetup_index_hash(), comparetup_index_hash_tiebreak(), TuplesortPublic::comparetup_tiebreak, elog(), TuplesortPublic::haveDatum1, LOG, TuplesortPublic::maincontext, MemoryContextSwitchTo(), TuplesortPublic::nKeys, palloc(), TuplesortPublic::readtup, readtup_index(), TuplesortPublic::removeabbrev, removeabbrev_index(), trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, TuplesortstateGetPublic, TuplesortPublic::writetup, and writetup_index().

Referenced by _h_spoolinit().

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 969 of file tuplesort.c.

970 {
972 
973  /*
974  * Free the main memory context, including the Tuplesortstate struct
975  * itself.
976  */
977  MemoryContextDelete(state->base.maincontext);
978 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:403
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:900

References MemoryContextDelete(), and tuplesort_free().

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

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nWorkers)

Definition at line 2952 of file tuplesort.c.

2953 {
2954  Size tapesSize;
2955 
2956  Assert(nWorkers > 0);
2957 
2958  /* Make sure that BufFile shared state is MAXALIGN'd */
2959  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
2960  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
2961 
2962  return tapesSize;
2963 }
#define MAXALIGN(LEN)
Definition: c.h:800
size_t Size
Definition: c.h:594
Size add_size(Size s1, Size s2)
Definition: shmem.c:502
Size mul_size(Size s1, Size s2)
Definition: shmem.c:519

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

Referenced by _bt_begin_parallel().

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 2534 of file tuplesort.c.

2536 {
2537  /*
2538  * Note: it might seem we should provide both memory and disk usage for a
2539  * disk-based sort. However, the current code doesn't track memory space
2540  * accurately once we have begun to return tuples to the caller (since we
2541  * don't account for pfree's the caller is expected to do), so we cannot
2542  * rely on availMem in a disk sort. This does not seem worth the overhead
2543  * to fix. Is it worth creating an API for the memory context code to
2544  * tell us how much is actually used in sortcontext?
2545  */
2547 
2548  if (state->isMaxSpaceDisk)
2550  else
2552  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
2553 
2554  switch (state->maxSpaceStatus)
2555  {
2556  case TSS_SORTEDINMEM:
2557  if (state->boundUsed)
2559  else
2561  break;
2562  case TSS_SORTEDONTAPE:
2564  break;
2565  case TSS_FINALMERGE:
2567  break;
2568  default:
2570  break;
2571  }
2572 }
TuplesortMethod sortMethod
Definition: tuplesort.h:102
TuplesortSpaceType spaceType
Definition: tuplesort.h:103
@ TSS_SORTEDONTAPE
Definition: tuplesort.c:164
@ TSS_SORTEDINMEM
Definition: tuplesort.c:163
@ TSS_FINALMERGE
Definition: tuplesort.c:165
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:986

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

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

◆ tuplesort_getdatum()

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

Definition at line 879 of file tuplesortvariants.c.

881 {
883  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
885  SortTuple stup;
886 
887  if (!tuplesort_gettuple_common(state, forward, &stup))
888  {
889  MemoryContextSwitchTo(oldcontext);
890  return false;
891  }
892 
893  /* Ensure we copy into caller's memory context */
894  MemoryContextSwitchTo(oldcontext);
895 
896  /* Record abbreviated key for caller */
897  if (base->sortKeys->abbrev_converter && abbrev)
898  *abbrev = stup.datum1;
899 
900  if (stup.isnull1 || !base->tuples)
901  {
902  *val = stup.datum1;
903  *isNull = stup.isnull1;
904  }
905  else
906  {
907  /* use stup.tuple because stup.datum1 may be an abbreviation */
908  if (copy)
909  *val = datumCopy(PointerGetDatum(stup.tuple), false,
910  arg->datumTypeLen);
911  else
912  *val = PointerGetDatum(stup.tuple);
913  *isNull = false;
914  }
915 
916  return true;
917 }
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
long val
Definition: informix.c:664
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
MemoryContext sortcontext
Definition: tuplesort.h:209
bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1493

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, datumCopy(), if(), MemoryContextSwitchTo(), PointerGetDatum(), TuplesortPublic::sortcontext, TuplesortPublic::sortKeys, TuplesortPublic::tuples, tuplesort_gettuple_common(), TuplesortstateGetPublic, and val.

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

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 818 of file tuplesortvariants.c.

819 {
821  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
822  SortTuple stup;
823 
824  if (!tuplesort_gettuple_common(state, forward, &stup))
825  stup.tuple = NULL;
826 
827  MemoryContextSwitchTo(oldcontext);
828 
829  return stup.tuple;
830 }
void * tuple
Definition: tuplesort.h:138

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

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 839 of file tuplesortvariants.c.

840 {
842  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
843  SortTuple stup;
844 
845  if (!tuplesort_gettuple_common(state, forward, &stup))
846  stup.tuple = NULL;
847 
848  MemoryContextSwitchTo(oldcontext);
849 
850  return (IndexTuple) stup.tuple;
851 }

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

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

◆ tuplesort_gettuple_common()

bool tuplesort_gettuple_common ( Tuplesortstate state,
bool  forward,
SortTuple stup 
)

Definition at line 1493 of file tuplesort.c.

1495 {
1496  unsigned int tuplen;
1497  size_t nmoved;
1498 
1499  Assert(!WORKER(state));
1500 
1501  switch (state->status)
1502  {
1503  case TSS_SORTEDINMEM:
1504  Assert(forward || state->base.sortopt & TUPLESORT_RANDOMACCESS);
1505  Assert(!state->slabAllocatorUsed);
1506  if (forward)
1507  {
1508  if (state->current < state->memtupcount)
1509  {
1510  *stup = state->memtuples[state->current++];
1511  return true;
1512  }
1513  state->eof_reached = true;
1514 
1515  /*
1516  * Complain if caller tries to retrieve more tuples than
1517  * originally asked for in a bounded sort. This is because
1518  * returning EOF here might be the wrong thing.
1519  */
1520  if (state->bounded && state->current >= state->bound)
1521  elog(ERROR, "retrieved too many tuples in a bounded sort");
1522 
1523  return false;
1524  }
1525  else
1526  {
1527  if (state->current <= 0)
1528  return false;
1529 
1530  /*
1531  * if all tuples are fetched already then we return last
1532  * tuple, else - tuple before last returned.
1533  */
1534  if (state->eof_reached)
1535  state->eof_reached = false;
1536  else
1537  {
1538  state->current--; /* last returned tuple */
1539  if (state->current <= 0)
1540  return false;
1541  }
1542  *stup = state->memtuples[state->current - 1];
1543  return true;
1544  }
1545  break;
1546 
1547  case TSS_SORTEDONTAPE:
1548  Assert(forward || state->base.sortopt & TUPLESORT_RANDOMACCESS);
1549  Assert(state->slabAllocatorUsed);
1550 
1551  /*
1552  * The slot that held the tuple that we returned in previous
1553  * gettuple call can now be reused.
1554  */
1555  if (state->lastReturnedTuple)
1556  {
1557  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1558  state->lastReturnedTuple = NULL;
1559  }
1560 
1561  if (forward)
1562  {
1563  if (state->eof_reached)
1564  return false;
1565 
1566  if ((tuplen = getlen(state->result_tape, true)) != 0)
1567  {
1568  READTUP(state, stup, state->result_tape, tuplen);
1569 
1570  /*
1571  * Remember the tuple we return, so that we can recycle
1572  * its memory on next call. (This can be NULL, in the
1573  * !state->tuples case).
1574  */
1575  state->lastReturnedTuple = stup->tuple;
1576 
1577  return true;
1578  }
1579  else
1580  {
1581  state->eof_reached = true;
1582  return false;
1583  }
1584  }
1585 
1586  /*
1587  * Backward.
1588  *
1589  * if all tuples are fetched already then we return last tuple,
1590  * else - tuple before last returned.
1591  */
1592  if (state->eof_reached)
1593  {
1594  /*
1595  * Seek position is pointing just past the zero tuplen at the
1596  * end of file; back up to fetch last tuple's ending length
1597  * word. If seek fails we must have a completely empty file.
1598  */
1599  nmoved = LogicalTapeBackspace(state->result_tape,
1600  2 * sizeof(unsigned int));
1601  if (nmoved == 0)
1602  return false;
1603  else if (nmoved != 2 * sizeof(unsigned int))
1604  elog(ERROR, "unexpected tape position");
1605  state->eof_reached = false;
1606  }
1607  else
1608  {
1609  /*
1610  * Back up and fetch previously-returned tuple's ending length
1611  * word. If seek fails, assume we are at start of file.
1612  */
1613  nmoved = LogicalTapeBackspace(state->result_tape,
1614  sizeof(unsigned int));
1615  if (nmoved == 0)
1616  return false;
1617  else if (nmoved != sizeof(unsigned int))
1618  elog(ERROR, "unexpected tape position");
1619  tuplen = getlen(state->result_tape, false);
1620 
1621  /*
1622  * Back up to get ending length word of tuple before it.
1623  */
1624  nmoved = LogicalTapeBackspace(state->result_tape,
1625  tuplen + 2 * sizeof(unsigned int));
1626  if (nmoved == tuplen + sizeof(unsigned int))
1627  {
1628  /*
1629  * We backed up over the previous tuple, but there was no
1630  * ending length word before it. That means that the prev
1631  * tuple is the first tuple in the file. It is now the
1632  * next to read in forward direction (not obviously right,
1633  * but that is what in-memory case does).
1634  */
1635  return false;
1636  }
1637  else if (nmoved != tuplen + 2 * sizeof(unsigned int))
1638  elog(ERROR, "bogus tuple length in backward scan");
1639  }
1640 
1641  tuplen = getlen(state->result_tape, false);
1642 
1643  /*
1644  * Now we have the length of the prior tuple, back up and read it.
1645  * Note: READTUP expects we are positioned after the initial
1646  * length word of the tuple, so back up to that point.
1647  */
1648  nmoved = LogicalTapeBackspace(state->result_tape,
1649  tuplen);
1650  if (nmoved != tuplen)
1651  elog(ERROR, "bogus tuple length in backward scan");
1652  READTUP(state, stup, state->result_tape, tuplen);
1653 
1654  /*
1655  * Remember the tuple we return, so that we can recycle its memory
1656  * on next call. (This can be NULL, in the Datum case).
1657  */
1658  state->lastReturnedTuple = stup->tuple;
1659 
1660  return true;
1661 
1662  case TSS_FINALMERGE:
1663  Assert(forward);
1664  /* We are managing memory ourselves, with the slab allocator. */
1665  Assert(state->slabAllocatorUsed);
1666 
1667  /*
1668  * The slab slot holding the tuple that we returned in previous
1669  * gettuple call can now be reused.
1670  */
1671  if (state->lastReturnedTuple)
1672  {
1673  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1674  state->lastReturnedTuple = NULL;
1675  }
1676 
1677  /*
1678  * This code should match the inner loop of mergeonerun().
1679  */
1680  if (state->memtupcount > 0)
1681  {
1682  int srcTapeIndex = state->memtuples[0].srctape;
1683  LogicalTape *srcTape = state->inputTapes[srcTapeIndex];
1684  SortTuple newtup;
1685 
1686  *stup = state->memtuples[0];
1687 
1688  /*
1689  * Remember the tuple we return, so that we can recycle its
1690  * memory on next call. (This can be NULL, in the Datum case).
1691  */
1692  state->lastReturnedTuple = stup->tuple;
1693 
1694  /*
1695  * Pull next tuple from tape, and replace the returned tuple
1696  * at top of the heap with it.
1697  */
1698  if (!mergereadnext(state, srcTape, &newtup))
1699  {
1700  /*
1701  * If no more data, we've reached end of run on this tape.
1702  * Remove the top node from the heap.
1703  */
1705  state->nInputRuns--;
1706 
1707  /*
1708  * Close the tape. It'd go away at the end of the sort
1709  * anyway, but better to release the memory early.
1710  */
1711  LogicalTapeClose(srcTape);
1712  return true;
1713  }
1714  newtup.srctape = srcTapeIndex;
1716  return true;
1717  }
1718  return false;
1719 
1720  default:
1721  elog(ERROR, "invalid tuplesort state");
1722  return false; /* keep compiler quiet */
1723  }
1724 }
size_t LogicalTapeBackspace(LogicalTape *lt, size_t size)
Definition: logtape.c:1062
void LogicalTapeClose(LogicalTape *lt)
Definition: logtape.c:733
int srctape
Definition: tuplesort.h:141
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:2809
static unsigned int getlen(LogicalTape *tape, bool eofOK)
Definition: tuplesort.c:2891
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:399
#define WORKER(state)
Definition: tuplesort.c:405
static bool mergereadnext(Tuplesortstate *state, LogicalTape *srcTape, SortTuple *stup)
Definition: tuplesort.c:2317
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:384
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:2833

References Assert(), elog(), ERROR, getlen(), LogicalTapeBackspace(), LogicalTapeClose(), mergereadnext(), READTUP, RELEASE_SLAB_SLOT, SortTuple::srctape, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, SortTuple::tuple, tuplesort_heap_delete_top(), tuplesort_heap_replace_top(), TUPLESORT_RANDOMACCESS, and WORKER.

Referenced by tuplesort_getdatum(), tuplesort_getheaptuple(), tuplesort_getindextuple(), tuplesort_gettupleslot(), and tuplesort_skiptuples().

◆ tuplesort_gettupleslot()

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

Definition at line 780 of file tuplesortvariants.c.

782 {
784  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
785  SortTuple stup;
786 
787  if (!tuplesort_gettuple_common(state, forward, &stup))
788  stup.tuple = NULL;
789 
790  MemoryContextSwitchTo(oldcontext);
791 
792  if (stup.tuple)
793  {
794  /* Record abbreviated key for caller */
795  if (base->sortKeys->abbrev_converter && abbrev)
796  *abbrev = stup.datum1;
797 
798  if (copy)
800 
801  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
802  return true;
803  }
804  else
805  {
806  ExecClearTuple(slot);
807  return false;
808  }
809 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1447
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1536
Datum datum1
Definition: tuplesort.h:139
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:432

References SortSupportData::abbrev_converter, SortTuple::datum1, ExecClearTuple(), ExecStoreMinimalTuple(), heap_copy_minimal_tuple(), MemoryContextSwitchTo(), TuplesortPublic::sortcontext, TuplesortPublic::sortKeys, SortTuple::tuple, tuplesort_gettuple_common(), and TuplesortstateGetPublic.

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

◆ tuplesort_initialize_shared()

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

Definition at line 2973 of file tuplesort.c.

2974 {
2975  int i;
2976 
2977  Assert(nWorkers > 0);
2978 
2979  SpinLockInit(&shared->mutex);
2980  shared->currentWorker = 0;
2981  shared->workersFinished = 0;
2982  SharedFileSetInit(&shared->fileset, seg);
2983  shared->nTapes = nWorkers;
2984  for (i = 0; i < nWorkers; i++)
2985  {
2986  shared->tapes[i].firstblocknumber = 0L;
2987  }
2988 }
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:44
#define SpinLockInit(lock)
Definition: spin.h:60
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:370
int workersFinished
Definition: tuplesort.c:358
int nTapes
Definition: tuplesort.c:364
slock_t mutex
Definition: tuplesort.c:347
int currentWorker
Definition: tuplesort.c:357
int64 firstblocknumber
Definition: logtape.h:54

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

Referenced by _bt_begin_parallel().

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

Definition at line 2470 of file tuplesort.c.

2471 {
2472  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2473 
2474  Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2475 
2476  switch (state->status)
2477  {
2478  case TSS_SORTEDINMEM:
2479  state->markpos_offset = state->current;
2480  state->markpos_eof = state->eof_reached;
2481  break;
2482  case TSS_SORTEDONTAPE:
2483  LogicalTapeTell(state->result_tape,
2484  &state->markpos_block,
2485  &state->markpos_offset);
2486  state->markpos_eof = state->eof_reached;
2487  break;
2488  default:
2489  elog(ERROR, "invalid tuplesort state");
2490  break;
2491  }
2492 
2493  MemoryContextSwitchTo(oldcontext);
2494 }
void LogicalTapeTell(LogicalTape *lt, int64 *blocknum, int *offset)
Definition: logtape.c:1162

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

Referenced by ExecSortMarkPos().

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 1801 of file tuplesort.c.

1802 {
1803  int mOrder;
1804 
1805  /*----------
1806  * In the merge phase, we need buffer space for each input and output tape.
1807  * Each pass in the balanced merge algorithm reads from M input tapes, and
1808  * writes to N output tapes. Each tape consumes TAPE_BUFFER_OVERHEAD bytes
1809  * of memory. In addition to that, we want MERGE_BUFFER_SIZE workspace per
1810  * input tape.
1811  *
1812  * totalMem = M * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE) +
1813  * N * TAPE_BUFFER_OVERHEAD
1814  *
1815  * Except for the last and next-to-last merge passes, where there can be
1816  * fewer tapes left to process, M = N. We choose M so that we have the
1817  * desired amount of memory available for the input buffers
1818  * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE), given the total memory
1819  * available for the tape buffers (allowedMem).
1820  *
1821  * Note: you might be thinking we need to account for the memtuples[]
1822  * array in this calculation, but we effectively treat that as part of the
1823  * MERGE_BUFFER_SIZE workspace.
1824  *----------
1825  */
1826  mOrder = allowedMem /
1828 
1829  /*
1830  * Even in minimum memory, use at least a MINORDER merge. On the other
1831  * hand, even when we have lots of memory, do not use more than a MAXORDER
1832  * merge. Tapes are pretty cheap, but they're not entirely free. Each
1833  * additional tape reduces the amount of memory available to build runs,
1834  * which in turn can cause the same sort to need more runs, which makes
1835  * merging slower even if it can still be done in a single pass. Also,
1836  * high order merges are quite slow due to CPU cache effects; it can be
1837  * faster to pay the I/O cost of a multi-pass merge than to perform a
1838  * single merge pass across many hundreds of tapes.
1839  */
1840  mOrder = Max(mOrder, MINORDER);
1841  mOrder = Min(mOrder, MAXORDER);
1842 
1843  return mOrder;
1844 }
#define Min(x, y)
Definition: c.h:993
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:182
#define MAXORDER
Definition: tuplesort.c:181
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:183
#define MINORDER
Definition: tuplesort.c:180

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

Referenced by cost_tuplesort(), and inittapes().

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

Definition at line 2578 of file tuplesort.c.

2579 {
2580  switch (m)
2581  {
2583  return "still in progress";
2585  return "top-N heapsort";
2586  case SORT_TYPE_QUICKSORT:
2587  return "quicksort";
2589  return "external sort";
2591  return "external merge";
2592  }
2593 
2594  return "unknown";
2595 }

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

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

Definition at line 1382 of file tuplesort.c.

1383 {
1384  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1385 
1386 #ifdef TRACE_SORT
1387  if (trace_sort)
1388  elog(LOG, "performsort of worker %d starting: %s",
1389  state->worker, pg_rusage_show(&state->ru_start));
1390 #endif
1391 
1392  switch (state->status)
1393  {
1394  case TSS_INITIAL:
1395 
1396  /*
1397  * We were able to accumulate all the tuples within the allowed
1398  * amount of memory, or leader to take over worker tapes
1399  */
1400  if (SERIAL(state))
1401  {
1402  /* Just qsort 'em and we're done */
1404  state->status = TSS_SORTEDINMEM;
1405  }
1406  else if (WORKER(state))
1407  {
1408  /*
1409  * Parallel workers must still dump out tuples to tape. No
1410  * merge is required to produce single output run, though.
1411  */
1412  inittapes(state, false);
1413  dumptuples(state, true);
1415  state->status = TSS_SORTEDONTAPE;
1416  }
1417  else
1418  {
1419  /*
1420  * Leader will take over worker tapes and merge worker runs.
1421  * Note that mergeruns sets the correct state->status.
1422  */
1424  mergeruns(state);
1425  }
1426  state->current = 0;
1427  state->eof_reached = false;
1428  state->markpos_block = 0L;
1429  state->markpos_offset = 0;
1430  state->markpos_eof = false;
1431  break;
1432 
1433  case TSS_BOUNDED:
1434 
1435  /*
1436  * We were able to accumulate all the tuples required for output
1437  * in memory, using a heap to eliminate excess tuples. Now we
1438  * have to transform the heap to a properly-sorted array. Note
1439  * that sort_bounded_heap sets the correct state->status.
1440  */
1442  state->current = 0;
1443  state->eof_reached = false;
1444  state->markpos_offset = 0;
1445  state->markpos_eof = false;
1446  break;
1447 
1448  case TSS_BUILDRUNS:
1449 
1450  /*
1451  * Finish tape-based sort. First, flush all tuples remaining in
1452  * memory out to tape; then merge until we have a single remaining
1453  * run (or, if !randomAccess and !WORKER(), one run per tape).
1454  * Note that mergeruns sets the correct state->status.
1455  */
1456  dumptuples(state, true);
1457  mergeruns(state);
1458  state->eof_reached = false;
1459  state->markpos_block = 0L;
1460  state->markpos_offset = 0;
1461  state->markpos_eof = false;
1462  break;
1463 
1464  default:
1465  elog(ERROR, "invalid tuplesort state");
1466  break;
1467  }
1468 
1469 #ifdef TRACE_SORT
1470  if (trace_sort)
1471  {
1472  if (state->status == TSS_FINALMERGE)
1473  elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
1474  state->worker, state->nInputTapes,
1475  pg_rusage_show(&state->ru_start));
1476  else
1477  elog(LOG, "performsort of worker %d done: %s",
1478  state->worker, pg_rusage_show(&state->ru_start));
1479  }
1480 #endif
1481 
1482  MemoryContextSwitchTo(oldcontext);
1483 }
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define SERIAL(state)
Definition: tuplesort.c:404
static void sort_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:2671
@ TSS_INITIAL
Definition: tuplesort.c:160
@ TSS_BUILDRUNS
Definition: tuplesort.c:162
@ TSS_BOUNDED
Definition: tuplesort.c:161
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:3104
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:2711
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:1888
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:3082
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2042
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2336

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

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

◆ tuplesort_putdatum()

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

Definition at line 716 of file tuplesortvariants.c.

717 {
721  SortTuple stup;
722 
723  /*
724  * Pass-by-value types or null values are just stored directly in
725  * stup.datum1 (and stup.tuple is not used and set to NULL).
726  *
727  * Non-null pass-by-reference values need to be copied into memory we
728  * control, and possibly abbreviated. The copied value is pointed to by
729  * stup.tuple and is treated as the canonical copy (e.g. to return via
730  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
731  * abbreviated value if abbreviation is happening, otherwise it's
732  * identical to stup.tuple.
733  */
734 
735  if (isNull || !base->tuples)
736  {
737  /*
738  * Set datum1 to zeroed representation for NULLs (to be consistent,
739  * and to support cheap inequality tests for NULL abbreviated keys).
740  */
741  stup.datum1 = !isNull ? val : (Datum) 0;
742  stup.isnull1 = isNull;
743  stup.tuple = NULL; /* no separate storage */
744  }
745  else
746  {
747  stup.isnull1 = false;
748  stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
749  stup.tuple = DatumGetPointer(stup.datum1);
750  }
751 
753  base->tuples &&
754  base->sortKeys->abbrev_converter && !isNull);
755 
756  MemoryContextSwitchTo(oldcontext);
757 }
uintptr_t Datum
Definition: postgres.h:64
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
MemoryContext tuplecontext
Definition: tuplesort.h:210
void tuplesort_puttuple_common(Tuplesortstate *state, SortTuple *tuple, bool useAbbrev)
Definition: tuplesort.c:1187

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, datumCopy(), DatumGetPointer(), if(), MemoryContextSwitchTo(), TuplesortPublic::sortKeys, TuplesortPublic::tuplecontext, TuplesortPublic::tuples, tuplesort_puttuple_common(), TuplesortstateGetPublic, and val.

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

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 649 of file tuplesortvariants.c.

650 {
651  SortTuple stup;
655 
656  /* copy the tuple into sort storage */
657  tup = heap_copytuple(tup);
658  stup.tuple = (void *) tup;
659 
660  /*
661  * set up first-column key value, and potentially abbreviate, if it's a
662  * simple column
663  */
664  if (base->haveDatum1)
665  {
666  stup.datum1 = heap_getattr(tup,
667  arg->indexInfo->ii_IndexAttrNumbers[0],
668  arg->tupDesc,
669  &stup.isnull1);
670  }
671 
673  base->haveDatum1 &&
674  base->sortKeys->abbrev_converter &&
675  !stup.isnull1);
676 
677  MemoryContextSwitchTo(oldcontext);
678 }
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:777
static Datum heap_getattr(HeapTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: htup_details.h:792
bool isnull1
Definition: tuplesort.h:140

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, SortTuple::datum1, TuplesortPublic::haveDatum1, heap_copytuple(), heap_getattr(), SortTuple::isnull1, MemoryContextSwitchTo(), TuplesortPublic::sortKeys, SortTuple::tuple, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), and TuplesortstateGetPublic.

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_putindextuplevalues()

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

Definition at line 685 of file tuplesortvariants.c.

688 {
689  SortTuple stup;
690  IndexTuple tuple;
693 
695  isnull, base->tuplecontext);
696  tuple = ((IndexTuple) stup.tuple);
697  tuple->t_tid = *self;
698  /* set up first-column key value */
699  stup.datum1 = index_getattr(tuple,
700  1,
701  RelationGetDescr(arg->indexRel),
702  &stup.isnull1);
703 
705  base->sortKeys &&
706  base->sortKeys->abbrev_converter &&
707  !stup.isnull1);
708 }
static Datum values[MAXATTR]
Definition: bootstrap.c:156
IndexTuple index_form_tuple_context(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull, MemoryContext context)
Definition: indextuple.c:65
IndexTupleData * IndexTuple
Definition: itup.h:53
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: itup.h:117
#define RelationGetDescr(relation)
Definition: rel.h:530
ItemPointerData t_tid
Definition: itup.h:37

References SortSupportData::abbrev_converter, arg, TuplesortPublic::arg, SortTuple::datum1, index_form_tuple_context(), index_getattr(), SortTuple::isnull1, RelationGetDescr, TuplesortPublic::sortKeys, IndexTupleData::t_tid, SortTuple::tuple, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), TuplesortstateGetPublic, and values.

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

◆ tuplesort_puttuple_common()

void tuplesort_puttuple_common ( Tuplesortstate state,
SortTuple tuple,
bool  useAbbrev 
)

Definition at line 1187 of file tuplesort.c.

1188 {
1189  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1190 
1191  Assert(!LEADER(state));
1192 
1193  /* Count the size of the out-of-line data */
1194  if (tuple->tuple != NULL)
1196 
1197  if (!useAbbrev)
1198  {
1199  /*
1200  * Leave ordinary Datum representation, or NULL value. If there is a
1201  * converter it won't expect NULL values, and cost model is not
1202  * required to account for NULL, so in that case we avoid calling
1203  * converter and just set datum1 to zeroed representation (to be
1204  * consistent, and to support cheap inequality tests for NULL
1205  * abbreviated keys).
1206  */
1207  }
1208  else if (!consider_abort_common(state))
1209  {
1210  /* Store abbreviated key representation */
1211  tuple->datum1 = state->base.sortKeys->abbrev_converter(tuple->datum1,
1212  state->base.sortKeys);
1213  }
1214  else
1215  {
1216  /*
1217  * Set state to be consistent with never trying abbreviation.
1218  *
1219  * Alter datum1 representation in already-copied tuples, so as to
1220  * ensure a consistent representation (current tuple was just
1221  * handled). It does not matter if some dumped tuples are already
1222  * sorted on tape, since serialized tuples lack abbreviated keys
1223  * (TSS_BUILDRUNS state prevents control reaching here in any case).
1224  */
1225  REMOVEABBREV(state, state->memtuples, state->memtupcount);
1226  }
1227 
1228  switch (state->status)
1229  {
1230  case TSS_INITIAL:
1231 
1232  /*
1233  * Save the tuple into the unsorted array. First, grow the array
1234  * as needed. Note that we try to grow the array when there is
1235  * still one free slot remaining --- if we fail, there'll still be
1236  * room to store the incoming tuple, and then we'll switch to
1237  * tape-based operation.
1238  */
1239  if (state->memtupcount >= state->memtupsize - 1)
1240  {
1241  (void) grow_memtuples(state);
1242  Assert(state->memtupcount < state->memtupsize);
1243  }
1244  state->memtuples[state->memtupcount++] = *tuple;
1245 
1246  /*
1247  * Check if it's time to switch over to a bounded heapsort. We do
1248  * so if the input tuple count exceeds twice the desired tuple
1249  * count (this is a heuristic for where heapsort becomes cheaper
1250  * than a quicksort), or if we've just filled workMem and have
1251  * enough tuples to meet the bound.
1252  *
1253  * Note that once we enter TSS_BOUNDED state we will always try to
1254  * complete the sort that way. In the worst case, if later input
1255  * tuples are larger than earlier ones, this might cause us to
1256  * exceed workMem significantly.
1257  */
1258  if (state->bounded &&
1259  (state->memtupcount > state->bound * 2 ||
1260  (state->memtupcount > state->bound && LACKMEM(state))))
1261  {
1262 #ifdef TRACE_SORT
1263  if (trace_sort)
1264  elog(LOG, "switching to bounded heapsort at %d tuples: %s",
1265  state->memtupcount,
1266  pg_rusage_show(&state->ru_start));
1267 #endif
1269  MemoryContextSwitchTo(oldcontext);
1270  return;
1271  }
1272 
1273  /*
1274  * Done if we still fit in available memory and have array slots.
1275  */
1276  if (state->memtupcount < state->memtupsize && !LACKMEM(state))
1277  {
1278  MemoryContextSwitchTo(oldcontext);
1279  return;
1280  }
1281 
1282  /*
1283  * Nope; time to switch to tape-based operation.
1284  */
1285  inittapes(state, true);
1286 
1287  /*
1288  * Dump all tuples.
1289  */
1290  dumptuples(state, false);
1291  break;
1292 
1293  case TSS_BOUNDED:
1294 
1295  /*
1296  * We don't want to grow the array here, so check whether the new
1297  * tuple can be discarded before putting it in. This should be a
1298  * good speed optimization, too, since when there are many more
1299  * input tuples than the bound, most input tuples can be discarded
1300  * with just this one comparison. Note that because we currently
1301  * have the sort direction reversed, we must check for <= not >=.
1302  */
1303  if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
1304  {
1305  /* new tuple <= top of the heap, so we can discard it */
1306  free_sort_tuple(state, tuple);
1308  }
1309  else
1310  {
1311  /* discard top of heap, replacing it with the new tuple */
1312  free_sort_tuple(state, &state->memtuples[0]);
1314  }
1315  break;
1316 
1317  case TSS_BUILDRUNS:
1318 
1319  /*
1320  * Save the tuple into the unsorted array (there must be space)
1321  */
1322  state->memtuples[state->memtupcount++] = *tuple;
1323 
1324  /*
1325  * If we are over the memory limit, dump all tuples.
1326  */
1327  dumptuples(state, false);
1328  break;
1329 
1330  default:
1331  elog(ERROR, "invalid tuplesort state");
1332  break;
1333  }
1334  MemoryContextSwitchTo(oldcontext);
1335 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:630
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:121
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:397
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:3163
#define REMOVEABBREV(state, stup, count)
Definition: tuplesort.c:396
#define LACKMEM(state)
Definition: tuplesort.c:401
#define USEMEM(state, amt)
Definition: tuplesort.c:402
static bool grow_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:1070
static void make_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:2622
#define LEADER(state)
Definition: tuplesort.c:406
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1338

References Assert(), CHECK_FOR_INTERRUPTS, COMPARETUP, consider_abort_common(), SortTuple::datum1, dumptuples(), elog(), ERROR, free_sort_tuple(), GetMemoryChunkSpace(), grow_memtuples(), inittapes(), LACKMEM, LEADER, LOG, make_bounded_heap(), MemoryContextSwitchTo(), pg_rusage_show(), REMOVEABBREV, trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_INITIAL, SortTuple::tuple, tuplesort_heap_replace_top(), and USEMEM.

Referenced by tuplesort_putdatum(), tuplesort_putheaptuple(), tuplesort_putindextuplevalues(), and tuplesort_puttupleslot().

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

Definition at line 616 of file tuplesortvariants.c.

617 {
620  TupleDesc tupDesc = (TupleDesc) base->arg;
621  SortTuple stup;
622  MinimalTuple tuple;
623  HeapTupleData htup;
624 
625  /* copy the tuple into sort storage */
626  tuple = ExecCopySlotMinimalTuple(slot);
627  stup.tuple = (void *) tuple;
628  /* set up first-column key value */
629  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
630  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
631  stup.datum1 = heap_getattr(&htup,
632  base->sortKeys[0].ssup_attno,
633  tupDesc,
634  &stup.isnull1);
635 
637  base->sortKeys->abbrev_converter &&
638  !stup.isnull1);
639 
640  MemoryContextSwitchTo(oldcontext);
641 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:617
struct TupleDescData * TupleDesc
Definition: tupdesc.h:89
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:470

References SortSupportData::abbrev_converter, TuplesortPublic::arg, ExecCopySlotMinimalTuple(), heap_getattr(), MemoryContextSwitchTo(), MINIMAL_TUPLE_OFFSET, TuplesortPublic::sortKeys, SortSupportData::ssup_attno, MinimalTupleData::t_len, TuplesortPublic::tuplecontext, tuplesort_puttuple_common(), and TuplesortstateGetPublic.

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

◆ tuplesort_readtup_alloc()

void* tuplesort_readtup_alloc ( Tuplesortstate state,
Size  tuplen 
)

Definition at line 2918 of file tuplesort.c.

2919 {
2920  SlabSlot *buf;
2921 
2922  /*
2923  * We pre-allocate enough slots in the slab arena that we should never run
2924  * out.
2925  */
2926  Assert(state->slabFreeHead);
2927 
2928  if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
2929  return MemoryContextAlloc(state->base.sortcontext, tuplen);
2930  else
2931  {
2932  buf = state->slabFreeHead;
2933  /* Reuse this slot */
2934  state->slabFreeHead = buf->nextfree;
2935 
2936  return buf;
2937  }
2938 }
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1021
static char * buf
Definition: pg_test_fsync.c:73
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:146

References Assert(), buf, MemoryContextAlloc(), and SLAB_SLOT_SIZE.

Referenced by readtup_cluster(), readtup_datum(), readtup_heap(), and readtup_index().

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

Definition at line 2437 of file tuplesort.c.

2438 {
2439  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2440 
2441  Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2442 
2443  switch (state->status)
2444  {
2445  case TSS_SORTEDINMEM:
2446  state->current = 0;
2447  state->eof_reached = false;
2448  state->markpos_offset = 0;
2449  state->markpos_eof = false;
2450  break;
2451  case TSS_SORTEDONTAPE:
2452  LogicalTapeRewindForRead(state->result_tape, 0);
2453  state->eof_reached = false;
2454  state->markpos_block = 0L;
2455  state->markpos_offset = 0;
2456  state->markpos_eof = false;
2457  break;
2458  default:
2459  elog(ERROR, "invalid tuplesort state");
2460  break;
2461  }
2462 
2463  MemoryContextSwitchTo(oldcontext);
2464 }
void LogicalTapeRewindForRead(LogicalTape *lt, size_t buffer_size)
Definition: logtape.c:846

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

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

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate state)

Definition at line 1037 of file tuplesort.c.

1038 {
1041 
1042  /*
1043  * After we've freed up per-batch memory, re-setup all of the state common
1044  * to both the first batch and any subsequent batch.
1045  */
1047 
1048  state->lastReturnedTuple = NULL;
1049  state->slabMemoryBegin = NULL;
1050  state->slabMemoryEnd = NULL;
1051  state->slabFreeHead = NULL;
1052 }

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

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

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

Definition at line 2501 of file tuplesort.c.

2502 {
2503  MemoryContext oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
2504 
2505  Assert(state->base.sortopt & TUPLESORT_RANDOMACCESS);
2506 
2507  switch (state->status)
2508  {
2509  case TSS_SORTEDINMEM:
2510  state->current = state->markpos_offset;
2511  state->eof_reached = state->markpos_eof;
2512  break;
2513  case TSS_SORTEDONTAPE:
2514  LogicalTapeSeek(state->result_tape,
2515  state->markpos_block,
2516  state->markpos_offset);
2517  state->eof_reached = state->markpos_eof;
2518  break;
2519  default:
2520  elog(ERROR, "invalid tuplesort state");
2521  break;
2522  }
2523 
2524  MemoryContextSwitchTo(oldcontext);
2525 }
void LogicalTapeSeek(LogicalTape *lt, int64 blocknum, int offset)
Definition: logtape.c:1133

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

Referenced by ExecSortRestrPos().

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

Definition at line 841 of file tuplesort.c.

842 {
843  /* Assert we're called before loading any tuples */
844  Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
845  /* Assert we allow bounded sorts */
846  Assert(state->base.sortopt & TUPLESORT_ALLOWBOUNDED);
847  /* Can't set the bound twice, either */
848  Assert(!state->bounded);
849  /* Also, this shouldn't be called in a parallel worker */
850  Assert(!WORKER(state));
851 
852  /* Parallel leader allows but ignores hint */
853  if (LEADER(state))
854  return;
855 
856 #ifdef DEBUG_BOUNDED_SORT
857  /* Honor GUC setting that disables the feature (for easy testing) */
858  if (!optimize_bounded_sort)
859  return;
860 #endif
861 
862  /* We want to be able to compute bound * 2, so limit the setting */
863  if (bound > (int64) (INT_MAX / 2))
864  return;
865 
866  state->bounded = true;
867  state->bound = (int) bound;
868 
869  /*
870  * Bounded sorts are not an effective target for abbreviated key
871  * optimization. Disable by setting state to be consistent with no
872  * abbreviation support.
873  */
874  state->base.sortKeys->abbrev_converter = NULL;
875  if (state->base.sortKeys->abbrev_full_comparator)
876  state->base.sortKeys->comparator = state->base.sortKeys->abbrev_full_comparator;
877 
878  /* Not strictly necessary, but be tidy */
879  state->base.sortKeys->abbrev_abort = NULL;
880  state->base.sortKeys->abbrev_full_comparator = NULL;
881 }
#define TUPLESORT_ALLOWBOUNDED
Definition: tuplesort.h:98

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

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

◆ tuplesort_skiptuples()

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

Definition at line 1733 of file tuplesort.c.

1734 {
1735  MemoryContext oldcontext;
1736 
1737  /*
1738  * We don't actually support backwards skip yet, because no callers need
1739  * it. The API is designed to allow for that later, though.
1740  */
1741  Assert(forward);
1742  Assert(ntuples >= 0);
1743  Assert(!WORKER(state));
1744 
1745  switch (state->status)
1746  {
1747  case TSS_SORTEDINMEM:
1748  if (state->memtupcount - state->current >= ntuples)
1749  {
1750  state->current += ntuples;
1751  return true;
1752  }
1753  state->current = state->memtupcount;
1754  state->eof_reached = true;
1755 
1756  /*
1757  * Complain if caller tries to retrieve more tuples than
1758  * originally asked for in a bounded sort. This is because
1759  * returning EOF here might be the wrong thing.
1760  */
1761  if (state->bounded && state->current >= state->bound)
1762  elog(ERROR, "retrieved too many tuples in a bounded sort");
1763 
1764  return false;
1765 
1766  case TSS_SORTEDONTAPE:
1767  case TSS_FINALMERGE:
1768 
1769  /*
1770  * We could probably optimize these cases better, but for now it's
1771  * not worth the trouble.
1772  */
1773  oldcontext = MemoryContextSwitchTo(state->base.sortcontext);
1774  while (ntuples-- > 0)
1775  {
1776  SortTuple stup;
1777 
1778  if (!tuplesort_gettuple_common(state, forward, &stup))
1779  {
1780  MemoryContextSwitchTo(oldcontext);
1781  return false;
1782  }
1784  }
1785  MemoryContextSwitchTo(oldcontext);
1786  return true;
1787 
1788  default:
1789  elog(ERROR, "invalid tuplesort state");
1790  return false; /* keep compiler quiet */
1791  }
1792 }

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

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

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType  t)

Definition at line 2601 of file tuplesort.c.

2602 {
2604  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
2605 }

References Assert(), SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate state)

Definition at line 889 of file tuplesort.c.

890 {
891  return state->boundUsed;
892 }

Referenced by ExecIncrementalSort().