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

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

◆ LACKMEM

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

Definition at line 527 of file tuplesort.c.

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

◆ 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:822
#define ERROR
Definition: elog.h:43

Definition at line 584 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 220 of file tuplesort.c.

Referenced by tuplesort_merge_order().

◆ MERGE_BUFFER_SIZE

#define MERGE_BUFFER_SIZE   (BLCKSZ * 32)

Definition at line 222 of file tuplesort.c.

Referenced by tuplesort_merge_order().

◆ MINORDER

#define MINORDER   6 /* minimum merge order */

Definition at line 219 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 526 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:1031
static char * buf
Definition: pg_test_fsync.c:68
Definition: regguts.h:298
#define IS_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:503

Definition at line 511 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 186 of file tuplesort.c.

Referenced by init_slab_allocator(), and readtup_alloc().

◆ TAPE_BUFFER_OVERHEAD

#define TAPE_BUFFER_OVERHEAD   BLCKSZ

Definition at line 221 of file tuplesort.c.

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

◆ USEMEM

◆ WORKER

◆ WRITETUP

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

Definition at line 525 of file tuplesort.c.

Referenced by dumptuples(), and mergeonerun().

Typedef Documentation

◆ SlabSlot

◆ SortTupleComparator

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

Definition at line 224 of file tuplesort.c.

Enumeration Type Documentation

◆ TupSortStatus

Enumerator
TSS_INITIAL 
TSS_BOUNDED 
TSS_BUILDRUNS 
TSS_SORTEDINMEM 
TSS_SORTEDONTAPE 
TSS_FINALMERGE 

Definition at line 198 of file tuplesort.c.

199 {
200  TSS_INITIAL, /* Loading tuples; still within memory limit */
201  TSS_BOUNDED, /* Loading tuples into bounded-size heap */
202  TSS_BUILDRUNS, /* Loading tuples; writing to tape */
203  TSS_SORTEDINMEM, /* Sort completed entirely in memory */
204  TSS_SORTEDONTAPE, /* Sort completed, final run is on tape */
205  TSS_FINALMERGE /* Performing final merge on-the-fly */
206 } TupSortStatus;
TupSortStatus
Definition: tuplesort.c:198

Function Documentation

◆ beginmerge()

static void beginmerge ( Tuplesortstate state)
static

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

2852 {
2853  int activeTapes;
2854  int tapenum;
2855  int srcTape;
2856 
2857  /* Heap should be empty here */
2858  Assert(state->memtupcount == 0);
2859 
2860  /* Adjust run counts and mark the active tapes */
2861  memset(state->mergeactive, 0,
2862  state->maxTapes * sizeof(*state->mergeactive));
2863  activeTapes = 0;
2864  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2865  {
2866  if (state->tp_dummy[tapenum] > 0)
2867  state->tp_dummy[tapenum]--;
2868  else
2869  {
2870  Assert(state->tp_runs[tapenum] > 0);
2871  state->tp_runs[tapenum]--;
2872  srcTape = state->tp_tapenum[tapenum];
2873  state->mergeactive[srcTape] = true;
2874  activeTapes++;
2875  }
2876  }
2877  Assert(activeTapes > 0);
2878  state->activeTapes = activeTapes;
2879 
2880  /* Load the merge heap with the first tuple from each input tape */
2881  for (srcTape = 0; srcTape < state->maxTapes; srcTape++)
2882  {
2883  SortTuple tup;
2884 
2885  if (mergereadnext(state, srcTape, &tup))
2886  {
2887  tup.srctape = srcTape;
2888  tuplesort_heap_insert(state, &tup);
2889  }
2890  }
2891 }
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3336
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2899
#define Assert(condition)
Definition: c.h:732
int srctape
Definition: tuplesort.c:172
int * tp_dummy
Definition: tuplesort.c:369
int * tp_tapenum
Definition: tuplesort.c:370
bool * mergeactive
Definition: tuplesort.c:358

◆ comparetup_cluster()

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

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

3709 {
3710  SortSupport sortKey = state->sortKeys;
3711  HeapTuple ltup;
3712  HeapTuple rtup;
3713  TupleDesc tupDesc;
3714  int nkey;
3715  int32 compare;
3716  Datum datum1,
3717  datum2;
3718  bool isnull1,
3719  isnull2;
3720  AttrNumber leading = state->indexInfo->ii_IndexAttrNumbers[0];
3721 
3722  /* Be prepared to compare additional sort keys */
3723  ltup = (HeapTuple) a->tuple;
3724  rtup = (HeapTuple) b->tuple;
3725  tupDesc = state->tupDesc;
3726 
3727  /* Compare the leading sort key, if it's simple */
3728  if (leading != 0)
3729  {
3730  compare = ApplySortComparator(a->datum1, a->isnull1,
3731  b->datum1, b->isnull1,
3732  sortKey);
3733  if (compare != 0)
3734  return compare;
3735 
3736  if (sortKey->abbrev_converter)
3737  {
3738  datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
3739  datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
3740 
3741  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3742  datum2, isnull2,
3743  sortKey);
3744  }
3745  if (compare != 0 || state->nKeys == 1)
3746  return compare;
3747  /* Compare additional columns the hard way */
3748  sortKey++;
3749  nkey = 1;
3750  }
3751  else
3752  {
3753  /* Must compare all keys the hard way */
3754  nkey = 0;
3755  }
3756 
3757  if (state->indexInfo->ii_Expressions == NULL)
3758  {
3759  /* If not expression index, just compare the proper heap attrs */
3760 
3761  for (; nkey < state->nKeys; nkey++, sortKey++)
3762  {
3763  AttrNumber attno = state->indexInfo->ii_IndexAttrNumbers[nkey];
3764 
3765  datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
3766  datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
3767 
3768  compare = ApplySortComparator(datum1, isnull1,
3769  datum2, isnull2,
3770  sortKey);
3771  if (compare != 0)
3772  return compare;
3773  }
3774  }
3775  else
3776  {
3777  /*
3778  * In the expression index case, compute the whole index tuple and
3779  * then compare values. It would perhaps be faster to compute only as
3780  * many columns as we need to compare, but that would require
3781  * duplicating all the logic in FormIndexDatum.
3782  */
3783  Datum l_index_values[INDEX_MAX_KEYS];
3784  bool l_index_isnull[INDEX_MAX_KEYS];
3785  Datum r_index_values[INDEX_MAX_KEYS];
3786  bool r_index_isnull[INDEX_MAX_KEYS];
3787  TupleTableSlot *ecxt_scantuple;
3788 
3789  /* Reset context each time to prevent memory leakage */
3791 
3792  ecxt_scantuple = GetPerTupleExprContext(state->estate)->ecxt_scantuple;
3793 
3794  ExecStoreHeapTuple(ltup, ecxt_scantuple, false);
3795  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3796  l_index_values, l_index_isnull);
3797 
3798  ExecStoreHeapTuple(rtup, ecxt_scantuple, false);
3799  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3800  r_index_values, r_index_isnull);
3801 
3802  for (; nkey < state->nKeys; nkey++, sortKey++)
3803  {
3804  compare = ApplySortComparator(l_index_values[nkey],
3805  l_index_isnull[nkey],
3806  r_index_values[nkey],
3807  r_index_isnull[nkey],
3808  sortKey);
3809  if (compare != 0)
3810  return compare;
3811  }
3812  }
3813 
3814  return 0;
3815 }
void FormIndexDatum(IndexInfo *indexInfo, TupleTableSlot *slot, EState *estate, Datum *values, bool *isnull)
Definition: index.c:2462
HeapTupleData * HeapTuple
Definition: htup.h:71
#define ResetPerTupleExprContext(estate)
Definition: executor.h:510
EState * estate
Definition: tuplesort.c:434
SortSupport sortKeys
Definition: tuplesort.c:412
Datum datum1
Definition: tuplesort.c:170
bool isnull1
Definition: tuplesort.c:171
signed int int32
Definition: c.h:346
#define GetPerTupleExprContext(estate)
Definition: executor.h:501
void * tuple
Definition: tuplesort.c:169
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
IndexInfo * indexInfo
Definition: tuplesort.c:433
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:160
#define INDEX_MAX_KEYS
AttrNumber ii_IndexAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:159
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:1317
TupleDesc tupDesc
Definition: tuplesort.c:411
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 4253 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().

4254 {
4255  int compare;
4256 
4257  compare = ApplySortComparator(a->datum1, a->isnull1,
4258  b->datum1, b->isnull1,
4259  state->sortKeys);
4260  if (compare != 0)
4261  return compare;
4262 
4263  /* if we have abbreviations, then "tuple" has the original value */
4264 
4265  if (state->sortKeys->abbrev_converter)
4267  PointerGetDatum(b->tuple), b->isnull1,
4268  state->sortKeys);
4269 
4270  return compare;
4271 }
#define PointerGetDatum(X)
Definition: postgres.h:556
SortSupport sortKeys
Definition: tuplesort.c:412
Datum datum1
Definition: tuplesort.c:170
bool isnull1
Definition: tuplesort.c:171
void * tuple
Definition: tuplesort.c:169
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 3508 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().

3509 {
3510  SortSupport sortKey = state->sortKeys;
3511  HeapTupleData ltup;
3512  HeapTupleData rtup;
3513  TupleDesc tupDesc;
3514  int nkey;
3515  int32 compare;
3516  AttrNumber attno;
3517  Datum datum1,
3518  datum2;
3519  bool isnull1,
3520  isnull2;
3521 
3522 
3523  /* Compare the leading sort key */
3524  compare = ApplySortComparator(a->datum1, a->isnull1,
3525  b->datum1, b->isnull1,
3526  sortKey);
3527  if (compare != 0)
3528  return compare;
3529 
3530  /* Compare additional sort keys */
3531  ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3532  ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
3533  rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3534  rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
3535  tupDesc = state->tupDesc;
3536 
3537  if (sortKey->abbrev_converter)
3538  {
3539  attno = sortKey->ssup_attno;
3540 
3541  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3542  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3543 
3544  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3545  datum2, isnull2,
3546  sortKey);
3547  if (compare != 0)
3548  return compare;
3549  }
3550 
3551  sortKey++;
3552  for (nkey = 1; nkey < state->nKeys; nkey++, sortKey++)
3553  {
3554  attno = sortKey->ssup_attno;
3555 
3556  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3557  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3558 
3559  compare = ApplySortComparator(datum1, isnull1,
3560  datum2, isnull2,
3561  sortKey);
3562  if (compare != 0)
3563  return compare;
3564  }
3565 
3566  return 0;
3567 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:412
Datum datum1
Definition: tuplesort.c:170
bool isnull1
Definition: tuplesort.c:171
signed int int32
Definition: c.h:346
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:169
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:411
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 3953 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().

