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