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