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 "lib/sort_template.h"
Include dependency graph for tuplesort.c:

Go to the source code of this file.

Data Structures

struct  SortTuple
 
union  SlabSlot
 
struct  Tuplesortstate
 
struct  Sharedsort
 

Macros

#define HEAP_SORT   0
 
#define INDEX_SORT   1
 
#define DATUM_SORT   2
 
#define CLUSTER_SORT   3
 
#define PARALLEL_SORT(state)
 
#define INITIAL_MEMTUPSIZE
 
#define SLAB_SLOT_SIZE   1024
 
#define MINORDER   6 /* minimum merge order */
 
#define MAXORDER   500 /* maximum merge order */
 
#define TAPE_BUFFER_OVERHEAD   BLCKSZ
 
#define MERGE_BUFFER_SIZE   (BLCKSZ * 32)
 
#define IS_SLAB_SLOT(state, tuple)
 
#define RELEASE_SLAB_SLOT(state, tuple)
 
#define COMPARETUP(state, a, b)   ((*(state)->comparetup) (a, b, state))
 
#define COPYTUP(state, stup, tup)   ((*(state)->copytup) (state, stup, tup))
 
#define WRITETUP(state, tape, stup)   ((*(state)->writetup) (state, tape, stup))
 
#define READTUP(state, stup, tape, len)   ((*(state)->readtup) (state, stup, tape, len))
 
#define LACKMEM(state)   ((state)->availMem < 0 && !(state)->slabAllocatorUsed)
 
#define USEMEM(state, amt)   ((state)->availMem -= (amt))
 
#define FREEMEM(state, amt)   ((state)->availMem += (amt))
 
#define SERIAL(state)   ((state)->shared == NULL)
 
#define WORKER(state)   ((state)->shared && (state)->worker != -1)
 
#define LEADER(state)   ((state)->shared && (state)->worker == -1)
 
#define LogicalTapeReadExact(tape, ptr, len)
 
#define ST_SORT   qsort_tuple_unsigned
 
#define ST_ELEMENT_TYPE   SortTuple
 
#define ST_COMPARE(a, b, state)   qsort_tuple_unsigned_compare(a, b, state)
 
#define ST_COMPARE_ARG_TYPE   Tuplesortstate
 
#define ST_CHECK_FOR_INTERRUPTS
 
#define ST_SCOPE   static
 
#define ST_DEFINE
 
#define ST_SORT   qsort_tuple_int32
 
#define ST_ELEMENT_TYPE   SortTuple
 
#define ST_COMPARE(a, b, state)   qsort_tuple_int32_compare(a, b, state)
 
#define ST_COMPARE_ARG_TYPE   Tuplesortstate
 
#define ST_CHECK_FOR_INTERRUPTS
 
#define ST_SCOPE   static
 
#define ST_DEFINE
 
#define ST_SORT   qsort_tuple
 
#define ST_ELEMENT_TYPE   SortTuple
 
#define ST_COMPARE_RUNTIME_POINTER
 
#define ST_COMPARE_ARG_TYPE   Tuplesortstate
 
#define ST_CHECK_FOR_INTERRUPTS
 
#define ST_SCOPE   static
 
#define ST_DECLARE
 
#define ST_DEFINE
 
#define ST_SORT   qsort_ssup
 
#define ST_ELEMENT_TYPE   SortTuple
 
#define ST_COMPARE(a, b, ssup)
 
#define ST_COMPARE_ARG_TYPE   SortSupportData
 
#define ST_CHECK_FOR_INTERRUPTS
 
#define ST_SCOPE   static
 
#define ST_DEFINE
 

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, int sortopt)
 
static void tuplesort_begin_batch (Tuplesortstate *state)
 
static void puttuple_common (Tuplesortstate *state, SortTuple *tuple)
 
static bool consider_abort_common (Tuplesortstate *state)
 
static void inittapes (Tuplesortstate *state, bool mergeruns)
 
static void inittapestate (Tuplesortstate *state, int maxTapes)
 
static void selectnewtape (Tuplesortstate *state)
 
static void init_slab_allocator (Tuplesortstate *state, int numSlots)
 
static void mergeruns (Tuplesortstate *state)
 
static void mergeonerun (Tuplesortstate *state)
 
static void beginmerge (Tuplesortstate *state)
 
static bool mergereadnext (Tuplesortstate *state, LogicalTape *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 (LogicalTape *tape, bool eofOK)
 
static void markrunend (LogicalTape *tape)
 
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, LogicalTape *tape, SortTuple *stup)
 
static void readtup_heap (Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, 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, LogicalTape *tape, SortTuple *stup)
 
static void readtup_cluster (Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, 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, LogicalTape *tape, SortTuple *stup)
 
static void readtup_index (Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, 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, LogicalTape *tape, SortTuple *stup)
 
static void readtup_datum (Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
 
static int worker_get_identifier (Tuplesortstate *state)
 
static void worker_freeze_result_tape (Tuplesortstate *state)
 
static void worker_nomergeruns (Tuplesortstate *state)
 
static void leader_takeover_tapes (Tuplesortstate *state)
 
static void free_sort_tuple (Tuplesortstate *state, SortTuple *stup)
 
static void tuplesort_free (Tuplesortstate *state)
 
static void tuplesort_updatemax (Tuplesortstate *state)
 
static pg_attribute_always_inline int qsort_tuple_unsigned_compare (SortTuple *a, SortTuple *b, Tuplesortstate *state)
 
static pg_attribute_always_inline int qsort_tuple_int32_compare (SortTuple *a, SortTuple *b, Tuplesortstate *state)
 
Tuplesortstatetuplesort_begin_heap (TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, bool uniqueNullsNotDistinct, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_index_gist (Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
 
Tuplesortstatetuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, int sortopt)
 
void tuplesort_set_bound (Tuplesortstate *state, int64 bound)
 
bool tuplesort_used_bound (Tuplesortstate *state)
 
void tuplesort_end (Tuplesortstate *state)
 
void tuplesort_reset (Tuplesortstate *state)
 
static bool grow_memtuples (Tuplesortstate *state)
 
void tuplesort_puttupleslot (Tuplesortstate *state, TupleTableSlot *slot)
 
void tuplesort_putheaptuple (Tuplesortstate *state, HeapTuple tup)
 
void tuplesort_putindextuplevalues (Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
 
void tuplesort_putdatum (Tuplesortstate *state, Datum val, bool isNull)
 
void tuplesort_performsort (Tuplesortstate *state)
 
static bool tuplesort_gettuple_common (Tuplesortstate *state, bool forward, SortTuple *stup)
 
bool tuplesort_gettupleslot (Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
 
HeapTuple tuplesort_getheaptuple (Tuplesortstate *state, bool forward)
 
IndexTuple tuplesort_getindextuple (Tuplesortstate *state, bool forward)
 
bool tuplesort_getdatum (Tuplesortstate *state, bool forward, Datum *val, bool *isNull, Datum *abbrev)
 
bool tuplesort_skiptuples (Tuplesortstate *state, int64 ntuples, bool forward)
 
int tuplesort_merge_order (int64 allowedMem)
 
static int64 merge_read_buffer_size (int64 avail_mem, int nInputTapes, int nInputRuns, int maxOutputTapes)
 
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)
 
int ssup_datum_unsigned_cmp (Datum x, Datum y, SortSupport ssup)
 
int ssup_datum_int32_cmp (Datum x, Datum y, SortSupport ssup)
 

Variables

bool trace_sort = false
 

Macro Definition Documentation

◆ CLUSTER_SORT

#define CLUSTER_SORT   3

Definition at line 126 of file tuplesort.c.

◆ COMPARETUP

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

Definition at line 551 of file tuplesort.c.

◆ COPYTUP

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

Definition at line 552 of file tuplesort.c.

◆ DATUM_SORT

#define DATUM_SORT   2

Definition at line 125 of file tuplesort.c.

◆ FREEMEM

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

Definition at line 557 of file tuplesort.c.

◆ HEAP_SORT

#define HEAP_SORT   0

Definition at line 123 of file tuplesort.c.

◆ INDEX_SORT

#define INDEX_SORT   1

Definition at line 124 of file tuplesort.c.

◆ INITIAL_MEMTUPSIZE

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

Definition at line 139 of file tuplesort.c.

◆ IS_SLAB_SLOT

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

Definition at line 531 of file tuplesort.c.

◆ LACKMEM

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

Definition at line 555 of file tuplesort.c.

◆ LEADER

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

Definition at line 560 of file tuplesort.c.

◆ LogicalTapeReadExact

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

Definition at line 612 of file tuplesort.c.

◆ MAXORDER

#define MAXORDER   500 /* maximum merge order */

Definition at line 235 of file tuplesort.c.

◆ MERGE_BUFFER_SIZE

#define MERGE_BUFFER_SIZE   (BLCKSZ * 32)

Definition at line 237 of file tuplesort.c.

◆ MINORDER

#define MINORDER   6 /* minimum merge order */

Definition at line 234 of file tuplesort.c.

◆ PARALLEL_SORT

#define PARALLEL_SORT (   state)
Value:
((state)->shared == NULL ? 0 : \
(state)->worker >= 0 ? 1 : 2)

Definition at line 129 of file tuplesort.c.

◆ READTUP

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

Definition at line 554 of file tuplesort.c.

◆ RELEASE_SLAB_SLOT

#define RELEASE_SLAB_SLOT (   state,
  tuple 
)
Value:
do { \
SlabSlot *buf = (SlabSlot *) tuple; \
{ \
buf->nextfree = (state)->slabFreeHead; \
(state)->slabFreeHead = buf; \
} while(0)
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
void pfree(void *pointer)
Definition: mcxt.c:1175
static char * buf
Definition: pg_test_fsync.c:67
#define IS_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:531

Definition at line 539 of file tuplesort.c.

◆ SERIAL

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

Definition at line 558 of file tuplesort.c.

◆ SLAB_SLOT_SIZE

#define SLAB_SLOT_SIZE   1024

Definition at line 200 of file tuplesort.c.

◆ ST_CHECK_FOR_INTERRUPTS [1/4]

#define ST_CHECK_FOR_INTERRUPTS

Definition at line 820 of file tuplesort.c.

◆ ST_CHECK_FOR_INTERRUPTS [2/4]

#define ST_CHECK_FOR_INTERRUPTS

Definition at line 820 of file tuplesort.c.

◆ ST_CHECK_FOR_INTERRUPTS [3/4]

#define ST_CHECK_FOR_INTERRUPTS

Definition at line 820 of file tuplesort.c.

◆ ST_CHECK_FOR_INTERRUPTS [4/4]

#define ST_CHECK_FOR_INTERRUPTS

Definition at line 820 of file tuplesort.c.

◆ ST_COMPARE [1/3]

#define ST_COMPARE (   a,
  b,
  ssup 
)
Value:
ApplySortComparator((a)->datum1, (a)->isnull1, \
(b)->datum1, (b)->isnull1, (ssup))
int b
Definition: isn.c:70
int a
Definition: isn.c:69
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200

Definition at line 816 of file tuplesort.c.

◆ ST_COMPARE [2/3]

#define ST_COMPARE (   a,
  b,
  state 
)    qsort_tuple_unsigned_compare(a, b, state)

Definition at line 816 of file tuplesort.c.

◆ ST_COMPARE [3/3]

#define ST_COMPARE (   a,
  b,
  state 
)    qsort_tuple_int32_compare(a, b, state)

Definition at line 816 of file tuplesort.c.

◆ ST_COMPARE_ARG_TYPE [1/4]

#define ST_COMPARE_ARG_TYPE   Tuplesortstate

Definition at line 819 of file tuplesort.c.

◆ ST_COMPARE_ARG_TYPE [2/4]

#define ST_COMPARE_ARG_TYPE   Tuplesortstate

Definition at line 819 of file tuplesort.c.

◆ ST_COMPARE_ARG_TYPE [3/4]

#define ST_COMPARE_ARG_TYPE   Tuplesortstate

Definition at line 819 of file tuplesort.c.

◆ ST_COMPARE_ARG_TYPE [4/4]

#define ST_COMPARE_ARG_TYPE   SortSupportData

Definition at line 819 of file tuplesort.c.

◆ ST_COMPARE_RUNTIME_POINTER

#define ST_COMPARE_RUNTIME_POINTER

Definition at line 806 of file tuplesort.c.

◆ ST_DECLARE

#define ST_DECLARE

Definition at line 810 of file tuplesort.c.

◆ ST_DEFINE [1/4]

#define ST_DEFINE

Definition at line 822 of file tuplesort.c.

◆ ST_DEFINE [2/4]

#define ST_DEFINE

Definition at line 822 of file tuplesort.c.

◆ ST_DEFINE [3/4]

#define ST_DEFINE

Definition at line 822 of file tuplesort.c.

◆ ST_DEFINE [4/4]

#define ST_DEFINE

Definition at line 822 of file tuplesort.c.

◆ ST_ELEMENT_TYPE [1/4]

#define ST_ELEMENT_TYPE   SortTuple

Definition at line 815 of file tuplesort.c.

◆ ST_ELEMENT_TYPE [2/4]

#define ST_ELEMENT_TYPE   SortTuple

Definition at line 815 of file tuplesort.c.

◆ ST_ELEMENT_TYPE [3/4]

#define ST_ELEMENT_TYPE   SortTuple

Definition at line 815 of file tuplesort.c.

◆ ST_ELEMENT_TYPE [4/4]

#define ST_ELEMENT_TYPE   SortTuple

Definition at line 815 of file tuplesort.c.

◆ ST_SCOPE [1/4]

#define ST_SCOPE   static

Definition at line 821 of file tuplesort.c.

◆ ST_SCOPE [2/4]

#define ST_SCOPE   static

Definition at line 821 of file tuplesort.c.

◆ ST_SCOPE [3/4]

#define ST_SCOPE   static

Definition at line 821 of file tuplesort.c.

◆ ST_SCOPE [4/4]

#define ST_SCOPE   static

Definition at line 821 of file tuplesort.c.

◆ ST_SORT [1/4]

#define ST_SORT   qsort_tuple_unsigned

Definition at line 814 of file tuplesort.c.

◆ ST_SORT [2/4]

#define ST_SORT   qsort_tuple_int32

Definition at line 814 of file tuplesort.c.

◆ ST_SORT [3/4]

#define ST_SORT   qsort_tuple

Definition at line 814 of file tuplesort.c.

◆ ST_SORT [4/4]

#define ST_SORT   qsort_ssup

Definition at line 814 of file tuplesort.c.

◆ TAPE_BUFFER_OVERHEAD

#define TAPE_BUFFER_OVERHEAD   BLCKSZ

Definition at line 236 of file tuplesort.c.

◆ USEMEM

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

Definition at line 556 of file tuplesort.c.

◆ WORKER

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

Definition at line 559 of file tuplesort.c.

◆ WRITETUP

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

Definition at line 553 of file tuplesort.c.

Typedef Documentation

◆ SlabSlot

typedef union SlabSlot SlabSlot

◆ SortTupleComparator

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

Definition at line 239 of file tuplesort.c.

Enumeration Type Documentation

◆ TupSortStatus

Enumerator
TSS_INITIAL 
TSS_BOUNDED 
TSS_BUILDRUNS 
TSS_SORTEDINMEM 
TSS_SORTEDONTAPE 
TSS_FINALMERGE 

Definition at line 212 of file tuplesort.c.

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

Function Documentation

◆ beginmerge()

static void beginmerge ( Tuplesortstate state)
static

Definition at line 3241 of file tuplesort.c.

3242 {
3243  int activeTapes;
3244  int srcTapeIndex;
3245 
3246  /* Heap should be empty here */
3247  Assert(state->memtupcount == 0);
3248 
3249  activeTapes = Min(state->nInputTapes, state->nInputRuns);
3250 
3251  for (srcTapeIndex = 0; srcTapeIndex < activeTapes; srcTapeIndex++)
3252  {
3253  SortTuple tup;
3254 
3255  if (mergereadnext(state, state->inputTapes[srcTapeIndex], &tup))
3256  {
3257  tup.srctape = srcTapeIndex;
3259  }
3260  }
3261 }
#define Min(x, y)
Definition: c.h:997
Assert(fmt[strlen(fmt) - 1] !='\n')
int srctape
Definition: tuplesort.c:186
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3716
static bool mergereadnext(Tuplesortstate *state, LogicalTape *srcTape, SortTuple *stup)
Definition: tuplesort.c:3269

References Assert(), mergereadnext(), Min, SortTuple::srctape, and tuplesort_heap_insert().

Referenced by mergeonerun(), and mergeruns().

◆ comparetup_cluster()

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

Definition at line 4084 of file tuplesort.c.

4086 {
4087  SortSupport sortKey = state->sortKeys;
4088  HeapTuple ltup;
4089  HeapTuple rtup;
4090  TupleDesc tupDesc;
4091  int nkey;
4092  int32 compare;
4093  Datum datum1,
4094  datum2;
4095  bool isnull1,
4096  isnull2;
4097 
4098  /* Be prepared to compare additional sort keys */
4099  ltup = (HeapTuple) a->tuple;
4100  rtup = (HeapTuple) b->tuple;
4101  tupDesc = state->tupDesc;
4102 
4103  /* Compare the leading sort key, if it's simple */
4104  if (state->haveDatum1)
4105  {
4106  compare = ApplySortComparator(a->datum1, a->isnull1,
4107  b->datum1, b->isnull1,
4108  sortKey);
4109  if (compare != 0)
4110  return compare;
4111 
4112  if (sortKey->abbrev_converter)
4113  {
4114  AttrNumber leading = state->indexInfo->ii_IndexAttrNumbers[0];
4115 
4116  datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
4117  datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
4118 
4119  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
4120  datum2, isnull2,
4121  sortKey);
4122  }
4123  if (compare != 0 || state->nKeys == 1)
4124  return compare;
4125  /* Compare additional columns the hard way */
4126  sortKey++;
4127  nkey = 1;
4128  }
4129  else
4130  {
4131  /* Must compare all keys the hard way */
4132  nkey = 0;
4133  }
4134 
4135  if (state->indexInfo->ii_Expressions == NULL)
4136  {
4137  /* If not expression index, just compare the proper heap attrs */
4138 
4139  for (; nkey < state->nKeys; nkey++, sortKey++)
4140  {
4141  AttrNumber attno = state->indexInfo->ii_IndexAttrNumbers[nkey];
4142 
4143  datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
4144  datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
4145 
4146  compare = ApplySortComparator(datum1, isnull1,
4147  datum2, isnull2,
4148  sortKey);
4149  if (compare != 0)
4150  return compare;
4151  }
4152  }
4153  else
4154  {
4155  /*
4156  * In the expression index case, compute the whole index tuple and
4157  * then compare values. It would perhaps be faster to compute only as
4158  * many columns as we need to compare, but that would require
4159  * duplicating all the logic in FormIndexDatum.
4160  */
4161  Datum l_index_values[INDEX_MAX_KEYS];
4162  bool l_index_isnull[INDEX_MAX_KEYS];
4163  Datum r_index_values[INDEX_MAX_KEYS];
4164  bool r_index_isnull[INDEX_MAX_KEYS];
4165  TupleTableSlot *ecxt_scantuple;
4166 
4167  /* Reset context each time to prevent memory leakage */
4169 
4170  ecxt_scantuple = GetPerTupleExprContext(state->estate)->ecxt_scantuple;
4171 
4172  ExecStoreHeapTuple(ltup, ecxt_scantuple, false);
4173  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
4174  l_index_values, l_index_isnull);
4175 
4176  ExecStoreHeapTuple(rtup, ecxt_scantuple, false);
4177  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
4178  r_index_values, r_index_isnull);
4179 
4180  for (; nkey < state->nKeys; nkey++, sortKey++)
4181  {
4182  compare = ApplySortComparator(l_index_values[nkey],
4183  l_index_isnull[nkey],
4184  r_index_values[nkey],
4185  r_index_isnull[nkey],
4186  sortKey);
4187  if (compare != 0)
4188  return compare;
4189  }
4190  }
4191 
4192  return 0;
4193 }
int16 AttrNumber
Definition: attnum.h:21
signed int int32
Definition: c.h:440
TupleTableSlot * ExecStoreHeapTuple(HeapTuple tuple, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1352
#define ResetPerTupleExprContext(estate)
Definition: executor.h:546
#define GetPerTupleExprContext(estate)
Definition: executor.h:537
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
HeapTupleData * HeapTuple
Definition: htup.h:71
static Datum heap_getattr(HeapTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: htup_details.h:788
void FormIndexDatum(IndexInfo *indexInfo, TupleTableSlot *slot, EState *estate, Datum *values, bool *isnull)
Definition: index.c:2707
#define INDEX_MAX_KEYS
uintptr_t Datum
Definition: postgres.h:411
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:341
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172

References a, SortSupportData::abbrev_converter, ApplySortAbbrevFullComparator(), ApplySortComparator(), b, compare(), ExecStoreHeapTuple(), FormIndexDatum(), GetPerTupleExprContext, heap_getattr(), INDEX_MAX_KEYS, and ResetPerTupleExprContext.

Referenced by tuplesort_begin_cluster().

◆ comparetup_datum()

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

Definition at line 4565 of file tuplesort.c.

4566 {
4567  int compare;
4568 
4569  compare = ApplySortComparator(a->datum1, a->isnull1,
4570  b->datum1, b->isnull1,
4571  state->sortKeys);
4572  if (compare != 0)
4573  return compare;
4574 
4575  /* if we have abbreviations, then "tuple" has the original value */
4576 
4577  if (state->sortKeys->abbrev_converter)
4579  PointerGetDatum(b->tuple), b->isnull1,
4580  state->sortKeys);
4581 
4582  return compare;
4583 }
#define PointerGetDatum(X)
Definition: postgres.h:600

References a, ApplySortAbbrevFullComparator(), ApplySortComparator(), b, compare(), and PointerGetDatum.

Referenced by tuplesort_begin_datum().

◆ comparetup_heap()

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

Definition at line 3888 of file tuplesort.c.

3889 {
3890  SortSupport sortKey = state->sortKeys;
3891  HeapTupleData ltup;
3892  HeapTupleData rtup;
3893  TupleDesc tupDesc;
3894  int nkey;
3895  int32 compare;
3896  AttrNumber attno;
3897  Datum datum1,
3898  datum2;
3899  bool isnull1,
3900  isnull2;
3901 
3902 
3903  /* Compare the leading sort key */
3904  compare = ApplySortComparator(a->datum1, a->isnull1,
3905  b->datum1, b->isnull1,
3906  sortKey);
3907  if (compare != 0)
3908  return compare;
3909 
3910  /* Compare additional sort keys */
3911  ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3912  ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
3913  rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3914  rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
3915  tupDesc = state->tupDesc;
3916 
3917  if (sortKey->abbrev_converter)
3918  {
3919  attno = sortKey->ssup_attno;
3920 
3921  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3922  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3923 
3924  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3925  datum2, isnull2,
3926  sortKey);
3927  if (compare != 0)
3928  return compare;
3929  }
3930 
3931  sortKey++;
3932  for (nkey = 1; nkey < state->nKeys; nkey++, sortKey++)
3933  {
3934  attno = sortKey->ssup_attno;
3935 
3936  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3937  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3938 
3939  compare = ApplySortComparator(datum1, isnull1,
3940  datum2, isnull2,
3941  sortKey);
3942  if (compare != 0)
3943  return compare;
3944  }
3945 
3946  return 0;
3947 }
MinimalTupleData * MinimalTuple
Definition: htup.h:27
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:613
uint32 t_len
Definition: htup.h:64
HeapTupleHeader t_data
Definition: htup.h:68
AttrNumber ssup_attno
Definition: sortsupport.h:81

