← Back to branch summary

~ubuntu-branches/debian/sid/postgresql-9.3/sid

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Martin Pitt
  • Date: 2013-05-08 05:39:52 UTC
  • Revision ID: package-import@ubuntu.com-20130508053952-1j7uilp7mjtrvq8q
Tags: upstream-9.3~beta1
Import upstream version 9.3~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/include/access/gist.h
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * gist.h
 
4
 *        The public API for GiST indexes. This API is exposed to
 
5
 *        individuals implementing GiST indexes, so backward-incompatible
 
6
 *        changes should be made with care.
 
7
 *
 
8
 *
 
9
 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
 
10
 * Portions Copyright (c) 1994, Regents of the University of California
 
11
 *
 
12
 * src/include/access/gist.h
 
13
 *
 
14
 *-------------------------------------------------------------------------
 
15
 */
 
16
#ifndef GIST_H
 
17
#define GIST_H
 
18
 
 
19
#include "access/xlog.h"
 
20
#include "access/xlogdefs.h"
 
21
#include "storage/block.h"
 
22
#include "storage/bufpage.h"
 
23
#include "utils/relcache.h"
 
24
 
 
25
/*
 
26
 * amproc indexes for GiST indexes.
 
27
 */
 
28
#define GIST_CONSISTENT_PROC                    1
 
29
#define GIST_UNION_PROC                                 2
 
30
#define GIST_COMPRESS_PROC                              3
 
31
#define GIST_DECOMPRESS_PROC                    4
 
32
#define GIST_PENALTY_PROC                               5
 
33
#define GIST_PICKSPLIT_PROC                             6
 
34
#define GIST_EQUAL_PROC                                 7
 
35
#define GIST_DISTANCE_PROC                              8
 
36
#define GISTNProcs                                              8
 
37
 
 
38
/*
 
39
 * strategy numbers for GiST opclasses that want to implement the old
 
40
 * RTREE behavior.
 
41
 */
 
42
#define RTLeftStrategyNumber                    1
 
43
#define RTOverLeftStrategyNumber                2
 
44
#define RTOverlapStrategyNumber                 3
 
45
#define RTOverRightStrategyNumber               4
 
46
#define RTRightStrategyNumber                   5
 
47
#define RTSameStrategyNumber                    6
 
48
#define RTContainsStrategyNumber                7               /* for @> */
 
49
#define RTContainedByStrategyNumber             8               /* for <@ */
 
50
#define RTOverBelowStrategyNumber               9
 
51
#define RTBelowStrategyNumber                   10
 
52
#define RTAboveStrategyNumber                   11
 
53
#define RTOverAboveStrategyNumber               12
 
54
#define RTOldContainsStrategyNumber             13              /* for old spelling of @> */
 
55
#define RTOldContainedByStrategyNumber  14              /* for old spelling of <@ */
 
56
#define RTKNNSearchStrategyNumber               15
 
57
 
 
58
/*
 
59
 * Page opaque data in a GiST index page.
 
60
 */
 
61
#define F_LEAF                          (1 << 0)        /* leaf page */
 
62
#define F_DELETED                       (1 << 1)        /* the page has been deleted */
 
63
#define F_TUPLES_DELETED        (1 << 2)        /* some tuples on the page are dead */
 
64
#define F_FOLLOW_RIGHT          (1 << 3)        /* page to the right has no downlink */
 
65
 
 
66
typedef XLogRecPtr GistNSN;
 
67
/*
 
68
 * For on-disk compatibility with pre-9.3 servers, NSN is stored as two
 
69
 * 32-bit fields on disk, same as LSNs.
 
70
 */
 
71
typedef PageXLogRecPtr PageGistNSN;
 
72
 
 
73
typedef struct GISTPageOpaqueData
 
74
{
 
75
        PageGistNSN     nsn;                    /* this value must change on page split */
 
76
        BlockNumber rightlink;          /* next page if any */
 
77
        uint16          flags;                  /* see bit definitions above */
 
78
        uint16          gist_page_id;   /* for identification of GiST indexes */
 
79
} GISTPageOpaqueData;
 
80
 
 
81
typedef GISTPageOpaqueData *GISTPageOpaque;
 
82
 
 
83
/*
 
84
 * The page ID is for the convenience of pg_filedump and similar utilities,
 
85
 * which otherwise would have a hard time telling pages of different index
 
86
 * types apart.  It should be the last 2 bytes on the page.  This is more or
 
87
 * less "free" due to alignment considerations.
 
88
 */
 
89
#define GIST_PAGE_ID            0xFF81
 
