PostgreSQL Source Code  git master
tuplesort.c File Reference
#include "postgres.h"
#include <limits.h>
#include "access/hash.h"
#include "access/htup_details.h"
#include "access/nbtree.h"
#include "catalog/index.h"
#include "catalog/pg_am.h"
#include "commands/tablespace.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "pg_trace.h"
#include "utils/datum.h"
#include "utils/logtape.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/pg_rusage.h"
#include "utils/rel.h"
#include "utils/sortsupport.h"
#include "utils/tuplesort.h"
#include "qsort_tuple.c"
Include dependency graph for tuplesort.c:

Go to the source code of this file.

Data Structures

struct  SortTuple
 
union  SlabSlot
 
struct  Tuplesortstate
 
struct  Sharedsort
 

Macros

#define HEAP_SORT   0
 
#define INDEX_SORT   1
 
#define DATUM_SORT   2
 
#define CLUSTER_SORT   3
 
#define PARALLEL_SORT(state)
 
#define INITIAL_MEMTUPSIZE
 
#define SLAB_SLOT_SIZE   1024
 
#define MINORDER   6 /* minimum merge order */
 
#define MAXORDER   500 /* maximum merge order */
 
#define TAPE_BUFFER_OVERHEAD   BLCKSZ
 
#define MERGE_BUFFER_SIZE   (BLCKSZ * 32)
 
#define IS_SLAB_SLOT(state, tuple)
 
#define RELEASE_SLAB_SLOT(state, tuple)
 
#define COMPARETUP(state, a, b)   ((*(state)->comparetup) (a, b, state))
 
#define COPYTUP(state, stup, tup)   ((*(state)->copytup) (state, stup, tup))
 
#define WRITETUP(state, tape, stup)   ((*(state)->writetup) (state, tape, stup))
 
#define READTUP(state, stup, tape, len)   ((*(state)->readtup) (state, stup, tape, len))
 
#define LACKMEM(state)   ((state)->availMem < 0 && !(state)->slabAllocatorUsed)
 
#define USEMEM(state, amt)   ((state)->availMem -= (amt))
 
#define FREEMEM(state, amt)   ((state)->availMem += (amt))
 
#define SERIAL(state)   ((state)->shared == NULL)
 
#define WORKER(state)   ((state)->shared && (state)->worker != -1)
 
#define LEADER(state)   ((state)->shared && (state)->worker == -1)
 
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
 

Typedefs

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

Enumerations

enum  TupSortStatus {
  TSS_INITIAL, TSS_BOUNDED, TSS_BUILDRUNS, TSS_SORTEDINMEM,
  TSS_SORTEDONTAPE, TSS_FINALMERGE
}
 

Functions

static Tuplesortstatetuplesort_begin_common (int workMem, SortCoordinate coordinate, bool randomAccess)
 
static void tuplesort_begin_batch (Tuplesortstate *state)
 
static void puttuple_common (Tuplesortstate *state, SortTuple *tuple)
 
static bool consider_abort_common (Tuplesortstate *state)
 
static void inittapes (Tuplesortstate *state, bool mergeruns)
 
static void inittapestate (Tuplesortstate *state, int maxTapes)
 
static void selectnewtape (Tuplesortstate *state)
 
static void init_slab_allocator (Tuplesortstate *state, int numSlots)
 
static void mergeruns (Tuplesortstate *state)
 
static void mergeonerun (Tuplesortstate *state)
 
static void beginmerge (Tuplesortstate *state)
 
static bool mergereadnext (Tuplesortstate *state, int srcTape, SortTuple *stup)
 
static void dumptuples (Tuplesortstate *state, bool alltuples)
 
static void make_bounded_heap (Tuplesortstate *state)
 
static void sort_bounded_heap (Tuplesortstate *state)
 
static void tuplesort_sort_memtuples (Tuplesortstate *state)
 
static void tuplesort_heap_insert (Tuplesortstate *state, SortTuple *tuple)
 
static void tuplesort_heap_replace_top (Tuplesortstate *state, SortTuple *tuple)
 
static void tuplesort_heap_delete_top (Tuplesortstate *state)
 
static void reversedirection (Tuplesortstate *state)
 
static unsigned int getlen (Tuplesortstate *state, int tapenum, bool eofOK)
 
static void markrunend (Tuplesortstate *state, int tapenum)
 
static void * readtup_alloc (Tuplesortstate *state, Size tuplen)
 
