← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/include/access/gist_private.h

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/include/access/gist_private.h
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * gist_private.h
 
4
 *        private declarations for GiST -- declarations related to the
 
5
 *        internal implementation of GiST, not the public API
 
6
 *
 
7
 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
 
8
 * Portions Copyright (c) 1994, Regents of the University of California
 
9
 *
 
10
 * src/include/access/gist_private.h
 
11
 *
 
12
 *-------------------------------------------------------------------------
 
13
 */
 
14
#ifndef GIST_PRIVATE_H
 
15
#define GIST_PRIVATE_H
 
16
 
 
17
#include "access/gist.h"
 
18
#include "access/itup.h"
 
19
#include "storage/bufmgr.h"
 
20
#include "utils/rbtree.h"
 
21
 
 
22
/* Buffer lock modes */
 
23
#define GIST_SHARE      BUFFER_LOCK_SHARE
 
24
#define GIST_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
 
25
#define GIST_UNLOCK BUFFER_LOCK_UNLOCK
 
26
 
 
27
/*
 
28
 * GISTSTATE: information needed for any GiST index operation
 
29
 *
 
30
 * This struct retains call info for the index's opclass-specific support
 
31
 * functions (per index column), plus the index's tuple descriptor.
 
32
 */
 
33
typedef struct GISTSTATE
 
34
{
 
35
        FmgrInfo        consistentFn[INDEX_MAX_KEYS];
 
36
        FmgrInfo        unionFn[INDEX_MAX_KEYS];
 
37
        FmgrInfo        compressFn[INDEX_MAX_KEYS];
 
38
        FmgrInfo        decompressFn[INDEX_MAX_KEYS];
 
39
        FmgrInfo        penaltyFn[INDEX_MAX_KEYS];
 
40
        FmgrInfo        picksplitFn[INDEX_MAX_KEYS];
 
41
        FmgrInfo        equalFn[INDEX_MAX_KEYS];
 
42
        FmgrInfo        distanceFn[INDEX_MAX_KEYS];
 
43
 
 
44
        /* Collations to pass to the support functions */
 
45
        Oid                     supportCollation[INDEX_MAX_KEYS];
 
46
 
 
47
        TupleDesc       tupdesc;
 
48
} GISTSTATE;
 
49
 
 
50
 
 
51
/*
 
52
 * During a GiST index search, we must maintain a queue of unvisited items,
 
53
 * which can be either individual heap tuples or whole index pages.  If it
 
54
 * is an ordered search, the unvisited items should be visited in distance
 
55
 * order.  Unvisited items at the same distance should be visited in
 
56
 * depth-first order, that is heap items first, then lower index pages, then
 
57
 * upper index pages; this rule avoids doing extra work during a search that
 
58
 * ends early due to LIMIT.
 
59
 *
 
60
 * To perform an ordered search, we use an RBTree to manage the distance-order
 
61
 * queue.  Each GISTSearchTreeItem stores all unvisited items of the same
 
62
 * distance; they are GISTSearchItems chained together via their next fields.
 
63
 *
 
64
 * In a non-ordered search (no order-by operators), the RBTree degenerates
 
65
 * to a single item, which we use as a queue of unvisited index pages only.
 
66
 * In this case matched heap items from the current index leaf page are
 
67
 * remembered in GISTScanOpaqueData.pageData[] and returned directly from
 
68
 * there, instead of building a separate GISTSearchItem for each one.
 
69
 */
 
70
 
 
71
/* Individual heap tuple to be visited */
 
72
typedef struct GISTSearchHeapItem
 
73
{
 
74
        ItemPointerData heapPtr;
 
75
        bool            recheck;                /* T if quals must be rechecked */
 
76
} GISTSearchHeapItem;
 
77
 
 
78
/* Unvisited item, either index page or heap tuple */
 
79
typedef struct GISTSearchItem
 
80
{
 
81
        struct GISTSearchItem *next;    /* list link */
 
82
        BlockNumber blkno;                      /* index page number, or InvalidBlockNumber */
 
83
        union
 
84
        {
 
85
                GistNSN         parentlsn;      /* parent page's LSN, if index page */
 
86
                /* we must store parentlsn to detect whether a split occurred */
 
87
                GISTSearchHeapItem heap;        /* heap info, if heap tuple */
 
88
        }                       data;
 
89
} GISTSearchItem;
 
90
 
 
91
#define GISTSearchItemIsHeap(item)      ((item).blkno == InvalidBlockNumber)
 
92
 
 
93
/*
 
94
 * Within a GISTSearchTreeItem's chain, heap items always appear before
 
95
 * index-page items, since we want to visit heap items first.  lastHeap points
 
96
 * to the last heap item in the chain, or is NULL if there are none.
 
97
 */
 