3955 {
3956  /*
3957  * This is similar to comparetup_heap(), but expects index tuples. There
3958  * is also special handling for enforcing uniqueness, and special
3959  * treatment for equal keys at the end.
3960  */
3961  SortSupport sortKey = state->sortKeys;
3962  IndexTuple tuple1;
3963  IndexTuple tuple2;
3964  int keysz;
3965  TupleDesc tupDes;
3966  bool equal_hasnull = false;
3967  int nkey;
3968  int32 compare;
3969  Datum datum1,
3970  datum2;
3971  bool isnull1,
3972  isnull2;
3973 
3974 
3975  /* Compare the leading sort key */
3976  compare = ApplySortComparator(a->datum1, a->isnull1,
3977  b->datum1, b->isnull1,
3978  sortKey);
3979  if (compare != 0)
3980  return compare;
3981 
3982  /* Compare additional sort keys */
3983  tuple1 = (IndexTuple) a->tuple;
3984  tuple2 = (IndexTuple) b->tuple;
3985  keysz = state->nKeys;
3986  tupDes = RelationGetDescr(state->indexRel);
3987 
3988  if (sortKey->abbrev_converter)
3989  {
3990  datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
3991  datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
3992 
3993  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3994  datum2, isnull2,
3995  sortKey);
3996  if (compare != 0)
3997  return compare;
3998  }
3999 
4000  /* they are equal, so we only need to examine one null flag */
4001  if (a->isnull1)
4002  equal_hasnull = true;
4003 
4004  sortKey++;
4005  for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
4006  {
4007  datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
4008  datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
4009 
4010  compare = ApplySortComparator(datum1, isnull1,
4011  datum2, isnull2,
4012  sortKey);
4013  if (compare != 0)
4014  return compare; /* done when we find unequal attributes */
4015 
4016  /* they are equal, so we only need to examine one null flag */
4017  if (isnull1)
4018  equal_hasnull = true;
4019  }
4020 
4021  /*
4022  * If btree has asked us to enforce uniqueness, complain if two equal
4023  * tuples are detected (unless there was at least one NULL field).
4024  *
4025  * It is sufficient to make the test here, because if two tuples are equal
4026  * they *must* get compared at some stage of the sort --- otherwise the
4027  * sort algorithm wouldn't have checked whether one must appear before the
4028  * other.
4029  */
4030  if (state->enforceUnique && !equal_hasnull)
4031  {
4033  bool isnull[INDEX_MAX_KEYS];
4034  char *key_desc;
4035 
4036  /*
4037  * Some rather brain-dead implementations of qsort (such as the one in
4038  * QNX 4) will sometimes call the comparison routine to compare a
4039  * value to itself, but we always use our own implementation, which
4040  * does not.
4041  */
4042  Assert(tuple1 != tuple2);
4043 
4044  index_deform_tuple(tuple1, tupDes, values, isnull);
4045 
4046  key_desc = BuildIndexValueDescription(state->indexRel, values, isnull);
4047 
4048  ereport(ERROR,
4049  (errcode(ERRCODE_UNIQUE_VIOLATION),
4050  errmsg("could not create unique index \"%s\"",
4052  key_desc ? errdetail("Key %s is duplicated.", key_desc) :
4053  errdetail("Duplicate keys exist."),
4054  errtableconstraint(state->heapRel,
4055  RelationGetRelationName(state->indexRel))));
4056  }
4057 
4058  /*
4059  * If key values are equal, we sort on ItemPointer. This is required for
4060  * btree indexes, since heap TID is treated as an implicit last key
4061  * attribute in order to ensure that all keys in the index are physically
4062  * unique.
4063  */
4064  {
4065  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4066  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4067 
4068  if (blk1 != blk2)
4069  return (blk1 < blk2) ? -1 : 1;
4070  }
4071  {
4074 
4075  if (pos1 != pos2)
4076  return (pos1 < pos2) ? -1 : 1;
4077  }
4078 
4079  /* ItemPointer values should never be equal */
4080  Assert(false);
4081 
4082  return 0;
4083 }
Relation heapRel
Definition: tuplesort.c:440
#define RelationGetDescr(relation)
Definition: rel.h:442
SortSupport sortKeys
Definition: tuplesort.c:412
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:170
int errcode(int sqlerrcode)
Definition: elog.c:570
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:171
signed int int32
Definition: c.h:346
uint16 OffsetNumber
Definition: off.h:24
void * tuple
Definition: tuplesort.c:169
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5222
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:860
#define RelationGetRelationName(relation)
Definition: rel.h:450
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:426
#define ereport(elevel, rest)
Definition: elog.h:141
Relation indexRel
Definition: tuplesort.c:441
uintptr_t Datum
Definition: postgres.h:367
#define Assert(condition)
Definition: c.h:732
bool enforceUnique
Definition: tuplesort.c:444
#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:784
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 4086 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().

4088 {
4089  Bucket bucket1;
4090  Bucket bucket2;
4091  IndexTuple tuple1;
4092  IndexTuple tuple2;
4093 
4094  /*
4095  * Fetch hash keys and mask off bits we don't want to sort by. We know
4096  * that the first column of the index tuple is the hash key.
4097  */
4098  Assert(!a->isnull1);
4100  state->max_buckets, state->high_mask,
4101  state->low_mask);
4102  Assert(!b->isnull1);
4104  state->max_buckets, state->high_mask,
4105  state->low_mask);
4106  if (bucket1 > bucket2)
4107  return 1;
4108  else if (bucket1 < bucket2)
4109  return -1;
4110 
4111  /*
4112  * If hash values are equal, we sort on ItemPointer. This does not affect
4113  * validity of the finished index, but it may be useful to have index
4114  * scans in physical order.
4115  */
4116  tuple1 = (IndexTuple) a->tuple;
4117  tuple2 = (IndexTuple) b->tuple;
4118 
4119  {
4120  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4121  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4122 
4123  if (blk1 != blk2)
4124  return (blk1 < blk2) ? -1 : 1;
4125  }
4126  {
4129 
4130  if (pos1 != pos2)
4131  return (pos1 < pos2) ? -1 : 1;
4132  }
4133 
4134  /* ItemPointer values should never be equal */
4135  Assert(false);
4136 
4137  return 0;
4138 }
#define DatumGetUInt32(X)
Definition: postgres.h:486
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:125
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:170
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:171
uint16 OffsetNumber
Definition: off.h:24
uint32 Bucket
Definition: hash.h:34
void * tuple
Definition: tuplesort.c:169
uint32 high_mask
Definition: tuplesort.c:447
IndexTupleData * IndexTuple
Definition: itup.h:53
#define Assert(condition)
Definition: c.h:732
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
uint32 max_buckets
Definition: tuplesort.c:449
uint32 low_mask
Definition: tuplesort.c:448
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98

◆ consider_abort_common()

static bool consider_abort_common ( Tuplesortstate state)
static

Definition at line 1746 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(), copytup_index(), tuplesort_putdatum(), and tuplesort_putindextuplevalues().

1747 {
1748  Assert(state->sortKeys[0].abbrev_converter != NULL);
1749  Assert(state->sortKeys[0].abbrev_abort != NULL);
1750  Assert(state->sortKeys[0].abbrev_full_comparator != NULL);
1751 
1752  /*
1753  * Check effectiveness of abbreviation optimization. Consider aborting
1754  * when still within memory limit.
1755  */
1756  if (state->status == TSS_INITIAL &&
1757  state->memtupcount >= state->abbrevNext)
1758  {
1759  state->abbrevNext *= 2;
1760 
1761  /*
1762  * Check opclass-supplied abbreviation abort routine. It may indicate
1763  * that abbreviation should not proceed.
1764  */
1765  if (!state->sortKeys->abbrev_abort(state->memtupcount,
1766  state->sortKeys))
1767  return false;
1768 
1769  /*
1770  * Finally, restore authoritative comparator, and indicate that
1771  * abbreviation is not in play by setting abbrev_converter to NULL
1772  */
1773  state->sortKeys[0].comparator = state->sortKeys[0].abbrev_full_comparator;
1774  state->sortKeys[0].abbrev_converter = NULL;
1775  /* Not strictly necessary, but be tidy */
1776  state->sortKeys[0].abbrev_abort = NULL;
1777  state->sortKeys[0].abbrev_full_comparator = NULL;
1778 
1779  /* Give up - expect original pass-by-value representation */
1780  return true;
1781  }
1782 
1783  return false;
1784 }
TupSortStatus status
Definition: tuplesort.c:232
int64 abbrevNext
Definition: tuplesort.c:426
SortSupport sortKeys
Definition: tuplesort.c:412
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define Assert(condition)
Definition: c.h:732
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 3818 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().

3819 {
3820  HeapTuple tuple = (HeapTuple) tup;
3821  Datum original;
3822  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3823 
3824  /* copy the tuple into sort storage */
3825  tuple = heap_copytuple(tuple);
3826  stup->tuple = (void *) tuple;
3827  USEMEM(state, GetMemoryChunkSpace(tuple));
3828 
3829  MemoryContextSwitchTo(oldcontext);
3830 
3831  /*
3832  * set up first-column key value, and potentially abbreviate, if it's a
3833  * simple column
3834  */
3835  if (state->indexInfo->ii_IndexAttrNumbers[0] == 0)
3836  return;
3837 
3838  original = heap_getattr(tuple,
3839  state->indexInfo->ii_IndexAttrNumbers[0],
3840  state->tupDesc,
3841  &stup->isnull1);
3842 
3843  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3844  {
3845  /*
3846  * Store ordinary Datum representation, or NULL value. If there is a
3847  * converter it won't expect NULL values, and cost model is not
3848  * required to account for NULL, so in that case we avoid calling
3849  * converter and just set datum1 to zeroed representation (to be
3850  * consistent, and to support cheap inequality tests for NULL
3851  * abbreviated keys).
3852  */
3853  stup->datum1 = original;
3854  }
3855  else if (!consider_abort_common(state))
3856  {
3857  /* Store abbreviated key representation */
3858  stup->datum1 = state->sortKeys->abbrev_converter(original,
3859  state->sortKeys);
3860  }
3861  else
3862  {
3863  /* Abort abbreviation */
3864  int i;
3865 
3866  stup->datum1 = original;
3867 
3868  /*
3869  * Set state to be consistent with never trying abbreviation.
3870  *
3871  * Alter datum1 representation in already-copied tuples, so as to
3872  * ensure a consistent representation (current tuple was just
3873  * handled). It does not matter if some dumped tuples are already
3874  * sorted on tape, since serialized tuples lack abbreviated keys
3875  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3876  */
3877  for (i = 0; i < state->memtupcount; i++)
3878  {
3879  SortTuple *mtup = &state->memtuples[i];
3880 
3881  tuple = (HeapTuple) mtup->tuple;
3882  mtup->datum1 = heap_getattr(tuple,
3883  state->indexInfo->ii_IndexAttrNumbers[0],
3884  state->tupDesc,
3885  &mtup->isnull1);
3886  }
3887  }
3888 }
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:680
HeapTupleData * HeapTuple
Definition: htup.h:71
SortSupport sortKeys
Definition: tuplesort.c:412
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:170
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:171
void * tuple
Definition: tuplesort.c:169
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1746
IndexInfo * indexInfo
Definition: tuplesort.c:433
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:245
#define USEMEM(state, amt)
Definition: tuplesort.c:528
int i
AttrNumber ii_IndexAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:159
TupleDesc tupDesc
Definition: tuplesort.c:411
SortTuple * memtuples
Definition: tuplesort.c:293

◆ copytup_datum()

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

Definition at line 4274 of file tuplesort.c.

References elog, and ERROR.

Referenced by tuplesort_begin_datum().

4275 {
4276  /* Not currently needed */
4277  elog(ERROR, "copytup_datum() should not be called");
4278 }
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:226

◆ copytup_heap()

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

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