References a, SortSupportData::abbrev_converter, ApplySortAbbrevFullComparator(), ApplySortComparator(), b, compare(), heap_getattr(), MINIMAL_TUPLE_OFFSET, SortSupportData::ssup_attno, HeapTupleData::t_data, and HeapTupleData::t_len.

Referenced by tuplesort_begin_heap().

◆ comparetup_index_btree()

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

Definition at line 4326 of file tuplesort.c.

4328 {
4329  /*
4330  * This is similar to comparetup_heap(), but expects index tuples. There
4331  * is also special handling for enforcing uniqueness, and special
4332  * treatment for equal keys at the end.
4333  */
4334  SortSupport sortKey = state->sortKeys;
4335  IndexTuple tuple1;
4336  IndexTuple tuple2;
4337  int keysz;
4338  TupleDesc tupDes;
4339  bool equal_hasnull = false;
4340  int nkey;
4341  int32 compare;
4342  Datum datum1,
4343  datum2;
4344  bool isnull1,
4345  isnull2;
4346 
4347 
4348  /* Compare the leading sort key */
4349  compare = ApplySortComparator(a->datum1, a->isnull1,
4350  b->datum1, b->isnull1,
4351  sortKey);
4352  if (compare != 0)
4353  return compare;
4354 
4355  /* Compare additional sort keys */
4356  tuple1 = (IndexTuple) a->tuple;
4357  tuple2 = (IndexTuple) b->tuple;
4358  keysz = state->nKeys;
4359  tupDes = RelationGetDescr(state->indexRel);
4360 
4361  if (sortKey->abbrev_converter)
4362  {
4363  datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
4364  datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
4365 
4366  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
4367  datum2, isnull2,
4368  sortKey);
4369  if (compare != 0)
4370  return compare;
4371  }
4372 
4373  /* they are equal, so we only need to examine one null flag */
4374  if (a->isnull1)
4375  equal_hasnull = true;
4376 
4377  sortKey++;
4378  for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
4379  {
4380  datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
4381  datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
4382 
4383  compare = ApplySortComparator(datum1, isnull1,
4384  datum2, isnull2,
4385  sortKey);
4386  if (compare != 0)
4387  return compare; /* done when we find unequal attributes */
4388 
4389  /* they are equal, so we only need to examine one null flag */
4390  if (isnull1)
4391  equal_hasnull = true;
4392  }
4393 
4394  /*
4395  * If btree has asked us to enforce uniqueness, complain if two equal
4396  * tuples are detected (unless there was at least one NULL field and NULLS
4397  * NOT DISTINCT was not set).
4398  *
4399  * It is sufficient to make the test here, because if two tuples are equal
4400  * they *must* get compared at some stage of the sort --- otherwise the
4401  * sort algorithm wouldn't have checked whether one must appear before the
4402  * other.
4403  */
4404  if (state->enforceUnique && !(!state->uniqueNullsNotDistinct && equal_hasnull))
4405  {
4407  bool isnull[INDEX_MAX_KEYS];
4408  char *key_desc;
4409 
4410  /*
4411  * Some rather brain-dead implementations of qsort (such as the one in
4412  * QNX 4) will sometimes call the comparison routine to compare a
4413  * value to itself, but we always use our own implementation, which
4414  * does not.
4415  */
4416  Assert(tuple1 != tuple2);
4417 
4418  index_deform_tuple(tuple1, tupDes, values, isnull);
4419 
4420  key_desc = BuildIndexValueDescription(state->indexRel, values, isnull);
4421 
4422  ereport(ERROR,
4423  (errcode(ERRCODE_UNIQUE_VIOLATION),
4424  errmsg("could not create unique index \"%s\"",
4425  RelationGetRelationName(state->indexRel)),
4426  key_desc ? errdetail("Key %s is duplicated.", key_desc) :
4427  errdetail("Duplicate keys exist."),
4428  errtableconstraint(state->heapRel,
4429  RelationGetRelationName(state->indexRel))));
4430  }
4431 
4432  /*
4433  * If key values are equal, we sort on ItemPointer. This is required for
4434  * btree indexes, since heap TID is treated as an implicit last key
4435  * attribute in order to ensure that all keys in the index are physically
4436  * unique.
4437  */
4438  {
4439  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4440  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4441 
4442  if (blk1 != blk2)
4443  return (blk1 < blk2) ? -1 : 1;
4444  }
4445  {
4448 
4449  if (pos1 != pos2)
4450  return (pos1 < pos2) ? -1 : 1;
4451  }
4452 
4453  /* ItemPointer values should never be equal */
4454  Assert(false);
4455 
4456  return 0;
4457 }
uint32 BlockNumber
Definition: block.h:31
static Datum values[MAXATTR]
Definition: bootstrap.c:156
int errdetail(const char *fmt,...)
Definition: elog.c:1037
int errcode(int sqlerrcode)
Definition: elog.c:693
int errmsg(const char *fmt,...)
Definition: elog.c:904
#define ereport(elevel,...)
Definition: elog.h:143
char * BuildIndexValueDescription(Relation indexRelation, Datum *values, bool *isnull)
Definition: genam.c:177
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:437
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:99
IndexTupleData * IndexTuple
Definition: itup.h:53
uint16 OffsetNumber
Definition: off.h:24
#define RelationGetDescr(relation)
Definition: rel.h:514
#define RelationGetRelationName(relation)
Definition: rel.h:522
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5867
ItemPointerData t_tid
Definition: itup.h:37

References a, SortSupportData::abbrev_converter, ApplySortAbbrevFullComparator(), ApplySortComparator(), Assert(), b, BuildIndexValueDescription(), compare(), ereport, errcode(), errdetail(), errmsg(), ERROR, errtableconstraint(), index_deform_tuple(), index_getattr, INDEX_MAX_KEYS, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, RelationGetDescr, RelationGetRelationName, IndexTupleData::t_tid, and values.

Referenced by tuplesort_begin_index_btree(), and tuplesort_begin_index_gist().

◆ comparetup_index_hash()

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

Definition at line 4460 of file tuplesort.c.

4462 {
4463  Bucket bucket1;
4464  Bucket bucket2;
4465  IndexTuple tuple1;
4466  IndexTuple tuple2;
4467 
4468  /*
4469  * Fetch hash keys and mask off bits we don't want to sort by. We know
4470  * that the first column of the index tuple is the hash key.
4471  */
4472  Assert(!a->isnull1);
4473  bucket1 = _hash_hashkey2bucket(DatumGetUInt32(a->datum1),
4474  state->max_buckets, state->high_mask,
4475  state->low_mask);
4476  Assert(!b->isnull1);
4477  bucket2 = _hash_hashkey2bucket(DatumGetUInt32(b->datum1),
4478  state->max_buckets, state->high_mask,
4479  state->low_mask);
4480  if (bucket1 > bucket2)
4481  return 1;
4482  else if (bucket1 < bucket2)
4483  return -1;
4484 
4485  /*
4486  * If hash values are equal, we sort on ItemPointer. This does not affect
4487  * validity of the finished index, but it may be useful to have index
4488  * scans in physical order.
4489  */
4490  tuple1 = (IndexTuple) a->tuple;
4491  tuple2 = (IndexTuple) b->tuple;
4492 
4493  {
4494  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4495  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4496 
4497  if (blk1 != blk2)
4498  return (blk1 < blk2) ? -1 : 1;
4499  }
4500  {
4503 
4504  if (pos1 != pos2)
4505  return (pos1 < pos2) ? -1 : 1;
4506  }
4507 
4508  /* ItemPointer values should never be equal */
4509  Assert(false);
4510 
4511  return 0;
4512 }
uint32 Bucket
Definition: hash.h:35
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:126
#define DatumGetUInt32(X)
Definition: postgres.h:530

References _hash_hashkey2bucket(), a, Assert(), b, DatumGetUInt32, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, and IndexTupleData::t_tid.

Referenced by tuplesort_begin_index_hash().

◆ consider_abort_common()

static bool consider_abort_common ( Tuplesortstate state)
static

Definition at line 2152 of file tuplesort.c.

2153 {
2154  Assert(state->sortKeys[0].abbrev_converter != NULL);
2155  Assert(state->sortKeys[0].abbrev_abort != NULL);
2156  Assert(state->sortKeys[0].abbrev_full_comparator != NULL);
2157 
2158  /*
2159  * Check effectiveness of abbreviation optimization. Consider aborting
2160  * when still within memory limit.
2161  */
2162  if (state->status == TSS_INITIAL &&
2163  state->memtupcount >= state->abbrevNext)
2164  {
2165  state->abbrevNext *= 2;
2166 
2167  /*
2168  * Check opclass-supplied abbreviation abort routine. It may indicate
2169  * that abbreviation should not proceed.
2170  */
2171  if (!state->sortKeys->abbrev_abort(state->memtupcount,
2172  state->sortKeys))
2173  return false;
2174 
2175  /*
2176  * Finally, restore authoritative comparator, and indicate that
2177  * abbreviation is not in play by setting abbrev_converter to NULL
2178  */
2179  state->sortKeys[0].comparator = state->sortKeys[0].abbrev_full_comparator;
2180  state->sortKeys[0].abbrev_converter = NULL;
2181  /* Not strictly necessary, but be tidy */
2182  state->sortKeys[0].abbrev_abort = NULL;
2183  state->sortKeys[0].abbrev_full_comparator = NULL;
2184 
2185  /* Give up - expect original pass-by-value representation */
2186  return true;
2187  }
2188 
2189  return false;
2190 }

References Assert(), and TSS_INITIAL.

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

◆ copytup_cluster()

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

Definition at line 4196 of file tuplesort.c.

4197 {
4198  HeapTuple tuple = (HeapTuple) tup;
4199  Datum original;
4200  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
4201 
4202  /* copy the tuple into sort storage */
4203  tuple = heap_copytuple(tuple);
4204  stup->tuple = (void *) tuple;
4205  USEMEM(state, GetMemoryChunkSpace(tuple));
4206 
4207  MemoryContextSwitchTo(oldcontext);
4208 
4209  /*
4210  * set up first-column key value, and potentially abbreviate, if it's a
4211  * simple column
4212  */
4213  if (!state->haveDatum1)
4214  return;
4215 
4216  original = heap_getattr(tuple,
4217  state->indexInfo->ii_IndexAttrNumbers[0],
4218  state->tupDesc,
4219  &stup->isnull1);
4220 
4221  if (!state->sortKeys->abbrev_converter || stup->isnull1)
4222  {
4223  /*
4224  * Store ordinary Datum representation, or NULL value. If there is a
4225  * converter it won't expect NULL values, and cost model is not
4226  * required to account for NULL, so in that case we avoid calling
4227  * converter and just set datum1 to zeroed representation (to be
4228  * consistent, and to support cheap inequality tests for NULL
4229  * abbreviated keys).
4230  */
4231  stup->datum1 = original;
4232  }
4233  else if (!consider_abort_common(state))
4234  {
4235  /* Store abbreviated key representation */
4236  stup->datum1 = state->sortKeys->abbrev_converter(original,
4237  state->sortKeys);
4238  }
4239  else
4240  {
4241  /* Abort abbreviation */
4242  int i;
4243 
4244  stup->datum1 = original;
4245 
4246  /*
4247  * Set state to be consistent with never trying abbreviation.
4248  *
4249  * Alter datum1 representation in already-copied tuples, so as to
4250  * ensure a consistent representation (current tuple was just
4251  * handled). It does not matter if some dumped tuples are already
4252  * sorted on tape, since serialized tuples lack abbreviated keys
4253  * (TSS_BUILDRUNS state prevents control reaching here in any case).
4254  */
4255  for (i = 0; i < state->memtupcount; i++)
4256  {
4257  SortTuple *mtup = &state->memtuples[i];
4258 
4259  tuple = (HeapTuple) mtup->tuple;
4260  mtup->datum1 = heap_getattr(tuple,
4261  state->indexInfo->ii_IndexAttrNumbers[0],
4262  state->tupDesc,
4263  &mtup->isnull1);
4264  }
4265  }
4266 }
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:680
int i
Definition: isn.c:73
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:434
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
bool isnull1
Definition: tuplesort.c:185
void * tuple
Definition: tuplesort.c:183
Datum datum1
Definition: tuplesort.c:184
#define USEMEM(state, amt)
Definition: tuplesort.c:556
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:2152

References consider_abort_common(), SortTuple::datum1, GetMemoryChunkSpace(), heap_copytuple(), heap_getattr(), i, SortTuple::isnull1, MemoryContextSwitchTo(), SortTuple::tuple, and USEMEM.

Referenced by tuplesort_begin_cluster().

◆ copytup_datum()

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

Definition at line 4586 of file tuplesort.c.

4587 {
4588  /* Not currently needed */
4589  elog(ERROR, "copytup_datum() should not be called");
4590 }

References elog(), and ERROR.

Referenced by tuplesort_begin_datum().

◆ copytup_heap()

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

Definition at line 3950 of file tuplesort.c.

3951 {
3952  /*
3953  * We expect the passed "tup" to be a TupleTableSlot, and form a
3954  * MinimalTuple using the exported interface for that.
3955  */
3956  TupleTableSlot *slot = (TupleTableSlot *) tup;
3957  Datum original;
3958  MinimalTuple tuple;
3959  HeapTupleData htup;
3960  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3961 
3962  /* copy the tuple into sort storage */
3963  tuple = ExecCopySlotMinimalTuple(slot);
3964  stup->tuple = (void *) tuple;
3965  USEMEM(state, GetMemoryChunkSpace(tuple));
3966  /* set up first-column key value */
3967  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3968  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3969  original = heap_getattr(&htup,
3970  state->sortKeys[0].ssup_attno,
3971  state->tupDesc,
3972  &stup->isnull1);
3973 
3974  MemoryContextSwitchTo(oldcontext);
3975 
3976  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3977  {
3978  /*
3979  * Store ordinary Datum representation, or NULL value. If there is a
3980  * converter it won't expect NULL values, and cost model is not
3981  * required to account for NULL, so in that case we avoid calling
3982  * converter and just set datum1 to zeroed representation (to be
3983  * consistent, and to support cheap inequality tests for NULL
3984  * abbreviated keys).
3985  */
3986  stup->datum1 = original;
3987  }
3988  else if (!consider_abort_common(state))
3989  {
3990  /* Store abbreviated key representation */
3991  stup->datum1 = state->sortKeys->abbrev_converter(original,
3992  state->sortKeys);
3993  }
3994  else
3995  {
3996  /* Abort abbreviation */
3997  int i;
3998 
3999  stup->datum1 = original;
4000 
4001  /*
4002  * Set state to be consistent with never trying abbreviation.
4003  *
4004  * Alter datum1 representation in already-copied tuples, so as to
4005  * ensure a consistent representation (current tuple was just
4006  * handled). It does not matter if some dumped tuples are already
4007  * sorted on tape, since serialized tuples lack abbreviated keys
4008  * (TSS_BUILDRUNS state prevents control reaching here in any case).
4009  */
4010  for (i = 0; i < state->memtupcount; i++)
4011  {
4012  SortTuple *mtup = &state->memtuples[i];
4013 
4014  htup.t_len = ((MinimalTuple) mtup->tuple)->t_len +
4016  htup.t_data = (HeapTupleHeader) ((char *) mtup->tuple -
4018 
4019  mtup->datum1 = heap_getattr(&htup,
4020  state->sortKeys[0].ssup_attno,
4021  state->tupDesc,
4022  &mtup->isnull1);
4023  }
4024  }
4025 }
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:463

References consider_abort_common(), SortTuple::datum1, ExecCopySlotMinimalTuple(), GetMemoryChunkSpace(), heap_getattr(), i, SortTuple::isnull1, MemoryContextSwitchTo(), MINIMAL_TUPLE_OFFSET, HeapTupleData::t_data, HeapTupleData::t_len, MinimalTupleData::t_len, SortTuple::tuple, and USEMEM.

Referenced by tuplesort_begin_heap().

◆ copytup_index()

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

Definition at line 4515 of file tuplesort.c.

4516 {
4517  /* Not currently needed */
4518  elog(ERROR, "copytup_index() should not be called");
4519 }

References elog(), and ERROR.

Referenced by tuplesort_begin_index_btree(), tuplesort_begin_index_gist(), and tuplesort_begin_index_hash().

◆ dumptuples()

static void dumptuples ( Tuplesortstate state,
bool  alltuples 
)
static

Definition at line 3288 of file tuplesort.c.

3289 {
3290  int memtupwrite;
3291  int i;
3292 
3293  /*
3294  * Nothing to do if we still fit in available memory and have array slots,
3295  * unless this is the final call during initial run generation.
3296  */
3297  if (state->memtupcount < state->memtupsize && !LACKMEM(state) &&
3298  !alltuples)
3299  return;
3300 
3301  /*
3302  * Final call might require no sorting, in rare cases where we just so
3303  * happen to have previously LACKMEM()'d at the point where exactly all
3304  * remaining tuples are loaded into memory, just before input was
3305  * exhausted. In general, short final runs are quite possible, but avoid
3306  * creating a completely empty run. In a worker, though, we must produce
3307  * at least one tape, even if it's empty.
3308  */
3309  if (state->memtupcount == 0 && state->currentRun > 0)
3310  return;
3311 
3312  Assert(state->status == TSS_BUILDRUNS);
3313 
3314  /*
3315  * It seems unlikely that this limit will ever be exceeded, but take no
3316  * chances
3317  */
3318  if (state->currentRun == INT_MAX)
3319  ereport(ERROR,
3320  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
3321  errmsg("cannot have more than %d runs for an external sort",
3322  INT_MAX)));
3323 
3324  if (state->currentRun > 0)
3326 
3327  state->currentRun++;
3328 
3329 #ifdef TRACE_SORT
3330  if (trace_sort)
3331  elog(LOG, "worker %d starting quicksort of run %d: %s",
3332  state->worker, state->currentRun,
3333  pg_rusage_show(&state->ru_start));
3334 #endif
3335 
3336  /*
3337  * Sort all tuples accumulated within the allowed amount of memory for
3338  * this run using quicksort
3339  */
3341 
3342 #ifdef TRACE_SORT
3343  if (trace_sort)
3344  elog(LOG, "worker %d finished quicksort of run %d: %s",
3345  state->worker, state->currentRun,
3346  pg_rusage_show(&state->ru_start));
3347 #endif
3348 
3349  memtupwrite = state->memtupcount;
3350  for (i = 0; i < memtupwrite; i++)
3351  {
3352  WRITETUP(state, state->destTape, &state->memtuples[i]);
3353  state->memtupcount--;
3354  }
3355 
3356  /*
3357  * Reset tuple memory. We've freed all of the tuples that we previously
3358  * allocated. It's important to avoid fragmentation when there is a stark
3359  * change in the sizes of incoming tuples. Fragmentation due to
3360  * AllocSetFree's bucketing by size class might be particularly bad if
3361  * this step wasn't taken.
3362  */
3363  MemoryContextReset(state->tuplecontext);
3364 
3365  markrunend(state->destTape);
3366 
3367 #ifdef TRACE_SORT
3368  if (trace_sort)
3369  elog(LOG, "worker %d finished writing run %d to tape %d: %s",
3370  state->worker, state->currentRun, (state->currentRun - 1) % state->nOutputTapes + 1,
3371  pg_rusage_show(&state->ru_start));
3372 #endif
3373 }
#define LOG
Definition: elog.h:25
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:143
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
static void selectnewtape(Tuplesortstate *state)
Definition: tuplesort.c:2927
static void markrunend(LogicalTape *tape)
Definition: tuplesort.c:3846
#define LACKMEM(state)
Definition: tuplesort.c:555
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:553
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3653
bool trace_sort
Definition: tuplesort.c:144

