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