1 /*-------------------------------------------------------------------------
4 * private declarations for GiST -- declarations related to the
5 * internal implementation of GiST, not the public API
7 * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
10 * src/include/access/gist_private.h
12 *-------------------------------------------------------------------------
14 #ifndef GIST_PRIVATE_H
15 #define GIST_PRIVATE_H
17 #include "access/gist.h"
18 #include "access/itup.h"
19 #include "storage/bufmgr.h"
21 #define GIST_UNLOCK BUFFER_LOCK_UNLOCK
22 #define GIST_SHARE BUFFER_LOCK_SHARE
23 #define GIST_EXCLUSIVE BUFFER_LOCK_EXCLUSIVE
28 * When we descend a tree, we keep a stack of parent pointers. This
29 * allows us to follow a chain of internal node points until we reach
30 * a leaf node, and then back up the stack to re-examine the internal
33 * 'parent' is the previous stack entry -- i.e. the node we arrived
34 * from. 'block' is the node's block number. 'offset' is the offset in
35 * the node's page that we stopped at (i.e. we followed the child
36 * pointer located at the specified offset).
38 typedef struct GISTSearchStack
40 struct GISTSearchStack *next;
42 /* to identify page changed */
44 /* to recognize split occured */
48 typedef struct GISTSTATE
50 FmgrInfo consistentFn[INDEX_MAX_KEYS];
51 FmgrInfo unionFn[INDEX_MAX_KEYS];
52 FmgrInfo compressFn[INDEX_MAX_KEYS];
53 FmgrInfo decompressFn[INDEX_MAX_KEYS];
54 FmgrInfo penaltyFn[INDEX_MAX_KEYS];
55 FmgrInfo picksplitFn[INDEX_MAX_KEYS];
56 FmgrInfo equalFn[INDEX_MAX_KEYS];
61 typedef struct ItemResult
63 ItemPointerData heapPtr;
64 OffsetNumber pageOffset; /* offset in index page */
69 * When we're doing a scan, we need to keep track of the parent stack
70 * for the marked and current items.
72 typedef struct GISTScanOpaqueData
74 GISTSearchStack *stack;
75 GISTSearchStack *markstk;
76 bool qual_ok; /* false if qual can never be satisfied */
78 MemoryContext tempCxt;
80 ItemPointerData curpos;
82 ItemResult pageData[BLCKSZ / sizeof(IndexTupleData)];
83 OffsetNumber nPageData;
84 OffsetNumber curPageData;
87 typedef GISTScanOpaqueData *GISTScanOpaque;
91 #define XLOG_GIST_PAGE_UPDATE 0x00
92 #define XLOG_GIST_NEW_ROOT 0x20
93 #define XLOG_GIST_PAGE_SPLIT 0x30
94 #define XLOG_GIST_INSERT_COMPLETE 0x40
95 #define XLOG_GIST_CREATE_INDEX 0x50
96 #define XLOG_GIST_PAGE_DELETE 0x60
98 typedef struct gistxlogPageUpdate
104 * It used to identify completeness of insert. Sets to leaf itup
108 /* number of deleted offsets */
112 * follow: 1. todelete OffsetNumbers 2. tuples to insert
114 } gistxlogPageUpdate;
116 typedef struct gistxlogPageSplit
119 BlockNumber origblkno; /* splitted page */
120 bool origleaf; /* was splitted page a leaf page? */
123 /* see comments on gistxlogPageUpdate */
127 * follow: 1. gistxlogPage and array of IndexTupleData per page
131 typedef struct gistxlogPage
134 int num; /* number of index tuples following */
137 typedef struct gistxlogInsertComplete
140 /* follows ItemPointerData key to clean */
141 } gistxlogInsertComplete;
143 typedef struct gistxlogPageDelete
147 } gistxlogPageDelete;
149 /* SplitedPageLayout - gistSplit function result */
150 typedef struct SplitedPageLayout
153 IndexTupleData *list;
155 IndexTuple itup; /* union key for page */
156 Page page; /* to operate */
157 Buffer buffer; /* to write after all proceed */
159 struct SplitedPageLayout *next;
163 * GISTInsertStack used for locking buffers and transfer arguments during
167 typedef struct GISTInsertStack
175 * log sequence number from page->lsn to recognize page update and
176 * compare it with page's nsn to recognize page split
181 OffsetNumber childoffnum;
183 /* pointer to parent and child */
184 struct GISTInsertStack *parent;
185 struct GISTInsertStack *child;
187 /* for gistFindPath */
188 struct GISTInsertStack *next;
191 typedef struct GistSplitVector
193 GIST_SPLITVEC splitVector; /* to/from PickSplit method */
195 Datum spl_lattr[INDEX_MAX_KEYS]; /* Union of subkeys in
197 bool spl_lisnull[INDEX_MAX_KEYS];
200 Datum spl_rattr[INDEX_MAX_KEYS]; /* Union of subkeys in
202 bool spl_risnull[INDEX_MAX_KEYS];
205 bool *spl_equiv; /* equivalent tuples which can be freely
206 * distributed between left and right pages */
212 IndexTuple *itup; /* in/out, points to compressed entry */
213 int ituplen; /* length of itup */
214 Size freespace; /* free space to be left */
215 GISTInsertStack *stack;
216 bool needInsertComplete;
218 /* pointer to heap tuple */
222 /* root page of a gist index */
223 #define GIST_ROOT_BLKNO 0
226 * mark tuples on inner pages during recovery
228 #define TUPLE_IS_VALID 0xffff
229 #define TUPLE_IS_INVALID 0xfffe
231 #define GistTupleIsInvalid(itup) ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
232 #define GistTupleSetValid(itup) ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
233 #define GistTupleSetInvalid(itup) ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_INVALID )
236 extern Datum gistbuild(PG_FUNCTION_ARGS);
237 extern Datum gistinsert(PG_FUNCTION_ARGS);
238 extern MemoryContext createTempGistContext(void);
239 extern void initGISTstate(GISTSTATE *giststate, Relation index);
240 extern void freeGISTstate(GISTSTATE *giststate);
241 extern void gistmakedeal(GISTInsertState *state, GISTSTATE *giststate);
242 extern void gistnewroot(Relation r, Buffer buffer, IndexTuple *itup, int len, ItemPointer key);
244 extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
245 int len, GISTSTATE *giststate);
247 extern GISTInsertStack *gistFindPath(Relation r, BlockNumber child);
250 extern void gist_redo(XLogRecPtr lsn, XLogRecord *record);
251 extern void gist_desc(StringInfo buf, uint8 xl_info, char *rec);
252 extern void gist_xlog_startup(void);
253 extern void gist_xlog_cleanup(void);
254 extern bool gist_safe_restartpoint(void);
255 extern IndexTuple gist_form_invalid_tuple(BlockNumber blkno);
257 extern XLogRecData *formUpdateRdata(RelFileNode node, Buffer buffer,
258 OffsetNumber *todelete, int ntodelete,
259 IndexTuple *itup, int ituplen, ItemPointer key);
261 extern XLogRecData *formSplitRdata(RelFileNode node,
262 BlockNumber blkno, bool page_is_leaf,
263 ItemPointer key, SplitedPageLayout *dist);
265 extern XLogRecPtr gistxlogInsertCompletion(RelFileNode node, ItemPointerData *keys, int len);
268 extern Datum gistgettuple(PG_FUNCTION_ARGS);
269 extern Datum gistgetbitmap(PG_FUNCTION_ARGS);
273 #define GiSTPageSize \
274 ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
276 #define GIST_MIN_FILLFACTOR 10
277 #define GIST_DEFAULT_FILLFACTOR 90
279 extern Datum gistoptions(PG_FUNCTION_ARGS);
280 extern bool gistfitpage(IndexTuple *itvec, int len);
281 extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
282 extern void gistcheckpage(Relation rel, Buffer buf);
283 extern Buffer gistNewBuffer(Relation r);
284 extern void gistfillbuffer(Page page, IndexTuple *itup, int len,
286 extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
287 extern IndexTuple *gistjoinvector(
288 IndexTuple *itvec, int *len,
289 IndexTuple *additvec, int addlen);
290 extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
292 extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
293 int len, GISTSTATE *giststate);
294 extern IndexTuple gistgetadjusted(Relation r,
297 GISTSTATE *giststate);
298 extern IndexTuple gistFormTuple(GISTSTATE *giststate,
299 Relation r, Datum *attdata, bool *isnull, bool newValues);
301 extern OffsetNumber gistchoose(Relation r, Page p,
303 GISTSTATE *giststate);
304 extern void gistcentryinit(GISTSTATE *giststate, int nkey,
305 GISTENTRY *e, Datum k,
307 OffsetNumber o, bool l, bool isNull);
309 extern void GISTInitBuffer(Buffer b, uint32 f);
310 extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
311 Datum k, Relation r, Page pg, OffsetNumber o,
312 bool l, bool isNull);
314 extern float gistpenalty(GISTSTATE *giststate, int attno,
315 GISTENTRY *key1, bool isNull1,
316 GISTENTRY *key2, bool isNull2);
317 extern bool gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len, int startkey,
318 Datum *attr, bool *isnull);
319 extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
320 extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
321 OffsetNumber o, GISTENTRY *attdata, bool *isnull);
323 extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
324 GISTENTRY *entry1, bool isnull1,
325 GISTENTRY *entry2, bool isnull2,
326 Datum *dst, bool *dstisnull);
328 extern XLogRecPtr GetXLogRecPtrForTemp(void);
331 extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
332 extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
335 extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
336 int len, GISTSTATE *giststate,
337 GistSplitVector *v, GistEntryVector *entryvec,
340 #endif /* GIST_PRIVATE_H */