References Assert(), elog(), ereport, errcode(), errmsg(), ERROR, i, LACKMEM, LOG, markrunend(), MemoryContextReset(), pg_rusage_show(), selectnewtape(), trace_sort, TSS_BUILDRUNS, tuplesort_sort_memtuples(), and WRITETUP.

Referenced by puttuple_common(), and tuplesort_performsort().

◆ free_sort_tuple()

static void free_sort_tuple ( Tuplesortstate state,
SortTuple stup 
)
static

Definition at line 4888 of file tuplesort.c.

4889 {
4890  if (stup->tuple)
4891  {
4893  pfree(stup->tuple);
4894  stup->tuple = NULL;
4895  }
4896 }
#define FREEMEM(state, amt)
Definition: tuplesort.c:557

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

Referenced by make_bounded_heap(), and puttuple_common().

◆ getlen()

static unsigned int getlen ( LogicalTape tape,
bool  eofOK 
)
static

Definition at line 3833 of file tuplesort.c.

3834 {
3835  unsigned int len;
3836 
3837  if (LogicalTapeRead(tape,
3838  &len, sizeof(len)) != sizeof(len))
3839  elog(ERROR, "unexpected end of tape");
3840  if (len == 0 && !eofOK)
3841  elog(ERROR, "unexpected end of data");
3842  return len;
3843 }

References elog(), ERROR, len, and LogicalTapeRead().

Referenced by mergereadnext(), and tuplesort_gettuple_common().

◆ grow_memtuples()

static bool grow_memtuples ( Tuplesortstate state)
static

Definition at line 1721 of file tuplesort.c.

1722 {
1723  int newmemtupsize;
1724  int memtupsize = state->memtupsize;
1725  int64 memNowUsed = state->allowedMem - state->availMem;
1726 
1727  /* Forget it if we've already maxed out memtuples, per comment above */
1728  if (!state->growmemtuples)
1729  return false;
1730 
1731  /* Select new value of memtupsize */
1732  if (memNowUsed <= state->availMem)
1733  {
1734  /*
1735  * We've used no more than half of allowedMem; double our usage,
1736  * clamping at INT_MAX tuples.
1737  */
1738  if (memtupsize < INT_MAX / 2)
1739  newmemtupsize = memtupsize * 2;
1740  else
1741  {
1742  newmemtupsize = INT_MAX;
1743  state->growmemtuples = false;
1744  }
1745  }
1746  else
1747  {
1748  /*
1749  * This will be the last increment of memtupsize. Abandon doubling
1750  * strategy and instead increase as much as we safely can.
1751  *
1752  * To stay within allowedMem, we can't increase memtupsize by more
1753  * than availMem / sizeof(SortTuple) elements. In practice, we want
1754  * to increase it by considerably less, because we need to leave some
1755  * space for the tuples to which the new array slots will refer. We
1756  * assume the new tuples will be about the same size as the tuples
1757  * we've already seen, and thus we can extrapolate from the space
1758  * consumption so far to estimate an appropriate new size for the
1759  * memtuples array. The optimal value might be higher or lower than
1760  * this estimate, but it's hard to know that in advance. We again
1761  * clamp at INT_MAX tuples.
1762  *
1763  * This calculation is safe against enlarging the array so much that
1764  * LACKMEM becomes true, because the memory currently used includes
1765  * the present array; thus, there would be enough allowedMem for the
1766  * new array elements even if no other memory were currently used.
1767  *
1768  * We do the arithmetic in float8, because otherwise the product of
1769  * memtupsize and allowedMem could overflow. Any inaccuracy in the
1770  * result should be insignificant; but even if we computed a
1771  * completely insane result, the checks below will prevent anything
1772  * really bad from happening.
1773  */
1774  double grow_ratio;
1775 
1776  grow_ratio = (double) state->allowedMem / (double) memNowUsed;
1777  if (memtupsize * grow_ratio < INT_MAX)
1778  newmemtupsize = (int) (memtupsize * grow_ratio);
1779  else
1780  newmemtupsize = INT_MAX;
1781 
1782  /* We won't make any further enlargement attempts */
1783  state->growmemtuples = false;
1784  }
1785 
1786  /* Must enlarge array by at least one element, else report failure */
1787  if (newmemtupsize <= memtupsize)
1788  goto noalloc;
1789 
1790  /*
1791  * On a 32-bit machine, allowedMem could exceed MaxAllocHugeSize. Clamp
1792  * to ensure our request won't be rejected. Note that we can easily
1793  * exhaust address space before facing this outcome. (This is presently
1794  * impossible due to guc.c's MAX_KILOBYTES limitation on work_mem, but
1795  * don't rely on that at this distance.)
1796  */
1797  if ((Size) newmemtupsize >= MaxAllocHugeSize / sizeof(SortTuple))
1798  {
1799  newmemtupsize = (int) (MaxAllocHugeSize / sizeof(SortTuple));
1800  state->growmemtuples = false; /* can't grow any more */
1801  }
1802 
1803  /*
1804  * We need to be sure that we do not cause LACKMEM to become true, else
1805  * the space management algorithm will go nuts. The code above should
1806  * never generate a dangerous request, but to be safe, check explicitly
1807  * that the array growth fits within availMem. (We could still cause
1808  * LACKMEM if the memory chunk overhead associated with the memtuples
1809  * array were to increase. That shouldn't happen because we chose the
1810  * initial array size large enough to ensure that palloc will be treating
1811  * both old and new arrays as separate chunks. But we'll check LACKMEM
1812  * explicitly below just in case.)
1813  */
1814  if (state->availMem < (int64) ((newmemtupsize - memtupsize) * sizeof(SortTuple)))
1815  goto noalloc;
1816 
1817  /* OK, do it */
1818  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
1819  state->memtupsize = newmemtupsize;
1820  state->memtuples = (SortTuple *)
1821  repalloc_huge(state->memtuples,
1822  state->memtupsize * sizeof(SortTuple));
1823  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
1824  if (LACKMEM(state))
1825  elog(ERROR, "unexpected out-of-memory situation in tuplesort");
1826  return true;
1827 
1828 noalloc:
1829  /* If for any reason we didn't realloc, shut off future attempts */
1830  state->growmemtuples = false;
1831  return false;
1832 }
size_t Size
Definition: c.h:551
void * repalloc_huge(void *pointer, Size size)
Definition: mcxt.c:1258
#define MaxAllocHugeSize
Definition: memutils.h:44

References elog(), ERROR, FREEMEM, GetMemoryChunkSpace(), LACKMEM, MaxAllocHugeSize, repalloc_huge(), and USEMEM.

Referenced by puttuple_common().

◆ init_slab_allocator()

static void init_slab_allocator ( Tuplesortstate state,
int  numSlots 
)
static

Definition at line 2960 of file tuplesort.c.

2961 {
2962  if (numSlots > 0)
2963  {
2964  char *p;
2965  int i;
2966 
2967  state->slabMemoryBegin = palloc(numSlots * SLAB_SLOT_SIZE);
2968  state->slabMemoryEnd = state->slabMemoryBegin +
2969  numSlots * SLAB_SLOT_SIZE;
2970  state->slabFreeHead = (SlabSlot *) state->slabMemoryBegin;
2971  USEMEM(state, numSlots * SLAB_SLOT_SIZE);
2972 
2973  p = state->slabMemoryBegin;
2974  for (i = 0; i < numSlots - 1; i++)
2975  {
2976  ((SlabSlot *) p)->nextfree = (SlabSlot *) (p + SLAB_SLOT_SIZE);
2977  p += SLAB_SLOT_SIZE;
2978  }
2979  ((SlabSlot *) p)->nextfree = NULL;
2980  }
2981  else
2982  {
2983  state->slabMemoryBegin = state->slabMemoryEnd = NULL;
2984  state->slabFreeHead = NULL;
2985  }
2986  state->slabAllocatorUsed = true;
2987 }
void * palloc(Size size)
Definition: mcxt.c:1068
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:200

References i, palloc(), SLAB_SLOT_SIZE, and USEMEM.

Referenced by mergeruns().

◆ inittapes()

static void inittapes ( Tuplesortstate state,
bool  mergeruns 
)
static

Definition at line 2842 of file tuplesort.c.

2843 {
2844  Assert(!LEADER(state));
2845 
2846  if (mergeruns)
2847  {
2848  /* Compute number of input tapes to use when merging */
2849  state->maxTapes = tuplesort_merge_order(state->allowedMem);
2850  }
2851  else
2852  {
2853  /* Workers can sometimes produce single run, output without merge */
2854  Assert(WORKER(state));
2855  state->maxTapes = MINORDER;
2856  }
2857 
2858 #ifdef TRACE_SORT
2859  if (trace_sort)
2860  elog(LOG, "worker %d switching to external sort with %d tapes: %s",
2861  state->worker, state->maxTapes, pg_rusage_show(&state->ru_start));
2862 #endif
2863 
2864  /* Create the tape set */
2865  inittapestate(state, state->maxTapes);
2866  state->tapeset =
2867  LogicalTapeSetCreate(false,
2868  state->shared ? &state->shared->fileset : NULL,
2869  state->worker);
2870 
2871  state->currentRun = 0;
2872 
2873  /*
2874  * Initialize logical tape arrays.
2875  */
2876  state->inputTapes = NULL;
2877  state->nInputTapes = 0;
2878  state->nInputRuns = 0;
2879 
2880  state->outputTapes = palloc0(state->maxTapes * sizeof(LogicalTape *));
2881  state->nOutputTapes = 0;
2882  state->nOutputRuns = 0;
2883 
2884  state->status = TSS_BUILDRUNS;
2885 
2887 }
LogicalTapeSet * LogicalTapeSetCreate(bool preallocate, SharedFileSet *fileset, int worker)
Definition: logtape.c:557
void * palloc0(Size size)
Definition: mcxt.c:1099
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2755
static void inittapestate(Tuplesortstate *state, int maxTapes)
Definition: tuplesort.c:2893
#define LEADER(state)
Definition: tuplesort.c:560
#define WORKER(state)
Definition: tuplesort.c:559
static void mergeruns(Tuplesortstate *state)
Definition: tuplesort.c:2996
#define MINORDER
Definition: tuplesort.c:234

References Assert(), elog(), inittapestate(), LEADER, LOG, LogicalTapeSetCreate(), mergeruns(), MINORDER, palloc0(), pg_rusage_show(), selectnewtape(), trace_sort, TSS_BUILDRUNS, tuplesort_merge_order(), and WORKER.

Referenced by puttuple_common(), and tuplesort_performsort().

◆ inittapestate()

static void inittapestate ( Tuplesortstate state,
int  maxTapes 
)
static

Definition at line 2893 of file tuplesort.c.

2894 {
2895  int64 tapeSpace;
2896 
2897  /*
2898  * Decrease availMem to reflect the space needed for tape buffers; but
2899  * don't decrease it to the point that we have no room for tuples. (That
2900  * case is only likely to occur if sorting pass-by-value Datums; in all
2901  * other scenarios the memtuples[] array is unlikely to occupy more than
2902  * half of allowedMem. In the pass-by-value case it's not important to
2903  * account for tuple space, so we don't care if LACKMEM becomes
2904  * inaccurate.)
2905  */
2906  tapeSpace = (int64) maxTapes * TAPE_BUFFER_OVERHEAD;
2907 
2908  if (tapeSpace + GetMemoryChunkSpace(state->memtuples) < state->allowedMem)
2909  USEMEM(state, tapeSpace);
2910 
2911  /*
2912  * Make sure that the temp file(s) underlying the tape set are created in
2913  * suitable temp tablespaces. For parallel sorts, this should have been
2914  * called already, but it doesn't matter if it is called a second time.
2915  */
2917 }
void PrepareTempTablespaces(void)
Definition: tablespace.c:1379
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:236

References GetMemoryChunkSpace(), PrepareTempTablespaces(), TAPE_BUFFER_OVERHEAD, and USEMEM.

Referenced by inittapes(), and leader_takeover_tapes().

◆ leader_takeover_tapes()

static void leader_takeover_tapes ( Tuplesortstate state)
static

Definition at line 4829 of file tuplesort.c.

4830 {
4831  Sharedsort *shared = state->shared;
4832  int nParticipants = state->nParticipants;
4833  int workersFinished;
4834  int j;
4835 
4836  Assert(LEADER(state));
4837  Assert(nParticipants >= 1);
4838 
4839  SpinLockAcquire(&shared->mutex);
4840  workersFinished = shared->workersFinished;
4841  SpinLockRelease(&shared->mutex);
4842 
4843  if (nParticipants != workersFinished)
4844  elog(ERROR, "cannot take over tapes before all workers finish");
4845 
4846  /*
4847  * Create the tapeset from worker tapes, including a leader-owned tape at
4848  * the end. Parallel workers are far more expensive than logical tapes,
4849  * so the number of tapes allocated here should never be excessive.
4850  */
4851  inittapestate(state, nParticipants);
4852  state->tapeset = LogicalTapeSetCreate(false, &shared->fileset, -1);
4853 
4854  /*
4855  * Set currentRun to reflect the number of runs we will merge (it's not
4856  * used for anything, this is just pro forma)
4857  */
4858  state->currentRun = nParticipants;
4859 
4860  /*
4861  * Initialize the state to look the same as after building the initial
4862  * runs.
4863  *
4864  * There will always be exactly 1 run per worker, and exactly one input
4865  * tape per run, because workers always output exactly 1 run, even when
4866  * there were no input tuples for workers to sort.
4867  */
4868  state->inputTapes = NULL;
4869  state->nInputTapes = 0;
4870  state->nInputRuns = 0;
4871 
4872  state->outputTapes = palloc0(nParticipants * sizeof(LogicalTape *));
4873  state->nOutputTapes = nParticipants;
4874  state->nOutputRuns = nParticipants;
4875 
4876  for (j = 0; j < nParticipants; j++)
4877  {
4878  state->outputTapes[j] = LogicalTapeImport(state->tapeset, j, &shared->tapes[j]);
4879  }
4880 
4881  state->status = TSS_BUILDRUNS;
4882 }
int j
Definition: isn.c:74
LogicalTape * LogicalTapeImport(LogicalTapeSet *lts, int worker, TapeShare *shared)
Definition: logtape.c:610
#define SpinLockRelease(lock)
Definition: spin.h:64
#define SpinLockAcquire(lock)
Definition: spin.h:62
SharedFileSet fileset
Definition: tuplesort.c:516
TapeShare tapes[FLEXIBLE_ARRAY_MEMBER]
Definition: tuplesort.c:525
int workersFinished
Definition: tuplesort.c:513
slock_t mutex
Definition: tuplesort.c:502

References Assert(), elog(), ERROR, Sharedsort::fileset, inittapestate(), j, LEADER, LogicalTapeImport(), LogicalTapeSetCreate(), Sharedsort::mutex, palloc0(), SpinLockAcquire, SpinLockRelease, Sharedsort::tapes, TSS_BUILDRUNS, and Sharedsort::workersFinished.

Referenced by tuplesort_performsort().

◆ make_bounded_heap()

static void make_bounded_heap ( Tuplesortstate state)
static

Definition at line 3564 of file tuplesort.c.

3565 {
3566  int tupcount = state->memtupcount;
3567  int i;
3568 
3569  Assert(state->status == TSS_INITIAL);
3570  Assert(state->bounded);
3571  Assert(tupcount >= state->bound);
3572  Assert(SERIAL(state));
3573 
3574  /* Reverse sort direction so largest entry will be at root */
3576 
3577  state->memtupcount = 0; /* make the heap empty */
3578  for (i = 0; i < tupcount; i++)
3579  {
3580  if (state->memtupcount < state->bound)
3581  {
3582  /* Insert next tuple into heap */
3583  /* Must copy source tuple to avoid possible overwrite */
3584  SortTuple stup = state->memtuples[i];
3585 
3586  tuplesort_heap_insert(state, &stup);
3587  }
3588  else
3589  {
3590  /*
3591  * The heap is full. Replace the largest entry with the new
3592  * tuple, or just discard it, if it's larger than anything already
3593  * in the heap.
3594  */
3595  if (COMPARETUP(state, &state->memtuples[i], &state->memtuples[0]) <= 0)
3596  {
3597  free_sort_tuple(state, &state->memtuples[i]);
3599  }
3600  else
3601  tuplesort_heap_replace_top(state, &state->memtuples[i]);
3602  }
3603  }
3604 
3605  Assert(state->memtupcount == state->bound);
3606  state->status = TSS_BOUNDED;
3607 }
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:121
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:551
#define SERIAL(state)
Definition: tuplesort.c:558
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4888
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3815
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3775

References Assert(), CHECK_FOR_INTERRUPTS, COMPARETUP, free_sort_tuple(), i, reversedirection(), SERIAL, TSS_BOUNDED, TSS_INITIAL, tuplesort_heap_insert(), and tuplesort_heap_replace_top().

Referenced by puttuple_common().

◆ markrunend()

static void markrunend ( LogicalTape tape)
static

Definition at line 3846 of file tuplesort.c.

3847 {
3848  unsigned int len = 0;
3849 
3850  LogicalTapeWrite(tape, (void *) &len, sizeof(len));
3851 }
void LogicalTapeWrite(LogicalTape *lt, void *ptr, size_t size)
Definition: logtape.c:762

References len, and LogicalTapeWrite().

Referenced by dumptuples(), and mergeonerun().

◆ merge_read_buffer_size()

static int64 merge_read_buffer_size ( int64  avail_mem,
int  nInputTapes,
int  nInputRuns,
int  maxOutputTapes 
)
static

Definition at line 2810 of file tuplesort.c.