98
typedef struct GISTSearchTreeItem
 
99
{
 
100
        RBNode          rbnode;                 /* this is an RBTree item */
 
101
        GISTSearchItem *head;           /* first chain member */
 
102
        GISTSearchItem *lastHeap;       /* last heap-tuple member, if any */
 
103
        double          distances[1];   /* array with numberOfOrderBys entries */
 
104
} GISTSearchTreeItem;
 
105
 
 
106
#define GSTIHDRSZ offsetof(GISTSearchTreeItem, distances)
 
107
 
 
108
/*
 
109
 * GISTScanOpaqueData: private state for a scan of a GiST index
 
110
 */
 
111
typedef struct GISTScanOpaqueData
 
112
{
 
113
        GISTSTATE  *giststate;          /* index information, see above */
 
114
        RBTree     *queue;                      /* queue of unvisited items */
 
115
        MemoryContext queueCxt;         /* context holding the queue */
 
116
        MemoryContext tempCxt;          /* workspace context for calling functions */
 
117
        bool            qual_ok;                /* false if qual can never be satisfied */
 
118
        bool            firstCall;              /* true until first gistgettuple call */
 
119
 
 
120
        GISTSearchTreeItem *curTreeItem;        /* current queue item, if any */
 
121
 
 
122
        /* pre-allocated workspace arrays */
 
123
        GISTSearchTreeItem *tmpTreeItem;        /* workspace to pass to rb_insert */
 
124
        double     *distances;          /* output area for gistindex_keytest */
 
125
 
 
126
        /* In a non-ordered search, returnable heap items are stored here: */
 
127
        GISTSearchHeapItem pageData[BLCKSZ / sizeof(IndexTupleData)];
 
128
        OffsetNumber nPageData;         /* number of valid items in array */
 
129
        OffsetNumber curPageData;       /* next item to return */
 
130
} GISTScanOpaqueData;
 
131
 
 
132
typedef GISTScanOpaqueData *GISTScanOpaque;
 
133
 
 
134
 
 
135
/* XLog stuff */
 
136
 
 
137
#define XLOG_GIST_PAGE_UPDATE           0x00
 
138
 /* #define XLOG_GIST_NEW_ROOT                   0x20 */        /* not used anymore */
 
139
#define XLOG_GIST_PAGE_SPLIT            0x30
 
140
 /* #define XLOG_GIST_INSERT_COMPLETE    0x40 */        /* not used anymore */
 
141
#define XLOG_GIST_CREATE_INDEX          0x50
 
142
#define XLOG_GIST_PAGE_DELETE           0x60
 
143
 
 
144
typedef struct gistxlogPageUpdate
 
145
{
 
146
        RelFileNode node;
 
147
        BlockNumber blkno;
 
148
 
 
149
        /*
 
150
         * If this operation completes a page split, by inserting a downlink for
 
151
         * the split page, leftchild points to the left half of the split.
 
152
         */
 
153
        BlockNumber leftchild;
 
154
 
 
155
        /* number of deleted offsets */
 
156
        uint16          ntodelete;
 
157
 
 
158
        /*
 
159
         * follow: 1. todelete OffsetNumbers 2. tuples to insert
 
160
         */
 
161
} gistxlogPageUpdate;
 
162
 
 
163
typedef struct gistxlogPageSplit
 
164
{
 
165
        RelFileNode node;
 
166
        BlockNumber origblkno;          /* splitted page */
 
167
        BlockNumber origrlink;          /* rightlink of the page before split */
 
168
        GistNSN         orignsn;                /* NSN of the page before split */
 
169
        bool            origleaf;               /* was splitted page a leaf page? */
 
170
 
 
171
        BlockNumber leftchild;          /* like in gistxlogPageUpdate */
 
172
        uint16          npage;                  /* # of pages in the split */
 
173
 
 
174
        /*
 
175
         * follow: 1. gistxlogPage and array of IndexTupleData per page
 
176
         */
 
177
} gistxlogPageSplit;
 
178
 
 
179
typedef struct gistxlogPage
 
180
{
 
181
        BlockNumber blkno;
 
182
        int                     num;                    /* number of index tuples following */
 
183
} gistxlogPage;
 
184
 
 
185
typedef struct gistxlogPageDelete
 
186
{
 
187
        RelFileNode node;
 
188
        BlockNumber blkno;
 
189
} gistxlogPageDelete;
 
190
 
 
191
/* SplitedPageLayout - gistSplit function result */
 
192
typedef struct SplitedPageLayout
 
