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