PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
tuplesort.c File Reference
#include "postgres.h"
#include <limits.h>
#include "access/htup_details.h"
#include "access/nbtree.h"
#include "catalog/index.h"
#include "catalog/pg_am.h"
#include "commands/tablespace.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "pg_trace.h"
#include "utils/datum.h"
#include "utils/logtape.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/pg_rusage.h"
#include "utils/rel.h"
#include "utils/sortsupport.h"
#include "utils/tuplesort.h"
#include "qsort_tuple.c"
Include dependency graph for tuplesort.c:

Go to the source code of this file.

Data Structures

struct  SortTuple
 
union  SlabSlot
 
struct  Tuplesortstate
 

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 RUN_FIRST   0
 
#define HEAP_RUN_NEXT   INT_MAX
 
#define RUN_SECOND   1
 
#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)
 
#define HEAPCOMPARE(tup1, tup2)
 

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 bool useselection (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 dumpbatch (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, bool checkIndex)
 
static void tuplesort_heap_replace_top (Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
 
static void tuplesort_heap_delete_top (Tuplesortstate *state, bool checkIndex)
 
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 hash_mask, 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, 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, const char **sortMethod, const char **spaceType, long *spaceUsed)
 

Variables

bool trace_sort = false
 

Macro Definition Documentation

#define CLUSTER_SORT   3

Definition at line 150 of file tuplesort.c.

Referenced by tuplesort_begin_cluster().

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

Definition at line 517 of file tuplesort.c.

Referenced by make_bounded_heap(), and puttuple_common().

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

Definition at line 518 of file tuplesort.c.

Referenced by tuplesort_putheaptuple(), and tuplesort_puttupleslot().

#define DATUM_SORT   2

Definition at line 149 of file tuplesort.c.

Referenced by tuplesort_begin_datum().

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

Definition at line 261 of file tuplesort.c.

Referenced by dumptuples(), and puttuple_common().

#define HEAP_SORT   0

Definition at line 147 of file tuplesort.c.

Referenced by tuplesort_begin_heap().

#define HEAPCOMPARE (   tup1,
  tup2 
)
Value:
(checkIndex && ((tup1)->tupindex != (tup2)->tupindex || \
(tup1)->tupindex == HEAP_RUN_NEXT) ? \
((tup1)->tupindex) - ((tup2)->tupindex) : \
COMPARETUP(state, tup1, tup2))
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:517
Definition: regguts.h:298
#define HEAP_RUN_NEXT
Definition: tuplesort.c:261

Definition at line 3274 of file tuplesort.c.

Referenced by tuplesort_heap_insert(), and tuplesort_heap_replace_top().

#define INDEX_SORT   1

Definition at line 148 of file tuplesort.c.

Referenced by tuplesort_begin_index_btree().

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

Definition at line 497 of file tuplesort.c.

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

Definition at line 521 of file tuplesort.c.

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

#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
#define elog
Definition: elog.h:219

Definition at line 573 of file tuplesort.c.

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

#define MAXORDER   500 /* maximum merge order */

Definition at line 251 of file tuplesort.c.

Referenced by tuplesort_merge_order().

#define MERGE_BUFFER_SIZE   (BLCKSZ * 32)

Definition at line 253 of file tuplesort.c.

Referenced by tuplesort_merge_order().

#define MINORDER   6 /* minimum merge order */

Definition at line 250 of file tuplesort.c.

Referenced by tuplesort_merge_order().

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

Definition at line 520 of file tuplesort.c.

Referenced by mergereadnext(), and tuplesort_gettuple_common().

#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:950
static char * buf
Definition: pg_test_fsync.c:65
union SlabSlot SlabSlot
Definition: regguts.h:298
#define IS_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:497

Definition at line 505 of file tuplesort.c.

Referenced by mergeonerun(), and tuplesort_gettuple_common().

#define RUN_SECOND   1

Definition at line 262 of file tuplesort.c.

Referenced by dumptuples(), and mergeruns().

#define SLAB_SLOT_SIZE   1024

Definition at line 217 of file tuplesort.c.

Referenced by init_slab_allocator(), and readtup_alloc().

#define TAPE_BUFFER_OVERHEAD   BLCKSZ

Definition at line 252 of file tuplesort.c.

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

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

Definition at line 519 of file tuplesort.c.

Referenced by dumpbatch(), dumptuples(), and mergeonerun().

Typedef Documentation

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

Definition at line 264 of file tuplesort.c.

Enumeration Type Documentation

Enumerator
TSS_INITIAL 
TSS_BOUNDED 
TSS_BUILDRUNS 
TSS_SORTEDINMEM 
TSS_SORTEDONTAPE 
TSS_FINALMERGE 

Definition at line 229 of file tuplesort.c.

230 {
231  TSS_INITIAL, /* Loading tuples; still within memory limit */
232  TSS_BOUNDED, /* Loading tuples into bounded-size heap */
233  TSS_BUILDRUNS, /* Loading tuples; writing to tape */
234  TSS_SORTEDINMEM, /* Sort completed entirely in memory */
235  TSS_SORTEDONTAPE, /* Sort completed, final run is on tape */
236  TSS_FINALMERGE /* Performing final merge on-the-fly */
237 } TupSortStatus;
TupSortStatus
Definition: tuplesort.c:229

Function Documentation

static void beginmerge ( Tuplesortstate state)
static

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

2843 {
2844  int activeTapes;
2845  int tapenum;
2846  int srcTape;
2847 
2848  /* Heap should be empty here */
2849  Assert(state->memtupcount == 0);
2850 
2851  /* Adjust run counts and mark the active tapes */
2852  memset(state->mergeactive, 0,
2853  state->maxTapes * sizeof(*state->mergeactive));
2854  activeTapes = 0;
2855  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2856  {
2857  if (state->tp_dummy[tapenum] > 0)
2858  state->tp_dummy[tapenum]--;
2859  else
2860  {
2861  Assert(state->tp_runs[tapenum] > 0);
2862  state->tp_runs[tapenum]--;
2863  srcTape = state->tp_tapenum[tapenum];
2864  state->mergeactive[srcTape] = true;
2865  activeTapes++;
2866  }
2867  }
2868  Assert(activeTapes > 0);
2869  state->activeTapes = activeTapes;
2870 
2871  /* Load the merge heap with the first tuple from each input tape */
2872  for (srcTape = 0; srcTape < state->maxTapes; srcTape++)
2873  {
2874  SortTuple tup;
2875 
2876  if (mergereadnext(state, srcTape, &tup))
2877  {
2878  tup.tupindex = srcTape;
2879  tuplesort_heap_insert(state, &tup, false);
2880  }
2881  }
2882 }
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2890
#define Assert(condition)
Definition: c.h:675
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3411
int tupindex
Definition: tuplesort.c:203
int * tp_dummy
Definition: tuplesort.c:417
int * tp_tapenum
Definition: tuplesort.c:418
bool * mergeactive
Definition: tuplesort.c:406
static int comparetup_cluster ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

Definition at line 3782 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, NULL, ResetPerTupleExprContext, Tuplesortstate::sortKeys, Tuplesortstate::tupDesc, and SortTuple::tuple.

Referenced by tuplesort_begin_cluster().

3784 {
3785  SortSupport sortKey = state->sortKeys;
3786  HeapTuple ltup;
3787  HeapTuple rtup;
3788  TupleDesc tupDesc;
3789  int nkey;
3790  int32 compare;
3791  Datum datum1,
3792  datum2;
3793  bool isnull1,
3794  isnull2;
3795  AttrNumber leading = state->indexInfo->ii_KeyAttrNumbers[0];
3796 
3797  /* Be prepared to compare additional sort keys */
3798  ltup = (HeapTuple) a->tuple;
3799  rtup = (HeapTuple) b->tuple;
3800  tupDesc = state->tupDesc;
3801 
3802  /* Compare the leading sort key, if it's simple */
3803  if (leading != 0)
3804  {
3805  compare = ApplySortComparator(a->datum1, a->isnull1,
3806  b->datum1, b->isnull1,
3807  sortKey);
3808  if (compare != 0)
3809  return compare;
3810 
3811  if (sortKey->abbrev_converter)
3812  {
3813  datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
3814  datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
3815 
3816  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3817  datum2, isnull2,
3818  sortKey);
3819  }
3820  if (compare != 0 || state->nKeys == 1)
3821  return compare;
3822  /* Compare additional columns the hard way */
3823  sortKey++;
3824  nkey = 1;
3825  }
3826  else
3827  {
3828  /* Must compare all keys the hard way */
3829  nkey = 0;
3830  }
3831 
3832  if (state->indexInfo->ii_Expressions == NULL)
3833  {
3834  /* If not expression index, just compare the proper heap attrs */
3835 
3836  for (; nkey < state->nKeys; nkey++, sortKey++)
3837  {
3838  AttrNumber attno = state->indexInfo->ii_KeyAttrNumbers[nkey];
3839 
3840  datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
3841  datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
3842 
3843  compare = ApplySortComparator(datum1, isnull1,
3844  datum2, isnull2,
3845  sortKey);
3846  if (compare != 0)
3847  return compare;
3848  }
3849  }
3850  else
3851  {
3852  /*
3853  * In the expression index case, compute the whole index tuple and
3854  * then compare values. It would perhaps be faster to compute only as
3855  * many columns as we need to compare, but that would require
3856  * duplicating all the logic in FormIndexDatum.
3857  */
3858  Datum l_index_values[INDEX_MAX_KEYS];
3859  bool l_index_isnull[INDEX_MAX_KEYS];
3860  Datum r_index_values[INDEX_MAX_KEYS];
3861  bool r_index_isnull[INDEX_MAX_KEYS];
3862  TupleTableSlot *ecxt_scantuple;
3863 
3864  /* Reset context each time to prevent memory leakage */
3866 
3867  ecxt_scantuple = GetPerTupleExprContext(state->estate)->ecxt_scantuple;
3868 
3869  ExecStoreTuple(ltup, ecxt_scantuple, InvalidBuffer, false);
3870  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3871  l_index_values, l_index_isnull);
3872 
3873  ExecStoreTuple(rtup, ecxt_scantuple, InvalidBuffer, false);
3874  FormIndexDatum(state->indexInfo, ecxt_scantuple, state->estate,
3875  r_index_values, r_index_isnull);
3876 
3877  for (; nkey < state->nKeys; nkey++, sortKey++)
3878  {
3879  compare = ApplySortComparator(l_index_values[nkey],
3880  l_index_isnull[nkey],
3881  r_index_values[nkey],
3882  r_index_isnull[nkey],
3883  sortKey);
3884  if (compare != 0)
3885  return compare;
3886  }
3887  }
3888 
3889  return 0;
3890 }
void FormIndexDatum(IndexInfo *indexInfo, TupleTableSlot *slot, EState *estate, Datum *values, bool *isnull)
Definition: index.c:1764
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:347
EState * estate
Definition: tuplesort.c:463
SortSupport sortKeys
Definition: tuplesort.c:441
Datum datum1
Definition: tuplesort.c:201
#define InvalidBuffer
Definition: buf.h:25
bool isnull1
Definition: tuplesort.c:202
signed int int32
Definition: c.h:256
#define GetPerTupleExprContext(estate)
Definition: executor.h:338
void * tuple
Definition: tuplesort.c:200
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
IndexInfo * indexInfo
Definition: tuplesort.c:462
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:769
uintptr_t Datum
Definition: postgres.h:372
#define NULL
Definition: c.h:229
List * ii_Expressions
Definition: execnodes.h:69
#define INDEX_MAX_KEYS
AttrNumber ii_KeyAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:68
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
int16 AttrNumber
Definition: attnum.h:21
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
TupleDesc tupDesc
Definition: tuplesort.c:440
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239
static int comparetup_datum ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

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

4319 {
4320  int compare;
4321 
4322  compare = ApplySortComparator(a->datum1, a->isnull1,
4323  b->datum1, b->isnull1,
4324  state->sortKeys);
4325  if (compare != 0)
4326  return compare;
4327 
4328  /* if we have abbreviations, then "tuple" has the original value */
4329 
4330  if (state->sortKeys->abbrev_converter)
4332  PointerGetDatum(b->tuple), b->isnull1,
4333  state->sortKeys);
4334 
4335  return compare;
4336 }
#define PointerGetDatum(X)
Definition: postgres.h:562
SortSupport sortKeys
Definition: tuplesort.c:441
Datum datum1
Definition: tuplesort.c:201
bool isnull1
Definition: tuplesort.c:202
void * tuple
Definition: tuplesort.c:200
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239
static int comparetup_heap ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

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

3584 {
3585  SortSupport sortKey = state->sortKeys;
3586  HeapTupleData ltup;
3587  HeapTupleData rtup;
3588  TupleDesc tupDesc;
3589  int nkey;
3590  int32 compare;
3591  AttrNumber attno;
3592  Datum datum1,
3593  datum2;
3594  bool isnull1,
3595  isnull2;
3596 
3597 
3598  /* Compare the leading sort key */
3599  compare = ApplySortComparator(a->datum1, a->isnull1,
3600  b->datum1, b->isnull1,
3601  sortKey);
3602  if (compare != 0)
3603  return compare;
3604 
3605  /* Compare additional sort keys */
3606  ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3607  ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
3608  rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
3609  rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
3610  tupDesc = state->tupDesc;
3611 
3612  if (sortKey->abbrev_converter)
3613  {
3614  attno = sortKey->ssup_attno;
3615 
3616  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3617  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3618 
3619  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
3620  datum2, isnull2,
3621  sortKey);
3622  if (compare != 0)
3623  return compare;
3624  }
3625 
3626  sortKey++;
3627  for (nkey = 1; nkey < state->nKeys; nkey++, sortKey++)
3628  {
3629  attno = sortKey->ssup_attno;
3630 
3631  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
3632  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
3633 
3634  compare = ApplySortComparator(datum1, isnull1,
3635  datum2, isnull2,
3636  sortKey);
3637  if (compare != 0)
3638  return compare;
3639  }
3640 
3641  return 0;
3642 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:441
Datum datum1
Definition: tuplesort.c:201
bool isnull1
Definition: tuplesort.c:202
signed int int32
Definition: c.h:256
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:200
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
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:769
uintptr_t Datum
Definition: postgres.h:372
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:620
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
int16 AttrNumber
Definition: attnum.h:21
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
TupleDesc tupDesc
Definition: tuplesort.c:440
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239
static int comparetup_index_btree ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

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

