Debian Codegraph @

src/backend/access/brin/brin_tuple.c

raw
1 /*
2 * brin_tuple.c
3 * Method implementations for tuples in BRIN indexes.
4 *
5 * Intended usage is that code outside this file only deals with
6 * BrinMemTuples, and convert to and from the on-disk representation through
7 * functions in this file.
8 *
9 * NOTES
10 *
11 * A BRIN tuple is similar to a heap tuple, with a few key differences. The
12 * first interesting difference is that the tuple header is much simpler, only
13 * containing its total length and a small area for flags. Also, the stored
14 * data does not match the relation tuple descriptor exactly: for each
15 * attribute in the descriptor, the index tuple carries an arbitrary number
16 * of values, depending on the opclass.
17 *
18 * Also, for each column of the index relation there are two null bits: one
19 * (hasnulls) stores whether any tuple within the page range has that column
20 * set to null; the other one (allnulls) stores whether the column values are
21 * all null. If allnulls is true, then the tuple data area does not contain
22 * values for that column at all; whereas it does if the hasnulls is set.
23 * Note the size of the null bitmask may not be the same as that of the
24 * datum array.
25 *
26 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
27 * Portions Copyright (c) 1994, Regents of the University of California
28 *
29 * IDENTIFICATION
30 * src/backend/access/brin/brin_tuple.c
31 */
32 #include "postgres.h"
33
34 #include "access/brin_tuple.h"
35 #include "access/detoast.h"
36 #include "access/heaptoast.h"
37 #include "access/htup_details.h"
38 #include "access/toast_internals.h"
39 #include "access/tupdesc.h"
40 #include "access/tupmacs.h"
41 #include "utils/datum.h"
42 #include "utils/memutils.h"
43
44
45 /*
46 * This enables de-toasting of index entries. Needed until VACUUM is
47 * smart enough to rebuild indexes from scratch.
48 */
49 #define TOAST_INDEX_HACK
50
51
52 static inline void brin_deconstruct_tuple(BrinDesc *brdesc,
53 char *tp, bits8 *nullbits, bool nulls,
54 Datum *values, bool *allnulls, bool *hasnulls);
55
56
57 /*
58 * Return a tuple descriptor used for on-disk storage of BRIN tuples.
59 */
60 static TupleDesc
61 brtuple_disk_tupdesc(BrinDesc *brdesc)
62 {
63 /* We cache these in the BrinDesc */
64 if (brdesc->bd_disktdesc == NULL)
65 {
66 int i;
67 int j;
68 AttrNumber attno = 1;
69 TupleDesc tupdesc;
70 MemoryContext oldcxt;
71
72 /* make sure it's in the bdesc's context */
73 oldcxt = MemoryContextSwitchTo(brdesc->bd_context);
74
75 tupdesc = CreateTemplateTupleDesc(brdesc->bd_totalstored);
76
77 for (i = 0; i < brdesc->bd_tupdesc->natts; i++)
78 {
79 for (j = 0; j < brdesc->bd_info[i]->oi_nstored; j++)
80 TupleDescInitEntry(tupdesc, attno++, NULL,
81 brdesc->bd_info[i]->oi_typcache[j]->type_id,
82 -1, 0);
83 }
84
85 MemoryContextSwitchTo(oldcxt);
86
87 brdesc->bd_disktdesc = tupdesc;
88 }
89
90 return brdesc->bd_disktdesc;
91 }
92
93 /*
94 * Generate a new on-disk tuple to be inserted in a BRIN index.
95 *
96 * See brin_form_placeholder_tuple if you touch this.
97 */
98 BrinTuple *
99 brin_form_tuple(BrinDesc *brdesc, BlockNumber blkno, BrinMemTuple *tuple,
100 Size *size)
101 {
102 Datum *values;
103 bool *nulls;
104 bool anynulls = false;
105 BrinTuple *rettuple;
106 int keyno;
107 int idxattno;
108 uint16 phony_infomask = 0;
109 bits8 *phony_nullbitmap;
110 Size len,
111 hoff,
112 data_len;
113 int i;
114
115 #ifdef TOAST_INDEX_HACK
116 Datum *untoasted_values;
117 int nuntoasted = 0;
118 #endif
119
120 Assert(brdesc->bd_totalstored > 0);
121
122 values = (Datum *) palloc(sizeof(Datum) * brdesc->bd_totalstored);
123 nulls = (bool *) palloc0(sizeof(bool) * brdesc->bd_totalstored);
124 phony_nullbitmap = (bits8 *)
125 palloc(sizeof(bits8) * BITMAPLEN(brdesc->bd_totalstored));
126
127 #ifdef TOAST_INDEX_HACK
128 untoasted_values = (Datum *) palloc(sizeof(Datum) * brdesc->bd_totalstored);
129 #endif
130
131 /*
132 * Set up the values/nulls arrays for heap_fill_tuple
133 */
134 idxattno = 0;
135 for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
136 {
137 int datumno;
138
139 /*
140 * "allnulls" is set when there's no nonnull value in any row in the
141 * column; when this happens, there is no data to store. Thus set the
142 * nullable bits for all data elements of this column and we're done.
143 */
144 if (tuple->bt_columns[keyno].bv_allnulls)
145 {
146 for (datumno = 0;
147 datumno < brdesc->bd_info[keyno]->oi_nstored;
148 datumno++)
149 nulls[idxattno++] = true;
150 anynulls = true;
151 continue;
152 }
153
154 /*
155 * The "hasnulls" bit is set when there are some null values in the
156 * data. We still need to store a real value, but the presence of
157 * this means we need a null bitmap.
158 */
159 if (tuple->bt_columns[keyno].bv_hasnulls)
160 anynulls = true;
161
162 /* If needed, serialize the values before forming the on-disk tuple. */
163 if (tuple->bt_columns[keyno].bv_serialize)
164 {
165 tuple->bt_columns[keyno].bv_serialize(brdesc,
166 tuple->bt_columns[keyno].bv_mem_value,
167 tuple->bt_columns[keyno].bv_values);
168 }
169
170 /*
171 * Now obtain the values of each stored datum. Note that some values
172 * might be toasted, and we cannot rely on the original heap values
173 * sticking around forever, so we must detoast them. Also try to
174 * compress them.
175 */
176 for (datumno = 0;
177 datumno < brdesc->bd_info[keyno]->oi_nstored;
178 datumno++)
179 {
180 Datum value = tuple->bt_columns[keyno].bv_values[datumno];
181
182 #ifdef TOAST_INDEX_HACK
183
184 /* We must look at the stored type, not at the index descriptor. */
185 TypeCacheEntry *atttype = brdesc->bd_info[keyno]->oi_typcache[datumno];
186
187 /* Do we need to free the value at the end? */
188 bool free_value = false;
189
190 /* For non-varlena types we don't need to do anything special */
191 if (atttype->typlen != -1)
192 {
193 values[idxattno++] = value;
194 continue;
195 }
196
197 /*
198 * Do nothing if value is not of varlena type. We don't need to
199 * care about NULL values here, thanks to bv_allnulls above.
200 *
201 * If value is stored EXTERNAL, must fetch it so we are not
202 * depending on outside storage.
203 *
204 * XXX Is this actually true? Could it be that the summary is NULL
205 * even for range with non-NULL data? E.g. degenerate bloom filter
206 * may be thrown away, etc.
207 */
208 if (VARATT_IS_EXTERNAL(DatumGetPointer(value)))
209 {
210 value = PointerGetDatum(detoast_external_attr((struct varlena *)
211 DatumGetPointer(value)));
212 free_value = true;
213 }
214
215 /*
216 * If value is above size target, and is of a compressible
217 * datatype, try to compress it in-line.
218 */
219 if (!VARATT_IS_EXTENDED(DatumGetPointer(value)) &&
220 VARSIZE(DatumGetPointer(value)) > TOAST_INDEX_TARGET &&
221 (atttype->typstorage == TYPSTORAGE_EXTENDED ||
222 atttype->typstorage == TYPSTORAGE_MAIN))
223 {
224 Datum cvalue;
225 char compression;
226 Form_pg_attribute att = TupleDescAttr(brdesc->bd_tupdesc,
227 keyno);
228
229 /*
230 * If the BRIN summary and indexed attribute use the same data
231 * type and it has a valid compression method, we can use the
232 * same compression method. Otherwise we have to use the
233 * default method.
234 */
235 if (att->atttypid == atttype->type_id)
236 compression = att->attcompression;
237 else
238 compression = InvalidCompressionMethod;
239
240 cvalue = toast_compress_datum(value, compression);
241
242 if (DatumGetPointer(cvalue) != NULL)
243 {
244 /* successful compression */
245 if (free_value)
246 pfree(DatumGetPointer(value));
247
248 value = cvalue;
249 free_value = true;
250 }
251 }
252
253 /*
254 * If we untoasted / compressed the value, we need to free it
255 * after forming the index tuple.
256 */
257 if (free_value)
258 untoasted_values[nuntoasted++] = value;
259
260 #endif
261
262 values[idxattno++] = value;
263 }
264 }
265
266 /* Assert we did not overrun temp arrays */
267 Assert(idxattno <= brdesc->bd_totalstored);
268
269 /* compute total space needed */
270 len = SizeOfBrinTuple;
271 if (anynulls)
272 {
273 /*
274 * We need a double-length bitmap on an on-disk BRIN index tuple; the
275 * first half stores the "allnulls" bits, the second stores
276 * "hasnulls".
277 */
278 len += BITMAPLEN(brdesc->bd_tupdesc->natts * 2);
279 }
280
281 len = hoff = MAXALIGN(len);
282
283 data_len = heap_compute_data_size(brtuple_disk_tupdesc(brdesc),
284 values, nulls);
285 len += data_len;
286
287 len = MAXALIGN(len);
288
289 rettuple = palloc0(len);
290 rettuple->bt_blkno = blkno;
291 rettuple->bt_info = hoff;
292
293 /* Assert that hoff fits in the space available */
294 Assert((rettuple->bt_info & BRIN_OFFSET_MASK) == hoff);
295
296 /*
297 * The infomask and null bitmap as computed by heap_fill_tuple are useless
298 * to us. However, that function will not accept a null infomask; and we
299 * need to pass a valid null bitmap so that it will correctly skip
300 * outputting null attributes in the data area.
301 */
302 heap_fill_tuple(brtuple_disk_tupdesc(brdesc),
303 values,
304 nulls,
305 (char *) rettuple + hoff,
306 data_len,
307 &phony_infomask,
308 phony_nullbitmap);
309
310 /* done with these */
311 pfree(values);
312 pfree(nulls);
313 pfree(phony_nullbitmap);
314
315 #ifdef TOAST_INDEX_HACK
316 for (i = 0; i < nuntoasted; i++)
317 pfree(DatumGetPointer(untoasted_values[i]));
318 #endif
319
320 /*
321 * Now fill in the real null bitmasks. allnulls first.
322 */
323 if (anynulls)
324 {
325 bits8 *bitP;
326 int bitmask;
327
328 rettuple->bt_info |= BRIN_NULLS_MASK;
329
330 /*
331 * Note that we reverse the sense of null bits in this module: we
332 * store a 1 for a null attribute rather than a 0. So we must reverse
333 * the sense of the att_isnull test in brin_deconstruct_tuple as well.
334 */
335 bitP = ((bits8 *) ((char *) rettuple + SizeOfBrinTuple)) - 1;
336 bitmask = HIGHBIT;
337 for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
338 {
339 if (bitmask != HIGHBIT)
340 bitmask <<= 1;
341 else
342 {
343 bitP += 1;
344 *bitP = 0x0;
345 bitmask = 1;
346 }
347
348 if (!tuple->bt_columns[keyno].bv_allnulls)
349 continue;
350
351 *bitP |= bitmask;
352 }
353 /* hasnulls bits follow */
354 for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
355 {
356 if (bitmask != HIGHBIT)
357 bitmask <<= 1;
358 else
359 {
360 bitP += 1;
361 *bitP = 0x0;
362 bitmask = 1;
363 }
364
365 if (!tuple->bt_columns[keyno].bv_hasnulls)
366 continue;
367
368 *bitP |= bitmask;
369 }
370 }
371
372 if (tuple->bt_placeholder)
373 rettuple->bt_info |= BRIN_PLACEHOLDER_MASK;
374
375 if (tuple->bt_empty_range)
376 rettuple->bt_info |= BRIN_EMPTY_RANGE_MASK;
377
378 *size = len;
379 return rettuple;
380 }
381
382 /*
383 * Generate a new on-disk tuple with no data values, marked as placeholder.
384 *
385 * This is a cut-down version of brin_form_tuple.
386 */
387 BrinTuple *
388 brin_form_placeholder_tuple(BrinDesc *brdesc, BlockNumber blkno, Size *size)
389 {
390 Size len;
391 Size hoff;
392 BrinTuple *rettuple;
393 int keyno;
394 bits8 *bitP;
395 int bitmask;
396
397 /* compute total space needed: always add nulls */
398 len = SizeOfBrinTuple;
399 len += BITMAPLEN(brdesc->bd_tupdesc->natts * 2);
400 len = hoff = MAXALIGN(len);
401
402 rettuple = palloc0(len);
403 rettuple->bt_blkno = blkno;
404 rettuple->bt_info = hoff;
405 rettuple->bt_info |= BRIN_NULLS_MASK | BRIN_PLACEHOLDER_MASK | BRIN_EMPTY_RANGE_MASK;
406
407 bitP = ((bits8 *) ((char *) rettuple + SizeOfBrinTuple)) - 1;
408 bitmask = HIGHBIT;
409 /* set allnulls true for all attributes */
410 for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
411 {
412 if (bitmask != HIGHBIT)
413 bitmask <<= 1;
414 else
415 {
416 bitP += 1;
417 *bitP = 0x0;
418 bitmask = 1;
419 }
420
421 *bitP |= bitmask;
422 }
423 /* no need to set hasnulls */
424
425 *size = len;
426 return rettuple;
427 }
428
429 /*
430 * Free a tuple created by brin_form_tuple
431 */
432 void
433 brin_free_tuple(BrinTuple *tuple)
434 {
435 pfree(tuple);
436 }
437
438 /*
439 * Given a brin tuple of size len, create a copy of it. If 'dest' is not
440 * NULL, its size is destsz, and can be used as output buffer; if the tuple
441 * to be copied does not fit, it is enlarged by repalloc, and the size is
442 * updated to match. This avoids palloc/free cycles when many brin tuples
443 * are being processed in loops.
444 */
445 BrinTuple *
446 brin_copy_tuple(BrinTuple *tuple, Size len, BrinTuple *dest, Size *destsz)
447 {
448 if (!destsz || *destsz == 0)
449 dest = palloc(len);
450 else if (len > *destsz)
451 {
452 dest = repalloc(dest, len);
453 *destsz = len;
454 }
455
456 memcpy(dest, tuple, len);
457
458 return dest;
459 }
460
461 /*
462 * Return whether two BrinTuples are bitwise identical.
463 */
464 bool
465 brin_tuples_equal(const BrinTuple *a, Size alen, const BrinTuple *b, Size blen)
466 {
467 if (alen != blen)
468 return false;
469 if (memcmp(a, b, alen) != 0)
470 return false;
471 return true;
472 }
473
474 /*
475 * Create a new BrinMemTuple from scratch, and initialize it to an empty
476 * state.
477 *
478 * Note: we don't provide any means to free a deformed tuple, so make sure to
479 * use a temporary memory context.
480 */
481 BrinMemTuple *
482 brin_new_memtuple(BrinDesc *brdesc)
483 {
484 BrinMemTuple *dtup;
485 long basesize;
486
487 basesize = MAXALIGN(sizeof(BrinMemTuple) +
488 sizeof(BrinValues) * brdesc->bd_tupdesc->natts);
489 dtup = palloc0(basesize + sizeof(Datum) * brdesc->bd_totalstored);
490
491 dtup->bt_values = palloc(sizeof(Datum) * brdesc->bd_totalstored);
492 dtup->bt_allnulls = palloc(sizeof(bool) * brdesc->bd_tupdesc->natts);
493 dtup->bt_hasnulls = palloc(sizeof(bool) * brdesc->bd_tupdesc->natts);
494
495 dtup->bt_empty_range = true;
496
497 dtup->bt_context = AllocSetContextCreate(CurrentMemoryContext,
498 "brin dtuple",
499 ALLOCSET_DEFAULT_SIZES);
500
501 brin_memtuple_initialize(dtup, brdesc);
502
503 return dtup;
504 }
505
506 /*
507 * Reset a BrinMemTuple to initial state. We return the same tuple, for
508 * notational convenience.
509 */
510 BrinMemTuple *
511 brin_memtuple_initialize(BrinMemTuple *dtuple, BrinDesc *brdesc)
512 {
513 int i;
514 char *currdatum;
515
516 MemoryContextReset(dtuple->bt_context);
517
518 currdatum = (char *) dtuple +
519 MAXALIGN(sizeof(BrinMemTuple) +
520 sizeof(BrinValues) * brdesc->bd_tupdesc->natts);
521 for (i = 0; i < brdesc->bd_tupdesc->natts; i++)
522 {
523 dtuple->bt_columns[i].bv_attno = i + 1;
524 dtuple->bt_columns[i].bv_allnulls = true;
525 dtuple->bt_columns[i].bv_hasnulls = false;
526 dtuple->bt_columns[i].bv_values = (Datum *) currdatum;
527
528 dtuple->bt_columns[i].bv_mem_value = PointerGetDatum(NULL);
529 dtuple->bt_columns[i].bv_serialize = NULL;
530 dtuple->bt_columns[i].bv_context = dtuple->bt_context;
531
532 currdatum += sizeof(Datum) * brdesc->bd_info[i]->oi_nstored;
533 }
534
535 dtuple->bt_empty_range = true;
536
537 return dtuple;
538 }
539
540 /*
541 * Convert a BrinTuple back to a BrinMemTuple. This is the reverse of
542 * brin_form_tuple.
543 *
544 * As an optimization, the caller can pass a previously allocated 'dMemtuple'.
545 * This avoids having to allocate it here, which can be useful when this
546 * function is called many times in a loop. It is caller's responsibility
547 * that the given BrinMemTuple matches what we need here.
548 *
549 * Note we don't need the "on disk tupdesc" here; we rely on our own routine to
550 * deconstruct the tuple from the on-disk format.
551 */
552 BrinMemTuple *
553 brin_deform_tuple(BrinDesc *brdesc, BrinTuple *tuple, BrinMemTuple *dMemtuple)
554 {
555 BrinMemTuple *dtup;
556 Datum *values;
557 bool *allnulls;
558 bool *hasnulls;
559 char *tp;
560 bits8 *nullbits;
561 int keyno;
562 int valueno;
563 MemoryContext oldcxt;
564
565 dtup = dMemtuple ? brin_memtuple_initialize(dMemtuple, brdesc) :
566 brin_new_memtuple(brdesc);
567
568 if (BrinTupleIsPlaceholder(tuple))
569 dtup->bt_placeholder = true;
570
571 /* ranges start as empty, depends on the BrinTuple */
572 if (!BrinTupleIsEmptyRange(tuple))
573 dtup->bt_empty_range = false;
574
575 dtup->bt_blkno = tuple->bt_blkno;
576
577 values = dtup->bt_values;
578 allnulls = dtup->bt_allnulls;
579 hasnulls = dtup->bt_hasnulls;
580
581 tp = (char *) tuple + BrinTupleDataOffset(tuple);
582
583 if (BrinTupleHasNulls(tuple))
584 nullbits = (bits8 *) ((char *) tuple + SizeOfBrinTuple);
585 else
586 nullbits = NULL;
587 brin_deconstruct_tuple(brdesc,
588 tp, nullbits, BrinTupleHasNulls(tuple),
589 values, allnulls, hasnulls);
590
591 /*
592 * Iterate to assign each of the values to the corresponding item in the
593 * values array of each column. The copies occur in the tuple's context.
594 */
595 oldcxt = MemoryContextSwitchTo(dtup->bt_context);
596 for (valueno = 0, keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
597 {
598 int i;
599
600 if (allnulls[keyno])
601 {
602 valueno += brdesc->bd_info[keyno]->oi_nstored;
603 continue;
604 }
605
606 /*
607 * We would like to skip datumCopy'ing the values datum in some cases,
608 * caller permitting ...
609 */
610 for (i = 0; i < brdesc->bd_info[keyno]->oi_nstored; i++)
611 dtup->bt_columns[keyno].bv_values[i] =
612 datumCopy(values[valueno++],
613 brdesc->bd_info[keyno]->oi_typcache[i]->typbyval,
614 brdesc->bd_info[keyno]->oi_typcache[i]->typlen);
615
616 dtup->bt_columns[keyno].bv_hasnulls = hasnulls[keyno];
617 dtup->bt_columns[keyno].bv_allnulls = false;
618
619 dtup->bt_columns[keyno].bv_mem_value = PointerGetDatum(NULL);
620 dtup->bt_columns[keyno].bv_serialize = NULL;
621 dtup->bt_columns[keyno].bv_context = dtup->bt_context;
622 }
623
624 MemoryContextSwitchTo(oldcxt);
625
626 return dtup;
627 }
628
629 /*
630 * brin_deconstruct_tuple
631 * Guts of attribute extraction from an on-disk BRIN tuple.
632 *
633 * Its arguments are:
634 * brdesc BRIN descriptor for the stored tuple
635 * tp pointer to the tuple data area
636 * nullbits pointer to the tuple nulls bitmask
637 * nulls "has nulls" bit in tuple infomask
638 * values output values, array of size brdesc->bd_totalstored
639 * allnulls output "allnulls", size brdesc->bd_tupdesc->natts
640 * hasnulls output "hasnulls", size brdesc->bd_tupdesc->natts
641 *
642 * Output arrays must have been allocated by caller.
643 */
644 static inline void
645 brin_deconstruct_tuple(BrinDesc *brdesc,
646 char *tp, bits8 *nullbits, bool nulls,
647 Datum *values, bool *allnulls, bool *hasnulls)
648 {
649 int attnum;
650 int stored;
651 TupleDesc diskdsc;
652 long off;
653
654 /*
655 * First iterate to natts to obtain both null flags for each attribute.
656 * Note that we reverse the sense of the att_isnull test, because we store
657 * 1 for a null value (rather than a 1 for a not null value as is the
658 * att_isnull convention used elsewhere.) See brin_form_tuple.
659 */
660 for (attnum = 0; attnum < brdesc->bd_tupdesc->natts; attnum++)
661 {
662 /*
663 * the "all nulls" bit means that all values in the page range for
664 * this column are nulls. Therefore there are no values in the tuple
665 * data area.
666 */
667 allnulls[attnum] = nulls && !att_isnull(attnum, nullbits);
668
669 /*
670 * the "has nulls" bit means that some tuples have nulls, but others
671 * have not-null values. Therefore we know the tuple contains data
672 * for this column.
673 *
674 * The hasnulls bits follow the allnulls bits in the same bitmask.
675 */
676 hasnulls[attnum] =
677 nulls && !att_isnull(brdesc->bd_tupdesc->natts + attnum, nullbits);
678 }
679
680 /*
681 * Iterate to obtain each attribute's stored values. Note that since we
682 * may reuse attribute entries for more than one column, we cannot cache
683 * offsets here.
684 */
685 diskdsc = brtuple_disk_tupdesc(brdesc);
686 stored = 0;
687 off = 0;
688 for (attnum = 0; attnum < brdesc->bd_tupdesc->natts; attnum++)
689 {
690 int datumno;
691
692 if (allnulls[attnum])
693 {
694 stored += brdesc->bd_info[attnum]->oi_nstored;
695 continue;
696 }
697
698 for (datumno = 0;
699 datumno < brdesc->bd_info[attnum]->oi_nstored;
700 datumno++)
701 {
702 CompactAttribute *thisatt = TupleDescCompactAttr(diskdsc, stored);
703
704 if (thisatt->attlen == -1)
705 {
706 off = att_pointer_alignby(off,
707 thisatt->attalignby,
708 -1,
709 tp + off);
710 }
711 else
712 {
713 /* not varlena, so safe to use att_nominal_alignby */
714 off = att_nominal_alignby(off, thisatt->attalignby);
715 }
716
717 values[stored++] = fetchatt(thisatt, tp + off);
718
719 off = att_addlength_pointer(off, thisatt->attlen, tp + off);
720 }
721 }
722 }