90
 
 
91
/*
 
92
 * This is the Split Vector to be returned by the PickSplit method.
 
93
 * PickSplit should fill the indexes of tuples to go to the left side into
 
94
 * spl_left[], and those to go to the right into spl_right[] (note the method
 
95
 * is responsible for palloc'ing both of these arrays!).  The tuple counts
 
96
 * go into spl_nleft/spl_nright, and spl_ldatum/spl_rdatum must be set to
 
97
 * the union keys for each side.
 
98
 *
 
99
 * If spl_ldatum_exists and spl_rdatum_exists are true, then we are performing
 
100
 * a "secondary split" using a non-first index column.  In this case some
 
101
 * decisions have already been made about a page split, and the set of tuples
 
102
 * being passed to PickSplit is just the tuples about which we are undecided.
 
103
 * spl_ldatum/spl_rdatum then contain the union keys for the tuples already
 
104
 * chosen to go left or right.  Ideally the PickSplit method should take those
 
105
 * keys into account while deciding what to do with the remaining tuples, ie
 
106
 * it should try to "build out" from those unions so as to minimally expand
 
107
 * them.  If it does so, it should union the given tuples' keys into the
 
108
 * existing spl_ldatum/spl_rdatum values rather than just setting those values
 
109
 * from scratch, and then set spl_ldatum_exists/spl_rdatum_exists to false to
 
110
 * show it has done this.
 
111
 *
 
112
 * If the PickSplit method fails to clear spl_ldatum_exists/spl_rdatum_exists,
 
113
 * the core GiST code will make its own decision about how to merge the
 
114
 * secondary-split results with the previously-chosen tuples, and will then
 
115
 * recompute the union keys from scratch.  This is a workable though often not
 
116
 * optimal approach.
 
117
 */
 
118
typedef struct GIST_SPLITVEC
 
119
{
 
120
        OffsetNumber *spl_left;         /* array of entries that go left */
 
121
        int                     spl_nleft;              /* size of this array */
 
122
        Datum           spl_ldatum;             /* Union of keys in spl_left */
 
123
        bool            spl_ldatum_exists;              /* true, if spl_ldatum already exists. */
 
124
 
 
125
        OffsetNumber *spl_right;        /* array of entries that go right */
 
126
        int                     spl_nright;             /* size of the array */
 
127
        Datum           spl_rdatum;             /* Union of keys in spl_right */
 
128
        bool            spl_rdatum_exists;              /* true, if spl_rdatum already exists. */
 
129
} GIST_SPLITVEC;
 
130
 
 
131
/*
 
132
 * An entry on a GiST node.  Contains the key, as well as its own
 
133
 * location (rel,page,offset) which can supply the matching pointer.
 
134
 * leafkey is a flag to tell us if the entry is in a leaf node.
 
135
 */
 
136
typedef struct GISTENTRY
 
137
{
 
138
        Datum           key;
 
139
        Relation        rel;
 
140
        Page            page;
 
141
        OffsetNumber offset;
 
142
        bool            leafkey;
 
143
} GISTENTRY;
 
144
 
 
145
#define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )
 
146
 
 
147
#define GistPageIsLeaf(page)    ( GistPageGetOpaque(page)->flags & F_LEAF)
 
148
#define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))
 
149
#define GistPageSetLeaf(page)   ( GistPageGetOpaque(page)->flags |= F_LEAF)
 
150
#define GistPageSetNonLeaf(page)        ( GistPageGetOpaque(page)->flags &= ~F_LEAF)
 
151
 
 
152
#define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED)
 
153
#define GistPageSetDeleted(page)        ( GistPageGetOpaque(page)->flags |= F_DELETED)
 
154
#define GistPageSetNonDeleted(page) ( GistPageGetOpaque(page)->flags &= ~F_DELETED)
 
155
 
 
156
#define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
 
157
#define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
 
158
#define GistClearTuplesDeleted(page)    ( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)
 
159
 
 
160
#define GistFollowRight(page) ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
 
161
#define GistMarkFollowRight(page) ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)
 
162
#define GistClearFollowRight(page)      ( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)
 
163
 
 
164
#define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
 
165
#define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
 
166
 
 
167
/*
 
168
 * Vector of GISTENTRY structs; user-defined methods union and picksplit
 
169
 * take it as one of their arguments
 
170
 */
 
171
typedef struct
 
172
{
 
173
        int32           n;                              /* number of elements */
 
174
        GISTENTRY       vector[FLEXIBLE_ARRAY_MEMBER];
 
175
} GistEntryVector;
 
176
 
 
177
#define GEVHDRSZ        (offsetof(GistEntryVector, vector))
 
178
 
 
179
/*
 
180
 * macro to initialize a GISTENTRY
 
181
 */
 
182
#define gistentryinit(e, k, r, pg, o, l) \
 
183
        do { (e).key = (k); (e).rel = (r); (e).page = (pg); \
 
184
                 (e).offset = (o); (e).leafkey = (l); } while (0)
 
185
 
 
186
#endif   /* GIST_H */