PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
brin_tuple.c
Go to the documentation of this file.
1 /*
2  * brin_tuples.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-2017, 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/htup_details.h"
35 #include "access/brin_tuple.h"
36 #include "access/tupdesc.h"
37 #include "access/tupmacs.h"
38 #include "utils/datum.h"
39 #include "utils/memutils.h"
40 
41 
42 static inline void brin_deconstruct_tuple(BrinDesc *brdesc,
43  char *tp, bits8 *nullbits, bool nulls,
44  Datum *values, bool *allnulls, bool *hasnulls);
45 
46 
47 /*
48  * Return a tuple descriptor used for on-disk storage of BRIN tuples.
49  */
50 static TupleDesc
52 {
53  /* We cache these in the BrinDesc */
54  if (brdesc->bd_disktdesc == NULL)
55  {
56  int i;
57  int j;
58  AttrNumber attno = 1;
59  TupleDesc tupdesc;
60  MemoryContext oldcxt;
61 
62  /* make sure it's in the bdesc's context */
63  oldcxt = MemoryContextSwitchTo(brdesc->bd_context);
64 
65  tupdesc = CreateTemplateTupleDesc(brdesc->bd_totalstored, false);
66 
67  for (i = 0; i < brdesc->bd_tupdesc->natts; i++)
68  {
69  for (j = 0; j < brdesc->bd_info[i]->oi_nstored; j++)
70  TupleDescInitEntry(tupdesc, attno++, NULL,
71  brdesc->bd_info[i]->oi_typcache[j]->type_id,
72  -1, 0);
73  }
74 
75  MemoryContextSwitchTo(oldcxt);
76 
77  brdesc->bd_disktdesc = tupdesc;
78  }
79 
80  return brdesc->bd_disktdesc;
81 }
82 
83 /*
84  * Generate a new on-disk tuple to be inserted in a BRIN index.
85  *
86  * See brin_form_placeholder_tuple if you touch this.
87  */
88 BrinTuple *
90  Size *size)
91 {
92  Datum *values;
93  bool *nulls;
94  bool anynulls = false;
95  BrinTuple *rettuple;
96  int keyno;
97  int idxattno;
98  uint16 phony_infomask = 0;
99  bits8 *phony_nullbitmap;
100  Size len,
101  hoff,
102  data_len;
103 
104  Assert(brdesc->bd_totalstored > 0);
105 
106  values = (Datum *) palloc(sizeof(Datum) * brdesc->bd_totalstored);
107  nulls = (bool *) palloc0(sizeof(bool) * brdesc->bd_totalstored);
108  phony_nullbitmap = (bits8 *)
109  palloc(sizeof(bits8) * BITMAPLEN(brdesc->bd_totalstored));
110 
111  /*
112  * Set up the values/nulls arrays for heap_fill_tuple
113  */
114  idxattno = 0;
115  for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
116  {
117  int datumno;
118 
119  /*
120  * "allnulls" is set when there's no nonnull value in any row in the
121  * column; when this happens, there is no data to store. Thus set the
122  * nullable bits for all data elements of this column and we're done.
123  */
124  if (tuple->bt_columns[keyno].bv_allnulls)
125  {
126  for (datumno = 0;
127  datumno < brdesc->bd_info[keyno]->oi_nstored;
128  datumno++)
129  nulls[idxattno++] = true;
130  anynulls = true;
131  continue;
132  }
133 
134  /*
135  * The "hasnulls" bit is set when there are some null values in the
136  * data. We still need to store a real value, but the presence of
137  * this means we need a null bitmap.
138  */
139  if (tuple->bt_columns[keyno].bv_hasnulls)
140  anynulls = true;
141 
142  for (datumno = 0;
143  datumno < brdesc->bd_info[keyno]->oi_nstored;
144  datumno++)
145  values[idxattno++] = tuple->bt_columns[keyno].bv_values[datumno];
146  }
147 
148  /* Assert we did not overrun temp arrays */
149  Assert(idxattno <= brdesc->bd_totalstored);
150 
151  /* compute total space needed */
152  len = SizeOfBrinTuple;
153  if (anynulls)
154  {
155  /*
156  * We need a double-length bitmap on an on-disk BRIN index tuple; the
157  * first half stores the "allnulls" bits, the second stores
158  * "hasnulls".
159  */
160  len += BITMAPLEN(brdesc->bd_tupdesc->natts * 2);
161  }
162 
163  len = hoff = MAXALIGN(len);
164 
165  data_len = heap_compute_data_size(brtuple_disk_tupdesc(brdesc),
166  values, nulls);
167  len += data_len;
168 
169  len = MAXALIGN(len);
170 
171  rettuple = palloc0(len);
172  rettuple->bt_blkno = blkno;
173  rettuple->bt_info = hoff;
174 
175  /* Assert that hoff fits in the space available */
176  Assert((rettuple->bt_info & BRIN_OFFSET_MASK) == hoff);
177 
178  /*
179  * The infomask and null bitmap as computed by heap_fill_tuple are useless
180  * to us. However, that function will not accept a null infomask; and we
181  * need to pass a valid null bitmap so that it will correctly skip
182  * outputting null attributes in the data area.
183  */
185  values,
186  nulls,
187  (char *) rettuple + hoff,
188  data_len,
189  &phony_infomask,
190  phony_nullbitmap);
191 
192  /* done with these */
193  pfree(values);
194  pfree(nulls);
195  pfree(phony_nullbitmap);
196 
197  /*
198  * Now fill in the real null bitmasks. allnulls first.
199  */
200  if (anynulls)
201  {
202  bits8 *bitP;
203  int bitmask;
204 
205  rettuple->bt_info |= BRIN_NULLS_MASK;
206 
207  /*
208  * Note that we reverse the sense of null bits in this module: we
209  * store a 1 for a null attribute rather than a 0. So we must reverse
210  * the sense of the att_isnull test in br_deconstruct_tuple as well.
211  */
212  bitP = ((bits8 *) ((char *) rettuple + SizeOfBrinTuple)) - 1;
213  bitmask = HIGHBIT;
214  for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
215  {
216  if (bitmask != HIGHBIT)
217  bitmask <<= 1;
218  else
219  {
220  bitP += 1;
221  *bitP = 0x0;
222  bitmask = 1;
223  }
224 
225  if (!tuple->bt_columns[keyno].bv_allnulls)
226  continue;
227 
228  *bitP |= bitmask;
229  }
230  /* hasnulls bits follow */
231  for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
232  {
233  if (bitmask != HIGHBIT)
234  bitmask <<= 1;
235  else
236  {
237  bitP += 1;
238  *bitP = 0x0;
239  bitmask = 1;
240  }
241 
242  if (!tuple->bt_columns[keyno].bv_hasnulls)
243  continue;
244 
245  *bitP |= bitmask;
246  }
247  bitP = ((bits8 *) (rettuple + SizeOfBrinTuple)) - 1;
248  }
249 
250  if (tuple->bt_placeholder)
251  rettuple->bt_info |= BRIN_PLACEHOLDER_MASK;
252 
253  *size = len;
254  return rettuple;
255 }
256 
257 /*
258  * Generate a new on-disk tuple with no data values, marked as placeholder.
259  *
260  * This is a cut-down version of brin_form_tuple.
261  */
262 BrinTuple *
264 {
265  Size len;
266  Size hoff;
267  BrinTuple *rettuple;
268  int keyno;
269  bits8 *bitP;
270  int bitmask;
271 
272  /* compute total space needed: always add nulls */
273  len = SizeOfBrinTuple;
274  len += BITMAPLEN(brdesc->bd_tupdesc->natts * 2);
275  len = hoff = MAXALIGN(len);
276 
277  rettuple = palloc0(len);
278  rettuple->bt_blkno = blkno;
279  rettuple->bt_info = hoff;
281 
282  bitP = ((bits8 *) ((char *) rettuple + SizeOfBrinTuple)) - 1;
283  bitmask = HIGHBIT;
284  /* set allnulls true for all attributes */
285  for (keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
286  {
287  if (bitmask != HIGHBIT)
288  bitmask <<= 1;
289  else
290  {
291  bitP += 1;
292  *bitP = 0x0;
293  bitmask = 1;
294  }
295 
296  *bitP |= bitmask;
297  }
298  /* no need to set hasnulls */
299 
300  *size = len;
301  return rettuple;
302 }
303 
304 /*
305  * Free a tuple created by brin_form_tuple
306  */
307 void
309 {
310  pfree(tuple);
311 }
312 
313 /*
314  * Create a palloc'd copy of a BrinTuple.
315  */
316 BrinTuple *
318 {
319  BrinTuple *newtup;
320 
321  newtup = palloc(len);
322  memcpy(newtup, tuple, len);
323 
324  return newtup;
325 }
326 
327 /*
328  * Return whether two BrinTuples are bitwise identical.
329  */
330 bool
331 brin_tuples_equal(const BrinTuple *a, Size alen, const BrinTuple *b, Size blen)
332 {
333  if (alen != blen)
334  return false;
335  if (memcmp(a, b, alen) != 0)
336  return false;
337  return true;
338 }
339 
340 /*
341  * Create a new BrinMemTuple from scratch, and initialize it to an empty
342  * state.
343  *
344  * Note: we don't provide any means to free a deformed tuple, so make sure to
345  * use a temporary memory context.
346  */
347 BrinMemTuple *
349 {
350  BrinMemTuple *dtup;
351  char *currdatum;
352  long basesize;
353  int i;
354 
355  basesize = MAXALIGN(sizeof(BrinMemTuple) +
356  sizeof(BrinValues) * brdesc->bd_tupdesc->natts);
357  dtup = palloc0(basesize + sizeof(Datum) * brdesc->bd_totalstored);
358  currdatum = (char *) dtup + basesize;
359  for (i = 0; i < brdesc->bd_tupdesc->natts; i++)
360  {
361  dtup->bt_columns[i].bv_attno = i + 1;
362  dtup->bt_columns[i].bv_allnulls = true;
363  dtup->bt_columns[i].bv_hasnulls = false;
364  dtup->bt_columns[i].bv_values = (Datum *) currdatum;
365  currdatum += sizeof(Datum) * brdesc->bd_info[i]->oi_nstored;
366  }
367 
369  "brin dtuple",
371  return dtup;
372 }
373 
374 /*
375  * Reset a BrinMemTuple to initial state
376  */
377 void
379 {
380  int i;
381 
383  for (i = 0; i < brdesc->bd_tupdesc->natts; i++)
384  {
385  dtuple->bt_columns[i].bv_allnulls = true;
386  dtuple->bt_columns[i].bv_hasnulls = false;
387  }
388 }
389 
390 /*
391  * Convert a BrinTuple back to a BrinMemTuple. This is the reverse of
392  * brin_form_tuple.
393  *
394  * Note we don't need the "on disk tupdesc" here; we rely on our own routine to
395  * deconstruct the tuple from the on-disk format.
396  */
397 BrinMemTuple *
399 {
400  BrinMemTuple *dtup;
401  Datum *values;
402  bool *allnulls;
403  bool *hasnulls;
404  char *tp;
405  bits8 *nullbits;
406  int keyno;
407  int valueno;
408  MemoryContext oldcxt;
409 
410  dtup = brin_new_memtuple(brdesc);
411 
412  if (BrinTupleIsPlaceholder(tuple))
413  dtup->bt_placeholder = true;
414  dtup->bt_blkno = tuple->bt_blkno;
415 
416  values = palloc(sizeof(Datum) * brdesc->bd_totalstored);
417  allnulls = palloc(sizeof(bool) * brdesc->bd_tupdesc->natts);
418  hasnulls = palloc(sizeof(bool) * brdesc->bd_tupdesc->natts);
419 
420  tp = (char *) tuple + BrinTupleDataOffset(tuple);
421 
422  if (BrinTupleHasNulls(tuple))
423  nullbits = (bits8 *) ((char *) tuple + SizeOfBrinTuple);
424  else
425  nullbits = NULL;
426  brin_deconstruct_tuple(brdesc,
427  tp, nullbits, BrinTupleHasNulls(tuple),
428  values, allnulls, hasnulls);
429 
430  /*
431  * Iterate to assign each of the values to the corresponding item in the
432  * values array of each column. The copies occur in the tuple's context.
433  */
434  oldcxt = MemoryContextSwitchTo(dtup->bt_context);
435  for (valueno = 0, keyno = 0; keyno < brdesc->bd_tupdesc->natts; keyno++)
436  {
437  int i;
438 
439  if (allnulls[keyno])
440  {
441  valueno += brdesc->bd_info[keyno]->oi_nstored;
442  continue;
443  }
444 
445  /*
446  * We would like to skip datumCopy'ing the values datum in some cases,
447  * caller permitting ...
448  */
449  for (i = 0; i < brdesc->bd_info[keyno]->oi_nstored; i++)
450  dtup->bt_columns[keyno].bv_values[i] =
451  datumCopy(values[valueno++],
452  brdesc->bd_info[keyno]->oi_typcache[i]->typbyval,
453  brdesc->bd_info[keyno]->oi_typcache[i]->typlen);
454 
455  dtup->bt_columns[keyno].bv_hasnulls = hasnulls[keyno];
456  dtup->bt_columns[keyno].bv_allnulls = false;
457  }
458 
459  MemoryContextSwitchTo(oldcxt);
460 
461  pfree(values);
462  pfree(allnulls);
463  pfree(hasnulls);
464 
465  return dtup;
466 }
467 
468 /*
469  * brin_deconstruct_tuple
470  * Guts of attribute extraction from an on-disk BRIN tuple.
471  *
472  * Its arguments are:
473  * brdesc BRIN descriptor for the stored tuple
474  * tp pointer to the tuple data area
475  * nullbits pointer to the tuple nulls bitmask
476  * nulls "has nulls" bit in tuple infomask
477  * values output values, array of size brdesc->bd_totalstored
478  * allnulls output "allnulls", size brdesc->bd_tupdesc->natts
479  * hasnulls output "hasnulls", size brdesc->bd_tupdesc->natts
480  *
481  * Output arrays must have been allocated by caller.
482  */
483 static inline void
485  char *tp, bits8 *nullbits, bool nulls,
486  Datum *values, bool *allnulls, bool *hasnulls)
487 {
488  int attnum;
489  int stored;
490  TupleDesc diskdsc;
491  long off;
492 
493  /*
494  * First iterate to natts to obtain both null flags for each attribute.
495  * Note that we reverse the sense of the att_isnull test, because we store
496  * 1 for a null value (rather than a 1 for a not null value as is the
497  * att_isnull convention used elsewhere.) See brin_form_tuple.
498  */
499  for (attnum = 0; attnum < brdesc->bd_tupdesc->natts; attnum++)
500  {
501  /*
502  * the "all nulls" bit means that all values in the page range for
503  * this column are nulls. Therefore there are no values in the tuple
504  * data area.
505  */
506  allnulls[attnum] = nulls && !att_isnull(attnum, nullbits);
507 
508  /*
509  * the "has nulls" bit means that some tuples have nulls, but others
510  * have not-null values. Therefore we know the tuple contains data
511  * for this column.
512  *
513  * The hasnulls bits follow the allnulls bits in the same bitmask.
514  */
515  hasnulls[attnum] =
516  nulls && !att_isnull(brdesc->bd_tupdesc->natts + attnum, nullbits);
517  }
518 
519  /*
520  * Iterate to obtain each attribute's stored values. Note that since we
521  * may reuse attribute entries for more than one column, we cannot cache
522  * offsets here.
523  */
524  diskdsc = brtuple_disk_tupdesc(brdesc);
525  stored = 0;
526  off = 0;
527  for (attnum = 0; attnum < brdesc->bd_tupdesc->natts; attnum++)
528  {
529  int datumno;
530 
531  if (allnulls[attnum])
532  {
533  stored += brdesc->bd_info[attnum]->oi_nstored;
534  continue;
535  }
536 
537  for (datumno = 0;
538  datumno < brdesc->bd_info[attnum]->oi_nstored;
539  datumno++)
540  {
541  Form_pg_attribute thisatt = diskdsc->attrs[stored];
542 
543  if (thisatt->attlen == -1)
544  {
545  off = att_align_pointer(off, thisatt->attalign, -1,
546  tp + off);
547  }
548  else
549  {
550  /* not varlena, so safe to use att_align_nominal */
551  off = att_align_nominal(off, thisatt->attalign);
552  }
553 
554  values[stored++] = fetchatt(thisatt, tp + off);
555 
556  off = att_addlength_pointer(off, thisatt->attlen, tp + off);
557  }
558  }
559 }
#define BRIN_OFFSET_MASK
Definition: brin_tuple.h:71
#define BrinTupleIsPlaceholder(tup)
Definition: brin_tuple.h:78
void heap_fill_tuple(TupleDesc tupleDesc, Datum *values, bool *isnull, char *data, Size data_size, uint16 *infomask, bits8 *bit)
Definition: heaptuple.c:146
#define SizeOfBrinTuple
Definition: brin_tuple.h:66
#define BrinTupleHasNulls(tup)
Definition: brin_tuple.h:77
#define att_align_nominal(cur_offset, attalign)
Definition: tupmacs.h:144
#define att_isnull(ATT, BITS)
Definition: tupmacs.h:21
BlockNumber bt_blkno
Definition: brin_tuple.h:39
Form_pg_attribute * attrs
Definition: tupdesc.h:74
bool bv_allnulls
Definition: brin_tuple.h:28
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
BrinMemTuple * brin_deform_tuple(BrinDesc *brdesc, BrinTuple *tuple)
Definition: brin_tuple.c:398
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
uint32 BlockNumber
Definition: block.h:31
#define BITMAPLEN(NATTS)
Definition: htup_details.h:548
BrinTuple * brin_copy_tuple(BrinTuple *tuple, Size len)
Definition: brin_tuple.c:317
BrinMemTuple * brin_new_memtuple(BrinDesc *brdesc)
Definition: brin_tuple.c:348
int16 typlen
Definition: typcache.h:35
bool typbyval
Definition: typcache.h:36
int natts
Definition: tupdesc.h:73
#define fetchatt(A, T)
Definition: tupmacs.h:37
unsigned short uint16
Definition: c.h:264
void pfree(void *pointer)
Definition: mcxt.c:992
static TupleDesc brtuple_disk_tupdesc(BrinDesc *brdesc)
Definition: brin_tuple.c:51
bool bt_placeholder
Definition: brin_tuple.h:38
bool bv_hasnulls
Definition: brin_tuple.h:27
TypeCacheEntry * oi_typcache[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_internal.h:34
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:145
AttrNumber bv_attno
Definition: brin_tuple.h:26
uint16 oi_nstored
Definition: brin_internal.h:28
int bd_totalstored
Definition: brin_internal.h:56
static void brin_deconstruct_tuple(BrinDesc *brdesc, char *tp, bits8 *nullbits, bool nulls, Datum *values, bool *allnulls, bool *hasnulls)
Definition: brin_tuple.c:484
bool brin_tuples_equal(const BrinTuple *a, Size alen, const BrinTuple *b, Size blen)
Definition: brin_tuple.c:331
BrinValues bt_columns[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_tuple.h:41
#define BRIN_NULLS_MASK
Definition: brin_tuple.h:74
TupleDesc bd_tupdesc
Definition: brin_internal.h:50
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:184
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
void TupleDescInitEntry(TupleDesc desc, AttrNumber attributeNumber, const char *attributeName, Oid oidtypeid, int32 typmod, int attdim)
Definition: tupdesc.c:493
#define att_addlength_pointer(cur_offset, attlen, attptr)
Definition: tupmacs.h:172
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:128
#define HIGHBIT
Definition: c.h:968
#define BRIN_PLACEHOLDER_MASK
Definition: brin_tuple.h:73
uint8 bits8
Definition: c.h:272
MemoryContext AllocSetContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: aset.c:440
void * palloc0(Size size)
Definition: mcxt.c:920
void brin_memtuple_initialize(BrinMemTuple *dtuple, BrinDesc *brdesc)
Definition: brin_tuple.c:378
uintptr_t Datum
Definition: postgres.h:374
#define att_align_pointer(cur_offset, attalign, attlen, attptr)
Definition: tupmacs.h:122
BrinOpcInfo * bd_info[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_internal.h:59
BlockNumber bt_blkno
Definition: brin_tuple.h:52
void brin_free_tuple(BrinTuple *tuple)
Definition: brin_tuple.c:308
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
size_t Size
Definition: c.h:353
#define MAXALIGN(LEN)
Definition: c.h:584
TupleDesc CreateTemplateTupleDesc(int natts, bool hasoid)
Definition: tupdesc.c:41
Size heap_compute_data_size(TupleDesc tupleDesc, Datum *values, bool *isnull)
Definition: heaptuple.c:85
MemoryContext bd_context
Definition: brin_internal.h:44
static Datum values[MAXATTR]
Definition: bootstrap.c:162
uint8 bt_info
Definition: brin_tuple.h:63
void * palloc(Size size)
Definition: mcxt.c:891
TupleDesc bd_disktdesc
Definition: brin_internal.h:53
BrinTuple * brin_form_tuple(BrinDesc *brdesc, BlockNumber blkno, BrinMemTuple *tuple, Size *size)
Definition: brin_tuple.c:89
#define BrinTupleDataOffset(tup)
Definition: brin_tuple.h:76
int i
Datum * bv_values
Definition: brin_tuple.h:29
BrinTuple * brin_form_placeholder_tuple(BrinDesc *brdesc, BlockNumber blkno, Size *size)
Definition: brin_tuple.c:263
int16 AttrNumber
Definition: attnum.h:21
MemoryContext bt_context
Definition: brin_tuple.h:40