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 139946 : 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 139946 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
185 : sortopt);
186 139946 : TuplesortPublic *base = TuplesortstateGetPublic(state);
187 : MemoryContext oldcontext;
188 : int i;
189 :
190 139946 : oldcontext = MemoryContextSwitchTo(base->maincontext);
191 :
192 : Assert(nkeys > 0);
193 :
194 139946 : 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 139946 : 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 139946 : base->removeabbrev = removeabbrev_heap;
209 139946 : base->comparetup = comparetup_heap;
210 139946 : base->comparetup_tiebreak = comparetup_heap_tiebreak;
211 139946 : base->writetup = writetup_heap;
212 139946 : base->readtup = readtup_heap;
213 139946 : base->haveDatum1 = true;
214 139946 : base->arg = tupDesc; /* assume we need not copy tupDesc */
215 :
216 : /* Prepare SortSupport data for each column */
217 139946 : base->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
218 :
219 336566 : for (i = 0; i < nkeys; i++)
220 : {
221 196632 : SortSupport sortKey = base->sortKeys + i;
222 :
223 : Assert(attNums[i] != 0);
224 : Assert(sortOperators[i] != 0);
225 :
226 196632 : sortKey->ssup_cxt = CurrentMemoryContext;
227 196632 : sortKey->ssup_collation = sortCollations[i];
228 196632 : sortKey->ssup_nulls_first = nullsFirstFlags[i];
229 196632 : sortKey->ssup_attno = attNums[i];
230 : /* Convey if abbreviation optimization is applicable in principle */
231 196632 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
232 :
233 196632 : 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 139934 : if (nkeys == 1 && !base->sortKeys->abbrev_converter)
243 69926 : base->onlyKey = base->sortKeys;
244 :
245 139934 : MemoryContextSwitchTo(oldcontext);
246 :
247 139934 : return state;
248 : }
249 :
250 : Tuplesortstate *
251 112 : tuplesort_begin_cluster(TupleDesc tupDesc,
252 : Relation indexRel,
253 : int workMem,
254 : SortCoordinate coordinate, int sortopt)
255 : {
256 112 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
257 : sortopt);
258 112 : 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 112 : oldcontext = MemoryContextSwitchTo(base->maincontext);
267 112 : arg = (TuplesortClusterArg *) palloc0(sizeof(TuplesortClusterArg));
268 :
269 112 : 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 112 : 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 112 : base->removeabbrev = removeabbrev_cluster;
285 112 : base->comparetup = comparetup_cluster;
286 112 : base->comparetup_tiebreak = comparetup_cluster_tiebreak;
287 112 : base->writetup = writetup_cluster;
288 112 : base->readtup = readtup_cluster;
289 112 : base->freestate = freestate_cluster;
290 112 : base->arg = arg;
291 :
292 112 : 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 112 : if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
299 24 : base->haveDatum1 = false;
300 : else
301 88 : base->haveDatum1 = true;
302 :
303 112 : arg->tupDesc = tupDesc; /* assume we need not copy tupDesc */
304 :
305 112 : indexScanKey = _bt_mkscankey(indexRel, NULL);
306 :
307 112 : 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 112 : base->sortKeys = (SortSupport) palloc0(base->nKeys *
326 : sizeof(SortSupportData));
327 :
328 248 : for (i = 0; i < base->nKeys; i++)
329 : {
330 136 : SortSupport sortKey = base->sortKeys + i;
331 136 : ScanKey scanKey = indexScanKey->scankeys + i;
332 : bool reverse;
333 :
334 136 : sortKey->ssup_cxt = CurrentMemoryContext;
335 136 : sortKey->ssup_collation = scanKey->sk_collation;
336 136 : sortKey->ssup_nulls_first =
337 136 : (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
338 136 : sortKey->ssup_attno = scanKey->sk_attno;
339 : /* Convey if abbreviation optimization is applicable in principle */
340 136 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
341 :
342 : Assert(sortKey->ssup_attno != 0);
343 :
344 136 : reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
345 :
346 136 : PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
347 : }
348 :
349 112 : pfree(indexScanKey);
350 :
351 112 : MemoryContextSwitchTo(oldcontext);
352 :
353 112 : return state;
354 : }
355 :
356 : Tuplesortstate *
357 94252 : 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 94252 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
366 : sortopt);
367 94252 : TuplesortPublic *base = TuplesortstateGetPublic(state);
368 : BTScanInsert indexScanKey;
369 : TuplesortIndexBTreeArg *arg;
370 : MemoryContext oldcontext;
371 : int i;
372 :
373 94252 : oldcontext = MemoryContextSwitchTo(base->maincontext);
374 94252 : arg = (TuplesortIndexBTreeArg *) palloc(sizeof(TuplesortIndexBTreeArg));
375 :
376 94252 : 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 94252 : 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 94252 : base->removeabbrev = removeabbrev_index;
392 94252 : base->comparetup = comparetup_index_btree;
393 94252 : base->comparetup_tiebreak = comparetup_index_btree_tiebreak;
394 94252 : base->writetup = writetup_index;
395 94252 : base->readtup = readtup_index;
396 94252 : base->haveDatum1 = true;
397 94252 : base->arg = arg;
398 :
399 94252 : arg->index.heapRel = heapRel;
400 94252 : arg->index.indexRel = indexRel;
401 94252 : arg->enforceUnique = enforceUnique;
402 94252 : arg->uniqueNullsNotDistinct = uniqueNullsNotDistinct;
403 :
404 94252 : indexScanKey = _bt_mkscankey(indexRel, NULL);
405 :
406 : /* Prepare SortSupport data for each column */
407 94252 : base->sortKeys = (SortSupport) palloc0(base->nKeys *
408 : sizeof(SortSupportData));
409 :
410 250596 : for (i = 0; i < base->nKeys; i++)
411 : {
412 156344 : SortSupport sortKey = base->sortKeys + i;
413 156344 : ScanKey scanKey = indexScanKey->scankeys + i;
414 : bool reverse;
415 :
416 156344 : sortKey->ssup_cxt = CurrentMemoryContext;
417 156344 : sortKey->ssup_collation = scanKey->sk_collation;
418 156344 : sortKey->ssup_nulls_first =
419 156344 : (scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
420 156344 : sortKey->ssup_attno = scanKey->sk_attno;
421 : /* Convey if abbreviation optimization is applicable in principle */
422 156344 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
423 :
424 : Assert(sortKey->ssup_attno != 0);
425 :
426 156344 : reverse = (scanKey->sk_flags & SK_BT_DESC) != 0;
427 :
428 156344 : PrepareSortSupportFromIndexRel(indexRel, reverse, sortKey);
429 : }
430 :
431 94252 : pfree(indexScanKey);
432 :
433 94252 : MemoryContextSwitchTo(oldcontext);
434 :
435 94252 : 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 802 : tuplesort_begin_index_gist(Relation heapRel,
491 : Relation indexRel,
492 : int workMem,
493 : SortCoordinate coordinate,
494 : int sortopt)
495 : {
496 802 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
497 : sortopt);
498 802 : TuplesortPublic *base = TuplesortstateGetPublic(state);
499 : MemoryContext oldcontext;
500 : TuplesortIndexBTreeArg *arg;
501 : int i;
502 :
503 802 : oldcontext = MemoryContextSwitchTo(base->maincontext);
504 802 : arg = (TuplesortIndexBTreeArg *) palloc(sizeof(TuplesortIndexBTreeArg));
505 :
506 802 : if (trace_sort)
507 0 : elog(LOG,
508 : "begin index sort: workMem = %d, randomAccess = %c",
509 : workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
510 :
511 802 : base->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel);
512 :
513 802 : base->removeabbrev = removeabbrev_index;
514 802 : base->comparetup = comparetup_index_btree;
515 802 : base->comparetup_tiebreak = comparetup_index_btree_tiebreak;
516 802 : base->writetup = writetup_index;
517 802 : base->readtup = readtup_index;
518 802 : base->haveDatum1 = true;
519 802 : base->arg = arg;
520 :
521 802 : arg->index.heapRel = heapRel;
522 802 : arg->index.indexRel = indexRel;
523 802 : arg->enforceUnique = false;
524 802 : arg->uniqueNullsNotDistinct = false;
525 :
526 : /* Prepare SortSupport data for each column */
527 802 : base->sortKeys = (SortSupport) palloc0(base->nKeys *
528 : sizeof(SortSupportData));
529 :
530 2196 : for (i = 0; i < base->nKeys; i++)
531 : {
532 1394 : SortSupport sortKey = base->sortKeys + i;
533 :
534 1394 : sortKey->ssup_cxt = CurrentMemoryContext;
535 1394 : sortKey->ssup_collation = indexRel->rd_indcollation[i];
536 1394 : sortKey->ssup_nulls_first = false;
537 1394 : sortKey->ssup_attno = i + 1;
538 : /* Convey if abbreviation optimization is applicable in principle */
539 1394 : sortKey->abbreviate = (i == 0 && base->haveDatum1);
540 :
541 : Assert(sortKey->ssup_attno != 0);
542 :
543 : /* Look for a sort support function */
544 1394 : PrepareSortSupportFromGistIndexRel(indexRel, sortKey);
545 : }
546 :
547 802 : MemoryContextSwitchTo(oldcontext);
548 :
549 802 : 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 60574 : tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation,
652 : bool nullsFirstFlag, int workMem,
653 : SortCoordinate coordinate, int sortopt)
654 : {
655 60574 : Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
656 : sortopt);
657 60574 : TuplesortPublic *base = TuplesortstateGetPublic(state);
658 : TuplesortDatumArg *arg;
659 : MemoryContext oldcontext;
660 : int16 typlen;
661 : bool typbyval;
662 :
663 60574 : oldcontext = MemoryContextSwitchTo(base->maincontext);
664 60574 : arg = (TuplesortDatumArg *) palloc(sizeof(TuplesortDatumArg));
665 :
666 60574 : if (trace_sort)
667 0 : elog(LOG,
668 : "begin datum sort: workMem = %d, randomAccess = %c",
669 : workMem, sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
670 :
671 60574 : 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 60574 : base->removeabbrev = removeabbrev_datum;
681 60574 : base->comparetup = comparetup_datum;
682 60574 : base->comparetup_tiebreak = comparetup_datum_tiebreak;
683 60574 : base->writetup = writetup_datum;
684 60574 : base->readtup = readtup_datum;
685 60574 : base->haveDatum1 = true;
686 60574 : base->arg = arg;
687 :
688 60574 : arg->datumType = datumType;
689 :
690 : /* lookup necessary attributes of the datum type */
691 60574 : get_typlenbyval(datumType, &typlen, &typbyval);
692 60574 : arg->datumTypeLen = typlen;
693 60574 : base->tuples = !typbyval;
694 :
695 : /* Prepare SortSupport data */
696 60574 : base->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));
697 :
698 60574 : base->sortKeys->ssup_cxt = CurrentMemoryContext;
699 60574 : base->sortKeys->ssup_collation = sortCollation;
700 60574 : 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 60574 : base->sortKeys->abbreviate = !typbyval;
711 :
712 60574 : 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 60574 : if (!base->sortKeys->abbrev_converter)
721 59782 : base->onlyKey = base->sortKeys;
722 :
723 60574 : MemoryContextSwitchTo(oldcontext);
724 :
725 60574 : 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 13462516 : tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
735 : {
736 13462516 : TuplesortPublic *base = TuplesortstateGetPublic(state);
737 13462516 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
738 13462516 : 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 13462516 : tuple = ExecCopySlotMinimalTuple(slot);
746 13462516 : stup.tuple = tuple;
747 : /* set up first-column key value */
748 13462516 : htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
749 13462516 : htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
750 26925032 : stup.datum1 = heap_getattr(&htup,
751 13462516 : base->sortKeys[0].ssup_attno,
752 : tupDesc,
753 : &stup.isnull1);
754 :
755 : /* GetMemoryChunkSpace is not supported for bump contexts */
756 13462516 : if (TupleSortUseBumpTupleCxt(base->sortopt))
757 9955948 : tuplen = MAXALIGN(tuple->t_len);
758 : else
759 3506568 : tuplen = GetMemoryChunkSpace(tuple);
760 :
761 13462516 : tuplesort_puttuple_common(state, &stup,
762 14581658 : base->sortKeys->abbrev_converter &&
763 1119142 : !stup.isnull1, tuplen);
764 :
765 13462516 : MemoryContextSwitchTo(oldcontext);
766 13462516 : }
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 547408 : tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup)
775 : {
776 : SortTuple stup;
777 547408 : TuplesortPublic *base = TuplesortstateGetPublic(state);
778 547408 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
779 547408 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
780 : Size tuplen;
781 :
782 : /* copy the tuple into sort storage */
783 547408 : tup = heap_copytuple(tup);
784 547408 : stup.tuple = tup;
785 :
786 : /*
787 : * set up first-column key value, and potentially abbreviate, if it's a
788 : * simple column
789 : */
790 547408 : if (base->haveDatum1)
791 : {
792 545782 : stup.datum1 = heap_getattr(tup,
793 545782 : arg->indexInfo->ii_IndexAttrNumbers[0],
794 : arg->tupDesc,
795 : &stup.isnull1);
796 : }
797 :
798 : /* GetMemoryChunkSpace is not supported for bump contexts */
799 547408 : if (TupleSortUseBumpTupleCxt(base->sortopt))
800 547408 : tuplen = MAXALIGN(HEAPTUPLESIZE + tup->t_len);
801 : else
802 0 : tuplen = GetMemoryChunkSpace(tup);
803 :
804 547408 : tuplesort_puttuple_common(state, &stup,
805 1093190 : base->haveDatum1 &&
806 910496 : base->sortKeys->abbrev_converter &&
807 363088 : !stup.isnull1, tuplen);
808 :
809 547408 : MemoryContextSwitchTo(oldcontext);
810 547408 : }
811 :
812 : /*
813 : * Collect one index tuple while collecting input data for sort, building
814 : * it from caller-supplied values.
815 : */
816 : void
817 13646026 : tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel,
818 : ItemPointer self, const Datum *values,
819 : const bool *isnull)
820 : {
821 : SortTuple stup;
822 : IndexTuple tuple;
823 13646026 : TuplesortPublic *base = TuplesortstateGetPublic(state);
824 13646026 : TuplesortIndexArg *arg = (TuplesortIndexArg *) base->arg;
825 : Size tuplen;
826 :
827 13646026 : stup.tuple = index_form_tuple_context(RelationGetDescr(rel), values,
828 : isnull, base->tuplecontext);
829 13646026 : tuple = ((IndexTuple) stup.tuple);
830 13646026 : tuple->t_tid = *self;
831 : /* set up first-column key value */
832 27292052 : stup.datum1 = index_getattr(tuple,
833 : 1,
834 13646026 : RelationGetDescr(arg->indexRel),
835 : &stup.isnull1);
836 :
837 : /* GetMemoryChunkSpace is not supported for bump contexts */
838 13646026 : if (TupleSortUseBumpTupleCxt(base->sortopt))
839 13646026 : tuplen = MAXALIGN(tuple->t_info & INDEX_SIZE_MASK);
840 : else
841 0 : tuplen = GetMemoryChunkSpace(tuple);
842 :
843 13646026 : tuplesort_puttuple_common(state, &stup,
844 27171052 : base->sortKeys &&
845 15825908 : base->sortKeys->abbrev_converter &&
846 2179882 : !stup.isnull1, tuplen);
847 13646026 : }
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 3915240 : tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
923 : {
924 3915240 : TuplesortPublic *base = TuplesortstateGetPublic(state);
925 3915240 : MemoryContext oldcontext = MemoryContextSwitchTo(base->tuplecontext);
926 3915240 : 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 3915240 : 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 2178510 : stup.datum1 = !isNull ? val : (Datum) 0;
948 2178510 : stup.isnull1 = isNull;
949 2178510 : stup.tuple = NULL; /* no separate storage */
950 : }
951 : else
952 : {
953 1736730 : stup.isnull1 = false;
954 1736730 : stup.datum1 = datumCopy(val, false, arg->datumTypeLen);
955 1736730 : stup.tuple = DatumGetPointer(stup.datum1);
956 : }
957 :
958 3915240 : tuplesort_puttuple_common(state, &stup,
959 5652772 : base->tuples &&
960 3915240 : base->sortKeys->abbrev_converter && !isNull, 0);
961 :
962 3915240 : MemoryContextSwitchTo(oldcontext);
963 3915240 : }
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 11697792 : tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy,
987 : TupleTableSlot *slot, Datum *abbrev)
988 : {
989 11697792 : TuplesortPublic *base = TuplesortstateGetPublic(state);
990 11697792 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
991 : SortTuple stup;
992 :
993 11697792 : if (!tuplesort_gettuple_common(state, forward, &stup))
994 142346 : stup.tuple = NULL;
995 :
996 11697792 : MemoryContextSwitchTo(oldcontext);
997 :
998 11697792 : if (stup.tuple)
999 : {
1000 : /* Record abbreviated key for caller */
1001 11555446 : if (base->sortKeys->abbrev_converter && abbrev)
1002 0 : *abbrev = stup.datum1;
1003 :
1004 11555446 : if (copy)
1005 4556 : stup.tuple = heap_copy_minimal_tuple((MinimalTuple) stup.tuple, 0);
1006 :
1007 11555446 : ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
1008 11555446 : return true;
1009 : }
1010 : else
1011 : {
1012 142346 : ExecClearTuple(slot);
1013 142346 : 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 547520 : tuplesort_getheaptuple(Tuplesortstate *state, bool forward)
1025 : {
1026 547520 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1027 547520 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1028 : SortTuple stup;
1029 :
1030 547520 : if (!tuplesort_gettuple_common(state, forward, &stup))
1031 112 : stup.tuple = NULL;
1032 :
1033 547520 : MemoryContextSwitchTo(oldcontext);
1034 :
1035 547520 : 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 13698180 : tuplesort_getindextuple(Tuplesortstate *state, bool forward)
1046 : {
1047 13698180 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1048 13698180 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1049 : SortTuple stup;
1050 :
1051 13698180 : if (!tuplesort_gettuple_common(state, forward, &stup))
1052 52532 : stup.tuple = NULL;
1053 :
1054 13698180 : MemoryContextSwitchTo(oldcontext);
1055 :
1056 13698180 : 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 2546190 : tuplesort_getdatum(Tuplesortstate *state, bool forward, bool copy,
1138 : Datum *val, bool *isNull, Datum *abbrev)
1139 : {
1140 2546190 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1141 2546190 : MemoryContext oldcontext = MemoryContextSwitchTo(base->sortcontext);
1142 2546190 : TuplesortDatumArg *arg = (TuplesortDatumArg *) base->arg;
1143 : SortTuple stup;
1144 :
1145 2546190 : if (!tuplesort_gettuple_common(state, forward, &stup))
1146 : {
1147 59262 : MemoryContextSwitchTo(oldcontext);
1148 59262 : return false;
1149 : }
1150 :
1151 : /* Ensure we copy into caller's memory context */
1152 2486928 : MemoryContextSwitchTo(oldcontext);
1153 :
1154 : /* Record abbreviated key for caller */
1155 2486928 : if (base->sortKeys->abbrev_converter && abbrev)
1156 55024 : *abbrev = stup.datum1;
1157 :
1158 2486928 : if (stup.isnull1 || !base->tuples)
1159 : {
1160 1350396 : *val = stup.datum1;
1161 1350396 : *isNull = stup.isnull1;
1162 : }
1163 : else
1164 : {
1165 : /* use stup.tuple because stup.datum1 may be an abbreviation */
1166 1136532 : if (copy)
1167 60048 : *val = datumCopy(PointerGetDatum(stup.tuple), false,
1168 : arg->datumTypeLen);
1169 : else
1170 1076484 : *val = PointerGetDatum(stup.tuple);
1171 1136532 : *isNull = false;
1172 : }
1173 :
1174 2486928 : 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 56061602 : comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1205 : {
1206 56061602 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1207 56061602 : SortSupport sortKey = base->sortKeys;
1208 : int32 compare;
1209 :
1210 :
1211 : /* Compare the leading sort key */
1212 56061602 : compare = ApplySortComparator(a->datum1, a->isnull1,
1213 56061602 : b->datum1, b->isnull1,
1214 : sortKey);
1215 56061602 : if (compare != 0)
1216 19323586 : return compare;
1217 :
1218 : /* Compare additional sort keys */
1219 36738016 : return comparetup_heap_tiebreak(a, b, state);
1220 : }
1221 :
1222 : static int
1223 39863462 : comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1224 : {
1225 39863462 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1226 39863462 : 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 39863462 : ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
1239 39863462 : ltup.t_data = (HeapTupleHeader) ((char *) a->tuple - MINIMAL_TUPLE_OFFSET);
1240 39863462 : rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
1241 39863462 : rtup.t_data = (HeapTupleHeader) ((char *) b->tuple - MINIMAL_TUPLE_OFFSET);
1242 39863462 : tupDesc = (TupleDesc) base->arg;
1243 :
1244 39863462 : if (sortKey->abbrev_converter)
1245 : {
1246 1046506 : attno = sortKey->ssup_attno;
1247 :
1248 1046506 : datum1 = heap_getattr(<up, attno, tupDesc, &isnull1);
1249 1046506 : datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
1250 :
1251 1046506 : compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1252 : datum2, isnull2,
1253 : sortKey);
1254 1046506 : if (compare != 0)
1255 874130 : return compare;
1256 : }
1257 :
1258 38989332 : sortKey++;
1259 40955790 : for (nkey = 1; nkey < base->nKeys; nkey++, sortKey++)
1260 : {
1261 39210188 : attno = sortKey->ssup_attno;
1262 :
1263 39210188 : datum1 = heap_getattr(<up, attno, tupDesc, &isnull1);
1264 39210188 : datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
1265 :
1266 39210188 : compare = ApplySortComparator(datum1, isnull1,
1267 : datum2, isnull2,
1268 : sortKey);
1269 39210188 : if (compare != 0)
1270 37243730 : return compare;
1271 : }
1272 :
1273 1745602 : 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 5996272 : comparetup_cluster(const SortTuple *a, const SortTuple *b,
1347 : Tuplesortstate *state)
1348 : {
1349 5996272 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1350 5996272 : SortSupport sortKey = base->sortKeys;
1351 : int32 compare;
1352 :
1353 : /* Compare the leading sort key, if it's simple */
1354 5996272 : if (base->haveDatum1)
1355 : {
1356 5984482 : compare = ApplySortComparator(a->datum1, a->isnull1,
1357 5984482 : b->datum1, b->isnull1,
1358 : sortKey);
1359 5984482 : if (compare != 0)
1360 5843352 : return compare;
1361 : }
1362 :
1363 152920 : return comparetup_cluster_tiebreak(a, b, state);
1364 : }
1365 :
1366 : static int
1367 587160 : comparetup_cluster_tiebreak(const SortTuple *a, const SortTuple *b,
1368 : Tuplesortstate *state)
1369 : {
1370 587160 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1371 587160 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
1372 587160 : SortSupport sortKey = base->sortKeys;
1373 : HeapTuple ltup;
1374 : HeapTuple rtup;
1375 : TupleDesc tupDesc;
1376 : int nkey;
1377 587160 : int32 compare = 0;
1378 : Datum datum1,
1379 : datum2;
1380 : bool isnull1,
1381 : isnull2;
1382 :
1383 587160 : ltup = (HeapTuple) a->tuple;
1384 587160 : rtup = (HeapTuple) b->tuple;
1385 587160 : tupDesc = arg->tupDesc;
1386 :
1387 : /* Compare the leading sort key, if it's simple */
1388 587160 : if (base->haveDatum1)
1389 : {
1390 575370 : 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 575370 : if (compare != 0 || base->nKeys == 1)
1402 147810 : 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 112 : freestate_cluster(Tuplesortstate *state)
1519 : {
1520 112 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1521 112 : TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
1522 :
1523 : /* Free any execution state created for CLUSTER case */
1524 112 : 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 112 : }
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 59175964 : 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 59175964 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1570 59175964 : SortSupport sortKey = base->sortKeys;
1571 : int32 compare;
1572 :
1573 : /* Compare the leading sort key */
1574 59175964 : compare = ApplySortComparator(a->datum1, a->isnull1,
1575 59175964 : b->datum1, b->isnull1,
1576 : sortKey);
1577 59175964 : if (compare != 0)
1578 53636094 : return compare;
1579 :
1580 : /* Compare additional sort keys */
1581 5539870 : return comparetup_index_btree_tiebreak(a, b, state);
1582 : }
1583 :
1584 : static int
1585 18542304 : comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
1586 : Tuplesortstate *state)
1587 : {
1588 18542304 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1589 18542304 : TuplesortIndexBTreeArg *arg = (TuplesortIndexBTreeArg *) base->arg;
1590 18542304 : SortSupport sortKey = base->sortKeys;
1591 : IndexTuple tuple1;
1592 : IndexTuple tuple2;
1593 : int keysz;
1594 : TupleDesc tupDes;
1595 18542304 : bool equal_hasnull = false;
1596 : int nkey;
1597 : int32 compare;
1598 : Datum datum1,
1599 : datum2;
1600 : bool isnull1,
1601 : isnull2;
1602 :
1603 18542304 : tuple1 = (IndexTuple) a->tuple;
1604 18542304 : tuple2 = (IndexTuple) b->tuple;
1605 18542304 : keysz = base->nKeys;
1606 18542304 : tupDes = RelationGetDescr(arg->index.indexRel);
1607 :
1608 18542304 : if (sortKey->abbrev_converter)
1609 : {
1610 887498 : datum1 = index_getattr(tuple1, 1, tupDes, &isnull1);
1611 887498 : datum2 = index_getattr(tuple2, 1, tupDes, &isnull2);
1612 :
1613 887498 : compare = ApplySortAbbrevFullComparator(datum1, isnull1,
1614 : datum2, isnull2,
1615 : sortKey);
1616 887498 : if (compare != 0)
1617 809492 : return compare;
1618 : }
1619 :
1620 : /* they are equal, so we only need to examine one null flag */
1621 17732812 : if (a->isnull1)
1622 15058 : equal_hasnull = true;
1623 :
1624 17732812 : sortKey++;
1625 20510092 : for (nkey = 2; nkey <= keysz; nkey++, sortKey++)
1626 : {
1627 7732392 : datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
1628 7732392 : datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
1629 :
1630 7732392 : compare = ApplySortComparator(datum1, isnull1,
1631 : datum2, isnull2,
1632 : sortKey);
1633 7732392 : if (compare != 0)
1634 4955112 : return compare; /* done when we find unequal attributes */
1635 :
1636 : /* they are equal, so we only need to examine one null flag */
1637 2777280 : 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 12777700 : 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 12777616 : BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
1687 12777616 : BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
1688 :
1689 12777616 : if (blk1 != blk2)
1690 11747418 : return (blk1 < blk2) ? -1 : 1;
1691 : }
1692 : {
1693 1030198 : OffsetNumber pos1 = ItemPointerGetOffsetNumber(&tuple1->t_tid);
1694 1030198 : OffsetNumber pos2 = ItemPointerGetOffsetNumber(&tuple2->t_tid);
1695 :
1696 1030198 : if (pos1 != pos2)
1697 1030198 : 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 6792086 : comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1977 : {
1978 6792086 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1979 : int compare;
1980 :
1981 6792086 : compare = ApplySortComparator(a->datum1, a->isnull1,
1982 6792086 : b->datum1, b->isnull1,
1983 : base->sortKeys);
1984 6792086 : if (compare != 0)
1985 6591816 : return compare;
1986 :
1987 200270 : return comparetup_datum_tiebreak(a, b, state);
1988 : }
1989 :
1990 : static int
1991 2698220 : comparetup_datum_tiebreak(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
1992 : {
1993 2698220 : TuplesortPublic *base = TuplesortstateGetPublic(state);
1994 2698220 : int32 compare = 0;
1995 :
1996 : /* if we have abbreviations, then "tuple" has the original value */
1997 2698220 : if (base->sortKeys->abbrev_converter)
1998 2497968 : compare = ApplySortAbbrevFullComparator(PointerGetDatum(a->tuple), a->isnull1,
1999 2497968 : PointerGetDatum(b->tuple), b->isnull1,
2000 : base->sortKeys);
2001 :
2002 2698220 : 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 : }
|
