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

Go to the source code of this file.

Data Structures

struct  SortTuple
 
union  SlabSlot
 
struct  Tuplesortstate
 

Macros

#define HEAP_SORT   0
 
#define INDEX_SORT   1
 
#define DATUM_SORT   2
 
#define CLUSTER_SORT   3
 
#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 LogicalTapeReadExact(tapeset, tapenum, ptr, len)
 

Typedefs

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

Enumerations

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

Functions

static Tuplesortstatetuplesort_begin_common (int workMem, bool randomAccess)
 
static void puttuple_common (Tuplesortstate *state, SortTuple *tuple)
 
static bool consider_abort_common (Tuplesortstate *state)
 
static void inittapes (Tuplesortstate *state)
 
static void selectnewtape (Tuplesortstate *state)
 
static void init_slab_allocator (Tuplesortstate *state, int numSlots)
 
static void mergeruns (Tuplesortstate *state)
 
static void mergeonerun (Tuplesortstate *state)
 
static void beginmerge (Tuplesortstate *state)
 
static bool mergereadnext (Tuplesortstate *state, int srcTape, SortTuple *stup)
 
static void dumptuples (Tuplesortstate *state, bool alltuples)
 
static void make_bounded_heap (Tuplesortstate *state)
 
static void sort_bounded_heap (Tuplesortstate *state)
 
static void tuplesort_sort_memtuples (Tuplesortstate *state)
 
static void tuplesort_heap_insert (Tuplesortstate *state, SortTuple *tuple)
 
static void tuplesort_heap_replace_top (Tuplesortstate *state, SortTuple *tuple)
 
static void tuplesort_heap_delete_top (Tuplesortstate *state)
 
static void reversedirection (Tuplesortstate *state)
 
static unsigned int getlen (Tuplesortstate *state, int tapenum, bool eofOK)
 
static void markrunend (Tuplesortstate *state, int tapenum)
 
static void * readtup_alloc (Tuplesortstate *state, Size tuplen)
 
