1 /*-------------------------------------------------------------------------
4 * interface routines for the postgres GiST index access method.
11 *-------------------------------------------------------------------------
17 #include <access/genam.h>
18 #include <access/gist.h>
19 #include <access/gistscan.h>
20 #include <access/heapam.h>
21 #include <catalog/index.h>
22 #include <executor/executor.h>
23 #include <storage/bufmgr.h>
24 #include <storage/bufpage.h>
25 #include <storage/lmgr.h>
26 #include <utils/syscache.h>
27 #include <utils/tqual.h>
30 #include <regex/utils.h>
35 /* non-export function prototypes */
36 static InsertIndexResult gistdoinsert(Relation r, IndexTuple itup,
37 GISTSTATE *GISTstate);
38 static InsertIndexResult gistentryinsert(Relation r, GISTSTACK *stk,
40 GISTSTATE *giststate);
41 static void gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
42 IndexTuple rtup, GISTSTATE *giststate);
43 static void gistAdjustKeys(Relation r, GISTSTACK *stk, BlockNumber blk,
44 char *datum, int att_size, GISTSTATE *giststate);
45 static void gistintinsert(Relation r, GISTSTACK *stk, IndexTuple ltup,
46 IndexTuple rtup, GISTSTATE *giststate);
47 static InsertIndexResult gistSplit(Relation r, Buffer buffer,
48 GISTSTACK *stack, IndexTuple itup,
49 GISTSTATE *giststate);
50 static void gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt,
52 static void GISTInitBuffer(Buffer b, uint32 f);
53 static BlockNumber gistChooseSubtree(Relation r, IndexTuple itup, int level,
55 GISTSTACK **retstack, Buffer *leafbuf);
56 static OffsetNumber gistchoose(Relation r, Page p, IndexTuple it,
57 GISTSTATE *giststate);
58 static int gistnospace(Page p, IndexTuple it);
59 void gistdelete(Relation r, ItemPointer tid);
60 static IndexTuple gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t);
61 static void gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr,
62 Relation r, Page pg, OffsetNumber o, int b, bool l);
63 static char *int_range_out(INTRANGE *r);
66 ** routine to build an index. Basically calls insert over and over
69 gistbuild(Relation heap,
85 InsertIndexResult res;
92 #ifndef OMIT_PARTIAL_INDEX
93 ExprContext *econtext;
94 TupleTable tupleTable;
104 Buffer buffer = InvalidBuffer;
107 /* no locking is needed */
109 setheapoverride(true); /* so we can see the new pg_index tuple */
110 initGISTstate(&giststate, index);
111 setheapoverride(false);
113 pred = predInfo->pred;
114 oldPred = predInfo->oldPred;
117 * We expect to be called exactly once for any index relation. If
118 * that's not the case, big trouble's what we have.
121 if (oldPred == NULL && (nb = RelationGetNumberOfBlocks(index)) != 0)
122 elog(ERROR, "%s already contains data", index->rd_rel->relname.data);
124 /* initialize the root page (if this is a new index) */
127 buffer = ReadBuffer(index, P_NEW);
128 GISTInitBuffer(buffer, F_LEAF);
132 /* init the tuple descriptors and get set for a heap scan */
133 hd = RelationGetDescr(heap);
134 id = RelationGetDescr(index);
135 d = (Datum *) palloc(natts * sizeof(*d));
136 nulls = (bool *) palloc(natts * sizeof(*nulls));
139 * If this is a predicate (partial) index, we will need to evaluate
140 * the predicate using ExecQual, which requires the current tuple to
141 * be in a slot of a TupleTable. In addition, ExecQual must have an
142 * ExprContext referring to that slot. Here, we initialize dummy
143 * TupleTable and ExprContext objects for this purpose. --Nels, Feb
146 #ifndef OMIT_PARTIAL_INDEX
147 if (pred != NULL || oldPred != NULL)
149 tupleTable = ExecCreateTupleTable(1);
150 slot = ExecAllocTableSlot(tupleTable);
151 econtext = makeNode(ExprContext);
152 FillDummyExprContext(econtext, slot, hd, buffer);
155 /* shut the compiler up */
161 #endif /* OMIT_PARTIAL_INDEX */
162 /* int the tuples as we insert them */
165 scan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);
167 while (HeapTupleIsValid(htup = heap_getnext(scan, 0)))
172 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
173 * this tuple if it was already in the existing partial index
177 #ifndef OMIT_PARTIAL_INDEX
178 /* SetSlotContents(slot, htup); */
180 if (ExecQual((List *) oldPred, econtext) == true)
185 #endif /* OMIT_PARTIAL_INDEX */
189 * Skip this tuple if it doesn't satisfy the partial-index
194 #ifndef OMIT_PARTIAL_INDEX
195 /* SetSlotContents(slot, htup); */
197 if (ExecQual((List *) pred, econtext) == false)
199 #endif /* OMIT_PARTIAL_INDEX */
205 * For the current heap tuple, extract all the attributes we use
206 * in this index, and note which are null.
209 for (i = 1; i <= natts; i++)
215 * Offsets are from the start of the tuple, and are
216 * zero-based; indices are one-based. The next call returns i
217 * - 1. That's data hiding for you.
220 attoff = AttrNumberGetAttrOffset(i);
223 * d[attoff] = HeapTupleGetAttributeValue(htup, buffer,
225 d[attoff] = GetIndexValue(htup,
231 nulls[attoff] = (attnull ? 'n' : ' ');
234 /* immediately compress keys to normalize */
235 compvec = (bool *) palloc(sizeof(bool) * natts);
236 for (i = 0; i < natts; i++)
238 gistcentryinit(&giststate, &tmpcentry, (char *) d[i],
239 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
240 -1 /* size is currently bogus */ , TRUE);
241 if (d[i] != (Datum) tmpcentry.pred && !(giststate.keytypbyval))
245 d[i] = (Datum) tmpcentry.pred;
248 /* form an index tuple and point it at the heap tuple */
249 itup = index_formtuple(id, &d[0], nulls);
250 itup->t_tid = htup->t_self;
253 * Since we already have the index relation locked, we call
254 * gistdoinsert directly. Normal access method calls dispatch
255 * through gistinsert, which locks the relation for write. This
256 * is the right thing to do if you're inserting single tups, but
257 * not when you're initializing the whole index at once.
260 res = gistdoinsert(index, itup, &giststate);
261 for (i = 0; i < natts; i++)
262 if (compvec[i] == TRUE)
263 pfree((char *) d[i]);
269 /* okay, all heap tuples are indexed */
272 if (pred != NULL || oldPred != NULL)
274 #ifndef OMIT_PARTIAL_INDEX
275 ExecDestroyTupleTable(tupleTable, true);
277 #endif /* OMIT_PARTIAL_INDEX */
281 * Since we just inted the tuples in the heap, we update its stats in
282 * pg_relation to guarantee that the planner takes advantage of the
283 * index we just created. UpdateStats() does a
284 * CommandinterIncrement(), which flushes changed entries from the
285 * system relcache. The act of constructing an index changes these
286 * heap and index tuples in the system catalogs, so they need to be
287 * flushed. We close them to guarantee that they will be.
290 hrelid = RelationGetRelid(heap);
291 irelid = RelationGetRelid(index);
295 UpdateStats(hrelid, nh, true);
296 UpdateStats(irelid, ni, false);
302 UpdateIndexPredicate(irelid, oldPred, pred);
311 * gistinsert -- wrapper for GiST tuple insertion.
313 * This is the public interface routine for tuple insertion in GiSTs.
314 * It doesn't do any work; just locks the relation and passes the buck.
317 gistinsert(Relation r, Datum *datum, char *nulls, ItemPointer ht_ctid, Relation heapRel)
319 InsertIndexResult res;
326 initGISTstate(&giststate, r);
328 /* immediately compress keys to normalize */
329 compvec = (bool *) palloc(sizeof(bool) * r->rd_att->natts);
330 for (i = 0; i < r->rd_att->natts; i++)
332 gistcentryinit(&giststate, &tmpentry, (char *) datum[i],
333 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
334 -1 /* size is currently bogus */ , TRUE);
335 if (datum[i] != (Datum) tmpentry.pred && !(giststate.keytypbyval))
339 datum[i] = (Datum) tmpentry.pred;
341 itup = index_formtuple(RelationGetDescr(r), datum, nulls);
342 itup->t_tid = *ht_ctid;
345 * Notes in ExecUtils:ExecOpenIndices()
347 RelationSetLockForWrite(r);
350 res = gistdoinsert(r, itup, &giststate);
351 for (i = 0; i < r->rd_att->natts; i++)
352 if (compvec[i] == TRUE)
353 pfree((char *) datum[i]);
361 ** Take a compressed entry, and install it on a page. Since we now know
362 ** where the entry will live, we decompress it and recompress it using
363 ** that knowledge (some compression routines may want to fish around
364 ** on the page, for example, or do something special for leaf nodes.)
367 gistPageAddItem(GISTSTATE *giststate,
372 OffsetNumber offsetNumber,
378 IndexTuple itup = (IndexTuple) item;
381 * recompress the item given that we now know the exact page and
382 * offset for insertion
384 gistdentryinit(giststate, dentry,
385 (((char *) itup) + sizeof(IndexTupleData)),
386 (Relation) 0, (Page) 0, (OffsetNumber) InvalidOffsetNumber,
387 IndexTupleSize(itup) - sizeof(IndexTupleData), FALSE);
388 gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
389 offsetNumber, dentry->bytes, FALSE);
390 *newtup = gist_tuple_replacekey(r, *dentry, itup);
392 if (tmpcentry.pred != dentry->pred
393 && tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
394 pfree(tmpcentry.pred);
396 return (PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
397 offsetNumber, flags));
401 static InsertIndexResult
402 gistdoinsert(Relation r,
403 IndexTuple itup, /* itup contains compressed entry */
404 GISTSTATE *giststate)
407 InsertIndexResult res;
416 /* 3rd arg is ignored for now */
417 blk = gistChooseSubtree(r, itup, 0, giststate, &stack, &buffer);
418 page = (Page) BufferGetPage(buffer);
420 if (gistnospace(page, itup))
422 /* need to do a split */
423 res = gistSplit(r, buffer, stack, itup, giststate);
424 gistfreestack(stack);
425 WriteBuffer(buffer); /* don't forget to release buffer! */
429 if (PageIsEmpty(page))
430 off = FirstOffsetNumber;
432 off = OffsetNumberNext(PageGetMaxOffsetNumber(page));
434 /* add the item and write the buffer */
435 l = gistPageAddItem(giststate, r, page, (Item) itup, IndexTupleSize(itup),
436 off, LP_USED, &tmpdentry, &newtup);
439 /* now expand the page boundary in the parent to include the new child */
440 gistAdjustKeys(r, stack, blk, tmpdentry.pred, tmpdentry.bytes, giststate);
441 gistfreestack(stack);
446 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
447 pfree(tmpdentry.pred);
449 /* build and return an InsertIndexResult for this insertion */
450 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
451 ItemPointerSet(&(res->pointerData), blk, l);
458 gistChooseSubtree(Relation r, IndexTuple itup, /* itup has compressed
461 GISTSTATE *giststate,
462 GISTSTACK **retstack /* out */ ,
463 Buffer *leafbuf /* out */ )
469 GISTPageOpaque opaque;
473 buffer = InvalidBuffer;
474 stack = (GISTSTACK *) NULL;
478 /* let go of current buffer before getting next */
479 if (buffer != InvalidBuffer)
480 ReleaseBuffer(buffer);
482 /* get next buffer */
483 buffer = ReadBuffer(r, blk);
484 page = (Page) BufferGetPage(buffer);
486 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
487 if (!(opaque->flags & F_LEAF))
492 n = (GISTSTACK *) palloc(sizeof(GISTSTACK));
493 n->gs_parent = stack;
495 n->gs_child = gistchoose(r, page, itup, giststate);
498 iid = PageGetItemId(page, n->gs_child);
499 which = (IndexTuple) PageGetItem(page, iid);
500 blk = ItemPointerGetBlockNumber(&(which->t_tid));
502 } while (!(opaque->flags & F_LEAF));
512 gistAdjustKeys(Relation r,
515 char *datum, /* datum is uncompressed */
517 GISTSTATE *giststate)
531 if (stk == (GISTSTACK *) NULL)
534 b = ReadBuffer(r, stk->gs_blk);
535 p = BufferGetPage(b);
537 oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->gs_child));
538 tid = (IndexTuple) oldud;
539 size = IndexTupleSize((IndexTuple) oldud) - sizeof(IndexTupleData);
540 oldud += sizeof(IndexTupleData);
542 evec = (bytea *) palloc(2 * sizeof(GISTENTRY) + VARHDRSZ);
543 VARSIZE(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
545 /* insert decompressed oldud into entry vector */
546 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[0],
547 oldud, r, p, stk->gs_child,
549 ev0p = &((GISTENTRY *) VARDATA(evec))[0];
551 /* insert datum entry into entry vector */
552 gistentryinit(((GISTENTRY *) VARDATA(evec))[1], datum,
553 (Relation) NULL, (Page) NULL, (OffsetNumber) 0, att_size, FALSE);
554 ev1p = &((GISTENTRY *) VARDATA(evec))[1];
556 /* form union of decompressed entries */
557 datum = (*fmgr_faddr(&giststate->unionFn)) (evec, &datumsize);
559 /* did union leave decompressed version of oldud unchanged? */
560 (*fmgr_faddr(&giststate->equalFn)) (ev0p->pred, datum, &result);
563 TupleDesc td = RelationGetDescr(r);
565 /* compress datum for storage on page */
566 gistcentryinit(giststate, ¢ry, datum, ev0p->rel, ev0p->page,
567 ev0p->offset, datumsize, FALSE);
568 if (td->attrs[0]->attlen >= 0)
570 memmove(oldud, centry.pred, att_size);
571 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
574 else if (VARSIZE(centry.pred) == VARSIZE(oldud))
576 memmove(oldud, centry.pred, VARSIZE(centry.pred));
577 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
584 * * new datum is not the same size as the old. * We have to
585 * delete the old entry and insert the new * one. Note that
586 * this may cause a split here!
589 ItemPointerData oldtid;
592 InsertIndexResult res;
594 /* delete old tuple */
595 ItemPointerSet(&oldtid, stk->gs_blk, stk->gs_child);
596 gistdelete(r, (ItemPointer) &oldtid);
598 /* generate and insert new tuple */
600 isnull = (char *) palloc(r->rd_rel->relnatts);
601 MemSet(isnull, ' ', r->rd_rel->relnatts);
602 newtup = (IndexTuple) index_formtuple(tupDesc,
603 (Datum *) ¢ry.pred, isnull);
605 /* set pointer in new tuple to point to current child */
606 ItemPointerSet(&oldtid, blk, 1);
607 newtup->t_tid = oldtid;
609 /* inserting the new entry also adjust keys above */
610 res = gistentryinsert(r, stk, newtup, giststate);
612 /* in stack, set info to point to new tuple */
613 stk->gs_blk = ItemPointerGetBlockNumber(&(res->pointerData));
614 stk->gs_child = ItemPointerGetOffsetNumber(&(res->pointerData));
620 if (centry.pred != datum)
629 * gistSplit -- split a page in the tree.
632 static InsertIndexResult
633 gistSplit(Relation r,
636 IndexTuple itup, /* contains compressed entry */
637 GISTSTATE *giststate)
651 OffsetNumber leftoff,
655 BlockNumber bufblock;
656 GISTPageOpaque opaque;
658 InsertIndexResult res;
668 isnull = (char *) palloc(r->rd_rel->relnatts);
669 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
671 p = (Page) BufferGetPage(buffer);
672 opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
676 * The root of the tree is the first block in the relation. If we're
677 * about to split the root, we need to do some hocus-pocus to enforce
681 if (BufferGetBlockNumber(buffer) == GISTP_ROOT)
683 leftbuf = ReadBuffer(r, P_NEW);
684 GISTInitBuffer(leftbuf, opaque->flags);
685 lbknum = BufferGetBlockNumber(leftbuf);
686 left = (Page) BufferGetPage(leftbuf);
691 IncrBufferRefCount(buffer);
692 lbknum = BufferGetBlockNumber(buffer);
693 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
696 rightbuf = ReadBuffer(r, P_NEW);
697 GISTInitBuffer(rightbuf, opaque->flags);
698 rbknum = BufferGetBlockNumber(rightbuf);
699 right = (Page) BufferGetPage(rightbuf);
701 /* generate the item array */
702 maxoff = PageGetMaxOffsetNumber(p);
703 entryvec = (bytea *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(GISTENTRY));
704 decompvec = (bool *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(bool));
705 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
707 item_1 = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
708 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(entryvec))[i],
709 (((char *) item_1) + sizeof(IndexTupleData)),
711 IndexTupleSize(item_1) - sizeof(IndexTupleData), FALSE);
712 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[i].pred)
713 == (((char *) item_1) + sizeof(IndexTupleData)))
714 decompvec[i] = FALSE;
719 /* add the new datum as the last entry */
720 gistdentryinit(giststate, &(((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]),
721 (((char *) itup) + sizeof(IndexTupleData)),
722 (Relation) NULL, (Page) NULL,
723 (OffsetNumber) 0, tmpentry.bytes, FALSE);
724 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]).pred !=
725 (((char *) itup) + sizeof(IndexTupleData)))
726 decompvec[maxoff + 1] = TRUE;
728 decompvec[maxoff + 1] = FALSE;
730 VARSIZE(entryvec) = (maxoff + 2) * sizeof(GISTENTRY) + VARHDRSZ;
732 /* now let the user-defined picksplit function set up the split vector */
733 (*fmgr_faddr(&giststate->picksplitFn)) (entryvec, &v);
735 /* compress ldatum and rdatum */
736 gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation) NULL,
737 (Page) NULL, (OffsetNumber) 0,
738 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
739 if (v.spl_ldatum != tmpentry.pred)
741 v.spl_ldatum = tmpentry.pred;
743 gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation) NULL,
744 (Page) NULL, (OffsetNumber) 0,
745 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
746 if (v.spl_rdatum != tmpentry.pred)
748 v.spl_rdatum = tmpentry.pred;
750 /* clean up the entry vector: its preds need to be deleted, too */
751 for (i = FirstOffsetNumber; i <= maxoff + 1; i = OffsetNumberNext(i))
753 pfree(((GISTENTRY *) VARDATA(entryvec))[i].pred);
757 leftoff = rightoff = FirstOffsetNumber;
758 maxoff = PageGetMaxOffsetNumber(p);
759 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
761 itemid = PageGetItemId(p, i);
762 item = (IndexTuple) PageGetItem(p, itemid);
764 if (i == *(v.spl_left))
766 gistPageAddItem(giststate, r, left, (Item) item,
767 IndexTupleSize(item),
768 leftoff, LP_USED, &tmpdentry, &newtup);
769 leftoff = OffsetNumberNext(leftoff);
770 v.spl_left++; /* advance in left split vector */
772 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
773 pfree(tmpdentry.pred);
774 if ((IndexTuple) item != newtup)
779 gistPageAddItem(giststate, r, right, (Item) item,
780 IndexTupleSize(item),
781 rightoff, LP_USED, &tmpdentry, &newtup);
782 rightoff = OffsetNumberNext(rightoff);
783 v.spl_right++; /* advance in right split vector */
785 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
786 pfree(tmpdentry.pred);
792 /* build an InsertIndexResult for this insertion */
793 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
795 /* now insert the new index tuple */
796 if (*(v.spl_left) != FirstOffsetNumber)
798 gistPageAddItem(giststate, r, left, (Item) itup,
799 IndexTupleSize(itup),
800 leftoff, LP_USED, &tmpdentry, &newtup);
801 leftoff = OffsetNumberNext(leftoff);
802 ItemPointerSet(&(res->pointerData), lbknum, leftoff);
804 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
805 pfree(tmpdentry.pred);
811 gistPageAddItem(giststate, r, right, (Item) itup,
812 IndexTupleSize(itup),
813 rightoff, LP_USED, &tmpdentry, &newtup);
814 rightoff = OffsetNumberNext(rightoff);
815 ItemPointerSet(&(res->pointerData), rbknum, rightoff);
817 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
818 pfree(tmpdentry.pred);
823 if ((bufblock = BufferGetBlockNumber(buffer)) != GISTP_ROOT)
824 PageRestoreTempPage(left, p);
825 WriteBuffer(leftbuf);
826 WriteBuffer(rightbuf);
829 * Okay, the page is split. We have three things left to do:
831 * 1) Adjust any active scans on this index to cope with changes we
832 * introduced in its structure by splitting this page.
834 * 2) "Tighten" the bounding box of the pointer to the left page in the
835 * parent node in the tree, if any. Since we moved a bunch of stuff
836 * off the left page, we expect it to get smaller. This happens in
837 * the internal insertion routine.
839 * 3) Insert a pointer to the right page in the parent. This may cause
840 * the parent to split. If it does, we need to repeat steps one and
841 * two for each split node in the tree.
844 /* adjust active scans */
845 gistadjscans(r, GISTOP_SPLIT, bufblock, FirstOffsetNumber);
849 ltup = (IndexTuple) index_formtuple(tupDesc,
850 (Datum *) &(v.spl_ldatum), isnull);
851 rtup = (IndexTuple) index_formtuple(tupDesc,
852 (Datum *) &(v.spl_rdatum), isnull);
855 /* set pointers to new child pages in the internal index tuples */
856 ItemPointerSet(&(ltup->t_tid), lbknum, 1);
857 ItemPointerSet(&(rtup->t_tid), rbknum, 1);
859 gistintinsert(r, stack, ltup, rtup, giststate);
868 ** After a split, we need to overwrite the old entry's key in the parent,
869 ** and install install an entry for the new key into the parent.
872 gistintinsert(Relation r,
874 IndexTuple ltup, /* new version of entry for old page */
875 IndexTuple rtup, /* entry for new page */
876 GISTSTATE *giststate)
878 ItemPointerData ltid;
880 if (stk == (GISTSTACK *) NULL)
882 gistnewroot(giststate, r, ltup, rtup);
886 /* remove old left pointer, insert the 2 new entries */
887 ItemPointerSet(<id, stk->gs_blk, stk->gs_child);
888 gistdelete(r, (ItemPointer) <id);
889 gistentryinserttwo(r, stk, ltup, rtup, giststate);
894 ** Insert two entries onto one page, handling a split for either one!
897 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
898 IndexTuple rtup, GISTSTATE *giststate)
902 InsertIndexResult res;
906 b = ReadBuffer(r, stk->gs_blk);
907 p = BufferGetPage(b);
909 if (gistnospace(p, ltup))
911 res = gistSplit(r, b, stk->gs_parent, ltup, giststate);
912 WriteBuffer(b); /* don't forget to release buffer! -
915 gistdoinsert(r, rtup, giststate);
919 gistPageAddItem(giststate, r, p, (Item) ltup,
920 IndexTupleSize(ltup), InvalidOffsetNumber,
921 LP_USED, &tmpentry, &newtup);
923 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
924 tmpentry.bytes, giststate);
926 if (tmpentry.pred != (((char *) ltup) + sizeof(IndexTupleData)))
927 pfree(tmpentry.pred);
930 gistentryinsert(r, stk, rtup, giststate);
936 ** Insert an entry onto a page
938 static InsertIndexResult
939 gistentryinsert(Relation r, GISTSTACK *stk, IndexTuple tup,
940 GISTSTATE *giststate)
944 InsertIndexResult res;
949 b = ReadBuffer(r, stk->gs_blk);
950 p = BufferGetPage(b);
952 if (gistnospace(p, tup))
954 res = gistSplit(r, b, stk->gs_parent, tup, giststate);
955 WriteBuffer(b); /* don't forget to release buffer! -
961 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
962 off = gistPageAddItem(giststate, r, p, (Item) tup, IndexTupleSize(tup),
963 InvalidOffsetNumber, LP_USED, &tmpentry, &newtup);
965 ItemPointerSet(&(res->pointerData), stk->gs_blk, off);
966 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
967 tmpentry.bytes, giststate);
969 if (tmpentry.pred != (((char *) tup) + sizeof(IndexTupleData)))
970 pfree(tmpentry.pred);
979 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt, IndexTuple rt)
986 b = ReadBuffer(r, GISTP_ROOT);
987 GISTInitBuffer(b, 0);
988 p = BufferGetPage(b);
989 gistPageAddItem(giststate, r, p, (Item) lt, IndexTupleSize(lt),
991 LP_USED, &tmpentry, &newtup);
993 if (tmpentry.pred != (((char *) lt) + sizeof(IndexTupleData)))
994 pfree(tmpentry.pred);
997 gistPageAddItem(giststate, r, p, (Item) rt, IndexTupleSize(rt),
998 OffsetNumberNext(FirstOffsetNumber), LP_USED,
1001 if (tmpentry.pred != (((char *) rt) + sizeof(IndexTupleData)))
1002 pfree(tmpentry.pred);
1009 GISTInitBuffer(Buffer b, uint32 f)
1011 GISTPageOpaque opaque;
1015 pageSize = BufferGetPageSize(b);
1017 page = BufferGetPage(b);
1018 MemSet(page, 0, (int) pageSize);
1019 PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
1021 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1027 ** find entry with lowest penalty
1030 gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
1031 GISTSTATE *giststate)
1033 OffsetNumber maxoff;
1045 idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
1046 id = ((char *) it) + sizeof(IndexTupleData);
1047 maxoff = PageGetMaxOffsetNumber(p);
1051 gistdentryinit(giststate, &identry, id, (Relation) NULL, (Page) NULL,
1052 (OffsetNumber) 0, idsize, FALSE);
1054 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1056 datum = (char *) PageGetItem(p, PageGetItemId(p, i));
1057 size = IndexTupleSize(datum) - sizeof(IndexTupleData);
1058 datum += sizeof(IndexTupleData);
1059 gistdentryinit(giststate, &entry, datum, r, p, i, size, FALSE);
1060 (*fmgr_faddr(&giststate->penaltyFn)) (&entry, &identry, &usize);
1061 if (which_grow < 0 || usize < which_grow)
1065 if (which_grow == 0)
1068 if (entry.pred != datum)
1071 if (identry.pred != id)
1072 pfree(identry.pred);
1078 gistnospace(Page p, IndexTuple it)
1080 return PageGetFreeSpace(p) < IndexTupleSize(it);
1084 gistfreestack(GISTSTACK *s)
1088 while (s != (GISTSTACK *) NULL)
1098 ** remove an entry from a page
1101 gistdelete(Relation r, ItemPointer tid)
1104 OffsetNumber offnum;
1109 * Notes in ExecUtils:ExecOpenIndices()
1110 * Also note that only vacuum deletes index tuples now...
1112 RelationSetLockForWrite(r);
1115 blkno = ItemPointerGetBlockNumber(tid);
1116 offnum = ItemPointerGetOffsetNumber(tid);
1118 /* adjust any scans that will be affected by this deletion */
1119 gistadjscans(r, GISTOP_DEL, blkno, offnum);
1121 /* delete the index tuple */
1122 buf = ReadBuffer(r, blkno);
1123 page = BufferGetPage(buf);
1125 PageIndexTupleDelete(page, offnum);
1132 initGISTstate(GISTSTATE *giststate, Relation index)
1134 RegProcedure consistent_proc,
1138 RegProcedure penalty_proc,
1142 Form_pg_index itupform;
1144 consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
1145 union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
1146 compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
1147 decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
1148 penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
1149 picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
1150 equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1151 fmgr_info(consistent_proc, &giststate->consistentFn);
1152 fmgr_info(union_proc, &giststate->unionFn);
1153 fmgr_info(compress_proc, &giststate->compressFn);
1154 fmgr_info(decompress_proc, &giststate->decompressFn);
1155 fmgr_info(penalty_proc, &giststate->penaltyFn);
1156 fmgr_info(picksplit_proc, &giststate->picksplitFn);
1157 fmgr_info(equal_proc, &giststate->equalFn);
1159 /* see if key type is different from type of attribute being indexed */
1160 htup = SearchSysCacheTuple(INDEXRELID,
1161 ObjectIdGetDatum(RelationGetRelid(index)),
1163 itupform = (Form_pg_index) GETSTRUCT(htup);
1164 if (!HeapTupleIsValid(htup))
1165 elog(ERROR, "initGISTstate: index %d not found",
1166 RelationGetRelid(index));
1167 giststate->haskeytype = itupform->indhaskeytype;
1168 if (giststate->haskeytype)
1170 /* key type is different -- is it byval? */
1171 htup = SearchSysCacheTuple(ATTNUM,
1172 ObjectIdGetDatum(itupform->indexrelid),
1173 UInt16GetDatum(FirstOffsetNumber),
1175 if (!HeapTupleIsValid(htup))
1177 elog(ERROR, "initGISTstate: no attribute tuple %d %d",
1178 itupform->indexrelid, FirstOffsetNumber);
1181 giststate->keytypbyval = (((Form_pg_attribute) htup)->attbyval);
1184 giststate->keytypbyval = FALSE;
1190 ** Given an IndexTuple to be inserted on a page, this routine replaces
1191 ** the key with another key, which may involve generating a new IndexTuple
1192 ** if the sizes don't match
1195 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1197 char *datum = (((char *) t) + sizeof(IndexTupleData));
1199 /* if new entry fits in index tuple, copy it in */
1200 if (entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData))
1202 memcpy(datum, entry.pred, entry.bytes);
1203 /* clear out old size */
1204 t->t_info &= 0xe000;
1205 /* or in new size */
1206 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1212 /* generate a new index tuple for the compressed entry */
1213 TupleDesc tupDesc = r->rd_att;
1218 isnull = (char *) palloc(r->rd_rel->relnatts);
1219 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
1220 isnull[blank] = ' ';
1221 newtup = (IndexTuple) index_formtuple(tupDesc,
1222 (Datum *) &(entry.pred),
1224 newtup->t_tid = t->t_tid;
1232 ** initialize a GiST entry with a decompressed version of pred
1235 gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1236 Page pg, OffsetNumber o, int b, bool l)
1240 gistentryinit(*e, pr, r, pg, o, b, l);
1241 if (giststate->haskeytype)
1243 dep = (GISTENTRY *) ((*fmgr_faddr(&giststate->decompressFn)) (e));
1244 gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1253 ** initialize a GiST entry with a compressed version of pred
1256 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1257 Page pg, OffsetNumber o, int b, bool l)
1261 gistentryinit(*e, pr, r, pg, o, b, l);
1262 if (giststate->haskeytype)
1264 cep = (GISTENTRY *) ((*fmgr_faddr(&giststate->compressFn)) (e));
1265 gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
1277 ** sloppy debugging support routine, requires recompilation with appropriate
1278 ** "out" method for the index keys. Could be fixed to find that info
1279 ** in the catalogs...
1282 _gistdump(Relation r)
1286 OffsetNumber offnum,
1289 BlockNumber nblocks;
1292 BlockNumber itblkno;
1293 OffsetNumber itoffno;
1297 nblocks = RelationGetNumberOfBlocks(r);
1298 for (blkno = 0; blkno < nblocks; blkno++)
1300 buf = ReadBuffer(r, blkno);
1301 page = BufferGetPage(buf);
1302 po = (GISTPageOpaque) PageGetSpecialPointer(page);
1303 maxoff = PageGetMaxOffsetNumber(page);
1304 printf("Page %d maxoff %d <%s>\n", blkno, maxoff,
1305 (po->flags & F_LEAF ? "LEAF" : "INTERNAL"));
1307 if (PageIsEmpty(page))
1313 for (offnum = FirstOffsetNumber;
1315 offnum = OffsetNumberNext(offnum))
1317 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
1318 itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1319 itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid));
1320 datum = ((char *) itup);
1321 datum += sizeof(IndexTupleData);
1322 /* get out function for type of key, and out it! */
1323 itkey = (char *) int_range_out((INTRANGE *) datum);
1324 /* itkey = " unable to print"; */
1325 printf("\t[%d] size %d heap <%d,%d> key:%s\n",
1326 offnum, IndexTupleSize(itup), itblkno, itoffno, itkey);
1335 int_range_out(INTRANGE *r)
1341 result = (char *) palloc(80);
1342 snprintf(result, 80, "[%d,%d): %d", r->lower, r->upper, r->flag);
1347 #endif /* defined GISTDEBUG */