193
{
 
194
        gistxlogPage block;
 
195
        IndexTupleData *list;
 
196
        int                     lenlist;
 
197
        IndexTuple      itup;                   /* union key for page */
 
198
        Page            page;                   /* to operate */
 
199
        Buffer          buffer;                 /* to write after all proceed */
 
200
 
 
201
        struct SplitedPageLayout *next;
 
202
} SplitedPageLayout;
 
203
 
 
204
/*
 
205
 * GISTInsertStack used for locking buffers and transfer arguments during
 
206
 * insertion
 
207
 */
 
208
typedef struct GISTInsertStack
 
209
{
 
210
        /* current page */
 
211
        BlockNumber blkno;
 
212
        Buffer          buffer;
 
213
        Page            page;
 
214
 
 
215
        /*
 
216
         * log sequence number from page->lsn to recognize page update and compare
 
217
         * it with page's nsn to recognize page split
 
218
         */
 
219
        GistNSN         lsn;
 
220
 
 
221
        /* child's offset */
 
222
        OffsetNumber childoffnum;
 
223
 
 
224
        /* pointer to parent */
 
225
        struct GISTInsertStack *parent;
 
226
 
 
227
        /* for gistFindPath */
 
228
        struct GISTInsertStack *next;
 
229
} GISTInsertStack;
 
230
 
 
231
typedef struct GistSplitVector
 
232
{
 
233
        GIST_SPLITVEC splitVector;      /* to/from PickSplit method */
 
234
 
 
235
        Datum           spl_lattr[INDEX_MAX_KEYS];              /* Union of subkeys in
 
236
                                                                                                 * spl_left */
 
237
        bool            spl_lisnull[INDEX_MAX_KEYS];
 
238
 
 
239
        Datum           spl_rattr[INDEX_MAX_KEYS];              /* Union of subkeys in
 
240
                                                                                                 * spl_right */
 
241
        bool            spl_risnull[INDEX_MAX_KEYS];
 
242
 
 
243
        bool       *spl_equiv;          /* equivalent tuples which can be freely
 
244
                                                                 * distributed between left and right pages */
 
245
} GistSplitVector;
 
246
 
 
247
typedef struct
 
248
{
 
249
        Relation        r;
 
250
        Size            freespace;              /* free space to be left */
 
251
 
 
252
        GISTInsertStack *stack;
 
253
} GISTInsertState;
 
254
 
 
255
/* root page of a gist index */
 
256
#define GIST_ROOT_BLKNO                         0
 
257
 
 
258
/*
 
259
 * Before PostgreSQL 9.1, we used rely on so-called "invalid tuples" on inner
 
260
 * pages to finish crash recovery of incomplete page splits. If a crash
 
261
 * happened in the middle of a page split, so that the downlink pointers were
 
262
 * not yet inserted, crash recovery inserted a special downlink pointer. The
 
263
 * semantics of an invalid tuple was that it if you encounter one in a scan,
 
264
 * it must always be followed, because we don't know if the tuples on the
 
265
 * child page match or not.
 
266
 *
 
267
 * We no longer create such invalid tuples, we now mark the left-half of such
 
268
 * an incomplete split with the F_FOLLOW_RIGHT flag instead, and finish the
 
269
 * split properly the next time we need to insert on that page. To retain
 
270
 * on-disk compatibility for the sake of pg_upgrade, we still store 0xffff as
 
271
 * the offset number of all inner tuples. If we encounter any invalid tuples
 
272
 * with 0xfffe during insertion, we throw an error, though scans still handle
 
273
 * them. You should only encounter invalid tuples if you pg_upgrade a pre-9.1
 
274
 * gist index which already has invalid tuples in it because of a crash. That
 
275
 * should be rare, and you are recommended to REINDEX anyway if you have any
 
276
 * invalid tuples in an index, so throwing an error is as far as we go with
 
277
 * supporting that.
 
278
 */
 
279
#define TUPLE_IS_VALID          0xffff
 
280
#define TUPLE_IS_INVALID        0xfffe
 
281
 
 
282
#define  GistTupleIsInvalid(itup)       ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
 
283
#define  GistTupleSetValid(itup)        ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
 
284
 
 
285
/* gist.c */
 
286
extern Datum gistbuild(PG_FUNCTION_ARGS);
 
287
extern Datum gistbuildempty(PG_FUNCTION_ARGS);
 
288
extern Datum gistinsert(PG_FUNCTION_ARGS);
 
289
extern MemoryContext createTempGistContext(void);
 
290
extern void initGISTstate(GISTSTATE *giststate, Relation index);
 
