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