static int comparetup_heap (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_heap (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_heap (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_heap (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static int comparetup_cluster (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_cluster (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_cluster (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_cluster (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static int comparetup_index_btree (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static int comparetup_index_hash (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_index (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_index (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_index (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static int comparetup_datum (const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
 
static void copytup_datum (Tuplesortstate *state, SortTuple *stup, void *tup)
 
static void writetup_datum (Tuplesortstate *state, int tapenum, SortTuple *stup)
 
static void readtup_datum (Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
 
static void free_sort_tuple (Tuplesortstate *state, SortTuple *stup)
 
Tuplesortstatetuplesort_begin_heap (TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, bool randomAccess)
 
Tuplesortstatetuplesort_begin_cluster (TupleDesc tupDesc, Relation indexRel, int workMem, bool randomAccess)
 
Tuplesortstatetuplesort_begin_index_btree (Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, bool randomAccess)
 
Tuplesortstatetuplesort_begin_index_hash (Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, bool randomAccess)
 
Tuplesortstatetuplesort_begin_datum (Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, bool randomAccess)
 
void tuplesort_set_bound (Tuplesortstate *state, int64 bound)
 
void tuplesort_end (Tuplesortstate *state)
 
static bool grow_memtuples (Tuplesortstate *state)
 
void tuplesort_puttupleslot (Tuplesortstate *state, TupleTableSlot *slot)
 
void tuplesort_putheaptuple (Tuplesortstate *state, HeapTuple tup)
 
void tuplesort_putindextuplevalues (Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
 
void tuplesort_putdatum (Tuplesortstate *state, Datum val, bool isNull)
 
void tuplesort_performsort (Tuplesortstate *state)
 
static bool tuplesort_gettuple_common (Tuplesortstate *state, bool forward, SortTuple *stup)
 
bool tuplesort_gettupleslot (Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
 
HeapTuple tuplesort_getheaptuple (Tuplesortstate *state, bool forward)
 
IndexTuple tuplesort_getindextuple (Tuplesortstate *state, bool forward)
 
bool tuplesort_getdatum (Tuplesortstate *state, bool forward, Datum *val, bool *isNull, Datum *abbrev)
 
bool tuplesort_skiptuples (Tuplesortstate *state, int64 ntuples, bool forward)
 
int tuplesort_merge_order (int64 allowedMem)
 
void tuplesort_rescan (Tuplesortstate *state)
 
void tuplesort_markpos (Tuplesortstate *state)
 
void tuplesort_restorepos (Tuplesortstate *state)
 
void tuplesort_get_stats (Tuplesortstate *state, TuplesortInstrumentation *stats)
 
const char * tuplesort_method_name (TuplesortMethod m)
 
const char * tuplesort_space_type_name (TuplesortSpaceType t)
 

Variables

bool trace_sort = false
 

Macro Definition Documentation

◆ CLUSTER_SORT

#define CLUSTER_SORT   3

Definition at line 114 of file tuplesort.c.

Referenced by tuplesort_begin_cluster().

◆ COMPARETUP

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

◆ COPYTUP

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

Definition at line 462 of file tuplesort.c.

Referenced by tuplesort_putheaptuple(), and tuplesort_puttupleslot().

◆ DATUM_SORT

#define DATUM_SORT   2

Definition at line 113 of file tuplesort.c.

Referenced by tuplesort_begin_datum().

◆ FREEMEM

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

◆ HEAP_SORT

#define HEAP_SORT   0

Definition at line 111 of file tuplesort.c.

Referenced by tuplesort_begin_heap().

◆ INDEX_SORT

#define INDEX_SORT   1

Definition at line 112 of file tuplesort.c.

Referenced by tuplesort_begin_index_btree().

◆ IS_SLAB_SLOT

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

Definition at line 441 of file tuplesort.c.

◆ LACKMEM

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

Definition at line 465 of file tuplesort.c.

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

◆ LogicalTapeReadExact

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

Definition at line 517 of file tuplesort.c.

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

◆ MAXORDER

#define MAXORDER   500 /* maximum merge order */

Definition at line 210 of file tuplesort.c.

Referenced by tuplesort_merge_order().

◆ MERGE_BUFFER_SIZE

#define MERGE_BUFFER_SIZE   (BLCKSZ * 32)

Definition at line 212 of file tuplesort.c.

Referenced by tuplesort_merge_order().

◆ MINORDER

#define MINORDER   6 /* minimum merge order */

Definition at line 209 of file tuplesort.c.

Referenced by tuplesort_merge_order().

◆ READTUP

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

Definition at line 464 of file tuplesort.c.

Referenced by mergereadnext(), and tuplesort_gettuple_common().

◆ RELEASE_SLAB_SLOT

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

Definition at line 449 of file tuplesort.c.

Referenced by mergeonerun(), and tuplesort_gettuple_common().

◆ SLAB_SLOT_SIZE

#define SLAB_SLOT_SIZE   1024

Definition at line 176 of file tuplesort.c.

Referenced by init_slab_allocator(), and readtup_alloc().

◆ TAPE_BUFFER_OVERHEAD

#define TAPE_BUFFER_OVERHEAD   BLCKSZ

Definition at line 211 of file tuplesort.c.

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

◆ USEMEM

◆ WRITETUP

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

Definition at line 463 of file tuplesort.c.

Referenced by dumptuples(), and mergeonerun().

Typedef Documentation

◆ SlabSlot

◆ SortTupleComparator

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

Definition at line 214 of file tuplesort.c.

Enumeration Type Documentation

◆ TupSortStatus

Enumerator
TSS_INITIAL 
TSS_BOUNDED 
TSS_BUILDRUNS 
TSS_SORTEDINMEM 
TSS_SORTEDONTAPE 
TSS_FINALMERGE 

Definition at line 188 of file tuplesort.c.

189 {
190  TSS_INITIAL, /* Loading tuples; still within memory limit */
191  TSS_BOUNDED, /* Loading tuples into bounded-size heap */
192  TSS_BUILDRUNS, /* Loading tuples; writing to tape */
193  TSS_SORTEDINMEM, /* Sort completed entirely in memory */
194  TSS_SORTEDONTAPE, /* Sort completed, final run is on tape */
195  TSS_FINALMERGE /* Performing final merge on-the-fly */
196 } TupSortStatus;
TupSortStatus
Definition: tuplesort.c:188

Function Documentation

◆ beginmerge()

static void beginmerge ( Tuplesortstate state)
static

Definition at line 2666 of file tuplesort.c.

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

Referenced by mergeonerun(), and mergeruns().

2667 {
2668  int activeTapes;
2669  int tapenum;
2670  int srcTape;
2671 
2672  /* Heap should be empty here */
2673  Assert(state->memtupcount == 0);
2674 
2675  /* Adjust run counts and mark the active tapes */
2676  memset(state->mergeactive, 0,
2677  state->maxTapes * sizeof(*state->mergeactive));
2678  activeTapes = 0;
2679  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2680  {
2681  if (state->tp_dummy[tapenum] > 0)
2682  state->tp_dummy[tapenum]--;
2683  else
2684  {
2685  Assert(state->tp_runs[tapenum] > 0);
2686  state->tp_runs[tapenum]--;
2687  srcTape = state->tp_tapenum[tapenum];
2688  state->mergeactive[srcTape] = true;
2689  activeTapes++;
2690  }
2691  }
2692  Assert(activeTapes > 0);
2693  state->activeTapes = activeTapes;
2694 
2695  /* Load the merge heap with the first tuple from each input tape */
2696  for (srcTape = 0; srcTape < state->maxTapes; srcTape++)
2697  {
2698  SortTuple tup;
2699 
2700  if (mergereadnext(state, srcTape, &tup))
2701  {
2702  tup.tupindex = srcTape;
2703  tuplesort_heap_insert(state, &tup);
2704  }
2705  }
2706 }
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3145
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2714
#define Assert(condition)
Definition: c.h:670
int tupindex
Definition: tuplesort.c:162
int * tp_dummy
Definition: tuplesort.c:359
int * tp_tapenum
Definition: tuplesort.c:360
bool * mergeactive
Definition: tuplesort.c:348

◆ comparetup_cluster()

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

Definition at line 3516 of file tuplesort.c.

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

Referenced by tuplesort_begin_cluster().

3518 {
3519  SortSupport sortKey = state->sortKeys;
3520  HeapTuple ltup;
3521  HeapTuple rtup;
3522  TupleDesc tupDesc;
3523  int nkey;
3524  int32 compare;
3525  Datum datum1,
3526  datum2;
3527  bool isnull1,
3528  isnull2;
3529  AttrNumber leading = state->indexInfo->ii_KeyAttrNumbers[0];
3530 
3531  /* Be prepared to compare additional sort keys */
3532  ltup = (HeapTuple) a->tuple;
3533  rtup = (HeapTuple) b->tuple;
3534  tupDesc = state->tupDesc;
3535 
3536  /* Compare the leading sort key, if it's simple */
3537  if (leading != 0)
3538  {
3539  compare = ApplySortComparator(a->datum1, a->isnull1,
3540  b->datum1, b->isnull1,
3541  sortKey);
3542  if (compare != 0)
3543  return compare;
3544 
3545  if (sortKey->abbrev_converter)
3546  {
3547  datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
3548  datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
3549 
3550  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3551  datum2, isnull2,
3552  sortKey);
3553  }
3554  if (compare != 0 || state->nKeys == 1)
3555  return compare;
3556  /* Compare additional columns the hard way */
3557  sortKey++;
3558  nkey = 1;
3559  }
3560  else
3561  {
3562  /* Must compare all keys the hard way */
3563  nkey = 0;
3564  }
3565 
3566  if (state->indexInfo->ii_Expressions == NULL)
3567  {
3568  /* If not expression index, just compare the proper heap attrs */
3569 
3570  for (; nkey < state->nKeys; nkey++, sortKey++)
3571  {
3572  AttrNumber attno = state->indexInfo->ii_KeyAttrNumbers[nkey];
3573 
3574  datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
3575  datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
3576 
3577  compare = ApplySortComparator(datum1, isnull1,
3578  datum2, isnull2,
3579  sortKey);
3580  if (compare != 0)
3581  return compare;
3582  }
3583  }
3584  else
3585  {
3586  /*
3587  * In the expression index case, compute the whole index tuple and
3588  * then compare values. It would perhaps be faster to compute only as
3589  * many columns as we need to compare, but that would require
3590  * duplicating all the logic in FormIndexDatum.
3591  */
3592  Datum l_index_values[INDEX_MAX_KEYS];
3593  bool l_index_isnull[INDEX_MAX_KEYS];
3594  Datum r_index_values[INDEX_MAX_KEYS];
3595  bool r_index_isnull[INDEX_MAX_KEYS];
3596  TupleTableSlot *ecxt_scantuple;
3597 
3598  /* Reset context each time to prevent memory leakage */
3600 
3601  ecxt_scantuple = GetPerTupleExprContext(state->estate)->ecxt_scantuple;
3602 
3603  ExecStoreTuple(ltup, ecxt_scantuple, InvalidBuffer, false);
3604  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3605  l_index_values, l_index_isnull);
3606 
3607  ExecStoreTuple(rtup, ecxt_scantuple, InvalidBuffer, false);
3608  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3609  r_index_values, r_index_isnull);
3610 
3611  for (; nkey < state->nKeys; nkey++, sortKey++)
3612  {
3613  compare = ApplySortComparator(l_index_values[nkey],
3614  l_index_isnull[nkey],
3615  r_index_values[nkey],
3616  r_index_isnull[nkey],
3617  sortKey);
3618  if (compare != 0)
3619  return compare;
3620  }
3621  }
3622 
3623  return 0;
3624 }
void FormIndexDatum(IndexInfo *indexInfo, TupleTableSlot *slot, EState *estate, Datum *values, bool *isnull)
Definition: index.c:1774
TupleTableSlot * ExecStoreTuple(HeapTuple tuple, TupleTableSlot *slot, Buffer buffer, bool shouldFree)
Definition: execTuples.c:320
HeapTupleData * HeapTuple
Definition: htup.h:70
#define ResetPerTupleExprContext(estate)
Definition: executor.h:476
EState * estate
Definition: tuplesort.c:405
SortSupport sortKeys
Definition: tuplesort.c:383
Datum datum1
Definition: tuplesort.c:160
#define InvalidBuffer
Definition: buf.h:25
bool isnull1
Definition: tuplesort.c:161
signed int int32
Definition: c.h:284
#define GetPerTupleExprContext(estate)
Definition: executor.h:467
void * tuple
Definition: tuplesort.c:159
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
IndexInfo * indexInfo
Definition: tuplesort.c:404
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:774
uintptr_t Datum
Definition: postgres.h:372
List * ii_Expressions
Definition: execnodes.h:136
#define INDEX_MAX_KEYS
AttrNumber ii_KeyAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:135
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
int16 AttrNumber
Definition: attnum.h:21
TupleDesc tupDesc
Definition: tuplesort.c:382
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239

◆ comparetup_datum()

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

Definition at line 4055 of file tuplesort.c.

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

Referenced by tuplesort_begin_datum().

4056 {
4057  int compare;
4058 
4059  compare = ApplySortComparator(a->datum1, a->isnull1,
4060  b->datum1, b->isnull1,
4061  state->sortKeys);
4062  if (compare != 0)
4063  return compare;
4064 
4065  /* if we have abbreviations, then "tuple" has the original value */
4066 
4067  if (state->sortKeys->abbrev_converter)
4069  PointerGetDatum(b->tuple), b->isnull1,
4070  state->sortKeys);
4071 
4072  return compare;
4073 }
#define PointerGetDatum(X)
Definition: postgres.h:562
SortSupport sortKeys
Definition: tuplesort.c:383
Datum datum1
Definition: tuplesort.c:160
bool isnull1
Definition: tuplesort.c:161
void * tuple
Definition: tuplesort.c:159
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239

◆ comparetup_heap()

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

Definition at line 3317 of file tuplesort.c.

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

Referenced by tuplesort_begin_heap().

3318 {
3319  SortSupport sortKey = state->sortKeys;
3320  HeapTupleData ltup;
3321  HeapTupleData rtup;
3322  TupleDesc tupDesc;
3323  int nkey;
3324  int32 compare;
3325  AttrNumber attno;
3326  Datum datum1,
3327  datum2;
3328  bool isnull1,
3329  isnull2;
3330 
3331 
3332  /* Compare the leading sort key */
3333  compare = ApplySortComparator(a->datum1, a->isnull1,
3334  b->datum1, b->isnull1,
3335  sortKey);
3336  if (compare != 0)
3337  return compare;
3338 
3339  /* Compare additional sort keys */
3340  ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3341  ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
3342  rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3343  rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
3344  tupDesc = state->tupDesc;
3345 
3346  if (sortKey->abbrev_converter)
3347  {
3348  attno = sortKey->ssup_attno;
3349 
3350  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3351  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3352 
3353  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3354  datum2, isnull2,
3355  sortKey);
3356  if (compare != 0)
3357  return compare;
3358  }
3359 
3360  sortKey++;
3361  for (nkey = 1; nkey < state->nKeys; nkey++, sortKey++)
3362  {
3363  attno = sortKey->ssup_attno;
3364 
3365  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3366  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3367 
3368  compare = ApplySortComparator(datum1, isnull1,
3369  datum2, isnull2,
3370  sortKey);
3371  if (compare != 0)
3372  return compare;
3373  }
3374 
3375  return 0;
3376 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:383
Datum datum1
Definition: tuplesort.c:160
bool isnull1
Definition: tuplesort.c:161
signed int int32
Definition: c.h:284
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:159
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:774
uintptr_t Datum
Definition: postgres.h:372
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:625
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
int16 AttrNumber
Definition: attnum.h:21
TupleDesc tupDesc
Definition: tuplesort.c:382
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239

◆ comparetup_index_btree()

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

Definition at line 3762 of file tuplesort.c.

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

Referenced by tuplesort_begin_index_btree().

3764 {
3765  /*
3766  * This is similar to comparetup_heap(), but expects index tuples. There
3767  * is also special handling for enforcing uniqueness, and special
3768  * treatment for equal keys at the end.
3769  */
3770  SortSupport sortKey = state->sortKeys;
3771  IndexTuple tuple1;
3772  IndexTuple tuple2;
3773  int keysz;
3774  TupleDesc tupDes;
3775  bool equal_hasnull = false;
3776  int nkey;
3777  int32 compare;
3778  Datum datum1,
3779  datum2;
3780  bool isnull1,
3781  isnull2;
3782 
3783 
3784  /* Compare the leading sort key */
3785  compare = ApplySortComparator(a->datum1, a->isnull1,
3786  b->datum1, b->isnull1,
3787  sortKey);
3788  if (compare != 0)
3789  return compare;
3790 
3791  /* Compare additional sort keys */
3792  tuple1 = (IndexTuple) a->tuple;
3793  tuple2 = (IndexTuple) b->tuple;
3794  keysz = state->nKeys;
3795  tupDes = RelationGetDescr(state->indexRel);
3796 
3797  if (sortKey->abbrev_converter)
3798  {
3799  datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
3800  datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
3801 
3802  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3803  datum2, isnull2,
3804  sortKey);
3805  if (compare != 0)
3806  return compare;
3807  }
3808 
3809  /* they are equal, so we only need to examine one null flag */
3810  if (a->isnull1)
3811  equal_hasnull = true;
3812 
3813  sortKey++;
3814  for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
3815  {
3816  datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
3817  datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
3818 
3819  compare = ApplySortComparator(datum1, isnull1,
3820  datum2, isnull2,
3821  sortKey);
3822  if (compare != 0)
3823  return compare; /* done when we find unequal attributes */
3824 
3825  /* they are equal, so we only need to examine one null flag */
3826  if (isnull1)
3827  equal_hasnull = true;
3828  }
3829 
3830  /*
3831  * If btree has asked us to enforce uniqueness, complain if two equal
3832  * tuples are detected (unless there was at least one NULL field).
3833  *
3834  * It is sufficient to make the test here, because if two tuples are equal
3835  * they *must* get compared at some stage of the sort --- otherwise the
3836  * sort algorithm wouldn't have checked whether one must appear before the
3837  * other.
3838  */
3839  if (state->enforceUnique && !equal_hasnull)
3840  {
3842  bool isnull[INDEX_MAX_KEYS];
3843  char *key_desc;
3844 
3845  /*
3846  * Some rather brain-dead implementations of qsort (such as the one in
3847  * QNX 4) will sometimes call the comparison routine to compare a
3848  * value to itself, but we always use our own implementation, which
3849  * does not.
3850  */
3851  Assert(tuple1 != tuple2);
3852 
3853  index_deform_tuple(tuple1, tupDes, values, isnull);
3854 
3855  key_desc = BuildIndexValueDescription(state->indexRel, values, isnull);
3856 
3857  ereport(ERROR,
3858  (errcode(ERRCODE_UNIQUE_VIOLATION),
3859  errmsg("could not create unique index \"%s\"",
3861  key_desc ? errdetail("Key %s is duplicated.", key_desc) :
3862  errdetail("Duplicate keys exist."),
3863  errtableconstraint(state->heapRel,
3864  RelationGetRelationName(state->indexRel))));
3865  }
3866 
3867  /*
3868  * If key values are equal, we sort on ItemPointer. This does not affect
3869  * validity of the finished index, but it may be useful to have index
3870  * scans in physical order.
3871  */
3872  {
3873  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
3874  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
3875 
3876  if (blk1 != blk2)
3877  return (blk1 < blk2) ? -1 : 1;
3878  }
3879  {
3882 
3883  if (pos1 != pos2)
3884  return (pos1 < pos2) ? -1 : 1;
3885  }
3886 
3887  return 0;
3888 }
Relation heapRel
Definition: tuplesort.c:411
#define RelationGetDescr(relation)
Definition: rel.h:437
SortSupport sortKeys
Definition: tuplesort.c:383
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:160
int errcode(int sqlerrcode)
Definition: elog.c:575
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:161
signed int int32
Definition: c.h:284
uint16 OffsetNumber
Definition: off.h:24
void * tuple
Definition: tuplesort.c:159
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5312
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
#define ERROR
Definition: elog.h:43
IndexTupleData * IndexTuple
Definition: itup.h:53
int errdetail(const char *fmt,...)
Definition: elog.c:873
#define RelationGetRelationName(relation)
Definition: rel.h:445
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:420
#define ereport(elevel, rest)
Definition: elog.h:122
Relation indexRel
Definition: tuplesort.c:412
uintptr_t Datum
Definition: postgres.h:372
#define Assert(condition)
Definition: c.h:670
bool enforceUnique
Definition: tuplesort.c:415
#define INDEX_MAX_KEYS
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:95
static Datum values[MAXATTR]
Definition: bootstrap.c:164
int errmsg(const char *fmt,...)
Definition: elog.c:797
char * BuildIndexValueDescription(Relation indexRelation, Datum *values, bool *isnull)
Definition: genam.c:177
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239

◆ comparetup_index_hash()

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

Definition at line 3891 of file tuplesort.c.

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

Referenced by tuplesort_begin_index_hash().

3893 {
3894  Bucket bucket1;
3895  Bucket bucket2;
3896  IndexTuple tuple1;
3897  IndexTuple tuple2;
3898 
3899  /*
3900  * Fetch hash keys and mask off bits we don't want to sort by. We know
3901  * that the first column of the index tuple is the hash key.
3902  */
3903  Assert(!a->isnull1);
3905  state->max_buckets, state->high_mask,
3906  state->low_mask);
3907  Assert(!b->isnull1);
3909  state->max_buckets, state->high_mask,
3910  state->low_mask);
3911  if (bucket1 > bucket2)
3912  return 1;
3913  else if (bucket1 < bucket2)
3914  return -1;
3915 
3916  /*
3917  * If hash values are equal, we sort on ItemPointer. This does not affect
3918  * validity of the finished index, but it may be useful to have index
3919  * scans in physical order.
3920  */
3921  tuple1 = (IndexTuple) a->tuple;
3922  tuple2 = (IndexTuple) b->tuple;
3923 
3924  {
3925  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
3926  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
3927 
3928  if (blk1 != blk2)
3929  return (blk1 < blk2) ? -1 : 1;
3930  }
3931  {
3934 
3935  if (pos1 != pos2)
3936  return (pos1 < pos2) ? -1 : 1;
3937  }
3938 
3939  return 0;
3940 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:125
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:160
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:161
uint16 OffsetNumber
Definition: off.h:24
uint32 Bucket
Definition: hash.h:34
void * tuple
Definition: tuplesort.c:159
uint32 high_mask
Definition: tuplesort.c:418
IndexTupleData * IndexTuple
Definition: itup.h:53
#define Assert(condition)
Definition: c.h:670
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:95
uint32 max_buckets
Definition: tuplesort.c:420
uint32 low_mask
Definition: tuplesort.c:419
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76

◆ consider_abort_common()

static bool consider_abort_common ( Tuplesortstate state)
static

Definition at line 1612 of file tuplesort.c.

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

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

1613 {
1614  Assert(state->sortKeys[0].abbrev_converter != NULL);
1615  Assert(state->sortKeys[0].abbrev_abort != NULL);
1616  Assert(state->sortKeys[0].abbrev_full_comparator != NULL);
1617 
1618  /*
1619  * Check effectiveness of abbreviation optimization. Consider aborting
1620  * when still within memory limit.
1621  */
1622  if (state->status == TSS_INITIAL &&
1623  state->memtupcount >= state->abbrevNext)
1624  {
1625  state->abbrevNext *= 2;
1626 
1627  /*
1628  * Check opclass-supplied abbreviation abort routine. It may indicate
1629  * that abbreviation should not proceed.
1630  */
1631  if (!state->sortKeys->abbrev_abort(state->memtupcount,
1632  state->sortKeys))
1633  return false;
1634 
1635  /*
1636  * Finally, restore authoritative comparator, and indicate that
1637  * abbreviation is not in play by setting abbrev_converter to NULL
1638  */
1639  state->sortKeys[0].comparator = state->sortKeys[0].abbrev_full_comparator;
1640  state->sortKeys[0].abbrev_converter = NULL;
1641  /* Not strictly necessary, but be tidy */
1642  state->sortKeys[0].abbrev_abort = NULL;
1643  state->sortKeys[0].abbrev_full_comparator = NULL;
1644 
1645  /* Give up - expect original pass-by-value representation */
1646  return true;
1647  }
1648 
1649  return false;
1650 }
TupSortStatus status
Definition: tuplesort.c:222
int64 abbrevNext
Definition: tuplesort.c:397
SortSupport sortKeys
Definition: tuplesort.c:383
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:107
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:192
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define Assert(condition)
Definition: c.h:670
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:183

◆ copytup_cluster()

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

Definition at line 3627 of file tuplesort.c.

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

Referenced by tuplesort_begin_cluster().

3628 {
3629  HeapTuple tuple = (HeapTuple) tup;
3630  Datum original;
3631  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3632 
3633  /* copy the tuple into sort storage */
3634  tuple = heap_copytuple(tuple);
3635  stup->tuple = (void *) tuple;
3636  USEMEM(state, GetMemoryChunkSpace(tuple));
3637 
3638  MemoryContextSwitchTo(oldcontext);
3639 
3640  /*
3641  * set up first-column key value, and potentially abbreviate, if it's a
3642  * simple column
3643  */
3644  if (state->indexInfo->ii_KeyAttrNumbers[0] == 0)
3645  return;
3646 
3647  original = heap_getattr(tuple,
3648  state->indexInfo->ii_KeyAttrNumbers[0],
3649  state->tupDesc,
3650  &stup->isnull1);
3651 
3652  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3653  {
3654  /*
3655  * Store ordinary Datum representation, or NULL value. If there is a
3656  * converter it won't expect NULL values, and cost model is not
3657  * required to account for NULL, so in that case we avoid calling
3658  * converter and just set datum1 to zeroed representation (to be
3659  * consistent, and to support cheap inequality tests for NULL
3660  * abbreviated keys).
3661  */
3662  stup->datum1 = original;
3663  }
3664  else if (!consider_abort_common(state))
3665  {
3666  /* Store abbreviated key representation */
3667  stup->datum1 = state->sortKeys->abbrev_converter(original,
3668  state->sortKeys);
3669  }
3670  else
3671  {
3672  /* Abort abbreviation */
3673  int i;
3674 
3675  stup->datum1 = original;
3676 
3677  /*
3678  * Set state to be consistent with never trying abbreviation.
3679  *
3680  * Alter datum1 representation in already-copied tuples, so as to
3681  * ensure a consistent representation (current tuple was just
3682  * handled). It does not matter if some dumped tuples are already
3683  * sorted on tape, since serialized tuples lack abbreviated keys
3684  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3685  */
3686  for (i = 0; i < state->memtupcount; i++)
3687  {
3688  SortTuple *mtup = &state->memtuples[i];
3689 
3690  tuple = (HeapTuple) mtup->tuple;
3691  mtup->datum1 = heap_getattr(tuple,
3692  state->indexInfo->ii_KeyAttrNumbers[0],
3693  state->tupDesc,
3694  &mtup->isnull1);
3695  }
3696  }
3697 }
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:611
HeapTupleData * HeapTuple
Definition: htup.h:70
SortSupport sortKeys
Definition: tuplesort.c:383
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:160
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool isnull1
Definition: tuplesort.c:161
void * tuple
Definition: tuplesort.c:159
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1612
IndexInfo * indexInfo
Definition: tuplesort.c:404
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:774
uintptr_t Datum
Definition: postgres.h:372
AttrNumber ii_KeyAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:135
MemoryContext tuplecontext
Definition: tuplesort.c:235
#define USEMEM(state, amt)
Definition: tuplesort.c:466
int i
TupleDesc tupDesc
Definition: tuplesort.c:382
SortTuple * memtuples
Definition: tuplesort.c:283

◆ copytup_datum()

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

Definition at line 4076 of file tuplesort.c.

References elog, and ERROR.

Referenced by tuplesort_begin_datum().

4077 {
4078  /* Not currently needed */
4079  elog(ERROR, "copytup_datum() should not be called");
4080 }
#define ERROR
Definition: elog.h:43
#define elog
Definition: elog.h:219

◆ copytup_heap()

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

Definition at line 3379 of file tuplesort.c.

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

Referenced by tuplesort_begin_heap().

3380 {
3381  /*
3382  * We expect the passed "tup" to be a TupleTableSlot, and form a
3383  * MinimalTuple using the exported interface for that.
3384  */
3385  TupleTableSlot *slot = (TupleTableSlot *) tup;
3386  Datum original;
3387  MinimalTuple tuple;
3388  HeapTupleData htup;
3389  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3390 
3391  /* copy the tuple into sort storage */
3392  tuple = ExecCopySlotMinimalTuple(slot);
3393  stup->tuple = (void *) tuple;
3394  USEMEM(state, GetMemoryChunkSpace(tuple));
3395  /* set up first-column key value */
3396  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3397  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3398  original = heap_getattr(&htup,
3399  state->sortKeys[0].ssup_attno,
3400  state->tupDesc,
3401  &stup->isnull1);
3402 
3403  MemoryContextSwitchTo(oldcontext);
3404 
3405  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3406  {
3407  /*
3408  * Store ordinary Datum representation, or NULL value. If there is a
3409  * converter it won't expect NULL values, and cost model is not
3410  * required to account for NULL, so in that case we avoid calling
3411  * converter and just set datum1 to zeroed representation (to be
3412  * consistent, and to support cheap inequality tests for NULL
3413  * abbreviated keys).
3414  */
3415  stup->datum1 = original;
3416  }
3417  else if (!consider_abort_common(state))
3418  {
3419  /* Store abbreviated key representation */
3420  stup->datum1 = state->sortKeys->abbrev_converter(original,
3421  state->sortKeys);
3422  }
3423  else
3424  {
3425  /* Abort abbreviation */
3426  int i;
3427 
3428  stup->datum1 = original;
3429 
3430  /*
3431  * Set state to be consistent with never trying abbreviation.
3432  *
3433  * Alter datum1 representation in already-copied tuples, so as to
3434  * ensure a consistent representation (current tuple was just
3435  * handled). It does not matter if some dumped tuples are already
3436  * sorted on tape, since serialized tuples lack abbreviated keys
3437  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3438  */
3439  for (i = 0; i < state->memtupcount; i++)
3440  {
3441  SortTuple *mtup = &state->memtuples[i];
3442 
3443  htup.t_len = ((MinimalTuple) mtup->tuple)->t_len +
3445  htup.t_data = (HeapTupleHeader) ((char *) mtup->tuple -
3447 
3448  mtup->datum1 = heap_getattr(&htup,
3449  state->sortKeys[0].ssup_attno,
3450  state->tupDesc,
3451  &mtup->isnull1);
3452  }
3453  }
3454 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:383
MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: execTuples.c:577
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:160
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool isnull1
Definition: tuplesort.c:161
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:159
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1612
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:774
uintptr_t Datum
Definition: postgres.h:372
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:625
MemoryContext tuplecontext
Definition: tuplesort.c:235
#define USEMEM(state, amt)
Definition: tuplesort.c:466
int i
TupleDesc tupDesc
Definition: tuplesort.c:382
SortTuple * memtuples
Definition: tuplesort.c:283

◆ copytup_index()

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

Definition at line 3943 of file tuplesort.c.

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

Referenced by tuplesort_begin_index_btree(), and tuplesort_begin_index_hash().

3944 {
3945  IndexTuple tuple = (IndexTuple) tup;
3946  unsigned int tuplen = IndexTupleSize(tuple);
3947  IndexTuple newtuple;
3948  Datum original;
3949 
3950  /* copy the tuple into sort storage */
3951  newtuple = (IndexTuple) MemoryContextAlloc(state->tuplecontext, tuplen);
3952  memcpy(newtuple, tuple, tuplen);
3953  USEMEM(state, GetMemoryChunkSpace(newtuple));
3954  stup->tuple = (void *) newtuple;
3955  /* set up first-column key value */
3956  original = index_getattr(newtuple,
3957  1,
3958  RelationGetDescr(state->indexRel),
3959  &stup->isnull1);
3960 
3961  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3962  {
3963  /*
3964  * Store ordinary Datum representation, or NULL value. If there is a
3965  * converter it won't expect NULL values, and cost model is not
3966  * required to account for NULL, so in that case we avoid calling
3967  * converter and just set datum1 to zeroed representation (to be
3968  * consistent, and to support cheap inequality tests for NULL
3969  * abbreviated keys).
3970  */
3971  stup->datum1 = original;
3972  }
3973  else if (!consider_abort_common(state))
3974  {
3975  /* Store abbreviated key representation */
3976  stup->datum1 = state->sortKeys->abbrev_converter(original,
3977  state->sortKeys);
3978  }
3979  else
3980  {
3981  /* Abort abbreviation */
3982  int i;
3983 
3984  stup->datum1 = original;
3985 
3986  /*
3987  * Set state to be consistent with never trying abbreviation.
3988  *
3989  * Alter datum1 representation in already-copied tuples, so as to
3990  * ensure a consistent representation (current tuple was just
3991  * handled). It does not matter if some dumped tuples are already
3992  * sorted on tape, since serialized tuples lack abbreviated keys
3993  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3994  */
3995  for (i = 0; i < state->memtupcount; i++)
3996  {
3997  SortTuple *mtup = &state->memtuples[i];
3998 
3999  tuple = (IndexTuple) mtup->tuple;
4000  mtup->datum1 = index_getattr(tuple,
4001  1,
4002  RelationGetDescr(state->indexRel),
4003  &mtup->isnull1);
4004  }
4005  }
4006 }
#define RelationGetDescr(relation)
Definition: rel.h:437
SortSupport sortKeys
Definition: tuplesort.c:383
Datum datum1
Definition: tuplesort.c:160
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool isnull1
Definition: tuplesort.c:161
void * tuple
Definition: tuplesort.c:159
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1612
IndexTupleData * IndexTuple
Definition: itup.h:53
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
Relation indexRel
Definition: tuplesort.c:412
uintptr_t Datum
Definition: postgres.h:372
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
MemoryContext tuplecontext
Definition: tuplesort.c:235
#define USEMEM(state, amt)
Definition: tuplesort.c:466
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:706
int i
#define IndexTupleSize(itup)
Definition: itup.h:70
SortTuple * memtuples
Definition: tuplesort.c:283

◆ dumptuples()

static void dumptuples ( Tuplesortstate state,
bool  alltuples 
)
static

Definition at line 2739 of file tuplesort.c.

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

Referenced by puttuple_common(), and tuplesort_performsort().

2740 {
2741  int memtupwrite;
2742  int i;
2743 
2744  /*
2745  * Nothing to do if we still fit in available memory and have array
2746  * slots, unless this is the final call during initial run generation.
2747  */
2748  if (state->memtupcount < state->memtupsize && !LACKMEM(state) &&
2749  !alltuples)
2750  return;
2751 
2752  /*
2753  * Final call might require no sorting, in rare cases where we just so
2754  * happen to have previously LACKMEM()'d at the point where exactly all
2755  * remaining tuples are loaded into memory, just before input was
2756  * exhausted.
2757  *
2758  * In general, short final runs are quite possible. Rather than allowing
2759  * a special case where there was a superfluous selectnewtape() call (i.e.
2760  * a call with no subsequent run actually written to destTape), we prefer
2761  * to write out a 0 tuple run.
2762  *
2763  * mergereadnext() is prepared for 0 tuple runs, and will reliably mark
2764  * the tape inactive for the merge when called from beginmerge(). This
2765  * case is therefore similar to the case where mergeonerun() finds a dummy
2766  * run for the tape, and so doesn't need to merge a run from the tape (or
2767  * conceptually "merges" the dummy run, if you prefer). According to
2768  * Knuth, Algorithm D "isn't strictly optimal" in its method of
2769  * distribution and dummy run assignment; this edge case seems very
2770  * unlikely to make that appreciably worse.
2771  */
2772  Assert(state->status == TSS_BUILDRUNS);
2773 
2774  /*
2775  * It seems unlikely that this limit will ever be exceeded, but take no
2776  * chances
2777  */
2778  if (state->currentRun == INT_MAX)
2779  ereport(ERROR,
2780  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2781  errmsg("cannot have more than %d runs for an external sort",
2782  INT_MAX)));
2783 
2784  state->currentRun++;
2785 
2786 #ifdef TRACE_SORT
2787  if (trace_sort)
2788  elog(LOG, "starting quicksort of run %d: %s",
2789  state->currentRun, pg_rusage_show(&state->ru_start));
2790 #endif
2791 
2792  /*
2793  * Sort all tuples accumulated within the allowed amount of memory for
2794  * this run using quicksort
2795  */
2796  tuplesort_sort_memtuples(state);
2797 
2798 #ifdef TRACE_SORT
2799  if (trace_sort)
2800  elog(LOG, "finished quicksort of run %d: %s",
2801  state->currentRun, pg_rusage_show(&state->ru_start));
2802 #endif
2803 
2804  memtupwrite = state->memtupcount;
2805  for (i = 0; i < memtupwrite; i++)
2806  {
2807  WRITETUP(state, state->tp_tapenum[state->destTape],
2808  &state->memtuples[i]);
2809  state->memtupcount--;
2810  }
2811 
2812  /*
2813  * Reset tuple memory. We've freed all of the tuples that we previously
2814  * allocated. It's important to avoid fragmentation when there is a stark
2815  * change in the sizes of incoming tuples. Fragmentation due to
2816  * AllocSetFree's bucketing by size class might be particularly bad if
2817  * this step wasn't taken.
2818  */
2820 
2821  markrunend(state, state->tp_tapenum[state->destTape]);
2822  state->tp_runs[state->destTape]++;
2823  state->tp_dummy[state->destTape]--; /* per Alg D step D2 */
2824 
2825 #ifdef TRACE_SORT
2826  if (trace_sort)
2827  elog(LOG, "finished writing run %d to tape %d: %s",
2828  state->currentRun, state->destTape,
2829  pg_rusage_show(&state->ru_start));
2830 #endif
2831 
2832  if (!alltuples)
2833  selectnewtape(state);
2834 }
TupSortStatus status
Definition: tuplesort.c:222
PGRUsage ru_start
Definition: tuplesort.c:434
int errcode(int sqlerrcode)
Definition: elog.c:575
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3275
#define ERROR
Definition: elog.h:43
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define ereport(elevel, rest)
Definition: elog.h:122
static void selectnewtape(Tuplesortstate *state)
Definition: tuplesort.c:2305
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:463
#define Assert(condition)
Definition: c.h:670
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3119
int * tp_dummy
Definition: tuplesort.c:359
MemoryContext tuplecontext
Definition: tuplesort.c:235
int errmsg(const char *fmt,...)
Definition: elog.c:797
int * tp_tapenum
Definition: tuplesort.c:360
int i
#define elog
Definition: elog.h:219
#define LACKMEM(state)
Definition: tuplesort.c:465
SortTuple * memtuples
Definition: tuplesort.c:283

◆ free_sort_tuple()

static void free_sort_tuple ( Tuplesortstate state,
SortTuple stup 
)
static

Definition at line 4164 of file tuplesort.c.

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

Referenced by make_bounded_heap(), and puttuple_common().

4165 {
4166  FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
4167  pfree(stup->tuple);
4168 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
void * tuple
Definition: tuplesort.c:159
void pfree(void *pointer)
Definition: mcxt.c:949
#define FREEMEM(state, amt)
Definition: tuplesort.c:467

◆ getlen()

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

Definition at line 3262 of file tuplesort.c.

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

Referenced by mergereadnext(), and tuplesort_gettuple_common().

3263 {
3264  unsigned int len;
3265 
3266  if (LogicalTapeRead(state->tapeset, tapenum,
3267  &len, sizeof(len)) != sizeof(len))
3268  elog(ERROR, "unexpected end of tape");
3269  if (len == 0 && !eofOK)
3270  elog(ERROR, "unexpected end of data");
3271  return len;
3272 }
size_t LogicalTapeRead(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:655
#define ERROR
Definition: elog.h:43
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
#define elog
Definition: elog.h:219

◆ grow_memtuples()

static bool grow_memtuples ( Tuplesortstate state)
static

Definition at line 1182 of file tuplesort.c.

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

Referenced by puttuple_common().

1183 {
1184  int newmemtupsize;
1185  int memtupsize = state->memtupsize;
1186  int64 memNowUsed = state->allowedMem - state->availMem;
1187 
1188  /* Forget it if we've already maxed out memtuples, per comment above */
1189  if (!state->growmemtuples)
1190  return false;
1191 
1192  /* Select new value of memtupsize */
1193  if (memNowUsed <= state->availMem)
1194  {
1195  /*
1196  * We've used no more than half of allowedMem; double our usage,
1197  * clamping at INT_MAX tuples.
1198  */
1199  if (memtupsize < INT_MAX / 2)
1200  newmemtupsize = memtupsize * 2;
1201  else
1202  {
1203  newmemtupsize = INT_MAX;
1204  state->growmemtuples = false;
1205  }
1206  }
1207  else
1208  {
1209  /*
1210  * This will be the last increment of memtupsize. Abandon doubling
1211  * strategy and instead increase as much as we safely can.
1212  *
1213  * To stay within allowedMem, we can't increase memtupsize by more
1214  * than availMem / sizeof(SortTuple) elements. In practice, we want
1215  * to increase it by considerably less, because we need to leave some
1216  * space for the tuples to which the new array slots will refer. We
1217  * assume the new tuples will be about the same size as the tuples
1218  * we've already seen, and thus we can extrapolate from the space
1219  * consumption so far to estimate an appropriate new size for the
1220  * memtuples array. The optimal value might be higher or lower than
1221  * this estimate, but it's hard to know that in advance. We again
1222  * clamp at INT_MAX tuples.
1223  *
1224  * This calculation is safe against enlarging the array so much that
1225  * LACKMEM becomes true, because the memory currently used includes
1226  * the present array; thus, there would be enough allowedMem for the
1227  * new array elements even if no other memory were currently used.
1228  *
1229  * We do the arithmetic in float8, because otherwise the product of
1230  * memtupsize and allowedMem could overflow. Any inaccuracy in the
1231  * result should be insignificant; but even if we computed a
1232  * completely insane result, the checks below will prevent anything
1233  * really bad from happening.
1234  */
1235  double grow_ratio;
1236 
1237  grow_ratio = (double) state->allowedMem / (double) memNowUsed;
1238  if (memtupsize * grow_ratio < INT_MAX)
1239  newmemtupsize = (int) (memtupsize * grow_ratio);
1240  else
1241  newmemtupsize = INT_MAX;
1242 
1243  /* We won't make any further enlargement attempts */
1244  state->growmemtuples = false;
1245  }
1246 
1247  /* Must enlarge array by at least one element, else report failure */
1248  if (newmemtupsize <= memtupsize)
1249  goto noalloc;
1250 
1251  /*
1252  * On a 32-bit machine, allowedMem could exceed MaxAllocHugeSize. Clamp
1253  * to ensure our request won't be rejected. Note that we can easily
1254  * exhaust address space before facing this outcome. (This is presently
1255  * impossible due to guc.c's MAX_KILOBYTES limitation on work_mem, but
1256  * don't rely on that at this distance.)
1257  */
1258  if ((Size) newmemtupsize >= MaxAllocHugeSize / sizeof(SortTuple))
1259  {
1260  newmemtupsize = (int) (MaxAllocHugeSize / sizeof(SortTuple));
1261  state->growmemtuples = false; /* can't grow any more */
1262  }
1263 
1264  /*
1265  * We need to be sure that we do not cause LACKMEM to become true, else
1266  * the space management algorithm will go nuts. The code above should
1267  * never generate a dangerous request, but to be safe, check explicitly
1268  * that the array growth fits within availMem. (We could still cause
1269  * LACKMEM if the memory chunk overhead associated with the memtuples
1270  * array were to increase. That shouldn't happen because we chose the
1271  * initial array size large enough to ensure that palloc will be treating
1272  * both old and new arrays as separate chunks. But we'll check LACKMEM
1273  * explicitly below just in case.)
1274  */
1275  if (state->availMem < (int64) ((newmemtupsize - memtupsize) * sizeof(SortTuple)))
1276  goto noalloc;
1277 
1278  /* OK, do it */
1279  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
1280  state->memtupsize = newmemtupsize;
1281  state->memtuples = (SortTuple *)
1282  repalloc_huge(state->memtuples,
1283  state->memtupsize * sizeof(SortTuple));
1284  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
1285  if (LACKMEM(state))
1286  elog(ERROR, "unexpected out-of-memory situation in tuplesort");
1287  return true;
1288 
1289 noalloc:
1290  /* If for any reason we didn't realloc, shut off future attempts */
1291  state->growmemtuples = false;
1292  return false;
1293 }
int64 availMem
Definition: tuplesort.c:230
bool growmemtuples
Definition: tuplesort.c:286
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
#define MaxAllocHugeSize
Definition: memutils.h:44
#define ERROR
Definition: elog.h:43
#define FREEMEM(state, amt)
Definition: tuplesort.c:467
int64 allowedMem
Definition: tuplesort.c:231
size_t Size
Definition: c.h:404
void * repalloc_huge(void *pointer, Size size)
Definition: mcxt.c:1030
#define USEMEM(state, amt)
Definition: tuplesort.c:466
#define elog
Definition: elog.h:219
#define LACKMEM(state)
Definition: tuplesort.c:465
SortTuple * memtuples
Definition: tuplesort.c:283

◆ init_slab_allocator()

static void init_slab_allocator ( Tuplesortstate state,
int  numSlots 
)
static

Definition at line 2337 of file tuplesort.c.

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

Referenced by mergeruns().

2338 {
2339  if (numSlots > 0)
2340  {
2341  char *p;
2342  int i;
2343 
2344  state->slabMemoryBegin = palloc(numSlots * SLAB_SLOT_SIZE);
2345  state->slabMemoryEnd = state->slabMemoryBegin +
2346  numSlots * SLAB_SLOT_SIZE;
2347  state->slabFreeHead = (SlabSlot *) state->slabMemoryBegin;
2348  USEMEM(state, numSlots * SLAB_SLOT_SIZE);
2349 
2350  p = state->slabMemoryBegin;
2351  for (i = 0; i < numSlots - 1; i++)
2352  {
2353  ((SlabSlot *) p)->nextfree = (SlabSlot *) (p + SLAB_SLOT_SIZE);
2354  p += SLAB_SLOT_SIZE;
2355  }
2356  ((SlabSlot *) p)->nextfree = NULL;
2357  }
2358  else
2359  {
2360  state->slabMemoryBegin = state->slabMemoryEnd = NULL;
2361  state->slabFreeHead = NULL;
2362  }
2363  state->slabAllocatorUsed = true;
2364 }
char * slabMemoryEnd
Definition: tuplesort.c:318
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:176
char * slabMemoryBegin
Definition: tuplesort.c:317
bool slabAllocatorUsed
Definition: tuplesort.c:315
void * palloc(Size size)
Definition: mcxt.c:848
#define USEMEM(state, amt)
Definition: tuplesort.c:466
int i
SlabSlot * slabFreeHead
Definition: tuplesort.c:319

◆ inittapes()

static void inittapes ( Tuplesortstate state)
static

Definition at line 2228 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::currentRun, Tuplesortstate::destTape, elog, GetMemoryChunkSpace(), Tuplesortstate::Level, LOG, LogicalTapeSetCreate(), Tuplesortstate::maxTapes, Tuplesortstate::memtuples, Tuplesortstate::mergeactive, palloc0(), pg_rusage_show(), PrepareTempTablespaces(), Tuplesortstate::ru_start, Tuplesortstate::status, TAPE_BUFFER_OVERHEAD, Tuplesortstate::tapeRange, Tuplesortstate::tapeset, Tuplesortstate::tp_dummy, Tuplesortstate::tp_fib, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, trace_sort, TSS_BUILDRUNS, tuplesort_merge_order(), and USEMEM.

Referenced by puttuple_common().

2229 {
2230  int maxTapes,
2231  j;
2232  int64 tapeSpace;
2233 
2234  /* Compute number of tapes to use: merge order plus 1 */
2235  maxTapes = tuplesort_merge_order(state->allowedMem) + 1;
2236 
2237  state->maxTapes = maxTapes;
2238  state->tapeRange = maxTapes - 1;
2239 
2240 #ifdef TRACE_SORT
2241  if (trace_sort)
2242  elog(LOG, "switching to external sort with %d tapes: %s",
2243  maxTapes, pg_rusage_show(&state->ru_start));
2244 #endif
2245 
2246  /*
2247  * Decrease availMem to reflect the space needed for tape buffers, when
2248  * writing the initial runs; but don't decrease it to the point that we
2249  * have no room for tuples. (That case is only likely to occur if sorting
2250  * pass-by-value Datums; in all other scenarios the memtuples[] array is
2251  * unlikely to occupy more than half of allowedMem. In the pass-by-value
2252  * case it's not important to account for tuple space, so we don't care if
2253  * LACKMEM becomes inaccurate.)
2254  */
2255  tapeSpace = (int64) maxTapes * TAPE_BUFFER_OVERHEAD;
2256 
2257  if (tapeSpace + GetMemoryChunkSpace(state->memtuples) < state->allowedMem)
2258  USEMEM(state, tapeSpace);
2259 
2260  /*
2261  * Make sure that the temp file(s) underlying the tape set are created in
2262  * suitable temp tablespaces.
2263  */
2265 
2266  /*
2267  * Create the tape set and allocate the per-tape data arrays.
2268  */
2269  state->tapeset = LogicalTapeSetCreate(maxTapes);
2270 
2271  state->mergeactive = (bool *) palloc0(maxTapes * sizeof(bool));
2272  state->tp_fib = (int *) palloc0(maxTapes * sizeof(int));
2273  state->tp_runs = (int *) palloc0(maxTapes * sizeof(int));
2274  state->tp_dummy = (int *) palloc0(maxTapes * sizeof(int));
2275  state->tp_tapenum = (int *) palloc0(maxTapes * sizeof(int));
2276 
2277  state->currentRun = 0;
2278 
2279  /*
2280  * Initialize variables of Algorithm D (step D1).
2281  */
2282  for (j = 0; j < maxTapes; j++)
2283  {
2284  state->tp_fib[j] = 1;
2285  state->tp_runs[j] = 0;
2286  state->tp_dummy[j] = 1;
2287  state->tp_tapenum[j] = j;
2288  }
2289  state->tp_fib[state->tapeRange] = 0;
2290  state->tp_dummy[state->tapeRange] = 0;
2291 
2292  state->Level = 1;
2293  state->destTape = 0;
2294 
2295  state->status = TSS_BUILDRUNS;
2296 }
TupSortStatus status
Definition: tuplesort.c:222
PGRUsage ru_start
Definition: tuplesort.c:434
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
LogicalTapeSet * LogicalTapeSetCreate(int ntapes)
Definition: logtape.c:379
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:211
void PrepareTempTablespaces(void)
Definition: tablespace.c:1287
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
int64 allowedMem
Definition: tuplesort.c:231
void * palloc0(Size size)
Definition: mcxt.c:877
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2188
int * tp_dummy
Definition: tuplesort.c:359
int * tp_tapenum
Definition: tuplesort.c:360
#define USEMEM(state, amt)
Definition: tuplesort.c:466
#define elog
Definition: elog.h:219
bool * mergeactive
Definition: tuplesort.c:348
SortTuple * memtuples
Definition: tuplesort.c:283

◆ make_bounded_heap()

static void make_bounded_heap ( Tuplesortstate state)
static

Definition at line 3032 of file tuplesort.c.

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

Referenced by puttuple_common().

3033 {
3034  int tupcount = state->memtupcount;
3035  int i;
3036 
3037  Assert(state->status == TSS_INITIAL);
3038  Assert(state->bounded);
3039  Assert(tupcount >= state->bound);
3040 
3041  /* Reverse sort direction so largest entry will be at root */
3042  reversedirection(state);
3043 
3044  state->memtupcount = 0; /* make the heap empty */
3045  for (i = 0; i < tupcount; i++)
3046  {
3047  if (state->memtupcount < state->bound)
3048  {
3049  /* Insert next tuple into heap */
3050  /* Must copy source tuple to avoid possible overwrite */
3051  SortTuple stup = state->memtuples[i];
3052 
3053  tuplesort_heap_insert(state, &stup);
3054  }
3055  else
3056  {
3057  /*
3058  * The heap is full. Replace the largest entry with the new
3059  * tuple, or just discard it, if it's larger than anything already
3060  * in the heap.
3061  */
3062  if (COMPARETUP(state, &state->memtuples[i], &state->memtuples[0]) <= 0)
3063  {
3064  free_sort_tuple(state, &state->memtuples[i]);
3066  }
3067  else
3068  tuplesort_heap_replace_top(state, &state->memtuples[i]);
3069  }
3070  }
3071 
3072  Assert(state->memtupcount == state->bound);
3073  state->status = TSS_BOUNDED;
3074 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3244
TupSortStatus status
Definition: tuplesort.c:222
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4164
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:461
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3145
#define Assert(condition)
Definition: c.h:670
int i
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3204
SortTuple * memtuples
Definition: tuplesort.c:283

◆ markrunend()

static void markrunend ( Tuplesortstate state,
int  tapenum 
)
static

Definition at line 3275 of file tuplesort.c.

References LogicalTapeWrite(), and Tuplesortstate::tapeset.

Referenced by dumptuples(), and mergeonerun().

3276 {
3277  unsigned int len = 0;
3278 
3279  LogicalTapeWrite(state->tapeset, tapenum, (void *) &len, sizeof(len));
3280 }
void LogicalTapeWrite(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:464
LogicalTapeSet * tapeset
Definition: tuplesort.c:236

◆ mergeonerun()

static void mergeonerun ( Tuplesortstate state)
static

Definition at line 2602 of file tuplesort.c.

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

Referenced by mergeruns().

2603 {
2604  int destTape = state->tp_tapenum[state->tapeRange];
2605  int srcTape;
2606 
2607  /*
2608  * Start the merge by loading one tuple from each active source tape into
2609  * the heap. We can also decrease the input run/dummy run counts.
2610  */
2611  beginmerge(state);
2612 
2613  /*
2614  * Execute merge by repeatedly extracting lowest tuple in heap, writing it
2615  * out, and replacing it with next tuple from same tape (if there is
2616  * another one).
2617  */
2618  while (state->memtupcount > 0)
2619  {
2620  SortTuple stup;
2621 
2622  /* write the tuple to destTape */
2623  srcTape = state->memtuples[0].tupindex;
2624  WRITETUP(state, destTape, &state->memtuples[0]);
2625 
2626  /* recycle the slot of the tuple we just wrote out, for the next read */
2627  if (state->memtuples[0].tuple)
2628  RELEASE_SLAB_SLOT(state, state->memtuples[0].tuple);
2629 
2630  /*
2631  * pull next tuple from the tape, and replace the written-out tuple in
2632  * the heap with it.
2633  */
2634  if (mergereadnext(state, srcTape, &stup))
2635  {
2636  stup.tupindex = srcTape;
2637  tuplesort_heap_replace_top(state, &stup);
2638 
2639  }
2640  else
2642  }
2643 
2644  /*
2645  * When the heap empties, we're done. Write an end-of-run marker on the
2646  * output tape, and increment its count of real runs.
2647  */
2648  markrunend(state, destTape);
2649  state->tp_runs[state->tapeRange]++;
2650 
2651 #ifdef TRACE_SORT
2652  if (trace_sort)
2653  elog(LOG, "finished %d-way merge step: %s", state->activeTapes,
2654  pg_rusage_show(&state->ru_start));
2655 #endif
2656 }
PGRUsage ru_start
Definition: tuplesort.c:434
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3275
void * tuple
Definition: tuplesort.c:159
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:463
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:449
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3180
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2714
int tupindex
Definition: tuplesort.c:162
int * tp_tapenum
Definition: tuplesort.c:360
#define elog
Definition: elog.h:219
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3204
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:2666
SortTuple * memtuples
Definition: tuplesort.c:283

◆ mergereadnext()

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

Definition at line 2714 of file tuplesort.c.

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

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

2715 {
2716  unsigned int tuplen;
2717 
2718  if (!state->mergeactive[srcTape])
2719  return false; /* tape's run is already exhausted */
2720 
2721  /* read next tuple, if any */
2722  if ((tuplen = getlen(state, srcTape, true)) == 0)
2723  {
2724  state->mergeactive[srcTape] = false;
2725  return false;
2726  }
2727  READTUP(state, stup, srcTape, tuplen);
2728 
2729  return true;
2730 }
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3262
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:464
bool * mergeactive
Definition: tuplesort.c:348

◆ mergeruns()

static void mergeruns ( Tuplesortstate state)
static

Definition at line 2373 of file tuplesort.c.

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

Referenced by tuplesort_performsort().

2374 {
2375  int tapenum,
2376  svTape,
2377  svRuns,
2378  svDummy;
2379  int numTapes;
2380  int numInputTapes;
2381 
2382  Assert(state->status == TSS_BUILDRUNS);
2383  Assert(state->memtupcount == 0);
2384 
2385  if (state->sortKeys != NULL && state->sortKeys->abbrev_converter != NULL)
2386  {
2387  /*
2388  * If there are multiple runs to be merged, when we go to read back
2389  * tuples from disk, abbreviated keys will not have been stored, and
2390  * we don't care to regenerate them. Disable abbreviation from this
2391  * point on.
2392  */
2393  state->sortKeys->abbrev_converter = NULL;
2395 
2396  /* Not strictly necessary, but be tidy */
2397  state->sortKeys->abbrev_abort = NULL;
2398  state->sortKeys->abbrev_full_comparator = NULL;
2399  }
2400 
2401  /*
2402  * Reset tuple memory. We've freed all the tuples that we previously
2403  * allocated. We will use the slab allocator from now on.
2404  */
2406  state->tuplecontext = NULL;
2407 
2408  /*
2409  * We no longer need a large memtuples array. (We will allocate a smaller
2410  * one for the heap later.)
2411  */
2412  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
2413  pfree(state->memtuples);
2414  state->memtuples = NULL;
2415 
2416  /*
2417  * If we had fewer runs than tapes, refund the memory that we imagined we
2418  * would need for the tape buffers of the unused tapes.
2419  *
2420  * numTapes and numInputTapes reflect the actual number of tapes we will
2421  * use. Note that the output tape's tape number is maxTapes - 1, so the
2422  * tape numbers of the used tapes are not consecutive, and you cannot just
2423  * loop from 0 to numTapes to visit all used tapes!
2424  */
2425  if (state->Level == 1)
2426  {
2427  numInputTapes = state->currentRun;
2428  numTapes = numInputTapes + 1;
2429  FREEMEM(state, (state->maxTapes - numTapes) * TAPE_BUFFER_OVERHEAD);
2430  }
2431  else
2432  {
2433  numInputTapes = state->tapeRange;
2434  numTapes = state->maxTapes;
2435  }
2436 
2437  /*
2438  * Initialize the slab allocator. We need one slab slot per input tape,
2439  * for the tuples in the heap, plus one to hold the tuple last returned
2440  * from tuplesort_gettuple. (If we're sorting pass-by-val Datums,
2441  * however, we don't need to do allocate anything.)
2442  *
2443  * From this point on, we no longer use the USEMEM()/LACKMEM() mechanism
2444  * to track memory usage of individual tuples.
2445  */
2446  if (state->tuples)
2447  init_slab_allocator(state, numInputTapes + 1);
2448  else
2449  init_slab_allocator(state, 0);
2450 
2451  /*
2452  * Allocate a new 'memtuples' array, for the heap. It will hold one tuple
2453  * from each input tape.
2454  */
2455  state->memtupsize = numInputTapes;
2456  state->memtuples = (SortTuple *) palloc(numInputTapes * sizeof(SortTuple));
2457  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
2458 
2459  /*
2460  * Use all the remaining memory we have available for read buffers among
2461  * the input tapes.
2462  *
2463  * We do this only after checking for the case that we produced only one
2464  * initial run, because there is no need to use a large read buffer when
2465  * we're reading from a single tape. With one tape, the I/O pattern will
2466  * be the same regardless of the buffer size.
2467  *
2468  * We don't try to "rebalance" the memory among tapes, when we start a new
2469  * merge phase, even if some tapes are inactive in the new phase. That
2470  * would be hard, because logtape.c doesn't know where one run ends and
2471  * another begins. When a new merge phase begins, and a tape doesn't
2472  * participate in it, its buffer nevertheless already contains tuples from
2473  * the next run on same tape, so we cannot release the buffer. That's OK
2474  * in practice, merge performance isn't that sensitive to the amount of
2475  * buffers used, and most merge phases use all or almost all tapes,
2476  * anyway.
2477  */
2478 #ifdef TRACE_SORT
2479  if (trace_sort)
2480  elog(LOG, "using " INT64_FORMAT " KB of memory for read buffers among %d input tapes",
2481  (state->availMem) / 1024, numInputTapes);
2482 #endif
2483 
2484  state->read_buffer_size = Max(state->availMem / numInputTapes, 0);
2485  USEMEM(state, state->read_buffer_size * numInputTapes);
2486 
2487  /* End of step D2: rewind all output tapes to prepare for merging */
2488  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2489  LogicalTapeRewindForRead(state->tapeset, tapenum, state->read_buffer_size);
2490 
2491  for (;;)
2492  {
2493  /*
2494  * At this point we know that tape[T] is empty. If there's just one
2495  * (real or dummy) run left on each input tape, then only one merge
2496  * pass remains. If we don't have to produce a materialized sorted
2497  * tape, we can stop at this point and do the final merge on-the-fly.
2498  */
2499  if (!state->randomAccess)
2500  {
2501  bool allOneRun = true;
2502 
2503  Assert(state->tp_runs[state->tapeRange] == 0);
2504  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2505  {
2506  if (state->tp_runs[tapenum] + state->tp_dummy[tapenum] != 1)
2507  {
2508  allOneRun = false;
2509  break;
2510  }
2511  }
2512  if (allOneRun)
2513  {
2514  /* Tell logtape.c we won't be writing anymore */
2516  /* Initialize for the final merge pass */
2517  beginmerge(state);
2518  state->status = TSS_FINALMERGE;
2519  return;
2520  }
2521  }
2522 
2523  /* Step D5: merge runs onto tape[T] until tape[P] is empty */
2524  while (state->tp_runs[state->tapeRange - 1] ||
2525  state->tp_dummy[state->tapeRange - 1])
2526  {
2527  bool allDummy = true;
2528 
2529  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2530  {
2531  if (state->tp_dummy[tapenum] == 0)
2532  {
2533  allDummy = false;
2534  break;
2535  }
2536  }
2537 
2538  if (allDummy)
2539  {
2540  state->tp_dummy[state->tapeRange]++;
2541  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2542  state->tp_dummy[tapenum]--;
2543  }
2544  else
2545  mergeonerun(state);
2546  }
2547 
2548  /* Step D6: decrease level */
2549  if (--state->Level == 0)
2550  break;
2551  /* rewind output tape T to use as new input */
2552  LogicalTapeRewindForRead(state->tapeset, state->tp_tapenum[state->tapeRange],
2553  state->read_buffer_size);
2554  /* rewind used-up input tape P, and prepare it for write pass */
2555  LogicalTapeRewindForWrite(state->tapeset, state->tp_tapenum[state->tapeRange - 1]);
2556  state->tp_runs[state->tapeRange - 1] = 0;
2557 
2558  /*
2559  * reassign tape units per step D6; note we no longer care about A[]
2560  */
2561  svTape = state->tp_tapenum[state->tapeRange];
2562  svDummy = state->tp_dummy[state->tapeRange];
2563  svRuns = state->tp_runs[state->tapeRange];
2564  for (tapenum = state->tapeRange; tapenum > 0; tapenum--)
2565  {
2566  state->tp_tapenum[tapenum] = state->tp_tapenum[tapenum - 1];
2567  state->tp_dummy[tapenum] = state->tp_dummy[tapenum - 1];
2568  state->tp_runs[tapenum] = state->tp_runs[tapenum - 1];
2569  }
2570  state->tp_tapenum[0] = svTape;
2571  state->tp_dummy[0] = svDummy;
2572  state->tp_runs[0] = svRuns;
2573  }
2574 
2575  /*
2576  * Done. Knuth says that the result is on TAPE[1], but since we exited
2577  * the loop without performing the last iteration of step D6, we have not
2578  * rearranged the tape unit assignment, and therefore the result is on
2579  * TAPE[T]. We need to do it this way so that we can freeze the final
2580  * output tape while rewinding it. The last iteration of step D6 would be
2581  * a waste of cycles anyway...
2582  */
2583  state->result_tape = state->tp_tapenum[state->tapeRange];
2584  LogicalTapeFreeze(state->tapeset, state->result_tape);
2585  state->status = TSS_SORTEDONTAPE;
2586 
2587  /* Release the read buffers of all the other tapes, by rewinding them. */
2588  for (tapenum = 0; tapenum < state->maxTapes; tapenum++)
2589  {
2590  if (tapenum != state->result_tape)
2591  LogicalTapeRewindForWrite(state->tapeset, tapenum);
2592  }
2593 }
int64 availMem
Definition: tuplesort.c:230
size_t read_buffer_size
Definition: tuplesort.c:322
TupSortStatus status
Definition: tuplesort.c:222
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:200
static void mergeonerun(Tuplesortstate *state)
Definition: tuplesort.c:2602
SortSupport sortKeys
Definition: tuplesort.c:383
bool randomAccess
Definition: tuplesort.c:224
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:629
static void init_slab_allocator(Tuplesortstate *state, int numSlots)
Definition: tuplesort.c:2337
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:211
void pfree(void *pointer)
Definition: mcxt.c:949
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:107
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:192
#define FREEMEM(state, amt)
Definition: tuplesort.c:467
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
#define Max(x, y)
Definition: c.h:796
#define Assert(condition)
Definition: c.h:670
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:183
#define INT64_FORMAT
Definition: c.h:338
void LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Definition: logtape.c:551
int * tp_dummy
Definition: tuplesort.c:359
MemoryContext tuplecontext
Definition: tuplesort.c:235
void * palloc(Size size)
Definition: mcxt.c:848
int * tp_tapenum
Definition: tuplesort.c:360
#define USEMEM(state, amt)
Definition: tuplesort.c:466
#define elog
Definition: elog.h:219
void LogicalTapeSetForgetFreeSpace(LogicalTapeSet *lts)
Definition: logtape.c:453
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:2666
void LogicalTapeFreeze(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:703
SortTuple * memtuples
Definition: tuplesort.c:283

◆ puttuple_common()

static void puttuple_common ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 1504 of file tuplesort.c.

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

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

1505 {
1506  switch (state->status)
1507  {
1508  case TSS_INITIAL:
1509 
1510  /*
1511  * Save the tuple into the unsorted array. First, grow the array
1512  * as needed. Note that we try to grow the array when there is
1513  * still one free slot remaining --- if we fail, there'll still be
1514  * room to store the incoming tuple, and then we'll switch to
1515  * tape-based operation.
1516  */
1517  if (state->memtupcount >= state->memtupsize - 1)
1518  {
1519  (void) grow_memtuples(state);
1520  Assert(state->memtupcount < state->memtupsize);
1521  }
1522  state->memtuples[state->memtupcount++] = *tuple;
1523 
1524  /*
1525  * Check if it's time to switch over to a bounded heapsort. We do
1526  * so if the input tuple count exceeds twice the desired tuple
1527  * count (this is a heuristic for where heapsort becomes cheaper
1528  * than a quicksort), or if we've just filled workMem and have
1529  * enough tuples to meet the bound.
1530  *
1531  * Note that once we enter TSS_BOUNDED state we will always try to
1532  * complete the sort that way. In the worst case, if later input
1533  * tuples are larger than earlier ones, this might cause us to
1534  * exceed workMem significantly.
1535  */
1536  if (state->bounded &&
1537  (state->memtupcount > state->bound * 2 ||
1538  (state->memtupcount > state->bound && LACKMEM(state))))
1539  {
1540 #ifdef TRACE_SORT
1541  if (trace_sort)
1542  elog(LOG, "switching to bounded heapsort at %d tuples: %s",
1543  state->memtupcount,
1544  pg_rusage_show(&state->ru_start));
1545 #endif
1546  make_bounded_heap(state);
1547  return;
1548  }
1549 
1550  /*
1551  * Done if we still fit in available memory and have array slots.
1552  */
1553  if (state->memtupcount < state->memtupsize && !LACKMEM(state))
1554  return;
1555 
1556  /*
1557  * Nope; time to switch to tape-based operation.
1558  */
1559  inittapes(state);
1560 
1561  /*
1562  * Dump all tuples.
1563  */
1564  dumptuples(state, false);
1565  break;
1566 
1567  case TSS_BOUNDED:
1568 
1569  /*
1570  * We don't want to grow the array here, so check whether the new
1571  * tuple can be discarded before putting it in. This should be a
1572  * good speed optimization, too, since when there are many more
1573  * input tuples than the bound, most input tuples can be discarded
1574  * with just this one comparison. Note that because we currently
1575  * have the sort direction reversed, we must check for <= not >=.
1576  */
1577  if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
1578  {
1579  /* new tuple <= top of the heap, so we can discard it */
1580  free_sort_tuple(state, tuple);
1582  }
1583  else
1584  {
1585  /* discard top of heap, replacing it with the new tuple */
1586  free_sort_tuple(state, &state->memtuples[0]);
1587  tuplesort_heap_replace_top(state, tuple);
1588  }
1589  break;
1590 
1591  case TSS_BUILDRUNS:
1592 
1593  /*
1594  * Save the tuple into the unsorted array (there must be
1595  * space)
1596  */
1597  state->memtuples[state->memtupcount++] = *tuple;
1598 
1599  /*
1600  * If we are over the memory limit, dump all tuples.
1601  */
1602  dumptuples(state, false);
1603  break;
1604 
1605  default:
1606  elog(ERROR, "invalid tuplesort state");
1607  break;
1608  }
1609 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2739
TupSortStatus status
Definition: tuplesort.c:222
static bool grow_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:1182
PGRUsage ru_start
Definition: tuplesort.c:434
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
#define ERROR
Definition: elog.h:43
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4164
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:461
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define Assert(condition)
Definition: c.h:670
static void inittapes(Tuplesortstate *state)
Definition: tuplesort.c:2228
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
#define elog
Definition: elog.h:219
static void make_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3032
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3204
#define LACKMEM(state)
Definition: tuplesort.c:465
SortTuple * memtuples
Definition: tuplesort.c:283

◆ readtup_alloc()

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

Definition at line 3289 of file tuplesort.c.

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

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

3290 {
3291  SlabSlot *buf;
3292 
3293  /*
3294  * We pre-allocate enough slots in the slab arena that we should never run
3295  * out.
3296  */
3297  Assert(state->slabFreeHead);
3298 
3299  if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
3300  return MemoryContextAlloc(state->sortcontext, tuplen);
3301  else
3302  {
3303  buf = state->slabFreeHead;
3304  /* Reuse this slot */
3305  state->slabFreeHead = buf->nextfree;
3306 
3307  return buf;
3308  }
3309 }
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:176
union SlabSlot * nextfree
Definition: tuplesort.c:180
MemoryContext sortcontext
Definition: tuplesort.c:234
static char * buf
Definition: pg_test_fsync.c:67
#define Assert(condition)
Definition: c.h:670
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:706
SlabSlot * slabFreeHead
Definition: tuplesort.c:319

◆ readtup_cluster()

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

Definition at line 3724 of file tuplesort.c.

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

Referenced by tuplesort_begin_cluster().

3726 {
3727  unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
3728  HeapTuple tuple = (HeapTuple) readtup_alloc(state,
3729  t_len + HEAPTUPLESIZE);
3730 
3731  /* Reconstruct the HeapTupleData header */
3732  tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
3733  tuple->t_len = t_len;
3734  LogicalTapeReadExact(state->tapeset, tapenum,
3735  &tuple->t_self, sizeof(ItemPointerData));
3736  /* We don't currently bother to reconstruct t_tableOid */
3737  tuple->t_tableOid = InvalidOid;
3738  /* Read in the tuple body */
3739  LogicalTapeReadExact(state->tapeset, tapenum,
3740  tuple->t_data, tuple->t_len);
3741  if (state->randomAccess) /* need trailing length word? */
3742  LogicalTapeReadExact(state->tapeset, tapenum,
3743  &tuplen, sizeof(tuplen));
3744  stup->tuple = (void *) tuple;
3745  /* set up first-column key value, if it's a simple column */
3746  if (state->indexInfo->ii_KeyAttrNumbers[0] != 0)
3747  stup->datum1 = heap_getattr(tuple,
3748  state->indexInfo->ii_KeyAttrNumbers[0],
3749  state->tupDesc,
3750  &stup->isnull1);
3751 }
HeapTupleData * HeapTuple
Definition: htup.h:70
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
bool randomAccess
Definition: tuplesort.c:224
Datum datum1
Definition: tuplesort.c:160
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:517
bool isnull1
Definition: tuplesort.c:161
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:159
ItemPointerData t_self
Definition: htup.h:65
uint32 t_len
Definition: htup.h:64
IndexInfo * indexInfo
Definition: tuplesort.c:404
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
Oid t_tableOid
Definition: htup.h:66
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:774
#define InvalidOid
Definition: postgres_ext.h:36
struct ItemPointerData ItemPointerData
AttrNumber ii_KeyAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:135
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3289
#define HEAPTUPLESIZE
Definition: htup.h:72
TupleDesc tupDesc
Definition: tuplesort.c:382

◆ readtup_datum()

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

Definition at line 4124 of file tuplesort.c.

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

Referenced by tuplesort_begin_datum().

4126 {
4127  unsigned int tuplen = len - sizeof(unsigned int);
4128 
4129  if (tuplen == 0)
4130  {
4131  /* it's NULL */
4132  stup->datum1 = (Datum) 0;
4133  stup->isnull1 = true;
4134  stup->tuple = NULL;
4135  }
4136  else if (!state->tuples)
4137  {
4138  Assert(tuplen == sizeof(Datum));
4139  LogicalTapeReadExact(state->tapeset, tapenum,
4140  &stup->datum1, tuplen);
4141  stup->isnull1 = false;
4142  stup->tuple = NULL;
4143  }
4144  else
4145  {
4146  void *raddr = readtup_alloc(state, tuplen);
4147 
4148  LogicalTapeReadExact(state->tapeset, tapenum,
4149  raddr, tuplen);
4150  stup->datum1 = PointerGetDatum(raddr);
4151  stup->isnull1 = false;
4152  stup->tuple = raddr;
4153  }
4154 
4155  if (state->randomAccess) /* need trailing length word? */
4156  LogicalTapeReadExact(state->tapeset, tapenum,
4157  &tuplen, sizeof(tuplen));
4158 }
#define PointerGetDatum(X)
Definition: postgres.h:562
bool randomAccess
Definition: tuplesort.c:224
Datum datum1
Definition: tuplesort.c:160
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:517
bool isnull1
Definition: tuplesort.c:161
void * tuple
Definition: tuplesort.c:159
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
uintptr_t Datum
Definition: postgres.h:372
#define Assert(condition)
Definition: c.h:670
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3289

◆ readtup_heap()

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

Definition at line 3484 of file tuplesort.c.

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

Referenced by tuplesort_begin_heap().

3486 {
3487  unsigned int tupbodylen = len - sizeof(int);
3488  unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
3489  MinimalTuple tuple = (MinimalTuple) readtup_alloc(state, tuplen);
3490  char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
3491  HeapTupleData htup;
3492 
3493  /* read in the tuple proper */
3494  tuple->t_len = tuplen;
3495  LogicalTapeReadExact(state->tapeset, tapenum,
3496  tupbody, tupbodylen);
3497  if (state->randomAccess) /* need trailing length word? */
3498  LogicalTapeReadExact(state->tapeset, tapenum,
3499  &tuplen, sizeof(tuplen));
3500  stup->tuple = (void *) tuple;
3501  /* set up first-column key value */
3502  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3503  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3504  stup->datum1 = heap_getattr(&htup,
3505  state->sortKeys[0].ssup_attno,
3506  state->tupDesc,
3507  &stup->isnull1);
3508 }
#define MINIMAL_TUPLE_DATA_OFFSET
Definition: htup_details.h:629
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:383
bool randomAccess
Definition: tuplesort.c:224
Datum datum1
Definition: tuplesort.c:160
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:517
bool isnull1
Definition: tuplesort.c:161
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:159
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:774
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:625
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3289
TupleDesc tupDesc
Definition: tuplesort.c:382

◆ readtup_index()

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

Definition at line 4031 of file tuplesort.c.

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

Referenced by tuplesort_begin_index_btree(), and tuplesort_begin_index_hash().

4033 {
4034  unsigned int tuplen = len - sizeof(unsigned int);
4035  IndexTuple tuple = (IndexTuple) readtup_alloc(state, tuplen);
4036 
4037  LogicalTapeReadExact(state->tapeset, tapenum,
4038  tuple, tuplen);
4039  if (state->randomAccess) /* need trailing length word? */
4040  LogicalTapeReadExact(state->tapeset, tapenum,
4041  &tuplen, sizeof(tuplen));
4042  stup->tuple = (void *) tuple;
4043  /* set up first-column key value */
4044  stup->datum1 = index_getattr(tuple,
4045  1,
4046  RelationGetDescr(state->indexRel),
4047  &stup->isnull1);
4048 }
#define RelationGetDescr(relation)
Definition: rel.h:437
bool randomAccess
Definition: tuplesort.c:224
Datum datum1
Definition: tuplesort.c:160
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:517
bool isnull1
Definition: tuplesort.c:161
void * tuple
Definition: tuplesort.c:159
IndexTupleData * IndexTuple
Definition: itup.h:53
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
Relation indexRel
Definition: tuplesort.c:412
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3289

◆ reversedirection()

static void reversedirection ( Tuplesortstate state)
static

Definition at line 3244 of file tuplesort.c.

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

Referenced by make_bounded_heap(), and sort_bounded_heap().

3245 {
3246  SortSupport sortKey = state->sortKeys;
3247  int nkey;
3248 
3249  for (nkey = 0; nkey < state->nKeys; nkey++, sortKey++)
3250  {
3251  sortKey->ssup_reverse = !sortKey->ssup_reverse;
3252  sortKey->ssup_nulls_first = !sortKey->ssup_nulls_first;
3253  }
3254 }
bool ssup_nulls_first
Definition: sortsupport.h:75
SortSupport sortKeys
Definition: tuplesort.c:383

◆ selectnewtape()

static void selectnewtape ( Tuplesortstate state)
static

Definition at line 2305 of file tuplesort.c.

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

Referenced by dumptuples().

2306 {
2307  int j;
2308  int a;
2309 
2310  /* Step D3: advance j (destTape) */
2311  if (state->tp_dummy[state->destTape] < state->tp_dummy[state->destTape + 1])
2312  {
2313  state->destTape++;
2314  return;
2315  }
2316  if (state->tp_dummy[state->destTape] != 0)
2317  {
2318  state->destTape = 0;
2319  return;
2320  }
2321 
2322  /* Step D4: increase level */
2323  state->Level++;
2324  a = state->tp_fib[0];
2325  for (j = 0; j < state->tapeRange; j++)
2326  {
2327  state->tp_dummy[j] = a + state->tp_fib[j + 1] - state->tp_fib[j];
2328  state->tp_fib[j] = a + state->tp_fib[j + 1];
2329  }
2330  state->destTape = 0;
2331 }
int * tp_dummy
Definition: tuplesort.c:359

◆ sort_bounded_heap()

static void sort_bounded_heap ( Tuplesortstate state)
static

Definition at line 3080 of file tuplesort.c.

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

Referenced by tuplesort_performsort().

3081 {
3082  int tupcount = state->memtupcount;
3083 
3084  Assert(state->status == TSS_BOUNDED);
3085  Assert(state->bounded);
3086  Assert(tupcount == state->bound);
3087 
3088  /*
3089  * We can unheapify in place because each delete-top call will remove the
3090  * largest entry, which we can promptly store in the newly freed slot at
3091  * the end. Once we're down to a single-entry heap, we're done.
3092  */
3093  while (state->memtupcount > 1)
3094  {
3095  SortTuple stup = state->memtuples[0];
3096 
3097  /* this sifts-up the next-largest entry and decreases memtupcount */
3099  state->memtuples[state->memtupcount] = stup;
3100  }
3101  state->memtupcount = tupcount;
3102 
3103  /*
3104  * Reverse sort direction back to the original state. This is not
3105  * actually necessary but seems like a good idea for tidiness.
3106  */
3107  reversedirection(state);
3108 
3109  state->status = TSS_SORTEDINMEM;
3110  state->boundUsed = true;
3111 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3244
TupSortStatus status
Definition: tuplesort.c:222
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3180
#define Assert(condition)
Definition: c.h:670
SortTuple * memtuples
Definition: tuplesort.c:283

◆ tuplesort_begin_cluster()

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

Definition at line 765 of file tuplesort.c.

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

Referenced by copy_heap_data().

768 {
769  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
770  ScanKey indexScanKey;
771  MemoryContext oldcontext;
772  int i;
773 
774  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
775 
776  oldcontext = MemoryContextSwitchTo(state->sortcontext);
777 
778 #ifdef TRACE_SORT
779  if (trace_sort)
780  elog(LOG,
781  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
783  workMem, randomAccess ? 't' : 'f');
784 #endif
785 
786  state->nKeys = RelationGetNumberOfAttributes(indexRel);
787 
788  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
789  false, /* no unique check */
790  state->nKeys,
791  workMem,
792  randomAccess);
793 
795  state->copytup = copytup_cluster;
796  state->writetup = writetup_cluster;
797  state->readtup = readtup_cluster;
798  state->abbrevNext = 10;
799 
800  state->indexInfo = BuildIndexInfo(indexRel);
801 
802  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
803 
804  indexScanKey = _bt_mkscankey_nodata(indexRel);
805 
806  if (state->indexInfo->ii_Expressions != NULL)
807  {
808  TupleTableSlot *slot;
809  ExprContext *econtext;
810 
811  /*
812  * We will need to use FormIndexDatum to evaluate the index
813  * expressions. To do that, we need an EState, as well as a
814  * TupleTableSlot to put the table tuples into. The econtext's
815  * scantuple has to point to that slot, too.
816  */
817  state->estate = CreateExecutorState();
818  slot = MakeSingleTupleTableSlot(tupDesc);
819  econtext = GetPerTupleExprContext(state->estate);
820  econtext->ecxt_scantuple = slot;
821  }
822 
823  /* Prepare SortSupport data for each column */
824  state->sortKeys = (SortSupport) palloc0(state->nKeys *
825  sizeof(SortSupportData));
826 
827  for (i = 0; i < state->nKeys; i++)
828  {
829  SortSupport sortKey = state->sortKeys + i;
830  ScanKey scanKey = indexScanKey + i;
831  int16 strategy;
832 
833  sortKey->ssup_cxt = CurrentMemoryContext;
834  sortKey->ssup_collation = scanKey->sk_collation;
835  sortKey->ssup_nulls_first =
836  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
837  sortKey->ssup_attno = scanKey->sk_attno;
838  /* Convey if abbreviation optimization is applicable in principle */
839  sortKey->abbreviate = (i == 0);
840 
841  AssertState(sortKey->ssup_attno != 0);
842 
843  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
845 
846  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
847  }
848 
849  _bt_freeskey(indexScanKey);
850 
851  MemoryContextSwitchTo(oldcontext);
852 
853  return state;
854 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:283
bool ssup_nulls_first
Definition: sortsupport.h:75
ScanKey _bt_mkscankey_nodata(Relation rel)
Definition: nbtutils.c:115
static void writetup_cluster(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:3700
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:673
int64 abbrevNext
Definition: tuplesort.c:397
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:431
EState * estate
Definition: tuplesort.c:405
SortSupport sortKeys
Definition: tuplesort.c:383
void _bt_freeskey(ScanKey skey)
Definition: nbtutils.c:155
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:255
#define BTREE_AM_OID
Definition: pg_am.h:70
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:247
#define CLUSTER_SORT
Definition: tuplesort.c:114
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3516
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:1645
#define LOG
Definition: elog.h:26
Form_pg_class rd_rel
Definition: rel.h:114
static void copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3627
bool trace_sort
Definition: tuplesort.c:118
#define GetPerTupleExprContext(estate)
Definition: executor.h:467
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3724
MemoryContext sortcontext
Definition: tuplesort.c:234
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:273
IndexInfo * indexInfo
Definition: tuplesort.c:404
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc)
Definition: execTuples.c:199
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:160
EState * CreateExecutorState(void)
Definition: execUtils.c:80
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:428
void * palloc0(Size size)
Definition: mcxt.c:877
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:265
int sk_flags
Definition: skey.h:66
List * ii_Expressions
Definition: execnodes.h:136
#define Assert(condition)
Definition: c.h:670
#define SK_BT_DESC
Definition: nbtree.h:427
Definition: regguts.h:298
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:197
Oid sk_collation
Definition: skey.h:70
int i
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:607
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67
TupleDesc tupDesc
Definition: tuplesort.c:382

◆ tuplesort_begin_common()

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

Definition at line 607 of file tuplesort.c.

References ALLOCSET_DEFAULT_SIZES, ALLOCSET_SEPARATE_THRESHOLD, AllocSetContextCreate(), Tuplesortstate::allowedMem, Tuplesortstate::availMem, Tuplesortstate::bounded, Tuplesortstate::boundUsed, CurrentMemoryContext, Tuplesortstate::currentRun, elog, ERROR, GetMemoryChunkSpace(), Tuplesortstate::growmemtuples, LACKMEM, Max, MemoryContextSwitchTo(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, palloc(), palloc0(), pg_rusage_init(), Tuplesortstate::randomAccess, Tuplesortstate::result_tape, Tuplesortstate::ru_start, Tuplesortstate::slabAllocatorUsed, Tuplesortstate::sortcontext, Tuplesortstate::status, Tuplesortstate::tapeset, trace_sort, TSS_INITIAL, Tuplesortstate::tuplecontext, Tuplesortstate::tuples, and USEMEM.

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

608 {
610  MemoryContext sortcontext;
611  MemoryContext tuplecontext;
612  MemoryContext oldcontext;
613 
614  /*
615  * Create a working memory context for this sort operation. All data
616  * needed by the sort will live inside this context.
617  */
619  "TupleSort main",
621 
622  /*
623  * Caller tuple (e.g. IndexTuple) memory context.
624  *
625  * A dedicated child context used exclusively for caller passed tuples
626  * eases memory management. Resetting at key points reduces
627  * fragmentation. Note that the memtuples array of SortTuples is allocated
628  * in the parent context, not this context, because there is no need to
629  * free memtuples early.
630  */
631  tuplecontext = AllocSetContextCreate(sortcontext,
632  "Caller tuples",
634 
635  /*
636  * Make the Tuplesortstate within the per-sort context. This way, we
637  * don't need a separate pfree() operation for it at shutdown.
638  */
639  oldcontext = MemoryContextSwitchTo(sortcontext);
640 
641  state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));
642 
643 #ifdef TRACE_SORT
644  if (trace_sort)
645  pg_rusage_init(&state->ru_start);
646 #endif
647 
648  state->status = TSS_INITIAL;
649  state->randomAccess = randomAccess;
650  state->bounded = false;
651  state->tuples = true;
652  state->boundUsed = false;
653  state->allowedMem = workMem * (int64) 1024;
654  state->availMem = state->allowedMem;
655  state->sortcontext = sortcontext;
656  state->tuplecontext = tuplecontext;
657  state->tapeset = NULL;
658 
659  state->memtupcount = 0;
660 
661  /*
662  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
663  * see comments in grow_memtuples().
664  */
665  state->memtupsize = Max(1024,
666  ALLOCSET_SEPARATE_THRESHOLD / sizeof(SortTuple) + 1);
667 
668  state->growmemtuples = true;
669  state->slabAllocatorUsed = false;
670  state->memtuples = (SortTuple *) palloc(state->memtupsize * sizeof(SortTuple));
671 
672  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
673 
674  /* workMem must be large enough for the minimal memtuples array */
675  if (LACKMEM(state))
676  elog(ERROR, "insufficient memory allowed for sort");
677 
678  state->currentRun = 0;
679 
680  /*
681  * maxTapes, tapeRange, and Algorithm D variables will be initialized by
682  * inittapes(), if needed
683  */
684 
685  state->result_tape = -1; /* flag that result tape has not been formed */
686 
687  MemoryContextSwitchTo(oldcontext);
688 
689  return state;
690 }
int64 availMem
Definition: tuplesort.c:230
TupSortStatus status
Definition: tuplesort.c:222
PGRUsage ru_start
Definition: tuplesort.c:434
bool randomAccess
Definition: tuplesort.c:224
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
bool growmemtuples
Definition: tuplesort.c:286
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool trace_sort
Definition: tuplesort.c:118
void pg_rusage_init(PGRUsage *ru0)
Definition: pg_rusage.c:27
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:234
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:165
#define ALLOCSET_SEPARATE_THRESHOLD
Definition: memutils.h:192
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
int64 allowedMem
Definition: tuplesort.c:231
MemoryContext AllocSetContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: aset.c:322
void * palloc0(Size size)
Definition: mcxt.c:877
#define Max(x, y)
Definition: c.h:796
Definition: regguts.h:298
bool slabAllocatorUsed
Definition: tuplesort.c:315
MemoryContext tuplecontext
Definition: tuplesort.c:235
void * palloc(Size size)
Definition: mcxt.c:848
#define USEMEM(state, amt)
Definition: tuplesort.c:466
#define elog
Definition: elog.h:219
#define LACKMEM(state)
Definition: tuplesort.c:465
SortTuple * memtuples
Definition: tuplesort.c:283

◆ tuplesort_begin_datum()

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

Definition at line 975 of file tuplesort.c.

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

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

978 {
979  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
980  MemoryContext oldcontext;
981  int16 typlen;
982  bool typbyval;
983 
984  oldcontext = MemoryContextSwitchTo(state->sortcontext);
985 
986 #ifdef TRACE_SORT
987  if (trace_sort)
988  elog(LOG,
989  "begin datum sort: workMem = %d, randomAccess = %c",
990  workMem, randomAccess ? 't' : 'f');
991 #endif
992 
993  state->nKeys = 1; /* always a one-column sort */
994 
995  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
996  false, /* no unique check */
997  1,
998  workMem,
999  randomAccess);
1000 
1001  state->comparetup = comparetup_datum;
1002  state->copytup = copytup_datum;
1003  state->writetup = writetup_datum;
1004  state->readtup = readtup_datum;
1005  state->abbrevNext = 10;
1006 
1007  state->datumType = datumType;
1008 
1009  /* lookup necessary attributes of the datum type */
1010  get_typlenbyval(datumType, &typlen, &typbyval);
1011  state->datumTypeLen = typlen;
1012  state->tuples = !typbyval;
1013 
1014  /* Prepare SortSupport data */
1015  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1016 
1018  state->sortKeys->ssup_collation = sortCollation;
1019  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1020 
1021  /*
1022  * Abbreviation is possible here only for by-reference types. In theory,
1023  * a pass-by-value datatype could have an abbreviated form that is cheaper
1024  * to compare. In a tuple sort, we could support that, because we can
1025  * always extract the original datum from the tuple is needed. Here, we
1026  * can't, because a datum sort only stores a single copy of the datum; the
1027  * "tuple" field of each sortTuple is NULL.
1028  */
1029  state->sortKeys->abbreviate = !typbyval;
1030 
1031  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1032 
1033  /*
1034  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1035  * tie-breaker comparisons may be required. Typically, the optimization
1036  * is only of value to pass-by-value types anyway, whereas abbreviated
1037  * keys are typically only of value to pass-by-reference types.
1038  */
1039  if (!state->sortKeys->abbrev_converter)
1040  state->onlyKey = state->sortKeys;
1041 
1042  MemoryContextSwitchTo(oldcontext);
1043 
1044  return state;
1045 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:283
bool ssup_nulls_first
Definition: sortsupport.h:75
int64 abbrevNext
Definition: tuplesort.c:397
SortSupport sortKeys
Definition: tuplesort.c:383
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:255
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:133
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:247
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
#define DATUM_SORT
Definition: tuplesort.c:113
MemoryContext sortcontext
Definition: tuplesort.c:234
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4055
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:273
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4076
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4124
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
static void writetup_datum(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4083
void * palloc0(Size size)
Definition: mcxt.c:877
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:265
Definition: regguts.h:298
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2001
SortSupport onlyKey
Definition: tuplesort.c:389
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:607

◆ tuplesort_begin_heap()

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

Definition at line 693 of file tuplesort.c.

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

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

698 {
699  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
700  MemoryContext oldcontext;
701  int i;
702 
703  oldcontext = MemoryContextSwitchTo(state->sortcontext);
704 
705  AssertArg(nkeys > 0);
706 
707 #ifdef TRACE_SORT
708  if (trace_sort)
709  elog(LOG,
710  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
711  nkeys, workMem, randomAccess ? 't' : 'f');
712 #endif
713 
714  state->nKeys = nkeys;
715 
716  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
717  false, /* no unique check */
718  nkeys,
719  workMem,
720  randomAccess);
721 
722  state->comparetup = comparetup_heap;
723  state->copytup = copytup_heap;
724  state->writetup = writetup_heap;
725  state->readtup = readtup_heap;
726 
727  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
728  state->abbrevNext = 10;
729 
730  /* Prepare SortSupport data for each column */
731  state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
732 
733  for (i = 0; i < nkeys; i++)
734  {
735  SortSupport sortKey = state->sortKeys + i;
736 
737  AssertArg(attNums[i] != 0);
738  AssertArg(sortOperators[i] != 0);
739 
740  sortKey->ssup_cxt = CurrentMemoryContext;
741  sortKey->ssup_collation = sortCollations[i];
742  sortKey->ssup_nulls_first = nullsFirstFlags[i];
743  sortKey->ssup_attno = attNums[i];
744  /* Convey if abbreviation optimization is applicable in principle */
745  sortKey->abbreviate = (i == 0);
746 
747  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
748  }
749 
750  /*
751  * The "onlyKey" optimization cannot be used with abbreviated keys, since
752  * tie-breaker comparisons may be required. Typically, the optimization
753  * is only of value to pass-by-value types anyway, whereas abbreviated
754  * keys are typically only of value to pass-by-reference types.
755  */
756  if (nkeys == 1 && !state->sortKeys->abbrev_converter)
757  state->onlyKey = state->sortKeys;
758 
759  MemoryContextSwitchTo(oldcontext);
760 
761  return state;
762 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
bool ssup_nulls_first
Definition: sortsupport.h:75
static int comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3317
int64 abbrevNext
Definition: tuplesort.c:397
SortSupport sortKeys
Definition: tuplesort.c:383
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:255
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:133
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:247
#define LOG
Definition: elog.h:26
#define HEAP_SORT
Definition: tuplesort.c:111
bool trace_sort
Definition: tuplesort.c:118
MemoryContext sortcontext
Definition: tuplesort.c:234
static void writetup_heap(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:3457
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:273
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define AssertArg(condition)
Definition: c.h:672
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3379
void * palloc0(Size size)
Definition: mcxt.c:877
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:265
Definition: regguts.h:298
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3484
int i
SortSupport onlyKey
Definition: tuplesort.c:389
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:607
TupleDesc tupDesc
Definition: tuplesort.c:382

◆ tuplesort_begin_index_btree()

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

Definition at line 857 of file tuplesort.c.

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

Referenced by _bt_spoolinit().

861 {
862  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
863  ScanKey indexScanKey;
864  MemoryContext oldcontext;
865  int i;
866 
867  oldcontext = MemoryContextSwitchTo(state->sortcontext);
868 
869 #ifdef TRACE_SORT
870  if (trace_sort)
871  elog(LOG,
872  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
873  enforceUnique ? 't' : 'f',
874  workMem, randomAccess ? 't' : 'f');
875 #endif
876 
877  state->nKeys = RelationGetNumberOfAttributes(indexRel);
878 
879  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
880  enforceUnique,
881  state->nKeys,
882  workMem,
883  randomAccess);
884 
886  state->copytup = copytup_index;
887  state->writetup = writetup_index;
888  state->readtup = readtup_index;
889  state->abbrevNext = 10;
890 
891  state->heapRel = heapRel;
892  state->indexRel = indexRel;
893  state->enforceUnique = enforceUnique;
894 
895  indexScanKey = _bt_mkscankey_nodata(indexRel);
896  state->nKeys = RelationGetNumberOfAttributes(indexRel);
897 
898  /* Prepare SortSupport data for each column */
899  state->sortKeys = (SortSupport) palloc0(state->nKeys *
900  sizeof(SortSupportData));
901 
902  for (i = 0; i < state->nKeys; i++)
903  {
904  SortSupport sortKey = state->sortKeys + i;
905  ScanKey scanKey = indexScanKey + i;
906  int16 strategy;
907 
908  sortKey->ssup_cxt = CurrentMemoryContext;
909  sortKey->ssup_collation = scanKey->sk_collation;
910  sortKey->ssup_nulls_first =
911  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
912  sortKey->ssup_attno = scanKey->sk_attno;
913  /* Convey if abbreviation optimization is applicable in principle */
914  sortKey->abbreviate = (i == 0);
915 
916  AssertState(sortKey->ssup_attno != 0);
917 
918  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
920 
921  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
922  }
923 
924  _bt_freeskey(indexScanKey);
925 
926  MemoryContextSwitchTo(oldcontext);
927 
928  return state;
929 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:283
bool ssup_nulls_first
Definition: sortsupport.h:75
ScanKey _bt_mkscankey_nodata(Relation rel)
Definition: nbtutils.c:115
Relation heapRel
Definition: tuplesort.c:411
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:673
int64 abbrevNext
Definition: tuplesort.c:397
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:431
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3943
SortSupport sortKeys
Definition: tuplesort.c:383
void _bt_freeskey(ScanKey skey)
Definition: nbtutils.c:155
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:255
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:247
#define INDEX_SORT
Definition: tuplesort.c:112
#define LOG
Definition: elog.h:26
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3762
bool trace_sort
Definition: tuplesort.c:118
MemoryContext sortcontext
Definition: tuplesort.c:234
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4009
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:273
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4031
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:160
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:428
void * palloc0(Size size)
Definition: mcxt.c:877
Relation indexRel
Definition: tuplesort.c:412
AttrNumber ssup_attno
Definition: sortsupport.h:81
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:265
int sk_flags
Definition: skey.h:66
#define SK_BT_DESC
Definition: nbtree.h:427
Definition: regguts.h:298
bool enforceUnique
Definition: tuplesort.c:415
Oid sk_collation
Definition: skey.h:70
int i
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:607
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67

◆ tuplesort_begin_index_hash()

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

Definition at line 932 of file tuplesort.c.

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

Referenced by _h_spoolinit().

938 {
939  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
940  MemoryContext oldcontext;
941 
942  oldcontext = MemoryContextSwitchTo(state->sortcontext);
943 
944 #ifdef TRACE_SORT
945  if (trace_sort)
946  elog(LOG,
947  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
948  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
949  high_mask,
950  low_mask,
951  max_buckets,
952  workMem, randomAccess ? 't' : 'f');
953 #endif
954 
955  state->nKeys = 1; /* Only one sort column, the hash code */
956 
958  state->copytup = copytup_index;
959  state->writetup = writetup_index;
960  state->readtup = readtup_index;
961 
962  state->heapRel = heapRel;
963  state->indexRel = indexRel;
964 
965  state->high_mask = high_mask;
966  state->low_mask = low_mask;
967  state->max_buckets = max_buckets;
968 
969  MemoryContextSwitchTo(oldcontext);
970 
971  return state;
972 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3891
Relation heapRel
Definition: tuplesort.c:411
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3943
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:255
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:247
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
MemoryContext sortcontext
Definition: tuplesort.c:234
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4009
uint32 high_mask
Definition: tuplesort.c:418
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:273
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4031
Relation indexRel
Definition: tuplesort.c:412
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:265
Definition: regguts.h:298
uint32 max_buckets
Definition: tuplesort.c:420
uint32 low_mask
Definition: tuplesort.c:419
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:607

◆ tuplesort_end()

void tuplesort_end ( Tuplesortstate state)

Definition at line 1104 of file tuplesort.c.

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

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

1105 {
1106  /* context swap probably not needed, but let's be safe */
1107  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1108 
1109 #ifdef TRACE_SORT
1110  long spaceUsed;
1111 
1112  if (state->tapeset)
1113  spaceUsed = LogicalTapeSetBlocks(state->tapeset);
1114  else
1115  spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
1116 #endif
1117 
1118  /*
1119  * Delete temporary "tape" files, if any.
1120  *
1121  * Note: want to include this in reported total cost of sort, hence need
1122  * for two #ifdef TRACE_SORT sections.
1123  */
1124  if (state->tapeset)
1125  LogicalTapeSetClose(state->tapeset);
1126 
1127 #ifdef TRACE_SORT
1128  if (trace_sort)
1129  {
1130  if (state->tapeset)
1131  elog(LOG, "external sort ended, %ld disk blocks used: %s",
1132  spaceUsed, pg_rusage_show(&state->ru_start));
1133  else
1134  elog(LOG, "internal sort ended, %ld KB used: %s",
1135  spaceUsed, pg_rusage_show(&state->ru_start));
1136  }
1137 
1138  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
1139 #else
1140 
1141  /*
1142  * If you disabled TRACE_SORT, you can still probe sort__done, but you
1143  * ain't getting space-used stats.
1144  */
1145  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, 0L);
1146 #endif
1147 
1148  /* Free any execution state created for CLUSTER case */
1149  if (state->estate != NULL)
1150  {
1151  ExprContext *econtext = GetPerTupleExprContext(state->estate);
1152 
1154  FreeExecutorState(state->estate);
1155  }
1156 
1157  MemoryContextSwitchTo(oldcontext);
1158 
1159  /*
1160  * Free the per-sort memory context, thereby releasing all working memory,
1161  * including the Tuplesortstate struct itself.
1162  */
1164 }
int64 availMem
Definition: tuplesort.c:230
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:200
PGRUsage ru_start
Definition: tuplesort.c:434
EState * estate
Definition: tuplesort.c:405
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:118
void FreeExecutorState(EState *estate)
Definition: execUtils.c:185
#define GetPerTupleExprContext(estate)
Definition: executor.h:467
MemoryContext sortcontext
Definition: tuplesort.c:234
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:216
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
int64 allowedMem
Definition: tuplesort.c:231
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:197
void LogicalTapeSetClose(LogicalTapeSet *lts)
Definition: logtape.c:427
#define elog
Definition: elog.h:219
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:889

◆ tuplesort_get_stats()

void tuplesort_get_stats ( Tuplesortstate state,
TuplesortInstrumentation stats 
)

Definition at line 2941 of file tuplesort.c.

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

Referenced by ExecSort(), and show_sort_info().

2943 {
2944  /*
2945  * Note: it might seem we should provide both memory and disk usage for a
2946  * disk-based sort. However, the current code doesn't track memory space
2947  * accurately once we have begun to return tuples to the caller (since we
2948  * don't account for pfree's the caller is expected to do), so we cannot
2949  * rely on availMem in a disk sort. This does not seem worth the overhead
2950  * to fix. Is it worth creating an API for the memory context code to
2951  * tell us how much is actually used in sortcontext?
2952  */
2953  if (state->tapeset)
2954  {
2956  stats->spaceUsed = LogicalTapeSetBlocks(state->tapeset) * (BLCKSZ / 1024);
2957  }
2958  else
2959  {
2961  stats->spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
2962  }
2963 
2964  switch (state->status)
2965  {
2966  case TSS_SORTEDINMEM:
2967  if (state->boundUsed)
2969  else
2971  break;
2972  case TSS_SORTEDONTAPE:
2974  break;
2975  case TSS_FINALMERGE:
2977  break;
2978  default:
2980  break;
2981  }
2982 }
int64 availMem
Definition: tuplesort.c:230
TupSortStatus status
Definition: tuplesort.c:222
TuplesortMethod sortMethod
Definition: tuplesort.h:56
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
int64 allowedMem
Definition: tuplesort.c:231
TuplesortSpaceType spaceType
Definition: tuplesort.h:57
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:889

◆ tuplesort_getdatum()

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

Definition at line 2082 of file tuplesort.c.

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

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

2084 {
2085  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2086  SortTuple stup;
2087 
2088  if (!tuplesort_gettuple_common(state, forward, &stup))
2089  {
2090  MemoryContextSwitchTo(oldcontext);
2091  return false;
2092  }
2093 
2094  /* Record abbreviated key for caller */
2095  if (state->sortKeys->abbrev_converter && abbrev)
2096  *abbrev = stup.datum1;
2097 
2098  if (stup.isnull1 || !state->tuples)
2099  {
2100  *val = stup.datum1;
2101  *isNull = stup.isnull1;
2102  }
2103  else
2104  {
2105  /* use stup.tuple because stup.datum1 may be an abbreviation */
2106  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2107  *isNull = false;
2108  }
2109 
2110  MemoryContextSwitchTo(oldcontext);
2111 
2112  return true;
2113 }
#define PointerGetDatum(X)
Definition: postgres.h:562
SortSupport sortKeys
Definition: tuplesort.c:383
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:160
bool isnull1
Definition: tuplesort.c:161
void * tuple
Definition: tuplesort.c:159
MemoryContext sortcontext
Definition: tuplesort.c:234
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1742
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:128
long val
Definition: informix.c:689

◆ tuplesort_getheaptuple()

HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2033 of file tuplesort.c.

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

Referenced by copy_heap_data().

2034 {
2035  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2036  SortTuple stup;
2037 
2038  if (!tuplesort_gettuple_common(state, forward, &stup))
2039  stup.tuple = NULL;
2040 
2041  MemoryContextSwitchTo(oldcontext);
2042 
2043  return stup.tuple;
2044 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:159
MemoryContext sortcontext
Definition: tuplesort.c:234
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1742

◆ tuplesort_getindextuple()

IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2053 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

2054 {
2055  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2056  SortTuple stup;
2057 
2058  if (!tuplesort_gettuple_common(state, forward, &stup))
2059  stup.tuple = NULL;
2060 
2061  MemoryContextSwitchTo(oldcontext);
2062 
2063  return (IndexTuple) stup.tuple;
2064 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:159
MemoryContext sortcontext
Definition: tuplesort.c:234
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1742

◆ tuplesort_gettuple_common()

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

Definition at line 1742 of file tuplesort.c.

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

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

1744 {
1745  unsigned int tuplen;
1746  size_t nmoved;
1747 
1748  switch (state->status)
1749  {
1750  case TSS_SORTEDINMEM:
1751  Assert(forward || state->randomAccess);
1752  Assert(!state->slabAllocatorUsed);
1753  if (forward)
1754  {
1755  if (state->current < state->memtupcount)
1756  {
1757  *stup = state->memtuples[state->current++];
1758  return true;
1759  }
1760  state->eof_reached = true;
1761 
1762  /*
1763  * Complain if caller tries to retrieve more tuples than
1764  * originally asked for in a bounded sort. This is because
1765  * returning EOF here might be the wrong thing.
1766  */
1767  if (state->bounded && state->current >= state->bound)
1768  elog(ERROR, "retrieved too many tuples in a bounded sort");
1769 
1770  return false;
1771  }
1772  else
1773  {
1774  if (state->current <= 0)
1775  return false;
1776 
1777  /*
1778  * if all tuples are fetched already then we return last
1779  * tuple, else - tuple before last returned.
1780  */
1781  if (state->eof_reached)
1782  state->eof_reached = false;
1783  else
1784  {
1785  state->current--; /* last returned tuple */
1786  if (state->current <= 0)
1787  return false;
1788  }
1789  *stup = state->memtuples[state->current - 1];
1790  return true;
1791  }
1792  break;
1793 
1794  case TSS_SORTEDONTAPE:
1795  Assert(forward || state->randomAccess);
1796  Assert(state->slabAllocatorUsed);
1797 
1798  /*
1799  * The slot that held the tuple that we returned in previous
1800  * gettuple call can now be reused.
1801  */
1802  if (state->lastReturnedTuple)
1803  {
1804  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1805  state->lastReturnedTuple = NULL;
1806  }
1807 
1808  if (forward)
1809  {
1810  if (state->eof_reached)
1811  return false;
1812 
1813  if ((tuplen = getlen(state, state->result_tape, true)) != 0)
1814  {
1815  READTUP(state, stup, state->result_tape, tuplen);
1816 
1817  /*
1818  * Remember the tuple we return, so that we can recycle
1819  * its memory on next call. (This can be NULL, in the
1820  * !state->tuples case).
1821  */
1822  state->lastReturnedTuple = stup->tuple;
1823 
1824  return true;
1825  }
1826  else
1827  {
1828  state->eof_reached = true;
1829  return false;
1830  }
1831  }
1832 
1833  /*
1834  * Backward.
1835  *
1836  * if all tuples are fetched already then we return last tuple,
1837  * else - tuple before last returned.
1838  */
1839  if (state->eof_reached)
1840  {
1841  /*
1842  * Seek position is pointing just past the zero tuplen at the
1843  * end of file; back up to fetch last tuple's ending length
1844  * word. If seek fails we must have a completely empty file.
1845  */
1846  nmoved = LogicalTapeBackspace(state->tapeset,
1847  state->result_tape,
1848  2 * sizeof(unsigned int));
1849  if (nmoved == 0)
1850  return false;
1851  else if (nmoved != 2 * sizeof(unsigned int))
1852  elog(ERROR, "unexpected tape position");
1853  state->eof_reached = false;
1854  }
1855  else
1856  {
1857  /*
1858  * Back up and fetch previously-returned tuple's ending length
1859  * word. If seek fails, assume we are at start of file.
1860  */
1861  nmoved = LogicalTapeBackspace(state->tapeset,
1862  state->result_tape,
1863  sizeof(unsigned int));
1864  if (nmoved == 0)
1865  return false;
1866  else if (nmoved != sizeof(unsigned int))
1867  elog(ERROR, "unexpected tape position");
1868  tuplen = getlen(state, state->result_tape, false);
1869 
1870  /*
1871  * Back up to get ending length word of tuple before it.
1872  */
1873  nmoved = LogicalTapeBackspace(state->tapeset,
1874  state->result_tape,
1875  tuplen + 2 * sizeof(unsigned int));
1876  if (nmoved == tuplen + sizeof(unsigned int))
1877  {
1878  /*
1879  * We backed up over the previous tuple, but there was no
1880  * ending length word before it. That means that the prev
1881  * tuple is the first tuple in the file. It is now the
1882  * next to read in forward direction (not obviously right,
1883  * but that is what in-memory case does).
1884  */
1885  return false;
1886  }
1887  else if (nmoved != tuplen + 2 * sizeof(unsigned int))
1888  elog(ERROR, "bogus tuple length in backward scan");
1889  }
1890 
1891  tuplen = getlen(state, state->result_tape, false);
1892 
1893  /*
1894  * Now we have the length of the prior tuple, back up and read it.
1895  * Note: READTUP expects we are positioned after the initial
1896  * length word of the tuple, so back up to that point.
1897  */
1898  nmoved = LogicalTapeBackspace(state->tapeset,
1899  state->result_tape,
1900  tuplen);
1901  if (nmoved != tuplen)
1902  elog(ERROR, "bogus tuple length in backward scan");
1903  READTUP(state, stup, state->result_tape, tuplen);
1904 
1905  /*
1906  * Remember the tuple we return, so that we can recycle its memory
1907  * on next call. (This can be NULL, in the Datum case).
1908  */
1909  state->lastReturnedTuple = stup->tuple;
1910 
1911  return true;
1912 
1913  case TSS_FINALMERGE:
1914  Assert(forward);
1915  /* We are managing memory ourselves, with the slab allocator. */
1916  Assert(state->slabAllocatorUsed);
1917 
1918  /*
1919  * The slab slot holding the tuple that we returned in previous
1920  * gettuple call can now be reused.
1921  */
1922  if (state->lastReturnedTuple)
1923  {
1924  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1925  state->lastReturnedTuple = NULL;
1926  }
1927 
1928  /*
1929  * This code should match the inner loop of mergeonerun().
1930  */
1931  if (state->memtupcount > 0)
1932  {
1933  int srcTape = state->memtuples[0].tupindex;
1934  SortTuple newtup;
1935 
1936  *stup = state->memtuples[0];
1937 
1938  /*
1939  * Remember the tuple we return, so that we can recycle its
1940  * memory on next call. (This can be NULL, in the Datum case).
1941  */
1942  state->lastReturnedTuple = stup->tuple;
1943 
1944  /*
1945  * Pull next tuple from tape, and replace the returned tuple
1946  * at top of the heap with it.
1947  */
1948  if (!mergereadnext(state, srcTape, &newtup))
1949  {
1950  /*
1951  * If no more data, we've reached end of run on this tape.
1952  * Remove the top node from the heap.
1953  */
1955 
1956  /*
1957  * Rewind to free the read buffer. It'd go away at the
1958  * end of the sort anyway, but better to release the
1959  * memory early.
1960  */
1961  LogicalTapeRewindForWrite(state->tapeset, srcTape);
1962  return true;
1963  }
1964  newtup.tupindex = srcTape;
1965  tuplesort_heap_replace_top(state, &newtup);
1966  return true;
1967  }
1968  return false;
1969 
1970  default:
1971  elog(ERROR, "invalid tuplesort state");
1972  return false; /* keep compiler quiet */
1973  }
1974 }
TupSortStatus status
Definition: tuplesort.c:222
bool randomAccess
Definition: tuplesort.c:224
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:629
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3262
void * tuple
Definition: tuplesort.c:159
#define ERROR
Definition: elog.h:43
void * lastReturnedTuple
Definition: tuplesort.c:330
size_t LogicalTapeBackspace(LogicalTapeSet *lts, int tapenum, size_t size)
Definition: logtape.c:768
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:464
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:449
static void tuplesort_heap_delete_top(Tuplesortstate *state)
Definition: tuplesort.c:3180
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2714
#define Assert(condition)
Definition: c.h:670
bool eof_reached
Definition: tuplesort.c:370
int tupindex
Definition: tuplesort.c:162
bool slabAllocatorUsed
Definition: tuplesort.c:315
#define elog
Definition: elog.h:219
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3204
SortTuple * memtuples
Definition: tuplesort.c:283

◆ tuplesort_gettupleslot()

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

Definition at line 1996 of file tuplesort.c.

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

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

1998 {
1999  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2000  SortTuple stup;
2001 
2002  if (!tuplesort_gettuple_common(state, forward, &stup))
2003  stup.tuple = NULL;
2004 
2005  MemoryContextSwitchTo(oldcontext);
2006 
2007  if (stup.tuple)
2008  {
2009  /* Record abbreviated key for caller */
2010  if (state->sortKeys->abbrev_converter && abbrev)
2011  *abbrev = stup.datum1;
2012 
2013  if (copy)
2015 
2016  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
2017  return true;
2018  }
2019  else
2020  {
2021  ExecClearTuple(slot);
2022  return false;
2023  }
2024 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:384
SortSupport sortKeys
Definition: tuplesort.c:383
TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: execTuples.c:439
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:160
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1480
void * tuple
Definition: tuplesort.c:159
MemoryContext sortcontext
Definition: tuplesort.c:234
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1742

◆ tuplesort_heap_delete_top()

static void tuplesort_heap_delete_top ( Tuplesortstate state)
static

Definition at line 3180 of file tuplesort.c.

References Tuplesortstate::memtupcount, Tuplesortstate::memtuples, and tuplesort_heap_replace_top().

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

3181 {
3182  SortTuple *memtuples = state->memtuples;
3183  SortTuple *tuple;
3184 
3185  if (--state->memtupcount <= 0)
3186  return;
3187 
3188  /*
3189  * Remove the last tuple in the heap, and re-insert it, by replacing the
3190  * current top node with it.
3191  */
3192  tuple = &memtuples[state->memtupcount];
3193  tuplesort_heap_replace_top(state, tuple);
3194 }
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple)
Definition: tuplesort.c:3204
SortTuple * memtuples
Definition: tuplesort.c:283

◆ tuplesort_heap_insert()

static void tuplesort_heap_insert ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 3145 of file tuplesort.c.

References Assert, CHECK_FOR_INTERRUPTS, COMPARETUP, i, Tuplesortstate::memtupcount, Tuplesortstate::memtuples, and Tuplesortstate::memtupsize.

Referenced by beginmerge(), and make_bounded_heap().

3146 {
3147  SortTuple *memtuples;
3148  int j;
3149 
3150  memtuples = state->memtuples;
3151  Assert(state->memtupcount < state->memtupsize);
3152 
3154 
3155  /*
3156  * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
3157  * using 1-based array indexes, not 0-based.
3158  */
3159  j = state->memtupcount++;
3160  while (j > 0)
3161  {
3162  int i = (j - 1) >> 1;
3163 
3164  if (COMPARETUP(state, tuple, &memtuples[i]) >= 0)
3165  break;
3166  memtuples[j] = memtuples[i];
3167  j = i;
3168  }
3169  memtuples[j] = *tuple;
3170 }
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:461
#define Assert(condition)
Definition: c.h:670
int i
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
SortTuple * memtuples
Definition: tuplesort.c:283

◆ tuplesort_heap_replace_top()

static void tuplesort_heap_replace_top ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 3204 of file tuplesort.c.

References Assert, CHECK_FOR_INTERRUPTS, COMPARETUP, i, Tuplesortstate::memtupcount, and Tuplesortstate::memtuples.

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

3205 {
3206  SortTuple *memtuples = state->memtuples;
3207  unsigned int i,
3208  n;
3209 
3210  Assert(state->memtupcount >= 1);
3211 
3213 
3214  /*
3215  * state->memtupcount is "int", but we use "unsigned int" for i, j, n.
3216  * This prevents overflow in the "2 * i + 1" calculation, since at the top
3217  * of the loop we must have i < n <= INT_MAX <= UINT_MAX/2.
3218  */
3219  n = state->memtupcount;
3220  i = 0; /* i is where the "hole" is */
3221  for (;;)
3222  {
3223  unsigned int j = 2 * i + 1;
3224 
3225  if (j >= n)
3226  break;
3227  if (j + 1 < n &&
3228  COMPARETUP(state, &memtuples[j], &memtuples[j + 1]) > 0)
3229  j++;
3230  if (COMPARETUP(state, tuple, &memtuples[j]) <= 0)
3231  break;
3232  memtuples[i] = memtuples[j];
3233  i = j;
3234  }
3235  memtuples[i] = *tuple;
3236 }
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:461
#define Assert(condition)
Definition: c.h:670
int i
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
SortTuple * memtuples
Definition: tuplesort.c:283

◆ tuplesort_markpos()

void tuplesort_markpos ( Tuplesortstate state)

Definition at line 2875 of file tuplesort.c.

References Assert, Tuplesortstate::current, elog, Tuplesortstate::eof_reached, ERROR, LogicalTapeTell(), Tuplesortstate::markpos_block, Tuplesortstate::markpos_eof, Tuplesortstate::markpos_offset, MemoryContextSwitchTo(), Tuplesortstate::randomAccess, Tuplesortstate::result_tape, Tuplesortstate::sortcontext, Tuplesortstate::status, Tuplesortstate::tapeset, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

Referenced by ExecSortMarkPos().

2876 {
2877  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2878 
2879  Assert(state->randomAccess);
2880 
2881  switch (state->status)
2882  {
2883  case TSS_SORTEDINMEM:
2884  state->markpos_offset = state->current;
2885  state->markpos_eof = state->eof_reached;
2886  break;
2887  case TSS_SORTEDONTAPE:
2888  LogicalTapeTell(state->tapeset,
2889  state->result_tape,
2890  &state->markpos_block,
2891  &state->markpos_offset);
2892  state->markpos_eof = state->eof_reached;
2893  break;
2894  default:
2895  elog(ERROR, "invalid tuplesort state");
2896  break;
2897  }
2898 
2899  MemoryContextSwitchTo(oldcontext);
2900 }
TupSortStatus status
Definition: tuplesort.c:222
bool randomAccess
Definition: tuplesort.c:224
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int markpos_offset
Definition: tuplesort.c:374
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:234
LogicalTapeSet * tapeset
Definition: tuplesort.c:236
void LogicalTapeTell(LogicalTapeSet *lts, int tapenum, long *blocknum, int *offset)
Definition: logtape.c:870
#define Assert(condition)
Definition: c.h:670
long markpos_block
Definition: tuplesort.c:373
bool eof_reached
Definition: tuplesort.c:370
bool markpos_eof
Definition: tuplesort.c:375
#define elog
Definition: elog.h:219

◆ tuplesort_merge_order()

int tuplesort_merge_order ( int64  allowedMem)

Definition at line 2188 of file tuplesort.c.

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

Referenced by cost_sort(), and inittapes().

2189 {
2190  int mOrder;
2191 
2192  /*
2193  * We need one tape for each merge input, plus another one for the output,
2194  * and each of these tapes needs buffer space. In addition we want
2195  * MERGE_BUFFER_SIZE workspace per input tape (but the output tape doesn't
2196  * count).
2197  *
2198  * Note: you might be thinking we need to account for the memtuples[]
2199  * array in this calculation, but we effectively treat that as part of the
2200  * MERGE_BUFFER_SIZE workspace.
2201  */
2202  mOrder = (allowedMem - TAPE_BUFFER_OVERHEAD) /
2204 
2205  /*
2206  * Even in minimum memory, use at least a MINORDER merge. On the other
2207  * hand, even when we have lots of memory, do not use more than a MAXORDER
2208  * merge. Tapes are pretty cheap, but they're not entirely free. Each
2209  * additional tape reduces the amount of memory available to build runs,
2210  * which in turn can cause the same sort to need more runs, which makes
2211  * merging slower even if it can still be done in a single pass. Also,
2212  * high order merges are quite slow due to CPU cache effects; it can be
2213  * faster to pay the I/O cost of a polyphase merge than to perform a
2214  * single merge pass across many hundreds of tapes.
2215  */
2216  mOrder = Max(mOrder, MINORDER);
2217  mOrder = Min(mOrder, MAXORDER);
2218 
2219  return mOrder;
2220 }
#define Min(x, y)
Definition: c.h:802
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:211
#define MERGE_BUFFER_SIZE
Definition: tuplesort.c:212
#define MINORDER
Definition: tuplesort.c:209
#define Max(x, y)
Definition: c.h:796
#define MAXORDER
Definition: tuplesort.c:210

◆ tuplesort_method_name()

const char* tuplesort_method_name ( TuplesortMethod  m)

Definition at line 2988 of file tuplesort.c.

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

Referenced by show_sort_info().

2989 {
2990  switch (m)
2991  {
2993  return "still in progress";
2995  return "top-N heapsort";
2996  case SORT_TYPE_QUICKSORT:
2997  return "quicksort";
2999  return "external sort";
3001  return "external merge";
3002  }
3003 
3004  return "unknown";
3005 }

◆ tuplesort_performsort()

void tuplesort_performsort ( Tuplesortstate state)

Definition at line 1656 of file tuplesort.c.

References Tuplesortstate::activeTapes, Tuplesortstate::current, dumptuples(), elog, Tuplesortstate::eof_reached, ERROR, LOG, Tuplesortstate::markpos_block, Tuplesortstate::markpos_eof, Tuplesortstate::markpos_offset, MemoryContextSwitchTo(), mergeruns(), pg_rusage_show(), Tuplesortstate::ru_start, sort_bounded_heap(), Tuplesortstate::sortcontext, Tuplesortstate::status, trace_sort, TSS_BOUNDED, TSS_BUILDRUNS, TSS_FINALMERGE, TSS_INITIAL, TSS_SORTEDINMEM, and tuplesort_sort_memtuples().

Referenced by _bt_leafbuild(), _h_indexbuild(), copy_heap_data(), ExecSort(), hypothetical_dense_rank_final(), hypothetical_rank_common(), initialize_phase(), mode_final(), percentile_cont_final_common(), percentile_cont_multi_final_common(), percentile_disc_final(), percentile_disc_multi_final(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), and validate_index().

1657 {
1658  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1659 
1660 #ifdef TRACE_SORT
1661  if (trace_sort)
1662  elog(LOG, "performsort starting: %s",
1663  pg_rusage_show(&state->ru_start));
1664 #endif
1665 
1666  switch (state->status)
1667  {
1668  case TSS_INITIAL:
1669 
1670  /*
1671  * We were able to accumulate all the tuples within the allowed
1672  * amount of memory. Just qsort 'em and we're done.
1673  */
1674  tuplesort_sort_memtuples(state);
1675  state->current = 0;
1676  state->eof_reached = false;
1677  state->markpos_offset = 0;
1678  state->markpos_eof = false;
1679  state->status = TSS_SORTEDINMEM;
1680  break;
1681 
1682  case TSS_BOUNDED:
1683 
1684  /*
1685  * We were able to accumulate all the tuples required for output
1686  * in memory, using a heap to eliminate excess tuples. Now we
1687  * have to transform the heap to a properly-sorted array.
1688  */
1689  sort_bounded_heap(state);
1690  state->current = 0;
1691  state->eof_reached = false;
1692  state->markpos_offset = 0;
1693  state->markpos_eof = false;
1694  state->status = TSS_SORTEDINMEM;
1695  break;
1696 
1697  case TSS_BUILDRUNS:
1698 
1699  /*
1700  * Finish tape-based sort. First, flush all tuples remaining in
1701  * memory out to tape; then merge until we have a single remaining
1702  * run (or, if !randomAccess, one run per tape). Note that
1703  * mergeruns sets the correct state->status.
1704  */
1705  dumptuples(state, true);
1706  mergeruns(state);
1707  state->eof_reached = false;
1708  state->markpos_block = 0L;
1709  state->markpos_offset = 0;
1710  state->markpos_eof = false;
1711  break;
1712 
1713  default:
1714  elog(ERROR, "invalid tuplesort state");
1715  break;
1716  }
1717 
1718 #ifdef TRACE_SORT
1719  if (trace_sort)
1720  {
1721  if (state->status == TSS_FINALMERGE)
1722  elog(LOG, "performsort done (except %d-way final merge): %s",
1723  state->activeTapes,
1724  pg_rusage_show(&state->ru_start));
1725  else
1726  elog(LOG, "performsort done: %s",
1727  pg_rusage_show(&state->ru_start));
1728  }
1729 #endif
1730 
1731  MemoryContextSwitchTo(oldcontext);
1732 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2739
TupSortStatus status
Definition: tuplesort.c:222
PGRUsage ru_start
Definition: tuplesort.c:434
static void sort_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3080
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define LOG
Definition: elog.h:26
int markpos_offset
Definition: tuplesort.c:374