PostgreSQL Source Code  git master
blscan.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * blscan.c
4  * Bloom index scan functions.
5  *
6  * Copyright (c) 2016-2017, PostgreSQL Global Development Group
7  *
8  * IDENTIFICATION
9  * contrib/bloom/blscan.c
10  *
11  *-------------------------------------------------------------------------
12  */
13 #include "postgres.h"
14 
15 #include "access/relscan.h"
16 #include "pgstat.h"
17 #include "miscadmin.h"
18 #include "storage/bufmgr.h"
19 #include "storage/lmgr.h"
20 #include "utils/memutils.h"
21 #include "utils/rel.h"
22 
23 #include "bloom.h"
24 
25 /*
26  * Begin scan of bloom index.
27  */
29 blbeginscan(Relation r, int nkeys, int norderbys)
30 {
31  IndexScanDesc scan;
32  BloomScanOpaque so;
33 
34  scan = RelationGetIndexScan(r, nkeys, norderbys);
35 
37  initBloomState(&so->state, scan->indexRelation);
38  so->sign = NULL;
39 
40  scan->opaque = so;
41 
42  return scan;
43 }
44 
45 /*
46  * Rescan a bloom index.
47  */
48 void
49 blrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
50  ScanKey orderbys, int norderbys)
51 {
53 
54  if (so->sign)
55  pfree(so->sign);
56  so->sign = NULL;
57 
58  if (scankey && scan->numberOfKeys > 0)
59  {
60  memmove(scan->keyData, scankey,
61  scan->numberOfKeys * sizeof(ScanKeyData));
62  }
63 }
64 
65 /*
66  * End scan of bloom index.
67  */
68 void
70 {
72 
73  if (so->sign)
74  pfree(so->sign);
75  so->sign = NULL;
76 }
77 
78 /*
79  * Insert all matching tuples into to a bitmap.
80  */
81 int64
83 {
84  int64 ntids = 0;
86  npages;
87  int i;
90 
91  if (so->sign == NULL)
92  {
93  /* New search: have to calculate search signature */
94  ScanKey skey = scan->keyData;
95 
96  so->sign = palloc0(sizeof(BloomSignatureWord) * so->state.opts.bloomLength);
97 
98  for (i = 0; i < scan->numberOfKeys; i++)
99  {
100  /*
101  * Assume bloom-indexable operators to be strict, so nothing could
102  * be found for NULL key.
103  */
104  if (skey->sk_flags & SK_ISNULL)
105  {
106  pfree(so->sign);
107  so->sign = NULL;
108  return 0;
109  }
110 
111  /* Add next value to the signature */
112  signValue(&so->state, so->sign, skey->sk_argument,
113  skey->sk_attno - 1);
114 
115  skey++;
116  }
117  }
118 
119  /*
120  * We're going to read the whole index. This is why we use appropriate
121  * buffer access strategy.
122  */
125 
126  for (blkno = BLOOM_HEAD_BLKNO; blkno < npages; blkno++)
127  {
128  Buffer buffer;
129  Page page;
130 
132  blkno, RBM_NORMAL, bas);
133 
134  LockBuffer(buffer, BUFFER_LOCK_SHARE);
135  page = BufferGetPage(buffer);
136  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
137 
138  if (!PageIsNew(page) && !BloomPageIsDeleted(page))
139  {
140  OffsetNumber offset,
141  maxOffset = BloomPageGetMaxOffset(page);
142 
143  for (offset = 1; offset <= maxOffset; offset++)
144  {
145  BloomTuple *itup = BloomPageGetTuple(&so->state, page, offset);
146  bool res = true;
147 
148  /* Check index signature with scan signature */
149  for (i = 0; i < so->state.opts.bloomLength; i++)
150  {
151  if ((itup->sign[i] & so->sign[i]) != so->sign[i])
152  {
153  res = false;
154  break;
155  }
156  }
157 
158  /* Add matching tuples to bitmap */
159  if (res)
160  {
161  tbm_add_tuples(tbm, &itup->heapPtr, 1, true);
162  ntids++;
163  }
164  }
165  }
166 
167  UnlockReleaseBuffer(buffer);
169  }
170  FreeAccessStrategy(bas);
171 
172  return ntids;
173 }
BufferAccessStrategy GetAccessStrategy(BufferAccessStrategyType btype)
Definition: freelist.c:542
#define BloomPageIsDeleted(page)
Definition: bloom.h:63
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:265
BloomOptions opts
Definition: bloom.h:140
void initBloomState(BloomState *state, Relation index)
Definition: blutils.c:153
void signValue(BloomState *state, BloomSignatureWord *sign, Datum value, int attno)
Definition: blutils.c:251
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:640
Snapshot xs_snapshot
Definition: relscan.h:91
uint32 BlockNumber
Definition: block.h:31
#define BLOOM_HEAD_BLKNO
Definition: bloom.h:78
Relation indexRelation
Definition: relscan.h:90
uint16 OffsetNumber
Definition: off.h:24
int64 blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: blscan.c:82
uint16 BloomSignatureWord
Definition: bloom.h:83
void pfree(void *pointer)
Definition: mcxt.c:949
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
void blendscan(IndexScanDesc scan)
Definition: blscan.c:69
#define memmove(d, s, c)
Definition: c.h:1045
IndexScanDesc blbeginscan(Relation r, int nkeys, int norderbys)
Definition: blscan.c:29
#define BloomPageGetTuple(state, page, offset)
Definition: bloom.h:70
#define SK_ISNULL
Definition: skey.h:115
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
void * palloc0(Size size)
Definition: mcxt.c:877
BloomState state
Definition: bloom.h:170
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:199
void blrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: blscan.c:49
void FreeAccessStrategy(BufferAccessStrategy strategy)
Definition: freelist.c:597
int sk_flags
Definition: skey.h:66
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:214
ScanKey keyData
Definition: relscan.h:94
BloomSignatureWord sign[FLEXIBLE_ARRAY_MEMBER]
Definition: bloom.h:161
int bloomLength
Definition: bloom.h:103
ItemPointerData heapPtr
Definition: bloom.h:160
#define PageIsNew(page)
Definition: bufpage.h:225
#define BloomPageGetMaxOffset(page)
Definition: bloom.h:60
void * palloc(Size size)
Definition: mcxt.c:848
int i
BloomScanOpaqueData * BloomScanOpaque
Definition: bloom.h:173
BloomSignatureWord * sign
Definition: bloom.h:169
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:88
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:78
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
int Buffer
Definition: buf.h:23
Datum sk_argument
Definition: skey.h:72
AttrNumber sk_attno
Definition: skey.h:67
Pointer Page
Definition: bufpage.h:74