291
extern void freeGISTstate(GISTSTATE *giststate);
 
292
 
 
293
extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
 
294
                  int len, GISTSTATE *giststate);
 
295
 
 
296
extern GISTInsertStack *gistFindPath(Relation r, BlockNumber child);
 
297
 
 
298
/* gistxlog.c */
 
299
extern void gist_redo(XLogRecPtr lsn, XLogRecord *record);
 
300
extern void gist_desc(StringInfo buf, uint8 xl_info, char *rec);
 
301
extern void gist_xlog_startup(void);
 
302
extern void gist_xlog_cleanup(void);
 
303
 
 
304
extern XLogRecPtr gistXLogUpdate(RelFileNode node, Buffer buffer,
 
305
                           OffsetNumber *todelete, int ntodelete,
 
306
                           IndexTuple *itup, int ntup,
 
307
                           Buffer leftchild);
 
308
 
 
309
extern XLogRecPtr gistXLogSplit(RelFileNode node,
 
310
                          BlockNumber blkno, bool page_is_leaf,
 
311
                          SplitedPageLayout *dist,
 
312
                          BlockNumber origrlink, GistNSN oldnsn,
 
313
                          Buffer leftchild);
 
314
 
 
315
/* gistget.c */
 
316
extern Datum gistgettuple(PG_FUNCTION_ARGS);
 
317
extern Datum gistgetbitmap(PG_FUNCTION_ARGS);
 
318
 
 
319
/* gistutil.c */
 
320
 
 
321
#define GiSTPageSize   \
 
322
        ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
 
323
 
 
324
#define GIST_MIN_FILLFACTOR                     10
 
325
#define GIST_DEFAULT_FILLFACTOR         90
 
326
 
 
327
extern Datum gistoptions(PG_FUNCTION_ARGS);
 
328
extern bool gistfitpage(IndexTuple *itvec, int len);
 
329
extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
 
330
extern void gistcheckpage(Relation rel, Buffer buf);
 
331
extern Buffer gistNewBuffer(Relation r);
 
332
extern void gistfillbuffer(Page page, IndexTuple *itup, int len,
 
333
                           OffsetNumber off);
 
334
extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
 
335
extern IndexTuple *gistjoinvector(
 
336
                           IndexTuple *itvec, int *len,
 
337
                           IndexTuple *additvec, int addlen);
 
338
extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
 
339
 
 
340
extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
 
341
                  int len, GISTSTATE *giststate);
 
342
extern IndexTuple gistgetadjusted(Relation r,
 
343
                                IndexTuple oldtup,
 
344
                                IndexTuple addtup,
 
345
                                GISTSTATE *giststate);
 
346
extern IndexTuple gistFormTuple(GISTSTATE *giststate,
 
347
                          Relation r, Datum *attdata, bool *isnull, bool newValues);
 
348
 
 
349
extern OffsetNumber gistchoose(Relation r, Page p,
 
350
                   IndexTuple it,
 
351
                   GISTSTATE *giststate);
 
352
extern void gistcentryinit(GISTSTATE *giststate, int nkey,
 
353
                           GISTENTRY *e, Datum k,
 
354
                           Relation r, Page pg,
 
355
                           OffsetNumber o, bool l, bool isNull);
 
356
 
 
357
extern void GISTInitBuffer(Buffer b, uint32 f);
 
358
extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
 
359
                           Datum k, Relation r, Page pg, OffsetNumber o,
 
360
                           bool l, bool isNull);
 
361
 
 
362
extern float gistpenalty(GISTSTATE *giststate, int attno,
 
363
                        GISTENTRY *key1, bool isNull1,
 
364
                        GISTENTRY *key2, bool isNull2);
 
365
extern void gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len, int startkey,
 
366
                                   Datum *attr, bool *isnull);
 
367
extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
 
368
extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
 
369
                                  OffsetNumber o, GISTENTRY *attdata, bool *isnull);
 
370
 
 
371
extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
 
372
                                 GISTENTRY *entry1, bool isnull1,
 
373
                                 GISTENTRY *entry2, bool isnull2,
 
374
                                 Datum *dst, bool *dstisnull);
 
375
 
 
376
extern XLogRecPtr GetXLogRecPtrForTemp(void);
 
377
 
 
378
/* gistvacuum.c */
 
379
extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
 
380
extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
 
381
 
 
382
/* gistsplit.c */
 
383
extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
 
384
                           int len, GISTSTATE *giststate,
 
385
                           GistSplitVector *v, GistEntryVector *entryvec,
 
386
                           int attno);
 
387
 
 
388
#endif   /* GIST_PRIVATE_H */