1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
|
/*--------------------------------------------------------------------------
* gin_private.h
* header file for postgres inverted index access method implementation.
*
* Copyright (c) 2006-2017, PostgreSQL Global Development Group
*
* src/include/access/gin_private.h
*--------------------------------------------------------------------------
*/
#ifndef GIN_PRIVATE_H
#define GIN_PRIVATE_H
#include "access/amapi.h"
#include "access/gin.h"
#include "access/ginblock.h"
#include "access/itup.h"
#include "fmgr.h"
#include "storage/bufmgr.h"
#include "lib/rbtree.h"
/*
* Storage type for GIN's reloptions
*/
typedef struct GinOptions
{
int32 vl_len_; /* varlena header (do not touch directly!) */
bool useFastUpdate; /* use fast updates? */
int pendingListCleanupSize; /* maximum size of pending list */
} GinOptions;
#define GIN_DEFAULT_USE_FASTUPDATE true
#define GinGetUseFastUpdate(relation) \
((relation)->rd_options ? \
((GinOptions *) (relation)->rd_options)->useFastUpdate : GIN_DEFAULT_USE_FASTUPDATE)
#define GinGetPendingListCleanupSize(relation) \
((relation)->rd_options && \
((GinOptions *) (relation)->rd_options)->pendingListCleanupSize != -1 ? \
((GinOptions *) (relation)->rd_options)->pendingListCleanupSize : \
gin_pending_list_limit)
/* Macros for buffer lock/unlock operations */
#define GIN_UNLOCK BUFFER_LOCK_UNLOCK
#define GIN_SHARE BUFFER_LOCK_SHARE
#define GIN_EXCLUSIVE BUFFER_LOCK_EXCLUSIVE
/*
* GinState: working data structure describing the index being worked on
*/
typedef struct GinState
{
Relation index;
bool oneCol; /* true if single-column index */
/*
* origTupDesc is the nominal tuple descriptor of the index, ie, the i'th
* attribute shows the key type (not the input data type!) of the i'th
* index column. In a single-column index this describes the actual leaf
* index tuples. In a multi-column index, the actual leaf tuples contain
* a smallint column number followed by a key datum of the appropriate
* type for that column. We set up tupdesc[i] to describe the actual
* rowtype of the index tuples for the i'th column, ie, (int2, keytype).
* Note that in any case, leaf tuples contain more data than is known to
* the TupleDesc; see access/gin/README for details.
*/
TupleDesc origTupdesc;
TupleDesc tupdesc[INDEX_MAX_KEYS];
/*
* Per-index-column opclass support functions
*/
FmgrInfo compareFn[INDEX_MAX_KEYS];
FmgrInfo extractValueFn[INDEX_MAX_KEYS];
FmgrInfo extractQueryFn[INDEX_MAX_KEYS];
FmgrInfo consistentFn[INDEX_MAX_KEYS];
FmgrInfo triConsistentFn[INDEX_MAX_KEYS];
FmgrInfo comparePartialFn[INDEX_MAX_KEYS]; /* optional method */
/* canPartialMatch[i] is true if comparePartialFn[i] is valid */
bool canPartialMatch[INDEX_MAX_KEYS];
/* Collations to pass to the support functions */
Oid supportCollation[INDEX_MAX_KEYS];
} GinState;
/* ginutil.c */
extern bytea *ginoptions(Datum reloptions, bool validate);
extern void initGinState(GinState *state, Relation index);
extern Buffer GinNewBuffer(Relation index);
extern void GinInitBuffer(Buffer b, uint32 f);
extern void GinInitPage(Page page, uint32 f, Size pageSize);
extern void GinInitMetabuffer(Buffer b);
extern int ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
Datum a, GinNullCategory categorya,
Datum b, GinNullCategory categoryb);
extern int ginCompareAttEntries(GinState *ginstate,
OffsetNumber attnuma, Datum a, GinNullCategory categorya,
OffsetNumber attnumb, Datum b, GinNullCategory categoryb);
extern Datum *ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
Datum value, bool isNull,
int32 *nentries, GinNullCategory **categories);
extern OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple);
extern Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple,
GinNullCategory *category);
/* gininsert.c */
extern IndexBuildResult *ginbuild(Relation heap, Relation index,
struct IndexInfo *indexInfo);
extern void ginbuildempty(Relation index);
extern bool gininsert(Relation index, Datum *values, bool *isnull,
ItemPointer ht_ctid, Relation heapRel,
IndexUniqueCheck checkUnique,
struct IndexInfo *indexInfo);
extern void ginEntryInsert(GinState *ginstate,
OffsetNumber attnum, Datum key, GinNullCategory category,
ItemPointerData *items, uint32 nitem,
GinStatsData *buildStats);
/* ginbtree.c */
typedef struct GinBtreeStack
{
BlockNumber blkno;
Buffer buffer;
OffsetNumber off;
ItemPointerData iptr;
/* predictNumber contains predicted number of pages on current level */
uint32 predictNumber;
struct GinBtreeStack *parent;
} GinBtreeStack;
typedef struct GinBtreeData *GinBtree;
/* Return codes for GinBtreeData.beginPlaceToPage method */
typedef enum
{
GPTP_NO_WORK,
GPTP_INSERT,
GPTP_SPLIT
} GinPlaceToPageRC;
typedef struct GinBtreeData
{
/* search methods */
BlockNumber (*findChildPage) (GinBtree, GinBtreeStack *);
BlockNumber (*getLeftMostChild) (GinBtree, Page);
bool (*isMoveRight) (GinBtree, Page);
bool (*findItem) (GinBtree, GinBtreeStack *);
/* insert methods */
OffsetNumber (*findChildPtr) (GinBtree, Page, BlockNumber, OffsetNumber);
GinPlaceToPageRC (*beginPlaceToPage) (GinBtree, Buffer, GinBtreeStack *, void *, BlockNumber, void **, Page *, Page *);
void (*execPlaceToPage) (GinBtree, Buffer, GinBtreeStack *, void *, BlockNumber, void *);
void *(*prepareDownlink) (GinBtree, Buffer);
void (*fillRoot) (GinBtree, Page, BlockNumber, Page, BlockNumber, Page);
bool isData;
Relation index;
BlockNumber rootBlkno;
GinState *ginstate; /* not valid in a data scan */
bool fullScan;
bool isBuild;
/* Search key for Entry tree */
OffsetNumber entryAttnum;
Datum entryKey;
GinNullCategory entryCategory;
/* Search key for data tree (posting tree) */
ItemPointerData itemptr;
} GinBtreeData;
/* This represents a tuple to be inserted to entry tree. */
typedef struct
{
IndexTuple entry; /* tuple to insert */
bool isDelete; /* delete old tuple at same offset? */
} GinBtreeEntryInsertData;
/*
* This represents an itempointer, or many itempointers, to be inserted to
* a data (posting tree) leaf page
*/
typedef struct
{
ItemPointerData *items;
uint32 nitem;
uint32 curitem;
} GinBtreeDataLeafInsertData;
/*
* For internal data (posting tree) pages, the insertion payload is a
* PostingItem
*/
extern GinBtreeStack *ginFindLeafPage(GinBtree btree, bool searchMode, Snapshot snapshot);
extern Buffer ginStepRight(Buffer buffer, Relation index, int lockmode);
extern void freeGinBtreeStack(GinBtreeStack *stack);
extern void ginInsertValue(GinBtree btree, GinBtreeStack *stack,
void *insertdata, GinStatsData *buildStats);
/* ginentrypage.c */
extern IndexTuple GinFormTuple(GinState *ginstate,
OffsetNumber attnum, Datum key, GinNullCategory category,
Pointer data, Size dataSize, int nipd, bool errorTooBig);
extern void ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum,
Datum key, GinNullCategory category,
GinState *ginstate);
extern void ginEntryFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage);
extern ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum,
IndexTuple itup, int *nitems);
/* gindatapage.c */
extern ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast);
extern int GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm);
extern BlockNumber createPostingTree(Relation index,
ItemPointerData *items, uint32 nitems,
GinStatsData *buildStats);
extern void GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset);
extern void GinPageDeletePostingItem(Page page, OffsetNumber offset);
extern void ginInsertItemPointers(Relation index, BlockNumber rootBlkno,
ItemPointerData *items, uint32 nitem,
GinStatsData *buildStats);
extern GinBtreeStack *ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno, Snapshot snapshot);
extern void ginDataFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage);
extern void ginPrepareDataScan(GinBtree btree, Relation index, BlockNumber rootBlkno);
/*
* This is declared in ginvacuum.c, but is passed between ginVacuumItemPointers
* and ginVacuumPostingTreeLeaf and as an opaque struct, so we need a forward
* declaration for it.
*/
typedef struct GinVacuumState GinVacuumState;
extern void ginVacuumPostingTreeLeaf(Relation rel, Buffer buf, GinVacuumState *gvs);
/* ginscan.c */
/*
* GinScanKeyData describes a single GIN index qualifier expression.
*
* From each qual expression, we extract one or more specific index search
* conditions, which are represented by GinScanEntryData. It's quite
* possible for identical search conditions to be requested by more than
* one qual expression, in which case we merge such conditions to have just
* one unique GinScanEntry --- this is particularly important for efficiency
* when dealing with full-index-scan entries. So there can be multiple
* GinScanKeyData.scanEntry pointers to the same GinScanEntryData.
*
* In each GinScanKeyData, nentries is the true number of entries, while
* nuserentries is the number that extractQueryFn returned (which is what
* we report to consistentFn). The "user" entries must come first.
*/
typedef struct GinScanKeyData *GinScanKey;
typedef struct GinScanEntryData *GinScanEntry;
typedef struct GinScanKeyData
{
/* Real number of entries in scanEntry[] (always > 0) */
uint32 nentries;
/* Number of entries that extractQueryFn and consistentFn know about */
uint32 nuserentries;
/* array of GinScanEntry pointers, one per extracted search condition */
GinScanEntry *scanEntry;
/*
* At least one of the entries in requiredEntries must be present for a
* tuple to match the overall qual.
*
* additionalEntries contains entries that are needed by the consistent
* function to decide if an item matches, but are not sufficient to
* satisfy the qual without entries from requiredEntries.
*/
GinScanEntry *requiredEntries;
int nrequired;
GinScanEntry *additionalEntries;
int nadditional;
/* array of check flags, reported to consistentFn */
GinTernaryValue *entryRes;
bool (*boolConsistentFn) (GinScanKey key);
GinTernaryValue (*triConsistentFn) (GinScanKey key);
FmgrInfo *consistentFmgrInfo;
FmgrInfo *triConsistentFmgrInfo;
Oid collation;
/* other data needed for calling consistentFn */
Datum query;
/* NB: these three arrays have only nuserentries elements! */
Datum *queryValues;
GinNullCategory *queryCategories;
Pointer *extra_data;
StrategyNumber strategy;
int32 searchMode;
OffsetNumber attnum;
/*
* Match status data. curItem is the TID most recently tested (could be a
* lossy-page pointer). curItemMatches is TRUE if it passes the
* consistentFn test; if so, recheckCurItem is the recheck flag.
* isFinished means that all the input entry streams are finished, so this
* key cannot succeed for any later TIDs.
*/
ItemPointerData curItem;
bool curItemMatches;
bool recheckCurItem;
bool isFinished;
} GinScanKeyData;
typedef struct GinScanEntryData
{
/* query key and other information from extractQueryFn */
Datum queryKey;
GinNullCategory queryCategory;
bool isPartialMatch;
Pointer extra_data;
StrategyNumber strategy;
int32 searchMode;
OffsetNumber attnum;
/* Current page in posting tree */
Buffer buffer;
/* current ItemPointer to heap */
ItemPointerData curItem;
/* for a partial-match or full-scan query, we accumulate all TIDs here */
TIDBitmap *matchBitmap;
TBMIterator *matchIterator;
TBMIterateResult *matchResult;
/* used for Posting list and one page in Posting tree */
ItemPointerData *list;
int nlist;
OffsetNumber offset;
bool isFinished;
bool reduceResult;
uint32 predictNumberResult;
GinBtreeData btree;
} GinScanEntryData;
typedef struct GinScanOpaqueData
{
MemoryContext tempCtx;
GinState ginstate;
GinScanKey keys; /* one per scan qualifier expr */
uint32 nkeys;
GinScanEntry *entries; /* one per index search condition */
uint32 totalentries;
uint32 allocentries; /* allocated length of entries[] */
MemoryContext keyCtx; /* used to hold key and entry data */
bool isVoidRes; /* true if query is unsatisfiable */
} GinScanOpaqueData;
typedef GinScanOpaqueData *GinScanOpaque;
extern IndexScanDesc ginbeginscan(Relation rel, int nkeys, int norderbys);
extern void ginendscan(IndexScanDesc scan);
extern void ginrescan(IndexScanDesc scan, ScanKey key, int nscankeys,
ScanKey orderbys, int norderbys);
extern void ginNewScanKey(IndexScanDesc scan);
extern void ginFreeScanKeys(GinScanOpaque so);
/* ginget.c */
extern int64 gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
/* ginlogic.c */
extern void ginInitConsistentFunction(GinState *ginstate, GinScanKey key);
/* ginvacuum.c */
extern IndexBulkDeleteResult *ginbulkdelete(IndexVacuumInfo *info,
IndexBulkDeleteResult *stats,
IndexBulkDeleteCallback callback,
void *callback_state);
extern IndexBulkDeleteResult *ginvacuumcleanup(IndexVacuumInfo *info,
IndexBulkDeleteResult *stats);
extern ItemPointer ginVacuumItemPointers(GinVacuumState *gvs,
ItemPointerData *items, int nitem, int *nremaining);
/* ginvalidate.c */
extern bool ginvalidate(Oid opclassoid);
/* ginbulk.c */
typedef struct GinEntryAccumulator
{
RBNode rbnode;
Datum key;
GinNullCategory category;
OffsetNumber attnum;
bool shouldSort;
ItemPointerData *list;
uint32 maxcount; /* allocated size of list[] */
uint32 count; /* current number of list[] entries */
} GinEntryAccumulator;
typedef struct
{
GinState *ginstate;
Size allocatedMemory;
GinEntryAccumulator *entryallocator;
uint32 eas_used;
RBTree *tree;
RBTreeIterator tree_walk;
} BuildAccumulator;
extern void ginInitBA(BuildAccumulator *accum);
extern void ginInsertBAEntries(BuildAccumulator *accum,
ItemPointer heapptr, OffsetNumber attnum,
Datum *entries, GinNullCategory *categories,
int32 nentries);
extern void ginBeginBAScan(BuildAccumulator *accum);
extern ItemPointerData *ginGetBAEntry(BuildAccumulator *accum,
OffsetNumber *attnum, Datum *key, GinNullCategory *category,
uint32 *n);
/* ginfast.c */
typedef struct GinTupleCollector
{
IndexTuple *tuples;
uint32 ntuples;
uint32 lentuples;
uint32 sumsize;
} GinTupleCollector;
extern void ginHeapTupleFastInsert(GinState *ginstate,
GinTupleCollector *collector);
extern void ginHeapTupleFastCollect(GinState *ginstate,
GinTupleCollector *collector,
OffsetNumber attnum, Datum value, bool isNull,
ItemPointer ht_ctid);
extern void ginInsertCleanup(GinState *ginstate, bool full_clean,
bool fill_fsm, IndexBulkDeleteResult *stats);
/* ginpostinglist.c */
extern GinPostingList *ginCompressPostingList(const ItemPointer ptrs, int nptrs,
int maxsize, int *nwritten);
extern int ginPostingListDecodeAllSegmentsToTbm(GinPostingList *ptr, int totalsize, TIDBitmap *tbm);
extern ItemPointer ginPostingListDecodeAllSegments(GinPostingList *ptr, int len, int *ndecoded);
extern ItemPointer ginPostingListDecode(GinPostingList *ptr, int *ndecoded);
extern ItemPointer ginMergeItemPointers(ItemPointerData *a, uint32 na,
ItemPointerData *b, uint32 nb,
int *nmerged);
/*
* Merging the results of several gin scans compares item pointers a lot,
* so we want this to be inlined.
*/
static inline int
ginCompareItemPointers(ItemPointer a, ItemPointer b)
{
uint64 ia = (uint64) GinItemPointerGetBlockNumber(a) << 32 | GinItemPointerGetOffsetNumber(a);
uint64 ib = (uint64) GinItemPointerGetBlockNumber(b) << 32 | GinItemPointerGetOffsetNumber(b);
if (ia == ib)
return 0;
else if (ia > ib)
return 1;
else
return -1;
}
extern int ginTraverseLock(Buffer buffer, bool searchMode);
#endif /* GIN_PRIVATE_H */
|