src/include/access/nbtree.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nbtree.h
   4  *        header file for postgres btree access method implementation.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * $Id: nbtree.h,v 1.36 2000/06/08 22:37:38 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #ifndef NBTREE_H
  15 #define NBTREE_H
  16
  17 #include "access/funcindex.h"
  18 #include "access/itup.h"
  19 #include "access/relscan.h"
  20 #include "access/sdir.h"
  21
  22 /*
  23  *      BTPageOpaqueData -- At the end of every page, we store a pointer
  24  *      to both siblings in the tree.  See Lehman and Yao's paper for more
  25  *      info.  In addition, we need to know what sort of page this is
  26  *      (leaf or internal), and whether the page is available for reuse.
  27  *
  28  *      Lehman and Yao's algorithm requires a ``high key'' on every page.
  29  *      The high key on a page is guaranteed to be greater than or equal
  30  *      to any key that appears on this page.  Our insertion algorithm
  31  *      guarantees that we can use the initial least key on our right
  32  *      sibling as the high key.  We allocate space for the line pointer
  33  *      to the high key in the opaque data at the end of the page.
  34  *
  35  *      Rightmost pages in the tree have no high key.
  36  */
  37
  38 typedef struct BTPageOpaqueData
  39 {
  40         BlockNumber btpo_prev;
  41         BlockNumber btpo_next;
  42         BlockNumber btpo_parent;
  43         uint16          btpo_flags;
  44
  45 #define BTP_LEAF                (1 << 0)
  46 #define BTP_ROOT                (1 << 1)
  47 #define BTP_FREE                (1 << 2)
  48 #define BTP_META                (1 << 3)
  49 #define BTP_CHAIN               (1 << 4)
  50
  51 } BTPageOpaqueData;
  52
  53 typedef BTPageOpaqueData *BTPageOpaque;
  54
  55 /*
  56  *      ScanOpaqueData is used to remember which buffers we're currently
  57  *      examining in the scan.  We keep these buffers locked and pinned
  58  *      and recorded in the opaque entry of the scan in order to avoid
  59  *      doing a ReadBuffer() for every tuple in the index.      This avoids
  60  *      semop() calls, which are expensive.
  61  *
  62  *      And it's used to remember actual scankey info (we need in it
  63  *      if some scankeys evaled at runtime).
  64  *
  65  *      curHeapIptr & mrkHeapIptr are heap iptr-s from current/marked
  66  *      index tuples: we don't adjust scans on insertions (and, if LLL
  67  *      is ON, don't hold locks on index pages between passes) - we
  68  *      use these pointers to restore index scan positions...
  69  *              - vadim 07/29/98
  70  */
  71
  72 typedef struct BTScanOpaqueData
  73 {
  74         Buffer          btso_curbuf;
  75         Buffer          btso_mrkbuf;
  76         ItemPointerData curHeapIptr;
  77         ItemPointerData mrkHeapIptr;
  78         uint16          qual_ok;                /* 0 for quals like key == 1 && key > 2 */
  79         uint16          numberOfKeys;   /* number of keys */
  80         uint16          numberOfFirstKeys;              /* number of keys for 1st
  81                                                                                  * attribute */
  82         ScanKey         keyData;                /* key descriptor */
  83 } BTScanOpaqueData;
  84
  85 typedef BTScanOpaqueData *BTScanOpaque;
  86
  87 /*
  88  *      BTItems are what we store in the btree.  Each item has an index
  89  *      tuple, including key and pointer values.  In addition, we must
  90  *      guarantee that all tuples in the index are unique, in order to
  91  *      satisfy some assumptions in Lehman and Yao.  The way that we do
  92  *      this is by generating a new OID for every insertion that we do in
  93  *      the tree.  This adds eight bytes to the size of btree index
  94  *      tuples.  Note that we do not use the OID as part of a composite
  95  *      key; the OID only serves as a unique identifier for a given index
  96  *      tuple (logical position within a page).
  97  *
  98  *      New comments:
  99  *      actually, we must guarantee that all tuples in A LEVEL
 100  *      are unique, not in ALL INDEX. So, we can use bti_itup->t_tid
 101  *      as unique identifier for a given index tuple (logical position
 102  *      within a level).        - vadim 04/09/97
 103  */
 104
 105 typedef struct BTItemData
 106 {
 107         IndexTupleData bti_itup;
 108 } BTItemData;
 109
 110 typedef BTItemData *BTItem;
 111
 112 #define BTItemSame(i1, i2)        ( i1->bti_itup.t_tid.ip_blkid.bi_hi == \
 113                                                                 i2->bti_itup.t_tid.ip_blkid.bi_hi && \
 114                                                                 i1->bti_itup.t_tid.ip_blkid.bi_lo == \
 115                                                                 i2->bti_itup.t_tid.ip_blkid.bi_lo && \
 116                                                                 i1->bti_itup.t_tid.ip_posid == \
 117                                                                 i2->bti_itup.t_tid.ip_posid )
 118
 119 /*
 120  *      BTStackData -- As we descend a tree, we push the (key, pointer)
 121  *      pairs from internal nodes onto a private stack.  If we split a
 122  *      leaf, we use this stack to walk back up the tree and insert data
 123  *      into parent nodes (and possibly to split them, too).  Lehman and
 124  *      Yao's update algorithm guarantees that under no circumstances can
 125  *      our private stack give us an irredeemably bad picture up the tree.
 126  *      Again, see the paper for details.
 127  */
 128
 129 typedef struct BTStackData
 130 {
 131         BlockNumber bts_blkno;
 132         OffsetNumber bts_offset;
 133         BTItem          bts_btitem;
 134         struct BTStackData *bts_parent;
 135 } BTStackData;
 136
 137 typedef BTStackData *BTStack;
 138
 139 typedef struct BTPageState
 140 {
 141         Buffer          btps_buf;
 142         Page            btps_page;
 143         BTItem          btps_lastbti;
 144         OffsetNumber btps_lastoff;
 145         OffsetNumber btps_firstoff;
 146         int                     btps_level;
 147         bool            btps_doupper;
 148         struct BTPageState *btps_next;
 149 } BTPageState;
 150
 151 /*
 152  *      We need to be able to tell the difference between read and write
 153  *      requests for pages, in order to do locking correctly.
 154  */
 155
 156 #define BT_READ                 BUFFER_LOCK_SHARE
 157 #define BT_WRITE                BUFFER_LOCK_EXCLUSIVE
 158
 159 /*
 160  *      Similarly, the difference between insertion and non-insertion binary
 161  *      searches on a given page makes a difference when we're descending the
 162  *      tree.
 163  */
 164
 165 #define BT_INSERTION    0
 166 #define BT_DESCENT              1
 167
 168 /*
 169  *      In general, the btree code tries to localize its knowledge about
 170  *      page layout to a couple of routines.  However, we need a special
 171  *      value to indicate "no page number" in those places where we expect
 172  *      page numbers.
 173  */
 174
 175 #define P_NONE                  0
 176 #define P_LEFTMOST(opaque)              ((opaque)->btpo_prev == P_NONE)
 177 #define P_RIGHTMOST(opaque)             ((opaque)->btpo_next == P_NONE)
 178
 179 #define P_HIKEY                 ((OffsetNumber) 1)
 180 #define P_FIRSTKEY              ((OffsetNumber) 2)
 181
 182 /*
 183  *      Strategy numbers -- ordering of these is <, <=, =, >=, >
 184  */
 185
 186 #define BTLessStrategyNumber                    1
 187 #define BTLessEqualStrategyNumber               2
 188 #define BTEqualStrategyNumber                   3
 189 #define BTGreaterEqualStrategyNumber    4
 190 #define BTGreaterStrategyNumber                 5
 191 #define BTMaxStrategyNumber                             5
 192
 193 /*
 194  *      When a new operator class is declared, we require that the user
 195  *      supply us with an amproc procedure for determining whether, for
 196  *      two keys a and b, a < b, a = b, or a > b.  This routine must
 197  *      return < 0, 0, > 0, respectively, in these three cases.  Since we
 198  *      only have one such proc in amproc, it's number 1.
 199  */
 200
 201 #define BTORDER_PROC    1
 202
 203 /*
 204  * prototypes for functions in nbtinsert.c
 205  */
 206 extern InsertIndexResult _bt_doinsert(Relation rel, BTItem btitem,
 207                          bool index_is_unique, Relation heapRel);
 208 extern bool _bt_itemcmp(Relation rel, Size keysz, ScanKey scankey,
 209                         BTItem item1, BTItem item2, StrategyNumber strat);
 210
 211 /*
 212  * prototypes for functions in nbtpage.c
 213  */
 214 extern void _bt_metapinit(Relation rel);
 215 extern Buffer _bt_getroot(Relation rel, int access);
 216 extern Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access);
 217 extern void _bt_relbuf(Relation rel, Buffer buf, int access);
 218 extern void _bt_wrtbuf(Relation rel, Buffer buf);
 219 extern void _bt_wrtnorelbuf(Relation rel, Buffer buf);
 220 extern void _bt_pageinit(Page page, Size size);
 221 extern void _bt_metaproot(Relation rel, BlockNumber rootbknum, int level);
 222 extern Buffer _bt_getstackbuf(Relation rel, BTStack stack, int access);
 223 extern void _bt_pagedel(Relation rel, ItemPointer tid);
 224
 225 /*
 226  * prototypes for functions in nbtree.c
 227  */
 228 extern bool BuildingBtree;              /* in nbtree.c */
 229
 230 extern void btbuild(Relation heap, Relation index, int natts,
 231                 AttrNumber *attnum, IndexStrategy istrat, uint16 pcount,
 232                 Datum *params, FuncIndexInfo *finfo, PredInfo *predInfo);
 233 extern InsertIndexResult btinsert(Relation rel, Datum *datum, char *nulls,
 234                  ItemPointer ht_ctid, Relation heapRel);
 235 extern char *btgettuple(IndexScanDesc scan, ScanDirection dir);
 236 extern char *btbeginscan(Relation rel, bool fromEnd, uint16 keysz,
 237                         ScanKey scankey);
 238
 239 extern void btrescan(IndexScanDesc scan, bool fromEnd, ScanKey scankey);
 240 extern void btmovescan(IndexScanDesc scan, Datum v);
 241 extern void btendscan(IndexScanDesc scan);
 242 extern void btmarkpos(IndexScanDesc scan);
 243 extern void btrestrpos(IndexScanDesc scan);
 244 extern void btdelete(Relation rel, ItemPointer tid);
 245
 246 /*
 247  * prototypes for functions in nbtscan.c
 248  */
 249 extern void _bt_regscan(IndexScanDesc scan);
 250 extern void _bt_dropscan(IndexScanDesc scan);
 251 extern void _bt_adjscans(Relation rel, ItemPointer tid);
 252 extern void AtEOXact_nbtree(void);
 253
 254 /*
 255  * prototypes for functions in nbtsearch.c
 256  */
 257 extern BTStack _bt_search(Relation rel, int keysz, ScanKey scankey,
 258                    Buffer *bufP);
 259 extern Buffer _bt_moveright(Relation rel, Buffer buf, int keysz,
 260                           ScanKey scankey, int access);
 261 extern bool _bt_skeycmp(Relation rel, Size keysz, ScanKey scankey,
 262                         Page page, ItemId itemid, StrategyNumber strat);
 263 extern OffsetNumber _bt_binsrch(Relation rel, Buffer buf, int keysz,
 264                         ScanKey scankey, int srchtype);
 265 extern RetrieveIndexResult _bt_next(IndexScanDesc scan, ScanDirection dir);
 266 extern RetrieveIndexResult _bt_first(IndexScanDesc scan, ScanDirection dir);
 267 extern bool _bt_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir);
 268
 269 /*
 270  * prototypes for functions in nbtstrat.c
 271  */
 272 extern StrategyNumber _bt_getstrat(Relation rel, AttrNumber attno,
 273                          RegProcedure proc);
 274
 275 /*
 276  * prototypes for functions in nbtutils.c
 277  */
 278 extern ScanKey _bt_mkscankey(Relation rel, IndexTuple itup);
 279 extern ScanKey _bt_mkscankey_nodata(Relation rel);
 280 extern void _bt_freeskey(ScanKey skey);
 281 extern void _bt_freestack(BTStack stack);
 282 extern void _bt_orderkeys(Relation relation, BTScanOpaque so);
 283 extern bool _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, Size *keysok);
 284 extern BTItem _bt_formitem(IndexTuple itup);
 285
 286 /*
 287  * prototypes for functions in nbtsort.c
 288  */
 289
 290 typedef struct BTSpool BTSpool; /* opaque type known only within nbtsort.c */
 291
 292 extern BTSpool *_bt_spoolinit(Relation index, bool isunique);
 293 extern void _bt_spooldestroy(BTSpool *btspool);
 294 extern void _bt_spool(BTItem btitem, BTSpool *btspool);
 295 extern void _bt_leafbuild(BTSpool *btspool);
 296
 297 #endif   /* NBTREE_H */