Line data Source code
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-2025, 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/gin_tuple.h"
24 : #include "access/hash.h"
25 : #include "access/htup_details.h"
26 : #include "access/nbtree.h"
27 : #include "catalog/index.h"
28 : #include "catalog/pg_collation.h"
29 : #include "executor/executor.h"
30 : #include "pg_trace.h"
31 : #include "utils/datum.h"
32 : #include "utils/guc.h"
33 : #include "utils/lsyscache.h"
34 : #include "utils/rel.h"
35 : #include "utils/tuplesort.h"
36 :
37 :
38 : /* sort-type codes for sort__start probes */
39 : #define HEAP_SORT 0
40 : #define INDEX_SORT 1
41 : #define DATUM_SORT 2
42 : #define CLUSTER_SORT 3
43 :
44 : static void removeabbrev_heap(Tuplesortstate *state, SortTuple *stups,
45 : int count);
46 : static void removeabbrev_cluster(Tuplesortstate *state, SortTuple *stups,
47 : int count);
48 : static void removeabbrev_index(Tuplesortstate *state, SortTuple *stups,
49 : int count);
50 : static void removeabbrev_index_brin(Tuplesortstate *state, SortTuple *stups,
51 : int count);
52 : static void removeabbrev_index_gin(Tuplesortstate *state, SortTuple *stups,
53 : int count);
54 : static void removeabbrev_datum(Tuplesortstate *state, SortTuple *stups,
55 : int count);
56 : static int comparetup_heap(const SortTuple *a, const SortTuple *b,
57 : Tuplesortstate *state);
58 : static int comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b,
59 : Tuplesortstate *state);
60 : static void writetup_heap(Tuplesortstate *state, LogicalTape *tape,
61 : SortTuple *stup);
62 : static void readtup_heap(Tuplesortstate *state, SortTuple *stup,
63 : LogicalTape *tape, unsigned int len);
64 : static int comparetup_cluster(const SortTuple *a, const SortTuple *b,
65 : Tuplesortstate *state);
66 : static int comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b,
67 : Tuplesortstate *state);
68 : static void writetup_cluster(Tuplesortstate *state, LogicalTape *tape,
69 : SortTuple *stup);
70 : static void readtup_cluster(Tuplesortstate *state, SortTuple *stup,
71 : LogicalTape *tape, unsigned int tuplen);
72 : static int comparetup_index_btree(const SortTuple *a, const SortTuple *b,
73 : Tuplesortstate *state);
74 : static int comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
75 : Tuplesortstate *state);
76 : static int comparetup_index_hash(const SortTuple *a, const SortTuple *b,
77 : Tuplesortstate *state);
78 : static int comparetup_index_hash_tiebreak(const SortTuple *a, const SortTuple *b,
79 : Tuplesortstate *state);
80 : static int comparetup_index_brin(const SortTuple *a, const SortTuple *b,
81 : Tuplesortstate *state);
82 : static int comparetup_index_gin(const SortTuple *a, const SortTuple *b,
83 : Tuplesortstate *state);
84 : static void writetup_index(Tuplesortstate *state, LogicalTape *tape,
85 : SortTuple *stup);
86 : static void readtup_index(Tuplesortstate *state, SortTuple *stup,
87 : LogicalTape *tape, unsigned int len);
88 : static void writetup_index_brin(Tuplesortstate *state, LogicalTape *tape,
89 : SortTuple *stup);
90 : static void readtup_index_brin(Tuplesortstate *state, SortTuple *stup,
91 : LogicalTape *tape, unsigned int len);
92 : static void writetup_index_gin(Tuplesortstate *state, LogicalTape *tape,
93 : SortTuple *stup);
94 : static void readtup_index_gin(Tuplesortstate *state, SortTuple *stup,
95 : LogicalTape *tape, unsigned int len);
96 : static int comparetup_datum(const SortTuple *a, const SortTuple *b,
97 : Tuplesortstate *state);
98 : static int comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b,
99 : Tuplesortstate *state);
100 : static void writetup_datum(Tuplesortstate *state, LogicalTape *tape,
101 : SortTuple *stup);
102 : static void readtup_datum(Tuplesortstate *state, SortTuple *stup,
103 : LogicalTape *tape, unsigned int len);
104 : static void freestate_cluster(Tuplesortstate *state);
105 :
106 : /*
107 : * Data structure pointed by "TuplesortPublic.arg" for the CLUSTER case. Set by
108 : * the tuplesort_begin_cluster.
109 : */
110 : typedef struct
111 : {
112 : TupleDesc tupDesc;
113 :
114 : IndexInfo *indexInfo; /* info about index being used for reference */
115 : EState *estate; /* for evaluating index expressions */
116 : } TuplesortClusterArg;
117 :
118 : /*
119 : * Data structure pointed by "TuplesortPublic.arg" for the IndexTuple case.
120 : * Set by tuplesort_begin_index_xxx and used only by the IndexTuple routines.
121 : */
122 : typedef struct
123 : {
124 : Relation heapRel; /* table the index is being built on */
125 : Relation indexRel; /* index being built */
126 : } TuplesortIndexArg;
127 :
128 : /*
129 : * Data structure pointed by "TuplesortPublic.arg" for the index_btree subcase.
130 : */
131 : typedef struct
132 : {
133 : TuplesortIndexArg index;
134 :
135 : bool enforceUnique; /* complain if we find duplicate tuples */
136 : bool uniqueNullsNotDistinct; /* unique constraint null treatment */
137 : } TuplesortIndexBTreeArg;
138 :
139 : /*
140 : * Data structure pointed by "TuplesortPublic.arg" for the index_hash subcase.
141 : */
142 : typedef struct
143 : {
144 : TuplesortIndexArg index;
145 :
146 : uint32 high_mask; /* masks for sortable part of hash code */
147 : uint32 low_mask;
148 : uint32 max_buckets;
149 : } TuplesortIndexHashArg;
150 :
151 : /*
152 : * Data structure pointed by "TuplesortPublic.arg" for the Datum case.
153 : * Set by tuplesort_begin_datum and used only by the DatumTuple routines.
154 : */
155 : typedef struct
156 : {
157 : /* the datatype oid of Datum's to be sorted */
158 : Oid datumType;
159 : /* we need typelen in order to know how to copy the Datums. */
160 : int datumTypeLen;
161 : } TuplesortDatumArg;
162 :
163 : /*
164 : * Computing BrinTuple size with only the tuple is difficult, so we want to track
165 : * the length referenced by the SortTuple. That's what BrinSortTuple is meant
166 : * to do - it's essentially a BrinTuple prefixed by its length.
167 : */
168 : typedef struct BrinSortTuple
169 : {
170 : Size tuplen;
171 : BrinTuple tuple;
172 : } BrinSortTuple;
173 :
174 : /* Size of the BrinSortTuple, given length of the BrinTuple. */
175 : #define BRINSORTTUPLE_SIZE(len) (offsetof(BrinSortTuple, tuple) + (len))
176 :
177 :
178 : Tuplesortstate *
179 119702 : tuplesort_begin_heap(TupleDesc tupDesc,
180 : int nkeys, AttrNumber *attNums,
181 : Oid *sortOperators, Oid *sortCollations,
182 : bool *nullsFirstFlags,
183 : int workMem, SortCoordinate coordinate, int sortopt)
184 : {
185 119702 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
186 : sortopt);
187 119702 : TuplesortPublic *base = TuplesortstateGetPublic(state);
188 : MemoryContext oldcontext;
189 : int i;
190 :
191 119702 : oldcontext = MemoryContextSwitchTo(base->maincontext);
192 :
193 : Assert(nkeys > 0);
194 :
195 119702 : if (trace_sort)
196 0 : elog(LOG,
197 : "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
198 : nkeys, workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
199 :
200 119702 : base->nKeys = nkeys;
201 :
202 : TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
203 : false, /* no unique check */
204 : nkeys,
205 : workMem,
206 : sortopt & TUPLESORT_RANDOMACCESS,
207 : PARALLEL_SORT(coordinate));
208 :
209 119702 : base->removeabbrev = removeabbrev_heap;
210 119702 : base->comparetup = comparetup_heap;
211 119702 : base->comparetup_tiebreak = comparetup_heap_tiebreak;
212 119702 : base->writetup = writetup_heap;
213 119702 : base->readtup = readtup_heap;
214 119702 : base->haveDatum1 = true;
215 119702 : base->arg = tupDesc; /* assume we need not copy tupDesc */
216 :
217 : /* Prepare SortSupport data for each column */
218 119702 : base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
219 :
220 294064 : for (i = 0; i < nkeys; i++)
221 : {
222 174374 : SortSupport sortKey = base->sortKeys + i;
223 :
224 : Assert(attNums[i] != 0);
225 : Assert(sortOperators[i] != 0);
226 :
227 174374 : sortKey->ssup_cxt = CurrentMemoryContext;
228 174374 : sortKey->ssup_collation = sortCollations[i];
229 174374 : sortKey->ssup_nulls_first = nullsFirstFlags[i];
230 174374 : sortKey->ssup_attno = attNums[i];
231 : /* Convey if abbreviation optimization is applicable in principle */
232 174374 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
233 :
234 174374 : PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
235 : }
236 :
237 : /*
238 : * The "onlyKey" optimization cannot be used with abbreviated keys, since
239 : * tie-breaker comparisons may be required. Typically, the optimization
240 : * is only of value to pass-by-value types anyway, whereas abbreviated
241 : * keys are typically only of value to pass-by-reference types.
242 : */
243 119690 : if (nkeys == 1 && !base->sortKeys->abbrev_converter)
244 69546 : base->onlyKey = base->sortKeys;
245 :
246 119690 : MemoryContextSwitchTo(oldcontext);
247 :
248 119690 : return state;
249 : }
250 :
251 : Tuplesortstate *
252 116 : tuplesort_begin_cluster(TupleDesc tupDesc,
253 : Relation indexRel,
254 : int workMem,
255 : SortCoordinate coordinate, int sortopt)
256 : {
257 116 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
258 : sortopt);
259 116 : TuplesortPublic *base = TuplesortstateGetPublic(state);
260 : BTScanInsert indexScanKey;
261 : MemoryContext oldcontext;
262 : TuplesortClusterArg *arg;
263 : int i;
264 :
265 : Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
266 :
267 116 : oldcontext = MemoryContextSwitchTo(base->maincontext);
268 116 : arg = (TuplesortClusterArg *) palloc0(sizeof(TuplesortClusterArg));
269 :
270 116 : if (trace_sort)
271 0 : elog(LOG,
272 : "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
273 : RelationGetNumberOfAttributes(indexRel),
274 : workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
275 :
276 116 : base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
277 :
278 : TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
279 : false, /* no unique check */
280 : base->nKeys,
281 : workMem,
282 : sortopt & TUPLESORT_RANDOMACCESS,
283 : PARALLEL_SORT(coordinate));
284 :
285 116 : base->removeabbrev = removeabbrev_cluster;
286 116 : base->comparetup = comparetup_cluster;
287 116 : base->comparetup_tiebreak = comparetup_cluster_tiebreak;
288 116 : base->writetup = writetup_cluster;
289 116 : base->readtup = readtup_cluster;
290 116 : base->freestate = freestate_cluster;
291 116 : base->arg = arg;
292 :
293 116 : arg->indexInfo = BuildIndexInfo(indexRel);
294 :
295 : /*
296 : * If we don't have a simple leading attribute, we don't currently
297 : * initialize datum1, so disable optimizations that require it.
298 : */
299 116 : if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
300 24 : base->haveDatum1 = false;
301 : else
302 92 : base->haveDatum1 = true;
303 :
304 116 : arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
305 :
306 116 : indexScanKey = _bt_mkscankey(indexRel, NULL);
307 :
308 116 : if (arg->indexInfo->ii_Expressions != NULL)
309 : {
310 : TupleTableSlot *slot;
311 : ExprContext *econtext;
312 :
313 : /*
314 : * We will need to use FormIndexDatum to evaluate the index
315 : * expressions. To do that, we need an EState, as well as a
316 : * TupleTableSlot to put the table tuples into. The econtext's
317 : * scantuple has to point to that slot, too.
318 : */
319 24 : arg->estate = CreateExecutorState();
320 24 : slot = MakeSingleTupleTableSlot(tupDesc, &TTSOpsHeapTuple);
321 24 : econtext = GetPerTupleExprContext(arg->estate);
322 24 : econtext->ecxt_scantuple = slot;
323 : }
324 :
325 : /* Prepare SortSupport data for each column */
326 116 : base->sortKeys = (SortSupport) palloc0(base->nKeys *
327 : sizeof(SortSupportData));
328 :
329 256 : for (i = 0; i < base->nKeys; i++)
330 : {
331 140 : SortSupport sortKey = base->sortKeys + i;
332 140 : ScanKey scanKey = indexScanKey->scankeys + i;
333 : bool reverse;
334 :
335 140 : sortKey->ssup_cxt = CurrentMemoryContext;
336 140 : sortKey->ssup_collation = scanKey->sk_collation;
337 140 : sortKey->ssup_nulls_first =
338 140 : (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
339 140 : sortKey->ssup_attno = scanKey->sk_attno;
340 : /* Convey if abbreviation optimization is applicable in principle */
341 140 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
342 :
343 : Assert(sortKey->ssup_attno != 0);
344 :
345 140 : reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
346 :
347 140 : PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
348 : }
349 :
350 116 : pfree(indexScanKey);
351 :
352 116 : MemoryContextSwitchTo(oldcontext);
353 :
354 116 : return state;
355 : }
356 :
357 : Tuplesortstate *
358 92670 : tuplesort_begin_index_btree(Relation heapRel,
359 : Relation indexRel,
360 : bool enforceUnique,
361 : bool uniqueNullsNotDistinct,
362 : int workMem,
363 : SortCoordinate coordinate,
364 : int sortopt)
365 : {
366 92670 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
367 : sortopt);
368 92670 : TuplesortPublic *base = TuplesortstateGetPublic(state);
369 : BTScanInsert indexScanKey;
370 : TuplesortIndexBTreeArg *arg;
371 : MemoryContext oldcontext;
372 : int i;
373 :
374 92670 : oldcontext = MemoryContextSwitchTo(base->maincontext);
375 92670 : arg = (TuplesortIndexBTreeArg *) palloc(sizeof(TuplesortIndexBTreeArg));
376 :
377 92670 : if (trace_sort)
378 0 : elog(LOG,
379 : "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
380 : enforceUnique ? 't' : 'f',
381 : workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
382 :
383 92670 : base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
384 :
385 : TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
386 : enforceUnique,
387 : base->nKeys,
388 : workMem,
389 : sortopt & TUPLESORT_RANDOMACCESS,
390 : PARALLEL_SORT(coordinate));
391 :
392 92670 : base->removeabbrev = removeabbrev_index;
393 92670 : base->comparetup = comparetup_index_btree;
394 92670 : base->comparetup_tiebreak = comparetup_index_btree_tiebreak;
395 92670 : base->writetup = writetup_index;
396 92670 : base->readtup = readtup_index;
397 92670 : base->haveDatum1 = true;
398 92670 : base->arg = arg;
399 :
400 92670 : arg->index.heapRel = heapRel;
401 92670 : arg->index.indexRel = indexRel;
402 92670 : arg->enforceUnique = enforceUnique;
403 92670 : arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
404 :
405 92670 : indexScanKey = _bt_mkscankey(indexRel, NULL);
406 :
407 : /* Prepare SortSupport data for each column */
408 92670 : base->sortKeys = (SortSupport) palloc0(base->nKeys *
409 : sizeof(SortSupportData));
410 :
411 246068 : for (i = 0; i < base->nKeys; i++)
412 : {
413 153398 : SortSupport sortKey = base->sortKeys + i;
414 153398 : ScanKey scanKey = indexScanKey->scankeys + i;
415 : bool reverse;
416 :
417 153398 : sortKey->ssup_cxt = CurrentMemoryContext;
418 153398 : sortKey->ssup_collation = scanKey->sk_collation;
419 153398 : sortKey->ssup_nulls_first =
420 153398 : (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
421 153398 : sortKey->ssup_attno = scanKey->sk_attno;
422 : /* Convey if abbreviation optimization is applicable in principle */
423 153398 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
424 :
425 : Assert(sortKey->ssup_attno != 0);
426 :
427 153398 : reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
428 :
429 153398 : PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
430 : }
431 :
432 92670 : pfree(indexScanKey);
433 :
434 92670 : MemoryContextSwitchTo(oldcontext);
435 :
436 92670 : return state;
437 : }
438 :
439 : Tuplesortstate *
440 8 : tuplesort_begin_index_hash(Relation heapRel,
441 : Relation indexRel,
442 : uint32 high_mask,
443 : uint32 low_mask,
444 : uint32 max_buckets,
445 : int workMem,
446 : SortCoordinate coordinate,
447 : int sortopt)
448 : {
449 8 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
450 : sortopt);
451 8 : TuplesortPublic *base = TuplesortstateGetPublic(state);
452 : MemoryContext oldcontext;
453 : TuplesortIndexHashArg *arg;
454 :
455 8 : oldcontext = MemoryContextSwitchTo(base->maincontext);
456 8 : arg = (TuplesortIndexHashArg *) palloc(sizeof(TuplesortIndexHashArg));
457 :
458 8 : if (trace_sort)
459 0 : elog(LOG,
460 : "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
461 : "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
462 : high_mask,
463 : low_mask,
464 : max_buckets,
465 : workMem,
466 : sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
467 :
468 8 : base->nKeys = 1; /* Only one sort column, the hash code */
469 :
470 8 : base->removeabbrev = removeabbrev_index;
471 8 : base->comparetup = comparetup_index_hash;
472 8 : base->comparetup_tiebreak = comparetup_index_hash_tiebreak;
473 8 : base->writetup = writetup_index;
474 8 : base->readtup = readtup_index;
475 8 : base->haveDatum1 = true;
476 8 : base->arg = arg;
477 :
478 8 : arg->index.heapRel = heapRel;
479 8 : arg->index.indexRel = indexRel;
480 :
481 8 : arg->high_mask = high_mask;
482 8 : arg->low_mask = low_mask;
483 8 : arg->max_buckets = max_buckets;
484 :
485 8 : MemoryContextSwitchTo(oldcontext);
486 :
487 8 : return state;
488 : }
489 :
490 : Tuplesortstate *
491 824 : tuplesort_begin_index_gist(Relation heapRel,
492 : Relation indexRel,
493 : int workMem,
494 : SortCoordinate coordinate,
495 : int sortopt)
496 : {
497 824 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
498 : sortopt);
499 824 : TuplesortPublic *base = TuplesortstateGetPublic(state);
500 : MemoryContext oldcontext;
501 : TuplesortIndexBTreeArg *arg;
502 : int i;
503 :
504 824 : oldcontext = MemoryContextSwitchTo(base->maincontext);
505 824 : arg = (TuplesortIndexBTreeArg *) palloc(sizeof(TuplesortIndexBTreeArg));
506 :
507 824 : if (trace_sort)
508 0 : elog(LOG,
509 : "begin index sort: workMem = %d, randomAccess = %c",
510 : workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
511 :
512 824 : base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
513 :
514 824 : base->removeabbrev = removeabbrev_index;
515 824 : base->comparetup = comparetup_index_btree;
516 824 : base->comparetup_tiebreak = comparetup_index_btree_tiebreak;
517 824 : base->writetup = writetup_index;
518 824 : base->readtup = readtup_index;
519 824 : base->haveDatum1 = true;
520 824 : base->arg = arg;
521 :
522 824 : arg->index.heapRel = heapRel;
523 824 : arg->index.indexRel = indexRel;
524 824 : arg->enforceUnique = false;
525 824 : arg->uniqueNullsNotDistinct = false;
526 :
527 : /* Prepare SortSupport data for each column */
528 824 : base->sortKeys = (SortSupport) palloc0(base->nKeys *
529 : sizeof(SortSupportData));
530 :
531 2262 : for (i = 0; i < base->nKeys; i++)
532 : {
533 1438 : SortSupport sortKey = base->sortKeys + i;
534 :
535 1438 : sortKey->ssup_cxt = CurrentMemoryContext;
536 1438 : sortKey->ssup_collation = indexRel->rd_indcollation[i];
537 1438 : sortKey->ssup_nulls_first = false;
538 1438 : sortKey->ssup_attno = i + 1;
539 : /* Convey if abbreviation optimization is applicable in principle */
540 1438 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
541 :
542 : Assert(sortKey->ssup_attno != 0);
543 :
544 : /* Look for a sort support function */
545 1438 : PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
546 : }
547 :
548 824 : MemoryContextSwitchTo(oldcontext);
549 :
550 824 : return state;
551 : }
552 :
553 : Tuplesortstate *
554 28 : tuplesort_begin_index_brin(int workMem,
555 : SortCoordinate coordinate,
556 : int sortopt)
557 : {
558 28 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
559 : sortopt);
560 28 : TuplesortPublic *base = TuplesortstateGetPublic(state);
561 :
562 28 : if (trace_sort)
563 0 : elog(LOG,
564 : "begin index sort: workMem = %d, randomAccess = %c",
565 : workMem,
566 : sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
567 :
568 28 : base->nKeys = 1; /* Only one sort column, the block number */
569 :
570 28 : base->removeabbrev = removeabbrev_index_brin;
571 28 : base->comparetup = comparetup_index_brin;
572 28 : base->writetup = writetup_index_brin;
573 28 : base->readtup = readtup_index_brin;
574 28 : base->haveDatum1 = true;
575 28 : base->arg = NULL;
576 :
577 28 : return state;
578 : }
579 :
580 : Tuplesortstate *
581 0 : tuplesort_begin_index_gin(Relation heapRel,
582 : Relation indexRel,
583 : int workMem, SortCoordinate coordinate,
584 : int sortopt)
585 : {
586 0 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
587 : sortopt);
588 0 : TuplesortPublic *base = TuplesortstateGetPublic(state);
589 : MemoryContext oldcontext;
590 : int i;
591 0 : TupleDesc desc = RelationGetDescr(indexRel);
592 :
593 0 : oldcontext = MemoryContextSwitchTo(base->maincontext);
594 :
595 : #ifdef TRACE_SORT
596 : if (trace_sort)
597 : elog(LOG,
598 : "begin index sort: workMem = %d, randomAccess = %c",
599 : workMem,
600 : sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
601 : #endif
602 :
603 : /*
604 : * Multi-column GIN indexes expand the row into a separate index entry for
605 : * attribute, and that's what we write into the tuplesort. But we still
606 : * need to initialize sortsupport for all the attributes.
607 : */
608 0 : base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
609 :
610 : /* Prepare SortSupport data for each column */
611 0 : base->sortKeys = (SortSupport) palloc0(base->nKeys *
612 : sizeof(SortSupportData));
613 :
614 0 : for (i = 0; i < base->nKeys; i++)
615 : {
616 0 : SortSupport sortKey = base->sortKeys + i;
617 0 : Form_pg_attribute att = TupleDescAttr(desc, i);
618 : TypeCacheEntry *typentry;
619 :
620 0 : sortKey->ssup_cxt = CurrentMemoryContext;
621 0 : sortKey->ssup_collation = indexRel->rd_indcollation[i];
622 0 : sortKey->ssup_nulls_first = false;
623 0 : sortKey->ssup_attno = i + 1;
624 0 : sortKey->abbreviate = false;
625 :
626 : Assert(sortKey->ssup_attno != 0);
627 :
628 0 : if (!OidIsValid(sortKey->ssup_collation))
629 0 : sortKey->ssup_collation = DEFAULT_COLLATION_OID;
630 :
631 : /*
632 : * Look for a ordering for the index key data type, and then the sort
633 : * support function.
634 : */
635 0 : typentry = lookup_type_cache(att->atttypid, TYPECACHE_LT_OPR);
636 0 : PrepareSortSupportFromOrderingOp(typentry->lt_opr, sortKey);
637 : }
638 :
639 0 : base->removeabbrev = removeabbrev_index_gin;
640 0 : base->comparetup = comparetup_index_gin;
641 0 : base->writetup = writetup_index_gin;
642 0 : base->readtup = readtup_index_gin;
643 0 : base->haveDatum1 = false;
644 0 : base->arg = NULL;
645 :
646 0 : MemoryContextSwitchTo(oldcontext);
647 :
648 0 : return state;
649 : }
650 :
651 : Tuplesortstate *
652 60882 : tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation,
653 : bool nullsFirstFlag, int workMem,
654 : SortCoordinate coordinate, int sortopt)
655 : {
656 60882 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
657 : sortopt);
658 60882 : TuplesortPublic *base = TuplesortstateGetPublic(state);
659 : TuplesortDatumArg *arg;
660 : MemoryContext oldcontext;
661 : int16 typlen;
662 : bool typbyval;
663 :
664 60882 : oldcontext = MemoryContextSwitchTo(base->maincontext);
665 60882 : arg = (TuplesortDatumArg *) palloc(sizeof(TuplesortDatumArg));
666 :
667 60882 : if (trace_sort)
668 0 : elog(LOG,
669 : "begin datum sort: workMem = %d, randomAccess = %c",
670 : workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
671 :
672 60882 : base->nKeys = 1; /* always a one-column sort */
673 :
674 : TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
675 : false, /* no unique check */
676 : 1,
677 : workMem,
678 : sortopt & TUPLESORT_RANDOMACCESS,
679 : PARALLEL_SORT(coordinate));
680 :
681 60882 : base->removeabbrev = removeabbrev_datum;
682 60882 : base->comparetup = comparetup_datum;
683 60882 : base->comparetup_tiebreak = comparetup_datum_tiebreak;
684 60882 : base->writetup = writetup_datum;
685 60882 : base->readtup = readtup_datum;
686 60882 : base->haveDatum1 = true;
687 60882 : base->arg = arg;
688 :
689 60882 : arg->datumType = datumType;
690 :
691 : /* lookup necessary attributes of the datum type */
692 60882 : get_typlenbyval(datumType, &typlen, &typbyval);
693 60882 : arg->datumTypeLen = typlen;
694 60882 : base->tuples = !typbyval;
695 :
696 : /* Prepare SortSupport data */
697 60882 : base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
698 :
699 60882 : base->sortKeys->ssup_cxt = CurrentMemoryContext;
700 60882 : base->sortKeys->ssup_collation = sortCollation;
701 60882 : base->sortKeys->ssup_nulls_first = nullsFirstFlag;
702 :
703 : /*
704 : * Abbreviation is possible here only for by-reference types. In theory,
705 : * a pass-by-value datatype could have an abbreviated form that is cheaper
706 : * to compare. In a tuple sort, we could support that, because we can
707 : * always extract the original datum from the tuple as needed. Here, we
708 : * can't, because a datum sort only stores a single copy of the datum; the
709 : * "tuple" field of each SortTuple is NULL.
710 : */
711 60882 : base->sortKeys->abbreviate = !typbyval;
712 :
713 60882 : PrepareSortSupportFromOrderingOp(sortOperator, base->sortKeys);
714 :
715 : /*
716 : * The "onlyKey" optimization cannot be used with abbreviated keys, since
717 : * tie-breaker comparisons may be required. Typically, the optimization
718 : * is only of value to pass-by-value types anyway, whereas abbreviated
719 : * keys are typically only of value to pass-by-reference types.
720 : */
721 60882 : if (!base->sortKeys->abbrev_converter)
722 60076 : base->onlyKey = base->sortKeys;
723 :
724 60882 : MemoryContextSwitchTo(oldcontext);
725 :
726 60882 : return state;
727 : }
728 :
729 : /*
730 : * Accept one tuple while collecting input data for sort.
731 : *
732 : * Note that the input data is always copied; the caller need not save it.
733 : */
734 : void
735 12646484 : tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
736 : {
737 12646484 : TuplesortPublic *base = TuplesortstateGetPublic(state);
738 12646484 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
739 12646484 : TupleDesc tupDesc = (TupleDesc) base->arg;
740 : SortTuple stup;
741 : MinimalTuple tuple;
742 : HeapTupleData htup;
743 : Size tuplen;
744 :
745 : /* copy the tuple into sort storage */
746 12646484 : tuple = ExecCopySlotMinimalTuple(slot);
747 12646484 : stup.tuple = tuple;
748 : /* set up first-column key value */
749 12646484 : htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
750 12646484 : htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
751 25292968 : stup.datum1 = heap_getattr(&htup,
752 12646484 : base->sortKeys[0].ssup_attno,
753 : tupDesc,
754 : &stup.isnull1);
755 :
756 : /* GetMemoryChunkSpace is not supported for bump contexts */
757 12646484 : if (TupleSortUseBumpTupleCxt(base->sortopt))
758 9143900 : tuplen = MAXALIGN(tuple->t_len);
759 : else
760 3502584 : tuplen = GetMemoryChunkSpace(tuple);
761 :
762 12646484 : tuplesort_puttuple_common(state, &stup,
763 13766950 : base->sortKeys->abbrev_converter &&
764 1120466 : !stup.isnull1, tuplen);
765 :
766 12646484 : MemoryContextSwitchTo(oldcontext);
767 12646484 : }
768 :
769 : /*
770 : * Accept one tuple while collecting input data for sort.
771 : *
772 : * Note that the input data is always copied; the caller need not save it.
773 : */
774 : void
775 547404 : tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup)
776 : {
777 : SortTuple stup;
778 547404 : TuplesortPublic *base = TuplesortstateGetPublic(state);
779 547404 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
780 547404 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
781 : Size tuplen;
782 :
783 : /* copy the tuple into sort storage */
784 547404 : tup = heap_copytuple(tup);
785 547404 : stup.tuple = tup;
786 :
787 : /*
788 : * set up first-column key value, and potentially abbreviate, if it's a
789 : * simple column
790 : */
791 547404 : if (base->haveDatum1)
792 : {
793 545778 : stup.datum1 = heap_getattr(tup,
794 545778 : arg->indexInfo->ii_IndexAttrNumbers[0],
795 : arg->tupDesc,
796 : &stup.isnull1);
797 : }
798 :
799 : /* GetMemoryChunkSpace is not supported for bump contexts */
800 547404 : if (TupleSortUseBumpTupleCxt(base->sortopt))
801 547404 : tuplen = MAXALIGN(HEAPTUPLESIZE + tup->t_len);
802 : else
803 0 : tuplen = GetMemoryChunkSpace(tup);
804 :
805 547404 : tuplesort_puttuple_common(state, &stup,
806 1093182 : base->haveDatum1 &&
807 910492 : base->sortKeys->abbrev_converter &&
808 363088 : !stup.isnull1, tuplen);
809 :
810 547404 : MemoryContextSwitchTo(oldcontext);
811 547404 : }
812 :
813 : /*
814 : * Collect one index tuple while collecting input data for sort, building
815 : * it from caller-supplied values.
816 : */
817 : void
818 13174490 : tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel,
819 : ItemPointer self, const Datum *values,
820 : const bool *isnull)
821 : {
822 : SortTuple stup;
823 : IndexTuple tuple;
824 13174490 : TuplesortPublic *base = TuplesortstateGetPublic(state);
825 13174490 : TuplesortIndexArg *arg = (TuplesortIndexArg *) base->arg;
826 : Size tuplen;
827 :
828 13174490 : stup.tuple = index_form_tuple_context(RelationGetDescr(rel), values,
829 : isnull, base->tuplecontext);
830 13174490 : tuple = ((IndexTuple) stup.tuple);
831 13174490 : tuple->t_tid = *self;
832 : /* set up first-column key value */
833 26348980 : stup.datum1 = index_getattr(tuple,
834 : 1,
835 13174490 : RelationGetDescr(arg->indexRel),
836 : &stup.isnull1);
837 :
838 : /* GetMemoryChunkSpace is not supported for bump contexts */
839 13174490 : if (TupleSortUseBumpTupleCxt(base->sortopt))
840 13174490 : tuplen = MAXALIGN(tuple->t_info & INDEX_SIZE_MASK);
841 : else
842 0 : tuplen = GetMemoryChunkSpace(tuple);
843 :
844 13174490 : tuplesort_puttuple_common(state, &stup,
845 26238980 : base->sortKeys &&
846 15297232 : base->sortKeys->abbrev_converter &&
847 2122742 : !stup.isnull1, tuplen);
848 13174490 : }
849 :
850 : /*
851 : * Collect one BRIN tuple while collecting input data for sort.
852 : */
853 : void
854 42 : tuplesort_putbrintuple(Tuplesortstate *state, BrinTuple *tuple, Size size)
855 : {
856 : SortTuple stup;
857 : BrinSortTuple *bstup;
858 42 : TuplesortPublic *base = TuplesortstateGetPublic(state);
859 42 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
860 : Size tuplen;
861 :
862 : /* allocate space for the whole BRIN sort tuple */
863 42 : bstup = palloc(BRINSORTTUPLE_SIZE(size));
864 :
865 42 : bstup->tuplen = size;
866 42 : memcpy(&bstup->tuple, tuple, size);
867 :
868 42 : stup.tuple = bstup;
869 42 : stup.datum1 = UInt32GetDatum(tuple->bt_blkno);
870 42 : stup.isnull1 = false;
871 :
872 : /* GetMemoryChunkSpace is not supported for bump contexts */
873 42 : if (TupleSortUseBumpTupleCxt(base->sortopt))
874 42 : tuplen = MAXALIGN(BRINSORTTUPLE_SIZE(size));
875 : else
876 0 : tuplen = GetMemoryChunkSpace(bstup);
877 :
878 42 : tuplesort_puttuple_common(state, &stup,
879 42 : base->sortKeys &&
880 42 : base->sortKeys->abbrev_converter &&
881 0 : !stup.isnull1, tuplen);
882 :
883 42 : MemoryContextSwitchTo(oldcontext);
884 42 : }
885 :
886 : void
887 0 : tuplesort_putgintuple(Tuplesortstate *state, GinTuple *tuple, Size size)
888 : {
889 : SortTuple stup;
890 : GinTuple *ctup;
891 0 : TuplesortPublic *base = TuplesortstateGetPublic(state);
892 0 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
893 : Size tuplen;
894 :
895 : /* copy the GinTuple into the right memory context */
896 0 : ctup = palloc(size);
897 0 : memcpy(ctup, tuple, size);
898 :
899 0 : stup.tuple = ctup;
900 0 : stup.datum1 = (Datum) 0;
901 0 : stup.isnull1 = false;
902 :
903 : /* GetMemoryChunkSpace is not supported for bump contexts */
904 0 : if (TupleSortUseBumpTupleCxt(base->sortopt))
905 0 : tuplen = MAXALIGN(size);
906 : else
907 0 : tuplen = GetMemoryChunkSpace(ctup);
908 :
909 0 : tuplesort_puttuple_common(state, &stup,
910 0 : base->sortKeys &&
911 0 : base->sortKeys->abbrev_converter &&
912 0 : !stup.isnull1, tuplen);
913 :
914 0 : MemoryContextSwitchTo(oldcontext);
915 0 : }
916 :
917 : /*
918 : * Accept one Datum while collecting input data for sort.
919 : *
920 : * If the Datum is pass-by-ref type, the value will be copied.
921 : */
922 : void
923 3905606 : tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
924 : {
925 3905606 : TuplesortPublic *base = TuplesortstateGetPublic(state);
926 3905606 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
927 3905606 : TuplesortDatumArg *arg = (TuplesortDatumArg *) base->arg;
928 : SortTuple stup;
929 :
930 : /*
931 : * Pass-by-value types or null values are just stored directly in
932 : * stup.datum1 (and stup.tuple is not used and set to NULL).
933 : *
934 : * Non-null pass-by-reference values need to be copied into memory we
935 : * control, and possibly abbreviated. The copied value is pointed to by
936 : * stup.tuple and is treated as the canonical copy (e.g. to return via
937 : * tuplesort_getdatum or when writing to tape); stup.datum1 gets the
938 : * abbreviated value if abbreviation is happening, otherwise it's
939 : * identical to stup.tuple.
940 : */
941 :
942 3905606 : if (isNull || !base->tuples)
943 : {
944 : /*
945 : * Set datum1 to zeroed representation for NULLs (to be consistent,
946 : * and to support cheap inequality tests for NULL abbreviated keys).
947 : */
948 2168476 : stup.datum1 = !isNull ? val : (Datum) 0;
949 2168476 : stup.isnull1 = isNull;
950 2168476 : stup.tuple = NULL; /* no separate storage */
951 : }
952 : else
953 : {
954 1737130 : stup.isnull1 = false;
955 1737130 : stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
956 1737130 : stup.tuple = DatumGetPointer(stup.datum1);
957 : }
958 :
959 3905606 : tuplesort_puttuple_common(state, &stup,
960 5643546 : base->tuples &&
961 3905606 : base->sortKeys->abbrev_converter && !isNull, 0);
962 :
963 3905606 : MemoryContextSwitchTo(oldcontext);
964 3905606 : }
965 :
966 : /*
967 : * Fetch the next tuple in either forward or back direction.
968 : * If successful, put tuple in slot and return true; else, clear the slot
969 : * and return false.
970 : *
971 : * Caller may optionally be passed back abbreviated value (on true return
972 : * value) when abbreviation was used, which can be used to cheaply avoid
973 : * equality checks that might otherwise be required. Caller can safely make a
974 : * determination of "non-equal tuple" based on simple binary inequality. A
975 : * NULL value in leading attribute will set abbreviated value to zeroed
976 : * representation, which caller may rely on in abbreviated inequality check.
977 : *
978 : * If copy is true, the slot receives a tuple that's been copied into the
979 : * caller's memory context, so that it will stay valid regardless of future
980 : * manipulations of the tuplesort's state (up to and including deleting the
981 : * tuplesort). If copy is false, the slot will just receive a pointer to a
982 : * tuple held within the tuplesort, which is more efficient, but only safe for
983 : * callers that are prepared to have any subsequent manipulation of the
984 : * tuplesort's state invalidate slot contents.
985 : */
986 : bool
987 10963134 : tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy,
988 : TupleTableSlot *slot, Datum *abbrev)
989 : {
990 10963134 : TuplesortPublic *base = TuplesortstateGetPublic(state);
991 10963134 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
992 : SortTuple stup;
993 :
994 10963134 : if (!tuplesort_gettuple_common(state, forward, &stup))
995 121714 : stup.tuple = NULL;
996 :
997 10963134 : MemoryContextSwitchTo(oldcontext);
998 :
999 10963134 : if (stup.tuple)
1000 : {
1001 : /* Record abbreviated key for caller */
1002 10841420 : if (base->sortKeys->abbrev_converter && abbrev)
1003 0 : *abbrev = stup.datum1;
1004 :
1005 10841420 : if (copy)
1006 4556 : stup.tuple = heap_copy_minimal_tuple((MinimalTuple) stup.tuple, 0);
1007 :
1008 10841420 : ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
1009 10841420 : return true;
1010 : }
1011 : else
1012 : {
1013 121714 : ExecClearTuple(slot);
1014 121714 : return false;
1015 : }
1016 : }
1017 :
1018 : /*
1019 : * Fetch the next tuple in either forward or back direction.
1020 : * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
1021 : * context, and must not be freed by caller. Caller may not rely on tuple
1022 : * remaining valid after any further manipulation of tuplesort.
1023 : */
1024 : HeapTuple
1025 547520 : tuplesort_getheaptuple(Tuplesortstate *state, bool forward)
1026 : {
1027 547520 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1028 547520 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1029 : SortTuple stup;
1030 :
1031 547520 : if (!tuplesort_gettuple_common(state, forward, &stup))
1032 116 : stup.tuple = NULL;
1033 :
1034 547520 : MemoryContextSwitchTo(oldcontext);
1035 :
1036 547520 : return stup.tuple;
1037 : }
1038 :
1039 : /*
1040 : * Fetch the next index tuple in either forward or back direction.
1041 : * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
1042 : * context, and must not be freed by caller. Caller may not rely on tuple
1043 : * remaining valid after any further manipulation of tuplesort.
1044 : */
1045 : IndexTuple
1046 13225638 : tuplesort_getindextuple(Tuplesortstate *state, bool forward)
1047 : {
1048 13225638 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1049 13225638 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1050 : SortTuple stup;
1051 :
1052 13225638 : if (!tuplesort_gettuple_common(state, forward, &stup))
1053 51526 : stup.tuple = NULL;
1054 :
1055 13225638 : MemoryContextSwitchTo(oldcontext);
1056 :
1057 13225638 : return (IndexTuple) stup.tuple;
1058 : }
1059 :
1060 : /*
1061 : * Fetch the next BRIN tuple in either forward or back direction.
1062 : * Returns NULL if no more tuples. Returned tuple belongs to tuplesort memory
1063 : * context, and must not be freed by caller. Caller may not rely on tuple
1064 : * remaining valid after any further manipulation of tuplesort.
1065 : */
1066 : BrinTuple *
1067 50 : tuplesort_getbrintuple(Tuplesortstate *state, Size *len, bool forward)
1068 : {
1069 50 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1070 50 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1071 : SortTuple stup;
1072 : BrinSortTuple *btup;
1073 :
1074 50 : if (!tuplesort_gettuple_common(state, forward, &stup))
1075 8 : stup.tuple = NULL;
1076 :
1077 50 : MemoryContextSwitchTo(oldcontext);
1078 :
1079 50 : if (!stup.tuple)
1080 8 : return NULL;
1081 :
1082 42 : btup = (BrinSortTuple *) stup.tuple;
1083 :
1084 42 : *len = btup->tuplen;
1085 :
1086 42 : return &btup->tuple;
1087 : }
1088 :
1089 : GinTuple *
1090 0 : tuplesort_getgintuple(Tuplesortstate *state, Size *len, bool forward)
1091 : {
1092 0 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1093 0 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1094 : SortTuple stup;
1095 : GinTuple *tup;
1096 :
1097 0 : if (!tuplesort_gettuple_common(state, forward, &stup))
1098 0 : stup.tuple = NULL;
1099 :
1100 0 : MemoryContextSwitchTo(oldcontext);
1101 :
1102 0 : if (!stup.tuple)
1103 0 : return NULL;
1104 :
1105 0 : tup = (GinTuple *) stup.tuple;
1106 :
1107 0 : *len = tup->tuplen;
1108 :
1109 0 : return tup;
1110 : }
1111 :
1112 : /*
1113 : * Fetch the next Datum in either forward or back direction.
1114 : * Returns false if no more datums.
1115 : *
1116 : * If the Datum is pass-by-ref type, the returned value is freshly palloc'd
1117 : * in caller's context, and is now owned by the caller (this differs from
1118 : * similar routines for other types of tuplesorts).
1119 : *
1120 : * Caller may optionally be passed back abbreviated value (on true return
1121 : * value) when abbreviation was used, which can be used to cheaply avoid
1122 : * equality checks that might otherwise be required. Caller can safely make a
1123 : * determination of "non-equal tuple" based on simple binary inequality. A
1124 : * NULL value will have a zeroed abbreviated value representation, which caller
1125 : * may rely on in abbreviated inequality check.
1126 : *
1127 : * For byref Datums, if copy is true, *val is set to a copy of the Datum
1128 : * copied into the caller's memory context, so that it will stay valid
1129 : * regardless of future manipulations of the tuplesort's state (up to and
1130 : * including deleting the tuplesort). If copy is false, *val will just be
1131 : * set to a pointer to the Datum held within the tuplesort, which is more
1132 : * efficient, but only safe for callers that are prepared to have any
1133 : * subsequent manipulation of the tuplesort's state invalidate slot contents.
1134 : * For byval Datums, the value of the 'copy' parameter has no effect.
1135 :
1136 : */
1137 : bool
1138 2530316 : tuplesort_getdatum(Tuplesortstate *state, bool forward, bool copy,
1139 : Datum *val, bool *isNull, Datum *abbrev)
1140 : {
1141 2530316 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1142 2530316 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1143 2530316 : TuplesortDatumArg *arg = (TuplesortDatumArg *) base->arg;
1144 : SortTuple stup;
1145 :
1146 2530316 : if (!tuplesort_gettuple_common(state, forward, &stup))
1147 : {
1148 59516 : MemoryContextSwitchTo(oldcontext);
1149 59516 : return false;
1150 : }
1151 :
1152 : /* Ensure we copy into caller's memory context */
1153 2470800 : MemoryContextSwitchTo(oldcontext);
1154 :
1155 : /* Record abbreviated key for caller */
1156 2470800 : if (base->sortKeys->abbrev_converter && abbrev)
1157 55024 : *abbrev = stup.datum1;
1158 :
1159 2470800 : if (stup.isnull1 || !base->tuples)
1160 : {
1161 1333868 : *val = stup.datum1;
1162 1333868 : *isNull = stup.isnull1;
1163 : }
1164 : else
1165 : {
1166 : /* use stup.tuple because stup.datum1 may be an abbreviation */
1167 1136932 : if (copy)
1168 60048 : *val = datumCopy(PointerGetDatum(stup.tuple), false,
1169 : arg->datumTypeLen);
1170 : else
1171 1076884 : *val = PointerGetDatum(stup.tuple);
1172 1136932 : *isNull = false;
1173 : }
1174 :
1175 2470800 : return true;
1176 : }
1177 :
1178 :
1179 : /*
1180 : * Routines specialized for HeapTuple (actually MinimalTuple) case
1181 : */
1182 :
1183 : static void
1184 12 : removeabbrev_heap(Tuplesortstate *state, SortTuple *stups, int count)
1185 : {
1186 : int i;
1187 12 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1188 :
1189 122892 : for (i = 0; i < count; i++)
1190 : {
1191 : HeapTupleData htup;
1192 :
1193 122880 : htup.t_len = ((MinimalTuple) stups[i].tuple)->t_len +
1194 : MINIMAL_TUPLE_OFFSET;
1195 122880 : htup.t_data = (HeapTupleHeader) ((char *) stups[i].tuple -
1196 : MINIMAL_TUPLE_OFFSET);
1197 122880 : stups[i].datum1 = heap_getattr(&htup,
1198 122880 : base->sortKeys[0].ssup_attno,
1199 122880 : (TupleDesc) base->arg,
1200 122880 : &stups[i].isnull1);
1201 : }
1202 12 : }
1203 :
1204 : static int
1205 48065956 : comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1206 : {
1207 48065956 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1208 48065956 : SortSupport sortKey = base->sortKeys;
1209 : int32 compare;
1210 :
1211 :
1212 : /* Compare the leading sort key */
1213 48065956 : compare = ApplySortComparator(a->datum1, a->isnull1,
1214 48065956 : b->datum1, b->isnull1,
1215 : sortKey);
1216 48065956 : if (compare != 0)
1217 18076752 : return compare;
1218 :
1219 : /* Compare additional sort keys */
1220 29989204 : return comparetup_heap_tiebreak(a, b, state);
1221 : }
1222 :
1223 : static int
1224 33113404 : comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1225 : {
1226 33113404 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1227 33113404 : SortSupport sortKey = base->sortKeys;
1228 : HeapTupleData ltup;
1229 : HeapTupleData rtup;
1230 : TupleDesc tupDesc;
1231 : int nkey;
1232 : int32 compare;
1233 : AttrNumber attno;
1234 : Datum datum1,
1235 : datum2;
1236 : bool isnull1,
1237 : isnull2;
1238 :
1239 33113404 : ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
1240 33113404 : ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
1241 33113404 : rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
1242 33113404 : rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
1243 33113404 : tupDesc = (TupleDesc) base->arg;
1244 :
1245 33113404 : if (sortKey->abbrev_converter)
1246 : {
1247 1060596 : attno = sortKey->ssup_attno;
1248 :
1249 1060596 : datum1 = heap_getattr(<up, attno, tupDesc, &isnull1);
1250 1060596 : datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
1251 :
1252 1060596 : compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1253 : datum2, isnull2,
1254 : sortKey);
1255 1060596 : if (compare != 0)
1256 887860 : return compare;
1257 : }
1258 :
1259 32225544 : sortKey++;
1260 34023426 : for (nkey = 1; nkey < base->nKeys; nkey++, sortKey++)
1261 : {
1262 32445398 : attno = sortKey->ssup_attno;
1263 :
1264 32445398 : datum1 = heap_getattr(<up, attno, tupDesc, &isnull1);
1265 32445398 : datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
1266 :
1267 32445398 : compare = ApplySortComparator(datum1, isnull1,
1268 : datum2, isnull2,
1269 : sortKey);
1270 32445398 : if (compare != 0)
1271 30647516 : return compare;
1272 : }
1273 :
1274 1578028 : return 0;
1275 : }
1276 :
1277 : static void
1278 1080450 : writetup_heap(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
1279 : {
1280 1080450 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1281 1080450 : MinimalTuple tuple = (MinimalTuple) stup->tuple;
1282 :
1283 : /* the part of the MinimalTuple we'll write: */
1284 1080450 : char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
1285 1080450 : unsigned int tupbodylen = tuple->t_len - MINIMAL_TUPLE_DATA_OFFSET;
1286 :
1287 : /* total on-disk footprint: */
1288 1080450 : unsigned int tuplen = tupbodylen + sizeof(int);
1289 :
1290 1080450 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1291 1080450 : LogicalTapeWrite(tape, tupbody, tupbodylen);
1292 1080450 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1293 30000 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1294 1080450 : }
1295 :
1296 : static void
1297 978180 : readtup_heap(Tuplesortstate *state, SortTuple *stup,
1298 : LogicalTape *tape, unsigned int len)
1299 : {
1300 978180 : unsigned int tupbodylen = len - sizeof(int);
1301 978180 : unsigned int tuplen = tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
1302 978180 : MinimalTuple tuple = (MinimalTuple) tuplesort_readtup_alloc(state, tuplen);
1303 978180 : char *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
1304 978180 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1305 : HeapTupleData htup;
1306 :
1307 : /* read in the tuple proper */
1308 978180 : tuple->t_len = tuplen;
1309 978180 : LogicalTapeReadExact(tape, tupbody, tupbodylen);
1310 978180 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1311 47784 : LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1312 978180 : stup->tuple = tuple;
1313 : /* set up first-column key value */
1314 978180 : htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
1315 978180 : htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
1316 1956360 : stup->datum1 = heap_getattr(&htup,
1317 978180 : base->sortKeys[0].ssup_attno,
1318 978180 : (TupleDesc) base->arg,
1319 : &stup->isnull1);
1320 978180 : }
1321 :
1322 : /*
1323 : * Routines specialized for the CLUSTER case (HeapTuple data, with
1324 : * comparisons per a btree index definition)
1325 : */
1326 :
1327 : static void
1328 12 : removeabbrev_cluster(Tuplesortstate *state, SortTuple *stups, int count)
1329 : {
1330 : int i;
1331 12 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1332 12 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
1333 :
1334 122892 : for (i = 0; i < count; i++)
1335 : {
1336 : HeapTuple tup;
1337 :
1338 122880 : tup = (HeapTuple) stups[i].tuple;
1339 122880 : stups[i].datum1 = heap_getattr(tup,
1340 122880 : arg->indexInfo->ii_IndexAttrNumbers[0],
1341 : arg->tupDesc,
1342 122880 : &stups[i].isnull1);
1343 : }
1344 12 : }
1345 :
1346 : static int
1347 5996208 : comparetup_cluster(const SortTuple *a, const SortTuple *b,
1348 : Tuplesortstate *state)
1349 : {
1350 5996208 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1351 5996208 : SortSupport sortKey = base->sortKeys;
1352 : int32 compare;
1353 :
1354 : /* Compare the leading sort key, if it's simple */
1355 5996208 : if (base->haveDatum1)
1356 : {
1357 5984418 : compare = ApplySortComparator(a->datum1, a->isnull1,
1358 5984418 : b->datum1, b->isnull1,
1359 : sortKey);
1360 5984418 : if (compare != 0)
1361 5843284 : return compare;
1362 : }
1363 :
1364 152924 : return comparetup_cluster_tiebreak(a, b, state);
1365 : }
1366 :
1367 : static int
1368 587166 : comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b,
1369 : Tuplesortstate *state)
1370 : {
1371 587166 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1372 587166 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
1373 587166 : SortSupport sortKey = base->sortKeys;
1374 : HeapTuple ltup;
1375 : HeapTuple rtup;
1376 : TupleDesc tupDesc;
1377 : int nkey;
1378 587166 : int32 compare = 0;
1379 : Datum datum1,
1380 : datum2;
1381 : bool isnull1,
1382 : isnull2;
1383 :
1384 587166 : ltup = (HeapTuple) a->tuple;
1385 587166 : rtup = (HeapTuple) b->tuple;
1386 587166 : tupDesc = arg->tupDesc;
1387 :
1388 : /* Compare the leading sort key, if it's simple */
1389 587166 : if (base->haveDatum1)
1390 : {
1391 575376 : if (sortKey->abbrev_converter)
1392 : {
1393 144452 : AttrNumber leading = arg->indexInfo->ii_IndexAttrNumbers[0];
1394 :
1395 144452 : datum1 = heap_getattr(ltup, leading, tupDesc, &isnull1);
1396 144452 : datum2 = heap_getattr(rtup, leading, tupDesc, &isnull2);
1397 :
1398 144452 : compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1399 : datum2, isnull2,
1400 : sortKey);
1401 : }
1402 575376 : if (compare != 0 || base->nKeys == 1)
1403 147816 : return compare;
1404 : /* Compare additional columns the hard way */
1405 427560 : sortKey++;
1406 427560 : nkey = 1;
1407 : }
1408 : else
1409 : {
1410 : /* Must compare all keys the hard way */
1411 11790 : nkey = 0;
1412 : }
1413 :
1414 439350 : if (arg->indexInfo->ii_Expressions == NULL)
1415 : {
1416 : /* If not expression index, just compare the proper heap attrs */
1417 :
1418 593520 : for (; nkey < base->nKeys; nkey++, sortKey++)
1419 : {
1420 593520 : AttrNumber attno = arg->indexInfo->ii_IndexAttrNumbers[nkey];
1421 :
1422 593520 : datum1 = heap_getattr(ltup, attno, tupDesc, &isnull1);
1423 593520 : datum2 = heap_getattr(rtup, attno, tupDesc, &isnull2);
1424 :
1425 593520 : compare = ApplySortComparator(datum1, isnull1,
1426 : datum2, isnull2,
1427 : sortKey);
1428 593520 : if (compare != 0)
1429 427560 : return compare;
1430 : }
1431 : }
1432 : else
1433 : {
1434 : /*
1435 : * In the expression index case, compute the whole index tuple and
1436 : * then compare values. It would perhaps be faster to compute only as
1437 : * many columns as we need to compare, but that would require
1438 : * duplicating all the logic in FormIndexDatum.
1439 : */
1440 : Datum l_index_values[INDEX_MAX_KEYS];
1441 : bool l_index_isnull[INDEX_MAX_KEYS];
1442 : Datum r_index_values[INDEX_MAX_KEYS];
1443 : bool r_index_isnull[INDEX_MAX_KEYS];
1444 : TupleTableSlot *ecxt_scantuple;
1445 :
1446 : /* Reset context each time to prevent memory leakage */
1447 11790 : ResetPerTupleExprContext(arg->estate);
1448 :
1449 11790 : ecxt_scantuple = GetPerTupleExprContext(arg->estate)->ecxt_scantuple;
1450 :
1451 11790 : ExecStoreHeapTuple(ltup, ecxt_scantuple, false);
1452 11790 : FormIndexDatum(arg->indexInfo, ecxt_scantuple, arg->estate,
1453 : l_index_values, l_index_isnull);
1454 :
1455 11790 : ExecStoreHeapTuple(rtup, ecxt_scantuple, false);
1456 11790 : FormIndexDatum(arg->indexInfo, ecxt_scantuple, arg->estate,
1457 : r_index_values, r_index_isnull);
1458 :
1459 12714 : for (; nkey < base->nKeys; nkey++, sortKey++)
1460 : {
1461 12714 : compare = ApplySortComparator(l_index_values[nkey],
1462 12714 : l_index_isnull[nkey],
1463 : r_index_values[nkey],
1464 12714 : r_index_isnull[nkey],
1465 : sortKey);
1466 12714 : if (compare != 0)
1467 11790 : return compare;
1468 : }
1469 : }
1470 :
1471 0 : return 0;
1472 : }
1473 :
1474 : static void
1475 60000 : writetup_cluster(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
1476 : {
1477 60000 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1478 60000 : HeapTuple tuple = (HeapTuple) stup->tuple;
1479 60000 : unsigned int tuplen = tuple->t_len + sizeof(ItemPointerData) + sizeof(int);
1480 :
1481 : /* We need to store t_self, but not other fields of HeapTupleData */
1482 60000 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1483 60000 : LogicalTapeWrite(tape, &tuple->t_self, sizeof(ItemPointerData));
1484 60000 : LogicalTapeWrite(tape, tuple->t_data, tuple->t_len);
1485 60000 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1486 0 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1487 60000 : }
1488 :
1489 : static void
1490 60000 : readtup_cluster(Tuplesortstate *state, SortTuple *stup,
1491 : LogicalTape *tape, unsigned int tuplen)
1492 : {
1493 60000 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1494 60000 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
1495 60000 : unsigned int t_len = tuplen - sizeof(ItemPointerData) - sizeof(int);
1496 60000 : HeapTuple tuple = (HeapTuple) tuplesort_readtup_alloc(state,
1497 : t_len + HEAPTUPLESIZE);
1498 :
1499 : /* Reconstruct the HeapTupleData header */
1500 60000 : tuple->t_data = (HeapTupleHeader) ((char *) tuple + HEAPTUPLESIZE);
1501 60000 : tuple->t_len = t_len;
1502 60000 : LogicalTapeReadExact(tape, &tuple->t_self, sizeof(ItemPointerData));
1503 : /* We don't currently bother to reconstruct t_tableOid */
1504 60000 : tuple->t_tableOid = InvalidOid;
1505 : /* Read in the tuple body */
1506 60000 : LogicalTapeReadExact(tape, tuple->t_data, tuple->t_len);
1507 60000 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1508 0 : LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1509 60000 : stup->tuple = tuple;
1510 : /* set up first-column key value, if it's a simple column */
1511 60000 : if (base->haveDatum1)
1512 60000 : stup->datum1 = heap_getattr(tuple,
1513 60000 : arg->indexInfo->ii_IndexAttrNumbers[0],
1514 : arg->tupDesc,
1515 : &stup->isnull1);
1516 60000 : }
1517 :
1518 : static void
1519 116 : freestate_cluster(Tuplesortstate *state)
1520 : {
1521 116 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1522 116 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
1523 :
1524 : /* Free any execution state created for CLUSTER case */
1525 116 : if (arg->estate != NULL)
1526 : {
1527 24 : ExprContext *econtext = GetPerTupleExprContext(arg->estate);
1528 :
1529 24 : ExecDropSingleTupleTableSlot(econtext->ecxt_scantuple);
1530 24 : FreeExecutorState(arg->estate);
1531 : }
1532 116 : }
1533 :
1534 : /*
1535 : * Routines specialized for IndexTuple case
1536 : *
1537 : * The btree and hash cases require separate comparison functions, but the
1538 : * IndexTuple representation is the same so the copy/write/read support
1539 : * functions can be shared.
1540 : */
1541 :
1542 : static void
1543 60 : removeabbrev_index(Tuplesortstate *state, SortTuple *stups, int count)
1544 : {
1545 60 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1546 60 : TuplesortIndexArg *arg = (TuplesortIndexArg *) base->arg;
1547 : int i;
1548 :
1549 614460 : for (i = 0; i < count; i++)
1550 : {
1551 : IndexTuple tuple;
1552 :
1553 614400 : tuple = stups[i].tuple;
1554 614400 : stups[i].datum1 = index_getattr(tuple,
1555 : 1,
1556 614400 : RelationGetDescr(arg->indexRel),
1557 614400 : &stups[i].isnull1);
1558 : }
1559 60 : }
1560 :
1561 : static int
1562 58234100 : comparetup_index_btree(const SortTuple *a, const SortTuple *b,
1563 : Tuplesortstate *state)
1564 : {
1565 : /*
1566 : * This is similar to comparetup_heap(), but expects index tuples. There
1567 : * is also special handling for enforcing uniqueness, and special
1568 : * treatment for equal keys at the end.
1569 : */
1570 58234100 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1571 58234100 : SortSupport sortKey = base->sortKeys;
1572 : int32 compare;
1573 :
1574 : /* Compare the leading sort key */
1575 58234100 : compare = ApplySortComparator(a->datum1, a->isnull1,
1576 58234100 : b->datum1, b->isnull1,
1577 : sortKey);
1578 58234100 : if (compare != 0)
1579 52682202 : return compare;
1580 :
1581 : /* Compare additional sort keys */
1582 5551898 : return comparetup_index_btree_tiebreak(a, b, state);
1583 : }
1584 :
1585 : static int
1586 17854900 : comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
1587 : Tuplesortstate *state)
1588 : {
1589 17854900 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1590 17854900 : TuplesortIndexBTreeArg *arg = (TuplesortIndexBTreeArg *) base->arg;
1591 17854900 : SortSupport sortKey = base->sortKeys;
1592 : IndexTuple tuple1;
1593 : IndexTuple tuple2;
1594 : int keysz;
1595 : TupleDesc tupDes;
1596 17854900 : bool equal_hasnull = false;
1597 : int nkey;
1598 : int32 compare;
1599 : Datum datum1,
1600 : datum2;
1601 : bool isnull1,
1602 : isnull2;
1603 :
1604 17854900 : tuple1 = (IndexTuple) a->tuple;
1605 17854900 : tuple2 = (IndexTuple) b->tuple;
1606 17854900 : keysz = base->nKeys;
1607 17854900 : tupDes = RelationGetDescr(arg->index.indexRel);
1608 :
1609 17854900 : if (sortKey->abbrev_converter)
1610 : {
1611 863548 : datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
1612 863548 : datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
1613 :
1614 863548 : compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1615 : datum2, isnull2,
1616 : sortKey);
1617 863548 : if (compare != 0)
1618 804472 : return compare;
1619 : }
1620 :
1621 : /* they are equal, so we only need to examine one null flag */
1622 17050428 : if (a->isnull1)
1623 15038 : equal_hasnull = true;
1624 :
1625 17050428 : sortKey++;
1626 19632536 : for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
1627 : {
1628 7394008 : datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
1629 7394008 : datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
1630 :
1631 7394008 : compare = ApplySortComparator(datum1, isnull1,
1632 : datum2, isnull2,
1633 : sortKey);
1634 7394008 : if (compare != 0)
1635 4811900 : return compare; /* done when we find unequal attributes */
1636 :
1637 : /* they are equal, so we only need to examine one null flag */
1638 2582108 : if (isnull1)
1639 25992 : equal_hasnull = true;
1640 : }
1641 :
1642 : /*
1643 : * If btree has asked us to enforce uniqueness, complain if two equal
1644 : * tuples are detected (unless there was at least one NULL field and NULLS
1645 : * NOT DISTINCT was not set).
1646 : *
1647 : * It is sufficient to make the test here, because if two tuples are equal
1648 : * they *must* get compared at some stage of the sort --- otherwise the
1649 : * sort algorithm wouldn't have checked whether one must appear before the
1650 : * other.
1651 : */
1652 12238528 : if (arg->enforceUnique && !(!arg->uniqueNullsNotDistinct && equal_hasnull))
1653 : {
1654 : Datum values[INDEX_MAX_KEYS];
1655 : bool isnull[INDEX_MAX_KEYS];
1656 : char *key_desc;
1657 :
1658 : /*
1659 : * Some rather brain-dead implementations of qsort (such as the one in
1660 : * QNX 4) will sometimes call the comparison routine to compare a
1661 : * value to itself, but we always use our own implementation, which
1662 : * does not.
1663 : */
1664 : Assert(tuple1 != tuple2);
1665 :
1666 84 : index_deform_tuple(tuple1, tupDes, values, isnull);
1667 :
1668 84 : key_desc = BuildIndexValueDescription(arg->index.indexRel, values, isnull);
1669 :
1670 84 : ereport(ERROR,
1671 : (errcode(ERRCODE_UNIQUE_VIOLATION),
1672 : errmsg("could not create unique index \"%s\"",
1673 : RelationGetRelationName(arg->index.indexRel)),
1674 : key_desc ? errdetail("Key %s is duplicated.", key_desc) :
1675 : errdetail("Duplicate keys exist."),
1676 : errtableconstraint(arg->index.heapRel,
1677 : RelationGetRelationName(arg->index.indexRel))));
1678 : }
1679 :
1680 : /*
1681 : * If key values are equal, we sort on ItemPointer. This is required for
1682 : * btree indexes, since heap TID is treated as an implicit last key
1683 : * attribute in order to ensure that all keys in the index are physically
1684 : * unique.
1685 : */
1686 : {
1687 12238444 : BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
1688 12238444 : BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
1689 :
1690 12238444 : if (blk1 != blk2)
1691 11232252 : return (blk1 < blk2) ? -1 : 1;
1692 : }
1693 : {
1694 1006192 : OffsetNumber pos1 = ItemPointerGetOffsetNumber(&tuple1->t_tid);
1695 1006192 : OffsetNumber pos2 = ItemPointerGetOffsetNumber(&tuple2->t_tid);
1696 :
1697 1006192 : if (pos1 != pos2)
1698 1006192 : return (pos1 < pos2) ? -1 : 1;
1699 : }
1700 :
1701 : /* ItemPointer values should never be equal */
1702 : Assert(false);
1703 :
1704 0 : return 0;
1705 : }
1706 :
1707 : static int
1708 1600854 : comparetup_index_hash(const SortTuple *a, const SortTuple *b,
1709 : Tuplesortstate *state)
1710 : {
1711 : Bucket bucket1;
1712 : Bucket bucket2;
1713 : uint32 hash1;
1714 : uint32 hash2;
1715 : IndexTuple tuple1;
1716 : IndexTuple tuple2;
1717 1600854 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1718 1600854 : TuplesortIndexHashArg *arg = (TuplesortIndexHashArg *) base->arg;
1719 :
1720 : /*
1721 : * Fetch hash keys and mask off bits we don't want to sort by, so that the
1722 : * initial sort is just on the bucket number. We know that the first
1723 : * column of the index tuple is the hash key.
1724 : */
1725 : Assert(!a->isnull1);
1726 1600854 : bucket1 = _hash_hashkey2bucket(DatumGetUInt32(a->datum1),
1727 : arg->max_buckets, arg->high_mask,
1728 : arg->low_mask);
1729 : Assert(!b->isnull1);
1730 1600854 : bucket2 = _hash_hashkey2bucket(DatumGetUInt32(b->datum1),
1731 : arg->max_buckets, arg->high_mask,
1732 : arg->low_mask);
1733 1600854 : if (bucket1 > bucket2)
1734 504890 : return 1;
1735 1095964 : else if (bucket1 < bucket2)
1736 481858 : return -1;
1737 :
1738 : /*
1739 : * If bucket values are equal, sort by hash values. This allows us to
1740 : * insert directly onto bucket/overflow pages, where the index tuples are
1741 : * stored in hash order to allow fast binary search within each page.
1742 : */
1743 614106 : hash1 = DatumGetUInt32(a->datum1);
1744 614106 : hash2 = DatumGetUInt32(b->datum1);
1745 614106 : if (hash1 > hash2)
1746 195788 : return 1;
1747 418318 : else if (hash1 < hash2)
1748 172926 : return -1;
1749 :
1750 : /*
1751 : * If hash values are equal, we sort on ItemPointer. This does not affect
1752 : * validity of the finished index, but it may be useful to have index
1753 : * scans in physical order.
1754 : */
1755 245392 : tuple1 = (IndexTuple) a->tuple;
1756 245392 : tuple2 = (IndexTuple) b->tuple;
1757 :
1758 : {
1759 245392 : BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
1760 245392 : BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
1761 :
1762 245392 : if (blk1 != blk2)
1763 213472 : return (blk1 < blk2) ? -1 : 1;
1764 : }
1765 : {
1766 31920 : OffsetNumber pos1 = ItemPointerGetOffsetNumber(&tuple1->t_tid);
1767 31920 : OffsetNumber pos2 = ItemPointerGetOffsetNumber(&tuple2->t_tid);
1768 :
1769 31920 : if (pos1 != pos2)
1770 31920 : return (pos1 < pos2) ? -1 : 1;
1771 : }
1772 :
1773 : /* ItemPointer values should never be equal */
1774 : Assert(false);
1775 :
1776 0 : return 0;
1777 : }
1778 :
1779 : /*
1780 : * Sorting for hash indexes only uses one sort key, so this shouldn't ever be
1781 : * called. It's only here for consistency.
1782 : */
1783 : static int
1784 0 : comparetup_index_hash_tiebreak(const SortTuple *a, const SortTuple *b,
1785 : Tuplesortstate *state)
1786 : {
1787 : Assert(false);
1788 :
1789 0 : return 0;
1790 : }
1791 :
1792 : static void
1793 3704014 : writetup_index(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
1794 : {
1795 3704014 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1796 3704014 : IndexTuple tuple = (IndexTuple) stup->tuple;
1797 : unsigned int tuplen;
1798 :
1799 3704014 : tuplen = IndexTupleSize(tuple) + sizeof(tuplen);
1800 3704014 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1801 3704014 : LogicalTapeWrite(tape, tuple, IndexTupleSize(tuple));
1802 3704014 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1803 0 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1804 3704014 : }
1805 :
1806 : static void
1807 3704014 : readtup_index(Tuplesortstate *state, SortTuple *stup,
1808 : LogicalTape *tape, unsigned int len)
1809 : {
1810 3704014 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1811 3704014 : TuplesortIndexArg *arg = (TuplesortIndexArg *) base->arg;
1812 3704014 : unsigned int tuplen = len - sizeof(unsigned int);
1813 3704014 : IndexTuple tuple = (IndexTuple) tuplesort_readtup_alloc(state, tuplen);
1814 :
1815 3704014 : LogicalTapeReadExact(tape, tuple, tuplen);
1816 3704014 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1817 0 : LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1818 3704014 : stup->tuple = tuple;
1819 : /* set up first-column key value */
1820 7408028 : stup->datum1 = index_getattr(tuple,
1821 : 1,
1822 3704014 : RelationGetDescr(arg->indexRel),
1823 : &stup->isnull1);
1824 3704014 : }
1825 :
1826 : /*
1827 : * Routines specialized for BrinTuple case
1828 : */
1829 :
1830 : static void
1831 0 : removeabbrev_index_brin(Tuplesortstate *state, SortTuple *stups, int count)
1832 : {
1833 : int i;
1834 :
1835 0 : for (i = 0; i < count; i++)
1836 : {
1837 : BrinSortTuple *tuple;
1838 :
1839 0 : tuple = stups[i].tuple;
1840 0 : stups[i].datum1 = UInt32GetDatum(tuple->tuple.bt_blkno);
1841 : }
1842 0 : }
1843 :
1844 : static int
1845 74 : comparetup_index_brin(const SortTuple *a, const SortTuple *b,
1846 : Tuplesortstate *state)
1847 : {
1848 : Assert(TuplesortstateGetPublic(state)->haveDatum1);
1849 :
1850 74 : if (DatumGetUInt32(a->datum1) > DatumGetUInt32(b->datum1))
1851 2 : return 1;
1852 :
1853 72 : if (DatumGetUInt32(a->datum1) < DatumGetUInt32(b->datum1))
1854 70 : return -1;
1855 :
1856 : /* silence compilers */
1857 2 : return 0;
1858 : }
1859 :
1860 : static void
1861 42 : writetup_index_brin(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
1862 : {
1863 42 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1864 42 : BrinSortTuple *tuple = (BrinSortTuple *) stup->tuple;
1865 42 : unsigned int tuplen = tuple->tuplen;
1866 :
1867 42 : tuplen = tuplen + sizeof(tuplen);
1868 42 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1869 42 : LogicalTapeWrite(tape, &tuple->tuple, tuple->tuplen);
1870 42 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1871 0 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1872 42 : }
1873 :
1874 : static void
1875 42 : readtup_index_brin(Tuplesortstate *state, SortTuple *stup,
1876 : LogicalTape *tape, unsigned int len)
1877 : {
1878 : BrinSortTuple *tuple;
1879 42 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1880 42 : unsigned int tuplen = len - sizeof(unsigned int);
1881 :
1882 : /*
1883 : * Allocate space for the BRIN sort tuple, which is BrinTuple with an
1884 : * extra length field.
1885 : */
1886 42 : tuple = (BrinSortTuple *) tuplesort_readtup_alloc(state,
1887 : BRINSORTTUPLE_SIZE(tuplen));
1888 :
1889 42 : tuple->tuplen = tuplen;
1890 :
1891 42 : LogicalTapeReadExact(tape, &tuple->tuple, tuplen);
1892 42 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1893 0 : LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1894 42 : stup->tuple = tuple;
1895 :
1896 : /* set up first-column key value, which is block number */
1897 42 : stup->datum1 = UInt32GetDatum(tuple->tuple.bt_blkno);
1898 42 : }
1899 :
1900 : /*
1901 : * Routines specialized for GIN case
1902 : */
1903 :
1904 : static void
1905 0 : removeabbrev_index_gin(Tuplesortstate *state, SortTuple *stups, int count)
1906 : {
1907 : Assert(false);
1908 0 : elog(ERROR, "removeabbrev_index_gin not implemented");
1909 : }
1910 :
1911 : static int
1912 0 : comparetup_index_gin(const SortTuple *a, const SortTuple *b,
1913 : Tuplesortstate *state)
1914 : {
1915 0 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1916 :
1917 : Assert(!TuplesortstateGetPublic(state)->haveDatum1);
1918 :
1919 0 : return _gin_compare_tuples((GinTuple *) a->tuple,
1920 0 : (GinTuple *) b->tuple,
1921 : base->sortKeys);
1922 : }
1923 :
1924 : static void
1925 0 : writetup_index_gin(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
1926 : {
1927 0 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1928 0 : GinTuple *tuple = (GinTuple *) stup->tuple;
1929 0 : unsigned int tuplen = tuple->tuplen;
1930 :
1931 0 : tuplen = tuplen + sizeof(tuplen);
1932 0 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1933 0 : LogicalTapeWrite(tape, tuple, tuple->tuplen);
1934 0 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1935 0 : LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
1936 0 : }
1937 :
1938 : static void
1939 0 : readtup_index_gin(Tuplesortstate *state, SortTuple *stup,
1940 : LogicalTape *tape, unsigned int len)
1941 : {
1942 : GinTuple *tuple;
1943 0 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1944 0 : unsigned int tuplen = len - sizeof(unsigned int);
1945 :
1946 : /*
1947 : * Allocate space for the GIN sort tuple, which already has the proper
1948 : * length included in the header.
1949 : */
1950 0 : tuple = (GinTuple *) tuplesort_readtup_alloc(state, tuplen);
1951 :
1952 0 : tuple->tuplen = tuplen;
1953 :
1954 0 : LogicalTapeReadExact(tape, tuple, tuplen);
1955 0 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
1956 0 : LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
1957 0 : stup->tuple = (void *) tuple;
1958 :
1959 : /* no abbreviations (FIXME maybe use attrnum for this?) */
1960 0 : stup->datum1 = (Datum) 0;
1961 0 : }
1962 :
1963 : /*
1964 : * Routines specialized for DatumTuple case
1965 : */
1966 :
1967 : static void
1968 12 : removeabbrev_datum(Tuplesortstate *state, SortTuple *stups, int count)
1969 : {
1970 : int i;
1971 :
1972 122892 : for (i = 0; i < count; i++)
1973 122880 : stups[i].datum1 = PointerGetDatum(stups[i].tuple);
1974 12 : }
1975 :
1976 : static int
1977 6791994 : comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1978 : {
1979 6791994 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1980 : int compare;
1981 :
1982 6791994 : compare = ApplySortComparator(a->datum1, a->isnull1,
1983 6791994 : b->datum1, b->isnull1,
1984 : base->sortKeys);
1985 6791994 : if (compare != 0)
1986 6591728 : return compare;
1987 :
1988 200266 : return comparetup_datum_tiebreak(a, b, state);
1989 : }
1990 :
1991 : static int
1992 2698216 : comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1993 : {
1994 2698216 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1995 2698216 : int32 compare = 0;
1996 :
1997 : /* if we have abbreviations, then "tuple" has the original value */
1998 2698216 : if (base->sortKeys->abbrev_converter)
1999 2497964 : compare = ApplySortAbbrevFullComparator(PointerGetDatum(a->tuple), a->isnull1,
2000 2497964 : PointerGetDatum(b->tuple), b->isnull1,
2001 : base->sortKeys);
2002 :
2003 2698216 : return compare;
2004 : }
2005 :
2006 : static void
2007 1080522 : writetup_datum(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
2008 : {
2009 1080522 : TuplesortPublic *base = TuplesortstateGetPublic(state);
2010 1080522 : TuplesortDatumArg *arg = (TuplesortDatumArg *) base->arg;
2011 : void *waddr;
2012 : unsigned int tuplen;
2013 : unsigned int writtenlen;
2014 :
2015 1080522 : if (stup->isnull1)
2016 : {
2017 66 : waddr = NULL;
2018 66 : tuplen = 0;
2019 : }
2020 1080456 : else if (!base->tuples)
2021 : {
2022 300132 : waddr = &stup->datum1;
2023 300132 : tuplen = sizeof(Datum);
2024 : }
2025 : else
2026 : {
2027 780324 : waddr = stup->tuple;
2028 780324 : tuplen = datumGetSize(PointerGetDatum(stup->tuple), false, arg->datumTypeLen);
2029 : Assert(tuplen != 0);
2030 : }
2031 :
2032 1080522 : writtenlen = tuplen + sizeof(unsigned int);
2033 :
2034 1080522 : LogicalTapeWrite(tape, &writtenlen, sizeof(writtenlen));
2035 1080522 : LogicalTapeWrite(tape, waddr, tuplen);
2036 1080522 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
2037 480264 : LogicalTapeWrite(tape, &writtenlen, sizeof(writtenlen));
2038 1080522 : }
2039 :
2040 : static void
2041 960552 : readtup_datum(Tuplesortstate *state, SortTuple *stup,
2042 : LogicalTape *tape, unsigned int len)
2043 : {
2044 960552 : TuplesortPublic *base = TuplesortstateGetPublic(state);
2045 960552 : unsigned int tuplen = len - sizeof(unsigned int);
2046 :
2047 960552 : if (tuplen == 0)
2048 : {
2049 : /* it's NULL */
2050 90 : stup->datum1 = (Datum) 0;
2051 90 : stup->isnull1 = true;
2052 90 : stup->tuple = NULL;
2053 : }
2054 960462 : else if (!base->tuples)
2055 : {
2056 : Assert(tuplen == sizeof(Datum));
2057 300138 : LogicalTapeReadExact(tape, &stup->datum1, tuplen);
2058 300138 : stup->isnull1 = false;
2059 300138 : stup->tuple = NULL;
2060 : }
2061 : else
2062 : {
2063 660324 : void *raddr = tuplesort_readtup_alloc(state, tuplen);
2064 :
2065 660324 : LogicalTapeReadExact(tape, raddr, tuplen);
2066 660324 : stup->datum1 = PointerGetDatum(raddr);
2067 660324 : stup->isnull1 = false;
2068 660324 : stup->tuple = raddr;
2069 : }
2070 :
2071 960552 : if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
2072 480312 : LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
2073 960552 : }
|
