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