PostgreSQL Source Code  git master
tuplesortvariants.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * tuplesortvariants.c
4  * Implementation of tuple sorting variants.
5  *
6  * This module handles the sorting of heap tuples, index tuples, or single
7  * Datums. The implementation is based on the generalized tuple sorting
8  * facility given in tuplesort.c. Support other kinds of sortable objects
9  * could be easily added here, another module, or even an extension.
10  *
11  *
12  * Copyright (c) 2022-2023, PostgreSQL Global Development Group
13  *
14  * IDENTIFICATION
15  * src/backend/utils/sort/tuplesortvariants.c
16  *
17  *-------------------------------------------------------------------------
18  */
19 
20 #include "postgres.h"
21 
22 #include "access/hash.h"
23 #include "access/htup_details.h"
24 #include "access/nbtree.h"
25 #include "catalog/index.h"
26 #include "executor/executor.h"
27 #include "pg_trace.h"
28 #include "utils/datum.h"
29 #include "utils/lsyscache.h"
30 #include "utils/guc.h"
31 #include "utils/tuplesort.h"
32 
33 
34 /* sort-type codes for sort__start probes */
35 #define HEAP_SORT 0
36 #define INDEX_SORT 1
37 #define DATUM_SORT 2
38 #define CLUSTER_SORT 3
39 
40 static void removeabbrev_heap(Tuplesortstate *state, SortTuple *stups,
41  int count);
43  int count);
45  int count);
47  int count);
48 static int comparetup_heap(const SortTuple *a, const SortTuple *b,
50 static int comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b,
52 static void writetup_heap(Tuplesortstate *state, LogicalTape *tape,
53  SortTuple *stup);
54 static void readtup_heap(Tuplesortstate *state, SortTuple *stup,
55  LogicalTape *tape, unsigned int len);
56 static int comparetup_cluster(const SortTuple *a, const SortTuple *b,
58 static int comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b,
61  SortTuple *stup);
62 static void readtup_cluster(Tuplesortstate *state, SortTuple *stup,
63  LogicalTape *tape, unsigned int tuplen);
64 static int comparetup_index_btree(const SortTuple *a, const SortTuple *b,
66 static int comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
68 static int comparetup_index_hash(const SortTuple *a, const SortTuple *b,
70 static int comparetup_index_hash_tiebreak(const SortTuple *a, const SortTuple *b,
73  SortTuple *stup);
74 static void readtup_index(Tuplesortstate *state, SortTuple *stup,
75  LogicalTape *tape, unsigned int len);
76 static int comparetup_datum(const SortTuple *a, const SortTuple *b,
78 static int comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b,
81  SortTuple *stup);
82 static void readtup_datum(Tuplesortstate *state, SortTuple *stup,
83  LogicalTape *tape, unsigned int len);
85 
86 /*
87  * Data struture pointed by "TuplesortPublic.arg" for the CLUSTER case. Set by
88  * the tuplesort_begin_cluster.
89  */
90 typedef struct
91 {
93 
94  IndexInfo *indexInfo; /* info about index being used for reference */
95  EState *estate; /* for evaluating index expressions */
97 
98 /*
99  * Data struture pointed by "TuplesortPublic.arg" for the IndexTuple case.
100  * Set by tuplesort_begin_index_xxx and used only by the IndexTuple routines.
101  */
102 typedef struct
103 {
104  Relation heapRel; /* table the index is being built on */
105  Relation indexRel; /* index being built */
107 
108 /*
109  * Data struture pointed by "TuplesortPublic.arg" for the index_btree subcase.
110  */
111 typedef struct
112 {
114 
115  bool enforceUnique; /* complain if we find duplicate tuples */
116  bool uniqueNullsNotDistinct; /* unique constraint null treatment */
118 
119 /*
120  * Data struture pointed by "TuplesortPublic.arg" for the index_hash subcase.
121  */
122 typedef struct
123 {
125 
126  uint32 high_mask; /* masks for sortable part of hash code */
130 
131 /*
132  * Data struture pointed by "TuplesortPublic.arg" for the Datum case.
133  * Set by tuplesort_begin_datum and used only by the DatumTuple routines.
134  */
135 typedef struct
136 {
137  /* the datatype oid of Datum's to be sorted */
139  /* we need typelen in order to know how to copy the Datums. */
142 
145  int nkeys, AttrNumber *attNums,
146  Oid *sortOperators, Oid *sortCollations,
147  bool *nullsFirstFlags,
148  int workMem, SortCoordinate coordinate, int sortopt)
149 {
150  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
151  sortopt);
153  MemoryContext oldcontext;
154  int i;
155 
156  oldcontext = MemoryContextSwitchTo(base->maincontext);
157 
158  Assert(nkeys > 0);
159 
160 #ifdef TRACE_SORT
161  if (trace_sort)
162  elog(LOG,
163  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
164  nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
165 #endif
166 
167  base->nKeys = nkeys;
168 
169  TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
170  false, /* no unique check */
171  nkeys,
172  workMem,
173  sortopt & TUPLESORT_RANDOMACCESS,
174  PARALLEL_SORT(coordinate));
175 
177  base->comparetup = comparetup_heap;
179  base->writetup = writetup_heap;
180  base->readtup = readtup_heap;
181  base->haveDatum1 = true;
182  base->arg = tupDesc; /* assume we need not copy tupDesc */
183 
184  /* Prepare SortSupport data for each column */
185  base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
186 
187  for (i = 0; i < nkeys; i++)
188  {
189  SortSupport sortKey = base->sortKeys + i;
190 
191  Assert(attNums[i] != 0);
192  Assert(sortOperators[i] != 0);
193 
194  sortKey->ssup_cxt = CurrentMemoryContext;
195  sortKey->ssup_collation = sortCollations[i];
196  sortKey->ssup_nulls_first = nullsFirstFlags[i];
197  sortKey->ssup_attno = attNums[i];
198  /* Convey if abbreviation optimization is applicable in principle */
199  sortKey->abbreviate = (i == 0 && base->haveDatum1);
200 
201  PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
202  }
203 
204  /*
205  * The "onlyKey" optimization cannot be used with abbreviated keys, since
206  * tie-breaker comparisons may be required. Typically, the optimization
207  * is only of value to pass-by-value types anyway, whereas abbreviated
208  * keys are typically only of value to pass-by-reference types.
209  */
210  if (nkeys == 1 && !base->sortKeys->abbrev_converter)
211  base->onlyKey = base->sortKeys;
212 
213  MemoryContextSwitchTo(oldcontext);
214 
215  return state;
216 }
217 
220  Relation indexRel,
221  int workMem,
222  SortCoordinate coordinate, int sortopt)
223 {
224  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
225  sortopt);
227  BTScanInsert indexScanKey;
228  MemoryContext oldcontext;
230  int i;
231 
232  Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
233 
234  oldcontext = MemoryContextSwitchTo(base->maincontext);
236 
237 #ifdef TRACE_SORT
238  if (trace_sort)
239  elog(LOG,
240  "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
242  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
243 #endif
244 
246 
247  TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
248  false, /* no unique check */
249  base->nKeys,
250  workMem,
251  sortopt & TUPLESORT_RANDOMACCESS,
252  PARALLEL_SORT(coordinate));
253 
257  base->writetup = writetup_cluster;
258  base->readtup = readtup_cluster;
260  base->arg = arg;
261 
262  arg->indexInfo = BuildIndexInfo(indexRel);
263 
264  /*
265  * If we don't have a simple leading attribute, we don't currently
266  * initialize datum1, so disable optimizations that require it.
267  */
268  if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
269  base->haveDatum1 = false;
270  else
271  base->haveDatum1 = true;
272 
273  arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
274 
275  indexScanKey = _bt_mkscankey(indexRel, NULL);
276 
277  if (arg->indexInfo->ii_Expressions != NULL)
278  {
279  TupleTableSlot *slot;
280  ExprContext *econtext;
281 
282  /*
283  * We will need to use FormIndexDatum to evaluate the index
284  * expressions. To do that, we need an EState, as well as a
285  * TupleTableSlot to put the table tuples into. The econtext's
286  * scantuple has to point to that slot, too.
287  */
288  arg->estate = CreateExecutorState();
289  slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
290  econtext = GetPerTupleExprContext(arg->estate);
291  econtext->ecxt_scantuple = slot;
292  }
293 
294  /* Prepare SortSupport data for each column */
295  base->sortKeys = (SortSupport) palloc0(base->nKeys *
296  sizeof(SortSupportData));
297 
298  for (i = 0; i < base->nKeys; i++)
299  {
300  SortSupport sortKey = base->sortKeys + i;
301  ScanKey scanKey = indexScanKey->scankeys + i;
302  int16 strategy;
303 
304  sortKey->ssup_cxt = CurrentMemoryContext;
305  sortKey->ssup_collation = scanKey->sk_collation;
306  sortKey->ssup_nulls_first =
307  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
308  sortKey->ssup_attno = scanKey->sk_attno;
309  /* Convey if abbreviation optimization is applicable in principle */
310  sortKey->abbreviate = (i == 0 && base->haveDatum1);
311 
312  Assert(sortKey->ssup_attno != 0);
313 
314  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
316 
317  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
318  }
319 
320  pfree(indexScanKey);
321 
322  MemoryContextSwitchTo(oldcontext);
323 
324  return state;
325 }
326 
329  Relation indexRel,
330  bool enforceUnique,
331  bool uniqueNullsNotDistinct,
332  int workMem,
333  SortCoordinate coordinate,
334  int sortopt)
335 {
336  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
337  sortopt);
339  BTScanInsert indexScanKey;
341  MemoryContext oldcontext;
342  int i;
343 
344  oldcontext = MemoryContextSwitchTo(base->maincontext);
346 
347 #ifdef TRACE_SORT
348  if (trace_sort)
349  elog(LOG,
350  "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
351  enforceUnique ? 't' : 'f',
352  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
353 #endif
354 
356 
357  TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
358  enforceUnique,
359  base->nKeys,
360  workMem,
361  sortopt & TUPLESORT_RANDOMACCESS,
362  PARALLEL_SORT(coordinate));
363 
367  base->writetup = writetup_index;
368  base->readtup = readtup_index;
369  base->haveDatum1 = true;
370  base->arg = arg;
371 
372  arg->index.heapRel = heapRel;
373  arg->index.indexRel = indexRel;
374  arg->enforceUnique = enforceUnique;
375  arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
376 
377  indexScanKey = _bt_mkscankey(indexRel, NULL);
378 
379  /* Prepare SortSupport data for each column */
380  base->sortKeys = (SortSupport) palloc0(base->nKeys *
381  sizeof(SortSupportData));
382 
383  for (i = 0; i < base->nKeys; i++)
384  {
385  SortSupport sortKey = base->sortKeys + i;
386  ScanKey scanKey = indexScanKey->scankeys + i;
387  int16 strategy;
388 
389  sortKey->ssup_cxt = CurrentMemoryContext;
390  sortKey->ssup_collation = scanKey->sk_collation;
391  sortKey->ssup_nulls_first =
392  (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
393  sortKey->ssup_attno = scanKey->sk_attno;
394  /* Convey if abbreviation optimization is applicable in principle */
395  sortKey->abbreviate = (i == 0 && base->haveDatum1);
396 
397  Assert(sortKey->ssup_attno != 0);
398 
399  strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
401 
402  PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
403  }
404 
405  pfree(indexScanKey);
406 
407  MemoryContextSwitchTo(oldcontext);
408 
409  return state;
410 }
411 
414  Relation indexRel,
415  uint32 high_mask,
416  uint32 low_mask,
417  uint32 max_buckets,
418  int workMem,
419  SortCoordinate coordinate,
420  int sortopt)
421 {
422  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
423  sortopt);
425  MemoryContext oldcontext;
427 
428  oldcontext = MemoryContextSwitchTo(base->maincontext);
430 
431 #ifdef TRACE_SORT
432  if (trace_sort)
433  elog(LOG,
434  "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
435  "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
436  high_mask,
437  low_mask,
438  max_buckets,
439  workMem,
440  sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
441 #endif
442 
443  base->nKeys = 1; /* Only one sort column, the hash code */
444 
448  base->writetup = writetup_index;
449  base->readtup = readtup_index;
450  base->haveDatum1 = true;
451  base->arg = arg;
452 
453  arg->index.heapRel = heapRel;
454  arg->index.indexRel = indexRel;
455 
456  arg->high_mask = high_mask;
457  arg->low_mask = low_mask;
458  arg->max_buckets = max_buckets;
459 
460  MemoryContextSwitchTo(oldcontext);
461 
462  return state;
463 }
464 
467  Relation indexRel,
468  int workMem,
469  SortCoordinate coordinate,
470  int sortopt)
471 {
472  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
473  sortopt);
475  MemoryContext oldcontext;
477  int i;
478 
479  oldcontext = MemoryContextSwitchTo(base->maincontext);
481 
482 #ifdef TRACE_SORT
483  if (trace_sort)
484  elog(LOG,
485  "begin index sort: workMem = %d, randomAccess = %c",
486  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
487 #endif
488 
490 
494  base->writetup = writetup_index;
495  base->readtup = readtup_index;
496  base->haveDatum1 = true;
497  base->arg = arg;
498 
499  arg->index.heapRel = heapRel;
500  arg->index.indexRel = indexRel;
501  arg->enforceUnique = false;
502  arg->uniqueNullsNotDistinct = false;
503 
504  /* Prepare SortSupport data for each column */
505  base->sortKeys = (SortSupport) palloc0(base->nKeys *
506  sizeof(SortSupportData));
507 
508  for (i = 0; i < base->nKeys; i++)
509  {
510  SortSupport sortKey = base->sortKeys + i;
511 
512  sortKey->ssup_cxt = CurrentMemoryContext;
513  sortKey->ssup_collation = indexRel->rd_indcollation[i];
514  sortKey->ssup_nulls_first = false;
515  sortKey->ssup_attno = i + 1;
516  /* Convey if abbreviation optimization is applicable in principle */
517  sortKey->abbreviate = (i == 0 && base->haveDatum1);
518 
519  Assert(sortKey->ssup_attno != 0);
520 
521  /* Look for a sort support function */
522  PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
523  }
524 
525  MemoryContextSwitchTo(oldcontext);
526 
527  return state;
528 }
529 
531 tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation,
532  bool nullsFirstFlag, int workMem,
533  SortCoordinate coordinate, int sortopt)
534 {
535  Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
536  sortopt);
539  MemoryContext oldcontext;
540  int16 typlen;
541  bool typbyval;
542 
543  oldcontext = MemoryContextSwitchTo(base->maincontext);
545 
546 #ifdef TRACE_SORT
547  if (trace_sort)
548  elog(LOG,
549  "begin datum sort: workMem = %d, randomAccess = %c",
550  workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
551 #endif
552 
553  base->nKeys = 1; /* always a one-column sort */
554 
555  TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
556  false, /* no unique check */
557  1,
558  workMem,
559  sortopt & TUPLESORT_RANDOMACCESS,
560  PARALLEL_SORT(coordinate));
561 
565  base->writetup = writetup_datum;
566  base->readtup = readtup_datum;
567  base->haveDatum1 = true;
568  base->arg = arg;
569 
570  arg->datumType = datumType;
571 
572  /* lookup necessary attributes of the datum type */
573  get_typlenbyval(datumType, &typlen, &typbyval);
574  arg->datumTypeLen = typlen;
575  base->tuples = !typbyval;
576 
577  /* Prepare SortSupport data */
578  base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
579 
581  base->sortKeys->ssup_collation = sortCollation;
582  base->sortKeys->ssup_nulls_first = nullsFirstFlag;
583 
584  /*
585  * Abbreviation is possible here only for by-reference types. In theory,
586  * a pass-by-value datatype could have an abbreviated form that is cheaper
587  * to compare. In a tuple sort, we could support that, because we can
588  * always extract the original datum from the tuple as needed. Here, we
589  * can't, because a datum sort only stores a single copy of the datum; the
590  * "tuple" field of each SortTuple is NULL.
591  */
592  base->sortKeys->abbreviate = !typbyval;
593 
594  PrepareSortSupportFromOrderingOp(sortOperator, base->sortKeys);
595 
596  /*
597  * The "onlyKey" optimization cannot be used with abbreviated keys, since
598  * tie-breaker comparisons may be required. Typically, the optimization
599  * is only of value to pass-by-value types anyway, whereas abbreviated
600  * keys are typically only of value to pass-by-reference types.
601  */
602  if (!base->sortKeys->abbrev_converter)
603  base->onlyKey = base->sortKeys;
604 
605  MemoryContextSwitchTo(oldcontext);
606 
607  return state;
608 }
609 
610 /*
611  * Accept one tuple while collecting input data for sort.
612  *
613  * Note that the input data is always copied; the caller need not save it.
614  */
615 void
617 {
620  TupleDesc tupDesc = (TupleDesc) base->arg;
621  SortTuple stup;
622  MinimalTuple tuple;
623  HeapTupleData htup;
624 
625  /* copy the tuple into sort storage */
626  tuple = ExecCopySlotMinimalTuple(slot);
627  stup.tuple = (void *) tuple;
628  /* set up first-column key value */
629  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
630  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
631  stup.datum1 = heap_getattr(&htup,
632  base->sortKeys[0].ssup_attno,
633  tupDesc,
634  &stup.isnull1);
635 
637  base->sortKeys->abbrev_converter &&
638  !stup.isnull1);
639 
640  MemoryContextSwitchTo(oldcontext);
641 }
642 
643 /*
644  * Accept one tuple while collecting input data for sort.
645  *
646  * Note that the input data is always copied; the caller need not save it.
647  */
648 void
650 {
651  SortTuple stup;
655 
656  /* copy the tuple into sort storage */
657  tup = heap_copytuple(tup);
658  stup.tuple = (void *) tup;
659 
660  /*
661  * set up first-column key value, and potentially abbreviate, if it's a
662  * simple column
663  */
664  if (base->haveDatum1)
665  {
666  stup.datum1 = heap_getattr(tup,
667  arg->indexInfo->ii_IndexAttrNumbers[0],
668  arg->tupDesc,
669  &stup.isnull1);
670  }
671 
673  base->haveDatum1 &&
674  base->sortKeys->abbrev_converter &&
675  !stup.isnull1);
676 
677  MemoryContextSwitchTo(oldcontext);
678 }
679 
680 /*
681  * Collect one index tuple while collecting input data for sort, building
682  * it from caller-supplied values.
683  */
684 void
686  ItemPointer self, Datum *values,
687  bool *isnull)
688 {
689  SortTuple stup;
690  IndexTuple tuple;
693 
695  isnull, base->tuplecontext);
696  tuple = ((IndexTuple) stup.tuple);
697  tuple->t_tid = *self;
698  /* set up first-column key value */
699  stup.datum1 = index_getattr(tuple,
700  1,
701  RelationGetDescr(arg->indexRel),
702  &stup.isnull1);
703 
705  base->sortKeys &&
706  base->sortKeys->abbrev_converter &&
707  !stup.isnull1);
708 }
709 
710 /*
711  * Accept one Datum while collecting input data for sort.
712  *
713  * If the Datum is pass-by-ref type, the value will be copied.
714  */
715 void
717 {
721  SortTuple stup;
722 
723  /*
724  * Pass-by-value types or null values are just stored directly in
725  * stup.datum1 (and stup.tuple is not used and set to NULL).
726  *
727  * Non-null pass-by-reference values need to be copied into memory we
728  * control, and possibly abbreviated. The copied value is pointed to by
729  * stup.tuple and is treated as the canonical copy (e.g. to return via
730  * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
731  * abbreviated value if abbreviation is happening, otherwise it's
732  * identical to stup.tuple.
733  */
734 
735  if (isNull || !base->tuples)
736  {
737  /*
738  * Set datum1 to zeroed representation for NULLs (to be consistent,
739  * and to support cheap inequality tests for NULL abbreviated keys).
740  */
741  stup.datum1 = !isNull ? val : (Datum) 0;
742  stup.isnull1 = isNull;
743  stup.tuple = NULL; /* no separate storage */
744  }
745  else
746  {
747  stup.isnull1 = false;
748  stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
749  stup.tuple = DatumGetPointer(stup.datum1);
750  }
751 
753  base->tuples &&
754  base->sortKeys->abbrev_converter && !isNull);
755 
756  MemoryContextSwitchTo(oldcontext);
757 }
758 
759 /*
760  * Fetch the next tuple in either forward or back direction.
761  * If successful, put tuple in slot and return true; else, clear the slot
762  * and return false.
763  *
764  * Caller may optionally be passed back abbreviated value (on true return
765  * value) when abbreviation was used, which can be used to cheaply avoid
766  * equality checks that might otherwise be required. Caller can safely make a
767  * determination of "non-equal tuple" based on simple binary inequality. A
768  * NULL value in leading attribute will set abbreviated value to zeroed
769  * representation, which caller may rely on in abbreviated inequality check.
770  *
771  * If copy is true, the slot receives a tuple that's been copied into the
772  * caller's memory context, so that it will stay valid regardless of future
773  * manipulations of the tuplesort's state (up to and including deleting the
774  * tuplesort). If copy is false, the slot will just receive a pointer to a
775  * tuple held within the tuplesort, which is more efficient, but only safe for
776  * callers that are prepared to have any subsequent manipulation of the
777  * tuplesort's state invalidate slot contents.
778  */
779 bool
780 tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy,
781  TupleTableSlot *slot, Datum *abbrev)
782 {
784  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
785  SortTuple stup;
786 
787  if (!tuplesort_gettuple_common(state, forward, &stup))
788  stup.tuple = NULL;
789 
790  MemoryContextSwitchTo(oldcontext);
791 
792  if (stup.tuple)
793  {
794  /* Record abbreviated key for caller */
795  if (base->sortKeys->abbrev_converter && abbrev)
796  *abbrev = stup.datum1;
797 
798  if (copy)
800 
801  ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
802  return true;
803  }
804  else
805  {
806  ExecClearTuple(slot);
807  return false;
808  }
809 }
810 
811 /*
812  * Fetch the next tuple in either forward or back direction.
813  * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
814  * context, and must not be freed by caller. Caller may not rely on tuple
815  * remaining valid after any further manipulation of tuplesort.
816  */
817 HeapTuple
819 {
821  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
822  SortTuple stup;
823 
824  if (!tuplesort_gettuple_common(state, forward, &stup))
825  stup.tuple = NULL;
826 
827  MemoryContextSwitchTo(oldcontext);
828 
829  return stup.tuple;
830 }
831 
832 /*
833  * Fetch the next index tuple in either forward or back direction.
834  * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
835  * context, and must not be freed by caller. Caller may not rely on tuple
836  * remaining valid after any further manipulation of tuplesort.
837  */
840 {
842  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
843  SortTuple stup;
844 
845  if (!tuplesort_gettuple_common(state, forward, &stup))
846  stup.tuple = NULL;
847 
848  MemoryContextSwitchTo(oldcontext);
849 
850  return (IndexTuple) stup.tuple;
851 }
852 
853 /*
854  * Fetch the next Datum in either forward or back direction.
855  * Returns false if no more datums.
856  *
857  * If the Datum is pass-by-ref type, the returned value is freshly palloc'd
858  * in caller's context, and is now owned by the caller (this differs from
859  * similar routines for other types of tuplesorts).
860  *
861  * Caller may optionally be passed back abbreviated value (on true return
862  * value) when abbreviation was used, which can be used to cheaply avoid
863  * equality checks that might otherwise be required. Caller can safely make a
864  * determination of "non-equal tuple" based on simple binary inequality. A
865  * NULL value will have a zeroed abbreviated value representation, which caller
866  * may rely on in abbreviated inequality check.
867  *
868  * For byref Datums, if copy is true, *val is set to a copy of the Datum
869  * copied into the caller's memory context, so that it will stay valid
870  * regardless of future manipulations of the tuplesort's state (up to and
871  * including deleting the tuplesort). If copy is false, *val will just be
872  * set to a pointer to the Datum held within the tuplesort, which is more
873  * efficient, but only safe for callers that are prepared to have any
874  * subsequent manipulation of the tuplesort's state invalidate slot contents.
875  * For byval Datums, the value of the 'copy' parameter has no effect.
876 
877  */
878 bool
879 tuplesort_getdatum(Tuplesortstate *state, bool forward, bool copy,
880  Datum *val, bool *isNull, Datum *abbrev)
881 {
883  MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
885  SortTuple stup;
886 
887  if (!tuplesort_gettuple_common(state, forward, &stup))
888  {
889  MemoryContextSwitchTo(oldcontext);
890  return false;
891  }
892 
893  /* Ensure we copy into caller's memory context */
894  MemoryContextSwitchTo(oldcontext);
895 
896  /* Record abbreviated key for caller */
897  if (base->sortKeys->abbrev_converter && abbrev)
898  *abbrev = stup.datum1;
899 
900  if (stup.isnull1 || !base->tuples)
901  {
902  *val = stup.datum1;
903  *isNull = stup.isnull1;
904  }
905  else
906  {
907  /* use stup.tuple because stup.datum1 may be an abbreviation */
908  if (copy)
909  *val = datumCopy(PointerGetDatum(stup.tuple), false,
910  arg->datumTypeLen);
911  else
912  *val = PointerGetDatum(stup.tuple);
913  *isNull = false;
914  }
915 
916  return true;
917 }
918 
919 
920 /*
921  * Routines specialized for HeapTuple (actually MinimalTuple) case
922  */
923 
924 static void
926 {
927  int i;
929 
930  for (i = 0; i < count; i++)
931  {
932  HeapTupleData htup;
933 
934  htup.t_len = ((MinimalTuple) stups[i].tuple)->t_len +
936  htup.t_data = (HeapTupleHeader) ((char *) stups[i].tuple -
938  stups[i].datum1 = heap_getattr(&htup,
939  base->sortKeys[0].ssup_attno,
940  (TupleDesc) base->arg,
941  &stups[i].isnull1);
942  }
943 }
944 
945 static int
947 {
949  SortSupport sortKey = base->sortKeys;
950  int32 compare;
951 
952 
953  /* Compare the leading sort key */
954  compare = ApplySortComparator(a->datum1, a->isnull1,
955  b->datum1, b->isnull1,
956  sortKey);
957  if (compare != 0)
958  return compare;
959 
960  /* Compare additional sort keys */
961  return comparetup_heap_tiebreak(a, b, state);
962 }
963 
964 static int
966 {
968  SortSupport sortKey = base->sortKeys;
969  HeapTupleData ltup;
970  HeapTupleData rtup;
971  TupleDesc tupDesc;
972  int nkey;
973  int32 compare;
974  AttrNumber attno;
975  Datum datum1,
976  datum2;
977  bool isnull1,
978  isnull2;
979 
980  ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
981  ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
982  rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
983  rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
984  tupDesc = (TupleDesc) base->arg;
985 
986  if (sortKey->abbrev_converter)
987  {
988  attno = sortKey->ssup_attno;
989 
990  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
991  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
992 
993  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
994  datum2, isnull2,
995  sortKey);
996  if (compare != 0)
997  return compare;
998  }
999 
1000  sortKey++;
1001  for (nkey = 1; nkey < base->nKeys; nkey++, sortKey++)
1002  {
1003  attno = sortKey->ssup_attno;
1004 
1005  datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
1006  datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
1007 
1008  compare = ApplySortComparator(datum1, isnull1,
1009  datum2, isnull2,
1010  sortKey);
1011  if (compare != 0)
1012  return compare;
1013  }
1014 
1015  return 0;
1016 }
1017 
1018 static void
1020 {
1022  MinimalTuple tuple = (MinimalTuple) stup->tuple;
1023 
1024  /* the part of the MinimalTuple we'll write: */
1025  char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
1026  unsigned int tupbodylen = tuple->t_len - MINIMAL_TUPLE_DATA_OFFSET;
1027 
1028  /* total on-disk footprint: */
1029  unsigned int tuplen = tupbodylen + sizeof(int);
1030 
1031  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1032  LogicalTapeWrite(tape, tupbody, tupbodylen);
1033  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1034  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1035 }
1036 
1037 static void
1039  LogicalTape *tape, unsigned int len)
1040 {
1041  unsigned int tupbodylen = len - sizeof(int);
1042  unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
1044  char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
1046  HeapTupleData htup;
1047 
1048  /* read in the tuple proper */
1049  tuple->t_len = tuplen;
1050  LogicalTapeReadExact(tape, tupbody, tupbodylen);
1051  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1052  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1053  stup->tuple = (void *) tuple;
1054  /* set up first-column key value */
1055  htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
1056  htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
1057  stup->datum1 = heap_getattr(&htup,
1058  base->sortKeys[0].ssup_attno,
1059  (TupleDesc) base->arg,
1060  &stup->isnull1);
1061 }
1062 
1063 /*
1064  * Routines specialized for the CLUSTER case (HeapTuple data, with
1065  * comparisons per a btree index definition)
1066  */
1067 
1068 static void
1070 {
1071  int i;
1074 
1075  for (i = 0; i < count; i++)
1076  {
1077  HeapTuple tup;
1078 
1079  tup = (HeapTuple) stups[i].tuple;
1080  stups[i].datum1 = heap_getattr(tup,
1081  arg->indexInfo->ii_IndexAttrNumbers[0],
1082  arg->tupDesc,
1083  &stups[i].isnull1);
1084  }
1085 }
1086 
1087 static int
1090 {
1092  SortSupport sortKey = base->sortKeys;
1093  int32 compare;
1094 
1095  /* Compare the leading sort key, if it's simple */
1096  if (base->haveDatum1)
1097  {
1098  compare = ApplySortComparator(a->datum1, a->isnull1,
1099  b->datum1, b->isnull1,
1100  sortKey);
1101  if (compare != 0)
1102  return compare;
1103  }
1104 
1106 }
1107 
1108 static int
1111 {
1114  SortSupport sortKey = base->sortKeys;
1115  HeapTuple ltup;
1116  HeapTuple rtup;
1117  TupleDesc tupDesc;
1118  int nkey;
1119  int32 compare = 0;
1120  Datum datum1,
1121  datum2;
1122  bool isnull1,
1123  isnull2;
1124 
1125  ltup = (HeapTuple) a->tuple;
1126  rtup = (HeapTuple) b->tuple;
1127  tupDesc = arg->tupDesc;
1128 
1129  /* Compare the leading sort key, if it's simple */
1130  if (base->haveDatum1)
1131  {
1132  if (sortKey->abbrev_converter)
1133  {
1134  AttrNumber leading = arg->indexInfo->ii_IndexAttrNumbers[0];
1135 
1136  datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
1137  datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
1138 
1139  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1140  datum2, isnull2,
1141  sortKey);
1142  }
1143  if (compare != 0 || base->nKeys == 1)
1144  return compare;
1145  /* Compare additional columns the hard way */
1146  sortKey++;
1147  nkey = 1;
1148  }
1149  else
1150  {
1151  /* Must compare all keys the hard way */
1152  nkey = 0;
1153  }
1154 
1155  if (arg->indexInfo->ii_Expressions == NULL)
1156  {
1157  /* If not expression index, just compare the proper heap attrs */
1158 
1159  for (; nkey < base->nKeys; nkey++, sortKey++)
1160  {
1161  AttrNumber attno = arg->indexInfo->ii_IndexAttrNumbers[nkey];
1162 
1163  datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
1164  datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
1165 
1166  compare = ApplySortComparator(datum1, isnull1,
1167  datum2, isnull2,
1168  sortKey);
1169  if (compare != 0)
1170  return compare;
1171  }
1172  }
1173  else
1174  {
1175  /*
1176  * In the expression index case, compute the whole index tuple and
1177  * then compare values. It would perhaps be faster to compute only as
1178  * many columns as we need to compare, but that would require
1179  * duplicating all the logic in FormIndexDatum.
1180  */
1181  Datum l_index_values[INDEX_MAX_KEYS];
1182  bool l_index_isnull[INDEX_MAX_KEYS];
1183  Datum r_index_values[INDEX_MAX_KEYS];
1184  bool r_index_isnull[INDEX_MAX_KEYS];
1185  TupleTableSlot *ecxt_scantuple;
1186 
1187  /* Reset context each time to prevent memory leakage */
1188  ResetPerTupleExprContext(arg->estate);
1189 
1190  ecxt_scantuple = GetPerTupleExprContext(arg->estate)->ecxt_scantuple;
1191 
1192  ExecStoreHeapTuple(ltup, ecxt_scantuple, false);
1193  FormIndexDatum(arg->indexInfo, ecxt_scantuple, arg->estate,
1194  l_index_values, l_index_isnull);
1195 
1196  ExecStoreHeapTuple(rtup, ecxt_scantuple, false);
1197  FormIndexDatum(arg->indexInfo, ecxt_scantuple, arg->estate,
1198  r_index_values, r_index_isnull);
1199 
1200  for (; nkey < base->nKeys; nkey++, sortKey++)
1201  {
1202  compare = ApplySortComparator(l_index_values[nkey],
1203  l_index_isnull[nkey],
1204  r_index_values[nkey],
1205  r_index_isnull[nkey],
1206  sortKey);
1207  if (compare != 0)
1208  return compare;
1209  }
1210  }
1211 
1212  return 0;
1213 }
1214 
1215 static void
1217 {
1219  HeapTuple tuple = (HeapTuple) stup->tuple;
1220  unsigned int tuplen = tuple->t_len + sizeof(ItemPointerData) + sizeof(int);
1221 
1222  /* We need to store t_self, but not other fields of HeapTupleData */
1223  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1224  LogicalTapeWrite(tape, &tuple->t_self, sizeof(ItemPointerData));
1225  LogicalTapeWrite(tape, tuple->t_data, tuple->t_len);
1226  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1227  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1228 }
1229 
1230 static void
1232  LogicalTape *tape, unsigned int tuplen)
1233 {
1236  unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
1238  t_len + HEAPTUPLESIZE);
1239 
1240  /* Reconstruct the HeapTupleData header */
1241  tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
1242  tuple->t_len = t_len;
1243  LogicalTapeReadExact(tape, &tuple->t_self, sizeof(ItemPointerData));
1244  /* We don't currently bother to reconstruct t_tableOid */
1245  tuple->t_tableOid = InvalidOid;
1246  /* Read in the tuple body */
1247  LogicalTapeReadExact(tape, tuple->t_data, tuple->t_len);
1248  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1249  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1250  stup->tuple = (void *) tuple;
1251  /* set up first-column key value, if it's a simple column */
1252  if (base->haveDatum1)
1253  stup->datum1 = heap_getattr(tuple,
1254  arg->indexInfo->ii_IndexAttrNumbers[0],
1255  arg->tupDesc,
1256  &stup->isnull1);
1257 }
1258 
1259 static void
1261 {
1264 
1265  /* Free any execution state created for CLUSTER case */
1266  if (arg->estate != NULL)
1267  {
1268  ExprContext *econtext = GetPerTupleExprContext(arg->estate);
1269 
1271  FreeExecutorState(arg->estate);
1272  }
1273 }
1274 
1275 /*
1276  * Routines specialized for IndexTuple case
1277  *
1278  * The btree and hash cases require separate comparison functions, but the
1279  * IndexTuple representation is the same so the copy/write/read support
1280  * functions can be shared.
1281  */
1282 
1283 static void
1285 {
1288  int i;
1289 
1290  for (i = 0; i < count; i++)
1291  {
1292  IndexTuple tuple;
1293 
1294  tuple = stups[i].tuple;
1295  stups[i].datum1 = index_getattr(tuple,
1296  1,
1297  RelationGetDescr(arg->indexRel),
1298  &stups[i].isnull1);
1299  }
1300 }
1301 
1302 static int
1305 {
1306  /*
1307  * This is similar to comparetup_heap(), but expects index tuples. There
1308  * is also special handling for enforcing uniqueness, and special
1309  * treatment for equal keys at the end.
1310  */
1312  SortSupport sortKey = base->sortKeys;
1313  int32 compare;
1314 
1315  /* Compare the leading sort key */
1316  compare = ApplySortComparator(a->datum1, a->isnull1,
1317  b->datum1, b->isnull1,
1318  sortKey);
1319  if (compare != 0)
1320  return compare;
1321 
1322  /* Compare additional sort keys */
1324 }
1325 
1326 static int
1329 {
1332  SortSupport sortKey = base->sortKeys;
1333  IndexTuple tuple1;
1334  IndexTuple tuple2;
1335  int keysz;
1336  TupleDesc tupDes;
1337  bool equal_hasnull = false;
1338  int nkey;
1339  int32 compare;
1340  Datum datum1,
1341  datum2;
1342  bool isnull1,
1343  isnull2;
1344 
1345  tuple1 = (IndexTuple) a->tuple;
1346  tuple2 = (IndexTuple) b->tuple;
1347  keysz = base->nKeys;
1348  tupDes = RelationGetDescr(arg->index.indexRel);
1349 
1350  if (sortKey->abbrev_converter)
1351  {
1352  datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
1353  datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
1354 
1355  compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1356  datum2, isnull2,
1357  sortKey);
1358  if (compare != 0)
1359  return compare;
1360  }
1361 
1362  /* they are equal, so we only need to examine one null flag */
1363  if (a->isnull1)
1364  equal_hasnull = true;
1365 
1366  sortKey++;
1367  for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
1368  {
1369  datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
1370  datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
1371 
1372  compare = ApplySortComparator(datum1, isnull1,
1373  datum2, isnull2,
1374  sortKey);
1375  if (compare != 0)
1376  return compare; /* done when we find unequal attributes */
1377 
1378  /* they are equal, so we only need to examine one null flag */
1379  if (isnull1)
1380  equal_hasnull = true;
1381  }
1382 
1383  /*
1384  * If btree has asked us to enforce uniqueness, complain if two equal
1385  * tuples are detected (unless there was at least one NULL field and NULLS
1386  * NOT DISTINCT was not set).
1387  *
1388  * It is sufficient to make the test here, because if two tuples are equal
1389  * they *must* get compared at some stage of the sort --- otherwise the
1390  * sort algorithm wouldn't have checked whether one must appear before the
1391  * other.
1392  */
1393  if (arg->enforceUnique && !(!arg->uniqueNullsNotDistinct && equal_hasnull))
1394  {
1396  bool isnull[INDEX_MAX_KEYS];
1397  char *key_desc;
1398 
1399  /*
1400  * Some rather brain-dead implementations of qsort (such as the one in
1401  * QNX 4) will sometimes call the comparison routine to compare a
1402  * value to itself, but we always use our own implementation, which
1403  * does not.
1404  */
1405  Assert(tuple1 != tuple2);
1406 
1407  index_deform_tuple(tuple1, tupDes, values, isnull);
1408 
1409  key_desc = BuildIndexValueDescription(arg->index.indexRel, values, isnull);
1410 
1411  ereport(ERROR,
1412  (errcode(ERRCODE_UNIQUE_VIOLATION),
1413  errmsg("could not create unique index \"%s\"",
1414  RelationGetRelationName(arg->index.indexRel)),
1415  key_desc ? errdetail("Key %s is duplicated.", key_desc) :
1416  errdetail("Duplicate keys exist."),
1417  errtableconstraint(arg->index.heapRel,
1418  RelationGetRelationName(arg->index.indexRel))));
1419  }
1420 
1421  /*
1422  * If key values are equal, we sort on ItemPointer. This is required for
1423  * btree indexes, since heap TID is treated as an implicit last key
1424  * attribute in order to ensure that all keys in the index are physically
1425  * unique.
1426  */
1427  {
1428  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
1429  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
1430 
1431  if (blk1 != blk2)
1432  return (blk1 < blk2) ? -1 : 1;
1433  }
1434  {
1435  OffsetNumber pos1 = ItemPointerGetOffsetNumber(&tuple1->t_tid);
1436  OffsetNumber pos2 = ItemPointerGetOffsetNumber(&tuple2->t_tid);
1437 
1438  if (pos1 != pos2)
1439  return (pos1 < pos2) ? -1 : 1;
1440  }
1441 
1442  /* ItemPointer values should never be equal */
1443  Assert(false);
1444 
1445  return 0;
1446 }
1447 
1448 static int
1451 {
1452  Bucket bucket1;
1453  Bucket bucket2;
1454  uint32 hash1;
1455  uint32 hash2;
1456  IndexTuple tuple1;
1457  IndexTuple tuple2;
1460 
1461  /*
1462  * Fetch hash keys and mask off bits we don't want to sort by, so that the
1463  * initial sort is just on the bucket number. We know that the first
1464  * column of the index tuple is the hash key.
1465  */
1466  Assert(!a->isnull1);
1467  bucket1 = _hash_hashkey2bucket(DatumGetUInt32(a->datum1),
1468  arg->max_buckets, arg->high_mask,
1469  arg->low_mask);
1470  Assert(!b->isnull1);
1471  bucket2 = _hash_hashkey2bucket(DatumGetUInt32(b->datum1),
1472  arg->max_buckets, arg->high_mask,
1473  arg->low_mask);
1474  if (bucket1 > bucket2)
1475  return 1;
1476  else if (bucket1 < bucket2)
1477  return -1;
1478 
1479  /*
1480  * If bucket values are equal, sort by hash values. This allows us to
1481  * insert directly onto bucket/overflow pages, where the index tuples are
1482  * stored in hash order to allow fast binary search within each page.
1483  */
1484  hash1 = DatumGetUInt32(a->datum1);
1485  hash2 = DatumGetUInt32(b->datum1);
1486  if (hash1 > hash2)
1487  return 1;
1488  else if (hash1 < hash2)
1489  return -1;
1490 
1491  /*
1492  * If hash values are equal, we sort on ItemPointer. This does not affect
1493  * validity of the finished index, but it may be useful to have index
1494  * scans in physical order.
1495  */
1496  tuple1 = (IndexTuple) a->tuple;
1497  tuple2 = (IndexTuple) b->tuple;
1498 
1499  {
1500  BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
1501  BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
1502 
1503  if (blk1 != blk2)
1504  return (blk1 < blk2) ? -1 : 1;
1505  }
1506  {
1509 
1510  if (pos1 != pos2)
1511  return (pos1 < pos2) ? -1 : 1;
1512  }
1513 
1514  /* ItemPointer values should never be equal */
1515  Assert(false);
1516 
1517  return 0;
1518 }
1519 
1520 /*
1521  * Sorting for hash indexes only uses one sort key, so this shouldn't ever be
1522  * called. It's only here for consistency.
1523  */
1524 static int
1527 {
1528  Assert(false);
1529 
1530  return 0;
1531 }
1532 
1533 static void
1535 {
1537  IndexTuple tuple = (IndexTuple) stup->tuple;
1538  unsigned int tuplen;
1539 
1540  tuplen = IndexTupleSize(tuple) + sizeof(tuplen);
1541  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1542  LogicalTapeWrite(tape, tuple, IndexTupleSize(tuple));
1543  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1544  LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1545 }
1546 
1547 static void
1549  LogicalTape *tape, unsigned int len)
1550 {
1553  unsigned int tuplen = len - sizeof(unsigned int);
1555 
1556  LogicalTapeReadExact(tape, tuple, tuplen);
1557  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1558  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1559  stup->tuple = (void *) tuple;
1560  /* set up first-column key value */
1561  stup->datum1 = index_getattr(tuple,
1562  1,
1563  RelationGetDescr(arg->indexRel),
1564  &stup->isnull1);
1565 }
1566 
1567 /*
1568  * Routines specialized for DatumTuple case
1569  */
1570 
1571 static void
1573 {
1574  int i;
1575 
1576  for (i = 0; i < count; i++)
1577  stups[i].datum1 = PointerGetDatum(stups[i].tuple);
1578 }
1579 
1580 static int
1582 {
1584  int compare;
1585 
1586  compare = ApplySortComparator(a->datum1, a->isnull1,
1587  b->datum1, b->isnull1,
1588  base->sortKeys);
1589  if (compare != 0)
1590  return compare;
1591 
1592  return comparetup_datum_tiebreak(a, b, state);
1593 }
1594 
1595 static int
1597 {
1599  int32 compare = 0;
1600 
1601  /* if we have abbreviations, then "tuple" has the original value */
1602  if (base->sortKeys->abbrev_converter)
1604  PointerGetDatum(b->tuple), b->isnull1,
1605  base->sortKeys);
1606 
1607  return compare;
1608 }
1609 
1610 static void
1612 {
1615  void *waddr;
1616  unsigned int tuplen;
1617  unsigned int writtenlen;
1618 
1619  if (stup->isnull1)
1620  {
1621  waddr = NULL;
1622  tuplen = 0;
1623  }
1624  else if (!base->tuples)
1625  {
1626  waddr = &stup->datum1;
1627  tuplen = sizeof(Datum);
1628  }
1629  else
1630  {
1631  waddr = stup->tuple;
1632  tuplen = datumGetSize(PointerGetDatum(stup->tuple), false, arg->datumTypeLen);
1633  Assert(tuplen != 0);
1634  }
1635 
1636  writtenlen = tuplen + sizeof(unsigned int);
1637 
1638  LogicalTapeWrite(tape, &writtenlen, sizeof(writtenlen));
1639  LogicalTapeWrite(tape, waddr, tuplen);
1640  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1641  LogicalTapeWrite(tape, &writtenlen, sizeof(writtenlen));
1642 }
1643 
1644 static void
1646  LogicalTape *tape, unsigned int len)
1647 {
1649  unsigned int tuplen = len - sizeof(unsigned int);
1650 
1651  if (tuplen == 0)
1652  {
1653  /* it's NULL */
1654  stup->datum1 = (Datum) 0;
1655  stup->isnull1 = true;
1656  stup->tuple = NULL;
1657  }
1658  else if (!base->tuples)
1659  {
1660  Assert(tuplen == sizeof(Datum));
1661  LogicalTapeReadExact(tape, &stup->datum1, tuplen);
1662  stup->isnull1 = false;
1663  stup->tuple = NULL;
1664  }
1665  else
1666  {
1667  void *raddr = tuplesort_readtup_alloc(state, tuplen);
1668 
1669  LogicalTapeReadExact(tape, raddr, tuplen);
1670  stup->datum1 = PointerGetDatum(raddr);
1671  stup->isnull1 = false;
1672  stup->tuple = raddr;
1673  }
1674 
1675  if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1676  LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1677 }
int16 AttrNumber
Definition: attnum.h:21
uint32 BlockNumber
Definition: block.h:31
static Datum values[MAXATTR]
Definition: bootstrap.c:156
unsigned int uint32
Definition: c.h:495
signed short int16
Definition: c.h:482
signed int int32
Definition: c.h:483
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
Size datumGetSize(Datum value, bool typByVal, int typLen)
Definition: datum.c:65
int errdetail(const char *fmt,...)
Definition: elog.c:1202
int errcode(int sqlerrcode)
Definition: elog.c:858
int errmsg(const char *fmt,...)
Definition: elog.c:1069
#define LOG
Definition: elog.h:31
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1255
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1447
TupleTableSlot * ExecStoreHeapTuple(HeapTuple tuple, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1353
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:84
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1239
EState * CreateExecutorState(void)
Definition: execUtils.c:93
void FreeExecutorState(EState *estate)
Definition: execUtils.c:194
#define ResetPerTupleExprContext(estate)
Definition: executor.h:558
#define GetPerTupleExprContext(estate)
Definition: executor.h:549
char * BuildIndexValueDescription(Relation indexRelation, Datum *values, bool *isnull)
Definition: genam.c:177
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
uint32 Bucket
Definition: hash.h:35
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:126
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:768
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1527
#define HEAPTUPLESIZE
Definition: htup.h:73
HeapTupleData * HeapTuple
Definition: htup.h:71
MinimalTupleData * MinimalTuple
Definition: htup.h:27
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define MINIMAL_TUPLE_OFFSET
Definition: htup_details.h:617
static Datum heap_getattr(HeapTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: htup_details.h:792
#define MINIMAL_TUPLE_DATA_OFFSET
Definition: htup_details.h:621
void FormIndexDatum(IndexInfo *indexInfo, TupleTableSlot *slot, EState *estate, Datum *values, bool *isnull)
Definition: index.c:2726
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2426
IndexTuple index_form_tuple_context(TupleDesc tupleDescriptor, Datum *values, bool *isnull, MemoryContext context)
Definition: indextuple.c:65
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:456
long val
Definition: informix.c:664
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int i
Definition: isn.c:73
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
IndexTupleData * IndexTuple
Definition: itup.h:53
#define IndexTupleSize(itup)
Definition: itup.h:70
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: itup.h:117
Assert(fmt[strlen(fmt) - 1] !='\n')
void LogicalTapeWrite(LogicalTape *lt, const void *ptr, size_t size)
Definition: logtape.c:761
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2233
void pfree(void *pointer)
Definition: mcxt.c:1456
void * palloc0(Size size)
Definition: mcxt.c:1257
MemoryContext CurrentMemoryContext
Definition: mcxt.c:135
void * palloc(Size size)
Definition: mcxt.c:1226
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1092
#define SK_BT_DESC
Definition: nbtree.h:1091
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
uint16 OffsetNumber
Definition: off.h:24
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
void * arg
#define INDEX_MAX_KEYS
const void size_t len
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:222
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
uintptr_t Datum
Definition: postgres.h:64
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
#define RelationGetDescr(relation)
Definition: rel.h:530
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:510
#define RelationGetRelationName(relation)
Definition: rel.h:538
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:523
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5989
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:189
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:135
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:162
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:341
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:798
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:249
ItemPointerData t_self
Definition: htup.h:65
uint32 t_len
Definition: htup.h:64
HeapTupleHeader t_data
Definition: htup.h:68
Oid t_tableOid
Definition: htup.h:66
ItemPointerData t_tid
Definition: itup.h:37
Oid * rd_indcollation
Definition: rel.h:216
Form_pg_class rd_rel
Definition: rel.h:111
int sk_flags
Definition: skey.h:66
Oid sk_collation
Definition: skey.h:70
AttrNumber sk_attno
Definition: skey.h:67
AttrNumber ssup_attno
Definition: sortsupport.h:81
bool ssup_nulls_first
Definition: sortsupport.h:75
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
MemoryContext ssup_cxt
Definition: sortsupport.h:66
bool isnull1
Definition: tuplesort.h:140
void * tuple
Definition: tuplesort.h:138
Datum datum1
Definition: tuplesort.h:139
TuplesortIndexArg index
TuplesortIndexArg index
SortSupport onlyKey
Definition: tuplesort.h:234
MemoryContext maincontext
Definition: tuplesort.h:207
void(* writetup)(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.h:183
void(* removeabbrev)(Tuplesortstate *state, SortTuple *stups, int count)
Definition: tuplesort.h:176
void(* freestate)(Tuplesortstate *state)
Definition: tuplesort.h:201
MemoryContext tuplecontext
Definition: tuplesort.h:210
MemoryContext sortcontext
Definition: tuplesort.h:209
void(* readtup)(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.h:192
SortTupleComparator comparetup
Definition: tuplesort.h:163
SortSupport sortKeys
Definition: tuplesort.h:224
SortTupleComparator comparetup_tiebreak
Definition: tuplesort.h:170
Definition: regguts.h:323
struct TupleDescData * TupleDesc
Definition: tupdesc.h:89
Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
Definition: tuplesort.c:643
void tuplesort_puttuple_common(Tuplesortstate *state, SortTuple *tuple, bool useAbbrev)
Definition: tuplesort.c:1187
bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1493
bool trace_sort
Definition: tuplesort.c:127
void * tuplesort_readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:2918
#define PARALLEL_SORT(coordinate)
Definition: tuplesort.h:244
#define TUPLESORT_RANDOMACCESS
Definition: tuplesort.h:95
#define LogicalTapeReadExact(tape, ptr, len)
Definition: tuplesort.h:251
#define TuplesortstateGetPublic(state)
Definition: tuplesort.h:248
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward)
static void removeabbrev_datum(Tuplesortstate *state, SortTuple *stups, int count)
static int comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
void tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
Tuplesortstate * tuplesort_begin_index_hash(Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, int sortopt)
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_index(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static int comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
static int comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Tuplesortstate * tuplesort_begin_index_gist(Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
Tuplesortstate * tuplesort_begin_index_btree(Relation heapRel, Relation indexRel, bool enforceUnique, bool uniqueNullsNotDistinct, int workMem, SortCoordinate coordinate, int sortopt)
static void removeabbrev_index(Tuplesortstate *state, SortTuple *stups, int count)
static int comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_datum(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
#define INDEX_SORT
static void readtup_heap(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int tuplen)
static void writetup_datum(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Tuplesortstate * tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, int sortopt)
#define CLUSTER_SORT
static int comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
#define DATUM_SORT
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
Tuplesortstate * tuplesort_begin_cluster(TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
static void writetup_heap(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static void writetup_index(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static int comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void freestate_cluster(Tuplesortstate *state)
static void removeabbrev_heap(Tuplesortstate *state, SortTuple *stups, int count)
void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup)
static int comparetup_cluster(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static int comparetup_index_hash_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
bool tuplesort_getdatum(Tuplesortstate *state, bool forward, bool copy, Datum *val, bool *isNull, Datum *abbrev)
static void writetup_cluster(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
static void removeabbrev_cluster(Tuplesortstate *state, SortTuple *stups, int count)
#define HEAP_SORT
Tuplesortstate * tuplesort_begin_heap(TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, int sortopt)
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:470
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:432