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