1/*-------------------------------------------------------------------------
4 * interface routines for the postgres GiST index access method.
7 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/access/gist/gist.c
13 *-------------------------------------------------------------------------
25#include "utils/fmgrprotos.h"
30/* non-export function prototypes */
38 bool unlockbuf,
bool unlockleftchild);
45 #define ROTATEDIST(d) do { \
46 SplitPageLayout *tmp = (SplitPageLayout *) palloc0(sizeof(SplitPageLayout)); \
47 tmp->block.blkno = InvalidBlockNumber; \
48 tmp->buffer = InvalidBuffer; \
55 * GiST handler function: return IndexAmRoutine with access method parameters
120 * Create and return a temporary memory context for use by GiST. We
121 * _always_ invoke user-provided methods in a temporary memory
122 * context, so that memory leaks in those functions cannot cause
123 * problems. Also, we use some additional temporary contexts in the
124 * GiST code itself, to avoid the need to do some awkward manual
131 "GiST temporary context",
136 * gistbuildempty() -- build an empty gist index in the initialization fork
143 /* Initialize the root page */
147 /* Initialize and xlog buffer */
154 /* Unlock and release the buffer */
159 * gistinsert -- wrapper for GiST tuple insertion.
161 * This is the public interface routine for tuple insertion in GiSTs.
162 * It doesn't do any work; just locks the relation and passes the buck.
175 /* Initialize GISTSTATE cache if first call in this statement */
176 if (giststate == NULL)
188 itup->t_tid = *ht_ctid;
201 * Place tuples from 'itup' to 'buffer'. If 'oldoffnum' is valid, the tuple
202 * at that offset is atomically removed along with inserting the new tuples.
203 * This is used to replace a tuple with a new one.
205 * If 'leftchildbuf' is valid, we're inserting the downlink for the page
206 * to the right of 'leftchildbuf', or updating the downlink for 'leftchildbuf'.
207 * F_FOLLOW_RIGHT flag on 'leftchildbuf' is cleared and NSN is set.
209 * If 'markfollowright' is true and the page is split, the left child is
210 * marked with F_FOLLOW_RIGHT flag. That is the normal case. During buffered
211 * index build, however, there is no concurrent access and the page splitting
212 * is done in a slightly simpler fashion, and false is passed.
214 * If there is not enough room on the page, it is split. All the split
215 * pages are kept pinned and locked and returned in *splitinfo, the caller
216 * is responsible for inserting the downlinks for them. However, if
217 * 'buffer' is the root page and it needs to be split, gistplacetopage()
218 * performs the split as one atomic operation, and *splitinfo is set to NIL.
219 * In that case, we continue to hold the root page locked, and the child
220 * pages are released; note that new tuple(s) are *not* on the root page
221 * but in one of the new child pages.
223 * If 'newblkno' is not NULL, returns the block number of page the first
224 * new/updated tuple was inserted to. Usually it's the given page, but could
225 * be its right sibling if the page was split.
227 * Returns 'true' if the page was split, 'false' otherwise.
236 bool markfollowright,
247 * Refuse to modify a page that's incompletely split. This should not
248 * happen because we finish any incomplete splits while we walk down the
249 * tree. However, it's remotely possible that another concurrent inserter
250 * splits a parent page, and errors out before completing the split. We
251 * will just throw an error in that case, and leave any split we had in
252 * progress unfinished too. The next insert that comes along will clean up
256 elog(
ERROR,
"concurrent GiST page split was incomplete");
258 /* should never try to insert to a deleted page */
264 * if isupdate, remove old key: This node's key has been modified, either
265 * because a child split occurred or because we needed to adjust our key
266 * for an insert in a child node. Therefore, remove the old version of
269 * for WAL replay, in the non-split case we handle this by setting up a
270 * one-element todelete array; in the split case, it's handled implicitly
271 * because the tuple vector passed to gistSplit won't include this tuple.
273 is_split =
gistnospace(page, itup, ntup, oldoffnum, freespace);
276 * If leaf page is full, try at first to delete dead tuples. And then
282 is_split =
gistnospace(page, itup, ntup, oldoffnum, freespace);
287 /* no space for insertion */
301 * Form index tuples vector to split. If we're replacing an old tuple,
302 * remove the old version from the vector.
307 /* on inner page we should remove old tuple */
312 memmove(itvec + pos, itvec + pos + 1,
sizeof(
IndexTuple) * (tlen - pos));
315 dist =
gistSplit(rel, page, itvec, tlen, giststate);
318 * Check that split didn't produce too many pages.
321 for (ptr = dist; ptr; ptr = ptr->
next)
323 /* in a root split, we'll add one more page to the list below */
327 elog(
ERROR,
"GiST page split into too many halves (%d, maximum %d)",
331 * Set up pages to work with. Allocate new buffers for all but the
332 * leftmost page. The original page becomes the new leftmost page, and
333 * is just replaced with the new contents.
335 * For a root-split, allocate new buffers for all child pages, the
336 * original page is overwritten with new root page containing
337 * downlinks to the new child pages.
342 /* save old rightlink and NSN */
350 /* clean all flags except F_LEAF */
355 for (; ptr; ptr = ptr->next)
357 /* Allocate new page */
368 * Now that we know which blocks the new pages go to, set up downlink
369 * tuples to point to them.
371 for (ptr = dist; ptr; ptr = ptr->
next)
378 * If this is a root split, we construct the new root page with the
379 * downlinks here directly, instead of requiring the caller to insert
380 * them. Add the new root page to the list along with the child pages.
392 /* Prepare a vector of all the downlinks */
393 for (ptr = dist; ptr; ptr = ptr->
next)
396 for (
i = 0, ptr = dist; ptr; ptr = ptr->
next)
397 downlinks[
i++] = ptr->itup;
410 /* Prepare split-info to be returned to caller */
411 for (ptr = dist; ptr; ptr = ptr->
next)
415 si->
buf = ptr->buffer;
417 *splitinfo =
lappend(*splitinfo, si);
422 * Fill all pages. All the pages are new, ie. freshly allocated empty
423 * pages, or a temporary copy of the old page.
425 for (ptr = dist; ptr; ptr = ptr->
next)
427 char *
data = (
char *) (ptr->list);
429 for (
int i = 0;
i < ptr->block.num;
i++)
437 * If this is the first inserted/updated tuple, let the caller
438 * know which page it landed on.
441 *newblkno = ptr->block.blkno;
446 /* Set up rightlinks */
449 ptr->next->block.blkno;
454 * Mark the all but the right-most page with the follow-right
455 * flag. It will be cleared as soon as the downlink is inserted
456 * into the parent, but this ensures that if we error out before
457 * that, the index is still consistent. (in buffering build mode,
458 * any error will abort the index build anyway, so this is not
461 if (ptr->next && !is_rootsplit && markfollowright)
467 * Copy the NSN of the original page to all pages. The
468 * F_FOLLOW_RIGHT flags ensure that scans will follow the
469 * rightlinks until the downlinks are inserted.
475 * gistXLogSplit() needs to WAL log a lot of pages, prepare WAL
476 * insertion for that. NB: The number of pages and data segments
477 * specified here must match the calculations in gistXLogSplit()!
485 * Must mark buffers dirty before XLogInsert, even though we'll still
486 * be changing their opaque fields below.
488 for (ptr = dist; ptr; ptr = ptr->
next)
494 * The first page in the chain was a temporary working copy meant to
495 * replace the old page. Copy it over the old page.
501 * Write the WAL record.
503 * If we're building a new index, however, we don't WAL-log changes
504 * yet. The LSN-NSN interlock between parent and child requires that
505 * LSNs never move backwards, so set the LSNs to a value that's
506 * smaller than any real or fake unlogged LSN that might be generated
507 * later. (There can't be any concurrent scans during index build, so
508 * we don't need to be able to detect concurrent splits yet.)
516 dist, oldrlink, oldnsn, leftchildbuf,
522 for (ptr = dist; ptr; ptr = ptr->
next)
526 * Return the new child buffers to the caller.
528 * If this was a root split, we've already inserted the downlink
529 * pointers, in the form of a new root page. Therefore we can release
530 * all the new buffers, and keep just the root page locked.
534 for (ptr = dist->
next; ptr; ptr = ptr->
next)
541 * Enough space. We always get here if ntup==0.
546 * Delete old tuple if any, then insert new tuple(s) if any. If
547 * possible, use the fast path of PageIndexTupleOverwrite.
553 /* One-for-one replacement, so use PageIndexTupleOverwrite */
556 elog(
ERROR,
"failed to add item to index page in \"%s\"",
561 /* Delete old, then append new tuple(s) to page */
568 /* Just append new tuples at the end of the page */
588 deloffs[0] = oldoffnum;
593 deloffs, ndeloffs, itup, ntup,
606 * If we inserted the downlink for a child page, set NSN and clear
607 * F_FOLLOW_RIGHT flag on the left child, so that concurrent scans know to
608 * follow the rightlink if and only if they looked at the parent page
609 * before we inserted the downlink.
611 * Note that we do this *after* writing the WAL record. That means that
612 * the possible full page image in the WAL record does not include these
613 * changes, and they must be replayed even if the page is restored from
614 * the full page image. There's a chicken-and-egg problem: if we updated
615 * the child pages first, we wouldn't know the recptr of the WAL record
616 * we're about to write.
634 * Workhorse routine for doing insertion into a GiST index. Note that
635 * this routine assumes it is invoked in a short-lived memory context,
636 * so it does not bother releasing palloc'd allocations.
647 bool xlocked =
false;
650 state.freespace = freespace;
652 state.heapRel = heapRel;
653 state.is_build = is_build;
655 /* Start from the root */
661 state.stack = stack = &firststack;
664 * Walk down along the path of smallest penalty, updating the parent
665 * pointers with the key we're inserting as we go. If we crash in the
666 * middle, the tree is consistent, although the possible parent updates
672 * If we split an internal page while descending the tree, we have to
673 * retry at the parent. (Normally, the LSN-NSN interlock below would
674 * also catch this and cause us to retry. But LSNs are not updated
675 * during index build.)
690 * Be optimistic and grab shared lock first. Swap it for an exclusive
691 * lock later if we need to update the page.
700 stack->
lsn = xlocked ?
705 * If this page was split but the downlink was never inserted to the
706 * parent because the inserting backend crashed before doing that, fix
716 /* someone might've completed the split when we unlocked */
733 * Concurrent split or page deletion detected. There's no
734 * guarantee that the downlink for this page is consistent with
735 * the tuple we're inserting anymore, so go back to parent and
736 * rechoose the best child.
747 * This is an internal page so continue to walk down the tree.
748 * Find the child node that has the minimum insertion penalty.
761 * Check that it's not a leftover invalid tuple from pre-9.1
765 (
errmsg(
"index \"%s\" contains an inner tuple marked as invalid",
767 errdetail(
"This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
768 errhint(
"Please REINDEX it.")));
771 * Check that the key representing the target child node is
772 * consistent with the key we're inserting. Update it if it's not.
778 * Swap shared lock for an exclusive one. Beware, the page may
779 * change while we unlock/lock the page...
790 /* the page was changed while we unlocked it, retry */
798 * We still hold the lock after gistinserttuple(), but it
799 * might have to split the page to make the updated tuple fit.
800 * In that case the updated tuple might migrate to the other
801 * half of the split, so we have to go back to the parent and
802 * descend back to the half that's a better fit for the new
809 * If this was a root split, the root page continues to be
810 * the parent and the updated tuple went to one of the
811 * child pages, so we just need to retry from the root
826 /* descend to the chosen child */
828 item->
blkno = childblkno;
831 state.stack = stack = item;
836 * Leaf page. Insert the new key. We've already updated all the
837 * parents on the way down, but we might have to split the page if
838 * it doesn't fit. gistinserttuple() will take care of that.
842 * Swap shared lock for an exclusive one. Be careful, the page may
843 * change while we unlock/lock the page...
856 * the only page that can become inner instead of leaf is
857 * the root page, so for root we should recheck it
862 * very rare situation: during unlock/lock index with
863 * number of pages = 1 was increased
871 * we don't need to check root split, because checking
872 * leaf/inner is enough to recognize split for root
880 * The page was split or deleted while we momentarily
881 * unlocked the page. Go back to parent.
890 /* now state.stack->(page, buffer and blkno) points to leaf page */
896 /* Release any pins we might still hold before exiting */
897 for (; stack; stack = stack->
parent)
905 * Traverse the tree to find path from root page to specified "child" block.
907 * returns a new insertion stack, starting from the parent of "child", up
908 * to the root. *downlinkoffnum is set to the offset of the downlink in the
909 * direct parent of child.
911 * To prevent deadlocks, this should lock only one page at a time.
934 /* Get next page to visit */
946 * Because we scan the index top-down, all the rest of the pages
947 * in the queue must be leaf pages as well.
953 /* currently, internal pages are never deleted */
959 * If F_FOLLOW_RIGHT is set, the page to the right doesn't have a
960 * downlink. This should not normally happen..
963 elog(
ERROR,
"concurrent GiST page split was incomplete");
969 * Page was split while we looked elsewhere. We didn't see the
970 * downlink to the right page when we scanned the parent, so add
971 * it to the queue now.
973 * Put the right page ahead of the queue, so that we visit it
974 * next. That's important, because if this is the lowest internal
975 * level, just above leaves, we might already have queued up some
976 * leaf pages, and we assume that there can't be any non-leaf
977 * pages behind leaf pages.
984 fifo =
lcons(ptr, fifo);
1003 /* Append this child to the list of pages to visit later */
1016 elog(
ERROR,
"failed to re-find parent of a page in index \"%s\", block %u",
1018 return NULL;
/* keep compiler quiet */
1022 * Updates the stack so that child->parent is the correct parent of the
1023 * child. child->parent must be exclusively locked on entry, and will
1024 * remain so at exit, but it might not be the same page anymore.
1039 /* Check if the downlink is still where it was before */
1045 return;
/* still there */
1049 * The page has changed since we looked. During normal operation, every
1050 * update of a page changes its LSN, so the LSN we memorized should have
1053 * During index build, however, we don't WAL-log the changes until we have
1054 * built the index, so the LSN doesn't change. There is no concurrent
1055 * activity during index build, but we might have changed the parent
1058 * We will also get here if child->downlinkoffnum is invalid. That happens
1059 * if 'parent' had been updated by an earlier call to this function on its
1060 * grandchild, which had to move right.
1066 * Scan the page to re-find the downlink. If the page was split, it might
1067 * have moved to a different page, so follow the right links until we find
1093 * End of chain and still didn't find parent. It's a very-very
1094 * rare situation when the root was split.
1105 * awful!!, we need search tree to find parent ... , but before we should
1106 * release all old parent
1109 ptr = child->
parent->
parent;
/* child->parent already released above */
1116 /* ok, find new path */
1119 /* read all buffers as expected by caller */
1120 /* note we don't lock them or gistcheckpage them here! */
1128 /* install new chain of parents to stack */
1131 /* make recursive call to normal processing */
1137 * Form a downlink pointer for the page in 'buf'.
1154 if (downlink == NULL)
1163 downlink = newdownlink;
1168 * If the page is completely empty, we can't form a meaningful downlink
1169 * for it. But we have to insert a downlink for the page. Any key will do,
1170 * as long as its consistent with the downlink of parent page, so that we
1171 * can legally insert it to the parent. A minimal one that matches as few
1172 * scans as possible would be best, to keep scans from doing useless work,
1173 * but we don't know how to construct that. So we just use the downlink of
1174 * the original page that was split - that's as far from optimal as it can
1197 * Complete the incomplete split of state->stack->page.
1208 (
errmsg(
"fixing incomplete split in index \"%s\", block %u",
1217 * Read the chain of split pages, following the rightlinks. Construct a
1218 * downlink tuple for each page.
1227 /* Form the new downlink tuples to insert to parent */
1233 splitinfo =
lappend(splitinfo, si);
1237 /* lock next page */
1245 /* Insert the downlinks */
1250 * Insert or replace a tuple in stack->buffer. If 'oldoffnum' is valid, the
1251 * tuple at 'oldoffnum' is replaced, otherwise the tuple is inserted as new.
1252 * 'stack' represents the path from the root to the page being updated.
1254 * The caller must hold an exclusive lock on stack->buffer. The lock is still
1255 * held on return, but the page might not contain the inserted tuple if the
1256 * page was split. The function returns true if the page was split, false
1268 * An extended workhorse version of gistinserttuple(). This version allows
1269 * inserting multiple tuples, or replacing a single tuple with multiple tuples.
1270 * This is used to recursively update the downlinks in the parent when a page
1273 * If leftchild and rightchild are valid, we're inserting/replacing the
1274 * downlink for rightchild, and leftchild is its left sibling. We clear the
1275 * F_FOLLOW_RIGHT flag and update NSN on leftchild, atomically with the
1276 * insertion of the downlink.
1278 * To avoid holding locks for longer than necessary, when recursing up the
1279 * tree to update the parents, the locking is a bit peculiar here. On entry,
1280 * the caller must hold an exclusive lock on stack->buffer, as well as
1281 * leftchild and rightchild if given. On return:
1283 * - Lock on stack->buffer is released, if 'unlockbuf' is true. The page is
1284 * always kept pinned, however.
1285 * - Lock on 'leftchild' is released, if 'unlockleftchild' is true. The page
1287 * - Lock and pin on 'rightchild' are always released.
1289 * Returns 'true' if the page had to be split. Note that if the page was
1290 * split, the inserted/updated tuples might've been inserted to a right
1291 * sibling of stack->buffer instead of stack->buffer itself.
1298 bool unlockbuf,
bool unlockleftchild)
1304 * Check for any rw conflicts (in serializable isolation level) just
1305 * before we intend to modify the page
1309 /* Insert the tuple(s) to the page, splitting the page if necessary */
1321 * Before recursing up in case the page was split, release locks on the
1322 * child pages. We don't need to keep them locked when updating the
1331 * If we had to split, insert/update the downlinks in the parent. If the
1332 * caller requested us to release the lock on stack->buffer, tell
1333 * gistfinishsplit() to do that as soon as it's safe to do so. If we
1334 * didn't have to split, release it ourselves.
1345 * Finish an incomplete split by inserting/updating the downlinks in parent
1346 * page. 'splitinfo' contains all the child pages involved in the split,
1347 * from left-to-right.
1349 * On entry, the caller must hold a lock on stack->buffer and all the child
1350 * pages in 'splitinfo'. If 'unlockbuf' is true, the lock on stack->buffer is
1351 * released on return. The child pages are always unlocked and unpinned.
1361 /* A split always contains at least two halves */
1365 * We need to insert downlinks for each new page, and update the downlink
1366 * for the original (leftmost) page in the split. Begin at the rightmost
1367 * page, inserting one downlink at a time until there's only two pages
1368 * left. Finally insert the downlink for the last new page and update the
1369 * downlink for the original page as one operation.
1374 * Insert downlinks for the siblings from right to left, until there are
1375 * only two siblings left.
1377 for (
int pos =
list_length(splitinfo) - 1; pos > 1; pos--)
1386 left->
buf, right->
buf,
false,
false))
1389 * If the parent page was split, the existing downlink might have
1394 /* gistinserttuples() released the lock on right->buf. */
1401 * Finally insert downlink for the remaining right page and update the
1402 * downlink for the original page to not contain the tuples that were
1403 * moved to the new pages.
1412 true,
/* Unlock parent */
1413 unlockbuf
/* Unlock stack->buffer if caller
1418 * The downlink might have moved when we updated it. Even if the page
1419 * wasn't split, because gistinserttuples() implements updating the old
1420 * tuple by removing and re-inserting it!
1427 * If we split the page because we had to adjust the downlink on an
1428 * internal page, while descending the tree for inserting a new tuple,
1429 * then this might no longer be the correct page for the new tuple. The
1430 * downlink to this page might not cover the new tuple anymore, it might
1431 * need to go to the newly-created right sibling instead. Tell the caller
1432 * to walk back up the stack, to re-check at the parent which page to
1435 * Normally, the LSN-NSN interlock during the tree descend would also
1436 * detect that a concurrent split happened (by ourselves), and cause us to
1437 * retry at the parent. But that mechanism doesn't work during index
1438 * build, because we don't do WAL-logging, and don't update LSNs, during
1445 * gistSplit -- split a page in the tree and fill struct
1446 * used for XLOG and real writes buffers. Function is recursive, ie
1447 * it will split page until keys will fit in every page.
1452 IndexTuple *itup,
/* contains compressed entry */
1462 /* this should never recurse very deeply, but better safe than sorry */
1465 /* there's no point in splitting an empty page */
1469 * If a single tuple doesn't fit on a page, no amount of splitting will
1474 (
errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1475 errmsg(
"index row size %zu exceeds maximum %zu for index \"%s\"",
1485 /* form left and right vector */
1495 /* finalize splitting (may need another split) */
1515 /* install on list's tail */
1516 while (resptr->
next)
1517 resptr = resptr->
next;
1534 * Create a GISTSTATE and fill it with information about the index
1544 /* safety check to protect fixed-size arrays in GISTSTATE */
1546 elog(
ERROR,
"numberOfAttributes %d > %d",
1549 /* Create the memory context that will hold the GISTSTATE */
1551 "GiST scan context",
1555 /* Create and fill in the GISTSTATE */
1559 giststate->
tempCxt = scanCxt;
/* caller must change this if needed */
1563 * The truncated tupdesc for non-leaf index tuples, which doesn't contain
1564 * the INCLUDE attributes.
1566 * It is used to form tuples during tuple adjustment and page split.
1567 * B-tree creates shortened tuple descriptor for every truncated tuple,
1568 * because it is doing this less often: it does not have to form truncated
1569 * tuples during page split. Also, B-tree is not adjusting tuples on
1570 * internal pages the way GiST does.
1584 /* opclasses are not required to provide a Compress method */
1592 /* opclasses are not required to provide a Decompress method */
1610 /* opclasses are not required to provide a Distance method */
1618 /* opclasses are not required to provide a Fetch method */
1627 * If the index column has a specified collation, we should honor that
1628 * while doing comparisons. However, we may have a collatable storage
1629 * type for a noncollatable indexed data type. If there's no index
1630 * collation then specify default collation in case the support
1631 * functions need collation. This is harmless if the support
1632 * functions don't care about collation, so we just do it
1633 * unconditionally. (We could alternatively call get_typcollation,
1634 * but that seems like expensive overkill --- there aren't going to be
1635 * any cases where a GiST storage type has a nondefault collation.)
1643 /* No opclass information for INCLUDE attributes */
1644 for (;
i <
index->rd_att->natts;
i++)
1666 /* It's sufficient to delete the scanCxt */
1671 * gistprunepage() -- try to remove LP_DEAD items from the given page.
1672 * Function assumes that buffer is exclusively locked.
1685 * Scan over all items to see which ones need to be deleted according to
1696 deletable[ndeletable++] = offnum;
1704 snapshotConflictHorizon =
1706 deletable, ndeletable);
1713 * Mark the page as not containing any LP_DEAD items. This is not
1714 * certainly true (there might be some that have recently been marked,
1715 * but weren't included in our target-item list), but it will almost
1716 * always be true and it doesn't seem worth an additional page scan to
1717 * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
1729 deletable, ndeletable,
1730 snapshotConflictHorizon,
1742 * Note: if we didn't find any LP_DEAD items, then the page's
1743 * F_HAS_GARBAGE hint bit is falsely set. We do not bother expending a
1744 * separate write to clear it, however. We will clear it when we split
#define InvalidBlockNumber
static Datum values[MAXATTR]
BlockNumber BufferGetBlockNumber(Buffer buffer)
Buffer ExtendBufferedRel(BufferManagerRelation bmr, ForkNumber forkNum, BufferAccessStrategy strategy, uint32 flags)
void ReleaseBuffer(Buffer buffer)
XLogRecPtr BufferGetLSNAtomic(Buffer buffer)
void UnlockReleaseBuffer(Buffer buffer)
void MarkBufferDirty(Buffer buffer)
void LockBuffer(Buffer buffer, int mode)
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
static Page BufferGetPage(Buffer buffer)
static bool BufferIsValid(Buffer bufnum)
void PageRestoreTempPage(Page tempPage, Page oldPage)
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
bool PageIndexTupleOverwrite(Page page, OffsetNumber offnum, Item newtup, Size newsize)
void PageIndexTupleDelete(Page page, OffsetNumber offnum)
Page PageGetTempPageCopySpecial(const PageData *page)
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static void PageSetLSN(Page page, XLogRecPtr lsn)
static XLogRecPtr PageGetLSN(const PageData *page)
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
#define OidIsValid(objectId)
int errdetail(const char *fmt,...)
int errhint(const char *fmt,...)
int errcode(int sqlerrcode)
int errmsg(const char *fmt,...)
#define ereport(elevel,...)
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
#define PG_RETURN_POINTER(x)
TransactionId index_compute_xid_horizon_for_tuples(Relation irel, Relation hrel, Buffer ibuf, OffsetNumber *itemnos, int nitems)
SplitPageLayout * gistSplit(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate)
GISTSTATE * initGISTstate(Relation index)
static GISTInsertStack * gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
static void gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
static void gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber *newblkno, Buffer leftchildbuf, List **splitinfo, bool markfollowright, Relation heapRel, bool is_build)
bool gistinsert(Relation r, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, IndexInfo *indexInfo)
void gistbuildempty(Relation index)
static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple *tuples, int ntup, OffsetNumber oldoffnum, Buffer leftchild, Buffer rightchild, bool unlockbuf, bool unlockleftchild)
MemoryContext createTempGistContext(void)
void freeGISTstate(GISTSTATE *giststate)
static bool gistinserttuple(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum)
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
static void gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
static IndexTuple gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate, GISTInsertStack *stack, bool is_build)
Datum gisthandler(PG_FUNCTION_ARGS)
#define GIST_DECOMPRESS_PROC
#define GIST_PICKSPLIT_PROC
#define GistMarkFollowRight(page)
#define GIST_CONSISTENT_PROC
#define GistClearFollowRight(page)
#define GIST_COMPRESS_PROC
#define GistClearPageHasGarbage(page)
#define GIST_PENALTY_PROC
#define GistPageIsLeaf(page)
#define GistFollowRight(page)
#define GIST_OPTIONS_PROC
#define GIST_DISTANCE_PROC
#define GistPageSetNSN(page, val)
#define GistPageIsDeleted(page)
#define GistPageGetOpaque(page)
#define GistPageHasGarbage(page)
#define GistPageGetNSN(page)
#define GIST_MAX_SPLIT_PAGES
#define GistTupleSetValid(itup)
#define GistTupleIsInvalid(itup)
IndexBuildResult * gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
bool gistgettuple(IndexScanDesc scan, ScanDirection dir)
int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
bool gistcanreturn(Relation index, int attno)
IndexScanDesc gistbeginscan(Relation r, int nkeys, int norderbys)
void gistendscan(IndexScanDesc scan)
void gistrescan(IndexScanDesc scan, ScanKey key, int nkeys, ScanKey orderbys, int norderbys)
void gistSplitByKey(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate, GistSplitVector *v, int attno)
bytea * gistoptions(Datum reloptions, bool validate)
Buffer gistNewBuffer(Relation r, Relation heaprel)
bool gistproperty(Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace)
void gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, const Datum *attdata, const bool *isnull, bool isleaf)
IndexTuple * gistextractpage(Page page, int *len)
bool gistfitpage(IndexTuple *itvec, int len)
IndexTuple gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
XLogRecPtr gistGetFakeLSN(Relation rel)
IndexTuple * gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
void GISTInitBuffer(Buffer b, uint32 f)
StrategyNumber gisttranslatecmptype(CompareType cmptype, Oid opfamily)
void gistcheckpage(Relation rel, Buffer buf)
IndexTupleData * gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
IndexBulkDeleteResult * gistvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
IndexBulkDeleteResult * gistbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
void gistadjustmembers(Oid opfamilyoid, Oid opclassoid, List *operators, List *functions)
bool gistvalidate(Oid opclassoid)
XLogRecPtr gistXLogSplit(bool page_is_leaf, SplitPageLayout *dist, BlockNumber origrlink, GistNSN orignsn, Buffer leftchildbuf, bool markfollowright)
XLogRecPtr gistXLogDelete(Buffer buffer, OffsetNumber *todelete, int ntodelete, TransactionId snapshotConflictHorizon, Relation heaprel)
XLogRecPtr gistXLogUpdate(Buffer buffer, OffsetNumber *todelete, int ntodelete, IndexTuple *itup, int ituplen, Buffer leftchildbuf)
Assert(PointerIsAligned(start, uint64))
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
IndexTuple CopyIndexTuple(IndexTuple source)
if(TABLE==NULL||TABLE_index==NULL)
#define ItemIdIsDead(itemId)
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
static void ItemPointerSetBlockNumber(ItemPointerData *pointer, BlockNumber blockNumber)
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
IndexTupleData * IndexTuple
static Size IndexTupleSize(const IndexTupleData *itup)
#define MaxIndexTuplesPerPage
List * lappend(List *list, void *datum)
List * list_delete_first(List *list)
List * lcons(void *datum, List *list)
void MemoryContextReset(MemoryContext context)
void * palloc0(Size size)
MemoryContext CurrentMemoryContext
void MemoryContextDelete(MemoryContext context)
#define AllocSetContextCreate
#define ALLOCSET_DEFAULT_SIZES
#define START_CRIT_SECTION()
#define END_CRIT_SECTION()
#define InvalidOffsetNumber
#define OffsetNumberIsValid(offsetNumber)
#define OffsetNumberNext(offsetNumber)
#define FirstOffsetNumber
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
static int list_length(const List *l)
static void * list_nth(const List *list, int n)
void PredicateLockPageSplit(Relation relation, BlockNumber oldblkno, BlockNumber newblkno)
void CheckForSerializableConflictIn(Relation relation, ItemPointer tid, BlockNumber blkno)
#define RelationGetRelationName(relation)
#define RelationNeedsWAL(relation)
#define IndexRelationGetNumberOfKeyAttributes(relation)
void gistcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
void check_stack_depth(void)
OffsetNumber downlinkoffnum
struct GISTInsertStack * parent
FmgrInfo fetchFn[INDEX_MAX_KEYS]
FmgrInfo penaltyFn[INDEX_MAX_KEYS]
Oid supportCollation[INDEX_MAX_KEYS]
FmgrInfo distanceFn[INDEX_MAX_KEYS]
FmgrInfo consistentFn[INDEX_MAX_KEYS]
FmgrInfo decompressFn[INDEX_MAX_KEYS]
FmgrInfo compressFn[INDEX_MAX_KEYS]
FmgrInfo equalFn[INDEX_MAX_KEYS]
FmgrInfo unionFn[INDEX_MAX_KEYS]
FmgrInfo picksplitFn[INDEX_MAX_KEYS]
GIST_SPLITVEC splitVector
Datum spl_lattr[INDEX_MAX_KEYS]
bool spl_lisnull[INDEX_MAX_KEYS]
Datum spl_rattr[INDEX_MAX_KEYS]
bool spl_risnull[INDEX_MAX_KEYS]
ambuildphasename_function ambuildphasename
ambuildempty_function ambuildempty
amvacuumcleanup_function amvacuumcleanup
amoptions_function amoptions
amestimateparallelscan_function amestimateparallelscan
amrestrpos_function amrestrpos
aminsert_function aminsert
amendscan_function amendscan
amtranslate_strategy_function amtranslatestrategy
amparallelrescan_function amparallelrescan
bool amconsistentordering
amtranslate_cmptype_function amtranslatecmptype
amcostestimate_function amcostestimate
amadjustmembers_function amadjustmembers
amgettuple_function amgettuple
amcanreturn_function amcanreturn
amgetbitmap_function amgetbitmap
amproperty_function amproperty
ambulkdelete_function ambulkdelete
amvalidate_function amvalidate
ammarkpos_function ammarkpos
bool amusemaintenanceworkmem
ambeginscan_function ambeginscan
amrescan_function amrescan
aminitparallelscan_function aminitparallelscan
uint8 amparallelvacuumoptions
aminsertcleanup_function aminsertcleanup
amgettreeheight_function amgettreeheight
bool amconsistentequality
struct SplitPageLayout * next
#define InvalidTransactionId
TupleDesc CreateTupleDescTruncatedCopy(TupleDesc tupdesc, int natts)
#define VACUUM_OPTION_PARALLEL_BULKDEL
#define VACUUM_OPTION_PARALLEL_COND_CLEANUP
#define XLogStandbyInfoActive()
#define XLogRecPtrIsInvalid(r)
XLogRecPtr log_newpage_buffer(Buffer buffer, bool page_std)
void XLogEnsureRecordSpace(int max_block_id, int ndatas)