2812 {
2813  int nOutputRuns;
2814  int nOutputTapes;
2815 
2816  /*
2817  * How many output tapes will we produce in this pass?
2818  *
2819  * This is nInputRuns / nInputTapes, rounded up.
2820  */
2821  nOutputRuns = (nInputRuns + nInputTapes - 1) / nInputTapes;
2822 
2823  nOutputTapes = Min(nOutputRuns, maxOutputTapes);
2824 
2825  /*
2826  * Each output tape consumes TAPE_BUFFER_OVERHEAD bytes of memory. All
2827  * remaining memory is divided evenly between the input tapes.
2828  *
2829  * This also follows from the formula in tuplesort_merge_order, but here
2830  * we derive the input buffer size from the amount of memory available,
2831  * and M and N.
2832  */
2833  return Max((avail_mem - TAPE_BUFFER_OVERHEAD * nOutputTapes) / nInputTapes, 0);
2834 }

References Max, Min, and TAPE_BUFFER_OVERHEAD.

Referenced by mergeruns().

◆ mergeonerun()

static void mergeonerun ( Tuplesortstate state)
static

Definition at line 3183 of file tuplesort.c.

3184 {
3185  int srcTapeIndex;
3186  LogicalTape *srcTape;
3187 
3188  /*
3189  * Start the merge by loading one tuple from each active source tape into
3190  * the heap.
3191  */
3192  beginmerge(state);
3193 
3194  /*
3195  * Execute merge by repeatedly extracting lowest tuple in heap, writing it
3196  * out, and replacing it with next tuple from same tape (if there is
3197  * another one).
3198  */
3199  while (state->memtupcount > 0)
3200  {
3201  SortTuple stup;
3202 
3203  /* write the tuple to destTape */
3204  srcTapeIndex = state->memtuples[0].srctape;
3205  srcTape = state->inputTapes[srcTapeIndex];
3206  WRITETUP(state, state->destTape, &state->memtuples[0]);
3207 
3208  /* recycle the slot of the tuple we just wrote out, for the next read */
3209  if (state->memtuples[0].tuple)
3210  RELEASE_SLAB_SLOT(state, state->memtuples[0].tuple);
3211 
3212  /*
3213  * pull next tuple from the tape, and replace the written-out tuple in
3214  * the heap with it.
3215  */
3216  if (mergereadnext(state, srcTape, &stup))
3217  {
3218  stup.srctape = srcTapeIndex;
3220  }
3221  else
3222  {
3224  state->nInputRuns--;
3225  }
3226  }
3227 
3228  /*
3229  * When the heap empties, we're done. Write an end-of-run marker on the
3230  * output tape.
3231  */
3232  markrunend(state->destTape);
3233 }
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3751
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:3241
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:539

References beginmerge(), markrunend(), mergereadnext(), RELEASE_SLAB_SLOT, SortTuple::srctape, tuplesort_heap_delete_top(), tuplesort_heap_replace_top(), and WRITETUP.

Referenced by mergeruns().

◆ mergereadnext()

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

Definition at line 3269 of file tuplesort.c.

3270 {
3271  unsigned int tuplen;
3272 
3273  /* read next tuple, if any */
3274  if ((tuplen = getlen(srcTape, true)) == 0)
3275  return false;
3276  READTUP(state, stup, srcTape, tuplen);
3277 
3278  return true;
3279 }
static unsigned int getlen(LogicalTape *tape, bool eofOK)
Definition: tuplesort.c:3833
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:554

References getlen(), and READTUP.

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

◆ mergeruns()

static void mergeruns ( Tuplesortstate state)
static

Definition at line 2996 of file tuplesort.c.

2997 {
2998  int tapenum;
2999 
3000  Assert(state->status == TSS_BUILDRUNS);
3001  Assert(state->memtupcount == 0);
3002 
3003  if (state->sortKeys != NULL && state->sortKeys->abbrev_converter != NULL)
3004  {
3005  /*
3006  * If there are multiple runs to be merged, when we go to read back
3007  * tuples from disk, abbreviated keys will not have been stored, and
3008  * we don't care to regenerate them. Disable abbreviation from this
3009  * point on.
3010  */
3011  state->sortKeys->abbrev_converter = NULL;
3012  state->sortKeys->comparator = state->sortKeys->abbrev_full_comparator;
3013 
3014  /* Not strictly necessary, but be tidy */
3015  state->sortKeys->abbrev_abort = NULL;
3016  state->sortKeys->abbrev_full_comparator = NULL;
3017  }
3018 
3019  /*
3020  * Reset tuple memory. We've freed all the tuples that we previously
3021  * allocated. We will use the slab allocator from now on.
3022  */
3023  MemoryContextResetOnly(state->tuplecontext);
3024 
3025  /*
3026  * We no longer need a large memtuples array. (We will allocate a smaller
3027  * one for the heap later.)
3028  */
3029  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
3030  pfree(state->memtuples);
3031  state->memtuples = NULL;
3032 
3033  /*
3034  * Initialize the slab allocator. We need one slab slot per input tape,
3035  * for the tuples in the heap, plus one to hold the tuple last returned
3036  * from tuplesort_gettuple. (If we're sorting pass-by-val Datums,
3037  * however, we don't need to do allocate anything.)
3038  *
3039  * In a multi-pass merge, we could shrink this allocation for the last
3040  * merge pass, if it has fewer tapes than previous passes, but we don't
3041  * bother.
3042  *
3043  * From this point on, we no longer use the USEMEM()/LACKMEM() mechanism
3044  * to track memory usage of individual tuples.
3045  */
3046  if (state->tuples)
3047  init_slab_allocator(state, state->nOutputTapes + 1);
3048  else
3050 
3051  /*
3052  * Allocate a new 'memtuples' array, for the heap. It will hold one tuple
3053  * from each input tape.
3054  *
3055  * We could shrink this, too, between passes in a multi-pass merge, but we
3056  * don't bother. (The initial input tapes are still in outputTapes. The
3057  * number of input tapes will not increase between passes.)
3058  */
3059  state->memtupsize = state->nOutputTapes;
3060  state->memtuples = (SortTuple *) MemoryContextAlloc(state->maincontext,
3061  state->nOutputTapes * sizeof(SortTuple));
3062  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
3063 
3064  /*
3065  * Use all the remaining memory we have available for tape buffers among
3066  * all the input tapes. At the beginning of each merge pass, we will
3067  * divide this memory between the input and output tapes in the pass.
3068  */
3069  state->tape_buffer_mem = state->availMem;
3070  USEMEM(state, state->tape_buffer_mem);
3071 #ifdef TRACE_SORT
3072  if (trace_sort)
3073  elog(LOG, "worker %d using %zu KB of memory for tape buffers",
3074  state->worker, state->tape_buffer_mem / 1024);
3075 #endif
3076 
3077  for (;;)
3078  {
3079  /*
3080  * On the first iteration, or if we have read all the runs from the
3081  * input tapes in a multi-pass merge, it's time to start a new pass.
3082  * Rewind all the output tapes, and make them inputs for the next
3083  * pass.
3084  */
3085  if (state->nInputRuns == 0)
3086  {
3087  int64 input_buffer_size;
3088 
3089  /* Close the old, emptied, input tapes */
3090  if (state->nInputTapes > 0)
3091  {
3092  for (tapenum = 0; tapenum < state->nInputTapes; tapenum++)
3093  LogicalTapeClose(state->inputTapes[tapenum]);
3094  pfree(state->inputTapes);
3095  }
3096 
3097  /* Previous pass's outputs become next pass's inputs. */
3098  state->inputTapes = state->outputTapes;
3099  state->nInputTapes = state->nOutputTapes;
3100  state->nInputRuns = state->nOutputRuns;
3101 
3102  /*
3103  * Reset output tape variables. The actual LogicalTapes will be
3104  * created as needed, here we only allocate the array to hold
3105  * them.
3106  */
3107  state->outputTapes = palloc0(state->nInputTapes * sizeof(LogicalTape *));
3108  state->nOutputTapes = 0;
3109  state->nOutputRuns = 0;
3110 
3111  /*
3112  * Redistribute the memory allocated for tape buffers, among the
3113  * new input and output tapes.
3114  */
3115  input_buffer_size = merge_read_buffer_size(state->tape_buffer_mem,
3116  state->nInputTapes,
3117  state->nInputRuns,
3118  state->maxTapes);
3119 
3120 #ifdef TRACE_SORT
3121  if (trace_sort)
3122  elog(LOG, "starting merge pass of %d input runs on %d tapes, " INT64_FORMAT " KB of memory for each input tape: %s",
3123  state->nInputRuns, state->nInputTapes, input_buffer_size / 1024,
3124  pg_rusage_show(&state->ru_start));
3125 #endif
3126 
3127  /* Prepare the new input tapes for merge pass. */
3128  for (tapenum = 0; tapenum < state->nInputTapes; tapenum++)
3129  LogicalTapeRewindForRead(state->inputTapes[tapenum], input_buffer_size);
3130 
3131  /*
3132  * If there's just one run left on each input tape, then only one
3133  * merge pass remains. If we don't have to produce a materialized
3134  * sorted tape, we can stop at this point and do the final merge
3135  * on-the-fly.
3136  */
3137  if ((state->sortopt & TUPLESORT_RANDOMACCESS) == 0
3138  && state->nInputRuns <= state->nInputTapes
3139  && !WORKER(state))
3140  {
3141  /* Tell logtape.c we won't be writing anymore */
3143  /* Initialize for the final merge pass */
3144  beginmerge(state);
3145  state->status = TSS_FINALMERGE;
3146  return;
3147  }
3148  }
3149 
3150  /* Select an output tape */
3152 
3153  /* Merge one run from each input tape. */
3154  mergeonerun(state);
3155 
3156  /*
3157  * If the input tapes are empty, and we output only one output run,
3158  * we're done. The current output tape contains the final result.
3159  */
3160  if (state->nInputRuns == 0 && state->nOutputRuns <= 1)
3161  break;
3162  }
3163 
3164  /*
3165  * Done. The result is on a single run on a single tape.
3166  */
3167  state->result_tape = state->outputTapes[0];
3168  if (!WORKER(state))
3169  LogicalTapeFreeze(state->result_tape, NULL);
3170  else
3172  state->status = TSS_SORTEDONTAPE;
3173 
3174  /* Close all the now-empty input tapes, to release their read buffers. */
3175  for (tapenum = 0; tapenum < state->nInputTapes; tapenum++)
3176  LogicalTapeClose(state->inputTapes[tapenum]);
3177 }
#define INT64_FORMAT
Definition: c.h:494
void LogicalTapeRewindForRead(LogicalTape *lt, size_t buffer_size)
Definition: logtape.c:847
void LogicalTapeSetForgetFreeSpace(LogicalTapeSet *lts)
Definition: logtape.c:751
void LogicalTapeClose(LogicalTape *lt)
Definition: logtape.c:734
void LogicalTapeFreeze(LogicalTape *lt, TapeShare *share)
Definition: logtape.c:982
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:863
void MemoryContextResetOnly(MemoryContext context)
Definition: mcxt.c:162
static void mergeonerun(Tuplesortstate *state)
Definition: tuplesort.c:3183
static int64 merge_read_buffer_size(int64 avail_mem, int nInputTapes, int nInputRuns, int maxOutputTapes)
Definition: tuplesort.c:2810
static void worker_freeze_result_tape(Tuplesortstate *state)
Definition: tuplesort.c:4769
static void init_slab_allocator(Tuplesortstate *state, int numSlots)
Definition: tuplesort.c:2960
#define TUPLESORT_RANDOMACCESS
Definition: tuplesort.h:93

References Assert(), beginmerge(), elog(), FREEMEM, GetMemoryChunkSpace(), init_slab_allocator(), INT64_FORMAT, LOG, LogicalTapeClose(), LogicalTapeFreeze(), LogicalTapeRewindForRead(), LogicalTapeSetForgetFreeSpace(), MemoryContextAlloc(), MemoryContextResetOnly(), merge_read_buffer_size(), mergeonerun(), palloc0(), pfree(), pg_rusage_show(), selectnewtape(), trace_sort, TSS_BUILDRUNS, TSS_FINALMERGE, TSS_SORTEDONTAPE, TUPLESORT_RANDOMACCESS, USEMEM, WORKER, and worker_freeze_result_tape().

Referenced by inittapes(), and tuplesort_performsort().

◆ puttuple_common()

static void puttuple_common ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 2043 of file tuplesort.c.

2044 {
2045  Assert(!LEADER(state));
2046 
2047  switch (state->status)
2048  {
2049  case TSS_INITIAL:
2050 
2051  /*
2052  * Save the tuple into the unsorted array. First, grow the array
2053  * as needed. Note that we try to grow the array when there is
2054  * still one free slot remaining --- if we fail, there'll still be
2055  * room to store the incoming tuple, and then we'll switch to
2056  * tape-based operation.
2057  */
2058  if (state->memtupcount >= state->memtupsize - 1)
2059  {
2060  (void) grow_memtuples(state);
2061  Assert(state->memtupcount < state->memtupsize);
2062  }
2063  state->memtuples[state->memtupcount++] = *tuple;
2064 
2065  /*
2066  * Check if it's time to switch over to a bounded heapsort. We do
2067  * so if the input tuple count exceeds twice the desired tuple
2068  * count (this is a heuristic for where heapsort becomes cheaper
2069  * than a quicksort), or if we've just filled workMem and have
2070  * enough tuples to meet the bound.
2071  *
2072  * Note that once we enter TSS_BOUNDED state we will always try to
2073  * complete the sort that way. In the worst case, if later input
2074  * tuples are larger than earlier ones, this might cause us to
2075  * exceed workMem significantly.
2076  */
2077  if (state->bounded &&
2078  (state->memtupcount > state->bound * 2 ||
2079  (state->memtupcount > state->bound && LACKMEM(state))))
2080  {
2081 #ifdef TRACE_SORT
2082  if (trace_sort)
2083  elog(LOG, "switching to bounded heapsort at %d tuples: %s",
2084  state->memtupcount,
2085  pg_rusage_show(&state->ru_start));
2086 #endif
2088  return;
2089  }
2090 
2091  /*
2092  * Done if we still fit in available memory and have array slots.
2093  */
2094  if (state->memtupcount < state->memtupsize && !LACKMEM(state))
2095  return;
2096 
2097  /*
2098  * Nope; time to switch to tape-based operation.
2099  */
2100  inittapes(state, true);
2101 
2102  /*
2103  * Dump all tuples.
2104  */
2105  dumptuples(state, false);
2106  break;
2107 
2108  case TSS_BOUNDED:
2109 
2110  /*
2111  * We don't want to grow the array here, so check whether the new
2112  * tuple can be discarded before putting it in. This should be a
2113  * good speed optimization, too, since when there are many more
2114  * input tuples than the bound, most input tuples can be discarded
2115  * with just this one comparison. Note that because we currently
2116  * have the sort direction reversed, we must check for <= not >=.
2117  */
2118  if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
2119  {
2120  /* new tuple <= top of the heap, so we can discard it */
2121  free_sort_tuple(state, tuple);
2123  }
2124  else
2125  {
2126  /* discard top of heap, replacing it with the new tuple */
2127  free_sort_tuple(state, &state->memtuples[0]);
2129  }
2130  break;
2131 
2132  case TSS_BUILDRUNS:
2133 
2134  /*
2135  * Save the tuple into the unsorted array (there must be space)
2136  */
2137  state->memtuples[state->memtupcount++] = *tuple;
2138 
2139  /*
2140  * If we are over the memory limit, dump all tuples.
2141  */
2142  dumptuples(state, false);
2143  break;
2144 
2145  default:
2146  elog(ERROR, "invalid tuplesort state");
2147  break;
2148  }
2149 }
static bool grow_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:1721
static void make_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3564
static void inittapes(Tuplesortstate *state, bool mergeruns)
Definition: tuplesort.c:2842
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:3288

References Assert(), CHECK_FOR_INTERRUPTS, COMPARETUP, dumptuples(), elog(), ERROR, free_sort_tuple(), grow_memtuples(), inittapes(), LACKMEM, LEADER, LOG, make_bounded_heap(), pg_rusage_show(), trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_INITIAL, and tuplesort_heap_replace_top().

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

◆ qsort_tuple_int32_compare()

static pg_attribute_always_inline int qsort_tuple_int32_compare ( SortTuple a,
SortTuple b,
Tuplesortstate state 
)
static

Definition at line 745 of file tuplesort.c.

746 {
747  int compare;
748 
749  compare = ApplyInt32SortComparator(a->datum1, a->isnull1,
750  b->datum1, b->isnull1,
751  &state->sortKeys[0]);
752 
753  if (compare != 0)
754  return compare;
755 
756  /*
757  * No need to waste effort calling the tiebreak function when there are no
758  * other keys to sort on.
759  */
760  if (state->onlyKey != NULL)
761  return 0;
762 
763  return state->comparetup(a, b, state);
764 }
static int ApplyInt32SortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:302

References a, ApplyInt32SortComparator(), b, and compare().

◆ qsort_tuple_unsigned_compare()

static pg_attribute_always_inline int qsort_tuple_unsigned_compare ( SortTuple a,
SortTuple b,
Tuplesortstate state 
)
static

Definition at line 698 of file tuplesort.c.

699 {
700  int compare;
701 
702  compare = ApplyUnsignedSortComparator(a->datum1, a->isnull1,
703  b->datum1, b->isnull1,
704  &state->sortKeys[0]);
705  if (compare != 0)
706  return compare;
707 
708  /*
709  * No need to waste effort calling the tiebreak function when there are no
710  * other keys to sort on.
711  */
712  if (state->onlyKey != NULL)
713  return 0;
714 
715  return state->comparetup(a, b, state);
716 }
static int ApplyUnsignedSortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:233

References a, ApplyUnsignedSortComparator(), b, and compare().

◆ readtup_alloc()

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

Definition at line 3860 of file tuplesort.c.

3861 {
3862  SlabSlot *buf;
3863 
3864  /*
3865  * We pre-allocate enough slots in the slab arena that we should never run
3866  * out.
3867  */
3868  Assert(state->slabFreeHead);
3869 
3870  if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
3871  return MemoryContextAlloc(state->sortcontext, tuplen);
3872  else
3873  {
3874  buf = state->slabFreeHead;
3875  /* Reuse this slot */
3876  state->slabFreeHead = buf->nextfree;
3877 
3878  return buf;
3879  }
3880 }

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

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

◆ readtup_cluster()

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

Definition at line 4290 of file tuplesort.c.

4292 {
4293  unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
4295  t_len + HEAPTUPLESIZE);
4296 
4297  /* Reconstruct the HeapTupleData header */
4298  tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
4299  tuple->t_len = t_len;
4300  LogicalTapeReadExact(tape, &tuple->t_self, sizeof(ItemPointerData));
4301  /* We don't currently bother to reconstruct t_tableOid */
4302  tuple->t_tableOid = InvalidOid;
4303  /* Read in the tuple body */
4304  LogicalTapeReadExact(tape, tuple->t_data, tuple->t_len);
4305  if (state->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length
4306  * word? */
4307  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
4308  stup->tuple = (void *) tuple;
4309  /* set up first-column key value, if it's a simple column */
4310  if (state->haveDatum1)
4311  stup->datum1 = heap_getattr(tuple,
4312  state->indexInfo->ii_IndexAttrNumbers[0],
4313  state->tupDesc,
4314  &stup->isnull1);
4315 }
#define HEAPTUPLESIZE
Definition: htup.h:73
struct ItemPointerData ItemPointerData
#define InvalidOid
Definition: postgres_ext.h:36
ItemPointerData t_self
Definition: htup.h:65
Oid t_tableOid
Definition: htup.h:66
#define LogicalTapeReadExact(tape, ptr, len)
Definition: tuplesort.c:612
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3860

References SortTuple::datum1, heap_getattr(), HEAPTUPLESIZE, InvalidOid, SortTuple::isnull1, LogicalTapeReadExact, readtup_alloc(), HeapTupleData::t_data, HeapTupleData::t_len, HeapTupleData::t_self, HeapTupleData::t_tableOid, SortTuple::tuple, and TUPLESORT_RANDOMACCESS.

Referenced by tuplesort_begin_cluster().

◆ readtup_datum()

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

Definition at line 4632 of file tuplesort.c.

