1 /*-------------------------------------------------------------------------
4 * private declarations for GiST -- declarations related to the
5 * internal implementation of GiST, not the public API
7 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
10 * $PostgreSQL: pgsql/src/include/access/gist_private.h,v 1.35 2008/10/22 12:53:56 teodor Exp $
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;
90 extern const XLogRecPtr XLogRecPtrForTemp;
92 #define XLOG_GIST_PAGE_UPDATE 0x00
93 #define XLOG_GIST_NEW_ROOT 0x20
94 #define XLOG_GIST_PAGE_SPLIT 0x30
95 #define XLOG_GIST_INSERT_COMPLETE 0x40
96 #define XLOG_GIST_CREATE_INDEX 0x50
97 #define XLOG_GIST_PAGE_DELETE 0x60
99 typedef struct gistxlogPageUpdate
105 * It used to identify completeness of insert. Sets to leaf itup
109 /* number of deleted offsets */
113 * follow: 1. todelete OffsetNumbers 2. tuples to insert
115 } gistxlogPageUpdate;
117 typedef struct gistxlogPageSplit
120 BlockNumber origblkno; /* splitted page */
121 bool origleaf; /* was splitted page a leaf page? */
124 /* see comments on gistxlogPageUpdate */
128 * follow: 1. gistxlogPage and array of IndexTupleData per page
132 typedef struct gistxlogPage
135 int num; /* number of index tuples following */
138 typedef struct gistxlogInsertComplete
141 /* follows ItemPointerData key to clean */
142 } gistxlogInsertComplete;
144 typedef struct gistxlogPageDelete
148 } gistxlogPageDelete;
150 /* SplitedPageLayout - gistSplit function result */
151 typedef struct SplitedPageLayout
154 IndexTupleData *list;
156 IndexTuple itup; /* union key for page */
157 Page page; /* to operate */
158 Buffer buffer; /* to write after all proceed */
160 struct SplitedPageLayout *next;
164 * GISTInsertStack used for locking buffers and transfer arguments during
168 typedef struct GISTInsertStack
176 * log sequence number from page->lsn to recognize page update and
177 * compare it with page's nsn to recognize page split
182 OffsetNumber childoffnum;
184 /* pointer to parent and child */
185 struct GISTInsertStack *parent;
186 struct GISTInsertStack *child;
188 /* for gistFindPath */
189 struct GISTInsertStack *next;
192 typedef struct GistSplitVector
194 GIST_SPLITVEC splitVector; /* to/from PickSplit method */
196 Datum spl_lattr[INDEX_MAX_KEYS]; /* Union of subkeys in
198 bool spl_lisnull[INDEX_MAX_KEYS];
201 Datum spl_rattr[INDEX_MAX_KEYS]; /* Union of subkeys in
203 bool spl_risnull[INDEX_MAX_KEYS];
206 bool *spl_equiv; /* equivalent tuples which can be freely
207 * distributed between left and right pages */
213 IndexTuple *itup; /* in/out, points to compressed entry */
214 int ituplen; /* length of itup */
215 Size freespace; /* free space to be left */
216 GISTInsertStack *stack;
217 bool needInsertComplete;
219 /* pointer to heap tuple */
223 /* root page of a gist index */
224 #define GIST_ROOT_BLKNO 0
227 * mark tuples on inner pages during recovery
229 #define TUPLE_IS_VALID 0xffff
230 #define TUPLE_IS_INVALID 0xfffe
232 #define GistTupleIsInvalid(itup) ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
233 #define GistTupleSetValid(itup) ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
234 #define GistTupleSetInvalid(itup) ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_INVALID )
237 extern Datum gistbuild(PG_FUNCTION_ARGS);
238 extern Datum gistinsert(PG_FUNCTION_ARGS);
239 extern MemoryContext createTempGistContext(void);
240 extern void initGISTstate(GISTSTATE *giststate, Relation index);
241 extern void freeGISTstate(GISTSTATE *giststate);
242 extern void gistmakedeal(GISTInsertState *state, GISTSTATE *giststate);
243 extern void gistnewroot(Relation r, Buffer buffer, IndexTuple *itup, int len, ItemPointer key);
245 extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
246 int len, GISTSTATE *giststate);
248 extern GISTInsertStack *gistFindPath(Relation r, BlockNumber child);
251 extern void gist_redo(XLogRecPtr lsn, XLogRecord *record);
252 extern void gist_desc(StringInfo buf, uint8 xl_info, char *rec);
253 extern void gist_xlog_startup(void);
254 extern void gist_xlog_cleanup(void);
255 extern bool gist_safe_restartpoint(void);
256 extern IndexTuple gist_form_invalid_tuple(BlockNumber blkno);
258 extern XLogRecData *formUpdateRdata(RelFileNode node, Buffer buffer,
259 OffsetNumber *todelete, int ntodelete,
260 IndexTuple *itup, int ituplen, ItemPointer key);
262 extern XLogRecData *formSplitRdata(RelFileNode node,
263 BlockNumber blkno, bool page_is_leaf,
264 ItemPointer key, SplitedPageLayout *dist);
266 extern XLogRecPtr gistxlogInsertCompletion(RelFileNode node, ItemPointerData *keys, int len);
269 extern Datum gistgettuple(PG_FUNCTION_ARGS);
270 extern Datum gistgetbitmap(PG_FUNCTION_ARGS);
274 #define GiSTPageSize \
275 ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
277 #define GIST_MIN_FILLFACTOR 10
278 #define GIST_DEFAULT_FILLFACTOR 90
280 extern Datum gistoptions(PG_FUNCTION_ARGS);
281 extern bool gistfitpage(IndexTuple *itvec, int len);
282 extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
283 extern void gistcheckpage(Relation rel, Buffer buf);
284 extern Buffer gistNewBuffer(Relation r);
285 extern void gistfillbuffer(Page page, IndexTuple *itup, int len,
287 extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
288 extern IndexTuple *gistjoinvector(
289 IndexTuple *itvec, int *len,
290 IndexTuple *additvec, int addlen);
291 extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
293 extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
294 int len, GISTSTATE *giststate);
295 extern IndexTuple gistgetadjusted(Relation r,
298 GISTSTATE *giststate);
299 extern IndexTuple gistFormTuple(GISTSTATE *giststate,
300 Relation r, Datum *attdata, bool *isnull, bool newValues);
302 extern OffsetNumber gistchoose(Relation r, Page p,
304 GISTSTATE *giststate);
305 extern void gistcentryinit(GISTSTATE *giststate, int nkey,
306 GISTENTRY *e, Datum k,
308 OffsetNumber o, bool l, bool isNull);
310 extern void GISTInitBuffer(Buffer b, uint32 f);
311 extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
312 Datum k, Relation r, Page pg, OffsetNumber o,
313 bool l, bool isNull);
315 extern float gistpenalty(GISTSTATE *giststate, int attno,
316 GISTENTRY *key1, bool isNull1,
317 GISTENTRY *key2, bool isNull2);
318 extern bool gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len, int startkey,
319 Datum *attr, bool *isnull);
320 extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
321 extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
322 OffsetNumber o, GISTENTRY *attdata, bool *isnull);
324 extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
325 GISTENTRY *entry1, bool isnull1,
326 GISTENTRY *entry2, bool isnull2,
327 Datum *dst, bool *dstisnull);
330 extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
331 extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
334 extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
335 int len, GISTSTATE *giststate,
336 GistSplitVector *v, GistEntryVector *entryvec,
339 #endif /* GIST_PRIVATE_H */