PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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-2024, 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/brin_tuple.h"
23#include "access/hash.h"
24#include "access/htup_details.h"
25#include "access/nbtree.h"
26#include "catalog/index.h"
27#include "executor/executor.h"
28#include "pg_trace.h"
29#include "utils/datum.h"
30#include "utils/guc.h"
31#include "utils/lsyscache.h"
32#include "utils/tuplesort.h"
33
34
35/* sort-type codes for sort__start probes */
36#define HEAP_SORT 0
37#define INDEX_SORT 1
38#define DATUM_SORT 2
39#define CLUSTER_SORT 3
40
42 int count);
44 int count);
46 int count);
48 int count);
50 int count);
51static int comparetup_heap(const SortTuple *a, const SortTuple *b,
53static int comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b,
56 SortTuple *stup);
57static void readtup_heap(Tuplesortstate *state, SortTuple *stup,
58 LogicalTape *tape, unsigned int len);
59static int comparetup_cluster(const SortTuple *a, const SortTuple *b,
61static int comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b,
64 SortTuple *stup);
66 LogicalTape *tape, unsigned int tuplen);
67static int comparetup_index_btree(const SortTuple *a, const SortTuple *b,
69static int comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
71static int comparetup_index_hash(const SortTuple *a, const SortTuple *b,
73static int comparetup_index_hash_tiebreak(const SortTuple *a, const SortTuple *b,
75static int comparetup_index_brin(const SortTuple *a, const SortTuple *b,
78 SortTuple *stup);
80 LogicalTape *tape, unsigned int len);
82 SortTuple *stup);
84 LogicalTape *tape, unsigned int len);
85static int comparetup_datum(const SortTuple *a, const SortTuple *b,
87static int comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b,
90 SortTuple *stup);
92 LogicalTape *tape, unsigned int len);
94
95/*
96 * Data structure pointed by "TuplesortPublic.arg" for the CLUSTER case. Set by
97 * the tuplesort_begin_cluster.
98 */
99typedef struct
100{
102
103 IndexInfo *indexInfo; /* info about index being used for reference */
104 EState *estate; /* for evaluating index expressions */
106
107/*
108 * Data structure pointed by "TuplesortPublic.arg" for the IndexTuple case.
109 * Set by tuplesort_begin_index_xxx and used only by the IndexTuple routines.
110 */
111typedef struct
112{
113 Relation heapRel; /* table the index is being built on */
114 Relation indexRel; /* index being built */
116
117/*
118 * Data structure pointed by "TuplesortPublic.arg" for the index_btree subcase.
119 */
120typedef struct
121{
123
124 bool enforceUnique; /* complain if we find duplicate tuples */
125 bool uniqueNullsNotDistinct; /* unique constraint null treatment */
127
128/*
129 * Data structure pointed by "TuplesortPublic.arg" for the index_hash subcase.
130 */
131typedef struct
132{
134
135 uint32 high_mask; /* masks for sortable part of hash code */
139
140/*
141 * Data structure pointed by "TuplesortPublic.arg" for the Datum case.
142 * Set by tuplesort_begin_datum and used only by the DatumTuple routines.
143 */
144typedef struct
145{
146 /* the datatype oid of Datum's to be sorted */
148 /* we need typelen in order to know how to copy the Datums. */
151
152/*
153 * Computing BrinTuple size with only the tuple is difficult, so we want to track
154 * the length referenced by the SortTuple. That's what BrinSortTuple is meant
155 * to do - it's essentially a BrinTuple prefixed by its length.
156 */
157typedef struct BrinSortTuple
158{
162
163/* Size of the BrinSortTuple, given length of the BrinTuple. */
164#define BRINSORTTUPLE_SIZE(len) (offsetof(BrinSortTuple, tuple) + (len))
165
166
169 int nkeys, AttrNumber *attNums,
170 Oid *sortOperators, Oid *sortCollations,
171 bool *nullsFirstFlags,
172 int workMem, SortCoordinate coordinate, int sortopt)
173{
174 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
175 sortopt);
177 MemoryContext oldcontext;
178 int i;
179
180 oldcontext = MemoryContextSwitchTo(base->maincontext);
181
182 Assert(nkeys > 0);
183
184 if (trace_sort)
185 elog(LOG,
186 "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
187 nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
188
189 base->nKeys = nkeys;
190
191 TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
192 false, /* no unique check */
193 nkeys,
194 workMem,
195 sortopt & TUPLESORT_RANDOMACCESS,
196 PARALLEL_SORT(coordinate));
197
201 base->writetup = writetup_heap;
202 base->readtup = readtup_heap;
203 base->haveDatum1 = true;
204 base->arg = tupDesc; /* assume we need not copy tupDesc */
205
206 /* Prepare SortSupport data for each column */
207 base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
208
209 for (i = 0; i < nkeys; i++)
210 {
211 SortSupport sortKey = base->sortKeys + i;
212
213 Assert(attNums[i] != 0);
214 Assert(sortOperators[i] != 0);
215
217 sortKey->ssup_collation = sortCollations[i];
218 sortKey->ssup_nulls_first = nullsFirstFlags[i];
219 sortKey->ssup_attno = attNums[i];
220 /* Convey if abbreviation optimization is applicable in principle */
221 sortKey->abbreviate = (i == 0 && base->haveDatum1);
222
223 PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
224 }
225
226 /*
227 * The "onlyKey" optimization cannot be used with abbreviated keys, since
228 * tie-breaker comparisons may be required. Typically, the optimization
229 * is only of value to pass-by-value types anyway, whereas abbreviated
230 * keys are typically only of value to pass-by-reference types.
231 */
232 if (nkeys == 1 && !base->sortKeys->abbrev_converter)
233 base->onlyKey = base->sortKeys;
234
235 MemoryContextSwitchTo(oldcontext);
236
237 return state;
238}
239
242 Relation indexRel,
243 int workMem,
244 SortCoordinate coordinate, int sortopt)
245{
246 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
247 sortopt);
249 BTScanInsert indexScanKey;
250 MemoryContext oldcontext;
252 int i;
253
254 Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
255
256 oldcontext = MemoryContextSwitchTo(base->maincontext);
258
259 if (trace_sort)
260 elog(LOG,
261 "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
263 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
264
266
267 TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
268 false, /* no unique check */
269 base->nKeys,
270 workMem,
271 sortopt & TUPLESORT_RANDOMACCESS,
272 PARALLEL_SORT(coordinate));
273
278 base->readtup = readtup_cluster;
280 base->arg = arg;
281
282 arg->indexInfo = BuildIndexInfo(indexRel);
283
284 /*
285 * If we don't have a simple leading attribute, we don't currently
286 * initialize datum1, so disable optimizations that require it.
287 */
288 if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
289 base->haveDatum1 = false;
290 else
291 base->haveDatum1 = true;
292
293 arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
294
295 indexScanKey = _bt_mkscankey(indexRel, NULL);
296
297 if (arg->indexInfo->ii_Expressions != NULL)
298 {
299 TupleTableSlot *slot;
300 ExprContext *econtext;
301
302 /*
303 * We will need to use FormIndexDatum to evaluate the index
304 * expressions. To do that, we need an EState, as well as a
305 * TupleTableSlot to put the table tuples into. The econtext's
306 * scantuple has to point to that slot, too.
307 */
308 arg->estate = CreateExecutorState();
310 econtext = GetPerTupleExprContext(arg->estate);
311 econtext->ecxt_scantuple = slot;
312 }
313
314 /* Prepare SortSupport data for each column */
315 base->sortKeys = (SortSupport) palloc0(base->nKeys *
316 sizeof(SortSupportData));
317
318 for (i = 0; i < base->nKeys; i++)
319 {
320 SortSupport sortKey = base->sortKeys + i;
321 ScanKey scanKey = indexScanKey->scankeys + i;
322 int16 strategy;
323
325 sortKey->ssup_collation = scanKey->sk_collation;
326 sortKey->ssup_nulls_first =
327 (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
328 sortKey->ssup_attno = scanKey->sk_attno;
329 /* Convey if abbreviation optimization is applicable in principle */
330 sortKey->abbreviate = (i == 0 && base->haveDatum1);
331
332 Assert(sortKey->ssup_attno != 0);
333
334 strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
336
337 PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
338 }
339
340 pfree(indexScanKey);
341
342 MemoryContextSwitchTo(oldcontext);
343
344 return state;
345}
346
349 Relation indexRel,
350 bool enforceUnique,
351 bool uniqueNullsNotDistinct,
352 int workMem,
353 SortCoordinate coordinate,
354 int sortopt)
355{
356 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
357 sortopt);
359 BTScanInsert indexScanKey;
361 MemoryContext oldcontext;
362 int i;
363
364 oldcontext = MemoryContextSwitchTo(base->maincontext);
366
367 if (trace_sort)
368 elog(LOG,
369 "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
370 enforceUnique ? 't' : 'f',
371 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
372
374
375 TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
376 enforceUnique,
377 base->nKeys,
378 workMem,
379 sortopt & TUPLESORT_RANDOMACCESS,
380 PARALLEL_SORT(coordinate));
381
385 base->writetup = writetup_index;
386 base->readtup = readtup_index;
387 base->haveDatum1 = true;
388 base->arg = arg;
389
390 arg->index.heapRel = heapRel;
391 arg->index.indexRel = indexRel;
392 arg->enforceUnique = enforceUnique;
393 arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
394
395 indexScanKey = _bt_mkscankey(indexRel, NULL);
396
397 /* Prepare SortSupport data for each column */
398 base->sortKeys = (SortSupport) palloc0(base->nKeys *
399 sizeof(SortSupportData));
400
401 for (i = 0; i < base->nKeys; i++)
402 {
403 SortSupport sortKey = base->sortKeys + i;
404 ScanKey scanKey = indexScanKey->scankeys + i;
405 int16 strategy;
406
408 sortKey->ssup_collation = scanKey->sk_collation;
409 sortKey->ssup_nulls_first =
410 (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
411 sortKey->ssup_attno = scanKey->sk_attno;
412 /* Convey if abbreviation optimization is applicable in principle */
413 sortKey->abbreviate = (i == 0 && base->haveDatum1);
414
415 Assert(sortKey->ssup_attno != 0);
416
417 strategy = (scanKey->sk_flags & SK_BT_DESC) != 0 ?
419
420 PrepareSortSupportFromIndexRel(indexRel, strategy, sortKey);
421 }
422
423 pfree(indexScanKey);
424
425 MemoryContextSwitchTo(oldcontext);
426
427 return state;
428}
429
432 Relation indexRel,
433 uint32 high_mask,
434 uint32 low_mask,
435 uint32 max_buckets,
436 int workMem,
437 SortCoordinate coordinate,
438 int sortopt)
439{
440 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
441 sortopt);
443 MemoryContext oldcontext;
445
446 oldcontext = MemoryContextSwitchTo(base->maincontext);
448
449 if (trace_sort)
450 elog(LOG,
451 "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
452 "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
453 high_mask,
454 low_mask,
455 max_buckets,
456 workMem,
457 sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
458
459 base->nKeys = 1; /* Only one sort column, the hash code */
460
464 base->writetup = writetup_index;
465 base->readtup = readtup_index;
466 base->haveDatum1 = true;
467 base->arg = arg;
468
469 arg->index.heapRel = heapRel;
470 arg->index.indexRel = indexRel;
471
472 arg->high_mask = high_mask;
473 arg->low_mask = low_mask;
474 arg->max_buckets = max_buckets;
475
476 MemoryContextSwitchTo(oldcontext);
477
478 return state;
479}
480
483 Relation indexRel,
484 int workMem,
485 SortCoordinate coordinate,
486 int sortopt)
487{
488 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
489 sortopt);
491 MemoryContext oldcontext;
493 int i;
494
495 oldcontext = MemoryContextSwitchTo(base->maincontext);
497
498 if (trace_sort)
499 elog(LOG,
500 "begin index sort: workMem = %d, randomAccess = %c",
501 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
502
504
508 base->writetup = writetup_index;
509 base->readtup = readtup_index;
510 base->haveDatum1 = true;
511 base->arg = arg;
512
513 arg->index.heapRel = heapRel;
514 arg->index.indexRel = indexRel;
515 arg->enforceUnique = false;
516 arg->uniqueNullsNotDistinct = false;
517
518 /* Prepare SortSupport data for each column */
519 base->sortKeys = (SortSupport) palloc0(base->nKeys *
520 sizeof(SortSupportData));
521
522 for (i = 0; i < base->nKeys; i++)
523 {
524 SortSupport sortKey = base->sortKeys + i;
525
527 sortKey->ssup_collation = indexRel->rd_indcollation[i];
528 sortKey->ssup_nulls_first = false;
529 sortKey->ssup_attno = i + 1;
530 /* Convey if abbreviation optimization is applicable in principle */
531 sortKey->abbreviate = (i == 0 && base->haveDatum1);
532
533 Assert(sortKey->ssup_attno != 0);
534
535 /* Look for a sort support function */
536 PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
537 }
538
539 MemoryContextSwitchTo(oldcontext);
540
541 return state;
542}
543
546 SortCoordinate coordinate,
547 int sortopt)
548{
549 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
550 sortopt);
552
553 if (trace_sort)
554 elog(LOG,
555 "begin index sort: workMem = %d, randomAccess = %c",
556 workMem,
557 sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
558
559 base->nKeys = 1; /* Only one sort column, the block number */
560
565 base->haveDatum1 = true;
566 base->arg = NULL;
567
568 return state;
569}
570
572tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation,
573 bool nullsFirstFlag, int workMem,
574 SortCoordinate coordinate, int sortopt)
575{
576 Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
577 sortopt);
580 MemoryContext oldcontext;
581 int16 typlen;
582 bool typbyval;
583
584 oldcontext = MemoryContextSwitchTo(base->maincontext);
586
587 if (trace_sort)
588 elog(LOG,
589 "begin datum sort: workMem = %d, randomAccess = %c",
590 workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
591
592 base->nKeys = 1; /* always a one-column sort */
593
594 TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
595 false, /* no unique check */
596 1,
597 workMem,
598 sortopt & TUPLESORT_RANDOMACCESS,
599 PARALLEL_SORT(coordinate));
600
604 base->writetup = writetup_datum;
605 base->readtup = readtup_datum;
606 base->haveDatum1 = true;
607 base->arg = arg;
608
609 arg->datumType = datumType;
610
611 /* lookup necessary attributes of the datum type */
612 get_typlenbyval(datumType, &typlen, &typbyval);
613 arg->datumTypeLen = typlen;
614 base->tuples = !typbyval;
615
616 /* Prepare SortSupport data */
617 base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
618
620 base->sortKeys->ssup_collation = sortCollation;
621 base->sortKeys->ssup_nulls_first = nullsFirstFlag;
622
623 /*
624 * Abbreviation is possible here only for by-reference types. In theory,
625 * a pass-by-value datatype could have an abbreviated form that is cheaper
626 * to compare. In a tuple sort, we could support that, because we can
627 * always extract the original datum from the tuple as needed. Here, we
628 * can't, because a datum sort only stores a single copy of the datum; the
629 * "tuple" field of each SortTuple is NULL.
630 */
631 base->sortKeys->abbreviate = !typbyval;
632
633 PrepareSortSupportFromOrderingOp(sortOperator, base->sortKeys);
634
635 /*
636 * The "onlyKey" optimization cannot be used with abbreviated keys, since
637 * tie-breaker comparisons may be required. Typically, the optimization
638 * is only of value to pass-by-value types anyway, whereas abbreviated
639 * keys are typically only of value to pass-by-reference types.
640 */
641 if (!base->sortKeys->abbrev_converter)
642 base->onlyKey = base->sortKeys;
643
644 MemoryContextSwitchTo(oldcontext);
645
646 return state;
647}
648
649/*
650 * Accept one tuple while collecting input data for sort.
651 *
652 * Note that the input data is always copied; the caller need not save it.
653 */
654void
656{
659 TupleDesc tupDesc = (TupleDesc) base->arg;
660 SortTuple stup;
661 MinimalTuple tuple;
662 HeapTupleData htup;
663 Size tuplen;
664
665 /* copy the tuple into sort storage */
666 tuple = ExecCopySlotMinimalTuple(slot);
667 stup.tuple = tuple;
668 /* set up first-column key value */
669 htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
670 htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
671 stup.datum1 = heap_getattr(&htup,
672 base->sortKeys[0].ssup_attno,
673 tupDesc,
674 &stup.isnull1);
675
676 /* GetMemoryChunkSpace is not supported for bump contexts */
678 tuplen = MAXALIGN(tuple->t_len);
679 else
680 tuplen = GetMemoryChunkSpace(tuple);
681
683 base->sortKeys->abbrev_converter &&
684 !stup.isnull1, tuplen);
685
686 MemoryContextSwitchTo(oldcontext);
687}
688
689/*
690 * Accept one tuple while collecting input data for sort.
691 *
692 * Note that the input data is always copied; the caller need not save it.
693 */
694void
696{
697 SortTuple stup;
701 Size tuplen;
702
703 /* copy the tuple into sort storage */
704 tup = heap_copytuple(tup);
705 stup.tuple = tup;
706
707 /*
708 * set up first-column key value, and potentially abbreviate, if it's a
709 * simple column
710 */
711 if (base->haveDatum1)
712 {
713 stup.datum1 = heap_getattr(tup,
714 arg->indexInfo->ii_IndexAttrNumbers[0],
715 arg->tupDesc,
716 &stup.isnull1);
717 }
718
719 /* GetMemoryChunkSpace is not supported for bump contexts */
721 tuplen = MAXALIGN(HEAPTUPLESIZE + tup->t_len);
722 else
723 tuplen = GetMemoryChunkSpace(tup);
724
726 base->haveDatum1 &&
727 base->sortKeys->abbrev_converter &&
728 !stup.isnull1, tuplen);
729
730 MemoryContextSwitchTo(oldcontext);
731}
732
733/*
734 * Collect one index tuple while collecting input data for sort, building
735 * it from caller-supplied values.
736 */
737void
739 ItemPointer self, const Datum *values,
740 const bool *isnull)
741{
742 SortTuple stup;
743 IndexTuple tuple;
746 Size tuplen;
747
749 isnull, base->tuplecontext);
750 tuple = ((IndexTuple) stup.tuple);
751 tuple->t_tid = *self;
752 /* set up first-column key value */
753 stup.datum1 = index_getattr(tuple,
754 1,
755 RelationGetDescr(arg->indexRel),
756 &stup.isnull1);
757
758 /* GetMemoryChunkSpace is not supported for bump contexts */
760 tuplen = MAXALIGN(tuple->t_info & INDEX_SIZE_MASK);
761 else
762 tuplen = GetMemoryChunkSpace(tuple);
763
765 base->sortKeys &&
766 base->sortKeys->abbrev_converter &&
767 !stup.isnull1, tuplen);
768}
769
770/*
771 * Collect one BRIN tuple while collecting input data for sort.
772 */
773void
775{
776 SortTuple stup;
777 BrinSortTuple *bstup;
780 Size tuplen;
781
782 /* allocate space for the whole BRIN sort tuple */
784
785 bstup->tuplen = size;
786 memcpy(&bstup->tuple, tuple, size);
787
788 stup.tuple = bstup;
789 stup.datum1 = tuple->bt_blkno;
790 stup.isnull1 = false;
791
792 /* GetMemoryChunkSpace is not supported for bump contexts */
795 else
796 tuplen = GetMemoryChunkSpace(bstup);
797
799 base->sortKeys &&
800 base->sortKeys->abbrev_converter &&
801 !stup.isnull1, tuplen);
802
803 MemoryContextSwitchTo(oldcontext);
804}
805
806/*
807 * Accept one Datum while collecting input data for sort.
808 *
809 * If the Datum is pass-by-ref type, the value will be copied.
810 */
811void
813{
817 SortTuple stup;
818
819 /*
820 * Pass-by-value types or null values are just stored directly in
821 * stup.datum1 (and stup.tuple is not used and set to NULL).
822 *
823 * Non-null pass-by-reference values need to be copied into memory we
824 * control, and possibly abbreviated. The copied value is pointed to by
825 * stup.tuple and is treated as the canonical copy (e.g. to return via
826 * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
827 * abbreviated value if abbreviation is happening, otherwise it's
828 * identical to stup.tuple.
829 */
830
831 if (isNull || !base->tuples)
832 {
833 /*
834 * Set datum1 to zeroed representation for NULLs (to be consistent,
835 * and to support cheap inequality tests for NULL abbreviated keys).
836 */
837 stup.datum1 = !isNull ? val : (Datum) 0;
838 stup.isnull1 = isNull;
839 stup.tuple = NULL; /* no separate storage */
840 }
841 else
842 {
843 stup.isnull1 = false;
844 stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
845 stup.tuple = DatumGetPointer(stup.datum1);
846 }
847
849 base->tuples &&
850 base->sortKeys->abbrev_converter && !isNull, 0);
851
852 MemoryContextSwitchTo(oldcontext);
853}
854
855/*
856 * Fetch the next tuple in either forward or back direction.
857 * If successful, put tuple in slot and return true; else, clear the slot
858 * and return false.
859 *
860 * Caller may optionally be passed back abbreviated value (on true return
861 * value) when abbreviation was used, which can be used to cheaply avoid
862 * equality checks that might otherwise be required. Caller can safely make a
863 * determination of "non-equal tuple" based on simple binary inequality. A
864 * NULL value in leading attribute will set abbreviated value to zeroed
865 * representation, which caller may rely on in abbreviated inequality check.
866 *
867 * If copy is true, the slot receives a tuple that's been copied into the
868 * caller's memory context, so that it will stay valid regardless of future
869 * manipulations of the tuplesort's state (up to and including deleting the
870 * tuplesort). If copy is false, the slot will just receive a pointer to a
871 * tuple held within the tuplesort, which is more efficient, but only safe for
872 * callers that are prepared to have any subsequent manipulation of the
873 * tuplesort's state invalidate slot contents.
874 */
875bool
877 TupleTableSlot *slot, Datum *abbrev)
878{
881 SortTuple stup;
882
883 if (!tuplesort_gettuple_common(state, forward, &stup))
884 stup.tuple = NULL;
885
886 MemoryContextSwitchTo(oldcontext);
887
888 if (stup.tuple)
889 {
890 /* Record abbreviated key for caller */
891 if (base->sortKeys->abbrev_converter && abbrev)
892 *abbrev = stup.datum1;
893
894 if (copy)
896
897 ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
898 return true;
899 }
900 else
901 {
902 ExecClearTuple(slot);
903 return false;
904 }
905}
906
907/*
908 * Fetch the next tuple in either forward or back direction.
909 * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
910 * context, and must not be freed by caller. Caller may not rely on tuple
911 * remaining valid after any further manipulation of tuplesort.
912 */
915{
918 SortTuple stup;
919
920 if (!tuplesort_gettuple_common(state, forward, &stup))
921 stup.tuple = NULL;
922
923 MemoryContextSwitchTo(oldcontext);
924
925 return stup.tuple;
926}
927
928/*
929 * Fetch the next index tuple in either forward or back direction.
930 * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
931 * context, and must not be freed by caller. Caller may not rely on tuple
932 * remaining valid after any further manipulation of tuplesort.
933 */
936{
939 SortTuple stup;
940
941 if (!tuplesort_gettuple_common(state, forward, &stup))
942 stup.tuple = NULL;
943
944 MemoryContextSwitchTo(oldcontext);
945
946 return (IndexTuple) stup.tuple;
947}
948
949/*
950 * Fetch the next BRIN tuple in either forward or back direction.
951 * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
952 * context, and must not be freed by caller. Caller may not rely on tuple
953 * remaining valid after any further manipulation of tuplesort.
954 */
955BrinTuple *
957{
960 SortTuple stup;
961 BrinSortTuple *btup;
962
963 if (!tuplesort_gettuple_common(state, forward, &stup))
964 stup.tuple = NULL;
965
966 MemoryContextSwitchTo(oldcontext);
967
968 if (!stup.tuple)
969 return NULL;
970
971 btup = (BrinSortTuple *) stup.tuple;
972
973 *len = btup->tuplen;
974
975 return &btup->tuple;
976}
977
978/*
979 * Fetch the next Datum in either forward or back direction.
980 * Returns false if no more datums.
981 *
982 * If the Datum is pass-by-ref type, the returned value is freshly palloc'd
983 * in caller's context, and is now owned by the caller (this differs from
984 * similar routines for other types of tuplesorts).
985 *
986 * Caller may optionally be passed back abbreviated value (on true return
987 * value) when abbreviation was used, which can be used to cheaply avoid
988 * equality checks that might otherwise be required. Caller can safely make a
989 * determination of "non-equal tuple" based on simple binary inequality. A
990 * NULL value will have a zeroed abbreviated value representation, which caller
991 * may rely on in abbreviated inequality check.
992 *
993 * For byref Datums, if copy is true, *val is set to a copy of the Datum
994 * copied into the caller's memory context, so that it will stay valid
995 * regardless of future manipulations of the tuplesort's state (up to and
996 * including deleting the tuplesort). If copy is false, *val will just be
997 * set to a pointer to the Datum held within the tuplesort, which is more
998 * efficient, but only safe for callers that are prepared to have any
999 * subsequent manipulation of the tuplesort's state invalidate slot contents.
1000 * For byval Datums, the value of the 'copy' parameter has no effect.
1001
1002 */
1003bool
1004tuplesort_getdatum(Tuplesortstate *state, bool forward, bool copy,
1005 Datum *val, bool *isNull, Datum *abbrev)
1006{
1010 SortTuple stup;
1011
1012 if (!tuplesort_gettuple_common(state, forward, &stup))
1013 {
1014 MemoryContextSwitchTo(oldcontext);
1015 return false;
1016 }
1017
1018 /* Ensure we copy into caller's memory context */
1019 MemoryContextSwitchTo(oldcontext);
1020
1021 /* Record abbreviated key for caller */
1022 if (base->sortKeys->abbrev_converter && abbrev)
1023 *abbrev = stup.datum1;
1024
1025 if (stup.isnull1 || !base->tuples)
1026 {
1027 *val = stup.datum1;
1028 *isNull = stup.isnull1;
1029 }
1030 else
1031 {
1032 /* use stup.tuple because stup.datum1 may be an abbreviation */
1033 if (copy)
1034 *val = datumCopy(PointerGetDatum(stup.tuple), false,
1035 arg->datumTypeLen);
1036 else
1037 *val = PointerGetDatum(stup.tuple);
1038 *isNull = false;
1039 }
1040
1041 return true;
1042}
1043
1044
1045/*
1046 * Routines specialized for HeapTuple (actually MinimalTuple) case
1047 */
1048
1049static void
1051{
1052 int i;
1054
1055 for (i = 0; i < count; i++)
1056 {
1057 HeapTupleData htup;
1058
1059 htup.t_len = ((MinimalTuple) stups[i].tuple)->t_len +
1061 htup.t_data = (HeapTupleHeader) ((char *) stups[i].tuple -
1063 stups[i].datum1 = heap_getattr(&htup,
1064 base->sortKeys[0].ssup_attno,
1065 (TupleDesc) base->arg,
1066 &stups[i].isnull1);
1067 }
1068}
1069
1070static int
1072{
1074 SortSupport sortKey = base->sortKeys;
1075 int32 compare;
1076
1077
1078 /* Compare the leading sort key */
1079 compare = ApplySortComparator(a->datum1, a->isnull1,
1080 b->datum1, b->isnull1,
1081 sortKey);
1082 if (compare != 0)
1083 return compare;
1084
1085 /* Compare additional sort keys */
1087}
1088
1089static int
1091{
1093 SortSupport sortKey = base->sortKeys;
1094 HeapTupleData ltup;
1095 HeapTupleData rtup;
1096 TupleDesc tupDesc;
1097 int nkey;
1098 int32 compare;
1099 AttrNumber attno;
1100 Datum datum1,
1101 datum2;
1102 bool isnull1,
1103 isnull2;
1104
1105 ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
1106 ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
1107 rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
1108 rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
1109 tupDesc = (TupleDesc) base->arg;
1110
1111 if (sortKey->abbrev_converter)
1112 {
1113 attno = sortKey->ssup_attno;
1114
1115 datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
1116 datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
1117
1118 compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1119 datum2, isnull2,
1120 sortKey);
1121 if (compare != 0)
1122 return compare;
1123 }
1124
1125 sortKey++;
1126 for (nkey = 1; nkey < base->nKeys; nkey++, sortKey++)
1127 {
1128 attno = sortKey->ssup_attno;
1129
1130 datum1 = heap_getattr(&ltup, attno, tupDesc, &isnull1);
1131 datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
1132
1133 compare = ApplySortComparator(datum1, isnull1,
1134 datum2, isnull2,
1135 sortKey);
1136 if (compare != 0)
1137 return compare;
1138 }
1139
1140 return 0;
1141}
1142
1143static void
1145{
1147 MinimalTuple tuple = (MinimalTuple) stup->tuple;
1148
1149 /* the part of the MinimalTuple we'll write: */
1150 char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
1151 unsigned int tupbodylen = tuple->t_len - MINIMAL_TUPLE_DATA_OFFSET;
1152
1153 /* total on-disk footprint: */
1154 unsigned int tuplen = tupbodylen + sizeof(int);
1155
1156 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1157 LogicalTapeWrite(tape, tupbody, tupbodylen);
1158 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1159 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1160}
1161
1162static void
1164 LogicalTape *tape, unsigned int len)
1165{
1166 unsigned int tupbodylen = len - sizeof(int);
1167 unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
1169 char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
1171 HeapTupleData htup;
1172
1173 /* read in the tuple proper */
1174 tuple->t_len = tuplen;
1175 LogicalTapeReadExact(tape, tupbody, tupbodylen);
1176 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1177 LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1178 stup->tuple = tuple;
1179 /* set up first-column key value */
1180 htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
1181 htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
1182 stup->datum1 = heap_getattr(&htup,
1183 base->sortKeys[0].ssup_attno,
1184 (TupleDesc) base->arg,
1185 &stup->isnull1);
1186}
1187
1188/*
1189 * Routines specialized for the CLUSTER case (HeapTuple data, with
1190 * comparisons per a btree index definition)
1191 */
1192
1193static void
1195{
1196 int i;
1199
1200 for (i = 0; i < count; i++)
1201 {
1202 HeapTuple tup;
1203
1204 tup = (HeapTuple) stups[i].tuple;
1205 stups[i].datum1 = heap_getattr(tup,
1206 arg->indexInfo->ii_IndexAttrNumbers[0],
1207 arg->tupDesc,
1208 &stups[i].isnull1);
1209 }
1210}
1211
1212static int
1215{
1217 SortSupport sortKey = base->sortKeys;
1218 int32 compare;
1219
1220 /* Compare the leading sort key, if it's simple */
1221 if (base->haveDatum1)
1222 {
1223 compare = ApplySortComparator(a->datum1, a->isnull1,
1224 b->datum1, b->isnull1,
1225 sortKey);
1226 if (compare != 0)
1227 return compare;
1228 }
1229
1231}
1232
1233static int
1236{
1239 SortSupport sortKey = base->sortKeys;
1240 HeapTuple ltup;
1241 HeapTuple rtup;
1242 TupleDesc tupDesc;
1243 int nkey;
1244 int32 compare = 0;
1245 Datum datum1,
1246 datum2;
1247 bool isnull1,
1248 isnull2;
1249
1250 ltup = (HeapTuple) a->tuple;
1251 rtup = (HeapTuple) b->tuple;
1252 tupDesc = arg->tupDesc;
1253
1254 /* Compare the leading sort key, if it's simple */
1255 if (base->haveDatum1)
1256 {
1257 if (sortKey->abbrev_converter)
1258 {
1259 AttrNumber leading = arg->indexInfo->ii_IndexAttrNumbers[0];
1260
1261 datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
1262 datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
1263
1264 compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1265 datum2, isnull2,
1266 sortKey);
1267 }
1268 if (compare != 0 || base->nKeys == 1)
1269 return compare;
1270 /* Compare additional columns the hard way */
1271 sortKey++;
1272 nkey = 1;
1273 }
1274 else
1275 {
1276 /* Must compare all keys the hard way */
1277 nkey = 0;
1278 }
1279
1280 if (arg->indexInfo->ii_Expressions == NULL)
1281 {
1282 /* If not expression index, just compare the proper heap attrs */
1283
1284 for (; nkey < base->nKeys; nkey++, sortKey++)
1285 {
1286 AttrNumber attno = arg->indexInfo->ii_IndexAttrNumbers[nkey];
1287
1288 datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
1289 datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
1290
1291 compare = ApplySortComparator(datum1, isnull1,
1292 datum2, isnull2,
1293 sortKey);
1294 if (compare != 0)
1295 return compare;
1296 }
1297 }
1298 else
1299 {
1300 /*
1301 * In the expression index case, compute the whole index tuple and
1302 * then compare values. It would perhaps be faster to compute only as
1303 * many columns as we need to compare, but that would require
1304 * duplicating all the logic in FormIndexDatum.
1305 */
1306 Datum l_index_values[INDEX_MAX_KEYS];
1307 bool l_index_isnull[INDEX_MAX_KEYS];
1308 Datum r_index_values[INDEX_MAX_KEYS];
1309 bool r_index_isnull[INDEX_MAX_KEYS];
1310 TupleTableSlot *ecxt_scantuple;
1311
1312 /* Reset context each time to prevent memory leakage */
1314
1315 ecxt_scantuple = GetPerTupleExprContext(arg->estate)->ecxt_scantuple;
1316
1317 ExecStoreHeapTuple(ltup, ecxt_scantuple, false);
1318 FormIndexDatum(arg->indexInfo, ecxt_scantuple, arg->estate,
1319 l_index_values, l_index_isnull);
1320
1321 ExecStoreHeapTuple(rtup, ecxt_scantuple, false);
1322 FormIndexDatum(arg->indexInfo, ecxt_scantuple, arg->estate,
1323 r_index_values, r_index_isnull);
1324
1325 for (; nkey < base->nKeys; nkey++, sortKey++)
1326 {
1327 compare = ApplySortComparator(l_index_values[nkey],
1328 l_index_isnull[nkey],
1329 r_index_values[nkey],
1330 r_index_isnull[nkey],
1331 sortKey);
1332 if (compare != 0)
1333 return compare;
1334 }
1335 }
1336
1337 return 0;
1338}
1339
1340static void
1342{
1344 HeapTuple tuple = (HeapTuple) stup->tuple;
1345 unsigned int tuplen = tuple->t_len + sizeof(ItemPointerData) + sizeof(int);
1346
1347 /* We need to store t_self, but not other fields of HeapTupleData */
1348 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1349 LogicalTapeWrite(tape, &tuple->t_self, sizeof(ItemPointerData));
1350 LogicalTapeWrite(tape, tuple->t_data, tuple->t_len);
1351 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1352 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1353}
1354
1355static void
1357 LogicalTape *tape, unsigned int tuplen)
1358{
1361 unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
1363 t_len + HEAPTUPLESIZE);
1364
1365 /* Reconstruct the HeapTupleData header */
1366 tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
1367 tuple->t_len = t_len;
1368 LogicalTapeReadExact(tape, &tuple->t_self, sizeof(ItemPointerData));
1369 /* We don't currently bother to reconstruct t_tableOid */
1370 tuple->t_tableOid = InvalidOid;
1371 /* Read in the tuple body */
1372 LogicalTapeReadExact(tape, tuple->t_data, tuple->t_len);
1373 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1374 LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1375 stup->tuple = tuple;
1376 /* set up first-column key value, if it's a simple column */
1377 if (base->haveDatum1)
1378 stup->datum1 = heap_getattr(tuple,
1379 arg->indexInfo->ii_IndexAttrNumbers[0],
1380 arg->tupDesc,
1381 &stup->isnull1);
1382}
1383
1384static void
1386{
1389
1390 /* Free any execution state created for CLUSTER case */
1391 if (arg->estate != NULL)
1392 {
1393 ExprContext *econtext = GetPerTupleExprContext(arg->estate);
1394
1396 FreeExecutorState(arg->estate);
1397 }
1398}
1399
1400/*
1401 * Routines specialized for IndexTuple case
1402 *
1403 * The btree and hash cases require separate comparison functions, but the
1404 * IndexTuple representation is the same so the copy/write/read support
1405 * functions can be shared.
1406 */
1407
1408static void
1410{
1413 int i;
1414
1415 for (i = 0; i < count; i++)
1416 {
1417 IndexTuple tuple;
1418
1419 tuple = stups[i].tuple;
1420 stups[i].datum1 = index_getattr(tuple,
1421 1,
1422 RelationGetDescr(arg->indexRel),
1423 &stups[i].isnull1);
1424 }
1425}
1426
1427static int
1430{
1431 /*
1432 * This is similar to comparetup_heap(), but expects index tuples. There
1433 * is also special handling for enforcing uniqueness, and special
1434 * treatment for equal keys at the end.
1435 */
1437 SortSupport sortKey = base->sortKeys;
1438 int32 compare;
1439
1440 /* Compare the leading sort key */
1441 compare = ApplySortComparator(a->datum1, a->isnull1,
1442 b->datum1, b->isnull1,
1443 sortKey);
1444 if (compare != 0)
1445 return compare;
1446
1447 /* Compare additional sort keys */
1449}
1450
1451static int
1454{
1457 SortSupport sortKey = base->sortKeys;
1458 IndexTuple tuple1;
1459 IndexTuple tuple2;
1460 int keysz;
1461 TupleDesc tupDes;
1462 bool equal_hasnull = false;
1463 int nkey;
1464 int32 compare;
1465 Datum datum1,
1466 datum2;
1467 bool isnull1,
1468 isnull2;
1469
1470 tuple1 = (IndexTuple) a->tuple;
1471 tuple2 = (IndexTuple) b->tuple;
1472 keysz = base->nKeys;
1473 tupDes = RelationGetDescr(arg->index.indexRel);
1474
1475 if (sortKey->abbrev_converter)
1476 {
1477 datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
1478 datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
1479
1480 compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1481 datum2, isnull2,
1482 sortKey);
1483 if (compare != 0)
1484 return compare;
1485 }
1486
1487 /* they are equal, so we only need to examine one null flag */
1488 if (a->isnull1)
1489 equal_hasnull = true;
1490
1491 sortKey++;
1492 for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
1493 {
1494 datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
1495 datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
1496
1497 compare = ApplySortComparator(datum1, isnull1,
1498 datum2, isnull2,
1499 sortKey);
1500 if (compare != 0)
1501 return compare; /* done when we find unequal attributes */
1502
1503 /* they are equal, so we only need to examine one null flag */
1504 if (isnull1)
1505 equal_hasnull = true;
1506 }
1507
1508 /*
1509 * If btree has asked us to enforce uniqueness, complain if two equal
1510 * tuples are detected (unless there was at least one NULL field and NULLS
1511 * NOT DISTINCT was not set).
1512 *
1513 * It is sufficient to make the test here, because if two tuples are equal
1514 * they *must* get compared at some stage of the sort --- otherwise the
1515 * sort algorithm wouldn't have checked whether one must appear before the
1516 * other.
1517 */
1518 if (arg->enforceUnique && !(!arg->uniqueNullsNotDistinct && equal_hasnull))
1519 {
1521 bool isnull[INDEX_MAX_KEYS];
1522 char *key_desc;
1523
1524 /*
1525 * Some rather brain-dead implementations of qsort (such as the one in
1526 * QNX 4) will sometimes call the comparison routine to compare a
1527 * value to itself, but we always use our own implementation, which
1528 * does not.
1529 */
1530 Assert(tuple1 != tuple2);
1531
1532 index_deform_tuple(tuple1, tupDes, values, isnull);
1533
1534 key_desc = BuildIndexValueDescription(arg->index.indexRel, values, isnull);
1535
1536 ereport(ERROR,
1537 (errcode(ERRCODE_UNIQUE_VIOLATION),
1538 errmsg("could not create unique index \"%s\"",
1539 RelationGetRelationName(arg->index.indexRel)),
1540 key_desc ? errdetail("Key %s is duplicated.", key_desc) :
1541 errdetail("Duplicate keys exist."),
1542 errtableconstraint(arg->index.heapRel,
1543 RelationGetRelationName(arg->index.indexRel))));
1544 }
1545
1546 /*
1547 * If key values are equal, we sort on ItemPointer. This is required for
1548 * btree indexes, since heap TID is treated as an implicit last key
1549 * attribute in order to ensure that all keys in the index are physically
1550 * unique.
1551 */
1552 {
1553 BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
1554 BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
1555
1556 if (blk1 != blk2)
1557 return (blk1 < blk2) ? -1 : 1;
1558 }
1559 {
1560 OffsetNumber pos1 = ItemPointerGetOffsetNumber(&tuple1->t_tid);
1561 OffsetNumber pos2 = ItemPointerGetOffsetNumber(&tuple2->t_tid);
1562
1563 if (pos1 != pos2)
1564 return (pos1 < pos2) ? -1 : 1;
1565 }
1566
1567 /* ItemPointer values should never be equal */
1568 Assert(false);
1569
1570 return 0;
1571}
1572
1573static int
1576{
1577 Bucket bucket1;
1578 Bucket bucket2;
1579 uint32 hash1;
1580 uint32 hash2;
1581 IndexTuple tuple1;
1582 IndexTuple tuple2;
1585
1586 /*
1587 * Fetch hash keys and mask off bits we don't want to sort by, so that the
1588 * initial sort is just on the bucket number. We know that the first
1589 * column of the index tuple is the hash key.
1590 */
1591 Assert(!a->isnull1);
1592 bucket1 = _hash_hashkey2bucket(DatumGetUInt32(a->datum1),
1593 arg->max_buckets, arg->high_mask,
1594 arg->low_mask);
1595 Assert(!b->isnull1);
1596 bucket2 = _hash_hashkey2bucket(DatumGetUInt32(b->datum1),
1597 arg->max_buckets, arg->high_mask,
1598 arg->low_mask);
1599 if (bucket1 > bucket2)
1600 return 1;
1601 else if (bucket1 < bucket2)
1602 return -1;
1603
1604 /*
1605 * If bucket values are equal, sort by hash values. This allows us to
1606 * insert directly onto bucket/overflow pages, where the index tuples are
1607 * stored in hash order to allow fast binary search within each page.
1608 */
1609 hash1 = DatumGetUInt32(a->datum1);
1610 hash2 = DatumGetUInt32(b->datum1);
1611 if (hash1 > hash2)
1612 return 1;
1613 else if (hash1 < hash2)
1614 return -1;
1615
1616 /*
1617 * If hash values are equal, we sort on ItemPointer. This does not affect
1618 * validity of the finished index, but it may be useful to have index
1619 * scans in physical order.
1620 */
1621 tuple1 = (IndexTuple) a->tuple;
1622 tuple2 = (IndexTuple) b->tuple;
1623
1624 {
1627
1628 if (blk1 != blk2)
1629 return (blk1 < blk2) ? -1 : 1;
1630 }
1631 {
1634
1635 if (pos1 != pos2)
1636 return (pos1 < pos2) ? -1 : 1;
1637 }
1638
1639 /* ItemPointer values should never be equal */
1640 Assert(false);
1641
1642 return 0;
1643}
1644
1645/*
1646 * Sorting for hash indexes only uses one sort key, so this shouldn't ever be
1647 * called. It's only here for consistency.
1648 */
1649static int
1652{
1653 Assert(false);
1654
1655 return 0;
1656}
1657
1658static void
1660{
1662 IndexTuple tuple = (IndexTuple) stup->tuple;
1663 unsigned int tuplen;
1664
1665 tuplen = IndexTupleSize(tuple) + sizeof(tuplen);
1666 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1667 LogicalTapeWrite(tape, tuple, IndexTupleSize(tuple));
1668 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1669 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1670}
1671
1672static void
1674 LogicalTape *tape, unsigned int len)
1675{
1678 unsigned int tuplen = len - sizeof(unsigned int);
1680
1681 LogicalTapeReadExact(tape, tuple, tuplen);
1682 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1683 LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1684 stup->tuple = tuple;
1685 /* set up first-column key value */
1686 stup->datum1 = index_getattr(tuple,
1687 1,
1688 RelationGetDescr(arg->indexRel),
1689 &stup->isnull1);
1690}
1691
1692/*
1693 * Routines specialized for BrinTuple case
1694 */
1695
1696static void
1698{
1699 int i;
1700
1701 for (i = 0; i < count; i++)
1702 {
1703 BrinSortTuple *tuple;
1704
1705 tuple = stups[i].tuple;
1706 stups[i].datum1 = tuple->tuple.bt_blkno;
1707 }
1708}
1709
1710static int
1713{
1714 Assert(TuplesortstateGetPublic(state)->haveDatum1);
1715
1716 if (DatumGetUInt32(a->datum1) > DatumGetUInt32(b->datum1))
1717 return 1;
1718
1719 if (DatumGetUInt32(a->datum1) < DatumGetUInt32(b->datum1))
1720 return -1;
1721
1722 /* silence compilers */
1723 return 0;
1724}
1725
1726static void
1728{
1730 BrinSortTuple *tuple = (BrinSortTuple *) stup->tuple;
1731 unsigned int tuplen = tuple->tuplen;
1732
1733 tuplen = tuplen + sizeof(tuplen);
1734 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1735 LogicalTapeWrite(tape, &tuple->tuple, tuple->tuplen);
1736 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1737 LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1738}
1739
1740static void
1742 LogicalTape *tape, unsigned int len)
1743{
1744 BrinSortTuple *tuple;
1746 unsigned int tuplen = len - sizeof(unsigned int);
1747
1748 /*
1749 * Allocate space for the BRIN sort tuple, which is BrinTuple with an
1750 * extra length field.
1751 */
1753 BRINSORTTUPLE_SIZE(tuplen));
1754
1755 tuple->tuplen = tuplen;
1756
1757 LogicalTapeReadExact(tape, &tuple->tuple, tuplen);
1758 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1759 LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1760 stup->tuple = tuple;
1761
1762 /* set up first-column key value, which is block number */
1763 stup->datum1 = tuple->tuple.bt_blkno;
1764}
1765
1766/*
1767 * Routines specialized for DatumTuple case
1768 */
1769
1770static void
1772{
1773 int i;
1774
1775 for (i = 0; i < count; i++)
1776 stups[i].datum1 = PointerGetDatum(stups[i].tuple);
1777}
1778
1779static int
1781{
1783 int compare;
1784
1785 compare = ApplySortComparator(a->datum1, a->isnull1,
1786 b->datum1, b->isnull1,
1787 base->sortKeys);
1788 if (compare != 0)
1789 return compare;
1790
1792}
1793
1794static int
1796{
1798 int32 compare = 0;
1799
1800 /* if we have abbreviations, then "tuple" has the original value */
1801 if (base->sortKeys->abbrev_converter)
1803 PointerGetDatum(b->tuple), b->isnull1,
1804 base->sortKeys);
1805
1806 return compare;
1807}
1808
1809static void
1811{
1814 void *waddr;
1815 unsigned int tuplen;
1816 unsigned int writtenlen;
1817
1818 if (stup->isnull1)
1819 {
1820 waddr = NULL;
1821 tuplen = 0;
1822 }
1823 else if (!base->tuples)
1824 {
1825 waddr = &stup->datum1;
1826 tuplen = sizeof(Datum);
1827 }
1828 else
1829 {
1830 waddr = stup->tuple;
1831 tuplen = datumGetSize(PointerGetDatum(stup->tuple), false, arg->datumTypeLen);
1832 Assert(tuplen != 0);
1833 }
1834
1835 writtenlen = tuplen + sizeof(unsigned int);
1836
1837 LogicalTapeWrite(tape, &writtenlen, sizeof(writtenlen));
1838 LogicalTapeWrite(tape, waddr, tuplen);
1839 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1840 LogicalTapeWrite(tape, &writtenlen, sizeof(writtenlen));
1841}
1842
1843static void
1845 LogicalTape *tape, unsigned int len)
1846{
1848 unsigned int tuplen = len - sizeof(unsigned int);
1849
1850 if (tuplen == 0)
1851 {
1852 /* it's NULL */
1853 stup->datum1 = (Datum) 0;
1854 stup->isnull1 = true;
1855 stup->tuple = NULL;
1856 }
1857 else if (!base->tuples)
1858 {
1859 Assert(tuplen == sizeof(Datum));
1860 LogicalTapeReadExact(tape, &stup->datum1, tuplen);
1861 stup->isnull1 = false;
1862 stup->tuple = NULL;
1863 }
1864 else
1865 {
1866 void *raddr = tuplesort_readtup_alloc(state, tuplen);
1867
1868 LogicalTapeReadExact(tape, raddr, tuplen);
1869 stup->datum1 = PointerGetDatum(raddr);
1870 stup->isnull1 = false;
1871 stup->tuple = raddr;
1872 }
1873
1874 if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1875 LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1876}
int16 AttrNumber
Definition: attnum.h:21
uint32 BlockNumber
Definition: block.h:31
static Datum values[MAXATTR]
Definition: bootstrap.c:151
#define MAXALIGN(LEN)
Definition: c.h:765
#define Assert(condition)
Definition: c.h:812
int16_t int16
Definition: c.h:480
int32_t int32
Definition: c.h:481
uint32_t uint32
Definition: c.h:485
size_t Size
Definition: c.h:559
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:1203
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define LOG
Definition: elog.h:31
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define ereport(elevel,...)
Definition: elog.h:149
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1425
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1441
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1633
const TupleTableSlotOps TTSOpsHeapTuple
Definition: execTuples.c:85
TupleTableSlot * ExecStoreHeapTuple(HeapTuple tuple, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1539
void FreeExecutorState(EState *estate)
Definition: execUtils.c:191
EState * CreateExecutorState(void)
Definition: execUtils.c:88
#define ResetPerTupleExprContext(estate)
Definition: executor.h:572
#define GetPerTupleExprContext(estate)
Definition: executor.h:563
char * BuildIndexValueDescription(Relation indexRelation, const Datum *values, const 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
for(;;)
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:125
HeapTuple heap_copytuple(HeapTuple tuple)
Definition: heaptuple.c:778
MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup)
Definition: heaptuple.c:1536
#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
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2426
void FormIndexDatum(IndexInfo *indexInfo, TupleTableSlot *slot, EState *estate, Datum *values, bool *isnull)
Definition: index.c:2727
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:456
IndexTuple index_form_tuple_context(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull, MemoryContext context)
Definition: indextuple.c:65
long val
Definition: informix.c:689
int b
Definition: isn.c:69
int a
Definition: isn.c:68
int i
Definition: isn.c:72
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76
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
#define INDEX_SIZE_MASK
Definition: itup.h:65
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:2251
void pfree(void *pointer)
Definition: mcxt.c:1521
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:721
void * palloc0(Size size)
Definition: mcxt.c:1347
void * palloc(Size size)
Definition: mcxt.c:1317
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1118
#define SK_BT_DESC
Definition: nbtree.h:1117
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:129
uint16 OffsetNumber
Definition: off.h:24
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
MemoryContextSwitchTo(old_ctx)
#define RelationGetDescr(relation)
Definition: rel.h:531
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:511
#define RelationGetRelationName(relation)
Definition: rel.h:539
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:524
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:6022
static pg_noinline void Size size
Definition: slab.c:607
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:188
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:161
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:793
BlockNumber bt_blkno
Definition: brin_tuple.h:66
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:258
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
unsigned short t_info
Definition: itup.h:49
Oid * rd_indcollation
Definition: rel.h:217
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:151
void * tuple
Definition: tuplesort.h:149
Datum datum1
Definition: tuplesort.h:150
TuplesortIndexArg index
TuplesortIndexArg index
SortSupport onlyKey
Definition: tuplesort.h:245
MemoryContext maincontext
Definition: tuplesort.h:218
void(* writetup)(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
Definition: tuplesort.h:194
void(* removeabbrev)(Tuplesortstate *state, SortTuple *stups, int count)
Definition: tuplesort.h:187
void(* freestate)(Tuplesortstate *state)
Definition: tuplesort.h:212
MemoryContext tuplecontext
Definition: tuplesort.h:221
MemoryContext sortcontext
Definition: tuplesort.h:220
void(* readtup)(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Definition: tuplesort.h:203
SortTupleComparator comparetup
Definition: tuplesort.h:174
SortSupport sortKeys
Definition: tuplesort.h:235
SortTupleComparator comparetup_tiebreak
Definition: tuplesort.h:181
Definition: regguts.h:323
struct TupleDescData * TupleDesc
Definition: tupdesc.h:137
Tuplesortstate * tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
Definition: tuplesort.c:642
void tuplesort_puttuple_common(Tuplesortstate *state, SortTuple *tuple, bool useAbbrev, Size tuplen)
Definition: tuplesort.c:1169
bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward, SortTuple *stup)
Definition: tuplesort.c:1470
bool trace_sort
Definition: tuplesort.c:124
void * tuplesort_readtup_alloc(Tuplesortstate *state, Size tuplen)
Definition: tuplesort.c:2883
#define TupleSortUseBumpTupleCxt(opt)
Definition: tuplesort.h:108
#define PARALLEL_SORT(coordinate)
Definition: tuplesort.h:255
#define TUPLESORT_RANDOMACCESS
Definition: tuplesort.h:96
#define LogicalTapeReadExact(tape, ptr, len)
Definition: tuplesort.h:262
#define TuplesortstateGetPublic(state)
Definition: tuplesort.h:259
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
static void writetup_index_brin(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
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)
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, const Datum *values, const bool *isnull)
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_brin(int workMem, SortCoordinate coordinate, int sortopt)
Tuplesortstate * tuplesort_begin_heap(TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, int sortopt)
Tuplesortstate * tuplesort_begin_cluster(TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
BrinTuple * tuplesort_getbrintuple(Tuplesortstate *state, Size *len, bool forward)
static void removeabbrev_index(Tuplesortstate *state, SortTuple *stups, int count)
Tuplesortstate * tuplesort_begin_index_btree(Relation heapRel, Relation indexRel, bool enforceUnique, bool uniqueNullsNotDistinct, int workMem, SortCoordinate coordinate, int sortopt)
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)
Tuplesortstate * tuplesort_begin_index_gist(Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
static void writetup_datum(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
struct BrinSortTuple BrinSortTuple
#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)
static void removeabbrev_index_brin(Tuplesortstate *state, SortTuple *stups, int count)
#define BRINSORTTUPLE_SIZE(len)
#define DATUM_SORT
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
static void readtup_index_brin(Tuplesortstate *state, SortTuple *stup, LogicalTape *tape, unsigned int len)
Tuplesortstate * tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, int sortopt)
void tuplesort_putbrintuple(Tuplesortstate *state, BrinTuple *tuple, Size size)
static void writetup_heap(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
static void writetup_index(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
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_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_brin(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)
static void removeabbrev_cluster(Tuplesortstate *state, SortTuple *stups, int count)
#define HEAP_SORT
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:492
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:454