3571 {
3572  /*
3573  * We expect the passed "tup" to be a TupleTableSlot, and form a
3574  * MinimalTuple using the exported interface for that.
3575  */
3576  TupleTableSlot *slot = (TupleTableSlot *) tup;
3577  Datum original;
3578  MinimalTuple tuple;
3579  HeapTupleData htup;
3580  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3581 
3582  /* copy the tuple into sort storage */
3583  tuple = ExecCopySlotMinimalTuple(slot);
3584  stup->tuple = (void *) tuple;
3585  USEMEM(state, GetMemoryChunkSpace(tuple));
3586  /* set up first-column key value */
3587  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3588  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3589  original = heap_getattr(&htup,
3590  state->sortKeys[0].ssup_attno,
3591  state->tupDesc,
3592  &stup->isnull1);
3593 
3594  MemoryContextSwitchTo(oldcontext);
3595 
3596  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3597  {
3598  /*
3599  * Store ordinary Datum representation, or NULL value. If there is a
3600  * converter it won't expect NULL values, and cost model is not
3601  * required to account for NULL, so in that case we avoid calling
3602  * converter and just set datum1 to zeroed representation (to be
3603  * consistent, and to support cheap inequality tests for NULL
3604  * abbreviated keys).
3605  */
3606  stup->datum1 = original;
3607  }
3608  else if (!consider_abort_common(state))
3609  {
3610  /* Store abbreviated key representation */
3611  stup->datum1 = state->sortKeys->abbrev_converter(original,
3612  state->sortKeys);
3613  }
3614  else
3615  {
3616  /* Abort abbreviation */
3617  int i;
3618 
3619  stup->datum1 = original;
3620 
3621  /*
3622  * Set state to be consistent with never trying abbreviation.
3623  *
3624  * Alter datum1 representation in already-copied tuples, so as to
3625  * ensure a consistent representation (current tuple was just
3626  * handled). It does not matter if some dumped tuples are already
3627  * sorted on tape, since serialized tuples lack abbreviated keys
3628  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3629  */
3630  for (i = 0; i < state->memtupcount; i++)
3631  {
3632  SortTuple *mtup = &state->memtuples[i];
3633 
3634  htup.t_len = ((MinimalTuple) mtup->tuple)->t_len +
3636  htup.t_data = (HeapTupleHeader) ((char *) mtup->tuple -
3638 
3639  mtup->datum1 = heap_getattr(&htup,
3640  state->sortKeys[0].ssup_attno,
3641  state->tupDesc,
3642  &mtup->isnull1);
3643  }
3644  }
3645 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:412
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:170
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:171
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:169
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1746
uint32 t_len
Definition: htup.h:64
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:464
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:245
#define USEMEM(state, amt)
Definition: tuplesort.c:528
int i
TupleDesc tupDesc
Definition: tuplesort.c:411
SortTuple * memtuples
Definition: tuplesort.c:293

◆ copytup_index()

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

Definition at line 4141 of file tuplesort.c.

References SortSupportData::abbrev_converter, consider_abort_common(), SortTuple::datum1, GetMemoryChunkSpace(), i, index_getattr, Tuplesortstate::indexRel, IndexTupleSize, SortTuple::isnull1, MemoryContextAlloc(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, RelationGetDescr, Tuplesortstate::sortKeys, SortTuple::tuple, Tuplesortstate::tuplecontext, and USEMEM.

Referenced by tuplesort_begin_index_btree(), and tuplesort_begin_index_hash().

4142 {
4143  IndexTuple tuple = (IndexTuple) tup;
4144  unsigned int tuplen = IndexTupleSize(tuple);
4145  IndexTuple newtuple;
4146  Datum original;
4147 
4148  /* copy the tuple into sort storage */
4149  newtuple = (IndexTuple) MemoryContextAlloc(state->tuplecontext, tuplen);
4150  memcpy(newtuple, tuple, tuplen);
4151  USEMEM(state, GetMemoryChunkSpace(newtuple));
4152  stup->tuple = (void *) newtuple;
4153  /* set up first-column key value */
4154  original = index_getattr(newtuple,
4155  1,
4156  RelationGetDescr(state->indexRel),
4157  &stup->isnull1);
4158 
4159  if (!state->sortKeys->abbrev_converter || stup->isnull1)
4160  {
4161  /*
4162  * Store ordinary Datum representation, or NULL value. If there is a
4163  * converter it won't expect NULL values, and cost model is not
4164  * required to account for NULL, so in that case we avoid calling
4165  * converter and just set datum1 to zeroed representation (to be
4166  * consistent, and to support cheap inequality tests for NULL
4167  * abbreviated keys).
4168  */
4169  stup->datum1 = original;
4170  }
4171  else if (!consider_abort_common(state))
4172  {
4173  /* Store abbreviated key representation */
4174  stup->datum1 = state->sortKeys->abbrev_converter(original,
4175  state->sortKeys);
4176  }
4177  else
4178  {
4179  /* Abort abbreviation */
4180  int i;
4181 
4182  stup->datum1 = original;
4183 
4184  /*
4185  * Set state to be consistent with never trying abbreviation.
4186  *
4187  * Alter datum1 representation in already-copied tuples, so as to
4188  * ensure a consistent representation (current tuple was just
4189  * handled). It does not matter if some dumped tuples are already
4190  * sorted on tape, since serialized tuples lack abbreviated keys
4191  * (TSS_BUILDRUNS state prevents control reaching here in any case).
4192  */
4193  for (i = 0; i < state->memtupcount; i++)
4194  {
4195  SortTuple *mtup = &state->memtuples[i];
4196 
4197  tuple = (IndexTuple) mtup->tuple;
4198  mtup->datum1 = index_getattr(tuple,
4199  1,
4200  RelationGetDescr(state->indexRel),
4201  &mtup->isnull1);
4202  }
4203  }
4204 }
#define RelationGetDescr(relation)
Definition: rel.h:442
SortSupport sortKeys
Definition: tuplesort.c:412
Datum datum1
Definition: tuplesort.c:170
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
bool isnull1
Definition: tuplesort.c:171
void * tuple
Definition: tuplesort.c:169
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1746
IndexTupleData * IndexTuple
Definition: itup.h:53
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
Relation indexRel
Definition: tuplesort.c:441
uintptr_t Datum
Definition: postgres.h:367
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
MemoryContext tuplecontext
Definition: tuplesort.c:245
#define USEMEM(state, amt)
Definition: tuplesort.c:528
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:771
int i
#define IndexTupleSize(itup)
Definition: itup.h:71
SortTuple * memtuples
Definition: tuplesort.c:293

◆ dumptuples()

static void dumptuples ( Tuplesortstate state,
bool  alltuples 
)
static

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

2925 {
2926  int memtupwrite;
2927  int i;
2928 
2929  /*
2930  * Nothing to do if we still fit in available memory and have array slots,
2931  * unless this is the final call during initial run generation.
2932  */
2933  if (state->memtupcount < state->memtupsize && !LACKMEM(state) &&
2934  !alltuples)
2935  return;
2936 
2937  /*
2938  * Final call might require no sorting, in rare cases where we just so
2939  * happen to have previously LACKMEM()'d at the point where exactly all
2940  * remaining tuples are loaded into memory, just before input was
2941  * exhausted.
2942  *
2943  * In general, short final runs are quite possible. Rather than allowing
2944  * a special case where there was a superfluous selectnewtape() call (i.e.
2945  * a call with no subsequent run actually written to destTape), we prefer
2946  * to write out a 0 tuple run.
2947  *
2948  * mergereadnext() is prepared for 0 tuple runs, and will reliably mark
2949  * the tape inactive for the merge when called from beginmerge(). This
2950  * case is therefore similar to the case where mergeonerun() finds a dummy
2951  * run for the tape, and so doesn't need to merge a run from the tape (or
2952  * conceptually "merges" the dummy run, if you prefer). According to
2953  * Knuth, Algorithm D "isn't strictly optimal" in its method of
2954  * distribution and dummy run assignment; this edge case seems very
2955  * unlikely to make that appreciably worse.
2956  */
2957  Assert(state->status == TSS_BUILDRUNS);
2958 
2959  /*
2960  * It seems unlikely that this limit will ever be exceeded, but take no
2961  * chances
2962  */
2963  if (state->currentRun == INT_MAX)
2964  ereport(ERROR,
2965  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2966  errmsg("cannot have more than %d runs for an external sort",
2967  INT_MAX)));
2968 
2969  state->currentRun++;
2970 
2971 #ifdef TRACE_SORT
2972  if (trace_sort)
2973  elog(LOG, "worker %d starting quicksort of run %d: %s",
2974  state->worker, state->currentRun,
2975  pg_rusage_show(&state->ru_start));
2976 #endif
2977 
2978  /*
2979  * Sort all tuples accumulated within the allowed amount of memory for
2980  * this run using quicksort
2981  */
2982  tuplesort_sort_memtuples(state);
2983 
2984 #ifdef TRACE_SORT
2985  if (trace_sort)
2986  elog(LOG, "worker %d finished quicksort of run %d: %s",
2987  state->worker, state->currentRun,
2988  pg_rusage_show(&state->ru_start));
2989 #endif
2990 
2991  memtupwrite = state->memtupcount;
2992  for (i = 0; i < memtupwrite; i++)
2993  {
2994  WRITETUP(state, state->tp_tapenum[state->destTape],
2995  &state->memtuples[i]);
2996  state->memtupcount--;
2997  }
2998 
2999  /*
3000  * Reset tuple memory. We've freed all of the tuples that we previously
3001  * allocated. It's important to avoid fragmentation when there is a stark
3002  * change in the sizes of incoming tuples. Fragmentation due to
3003  * AllocSetFree's bucketing by size class might be particularly bad if
3004  * this step wasn't taken.
3005  */
3007 
3008  markrunend(state, state->tp_tapenum[state->destTape]);
3009  state->tp_runs[state->destTape]++;
3010  state->tp_dummy[state->destTape]--; /* per Alg D step D2 */
3011 
3012 #ifdef TRACE_SORT
3013  if (trace_sort)
3014  elog(LOG, "worker %d finished writing run %d to tape %d: %s",
3015  state->worker, state->currentRun, state->destTape,
3016  pg_rusage_show(&state->ru_start));
3017 #endif
3018 
3019  if (!alltuples)
3020  selectnewtape(state);
3021 }
TupSortStatus status
Definition: tuplesort.c:232
PGRUsage ru_start
Definition: tuplesort.c:463
int errcode(int sqlerrcode)
Definition: elog.c:570
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3466
#define ERROR
Definition: elog.h:43
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define ereport(elevel, rest)
Definition: elog.h:141
static void selectnewtape(Tuplesortstate *state)
Definition: tuplesort.c:2493
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:525
#define Assert(condition)
Definition: c.h:732
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3308
int * tp_dummy
Definition: tuplesort.c:369
MemoryContext tuplecontext
Definition: tuplesort.c:245
int errmsg(const char *fmt,...)
Definition: elog.c:784
int * tp_tapenum
Definition: tuplesort.c:370
#define elog(elevel,...)
Definition: elog.h:226
int i
#define LACKMEM(state)
Definition: tuplesort.c:527
SortTuple * memtuples
Definition: tuplesort.c:293

◆ free_sort_tuple()

static void free_sort_tuple ( Tuplesortstate state,
SortTuple stup 
)
static

Definition at line 4585 of file tuplesort.c.

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

Referenced by make_bounded_heap(), and puttuple_common().

4586 {
4587  FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
4588  pfree(stup->tuple);
4589 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
void * tuple
Definition: tuplesort.c:169
void pfree(void *pointer)
Definition: mcxt.c:1031
#define FREEMEM(state, amt)
Definition: tuplesort.c:529

◆ getlen()

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

Definition at line 3453 of file tuplesort.c.

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

Referenced by mergereadnext(), and tuplesort_gettuple_common().

3454 {
3455  unsigned int len;
3456 
3457  if (LogicalTapeRead(state->tapeset, tapenum,
3458  &len, sizeof(len)) != sizeof(len))
3459  elog(ERROR, "unexpected end of tape");
3460  if (len == 0 && !eofOK)
3461  elog(ERROR, "unexpected end of data");
3462  return len;
3463 }
size_t LogicalTapeRead(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:822
#define ERROR
Definition: elog.h:43
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
#define elog(elevel,...)
Definition: elog.h:226

◆ grow_memtuples()

static bool grow_memtuples ( Tuplesortstate state)
static

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

1316 {
1317  int newmemtupsize;
1318  int memtupsize = state->memtupsize;
1319  int64 memNowUsed = state->allowedMem - state->availMem;
1320 
1321  /* Forget it if we've already maxed out memtuples, per comment above */
1322  if (!state->growmemtuples)
1323  return false;
1324 
1325  /* Select new value of memtupsize */
1326  if (memNowUsed <= state->availMem)
1327  {
1328  /*
1329  * We've used no more than half of allowedMem; double our usage,
1330  * clamping at INT_MAX tuples.
1331  */
1332  if (memtupsize < INT_MAX / 2)
1333  newmemtupsize = memtupsize * 2;
1334  else
1335  {
1336  newmemtupsize = INT_MAX;
1337  state->growmemtuples = false;
1338  }
1339  }
1340  else
1341  {
1342  /*
1343  * This will be the last increment of memtupsize. Abandon doubling
1344  * strategy and instead increase as much as we safely can.
1345  *
1346  * To stay within allowedMem, we can't increase memtupsize by more
1347  * than availMem / sizeof(SortTuple) elements. In practice, we want
1348  * to increase it by considerably less, because we need to leave some
1349  * space for the tuples to which the new array slots will refer. We
1350  * assume the new tuples will be about the same size as the tuples
1351  * we've already seen, and thus we can extrapolate from the space
1352  * consumption so far to estimate an appropriate new size for the
1353  * memtuples array. The optimal value might be higher or lower than
1354  * this estimate, but it's hard to know that in advance. We again
1355  * clamp at INT_MAX tuples.
1356  *
1357  * This calculation is safe against enlarging the array so much that
1358  * LACKMEM becomes true, because the memory currently used includes
1359  * the present array; thus, there would be enough allowedMem for the
1360  * new array elements even if no other memory were currently used.
1361  *
1362  * We do the arithmetic in float8, because otherwise the product of
1363  * memtupsize and allowedMem could overflow. Any inaccuracy in the
1364  * result should be insignificant; but even if we computed a
1365  * completely insane result, the checks below will prevent anything
1366  * really bad from happening.
1367  */
1368  double grow_ratio;
1369 
1370  grow_ratio = (double) state->allowedMem / (double) memNowUsed;
1371  if (memtupsize * grow_ratio < INT_MAX)
1372  newmemtupsize = (int) (memtupsize * grow_ratio);
1373  else
1374  newmemtupsize = INT_MAX;
1375 
1376  /* We won't make any further enlargement attempts */
1377  state->growmemtuples = false;
1378  }
1379 
1380  /* Must enlarge array by at least one element, else report failure */
1381  if (newmemtupsize <= memtupsize)
1382  goto noalloc;
1383 
1384  /*
1385  * On a 32-bit machine, allowedMem could exceed MaxAllocHugeSize. Clamp
1386  * to ensure our request won't be rejected. Note that we can easily
1387  * exhaust address space before facing this outcome. (This is presently
1388  * impossible due to guc.c's MAX_KILOBYTES limitation on work_mem, but
1389  * don't rely on that at this distance.)
1390  */
1391  if ((Size) newmemtupsize >= MaxAllocHugeSize / sizeof(SortTuple))
1392  {
1393  newmemtupsize = (int) (MaxAllocHugeSize / sizeof(SortTuple));
1394  state->growmemtuples = false; /* can't grow any more */
1395  }
1396 
1397  /*
1398  * We need to be sure that we do not cause LACKMEM to become true, else
1399  * the space management algorithm will go nuts. The code above should
1400  * never generate a dangerous request, but to be safe, check explicitly
1401  * that the array growth fits within availMem. (We could still cause
1402  * LACKMEM if the memory chunk overhead associated with the memtuples
1403  * array were to increase. That shouldn't happen because we chose the
1404  * initial array size large enough to ensure that palloc will be treating
1405  * both old and new arrays as separate chunks. But we'll check LACKMEM
1406  * explicitly below just in case.)
1407  */
1408  if (state->availMem < (int64) ((newmemtupsize - memtupsize) * sizeof(SortTuple)))
1409  goto noalloc;
1410 
1411  /* OK, do it */
1412  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
1413  state->memtupsize = newmemtupsize;
1414  state->memtuples = (SortTuple *)
1415  repalloc_huge(state->memtuples,
1416  state->memtupsize * sizeof(SortTuple));
1417  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
1418  if (LACKMEM(state))
1419  elog(ERROR, "unexpected out-of-memory situation in tuplesort");
1420  return true;
1421 
1422 noalloc:
1423  /* If for any reason we didn't realloc, shut off future attempts */
1424  state->growmemtuples = false;
1425  return false;
1426 }
int64 availMem
Definition: tuplesort.c:240
bool growmemtuples
Definition: tuplesort.c:296
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:529
int64 allowedMem
Definition: tuplesort.c:241
size_t Size
Definition: c.h:466
void * repalloc_huge(void *pointer, Size size)
Definition: mcxt.c:1114
#define USEMEM(state, amt)
Definition: tuplesort.c:528
#define elog(elevel,...)
Definition: elog.h:226
#define LACKMEM(state)
Definition: tuplesort.c:527
SortTuple * memtuples
Definition: tuplesort.c:293

◆ init_slab_allocator()

static void init_slab_allocator ( Tuplesortstate state,
int  numSlots 
)
static

Definition at line 2525 of file tuplesort.c.

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

Referenced by mergeruns().

2526 {
2527  if (numSlots > 0)
2528  {
2529  char *p;
2530  int i;
2531 
2532  state->slabMemoryBegin = palloc(numSlots * SLAB_SLOT_SIZE);
2533  state->slabMemoryEnd = state->slabMemoryBegin +
2534  numSlots * SLAB_SLOT_SIZE;
2535  state->slabFreeHead = (SlabSlot *) state->slabMemoryBegin;
2536  USEMEM(state, numSlots * SLAB_SLOT_SIZE);
2537 
2538  p = state->slabMemoryBegin;
2539  for (i = 0; i < numSlots - 1; i++)
2540  {
2541  ((SlabSlot *) p)->nextfree = (SlabSlot *) (p + SLAB_SLOT_SIZE);
2542  p += SLAB_SLOT_SIZE;
2543  }
2544  ((SlabSlot *) p)->nextfree = NULL;
2545  }
2546  else
2547  {
2548  state->slabMemoryBegin = state->slabMemoryEnd = NULL;
2549  state->slabFreeHead = NULL;
2550  }
2551  state->slabAllocatorUsed = true;
2552 }
char * slabMemoryEnd
Definition: tuplesort.c:328
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:186
char * slabMemoryBegin
Definition: tuplesort.c:327
bool slabAllocatorUsed
Definition: tuplesort.c:325
void * palloc(Size size)
Definition: mcxt.c:924
#define USEMEM(state, amt)
Definition: tuplesort.c:528
int i
SlabSlot * slabFreeHead
Definition: tuplesort.c:329

◆ inittapes()

static void inittapes ( Tuplesortstate state,
bool  mergeruns 
)
static

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

2393 {
2394  int maxTapes,
2395  j;
2396 
2397  Assert(!LEADER(state));
2398 
2399  if (mergeruns)
2400  {
2401  /* Compute number of tapes to use: merge order plus 1 */
2402  maxTapes = tuplesort_merge_order(state->allowedMem) + 1;
2403  }
2404  else
2405  {
2406  /* Workers can sometimes produce single run, output without merge */
2407  Assert(WORKER(state));
2408  maxTapes = MINORDER + 1;
2409  }
2410 
2411 #ifdef TRACE_SORT
2412  if (trace_sort)
2413  elog(LOG, "worker %d switching to external sort with %d tapes: %s",
2414  state->worker, maxTapes, pg_rusage_show(&state->ru_start));
2415 #endif
2416 
2417  /* Create the tape set and allocate the per-tape data arrays */
2418  inittapestate(state, maxTapes);
2419  state->tapeset =
2420  LogicalTapeSetCreate(maxTapes, NULL,
2421  state->shared ? &state->shared->fileset : NULL,
2422  state->worker);
2423 
2424  state->currentRun = 0;
2425 
2426  /*
2427  * Initialize variables of Algorithm D (step D1).
2428  */
2429  for (j = 0; j < maxTapes; j++)
2430  {
2431  state->tp_fib[j] = 1;
2432  state->tp_runs[j] = 0;
2433  state->tp_dummy[j] = 1;
2434  state->tp_tapenum[j] = j;
2435  }
2436  state->tp_fib[state->tapeRange] = 0;
2437  state->tp_dummy[state->tapeRange] = 0;
2438 
2439  state->Level = 1;
2440  state->destTape = 0;
2441 
2442  state->status = TSS_BUILDRUNS;
2443 }
TupSortStatus status
Definition: tuplesort.c:232
PGRUsage ru_start
Definition: tuplesort.c:463
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2561
LogicalTapeSet * LogicalTapeSetCreate(int ntapes, TapeShare *shared, SharedFileSet *fileset, int worker)
Definition: logtape.c:510
Sharedsort * shared
Definition: tuplesort.c:403
#define MINORDER
Definition: tuplesort.c:219
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define LEADER(state)
Definition: tuplesort.c:532
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
#define WORKER(state)
Definition: tuplesort.c:531
int64 allowedMem
Definition: tuplesort.c:241
#define Assert(condition)
Definition: c.h:732
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2352
int * tp_dummy
Definition: tuplesort.c:369
int * tp_tapenum
Definition: tuplesort.c:370
#define elog(elevel,...)
Definition: elog.h:226
static void inittapestate(Tuplesortstate *state, int maxTapes)
Definition: tuplesort.c:2449
SharedFileSet fileset
Definition: tuplesort.c:488

◆ inittapestate()

static void inittapestate ( Tuplesortstate state,
int  maxTapes 
)
static

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

2450 {
2451  int64 tapeSpace;
2452 
2453  /*
2454  * Decrease availMem to reflect the space needed for tape buffers; but
2455  * don't decrease it to the point that we have no room for tuples. (That
2456  * case is only likely to occur if sorting pass-by-value Datums; in all
2457  * other scenarios the memtuples[] array is unlikely to occupy more than
2458  * half of allowedMem. In the pass-by-value case it's not important to
2459  * account for tuple space, so we don't care if LACKMEM becomes
2460  * inaccurate.)
2461  */
2462  tapeSpace = (int64) maxTapes * TAPE_BUFFER_OVERHEAD;
2463 
2464  if (tapeSpace + GetMemoryChunkSpace(state->memtuples) < state->allowedMem)
2465  USEMEM(state, tapeSpace);
2466 
2467  /*
2468  * Make sure that the temp file(s) underlying the tape set are created in
2469  * suitable temp tablespaces. For parallel sorts, this should have been
2470  * called already, but it doesn't matter if it is called a second time.
2471  */
2473 
2474  state->mergeactive = (bool *) palloc0(maxTapes * sizeof(bool));
2475  state->tp_fib = (int *) palloc0(maxTapes * sizeof(int));
2476  state->tp_runs = (int *) palloc0(maxTapes * sizeof(int));
2477  state->tp_dummy = (int *) palloc0(maxTapes * sizeof(int));
2478  state->tp_tapenum = (int *) palloc0(maxTapes * sizeof(int));
2479 
2480  /* Record # of tapes allocated (for duration of sort) */
2481  state->maxTapes = maxTapes;
2482  /* Record maximum # of tapes usable as inputs when merging */
2483  state->tapeRange = maxTapes - 1;
2484 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:221
void PrepareTempTablespaces(void)
Definition: tablespace.c:1324
int64 allowedMem
Definition: tuplesort.c:241
void * palloc0(Size size)
Definition: mcxt.c:955
int * tp_dummy
Definition: tuplesort.c:369
int * tp_tapenum
Definition: tuplesort.c:370
#define USEMEM(state, amt)
Definition: tuplesort.c:528
bool * mergeactive
Definition: tuplesort.c:358
SortTuple * memtuples
Definition: tuplesort.c:293

◆ leader_takeover_tapes()

static void leader_takeover_tapes ( Tuplesortstate state)
static

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

4521 {
4522  Sharedsort *shared = state->shared;
4523  int nParticipants = state->nParticipants;
4524  int workersFinished;
4525  int j;
4526 
4527  Assert(LEADER(state));
4528  Assert(nParticipants >= 1);
4529 
4530  SpinLockAcquire(&shared->mutex);
4531  workersFinished = shared->workersFinished;
4532  SpinLockRelease(&shared->mutex);
4533 
4534  if (nParticipants != workersFinished)
4535  elog(ERROR, "cannot take over tapes before all workers finish");
4536 
4537  /*
4538  * Create the tapeset from worker tapes, including a leader-owned tape at
4539  * the end. Parallel workers are far more expensive than logical tapes,
4540  * so the number of tapes allocated here should never be excessive.
4541  *
4542  * We still have a leader tape, though it's not possible to write to it
4543  * due to restrictions in the shared fileset infrastructure used by
4544  * logtape.c. It will never be written to in practice because
4545  * randomAccess is disallowed for parallel sorts.
4546  */
4547  inittapestate(state, nParticipants + 1);
4548  state->tapeset = LogicalTapeSetCreate(nParticipants + 1, shared->tapes,
4549  &shared->fileset, state->worker);
4550 
4551  /* mergeruns() relies on currentRun for # of runs (in one-pass cases) */
4552  state->currentRun = nParticipants;
4553 
4554  /*
4555  * Initialize variables of Algorithm D to be consistent with runs from
4556  * workers having been generated in the leader.
4557  *
4558  * There will always be exactly 1 run per worker, and exactly one input
4559  * tape per run, because workers always output exactly 1 run, even when
4560  * there were no input tuples for workers to sort.
4561  */
4562  for (j = 0; j < state->maxTapes; j++)
4563  {
4564  /* One real run; no dummy runs for worker tapes */
4565  state->tp_fib[j] = 1;
4566  state->tp_runs[j] = 1;
4567  state->tp_dummy[j] = 0;
4568  state->tp_tapenum[j] = j;
4569  }
4570  /* Leader tape gets one dummy run, and no real runs */
4571  state->tp_fib[state->tapeRange] = 0;
4572  state->tp_runs[state->tapeRange] = 0;
4573  state->tp_dummy[state->tapeRange] = 1;
4574 
4575  state->Level = 1;
4576  state->destTape = 0;
4577 
4578  state->status = TSS_BUILDRUNS;
4579 }
TupSortStatus status
Definition: tuplesort.c:232
slock_t mutex
Definition: tuplesort.c:474
#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:510
Sharedsort * shared
Definition: tuplesort.c:403
#define LEADER(state)
Definition: tuplesort.c:532
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
int workersFinished
Definition: tuplesort.c:485
#define SpinLockRelease(lock)
Definition: spin.h:64
#define Assert(condition)
Definition: c.h:732
int * tp_dummy
Definition: tuplesort.c:369
int * tp_tapenum
Definition: tuplesort.c:370
#define elog(elevel,...)
Definition: elog.h:226
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:497
static void inittapestate(Tuplesortstate *state, int maxTapes)
Definition: tuplesort.c:2449
SharedFileSet fileset
Definition: tuplesort.c:488

◆ make_bounded_heap()

static void make_bounded_heap ( Tuplesortstate state)
static

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

3220 {
3221  int tupcount = state->memtupcount;
3222  int i;
3223 
3224  Assert(state->status == TSS_INITIAL);
3225  Assert(state->bounded);
3226  Assert(tupcount >= state->bound);
3227  Assert(SERIAL(state));
3228 
3229  /* Reverse sort direction so largest entry will be at root */
3230  reversedirection(state);
3231 
3232  state->memtupcount = 0; /* make the heap empty */
3233  for (i = 0; i < tupcount; i++)
3234  {
3235  if (state->memtupcount < state->bound)
3236  {
3237  /* Insert next tuple into heap */
3238  /* Must copy source tuple to avoid possible overwrite */
3239  SortTuple stup = state->memtuples[i];
3240 
3241  tuplesort_heap_insert(state, &stup);
3242  }
3243  else
3244  {
3245  /*
3246  * The heap is full. Replace the largest entry with the new
3247  * tuple, or just discard it, if it's larger than anything already
3248  * in the heap.
3249  */
3250  if (COMPARETUP(state, &state->memtuples[i], &state->memtuples[0]) <= 0)
3251  {
3252  free_sort_tuple(state, &state->memtuples[i]);
3254  }
3255  else
3256  tuplesort_heap_replace_top(state, &state->memtuples[i]);
3257  }
3258  }
3259 
3260  Assert(state->memtupcount == state->bound);
3261  state->status = TSS_BOUNDED;
3262 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3435
TupSortStatus status
Definition: tuplesort.c:232
#define SERIAL(state)
Definition: tuplesort.c:530
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4585
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:523
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3336
#define Assert(condition)
Definition: c.h:732
int i
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3395
SortTuple * memtuples
Definition: tuplesort.c:293

◆ markrunend()

static void markrunend ( Tuplesortstate state,
int  tapenum 
)
static

Definition at line 3466 of file tuplesort.c.

References LogicalTapeWrite(), and Tuplesortstate::tapeset.

Referenced by dumptuples(), and mergeonerun().

3467 {
3468  unsigned int len = 0;
3469 
3470  LogicalTapeWrite(state->tapeset, tapenum, (void *) &len, sizeof(len));
3471 }
void LogicalTapeWrite(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:621
LogicalTapeSet * tapeset
Definition: tuplesort.c:246

◆ mergeonerun()

static void mergeonerun ( Tuplesortstate state)
static

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

2789 {
2790  int destTape = state->tp_tapenum[state->tapeRange];
2791  int srcTape;
2792 
2793  /*
2794  * Start the merge by loading one tuple from each active source tape into
2795  * the heap. We can also decrease the input run/dummy run counts.
2796  */
2797  beginmerge(state);
2798 
2799  /*
2800  * Execute merge by repeatedly extracting lowest tuple in heap, writing it
2801  * out, and replacing it with next tuple from same tape (if there is
2802  * another one).
2803  */
2804  while (state->memtupcount > 0)
2805  {
2806  SortTuple stup;
2807 
2808  /* write the tuple to destTape */
2809  srcTape = state->memtuples[0].srctape;
2810  WRITETUP(state, destTape, &state->memtuples[0]);
2811 
2812  /* recycle the slot of the tuple we just wrote out, for the next read */
2813  if (state->memtuples[0].tuple)
2814  RELEASE_SLAB_SLOT(state, state->memtuples[0].tuple);
2815 
2816  /*
2817  * pull next tuple from the tape, and replace the written-out tuple in
2818  * the heap with it.
2819  */
2820  if (mergereadnext(state, srcTape, &stup))
2821  {
2822  stup.srctape = srcTape;
2823  tuplesort_heap_replace_top(state, &stup);
2824  }
2825  else
2827  }
2828 
2829  /*
2830  * When the heap empties, we're done. Write an end-of-run marker on the
2831  * output tape, and increment its count of real runs.
2832  */
2833  markrunend(state, destTape);
2834  state->tp_runs[state->tapeRange]++;
2835 
2836 #ifdef TRACE_SORT
2837  if (trace_sort)
2838  elog(LOG, "worker %d finished %d-way merge step: %s", state->worker,
2839  state->activeTapes, pg_rusage_show(&state->ru_start));
2840 #endif
2841 }
PGRUsage ru_start
Definition: tuplesort.c:463
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3466
void * tuple
Definition: tuplesort.c:169
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:525
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:511
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3371
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2899
int srctape
Definition: tuplesort.c:172
int * tp_tapenum
Definition: tuplesort.c:370
#define elog(elevel,...)
Definition: elog.h:226
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3395
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:2851
SortTuple * memtuples
Definition: tuplesort.c:293

◆ mergereadnext()

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

Definition at line 2899 of file tuplesort.c.

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

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

2900 {
2901  unsigned int tuplen;
2902 
2903  if (!state->mergeactive[srcTape])
2904  return false; /* tape's run is already exhausted */
2905 
2906  /* read next tuple, if any */
2907  if ((tuplen = getlen(state, srcTape, true)) == 0)
2908  {
2909  state->mergeactive[srcTape] = false;
2910  return false;
2911  }
2912  READTUP(state, stup, srcTape, tuplen);
2913 
2914  return true;
2915 }
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3453
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:526
bool * mergeactive
Definition: tuplesort.c:358

◆ mergeruns()

static void mergeruns ( Tuplesortstate state)
static

Definition at line 2561 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(), Max, Tuplesortstate::maxTapes, MemoryContextDelete(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, mergeonerun(), palloc(), 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().

2562 {
2563  int tapenum,
2564  svTape,
2565  svRuns,
2566  svDummy;
2567  int numTapes;
2568  int numInputTapes;
2569 
2570  Assert(state->status == TSS_BUILDRUNS);
2571  Assert(state->memtupcount == 0);
2572 
2573  if (state->sortKeys != NULL && state->sortKeys->abbrev_converter != NULL)
2574  {
2575  /*
2576  * If there are multiple runs to be merged, when we go to read back
2577  * tuples from disk, abbreviated keys will not have been stored, and
2578  * we don't care to regenerate them. Disable abbreviation from this
2579  * point on.
2580  */
2581  state->sortKeys->abbrev_converter = NULL;
2583 
2584  /* Not strictly necessary, but be tidy */
2585  state->sortKeys->abbrev_abort = NULL;
2586  state->sortKeys->abbrev_full_comparator = NULL;
2587  }
2588 
2589  /*
2590  * Reset tuple memory. We've freed all the tuples that we previously
2591  * allocated. We will use the slab allocator from now on.
2592  */
2594  state->tuplecontext = NULL;
2595 
2596  /*
2597  * We no longer need a large memtuples array. (We will allocate a smaller
2598  * one for the heap later.)
2599  */
2600  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
2601  pfree(state->memtuples);
2602  state->memtuples = NULL;
2603 
2604  /*
2605  * If we had fewer runs than tapes, refund the memory that we imagined we
2606  * would need for the tape buffers of the unused tapes.
2607  *
2608  * numTapes and numInputTapes reflect the actual number of tapes we will
2609  * use. Note that the output tape's tape number is maxTapes - 1, so the
2610  * tape numbers of the used tapes are not consecutive, and you cannot just
2611  * loop from 0 to numTapes to visit all used tapes!
2612  */
2613  if (state->Level == 1)
2614  {
2615  numInputTapes = state->currentRun;
2616  numTapes = numInputTapes + 1;
2617  FREEMEM(state, (state->maxTapes - numTapes) * TAPE_BUFFER_OVERHEAD);
2618  }
2619  else
2620  {
2621  numInputTapes = state->tapeRange;
2622  numTapes = state->maxTapes;
2623  }
2624 
2625  /*
2626  * Initialize the slab allocator. We need one slab slot per input tape,
2627  * for the tuples in the heap, plus one to hold the tuple last returned
2628  * from tuplesort_gettuple. (If we're sorting pass-by-val Datums,
2629  * however, we don't need to do allocate anything.)
2630  *
2631  * From this point on, we no longer use the USEMEM()/LACKMEM() mechanism
2632  * to track memory usage of individual tuples.
2633  */
2634  if (state->tuples)
2635  init_slab_allocator(state, numInputTapes + 1);
2636  else
2637  init_slab_allocator(state, 0);
2638 
2639  /*
2640  * Allocate a new 'memtuples' array, for the heap. It will hold one tuple
2641  * from each input tape.
2642  */
2643  state->memtupsize = numInputTapes;
2644  state->memtuples = (SortTuple *) palloc(numInputTapes * sizeof(SortTuple));
2645  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
2646 
2647  /*
2648  * Use all the remaining memory we have available for read buffers among
2649  * the input tapes.
2650  *
2651  * We don't try to "rebalance" the memory among tapes, when we start a new
2652  * merge phase, even if some tapes are inactive in the new phase. That
2653  * would be hard, because logtape.c doesn't know where one run ends and
2654  * another begins. When a new merge phase begins, and a tape doesn't
2655  * participate in it, its buffer nevertheless already contains tuples from
2656  * the next run on same tape, so we cannot release the buffer. That's OK
2657  * in practice, merge performance isn't that sensitive to the amount of
2658  * buffers used, and most merge phases use all or almost all tapes,
2659  * anyway.
2660  */
2661 #ifdef TRACE_SORT
2662  if (trace_sort)
2663  elog(LOG, "worker %d using " INT64_FORMAT " KB of memory for read buffers among %d input tapes",
2664  state->worker, state->availMem / 1024, numInputTapes);
2665 #endif
2666 
2667  state->read_buffer_size = Max(state->availMem / numInputTapes, 0);
2668  USEMEM(state, state->read_buffer_size * numInputTapes);
2669 
2670  /* End of step D2: rewind all output tapes to prepare for merging */
2671  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2672  LogicalTapeRewindForRead(state->tapeset, tapenum, state->read_buffer_size);
2673 
2674  for (;;)
2675  {
2676  /*
2677  * At this point we know that tape[T] is empty. If there's just one
2678  * (real or dummy) run left on each input tape, then only one merge
2679  * pass remains. If we don't have to produce a materialized sorted
2680  * tape, we can stop at this point and do the final merge on-the-fly.
2681  */
2682  if (!state->randomAccess && !WORKER(state))
2683  {
2684  bool allOneRun = true;
2685 
2686  Assert(state->tp_runs[state->tapeRange] == 0);
2687  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2688  {
2689  if (state->tp_runs[tapenum] + state->tp_dummy[tapenum] != 1)
2690  {
2691  allOneRun = false;
2692  break;
2693  }
2694  }
2695  if (allOneRun)
2696  {
2697  /* Tell logtape.c we won't be writing anymore */
2699  /* Initialize for the final merge pass */
2700  beginmerge(state);
2701  state->status = TSS_FINALMERGE;
2702  return;
2703  }
2704  }
2705 
2706  /* Step D5: merge runs onto tape[T] until tape[P] is empty */
2707  while (state->tp_runs[state->tapeRange - 1] ||
2708  state->tp_dummy[state->tapeRange - 1])
2709  {
2710  bool allDummy = true;
2711 
2712  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2713  {
2714  if (state->tp_dummy[tapenum] == 0)
2715  {
2716  allDummy = false;
2717  break;
2718  }
2719  }
2720 
2721  if (allDummy)
2722  {
2723  state->tp_dummy[state->tapeRange]++;
2724  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2725  state->tp_dummy[tapenum]--;
2726  }
2727  else
2728  mergeonerun(state);
2729  }
2730 
2731  /* Step D6: decrease level */
2732  if (--state->Level == 0)
2733  break;
2734  /* rewind output tape T to use as new input */
2735  LogicalTapeRewindForRead(state->tapeset, state->tp_tapenum[state->tapeRange],
2736  state->read_buffer_size);
2737  /* rewind used-up input tape P, and prepare it for write pass */
2738  LogicalTapeRewindForWrite(state->tapeset, state->tp_tapenum[state->tapeRange - 1]);
2739  state->tp_runs[state->tapeRange - 1] = 0;
2740 
2741  /*
2742  * reassign tape units per step D6; note we no longer care about A[]
2743  */
2744  svTape = state->tp_tapenum[state->tapeRange];
2745  svDummy = state->tp_dummy[state->tapeRange];
2746  svRuns = state->tp_runs[state->tapeRange];
2747  for (tapenum = state->tapeRange; tapenum > 0; tapenum--)
2748  {
2749  state->tp_tapenum[tapenum] = state->tp_tapenum[tapenum - 1];
2750  state->tp_dummy[tapenum] = state->tp_dummy[tapenum - 1];
2751  state->tp_runs[tapenum] = state->tp_runs[tapenum - 1];
2752  }
2753  state->tp_tapenum[0] = svTape;
2754  state->tp_dummy[0] = svDummy;
2755  state->tp_runs[0] = svRuns;
2756  }
2757 
2758  /*
2759  * Done. Knuth says that the result is on TAPE[1], but since we exited
2760  * the loop without performing the last iteration of step D6, we have not
2761  * rearranged the tape unit assignment, and therefore the result is on
2762  * TAPE[T]. We need to do it this way so that we can freeze the final
2763  * output tape while rewinding it. The last iteration of step D6 would be
2764  * a waste of cycles anyway...
2765  */
2766  state->result_tape = state->tp_tapenum[state->tapeRange];
2767  if (!WORKER(state))
2768  LogicalTapeFreeze(state->tapeset, state->result_tape, NULL);
2769  else
2771  state->status = TSS_SORTEDONTAPE;
2772 
2773  /* Release the read buffers of all the other tapes, by rewinding them. */
2774  for (tapenum = 0; tapenum < state->maxTapes; tapenum++)
2775  {
2776  if (tapenum != state->result_tape)
2777  LogicalTapeRewindForWrite(state->tapeset, tapenum);
2778  }
2779 }
int64 availMem
Definition: tuplesort.c:240
size_t read_buffer_size
Definition: tuplesort.c:332
TupSortStatus status
Definition: tuplesort.c:232
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
static void mergeonerun(Tuplesortstate *state)
Definition: tuplesort.c:2788
static void worker_freeze_result_tape(Tuplesortstate *state)
Definition: tuplesort.c:4461
SortSupport sortKeys
Definition: tuplesort.c:412
bool randomAccess
Definition: tuplesort.c:234
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:796
static void init_slab_allocator(Tuplesortstate *state, int numSlots)
Definition: tuplesort.c:2525
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:221
void pfree(void *pointer)
Definition: mcxt.c:1031
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:529
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
#define WORKER(state)
Definition: tuplesort.c:531
#define Max(x, y)
Definition: c.h:898
#define Assert(condition)
Definition: c.h:732
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182
#define INT64_FORMAT
Definition: c.h:400
void LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Definition: logtape.c:709
int * tp_dummy
Definition: tuplesort.c:369
void LogicalTapeFreeze(LogicalTapeSet *lts, int tapenum, TapeShare *share)
Definition: logtape.c:876
MemoryContext tuplecontext
Definition: tuplesort.c:245
void * palloc(Size size)
Definition: mcxt.c:924
int * tp_tapenum
Definition: tuplesort.c:370
#define USEMEM(state, amt)
Definition: tuplesort.c:528
#define elog(elevel,...)
Definition: elog.h:226
void LogicalTapeSetForgetFreeSpace(LogicalTapeSet *lts)
Definition: logtape.c:610
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:2851
SortTuple * memtuples
Definition: tuplesort.c:293

◆ puttuple_common()

static void puttuple_common ( Tuplesortstate state,
SortTuple tuple 
)
static

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

1638 {
1639  Assert(!LEADER(state));
1640 
1641  switch (state->status)
1642  {
1643  case TSS_INITIAL:
1644 
1645  /*
1646  * Save the tuple into the unsorted array. First, grow the array
1647  * as needed. Note that we try to grow the array when there is
1648  * still one free slot remaining --- if we fail, there'll still be
1649  * room to store the incoming tuple, and then we'll switch to
1650  * tape-based operation.
1651  */
1652  if (state->memtupcount >= state->memtupsize - 1)
1653  {
1654  (void) grow_memtuples(state);
1655  Assert(state->memtupcount < state->memtupsize);
1656  }
1657  state->memtuples[state->memtupcount++] = *tuple;
1658 
1659  /*
1660  * Check if it's time to switch over to a bounded heapsort. We do
1661  * so if the input tuple count exceeds twice the desired tuple
1662  * count (this is a heuristic for where heapsort becomes cheaper
1663  * than a quicksort), or if we've just filled workMem and have
1664  * enough tuples to meet the bound.
1665  *
1666  * Note that once we enter TSS_BOUNDED state we will always try to
1667  * complete the sort that way. In the worst case, if later input
1668  * tuples are larger than earlier ones, this might cause us to
1669  * exceed workMem significantly.
1670  */
1671  if (state->bounded &&
1672  (state->memtupcount > state->bound * 2 ||
1673  (state->memtupcount > state->bound && LACKMEM(state))))
1674  {
1675 #ifdef TRACE_SORT
1676  if (trace_sort)
1677  elog(LOG, "switching to bounded heapsort at %d tuples: %s",
1678  state->memtupcount,
1679  pg_rusage_show(&state->ru_start));
1680 #endif
1681  make_bounded_heap(state);
1682  return;
1683  }
1684 
1685  /*
1686  * Done if we still fit in available memory and have array slots.
1687  */
1688  if (state->memtupcount < state->memtupsize && !LACKMEM(state))
1689  return;
1690 
1691  /*
1692  * Nope; time to switch to tape-based operation.
1693  */
1694  inittapes(state, true);
1695 
1696  /*
1697  * Dump all tuples.
1698  */
1699  dumptuples(state, false);
1700  break;
1701 
1702  case TSS_BOUNDED:
1703 
1704  /*
1705  * We don't want to grow the array here, so check whether the new
1706  * tuple can be discarded before putting it in. This should be a
1707  * good speed optimization, too, since when there are many more
1708  * input tuples than the bound, most input tuples can be discarded
1709  * with just this one comparison. Note that because we currently
1710  * have the sort direction reversed, we must check for <= not >=.
1711  */
1712  if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
1713  {
1714  /* new tuple <= top of the heap, so we can discard it */
1715  free_sort_tuple(state, tuple);
1717  }
1718  else
1719  {
1720  /* discard top of heap, replacing it with the new tuple */
1721  free_sort_tuple(state, &state->memtuples[0]);
1722  tuplesort_heap_replace_top(state, tuple);
1723  }
1724  break;
1725 
1726  case TSS_BUILDRUNS:
1727 
1728  /*
1729  * Save the tuple into the unsorted array (there must be space)
1730  */
1731  state->memtuples[state->memtupcount++] = *tuple;
1732 
1733  /*
1734  * If we are over the memory limit, dump all tuples.
1735  */
1736  dumptuples(state, false);
1737  break;
1738 
1739  default:
1740  elog(ERROR, "invalid tuplesort state");
1741  break;
1742  }
1743 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2924
TupSortStatus status
Definition: tuplesort.c:232
static bool grow_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:1315
PGRUsage ru_start
Definition: tuplesort.c:463
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:2392
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:130
#define ERROR
Definition: elog.h:43
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4585
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:523
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define LEADER(state)
Definition: tuplesort.c:532
#define Assert(condition)
Definition: c.h:732
#define elog(elevel,...)
Definition: elog.h:226
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
static void make_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3219
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3395
#define LACKMEM(state)
Definition: tuplesort.c:527
SortTuple * memtuples
Definition: tuplesort.c:293

◆ readtup_alloc()

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

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

3481 {
3482  SlabSlot *buf;
3483 
3484  /*
3485  * We pre-allocate enough slots in the slab arena that we should never run
3486  * out.
3487  */
3488  Assert(state->slabFreeHead);
3489 
3490  if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
3491  return MemoryContextAlloc(state->sortcontext, tuplen);
3492  else
3493  {
3494  buf = state->slabFreeHead;
3495  /* Reuse this slot */
3496  state->slabFreeHead = buf->nextfree;
3497 
3498  return buf;
3499  }
3500 }
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:186
union SlabSlot * nextfree
Definition: tuplesort.c:190
MemoryContext sortcontext
Definition: tuplesort.c:244
static char * buf
Definition: pg_test_fsync.c:68
#define Assert(condition)
Definition: c.h:732
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:771
SlabSlot * slabFreeHead
Definition: tuplesort.c:329

◆ readtup_cluster()

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

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

3917 {
3918  unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
3919  HeapTuple tuple = (HeapTuple) readtup_alloc(state,
3920  t_len + HEAPTUPLESIZE);
3921 
3922  /* Reconstruct the HeapTupleData header */
3923  tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
3924  tuple->t_len = t_len;
3925  LogicalTapeReadExact(state->tapeset, tapenum,
3926  &tuple->t_self, sizeof(ItemPointerData));
3927  /* We don't currently bother to reconstruct t_tableOid */
3928  tuple->t_tableOid = InvalidOid;
3929  /* Read in the tuple body */
3930  LogicalTapeReadExact(state->tapeset, tapenum,
3931  tuple->t_data, tuple->t_len);
3932  if (state->randomAccess) /* need trailing length word? */
3933  LogicalTapeReadExact(state->tapeset, tapenum,
3934  &tuplen, sizeof(tuplen));
3935  stup->tuple = (void *) tuple;
3936  /* set up first-column key value, if it's a simple column */
3937  if (state->indexInfo->ii_IndexAttrNumbers[0] != 0)
3938  stup->datum1 = heap_getattr(tuple,
3939  state->indexInfo->ii_IndexAttrNumbers[0],
3940  state->tupDesc,
3941  &stup->isnull1);
3942 }
HeapTupleData * HeapTuple
Definition: htup.h:71
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
bool randomAccess
Definition: tuplesort.c:234
Datum datum1
Definition: tuplesort.c:170
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:584
bool isnull1
Definition: tuplesort.c:171
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:169
ItemPointerData t_self
Definition: htup.h:65
uint32 t_len
Definition: htup.h:64
IndexInfo * indexInfo
Definition: tuplesort.c:433
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
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:3480
#define HEAPTUPLESIZE
Definition: htup.h:73
AttrNumber ii_IndexAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:159
TupleDesc tupDesc
Definition: tuplesort.c:411

◆ readtup_datum()

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

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

4324 {
4325  unsigned int tuplen = len - sizeof(unsigned int);
4326 
4327  if (tuplen == 0)
4328  {
4329  /* it's NULL */
4330  stup->datum1 = (Datum) 0;
4331  stup->isnull1 = true;
4332  stup->tuple = NULL;
4333  }
4334  else if (!state->tuples)
4335  {
4336  Assert(tuplen == sizeof(Datum));
4337  LogicalTapeReadExact(state->tapeset, tapenum,
4338  &stup->datum1, tuplen);
4339  stup->isnull1 = false;
4340  stup->tuple = NULL;
4341  }
4342  else
4343  {
4344  void *raddr = readtup_alloc(state, tuplen);
4345 
4346  LogicalTapeReadExact(state->tapeset, tapenum,
4347  raddr, tuplen);
4348  stup->datum1 = PointerGetDatum(raddr);
4349  stup->isnull1 = false;
4350  stup->tuple = raddr;
4351  }
4352 
4353  if (state->randomAccess) /* need trailing length word? */
4354  LogicalTapeReadExact(state->tapeset, tapenum,
4355  &tuplen, sizeof(tuplen));
4356 }
#define PointerGetDatum(X)
Definition: postgres.h:556
bool randomAccess
Definition: tuplesort.c:234
Datum datum1
Definition: tuplesort.c:170
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:584
bool isnull1
Definition: tuplesort.c:171
void * tuple
Definition: tuplesort.c:169
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
uintptr_t Datum
Definition: postgres.h:367
#define Assert(condition)
Definition: c.h:732
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3480

◆ readtup_heap()

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

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

3677 {
3678  unsigned int tupbodylen = len - sizeof(int);
3679  unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
3680  MinimalTuple tuple = (MinimalTuple) readtup_alloc(state, tuplen);
3681  char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
3682  HeapTupleData htup;
3683 
3684  /* read in the tuple proper */
3685  tuple->t_len = tuplen;
3686  LogicalTapeReadExact(state->tapeset, tapenum,
3687  tupbody, tupbodylen);
3688  if (state->randomAccess) /* need trailing length word? */
3689  LogicalTapeReadExact(state->tapeset, tapenum,
3690  &tuplen, sizeof(tuplen));
3691  stup->tuple = (void *) tuple;
3692  /* set up first-column key value */
3693  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3694  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3695  stup->datum1 = heap_getattr(&htup,
3696  state->sortKeys[0].ssup_attno,
3697  state->tupDesc,
3698  &stup->isnull1);
3699 }
#define MINIMAL_TUPLE_DATA_OFFSET
Definition: htup_details.h:623
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:412
bool randomAccess
Definition: tuplesort.c:234
Datum datum1
Definition: tuplesort.c:170
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:584
bool isnull1
Definition: tuplesort.c:171
HeapTupleHeader t_data
Definition: htup.h:68
void * tuple
Definition: tuplesort.c:169
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
#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:3480
TupleDesc tupDesc
Definition: tuplesort.c:411

◆ readtup_index()

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

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

4231 {
4232  unsigned int tuplen = len - sizeof(unsigned int);
4233  IndexTuple tuple = (IndexTuple) readtup_alloc(state, tuplen);
4234 
4235  LogicalTapeReadExact(state->tapeset, tapenum,
4236  tuple, tuplen);
4237  if (state->randomAccess) /* need trailing length word? */
4238  LogicalTapeReadExact(state->tapeset, tapenum,
4239  &tuplen, sizeof(tuplen));
4240  stup->tuple = (void *) tuple;
4241  /* set up first-column key value */
4242  stup->datum1 = index_getattr(tuple,
4243  1,
4244  RelationGetDescr(state->indexRel),
4245  &stup->isnull1);
4246 }
#define RelationGetDescr(relation)
Definition: rel.h:442
bool randomAccess
Definition: tuplesort.c:234
Datum datum1
Definition: tuplesort.c:170
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:584
bool isnull1
Definition: tuplesort.c:171
void * tuple
Definition: tuplesort.c:169
IndexTupleData * IndexTuple
Definition: itup.h:53
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
Relation indexRel
Definition: tuplesort.c:441
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3480

◆ reversedirection()

static void reversedirection ( Tuplesortstate state)
static

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

3436 {
3437  SortSupport sortKey = state->sortKeys;
3438  int nkey;
3439 
3440  for (nkey = 0; nkey < state->nKeys; nkey++, sortKey++)
3441  {
3442  sortKey->ssup_reverse = !sortKey->ssup_reverse;
3443  sortKey->ssup_nulls_first = !sortKey->ssup_nulls_first;
3444  }
3445 }
bool ssup_nulls_first
Definition: sortsupport.h:75
SortSupport sortKeys
Definition: tuplesort.c:412

◆ selectnewtape()

static void selectnewtape ( Tuplesortstate state)
static

Definition at line 2493 of file tuplesort.c.

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

Referenced by dumptuples().

2494 {
2495  int j;
2496  int a;
2497 
2498  /* Step D3: advance j (destTape) */
2499  if (state->tp_dummy[state->destTape] < state->tp_dummy[state->destTape + 1])
2500  {
2501  state->destTape++;
2502  return;
2503  }
2504  if (state->tp_dummy[state->destTape] != 0)
2505  {
2506  state->destTape = 0;
2507  return;
2508  }
2509 
2510  /* Step D4: increase level */
2511  state->Level++;
2512  a = state->tp_fib[0];
2513  for (j = 0; j < state->tapeRange; j++)
2514  {
2515  state->tp_dummy[j] = a + state->tp_fib[j + 1] - state->tp_fib[j];
2516  state->tp_fib[j] = a + state->tp_fib[j + 1];
2517  }
2518  state->destTape = 0;
2519 }
int * tp_dummy
Definition: tuplesort.c:369

◆ sort_bounded_heap()

static void sort_bounded_heap ( Tuplesortstate state)
static

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

3269 {
3270  int tupcount = state->memtupcount;
3271 
3272  Assert(state->status == TSS_BOUNDED);
3273  Assert(state->bounded);
3274  Assert(tupcount == state->bound);
3275  Assert(SERIAL(state));
3276 
3277  /*
3278  * We can unheapify in place because each delete-top call will remove the
3279  * largest entry, which we can promptly store in the newly freed slot at
3280  * the end. Once we're down to a single-entry heap, we're done.
3281  */
3282  while (state->memtupcount > 1)
3283  {
3284  SortTuple stup = state->memtuples[0];
3285 
3286  /* this sifts-up the next-largest entry and decreases memtupcount */
3288  state->memtuples[state->memtupcount] = stup;
3289  }
3290  state->memtupcount = tupcount;
3291 
3292  /*
3293  * Reverse sort direction back to the original state. This is not
3294  * actually necessary but seems like a good idea for tidiness.
3295  */
3296  reversedirection(state);
3297 
3298  state->status = TSS_SORTEDINMEM;
3299  state->boundUsed = true;
3300 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3435
TupSortStatus status
Definition: tuplesort.c:232
#define SERIAL(state)
Definition: tuplesort.c:530
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3371
#define Assert(condition)
Definition: c.h:732
SortTuple * memtuples
Definition: tuplesort.c:293

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 4413 of file tuplesort.c.

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

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

◆ tuplesort_begin_cluster()

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

Definition at line 880 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

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

◆ tuplesort_begin_common()

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

Definition at line 681 of file tuplesort.c.

References ALLOCSET_DEFAULT_SIZES, ALLOCSET_SEPARATE_THRESHOLD, AllocSetContextCreate, Tuplesortstate::allowedMem, Assert, Tuplesortstate::availMem, Tuplesortstate::bounded, Tuplesortstate::boundUsed, CurrentMemoryContext, Tuplesortstate::currentRun, elog, ERROR, GetMemoryChunkSpace(), Tuplesortstate::growmemtuples, SortCoordinateData::isWorker, LACKMEM, Max, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, SortCoordinateData::nParticipants, Tuplesortstate::nParticipants, palloc(), palloc0(), pg_rusage_init(), Tuplesortstate::randomAccess, Tuplesortstate::result_tape, Tuplesortstate::ru_start, Tuplesortstate::shared, SortCoordinateData::sharedsort, Tuplesortstate::slabAllocatorUsed, Tuplesortstate::sortcontext, Tuplesortstate::status, Tuplesortstate::tapeset, trace_sort, TSS_INITIAL, Tuplesortstate::tuplecontext, Tuplesortstate::tuples, USEMEM, 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().

683 {
685  MemoryContext sortcontext;
686  MemoryContext tuplecontext;
687  MemoryContext oldcontext;
688 
689  /* See leader_takeover_tapes() remarks on randomAccess support */
690  if (coordinate && randomAccess)
691  elog(ERROR, "random access disallowed under parallel sort");
692 
693  /*
694  * Create a working memory context for this sort operation. All data
695  * needed by the sort will live inside this context.
696  */
698  "TupleSort main",
700 
701  /*
702  * Caller tuple (e.g. IndexTuple) memory context.
703  *
704  * A dedicated child context used exclusively for caller passed tuples
705  * eases memory management. Resetting at key points reduces
706  * fragmentation. Note that the memtuples array of SortTuples is allocated
707  * in the parent context, not this context, because there is no need to
708  * free memtuples early.
709  */
710  tuplecontext = AllocSetContextCreate(sortcontext,
711  "Caller tuples",
713 
714  /*
715  * Make the Tuplesortstate within the per-sort context. This way, we
716  * don't need a separate pfree() operation for it at shutdown.
717  */
718  oldcontext = MemoryContextSwitchTo(sortcontext);
719 
720  state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));
721 
722 #ifdef TRACE_SORT
723  if (trace_sort)
724  pg_rusage_init(&state->ru_start);
725 #endif
726 
727  state->status = TSS_INITIAL;
728  state->randomAccess = randomAccess;
729  state->bounded = false;
730  state->tuples = true;
731  state->boundUsed = false;
732 
733  /*
734  * workMem is forced to be at least 64KB, the current minimum valid value
735  * for the work_mem GUC. This is a defense against parallel sort callers
736  * that divide out memory among many workers in a way that leaves each
737  * with very little memory.
738  */
739  state->allowedMem = Max(workMem, 64) * (int64) 1024;
740  state->availMem = state->allowedMem;
741  state->sortcontext = sortcontext;
742  state->tuplecontext = tuplecontext;
743  state->tapeset = NULL;
744 
745  state->memtupcount = 0;
746 
747  /*
748  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
749  * see comments in grow_memtuples().
750  */
751  state->memtupsize = Max(1024,
752  ALLOCSET_SEPARATE_THRESHOLD / sizeof(SortTuple) + 1);
753 
754  state->growmemtuples = true;
755  state->slabAllocatorUsed = false;
756  state->memtuples = (SortTuple *) palloc(state->memtupsize * sizeof(SortTuple));
757 
758  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
759 
760  /* workMem must be large enough for the minimal memtuples array */
761  if (LACKMEM(state))
762  elog(ERROR, "insufficient memory allowed for sort");
763 
764  state->currentRun = 0;
765 
766  /*
767  * maxTapes, tapeRange, and Algorithm D variables will be initialized by
768  * inittapes(), if needed
769  */
770 
771  state->result_tape = -1; /* flag that result tape has not been formed */
772 
773  /*
774  * Initialize parallel-related state based on coordination information
775  * from caller
776  */
777  if (!coordinate)
778  {
779  /* Serial sort */
780  state->shared = NULL;
781  state->worker = -1;
782  state->nParticipants = -1;
783  }
784  else if (coordinate->isWorker)
785  {
786  /* Parallel worker produces exactly one final run from all input */
787  state->shared = coordinate->sharedsort;
788  state->worker = worker_get_identifier(state);
789  state->nParticipants = -1;
790  }
791  else
792  {
793  /* Parallel leader state only used for final merge */
794  state->shared = coordinate->sharedsort;
795  state->worker = -1;
796  state->nParticipants = coordinate->nParticipants;
797  Assert(state->nParticipants >= 1);
798  }
799 
800  MemoryContextSwitchTo(oldcontext);
801 
802  return state;
803 }
int64 availMem
Definition: tuplesort.c:240
TupSortStatus status
Definition: tuplesort.c:232
#define AllocSetContextCreate
Definition: memutils.h:169
PGRUsage ru_start
Definition: tuplesort.c:463
bool randomAccess
Definition: tuplesort.c:234
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Sharedsort * sharedsort
Definition: tuplesort.h:55
bool growmemtuples
Definition: tuplesort.c:296
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
static int worker_get_identifier(Tuplesortstate *state)
Definition: tuplesort.c:4433
bool trace_sort
Definition: tuplesort.c:130
void pg_rusage_init(PGRUsage *ru0)
Definition: pg_rusage.c:27
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:244
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:191
Sharedsort * shared
Definition: tuplesort.c:403
#define ALLOCSET_SEPARATE_THRESHOLD
Definition: memutils.h:218
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
int64 allowedMem
Definition: tuplesort.c:241
void * palloc0(Size size)
Definition: mcxt.c:955
#define Max(x, y)
Definition: c.h:898
#define Assert(condition)
Definition: c.h:732
Definition: regguts.h:298
bool slabAllocatorUsed
Definition: tuplesort.c:325
MemoryContext tuplecontext
Definition: tuplesort.c:245
void * palloc(Size size)
Definition: mcxt.c:924
#define USEMEM(state, amt)
Definition: tuplesort.c:528
#define elog(elevel,...)
Definition: elog.h:226
#define LACKMEM(state)
Definition: tuplesort.c:527
SortTuple * memtuples
Definition: tuplesort.c:293

◆ tuplesort_begin_datum()

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

Definition at line 1099 of file tuplesort.c.

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

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

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

◆ tuplesort_begin_heap()

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

Definition at line 806 of file tuplesort.c.

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

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

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

◆ tuplesort_begin_index_btree()

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

Definition at line 975 of file tuplesort.c.

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

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

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

◆ tuplesort_begin_index_hash()

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

Definition at line 1053 of file tuplesort.c.

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

Referenced by _h_spoolinit().

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

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1235 of file tuplesort.c.

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

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

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

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nWorkers)

Definition at line 4369 of file tuplesort.c.

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

Referenced by _bt_begin_parallel().

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

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 3128 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, Tuplesortstate::boundUsed, LogicalTapeSetBlocks(), SORT_SPACE_TYPE_DISK, SORT_SPACE_TYPE_MEMORY, SORT_TYPE_EXTERNAL_MERGE, SORT_TYPE_EXTERNAL_SORT, SORT_TYPE_QUICKSORT, SORT_TYPE_STILL_IN_PROGRESS, SORT_TYPE_TOP_N_HEAPSORT, TuplesortInstrumentation::sortMethod, TuplesortInstrumentation::spaceType, TuplesortInstrumentation::spaceUsed, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_FINALMERGE, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

Referenced by ExecSort(), and show_sort_info().

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

◆ tuplesort_getdatum()

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

Definition at line 2244 of file tuplesort.c.

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

Referenced by 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().

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

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2195 of file tuplesort.c.

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

Referenced by heapam_relation_copy_for_cluster().

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

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2215 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

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

◆ tuplesort_gettuple_common()

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

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

1903 {
1904  unsigned int tuplen;
1905  size_t nmoved;
1906 
1907  Assert(!WORKER(state));
1908 
1909  switch (state->status)
1910  {
1911  case TSS_SORTEDINMEM:
1912  Assert(forward || state->randomAccess);
1913  Assert(!state->slabAllocatorUsed);
1914  if (forward)
1915  {
1916  if (state->current < state->memtupcount)
1917  {
1918  *stup = state->memtuples[state->current++];
1919  return true;
1920  }
1921  state->eof_reached = true;
1922 
1923  /*
1924  * Complain if caller tries to retrieve more tuples than
1925  * originally asked for in a bounded sort. This is because
1926  * returning EOF here might be the wrong thing.
1927  */
1928  if (state->bounded && state->current >= state->bound)
1929  elog(ERROR, "retrieved too many tuples in a bounded sort");
1930 
1931  return false;
1932  }
1933  else
1934  {
1935  if (state->current <= 0)
1936  return false;
1937 
1938  /*
1939  * if all tuples are fetched already then we return last
1940  * tuple, else - tuple before last returned.
1941  */
1942  if (state->eof_reached)
1943  state->eof_reached = false;
1944  else
1945  {
1946  state->current--; /* last returned tuple */
1947  if (state->current <= 0)
1948  return false;
1949  }
1950  *stup = state->memtuples[state->current - 1];
1951  return true;
1952  }
1953  break;
1954 
1955  case TSS_SORTEDONTAPE:
1956  Assert(forward || state->randomAccess);
1957  Assert(state->slabAllocatorUsed);
1958 
1959  /*
1960  * The slot that held the tuple that we returned in previous
1961  * gettuple call can now be reused.
1962  */
1963  if (state->lastReturnedTuple)
1964  {
1965  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1966  state->lastReturnedTuple = NULL;
1967  }
1968 
1969  if (forward)
1970  {
1971  if (state->eof_reached)
1972  return false;
1973 
1974  if ((tuplen = getlen(state, state->result_tape, true)) != 0)
1975  {
1976  READTUP(state, stup, state->result_tape, tuplen);
1977 
1978  /*
1979  * Remember the tuple we return, so that we can recycle
1980  * its memory on next call. (This can be NULL, in the
1981  * !state->tuples case).
1982  */
1983  state->lastReturnedTuple = stup->tuple;
1984 
1985  return true;
1986  }
1987  else
1988  {
1989  state->eof_reached = true;
1990  return false;
1991  }
1992  }
1993 
1994  /*
1995  * Backward.
1996  *
1997  * if all tuples are fetched already then we return last tuple,
1998  * else - tuple before last returned.
1999  */
2000  if (state->eof_reached)
2001  {
2002  /*
2003  * Seek position is pointing just past the zero tuplen at the
2004  * end of file; back up to fetch last tuple's ending length
2005  * word. If seek fails we must have a completely empty file.
2006  */
2007  nmoved = LogicalTapeBackspace(state->tapeset,
2008  state->result_tape,
2009  2 * sizeof(unsigned int));
2010  if (nmoved == 0)
2011  return false;
2012  else if (nmoved != 2 * sizeof(unsigned int))
2013  elog(ERROR, "unexpected tape position");
2014  state->eof_reached = false;
2015  }
2016  else
2017  {
2018  /*
2019  * Back up and fetch previously-returned tuple's ending length
2020  * word. If seek fails, assume we are at start of file.
2021  */
2022  nmoved = LogicalTapeBackspace(state->tapeset,
2023  state->result_tape,
2024  sizeof(unsigned int));
2025  if (nmoved == 0)
2026  return false;
2027  else if (nmoved != sizeof(unsigned int))
2028  elog(ERROR, "unexpected tape position");
2029  tuplen = getlen(state, state->result_tape, false);
2030 
2031  /*
2032  * Back up to get ending length word of tuple before it.
2033  */
2034  nmoved = LogicalTapeBackspace(state->tapeset,
2035  state->result_tape,
2036  tuplen + 2 * sizeof(unsigned int));
2037  if (nmoved == tuplen + sizeof(unsigned int))
2038  {
2039  /*
2040  * We backed up over the previous tuple, but there was no
2041  * ending length word before it. That means that the prev
2042  * tuple is the first tuple in the file. It is now the
2043  * next to read in forward direction (not obviously right,
2044  * but that is what in-memory case does).
2045  */
2046  return false;
2047  }
2048  else if (nmoved != tuplen + 2 * sizeof(unsigned int))
2049  elog(ERROR, "bogus tuple length in backward scan");
2050  }
2051 
2052  tuplen = getlen(state, state->result_tape, false);
2053 
2054  /*
2055  * Now we have the length of the prior tuple, back up and read it.
2056  * Note: READTUP expects we are positioned after the initial
2057  * length word of the tuple, so back up to that point.
2058  */
2059  nmoved = LogicalTapeBackspace(state->tapeset,
2060  state->result_tape,
2061  tuplen);
2062  if (nmoved != tuplen)
2063  elog(ERROR, "bogus tuple length in backward scan");
2064  READTUP(state, stup, state->result_tape, tuplen);
2065 
2066  /*
2067  * Remember the tuple we return, so that we can recycle its memory
2068  * on next call. (This can be NULL, in the Datum case).
2069  */
2070  state->lastReturnedTuple = stup->tuple;
2071 
2072  return true;
2073 
2074  case TSS_FINALMERGE:
2075  Assert(forward);
2076  /* We are managing memory ourselves, with the slab allocator. */
2077  Assert(state->slabAllocatorUsed);
2078 
2079  /*
2080  * The slab slot holding the tuple that we returned in previous
2081  * gettuple call can now be reused.
2082  */
2083  if (state->lastReturnedTuple)
2084  {
2085  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
2086  state->lastReturnedTuple = NULL;
2087  }
2088 
2089  /*
2090  * This code should match the inner loop of mergeonerun().
2091  */
2092  if (state->memtupcount > 0)
2093  {
2094  int srcTape = state->memtuples[0].srctape;
2095  SortTuple newtup;
2096 
2097  *stup = state->memtuples[0];
2098 
2099  /*
2100  * Remember the tuple we return, so that we can recycle its
2101  * memory on next call. (This can be NULL, in the Datum case).
2102  */
2103  state->lastReturnedTuple = stup->tuple;
2104 
2105  /*
2106  * Pull next tuple from tape, and replace the returned tuple
2107  * at top of the heap with it.
2108  */
2109  if (!mergereadnext(state, srcTape, &newtup))
2110  {
2111  /*
2112  * If no more data, we've reached end of run on this tape.
2113  * Remove the top node from the heap.
2114  */
2116 
2117  /*
2118  * Rewind to free the read buffer. It'd go away at the
2119  * end of the sort anyway, but better to release the
2120  * memory early.
2121  */
2122  LogicalTapeRewindForWrite(state->tapeset, srcTape);
2123  return true;
2124  }
2125  newtup.srctape = srcTape;
2126  tuplesort_heap_replace_top(state, &newtup);
2127  return true;
2128  }
2129  return false;
2130 
2131  default:
2132  elog(ERROR, "invalid tuplesort state");
2133  return false; /* keep compiler quiet */
2134  }
2135 }
TupSortStatus status
Definition: tuplesort.c:232
bool randomAccess
Definition: tuplesort.c:234
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:796
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3453
void * tuple
Definition: tuplesort.c:169
#define ERROR
Definition: elog.h:43
void * lastReturnedTuple
Definition: tuplesort.c:340
size_t LogicalTapeBackspace(LogicalTapeSet *lts, int tapenum, size_t size)
Definition: logtape.c:960
LogicalTapeSet * tapeset
Definition: tuplesort.c:246
#define WORKER(state)
Definition: tuplesort.c:531
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:526
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:511
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3371
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2899
#define Assert(condition)
Definition: c.h:732
int srctape
Definition: tuplesort.c:172
bool eof_reached
Definition: tuplesort.c:380
bool slabAllocatorUsed
Definition: tuplesort.c:325
#define elog(elevel,...)
Definition: elog.h:226
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3395
SortTuple * memtuples
Definition: tuplesort.c:293

◆ tuplesort_gettupleslot()