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