Age Owner TLA Line data Source code
1 : /*--------------------------------------------------------------------------
2 : * gin_private.h
3 : * header file for postgres inverted index access method implementation.
4 : *
5 : * Copyright (c) 2006-2023, 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 indexrel, Buffer buffer,
244 : GinVacuumState *gvs);
245 :
246 : /* ginscan.c */
247 :
248 : /*
249 : * GinScanKeyData describes a single GIN index qualifier expression.
250 : *
251 : * From each qual expression, we extract one or more specific index search
252 : * conditions, which are represented by GinScanEntryData. It's quite
253 : * possible for identical search conditions to be requested by more than
254 : * one qual expression, in which case we merge such conditions to have just
255 : * one unique GinScanEntry --- this is particularly important for efficiency
256 : * when dealing with full-index-scan entries. So there can be multiple
257 : * GinScanKeyData.scanEntry pointers to the same GinScanEntryData.
258 : *
259 : * In each GinScanKeyData, nentries is the true number of entries, while
260 : * nuserentries is the number that extractQueryFn returned (which is what
261 : * we report to consistentFn). The "user" entries must come first.
262 : */
263 : typedef struct GinScanKeyData *GinScanKey;
264 :
265 : typedef struct GinScanEntryData *GinScanEntry;
266 :
267 : typedef struct GinScanKeyData
268 : {
269 : /* Real number of entries in scanEntry[] (always > 0) */
270 : uint32 nentries;
271 : /* Number of entries that extractQueryFn and consistentFn know about */
272 : uint32 nuserentries;
273 :
274 : /* array of GinScanEntry pointers, one per extracted search condition */
275 : GinScanEntry *scanEntry;
276 :
277 : /*
278 : * At least one of the entries in requiredEntries must be present for a
279 : * tuple to match the overall qual.
280 : *
281 : * additionalEntries contains entries that are needed by the consistent
282 : * function to decide if an item matches, but are not sufficient to
283 : * satisfy the qual without entries from requiredEntries.
284 : */
285 : GinScanEntry *requiredEntries;
286 : int nrequired;
287 : GinScanEntry *additionalEntries;
288 : int nadditional;
289 :
290 : /* array of check flags, reported to consistentFn */
291 : GinTernaryValue *entryRes;
292 : bool (*boolConsistentFn) (GinScanKey key);
293 : GinTernaryValue (*triConsistentFn) (GinScanKey key);
294 : FmgrInfo *consistentFmgrInfo;
295 : FmgrInfo *triConsistentFmgrInfo;
296 : Oid collation;
297 :
298 : /* other data needed for calling consistentFn */
299 : Datum query;
300 : /* NB: these three arrays have only nuserentries elements! */
301 : Datum *queryValues;
302 : GinNullCategory *queryCategories;
303 : Pointer *extra_data;
304 : StrategyNumber strategy;
305 : int32 searchMode;
306 : OffsetNumber attnum;
307 :
308 : /*
309 : * An excludeOnly scan key is not able to enumerate all matching tuples.
310 : * That is, to be semantically correct on its own, it would need to have a
311 : * GIN_CAT_EMPTY_QUERY scanEntry, but it doesn't. Such a key can still be
312 : * used to filter tuples returned by other scan keys, so we will get the
313 : * right answers as long as there's at least one non-excludeOnly scan key
314 : * for each index attribute considered by the search. For efficiency
315 : * reasons we don't want to have unnecessary GIN_CAT_EMPTY_QUERY entries,
316 : * so we will convert an excludeOnly scan key to non-excludeOnly (by
317 : * adding a GIN_CAT_EMPTY_QUERY scanEntry) only if there are no other
318 : * non-excludeOnly scan keys.
319 : */
320 : bool excludeOnly;
321 :
322 : /*
323 : * Match status data. curItem is the TID most recently tested (could be a
324 : * lossy-page pointer). curItemMatches is true if it passes the
325 : * consistentFn test; if so, recheckCurItem is the recheck flag.
326 : * isFinished means that all the input entry streams are finished, so this
327 : * key cannot succeed for any later TIDs.
328 : */
329 : ItemPointerData curItem;
330 : bool curItemMatches;
331 : bool recheckCurItem;
332 : bool isFinished;
333 : } GinScanKeyData;
334 :
335 : typedef struct GinScanEntryData
336 : {
337 : /* query key and other information from extractQueryFn */
338 : Datum queryKey;
339 : GinNullCategory queryCategory;
340 : bool isPartialMatch;
341 : Pointer extra_data;
342 : StrategyNumber strategy;
343 : int32 searchMode;
344 : OffsetNumber attnum;
345 :
346 : /* Current page in posting tree */
347 : Buffer buffer;
348 :
349 : /* current ItemPointer to heap */
350 : ItemPointerData curItem;
351 :
352 : /* for a partial-match or full-scan query, we accumulate all TIDs here */
353 : TIDBitmap *matchBitmap;
354 : TBMIterator *matchIterator;
355 : TBMIterateResult *matchResult;
356 :
357 : /* used for Posting list and one page in Posting tree */
358 : ItemPointerData *list;
359 : int nlist;
360 : OffsetNumber offset;
361 :
362 : bool isFinished;
363 : bool reduceResult;
364 : uint32 predictNumberResult;
365 : GinBtreeData btree;
366 : } GinScanEntryData;
367 :
368 : typedef struct GinScanOpaqueData
369 : {
370 : MemoryContext tempCtx;
371 : GinState ginstate;
372 :
373 : GinScanKey keys; /* one per scan qualifier expr */
374 : uint32 nkeys;
375 :
376 : GinScanEntry *entries; /* one per index search condition */
377 : uint32 totalentries;
378 : uint32 allocentries; /* allocated length of entries[] */
379 :
380 : MemoryContext keyCtx; /* used to hold key and entry data */
381 :
382 : bool isVoidRes; /* true if query is unsatisfiable */
383 : } GinScanOpaqueData;
384 :
385 : typedef GinScanOpaqueData *GinScanOpaque;
386 :
387 : extern IndexScanDesc ginbeginscan(Relation rel, int nkeys, int norderbys);
388 : extern void ginendscan(IndexScanDesc scan);
389 : extern void ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
390 : ScanKey orderbys, int norderbys);
391 : extern void ginNewScanKey(IndexScanDesc scan);
392 : extern void ginFreeScanKeys(GinScanOpaque so);
393 :
394 : /* ginget.c */
395 : extern int64 gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
396 :
397 : /* ginlogic.c */
398 : extern void ginInitConsistentFunction(GinState *ginstate, GinScanKey key);
399 :
400 : /* ginvacuum.c */
401 : extern IndexBulkDeleteResult *ginbulkdelete(IndexVacuumInfo *info,
402 : IndexBulkDeleteResult *stats,
403 : IndexBulkDeleteCallback callback,
404 : void *callback_state);
405 : extern IndexBulkDeleteResult *ginvacuumcleanup(IndexVacuumInfo *info,
406 : IndexBulkDeleteResult *stats);
407 : extern ItemPointer ginVacuumItemPointers(GinVacuumState *gvs,
408 : ItemPointerData *items, int nitem, int *nremaining);
409 :
410 : /* ginvalidate.c */
411 : extern bool ginvalidate(Oid opclassoid);
412 : extern void ginadjustmembers(Oid opfamilyoid,
413 : Oid opclassoid,
414 : List *operators,
415 : List *functions);
416 :
417 : /* ginbulk.c */
418 : typedef struct GinEntryAccumulator
419 : {
420 : RBTNode rbtnode;
421 : Datum key;
422 : GinNullCategory category;
423 : OffsetNumber attnum;
424 : bool shouldSort;
425 : ItemPointerData *list;
426 : uint32 maxcount; /* allocated size of list[] */
427 : uint32 count; /* current number of list[] entries */
428 : } GinEntryAccumulator;
429 :
430 : typedef struct
431 : {
432 : GinState *ginstate;
433 : Size allocatedMemory;
434 : GinEntryAccumulator *entryallocator;
435 : uint32 eas_used;
436 : RBTree *tree;
437 : RBTreeIterator tree_walk;
438 : } BuildAccumulator;
439 :
440 : extern void ginInitBA(BuildAccumulator *accum);
441 : extern void ginInsertBAEntries(BuildAccumulator *accum,
442 : ItemPointer heapptr, OffsetNumber attnum,
443 : Datum *entries, GinNullCategory *categories,
444 : int32 nentries);
445 : extern void ginBeginBAScan(BuildAccumulator *accum);
446 : extern ItemPointerData *ginGetBAEntry(BuildAccumulator *accum,
447 : OffsetNumber *attnum, Datum *key, GinNullCategory *category,
448 : uint32 *n);
449 :
450 : /* ginfast.c */
451 :
452 : typedef struct GinTupleCollector
453 : {
454 : IndexTuple *tuples;
455 : uint32 ntuples;
456 : uint32 lentuples;
457 : uint32 sumsize;
458 : } GinTupleCollector;
459 :
460 : extern void ginHeapTupleFastInsert(GinState *ginstate,
461 : GinTupleCollector *collector);
462 : extern void ginHeapTupleFastCollect(GinState *ginstate,
463 : GinTupleCollector *collector,
464 : OffsetNumber attnum, Datum value, bool isNull,
465 : ItemPointer ht_ctid);
466 : extern void ginInsertCleanup(GinState *ginstate, bool full_clean,
467 : bool fill_fsm, bool forceCleanup, IndexBulkDeleteResult *stats);
468 :
469 : /* ginpostinglist.c */
470 :
471 : extern GinPostingList *ginCompressPostingList(const ItemPointer ipd, int nipd,
472 : int maxsize, int *nwritten);
473 : extern int ginPostingListDecodeAllSegmentsToTbm(GinPostingList *ptr, int len, TIDBitmap *tbm);
474 :
475 : extern ItemPointer ginPostingListDecodeAllSegments(GinPostingList *segment, int len,
476 : int *ndecoded_out);
477 : extern ItemPointer ginPostingListDecode(GinPostingList *plist, int *ndecoded_out);
478 : extern ItemPointer ginMergeItemPointers(ItemPointerData *a, uint32 na,
479 : ItemPointerData *b, uint32 nb,
480 : int *nmerged);
481 :
482 : /*
483 : * Merging the results of several gin scans compares item pointers a lot,
484 : * so we want this to be inlined.
485 : */
486 : static inline int
3571 heikki.linnakangas 487 GIC 6389908 : ginCompareItemPointers(ItemPointer a, ItemPointer b)
488 : {
2203 alvherre 489 CBC 6389908 : uint64 ia = (uint64) GinItemPointerGetBlockNumber(a) << 32 | GinItemPointerGetOffsetNumber(a);
2203 alvherre 490 GIC 6389908 : uint64 ib = (uint64) GinItemPointerGetBlockNumber(b) << 32 | GinItemPointerGetOffsetNumber(b);
3571 heikki.linnakangas 491 ECB :
3571 heikki.linnakangas 492 CBC 6389908 : if (ia == ib)
3571 heikki.linnakangas 493 GIC 2152574 : return 0;
3571 heikki.linnakangas 494 CBC 4237334 : else if (ia > ib)
495 1201872 : return 1;
3571 heikki.linnakangas 496 ECB : else
3571 heikki.linnakangas 497 CBC 3035462 : return -1;
498 : }
3571 heikki.linnakangas 499 ECB :
500 : extern int ginTraverseLock(Buffer buffer, bool searchMode);
501 :
502 : #endif /* GIN_PRIVATE_H */
|