4030 {
4031  /*
4032  * This is similar to comparetup_heap(), but expects index tuples. There
4033  * is also special handling for enforcing uniqueness, and special
4034  * treatment for equal keys at the end.
4035  */
4036  SortSupport sortKey = state->sortKeys;
4037  IndexTuple tuple1;
4038  IndexTuple tuple2;
4039  int keysz;
4040  TupleDesc tupDes;
4041  bool equal_hasnull = false;
4042  int nkey;
4043  int32 compare;
4044  Datum datum1,
4045  datum2;
4046  bool isnull1,
4047  isnull2;
4048 
4049 
4050  /* Compare the leading sort key */
4051  compare = ApplySortComparator(a->datum1, a->isnull1,
4052  b->datum1, b->isnull1,
4053  sortKey);
4054  if (compare != 0)
4055  return compare;
4056 
4057  /* Compare additional sort keys */
4058  tuple1 = (IndexTuple) a->tuple;
4059  tuple2 = (IndexTuple) b->tuple;
4060  keysz = state->nKeys;
4061  tupDes = RelationGetDescr(state->indexRel);
4062 
4063  if (sortKey->abbrev_converter)
4064  {
4065  datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
4066  datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
4067 
4068  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
4069  datum2, isnull2,
4070  sortKey);
4071  if (compare != 0)
4072  return compare;
4073  }
4074 
4075  /* they are equal, so we only need to examine one null flag */
4076  if (a->isnull1)
4077  equal_hasnull = true;
4078 
4079  sortKey++;
4080  for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
4081  {
4082  datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
4083  datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
4084 
4085  compare = ApplySortComparator(datum1, isnull1,
4086  datum2, isnull2,
4087  sortKey);
4088  if (compare != 0)
4089  return compare; /* done when we find unequal attributes */
4090 
4091  /* they are equal, so we only need to examine one null flag */
4092  if (isnull1)
4093  equal_hasnull = true;
4094  }
4095 
4096  /*
4097  * If btree has asked us to enforce uniqueness, complain if two equal
4098  * tuples are detected (unless there was at least one NULL field).
4099  *
4100  * It is sufficient to make the test here, because if two tuples are equal
4101  * they *must* get compared at some stage of the sort --- otherwise the
4102  * sort algorithm wouldn't have checked whether one must appear before the
4103  * other.
4104  */
4105  if (state->enforceUnique && !equal_hasnull)
4106  {
4108  bool isnull[INDEX_MAX_KEYS];
4109  char *key_desc;
4110 
4111  /*
4112  * Some rather brain-dead implementations of qsort (such as the one in
4113  * QNX 4) will sometimes call the comparison routine to compare a
4114  * value to itself, but we always use our own implementation, which
4115  * does not.
4116  */
4117  Assert(tuple1 != tuple2);
4118 
4119  index_deform_tuple(tuple1, tupDes, values, isnull);
4120 
4121  key_desc = BuildIndexValueDescription(state->indexRel, values, isnull);
4122 
4123  ereport(ERROR,
4124  (errcode(ERRCODE_UNIQUE_VIOLATION),
4125  errmsg("could not create unique index \"%s\"",
4127  key_desc ? errdetail("Key %s is duplicated.", key_desc) :
4128  errdetail("Duplicate keys exist."),
4129  errtableconstraint(state->heapRel,
4130  RelationGetRelationName(state->indexRel))));
4131  }
4132 
4133  /*
4134  * If key values are equal, we sort on ItemPointer. This does not affect
4135  * validity of the finished index, but it may be useful to have index
4136  * scans in physical order.
4137  */
4138  {
4139  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4140  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4141 
4142  if (blk1 != blk2)
4143  return (blk1 < blk2) ? -1 : 1;
4144  }
4145  {
4148 
4149  if (pos1 != pos2)
4150  return (pos1 < pos2) ? -1 : 1;
4151  }
4152 
4153  return 0;
4154 }
Relation heapRel
Definition: tuplesort.c:469
#define RelationGetDescr(relation)
Definition: rel.h:425
SortSupport sortKeys
Definition: tuplesort.c:441
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:201
int errcode(int sqlerrcode)
Definition: elog.c:575
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:202
signed int int32
Definition: c.h:256
uint16 OffsetNumber
Definition: off.h:24
void * tuple
Definition: tuplesort.c:200
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5209
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:433
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:416
#define ereport(elevel, rest)
Definition: elog.h:122
Relation indexRel
Definition: tuplesort.c:470
uintptr_t Datum
Definition: postgres.h:372
#define Assert(condition)
Definition: c.h:675
bool enforceUnique
Definition: tuplesort.c:473
#define INDEX_MAX_KEYS
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:76
static Datum values[MAXATTR]
Definition: bootstrap.c:162
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:66
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:201
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:239
static int comparetup_index_hash ( const SortTuple a,
const SortTuple b,
Tuplesortstate state 
)
static

Definition at line 4157 of file tuplesort.c.

References Assert, SortTuple::datum1, DatumGetUInt32, Tuplesortstate::hash_mask, SortTuple::isnull1, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, IndexTupleData::t_tid, and SortTuple::tuple.

Referenced by tuplesort_begin_index_hash().

