PostgreSQL Source Code  git master
bloom.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * bloom.h
4  * Header for bloom index.
5  *
6  * Copyright (c) 2016-2023, PostgreSQL Global Development Group
7  *
8  * IDENTIFICATION
9  * contrib/bloom/bloom.h
10  *
11  *-------------------------------------------------------------------------
12  */
13 #ifndef _BLOOM_H_
14 #define _BLOOM_H_
15 
16 #include "access/amapi.h"
17 #include "access/generic_xlog.h"
18 #include "access/itup.h"
19 #include "access/xlog.h"
20 #include "fmgr.h"
21 #include "nodes/pathnodes.h"
22 
23 /* Support procedures numbers */
24 #define BLOOM_HASH_PROC 1
25 #define BLOOM_OPTIONS_PROC 2
26 #define BLOOM_NPROC 2
27 
28 /* Scan strategies */
29 #define BLOOM_EQUAL_STRATEGY 1
30 #define BLOOM_NSTRATEGIES 1
31 
32 /* Opaque for bloom pages */
33 typedef struct BloomPageOpaqueData
34 {
35  OffsetNumber maxoff; /* number of index tuples on page */
36  uint16 flags; /* see bit definitions below */
37  uint16 unused; /* placeholder to force maxaligning of size of
38  * BloomPageOpaqueData and to place
39  * bloom_page_id exactly at the end of page */
40  uint16 bloom_page_id; /* for identification of BLOOM indexes */
42 
44 
45 /* Bloom page flags */
46 #define BLOOM_META (1<<0)
47 #define BLOOM_DELETED (2<<0)
48 
49 /*
50  * The page ID is for the convenience of pg_filedump and similar utilities,
51  * which otherwise would have a hard time telling pages of different index
52  * types apart. It should be the last 2 bytes on the page. This is more or
53  * less "free" due to alignment considerations.
54  *
55  * See comments above GinPageOpaqueData.
56  */
57 #define BLOOM_PAGE_ID 0xFF83
58 
59 /* Macros for accessing bloom page structures */
60 #define BloomPageGetOpaque(page) ((BloomPageOpaque) PageGetSpecialPointer(page))
61 #define BloomPageGetMaxOffset(page) (BloomPageGetOpaque(page)->maxoff)
62 #define BloomPageIsMeta(page) \
63  ((BloomPageGetOpaque(page)->flags & BLOOM_META) != 0)
64 #define BloomPageIsDeleted(page) \
65  ((BloomPageGetOpaque(page)->flags & BLOOM_DELETED) != 0)
66 #define BloomPageSetDeleted(page) \
67  (BloomPageGetOpaque(page)->flags |= BLOOM_DELETED)
68 #define BloomPageSetNonDeleted(page) \
69  (BloomPageGetOpaque(page)->flags &= ~BLOOM_DELETED)
70 #define BloomPageGetData(page) ((BloomTuple *)PageGetContents(page))
71 #define BloomPageGetTuple(state, page, offset) \
72  ((BloomTuple *)(PageGetContents(page) \
73  + (state)->sizeOfBloomTuple * ((offset) - 1)))
74 #define BloomPageGetNextTuple(state, tuple) \
75  ((BloomTuple *)((Pointer)(tuple) + (state)->sizeOfBloomTuple))
76 
77 /* Preserved page numbers */
78 #define BLOOM_METAPAGE_BLKNO (0)
79 #define BLOOM_HEAD_BLKNO (1) /* first data page */
80 
81 /*
82  * We store Bloom signatures as arrays of uint16 words.
83  */
85 
86 #define SIGNWORDBITS ((int) (BITS_PER_BYTE * sizeof(BloomSignatureWord)))
87 
88 /*
89  * Default and maximum Bloom signature length in bits.
90  */
91 #define DEFAULT_BLOOM_LENGTH (5 * SIGNWORDBITS)
92 #define MAX_BLOOM_LENGTH (256 * SIGNWORDBITS)
93 
94 /*
95  * Default and maximum signature bits generated per index key.
96  */
97 #define DEFAULT_BLOOM_BITS 2
98 #define MAX_BLOOM_BITS (MAX_BLOOM_LENGTH - 1)
99 
100 /* Bloom index options */
101 typedef struct BloomOptions
102 {
103  int32 vl_len_; /* varlena header (do not touch directly!) */
104  int bloomLength; /* length of signature in words (not bits!) */
105  int bitSize[INDEX_MAX_KEYS]; /* # of bits generated for each
106  * index key */
108 
109 /*
110  * FreeBlockNumberArray - array of block numbers sized so that metadata fill
111  * all space in metapage.
112  */
116  - MAXALIGN(sizeof(uint16) * 2 + sizeof(uint32) + sizeof(BloomOptions))
117  ) / sizeof(BlockNumber)
118 ];
119 
120 /* Metadata of bloom index */
121 typedef struct BloomMetaPageData
122 {
129 
130 /* Magic number to distinguish bloom pages among anothers */
131 #define BLOOM_MAGICK_NUMBER (0xDBAC0DED)
132 
133 /* Number of blocks numbers fit in BloomMetaPageData */
134 #define BloomMetaBlockN (sizeof(FreeBlockNumberArray) / sizeof(BlockNumber))
135 
136 #define BloomPageGetMeta(page) ((BloomMetaPageData *) PageGetContents(page))
137 
138 typedef struct BloomState
139 {
142  BloomOptions opts; /* copy of options on index's metapage */
144 
145  /*
146  * sizeOfBloomTuple is index-specific, and it depends on reloptions, so
147  * precompute it
148  */
151 
152 #define BloomPageGetFreeSpace(state, page) \
153  (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) \
154  - BloomPageGetMaxOffset(page) * (state)->sizeOfBloomTuple \
155  - MAXALIGN(sizeof(BloomPageOpaqueData)))
156 
157 /*
158  * Tuples are very different from all other relations
159  */
160 typedef struct BloomTuple
161 {
165 
166 #define BLOOMTUPLEHDRSZ offsetof(BloomTuple, sign)
167 
168 /* Opaque data structure for bloom index scan */
169 typedef struct BloomScanOpaqueData
170 {
171  BloomSignatureWord *sign; /* Scan signature */
174 
176 
177 /* blutils.c */
179 extern void BloomFillMetapage(Relation index, Page metaPage);
180 extern void BloomInitMetapage(Relation index);
181 extern void BloomInitPage(Page page, uint16 flags);
183 extern void signValue(BloomState *state, BloomSignatureWord *sign, Datum value, int attno);
184 extern BloomTuple *BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull);
185 extern bool BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple);
186 
187 /* blvalidate.c */
188 extern bool blvalidate(Oid opclassoid);
189 
190 /* index access method interface functions */
191 extern bool blinsert(Relation index, Datum *values, bool *isnull,
192  ItemPointer ht_ctid, Relation heapRel,
193  IndexUniqueCheck checkUnique,
194  bool indexUnchanged,
195  struct IndexInfo *indexInfo);
196 extern IndexScanDesc blbeginscan(Relation r, int nkeys, int norderbys);
197 extern int64 blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
198 extern void blrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
199  ScanKey orderbys, int norderbys);
200 extern void blendscan(IndexScanDesc scan);
202  struct IndexInfo *indexInfo);
203 extern void blbuildempty(Relation index);
206  void *callback_state);
208  IndexBulkDeleteResult *stats);
209 extern bytea *bloptions(Datum reloptions, bool validate);
210 extern void blcostestimate(PlannerInfo *root, IndexPath *path,
211  double loop_count, Cost *indexStartupCost,
212  Cost *indexTotalCost, Selectivity *indexSelectivity,
213  double *indexCorrelation, double *indexPages);
214 
215 #endif
uint32 BlockNumber
Definition: block.h:31
bytea * bloptions(Datum reloptions, bool validate)
Definition: blutils.c:481
BlockNumber FreeBlockNumberArray[MAXALIGN_DOWN(BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(BloomPageOpaqueData)) - MAXALIGN(sizeof(uint16) *2+sizeof(uint32)+sizeof(BloomOptions)))/sizeof(BlockNumber)]
Definition: bloom.h:118
BloomTuple * BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull)
Definition: blutils.c:293
void BloomInitMetapage(Relation index)
Definition: blutils.c:454
bool blvalidate(Oid opclassoid)
Definition: blvalidate.c:32
void BloomInitPage(Page page, uint16 flags)
Definition: blutils.c:407
int64 blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: blscan.c:81
IndexScanDesc blbeginscan(Relation r, int nkeys, int norderbys)
Definition: blscan.c:28
bool BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple)
Definition: blutils.c:318
void blcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
Definition: blcost.c:23
IndexBuildResult * blbuild(Relation heap, Relation index, struct IndexInfo *indexInfo)
Definition: blinsert.c:121
void blbuildempty(Relation index)
Definition: blinsert.c:164
BloomPageOpaqueData * BloomPageOpaque
Definition: bloom.h:43
struct BloomMetaPageData BloomMetaPageData
struct BloomOptions BloomOptions
Buffer BloomNewBuffer(Relation index)
Definition: blutils.c:353
struct BloomPageOpaqueData BloomPageOpaqueData
void BloomFillMetapage(Relation index, Page metaPage)
Definition: blutils.c:422
bool blinsert(Relation index, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, struct IndexInfo *indexInfo)
Definition: blinsert.c:197
struct BloomState BloomState
IndexBulkDeleteResult * blbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
Definition: blvacuum.c:34
struct BloomTuple BloomTuple
uint16 BloomSignatureWord
Definition: bloom.h:84
void signValue(BloomState *state, BloomSignatureWord *sign, Datum value, int attno)
Definition: blutils.c:260
void initBloomState(BloomState *state, Relation index)
Definition: blutils.c:161
IndexBulkDeleteResult * blvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
Definition: blvacuum.c:169
BloomScanOpaqueData * BloomScanOpaque
Definition: bloom.h:175
struct BloomScanOpaqueData BloomScanOpaqueData
void blendscan(IndexScanDesc scan)
Definition: blscan.c:68
void blrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: blscan.c:48
static Datum values[MAXATTR]
Definition: bootstrap.c:156
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:78
#define SizeOfPageHeaderData
Definition: bufpage.h:213
unsigned short uint16
Definition: c.h:489
unsigned int uint32
Definition: c.h:490
#define MAXALIGN_DOWN(LEN)
Definition: c.h:807
#define MAXALIGN(LEN)
Definition: c.h:795
signed int int32
Definition: c.h:478
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:382
size_t Size
Definition: c.h:589
bool(* IndexBulkDeleteCallback)(ItemPointer itemptr, void *state)
Definition: genam.h:86
IndexUniqueCheck
Definition: genam.h:115
static struct @143 value
char sign
Definition: informix.c:668
double Cost
Definition: nodes.h:251
double Selectivity
Definition: nodes.h:250
uint16 OffsetNumber
Definition: off.h:24
#define INDEX_MAX_KEYS
uintptr_t Datum
Definition: postgres.h:64
unsigned int Oid
Definition: postgres_ext.h:31
FreeBlockNumberArray notFullPage
Definition: bloom.h:127
BloomOptions opts
Definition: bloom.h:126
uint32 magickNumber
Definition: bloom.h:123
uint16 nEnd
Definition: bloom.h:125
uint16 nStart
Definition: bloom.h:124
int32 vl_len_
Definition: bloom.h:103
int bloomLength
Definition: bloom.h:104
int bitSize[INDEX_MAX_KEYS]
Definition: bloom.h:105
OffsetNumber maxoff
Definition: bloom.h:35
uint16 flags
Definition: bloom.h:36
uint16 unused
Definition: bloom.h:37
uint16 bloom_page_id
Definition: bloom.h:40
BloomSignatureWord * sign
Definition: bloom.h:171
BloomState state
Definition: bloom.h:172
BloomOptions opts
Definition: bloom.h:142
Size sizeOfBloomTuple
Definition: bloom.h:149
Oid collations[INDEX_MAX_KEYS]
Definition: bloom.h:141
int32 nColumns
Definition: bloom.h:143
FmgrInfo hashFn[INDEX_MAX_KEYS]
Definition: bloom.h:140
BloomSignatureWord sign[FLEXIBLE_ARRAY_MEMBER]
Definition: bloom.h:163
ItemPointerData heapPtr
Definition: bloom.h:162
Definition: fmgr.h:57
Definition: type.h:95
Definition: regguts.h:318
Definition: c.h:671
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:46