PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
nbtree.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * nbtree.h
4  * header file for postgres btree access method implementation.
5  *
6  *
7  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * src/include/access/nbtree.h
11  *
12  *-------------------------------------------------------------------------
13  */
14 #ifndef NBTREE_H
15 #define NBTREE_H
16 
17 #include "access/amapi.h"
18 #include "access/itup.h"
19 #include "access/sdir.h"
20 #include "access/xlogreader.h"
21 #include "catalog/pg_index.h"
22 #include "lib/stringinfo.h"
23 #include "storage/bufmgr.h"
24 
25 /* There's room for a 16-bit vacuum cycle ID in BTPageOpaqueData */
26 typedef uint16 BTCycleId;
27 
28 /*
29  * BTPageOpaqueData -- At the end of every page, we store a pointer
30  * to both siblings in the tree. This is used to do forward/backward
31  * index scans. The next-page link is also critical for recovery when
32  * a search has navigated to the wrong page due to concurrent page splits
33  * or deletions; see src/backend/access/nbtree/README for more info.
34  *
35  * In addition, we store the page's btree level (counting upwards from
36  * zero at a leaf page) as well as some flag bits indicating the page type
37  * and status. If the page is deleted, we replace the level with the
38  * next-transaction-ID value indicating when it is safe to reclaim the page.
39  *
40  * We also store a "vacuum cycle ID". When a page is split while VACUUM is
41  * processing the index, a nonzero value associated with the VACUUM run is
42  * stored into both halves of the split page. (If VACUUM is not running,
43  * both pages receive zero cycleids.) This allows VACUUM to detect whether
44  * a page was split since it started, with a small probability of false match
45  * if the page was last split some exact multiple of MAX_BT_CYCLE_ID VACUUMs
46  * ago. Also, during a split, the BTP_SPLIT_END flag is cleared in the left
47  * (original) page, and set in the right page, but only if the next page
48  * to its right has a different cycleid.
49  *
50  * NOTE: the BTP_LEAF flag bit is redundant since level==0 could be tested
51  * instead.
52  */
53 
54 typedef struct BTPageOpaqueData
55 {
56  BlockNumber btpo_prev; /* left sibling, or P_NONE if leftmost */
57  BlockNumber btpo_next; /* right sibling, or P_NONE if rightmost */
58  union
59  {
60  uint32 level; /* tree level --- zero for leaf pages */
61  TransactionId xact; /* next transaction ID, if deleted */
62  } btpo;
63  uint16 btpo_flags; /* flag bits, see below */
64  BTCycleId btpo_cycleid; /* vacuum cycle ID of latest split */
66 
68 
69 /* Bits defined in btpo_flags */
70 #define BTP_LEAF (1 << 0) /* leaf page, i.e. not internal page */
71 #define BTP_ROOT (1 << 1) /* root page (has no parent) */
72 #define BTP_DELETED (1 << 2) /* page has been deleted from tree */
73 #define BTP_META (1 << 3) /* meta-page */
74 #define BTP_HALF_DEAD (1 << 4) /* empty, but still in tree */
75 #define BTP_SPLIT_END (1 << 5) /* rightmost page of split group */
76 #define BTP_HAS_GARBAGE (1 << 6) /* page has LP_DEAD tuples */
77 #define BTP_INCOMPLETE_SPLIT (1 << 7) /* right sibling's downlink is missing */
78 
79 /*
80  * The max allowed value of a cycle ID is a bit less than 64K. This is
81  * for convenience of pg_filedump and similar utilities: we want to use
82  * the last 2 bytes of special space as an index type indicator, and
83  * restricting cycle ID lets btree use that space for vacuum cycle IDs
84  * while still allowing index type to be identified.
85  */
86 #define MAX_BT_CYCLE_ID 0xFF7F
87 
88 
89 /*
90  * The Meta page is always the first page in the btree index.
91  * Its primary purpose is to point to the location of the btree root page.
92  * We also point to the "fast" root, which is the current effective root;
93  * see README for discussion.
94  */
95 
96 typedef struct BTMetaPageData
97 {
98  uint32 btm_magic; /* should contain BTREE_MAGIC */
99  uint32 btm_version; /* should contain BTREE_VERSION */
100  BlockNumber btm_root; /* current root location */
101  uint32 btm_level; /* tree level of the root page */
102  BlockNumber btm_fastroot; /* current "fast" root location */
103  uint32 btm_fastlevel; /* tree level of the "fast" root page */
105 
106 #define BTPageGetMeta(p) \
107  ((BTMetaPageData *) PageGetContents(p))
108 
109 #define BTREE_METAPAGE 0 /* first page is meta */
110 #define BTREE_MAGIC 0x053162 /* magic number of btree pages */
111 #define BTREE_VERSION 2 /* current version number */
112 
113 /*
114  * Maximum size of a btree index entry, including its tuple header.
115  *
116  * We actually need to be able to fit three items on every page,
117  * so restrict any one item to 1/3 the per-page available space.
118  */
119 #define BTMaxItemSize(page) \
120  MAXALIGN_DOWN((PageGetPageSize(page) - \
121  MAXALIGN(SizeOfPageHeaderData + 3*sizeof(ItemIdData)) - \
122  MAXALIGN(sizeof(BTPageOpaqueData))) / 3)
123 
124 /*
125  * The leaf-page fillfactor defaults to 90% but is user-adjustable.
126  * For pages above the leaf level, we use a fixed 70% fillfactor.
127  * The fillfactor is applied during index build and when splitting
128  * a rightmost page; when splitting non-rightmost pages we try to
129  * divide the data equally.
130  */
131 #define BTREE_MIN_FILLFACTOR 10
132 #define BTREE_DEFAULT_FILLFACTOR 90
133 #define BTREE_NONLEAF_FILLFACTOR 70
134 
135 /*
136  * Test whether two btree entries are "the same".
137  *
138  * Old comments:
139  * In addition, we must guarantee that all tuples in the index are unique,
140  * in order to satisfy some assumptions in Lehman and Yao. The way that we
141  * do this is by generating a new OID for every insertion that we do in the
142  * tree. This adds eight bytes to the size of btree index tuples. Note
143  * that we do not use the OID as part of a composite key; the OID only
144  * serves as a unique identifier for a given index tuple (logical position
145  * within a page).
146  *
147  * New comments:
148  * actually, we must guarantee that all tuples in A LEVEL
149  * are unique, not in ALL INDEX. So, we can use the t_tid
150  * as unique identifier for a given index tuple (logical position
151  * within a level). - vadim 04/09/97
152  */
153 #define BTTidSame(i1, i2) \
154  ( (i1).ip_blkid.bi_hi == (i2).ip_blkid.bi_hi && \
155  (i1).ip_blkid.bi_lo == (i2).ip_blkid.bi_lo && \
156  (i1).ip_posid == (i2).ip_posid )
157 #define BTEntrySame(i1, i2) \
158  BTTidSame((i1)->t_tid, (i2)->t_tid)
159 
160 
161 /*
162  * In general, the btree code tries to localize its knowledge about
163  * page layout to a couple of routines. However, we need a special
164  * value to indicate "no page number" in those places where we expect
165  * page numbers. We can use zero for this because we never need to
166  * make a pointer to the metadata page.
167  */
168 
169 #define P_NONE 0
170 
171 /*
172  * Macros to test whether a page is leftmost or rightmost on its tree level,
173  * as well as other state info kept in the opaque data.
174  */
175 #define P_LEFTMOST(opaque) ((opaque)->btpo_prev == P_NONE)
176 #define P_RIGHTMOST(opaque) ((opaque)->btpo_next == P_NONE)
177 #define P_ISLEAF(opaque) ((opaque)->btpo_flags & BTP_LEAF)
178 #define P_ISROOT(opaque) ((opaque)->btpo_flags & BTP_ROOT)
179 #define P_ISDELETED(opaque) ((opaque)->btpo_flags & BTP_DELETED)
180 #define P_ISHALFDEAD(opaque) ((opaque)->btpo_flags & BTP_HALF_DEAD)
181 #define P_IGNORE(opaque) ((opaque)->btpo_flags & (BTP_DELETED|BTP_HALF_DEAD))
182 #define P_HAS_GARBAGE(opaque) ((opaque)->btpo_flags & BTP_HAS_GARBAGE)
183 #define P_INCOMPLETE_SPLIT(opaque) ((opaque)->btpo_flags & BTP_INCOMPLETE_SPLIT)
184 
185 /*
186  * Lehman and Yao's algorithm requires a ``high key'' on every non-rightmost
187  * page. The high key is not a data key, but gives info about what range of
188  * keys is supposed to be on this page. The high key on a page is required
189  * to be greater than or equal to any data key that appears on the page.
190  * If we find ourselves trying to insert a key > high key, we know we need
191  * to move right (this should only happen if the page was split since we
192  * examined the parent page).
193  *
194  * Our insertion algorithm guarantees that we can use the initial least key
195  * on our right sibling as the high key. Once a page is created, its high
196  * key changes only if the page is split.
197  *
198  * On a non-rightmost page, the high key lives in item 1 and data items
199  * start in item 2. Rightmost pages have no high key, so we store data
200  * items beginning in item 1.
201  */
202 
203 #define P_HIKEY ((OffsetNumber) 1)
204 #define P_FIRSTKEY ((OffsetNumber) 2)
205 #define P_FIRSTDATAKEY(opaque) (P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY)
206 
207 
208 /*
209  * Operator strategy numbers for B-tree have been moved to access/stratnum.h,
210  * because many places need to use them in ScanKeyInit() calls.
211  *
212  * The strategy numbers are chosen so that we can commute them by
213  * subtraction, thus:
214  */
215 #define BTCommuteStrategyNumber(strat) (BTMaxStrategyNumber + 1 - (strat))
216 
217 /*
218  * When a new operator class is declared, we require that the user
219  * supply us with an amproc procedure (BTORDER_PROC) for determining
220  * whether, for two keys a and b, a < b, a = b, or a > b. This routine
221  * must return < 0, 0, > 0, respectively, in these three cases. (It must
222  * not return INT_MIN, since we may negate the result before using it.)
223  *
224  * To facilitate accelerated sorting, an operator class may choose to
225  * offer a second procedure (BTSORTSUPPORT_PROC). For full details, see
226  * src/include/utils/sortsupport.h.
227  */
228 
229 #define BTORDER_PROC 1
230 #define BTSORTSUPPORT_PROC 2
231 #define BTNProcs 2
232 
233 /*
234  * We need to be able to tell the difference between read and write
235  * requests for pages, in order to do locking correctly.
236  */
237 
238 #define BT_READ BUFFER_LOCK_SHARE
239 #define BT_WRITE BUFFER_LOCK_EXCLUSIVE
240 
241 /*
242  * BTStackData -- As we descend a tree, we push the (location, downlink)
243  * pairs from internal pages onto a private stack. If we split a
244  * leaf, we use this stack to walk back up the tree and insert data
245  * into parent pages (and possibly to split them, too). Lehman and
246  * Yao's update algorithm guarantees that under no circumstances can
247  * our private stack give us an irredeemably bad picture up the tree.
248  * Again, see the paper for details.
249  */
250 
251 typedef struct BTStackData
252 {
257 } BTStackData;
258 
260 
261 /*
262  * BTScanOpaqueData is the btree-private state needed for an indexscan.
263  * This consists of preprocessed scan keys (see _bt_preprocess_keys() for
264  * details of the preprocessing), information about the current location
265  * of the scan, and information about the marked location, if any. (We use
266  * BTScanPosData to represent the data needed for each of current and marked
267  * locations.) In addition we can remember some known-killed index entries
268  * that must be marked before we can move off the current page.
269  *
270  * Index scans work a page at a time: we pin and read-lock the page, identify
271  * all the matching items on the page and save them in BTScanPosData, then
272  * release the read-lock while returning the items to the caller for
273  * processing. This approach minimizes lock/unlock traffic. Note that we
274  * keep the pin on the index page until the caller is done with all the items
275  * (this is needed for VACUUM synchronization, see nbtree/README). When we
276  * are ready to step to the next page, if the caller has told us any of the
277  * items were killed, we re-lock the page to mark them killed, then unlock.
278  * Finally we drop the pin and step to the next page in the appropriate
279  * direction.
280  *
281  * If we are doing an index-only scan, we save the entire IndexTuple for each
282  * matched item, otherwise only its heap TID and offset. The IndexTuples go
283  * into a separate workspace array; each BTScanPosItem stores its tuple's
284  * offset within that array.
285  */
286 
287 typedef struct BTScanPosItem /* what we remember about each match */
288 {
289  ItemPointerData heapTid; /* TID of referenced heap item */
290  OffsetNumber indexOffset; /* index item's location within page */
291  LocationIndex tupleOffset; /* IndexTuple's offset in workspace, if any */
292 } BTScanPosItem;
293 
294 typedef struct BTScanPosData
295 {
296  Buffer buf; /* if valid, the buffer is pinned */
297 
298  XLogRecPtr lsn; /* pos in the WAL stream when page was read */
299  BlockNumber currPage; /* page referenced by items array */
300  BlockNumber nextPage; /* page's right link when we scanned it */
301 
302  /*
303  * moreLeft and moreRight track whether we think there may be matching
304  * index entries to the left and right of the current page, respectively.
305  * We can clear the appropriate one of these flags when _bt_checkkeys()
306  * returns continuescan = false.
307  */
308  bool moreLeft;
309  bool moreRight;
310 
311  /*
312  * If we are doing an index-only scan, nextTupleOffset is the first free
313  * location in the associated tuple storage workspace.
314  */
316 
317  /*
318  * The items array is always ordered in index order (ie, increasing
319  * indexoffset). When scanning backwards it is convenient to fill the
320  * array back-to-front, so we start at the last slot and fill downwards.
321  * Hence we need both a first-valid-entry and a last-valid-entry counter.
322  * itemIndex is a cursor showing which entry was last returned to caller.
323  */
324  int firstItem; /* first valid index in items[] */
325  int lastItem; /* last valid index in items[] */
326  int itemIndex; /* current index in items[] */
327 
329 } BTScanPosData;
330 
332 
333 #define BTScanPosIsPinned(scanpos) \
334 ( \
335  AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
336  !BufferIsValid((scanpos).buf)), \
337  BufferIsValid((scanpos).buf) \
338 )
339 #define BTScanPosUnpin(scanpos) \
340  do { \
341  ReleaseBuffer((scanpos).buf); \
342  (scanpos).buf = InvalidBuffer; \
343  } while (0)
344 #define BTScanPosUnpinIfPinned(scanpos) \
345  do { \
346  if (BTScanPosIsPinned(scanpos)) \
347  BTScanPosUnpin(scanpos); \
348  } while (0)
349 
350 #define BTScanPosIsValid(scanpos) \
351 ( \
352  AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
353  !BufferIsValid((scanpos).buf)), \
354  BlockNumberIsValid((scanpos).currPage) \
355 )
356 #define BTScanPosInvalidate(scanpos) \
357  do { \
358  (scanpos).currPage = InvalidBlockNumber; \
359  (scanpos).nextPage = InvalidBlockNumber; \
360  (scanpos).buf = InvalidBuffer; \
361  (scanpos).lsn = InvalidXLogRecPtr; \
362  (scanpos).nextTupleOffset = 0; \
363  } while (0);
364 
365 /* We need one of these for each equality-type SK_SEARCHARRAY scan key */
366 typedef struct BTArrayKeyInfo
367 {
368  int scan_key; /* index of associated key in arrayKeyData */
369  int cur_elem; /* index of current element in elem_values */
370  int mark_elem; /* index of marked element in elem_values */
371  int num_elems; /* number of elems in current array value */
372  Datum *elem_values; /* array of num_elems Datums */
374 
375 typedef struct BTScanOpaqueData
376 {
377  /* these fields are set by _bt_preprocess_keys(): */
378  bool qual_ok; /* false if qual can never be satisfied */
379  int numberOfKeys; /* number of preprocessed scan keys */
380  ScanKey keyData; /* array of preprocessed scan keys */
381 
382  /* workspace for SK_SEARCHARRAY support */
383  ScanKey arrayKeyData; /* modified copy of scan->keyData */
384  int numArrayKeys; /* number of equality-type array keys (-1 if
385  * there are any unsatisfiable array keys) */
386  int arrayKeyCount; /* count indicating number of array scan keys
387  * processed */
388  BTArrayKeyInfo *arrayKeys; /* info about each equality-type array key */
389  MemoryContext arrayContext; /* scan-lifespan context for array data */
390 
391  /* info about killed items if any (killedItems is NULL if never used) */
392  int *killedItems; /* currPos.items indexes of killed items */
393  int numKilled; /* number of currently stored items */
394 
395  /*
396  * If we are doing an index-only scan, these are the tuple storage
397  * workspaces for the currPos and markPos respectively. Each is of size
398  * BLCKSZ, so it can hold as much as a full page's worth of tuples.
399  */
400  char *currTuples; /* tuple storage for currPos */
401  char *markTuples; /* tuple storage for markPos */
402 
403  /*
404  * If the marked position is on the same page as current position, we
405  * don't use markPos, but just keep the marked itemIndex in markItemIndex
406  * (all the rest of currPos is valid for the mark position). Hence, to
407  * determine if there is a mark, first look at markItemIndex, then at
408  * markPos.
409  */
410  int markItemIndex; /* itemIndex, or -1 if not valid */
411 
412  /* keep these last in struct for efficiency */
413  BTScanPosData currPos; /* current position data */
414  BTScanPosData markPos; /* marked position, if any */
416 
418 
419 /*
420  * We use some private sk_flags bits in preprocessed scan keys. We're allowed
421  * to use bits 16-31 (see skey.h). The uppermost bits are copied from the
422  * index's indoption[] array entry for the index attribute.
423  */
424 #define SK_BT_REQFWD 0x00010000 /* required to continue forward scan */
425 #define SK_BT_REQBKWD 0x00020000 /* required to continue backward scan */
426 #define SK_BT_INDOPTION_SHIFT 24 /* must clear the above bits */
427 #define SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)
428 #define SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)
429 
430 /*
431  * external entry points for btree, in nbtree.c
432  */
434  struct IndexInfo *indexInfo);
435 extern void btbuildempty(Relation index);
436 extern bool btinsert(Relation rel, Datum *values, bool *isnull,
437  ItemPointer ht_ctid, Relation heapRel,
438  IndexUniqueCheck checkUnique,
439  struct IndexInfo *indexInfo);
440 extern IndexScanDesc btbeginscan(Relation rel, int nkeys, int norderbys);
441 extern Size btestimateparallelscan(void);
442 extern void btinitparallelscan(void *target);
443 extern bool btgettuple(IndexScanDesc scan, ScanDirection dir);
444 extern int64 btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
445 extern void btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
446  ScanKey orderbys, int norderbys);
447 extern void btparallelrescan(IndexScanDesc scan);
448 extern void btendscan(IndexScanDesc scan);
449 extern void btmarkpos(IndexScanDesc scan);
450 extern void btrestrpos(IndexScanDesc scan);
452  IndexBulkDeleteResult *stats,
454  void *callback_state);
456  IndexBulkDeleteResult *stats);
457 extern bool btcanreturn(Relation index, int attno);
458 
459 /*
460  * prototypes for internal functions in nbtree.c
461  */
462 extern bool _bt_parallel_seize(IndexScanDesc scan, BlockNumber *pageno);
463 extern void _bt_parallel_release(IndexScanDesc scan, BlockNumber scan_page);
464 extern void _bt_parallel_done(IndexScanDesc scan);
466 
467 /*
468  * prototypes for functions in nbtinsert.c
469  */
470 extern bool _bt_doinsert(Relation rel, IndexTuple itup,
471  IndexUniqueCheck checkUnique, Relation heapRel);
472 extern Buffer _bt_getstackbuf(Relation rel, BTStack stack, int access);
473 extern void _bt_finish_split(Relation rel, Buffer bbuf, BTStack stack);
474 
475 /*
476  * prototypes for functions in nbtpage.c
477  */
478 extern void _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level);
479 extern Buffer _bt_getroot(Relation rel, int access);
480 extern Buffer _bt_gettrueroot(Relation rel);
481 extern int _bt_getrootheight(Relation rel);
482 extern void _bt_checkpage(Relation rel, Buffer buf);
483 extern Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access);
484 extern Buffer _bt_relandgetbuf(Relation rel, Buffer obuf,
485  BlockNumber blkno, int access);
486 extern void _bt_relbuf(Relation rel, Buffer buf);
487 extern void _bt_pageinit(Page page, Size size);
488 extern bool _bt_page_recyclable(Page page);
489 extern void _bt_delitems_delete(Relation rel, Buffer buf,
490  OffsetNumber *itemnos, int nitems, Relation heapRel);
491 extern void _bt_delitems_vacuum(Relation rel, Buffer buf,
492  OffsetNumber *itemnos, int nitems,
493  BlockNumber lastBlockVacuumed);
494 extern int _bt_pagedel(Relation rel, Buffer buf);
495 
496 /*
497  * prototypes for functions in nbtsearch.c
498  */
499 extern BTStack _bt_search(Relation rel,
500  int keysz, ScanKey scankey, bool nextkey,
501  Buffer *bufP, int access, Snapshot snapshot);
502 extern Buffer _bt_moveright(Relation rel, Buffer buf, int keysz,
503  ScanKey scankey, bool nextkey, bool forupdate, BTStack stack,
504  int access, Snapshot snapshot);
505 extern OffsetNumber _bt_binsrch(Relation rel, Buffer buf, int keysz,
506  ScanKey scankey, bool nextkey);
507 extern int32 _bt_compare(Relation rel, int keysz, ScanKey scankey,
508  Page page, OffsetNumber offnum);
509 extern bool _bt_first(IndexScanDesc scan, ScanDirection dir);
510 extern bool _bt_next(IndexScanDesc scan, ScanDirection dir);
511 extern Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost,
512  Snapshot snapshot);
513 
514 /*
515  * prototypes for functions in nbtutils.c
516  */
517 extern ScanKey _bt_mkscankey(Relation rel, IndexTuple itup);
519 extern void _bt_freeskey(ScanKey skey);
520 extern void _bt_freestack(BTStack stack);
521 extern void _bt_preprocess_array_keys(IndexScanDesc scan);
522 extern void _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir);
523 extern bool _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir);
524 extern void _bt_mark_array_keys(IndexScanDesc scan);
525 extern void _bt_restore_array_keys(IndexScanDesc scan);
526 extern void _bt_preprocess_keys(IndexScanDesc scan);
528  Page page, OffsetNumber offnum,
529  ScanDirection dir, bool *continuescan);
530 extern void _bt_killitems(IndexScanDesc scan);
533 extern void _bt_end_vacuum(Relation rel);
534 extern void _bt_end_vacuum_callback(int code, Datum arg);
535 extern Size BTreeShmemSize(void);
536 extern void BTreeShmemInit(void);
537 extern bytea *btoptions(Datum reloptions, bool validate);
538 extern bool btproperty(Oid index_oid, int attno,
539  IndexAMProperty prop, const char *propname,
540  bool *res, bool *isnull);
541 
542 /*
543  * prototypes for functions in nbtvalidate.c
544  */
545 extern bool btvalidate(Oid opclassoid);
546 
547 /*
548  * prototypes for functions in nbtsort.c
549  */
550 typedef struct BTSpool BTSpool; /* opaque type known only within nbtsort.c */
551 
553  bool isunique, bool isdead);
554 extern void _bt_spooldestroy(BTSpool *btspool);
555 extern void _bt_spool(BTSpool *btspool, ItemPointer self,
556  Datum *values, bool *isnull);
557 extern void _bt_leafbuild(BTSpool *btspool, BTSpool *spool2);
558 
559 #endif /* NBTREE_H */
void btparallelrescan(IndexScanDesc scan)
Definition: nbtree.c:726
BTCycleId _bt_start_vacuum(Relation rel)
Definition: nbtutils.c:1907
void btendscan(IndexScanDesc scan)
Definition: nbtree.c:580
bool _bt_page_recyclable(Page page)
Definition: nbtpage.c:744
struct BTMetaPageData BTMetaPageData
bool _bt_first(IndexScanDesc scan, ScanDirection dir)
Definition: nbtsearch.c:536
bool _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:547
BlockNumber btpo_next
Definition: nbtree.h:57
void _bt_preprocess_keys(IndexScanDesc scan)
Definition: nbtutils.c:745
void _bt_spool(BTSpool *btspool, ItemPointer self, Datum *values, bool *isnull)
Definition: nbtsort.c:190
IndexAMProperty
Definition: amapi.h:34
int _bt_getrootheight(Relation rel)
Definition: nbtpage.c:435
bool moreRight
Definition: nbtree.h:309
uint32 TransactionId
Definition: c.h:393
uint32 btm_version
Definition: nbtree.h:99
BTScanPosItem items[MaxIndexTuplesPerPage]
Definition: nbtree.h:328
void _bt_pageinit(Page page, Size size)
Definition: nbtpage.c:732
int mark_elem
Definition: nbtree.h:370
MemoryContext arrayContext
Definition: nbtree.h:389
void _bt_checkpage(Relation rel, Buffer buf)
Definition: nbtpage.c:503
int itemIndex
Definition: nbtree.h:326
char * currTuples
Definition: nbtree.h:400
uint32 btm_magic
Definition: nbtree.h:98
void _bt_freeskey(ScanKey skey)
Definition: nbtutils.c:155
void _bt_finish_split(Relation rel, Buffer bbuf, BTStack stack)
Definition: nbtinsert.c:1745
BlockNumber currPage
Definition: nbtree.h:299
IndexBulkDeleteResult * btbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
Definition: nbtree.c:917
int32 _bt_compare(Relation rel, int keysz, ScanKey scankey, Page page, OffsetNumber offnum)
Definition: nbtsearch.c:428
BTStackData * BTStack
Definition: nbtree.h:259
BTSpool * _bt_spoolinit(Relation heap, Relation index, bool isunique, bool isdead)
Definition: nbtsort.c:152
void _bt_delitems_vacuum(Relation rel, Buffer buf, OffsetNumber *itemnos, int nitems, BlockNumber lastBlockVacuumed)
Definition: nbtpage.c:789
OffsetNumber indexOffset
Definition: nbtree.h:290
Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access)
Definition: nbtpage.c:570
uint32 BlockNumber
Definition: block.h:31
void btinitparallelscan(void *target)
Definition: nbtree.c:711
void _bt_end_vacuum_callback(int code, Datum arg)
Definition: nbtutils.c:1992
unsigned int Oid
Definition: postgres_ext.h:31
Datum * elem_values
Definition: nbtree.h:372
bool moreLeft
Definition: nbtree.h:308
IndexTupleData bts_btentry
Definition: nbtree.h:255
TransactionId xact
Definition: nbtree.h:61
void btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: nbtree.c:520
BTPageOpaqueData * BTPageOpaque
Definition: nbtree.h:67
struct BTScanPosData BTScanPosData
union BTPageOpaqueData::@39 btpo
Relation heap
Definition: nbtsort.c:88
signed int int32
Definition: c.h:253
uint16 OffsetNumber
Definition: off.h:24
IndexBuildResult * btbuild(Relation heap, Relation index, struct IndexInfo *indexInfo)
Definition: nbtree.c:174
Definition: type.h:90
void _bt_leafbuild(BTSpool *btspool, BTSpool *spool2)
Definition: nbtsort.c:201
void _bt_parallel_done(IndexScanDesc scan)
Definition: nbtree.c:848
BTStack _bt_search(Relation rel, int keysz, ScanKey scankey, bool nextkey, Buffer *bufP, int access, Snapshot snapshot)
Definition: nbtsearch.c:97
IndexUniqueCheck
Definition: genam.h:111
bool _bt_doinsert(Relation rel, IndexTuple itup, IndexUniqueCheck checkUnique, Relation heapRel)
Definition: nbtinsert.c:108
int nextTupleOffset
Definition: nbtree.h:315
int lastItem
Definition: nbtree.h:325
struct BTPageOpaqueData BTPageOpaqueData
bool btcanreturn(Relation index, int attno)
Definition: nbtree.c:1390
BlockNumber btm_fastroot
Definition: nbtree.h:102
Buffer _bt_moveright(Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey, bool forupdate, BTStack stack, int access, Snapshot snapshot)
Definition: nbtsearch.c:214
void _bt_mark_array_keys(IndexScanDesc scan)
Definition: nbtutils.c:606
unsigned short uint16
Definition: c.h:264
BTScanPosData markPos
Definition: nbtree.h:414
uint16 BTCycleId
Definition: nbtree.h:26
void _bt_parallel_advance_array_keys(IndexScanDesc scan)
Definition: nbtree.c:889
BTScanOpaqueData * BTScanOpaque
Definition: nbtree.h:417
void _bt_spooldestroy(BTSpool *btspool)
Definition: nbtsort.c:180
struct BTArrayKeyInfo BTArrayKeyInfo
bool isunique
Definition: nbtsort.c:90
BTCycleId btpo_cycleid
Definition: nbtree.h:64
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:49
struct BTScanPosItem BTScanPosItem
int cur_elem
Definition: nbtree.h:369
IndexTuple _bt_checkkeys(IndexScanDesc scan, Page page, OffsetNumber offnum, ScanDirection dir, bool *continuescan)
Definition: nbtutils.c:1359
int numArrayKeys
Definition: nbtree.h:384
BlockNumber btpo_prev
Definition: nbtree.h:56
OffsetNumber bts_offset
Definition: nbtree.h:254
static char * buf
Definition: pg_test_fsync.c:65
bool btvalidate(Oid opclassoid)
Definition: nbtvalidate.c:38
IndexScanDesc btbeginscan(Relation rel, int nkeys, int norderbys)
Definition: nbtree.c:474
int arrayKeyCount
Definition: nbtree.h:386
ScanDirection
Definition: sdir.h:22
void BTreeShmemInit(void)
Definition: nbtutils.c:2014
char * markTuples
Definition: nbtree.h:401
void btrestrpos(IndexScanDesc scan)
Definition: nbtree.c:646
unsigned int uint32
Definition: c.h:265
int firstItem
Definition: nbtree.h:324
BTCycleId _bt_vacuum_cycleid(Relation rel)
Definition: nbtutils.c:1873
Size btestimateparallelscan(void)
Definition: nbtree.c:702
void _bt_end_vacuum(Relation rel)
Definition: nbtutils.c:1964
void _bt_freestack(BTStack stack)
Definition: nbtutils.c:164
ScanKey arrayKeyData
Definition: nbtree.h:383
void _bt_parallel_release(IndexScanDesc scan, BlockNumber scan_page)
Definition: nbtree.c:825
BTScanPosData * BTScanPos
Definition: nbtree.h:331
uint32 btm_fastlevel
Definition: nbtree.h:103
uint32 level
Definition: nbtree.h:60
bool _bt_next(IndexScanDesc scan, ScanDirection dir)
Definition: nbtsearch.c:1129
IndexBulkDeleteResult * btvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
Definition: nbtree.c:947
uintptr_t Datum
Definition: postgres.h:374
int num_elems
Definition: nbtree.h:371
uint16 LocationIndex
Definition: bufpage.h:83
BlockNumber btm_root
Definition: nbtree.h:100
void _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level)
Definition: nbtpage.c:49
bool btproperty(Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
Definition: nbtutils.c:2054
BlockNumber bts_blkno
Definition: nbtree.h:253
void _bt_relbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:720
int markItemIndex
Definition: nbtree.h:410
void _bt_killitems(IndexScanDesc scan)
Definition: nbtutils.c:1732
int * killedItems
Definition: nbtree.h:392
uint64 XLogRecPtr
Definition: xlogdefs.h:21
void _bt_delitems_delete(Relation rel, Buffer buf, OffsetNumber *itemnos, int nitems, Relation heapRel)
Definition: nbtpage.c:862
void _bt_restore_array_keys(IndexScanDesc scan)
Definition: nbtutils.c:625
Buffer _bt_getroot(Relation rel, int access)
Definition: nbtpage.c:104
Buffer _bt_relandgetbuf(Relation rel, Buffer obuf, BlockNumber blkno, int access)
Definition: nbtpage.c:701
size_t Size
Definition: c.h:352
OffsetNumber _bt_binsrch(Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey)
Definition: nbtsearch.c:323
int numberOfKeys
Definition: nbtree.h:379
struct BTStackData * bts_parent
Definition: nbtree.h:256
ItemPointerData heapTid
Definition: nbtree.h:289
BlockNumber nextPage
Definition: nbtree.h:300
static Datum values[MAXATTR]
Definition: bootstrap.c:162
int64 btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: nbtree.c:416
BTScanPosData currPos
Definition: nbtree.h:413
bool btgettuple(IndexScanDesc scan, ScanDirection dir)
Definition: nbtree.c:342
#define MaxIndexTuplesPerPage
Definition: itup.h:137
ScanKey keyData
Definition: nbtree.h:380
void btmarkpos(IndexScanDesc scan)
Definition: nbtree.c:616
uint32 btm_level
Definition: nbtree.h:101
Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost, Snapshot snapshot)
Definition: nbtsearch.c:1764
BTArrayKeyInfo * arrayKeys
Definition: nbtree.h:388
void _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:521
void * arg
Size BTreeShmemSize(void)
Definition: nbtutils.c:2001
Definition: c.h:434
ScanKey _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:62
XLogRecPtr lsn
Definition: nbtree.h:298
Buffer buf
Definition: nbtree.h:296
bool btinsert(Relation rel, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, struct IndexInfo *indexInfo)
Definition: nbtree.c:319
bool _bt_parallel_seize(IndexScanDesc scan, BlockNumber *pageno)
Definition: nbtree.c:767
LocationIndex tupleOffset
Definition: nbtree.h:291
uint16 btpo_flags
Definition: nbtree.h:63
bytea * btoptions(Datum reloptions, bool validate)
Definition: nbtutils.c:2042
int Buffer
Definition: buf.h:23
struct BTStackData BTStackData
int scan_key
Definition: nbtree.h:368
void btbuildempty(Relation index)
Definition: nbtree.c:283
bool(* IndexBulkDeleteCallback)(ItemPointer itemptr, void *state)
Definition: genam.h:83
struct BTScanOpaqueData BTScanOpaqueData
void _bt_preprocess_array_keys(IndexScanDesc scan)
Definition: nbtutils.c:192
int _bt_pagedel(Relation rel, Buffer buf)
Definition: nbtpage.c:1109
Buffer _bt_getstackbuf(Relation rel, BTStack stack, int access)
Definition: nbtinsert.c:1804
Pointer Page
Definition: bufpage.h:74
Buffer _bt_gettrueroot(Relation rel)
Definition: nbtpage.c:341
ScanKey _bt_mkscankey_nodata(Relation rel)
Definition: nbtutils.c:115