4634 {
4635  unsigned int tuplen = len - sizeof(unsigned int);
4636 
4637  if (tuplen == 0)
4638  {
4639  /* it's NULL */
4640  stup->datum1 = (Datum) 0;
4641  stup->isnull1 = true;
4642  stup->tuple = NULL;
4643  }
4644  else if (!state->tuples)
4645  {
4646  Assert(tuplen == sizeof(Datum));
4647  LogicalTapeReadExact(tape, &stup->datum1, tuplen);
4648  stup->isnull1 = false;
4649  stup->tuple = NULL;
4650  }
4651  else
4652  {
4653  void *raddr = readtup_alloc(state, tuplen);
4654 
4655  LogicalTapeReadExact(tape, raddr, tuplen);
4656  stup->datum1 = PointerGetDatum(raddr);
4657  stup->isnull1 = false;
4658  stup->tuple = raddr;
4659  }
4660 
4661  if (state->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length
4662  * word? */
4663  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
4664 }

References Assert(), SortTuple::datum1, SortTuple::isnull1, len, LogicalTapeReadExact, PointerGetDatum, readtup_alloc(), SortTuple::tuple, and TUPLESORT_RANDOMACCESS.

Referenced by tuplesort_begin_datum().

◆ readtup_heap()

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

Definition at line 4053 of file tuplesort.c.

4055 {
4056  unsigned int tupbodylen = len - sizeof(int);
4057  unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
4058  MinimalTuple tuple = (MinimalTuple) readtup_alloc(state, tuplen);
4059  char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
4060  HeapTupleData htup;
4061 
4062  /* read in the tuple proper */
4063  tuple->t_len = tuplen;
4064  LogicalTapeReadExact(tape, tupbody, tupbodylen);
4065  if (state->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length
4066  * word? */
4067  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
4068  stup->tuple = (void *) tuple;
4069  /* set up first-column key value */
4070  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
4071  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
4072  stup->datum1 = heap_getattr(&htup,
4073  state->sortKeys[0].ssup_attno,
4074  state->tupDesc,
4075  &stup->isnull1);
4076 }
#define MINIMAL_TUPLE_DATA_OFFSET
Definition: htup_details.h:617

References SortTuple::datum1, heap_getattr(), SortTuple::isnull1, len, LogicalTapeReadExact, MINIMAL_TUPLE_DATA_OFFSET, MINIMAL_TUPLE_OFFSET, readtup_alloc(), HeapTupleData::t_data, HeapTupleData::t_len, MinimalTupleData::t_len, SortTuple::tuple, and TUPLESORT_RANDOMACCESS.

Referenced by tuplesort_begin_heap().

◆ readtup_index()

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

Definition at line 4542 of file tuplesort.c.

4544 {
4545  unsigned int tuplen = len - sizeof(unsigned int);
4546  IndexTuple tuple = (IndexTuple) readtup_alloc(state, tuplen);
4547 
4548  LogicalTapeReadExact(tape, tuple, tuplen);
4549  if (state->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length
4550  * word? */
4551  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
4552  stup->tuple = (void *) tuple;
4553  /* set up first-column key value */
4554  stup->datum1 = index_getattr(tuple,
4555  1,
4556  RelationGetDescr(state->indexRel),
4557  &stup->isnull1);
4558 }

References SortTuple::datum1, index_getattr, SortTuple::isnull1, len, LogicalTapeReadExact, readtup_alloc(), RelationGetDescr, SortTuple::tuple, and TUPLESORT_RANDOMACCESS.

Referenced by tuplesort_begin_index_btree(), tuplesort_begin_index_gist(), and tuplesort_begin_index_hash().

◆ reversedirection()

static void reversedirection ( Tuplesortstate state)
static

Definition at line 3815 of file tuplesort.c.

3816 {
3817  SortSupport sortKey = state->sortKeys;
3818  int nkey;
3819 
3820  for (nkey = 0; nkey < state->nKeys; nkey++, sortKey++)
3821  {
3822  sortKey->ssup_reverse = !sortKey->ssup_reverse;
3823  sortKey->ssup_nulls_first = !sortKey->ssup_nulls_first;
3824  }
3825 }
bool ssup_nulls_first
Definition: sortsupport.h:75

References SortSupportData::ssup_nulls_first, and SortSupportData::ssup_reverse.

Referenced by make_bounded_heap(), and sort_bounded_heap().

◆ selectnewtape()

static void selectnewtape ( Tuplesortstate state)
static

Definition at line 2927 of file tuplesort.c.

2928 {
2929  /*
2930  * At the beginning of each merge pass, nOutputTapes and nOutputRuns are
2931  * both zero. On each call, we create a new output tape to hold the next
2932  * run, until maxTapes is reached. After that, we assign new runs to the
2933  * existing tapes in a round robin fashion.
2934  */
2935  if (state->nOutputTapes < state->maxTapes)
2936  {
2937  /* Create a new tape to hold the next run */
2938  Assert(state->outputTapes[state->nOutputRuns] == NULL);
2939  Assert(state->nOutputRuns == state->nOutputTapes);
2940  state->destTape = LogicalTapeCreate(state->tapeset);
2941  state->outputTapes[state->nOutputTapes] = state->destTape;
2942  state->nOutputTapes++;
2943  state->nOutputRuns++;
2944  }
2945  else
2946  {
2947  /*
2948  * We have reached the max number of tapes. Append to an existing
2949  * tape.
2950  */
2951  state->destTape = state->outputTapes[state->nOutputRuns % state->nOutputTapes];
2952  state->nOutputRuns++;
2953  }
2954 }
LogicalTape * LogicalTapeCreate(LogicalTapeSet *lts)
Definition: logtape.c:681

References Assert(), and LogicalTapeCreate().

Referenced by dumptuples(), inittapes(), and mergeruns().

◆ sort_bounded_heap()

static void sort_bounded_heap ( Tuplesortstate state)
static

Definition at line 3613 of file tuplesort.c.

3614 {
3615  int tupcount = state->memtupcount;
3616 
3617  Assert(state->status == TSS_BOUNDED);
3618  Assert(state->bounded);
3619  Assert(tupcount == state->bound);
3620  Assert(SERIAL(state));
3621 
3622  /*
3623  * We can unheapify in place because each delete-top call will remove the
3624  * largest entry, which we can promptly store in the newly freed slot at
3625  * the end. Once we're down to a single-entry heap, we're done.
3626  */
3627  while (state->memtupcount > 1)
3628  {
3629  SortTuple stup = state->memtuples[0];
3630 
3631  /* this sifts-up the next-largest entry and decreases memtupcount */
3633  state->memtuples[state->memtupcount] = stup;
3634  }
3635  state->memtupcount = tupcount;
3636 
3637  /*
3638  * Reverse sort direction back to the original state. This is not
3639  * actually necessary but seems like a good idea for tidiness.
3640  */
3642 
3643  state->status = TSS_SORTEDINMEM;
3644  state->boundUsed = true;
3645 }

References Assert(), reversedirection(), SERIAL, TSS_BOUNDED, TSS_SORTEDINMEM, and tuplesort_heap_delete_top().

Referenced by tuplesort_performsort().

◆ ssup_datum_int32_cmp()

int ssup_datum_int32_cmp ( Datum  x,
Datum  y,
SortSupport  ssup 
)

Definition at line 4926 of file tuplesort.c.

4927 {
4928  int32 xx = DatumGetInt32(x);
4929  int32 yy = DatumGetInt32(y);
4930 
4931  if (xx < yy)
4932  return -1;
4933  else if (xx > yy)
4934  return 1;
4935  else
4936  return 0;
4937 }
int y
Definition: isn.c:72
int x
Definition: isn.c:71
#define DatumGetInt32(X)
Definition: postgres.h:516

References DatumGetInt32, x, and y.

Referenced by btint4sortsupport(), date_sortsupport(), and tuplesort_sort_memtuples().

◆ ssup_datum_unsigned_cmp()

int ssup_datum_unsigned_cmp ( Datum  x,
Datum  y,
SortSupport  ssup 
)

Definition at line 4899 of file tuplesort.c.

4900 {
4901  if (x < y)
4902  return -1;
4903  else if (x > y)
4904  return 1;
4905  else
4906  return 0;
4907 }

References x, and y.

Referenced by gist_point_sortsupport(), macaddr_sortsupport(), network_sortsupport(), tuplesort_sort_memtuples(), uuid_sortsupport(), and varstr_sortsupport().

◆ tuplesort_attach_shared()

void tuplesort_attach_shared ( Sharedsort shared,
dsm_segment seg 
)

Definition at line 4721 of file tuplesort.c.

4722 {
4723  /* Attach to SharedFileSet */
4724  SharedFileSetAttach(&shared->fileset, seg);
4725 }
void SharedFileSetAttach(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:62

References Sharedsort::fileset, and SharedFileSetAttach().

Referenced by _bt_parallel_build_main().

◆ tuplesort_begin_batch()

static void tuplesort_begin_batch ( Tuplesortstate state)
static

Definition at line 956 of file tuplesort.c.

957 {
958  MemoryContext oldcontext;
959 
960  oldcontext = MemoryContextSwitchTo(state->maincontext);
961 
962  /*
963  * Caller tuple (e.g. IndexTuple) memory context.
964  *
965  * A dedicated child context used exclusively for caller passed tuples
966  * eases memory management. Resetting at key points reduces
967  * fragmentation. Note that the memtuples array of SortTuples is allocated
968  * in the parent context, not this context, because there is no need to
969  * free memtuples early. For bounded sorts, tuples may be pfreed in any
970  * order, so we use a regular aset.c context so that it can make use of
971  * free'd memory. When the sort is not bounded, we make use of a
972  * generation.c context as this keeps allocations more compact with less
973  * wastage. Allocations are also slightly more CPU efficient.
974  */
975  if (state->sortopt & TUPLESORT_ALLOWBOUNDED)
976  state->tuplecontext = AllocSetContextCreate(state->sortcontext,
977  "Caller tuples",
979  else
980  state->tuplecontext = GenerationContextCreate(state->sortcontext,
981  "Caller tuples",
983 
984 
985  state->status = TSS_INITIAL;
986  state->bounded = false;
987  state->boundUsed = false;
988 
989  state->availMem = state->allowedMem;
990 
991  state->tapeset = NULL;
992 
993  state->memtupcount = 0;
994 
995  /*
996  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
997  * see comments in grow_memtuples().
998  */
999  state->growmemtuples = true;
1000  state->slabAllocatorUsed = false;
1001  if (state->memtuples != NULL && state->memtupsize != INITIAL_MEMTUPSIZE)
1002  {
1003  pfree(state->memtuples);
1004  state->memtuples = NULL;
1005  state->memtupsize = INITIAL_MEMTUPSIZE;
1006  }
1007  if (state->memtuples == NULL)
1008  {
1009  state->memtuples = (SortTuple *) palloc(state->memtupsize * sizeof(SortTuple));
1010  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
1011  }
1012 
1013  /* workMem must be large enough for the minimal memtuples array */
1014  if (LACKMEM(state))
1015  elog(ERROR, "insufficient memory allowed for sort");
1016 
1017  state->currentRun = 0;
1018 
1019  /*
1020  * Tape variables (inputTapes, outputTapes, etc.) will be initialized by
1021  * inittapes(), if needed.
1022  */
1023 
1024  state->result_tape = NULL; /* flag that result tape has not been formed */
1025 
1026  MemoryContextSwitchTo(oldcontext);
1027 }
MemoryContext GenerationContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: generation.c:215
#define AllocSetContextCreate
Definition: memutils.h:173
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:197
#define INITIAL_MEMTUPSIZE
Definition: tuplesort.c:139
#define TUPLESORT_ALLOWBOUNDED
Definition: tuplesort.h:96

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, elog(), ERROR, GenerationContextCreate(), GetMemoryChunkSpace(), INITIAL_MEMTUPSIZE, LACKMEM, MemoryContextSwitchTo(), palloc(), pfree(), TSS_INITIAL, TUPLESORT_ALLOWBOUNDED, and USEMEM.

Referenced by tuplesort_begin_common(), and tuplesort_reset().

◆ tuplesort_begin_cluster()

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

Definition at line 1105 of file tuplesort.c.

1109 {
1110  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1111  sortopt);
1112  BTScanInsert indexScanKey;
1113  MemoryContext oldcontext;
1114  int i;
1115 
1116  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
1117 
1118  oldcontext = MemoryContextSwitchTo(state->maincontext);
1119 
1120 #ifdef TRACE_SORT
1121  if (trace_sort)
1122  elog(LOG,
1123  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
1125  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
1126 #endif
1127 
1128  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1129 
1130  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
1131  false, /* no unique check */
1132  state->nKeys,
1133  workMem,
1134  sortopt & TUPLESORT_RANDOMACCESS,
1135  PARALLEL_SORT(state));
1136 
1137  state->comparetup = comparetup_cluster;
1138  state->copytup = copytup_cluster;
1139  state->writetup = writetup_cluster;
1140  state->readtup = readtup_cluster;
1141  state->abbrevNext = 10;
1142 
1143  state->indexInfo = BuildIndexInfo(indexRel);
1144 
1145  /*
1146  * If we don't have a simple leading attribute, we don't currently
1147  * initialize datum1, so disable optimizations that require it.
1148  */
1149  if (state->indexInfo->ii_IndexAttrNumbers[0] == 0)
1150  state->haveDatum1 = false;
1151  else
1152  state->haveDatum1 = true;
1153 
1154  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
1155 
1156  indexScanKey = _bt_mkscankey(indexRel, NULL);
1157 
1158  if (state->indexInfo->ii_Expressions != NULL)
1159  {
1160  TupleTableSlot *slot;
1161  ExprContext *econtext;
1162 
1163  /*
1164  * We will need to use FormIndexDatum to evaluate the index
1165  * expressions. To do that, we need an EState, as well as a
1166  * TupleTableSlot to put the table tuples into. The econtext's
1167  * scantuple has to point to that slot, too.
1168  */
1169  state->estate = CreateExecutorState();
1170  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
1171  econtext = GetPerTupleExprContext(state->estate);
1172  econtext->ecxt_scantuple = slot;
1173  }
1174 
1175  /* Prepare SortSupport data for each column */
1176  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1177  sizeof(SortSupportData));
1178 
1179  for (i = 0; i < state->nKeys; i++)
1180  {
1181  SortSupport sortKey = state->sortKeys + i;
1182  ScanKey scanKey = indexScanKey->scankeys + i;
1183  int16 strategy;
1184 
1185  sortKey->ssup_cxt = CurrentMemoryContext;
1186  sortKey->ssup_collation = scanKey->sk_collation;
1187  sortKey->ssup_nulls_first =
1188  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1189  sortKey->ssup_attno = scanKey->sk_attno;
1190  /* Convey if abbreviation optimization is applicable in principle */
1191  sortKey->abbreviate = (i == 0 && state->haveDatum1);
1192 
1193  AssertState(sortKey->ssup_attno != 0);
1194 
1195  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1197 
1198  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1199  }
1200 
1201  pfree(indexScanKey);
1202 
1203  MemoryContextSwitchTo(oldcontext);
1204 
1205  return state;
1206 }
#define AssertState(condition)
Definition: c.h:818
signed short int16
Definition: c.h:439
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:84
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1238
EState * CreateExecutorState(void)
Definition: execUtils.c:90
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2418
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1085
#define SK_BT_DESC
Definition: nbtree.h:1084
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:494
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:507
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:162
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:793
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:232
Form_pg_class rd_rel
Definition: rel.h:109
int sk_flags
Definition: skey.h:66
Oid sk_collation
Definition: skey.h:70
AttrNumber sk_attno
Definition: skey.h:67
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static void copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4196
#define PARALLEL_SORT(state)
Definition: tuplesort.c:129
#define CLUSTER_SORT
Definition: tuplesort.c:126
static Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
Definition: tuplesort.c:845
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.c:4290
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4084
static void writetup_cluster(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.c:4269

References _bt_mkscankey(), SortSupportData::abbreviate, Assert(), AssertState, BTGreaterStrategyNumber, BTLessStrategyNumber, BuildIndexInfo(), CLUSTER_SORT, comparetup_cluster(), copytup_cluster(), CreateExecutorState(), CurrentMemoryContext, ExprContext::ecxt_scantuple, elog(), GetPerTupleExprContext, i, IndexRelationGetNumberOfKeyAttributes, LOG, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), RelationData::rd_rel, readtup_cluster(), RelationGetNumberOfAttributes, BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, TTSOpsHeapTuple, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, and writetup_cluster().

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_begin_common()

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

Definition at line 845 of file tuplesort.c.

846 {
848  MemoryContext maincontext;
849  MemoryContext sortcontext;
850  MemoryContext oldcontext;
851 
852  /* See leader_takeover_tapes() remarks on random access support */
853  if (coordinate && (sortopt & TUPLESORT_RANDOMACCESS))
854  elog(ERROR, "random access disallowed under parallel sort");
855 
856  /*
857  * Memory context surviving tuplesort_reset. This memory context holds
858  * data which is useful to keep while sorting multiple similar batches.
859  */
861  "TupleSort main",
863 
864  /*
865  * Create a working memory context for one sort operation. The content of
866  * this context is deleted by tuplesort_reset.
867  */
868  sortcontext = AllocSetContextCreate(maincontext,
869  "TupleSort sort",
871 
872  /*
873  * Additionally a working memory context for tuples is setup in
874  * tuplesort_begin_batch.
875  */
876 
877  /*
878  * Make the Tuplesortstate within the per-sortstate context. This way, we
879  * don't need a separate pfree() operation for it at shutdown.
880  */
881  oldcontext = MemoryContextSwitchTo(maincontext);
882 
884 
885 #ifdef TRACE_SORT
886  if (trace_sort)
887  pg_rusage_init(&state->ru_start);
888 #endif
889 
890  state->sortopt = sortopt;
891  state->tuples = true;
892 
893  /*
894  * workMem is forced to be at least 64KB, the current minimum valid value
895  * for the work_mem GUC. This is a defense against parallel sort callers
896  * that divide out memory among many workers in a way that leaves each
897  * with very little memory.
898  */
899  state->allowedMem = Max(workMem, 64) * (int64) 1024;
900  state->sortcontext = sortcontext;
901  state->maincontext = maincontext;
902 
903  /*
904  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
905  * see comments in grow_memtuples().
906  */
907  state->memtupsize = INITIAL_MEMTUPSIZE;
908  state->memtuples = NULL;
909 
910  /*
911  * After all of the other non-parallel-related state, we setup all of the
912  * state needed for each batch.
913  */
915 
916  /*
917  * Initialize parallel-related state based on coordination information
918  * from caller
919  */
920  if (!coordinate)
921  {
922  /* Serial sort */
923  state->shared = NULL;
924  state->worker = -1;
925  state->nParticipants = -1;
926  }
927  else if (coordinate->isWorker)
928  {
929  /* Parallel worker produces exactly one final run from all input */
930  state->shared = coordinate->sharedsort;
931  state->worker = worker_get_identifier(state);
932  state->nParticipants = -1;
933  }
934  else
935  {
936  /* Parallel leader state only used for final merge */
937  state->shared = coordinate->sharedsort;
938  state->worker = -1;
939  state->nParticipants = coordinate->nParticipants;
940  Assert(state->nParticipants >= 1);
941  }
942 
943  MemoryContextSwitchTo(oldcontext);
944 
945  return state;
946 }
void pg_rusage_init(PGRUsage *ru0)
Definition: pg_rusage.c:27
Sharedsort * sharedsort
Definition: tuplesort.h:55
static int worker_get_identifier(Tuplesortstate *state)
Definition: tuplesort.c:4741
static void tuplesort_begin_batch(Tuplesortstate *state)
Definition: tuplesort.c:956

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

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

◆ tuplesort_begin_datum()

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

Definition at line 1396 of file tuplesort.c.

1399 {
1400  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1401  sortopt);
1402  MemoryContext oldcontext;
1403  int16 typlen;
1404  bool typbyval;
1405 
1406  oldcontext = MemoryContextSwitchTo(state->maincontext);
1407 
1408 #ifdef TRACE_SORT
1409  if (trace_sort)
1410  elog(LOG,
1411  "begin datum sort: workMem = %d, randomAccess = %c",
1412  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
1413 #endif
1414 
1415  state->nKeys = 1; /* always a one-column sort */
1416 
1417  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
1418  false, /* no unique check */
1419  1,
1420  workMem,
1421  sortopt & TUPLESORT_RANDOMACCESS,
1422  PARALLEL_SORT(state));
1423 
1424  state->comparetup = comparetup_datum;
1425  state->copytup = copytup_datum;
1426  state->writetup = writetup_datum;
1427  state->readtup = readtup_datum;
1428  state->abbrevNext = 10;
1429  state->haveDatum1 = true;
1430 
1431  state->datumType = datumType;
1432 
1433  /* lookup necessary attributes of the datum type */
1434  get_typlenbyval(datumType, &typlen, &typbyval);
1435  state->datumTypeLen = typlen;
1436  state->tuples = !typbyval;
1437 
1438  /* Prepare SortSupport data */
1439  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1440 
1441  state->sortKeys->ssup_cxt = CurrentMemoryContext;
1442  state->sortKeys->ssup_collation = sortCollation;
1443  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1444 
1445  /*
1446  * Abbreviation is possible here only for by-reference types. In theory,
1447  * a pass-by-value datatype could have an abbreviated form that is cheaper
1448  * to compare. In a tuple sort, we could support that, because we can
1449  * always extract the original datum from the tuple as needed. Here, we
1450  * can't, because a datum sort only stores a single copy of the datum; the
1451  * "tuple" field of each SortTuple is NULL.
1452  */
1453  state->sortKeys->abbreviate = !typbyval;
1454 
1455  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1456 
1457  /*
1458  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1459  * tie-breaker comparisons may be required. Typically, the optimization
1460  * is only of value to pass-by-value types anyway, whereas abbreviated
1461  * keys are typically only of value to pass-by-reference types.
1462  */
1463  if (!state->sortKeys->abbrev_converter)
1464  state->onlyKey = state->sortKeys;
1465 
1466  MemoryContextSwitchTo(oldcontext);
1467 
1468  return state;
1469 }
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2208
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:135
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4565
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.c:4632
static void writetup_datum(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.c:4593
#define DATUM_SORT
Definition: tuplesort.c:125
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4586

References comparetup_datum(), copytup_datum(), CurrentMemoryContext, DATUM_SORT, elog(), get_typlenbyval(), LOG, MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), readtup_datum(), trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, and writetup_datum().

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

◆ tuplesort_begin_heap()

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

Definition at line 1030 of file tuplesort.c.

1035 {
1036  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1037  sortopt);
1038  MemoryContext oldcontext;
1039  int i;
1040 
1041  oldcontext = MemoryContextSwitchTo(state->maincontext);
1042 
1043  AssertArg(nkeys > 0);
1044 
1045 #ifdef TRACE_SORT
1046  if (trace_sort)
1047  elog(LOG,
1048  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
1049  nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
1050 #endif
1051 
1052  state->nKeys = nkeys;
1053 
1054  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
1055  false, /* no unique check */
1056  nkeys,
1057  workMem,
1058  sortopt & TUPLESORT_RANDOMACCESS,
1059  PARALLEL_SORT(state));
1060 
1061  state->comparetup = comparetup_heap;
1062  state->copytup = copytup_heap;
1063  state->writetup = writetup_heap;
1064  state->readtup = readtup_heap;
1065  state->haveDatum1 = true;
1066 
1067  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
1068  state->abbrevNext = 10;
1069 
1070  /* Prepare SortSupport data for each column */
1071  state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
1072 
1073  for (i = 0; i < nkeys; i++)
1074  {
1075  SortSupport sortKey = state->sortKeys + i;
1076 
1077  AssertArg(attNums[i] != 0);
1078  AssertArg(sortOperators[i] != 0);
1079 
1080  sortKey->ssup_cxt = CurrentMemoryContext;
1081  sortKey->ssup_collation = sortCollations[i];
1082  sortKey->ssup_nulls_first = nullsFirstFlags[i];
1083  sortKey->ssup_attno = attNums[i];
1084  /* Convey if abbreviation optimization is applicable in principle */
1085  sortKey->abbreviate = (i == 0 && state->haveDatum1);
1086 
1087  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
1088  }
1089 
1090  /*
1091  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1092  * tie-breaker comparisons may be required. Typically, the optimization
1093  * is only of value to pass-by-value types anyway, whereas abbreviated
1094  * keys are typically only of value to pass-by-reference types.
1095  */
1096  if (nkeys == 1 && !state->sortKeys->abbrev_converter)
1097  state->onlyKey = state->sortKeys;
1098 
1099  MemoryContextSwitchTo(oldcontext);
1100 
1101  return state;
1102 }
#define AssertArg(condition)
Definition: c.h:817
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3950
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.c:4053
static int comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3888
static void writetup_heap(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.c:4028
#define HEAP_SORT
Definition: tuplesort.c:123

References SortSupportData::abbreviate, AssertArg, comparetup_heap(), copytup_heap(), CurrentMemoryContext, elog(), HEAP_SORT, i, LOG, MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, PrepareSortSupportFromOrderingOp(), readtup_heap(), SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, and writetup_heap().

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

◆ tuplesort_begin_index_btree()

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

Definition at line 1209 of file tuplesort.c.

1216 {
1217  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1218  sortopt);
1219  BTScanInsert indexScanKey;
1220  MemoryContext oldcontext;
1221  int i;
1222 
1223  oldcontext = MemoryContextSwitchTo(state->maincontext);
1224 
1225 #ifdef TRACE_SORT
1226  if (trace_sort)
1227  elog(LOG,
1228  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
1229  enforceUnique ? 't' : 'f',
1230  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
1231 #endif
1232 
1233  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1234 
1235  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
1236  enforceUnique,
1237  state->nKeys,
1238  workMem,
1239  sortopt & TUPLESORT_RANDOMACCESS,
1240  PARALLEL_SORT(state));
1241 
1242  state->comparetup = comparetup_index_btree;
1243  state->copytup = copytup_index;
1244  state->writetup = writetup_index;
1245  state->readtup = readtup_index;
1246  state->abbrevNext = 10;
1247  state->haveDatum1 = true;
1248 
1249  state->heapRel = heapRel;
1250  state->indexRel = indexRel;
1251  state->enforceUnique = enforceUnique;
1252  state->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
1253 
1254  indexScanKey = _bt_mkscankey(indexRel, NULL);
1255 
1256  /* Prepare SortSupport data for each column */
1257  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1258  sizeof(SortSupportData));
1259 
1260  for (i = 0; i < state->nKeys; i++)
1261  {
1262  SortSupport sortKey = state->sortKeys + i;
1263  ScanKey scanKey = indexScanKey->scankeys + i;
1264  int16 strategy;
1265 
1266  sortKey->ssup_cxt = CurrentMemoryContext;
1267  sortKey->ssup_collation = scanKey->sk_collation;
1268  sortKey->ssup_nulls_first =
1269  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
1270  sortKey->ssup_attno = scanKey->sk_attno;
1271  /* Convey if abbreviation optimization is applicable in principle */
1272  sortKey->abbreviate = (i == 0 && state->haveDatum1);
1273 
1274  AssertState(sortKey->ssup_attno != 0);
1275 
1276  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
1278 
1279  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
1280  }
1281 
1282  pfree(indexScanKey);
1283 
1284  MemoryContextSwitchTo(oldcontext);
1285 
1286  return state;
1287 }
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4326
static void readtup_index(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.c:4542
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4515
#define INDEX_SORT
Definition: tuplesort.c:124
static void writetup_index(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.c:4522

References _bt_mkscankey(), SortSupportData::abbreviate, AssertState, BTGreaterStrategyNumber, BTLessStrategyNumber, comparetup_index_btree(), copytup_index(), CurrentMemoryContext, elog(), i, INDEX_SORT, IndexRelationGetNumberOfKeyAttributes, LOG, MemoryContextSwitchTo(), palloc0(), PARALLEL_SORT, pfree(), PrepareSortSupportFromIndexRel(), readtup_index(), BTScanInsertData::scankeys, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, and writetup_index().

Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().

◆ tuplesort_begin_index_gist()

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

Definition at line 1338 of file tuplesort.c.

1343 {
1344  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1345  sortopt);
1346  MemoryContext oldcontext;
1347  int i;
1348 
1349  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1350 
1351 #ifdef TRACE_SORT
1352  if (trace_sort)
1353  elog(LOG,
1354  "begin index sort: workMem = %d, randomAccess = %c",
1355  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
1356 #endif
1357 
1358  state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
1359 
1360  state->comparetup = comparetup_index_btree;
1361  state->copytup = copytup_index;
1362  state->writetup = writetup_index;
1363  state->readtup = readtup_index;
1364  state->haveDatum1 = true;
1365 
1366  state->heapRel = heapRel;
1367  state->indexRel = indexRel;
1368 
1369  /* Prepare SortSupport data for each column */
1370  state->sortKeys = (SortSupport) palloc0(state->nKeys *
1371  sizeof(SortSupportData));
1372 
1373  for (i = 0; i < state->nKeys; i++)
1374  {
1375  SortSupport sortKey = state->sortKeys + i;
1376 
1377  sortKey->ssup_cxt = CurrentMemoryContext;
1378  sortKey->ssup_collation = indexRel->rd_indcollation[i];
1379  sortKey->ssup_nulls_first = false;
1380  sortKey->ssup_attno = i + 1;
1381  /* Convey if abbreviation optimization is applicable in principle */
1382  sortKey->abbreviate = (i == 0 && state->haveDatum1);
1383 
1384  AssertState(sortKey->ssup_attno != 0);
1385 
1386  /* Look for a sort support function */
1387  PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
1388  }
1389 
1390  MemoryContextSwitchTo(oldcontext);
1391 
1392  return state;
1393 }
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:189
Oid * rd_indcollation
Definition: rel.h:212

References SortSupportData::abbreviate, AssertState, comparetup_index_btree(), copytup_index(), CurrentMemoryContext, elog(), i, IndexRelationGetNumberOfKeyAttributes, LOG, MemoryContextSwitchTo(), palloc0(), PrepareSortSupportFromGistIndexRel(), RelationData::rd_indcollation, readtup_index(), SortSupportData::ssup_attno, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, and writetup_index().

Referenced by gistbuild().

◆ tuplesort_begin_index_hash()

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

Definition at line 1290 of file tuplesort.c.

1298 {
1299  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
1300  sortopt);
1301  MemoryContext oldcontext;
1302 
1303  oldcontext = MemoryContextSwitchTo(state->maincontext);
1304 
1305 #ifdef TRACE_SORT
1306  if (trace_sort)
1307  elog(LOG,
1308  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
1309  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
1310  high_mask,
1311  low_mask,
1312  max_buckets,
1313  workMem,
1314  sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
1315 #endif
1316 
1317  state->nKeys = 1; /* Only one sort column, the hash code */
1318 
1319  state->comparetup = comparetup_index_hash;
1320  state->copytup = copytup_index;
1321  state->writetup = writetup_index;
1322  state->readtup = readtup_index;
1323  state->haveDatum1 = true;
1324 
1325  state->heapRel = heapRel;
1326  state->indexRel = indexRel;
1327 
1328  state->high_mask = high_mask;
1329  state->low_mask = low_mask;
1330  state->max_buckets = max_buckets;
1331 
1332  MemoryContextSwitchTo(oldcontext);
1333 
1334  return state;
1335 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4460

References comparetup_index_hash(), copytup_index(), elog(), LOG, MemoryContextSwitchTo(), readtup_index(), trace_sort, tuplesort_begin_common(), TUPLESORT_RANDOMACCESS, and writetup_index().

Referenced by _h_spoolinit().

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1620 of file tuplesort.c.

1621 {
1623 
1624  /*
1625  * Free the main memory context, including the Tuplesortstate struct
1626  * itself.
1627  */
1628  MemoryContextDelete(state->maincontext);
1629 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:218
static void tuplesort_free(Tuplesortstate *state)
Definition: tuplesort.c:1543

References MemoryContextDelete(), and tuplesort_free().

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

◆ tuplesort_estimate_shared()

Size tuplesort_estimate_shared ( int  nWorkers)

Definition at line 4677 of file tuplesort.c.

4678 {
4679  Size tapesSize;
4680 
4681  Assert(nWorkers > 0);
4682 
4683  /* Make sure that BufFile shared state is MAXALIGN'd */
4684  tapesSize = mul_size(sizeof(TapeShare), nWorkers);
4685  tapesSize = MAXALIGN(add_size(tapesSize, offsetof(Sharedsort, tapes)));
4686 
4687  return tapesSize;
4688 }
#define MAXALIGN(LEN)
Definition: c.h:768
#define offsetof(type, field)
Definition: c.h:738
Size add_size(Size s1, Size s2)
Definition: shmem.c:502
Size mul_size(Size s1, Size s2)
Definition: shmem.c:519

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

Referenced by _bt_begin_parallel().

◆ tuplesort_free()

static void tuplesort_free ( Tuplesortstate state)
static

Definition at line 1543 of file tuplesort.c.

1544 {
1545  /* context swap probably not needed, but let's be safe */
1546  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1547 
1548 #ifdef TRACE_SORT
1549  long spaceUsed;
1550 
1551  if (state->tapeset)
1552  spaceUsed = LogicalTapeSetBlocks(state->tapeset);
1553  else
1554  spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
1555 #endif
1556 
1557  /*
1558  * Delete temporary "tape" files, if any.
1559  *
1560  * Note: want to include this in reported total cost of sort, hence need
1561  * for two #ifdef TRACE_SORT sections.
1562  *
1563  * We don't bother to destroy the individual tapes here. They will go away
1564  * with the sortcontext. (In TSS_FINALMERGE state, we have closed
1565  * finished tapes already.)
1566  */
1567  if (state->tapeset)
1568  LogicalTapeSetClose(state->tapeset);
1569 
1570 #ifdef TRACE_SORT
1571  if (trace_sort)
1572  {
1573  if (state->tapeset)
1574  elog(LOG, "%s of worker %d ended, %ld disk blocks used: %s",
1575  SERIAL(state) ? "external sort" : "parallel external sort",
1576  state->worker, spaceUsed, pg_rusage_show(&state->ru_start));
1577  else
1578  elog(LOG, "%s of worker %d ended, %ld KB used: %s",
1579  SERIAL(state) ? "internal sort" : "unperformed parallel sort",
1580  state->worker, spaceUsed, pg_rusage_show(&state->ru_start));
1581  }
1582 
1583  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
1584 #else
1585 
1586  /*
1587  * If you disabled TRACE_SORT, you can still probe sort__done, but you
1588  * ain't getting space-used stats.
1589  */
1590  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, 0L);
1591 #endif
1592 
1593  /* Free any execution state created for CLUSTER case */
1594  if (state->estate != NULL)
1595  {
1596  ExprContext *econtext = GetPerTupleExprContext(state->estate);
1597 
1599  FreeExecutorState(state->estate);
1600  }
1601 
1602  MemoryContextSwitchTo(oldcontext);
1603 
1604  /*
1605  * Free the per-sort memory context, thereby releasing all working memory.
1606  */
1607  MemoryContextReset(state->sortcontext);
1608 }
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1254
void FreeExecutorState(EState *estate)
Definition: execUtils.c:186
void LogicalTapeSetClose(LogicalTapeSet *lts)
Definition: logtape.c:668
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:1184

References ExprContext::ecxt_scantuple, elog(), ExecDropSingleTupleTableSlot(), FreeExecutorState(), GetPerTupleExprContext, LOG, LogicalTapeSetBlocks(), LogicalTapeSetClose(), MemoryContextReset(), MemoryContextSwitchTo(), pg_rusage_show(), SERIAL, and trace_sort.

Referenced by tuplesort_end(), and tuplesort_reset().

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 3476 of file tuplesort.c.

3478 {
3479  /*
3480  * Note: it might seem we should provide both memory and disk usage for a
3481  * disk-based sort. However, the current code doesn't track memory space
3482  * accurately once we have begun to return tuples to the caller (since we
3483  * don't account for pfree's the caller is expected to do), so we cannot
3484  * rely on availMem in a disk sort. This does not seem worth the overhead
3485  * to fix. Is it worth creating an API for the memory context code to
3486  * tell us how much is actually used in sortcontext?
3487  */
3489 
3490  if (state->isMaxSpaceDisk)
3492  else
3494  stats->spaceUsed = (state->maxSpace + 1023) / 1024;
3495 
3496  switch (state->maxSpaceStatus)
3497  {
3498  case TSS_SORTEDINMEM:
3499  if (state->boundUsed)
3501  else
3503  break;
3504  case TSS_SORTEDONTAPE:
3506  break;
3507  case TSS_FINALMERGE:
3509  break;
3510  default:
3512  break;
3513  }
3514 }
TuplesortMethod sortMethod
Definition: tuplesort.h:100
TuplesortSpaceType spaceType
Definition: tuplesort.h:101
static void tuplesort_updatemax(Tuplesortstate *state)
Definition: tuplesort.c:1637
@ SORT_SPACE_TYPE_DISK
Definition: tuplesort.h:85
@ SORT_SPACE_TYPE_MEMORY
Definition: tuplesort.h:86
@ SORT_TYPE_EXTERNAL_SORT
Definition: tuplesort.h:77
@ SORT_TYPE_TOP_N_HEAPSORT
Definition: tuplesort.h:75
@ SORT_TYPE_QUICKSORT
Definition: tuplesort.h:76
@ SORT_TYPE_STILL_IN_PROGRESS
Definition: tuplesort.h:74
@ SORT_TYPE_EXTERNAL_MERGE
Definition: tuplesort.h:78

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

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

◆ tuplesort_getdatum()

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

Definition at line 2647 of file tuplesort.c.

2649 {
2650  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2651  SortTuple stup;
2652 
2653  if (!tuplesort_gettuple_common(state, forward, &stup))
2654  {
2655  MemoryContextSwitchTo(oldcontext);
2656  return false;
2657  }
2658 
2659  /* Ensure we copy into caller's memory context */
2660  MemoryContextSwitchTo(oldcontext);
2661 
2662  /* Record abbreviated key for caller */
2663  if (state->sortKeys->abbrev_converter && abbrev)
2664  *abbrev = stup.datum1;
2665 
2666  if (stup.isnull1 || !state->tuples)
2667  {
2668  *val = stup.datum1;
2669  *isNull = stup.isnull1;
2670  }
2671  else
2672  {
2673  /* use stup.tuple because stup.datum1 may be an abbreviation */
2674  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2675  *isNull = false;
2676  }
2677 
2678  return true;
2679 }
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
long val
Definition: informix.c:664
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:2307

References SortTuple::datum1, datumCopy(), SortTuple::isnull1, MemoryContextSwitchTo(), PointerGetDatum, SortTuple::tuple, tuplesort_gettuple_common(), and val.

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

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2598 of file tuplesort.c.

2599 {
2600  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2601  SortTuple stup;
2602 
2603  if (!tuplesort_gettuple_common(state, forward, &stup))
2604  stup.tuple = NULL;
2605 
2606  MemoryContextSwitchTo(oldcontext);
2607 
2608  return stup.tuple;
2609 }

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

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2618 of file tuplesort.c.

2619 {
2620  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2621  SortTuple stup;
2622 
2623  if (!tuplesort_gettuple_common(state, forward, &stup))
2624  stup.tuple = NULL;
2625 
2626  MemoryContextSwitchTo(oldcontext);
2627 
2628  return (IndexTuple) stup.tuple;
2629 }

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

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

◆ tuplesort_gettuple_common()

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

Definition at line 2307 of file tuplesort.c.

2309 {
2310  unsigned int tuplen;
2311  size_t nmoved;
2312 
2313  Assert(!WORKER(state));
2314 
2315  switch (state->status)
2316  {
2317  case TSS_SORTEDINMEM:
2318  Assert(forward || state->sortopt & TUPLESORT_RANDOMACCESS);
2319  Assert(!state->slabAllocatorUsed);
2320  if (forward)
2321  {
2322  if (state->current < state->memtupcount)
2323  {
2324  *stup = state->memtuples[state->current++];
2325  return true;
2326  }
2327  state->eof_reached = true;
2328 
2329  /*
2330  * Complain if caller tries to retrieve more tuples than
2331  * originally asked for in a bounded sort. This is because
2332  * returning EOF here might be the wrong thing.
2333  */
2334  if (state->bounded && state->current >= state->bound)
2335  elog(ERROR, "retrieved too many tuples in a bounded sort");
2336 
2337  return false;
2338  }
2339  else
2340  {
2341  if (state->current <= 0)
2342  return false;
2343 
2344  /*
2345  * if all tuples are fetched already then we return last
2346  * tuple, else - tuple before last returned.
2347  */
2348  if (state->eof_reached)
2349  state->eof_reached = false;
2350  else
2351  {
2352  state->current--; /* last returned tuple */
2353  if (state->current <= 0)
2354  return false;
2355  }
2356  *stup = state->memtuples[state->current - 1];
2357  return true;
2358  }
2359  break;
2360 
2361  case TSS_SORTEDONTAPE:
2362  Assert(forward || state->sortopt & TUPLESORT_RANDOMACCESS);
2363  Assert(state->slabAllocatorUsed);
2364 
2365  /*
2366  * The slot that held the tuple that we returned in previous
2367  * gettuple call can now be reused.
2368  */
2369  if (state->lastReturnedTuple)
2370  {
2371  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
2372  state->lastReturnedTuple = NULL;
2373  }
2374 
2375  if (forward)
2376  {
2377  if (state->eof_reached)
2378  return false;
2379 
2380  if ((tuplen = getlen(state->result_tape, true)) != 0)
2381  {
2382  READTUP(state, stup, state->result_tape, tuplen);
2383 
2384  /*
2385  * Remember the tuple we return, so that we can recycle
2386  * its memory on next call. (This can be NULL, in the
2387  * !state->tuples case).
2388  */
2389  state->lastReturnedTuple = stup->tuple;
2390 
2391  return true;
2392  }
2393  else
2394  {
2395  state->eof_reached = true;
2396  return false;
2397  }
2398  }
2399 
2400  /*
2401  * Backward.
2402  *
2403  * if all tuples are fetched already then we return last tuple,
2404  * else - tuple before last returned.
2405  */
2406  if (state->eof_reached)
2407  {
2408  /*
2409  * Seek position is pointing just past the zero tuplen at the
2410  * end of file; back up to fetch last tuple's ending length
2411  * word. If seek fails we must have a completely empty file.
2412  */
2413  nmoved = LogicalTapeBackspace(state->result_tape,
2414  2 * sizeof(unsigned int));
2415  if (nmoved == 0)
2416  return false;
2417  else if (nmoved != 2 * sizeof(unsigned int))
2418  elog(ERROR, "unexpected tape position");
2419  state->eof_reached = false;
2420  }
2421  else
2422  {
2423  /*
2424  * Back up and fetch previously-returned tuple's ending length
2425  * word. If seek fails, assume we are at start of file.
2426  */
2427  nmoved = LogicalTapeBackspace(state->result_tape,
2428  sizeof(unsigned int));
2429  if (nmoved == 0)
2430  return false;
2431  else if (nmoved != sizeof(unsigned int))
2432  elog(ERROR, "unexpected tape position");
2433  tuplen = getlen(state->result_tape, false);
2434 
2435  /*
2436  * Back up to get ending length word of tuple before it.
2437  */
2438  nmoved = LogicalTapeBackspace(state->result_tape,
2439  tuplen + 2 * sizeof(unsigned int));
2440  if (nmoved == tuplen + sizeof(unsigned int))
2441  {
2442  /*
2443  * We backed up over the previous tuple, but there was no
2444  * ending length word before it. That means that the prev
2445  * tuple is the first tuple in the file. It is now the
2446  * next to read in forward direction (not obviously right,
2447  * but that is what in-memory case does).
2448  */
2449  return false;
2450  }
2451  else if (nmoved != tuplen + 2 * sizeof(unsigned int))
2452  elog(ERROR, "bogus tuple length in backward scan");
2453  }
2454 
2455  tuplen = getlen(state->result_tape, false);
2456 
2457  /*
2458  * Now we have the length of the prior tuple, back up and read it.
2459  * Note: READTUP expects we are positioned after the initial
2460  * length word of the tuple, so back up to that point.
2461  */
2462  nmoved = LogicalTapeBackspace(state->result_tape,
2463  tuplen);
2464  if (nmoved != tuplen)
2465  elog(ERROR, "bogus tuple length in backward scan");
2466  READTUP(state, stup, state->result_tape, tuplen);
2467 
2468  /*
2469  * Remember the tuple we return, so that we can recycle its memory
2470  * on next call. (This can be NULL, in the Datum case).
2471  */
2472  state->lastReturnedTuple = stup->tuple;
2473 
2474  return true;
2475 
2476  case TSS_FINALMERGE:
2477  Assert(forward);
2478  /* We are managing memory ourselves, with the slab allocator. */
2479  Assert(state->slabAllocatorUsed);
2480 
2481  /*
2482  * The slab slot holding the tuple that we returned in previous
2483  * gettuple call can now be reused.
2484  */
2485  if (state->lastReturnedTuple)
2486  {
2487  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
2488  state->lastReturnedTuple = NULL;
2489  }
2490 
2491  /*
2492  * This code should match the inner loop of mergeonerun().
2493  */
2494  if (state->memtupcount > 0)
2495  {
2496  int srcTapeIndex = state->memtuples[0].srctape;
2497  LogicalTape *srcTape = state->inputTapes[srcTapeIndex];
2498  SortTuple newtup;
2499 
2500  *stup = state->memtuples[0];
2501 
2502  /*
2503  * Remember the tuple we return, so that we can recycle its
2504  * memory on next call. (This can be NULL, in the Datum case).
2505  */
2506  state->lastReturnedTuple = stup->tuple;
2507 
2508  /*
2509  * Pull next tuple from tape, and replace the returned tuple
2510  * at top of the heap with it.
2511  */
2512  if (!mergereadnext(state, srcTape, &newtup))
2513  {
2514  /*
2515  * If no more data, we've reached end of run on this tape.
2516  * Remove the top node from the heap.
2517  */
2519  state->nInputRuns--;
2520 
2521  /*
2522  * Close the tape. It'd go away at the end of the sort
2523  * anyway, but better to release the memory early.
2524  */
2525  LogicalTapeClose(srcTape);
2526  return true;
2527  }
2528  newtup.srctape = srcTapeIndex;
2530  return true;
2531  }
2532  return false;
2533 
2534  default:
2535  elog(ERROR, "invalid tuplesort state");
2536  return false; /* keep compiler quiet */
2537  }
2538 }
size_t LogicalTapeBackspace(LogicalTape *lt, size_t size)
Definition: logtape.c:1063

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

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

◆ tuplesort_gettupleslot()

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

Definition at line 2561 of file tuplesort.c.

2563 {
2564  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2565  SortTuple stup;
2566 
2567  if (!tuplesort_gettuple_common(state, forward, &stup))
2568  stup.tuple = NULL;
2569 
2570  MemoryContextSwitchTo(oldcontext);
2571 
2572  if (stup.tuple)
2573  {
2574  /* Record abbreviated key for caller */
2575  if (state->sortKeys->abbrev_converter && abbrev)
2576  *abbrev = stup.datum1;
2577 
2578  if (copy)
2580 
2581  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
2582  return true;
2583  }
2584  else
2585  {
2586  ExecClearTuple(slot);
2587  return false;
2588  }
2589 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1446
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1439
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:425

References SortTuple::datum1, ExecClearTuple(), ExecStoreMinimalTuple(), heap_copy_minimal_tuple(), MemoryContextSwitchTo(), SortTuple::tuple, and tuplesort_gettuple_common().

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

◆ tuplesort_heap_delete_top()

static void tuplesort_heap_delete_top ( Tuplesortstate state)
static

Definition at line 3751 of file tuplesort.c.

3752 {
3753  SortTuple *memtuples = state->memtuples;
3754  SortTuple *tuple;
3755 
3756  if (--state->memtupcount <= 0)
3757  return;
3758 
3759  /*
3760  * Remove the last tuple in the heap, and re-insert it, by replacing the
3761  * current top node with it.
3762  */
3763  tuple = &memtuples[state->memtupcount];
3765 }

References tuplesort_heap_replace_top().

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

◆ tuplesort_heap_insert()

static void tuplesort_heap_insert ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 3716 of file tuplesort.c.

3717 {
3718  SortTuple *memtuples;
3719  int j;
3720 
3721  memtuples = state->memtuples;
3722  Assert(state->memtupcount < state->memtupsize);
3723 
3725 
3726  /*
3727  * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
3728  * using 1-based array indexes, not 0-based.
3729  */
3730  j = state->memtupcount++;
3731  while (j > 0)
3732  {
3733  int i = (j - 1) >> 1;
3734 
3735  if (COMPARETUP(state, tuple, &memtuples[i]) >= 0)
3736  break;
3737  memtuples[j] = memtuples[i];
3738  j = i;
3739  }
3740  memtuples[j] = *tuple;
3741 }

References Assert(), CHECK_FOR_INTERRUPTS, COMPARETUP, i, and j.

Referenced by beginmerge(), and make_bounded_heap().

◆ tuplesort_heap_replace_top()

static void tuplesort_heap_replace_top ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 3775 of file tuplesort.c.

3776 {
3777  SortTuple *memtuples = state->memtuples;
3778  unsigned int i,
3779  n;
3780 
3781  Assert(state->memtupcount >= 1);
3782 
3784 
3785  /*
3786  * state->memtupcount is "int", but we use "unsigned int" for i, j, n.
3787  * This prevents overflow in the "2 * i + 1" calculation, since at the top
3788  * of the loop we must have i < n <= INT_MAX <= UINT_MAX/2.
3789  */
3790  n = state->memtupcount;
3791  i = 0; /* i is where the "hole" is */
3792  for (;;)
3793  {
3794  unsigned int j = 2 * i + 1;
3795 
3796  if (j >= n)
3797  break;
3798  if (j + 1 < n &&
3799  COMPARETUP(state, &memtuples[j], &memtuples[j + 1]) > 0)
3800  j++;
3801  if (COMPARETUP(state, tuple, &memtuples[j]) <= 0)
3802  break;
3803  memtuples[i] = memtuples[j];
3804  i = j;
3805  }
3806  memtuples[i] = *tuple;
3807 }

References Assert(), CHECK_FOR_INTERRUPTS, COMPARETUP, i, and j.

Referenced by make_bounded_heap(), mergeonerun(), puttuple_common(), tuplesort_gettuple_common(), and tuplesort_heap_delete_top().

◆ tuplesort_initialize_shared()

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

Definition at line 4698 of file tuplesort.c.

4699 {
4700  int i;
4701 
4702  Assert(nWorkers > 0);
4703 
4704  SpinLockInit(&shared->mutex);
4705  shared->currentWorker = 0;
4706  shared->workersFinished = 0;
4707  SharedFileSetInit(&shared->fileset, seg);
4708  shared->nTapes = nWorkers;
4709  for (i = 0; i < nWorkers; i++)
4710  {
4711  shared->tapes[i].firstblocknumber = 0L;
4712  }
4713 }
void SharedFileSetInit(SharedFileSet *fileset, dsm_segment *seg)
Definition: sharedfileset.c:44
#define SpinLockInit(lock)
Definition: spin.h:60
int nTapes
Definition: tuplesort.c:519
int currentWorker
Definition: tuplesort.c:512
long firstblocknumber
Definition: logtape.h:54

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

Referenced by _bt_begin_parallel().

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

Definition at line 3412 of file tuplesort.c.

3413 {
3414  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3415 
3416  Assert(state->sortopt & TUPLESORT_RANDOMACCESS);
3417 
3418  switch (state->status)
3419  {
3420  case TSS_SORTEDINMEM:
3421  state->markpos_offset = state->current;
3422  state->markpos_eof = state->eof_reached;
3423  break;
3424  case TSS_SORTEDONTAPE:
3425  LogicalTapeTell(state->result_tape,
3426  &state->markpos_block,
3427  &state->markpos_offset);
3428  state->markpos_eof = state->eof_reached;
3429  break;
3430  default:
3431  elog(ERROR, "invalid tuplesort state");
3432  break;
3433  }
3434 
3435  MemoryContextSwitchTo(oldcontext);
3436 }
void LogicalTapeTell(LogicalTape *lt, long *blocknum, int *offset)
Definition: logtape.c:1163

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

Referenced by ExecSortMarkPos().

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2755 of file tuplesort.c.

2756 {
2757  int mOrder;
2758 
2759  /*----------
2760  * In the merge phase, we need buffer space for each input and output tape.
2761  * Each pass in the balanced merge algorithm reads from M input tapes, and
2762  * writes to N output tapes. Each tape consumes TAPE_BUFFER_OVERHEAD bytes
2763  * of memory. In addition to that, we want MERGE_BUFFER_SIZE workspace per
2764  * input tape.
2765  *
2766  * totalMem = M * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE) +
2767  * N * TAPE_BUFFER_OVERHEAD
2768  *
2769  * Except for the last and next-to-last merge passes, where there can be
2770  * fewer tapes left to process, M = N. We choose M so that we have the
2771  * desired amount of memory available for the input buffers
2772  * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE), given the total memory
2773  * available for the tape buffers (allowedMem).
2774  *
2775  * Note: you might be thinking we need to account for the memtuples[]
2776  * array in this calculation, but we effectively treat that as part of the
2777  * MERGE_BUFFER_SIZE workspace.
2778  *----------
2779  */
2780  mOrder = allowedMem /
2782 
2783  /*
2784  * Even in minimum memory, use at least a MINORDER merge. On the other
2785  * hand, even when we have lots of memory, do not use more than a MAXORDER
2786  * merge. Tapes are pretty cheap, but they're not entirely free. Each
2787  * additional tape reduces the amount of memory available to build runs,
2788  * which in turn can cause the same sort to need more runs, which makes
2789  * merging slower even if it can still be done in a single pass. Also,
2790  * high order merges are quite slow due to CPU cache effects; it can be
2791  * faster to pay the I/O cost of a multi-pass merge than to perform a
2792  * single merge pass across many hundreds of tapes.
2793  */
2794  mOrder = Max(mOrder, MINORDER);
2795  mOrder = Min(mOrder, MAXORDER);
2796 
2797  return mOrder;
2798 }
#define MAXORDER
Definition: tuplesort.c:235
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:237

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

Referenced by cost_tuplesort(), and inittapes().

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

Definition at line 3520 of file tuplesort.c.

3521 {
3522  switch (m)
3523  {
3525  return "still in progress";
3527  return "top-N heapsort";
3528  case SORT_TYPE_QUICKSORT:
3529  return "quicksort";
3531  return "external sort";
3533  return "external merge";
3534  }
3535 
3536  return "unknown";
3537 }

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

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

Definition at line 2196 of file tuplesort.c.

2197 {
2198  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2199 
2200 #ifdef TRACE_SORT
2201  if (trace_sort)
2202  elog(LOG, "performsort of worker %d starting: %s",
2203  state->worker, pg_rusage_show(&state->ru_start));
2204 #endif
2205 
2206  switch (state->status)
2207  {
2208  case TSS_INITIAL:
2209 
2210  /*
2211  * We were able to accumulate all the tuples within the allowed
2212  * amount of memory, or leader to take over worker tapes
2213  */
2214  if (SERIAL(state))
2215  {
2216  /* Just qsort 'em and we're done */
2218  state->status = TSS_SORTEDINMEM;
2219  }
2220  else if (WORKER(state))
2221  {
2222  /*
2223  * Parallel workers must still dump out tuples to tape. No
2224  * merge is required to produce single output run, though.
2225  */
2226  inittapes(state, false);
2227  dumptuples(state, true);
2229  state->status = TSS_SORTEDONTAPE;
2230  }
2231  else
2232  {
2233  /*
2234  * Leader will take over worker tapes and merge worker runs.
2235  * Note that mergeruns sets the correct state->status.
2236  */
2238  mergeruns(state);
2239  }
2240  state->current = 0;
2241  state->eof_reached = false;
2242  state->markpos_block = 0L;
2243  state->markpos_offset = 0;
2244  state->markpos_eof = false;
2245  break;
2246 
2247  case TSS_BOUNDED:
2248 
2249  /*
2250  * We were able to accumulate all the tuples required for output
2251  * in memory, using a heap to eliminate excess tuples. Now we
2252  * have to transform the heap to a properly-sorted array.
2253  */
2255  state->current = 0;
2256  state->eof_reached = false;
2257  state->markpos_offset = 0;
2258  state->markpos_eof = false;
2259  state->status = TSS_SORTEDINMEM;
2260  break;
2261 
2262  case TSS_BUILDRUNS:
2263 
2264  /*
2265  * Finish tape-based sort. First, flush all tuples remaining in
2266  * memory out to tape; then merge until we have a single remaining
2267  * run (or, if !randomAccess and !WORKER(), one run per tape).
2268  * Note that mergeruns sets the correct state->status.
2269  */
2270  dumptuples(state, true);
2271  mergeruns(state);
2272  state->eof_reached = false;
2273  state->markpos_block = 0L;
2274  state->markpos_offset = 0;
2275  state->markpos_eof = false;
2276  break;
2277 
2278  default:
2279  elog(ERROR, "invalid tuplesort state");
2280  break;
2281  }
2282 
2283 #ifdef TRACE_SORT
2284  if (trace_sort)
2285  {
2286  if (state->status == TSS_FINALMERGE)
2287  elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
2288  state->worker, state->nInputTapes,
2289  pg_rusage_show(&state->ru_start));
2290  else
2291  elog(LOG, "performsort of worker %d done: %s",
2292  state->worker, pg_rusage_show(&state->ru_start));
2293  }
2294 #endif
2295 
2296  MemoryContextSwitchTo(oldcontext);
2297 }
static void sort_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3613
static void leader_takeover_tapes(Tuplesortstate *state)
Definition: tuplesort.c:4829
static void worker_nomergeruns(Tuplesortstate *state)
Definition: tuplesort.c:4807

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

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

◆ tuplesort_putdatum()

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

Definition at line 1961 of file tuplesort.c.

1962 {
1963  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1964  SortTuple stup;
1965 
1966  /*
1967  * Pass-by-value types or null values are just stored directly in
1968  * stup.datum1 (and stup.tuple is not used and set to NULL).
1969  *
1970  * Non-null pass-by-reference values need to be copied into memory we
1971  * control, and possibly abbreviated. The copied value is pointed to by
1972  * stup.tuple and is treated as the canonical copy (e.g. to return via
1973  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
1974  * abbreviated value if abbreviation is happening, otherwise it's
1975  * identical to stup.tuple.
1976  */
1977 
1978  if (isNull || !state->tuples)
1979  {
1980  /*
1981  * Set datum1 to zeroed representation for NULLs (to be consistent,
1982  * and to support cheap inequality tests for NULL abbreviated keys).
1983  */
1984  stup.datum1 = !isNull ? val : (Datum) 0;
1985  stup.isnull1 = isNull;
1986  stup.tuple = NULL; /* no separate storage */
1987  MemoryContextSwitchTo(state->sortcontext);
1988  }
1989  else
1990  {
1991  Datum original = datumCopy(val, false, state->datumTypeLen);
1992 
1993  stup.isnull1 = false;
1994  stup.tuple = DatumGetPointer(original);
1996  MemoryContextSwitchTo(state->sortcontext);
1997 
1998  if (!state->sortKeys->abbrev_converter)
1999  {
2000  stup.datum1 = original;
2001  }
2002  else if (!consider_abort_common(state))
2003  {
2004  /* Store abbreviated key representation */
2005  stup.datum1 = state->sortKeys->abbrev_converter(original,
2006  state->sortKeys);
2007  }
2008  else
2009  {
2010  /* Abort abbreviation */
2011  int i;
2012 
2013  stup.datum1 = original;
2014 
2015  /*
2016  * Set state to be consistent with never trying abbreviation.
2017  *
2018  * Alter datum1 representation in already-copied tuples, so as to
2019  * ensure a consistent representation (current tuple was just
2020  * handled). It does not matter if some dumped tuples are already
2021  * sorted on tape, since serialized tuples lack abbreviated keys
2022  * (TSS_BUILDRUNS state prevents control reaching here in any
2023  * case).
2024  */
2025  for (i = 0; i < state->memtupcount; i++)
2026  {
2027  SortTuple *mtup = &state->memtuples[i];
2028 
2029  mtup->datum1 = PointerGetDatum(mtup->tuple);
2030  }
2031  }
2032  }
2033 
2034  puttuple_common(state, &stup);
2035 
2036  MemoryContextSwitchTo(oldcontext);
2037 }
#define DatumGetPointer(X)
Definition: postgres.h:593
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:2043

References consider_abort_common(), SortTuple::datum1, datumCopy(), DatumGetPointer, GetMemoryChunkSpace(), i, SortTuple::isnull1, MemoryContextSwitchTo(), PointerGetDatum, puttuple_common(), SortTuple::tuple, USEMEM, and val.

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

◆ tuplesort_putheaptuple()

void tuplesort_putheaptuple ( Tuplesortstate state,
HeapTuple  tup 
)

Definition at line 1862 of file tuplesort.c.

1863 {
1864  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1865  SortTuple stup;
1866 
1867  /*
1868  * Copy the given tuple into memory we control, and decrease availMem.
1869  * Then call the common code.
1870  */
1871  COPYTUP(state, &stup, (void *) tup);
1872 
1873  puttuple_common(state, &stup);
1874 
1875  MemoryContextSwitchTo(oldcontext);
1876 }
#define COPYTUP(state, stup, tup)
Definition: tuplesort.c:552

References COPYTUP, MemoryContextSwitchTo(), and puttuple_common().

Referenced by heapam_relation_copy_for_cluster().

◆ tuplesort_putindextuplevalues()

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

Definition at line 1883 of file tuplesort.c.

1886 {
1887  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
1888  SortTuple stup;
1889  Datum original;
1890  IndexTuple tuple;
1891 
1892  stup.tuple = index_form_tuple(RelationGetDescr(rel), values, isnull);
1893  tuple = ((IndexTuple) stup.tuple);
1894  tuple->t_tid = *self;
1896  /* set up first-column key value */
1897  original = index_getattr(tuple,
1898  1,
1899  RelationGetDescr(state->indexRel),
1900  &stup.isnull1);
1901 
1902  MemoryContextSwitchTo(state->sortcontext);
1903 
1904  if (!state->sortKeys || !state->sortKeys->abbrev_converter || stup.isnull1)
1905  {
1906  /*
1907  * Store ordinary Datum representation, or NULL value. If there is a
1908  * converter it won't expect NULL values, and cost model is not
1909  * required to account for NULL, so in that case we avoid calling
1910  * converter and just set datum1 to zeroed representation (to be
1911  * consistent, and to support cheap inequality tests for NULL
1912  * abbreviated keys).
1913  */
1914  stup.datum1 = original;
1915  }
1916  else if (!consider_abort_common(state))
1917  {
1918  /* Store abbreviated key representation */
1919  stup.datum1 = state->sortKeys->abbrev_converter(original,
1920  state->sortKeys);
1921  }
1922  else
1923  {
1924  /* Abort abbreviation */
1925  int i;
1926 
1927  stup.datum1 = original;
1928 
1929  /*
1930  * Set state to be consistent with never trying abbreviation.
1931  *
1932  * Alter datum1 representation in already-copied tuples, so as to
1933  * ensure a consistent representation (current tuple was just
1934  * handled). It does not matter if some dumped tuples are already
1935  * sorted on tape, since serialized tuples lack abbreviated keys
1936  * (TSS_BUILDRUNS state prevents control reaching here in any case).
1937  */
1938  for (i = 0; i < state->memtupcount; i++)
1939  {
1940  SortTuple *mtup = &state->memtuples[i];
1941 
1942  tuple = mtup->tuple;
1943  mtup->datum1 = index_getattr(tuple,
1944  1,
1945  RelationGetDescr(state->indexRel),
1946  &mtup->isnull1);
1947  }
1948  }
1949 
1950  puttuple_common(state, &stup);
1951 
1952  MemoryContextSwitchTo(oldcontext);
1953 }
IndexTuple index_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:47

References consider_abort_common(), SortTuple::datum1, GetMemoryChunkSpace(), i, index_form_tuple(), index_getattr, SortTuple::isnull1, MemoryContextSwitchTo(), puttuple_common(), RelationGetDescr, IndexTupleData::t_tid, SortTuple::tuple, USEMEM, and values.

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

◆ tuplesort_puttupleslot()

void tuplesort_puttupleslot ( Tuplesortstate state,
TupleTableSlot slot 
)

Definition at line 1840 of file tuplesort.c.

1841 {
1842  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1843  SortTuple stup;
1844 
1845  /*
1846  * Copy the given tuple into memory we control, and decrease availMem.
1847  * Then call the common code.
1848  */
1849  COPYTUP(state, &stup, (void *) slot);
1850 
1851  puttuple_common(state, &stup);
1852 
1853  MemoryContextSwitchTo(oldcontext);
1854 }

References COPYTUP, MemoryContextSwitchTo(), and puttuple_common().

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

◆ tuplesort_rescan()

void tuplesort_rescan ( Tuplesortstate state)

Definition at line 3379 of file tuplesort.c.

3380 {
3381  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3382 
3383  Assert(state->sortopt & TUPLESORT_RANDOMACCESS);
3384 
3385  switch (state->status)
3386  {
3387  case TSS_SORTEDINMEM:
3388  state->current = 0;
3389  state->eof_reached = false;
3390  state->markpos_offset = 0;
3391  state->markpos_eof = false;
3392  break;
3393  case TSS_SORTEDONTAPE:
3394  LogicalTapeRewindForRead(state->result_tape, 0);
3395  state->eof_reached = false;
3396  state->markpos_block = 0L;
3397  state->markpos_offset = 0;
3398  state->markpos_eof = false;
3399  break;
3400  default:
3401  elog(ERROR, "invalid tuplesort state");
3402  break;
3403  }
3404 
3405  MemoryContextSwitchTo(oldcontext);
3406 }

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

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

◆ tuplesort_reset()

void tuplesort_reset ( Tuplesortstate state)

Definition at line 1688 of file tuplesort.c.

1689 {
1692 
1693  /*
1694  * After we've freed up per-batch memory, re-setup all of the state common
1695  * to both the first batch and any subsequent batch.
1696  */
1698 
1699  state->lastReturnedTuple = NULL;
1700  state->slabMemoryBegin = NULL;
1701  state->slabMemoryEnd = NULL;
1702  state->slabFreeHead = NULL;
1703 }

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

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

◆ tuplesort_restorepos()

void tuplesort_restorepos ( Tuplesortstate state)

Definition at line 3443 of file tuplesort.c.

3444 {
3445  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
3446 
3447  Assert(state->sortopt & TUPLESORT_RANDOMACCESS);
3448 
3449  switch (state->status)
3450  {
3451  case TSS_SORTEDINMEM:
3452  state->current = state->markpos_offset;
3453  state->eof_reached = state->markpos_eof;
3454  break;
3455  case TSS_SORTEDONTAPE:
3456  LogicalTapeSeek(state->result_tape,
3457  state->markpos_block,
3458  state->markpos_offset);
3459  state->eof_reached = state->markpos_eof;
3460  break;
3461  default:
3462  elog(ERROR, "invalid tuplesort state");
3463  break;
3464  }
3465 
3466  MemoryContextSwitchTo(oldcontext);
3467 }
void LogicalTapeSeek(LogicalTape *lt, long blocknum, int offset)
Definition: logtape.c:1134

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

Referenced by ExecSortRestrPos().

◆ tuplesort_set_bound()

void tuplesort_set_bound ( Tuplesortstate state,
int64  bound 
)

Definition at line 1484 of file tuplesort.c.

1485 {
1486  /* Assert we're called before loading any tuples */
1487  Assert(state->status == TSS_INITIAL && state->memtupcount == 0);
1488  /* Assert we allow bounded sorts */
1489  Assert(state->sortopt & TUPLESORT_ALLOWBOUNDED);
1490  /* Can't set the bound twice, either */
1491  Assert(!state->bounded);
1492  /* Also, this shouldn't be called in a parallel worker */
1493  Assert(!WORKER(state));
1494 
1495  /* Parallel leader allows but ignores hint */
1496  if (LEADER(state))
1497  return;
1498 
1499 #ifdef DEBUG_BOUNDED_SORT
1500  /* Honor GUC setting that disables the feature (for easy testing) */
1501  if (!optimize_bounded_sort)
1502  return;
1503 #endif
1504 
1505  /* We want to be able to compute bound * 2, so limit the setting */
1506  if (bound > (int64) (INT_MAX / 2))
1507  return;
1508 
1509  state->bounded = true;
1510  state->bound = (int) bound;
1511 
1512  /*
1513  * Bounded sorts are not an effective target for abbreviated key
1514  * optimization. Disable by setting state to be consistent with no
1515  * abbreviation support.
1516  */
1517  state->sortKeys->abbrev_converter = NULL;
1518  if (state->sortKeys->abbrev_full_comparator)
1519  state->sortKeys->comparator = state->sortKeys->abbrev_full_comparator;
1520 
1521  /* Not strictly necessary, but be tidy */
1522  state->sortKeys->abbrev_abort = NULL;
1523  state->sortKeys->abbrev_full_comparator = NULL;
1524 }

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

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

◆ tuplesort_skiptuples()

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

Definition at line 2687 of file tuplesort.c.

2688 {
2689  MemoryContext oldcontext;
2690 
2691  /*
2692  * We don't actually support backwards skip yet, because no callers need
2693  * it. The API is designed to allow for that later, though.
2694  */
2695  Assert(forward);
2696  Assert(ntuples >= 0);
2697  Assert(!WORKER(state));
2698 
2699  switch (state->status)
2700  {
2701  case TSS_SORTEDINMEM:
2702  if (state->memtupcount - state->current >= ntuples)
2703  {
2704  state->current += ntuples;
2705  return true;
2706  }
2707  state->current = state->memtupcount;
2708  state->eof_reached = true;
2709 
2710  /*
2711  * Complain if caller tries to retrieve more tuples than
2712  * originally asked for in a bounded sort. This is because
2713  * returning EOF here might be the wrong thing.
2714  */
2715  if (state->bounded && state->current >= state->bound)
2716  elog(ERROR, "retrieved too many tuples in a bounded sort");
2717 
2718  return false;
2719 
2720  case TSS_SORTEDONTAPE:
2721  case TSS_FINALMERGE:
2722 
2723  /*
2724  * We could probably optimize these cases better, but for now it's
2725  * not worth the trouble.
2726  */
2727  oldcontext = MemoryContextSwitchTo(state->sortcontext);
2728  while (ntuples-- > 0)
2729  {
2730  SortTuple stup;
2731 
2732  if (!tuplesort_gettuple_common(state, forward, &stup))
2733  {
2734  MemoryContextSwitchTo(oldcontext);
2735  return false;
2736  }
2738  }
2739  MemoryContextSwitchTo(oldcontext);
2740  return true;
2741 
2742  default:
2743  elog(ERROR, "invalid tuplesort state");
2744  return false; /* keep compiler quiet */
2745  }
2746 }

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

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

◆ tuplesort_sort_memtuples()

static void tuplesort_sort_memtuples ( Tuplesortstate state)
static

Definition at line 3653 of file tuplesort.c.

3654 {
3655  Assert(!LEADER(state));
3656 
3657  if (state->memtupcount > 1)
3658  {
3659  /*
3660  * Do we have the leading column's value or abbreviation in datum1,
3661  * and is there a specialization for its comparator?
3662  */
3663  if (state->haveDatum1 && state->sortKeys)
3664  {
3665  if (state->sortKeys[0].comparator == ssup_datum_unsigned_cmp)
3666  {
3667  qsort_tuple_unsigned(state->memtuples,
3668  state->memtupcount,
3669  state);
3670  return;
3671  }
3672 #if SIZEOF_DATUM >= 8
3673  else if (state->sortKeys[0].comparator == ssup_datum_signed_cmp)
3674  {
3675  qsort_tuple_signed(state->memtuples,
3676  state->memtupcount,
3677  state);
3678  return;
3679  }
3680 #endif
3681  else if (state->sortKeys[0].comparator == ssup_datum_int32_cmp)
3682  {
3683  qsort_tuple_int32(state->memtuples,
3684  state->memtupcount,
3685  state);
3686  return;
3687  }
3688  }
3689 
3690  /* Can we use the single-key sort function? */
3691  if (state->onlyKey != NULL)
3692  {
3693  qsort_ssup(state->memtuples, state->memtupcount,
3694  state->onlyKey);
3695  }
3696  else
3697  {
3698  qsort_tuple(state->memtuples,
3699  state->memtupcount,
3700  state->comparetup,
3701  state);
3702  }
3703  }
3704 }
int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup)
Definition: tuplesort.c:4899
int ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup)
Definition: tuplesort.c:4926

References Assert(), LEADER, ssup_datum_int32_cmp(), and ssup_datum_unsigned_cmp().

Referenced by dumptuples(), and tuplesort_performsort().

◆ tuplesort_space_type_name()

const char* tuplesort_space_type_name ( TuplesortSpaceType  t)

Definition at line 3543 of file tuplesort.c.

3544 {
3546  return t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
3547 }

References Assert(), SORT_SPACE_TYPE_DISK, and SORT_SPACE_TYPE_MEMORY.

Referenced by show_incremental_sort_group_info(), and show_sort_info().

◆ tuplesort_updatemax()

static void tuplesort_updatemax ( Tuplesortstate state)
static

Definition at line 1637 of file tuplesort.c.

1638 {
1639  int64 spaceUsed;
1640  bool isSpaceDisk;
1641 
1642  /*
1643  * Note: it might seem we should provide both memory and disk usage for a
1644  * disk-based sort. However, the current code doesn't track memory space
1645  * accurately once we have begun to return tuples to the caller (since we
1646  * don't account for pfree's the caller is expected to do), so we cannot
1647  * rely on availMem in a disk sort. This does not seem worth the overhead
1648  * to fix. Is it worth creating an API for the memory context code to
1649  * tell us how much is actually used in sortcontext?
1650  */
1651  if (state->tapeset)
1652  {
1653  isSpaceDisk = true;
1654  spaceUsed = LogicalTapeSetBlocks(state->tapeset) * BLCKSZ;
1655  }
1656  else
1657  {
1658  isSpaceDisk = false;
1659  spaceUsed = state->allowedMem - state->availMem;
1660  }
1661 
1662  /*
1663  * Sort evicts data to the disk when it wasn't able to fit that data into
1664  * main memory. This is why we assume space used on the disk to be more
1665  * important for tracking resource usage than space used in memory. Note
1666  * that the amount of space occupied by some tupleset on the disk might be
1667  * less than amount of space occupied by the same tupleset in memory due
1668  * to more compact representation.
1669  */
1670  if ((isSpaceDisk && !state->isMaxSpaceDisk) ||
1671  (isSpaceDisk == state->isMaxSpaceDisk && spaceUsed > state->maxSpace))
1672  {
1673  state->maxSpace = spaceUsed;
1674  state->isMaxSpaceDisk = isSpaceDisk;
1675  state->maxSpaceStatus = state->status;
1676  }
1677 }

References LogicalTapeSetBlocks().

Referenced by tuplesort_get_stats(), and tuplesort_reset().

◆ tuplesort_used_bound()

bool tuplesort_used_bound ( Tuplesortstate state)

Definition at line 1532 of file tuplesort.c.

1533 {
1534  return state->boundUsed;
1535 }

Referenced by ExecIncrementalSort().

◆ worker_freeze_result_tape()

static void worker_freeze_result_tape ( Tuplesortstate state)
static

Definition at line 4769 of file tuplesort.c.

4770 {
4771  Sharedsort *shared = state->shared;
4772  TapeShare output;
4773 
4774  Assert(WORKER(state));
4775  Assert(state->result_tape != NULL);
4776  Assert(state->memtupcount == 0);
4777 
4778  /*
4779  * Free most remaining memory, in case caller is sensitive to our holding
4780  * on to it. memtuples may not be a tiny merge heap at this point.
4781  */
4782  pfree(state->memtuples);
4783  /* Be tidy */
4784  state->memtuples = NULL;
4785  state->memtupsize = 0;
4786 
4787  /*
4788  * Parallel worker requires result tape metadata, which is to be stored in
4789  * shared memory for leader
4790  */
4791  LogicalTapeFreeze(state->result_tape, &output);
4792 
4793  /* Store properties of output tape, and update finished worker count */
4794  SpinLockAcquire(&shared->mutex);
4795  shared->tapes[state->worker] = output;
4796  shared->workersFinished++;
4797  SpinLockRelease(&shared->mutex);
4798 }
static void output(uint64 loop_count)

References Assert(), LogicalTapeFreeze(), Sharedsort::mutex, output(), pfree(), SpinLockAcquire, SpinLockRelease, Sharedsort::tapes, WORKER, and Sharedsort::workersFinished.

Referenced by mergeruns(), and worker_nomergeruns().

◆ worker_get_identifier()

static int worker_get_identifier ( Tuplesortstate state)
static

Definition at line 4741 of file tuplesort.c.

4742 {
4743  Sharedsort *shared = state->shared;
4744  int worker;
4745 
4746  Assert(WORKER(state));
4747 
4748  SpinLockAcquire(&shared->mutex);
4749  worker = shared->currentWorker++;
4750  SpinLockRelease(&shared->mutex);
4751 
4752  return worker;
4753 }

References Assert(), Sharedsort::currentWorker, Sharedsort::mutex, SpinLockAcquire, SpinLockRelease, and WORKER.

Referenced by tuplesort_begin_common().

◆ worker_nomergeruns()

static void worker_nomergeruns ( Tuplesortstate state)
static

Definition at line 4807 of file tuplesort.c.

4808 {
4809  Assert(WORKER(state));
4810  Assert(state->result_tape == NULL);
4811  Assert(state->nOutputRuns == 1);
4812 
4813  state->result_tape = state->destTape;
4815 }

References Assert(), WORKER, and worker_freeze_result_tape().

Referenced by tuplesort_performsort().

◆ writetup_cluster()

static void writetup_cluster ( Tuplesortstate state,
LogicalTape tape,
SortTuple stup 
)
static

Definition at line 4269 of file tuplesort.c.

4270 {
4271  HeapTuple tuple = (HeapTuple) stup->tuple;
4272  unsigned int tuplen = tuple->t_len + sizeof(ItemPointerData) + sizeof(int);
4273 
4274  /* We need to store t_self, but not other fields of HeapTupleData */
4275  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
4276  LogicalTapeWrite(tape, &tuple->t_self, sizeof(ItemPointerData));
4277  LogicalTapeWrite(tape, tuple->t_data, tuple->t_len);
4278  if (state->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length
4279  * word? */
4280  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
4281 
4282  if (!state->slabAllocatorUsed)
4283  {
4285  heap_freetuple(tuple);
4286  }
4287 }
void heap_freetuple(HeapTuple htup)
Definition: heaptuple.c:1338

References FREEMEM, GetMemoryChunkSpace(), heap_freetuple(), LogicalTapeWrite(), HeapTupleData::t_data, HeapTupleData::t_len, HeapTupleData::t_self, SortTuple::tuple, and TUPLESORT_RANDOMACCESS.

Referenced by tuplesort_begin_cluster().

◆ writetup_datum()

static void writetup_datum ( Tuplesortstate state,
LogicalTape tape,
SortTuple stup 
)
static

Definition at line 4593 of file tuplesort.c.

4594 {
4595  void *waddr;
4596  unsigned int tuplen;
4597  unsigned int writtenlen;
4598 
4599  if (stup->isnull1)
4600  {
4601  waddr = NULL;
4602  tuplen = 0;
4603  }
4604  else if (!state->tuples)
4605  {
4606  waddr = &stup->datum1;
4607  tuplen = sizeof(Datum);
4608  }
4609  else
4610  {
4611  waddr = stup->tuple;
4612  tuplen = datumGetSize(PointerGetDatum(stup->tuple), false, state->datumTypeLen);
4613  Assert(tuplen != 0);
4614  }
4615 
4616  writtenlen = tuplen + sizeof(unsigned int);
4617 
4618  LogicalTapeWrite(tape, (void *) &writtenlen, sizeof(writtenlen));
4619  LogicalTapeWrite(tape, waddr, tuplen);
4620  if (state->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length
4621  * word? */
4622  LogicalTapeWrite(tape, (void *) &writtenlen, sizeof(writtenlen));
4623 
4624  if (!state->slabAllocatorUsed && stup->tuple)
4625  {
4627  pfree(stup->tuple);
4628  }
4629 }
Size datumGetSize(Datum value, bool typByVal, int typLen)
Definition: datum.c:65

References Assert(), SortTuple::datum1, datumGetSize(), FREEMEM, GetMemoryChunkSpace(), SortTuple::isnull1, LogicalTapeWrite(), pfree(), PointerGetDatum, SortTuple::tuple, and TUPLESORT_RANDOMACCESS.

Referenced by tuplesort_begin_datum().

◆ writetup_heap()

static void writetup_heap ( Tuplesortstate state,
LogicalTape tape,
SortTuple stup 
)