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