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