static int comparetup_heap (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_heap (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_heap (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_heap (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static int comparetup_cluster (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_cluster (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_cluster (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_cluster (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static int comparetup_index_btree (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static int comparetup_index_hash (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_index (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_index (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_index (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static int comparetup_datum (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_datum (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_datum (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_datum (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static int worker_get_identifier (Tuplesortstate *state)
 
static void worker_freeze_result_tape (Tuplesortstate *state)
 
static void worker_nomergeruns (Tuplesortstate *state)
 
static void leader_takeover_tapes (Tuplesortstate *state)
 
static void free_sort_tuple (Tuplesortstate *state, SortTuple *stup)
 
static void tuplesort_free (Tuplesortstate *state)
 
static void tuplesort_updatemax (Tuplesortstate *state)
 
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)
 
bool tuplesort_used_bound (Tuplesortstate *state)
 
void tuplesort_end (Tuplesortstate *state)
 
void tuplesort_reset (Tuplesortstate *state)
 
static bool grow_memtuples (Tuplesortstate *state)
 
void tuplesort_puttupleslot (Tuplesortstate *state, TupleTableSlot *slot)
 
void tuplesort_putheaptuple (Tuplesortstate *state, HeapTuple tup)
 
void tuplesort_putindextuplevalues (Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
 
void tuplesort_putdatum (Tuplesortstate *state, Datum val, bool isNull)
 
void tuplesort_performsort (Tuplesortstate *state)
 
static bool tuplesort_gettuple_common (Tuplesortstate *state, bool forward, SortTuple *stup)
 
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)
 
int tuplesort_merge_order (int64 allowedMem)
 
void tuplesort_rescan (Tuplesortstate *state)
 
void tuplesort_markpos (Tuplesortstate *state)
 
void tuplesort_restorepos (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)
 
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)
 

Variables

bool trace_sort = false
 

Macro Definition Documentation

◆ CLUSTER_SORT

#define CLUSTER_SORT   3

Definition at line 122 of file tuplesort.c.

Referenced by tuplesort_begin_cluster().

◆ COMPARETUP

#define COMPARETUP (   state,
  a,
 
)    ((*(state)->comparetup) (a, b, state))

◆ COPYTUP

#define COPYTUP (   state,
  stup,
  tup 
)    ((*(state)->copytup) (state, stup, tup))

Definition at line 542 of file tuplesort.c.

Referenced by tuplesort_putheaptuple(), and tuplesort_puttupleslot().

◆ DATUM_SORT

#define DATUM_SORT   2

Definition at line 121 of file tuplesort.c.

Referenced by tuplesort_begin_datum().

◆ FREEMEM

#define FREEMEM (   state,
  amt 
)    ((state)->availMem += (amt))

◆ HEAP_SORT

#define HEAP_SORT   0

Definition at line 119 of file tuplesort.c.

Referenced by tuplesort_begin_heap().

◆ INDEX_SORT

#define INDEX_SORT   1

Definition at line 120 of file tuplesort.c.

Referenced by tuplesort_begin_index_btree().

◆ INITIAL_MEMTUPSIZE

#define INITIAL_MEMTUPSIZE
Value:
Max(1024, \
#define ALLOCSET_SEPARATE_THRESHOLD
Definition: memutils.h:219
#define Max(x, y)
Definition: c.h:914

Definition at line 135 of file tuplesort.c.

Referenced by tuplesort_begin_batch(), and tuplesort_begin_common().

◆ IS_SLAB_SLOT

#define IS_SLAB_SLOT (   state,
  tuple 
)
Value:
((char *) (tuple) >= (state)->slabMemoryBegin && \
(char *) (tuple) < (state)->slabMemoryEnd)
Definition: regguts.h:298

Definition at line 521 of file tuplesort.c.

◆ LACKMEM

#define LACKMEM (   state)    ((state)->availMem < 0 && !(state)->slabAllocatorUsed)

Definition at line 545 of file tuplesort.c.

Referenced by dumptuples(), grow_memtuples(), puttuple_common(), and tuplesort_begin_batch().

◆ LEADER

#define LEADER (   state)    ((state)->shared && (state)->worker == -1)

◆ LogicalTapeReadExact

#define LogicalTapeReadExact (   tapeset,
  tapenum,
  ptr,
  len 
)
Value:
do { \
if (LogicalTapeRead(tapeset, tapenum, ptr, len) != (size_t) (len)) \
elog(ERROR, "unexpected end of data"); \
} while(0)
size_t LogicalTapeRead(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:956
#define ERROR
Definition: elog.h:43

Definition at line 602 of file tuplesort.c.

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

◆ MAXORDER

#define MAXORDER   500 /* maximum merge order */

Definition at line 230 of file tuplesort.c.

Referenced by tuplesort_merge_order().

◆ MERGE_BUFFER_SIZE

#define MERGE_BUFFER_SIZE   (BLCKSZ * 32)

Definition at line 232 of file tuplesort.c.

Referenced by tuplesort_merge_order().

◆ MINORDER

#define MINORDER   6 /* minimum merge order */

Definition at line 229 of file tuplesort.c.

Referenced by inittapes(), and tuplesort_merge_order().

◆ PARALLEL_SORT

#define PARALLEL_SORT (   state)
Value:
((state)->shared == NULL ? 0 : \
(state)->worker >= 0 ? 1 : 2)
Definition: regguts.h:298

Definition at line 125 of file tuplesort.c.

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

◆ READTUP

#define READTUP (   state,
  stup,
  tape,
  len 
)    ((*(state)->readtup) (state, stup, tape, len))

Definition at line 544 of file tuplesort.c.

Referenced by mergereadnext(), and tuplesort_gettuple_common().

◆ RELEASE_SLAB_SLOT

#define RELEASE_SLAB_SLOT (   state,
  tuple 
)
Value:
do { \
SlabSlot *buf = (SlabSlot *) tuple; \
\
if (IS_SLAB_SLOT((state), buf)) \
{ \
buf->nextfree = (state)->slabFreeHead; \
(state)->slabFreeHead = buf; \
pfree(buf); \
} while(0)
void pfree(void *pointer)
Definition: mcxt.c:1056
static char * buf
Definition: pg_test_fsync.c:67
Definition: regguts.h:298
#define IS_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:521

Definition at line 529 of file tuplesort.c.

Referenced by mergeonerun(), and tuplesort_gettuple_common().

◆ SERIAL

#define SERIAL (   state)    ((state)->shared == NULL)

◆ SLAB_SLOT_SIZE

#define SLAB_SLOT_SIZE   1024

Definition at line 196 of file tuplesort.c.

Referenced by init_slab_allocator(), and readtup_alloc().

◆ TAPE_BUFFER_OVERHEAD

#define TAPE_BUFFER_OVERHEAD   BLCKSZ

Definition at line 231 of file tuplesort.c.

Referenced by inittapestate(), mergeruns(), and tuplesort_merge_order().

◆ USEMEM

#define USEMEM (   state,
  amt 
)    ((state)->availMem -= (amt))

◆ WORKER

◆ WRITETUP

#define WRITETUP (   state,
  tape,
  stup 
)    ((*(state)->writetup) (state, tape, stup))

Definition at line 543 of file tuplesort.c.

Referenced by dumptuples(), and mergeonerun().

Typedef Documentation

◆ SlabSlot

typedef union SlabSlot SlabSlot

◆ SortTupleComparator

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

Definition at line 234 of file tuplesort.c.

Enumeration Type Documentation

◆ TupSortStatus

Enumerator
TSS_INITIAL 
TSS_BOUNDED 
TSS_BUILDRUNS 
TSS_SORTEDINMEM 
TSS_SORTEDONTAPE 
TSS_FINALMERGE 

Definition at line 208 of file tuplesort.c.

209 {
210  TSS_INITIAL, /* Loading tuples; still within memory limit */
211  TSS_BOUNDED, /* Loading tuples into bounded-size heap */
212  TSS_BUILDRUNS, /* Loading tuples; writing to tape */
213  TSS_SORTEDINMEM, /* Sort completed entirely in memory */
214  TSS_SORTEDONTAPE, /* Sort completed, final run is on tape */
215  TSS_FINALMERGE /* Performing final merge on-the-fly */
216 } TupSortStatus;
TupSortStatus
Definition: tuplesort.c:208

Function Documentation

◆ beginmerge()

static void beginmerge ( Tuplesortstate state)
static

Definition at line 3025 of file tuplesort.c.

References Tuplesortstate::activeTapes, Assert, Tuplesortstate::maxTapes, Tuplesortstate::memtupcount, Tuplesortstate::mergeactive, mergereadnext(), SortTuple::srctape, Tuplesortstate::tapeRange, Tuplesortstate::tp_dummy, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, and tuplesort_heap_insert().

Referenced by mergeonerun(), and mergeruns().

3026 {
3027  int activeTapes;
3028  int tapenum;
3029  int srcTape;
3030 
3031  /* Heap should be empty here */
3032  Assert(state->memtupcount == 0);
3033 
3034  /* Adjust run counts and mark the active tapes */
3035  memset(state->mergeactive, 0,
3036  state->maxTapes * sizeof(*state->mergeactive));
3037  activeTapes = 0;
3038  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
3039  {
3040  if (state->tp_dummy[tapenum] > 0)
3041  state->tp_dummy[tapenum]--;
3042  else
3043  {
3044  Assert(state->tp_runs[tapenum] > 0);
3045  state->tp_runs[tapenum]--;
3046  srcTape = state->tp_tapenum[tapenum];
3047  state->mergeactive[srcTape] = true;
3048  activeTapes++;
3049  }
3050  }
3051  Assert(activeTapes > 0);
3052  state->activeTapes = activeTapes;
3053 
3054  /* Load the merge heap with the first tuple from each input tape */
3055  for (srcTape = 0; srcTape < state->maxTapes; srcTape++)
3056  {
3057  SortTuple tup;
3058 
3059  if (mergereadnext(state, srcTape, &tup))
3060  {
3061  tup.srctape = srcTape;
3062  tuplesort_heap_insert(state, &tup);
3063  }
3064  }
3065 }
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3507
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:3073
#define Assert(condition)
Definition: c.h:738
int srctape
Definition: tuplesort.c:182
int * tp_dummy
Definition: tuplesort.c:387
int * tp_tapenum
Definition: tuplesort.c:388
bool * mergeactive
Definition: tuplesort.c:376

◆ comparetup_cluster()

static int comparetup_cluster ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

Definition at line 3878 of file tuplesort.c.

References SortSupportData::abbrev_converter, ApplySortAbbrevFullComparator(), ApplySortComparator(), compare(), SortTuple::datum1, Tuplesortstate::estate, ExecStoreHeapTuple(), FormIndexDatum(), GetPerTupleExprContext, heap_getattr, IndexInfo::ii_Expressions, IndexInfo::ii_IndexAttrNumbers, INDEX_MAX_KEYS, Tuplesortstate::indexInfo, SortTuple::isnull1, Tuplesortstate::nKeys, ResetPerTupleExprContext, Tuplesortstate::sortKeys, Tuplesortstate::tupDesc, and SortTuple::tuple.

Referenced by tuplesort_begin_cluster().

3880 {
3881  SortSupport sortKey = state->sortKeys;
3882  HeapTuple ltup;
3883  HeapTuple rtup;
3884  TupleDesc tupDesc;
3885  int nkey;
3886  int32 compare;
3887  Datum datum1,
3888  datum2;
3889  bool isnull1,
3890  isnull2;
3891  AttrNumber leading = state->indexInfo->ii_IndexAttrNumbers[0];
3892 
3893  /* Be prepared to compare additional sort keys */
3894  ltup = (HeapTuple) a->tuple;
3895  rtup = (HeapTuple) b->tuple;
3896  tupDesc = state->tupDesc;
3897 
3898  /* Compare the leading sort key, if it's simple */
3899  if (leading != 0)
3900  {
3901  compare = ApplySortComparator(a->datum1, a->isnull1,
3902  b->datum1, b->isnull1,
3903  sortKey);
3904  if (compare != 0)
3905  return compare;
3906 
3907  if (sortKey->abbrev_converter)
3908  {
3909  datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
3910  datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
3911 
3912  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3913  datum2, isnull2,
3914  sortKey);
3915  }
3916  if (compare != 0 || state->nKeys == 1)
3917  return compare;
3918  /* Compare additional columns the hard way */
3919  sortKey++;
3920  nkey = 1;
3921  }
3922  else
3923  {
3924  /* Must compare all keys the hard way */
3925  nkey = 0;
3926  }
3927 
3928  if (state->indexInfo->ii_Expressions == NULL)
3929  {
3930  /* If not expression index, just compare the proper heap attrs */
3931 
3932  for (; nkey < state->nKeys; nkey++, sortKey++)
3933  {
3934  AttrNumber attno = state->indexInfo->ii_IndexAttrNumbers[nkey];
3935 
3936  datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
3937  datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
3938 
3939  compare = ApplySortComparator(datum1, isnull1,
3940  datum2, isnull2,
3941  sortKey);
3942  if (compare != 0)
3943  return compare;
3944  }
3945  }
3946  else
3947  {
3948  /*
3949  * In the expression index case, compute the whole index tuple and
3950  * then compare values. It would perhaps be faster to compute only as
3951  * many columns as we need to compare, but that would require
3952  * duplicating all the logic in FormIndexDatum.
3953  */
3954  Datum l_index_values[INDEX_MAX_KEYS];
3955  bool l_index_isnull[INDEX_MAX_KEYS];
3956  Datum r_index_values[INDEX_MAX_KEYS];
3957  bool r_index_isnull[INDEX_MAX_KEYS];
3958  TupleTableSlot *ecxt_scantuple;
3959 
3960  /* Reset context each time to prevent memory leakage */
3962 
3963  ecxt_scantuple = GetPerTupleExprContext(state->estate)->ecxt_scantuple;
3964 
3965  ExecStoreHeapTuple(ltup, ecxt_scantuple, false);
3966  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3967  l_index_values, l_index_isnull);
3968 
3969  ExecStoreHeapTuple(rtup, ecxt_scantuple, false);
3970  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3971  r_index_values, r_index_isnull);
3972 
3973  for (; nkey < state->nKeys; nkey++, sortKey++)
3974  {
3975  compare = ApplySortComparator(l_index_values[nkey],
3976  l_index_isnull[nkey],
3977  r_index_values[nkey],
3978  r_index_isnull[nkey],
3979  sortKey);
3980  if (compare != 0)
3981  return compare;
3982  }
3983  }
3984 
3985  return 0;
3986 }
void FormIndexDatum(IndexInfo *indexInfo, TupleTableSlot *slot, EState *estate, Datum *values, bool *isnull)
Definition: index.c:2599
HeapTupleData * HeapTuple
Definition: htup.h:71
#define ResetPerTupleExprContext(estate)
Definition: executor.h:516
EState * estate
Definition: tuplesort.c:452
SortSupport sortKeys
Definition: tuplesort.c:430
Datum datum1
Definition: tuplesort.c:180
bool isnull1
Definition: tuplesort.c:181
signed int int32
Definition: c.h:355
#define GetPerTupleExprContext(estate)
Definition: executor.h:507
void * tuple
Definition: tuplesort.c:179
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
IndexInfo * indexInfo
Definition: tuplesort.c:451
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:762
uintptr_t Datum
Definition: postgres.h:367
List * ii_Expressions
Definition: execnodes.h:161
#define INDEX_MAX_KEYS
AttrNumber ii_IndexAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:160
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
int16 AttrNumber
Definition: attnum.h:21
TupleTableSlot * ExecStoreHeapTuple(HeapTuple tuple, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1322
TupleDesc tupDesc
Definition: tuplesort.c:429
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:238

◆ comparetup_datum()

static int comparetup_datum ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

Definition at line 4365 of file tuplesort.c.

References SortSupportData::abbrev_converter, ApplySortAbbrevFullComparator(), ApplySortComparator(), compare(), SortTuple::datum1, SortTuple::isnull1, PointerGetDatum, Tuplesortstate::sortKeys, and SortTuple::tuple.

Referenced by tuplesort_begin_datum().

4366 {
4367  int compare;
4368 
4369  compare = ApplySortComparator(a->datum1, a->isnull1,
4370  b->datum1, b->isnull1,
4371  state->sortKeys);
4372  if (compare != 0)
4373  return compare;
4374 
4375  /* if we have abbreviations, then "tuple" has the original value */
4376 
4377  if (state->sortKeys->abbrev_converter)
4379  PointerGetDatum(b->tuple), b->isnull1,
4380  state->sortKeys);
4381 
4382  return compare;
4383 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:430
Datum datum1
Definition: tuplesort.c:180
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:238

◆ comparetup_heap()

static int comparetup_heap ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

Definition at line 3679 of file tuplesort.c.

References SortSupportData::abbrev_converter, ApplySortAbbrevFullComparator(), ApplySortComparator(), compare(), SortTuple::datum1, heap_getattr, SortTuple::isnull1, MINIMAL_TUPLE_OFFSET, Tuplesortstate::nKeys, Tuplesortstate::sortKeys, SortSupportData::ssup_attno, HeapTupleData::t_data, HeapTupleData::t_len, Tuplesortstate::tupDesc, and SortTuple::tuple.

Referenced by tuplesort_begin_heap().

3680 {
3681  SortSupport sortKey = state->sortKeys;
3682  HeapTupleData ltup;
3683  HeapTupleData rtup;
3684  TupleDesc tupDesc;
3685  int nkey;
3686  int32 compare;
3687  AttrNumber attno;
3688  Datum datum1,
3689  datum2;
3690  bool isnull1,
3691  isnull2;
3692 
3693 
3694  /* Compare the leading sort key */
3695  compare = ApplySortComparator(a->datum1, a->isnull1,
3696  b->datum1, b->isnull1,
3697  sortKey);
3698  if (compare != 0)
3699  return compare;
3700 
3701  /* Compare additional sort keys */
3702  ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3703  ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
3704  rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3705  rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
3706  tupDesc = state->tupDesc;
3707 
3708  if (sortKey->abbrev_converter)
3709  {
3710  attno = sortKey->ssup_attno;
3711 
3712  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3713  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3714 
3715  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3716  datum2, isnull2,
3717  sortKey);
3718  if (compare != 0)
3719  return compare;
3720  }
3721 
3722  sortKey++;
3723  for (nkey = 1; nkey < state->nKeys; nkey++, sortKey++)
3724  {
3725  attno = sortKey->ssup_attno;
3726 
3727  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3728  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3729 
3730  compare = ApplySortComparator(datum1, isnull1,
3731  datum2, isnull2,
3732  sortKey);
3733  if (compare != 0)
3734  return compare;
3735  }
3736 
3737  return 0;
3738 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:430
Datum datum1
Definition: tuplesort.c:180
bool isnull1
Definition: tuplesort.c:181
signed int int32
Definition: c.h:355
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:179
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:762
uintptr_t Datum
Definition: postgres.h:367
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:619
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
int16 AttrNumber
Definition: attnum.h:21
TupleDesc tupDesc
Definition: tuplesort.c:429
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:238

◆ comparetup_index_btree()

static int comparetup_index_btree ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

Definition at line 4124 of file tuplesort.c.

References SortSupportData::abbrev_converter, ApplySortAbbrevFullComparator(), ApplySortComparator(), Assert, BuildIndexValueDescription(), compare(), SortTuple::datum1, Tuplesortstate::enforceUnique, ereport, errcode(), errdetail(), errmsg(), ERROR, errtableconstraint(), Tuplesortstate::heapRel, index_deform_tuple(), index_getattr, INDEX_MAX_KEYS, Tuplesortstate::indexRel, SortTuple::isnull1, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, Tuplesortstate::nKeys, RelationGetDescr, RelationGetRelationName, Tuplesortstate::sortKeys, IndexTupleData::t_tid, SortTuple::tuple, and values.

Referenced by tuplesort_begin_index_btree().

4126 {
4127  /*
4128  * This is similar to comparetup_heap(), but expects index tuples. There
4129  * is also special handling for enforcing uniqueness, and special
4130  * treatment for equal keys at the end.
4131  */
4132  SortSupport sortKey = state->sortKeys;
4133  IndexTuple tuple1;
4134  IndexTuple tuple2;
4135  int keysz;
4136  TupleDesc tupDes;
4137  bool equal_hasnull = false;
4138  int nkey;
4139  int32 compare;
4140  Datum datum1,
4141  datum2;
4142  bool isnull1,
4143  isnull2;
4144 
4145 
4146  /* Compare the leading sort key */
4147  compare = ApplySortComparator(a->datum1, a->isnull1,
4148  b->datum1, b->isnull1,
4149  sortKey);
4150  if (compare != 0)
4151  return compare;
4152 
4153  /* Compare additional sort keys */
4154  tuple1 = (IndexTuple) a->tuple;
4155  tuple2 = (IndexTuple) b->tuple;
4156  keysz = state->nKeys;
4157  tupDes = RelationGetDescr(state->indexRel);
4158 
4159  if (sortKey->abbrev_converter)
4160  {
4161  datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
4162  datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
4163 
4164  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
4165  datum2, isnull2,
4166  sortKey);
4167  if (compare != 0)
4168  return compare;
4169  }
4170 
4171  /* they are equal, so we only need to examine one null flag */
4172  if (a->isnull1)
4173  equal_hasnull = true;
4174 
4175  sortKey++;
4176  for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
4177  {
4178  datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
4179  datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
4180 
4181  compare = ApplySortComparator(datum1, isnull1,
4182  datum2, isnull2,
4183  sortKey);
4184  if (compare != 0)
4185  return compare; /* done when we find unequal attributes */
4186 
4187  /* they are equal, so we only need to examine one null flag */
4188  if (isnull1)
4189  equal_hasnull = true;
4190  }
4191 
4192  /*
4193  * If btree has asked us to enforce uniqueness, complain if two equal
4194  * tuples are detected (unless there was at least one NULL field).
4195  *
4196  * It is sufficient to make the test here, because if two tuples are equal
4197  * they *must* get compared at some stage of the sort --- otherwise the
4198  * sort algorithm wouldn't have checked whether one must appear before the
4199  * other.
4200  */
4201  if (state->enforceUnique && !equal_hasnull)
4202  {
4204  bool isnull[INDEX_MAX_KEYS];
4205  char *key_desc;
4206 
4207  /*
4208  * Some rather brain-dead implementations of qsort (such as the one in
4209  * QNX 4) will sometimes call the comparison routine to compare a
4210  * value to itself, but we always use our own implementation, which
4211  * does not.
4212  */
4213  Assert(tuple1 != tuple2);
4214 
4215  index_deform_tuple(tuple1, tupDes, values, isnull);
4216 
4217  key_desc = BuildIndexValueDescription(state->indexRel, values, isnull);
4218 
4219  ereport(ERROR,
4220  (errcode(ERRCODE_UNIQUE_VIOLATION),
4221  errmsg("could not create unique index \"%s\"",
4223  key_desc ? errdetail("Key %s is duplicated.", key_desc) :
4224  errdetail("Duplicate keys exist."),
4225  errtableconstraint(state->heapRel,
4226  RelationGetRelationName(state->indexRel))));
4227  }
4228 
4229  /*
4230  * If key values are equal, we sort on ItemPointer. This is required for
4231  * btree indexes, since heap TID is treated as an implicit last key
4232  * attribute in order to ensure that all keys in the index are physically
4233  * unique.
4234  */
4235  {
4236  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4237  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4238 
4239  if (blk1 != blk2)
4240  return (blk1 < blk2) ? -1 : 1;
4241  }
4242  {
4245 
4246  if (pos1 != pos2)
4247  return (pos1 < pos2) ? -1 : 1;
4248  }
4249 
4250  /* ItemPointer values should never be equal */
4251  Assert(false);
4252 
4253  return 0;
4254 }
Relation heapRel
Definition: tuplesort.c:458
#define RelationGetDescr(relation)
Definition: rel.h:482
SortSupport sortKeys
Definition: tuplesort.c:430
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:180
int errcode(int sqlerrcode)
Definition: elog.c:610
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:181
signed int int32
Definition: c.h:355
uint16 OffsetNumber
Definition: off.h:24
void * tuple
Definition: tuplesort.c:179
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5543
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
#define ERROR
Definition: elog.h:43
IndexTupleData * IndexTuple
Definition: itup.h:53
int errdetail(const char *fmt,...)
Definition: elog.c:957
#define RelationGetRelationName(relation)
Definition: rel.h:490
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:434
Relation indexRel
Definition: tuplesort.c:459
uintptr_t Datum
Definition: postgres.h:367
#define ereport(elevel,...)
Definition: elog.h:144
#define Assert(condition)
Definition: c.h:738
bool enforceUnique
Definition: tuplesort.c:462
#define INDEX_MAX_KEYS
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
static Datum values[MAXATTR]
Definition: bootstrap.c:167
int errmsg(const char *fmt,...)
Definition: elog.c:824
char * BuildIndexValueDescription(Relation indexRelation, Datum *values, bool *isnull)
Definition: genam.c:176
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:238

◆ comparetup_index_hash()

static int comparetup_index_hash ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

Definition at line 4257 of file tuplesort.c.

References _hash_hashkey2bucket(), Assert, SortTuple::datum1, DatumGetUInt32, Tuplesortstate::high_mask, SortTuple::isnull1, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, Tuplesortstate::low_mask, Tuplesortstate::max_buckets, IndexTupleData::t_tid, and SortTuple::tuple.

Referenced by tuplesort_begin_index_hash().

4259 {
4260  Bucket bucket1;
4261  Bucket bucket2;
4262  IndexTuple tuple1;
4263  IndexTuple tuple2;
4264 
4265  /*
4266  * Fetch hash keys and mask off bits we don't want to sort by. We know
4267  * that the first column of the index tuple is the hash key.
4268  */
4269  Assert(!a->isnull1);
4271  state->max_buckets, state->high_mask,
4272  state->low_mask);
4273  Assert(!b->isnull1);
4275  state->max_buckets, state->high_mask,
4276  state->low_mask);
4277  if (bucket1 > bucket2)
4278  return 1;
4279  else if (bucket1 < bucket2)
4280  return -1;
4281 
4282  /*
4283  * If hash values are equal, we sort on ItemPointer. This does not affect
4284  * validity of the finished index, but it may be useful to have index
4285  * scans in physical order.
4286  */
4287  tuple1 = (IndexTuple) a->tuple;
4288  tuple2 = (IndexTuple) b->tuple;
4289 
4290  {
4291  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4292  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4293 
4294  if (blk1 != blk2)
4295  return (blk1 < blk2) ? -1 : 1;
4296  }
4297  {
4300 
4301  if (pos1 != pos2)
4302  return (pos1 < pos2) ? -1 : 1;
4303  }
4304 
4305  /* ItemPointer values should never be equal */
4306  Assert(false);
4307 
4308  return 0;
4309 }
#define DatumGetUInt32(X)
Definition: postgres.h:486
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:126
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:180
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:181
uint16 OffsetNumber
Definition: off.h:24
uint32 Bucket
Definition: hash.h:35
void * tuple
Definition: tuplesort.c:179
uint32 high_mask
Definition: tuplesort.c:465
IndexTupleData * IndexTuple
Definition: itup.h:53
#define Assert(condition)
Definition: c.h:738
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
uint32 max_buckets
Definition: tuplesort.c:467
uint32 low_mask
Definition: tuplesort.c:466
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98

◆ consider_abort_common()

static bool consider_abort_common ( Tuplesortstate state)
static

Definition at line 1920 of file tuplesort.c.

References SortSupportData::abbrev_abort, SortSupportData::abbrev_converter, SortSupportData::abbrev_full_comparator, Tuplesortstate::abbrevNext, Assert, SortSupportData::comparator, Tuplesortstate::memtupcount, Tuplesortstate::sortKeys, Tuplesortstate::status, and TSS_INITIAL.

Referenced by copytup_cluster(), copytup_heap(), tuplesort_putdatum(), and tuplesort_putindextuplevalues().

1921 {
1922  Assert(state->sortKeys[0].abbrev_converter != NULL);
1923  Assert(state->sortKeys[0].abbrev_abort != NULL);
1924  Assert(state->sortKeys[0].abbrev_full_comparator != NULL);
1925 
1926  /*
1927  * Check effectiveness of abbreviation optimization. Consider aborting
1928  * when still within memory limit.
1929  */
1930  if (state->status == TSS_INITIAL &&
1931  state->memtupcount >= state->abbrevNext)
1932  {
1933  state->abbrevNext *= 2;
1934 
1935  /*
1936  * Check opclass-supplied abbreviation abort routine. It may indicate
1937  * that abbreviation should not proceed.
1938  */
1939  if (!state->sortKeys->abbrev_abort(state->memtupcount,
1940  state->sortKeys))
1941  return false;
1942 
1943  /*
1944  * Finally, restore authoritative comparator, and indicate that
1945  * abbreviation is not in play by setting abbrev_converter to NULL
1946  */
1947  state->sortKeys[0].comparator = state->sortKeys[0].abbrev_full_comparator;
1948  state->sortKeys[0].abbrev_converter = NULL;
1949  /* Not strictly necessary, but be tidy */
1950  state->sortKeys[0].abbrev_abort = NULL;
1951  state->sortKeys[0].abbrev_full_comparator = NULL;
1952 
1953  /* Give up - expect original pass-by-value representation */
1954  return true;
1955  }
1956 
1957  return false;
1958 }
TupSortStatus status
Definition: tuplesort.c:242
int64 abbrevNext
Definition: tuplesort.c:444
SortSupport sortKeys
Definition: tuplesort.c:430
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define Assert(condition)
Definition: c.h:738
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182

◆ copytup_cluster()

static void copytup_cluster ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

Definition at line 3989 of file tuplesort.c.

References SortSupportData::abbrev_converter, consider_abort_common(), SortTuple::datum1, GetMemoryChunkSpace(), heap_copytuple(), heap_getattr, i, IndexInfo::ii_IndexAttrNumbers, Tuplesortstate::indexInfo, SortTuple::isnull1, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::sortKeys, Tuplesortstate::tupDesc, SortTuple::tuple, Tuplesortstate::tuplecontext, and USEMEM.

Referenced by tuplesort_begin_cluster().

3990 {
3991  HeapTuple tuple = (HeapTuple) tup;
3992  Datum original;
3993  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3994 
3995  /* copy the tuple into sort storage */
3996  tuple = heap_copytuple(tuple);
3997  stup->tuple = (void *) tuple;
3998  USEMEM(state, GetMemoryChunkSpace(tuple));
3999 
4000  MemoryContextSwitchTo(oldcontext);
4001 
4002  /*
4003  * set up first-column key value, and potentially abbreviate, if it's a
4004  * simple column
4005  */
4006  if (state->indexInfo->ii_IndexAttrNumbers[0] == 0)
4007  return;
4008 
4009  original = heap_getattr(tuple,
4010  state->indexInfo->ii_IndexAttrNumbers[0],
4011  state->tupDesc,
4012  &stup->isnull1);
4013 
4014  if (!state->sortKeys->abbrev_converter || stup->isnull1)
4015  {
4016  /*
4017  * Store ordinary Datum representation, or NULL value. If there is a
4018  * converter it won't expect NULL values, and cost model is not
4019  * required to account for NULL, so in that case we avoid calling
4020  * converter and just set datum1 to zeroed representation (to be
4021  * consistent, and to support cheap inequality tests for NULL
4022  * abbreviated keys).
4023  */
4024  stup->datum1 = original;
4025  }
4026  else if (!consider_abort_common(state))
4027  {
4028  /* Store abbreviated key representation */
4029  stup->datum1 = state->sortKeys->abbrev_converter(original,
4030  state->sortKeys);
4031  }
4032  else
4033  {
4034  /* Abort abbreviation */
4035  int i;
4036 
4037  stup->datum1 = original;
4038 
4039  /*
4040  * Set state to be consistent with never trying abbreviation.
4041  *
4042  * Alter datum1 representation in already-copied tuples, so as to
4043  * ensure a consistent representation (current tuple was just
4044  * handled). It does not matter if some dumped tuples are already
4045  * sorted on tape, since serialized tuples lack abbreviated keys
4046  * (TSS_BUILDRUNS state prevents control reaching here in any case).
4047  */
4048  for (i = 0; i < state->memtupcount; i++)
4049  {
4050  SortTuple *mtup = &state->memtuples[i];
4051 
4052  tuple = (HeapTuple) mtup->tuple;
4053  mtup->datum1 = heap_getattr(tuple,
4054  state->indexInfo->ii_IndexAttrNumbers[0],
4055  state->tupDesc,
4056  &mtup->isnull1);
4057  }
4058  }
4059 }
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:680
HeapTupleData * HeapTuple
Definition: htup.h:71
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1920
IndexInfo * indexInfo
Definition: tuplesort.c:451
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:762
uintptr_t Datum
Definition: postgres.h:367
MemoryContext tuplecontext
Definition: tuplesort.c:263
#define USEMEM(state, amt)
Definition: tuplesort.c:546
int i
AttrNumber ii_IndexAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:160
TupleDesc tupDesc
Definition: tuplesort.c:429
SortTuple * memtuples
Definition: tuplesort.c:311

◆ copytup_datum()

static void copytup_datum ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

Definition at line 4386 of file tuplesort.c.

References elog, and ERROR.

Referenced by tuplesort_begin_datum().

4387 {
4388  /* Not currently needed */
4389  elog(ERROR, "copytup_datum() should not be called");
4390 }
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:214

◆ copytup_heap()

static void copytup_heap ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

Definition at line 3741 of file tuplesort.c.

References SortSupportData::abbrev_converter, consider_abort_common(), SortTuple::datum1, ExecCopySlotMinimalTuple(), GetMemoryChunkSpace(), heap_getattr, i, SortTuple::isnull1, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, MINIMAL_TUPLE_OFFSET, Tuplesortstate::sortKeys, SortSupportData::ssup_attno, HeapTupleData::t_data, HeapTupleData::t_len, MinimalTupleData::t_len, Tuplesortstate::tupDesc, SortTuple::tuple, Tuplesortstate::tuplecontext, and USEMEM.

Referenced by tuplesort_begin_heap().

3742 {
3743  /*
3744  * We expect the passed "tup" to be a TupleTableSlot, and form a
3745  * MinimalTuple using the exported interface for that.
3746  */
3747  TupleTableSlot *slot = (TupleTableSlot *) tup;
3748  Datum original;
3749  MinimalTuple tuple;
3750  HeapTupleData htup;
3751  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3752 
3753  /* copy the tuple into sort storage */
3754  tuple = ExecCopySlotMinimalTuple(slot);
3755  stup->tuple = (void *) tuple;
3756  USEMEM(state, GetMemoryChunkSpace(tuple));
3757  /* set up first-column key value */
3758  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3759  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3760  original = heap_getattr(&htup,
3761  state->sortKeys[0].ssup_attno,
3762  state->tupDesc,
3763  &stup->isnull1);
3764 
3765  MemoryContextSwitchTo(oldcontext);
3766 
3767  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3768  {
3769  /*
3770  * Store ordinary Datum representation, or NULL value. If there is a
3771  * converter it won't expect NULL values, and cost model is not
3772  * required to account for NULL, so in that case we avoid calling
3773  * converter and just set datum1 to zeroed representation (to be
3774  * consistent, and to support cheap inequality tests for NULL
3775  * abbreviated keys).
3776  */
3777  stup->datum1 = original;
3778  }
3779  else if (!consider_abort_common(state))
3780  {
3781  /* Store abbreviated key representation */
3782  stup->datum1 = state->sortKeys->abbrev_converter(original,
3783  state->sortKeys);
3784  }
3785  else
3786  {
3787  /* Abort abbreviation */
3788  int i;
3789 
3790  stup->datum1 = original;
3791 
3792  /*
3793  * Set state to be consistent with never trying abbreviation.
3794  *
3795  * Alter datum1 representation in already-copied tuples, so as to
3796  * ensure a consistent representation (current tuple was just
3797  * handled). It does not matter if some dumped tuples are already
3798  * sorted on tape, since serialized tuples lack abbreviated keys
3799  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3800  */
3801  for (i = 0; i < state->memtupcount; i++)
3802  {
3803  SortTuple *mtup = &state->memtuples[i];
3804 
3805  htup.t_len = ((MinimalTuple) mtup->tuple)->t_len +
3807  htup.t_data = (HeapTupleHeader) ((char *) mtup->tuple -
3809 
3810  mtup->datum1 = heap_getattr(&htup,
3811  state->sortKeys[0].ssup_attno,
3812  state->tupDesc,
3813  &mtup->isnull1);
3814  }
3815  }
3816 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:181
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:179
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1920
uint32 t_len
Definition: htup.h:64
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:463
MinimalTupleData * MinimalTuple
Definition: htup.h:27
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:762
uintptr_t Datum
Definition: postgres.h:367
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:619
MemoryContext tuplecontext
Definition: tuplesort.c:263
#define USEMEM(state, amt)
Definition: tuplesort.c:546
int i
TupleDesc tupDesc
Definition: tuplesort.c:429
SortTuple * memtuples
Definition: tuplesort.c:311

◆ copytup_index()

static void copytup_index ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

Definition at line 4312 of file tuplesort.c.

References elog, and ERROR.

Referenced by tuplesort_begin_index_btree(), and tuplesort_begin_index_hash().

4313 {
4314  /* Not currently needed */
4315  elog(ERROR, "copytup_index() should not be called");
4316 }
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:214

◆ dumptuples()

static void dumptuples ( Tuplesortstate state,
bool  alltuples 
)
static

Definition at line 3098 of file tuplesort.c.

References Assert, Tuplesortstate::currentRun, Tuplesortstate::destTape, elog, ereport, errcode(), errmsg(), ERROR, i, LACKMEM, LOG, markrunend(), MemoryContextReset(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, pg_rusage_show(), Tuplesortstate::ru_start, selectnewtape(), Tuplesortstate::status, Tuplesortstate::tp_dummy, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, trace_sort, TSS_BUILDRUNS, Tuplesortstate::tuplecontext, tuplesort_sort_memtuples(), Tuplesortstate::worker, and WRITETUP.

Referenced by puttuple_common(), and tuplesort_performsort().

3099 {
3100  int memtupwrite;
3101  int i;
3102 
3103  /*
3104  * Nothing to do if we still fit in available memory and have array slots,
3105  * unless this is the final call during initial run generation.
3106  */
3107  if (state->memtupcount < state->memtupsize && !LACKMEM(state) &&
3108  !alltuples)
3109  return;
3110 
3111  /*
3112  * Final call might require no sorting, in rare cases where we just so
3113  * happen to have previously LACKMEM()'d at the point where exactly all
3114  * remaining tuples are loaded into memory, just before input was
3115  * exhausted.
3116  *
3117  * In general, short final runs are quite possible. Rather than allowing
3118  * a special case where there was a superfluous selectnewtape() call (i.e.
3119  * a call with no subsequent run actually written to destTape), we prefer
3120  * to write out a 0 tuple run.
3121  *
3122  * mergereadnext() is prepared for 0 tuple runs, and will reliably mark
3123  * the tape inactive for the merge when called from beginmerge(). This
3124  * case is therefore similar to the case where mergeonerun() finds a dummy
3125  * run for the tape, and so doesn't need to merge a run from the tape (or
3126  * conceptually "merges" the dummy run, if you prefer). According to
3127  * Knuth, Algorithm D "isn't strictly optimal" in its method of
3128  * distribution and dummy run assignment; this edge case seems very
3129  * unlikely to make that appreciably worse.
3130  */
3131  Assert(state->status == TSS_BUILDRUNS);
3132 
3133  /*
3134  * It seems unlikely that this limit will ever be exceeded, but take no
3135  * chances
3136  */
3137  if (state->currentRun == INT_MAX)
3138  ereport(ERROR,
3139  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
3140  errmsg("cannot have more than %d runs for an external sort",
3141  INT_MAX)));
3142 
3143  state->currentRun++;
3144 
3145 #ifdef TRACE_SORT
3146  if (trace_sort)
3147  elog(LOG, "worker %d starting quicksort of run %d: %s",
3148  state->worker, state->currentRun,
3149  pg_rusage_show(&state->ru_start));
3150 #endif
3151 
3152  /*
3153  * Sort all tuples accumulated within the allowed amount of memory for
3154  * this run using quicksort
3155  */
3156  tuplesort_sort_memtuples(state);
3157 
3158 #ifdef TRACE_SORT
3159  if (trace_sort)
3160  elog(LOG, "worker %d finished quicksort of run %d: %s",
3161  state->worker, state->currentRun,
3162  pg_rusage_show(&state->ru_start));
3163 #endif
3164 
3165  memtupwrite = state->memtupcount;
3166  for (i = 0; i < memtupwrite; i++)
3167  {
3168  WRITETUP(state, state->tp_tapenum[state->destTape],
3169  &state->memtuples[i]);
3170  state->memtupcount--;
3171  }
3172 
3173  /*
3174  * Reset tuple memory. We've freed all of the tuples that we previously
3175  * allocated. It's important to avoid fragmentation when there is a stark
3176  * change in the sizes of incoming tuples. Fragmentation due to
3177  * AllocSetFree's bucketing by size class might be particularly bad if
3178  * this step wasn't taken.
3179  */
3181 
3182  markrunend(state, state->tp_tapenum[state->destTape]);
3183  state->tp_runs[state->destTape]++;
3184  state->tp_dummy[state->destTape]--; /* per Alg D step D2 */
3185 
3186 #ifdef TRACE_SORT
3187  if (trace_sort)
3188  elog(LOG, "worker %d finished writing run %d to tape %d: %s",
3189  state->worker, state->currentRun, state->destTape,
3190  pg_rusage_show(&state->ru_start));
3191 #endif
3192 
3193  if (!alltuples)
3194  selectnewtape(state);
3195 }
TupSortStatus status
Definition: tuplesort.c:242
PGRUsage ru_start
Definition: tuplesort.c:481
int errcode(int sqlerrcode)
Definition: elog.c:610
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3637
#define ERROR
Definition: elog.h:43
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
static void selectnewtape(Tuplesortstate *state)
Definition: tuplesort.c:2667
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:543
#define ereport(elevel,...)
Definition: elog.h:144
#define Assert(condition)
Definition: c.h:738
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3479
int * tp_dummy
Definition: tuplesort.c:387
MemoryContext tuplecontext
Definition: tuplesort.c:263
int errmsg(const char *fmt,...)
Definition: elog.c:824
int * tp_tapenum
Definition: tuplesort.c:388
#define elog(elevel,...)
Definition: elog.h:214
int i
#define LACKMEM(state)
Definition: tuplesort.c:545
SortTuple * memtuples
Definition: tuplesort.c:311

◆ free_sort_tuple()

static void free_sort_tuple ( Tuplesortstate state,
SortTuple stup 
)
static

Definition at line 4697 of file tuplesort.c.

References FREEMEM, GetMemoryChunkSpace(), pfree(), and SortTuple::tuple.

Referenced by make_bounded_heap(), and puttuple_common().

4698 {
4699  FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
4700  pfree(stup->tuple);
4701 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
void * tuple
Definition: tuplesort.c:179
void pfree(void *pointer)
Definition: mcxt.c:1056
#define FREEMEM(state, amt)
Definition: tuplesort.c:547

◆ getlen()

static unsigned int getlen ( Tuplesortstate state,
int  tapenum,
bool  eofOK 
)
static

Definition at line 3624 of file tuplesort.c.

References elog, ERROR, LogicalTapeRead(), and Tuplesortstate::tapeset.

Referenced by mergereadnext(), and tuplesort_gettuple_common().

3625 {
3626  unsigned int len;
3627 
3628  if (LogicalTapeRead(state->tapeset, tapenum,
3629  &len, sizeof(len)) != sizeof(len))
3630  elog(ERROR, "unexpected end of tape");
3631  if (len == 0 && !eofOK)
3632  elog(ERROR, "unexpected end of data");
3633  return len;
3634 }
size_t LogicalTapeRead(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:956
#define ERROR
Definition: elog.h:43
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define elog(elevel,...)
Definition: elog.h:214

◆ grow_memtuples()

static bool grow_memtuples ( Tuplesortstate state)
static

Definition at line 1489 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, elog, ERROR, FREEMEM, GetMemoryChunkSpace(), Tuplesortstate::growmemtuples, LACKMEM, MaxAllocHugeSize, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, repalloc_huge(), and USEMEM.

Referenced by puttuple_common().

1490 {
1491  int newmemtupsize;
1492  int memtupsize = state->memtupsize;
1493  int64 memNowUsed = state->allowedMem - state->availMem;
1494 
1495  /* Forget it if we've already maxed out memtuples, per comment above */
1496  if (!state->growmemtuples)
1497  return false;
1498 
1499  /* Select new value of memtupsize */
1500  if (memNowUsed <= state->availMem)
1501  {
1502  /*
1503  * We've used no more than half of allowedMem; double our usage,
1504  * clamping at INT_MAX tuples.
1505  */
1506  if (memtupsize < INT_MAX / 2)
1507  newmemtupsize = memtupsize * 2;
1508  else
1509  {
1510  newmemtupsize = INT_MAX;
1511  state->growmemtuples = false;
1512  }
1513  }
1514  else
1515  {
1516  /*
1517  * This will be the last increment of memtupsize. Abandon doubling
1518  * strategy and instead increase as much as we safely can.
1519  *
1520  * To stay within allowedMem, we can't increase memtupsize by more
1521  * than availMem / sizeof(SortTuple) elements. In practice, we want
1522  * to increase it by considerably less, because we need to leave some
1523  * space for the tuples to which the new array slots will refer. We
1524  * assume the new tuples will be about the same size as the tuples
1525  * we've already seen, and thus we can extrapolate from the space
1526  * consumption so far to estimate an appropriate new size for the
1527  * memtuples array. The optimal value might be higher or lower than
1528  * this estimate, but it's hard to know that in advance. We again
1529  * clamp at INT_MAX tuples.
1530  *
1531  * This calculation is safe against enlarging the array so much that
1532  * LACKMEM becomes true, because the memory currently used includes
1533  * the present array; thus, there would be enough allowedMem for the
1534  * new array elements even if no other memory were currently used.
1535  *
1536  * We do the arithmetic in float8, because otherwise the product of
1537  * memtupsize and allowedMem could overflow. Any inaccuracy in the
1538  * result should be insignificant; but even if we computed a
1539  * completely insane result, the checks below will prevent anything
1540  * really bad from happening.
1541  */
1542  double grow_ratio;
1543 
1544  grow_ratio = (double) state->allowedMem / (double) memNowUsed;
1545  if (memtupsize * grow_ratio < INT_MAX)
1546  newmemtupsize = (int) (memtupsize * grow_ratio);
1547  else
1548  newmemtupsize = INT_MAX;
1549 
1550  /* We won't make any further enlargement attempts */
1551  state->growmemtuples = false;
1552  }
1553 
1554  /* Must enlarge array by at least one element, else report failure */
1555  if (newmemtupsize <= memtupsize)
1556  goto noalloc;
1557 
1558  /*
1559  * On a 32-bit machine, allowedMem could exceed MaxAllocHugeSize. Clamp
1560  * to ensure our request won't be rejected. Note that we can easily
1561  * exhaust address space before facing this outcome. (This is presently
1562  * impossible due to guc.c's MAX_KILOBYTES limitation on work_mem, but
1563  * don't rely on that at this distance.)
1564  */
1565  if ((Size) newmemtupsize >= MaxAllocHugeSize / sizeof(SortTuple))
1566  {
1567  newmemtupsize = (int) (MaxAllocHugeSize / sizeof(SortTuple));
1568  state->growmemtuples = false; /* can't grow any more */
1569  }
1570 
1571  /*
1572  * We need to be sure that we do not cause LACKMEM to become true, else
1573  * the space management algorithm will go nuts. The code above should
1574  * never generate a dangerous request, but to be safe, check explicitly
1575  * that the array growth fits within availMem. (We could still cause
1576  * LACKMEM if the memory chunk overhead associated with the memtuples
1577  * array were to increase. That shouldn't happen because we chose the
1578  * initial array size large enough to ensure that palloc will be treating
1579  * both old and new arrays as separate chunks. But we'll check LACKMEM
1580  * explicitly below just in case.)
1581  */
1582  if (state->availMem < (int64) ((newmemtupsize - memtupsize) * sizeof(SortTuple)))
1583  goto noalloc;
1584 
1585  /* OK, do it */
1586  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
1587  state->memtupsize = newmemtupsize;
1588  state->memtuples = (SortTuple *)
1589  repalloc_huge(state->memtuples,
1590  state->memtupsize * sizeof(SortTuple));
1591  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
1592  if (LACKMEM(state))
1593  elog(ERROR, "unexpected out-of-memory situation in tuplesort");
1594  return true;
1595 
1596 noalloc:
1597  /* If for any reason we didn't realloc, shut off future attempts */
1598  state->growmemtuples = false;
1599  return false;
1600 }
int64 availMem
Definition: tuplesort.c:250
bool growmemtuples
Definition: tuplesort.c:314
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
#define MaxAllocHugeSize
Definition: memutils.h:44
#define ERROR
Definition: elog.h:43
#define FREEMEM(state, amt)
Definition: tuplesort.c:547
int64 allowedMem
Definition: tuplesort.c:251
size_t Size
Definition: c.h:466
void * repalloc_huge(void *pointer, Size size)
Definition: mcxt.c:1139
#define USEMEM(state, amt)
Definition: tuplesort.c:546
#define elog(elevel,...)
Definition: elog.h:214
#define LACKMEM(state)
Definition: tuplesort.c:545
SortTuple * memtuples
Definition: tuplesort.c:311

◆ init_slab_allocator()

static void init_slab_allocator ( Tuplesortstate state,
int  numSlots 
)
static

Definition at line 2699 of file tuplesort.c.

References i, palloc(), SLAB_SLOT_SIZE, Tuplesortstate::slabAllocatorUsed, Tuplesortstate::slabFreeHead, Tuplesortstate::slabMemoryBegin, Tuplesortstate::slabMemoryEnd, and USEMEM.

Referenced by mergeruns().

2700 {
2701  if (numSlots > 0)
2702  {
2703  char *p;
2704  int i;
2705 
2706  state->slabMemoryBegin = palloc(numSlots * SLAB_SLOT_SIZE);
2707  state->slabMemoryEnd = state->slabMemoryBegin +
2708  numSlots * SLAB_SLOT_SIZE;
2709  state->slabFreeHead = (SlabSlot *) state->slabMemoryBegin;
2710  USEMEM(state, numSlots * SLAB_SLOT_SIZE);
2711 
2712  p = state->slabMemoryBegin;
2713  for (i = 0; i < numSlots - 1; i++)
2714  {
2715  ((SlabSlot *) p)->nextfree = (SlabSlot *) (p + SLAB_SLOT_SIZE);
2716  p += SLAB_SLOT_SIZE;
2717  }
2718  ((SlabSlot *) p)->nextfree = NULL;
2719  }
2720  else
2721  {
2722  state->slabMemoryBegin = state->slabMemoryEnd = NULL;
2723  state->slabFreeHead = NULL;
2724  }
2725  state->slabAllocatorUsed = true;
2726 }
char * slabMemoryEnd
Definition: tuplesort.c:346
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:196
char * slabMemoryBegin
Definition: tuplesort.c:345
bool slabAllocatorUsed
Definition: tuplesort.c:343
void * palloc(Size size)
Definition: mcxt.c:949
#define USEMEM(state, amt)
Definition: tuplesort.c:546
int i
SlabSlot * slabFreeHead
Definition: tuplesort.c:347

◆ inittapes()

static void inittapes ( Tuplesortstate state,
bool  mergeruns 
)
static

Definition at line 2566 of file tuplesort.c.

References Tuplesortstate::allowedMem, Assert, Tuplesortstate::currentRun, Tuplesortstate::destTape, elog, Sharedsort::fileset, inittapestate(), LEADER, Tuplesortstate::Level, LOG, LogicalTapeSetCreate(), MINORDER, pg_rusage_show(), Tuplesortstate::ru_start, Tuplesortstate::shared, Tuplesortstate::status, Tuplesortstate::tapeRange, Tuplesortstate::tapeset, Tuplesortstate::tp_dummy, Tuplesortstate::tp_fib, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, trace_sort, TSS_BUILDRUNS, tuplesort_merge_order(), Tuplesortstate::worker, and WORKER.

Referenced by puttuple_common(), and tuplesort_performsort().

2567 {
2568  int maxTapes,
2569  j;
2570 
2571  Assert(!LEADER(state));
2572 
2573  if (mergeruns)
2574  {
2575  /* Compute number of tapes to use: merge order plus 1 */
2576  maxTapes = tuplesort_merge_order(state->allowedMem) + 1;
2577  }
2578  else
2579  {
2580  /* Workers can sometimes produce single run, output without merge */
2581  Assert(WORKER(state));
2582  maxTapes = MINORDER + 1;
2583  }
2584 
2585 #ifdef TRACE_SORT
2586  if (trace_sort)
2587  elog(LOG, "worker %d switching to external sort with %d tapes: %s",
2588  state->worker, maxTapes, pg_rusage_show(&state->ru_start));
2589 #endif
2590 
2591  /* Create the tape set and allocate the per-tape data arrays */
2592  inittapestate(state, maxTapes);
2593  state->tapeset =
2594  LogicalTapeSetCreate(maxTapes, NULL,
2595  state->shared ? &state->shared->fileset : NULL,
2596  state->worker);
2597 
2598  state->currentRun = 0;
2599 
2600  /*
2601  * Initialize variables of Algorithm D (step D1).
2602  */
2603  for (j = 0; j < maxTapes; j++)
2604  {
2605  state->tp_fib[j] = 1;
2606  state->tp_runs[j] = 0;
2607  state->tp_dummy[j] = 1;
2608  state->tp_tapenum[j] = j;
2609  }
2610  state->tp_fib[state->tapeRange] = 0;
2611  state->tp_dummy[state->tapeRange] = 0;
2612 
2613  state->Level = 1;
2614  state->destTape = 0;
2615 
2616  state->status = TSS_BUILDRUNS;
2617 }
TupSortStatus status
Definition: tuplesort.c:242
PGRUsage ru_start
Definition: tuplesort.c:481
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2735
LogicalTapeSet * LogicalTapeSetCreate(int ntapes, TapeShare *shared, SharedFileSet *fileset, int worker)
Definition: logtape.c:665
Sharedsort * shared
Definition: tuplesort.c:421
#define MINORDER
Definition: tuplesort.c:229
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define LEADER(state)
Definition: tuplesort.c:550
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define WORKER(state)
Definition: tuplesort.c:549
int64 allowedMem
Definition: tuplesort.c:251
#define Assert(condition)
Definition: c.h:738
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2526
int * tp_dummy
Definition: tuplesort.c:387
int * tp_tapenum
Definition: tuplesort.c:388
#define elog(elevel,...)
Definition: elog.h:214
static void inittapestate(Tuplesortstate *state, int maxTapes)
Definition: tuplesort.c:2623
SharedFileSet fileset
Definition: tuplesort.c:506

◆ inittapestate()

static void inittapestate ( Tuplesortstate state,
int  maxTapes 
)
static

Definition at line 2623 of file tuplesort.c.

References Tuplesortstate::allowedMem, GetMemoryChunkSpace(), Tuplesortstate::maxTapes, Tuplesortstate::memtuples, Tuplesortstate::mergeactive, palloc0(), PrepareTempTablespaces(), TAPE_BUFFER_OVERHEAD, Tuplesortstate::tapeRange, Tuplesortstate::tp_dummy, Tuplesortstate::tp_fib, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, and USEMEM.

Referenced by inittapes(), and leader_takeover_tapes().

2624 {
2625  int64 tapeSpace;
2626 
2627  /*
2628  * Decrease availMem to reflect the space needed for tape buffers; but
2629  * don't decrease it to the point that we have no room for tuples. (That
2630  * case is only likely to occur if sorting pass-by-value Datums; in all
2631  * other scenarios the memtuples[] array is unlikely to occupy more than
2632  * half of allowedMem. In the pass-by-value case it's not important to
2633  * account for tuple space, so we don't care if LACKMEM becomes
2634  * inaccurate.)
2635  */
2636  tapeSpace = (int64) maxTapes * TAPE_BUFFER_OVERHEAD;
2637 
2638  if (tapeSpace + GetMemoryChunkSpace(state->memtuples) < state->allowedMem)
2639  USEMEM(state, tapeSpace);
2640 
2641  /*
2642  * Make sure that the temp file(s) underlying the tape set are created in
2643  * suitable temp tablespaces. For parallel sorts, this should have been
2644  * called already, but it doesn't matter if it is called a second time.
2645  */
2647 
2648  state->mergeactive = (bool *) palloc0(maxTapes * sizeof(bool));
2649  state->tp_fib = (int *) palloc0(maxTapes * sizeof(int));
2650  state->tp_runs = (int *) palloc0(maxTapes * sizeof(int));
2651  state->tp_dummy = (int *) palloc0(maxTapes * sizeof(int));
2652  state->tp_tapenum = (int *) palloc0(maxTapes * sizeof(int));
2653 
2654  /* Record # of tapes allocated (for duration of sort) */
2655  state->maxTapes = maxTapes;
2656  /* Record maximum # of tapes usable as inputs when merging */
2657  state->tapeRange = maxTapes - 1;
2658 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:231
void PrepareTempTablespaces(void)
Definition: tablespace.c:1323
int64 allowedMem
Definition: tuplesort.c:251
void * palloc0(Size size)
Definition: mcxt.c:980
int * tp_dummy
Definition: tuplesort.c:387
int * tp_tapenum
Definition: tuplesort.c:388
#define USEMEM(state, amt)
Definition: tuplesort.c:546
bool * mergeactive
Definition: tuplesort.c:376
SortTuple * memtuples
Definition: tuplesort.c:311

◆ leader_takeover_tapes()

static void leader_takeover_tapes ( Tuplesortstate state)
static

Definition at line 4632 of file tuplesort.c.

References Assert, Tuplesortstate::currentRun, Tuplesortstate::destTape, elog, ERROR, Sharedsort::fileset, inittapestate(), LEADER, Tuplesortstate::Level, LogicalTapeSetCreate(), Tuplesortstate::maxTapes, Sharedsort::mutex, Tuplesortstate::nParticipants, Tuplesortstate::shared, SpinLockAcquire, SpinLockRelease, Tuplesortstate::status, Tuplesortstate::tapeRange, Sharedsort::tapes, Tuplesortstate::tapeset, Tuplesortstate::tp_dummy, Tuplesortstate::tp_fib, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, TSS_BUILDRUNS, Tuplesortstate::worker, and Sharedsort::workersFinished.

Referenced by tuplesort_performsort().

4633 {
4634  Sharedsort *shared = state->shared;
4635  int nParticipants = state->nParticipants;
4636  int workersFinished;
4637  int j;
4638 
4639  Assert(LEADER(state));
4640  Assert(nParticipants >= 1);
4641 
4642  SpinLockAcquire(&shared->mutex);
4643  workersFinished = shared->workersFinished;
4644  SpinLockRelease(&shared->mutex);
4645 
4646  if (nParticipants != workersFinished)
4647  elog(ERROR, "cannot take over tapes before all workers finish");
4648 
4649  /*
4650  * Create the tapeset from worker tapes, including a leader-owned tape at
4651  * the end. Parallel workers are far more expensive than logical tapes,
4652  * so the number of tapes allocated here should never be excessive.
4653  *
4654  * We still have a leader tape, though it's not possible to write to it
4655  * due to restrictions in the shared fileset infrastructure used by
4656  * logtape.c. It will never be written to in practice because
4657  * randomAccess is disallowed for parallel sorts.
4658  */
4659  inittapestate(state, nParticipants + 1);
4660  state->tapeset = LogicalTapeSetCreate(nParticipants + 1, shared->tapes,
4661  &shared->fileset, state->worker);
4662 
4663  /* mergeruns() relies on currentRun for # of runs (in one-pass cases) */
4664  state->currentRun = nParticipants;
4665 
4666  /*
4667  * Initialize variables of Algorithm D to be consistent with runs from
4668  * workers having been generated in the leader.
4669  *
4670  * There will always be exactly 1 run per worker, and exactly one input
4671  * tape per run, because workers always output exactly 1 run, even when
4672  * there were no input tuples for workers to sort.
4673  */
4674  for (j = 0; j < state->maxTapes; j++)
4675  {
4676  /* One real run; no dummy runs for worker tapes */
4677  state->tp_fib[j] = 1;
4678  state->tp_runs[j] = 1;
4679  state->tp_dummy[j] = 0;
4680  state->tp_tapenum[j] = j;
4681  }
4682  /* Leader tape gets one dummy run, and no real runs */
4683  state->tp_fib[state->tapeRange] = 0;
4684  state->tp_runs[state->tapeRange] = 0;
4685  state->tp_dummy[state->tapeRange] = 1;
4686 
4687  state->Level = 1;
4688  state->destTape = 0;
4689 
4690  state->status = TSS_BUILDRUNS;
4691 }
TupSortStatus status
Definition: tuplesort.c:242
slock_t mutex
Definition: tuplesort.c:492
#define SpinLockAcquire(lock)
Definition: spin.h:62
#define ERROR
Definition: elog.h:43
LogicalTapeSet * LogicalTapeSetCreate(int ntapes, TapeShare *shared, SharedFileSet *fileset, int worker)
Definition: logtape.c:665
Sharedsort * shared
Definition: tuplesort.c:421
#define LEADER(state)
Definition: tuplesort.c:550
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
int workersFinished
Definition: tuplesort.c:503
#define SpinLockRelease(lock)
Definition: spin.h:64
#define Assert(condition)
Definition: c.h:738
int * tp_dummy
Definition: tuplesort.c:387
int * tp_tapenum
Definition: tuplesort.c:388
#define elog(elevel,...)
Definition: elog.h:214
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:515
static void inittapestate(Tuplesortstate *state, int maxTapes)
Definition: tuplesort.c:2623
SharedFileSet fileset
Definition: tuplesort.c:506

◆ make_bounded_heap()

static void make_bounded_heap ( Tuplesortstate state)
static

Definition at line 3390 of file tuplesort.c.

References Assert, Tuplesortstate::bound, Tuplesortstate::bounded, CHECK_FOR_INTERRUPTS, COMPARETUP, free_sort_tuple(), i, Tuplesortstate::memtupcount, Tuplesortstate::memtuples, reversedirection(), SERIAL, Tuplesortstate::status, TSS_BOUNDED, TSS_INITIAL, tuplesort_heap_insert(), and tuplesort_heap_replace_top().

Referenced by puttuple_common().

3391 {
3392  int tupcount = state->memtupcount;
3393  int i;
3394 
3395  Assert(state->status == TSS_INITIAL);
3396  Assert(state->bounded);
3397  Assert(tupcount >= state->bound);
3398  Assert(SERIAL(state));
3399 
3400  /* Reverse sort direction so largest entry will be at root */
3401  reversedirection(state);
3402 
3403  state->memtupcount = 0; /* make the heap empty */
3404  for (i = 0; i < tupcount; i++)
3405  {
3406  if (state->memtupcount < state->bound)
3407  {
3408  /* Insert next tuple into heap */
3409  /* Must copy source tuple to avoid possible overwrite */
3410  SortTuple stup = state->memtuples[i];
3411 
3412  tuplesort_heap_insert(state, &stup);
3413  }
3414  else
3415  {
3416  /*
3417  * The heap is full. Replace the largest entry with the new
3418  * tuple, or just discard it, if it's larger than anything already
3419  * in the heap.
3420  */
3421  if (COMPARETUP(state, &state->memtuples[i], &state->memtuples[0]) <= 0)
3422  {
3423  free_sort_tuple(state, &state->memtuples[i]);
3425  }
3426  else
3427  tuplesort_heap_replace_top(state, &state->memtuples[i]);
3428  }
3429  }
3430 
3431  Assert(state->memtupcount == state->bound);
3432  state->status = TSS_BOUNDED;
3433 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3606
TupSortStatus status
Definition: tuplesort.c:242
#define SERIAL(state)
Definition: tuplesort.c:548
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4697
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:541
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3507
#define Assert(condition)
Definition: c.h:738
int i
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3566
SortTuple * memtuples
Definition: tuplesort.c:311

◆ markrunend()

static void markrunend ( Tuplesortstate state,
int  tapenum 
)
static

Definition at line 3637 of file tuplesort.c.

References LogicalTapeWrite(), and Tuplesortstate::tapeset.

Referenced by dumptuples(), and mergeonerun().

3638 {
3639  unsigned int len = 0;
3640 
3641  LogicalTapeWrite(state->tapeset, tapenum, (void *) &len, sizeof(len));
3642 }
void LogicalTapeWrite(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:754
LogicalTapeSet * tapeset
Definition: tuplesort.c:264

◆ mergeonerun()

static void mergeonerun ( Tuplesortstate state)
static

Definition at line 2962 of file tuplesort.c.

References Tuplesortstate::activeTapes, beginmerge(), elog, LOG, markrunend(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, mergereadnext(), pg_rusage_show(), RELEASE_SLAB_SLOT, Tuplesortstate::ru_start, SortTuple::srctape, Tuplesortstate::tapeRange, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, trace_sort, SortTuple::tuple, tuplesort_heap_delete_top(), tuplesort_heap_replace_top(), Tuplesortstate::worker, and WRITETUP.

Referenced by mergeruns().

2963 {
2964  int destTape = state->tp_tapenum[state->tapeRange];
2965  int srcTape;
2966 
2967  /*
2968  * Start the merge by loading one tuple from each active source tape into
2969  * the heap. We can also decrease the input run/dummy run counts.
2970  */
2971  beginmerge(state);
2972 
2973  /*
2974  * Execute merge by repeatedly extracting lowest tuple in heap, writing it
2975  * out, and replacing it with next tuple from same tape (if there is
2976  * another one).
2977  */
2978  while (state->memtupcount > 0)
2979  {
2980  SortTuple stup;
2981 
2982  /* write the tuple to destTape */
2983  srcTape = state->memtuples[0].srctape;
2984  WRITETUP(state, destTape, &state->memtuples[0]);
2985 
2986  /* recycle the slot of the tuple we just wrote out, for the next read */
2987  if (state->memtuples[0].tuple)
2988  RELEASE_SLAB_SLOT(state, state->memtuples[0].tuple);
2989 
2990  /*
2991  * pull next tuple from the tape, and replace the written-out tuple in
2992  * the heap with it.
2993  */
2994  if (mergereadnext(state, srcTape, &stup))
2995  {
2996  stup.srctape = srcTape;
2997  tuplesort_heap_replace_top(state, &stup);
2998  }
2999  else
3001  }
3002 
3003  /*
3004  * When the heap empties, we're done. Write an end-of-run marker on the
3005  * output tape, and increment its count of real runs.
3006  */
3007  markrunend(state, destTape);
3008  state->tp_runs[state->tapeRange]++;
3009 
3010 #ifdef TRACE_SORT
3011  if (trace_sort)
3012  elog(LOG, "worker %d finished %d-way merge step: %s", state->worker,
3013  state->activeTapes, pg_rusage_show(&state->ru_start));
3014 #endif
3015 }
PGRUsage ru_start
Definition: tuplesort.c:481
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3637
void * tuple
Definition: tuplesort.c:179
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:543
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:529
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3542
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:3073
int srctape
Definition: tuplesort.c:182
int * tp_tapenum
Definition: tuplesort.c:388
#define elog(elevel,...)
Definition: elog.h:214
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3566
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:3025
SortTuple * memtuples
Definition: tuplesort.c:311

◆ mergereadnext()

static bool mergereadnext ( Tuplesortstate state,
int  srcTape,
SortTuple stup 
)
static

Definition at line 3073 of file tuplesort.c.

References getlen(), Tuplesortstate::mergeactive, and READTUP.

Referenced by beginmerge(), mergeonerun(), and tuplesort_gettuple_common().

3074 {
3075  unsigned int tuplen;
3076 
3077  if (!state->mergeactive[srcTape])
3078  return false; /* tape's run is already exhausted */
3079 
3080  /* read next tuple, if any */
3081  if ((tuplen = getlen(state, srcTape, true)) == 0)
3082  {
3083  state->mergeactive[srcTape] = false;
3084  return false;
3085  }
3086  READTUP(state, stup, srcTape, tuplen);
3087 
3088  return true;
3089 }
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3624
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:544
bool * mergeactive
Definition: tuplesort.c:376

◆ mergeruns()

static void mergeruns ( Tuplesortstate state)
static

Definition at line 2735 of file tuplesort.c.

References SortSupportData::abbrev_abort, SortSupportData::abbrev_converter, SortSupportData::abbrev_full_comparator, Assert, Tuplesortstate::availMem, beginmerge(), SortSupportData::comparator, Tuplesortstate::currentRun, elog, FREEMEM, GetMemoryChunkSpace(), init_slab_allocator(), INT64_FORMAT, Tuplesortstate::Level, LOG, LogicalTapeFreeze(), LogicalTapeRewindForRead(), LogicalTapeRewindForWrite(), LogicalTapeSetForgetFreeSpace(), Tuplesortstate::maincontext, Max, Tuplesortstate::maxTapes, MemoryContextAlloc(), MemoryContextResetOnly(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, mergeonerun(), pfree(), Tuplesortstate::randomAccess, Tuplesortstate::read_buffer_size, Tuplesortstate::result_tape, Tuplesortstate::sortKeys, Tuplesortstate::status, TAPE_BUFFER_OVERHEAD, Tuplesortstate::tapeRange, Tuplesortstate::tapeset, Tuplesortstate::tp_dummy, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, trace_sort, TSS_BUILDRUNS, TSS_FINALMERGE, TSS_SORTEDONTAPE, Tuplesortstate::tuplecontext, Tuplesortstate::tuples, USEMEM, Tuplesortstate::worker, WORKER, and worker_freeze_result_tape().

Referenced by tuplesort_performsort().

2736 {
2737  int tapenum,
2738  svTape,
2739  svRuns,
2740  svDummy;
2741  int numTapes;
2742  int numInputTapes;
2743 
2744  Assert(state->status == TSS_BUILDRUNS);
2745  Assert(state->memtupcount == 0);
2746 
2747  if (state->sortKeys != NULL && state->sortKeys->abbrev_converter != NULL)
2748  {
2749  /*
2750  * If there are multiple runs to be merged, when we go to read back
2751  * tuples from disk, abbreviated keys will not have been stored, and
2752  * we don't care to regenerate them. Disable abbreviation from this
2753  * point on.
2754  */
2755  state->sortKeys->abbrev_converter = NULL;
2757 
2758  /* Not strictly necessary, but be tidy */
2759  state->sortKeys->abbrev_abort = NULL;
2760  state->sortKeys->abbrev_full_comparator = NULL;
2761  }
2762 
2763  /*
2764  * Reset tuple memory. We've freed all the tuples that we previously
2765  * allocated. We will use the slab allocator from now on.
2766  */
2768 
2769  /*
2770  * We no longer need a large memtuples array. (We will allocate a smaller
2771  * one for the heap later.)
2772  */
2773  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
2774  pfree(state->memtuples);
2775  state->memtuples = NULL;
2776 
2777  /*
2778  * If we had fewer runs than tapes, refund the memory that we imagined we
2779  * would need for the tape buffers of the unused tapes.
2780  *
2781  * numTapes and numInputTapes reflect the actual number of tapes we will
2782  * use. Note that the output tape's tape number is maxTapes - 1, so the
2783  * tape numbers of the used tapes are not consecutive, and you cannot just
2784  * loop from 0 to numTapes to visit all used tapes!
2785  */
2786  if (state->Level == 1)
2787  {
2788  numInputTapes = state->currentRun;
2789  numTapes = numInputTapes + 1;
2790  FREEMEM(state, (state->maxTapes - numTapes) * TAPE_BUFFER_OVERHEAD);
2791  }
2792  else
2793  {
2794  numInputTapes = state->tapeRange;
2795  numTapes = state->maxTapes;
2796  }
2797 
2798  /*
2799  * Initialize the slab allocator. We need one slab slot per input tape,
2800  * for the tuples in the heap, plus one to hold the tuple last returned
2801  * from tuplesort_gettuple. (If we're sorting pass-by-val Datums,
2802  * however, we don't need to do allocate anything.)
2803  *
2804  * From this point on, we no longer use the USEMEM()/LACKMEM() mechanism
2805  * to track memory usage of individual tuples.
2806  */
2807  if (state->tuples)
2808  init_slab_allocator(state, numInputTapes + 1);
2809  else
2810  init_slab_allocator(state, 0);
2811 
2812  /*
2813  * Allocate a new 'memtuples' array, for the heap. It will hold one tuple
2814  * from each input tape.
2815  */
2816  state->memtupsize = numInputTapes;
2817  state->memtuples = (SortTuple *) MemoryContextAlloc(state->maincontext,
2818  numInputTapes * sizeof(SortTuple));
2819  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
2820 
2821  /*
2822  * Use all the remaining memory we have available for read buffers among
2823  * the input tapes.
2824  *
2825  * We don't try to "rebalance" the memory among tapes, when we start a new
2826  * merge phase, even if some tapes are inactive in the new phase. That
2827  * would be hard, because logtape.c doesn't know where one run ends and
2828  * another begins. When a new merge phase begins, and a tape doesn't
2829  * participate in it, its buffer nevertheless already contains tuples from
2830  * the next run on same tape, so we cannot release the buffer. That's OK
2831  * in practice, merge performance isn't that sensitive to the amount of
2832  * buffers used, and most merge phases use all or almost all tapes,
2833  * anyway.
2834  */
2835 #ifdef TRACE_SORT
2836  if (trace_sort)
2837  elog(LOG, "worker %d using " INT64_FORMAT " KB of memory for read buffers among %d input tapes",
2838  state->worker, state->availMem / 1024, numInputTapes);
2839 #endif
2840 
2841  state->read_buffer_size = Max(state->availMem / numInputTapes, 0);
2842  USEMEM(state, state->read_buffer_size * numInputTapes);
2843 
2844  /* End of step D2: rewind all output tapes to prepare for merging */
2845  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2846  LogicalTapeRewindForRead(state->tapeset, tapenum, state->read_buffer_size);
2847 
2848  for (;;)
2849  {
2850  /*
2851  * At this point we know that tape[T] is empty. If there's just one
2852  * (real or dummy) run left on each input tape, then only one merge
2853  * pass remains. If we don't have to produce a materialized sorted
2854  * tape, we can stop at this point and do the final merge on-the-fly.
2855  */
2856  if (!state->randomAccess && !WORKER(state))
2857  {
2858  bool allOneRun = true;
2859 
2860  Assert(state->tp_runs[state->tapeRange] == 0);
2861  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2862  {
2863  if (state->tp_runs[tapenum] + state->tp_dummy[tapenum] != 1)
2864  {
2865  allOneRun = false;
2866  break;
2867  }
2868  }
2869  if (allOneRun)
2870  {
2871  /* Tell logtape.c we won't be writing anymore */
2873  /* Initialize for the final merge pass */
2874  beginmerge(state);
2875  state->status = TSS_FINALMERGE;
2876  return;
2877  }
2878  }
2879 
2880  /* Step D5: merge runs onto tape[T] until tape[P] is empty */
2881  while (state->tp_runs[state->tapeRange - 1] ||
2882  state->tp_dummy[state->tapeRange - 1])
2883  {
2884  bool allDummy = true;
2885 
2886  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2887  {
2888  if (state->tp_dummy[tapenum] == 0)
2889  {
2890  allDummy = false;
2891  break;
2892  }
2893  }
2894 
2895  if (allDummy)
2896  {
2897  state->tp_dummy[state->tapeRange]++;
2898  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2899  state->tp_dummy[tapenum]--;
2900  }
2901  else
2902  mergeonerun(state);
2903  }
2904 
2905  /* Step D6: decrease level */
2906  if (--state->Level == 0)
2907  break;
2908  /* rewind output tape T to use as new input */
2909  LogicalTapeRewindForRead(state->tapeset, state->tp_tapenum[state->tapeRange],
2910  state->read_buffer_size);
2911  /* rewind used-up input tape P, and prepare it for write pass */
2912  LogicalTapeRewindForWrite(state->tapeset, state->tp_tapenum[state->tapeRange - 1]);
2913  state->tp_runs[state->tapeRange - 1] = 0;
2914 
2915  /*
2916  * reassign tape units per step D6; note we no longer care about A[]
2917  */
2918  svTape = state->tp_tapenum[state->tapeRange];
2919  svDummy = state->tp_dummy[state->tapeRange];
2920  svRuns = state->tp_runs[state->tapeRange];
2921  for (tapenum = state->tapeRange; tapenum > 0; tapenum--)
2922  {
2923  state->tp_tapenum[tapenum] = state->tp_tapenum[tapenum - 1];
2924  state->tp_dummy[tapenum] = state->tp_dummy[tapenum - 1];
2925  state->tp_runs[tapenum] = state->tp_runs[tapenum - 1];
2926  }
2927  state->tp_tapenum[0] = svTape;
2928  state->tp_dummy[0] = svDummy;
2929  state->tp_runs[0] = svRuns;
2930  }
2931 
2932  /*
2933  * Done. Knuth says that the result is on TAPE[1], but since we exited
2934  * the loop without performing the last iteration of step D6, we have not
2935  * rearranged the tape unit assignment, and therefore the result is on
2936  * TAPE[T]. We need to do it this way so that we can freeze the final
2937  * output tape while rewinding it. The last iteration of step D6 would be
2938  * a waste of cycles anyway...
2939  */
2940  state->result_tape = state->tp_tapenum[state->tapeRange];
2941  if (!WORKER(state))
2942  LogicalTapeFreeze(state->tapeset, state->result_tape, NULL);
2943  else
2945  state->status = TSS_SORTEDONTAPE;
2946 
2947  /* Release the read buffers of all the other tapes, by rewinding them. */
2948  for (tapenum = 0; tapenum < state->maxTapes; tapenum++)
2949  {
2950  if (tapenum != state->result_tape)
2951  LogicalTapeRewindForWrite(state->tapeset, tapenum);
2952  }
2953 }
int64 availMem
Definition: tuplesort.c:250
size_t read_buffer_size
Definition: tuplesort.c:350
TupSortStatus status
Definition: tuplesort.c:242
static void mergeonerun(Tuplesortstate *state)
Definition: tuplesort.c:2962
static void worker_freeze_result_tape(Tuplesortstate *state)
Definition: tuplesort.c:4573
SortSupport sortKeys
Definition: tuplesort.c:430
MemoryContext maincontext
Definition: tuplesort.c:260
bool randomAccess
Definition: tuplesort.c:244
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
#define LOG
Definition: elog.h:26
void MemoryContextResetOnly(MemoryContext context)
Definition: mcxt.c:155
bool trace_sort
Definition: tuplesort.c:140
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:930
static void init_slab_allocator(Tuplesortstate *state, int numSlots)
Definition: tuplesort.c:2699
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:231
void pfree(void *pointer)
Definition: mcxt.c:1056
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
#define FREEMEM(state, amt)
Definition: tuplesort.c:547
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define WORKER(state)
Definition: tuplesort.c:549
#define Max(x, y)
Definition: c.h:914
#define Assert(condition)
Definition: c.h:738
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182
#define INT64_FORMAT
Definition: c.h:409
void LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Definition: logtape.c:842
int * tp_dummy
Definition: tuplesort.c:387
void LogicalTapeFreeze(LogicalTapeSet *lts, int tapenum, TapeShare *share)
Definition: logtape.c:1013
MemoryContext tuplecontext
Definition: tuplesort.c:263
int * tp_tapenum
Definition: tuplesort.c:388
#define USEMEM(state, amt)
Definition: tuplesort.c:546
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:796
#define elog(elevel,...)
Definition: elog.h:214
void LogicalTapeSetForgetFreeSpace(LogicalTapeSet *lts)
Definition: logtape.c:743
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:3025
SortTuple * memtuples
Definition: tuplesort.c:311

◆ puttuple_common()

static void puttuple_common ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 1811 of file tuplesort.c.

References Assert, Tuplesortstate::bound, Tuplesortstate::bounded, CHECK_FOR_INTERRUPTS, COMPARETUP, dumptuples(), elog, ERROR, free_sort_tuple(), grow_memtuples(), inittapes(), LACKMEM, LEADER, LOG, make_bounded_heap(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, pg_rusage_show(), Tuplesortstate::ru_start, Tuplesortstate::status, trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_INITIAL, and tuplesort_heap_replace_top().

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

1812 {
1813  Assert(!LEADER(state));
1814 
1815  switch (state->status)
1816  {
1817  case TSS_INITIAL:
1818 
1819  /*
1820  * Save the tuple into the unsorted array. First, grow the array
1821  * as needed. Note that we try to grow the array when there is
1822  * still one free slot remaining --- if we fail, there'll still be
1823  * room to store the incoming tuple, and then we'll switch to
1824  * tape-based operation.
1825  */
1826  if (state->memtupcount >= state->memtupsize - 1)
1827  {
1828  (void) grow_memtuples(state);
1829  Assert(state->memtupcount < state->memtupsize);
1830  }
1831  state->memtuples[state->memtupcount++] = *tuple;
1832 
1833  /*
1834  * Check if it's time to switch over to a bounded heapsort. We do
1835  * so if the input tuple count exceeds twice the desired tuple
1836  * count (this is a heuristic for where heapsort becomes cheaper
1837  * than a quicksort), or if we've just filled workMem and have
1838  * enough tuples to meet the bound.
1839  *
1840  * Note that once we enter TSS_BOUNDED state we will always try to
1841  * complete the sort that way. In the worst case, if later input
1842  * tuples are larger than earlier ones, this might cause us to
1843  * exceed workMem significantly.
1844  */
1845  if (state->bounded &&
1846  (state->memtupcount > state->bound * 2 ||
1847  (state->memtupcount > state->bound && LACKMEM(state))))
1848  {
1849 #ifdef TRACE_SORT
1850  if (trace_sort)
1851  elog(LOG, "switching to bounded heapsort at %d tuples: %s",
1852  state->memtupcount,
1853  pg_rusage_show(&state->ru_start));
1854 #endif
1855  make_bounded_heap(state);
1856  return;
1857  }
1858 
1859  /*
1860  * Done if we still fit in available memory and have array slots.
1861  */
1862  if (state->memtupcount < state->memtupsize && !LACKMEM(state))
1863  return;
1864 
1865  /*
1866  * Nope; time to switch to tape-based operation.
1867  */
1868  inittapes(state, true);
1869 
1870  /*
1871  * Dump all tuples.
1872  */
1873  dumptuples(state, false);
1874  break;
1875 
1876  case TSS_BOUNDED:
1877 
1878  /*
1879  * We don't want to grow the array here, so check whether the new
1880  * tuple can be discarded before putting it in. This should be a
1881  * good speed optimization, too, since when there are many more
1882  * input tuples than the bound, most input tuples can be discarded
1883  * with just this one comparison. Note that because we currently
1884  * have the sort direction reversed, we must check for <= not >=.
1885  */
1886  if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
1887  {
1888  /* new tuple <= top of the heap, so we can discard it */
1889  free_sort_tuple(state, tuple);
1891  }
1892  else
1893  {
1894  /* discard top of heap, replacing it with the new tuple */
1895  free_sort_tuple(state, &state->memtuples[0]);
1896  tuplesort_heap_replace_top(state, tuple);
1897  }
1898  break;
1899 
1900  case TSS_BUILDRUNS:
1901 
1902  /*
1903  * Save the tuple into the unsorted array (there must be space)
1904  */
1905  state->memtuples[state->memtupcount++] = *tuple;
1906 
1907  /*
1908  * If we are over the memory limit, dump all tuples.
1909  */
1910  dumptuples(state, false);
1911  break;
1912 
1913  default:
1914  elog(ERROR, "invalid tuplesort state");
1915  break;
1916  }
1917 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:3098
TupSortStatus status
Definition: tuplesort.c:242
static bool grow_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:1489
PGRUsage ru_start
Definition: tuplesort.c:481
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:2566
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
#define ERROR
Definition: elog.h:43
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4697
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:541
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define LEADER(state)
Definition: tuplesort.c:550
#define Assert(condition)
Definition: c.h:738
#define elog(elevel,...)
Definition: elog.h:214
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
static void make_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3390
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3566
#define LACKMEM(state)
Definition: tuplesort.c:545
SortTuple * memtuples
Definition: tuplesort.c:311

◆ readtup_alloc()

static void * readtup_alloc ( Tuplesortstate state,
Size  tuplen 
)
static

Definition at line 3651 of file tuplesort.c.

References Assert, buf, MemoryContextAlloc(), SlabSlot::nextfree, SLAB_SLOT_SIZE, Tuplesortstate::slabFreeHead, and Tuplesortstate::sortcontext.

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

3652 {
3653  SlabSlot *buf;
3654 
3655  /*
3656  * We pre-allocate enough slots in the slab arena that we should never run
3657  * out.
3658  */
3659  Assert(state->slabFreeHead);
3660 
3661  if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
3662  return MemoryContextAlloc(state->sortcontext, tuplen);
3663  else
3664  {
3665  buf = state->slabFreeHead;
3666  /* Reuse this slot */
3667  state->slabFreeHead = buf->nextfree;
3668 
3669  return buf;
3670  }
3671 }
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:196
union SlabSlot * nextfree
Definition: tuplesort.c:200
MemoryContext sortcontext
Definition: tuplesort.c:262
static char * buf
Definition: pg_test_fsync.c:67
#define Assert(condition)
Definition: c.h:738
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:796
SlabSlot * slabFreeHead
Definition: tuplesort.c:347

◆ readtup_cluster()

static void readtup_cluster ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

Definition at line 4086 of file tuplesort.c.

References SortTuple::datum1, heap_getattr, HEAPTUPLESIZE, IndexInfo::ii_IndexAttrNumbers, Tuplesortstate::indexInfo, InvalidOid, SortTuple::isnull1, LogicalTapeReadExact, Tuplesortstate::randomAccess, readtup_alloc(), HeapTupleData::t_data, HeapTupleData::t_len, HeapTupleData::t_self, HeapTupleData::t_tableOid, Tuplesortstate::tapeset, Tuplesortstate::tupDesc, and SortTuple::tuple.

Referenced by tuplesort_begin_cluster().

4088 {
4089  unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
4090  HeapTuple tuple = (HeapTuple) readtup_alloc(state,
4091  t_len + HEAPTUPLESIZE);
4092 
4093  /* Reconstruct the HeapTupleData header */
4094  tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
4095  tuple->t_len = t_len;
4096  LogicalTapeReadExact(state->tapeset, tapenum,
4097  &tuple->t_self, sizeof(ItemPointerData));
4098  /* We don't currently bother to reconstruct t_tableOid */
4099  tuple->t_tableOid = InvalidOid;
4100  /* Read in the tuple body */
4101  LogicalTapeReadExact(state->tapeset, tapenum,
4102  tuple->t_data, tuple->t_len);
4103  if (state->randomAccess) /* need trailing length word? */
4104  LogicalTapeReadExact(state->tapeset, tapenum,
4105  &tuplen, sizeof(tuplen));
4106  stup->tuple = (void *) tuple;
4107  /* set up first-column key value, if it's a simple column */
4108  if (state->indexInfo->ii_IndexAttrNumbers[0] != 0)
4109  stup->datum1 = heap_getattr(tuple,
4110  state->indexInfo->ii_IndexAttrNumbers[0],
4111  state->tupDesc,
4112  &stup->isnull1);
4113 }
HeapTupleData * HeapTuple
Definition: htup.h:71
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
bool randomAccess
Definition: tuplesort.c:244
Datum datum1
Definition: tuplesort.c:180
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:602
bool isnull1
Definition: tuplesort.c:181
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:179
ItemPointerData t_self
Definition: htup.h:65
uint32 t_len
Definition: htup.h:64
IndexInfo * indexInfo
Definition: tuplesort.c:451
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
Oid t_tableOid
Definition: htup.h:66
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:762
#define InvalidOid
Definition: postgres_ext.h:36
struct ItemPointerData ItemPointerData
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3651
#define HEAPTUPLESIZE
Definition: htup.h:73
AttrNumber ii_IndexAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:160
TupleDesc tupDesc
Definition: tuplesort.c:429

◆ readtup_datum()

static void readtup_datum ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

Definition at line 4434 of file tuplesort.c.

References Assert, SortTuple::datum1, SortTuple::isnull1, LogicalTapeReadExact, PointerGetDatum, Tuplesortstate::randomAccess, readtup_alloc(), Tuplesortstate::tapeset, SortTuple::tuple, and Tuplesortstate::tuples.

Referenced by tuplesort_begin_datum().

4436 {
4437  unsigned int tuplen = len - sizeof(unsigned int);
4438 
4439  if (tuplen == 0)
4440  {
4441  /* it's NULL */
4442  stup->datum1 = (Datum) 0;
4443  stup->isnull1 = true;
4444  stup->tuple = NULL;
4445  }
4446  else if (!state->tuples)
4447  {
4448  Assert(tuplen == sizeof(Datum));
4449  LogicalTapeReadExact(state->tapeset, tapenum,
4450  &stup->datum1, tuplen);
4451  stup->isnull1 = false;
4452  stup->tuple = NULL;
4453  }
4454  else
4455  {
4456  void *raddr = readtup_alloc(state, tuplen);
4457 
4458  LogicalTapeReadExact(state->tapeset, tapenum,
4459  raddr, tuplen);
4460  stup->datum1 = PointerGetDatum(raddr);
4461  stup->isnull1 = false;
4462  stup->tuple = raddr;
4463  }
4464 
4465  if (state->randomAccess) /* need trailing length word? */
4466  LogicalTapeReadExact(state->tapeset, tapenum,
4467  &tuplen, sizeof(tuplen));
4468 }
#define PointerGetDatum(X)
Definition: postgres.h:556
bool randomAccess
Definition: tuplesort.c:244
Datum datum1
Definition: tuplesort.c:180
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:602
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
uintptr_t Datum
Definition: postgres.h:367
#define Assert(condition)
Definition: c.h:738
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3651

◆ readtup_heap()

static void readtup_heap ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

Definition at line 3846 of file tuplesort.c.

References SortTuple::datum1, heap_getattr, SortTuple::isnull1, LogicalTapeReadExact, MINIMAL_TUPLE_DATA_OFFSET, MINIMAL_TUPLE_OFFSET, Tuplesortstate::randomAccess, readtup_alloc(), Tuplesortstate::sortKeys, SortSupportData::ssup_attno, HeapTupleData::t_data, HeapTupleData::t_len, MinimalTupleData::t_len, Tuplesortstate::tapeset, Tuplesortstate::tupDesc, and SortTuple::tuple.

Referenced by tuplesort_begin_heap().

3848 {
3849  unsigned int tupbodylen = len - sizeof(int);
3850  unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
3851  MinimalTuple tuple = (MinimalTuple) readtup_alloc(state, tuplen);
3852  char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
3853  HeapTupleData htup;
3854 
3855  /* read in the tuple proper */
3856  tuple->t_len = tuplen;
3857  LogicalTapeReadExact(state->tapeset, tapenum,
3858  tupbody, tupbodylen);
3859  if (state->randomAccess) /* need trailing length word? */
3860  LogicalTapeReadExact(state->tapeset, tapenum,
3861  &tuplen, sizeof(tuplen));
3862  stup->tuple = (void *) tuple;
3863  /* set up first-column key value */
3864  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3865  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3866  stup->datum1 = heap_getattr(&htup,
3867  state->sortKeys[0].ssup_attno,
3868  state->tupDesc,
3869  &stup->isnull1);
3870 }
#define MINIMAL_TUPLE_DATA_OFFSET
Definition: htup_details.h:623
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:430
bool randomAccess
Definition: tuplesort.c:244
Datum datum1
Definition: tuplesort.c:180
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:602
bool isnull1
Definition: tuplesort.c:181
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:179
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:762
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:619
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3651
TupleDesc tupDesc
Definition: tuplesort.c:429

◆ readtup_index()

static void readtup_index ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

Definition at line 4341 of file tuplesort.c.

References SortTuple::datum1, index_getattr, Tuplesortstate::indexRel, SortTuple::isnull1, LogicalTapeReadExact, Tuplesortstate::randomAccess, readtup_alloc(), RelationGetDescr, Tuplesortstate::tapeset, and SortTuple::tuple.

Referenced by tuplesort_begin_index_btree(), and tuplesort_begin_index_hash().

4343 {
4344  unsigned int tuplen = len - sizeof(unsigned int);
4345  IndexTuple tuple = (IndexTuple) readtup_alloc(state, tuplen);
4346 
4347  LogicalTapeReadExact(state->tapeset, tapenum,
4348  tuple, tuplen);
4349  if (state->randomAccess) /* need trailing length word? */
4350  LogicalTapeReadExact(state->tapeset, tapenum,
4351  &tuplen, sizeof(tuplen));
4352  stup->tuple = (void *) tuple;
4353  /* set up first-column key value */
4354  stup->datum1 = index_getattr(tuple,
4355  1,
4356  RelationGetDescr(state->indexRel),
4357  &stup->isnull1);
4358 }
#define RelationGetDescr(relation)
Definition: rel.h:482
bool randomAccess
Definition: tuplesort.c:244
Datum datum1
Definition: tuplesort.c:180
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:602
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
IndexTupleData * IndexTuple
Definition: itup.h:53
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
Relation indexRel
Definition: tuplesort.c:459
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3651

◆ reversedirection()

static void reversedirection ( Tuplesortstate state)
static

Definition at line 3606 of file tuplesort.c.

References Tuplesortstate::nKeys, Tuplesortstate::sortKeys, SortSupportData::ssup_nulls_first, and SortSupportData::ssup_reverse.

Referenced by make_bounded_heap(), and sort_bounded_heap().

3607 {
3608  SortSupport sortKey = state->sortKeys;
3609  int nkey;
3610 
3611  for (nkey = 0; nkey < state->nKeys; nkey++, sortKey++)
3612  {
3613  sortKey->ssup_reverse = !sortKey->ssup_reverse;
3614  sortKey->ssup_nulls_first = !sortKey->ssup_nulls_first;
3615  }
3616 }
bool ssup_nulls_first
Definition: sortsupport.h:75
SortSupport sortKeys
Definition: tuplesort.c:430

◆ selectnewtape()

static void selectnewtape ( Tuplesortstate state)
static

Definition at line 2667 of file tuplesort.c.

References Tuplesortstate::destTape, Tuplesortstate::Level, Tuplesortstate::tapeRange, Tuplesortstate::tp_dummy, and Tuplesortstate::tp_fib.

Referenced by dumptuples().

2668 {
2669  int j;
2670  int a;
2671 
2672  /* Step D3: advance j (destTape) */
2673  if (state->tp_dummy[state->destTape] < state->tp_dummy[state->destTape + 1])
2674  {
2675  state->destTape++;
2676  return;
2677  }
2678  if (state->tp_dummy[state->destTape] != 0)
2679  {
2680  state->destTape = 0;
2681  return;
2682  }
2683 
2684  /* Step D4: increase level */
2685  state->Level++;
2686  a = state->tp_fib[0];
2687  for (j = 0; j < state->tapeRange; j++)
2688  {
2689  state->tp_dummy[j] = a + state->tp_fib[j + 1] - state->tp_fib[j];
2690  state->tp_fib[j] = a + state->tp_fib[j + 1];
2691  }
2692  state->destTape = 0;
2693 }
int * tp_dummy
Definition: tuplesort.c:387

◆ sort_bounded_heap()

static void sort_bounded_heap ( Tuplesortstate state)
static

Definition at line 3439 of file tuplesort.c.

References Assert, Tuplesortstate::bound, Tuplesortstate::bounded, Tuplesortstate::boundUsed, Tuplesortstate::memtupcount, Tuplesortstate::memtuples, reversedirection(), SERIAL, Tuplesortstate::status, TSS_BOUNDED, TSS_SORTEDINMEM, and tuplesort_heap_delete_top().

Referenced by tuplesort_performsort().

3440 {
3441  int tupcount = state->memtupcount;
3442 
3443  Assert(state->status == TSS_BOUNDED);
3444  Assert(state->bounded);
3445  Assert(tupcount == state->bound);
3446  Assert(SERIAL(state));
3447 
3448  /*
3449  * We can unheapify in place because each delete-top call will remove the
3450  * largest entry, which we can promptly store in the newly freed slot at
3451  * the end. Once we're down to a single-entry heap, we're done.
3452  */
3453  while (state->memtupcount > 1)
3454  {
3455  SortTuple stup = state->memtuples[0];
3456 
3457  /* this sifts-up the next-largest entry and decreases memtupcount */
3459  state->memtuples[state->memtupcount] = stup;
3460  }
3461  state->memtupcount = tupcount;
3462 
3463  /*
3464  * Reverse sort direction back to the original state. This is not
3465  * actually necessary but seems like a good idea for tidiness.
3466  */
3467  reversedirection(state);
3468 
3469  state->status = TSS_SORTEDINMEM;
3470  state->boundUsed = true;
3471 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3606
TupSortStatus status
Definition: tuplesort.c:242
#define SERIAL(state)
Definition: tuplesort.c:548
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3542
#define Assert(condition)
Definition: c.h:738
SortTuple * memtuples
Definition: tuplesort.c:311

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 4525 of file tuplesort.c.

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

4526 {
4527  /* Attach to SharedFileSet */
4528  SharedFileSetAttach(&shared->fileset, seg);
4529 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:78
SharedFileSet fileset
Definition: tuplesort.c:506

◆ tuplesort_begin_batch()

static void tuplesort_begin_batch ( Tuplesortstate state)
static

Definition at line 814 of file tuplesort.c.

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Tuplesortstate::allowedMem, Tuplesortstate::availMem, Tuplesortstate::bounded, Tuplesortstate::boundUsed, Tuplesortstate::currentRun, elog, ERROR, GetMemoryChunkSpace(), Tuplesortstate::growmemtuples, INITIAL_MEMTUPSIZE, LACKMEM, Tuplesortstate::maincontext, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, palloc(), pfree(), Tuplesortstate::result_tape, Tuplesortstate::slabAllocatorUsed, Tuplesortstate::sortcontext, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_INITIAL, Tuplesortstate::tuplecontext, and USEMEM.

Referenced by tuplesort_begin_common(), and tuplesort_reset().

815 {
816  MemoryContext oldcontext;
817 
818  oldcontext = MemoryContextSwitchTo(state->maincontext);
819 
820  /*
821  * Caller tuple (e.g. IndexTuple) memory context.
822  *
823  * A dedicated child context used exclusively for caller passed tuples
824  * eases memory management. Resetting at key points reduces
825  * fragmentation. Note that the memtuples array of SortTuples is allocated
826  * in the parent context, not this context, because there is no need to
827  * free memtuples early.
828  */
830  "Caller tuples",
832 
833  state->status = TSS_INITIAL;
834  state->bounded = false;
835  state->boundUsed = false;
836 
837  state->availMem = state->allowedMem;
838 
839  state->tapeset = NULL;
840 
841  state->memtupcount = 0;
842 
843  /*
844  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
845  * see comments in grow_memtuples().
846  */
847  state->growmemtuples = true;
848  state->slabAllocatorUsed = false;
849  if (state->memtuples != NULL && state->memtupsize != INITIAL_MEMTUPSIZE)
850  {
851  pfree(state->memtuples);
852  state->memtuples = NULL;
854  }
855  if (state->memtuples == NULL)
856  {
857  state->memtuples = (SortTuple *) palloc(state->memtupsize * sizeof(SortTuple));
858  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
859  }
860 
861  /* workMem must be large enough for the minimal memtuples array */
862  if (LACKMEM(state))
863  elog(ERROR, "insufficient memory allowed for sort");
864 
865  state->currentRun = 0;
866 
867  /*
868  * maxTapes, tapeRange, and Algorithm D variables will be initialized by
869  * inittapes(), if needed
870  */
871 
872  state->result_tape = -1; /* flag that result tape has not been formed */
873 
874  MemoryContextSwitchTo(oldcontext);
875 }
int64 availMem
Definition: tuplesort.c:250
TupSortStatus status
Definition: tuplesort.c:242
#define AllocSetContextCreate
Definition: memutils.h:170
MemoryContext maincontext
Definition: tuplesort.c:260
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
bool growmemtuples
Definition: tuplesort.c:314
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
void pfree(void *pointer)
Definition: mcxt.c:1056
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:192
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
int64 allowedMem
Definition: tuplesort.c:251
#define INITIAL_MEMTUPSIZE
Definition: tuplesort.c:135
bool slabAllocatorUsed
Definition: tuplesort.c:343
MemoryContext tuplecontext
Definition: tuplesort.c:263
void * palloc(Size size)
Definition: mcxt.c:949
#define USEMEM(state, amt)
Definition: tuplesort.c:546
#define elog(elevel,...)
Definition: elog.h:214
#define LACKMEM(state)
Definition: tuplesort.c:545
SortTuple * memtuples
Definition: tuplesort.c:311

◆ tuplesort_begin_cluster()

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

Definition at line 952 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

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

◆ tuplesort_begin_common()

static Tuplesortstate * tuplesort_begin_common ( int  workMem,
SortCoordinate  coordinate,
bool  randomAccess 
)
static

Definition at line 702 of file tuplesort.c.

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Tuplesortstate::allowedMem, Assert, CurrentMemoryContext, elog, ERROR, INITIAL_MEMTUPSIZE, SortCoordinateData::isWorker, Tuplesortstate::maincontext, Max, MemoryContextSwitchTo(), Tuplesortstate::memtuples, Tuplesortstate::memtupsize, SortCoordinateData::nParticipants, Tuplesortstate::nParticipants, palloc0(), pg_rusage_init(), Tuplesortstate::randomAccess, Tuplesortstate::ru_start, Tuplesortstate::shared, SortCoordinateData::sharedsort, Tuplesortstate::sortcontext, trace_sort, Tuplesortstate::tuples, tuplesort_begin_batch(), Tuplesortstate::worker, and worker_get_identifier().

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

704 {
706  MemoryContext maincontext;
707  MemoryContext sortcontext;
708  MemoryContext oldcontext;
709 
710  /* See leader_takeover_tapes() remarks on randomAccess support */
711  if (coordinate && randomAccess)
712  elog(ERROR, "random access disallowed under parallel sort");
713 
714  /*
715  * Memory context surviving tuplesort_reset. This memory context holds
716  * data which is useful to keep while sorting multiple similar batches.
717  */
719  "TupleSort main",
721 
722  /*
723  * Create a working memory context for one sort operation. The content of
724  * this context is deleted by tuplesort_reset.
725  */
726  sortcontext = AllocSetContextCreate(maincontext,
727  "TupleSort sort",
729 
730  /*
731  * Additionally a working memory context for tuples is setup in
732  * tuplesort_begin_batch.
733  */
734 
735  /*
736  * Make the Tuplesortstate within the per-sortstate context. This way, we
737  * don't need a separate pfree() operation for it at shutdown.
738  */
739  oldcontext = MemoryContextSwitchTo(maincontext);
740 
741  state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));
742 
743 #ifdef TRACE_SORT
744  if (trace_sort)
745  pg_rusage_init(&state->ru_start);
746 #endif
747 
748  state->randomAccess = randomAccess;
749  state->tuples = true;
750 
751  /*
752  * workMem is forced to be at least 64KB, the current minimum valid value
753  * for the work_mem GUC. This is a defense against parallel sort callers
754  * that divide out memory among many workers in a way that leaves each
755  * with very little memory.
756  */
757  state->allowedMem = Max(workMem, 64) * (int64) 1024;
758  state->sortcontext = sortcontext;
759  state->maincontext = maincontext;
760 
761  /*
762  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
763  * see comments in grow_memtuples().
764  */
766  state->memtuples = NULL;
767 
768  /*
769  * After all of the other non-parallel-related state, we setup all of the
770  * state needed for each batch.
771  */
772  tuplesort_begin_batch(state);
773 
774  /*
775  * Initialize parallel-related state based on coordination information
776  * from caller
777  */
778  if (!coordinate)
779  {
780  /* Serial sort */
781  state->shared = NULL;
782  state->worker = -1;
783  state->nParticipants = -1;
784  }
785  else if (coordinate->isWorker)
786  {
787  /* Parallel worker produces exactly one final run from all input */
788  state->shared = coordinate->sharedsort;
789  state->worker = worker_get_identifier(state);
790  state->nParticipants = -1;
791  }
792  else
793  {
794  /* Parallel leader state only used for final merge */
795  state->shared = coordinate->sharedsort;
796  state->worker = -1;
797  state->nParticipants = coordinate->nParticipants;
798  Assert(state->nParticipants >= 1);
799  }
800 
801  MemoryContextSwitchTo(oldcontext);
802 
803  return state;
804 }
#define AllocSetContextCreate
Definition: memutils.h:170
PGRUsage ru_start
Definition: tuplesort.c:481
MemoryContext maincontext
Definition: tuplesort.c:260
bool randomAccess
Definition: tuplesort.c:244
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Sharedsort * sharedsort
Definition: tuplesort.h:55
static int worker_get_identifier(Tuplesortstate *state)
Definition: tuplesort.c:4545
bool trace_sort
Definition: tuplesort.c:140
void pg_rusage_init(PGRUsage *ru0)
Definition: pg_rusage.c:27
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:814
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:262
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:192
Sharedsort * shared
Definition: tuplesort.c:421
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
int64 allowedMem
Definition: tuplesort.c:251
void * palloc0(Size size)
Definition: mcxt.c:980
#define Max(x, y)
Definition: c.h:914
#define Assert(condition)
Definition: c.h:738
Definition: regguts.h:298
#define INITIAL_MEMTUPSIZE
Definition: tuplesort.c:135
#define elog(elevel,...)
Definition: elog.h:214
SortTuple * memtuples
Definition: tuplesort.c:311

◆ tuplesort_begin_datum()

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

Definition at line 1171 of file tuplesort.c.

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

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

1174 {
1175  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1176  randomAccess);
1177  MemoryContext oldcontext;
1178  int16 typlen;
1179  bool typbyval;
1180 
1181  oldcontext = MemoryContextSwitchTo(state->maincontext);
1182 
1183 #ifdef TRACE_SORT
1184  if (trace_sort)
1185  elog(LOG,
1186  "begin datum sort: workMem = %d, randomAccess = %c",
1187  workMem, randomAccess ? 't' : 'f');
1188 #endif
1189 
1190  state->nKeys = 1; /* always a one-column sort */
1191 
1192  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
1193  false, /* no unique check */
1194  1,
1195  workMem,
1196  randomAccess,
1197  PARALLEL_SORT(state));
1198 
1199  state->comparetup = comparetup_datum;
1200  state->copytup = copytup_datum;
1201  state->writetup = writetup_datum;
1202  state->readtup = readtup_datum;
1203  state->abbrevNext = 10;
1204 
1205  state->datumType = datumType;
1206 
1207  /* lookup necessary attributes of the datum type */
1208  get_typlenbyval(datumType, &typlen, &typbyval);
1209  state->datumTypeLen = typlen;
1210  state->tuples = !typbyval;
1211 
1212  /* Prepare SortSupport data */
1213  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1214 
1216  state->sortKeys->ssup_collation = sortCollation;
1217  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1218 
1219  /*
1220  * Abbreviation is possible here only for by-reference types. In theory,
1221  * a pass-by-value datatype could have an abbreviated form that is cheaper
1222  * to compare. In a tuple sort, we could support that, because we can
1223  * always extract the original datum from the tuple as needed. Here, we
1224  * can't, because a datum sort only stores a single copy of the datum; the
1225  * "tuple" field of each SortTuple is NULL.
1226  */
1227  state->sortKeys->abbreviate = !typbyval;
1228 
1229  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1230 
1231  /*
1232  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1233  * tie-breaker comparisons may be required. Typically, the optimization
1234  * is only of value to pass-by-value types anyway, whereas abbreviated
1235  * keys are typically only of value to pass-by-reference types.
1236  */
1237  if (!state->sortKeys->abbrev_converter)
1238  state->onlyKey = state->sortKeys;
1239 
1240  MemoryContextSwitchTo(oldcontext);
1241 
1242  return state;
1243 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:354
bool ssup_nulls_first
Definition: sortsupport.h:75
int64 abbrevNext
Definition: tuplesort.c:444
SortSupport sortKeys
Definition: tuplesort.c:430
MemoryContext maincontext
Definition: tuplesort.c:260
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:283
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:275
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
#define PARALLEL_SORT(state)
Definition: tuplesort.c:125
#define DATUM_SORT
Definition: tuplesort.c:121
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4365
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:301
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4386
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4434
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
static void writetup_datum(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4393
void * palloc0(Size size)
Definition: mcxt.c:980
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:293
Definition: regguts.h:298
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2139
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:702
#define elog(elevel,...)
Definition: elog.h:214
SortSupport onlyKey
Definition: tuplesort.c:436

◆ tuplesort_begin_heap()

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

Definition at line 878 of file tuplesort.c.

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

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

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

◆ tuplesort_begin_index_btree()

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

Definition at line 1047 of file tuplesort.c.

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

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

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

◆ tuplesort_begin_index_hash()

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

Definition at line 1125 of file tuplesort.c.

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

Referenced by _h_spoolinit().

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

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1388 of file tuplesort.c.

References Tuplesortstate::maincontext, MemoryContextDelete(), and tuplesort_free().

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

1389 {
1390  tuplesort_free(state);
1391 
1392  /*
1393  * Free the main memory context, including the Tuplesortstate struct
1394  * itself.
1395  */
1397 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
MemoryContext maincontext
Definition: tuplesort.c:260
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1315

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nWorkers)

Definition at line 4481 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

4482 {
4483  Size tapesSize;
4484 
4485  Assert(nWorkers > 0);
4486 
4487  /* Make sure that BufFile shared state is MAXALIGN'd */
4488  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4489  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4490 
4491  return tapesSize;
4492 }
Size mul_size(Size s1, Size s2)
Definition: shmem.c:515
Size add_size(Size s1, Size s2)
Definition: shmem.c:498
#define Assert(condition)
Definition: c.h:738
size_t Size
Definition: c.h:466
#define MAXALIGN(LEN)
Definition: c.h:691
#define offsetof(type, field)
Definition: c.h:661

◆ tuplesort_free()

static void tuplesort_free ( Tuplesortstate state)
static

Definition at line 1315 of file tuplesort.c.

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

Referenced by tuplesort_end(), and tuplesort_reset().

1316 {
1317  /* context swap probably not needed, but let's be safe */
1318  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1319 
1320 #ifdef TRACE_SORT
1321  long spaceUsed;
1322 
1323  if (state->tapeset)
1324  spaceUsed = LogicalTapeSetBlocks(state->tapeset);
1325  else
1326  spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
1327 #endif
1328 
1329  /*
1330  * Delete temporary "tape" files, if any.
1331  *
1332  * Note: want to include this in reported total cost of sort, hence need
1333  * for two #ifdef TRACE_SORT sections.
1334  */
1335  if (state->tapeset)
1336  LogicalTapeSetClose(state->tapeset);
1337 
1338 #ifdef TRACE_SORT
1339  if (trace_sort)
1340  {
1341  if (state->tapeset)
1342  elog(LOG, "%s of worker %d ended, %ld disk blocks used: %s",
1343  SERIAL(state) ? "external sort" : "parallel external sort",
1344  state->worker, spaceUsed, pg_rusage_show(&state->ru_start));
1345  else
1346  elog(LOG, "%s of worker %d ended, %ld KB used: %s",
1347  SERIAL(state) ? "internal sort" : "unperformed parallel sort",
1348  state->worker, spaceUsed, pg_rusage_show(&state->ru_start));
1349  }
1350 
1351  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
1352 #else
1353 
1354  /*
1355  * If you disabled TRACE_SORT, you can still probe sort__done, but you
1356  * ain't getting space-used stats.
1357  */
1358  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, 0L);
1359 #endif
1360 
1361  /* Free any execution state created for CLUSTER case */
1362  if (state->estate != NULL)
1363  {
1364  ExprContext *econtext = GetPerTupleExprContext(state->estate);
1365 
1367  FreeExecutorState(state->estate);
1368  }
1369 
1370  MemoryContextSwitchTo(oldcontext);
1371 
1372  /*
1373  * Free the per-sort memory context, thereby releasing all working memory.
1374  */
1376 }
int64 availMem
Definition: tuplesort.c:250
PGRUsage ru_start
Definition: tuplesort.c:481
#define SERIAL(state)
Definition: tuplesort.c:548
EState * estate
Definition: tuplesort.c:452
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:140
void FreeExecutorState(EState *estate)
Definition: execUtils.c:191
#define GetPerTupleExprContext(estate)
Definition: executor.h:507
MemoryContext sortcontext
Definition: tuplesort.c:262
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1224
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
int64 allowedMem
Definition: tuplesort.c:251
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:226
#define elog(elevel,...)
Definition: elog.h:214
void LogicalTapeSetClose(LogicalTapeSet *lts)
Definition: logtape.c:716
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:1248

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 3302 of file tuplesort.c.

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

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

3304 {
3305  /*
3306  * Note: it might seem we should provide both memory and disk usage for a
3307  * disk-based sort. However, the current code doesn't track memory space
3308  * accurately once we have begun to return tuples to the caller (since we
3309  * don't account for pfree's the caller is expected to do), so we cannot
3310  * rely on availMem in a disk sort. This does not seem worth the overhead
3311  * to fix. Is it worth creating an API for the memory context code to
3312  * tell us how much is actually used in sortcontext?
3313  */
3314  tuplesort_updatemax(state);
3315 
3316  if (state->isMaxSpaceDisk)
3318  else
3320  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
3321 
3322  switch (state->maxSpaceStatus)
3323  {
3324  case TSS_SORTEDINMEM:
3325  if (state->boundUsed)
3327  else
3329  break;
3330  case TSS_SORTEDONTAPE:
3332  break;
3333  case TSS_FINALMERGE:
3335  break;
3336  default:
3338  break;
3339  }
3340 }
bool isMaxSpaceDisk
Definition: tuplesort.c:256
int64 maxSpace
Definition: tuplesort.c:254
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1405
TupSortStatus maxSpaceStatus
Definition: tuplesort.c:259
TuplesortMethod sortMethod
Definition: tuplesort.h:91
TuplesortSpaceType spaceType
Definition: tuplesort.h:92

◆ tuplesort_getdatum()

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

Definition at line 2418 of file tuplesort.c.

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

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

2420 {
2421  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2422  SortTuple stup;
2423 
2424  if (!tuplesort_gettuple_common(state, forward, &stup))
2425  {
2426  MemoryContextSwitchTo(oldcontext);
2427  return false;
2428  }
2429 
2430  /* Ensure we copy into caller's memory context */
2431  MemoryContextSwitchTo(oldcontext);
2432 
2433  /* Record abbreviated key for caller */
2434  if (state->sortKeys->abbrev_converter && abbrev)
2435  *abbrev = stup.datum1;
2436 
2437  if (stup.isnull1 || !state->tuples)
2438  {
2439  *val = stup.datum1;
2440  *isNull = stup.isnull1;
2441  }
2442  else
2443  {
2444  /* use stup.tuple because stup.datum1 may be an abbreviation */
2445  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2446  *isNull = false;
2447  }
2448 
2449  return true;
2450 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:430
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:180
bool isnull1
Definition: tuplesort.c:181
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:131
long val
Definition: informix.c:664

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2369 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

2370 {
2371  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2372  SortTuple stup;
2373 
2374  if (!tuplesort_gettuple_common(state, forward, &stup))
2375  stup.tuple = NULL;
2376 
2377  MemoryContextSwitchTo(oldcontext);
2378 
2379  return stup.tuple;
2380 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2389 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

2390 {
2391  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2392  SortTuple stup;
2393 
2394  if (!tuplesort_gettuple_common(state, forward, &stup))
2395  stup.tuple = NULL;
2396 
2397  MemoryContextSwitchTo(oldcontext);
2398 
2399  return (IndexTuple) stup.tuple;
2400 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:179
MemoryContext sortcontext
Definition: tuplesort.c:262
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2075

◆ tuplesort_gettuple_common()

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

Definition at line 2075 of file tuplesort.c.

References Assert, Tuplesortstate::bound, Tuplesortstate::bounded, Tuplesortstate::current, elog, Tuplesortstate::eof_reached, ERROR, getlen(), Tuplesortstate::lastReturnedTuple, LogicalTapeBackspace(), LogicalTapeRewindForWrite(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, mergereadnext(), Tuplesortstate::randomAccess, READTUP, RELEASE_SLAB_SLOT, Tuplesortstate::result_tape, Tuplesortstate::slabAllocatorUsed, SortTuple::srctape, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_FINALMERGE, TSS_SORTEDINMEM, TSS_SORTEDONTAPE, SortTuple::tuple, tuplesort_heap_delete_top(), tuplesort_heap_replace_top(), and WORKER.

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

2077 {
2078  unsigned int tuplen;
2079  size_t nmoved;
2080 
2081  Assert(!WORKER(state));
2082 
2083  switch (state->status)
2084  {
2085  case TSS_SORTEDINMEM:
2086  Assert(forward || state->randomAccess);
2087  Assert(!state->slabAllocatorUsed);
2088  if (forward)
2089  {
2090  if (state->current < state->memtupcount)
2091  {
2092  *stup = state->memtuples[state->current++];
2093  return true;
2094  }
2095  state->eof_reached = true;
2096 
2097  /*
2098  * Complain if caller tries to retrieve more tuples than
2099  * originally asked for in a bounded sort. This is because
2100  * returning EOF here might be the wrong thing.
2101  */
2102  if (state->bounded && state->current >= state->bound)
2103  elog(ERROR, "retrieved too many tuples in a bounded sort");
2104 
2105  return false;
2106  }
2107  else
2108  {
2109  if (state->current <= 0)
2110  return false;
2111 
2112  /*
2113  * if all tuples are fetched already then we return last
2114  * tuple, else - tuple before last returned.
2115  */
2116  if (state->eof_reached)
2117  state->eof_reached = false;
2118  else
2119  {
2120  state->current--; /* last returned tuple */
2121  if (state->current <= 0)
2122  return false;
2123  }
2124  *stup = state->memtuples[state->current - 1];
2125  return true;
2126  }
2127  break;
2128 
2129  case TSS_SORTEDONTAPE:
2130  Assert(forward || state->randomAccess);
2131  Assert(state->slabAllocatorUsed);
2132 
2133  /*
2134  * The slot that held the tuple that we returned in previous
2135  * gettuple call can now be reused.
2136  */
2137  if (state->lastReturnedTuple)
2138  {
2139  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
2140  state->lastReturnedTuple = NULL;
2141  }
2142 
2143  if (forward)
2144  {
2145  if (state->eof_reached)
2146  return false;
2147 
2148  if ((tuplen = getlen(state, state->result_tape, true)) != 0)
2149  {
2150  READTUP(state, stup, state->result_tape, tuplen);
2151 
2152  /*
2153  * Remember the tuple we return, so that we can recycle
2154  * its memory on next call. (This can be NULL, in the
2155  * !state->tuples case).
2156  */
2157  state->lastReturnedTuple = stup->tuple;
2158 
2159  return true;
2160  }
2161  else
2162  {
2163  state->eof_reached = true;
2164  return false;
2165  }
2166  }
2167 
2168  /*
2169  * Backward.
2170  *
2171  * if all tuples are fetched already then we return last tuple,
2172  * else - tuple before last returned.
2173  */
2174  if (state->eof_reached)
2175  {
2176  /*
2177  * Seek position is pointing just past the zero tuplen at the
2178  * end of file; back up to fetch last tuple's ending length
2179  * word. If seek fails we must have a completely empty file.
2180  */
2181  nmoved = LogicalTapeBackspace(state->tapeset,
2182  state->result_tape,
2183  2 * sizeof(unsigned int));
2184  if (nmoved == 0)
2185  return false;
2186  else if (nmoved != 2 * sizeof(unsigned int))
2187  elog(ERROR, "unexpected tape position");
2188  state->eof_reached = false;
2189  }
2190  else
2191  {
2192  /*
2193  * Back up and fetch previously-returned tuple's ending length
2194  * word. If seek fails, assume we are at start of file.
2195  */
2196  nmoved = LogicalTapeBackspace(state->tapeset,
2197  state->result_tape,
2198  sizeof(unsigned int));
2199  if (nmoved == 0)
2200  return false;
2201  else if (nmoved != sizeof(unsigned int))
2202  elog(ERROR, "unexpected tape position");
2203  tuplen = getlen(state, state->result_tape, false);
2204 
2205  /*
2206  * Back up to get ending length word of tuple before it.
2207  */
2208  nmoved = LogicalTapeBackspace(state->tapeset,
2209  state->result_tape,
2210  tuplen + 2 * sizeof(unsigned int));
2211  if (nmoved == tuplen + sizeof(unsigned int))
2212  {
2213  /*
2214  * We backed up over the previous tuple, but there was no
2215  * ending length word before it. That means that the prev
2216  * tuple is the first tuple in the file. It is now the
2217  * next to read in forward direction (not obviously right,
2218  * but that is what in-memory case does).
2219  */
2220  return false;
2221  }
2222  else if (nmoved != tuplen + 2 * sizeof(unsigned int))
2223  elog(ERROR, "bogus tuple length in backward scan");
2224  }
2225 
2226  tuplen = getlen(state, state->result_tape, false);
2227 
2228  /*
2229  * Now we have the length of the prior tuple, back up and read it.
2230  * Note: READTUP expects we are positioned after the initial
2231  * length word of the tuple, so back up to that point.
2232  */
2233  nmoved = LogicalTapeBackspace(state->tapeset,
2234  state->result_tape,
2235  tuplen);
2236  if (nmoved != tuplen)
2237  elog(ERROR, "bogus tuple length in backward scan");
2238  READTUP(state, stup, state->result_tape, tuplen);
2239 
2240  /*
2241  * Remember the tuple we return, so that we can recycle its memory
2242  * on next call. (This can be NULL, in the Datum case).
2243  */
2244  state->lastReturnedTuple = stup->tuple;
2245 
2246  return true;
2247 
2248  case TSS_FINALMERGE:
2249  Assert(forward);
2250  /* We are managing memory ourselves, with the slab allocator. */
2251  Assert(state->slabAllocatorUsed);
2252 
2253  /*
2254  * The slab slot holding the tuple that we returned in previous
2255  * gettuple call can now be reused.
2256  */
2257  if (state->lastReturnedTuple)
2258  {
2259  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
2260  state->lastReturnedTuple = NULL;
2261  }
2262 
2263  /*
2264  * This code should match the inner loop of mergeonerun().
2265  */
2266  if (state->memtupcount > 0)
2267  {
2268  int srcTape = state->memtuples[0].srctape;
2269  SortTuple newtup;
2270 
2271  *stup = state->memtuples[0];
2272 
2273  /*
2274  * Remember the tuple we return, so that we can recycle its
2275  * memory on next call. (This can be NULL, in the Datum case).
2276  */
2277  state->lastReturnedTuple = stup->tuple;
2278 
2279  /*
2280  * Pull next tuple from tape, and replace the returned tuple
2281  * at top of the heap with it.
2282  */
2283  if (!mergereadnext(state, srcTape, &newtup))
2284  {
2285  /*
2286  * If no more data, we've reached end of run on this tape.
2287  * Remove the top node from the heap.
2288  */
2290 
2291  /*
2292  * Rewind to free the read buffer. It'd go away at the
2293  * end of the sort anyway, but better to release the
2294  * memory early.
2295  */
2296  LogicalTapeRewindForWrite(state->tapeset, srcTape);
2297  return true;
2298  }
2299  newtup.srctape = srcTape;
2300  tuplesort_heap_replace_top(state, &newtup);
2301  return true;
2302  }
2303  return false;
2304 
2305  default:
2306  elog(ERROR, "invalid tuplesort state");
2307  return false; /* keep compiler quiet */
2308  }
2309 }
TupSortStatus status
Definition: tuplesort.c:242
bool randomAccess
Definition: tuplesort.c:244
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:930
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3624
void * tuple
Definition: tuplesort.c:179
#define ERROR
Definition: elog.h:43
void * lastReturnedTuple
Definition: tuplesort.c:358
size_t LogicalTapeBackspace(LogicalTapeSet *lts, int tapenum, size_t size)
Definition: logtape.c:1116
LogicalTapeSet * tapeset
Definition: tuplesort.c:264
#define WORKER(state)
Definition: tuplesort.c:549
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:544
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:529
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3542
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:3073
#define Assert(condition)
Definition: c.h:738
int srctape
Definition: tuplesort.c:182
bool eof_reached
Definition: tuplesort.c:398
bool slabAllocatorUsed
Definition: tuplesort.c:343
#define elog(elevel,...)
Definition: elog.h:214