4159 {
4160  uint32 hash1;
4161  uint32 hash2;
4162  IndexTuple tuple1;
4163  IndexTuple tuple2;
4164 
4165  /*
4166  * Fetch hash keys and mask off bits we don't want to sort by. We know
4167  * that the first column of the index tuple is the hash key.
4168  */
4169  Assert(!a->isnull1);
4170  hash1 = DatumGetUInt32(a->datum1) & state->hash_mask;
4171  Assert(!b->isnull1);
4172  hash2 = DatumGetUInt32(b->datum1) & state->hash_mask;
4173 
4174  if (hash1 > hash2)
4175  return 1;
4176  else if (hash1 < hash2)
4177  return -1;
4178 
4179  /*
4180  * If hash values are equal, we sort on ItemPointer. This does not affect
4181  * validity of the finished index, but it may be useful to have index
4182  * scans in physical order.
4183  */
4184  tuple1 = (IndexTuple) a->tuple;
4185  tuple2 = (IndexTuple) b->tuple;
4186 
4187  {
4188  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
4189  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
4190 
4191  if (blk1 != blk2)
4192  return (blk1 < blk2) ? -1 : 1;
4193  }
4194  {
4197 
4198  if (pos1 != pos2)
4199  return (pos1 < pos2) ? -1 : 1;
4200  }
4201 
4202  return 0;
4203 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
ItemPointerData t_tid
Definition: itup.h:37
Datum datum1
Definition: tuplesort.c:201
uint32 BlockNumber
Definition: block.h:31
bool isnull1
Definition: tuplesort.c:202
uint16 OffsetNumber
Definition: off.h:24
void * tuple
Definition: tuplesort.c:200
IndexTupleData * IndexTuple
Definition: itup.h:53
unsigned int uint32
Definition: c.h:268
#define Assert(condition)
Definition: c.h:675
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:76
uint32 hash_mask
Definition: tuplesort.c:476
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:66
static bool consider_abort_common ( Tuplesortstate state)
static

Definition at line 1719 of file tuplesort.c.

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

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

1720 {
1721  Assert(state->sortKeys[0].abbrev_converter != NULL);
1722  Assert(state->sortKeys[0].abbrev_abort != NULL);
1724 
1725  /*
1726  * Check effectiveness of abbreviation optimization. Consider aborting
1727  * when still within memory limit.
1728  */
1729  if (state->status == TSS_INITIAL &&
1730  state->memtupcount >= state->abbrevNext)
1731  {
1732  state->abbrevNext *= 2;
1733 
1734  /*
1735  * Check opclass-supplied abbreviation abort routine. It may indicate
1736  * that abbreviation should not proceed.
1737  */
1738  if (!state->sortKeys->abbrev_abort(state->memtupcount,
1739  state->sortKeys))
1740  return false;
1741 
1742  /*
1743  * Finally, restore authoritative comparator, and indicate that
1744  * abbreviation is not in play by setting abbrev_converter to NULL
1745  */
1746  state->sortKeys[0].comparator = state->sortKeys[0].abbrev_full_comparator;
1747  state->sortKeys[0].abbrev_converter = NULL;
1748  /* Not strictly necessary, but be tidy */
1749  state->sortKeys[0].abbrev_abort = NULL;
1750  state->sortKeys[0].abbrev_full_comparator = NULL;
1751 
1752  /* Give up - expect original pass-by-value representation */
1753  return true;
1754  }
1755 
1756  return false;
1757 }
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:107
TupSortStatus status
Definition: tuplesort.c:272
int64 abbrevNext
Definition: tuplesort.c:455
SortSupport sortKeys
Definition: tuplesort.c:441
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:192
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:183
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static void copytup_cluster ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

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

3894 {
3895  HeapTuple tuple = (HeapTuple) tup;
3896  Datum original;
3897  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3898 
3899  /* copy the tuple into sort storage */
3900  tuple = heap_copytuple(tuple);
3901  stup->tuple = (void *) tuple;
3902  USEMEM(state, GetMemoryChunkSpace(tuple));
3903 
3904  MemoryContextSwitchTo(oldcontext);
3905 
3906  /*
3907  * set up first-column key value, and potentially abbreviate, if it's a
3908  * simple column
3909  */
3910  if (state->indexInfo->ii_KeyAttrNumbers[0] == 0)
3911  return;
3912 
3913  original = heap_getattr(tuple,
3914  state->indexInfo->ii_KeyAttrNumbers[0],
3915  state->tupDesc,
3916  &stup->isnull1);
3917 
3918  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3919  {
3920  /*
3921  * Store ordinary Datum representation, or NULL value. If there is a
3922  * converter it won't expect NULL values, and cost model is not
3923  * required to account for NULL, so in that case we avoid calling
3924  * converter and just set datum1 to zeroed representation (to be
3925  * consistent, and to support cheap inequality tests for NULL
3926  * abbreviated keys).
3927  */
3928  stup->datum1 = original;
3929  }
3930  else if (!consider_abort_common(state))
3931  {
3932  /* Store abbreviated key representation */
3933  stup->datum1 = state->sortKeys->abbrev_converter(original,
3934  state->sortKeys);
3935  }
3936  else
3937  {
3938  /* Abort abbreviation */
3939  int i;
3940 
3941  stup->datum1 = original;
3942 
3943  /*
3944  * Set state to be consistent with never trying abbreviation.
3945  *
3946  * Alter datum1 representation in already-copied tuples, so as to
3947  * ensure a consistent representation (current tuple was just
3948  * handled). It does not matter if some dumped tuples are already
3949  * sorted on tape, since serialized tuples lack abbreviated keys
3950  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3951  */
3952  for (i = 0; i < state->memtupcount; i++)
3953  {
3954  SortTuple *mtup = &state->memtuples[i];
3955 
3956  tuple = (HeapTuple) mtup->tuple;
3957  mtup->datum1 = heap_getattr(tuple,
3958  state->indexInfo->ii_KeyAttrNumbers[0],
3959  state->tupDesc,
3960  &mtup->isnull1);
3961  }
3962  }
3963 }
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:608
HeapTupleData * HeapTuple
Definition: htup.h:70
SortSupport sortKeys
Definition: tuplesort.c:441
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:201
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool isnull1
Definition: tuplesort.c:202
void * tuple
Definition: tuplesort.c:200
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1719
IndexInfo * indexInfo
Definition: tuplesort.c:462
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:769
uintptr_t Datum
Definition: postgres.h:372
AttrNumber ii_KeyAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:68
MemoryContext tuplecontext
Definition: tuplesort.c:285
#define USEMEM(state, amt)
Definition: tuplesort.c:522
int i
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
TupleDesc tupDesc
Definition: tuplesort.c:440
SortTuple * memtuples
Definition: tuplesort.c:333
static void copytup_datum ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

Definition at line 4339 of file tuplesort.c.

References elog, and ERROR.

Referenced by tuplesort_begin_datum().

4340 {
4341  /* Not currently needed */
4342  elog(ERROR, "copytup_datum() should not be called");
4343 }
#define ERROR
Definition: elog.h:43
#define elog
Definition: elog.h:219
static void copytup_heap ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

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

3646 {
3647  /*
3648  * We expect the passed "tup" to be a TupleTableSlot, and form a
3649  * MinimalTuple using the exported interface for that.
3650  */
3651  TupleTableSlot *slot = (TupleTableSlot *) tup;
3652  Datum original;
3653  MinimalTuple tuple;
3654  HeapTupleData htup;
3655  MemoryContext oldcontext = MemoryContextSwitchTo(state->tuplecontext);
3656 
3657  /* copy the tuple into sort storage */
3658  tuple = ExecCopySlotMinimalTuple(slot);
3659  stup->tuple = (void *) tuple;
3660  USEMEM(state, GetMemoryChunkSpace(tuple));
3661  /* set up first-column key value */
3662  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3663  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3664  original = heap_getattr(&htup,
3665  state->sortKeys[0].ssup_attno,
3666  state->tupDesc,
3667  &stup->isnull1);
3668 
3669  MemoryContextSwitchTo(oldcontext);
3670 
3671  if (!state->sortKeys->abbrev_converter || stup->isnull1)
3672  {
3673  /*
3674  * Store ordinary Datum representation, or NULL value. If there is a
3675  * converter it won't expect NULL values, and cost model is not
3676  * required to account for NULL, so in that case we avoid calling
3677  * converter and just set datum1 to zeroed representation (to be
3678  * consistent, and to support cheap inequality tests for NULL
3679  * abbreviated keys).
3680  */
3681  stup->datum1 = original;
3682  }
3683  else if (!consider_abort_common(state))
3684  {
3685  /* Store abbreviated key representation */
3686  stup->datum1 = state->sortKeys->abbrev_converter(original,
3687  state->sortKeys);
3688  }
3689  else
3690  {
3691  /* Abort abbreviation */
3692  int i;
3693 
3694  stup->datum1 = original;
3695 
3696  /*
3697  * Set state to be consistent with never trying abbreviation.
3698  *
3699  * Alter datum1 representation in already-copied tuples, so as to
3700  * ensure a consistent representation (current tuple was just
3701  * handled). It does not matter if some dumped tuples are already
3702  * sorted on tape, since serialized tuples lack abbreviated keys
3703  * (TSS_BUILDRUNS state prevents control reaching here in any case).
3704  */
3705  for (i = 0; i < state->memtupcount; i++)
3706  {
3707  SortTuple *mtup = &state->memtuples[i];
3708 
3709  htup.t_len = ((MinimalTuple) mtup->tuple)->t_len +
3711  htup.t_data = (HeapTupleHeader) ((char *) mtup->tuple -
3713 
3714  mtup->datum1 = heap_getattr(&htup,
3715  state->sortKeys[0].ssup_attno,
3716  state->tupDesc,
3717  &mtup->isnull1);
3718  }
3719  }
3720 }
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:441
MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: execTuples.c:577
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:201
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool isnull1
Definition: tuplesort.c:202
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:200
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1719
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:769
uintptr_t Datum
Definition: postgres.h:372
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:620
MemoryContext tuplecontext
Definition: tuplesort.c:285
#define USEMEM(state, amt)
Definition: tuplesort.c:522
int i
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
TupleDesc tupDesc
Definition: tuplesort.c:440
SortTuple * memtuples
Definition: tuplesort.c:333
static void copytup_index ( Tuplesortstate state,
SortTuple stup,
void *  tup 
)
static

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

4207 {
4208  IndexTuple tuple = (IndexTuple) tup;
4209  unsigned int tuplen = IndexTupleSize(tuple);
4210  IndexTuple newtuple;
4211  Datum original;
4212 
4213  /* copy the tuple into sort storage */
4214  newtuple = (IndexTuple) MemoryContextAlloc(state->tuplecontext, tuplen);
4215  memcpy(newtuple, tuple, tuplen);
4216  USEMEM(state, GetMemoryChunkSpace(newtuple));
4217  stup->tuple = (void *) newtuple;
4218  /* set up first-column key value */
4219  original = index_getattr(newtuple,
4220  1,
4221  RelationGetDescr(state->indexRel),
4222  &stup->isnull1);
4223 
4224  if (!state->sortKeys->abbrev_converter || stup->isnull1)
4225  {
4226  /*
4227  * Store ordinary Datum representation, or NULL value. If there is a
4228  * converter it won't expect NULL values, and cost model is not
4229  * required to account for NULL, so in that case we avoid calling
4230  * converter and just set datum1 to zeroed representation (to be
4231  * consistent, and to support cheap inequality tests for NULL
4232  * abbreviated keys).
4233  */
4234  stup->datum1 = original;
4235  }
4236  else if (!consider_abort_common(state))
4237  {
4238  /* Store abbreviated key representation */
4239  stup->datum1 = state->sortKeys->abbrev_converter(original,
4240  state->sortKeys);
4241  }
4242  else
4243  {
4244  /* Abort abbreviation */
4245  int i;
4246 
4247  stup->datum1 = original;
4248 
4249  /*
4250  * Set state to be consistent with never trying abbreviation.
4251  *
4252  * Alter datum1 representation in already-copied tuples, so as to
4253  * ensure a consistent representation (current tuple was just
4254  * handled). It does not matter if some dumped tuples are already
4255  * sorted on tape, since serialized tuples lack abbreviated keys
4256  * (TSS_BUILDRUNS state prevents control reaching here in any case).
4257  */
4258  for (i = 0; i < state->memtupcount; i++)
4259  {
4260  SortTuple *mtup = &state->memtuples[i];
4261 
4262  tuple = (IndexTuple) mtup->tuple;
4263  mtup->datum1 = index_getattr(tuple,
4264  1,
4265  RelationGetDescr(state->indexRel),
4266  &mtup->isnull1);
4267  }
4268  }
4269 }
#define RelationGetDescr(relation)
Definition: rel.h:425
SortSupport sortKeys
Definition: tuplesort.c:441
Datum datum1
Definition: tuplesort.c:201
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool isnull1
Definition: tuplesort.c:202
void * tuple
Definition: tuplesort.c:200
static bool consider_abort_common(Tuplesortstate *state)
Definition: tuplesort.c:1719
IndexTupleData * IndexTuple
Definition: itup.h:53
Relation indexRel
Definition: tuplesort.c:470
uintptr_t Datum
Definition: postgres.h:372
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
MemoryContext tuplecontext
Definition: tuplesort.c:285
#define USEMEM(state, amt)
Definition: tuplesort.c:522
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:707
int i
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define IndexTupleSize(itup)
Definition: itup.h:70
SortTuple * memtuples
Definition: tuplesort.c:333
static void dumpbatch ( Tuplesortstate state,
bool  alltuples 
)
static

Definition at line 3022 of file tuplesort.c.

References Assert, Tuplesortstate::currentRun, Tuplesortstate::destTape, elog, ereport, errcode(), errmsg(), ERROR, i, LOG, markrunend(), MemoryContextReset(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, 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 dumptuples().

3023 {
3024  int memtupwrite;
3025  int i;
3026 
3027  /*
3028  * Final call might require no sorting, in rare cases where we just so
3029  * happen to have previously LACKMEM()'d at the point where exactly all
3030  * remaining tuples are loaded into memory, just before input was
3031  * exhausted.
3032  *
3033  * In general, short final runs are quite possible. Rather than allowing
3034  * a special case where there was a superfluous selectnewtape() call (i.e.
3035  * a call with no subsequent run actually written to destTape), we prefer
3036  * to write out a 0 tuple run.
3037  *
3038  * mergereadnext() is prepared for 0 tuple runs, and will reliably mark
3039  * the tape inactive for the merge when called from beginmerge(). This
3040  * case is therefore similar to the case where mergeonerun() finds a dummy
3041  * run for the tape, and so doesn't need to merge a run from the tape (or
3042  * conceptually "merges" the dummy run, if you prefer). According to
3043  * Knuth, Algorithm D "isn't strictly optimal" in its method of
3044  * distribution and dummy run assignment; this edge case seems very
3045  * unlikely to make that appreciably worse.
3046  */
3047  Assert(state->status == TSS_BUILDRUNS);
3048 
3049  /*
3050  * It seems unlikely that this limit will ever be exceeded, but take no
3051  * chances
3052  */
3053  if (state->currentRun == INT_MAX)
3054  ereport(ERROR,
3055  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
3056  errmsg("cannot have more than %d runs for an external sort",
3057  INT_MAX)));
3058 
3059  state->currentRun++;
3060 
3061 #ifdef TRACE_SORT
3062  if (trace_sort)
3063  elog(LOG, "starting quicksort of run %d: %s",
3064  state->currentRun, pg_rusage_show(&state->ru_start));
3065 #endif
3066 
3067  /*
3068  * Sort all tuples accumulated within the allowed amount of memory for
3069  * this run using quicksort
3070  */
3071  tuplesort_sort_memtuples(state);
3072 
3073 #ifdef TRACE_SORT
3074  if (trace_sort)
3075  elog(LOG, "finished quicksort of run %d: %s",
3076  state->currentRun, pg_rusage_show(&state->ru_start));
3077 #endif
3078 
3079  memtupwrite = state->memtupcount;
3080  for (i = 0; i < memtupwrite; i++)
3081  {
3082  WRITETUP(state, state->tp_tapenum[state->destTape],
3083  &state->memtuples[i]);
3084  state->memtupcount--;
3085  }
3086 
3087  /*
3088  * Reset tuple memory. We've freed all of the tuples that we previously
3089  * allocated. It's important to avoid fragmentation when there is a stark
3090  * change in the sizes of incoming tuples. Fragmentation due to
3091  * AllocSetFree's bucketing by size class might be particularly bad if
3092  * this step wasn't taken.
3093  */
3095 
3096  markrunend(state, state->tp_tapenum[state->destTape]);
3097  state->tp_runs[state->destTape]++;
3098  state->tp_dummy[state->destTape]--; /* per Alg D step D2 */
3099 
3100 #ifdef TRACE_SORT
3101  if (trace_sort)
3102  elog(LOG, "finished writing run %d to tape %d: %s",
3103  state->currentRun, state->destTape,
3104  pg_rusage_show(&state->ru_start));
3105 #endif
3106 
3107  if (!alltuples)
3108  selectnewtape(state);
3109 }
TupSortStatus status
Definition: tuplesort.c:272
PGRUsage ru_start
Definition: tuplesort.c:490
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:154
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3541
#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:2465
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:519
#define Assert(condition)
Definition: c.h:675
static void tuplesort_sort_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:3385
int * tp_dummy
Definition: tuplesort.c:417
MemoryContext tuplecontext
Definition: tuplesort.c:285
int errmsg(const char *fmt,...)
Definition: elog.c:797
int * tp_tapenum
Definition: tuplesort.c:418
int i
#define elog
Definition: elog.h:219
SortTuple * memtuples
Definition: tuplesort.c:333
static void dumptuples ( Tuplesortstate state,
bool  alltuples 
)
static

Definition at line 2930 of file tuplesort.c.

References Assert, Tuplesortstate::currentRun, Tuplesortstate::destTape, dumpbatch(), elog, HEAP_RUN_NEXT, LACKMEM, LOG, markrunend(), Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, pg_rusage_show(), Tuplesortstate::replaceActive, Tuplesortstate::ru_start, RUN_FIRST, RUN_SECOND, selectnewtape(), Tuplesortstate::tp_dummy, Tuplesortstate::tp_runs, Tuplesortstate::tp_tapenum, trace_sort, SortTuple::tupindex, tuplesort_heap_delete_top(), and WRITETUP.

Referenced by puttuple_common(), and tuplesort_performsort().

2931 {
2932  while (alltuples ||
2933  (LACKMEM(state) && state->memtupcount > 1) ||
2934  state->memtupcount >= state->memtupsize)
2935  {
2936  if (state->replaceActive)
2937  {
2938  /*
2939  * Still holding out for a case favorable to replacement
2940  * selection. Still incrementally spilling using heap.
2941  *
2942  * Dump the heap's frontmost entry, and remove it from the heap.
2943  */
2944  Assert(state->memtupcount > 0);
2945  WRITETUP(state, state->tp_tapenum[state->destTape],
2946  &state->memtuples[0]);
2947  tuplesort_heap_delete_top(state, true);
2948  }
2949  else
2950  {
2951  /*
2952  * Once committed to quicksorting runs, never incrementally spill
2953  */
2954  dumpbatch(state, alltuples);
2955  break;
2956  }
2957 
2958  /*
2959  * If top run number has changed, we've finished the current run (this
2960  * can only be the first run), and will no longer spill incrementally.
2961  */
2962  if (state->memtupcount == 0 ||
2963  state->memtuples[0].tupindex == HEAP_RUN_NEXT)
2964  {
2965  markrunend(state, state->tp_tapenum[state->destTape]);
2966  Assert(state->currentRun == RUN_FIRST);
2967  state->currentRun++;
2968  state->tp_runs[state->destTape]++;
2969  state->tp_dummy[state->destTape]--; /* per Alg D step D2 */
2970 
2971 #ifdef TRACE_SORT
2972  if (trace_sort)
2973  elog(LOG, "finished incrementally writing %s run %d to tape %d: %s",
2974  (state->memtupcount == 0) ? "only" : "first",
2975  state->currentRun, state->destTape,
2976  pg_rusage_show(&state->ru_start));
2977 #endif
2978 
2979  /*
2980  * Done if heap is empty, which is possible when there is only one
2981  * long run.
2982  */
2983  Assert(state->currentRun == RUN_SECOND);
2984  if (state->memtupcount == 0)
2985  {
2986  /*
2987  * Replacement selection best case; no final merge required,
2988  * because there was only one initial run (second run has no
2989  * tuples). See RUN_SECOND case in mergeruns().
2990  */
2991  break;
2992  }
2993 
2994  /*
2995  * Abandon replacement selection for second run (as well as any
2996  * subsequent runs).
2997  */
2998  state->replaceActive = false;
2999 
3000  /*
3001  * First tuple of next run should not be heapified, and so will
3002  * bear placeholder run number. In practice this must actually be
3003  * the second run, which just became the currentRun, so we're
3004  * clear to quicksort and dump the tuples in batch next time
3005  * memtuples becomes full.
3006  */
3007  Assert(state->memtuples[0].tupindex == HEAP_RUN_NEXT);
3008  selectnewtape(state);
3009  }
3010  }
3011 }
PGRUsage ru_start
Definition: tuplesort.c:490
static void tuplesort_heap_delete_top(Tuplesortstate *state, bool checkIndex)
Definition: tuplesort.c:3448
#define RUN_FIRST
Definition: tuplesort.c:260
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3541
bool replaceActive
Definition: tuplesort.c:387
static void dumpbatch(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:3022
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
static void selectnewtape(Tuplesortstate *state)
Definition: tuplesort.c:2465
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:519
#define Assert(condition)
Definition: c.h:675
int tupindex
Definition: tuplesort.c:203
#define HEAP_RUN_NEXT
Definition: tuplesort.c:261
int * tp_dummy
Definition: tuplesort.c:417
int * tp_tapenum
Definition: tuplesort.c:418
#define elog
Definition: elog.h:219
#define LACKMEM(state)
Definition: tuplesort.c:521
#define RUN_SECOND
Definition: tuplesort.c:262
SortTuple * memtuples
Definition: tuplesort.c:333
static void free_sort_tuple ( Tuplesortstate state,
SortTuple stup 
)
static

Definition at line 4427 of file tuplesort.c.

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

Referenced by make_bounded_heap(), and puttuple_common().

4428 {
4429  FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
4430  pfree(stup->tuple);
4431 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
void * tuple
Definition: tuplesort.c:200
void pfree(void *pointer)
Definition: mcxt.c:950
#define FREEMEM(state, amt)
Definition: tuplesort.c:523
static unsigned int getlen ( Tuplesortstate state,
int  tapenum,
bool  eofOK 
)
static

Definition at line 3528 of file tuplesort.c.

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

Referenced by mergereadnext(), and tuplesort_gettuple_common().

3529 {
3530  unsigned int len;
3531 
3532  if (LogicalTapeRead(state->tapeset, tapenum,
3533  &len, sizeof(len)) != sizeof(len))
3534  elog(ERROR, "unexpected end of tape");
3535  if (len == 0 && !eofOK)
3536  elog(ERROR, "unexpected end of data");
3537  return len;
3538 }
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:286
#define elog
Definition: elog.h:219
static bool grow_memtuples ( Tuplesortstate state)
static

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

1236 {
1237  int newmemtupsize;
1238  int memtupsize = state->memtupsize;
1239  int64 memNowUsed = state->allowedMem - state->availMem;
1240 
1241  /* Forget it if we've already maxed out memtuples, per comment above */
1242  if (!state->growmemtuples)
1243  return false;
1244 
1245  /* Select new value of memtupsize */
1246  if (memNowUsed <= state->availMem)
1247  {
1248  /*
1249  * We've used no more than half of allowedMem; double our usage,
1250  * clamping at INT_MAX tuples.
1251  */
1252  if (memtupsize < INT_MAX / 2)
1253  newmemtupsize = memtupsize * 2;
1254  else
1255  {
1256  newmemtupsize = INT_MAX;
1257  state->growmemtuples = false;
1258  }
1259  }
1260  else
1261  {
1262  /*
1263  * This will be the last increment of memtupsize. Abandon doubling
1264  * strategy and instead increase as much as we safely can.
1265  *
1266  * To stay within allowedMem, we can't increase memtupsize by more
1267  * than availMem / sizeof(SortTuple) elements. In practice, we want
1268  * to increase it by considerably less, because we need to leave some
1269  * space for the tuples to which the new array slots will refer. We
1270  * assume the new tuples will be about the same size as the tuples
1271  * we've already seen, and thus we can extrapolate from the space
1272  * consumption so far to estimate an appropriate new size for the
1273  * memtuples array. The optimal value might be higher or lower than
1274  * this estimate, but it's hard to know that in advance. We again
1275  * clamp at INT_MAX tuples.
1276  *
1277  * This calculation is safe against enlarging the array so much that
1278  * LACKMEM becomes true, because the memory currently used includes
1279  * the present array; thus, there would be enough allowedMem for the
1280  * new array elements even if no other memory were currently used.
1281  *
1282  * We do the arithmetic in float8, because otherwise the product of
1283  * memtupsize and allowedMem could overflow. Any inaccuracy in the
1284  * result should be insignificant; but even if we computed a
1285  * completely insane result, the checks below will prevent anything
1286  * really bad from happening.
1287  */
1288  double grow_ratio;
1289 
1290  grow_ratio = (double) state->allowedMem / (double) memNowUsed;
1291  if (memtupsize * grow_ratio < INT_MAX)
1292  newmemtupsize = (int) (memtupsize * grow_ratio);
1293  else
1294  newmemtupsize = INT_MAX;
1295 
1296  /* We won't make any further enlargement attempts */
1297  state->growmemtuples = false;
1298  }
1299 
1300  /* Must enlarge array by at least one element, else report failure */
1301  if (newmemtupsize <= memtupsize)
1302  goto noalloc;
1303 
1304  /*
1305  * On a 32-bit machine, allowedMem could exceed MaxAllocHugeSize. Clamp
1306  * to ensure our request won't be rejected. Note that we can easily
1307  * exhaust address space before facing this outcome. (This is presently
1308  * impossible due to guc.c's MAX_KILOBYTES limitation on work_mem, but
1309  * don't rely on that at this distance.)
1310  */
1311  if ((Size) newmemtupsize >= MaxAllocHugeSize / sizeof(SortTuple))
1312  {
1313  newmemtupsize = (int) (MaxAllocHugeSize / sizeof(SortTuple));
1314  state->growmemtuples = false; /* can't grow any more */
1315  }
1316 
1317  /*
1318  * We need to be sure that we do not cause LACKMEM to become true, else
1319  * the space management algorithm will go nuts. The code above should
1320  * never generate a dangerous request, but to be safe, check explicitly
1321  * that the array growth fits within availMem. (We could still cause
1322  * LACKMEM if the memory chunk overhead associated with the memtuples
1323  * array were to increase. That shouldn't happen because we chose the
1324  * initial array size large enough to ensure that palloc will be treating
1325  * both old and new arrays as separate chunks. But we'll check LACKMEM
1326  * explicitly below just in case.)
1327  */
1328  if (state->availMem < (int64) ((newmemtupsize - memtupsize) * sizeof(SortTuple)))
1329  goto noalloc;
1330 
1331  /* OK, do it */
1332  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
1333  state->memtupsize = newmemtupsize;
1334  state->memtuples = (SortTuple *)
1335  repalloc_huge(state->memtuples,
1336  state->memtupsize * sizeof(SortTuple));
1337  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
1338  if (LACKMEM(state))
1339  elog(ERROR, "unexpected out-of-memory situation in tuplesort");
1340  return true;
1341 
1342 noalloc:
1343  /* If for any reason we didn't realloc, shut off future attempts */
1344  state->growmemtuples = false;
1345  return false;
1346 }
int64 availMem
Definition: tuplesort.c:280
bool growmemtuples
Definition: tuplesort.c:336
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:523
int64 allowedMem
Definition: tuplesort.c:281
size_t Size
Definition: c.h:356
void * repalloc_huge(void *pointer, Size size)
Definition: mcxt.c:1031
#define USEMEM(state, amt)
Definition: tuplesort.c:522
#define elog
Definition: elog.h:219
#define LACKMEM(state)
Definition: tuplesort.c:521
SortTuple * memtuples
Definition: tuplesort.c:333
static void init_slab_allocator ( Tuplesortstate state,
int  numSlots 
)
static

Definition at line 2497 of file tuplesort.c.

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

Referenced by mergeruns().

2498 {
2499  if (numSlots > 0)
2500  {
2501  char *p;
2502  int i;
2503 
2504  state->slabMemoryBegin = palloc(numSlots * SLAB_SLOT_SIZE);
2505  state->slabMemoryEnd = state->slabMemoryBegin +
2506  numSlots * SLAB_SLOT_SIZE;
2507  state->slabFreeHead = (SlabSlot *) state->slabMemoryBegin;
2508  USEMEM(state, numSlots * SLAB_SLOT_SIZE);
2509 
2510  p = state->slabMemoryBegin;
2511  for (i = 0; i < numSlots - 1; i++)
2512  {
2513  ((SlabSlot *) p)->nextfree = (SlabSlot *) (p + SLAB_SLOT_SIZE);
2514  p += SLAB_SLOT_SIZE;
2515  }
2516  ((SlabSlot *) p)->nextfree = NULL;
2517  }
2518  else
2519  {
2520  state->slabMemoryBegin = state->slabMemoryEnd = NULL;
2521  state->slabFreeHead = NULL;
2522  }
2523  state->slabAllocatorUsed = true;
2524 }
char * slabMemoryEnd
Definition: tuplesort.c:368
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:217
char * slabMemoryBegin
Definition: tuplesort.c:367
#define NULL
Definition: c.h:229
bool slabAllocatorUsed
Definition: tuplesort.c:365
void * palloc(Size size)
Definition: mcxt.c:849
#define USEMEM(state, amt)
Definition: tuplesort.c:522
int i
SlabSlot * slabFreeHead
Definition: tuplesort.c:369
static void inittapes ( Tuplesortstate state)
static

Definition at line 2351 of file tuplesort.c.

References Tuplesortstate::allowedMem, Assert, Tuplesortstate::currentRun, Tuplesortstate::destTape, elog, GetMemoryChunkSpace(), Tuplesortstate::Level, LOG, LogicalTapeSetCreate(), Tuplesortstate::maxTapes, Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::mergeactive, palloc0(), pg_rusage_show(), PrepareTempTablespaces(), Tuplesortstate::replaceActive, Tuplesortstate::ru_start, RUN_FIRST, 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, SortTuple::tupindex, tuplesort_heap_insert(), tuplesort_merge_order(), USEMEM, and useselection().

Referenced by puttuple_common().

2352 {
2353  int maxTapes,
2354  j;
2355  int64 tapeSpace;
2356 
2357  /* Compute number of tapes to use: merge order plus 1 */
2358  maxTapes = tuplesort_merge_order(state->allowedMem) + 1;
2359 
2360  state->maxTapes = maxTapes;
2361  state->tapeRange = maxTapes - 1;
2362 
2363 #ifdef TRACE_SORT
2364  if (trace_sort)
2365  elog(LOG, "switching to external sort with %d tapes: %s",
2366  maxTapes, pg_rusage_show(&state->ru_start));
2367 #endif
2368 
2369  /*
2370  * Decrease availMem to reflect the space needed for tape buffers, when
2371  * writing the initial runs; but don't decrease it to the point that we
2372  * have no room for tuples. (That case is only likely to occur if sorting
2373  * pass-by-value Datums; in all other scenarios the memtuples[] array is
2374  * unlikely to occupy more than half of allowedMem. In the pass-by-value
2375  * case it's not important to account for tuple space, so we don't care if
2376  * LACKMEM becomes inaccurate.)
2377  */
2378  tapeSpace = (int64) maxTapes *TAPE_BUFFER_OVERHEAD;
2379 
2380  if (tapeSpace + GetMemoryChunkSpace(state->memtuples) < state->allowedMem)
2381  USEMEM(state, tapeSpace);
2382 
2383  /*
2384  * Make sure that the temp file(s) underlying the tape set are created in
2385  * suitable temp tablespaces.
2386  */
2388 
2389  /*
2390  * Create the tape set and allocate the per-tape data arrays.
2391  */
2392  state->tapeset = LogicalTapeSetCreate(maxTapes);
2393 
2394  state->mergeactive = (bool *) palloc0(maxTapes * sizeof(bool));
2395  state->tp_fib = (int *) palloc0(maxTapes * sizeof(int));
2396  state->tp_runs = (int *) palloc0(maxTapes * sizeof(int));
2397  state->tp_dummy = (int *) palloc0(maxTapes * sizeof(int));
2398  state->tp_tapenum = (int *) palloc0(maxTapes * sizeof(int));
2399 
2400  /*
2401  * Give replacement selection a try based on user setting. There will be
2402  * a switch to a simple hybrid sort-merge strategy after the first run
2403  * (iff we could not output one long run).
2404  */
2405  state->replaceActive = useselection(state);
2406 
2407  if (state->replaceActive)
2408  {
2409  /*
2410  * Convert the unsorted contents of memtuples[] into a heap. Each
2411  * tuple is marked as belonging to run number zero.
2412  *
2413  * NOTE: we pass false for checkIndex since there's no point in
2414  * comparing indexes in this step, even though we do intend the
2415  * indexes to be part of the sort key...
2416  */
2417  int ntuples = state->memtupcount;
2418 
2419 #ifdef TRACE_SORT
2420  if (trace_sort)
2421  elog(LOG, "replacement selection will sort %d first run tuples",
2422  state->memtupcount);
2423 #endif
2424  state->memtupcount = 0; /* make the heap empty */
2425 
2426  for (j = 0; j < ntuples; j++)
2427  {
2428  /* Must copy source tuple to avoid possible overwrite */
2429  SortTuple stup = state->memtuples[j];
2430 
2431  stup.tupindex = RUN_FIRST;
2432  tuplesort_heap_insert(state, &stup, false);
2433  }
2434  Assert(state->memtupcount == ntuples);
2435  }
2436 
2437  state->currentRun = RUN_FIRST;
2438 
2439  /*
2440  * Initialize variables of Algorithm D (step D1).
2441  */
2442  for (j = 0; j < maxTapes; j++)
2443  {
2444  state->tp_fib[j] = 1;
2445  state->tp_runs[j] = 0;
2446  state->tp_dummy[j] = 1;
2447  state->tp_tapenum[j] = j;
2448  }
2449  state->tp_fib[state->tapeRange] = 0;
2450  state->tp_dummy[state->tapeRange] = 0;
2451 
2452  state->Level = 1;
2453  state->destTape = 0;
2454 
2455  state->status = TSS_BUILDRUNS;
2456 }
TupSortStatus status
Definition: tuplesort.c:272
PGRUsage ru_start
Definition: tuplesort.c:490
#define RUN_FIRST
Definition: tuplesort.c:260
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
LogicalTapeSet * LogicalTapeSetCreate(int ntapes)
Definition: logtape.c:379
bool replaceActive
Definition: tuplesort.c:387
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:252
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:286
int64 allowedMem
Definition: tuplesort.c:281
void * palloc0(Size size)
Definition: mcxt.c:878
#define Assert(condition)
Definition: c.h:675
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3411
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2289
int tupindex
Definition: tuplesort.c:203
static bool useselection(Tuplesortstate *state)
Definition: tuplesort.c:2331
int * tp_dummy
Definition: tuplesort.c:417
int * tp_tapenum
Definition: tuplesort.c:418
#define USEMEM(state, amt)
Definition: tuplesort.c:522
#define elog
Definition: elog.h:219
bool * mergeactive
Definition: tuplesort.c:406
SortTuple * memtuples
Definition: tuplesort.c:333
static void make_bounded_heap ( Tuplesortstate state)
static

Definition at line 3294 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, SortTuple::tupindex, tuplesort_heap_insert(), and tuplesort_heap_replace_top().

Referenced by puttuple_common().

3295 {
3296  int tupcount = state->memtupcount;
3297  int i;
3298 
3299  Assert(state->status == TSS_INITIAL);
3300  Assert(state->bounded);
3301  Assert(tupcount >= state->bound);
3302 
3303  /* Reverse sort direction so largest entry will be at root */
3304  reversedirection(state);
3305 
3306  state->memtupcount = 0; /* make the heap empty */
3307  for (i = 0; i < tupcount; i++)
3308  {
3309  if (state->memtupcount < state->bound)
3310  {
3311  /* Insert next tuple into heap */
3312  /* Must copy source tuple to avoid possible overwrite */
3313  SortTuple stup = state->memtuples[i];
3314 
3315  stup.tupindex = 0; /* not used */
3316  tuplesort_heap_insert(state, &stup, false);
3317  }
3318  else
3319  {
3320  /*
3321  * The heap is full. Replace the largest entry with the new
3322  * tuple, or just discard it, if it's larger than anything already
3323  * in the heap.
3324  */
3325  if (COMPARETUP(state, &state->memtuples[i], &state->memtuples[0]) <= 0)
3326  {
3327  free_sort_tuple(state, &state->memtuples[i]);
3329  }
3330  else
3331  tuplesort_heap_replace_top(state, &state->memtuples[i], false);
3332  }
3333  }
3334 
3335  Assert(state->memtupcount == state->bound);
3336  state->status = TSS_BOUNDED;
3337 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3510
TupSortStatus status
Definition: tuplesort.c:272
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3473
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4427
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:517
#define Assert(condition)
Definition: c.h:675
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3411
int tupindex
Definition: tuplesort.c:203
int i
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:97
SortTuple * memtuples
Definition: tuplesort.c:333
static void markrunend ( Tuplesortstate state,
int  tapenum 
)
static

Definition at line 3541 of file tuplesort.c.

References LogicalTapeWrite(), and Tuplesortstate::tapeset.

Referenced by dumpbatch(), dumptuples(), and mergeonerun().

3542 {
3543  unsigned int len = 0;
3544 
3545  LogicalTapeWrite(state->tapeset, tapenum, (void *) &len, sizeof(len));
3546 }
void LogicalTapeWrite(LogicalTapeSet *lts, int tapenum, void *ptr, size_t size)
Definition: logtape.c:464
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
static void mergeonerun ( Tuplesortstate state)
static

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

2779 {
2780  int destTape = state->tp_tapenum[state->tapeRange];
2781  int srcTape;
2782 
2783  /*
2784  * Start the merge by loading one tuple from each active source tape into
2785  * the heap. We can also decrease the input run/dummy run counts.
2786  */
2787  beginmerge(state);
2788 
2789  /*
2790  * Execute merge by repeatedly extracting lowest tuple in heap, writing it
2791  * out, and replacing it with next tuple from same tape (if there is
2792  * another one).
2793  */
2794  while (state->memtupcount > 0)
2795  {
2796  SortTuple stup;
2797 
2798  /* write the tuple to destTape */
2799  srcTape = state->memtuples[0].tupindex;
2800  WRITETUP(state, destTape, &state->memtuples[0]);
2801 
2802  /* recycle the slot of the tuple we just wrote out, for the next read */
2803  if (state->memtuples[0].tuple)
2804  RELEASE_SLAB_SLOT(state, state->memtuples[0].tuple);
2805 
2806  /*
2807  * pull next tuple from the tape, and replace the written-out tuple in
2808  * the heap with it.
2809  */
2810  if (mergereadnext(state, srcTape, &stup))
2811  {
2812  stup.tupindex = srcTape;
2813  tuplesort_heap_replace_top(state, &stup, false);
2814 
2815  }
2816  else
2817  tuplesort_heap_delete_top(state, false);
2818  }
2819 
2820  /*
2821  * When the heap empties, we're done. Write an end-of-run marker on the
2822  * output tape, and increment its count of real runs.
2823  */
2824  markrunend(state, destTape);
2825  state->tp_runs[state->tapeRange]++;
2826 
2827 #ifdef TRACE_SORT
2828  if (trace_sort)
2829  elog(LOG, "finished %d-way merge step: %s", state->activeTapes,
2830  pg_rusage_show(&state->ru_start));
2831 #endif
2832 }
PGRUsage ru_start
Definition: tuplesort.c:490
static void tuplesort_heap_delete_top(Tuplesortstate *state, bool checkIndex)
Definition: tuplesort.c:3448
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
static void markrunend(Tuplesortstate *state, int tapenum)
Definition: tuplesort.c:3541
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3473
void * tuple
Definition: tuplesort.c:200
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define WRITETUP(state, tape, stup)
Definition: tuplesort.c:519
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:505
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2890
int tupindex
Definition: tuplesort.c:203
int * tp_tapenum
Definition: tuplesort.c:418
#define elog
Definition: elog.h:219
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:2842
SortTuple * memtuples
Definition: tuplesort.c:333
static bool mergereadnext ( Tuplesortstate state,
int  srcTape,
SortTuple stup 
)
static

Definition at line 2890 of file tuplesort.c.

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

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

2891 {
2892  unsigned int tuplen;
2893 
2894  if (!state->mergeactive[srcTape])
2895  return false; /* tape's run is already exhausted */
2896 
2897  /* read next tuple, if any */
2898  if ((tuplen = getlen(state, srcTape, true)) == 0)
2899  {
2900  state->mergeactive[srcTape] = false;
2901  return false;
2902  }
2903  READTUP(state, stup, srcTape, tuplen);
2904 
2905  return true;
2906 }
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3528
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:520
bool * mergeactive
Definition: tuplesort.c:406
static void mergeruns ( Tuplesortstate state)
static

Definition at line 2533 of file tuplesort.c.

References SortSupportData::abbrev_abort, SortSupportData::abbrev_converter, SortSupportData::abbrev_full_comparator, Assert, Tuplesortstate::availMem, beginmerge(), SortSupportData::comparator, Tuplesortstate::currentRun, Tuplesortstate::destTape, 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(), NULL, palloc(), pfree(), Tuplesortstate::randomAccess, Tuplesortstate::read_buffer_size, Tuplesortstate::result_tape, RUN_SECOND, 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().

2534 {
2535  int tapenum,
2536  svTape,
2537  svRuns,
2538  svDummy;
2539  int numTapes;
2540  int numInputTapes;
2541 
2542  Assert(state->status == TSS_BUILDRUNS);
2543  Assert(state->memtupcount == 0);
2544 
2545  if (state->sortKeys != NULL && state->sortKeys->abbrev_converter != NULL)
2546  {
2547  /*
2548  * If there are multiple runs to be merged, when we go to read back
2549  * tuples from disk, abbreviated keys will not have been stored, and
2550  * we don't care to regenerate them. Disable abbreviation from this
2551  * point on.
2552  */
2553  state->sortKeys->abbrev_converter = NULL;
2555 
2556  /* Not strictly necessary, but be tidy */
2557  state->sortKeys->abbrev_abort = NULL;
2559  }
2560 
2561  /*
2562  * Reset tuple memory. We've freed all the tuples that we previously
2563  * allocated. We will use the slab allocator from now on.
2564  */
2566  state->tuplecontext = NULL;
2567 
2568  /*
2569  * We no longer need a large memtuples array. (We will allocate a smaller
2570  * one for the heap later.)
2571  */
2572  FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
2573  pfree(state->memtuples);
2574  state->memtuples = NULL;
2575 
2576  /*
2577  * If we had fewer runs than tapes, refund the memory that we imagined we
2578  * would need for the tape buffers of the unused tapes.
2579  *
2580  * numTapes and numInputTapes reflect the actual number of tapes we will
2581  * use. Note that the output tape's tape number is maxTapes - 1, so the
2582  * tape numbers of the used tapes are not consecutive, and you cannot just
2583  * loop from 0 to numTapes to visit all used tapes!
2584  */
2585  if (state->Level == 1)
2586  {
2587  numInputTapes = state->currentRun;
2588  numTapes = numInputTapes + 1;
2589  FREEMEM(state, (state->maxTapes - numTapes) * TAPE_BUFFER_OVERHEAD);
2590  }
2591  else
2592  {
2593  numInputTapes = state->tapeRange;
2594  numTapes = state->maxTapes;
2595  }
2596 
2597  /*
2598  * Initialize the slab allocator. We need one slab slot per input tape,
2599  * for the tuples in the heap, plus one to hold the tuple last returned
2600  * from tuplesort_gettuple. (If we're sorting pass-by-val Datums,
2601  * however, we don't need to do allocate anything.)
2602  *
2603  * From this point on, we no longer use the USEMEM()/LACKMEM() mechanism
2604  * to track memory usage of individual tuples.
2605  */
2606  if (state->tuples)
2607  init_slab_allocator(state, numInputTapes + 1);
2608  else
2609  init_slab_allocator(state, 0);
2610 
2611  /*
2612  * If we produced only one initial run (quite likely if the total data
2613  * volume is between 1X and 2X workMem when replacement selection is used,
2614  * but something we particular count on when input is presorted), we can
2615  * just use that tape as the finished output, rather than doing a useless
2616  * merge. (This obvious optimization is not in Knuth's algorithm.)
2617  */
2618  if (state->currentRun == RUN_SECOND)
2619  {
2620  state->result_tape = state->tp_tapenum[state->destTape];
2621  /* must freeze and rewind the finished output tape */
2622  LogicalTapeFreeze(state->tapeset, state->result_tape);
2623  state->status = TSS_SORTEDONTAPE;
2624  return;
2625  }
2626 
2627  /*
2628  * Allocate a new 'memtuples' array, for the heap. It will hold one tuple
2629  * from each input tape.
2630  */
2631  state->memtupsize = numInputTapes;
2632  state->memtuples = (SortTuple *) palloc(numInputTapes * sizeof(SortTuple));
2633  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
2634 
2635  /*
2636  * Use all the remaining memory we have available for read buffers among
2637  * the input tapes.
2638  *
2639  * We do this only after checking for the case that we produced only one
2640  * initial run, because there is no need to use a large read buffer when
2641  * we're reading from a single tape. With one tape, the I/O pattern will
2642  * be the same regardless of the buffer size.
2643  *
2644  * We don't try to "rebalance" the memory among tapes, when we start a new
2645  * merge phase, even if some tapes are inactive in the new phase. That
2646  * would be hard, because logtape.c doesn't know where one run ends and
2647  * another begins. When a new merge phase begins, and a tape doesn't
2648  * participate in it, its buffer nevertheless already contains tuples from
2649  * the next run on same tape, so we cannot release the buffer. That's OK
2650  * in practice, merge performance isn't that sensitive to the amount of
2651  * buffers used, and most merge phases use all or almost all tapes,
2652  * anyway.
2653  */
2654 #ifdef TRACE_SORT
2655  if (trace_sort)
2656  elog(LOG, "using " INT64_FORMAT " KB of memory for read buffers among %d input tapes",
2657  (state->availMem) / 1024, numInputTapes);
2658 #endif
2659 
2660  state->read_buffer_size = Max(state->availMem / numInputTapes, 0);
2661  USEMEM(state, state->read_buffer_size * numInputTapes);
2662 
2663  /* End of step D2: rewind all output tapes to prepare for merging */
2664  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2665  LogicalTapeRewindForRead(state->tapeset, tapenum, state->read_buffer_size);
2666 
2667  for (;;)
2668  {
2669  /*
2670  * At this point we know that tape[T] is empty. If there's just one
2671  * (real or dummy) run left on each input tape, then only one merge
2672  * pass remains. If we don't have to produce a materialized sorted
2673  * tape, we can stop at this point and do the final merge on-the-fly.
2674  */
2675  if (!state->randomAccess)
2676  {
2677  bool allOneRun = true;
2678 
2679  Assert(state->tp_runs[state->tapeRange] == 0);
2680  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2681  {
2682  if (state->tp_runs[tapenum] + state->tp_dummy[tapenum] != 1)
2683  {
2684  allOneRun = false;
2685  break;
2686  }
2687  }
2688  if (allOneRun)
2689  {
2690  /* Tell logtape.c we won't be writing anymore */
2692  /* Initialize for the final merge pass */
2693  beginmerge(state);
2694  state->status = TSS_FINALMERGE;
2695  return;
2696  }
2697  }
2698 
2699  /* Step D5: merge runs onto tape[T] until tape[P] is empty */
2700  while (state->tp_runs[state->tapeRange - 1] ||
2701  state->tp_dummy[state->tapeRange - 1])
2702  {
2703  bool allDummy = true;
2704 
2705  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2706  {
2707  if (state->tp_dummy[tapenum] == 0)
2708  {
2709  allDummy = false;
2710  break;
2711  }
2712  }
2713 
2714  if (allDummy)
2715  {
2716  state->tp_dummy[state->tapeRange]++;
2717  for (tapenum = 0; tapenum < state->tapeRange; tapenum++)
2718  state->tp_dummy[tapenum]--;
2719  }
2720  else
2721  mergeonerun(state);
2722  }
2723 
2724  /* Step D6: decrease level */
2725  if (--state->Level == 0)
2726  break;
2727  /* rewind output tape T to use as new input */
2728  LogicalTapeRewindForRead(state->tapeset, state->tp_tapenum[state->tapeRange],
2729  state->read_buffer_size);
2730  /* rewind used-up input tape P, and prepare it for write pass */
2731  LogicalTapeRewindForWrite(state->tapeset, state->tp_tapenum[state->tapeRange - 1]);
2732  state->tp_runs[state->tapeRange - 1] = 0;
2733 
2734  /*
2735  * reassign tape units per step D6; note we no longer care about A[]
2736  */
2737  svTape = state->tp_tapenum[state->tapeRange];
2738  svDummy = state->tp_dummy[state->tapeRange];
2739  svRuns = state->tp_runs[state->tapeRange];
2740  for (tapenum = state->tapeRange; tapenum > 0; tapenum--)
2741  {
2742  state->tp_tapenum[tapenum] = state->tp_tapenum[tapenum - 1];
2743  state->tp_dummy[tapenum] = state->tp_dummy[tapenum - 1];
2744  state->tp_runs[tapenum] = state->tp_runs[tapenum - 1];
2745  }
2746  state->tp_tapenum[0] = svTape;
2747  state->tp_dummy[0] = svDummy;
2748  state->tp_runs[0] = svRuns;
2749  }
2750 
2751  /*
2752  * Done. Knuth says that the result is on TAPE[1], but since we exited
2753  * the loop without performing the last iteration of step D6, we have not
2754  * rearranged the tape unit assignment, and therefore the result is on
2755  * TAPE[T]. We need to do it this way so that we can freeze the final
2756  * output tape while rewinding it. The last iteration of step D6 would be
2757  * a waste of cycles anyway...
2758  */
2759  state->result_tape = state->tp_tapenum[state->tapeRange];
2760  LogicalTapeFreeze(state->tapeset, state->result_tape);
2761  state->status = TSS_SORTEDONTAPE;
2762 
2763  /* Release the read buffers of all the other tapes, by rewinding them. */
2764  for (tapenum = 0; tapenum < state->maxTapes; tapenum++)
2765  {
2766  if (tapenum != state->result_tape)
2767  LogicalTapeRewindForWrite(state->tapeset, tapenum);
2768  }
2769 }
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:107
int64 availMem
Definition: tuplesort.c:280
size_t read_buffer_size
Definition: tuplesort.c:372
TupSortStatus status
Definition: tuplesort.c:272
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:200
static void mergeonerun(Tuplesortstate *state)
Definition: tuplesort.c:2778
SortSupport sortKeys
Definition: tuplesort.c:441
bool randomAccess
Definition: tuplesort.c:274
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:629
static void init_slab_allocator(Tuplesortstate *state, int numSlots)
Definition: tuplesort.c:2497
#define TAPE_BUFFER_OVERHEAD
Definition: tuplesort.c:252
void pfree(void *pointer)
Definition: mcxt.c:950
#define FREEMEM(state, amt)
Definition: tuplesort.c:523
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:192
#define Max(x, y)
Definition: c.h:800
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define INT64_FORMAT
Definition: c.h:315
void LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Definition: logtape.c:551
int * tp_dummy
Definition: tuplesort.c:417
MemoryContext tuplecontext
Definition: tuplesort.c:285
void * palloc(Size size)
Definition: mcxt.c:849
int * tp_tapenum
Definition: tuplesort.c:418
#define USEMEM(state, amt)
Definition: tuplesort.c:522
#define elog
Definition: elog.h:219
void LogicalTapeSetForgetFreeSpace(LogicalTapeSet *lts)
Definition: logtape.c:453
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:183
static void beginmerge(Tuplesortstate *state)
Definition: tuplesort.c:2842
void LogicalTapeFreeze(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:703
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
#define RUN_SECOND
Definition: tuplesort.c:262
SortTuple * memtuples
Definition: tuplesort.c:333
static void puttuple_common ( Tuplesortstate state,
SortTuple tuple 
)
static

Definition at line 1557 of file tuplesort.c.

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

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

1558 {
1559  switch (state->status)
1560  {
1561  case TSS_INITIAL:
1562 
1563  /*
1564  * Save the tuple into the unsorted array. First, grow the array
1565  * as needed. Note that we try to grow the array when there is
1566  * still one free slot remaining --- if we fail, there'll still be
1567  * room to store the incoming tuple, and then we'll switch to
1568  * tape-based operation.
1569  */
1570  if (state->memtupcount >= state->memtupsize - 1)
1571  {
1572  (void) grow_memtuples(state);
1573  Assert(state->memtupcount < state->memtupsize);
1574  }
1575  state->memtuples[state->memtupcount++] = *tuple;
1576 
1577  /*
1578  * Check if it's time to switch over to a bounded heapsort. We do
1579  * so if the input tuple count exceeds twice the desired tuple
1580  * count (this is a heuristic for where heapsort becomes cheaper
1581  * than a quicksort), or if we've just filled workMem and have
1582  * enough tuples to meet the bound.
1583  *
1584  * Note that once we enter TSS_BOUNDED state we will always try to
1585  * complete the sort that way. In the worst case, if later input
1586  * tuples are larger than earlier ones, this might cause us to
1587  * exceed workMem significantly.
1588  */
1589  if (state->bounded &&
1590  (state->memtupcount > state->bound * 2 ||
1591  (state->memtupcount > state->bound && LACKMEM(state))))
1592  {
1593 #ifdef TRACE_SORT
1594  if (trace_sort)
1595  elog(LOG, "switching to bounded heapsort at %d tuples: %s",
1596  state->memtupcount,
1597  pg_rusage_show(&state->ru_start));
1598 #endif
1599  make_bounded_heap(state);
1600  return;
1601  }
1602 
1603  /*
1604  * Done if we still fit in available memory and have array slots.
1605  */
1606  if (state->memtupcount < state->memtupsize && !LACKMEM(state))
1607  return;
1608 
1609  /*
1610  * Nope; time to switch to tape-based operation.
1611  */
1612  inittapes(state);
1613 
1614  /*
1615  * Dump tuples until we are back under the limit.
1616  */
1617  dumptuples(state, false);
1618  break;
1619 
1620  case TSS_BOUNDED:
1621 
1622  /*
1623  * We don't want to grow the array here, so check whether the new
1624  * tuple can be discarded before putting it in. This should be a
1625  * good speed optimization, too, since when there are many more
1626  * input tuples than the bound, most input tuples can be discarded
1627  * with just this one comparison. Note that because we currently
1628  * have the sort direction reversed, we must check for <= not >=.
1629  */
1630  if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
1631  {
1632  /* new tuple <= top of the heap, so we can discard it */
1633  free_sort_tuple(state, tuple);
1635  }
1636  else
1637  {
1638  /* discard top of heap, replacing it with the new tuple */
1639  free_sort_tuple(state, &state->memtuples[0]);
1640  tuple->tupindex = 0; /* not used */
1641  tuplesort_heap_replace_top(state, tuple, false);
1642  }
1643  break;
1644 
1645  case TSS_BUILDRUNS:
1646 
1647  /*
1648  * Insert the tuple into the heap, with run number currentRun if
1649  * it can go into the current run, else HEAP_RUN_NEXT. The tuple
1650  * can go into the current run if it is >= the first
1651  * not-yet-output tuple. (Actually, it could go into the current
1652  * run if it is >= the most recently output tuple ... but that
1653  * would require keeping around the tuple we last output, and it's
1654  * simplest to let writetup free each tuple as soon as it's
1655  * written.)
1656  *
1657  * Note that this only applies when:
1658  *
1659  * - currentRun is RUN_FIRST
1660  *
1661  * - Replacement selection is in use (typically it is never used).
1662  *
1663  * When these two conditions are not both true, all tuples are
1664  * appended indifferently, much like the TSS_INITIAL case.
1665  *
1666  * There should always be room to store the incoming tuple.
1667  */
1668  Assert(!state->replaceActive || state->memtupcount > 0);
1669  if (state->replaceActive &&
1670  COMPARETUP(state, tuple, &state->memtuples[0]) >= 0)
1671  {
1672  Assert(state->currentRun == RUN_FIRST);
1673 
1674  /*
1675  * Insert tuple into first, fully heapified run.
1676  *
1677  * Unlike classic replacement selection, which this module was
1678  * previously based on, only RUN_FIRST tuples are fully
1679  * heapified. Any second/next run tuples are appended
1680  * indifferently. While HEAP_RUN_NEXT tuples may be sifted
1681  * out of the way of first run tuples, COMPARETUP() will never
1682  * be called for the run's tuples during sifting (only our
1683  * initial COMPARETUP() call is required for the tuple, to
1684  * determine that the tuple does not belong in RUN_FIRST).
1685  */
1686  tuple->tupindex = state->currentRun;
1687  tuplesort_heap_insert(state, tuple, true);
1688  }
1689  else
1690  {
1691  /*
1692  * Tuple was determined to not belong to heapified RUN_FIRST,
1693  * or replacement selection not in play. Append the tuple to
1694  * memtuples indifferently.
1695  *
1696  * dumptuples() does not trust that the next run's tuples are
1697  * heapified. Anything past the first run will always be
1698  * quicksorted even when replacement selection is initially
1699  * used. (When it's never used, every tuple still takes this
1700  * path.)
1701  */
1702  tuple->tupindex = HEAP_RUN_NEXT;
1703  state->memtuples[state->memtupcount++] = *tuple;
1704  }
1705 
1706  /*
1707  * If we are over the memory limit, dump tuples till we're under.
1708  */
1709  dumptuples(state, false);
1710  break;
1711 
1712  default:
1713  elog(ERROR, "invalid tuplesort state");
1714  break;
1715  }
1716 }
static void dumptuples(Tuplesortstate *state, bool alltuples)
Definition: tuplesort.c:2930
TupSortStatus status
Definition: tuplesort.c:272
static bool grow_memtuples(Tuplesortstate *state)
Definition: tuplesort.c:1235
PGRUsage ru_start
Definition: tuplesort.c:490
#define RUN_FIRST
Definition: tuplesort.c:260
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3473
bool replaceActive
Definition: tuplesort.c:387
#define ERROR
Definition: elog.h:43
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
Definition: tuplesort.c:4427
#define COMPARETUP(state, a, b)
Definition: tuplesort.c:517
const char * pg_rusage_show(const PGRUsage *ru0)
Definition: pg_rusage.c:40
#define Assert(condition)
Definition: c.h:675
static void inittapes(Tuplesortstate *state)
Definition: tuplesort.c:2351
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3411
int tupindex
Definition: tuplesort.c:203
#define HEAP_RUN_NEXT
Definition: tuplesort.c:261
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:97
#define elog
Definition: elog.h:219
static void make_bounded_heap(Tuplesortstate *state)
Definition: tuplesort.c:3294
#define LACKMEM(state)
Definition: tuplesort.c:521
SortTuple * memtuples
Definition: tuplesort.c:333
static void * readtup_alloc ( Tuplesortstate state,
Size  tuplen 
)
static

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

3556 {
3557  SlabSlot *buf;
3558 
3559  /*
3560  * We pre-allocate enough slots in the slab arena that we should never run
3561  * out.
3562  */
3563  Assert(state->slabFreeHead);
3564 
3565  if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
3566  return MemoryContextAlloc(state->sortcontext, tuplen);
3567  else
3568  {
3569  buf = state->slabFreeHead;
3570  /* Reuse this slot */
3571  state->slabFreeHead = buf->nextfree;
3572 
3573  return buf;
3574  }
3575 }
#define SLAB_SLOT_SIZE
Definition: tuplesort.c:217
union SlabSlot * nextfree
Definition: tuplesort.c:221
MemoryContext sortcontext
Definition: tuplesort.c:284
static char * buf
Definition: pg_test_fsync.c:65
#define Assert(condition)
Definition: c.h:675
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:707
SlabSlot * slabFreeHead
Definition: tuplesort.c:369
static void readtup_cluster ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

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

3992 {
3993  unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
3994  HeapTuple tuple = (HeapTuple) readtup_alloc(state,
3995  t_len + HEAPTUPLESIZE);
3996 
3997  /* Reconstruct the HeapTupleData header */
3998  tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
3999  tuple->t_len = t_len;
4000  LogicalTapeReadExact(state->tapeset, tapenum,
4001  &tuple->t_self, sizeof(ItemPointerData));
4002  /* We don't currently bother to reconstruct t_tableOid */
4003  tuple->t_tableOid = InvalidOid;
4004  /* Read in the tuple body */
4005  LogicalTapeReadExact(state->tapeset, tapenum,
4006  tuple->t_data, tuple->t_len);
4007  if (state->randomAccess) /* need trailing length word? */
4008  LogicalTapeReadExact(state->tapeset, tapenum,
4009  &tuplen, sizeof(tuplen));
4010  stup->tuple = (void *) tuple;
4011  /* set up first-column key value, if it's a simple column */
4012  if (state->indexInfo->ii_KeyAttrNumbers[0] != 0)
4013  stup->datum1 = heap_getattr(tuple,
4014  state->indexInfo->ii_KeyAttrNumbers[0],
4015  state->tupDesc,
4016  &stup->isnull1);
4017 }
HeapTupleData * HeapTuple
Definition: htup.h:70
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
bool randomAccess
Definition: tuplesort.c:274
Datum datum1
Definition: tuplesort.c:201
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:573
bool isnull1
Definition: tuplesort.c:202
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:200
ItemPointerData t_self
Definition: htup.h:65
uint32 t_len
Definition: htup.h:64
IndexInfo * indexInfo
Definition: tuplesort.c:462
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
Oid t_tableOid
Definition: htup.h:66
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:769
#define InvalidOid
Definition: postgres_ext.h:36
struct ItemPointerData ItemPointerData
AttrNumber ii_KeyAttrNumbers[INDEX_MAX_KEYS]
Definition: execnodes.h:68
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3555
#define HEAPTUPLESIZE
Definition: htup.h:72
TupleDesc tupDesc
Definition: tuplesort.c:440
static void readtup_datum ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

Definition at line 4387 of file tuplesort.c.

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

Referenced by tuplesort_begin_datum().

4389 {
4390  unsigned int tuplen = len - sizeof(unsigned int);
4391 
4392  if (tuplen == 0)
4393  {
4394  /* it's NULL */
4395  stup->datum1 = (Datum) 0;
4396  stup->isnull1 = true;
4397  stup->tuple = NULL;
4398  }
4399  else if (!state->tuples)
4400  {
4401  Assert(tuplen == sizeof(Datum));
4402  LogicalTapeReadExact(state->tapeset, tapenum,
4403  &stup->datum1, tuplen);
4404  stup->isnull1 = false;
4405  stup->tuple = NULL;
4406  }
4407  else
4408  {
4409  void *raddr = readtup_alloc(state, tuplen);
4410 
4411  LogicalTapeReadExact(state->tapeset, tapenum,
4412  raddr, tuplen);
4413  stup->datum1 = PointerGetDatum(raddr);
4414  stup->isnull1 = false;
4415  stup->tuple = raddr;
4416  }
4417 
4418  if (state->randomAccess) /* need trailing length word? */
4419  LogicalTapeReadExact(state->tapeset, tapenum,
4420  &tuplen, sizeof(tuplen));
4421 }
#define PointerGetDatum(X)
Definition: postgres.h:562
bool randomAccess
Definition: tuplesort.c:274
Datum datum1
Definition: tuplesort.c:201
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:573
bool isnull1
Definition: tuplesort.c:202
void * tuple
Definition: tuplesort.c:200
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
uintptr_t Datum
Definition: postgres.h:372
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3555
static void readtup_heap ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

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

3752 {
3753  unsigned int tupbodylen = len - sizeof(int);
3754  unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
3755  MinimalTuple tuple = (MinimalTuple) readtup_alloc(state, tuplen);
3756  char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
3757  HeapTupleData htup;
3758 
3759  /* read in the tuple proper */
3760  tuple->t_len = tuplen;
3761  LogicalTapeReadExact(state->tapeset, tapenum,
3762  tupbody, tupbodylen);
3763  if (state->randomAccess) /* need trailing length word? */
3764  LogicalTapeReadExact(state->tapeset, tapenum,
3765  &tuplen, sizeof(tuplen));
3766  stup->tuple = (void *) tuple;
3767  /* set up first-column key value */
3768  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
3769  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
3770  stup->datum1 = heap_getattr(&htup,
3771  state->sortKeys[0].ssup_attno,
3772  state->tupDesc,
3773  &stup->isnull1);
3774 }
#define MINIMAL_TUPLE_DATA_OFFSET
Definition: htup_details.h:624
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
SortSupport sortKeys
Definition: tuplesort.c:441
bool randomAccess
Definition: tuplesort.c:274
Datum datum1
Definition: tuplesort.c:201
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:573
bool isnull1
Definition: tuplesort.c:202
HeapTupleHeader t_data
Definition: htup.h:67
void * tuple
Definition: tuplesort.c:200
uint32 t_len
Definition: htup.h:64
MinimalTupleData * MinimalTuple
Definition: htup.h:27
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:769
AttrNumber ssup_attno
Definition: sortsupport.h:81
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:620
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3555
TupleDesc tupDesc
Definition: tuplesort.c:440
static void readtup_index ( Tuplesortstate state,
SortTuple stup,
int  tapenum,
unsigned int  len 
)
static

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

4296 {
4297  unsigned int tuplen = len - sizeof(unsigned int);
4298  IndexTuple tuple = (IndexTuple) readtup_alloc(state, tuplen);
4299 
4300  LogicalTapeReadExact(state->tapeset, tapenum,
4301  tuple, tuplen);
4302  if (state->randomAccess) /* need trailing length word? */
4303  LogicalTapeReadExact(state->tapeset, tapenum,
4304  &tuplen, sizeof(tuplen));
4305  stup->tuple = (void *) tuple;
4306  /* set up first-column key value */
4307  stup->datum1 = index_getattr(tuple,
4308  1,
4309  RelationGetDescr(state->indexRel),
4310  &stup->isnull1);
4311 }
#define RelationGetDescr(relation)
Definition: rel.h:425
bool randomAccess
Definition: tuplesort.c:274
Datum datum1
Definition: tuplesort.c:201
#define LogicalTapeReadExact(tapeset, tapenum, ptr, len)
Definition: tuplesort.c:573
bool isnull1
Definition: tuplesort.c:202
void * tuple
Definition: tuplesort.c:200
IndexTupleData * IndexTuple
Definition: itup.h:53
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
Relation indexRel
Definition: tuplesort.c:470
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
static void * readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:3555
static void reversedirection ( Tuplesortstate state)
static

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

3511 {
3512  SortSupport sortKey = state->sortKeys;
3513  int nkey;
3514 
3515  for (nkey = 0; nkey < state->nKeys; nkey++, sortKey++)
3516  {
3517  sortKey->ssup_reverse = !sortKey->ssup_reverse;
3518  sortKey->ssup_nulls_first = !sortKey->ssup_nulls_first;
3519  }
3520 }
bool ssup_nulls_first
Definition: sortsupport.h:75
SortSupport sortKeys
Definition: tuplesort.c:441
static void selectnewtape ( Tuplesortstate state)
static

Definition at line 2465 of file tuplesort.c.

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

Referenced by dumpbatch(), and dumptuples().

2466 {
2467  int j;
2468  int a;
2469 
2470  /* Step D3: advance j (destTape) */
2471  if (state->tp_dummy[state->destTape] < state->tp_dummy[state->destTape + 1])
2472  {
2473  state->destTape++;
2474  return;
2475  }
2476  if (state->tp_dummy[state->destTape] != 0)
2477  {
2478  state->destTape = 0;
2479  return;
2480  }
2481 
2482  /* Step D4: increase level */
2483  state->Level++;
2484  a = state->tp_fib[0];
2485  for (j = 0; j < state->tapeRange; j++)
2486  {
2487  state->tp_dummy[j] = a + state->tp_fib[j + 1] - state->tp_fib[j];
2488  state->tp_fib[j] = a + state->tp_fib[j + 1];
2489  }
2490  state->destTape = 0;
2491 }
int * tp_dummy
Definition: tuplesort.c:417
static void sort_bounded_heap ( Tuplesortstate state)
static

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

3344 {
3345  int tupcount = state->memtupcount;
3346 
3347  Assert(state->status == TSS_BOUNDED);
3348  Assert(state->bounded);
3349  Assert(tupcount == state->bound);
3350 
3351  /*
3352  * We can unheapify in place because each delete-top call will remove the
3353  * largest entry, which we can promptly store in the newly freed slot at
3354  * the end. Once we're down to a single-entry heap, we're done.
3355  */
3356  while (state->memtupcount > 1)
3357  {
3358  SortTuple stup = state->memtuples[0];
3359 
3360  /* this sifts-up the next-largest entry and decreases memtupcount */
3361  tuplesort_heap_delete_top(state, false);
3362  state->memtuples[state->memtupcount] = stup;
3363  }
3364  state->memtupcount = tupcount;
3365 
3366  /*
3367  * Reverse sort direction back to the original state. This is not
3368  * actually necessary but seems like a good idea for tidiness.
3369  */
3370  reversedirection(state);
3371 
3372  state->status = TSS_SORTEDINMEM;
3373  state->boundUsed = true;
3374 }
static void reversedirection(Tuplesortstate *state)
Definition: tuplesort.c:3510
TupSortStatus status
Definition: tuplesort.c:272
static void tuplesort_heap_delete_top(Tuplesortstate *state, bool checkIndex)
Definition: tuplesort.c:3448
#define Assert(condition)
Definition: c.h:675
SortTuple * memtuples
Definition: tuplesort.c:333
Tuplesortstate* tuplesort_begin_cluster ( TupleDesc  tupDesc,
Relation  indexRel,
int  workMem,
bool  randomAccess 
)

Definition at line 825 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, NULL, 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().

828 {
829  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
830  ScanKey indexScanKey;
831  MemoryContext oldcontext;
832  int i;
833 
834  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
835 
836  oldcontext = MemoryContextSwitchTo(state->sortcontext);
837 
838 #ifdef TRACE_SORT
839  if (trace_sort)
840  elog(LOG,
841  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
843  workMem, randomAccess ? 't' : 'f');
844 #endif
845 
846  state->nKeys = RelationGetNumberOfAttributes(indexRel);
847 
848  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
849  false, /* no unique check */
850  state->nKeys,
851  workMem,
852  randomAccess);
853 
855  state->copytup = copytup_cluster;
856  state->writetup = writetup_cluster;
857  state->readtup = readtup_cluster;
858  state->abbrevNext = 10;
859 
860  state->indexInfo = BuildIndexInfo(indexRel);
861 
862  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
863 
864  indexScanKey = _bt_mkscankey_nodata(indexRel);
865 
866  if (state->indexInfo->ii_Expressions != NULL)
867  {
868  TupleTableSlot *slot;
869  ExprContext *econtext;
870 
871  /*
872  * We will need to use FormIndexDatum to evaluate the index
873  * expressions. To do that, we need an EState, as well as a
874  * TupleTableSlot to put the table tuples into. The econtext's
875  * scantuple has to point to that slot, too.
876  */
877  state->estate = CreateExecutorState();
878  slot = MakeSingleTupleTableSlot(tupDesc);
879  econtext = GetPerTupleExprContext(state->estate);
880  econtext->ecxt_scantuple = slot;
881  }
882 
883  /* Prepare SortSupport data for each column */
884  state->sortKeys = (SortSupport) palloc0(state->nKeys *
885  sizeof(SortSupportData));
886 
887  for (i = 0; i < state->nKeys; i++)
888  {
889  SortSupport sortKey = state->sortKeys + i;
890  ScanKey scanKey = indexScanKey + i;
891  int16 strategy;
892 
893  sortKey->ssup_cxt = CurrentMemoryContext;
894  sortKey->ssup_collation = scanKey->sk_collation;
895  sortKey->ssup_nulls_first =
896  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
897  sortKey->ssup_attno = scanKey->sk_attno;
898  /* Convey if abbreviation optimization is applicable in principle */
899  sortKey->abbreviate = (i == 0);
900 
901  AssertState(sortKey->ssup_attno != 0);
902 
903  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
905 
906  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
907  }
908 
909  _bt_freeskey(indexScanKey);
910 
911  MemoryContextSwitchTo(oldcontext);
912 
913  return state;
914 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:255
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:3966
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:678
int64 abbrevNext
Definition: tuplesort.c:455
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:419
EState * estate
Definition: tuplesort.c:463
SortSupport sortKeys
Definition: tuplesort.c:441
void _bt_freeskey(ScanKey skey)
Definition: nbtutils.c:155
#define BTREE_AM_OID
Definition: pg_am.h:70
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:297
#define CLUSTER_SORT
Definition: tuplesort.c:150
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:3782
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:1639
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:315
#define LOG
Definition: elog.h:26
Form_pg_class rd_rel
Definition: rel.h:113
static void copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3893
bool trace_sort
Definition: tuplesort.c:154
#define GetPerTupleExprContext(estate)
Definition: executor.h:338
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3990
MemoryContext sortcontext
Definition: tuplesort.c:284
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:323
IndexInfo * indexInfo
Definition: tuplesort.c:462
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:73
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:428
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:305
void * palloc0(Size size)
Definition: mcxt.c:878
AttrNumber ssup_attno
Definition: sortsupport.h:81
int sk_flags
Definition: skey.h:66
#define NULL
Definition: c.h:229
List * ii_Expressions
Definition: execnodes.h:69
#define Assert(condition)
Definition: c.h:675
#define SK_BT_DESC
Definition: nbtree.h:427
Definition: regguts.h:298
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:130
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:667
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67
TupleDesc tupDesc
Definition: tuplesort.c:440
static Tuplesortstate * tuplesort_begin_common ( int  workMem,
bool  randomAccess 
)
static

Definition at line 667 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, NULL, palloc(), palloc0(), pg_rusage_init(), Tuplesortstate::randomAccess, Tuplesortstate::result_tape, Tuplesortstate::ru_start, RUN_FIRST, 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().

668 {
670  MemoryContext sortcontext;
671  MemoryContext tuplecontext;
672  MemoryContext oldcontext;
673 
674  /*
675  * Create a working memory context for this sort operation. All data
676  * needed by the sort will live inside this context.
677  */
679  "TupleSort main",
681 
682  /*
683  * Caller tuple (e.g. IndexTuple) memory context.
684  *
685  * A dedicated child context used exclusively for caller passed tuples
686  * eases memory management. Resetting at key points reduces
687  * fragmentation. Note that the memtuples array of SortTuples is allocated
688  * in the parent context, not this context, because there is no need to
689  * free memtuples early.
690  */
691  tuplecontext = AllocSetContextCreate(sortcontext,
692  "Caller tuples",
694 
695  /*
696  * Make the Tuplesortstate within the per-sort context. This way, we
697  * don't need a separate pfree() operation for it at shutdown.
698  */
699  oldcontext = MemoryContextSwitchTo(sortcontext);
700 
701  state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));
702 
703 #ifdef TRACE_SORT
704  if (trace_sort)
705  pg_rusage_init(&state->ru_start);
706 #endif
707 
708  state->status = TSS_INITIAL;
709  state->randomAccess = randomAccess;
710  state->bounded = false;
711  state->tuples = true;
712  state->boundUsed = false;
713  state->allowedMem = workMem * (int64) 1024;
714  state->availMem = state->allowedMem;
715  state->sortcontext = sortcontext;
716  state->tuplecontext = tuplecontext;
717  state->tapeset = NULL;
718 
719  state->memtupcount = 0;
720 
721  /*
722  * Initial size of array must be more than ALLOCSET_SEPARATE_THRESHOLD;
723  * see comments in grow_memtuples().
724  */
725  state->memtupsize = Max(1024,
726  ALLOCSET_SEPARATE_THRESHOLD / sizeof(SortTuple) + 1);
727 
728  state->growmemtuples = true;
729  state->slabAllocatorUsed = false;
730  state->memtuples = (SortTuple *) palloc(state->memtupsize * sizeof(SortTuple));
731 
732  USEMEM(state, GetMemoryChunkSpace(state->memtuples));
733 
734  /* workMem must be large enough for the minimal memtuples array */
735  if (LACKMEM(state))
736  elog(ERROR, "insufficient memory allowed for sort");
737 
738  state->currentRun = RUN_FIRST;
739 
740  /*
741  * maxTapes, tapeRange, and Algorithm D variables will be initialized by
742  * inittapes(), if needed
743  */
744 
745  state->result_tape = -1; /* flag that result tape has not been formed */
746 
747  MemoryContextSwitchTo(oldcontext);
748 
749  return state;
750 }
int64 availMem
Definition: tuplesort.c:280
TupSortStatus status
Definition: tuplesort.c:272
PGRUsage ru_start
Definition: tuplesort.c:490
#define RUN_FIRST
Definition: tuplesort.c:260
bool randomAccess
Definition: tuplesort.c:274
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
bool growmemtuples
Definition: tuplesort.c:336
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
bool trace_sort
Definition: tuplesort.c:154
void pg_rusage_init(PGRUsage *ru0)
Definition: pg_rusage.c:27
#define ERROR
Definition: elog.h:43
MemoryContext sortcontext
Definition: tuplesort.c:284
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:165
#define ALLOCSET_SEPARATE_THRESHOLD
Definition: memutils.h:192
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
int64 allowedMem
Definition: tuplesort.c:281
MemoryContext AllocSetContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: aset.c:322
void * palloc0(Size size)
Definition: mcxt.c:878
#define Max(x, y)
Definition: c.h:800
#define NULL
Definition: c.h:229
Definition: regguts.h:298
bool slabAllocatorUsed
Definition: tuplesort.c:365
MemoryContext tuplecontext
Definition: tuplesort.c:285
void * palloc(Size size)
Definition: mcxt.c:849
#define USEMEM(state, amt)
Definition: tuplesort.c:522
#define elog
Definition: elog.h:219
#define LACKMEM(state)
Definition: tuplesort.c:521
SortTuple * memtuples
Definition: tuplesort.c:333
Tuplesortstate* tuplesort_begin_datum ( Oid  datumType,
Oid  sortOperator,
Oid  sortCollation,
bool  nullsFirstFlag,
int  workMem,
bool  randomAccess 
)

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

1031 {
1032  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
1033  MemoryContext oldcontext;
1034  int16 typlen;
1035  bool typbyval;
1036 
1037  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1038 
1039 #ifdef TRACE_SORT
1040  if (trace_sort)
1041  elog(LOG,
1042  "begin datum sort: workMem = %d, randomAccess = %c",
1043  workMem, randomAccess ? 't' : 'f');
1044 #endif
1045 
1046  state->nKeys = 1; /* always a one-column sort */
1047 
1048  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
1049  false, /* no unique check */
1050  1,
1051  workMem,
1052  randomAccess);
1053 
1054  state->comparetup = comparetup_datum;
1055  state->copytup = copytup_datum;
1056  state->writetup = writetup_datum;
1057  state->readtup = readtup_datum;
1058  state->abbrevNext = 10;
1059 
1060  state->datumType = datumType;
1061 
1062  /* lookup necessary attributes of the datum type */
1063  get_typlenbyval(datumType, &typlen, &typbyval);
1064  state->datumTypeLen = typlen;
1065  state->tuples = !typbyval;
1066 
1067  /* Prepare SortSupport data */
1068  state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
1069 
1071  state->sortKeys->ssup_collation = sortCollation;
1072  state->sortKeys->ssup_nulls_first = nullsFirstFlag;
1073 
1074  /*
1075  * Abbreviation is possible here only for by-reference types. In theory,
1076  * a pass-by-value datatype could have an abbreviated form that is cheaper
1077  * to compare. In a tuple sort, we could support that, because we can
1078  * always extract the original datum from the tuple is needed. Here, we
1079  * can't, because a datum sort only stores a single copy of the datum; the
1080  * "tuple" field of each sortTuple is NULL.
1081  */
1082  state->sortKeys->abbreviate = !typbyval;
1083 
1084  PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
1085 
1086  /*
1087  * The "onlyKey" optimization cannot be used with abbreviated keys, since
1088  * tie-breaker comparisons may be required. Typically, the optimization
1089  * is only of value to pass-by-value types anyway, whereas abbreviated
1090  * keys are typically only of value to pass-by-reference types.
1091  */
1092  if (!state->sortKeys->abbrev_converter)
1093  state->onlyKey = state->sortKeys;
1094 
1095  MemoryContextSwitchTo(oldcontext);
1096 
1097  return state;
1098 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:255
bool ssup_nulls_first
Definition: sortsupport.h:75
int64 abbrevNext
Definition: tuplesort.c:455
SortSupport sortKeys
Definition: tuplesort.c:441
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:133
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:297
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:315
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
#define DATUM_SORT
Definition: tuplesort.c:149
MemoryContext sortcontext
Definition: tuplesort.c:284
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4318
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4339
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4387
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:323
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
static void writetup_datum(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4346
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:305
void * palloc0(Size size)
Definition: mcxt.c:878
Definition: regguts.h:298
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:1969
SortSupport onlyKey
Definition: tuplesort.c:447
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:667
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
Tuplesortstate* tuplesort_begin_heap ( TupleDesc  tupDesc,
int  nkeys,
AttrNumber attNums,
Oid sortOperators,
Oid sortCollations,
bool nullsFirstFlags,
int  workMem,
bool  randomAccess 
)

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

758 {
759  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
760  MemoryContext oldcontext;
761  int i;
762 
763  oldcontext = MemoryContextSwitchTo(state->sortcontext);
764 
765  AssertArg(nkeys > 0);
766 
767 #ifdef TRACE_SORT
768  if (trace_sort)
769  elog(LOG,
770  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
771  nkeys, workMem, randomAccess ? 't' : 'f');
772 #endif
773 
774  state->nKeys = nkeys;
775 
776  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
777  false, /* no unique check */
778  nkeys,
779  workMem,
780  randomAccess);
781 
782  state->comparetup = comparetup_heap;
783  state->copytup = copytup_heap;
784  state->writetup = writetup_heap;
785  state->readtup = readtup_heap;
786 
787  state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
788  state->abbrevNext = 10;
789 
790  /* Prepare SortSupport data for each column */
791  state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
792 
793  for (i = 0; i < nkeys; i++)
794  {
795  SortSupport sortKey = state->sortKeys + i;
796 
797  AssertArg(attNums[i] != 0);
798  AssertArg(sortOperators[i] != 0);
799 
800  sortKey->ssup_cxt = CurrentMemoryContext;
801  sortKey->ssup_collation = sortCollations[i];
802  sortKey->ssup_nulls_first = nullsFirstFlags[i];
803  sortKey->ssup_attno = attNums[i];
804  /* Convey if abbreviation optimization is applicable in principle */
805  sortKey->abbreviate = (i == 0);
806 
807  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
808  }
809 
810  /*
811  * The "onlyKey" optimization cannot be used with abbreviated keys, since
812  * tie-breaker comparisons may be required. Typically, the optimization
813  * is only of value to pass-by-value types anyway, whereas abbreviated
814  * keys are typically only of value to pass-by-reference types.
815  */
816  if (nkeys == 1 && !state->sortKeys->abbrev_converter)
817  state->onlyKey = state->sortKeys;
818 
819  MemoryContextSwitchTo(oldcontext);
820 
821  return state;
822 }
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:3583
int64 abbrevNext
Definition: tuplesort.c:455
SortSupport sortKeys
Definition: tuplesort.c:441
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:133
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:297
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:315
#define LOG
Definition: elog.h:26
#define HEAP_SORT
Definition: tuplesort.c:147
bool trace_sort
Definition: tuplesort.c:154
MemoryContext sortcontext
Definition: tuplesort.c:284
static void writetup_heap(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:3723
MemoryContext ssup_cxt
Definition: sortsupport.h:66
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:323
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define AssertArg(condition)
Definition: c.h:677
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:3645
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:305
void * palloc0(Size size)
Definition: mcxt.c:878
AttrNumber ssup_attno
Definition: sortsupport.h:81
Definition: regguts.h:298
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:3750
int i
SortSupport onlyKey
Definition: tuplesort.c:447
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:667
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
TupleDesc tupDesc
Definition: tuplesort.c:440
Tuplesortstate* tuplesort_begin_index_btree ( Relation  heapRel,
Relation  indexRel,
bool  enforceUnique,
int  workMem,
bool  randomAccess 
)

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

921 {
922  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
923  ScanKey indexScanKey;
924  MemoryContext oldcontext;
925  int i;
926 
927  oldcontext = MemoryContextSwitchTo(state->sortcontext);
928 
929 #ifdef TRACE_SORT
930  if (trace_sort)
931  elog(LOG,
932  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
933  enforceUnique ? 't' : 'f',
934  workMem, randomAccess ? 't' : 'f');
935 #endif
936 
937  state->nKeys = RelationGetNumberOfAttributes(indexRel);
938 
939  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
940  enforceUnique,
941  state->nKeys,
942  workMem,
943  randomAccess);
944 
946  state->copytup = copytup_index;
947  state->writetup = writetup_index;
948  state->readtup = readtup_index;
949  state->abbrevNext = 10;
950 
951  state->heapRel = heapRel;
952  state->indexRel = indexRel;
953  state->enforceUnique = enforceUnique;
954 
955  indexScanKey = _bt_mkscankey_nodata(indexRel);
956  state->nKeys = RelationGetNumberOfAttributes(indexRel);
957 
958  /* Prepare SortSupport data for each column */
959  state->sortKeys = (SortSupport) palloc0(state->nKeys *
960  sizeof(SortSupportData));
961 
962  for (i = 0; i < state->nKeys; i++)
963  {
964  SortSupport sortKey = state->sortKeys + i;
965  ScanKey scanKey = indexScanKey + i;
966  int16 strategy;
967 
968  sortKey->ssup_cxt = CurrentMemoryContext;
969  sortKey->ssup_collation = scanKey->sk_collation;
970  sortKey->ssup_nulls_first =
971  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
972  sortKey->ssup_attno = scanKey->sk_attno;
973  /* Convey if abbreviation optimization is applicable in principle */
974  sortKey->abbreviate = (i == 0);
975 
976  AssertState(sortKey->ssup_attno != 0);
977 
978  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
980 
981  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
982  }
983 
984  _bt_freeskey(indexScanKey);
985 
986  MemoryContextSwitchTo(oldcontext);
987 
988  return state;
989 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
signed short int16
Definition: c.h:255
bool ssup_nulls_first
Definition: sortsupport.h:75
ScanKey _bt_mkscankey_nodata(Relation rel)
Definition: nbtutils.c:115
Relation heapRel
Definition: tuplesort.c:469
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define AssertState(condition)
Definition: c.h:678
int64 abbrevNext
Definition: tuplesort.c:455
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:419
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4206
SortSupport sortKeys
Definition: tuplesort.c:441
void _bt_freeskey(ScanKey skey)
Definition: nbtutils.c:155
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:297
#define INDEX_SORT
Definition: tuplesort.c:148
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:315
#define LOG
Definition: elog.h:26
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4028
bool trace_sort
Definition: tuplesort.c:154
MemoryContext sortcontext
Definition: tuplesort.c:284
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4272
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4294
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:323
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(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:305
void * palloc0(Size size)
Definition: mcxt.c:878
Relation indexRel
Definition: tuplesort.c:470
AttrNumber ssup_attno
Definition: sortsupport.h:81
int sk_flags
Definition: skey.h:66
#define SK_BT_DESC
Definition: nbtree.h:427
Definition: regguts.h:298
bool enforceUnique
Definition: tuplesort.c:473
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:667
#define BTLessStrategyNumber
Definition: stratnum.h:29
AttrNumber sk_attno
Definition: skey.h:67
Tuplesortstate* tuplesort_begin_index_hash ( Relation  heapRel,
Relation  indexRel,
uint32  hash_mask,
int  workMem,
bool  randomAccess 
)

Definition at line 992 of file tuplesort.c.

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

Referenced by _h_spoolinit().

996 {
997  Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
998  MemoryContext oldcontext;
999 
1000  oldcontext = MemoryContextSwitchTo(state->sortcontext);
1001 
1002 #ifdef TRACE_SORT
1003  if (trace_sort)
1004  elog(LOG,
1005  "begin index sort: hash_mask = 0x%x, workMem = %d, randomAccess = %c",
1006  hash_mask,
1007  workMem, randomAccess ? 't' : 'f');
1008 #endif
1009 
1010  state->nKeys = 1; /* Only one sort column, the hash code */
1011 
1013  state->copytup = copytup_index;
1014  state->writetup = writetup_index;
1015  state->readtup = readtup_index;
1016 
1017  state->heapRel = heapRel;
1018  state->indexRel = indexRel;
1019 
1020  state->hash_mask = hash_mask;
1021 
1022  MemoryContextSwitchTo(oldcontext);
1023 
1024  return state;
1025 }
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Definition: tuplesort.c:4157
Relation heapRel
Definition: tuplesort.c:469
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:4206
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
SortTupleComparator comparetup
Definition: tuplesort.c:297
void(* writetup)(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:315
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
MemoryContext sortcontext
Definition: tuplesort.c:284
static void writetup_index(Tuplesortstate *state, int tapenum, SortTuple *stup)
Definition: tuplesort.c:4272
void hash_mask(char *pagedata, BlockNumber blkno)
Definition: hash_xlog.c:1228
static void readtup_index(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:4294
void(* readtup)(Tuplesortstate *state, SortTuple *stup, int tapenum, unsigned int len)
Definition: tuplesort.c:323
void(* copytup)(Tuplesortstate *state, SortTuple *stup, void *tup)
Definition: tuplesort.c:305
Relation indexRel
Definition: tuplesort.c:470
Definition: regguts.h:298
uint32 hash_mask
Definition: tuplesort.c:476
#define elog
Definition: elog.h:219
static Tuplesortstate * tuplesort_begin_common(int workMem, bool randomAccess)
Definition: tuplesort.c:667
void tuplesort_end ( Tuplesortstate state)

Definition at line 1157 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, ExprContext::ecxt_scantuple, elog, Tuplesortstate::estate, ExecDropSingleTupleTableSlot(), FreeExecutorState(), GetPerTupleExprContext, LOG, LogicalTapeSetBlocks(), LogicalTapeSetClose(), MemoryContextDelete(), MemoryContextSwitchTo(), NULL, 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(), hypothetical_dense_rank_final(), hypothetical_rank_common(), initialize_aggregate(), initialize_phase(), ordered_set_shutdown(), process_ordered_aggregate_multi(), process_ordered_aggregate_single(), and validate_index().

1158 {
1159  /* context swap probably not needed, but let's be safe */
1160  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
1161 
1162 #ifdef TRACE_SORT
1163  long spaceUsed;
1164 
1165  if (state->tapeset)
1166  spaceUsed = LogicalTapeSetBlocks(state->tapeset);
1167  else
1168  spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
1169 #endif
1170 
1171  /*
1172  * Delete temporary "tape" files, if any.
1173  *
1174  * Note: want to include this in reported total cost of sort, hence need
1175  * for two #ifdef TRACE_SORT sections.
1176  */
1177  if (state->tapeset)
1178  LogicalTapeSetClose(state->tapeset);
1179 
1180 #ifdef TRACE_SORT
1181  if (trace_sort)
1182  {
1183  if (state->tapeset)
1184  elog(LOG, "external sort ended, %ld disk blocks used: %s",
1185  spaceUsed, pg_rusage_show(&state->ru_start));
1186  else
1187  elog(LOG, "internal sort ended, %ld KB used: %s",
1188  spaceUsed, pg_rusage_show(&state->ru_start));
1189  }
1190 
1191  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
1192 #else
1193 
1194  /*
1195  * If you disabled TRACE_SORT, you can still probe sort__done, but you
1196  * ain't getting space-used stats.
1197  */
1198  TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, 0L);
1199 #endif
1200 
1201  /* Free any execution state created for CLUSTER case */
1202  if (state->estate != NULL)
1203  {
1204  ExprContext *econtext = GetPerTupleExprContext(state->estate);
1205 
1207  FreeExecutorState(state->estate);
1208  }
1209 
1210  MemoryContextSwitchTo(oldcontext);
1211 
1212  /*
1213  * Free the per-sort memory context, thereby releasing all working memory,
1214  * including the Tuplesortstate struct itself.
1215  */
1217 }
int64 availMem
Definition: tuplesort.c:280
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:200
PGRUsage ru_start
Definition: tuplesort.c:490
EState * estate
Definition: tuplesort.c:463
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define LOG
Definition: elog.h:26
bool trace_sort
Definition: tuplesort.c:154
void FreeExecutorState(EState *estate)
Definition: execUtils.c:169
#define GetPerTupleExprContext(estate)
Definition: executor.h:338
MemoryContext sortcontext
Definition: tuplesort.c:284
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:286
int64 allowedMem
Definition: tuplesort.c:281
#define NULL
Definition: c.h:229
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:130
void LogicalTapeSetClose(LogicalTapeSet *lts)
Definition: logtape.c:427
#define elog
Definition: elog.h:219
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:889
void tuplesort_get_stats ( Tuplesortstate state,
const char **  sortMethod,
const char **  spaceType,
long *  spaceUsed 
)

Definition at line 3217 of file tuplesort.c.

References Tuplesortstate::allowedMem, Tuplesortstate::availMem, Tuplesortstate::boundUsed, LogicalTapeSetBlocks(), Tuplesortstate::status, Tuplesortstate::tapeset, TSS_FINALMERGE, TSS_SORTEDINMEM, and TSS_SORTEDONTAPE.

Referenced by show_sort_info().

3221 {
3222  /*
3223  * Note: it might seem we should provide both memory and disk usage for a
3224  * disk-based sort. However, the current code doesn't track memory space
3225  * accurately once we have begun to return tuples to the caller (since we
3226  * don't account for pfree's the caller is expected to do), so we cannot
3227  * rely on availMem in a disk sort. This does not seem worth the overhead
3228  * to fix. Is it worth creating an API for the memory context code to
3229  * tell us how much is actually used in sortcontext?
3230  */
3231  if (state->tapeset)
3232  {
3233  *spaceType = "Disk";
3234  *spaceUsed = LogicalTapeSetBlocks(state->tapeset) * (BLCKSZ / 1024);
3235  }
3236  else
3237  {
3238  *spaceType = "Memory";
3239  *spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
3240  }
3241 
3242  switch (state->status)
3243  {
3244  case TSS_SORTEDINMEM:
3245  if (state->boundUsed)
3246  *sortMethod = "top-N heapsort";
3247  else
3248  *sortMethod = "quicksort";
3249  break;
3250  case TSS_SORTEDONTAPE:
3251  *sortMethod = "external sort";
3252  break;
3253  case TSS_FINALMERGE:
3254  *sortMethod = "external merge";
3255  break;
3256  default:
3257  *sortMethod = "still in progress";
3258  break;
3259  }
3260 }
int64 availMem
Definition: tuplesort.c:280
TupSortStatus status
Definition: tuplesort.c:272
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
int64 allowedMem
Definition: tuplesort.c:281
long LogicalTapeSetBlocks(LogicalTapeSet *lts)
Definition: logtape.c:889
bool tuplesort_getdatum ( Tuplesortstate state,
bool  forward,
Datum val,
bool isNull,
Datum abbrev 
)

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

2185 {
2186  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2187  SortTuple stup;
2188 
2189  if (!tuplesort_gettuple_common(state, forward, &stup))
2190  {
2191  MemoryContextSwitchTo(oldcontext);
2192  return false;
2193  }
2194 
2195  /* Record abbreviated key for caller */
2196  if (state->sortKeys->abbrev_converter && abbrev)
2197  *abbrev = stup.datum1;
2198 
2199  if (stup.isnull1 || !state->tuples)
2200  {
2201  *val = stup.datum1;
2202  *isNull = stup.isnull1;
2203  }
2204  else
2205  {
2206  /* use stup.tuple because stup.datum1 may be an abbreviation */
2207  *val = datumCopy(PointerGetDatum(stup.tuple), false, state->datumTypeLen);
2208  *isNull = false;
2209  }
2210 
2211  MemoryContextSwitchTo(oldcontext);
2212 
2213  return true;
2214 }
#define PointerGetDatum(X)
Definition: postgres.h:562
SortSupport sortKeys
Definition: tuplesort.c:441
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:201
bool isnull1
Definition: tuplesort.c:202
void * tuple
Definition: tuplesort.c:200
MemoryContext sortcontext
Definition: tuplesort.c:284
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1848
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:128
long val
Definition: informix.c:689
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
HeapTuple tuplesort_getheaptuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2134 of file tuplesort.c.

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

Referenced by copy_heap_data().

2135 {
2136  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2137  SortTuple stup;
2138 
2139  if (!tuplesort_gettuple_common(state, forward, &stup))
2140  stup.tuple = NULL;
2141 
2142  MemoryContextSwitchTo(oldcontext);
2143 
2144  return stup.tuple;
2145 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:200
MemoryContext sortcontext
Definition: tuplesort.c:284
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1848
#define NULL
Definition: c.h:229
IndexTuple tuplesort_getindextuple ( Tuplesortstate state,
bool  forward 
)

Definition at line 2154 of file tuplesort.c.

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

Referenced by _bt_load(), and _h_indexbuild().

2155 {
2156  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2157  SortTuple stup;
2158 
2159  if (!tuplesort_gettuple_common(state, forward, &stup))
2160  stup.tuple = NULL;
2161 
2162  MemoryContextSwitchTo(oldcontext);
2163 
2164  return (IndexTuple) stup.tuple;
2165 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * tuple
Definition: tuplesort.c:200
MemoryContext sortcontext
Definition: tuplesort.c:284
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1848
#define NULL
Definition: c.h:229
static bool tuplesort_gettuple_common ( Tuplesortstate state,
bool  forward,
SortTuple stup 
)
static

Definition at line 1848 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(), NULL, 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().

1850 {
1851  unsigned int tuplen;
1852  size_t nmoved;
1853 
1854  switch (state->status)
1855  {
1856  case TSS_SORTEDINMEM:
1857  Assert(forward || state->randomAccess);
1858  Assert(!state->slabAllocatorUsed);
1859  if (forward)
1860  {
1861  if (state->current < state->memtupcount)
1862  {
1863  *stup = state->memtuples[state->current++];
1864  return true;
1865  }
1866  state->eof_reached = true;
1867 
1868  /*
1869  * Complain if caller tries to retrieve more tuples than
1870  * originally asked for in a bounded sort. This is because
1871  * returning EOF here might be the wrong thing.
1872  */
1873  if (state->bounded && state->current >= state->bound)
1874  elog(ERROR, "retrieved too many tuples in a bounded sort");
1875 
1876  return false;
1877  }
1878  else
1879  {
1880  if (state->current <= 0)
1881  return false;
1882 
1883  /*
1884  * if all tuples are fetched already then we return last
1885  * tuple, else - tuple before last returned.
1886  */
1887  if (state->eof_reached)
1888  state->eof_reached = false;
1889  else
1890  {
1891  state->current--; /* last returned tuple */
1892  if (state->current <= 0)
1893  return false;
1894  }
1895  *stup = state->memtuples[state->current - 1];
1896  return true;
1897  }
1898  break;
1899 
1900  case TSS_SORTEDONTAPE:
1901  Assert(forward || state->randomAccess);
1902  Assert(state->slabAllocatorUsed);
1903 
1904  /*
1905  * The slot that held the tuple that we returned in previous
1906  * gettuple call can now be reused.
1907  */
1908  if (state->lastReturnedTuple)
1909  {
1910  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
1911  state->lastReturnedTuple = NULL;
1912  }
1913 
1914  if (forward)
1915  {
1916  if (state->eof_reached)
1917  return false;
1918 
1919  if ((tuplen = getlen(state, state->result_tape, true)) != 0)
1920  {
1921  READTUP(state, stup, state->result_tape, tuplen);
1922 
1923  /*
1924  * Remember the tuple we return, so that we can recycle
1925  * its memory on next call. (This can be NULL, in the
1926  * !state->tuples case).
1927  */
1928  state->lastReturnedTuple = stup->tuple;
1929 
1930  return true;
1931  }
1932  else
1933  {
1934  state->eof_reached = true;
1935  return false;
1936  }
1937  }
1938 
1939  /*
1940  * Backward.
1941  *
1942  * if all tuples are fetched already then we return last tuple,
1943  * else - tuple before last returned.
1944  */
1945  if (state->eof_reached)
1946  {
1947  /*
1948  * Seek position is pointing just past the zero tuplen at the
1949  * end of file; back up to fetch last tuple's ending length
1950  * word. If seek fails we must have a completely empty file.
1951  */
1952  nmoved = LogicalTapeBackspace(state->tapeset,
1953  state->result_tape,
1954  2 * sizeof(unsigned int));
1955  if (nmoved == 0)
1956  return false;
1957  else if (nmoved != 2 * sizeof(unsigned int))
1958  elog(ERROR, "unexpected tape position");
1959  state->eof_reached = false;
1960  }
1961  else
1962  {
1963  /*
1964  * Back up and fetch previously-returned tuple's ending length
1965  * word. If seek fails, assume we are at start of file.
1966  */
1967  nmoved = LogicalTapeBackspace(state->tapeset,
1968  state->result_tape,
1969  sizeof(unsigned int));
1970  if (nmoved == 0)
1971  return false;
1972  else if (nmoved != sizeof(unsigned int))
1973  elog(ERROR, "unexpected tape position");
1974  tuplen = getlen(state, state->result_tape, false);
1975 
1976  /*
1977  * Back up to get ending length word of tuple before it.
1978  */
1979  nmoved = LogicalTapeBackspace(state->tapeset,
1980  state->result_tape,
1981  tuplen + 2 * sizeof(unsigned int));
1982  if (nmoved == tuplen + sizeof(unsigned int))
1983  {
1984  /*
1985  * We backed up over the previous tuple, but there was no
1986  * ending length word before it. That means that the prev
1987  * tuple is the first tuple in the file. It is now the
1988  * next to read in forward direction (not obviously right,
1989  * but that is what in-memory case does).
1990  */
1991  return false;
1992  }
1993  else if (nmoved != tuplen + 2 * sizeof(unsigned int))
1994  elog(ERROR, "bogus tuple length in backward scan");
1995  }
1996 
1997  tuplen = getlen(state, state->result_tape, false);
1998 
1999  /*
2000  * Now we have the length of the prior tuple, back up and read it.
2001  * Note: READTUP expects we are positioned after the initial
2002  * length word of the tuple, so back up to that point.
2003  */
2004  nmoved = LogicalTapeBackspace(state->tapeset,
2005  state->result_tape,
2006  tuplen);
2007  if (nmoved != tuplen)
2008  elog(ERROR, "bogus tuple length in backward scan");
2009  READTUP(state, stup, state->result_tape, tuplen);
2010 
2011  /*
2012  * Remember the tuple we return, so that we can recycle its memory
2013  * on next call. (This can be NULL, in the Datum case).
2014  */
2015  state->lastReturnedTuple = stup->tuple;
2016 
2017  return true;
2018 
2019  case TSS_FINALMERGE:
2020  Assert(forward);
2021  /* We are managing memory ourselves, with the slab allocator. */
2022  Assert(state->slabAllocatorUsed);
2023 
2024  /*
2025  * The slab slot holding the tuple that we returned in previous
2026  * gettuple call can now be reused.
2027  */
2028  if (state->lastReturnedTuple)
2029  {
2030  RELEASE_SLAB_SLOT(state, state->lastReturnedTuple);
2031  state->lastReturnedTuple = NULL;
2032  }
2033 
2034  /*
2035  * This code should match the inner loop of mergeonerun().
2036  */
2037  if (state->memtupcount > 0)
2038  {
2039  int srcTape = state->memtuples[0].tupindex;
2040  SortTuple newtup;
2041 
2042  *stup = state->memtuples[0];
2043 
2044  /*
2045  * Remember the tuple we return, so that we can recycle its
2046  * memory on next call. (This can be NULL, in the Datum case).
2047  */
2048  state->lastReturnedTuple = stup->tuple;
2049 
2050  /*
2051  * Pull next tuple from tape, and replace the returned tuple
2052  * at top of the heap with it.
2053  */
2054  if (!mergereadnext(state, srcTape, &newtup))
2055  {
2056  /*
2057  * If no more data, we've reached end of run on this tape.
2058  * Remove the top node from the heap.
2059  */
2060  tuplesort_heap_delete_top(state, false);
2061 
2062  /*
2063  * Rewind to free the read buffer. It'd go away at the
2064  * end of the sort anyway, but better to release the
2065  * memory early.
2066  */
2067  LogicalTapeRewindForWrite(state->tapeset, srcTape);
2068  return true;
2069  }
2070  newtup.tupindex = srcTape;
2071  tuplesort_heap_replace_top(state, &newtup, false);
2072  return true;
2073  }
2074  return false;
2075 
2076  default:
2077  elog(ERROR, "invalid tuplesort state");
2078  return false; /* keep compiler quiet */
2079  }
2080 }
TupSortStatus status
Definition: tuplesort.c:272
static void tuplesort_heap_delete_top(Tuplesortstate *state, bool checkIndex)
Definition: tuplesort.c:3448
bool randomAccess
Definition: tuplesort.c:274
void LogicalTapeRewindForWrite(LogicalTapeSet *lts, int tapenum)
Definition: logtape.c:629
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK)
Definition: tuplesort.c:3528
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3473
void * tuple
Definition: tuplesort.c:200
#define ERROR
Definition: elog.h:43
void * lastReturnedTuple
Definition: tuplesort.c:380
size_t LogicalTapeBackspace(LogicalTapeSet *lts, int tapenum, size_t size)
Definition: logtape.c:768
LogicalTapeSet * tapeset
Definition: tuplesort.c:286
#define READTUP(state, stup, tape, len)
Definition: tuplesort.c:520
#define RELEASE_SLAB_SLOT(state, tuple)
Definition: tuplesort.c:505
static bool mergereadnext(Tuplesortstate *state, int srcTape, SortTuple *stup)
Definition: tuplesort.c:2890
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
bool eof_reached
Definition: tuplesort.c:428
int tupindex
Definition: tuplesort.c:203
bool slabAllocatorUsed
Definition: tuplesort.c:365
#define elog
Definition: elog.h:219
SortTuple * memtuples
Definition: tuplesort.c:333
bool tuplesort_gettupleslot ( Tuplesortstate state,
bool  forward,
TupleTableSlot slot,
Datum abbrev 
)

Definition at line 2099 of file tuplesort.c.

References SortSupportData::abbrev_converter, SortTuple::datum1, ExecClearTuple(), ExecStoreMinimalTuple(), heap_copy_minimal_tuple(), MemoryContextSwitchTo(), NULL, 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().

2101 {
2102  MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
2103  SortTuple stup;
2104 
2105  if (!tuplesort_gettuple_common(state, forward, &stup))
2106  stup.tuple = NULL;
2107 
2108  MemoryContextSwitchTo(oldcontext);
2109 
2110  if (stup.tuple)
2111  {
2112  /* Record abbreviated key for caller */
2113  if (state->sortKeys->abbrev_converter && abbrev)
2114  *abbrev = stup.datum1;
2115 
2117  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, true);
2118  return true;
2119  }
2120  else
2121  {
2122  ExecClearTuple(slot);
2123  return false;
2124  }
2125 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:384
SortSupport sortKeys
Definition: tuplesort.c:441
TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: execTuples.c:439
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum datum1
Definition: tuplesort.c:201
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1481
void * tuple
Definition: tuplesort.c:200
MemoryContext sortcontext
Definition: tuplesort.c:284
static bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1848
#define NULL
Definition: c.h:229
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:173
static void tuplesort_heap_delete_top ( Tuplesortstate state,
bool  checkIndex 
)
static

Definition at line 3448 of file tuplesort.c.

References Assert, Tuplesortstate::currentRun, Tuplesortstate::memtupcount, Tuplesortstate::memtuples, RUN_FIRST, and tuplesort_heap_replace_top().

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

3449 {
3450  SortTuple *memtuples = state->memtuples;
3451  SortTuple *tuple;
3452 
3453  Assert(!checkIndex || state->currentRun == RUN_FIRST);
3454  if (--state->memtupcount <= 0)
3455  return;
3456 
3457  /*
3458  * Remove the last tuple in the heap, and re-insert it, by replacing the
3459  * current top node with it.
3460  */
3461  tuple = &memtuples[state->memtupcount];
3462  tuplesort_heap_replace_top(state, tuple, checkIndex);
3463 }
#define RUN_FIRST
Definition: tuplesort.c:260
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple, bool checkIndex)
Definition: tuplesort.c:3473
#define Assert(condition)
Definition: c.h:675
SortTuple * memtuples
Definition: tuplesort.c:333
static void tuplesort_heap_insert ( Tuplesortstate state,
SortTuple tuple,
bool  checkIndex 
)
static

Definition at line 3411 of file tuplesort.c.

References Assert, CHECK_FOR_INTERRUPTS, HEAPCOMPARE, i, Tuplesortstate::memtupcount, Tuplesortstate::memtuples, Tuplesortstate::memtupsize, RUN_FIRST, and SortTuple::tupindex.

Referenced by beginmerge(), inittapes(), make_bounded_heap(), and puttuple_common().

3413 {
3414  SortTuple *memtuples;
3415  int j;
3416 
3417  memtuples = state->memtuples;
3418  Assert(state->memtupcount < state->memtupsize);
3419  Assert(!checkIndex || tuple->tupindex == RUN_FIRST);
3420 
3422 
3423  /*
3424  * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
3425  * using 1-based array indexes, not 0-based.
3426  */
3427  j = state->memtupcount++;
3428  while (j > 0)
3429  {
3430  int i = (j - 1) >> 1;
3431 
3432  if (HEAPCOMPARE(tuple, &memtuples[i]) >= 0)
3433  break;
3434  memtuples[j] = memtuples[i];
3435  j = i;
3436  }
3437  memtuples[j] = *tuple;
3438 }
#define RUN_FIRST
Definition: tuplesort.c:260
#define HEAPCOMPARE(tup1, tup2)
Definition: tuplesort.c:3274
#define Assert(condition)
Definition: c.h:675
int tupindex
Definition: tuplesort.c:203
int i
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:97
SortTuple * memtuples
Definition: tuplesort.c:333
static void tuplesort_heap_replace_top ( Tuplesortstate state,
SortTuple tuple,
bool  checkIndex 
)
static

Definition at line 3473 of file tuplesort.c.

References Assert, CHECK_FOR_INTERRUPTS, Tuplesortstate::currentRun, HEAPCOMPARE, i, Tuplesortstate::memtupcount, Tuplesortstate::memtuples, and RUN_FIRST.

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

3475 {
3476  SortTuple *memtuples = state->memtuples;
3477  int i,
3478  n;
3479 
3480  Assert(!checkIndex || state->currentRun == RUN_FIRST);
3481  Assert(state->memtupcount >= 1);
3482 
3484 
3485  n = state->memtupcount;
3486  i = 0; /* i is where the "hole" is */
3487  for (;;)
3488  {
3489  int j = 2 * i + 1;
3490 
3491  if (j >= n)
3492  break;
3493  if (j + 1 < n &&
3494  HEAPCOMPARE(&memtuples[j], &memtuples[j + 1]) > 0)
3495  j++;
3496  if (HEAPCOMPARE(tuple, &memtuples[j]) <= 0)
3497  break;
3498  memtuples[i] = memtuples[j];
3499  i = j;
3500  }
3501  memtuples[i] = *