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>
29 # include <regex/utils.h>
34 /* non-export function prototypes */
35 static InsertIndexResult gistdoinsert(Relation r, IndexTuple itup,
36 GISTSTATE *GISTstate);
37 static InsertIndexResult gistentryinsert(Relation r, GISTSTACK *stk,
39 GISTSTATE *giststate);
40 static void gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
41 IndexTuple rtup, GISTSTATE *giststate);
42 static void gistAdjustKeys(Relation r, GISTSTACK *stk, BlockNumber blk,
43 char *datum, int att_size, GISTSTATE *giststate);
44 static void gistintinsert(Relation r, GISTSTACK *stk, IndexTuple ltup,
45 IndexTuple rtup, GISTSTATE *giststate);
46 static InsertIndexResult gistSplit(Relation r, Buffer buffer,
47 GISTSTACK *stack, IndexTuple itup,
48 GISTSTATE *giststate);
49 static void gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt,
51 static void GISTInitBuffer(Buffer b, uint32 f);
52 static BlockNumber gistChooseSubtree(Relation r, IndexTuple itup, int level,
54 GISTSTACK **retstack, Buffer *leafbuf);
55 static OffsetNumber gistchoose(Relation r, Page p, IndexTuple it,
56 GISTSTATE *giststate);
57 static int gistnospace(Page p, IndexTuple it);
58 void gistdelete(Relation r, ItemPointer tid);
59 static IndexTuple gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t);
63 ** routine to build an index. Basically calls insert over and over
66 gistbuild(Relation heap,
82 InsertIndexResult res;
86 #ifndef OMIT_PARTIAL_INDEX
87 ExprContext *econtext;
88 TupleTable tupleTable;
97 /* GiSTs only know how to do stupid locking now */
98 RelationSetLockForWrite(index);
100 setheapoverride(TRUE); /* so we can see the new pg_index tuple */
101 initGISTstate(&giststate, index);
102 setheapoverride(FALSE);
104 pred = predInfo->pred;
105 oldPred = predInfo->oldPred;
108 * We expect to be called exactly once for any index relation.
109 * If that's not the case, big trouble's what we have.
112 if (oldPred == NULL && (nb = RelationGetNumberOfBlocks(index)) != 0)
113 elog(WARN, "%.16s already contains data", &(index->rd_rel->relname.data[0]));
115 /* initialize the root page (if this is a new index) */
116 if (oldPred == NULL) {
117 buffer = ReadBuffer(index, P_NEW);
118 GISTInitBuffer(buffer, F_LEAF);
122 /* init the tuple descriptors and get set for a heap scan */
123 hd = RelationGetTupleDescriptor(heap);
124 id = RelationGetTupleDescriptor(index);
125 d = (Datum *)palloc(natts * sizeof (*d));
126 nulls = (bool *)palloc(natts * sizeof (*nulls));
129 * If this is a predicate (partial) index, we will need to evaluate the
130 * predicate using ExecQual, which requires the current tuple to be in a
131 * slot of a TupleTable. In addition, ExecQual must have an ExprContext
132 * referring to that slot. Here, we initialize dummy TupleTable and
133 * ExprContext objects for this purpose. --Nels, Feb '92
135 #ifndef OMIT_PARTIAL_INDEX
136 if (pred != NULL || oldPred != NULL) {
137 tupleTable = ExecCreateTupleTable(1);
138 slot = ExecAllocTableSlot(tupleTable);
139 econtext = makeNode(ExprContext);
140 FillDummyExprContext(econtext, slot, hd, buffer);
142 else /* shut the compiler up */
148 #endif /* OMIT_PARTIAL_INDEX */
149 scan = heap_beginscan(heap, 0, NowTimeQual, 0, (ScanKey) NULL);
150 htup = heap_getnext(scan, 0, &buffer);
152 /* int the tuples as we insert them */
155 for (; HeapTupleIsValid(htup); htup = heap_getnext(scan, 0, &buffer)) {
160 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
161 * this tuple if it was already in the existing partial index
163 if (oldPred != NULL) {
164 #ifndef OMIT_PARTIAL_INDEX
165 /*SetSlotContents(slot, htup); */
167 if (ExecQual((List*)oldPred, econtext) == true) {
171 #endif /* OMIT_PARTIAL_INDEX */
174 /* Skip this tuple if it doesn't satisfy the partial-index predicate */
176 #ifndef OMIT_PARTIAL_INDEX
177 /*SetSlotContents(slot, htup); */
179 if (ExecQual((List*)pred, econtext) == false)
181 #endif /* OMIT_PARTIAL_INDEX */
187 * For the current heap tuple, extract all the attributes
188 * we use in this index, and note which are null.
191 for (i = 1; i <= natts; i++) {
196 * Offsets are from the start of the tuple, and are
197 * zero-based; indices are one-based. The next call
198 * returns i - 1. That's data hiding for you.
201 attoff = AttrNumberGetAttrOffset(i);
203 d[attoff] = HeapTupleGetAttributeValue(htup, buffer,
205 d[attoff] = GetIndexValue(htup,
212 nulls[attoff] = (attnull ? 'n' : ' ');
215 /* immediately compress keys to normalize */
216 compvec = (bool *)palloc(sizeof(bool) * natts);
217 for (i = 0; i < natts; i++) {
218 gistcentryinit(&giststate, &tmpcentry, (char *)d[i],
219 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
220 -1 /* size is currently bogus */, TRUE);
221 if (d[i] != (Datum)tmpcentry.pred && !(giststate.keytypbyval))
223 else compvec[i] = FALSE;
224 d[i] = (Datum)tmpcentry.pred;
227 /* form an index tuple and point it at the heap tuple */
228 itup = index_formtuple(id, &d[0], nulls);
229 itup->t_tid = htup->t_ctid;
232 * Since we already have the index relation locked, we
233 * call gistdoinsert directly. Normal access method calls
234 * dispatch through gistinsert, which locks the relation
235 * for write. This is the right thing to do if you're
236 * inserting single tups, but not when you're initializing
237 * the whole index at once.
240 res = gistdoinsert(index, itup, &giststate);
241 for (i = 0; i < natts; i++)
242 if (compvec[i] == TRUE) pfree((char *)d[i]);
248 /* okay, all heap tuples are indexed */
250 RelationUnsetLockForWrite(index);
252 if (pred != NULL || oldPred != NULL) {
253 #ifndef OMIT_PARTIAL_INDEX
254 ExecDestroyTupleTable(tupleTable, true);
256 #endif /* OMIT_PARTIAL_INDEX */
260 * Since we just inted the tuples in the heap, we update its
261 * stats in pg_relation to guarantee that the planner takes
262 * advantage of the index we just created. UpdateStats() does a
263 * CommandinterIncrement(), which flushes changed entries from
264 * the system relcache. The act of constructing an index changes
265 * these heap and index tuples in the system catalogs, so they
266 * need to be flushed. We close them to guarantee that they
270 hrelid = heap->rd_id;
271 irelid = index->rd_id;
275 UpdateStats(hrelid, nh, true);
276 UpdateStats(irelid, ni, false);
278 if (oldPred != NULL) {
279 if (ni == nh) pred = NULL;
280 UpdateIndexPredicate(irelid, oldPred, pred);
289 * gistinsert -- wrapper for GiST tuple insertion.
291 * This is the public interface routine for tuple insertion in GiSTs.
292 * It doesn't do any work; just locks the relation and passes the buck.
295 gistinsert(Relation r, Datum *datum, char *nulls, ItemPointer ht_ctid, Relation heapRel)
297 InsertIndexResult res;
304 initGISTstate(&giststate, r);
306 /* immediately compress keys to normalize */
307 compvec = (bool *)palloc(sizeof(bool) * r->rd_att->natts);
308 for (i = 0; i < r->rd_att->natts; i++) {
309 gistcentryinit(&giststate, &tmpentry, (char *)datum[i],
310 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
311 -1 /* size is currently bogus */, TRUE);
312 if (datum[i] != (Datum)tmpentry.pred && !(giststate.keytypbyval))
314 else compvec[i] = FALSE;
315 datum[i] = (Datum)tmpentry.pred;
317 itup = index_formtuple(RelationGetTupleDescriptor(r), datum, nulls);
318 itup->t_tid = *ht_ctid;
320 RelationSetLockForWrite(r);
321 res = gistdoinsert(r, itup, &giststate);
322 for (i = 0; i < r->rd_att->natts; i++)
323 if (compvec[i] == TRUE) pfree((char *)datum[i]);
327 /* XXX two-phase locking -- don't unlock the relation until EOT */
332 ** Take a compressed entry, and install it on a page. Since we now know
333 ** where the entry will live, we decompress it and recompress it using
334 ** that knowledge (some compression routines may want to fish around
335 ** on the page, for example, or do something special for leaf nodes.)
338 gistPageAddItem(GISTSTATE *giststate,
343 OffsetNumber offsetNumber,
349 IndexTuple itup = (IndexTuple)item;
351 /* recompress the item given that we now know the exact page and
352 offset for insertion */
353 gistdentryinit(giststate, dentry,
354 (((char *) itup) + sizeof(IndexTupleData)),
355 (Relation)0, (Page)0, (OffsetNumber)InvalidOffsetNumber,
356 IndexTupleSize(itup) - sizeof(IndexTupleData), FALSE);
357 gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
358 offsetNumber, dentry->bytes, FALSE);
359 *newtup = gist_tuple_replacekey(r, *dentry, itup);
361 if (tmpcentry.pred != dentry->pred
362 && tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
363 pfree(tmpcentry.pred);
365 return(PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
366 offsetNumber, flags));
370 static InsertIndexResult
371 gistdoinsert(Relation r,
372 IndexTuple itup, /* itup contains compressed entry */
373 GISTSTATE *giststate)
376 InsertIndexResult res;
385 /* 3rd arg is ignored for now */
386 blk = gistChooseSubtree(r, itup, 0, giststate, &stack, &buffer);
387 page = (Page) BufferGetPage(buffer);
389 if (gistnospace(page, itup)) {
390 /* need to do a split */
391 res = gistSplit(r, buffer, stack, itup, giststate);
392 gistfreestack(stack);
393 WriteBuffer(buffer); /* don't forget to release buffer! */
397 if (PageIsEmpty(page))
398 off = FirstOffsetNumber;
400 off = OffsetNumberNext(PageGetMaxOffsetNumber(page));
402 /* add the item and write the buffer */
403 l = gistPageAddItem(giststate, r, page, (Item) itup, IndexTupleSize(itup),
404 off, LP_USED, &tmpdentry, &newtup);
407 /* now expand the page boundary in the parent to include the new child */
408 gistAdjustKeys(r, stack, blk, tmpdentry.pred, tmpdentry.bytes, giststate);
409 gistfreestack(stack);
414 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
415 pfree(tmpdentry.pred);
417 /* build and return an InsertIndexResult for this insertion */
418 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
419 ItemPointerSet(&(res->pointerData), blk, l);
426 gistChooseSubtree(Relation r, IndexTuple itup, /* itup has compressed entry */
428 GISTSTATE *giststate,
429 GISTSTACK **retstack /*out*/,
430 Buffer *leafbuf /*out*/)
436 GISTPageOpaque opaque;
440 buffer = InvalidBuffer;
441 stack = (GISTSTACK *) NULL;
444 /* let go of current buffer before getting next */
445 if (buffer != InvalidBuffer)
446 ReleaseBuffer(buffer);
448 /* get next buffer */
449 buffer = ReadBuffer(r, blk);
450 page = (Page) BufferGetPage(buffer);
452 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
453 if (!(opaque->flags & F_LEAF)) {
457 n = (GISTSTACK *) palloc(sizeof(GISTSTACK));
458 n->gs_parent = stack;
460 n->gs_child = gistchoose(r, page, itup, giststate);
463 iid = PageGetItemId(page, n->gs_child);
464 which = (IndexTuple) PageGetItem(page, iid);
465 blk = ItemPointerGetBlockNumber(&(which->t_tid));
467 } while (!(opaque->flags & F_LEAF));
477 gistAdjustKeys(Relation r,
480 char *datum, /* datum is uncompressed */
482 GISTSTATE *giststate)
489 GISTENTRY centry, *ev0p, *ev1p;
493 if (stk == (GISTSTACK *) NULL)
496 b = ReadBuffer(r, stk->gs_blk);
497 p = BufferGetPage(b);
499 oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->gs_child));
500 tid = (IndexTuple) oldud;
501 size = IndexTupleSize((IndexTuple)oldud) - sizeof(IndexTupleData);
502 oldud += sizeof(IndexTupleData);
504 evec = (bytea *) palloc(2*sizeof(GISTENTRY) + VARHDRSZ);
505 VARSIZE(evec) = 2*sizeof(GISTENTRY) + VARHDRSZ;
507 /* insert decompressed oldud into entry vector */
508 gistdentryinit(giststate, &((GISTENTRY *)VARDATA(evec))[0],
509 oldud, r, p, stk->gs_child,
511 ev0p = &((GISTENTRY *)VARDATA(evec))[0];
513 /* insert datum entry into entry vector */
514 gistentryinit(((GISTENTRY *)VARDATA(evec))[1], datum,
515 (Relation)NULL,(Page)NULL,(OffsetNumber)0, att_size, FALSE);
516 ev1p = &((GISTENTRY *)VARDATA(evec))[1];
518 /* form union of decompressed entries */
519 datum = (char *) (giststate->unionFn)(evec, &datumsize);
521 /* did union leave decompressed version of oldud unchanged? */
522 (giststate->equalFn)(ev0p->pred, datum, &result);
524 TupleDesc td = RelationGetTupleDescriptor(r);
526 /* compress datum for storage on page */
527 gistcentryinit(giststate, ¢ry, datum, ev0p->rel, ev0p->page,
528 ev0p->offset, datumsize, FALSE);
529 if (td->attrs[0]->attlen >= 0) {
530 memmove(oldud, centry.pred, att_size);
531 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
534 else if (VARSIZE(centry.pred) == VARSIZE(oldud)) {
535 memmove(oldud, centry.pred, VARSIZE(centry.pred));
536 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
541 ** new datum is not the same size as the old.
542 ** We have to delete the old entry and insert the new
543 ** one. Note that this may cause a split here!
546 ItemPointerData oldtid;
549 InsertIndexResult res;
551 /* delete old tuple */
552 ItemPointerSet(&oldtid, stk->gs_blk, stk->gs_child);
553 gistdelete(r, (ItemPointer)&oldtid);
555 /* generate and insert new tuple */
557 isnull = (char *) palloc(r->rd_rel->relnatts);
558 memset(isnull, ' ', r->rd_rel->relnatts);
559 newtup = (IndexTuple) index_formtuple(tupDesc,
560 (Datum *) ¢ry.pred, isnull);
562 /* set pointer in new tuple to point to current child */
563 ItemPointerSet(&oldtid, blk, 1);
564 newtup->t_tid = oldtid;
566 /* inserting the new entry also adjust keys above */
567 res = gistentryinsert(r, stk, newtup, giststate);
569 /* in stack, set info to point to new tuple */
570 stk->gs_blk = ItemPointerGetBlockNumber(&(res->pointerData));
571 stk->gs_child = ItemPointerGetOffsetNumber(&(res->pointerData));
577 if (centry.pred != datum)
587 * gistSplit -- split a page in the tree.
590 static InsertIndexResult
591 gistSplit(Relation r,
594 IndexTuple itup, /* contains compressed entry */
595 GISTSTATE *giststate)
598 Buffer leftbuf, rightbuf;
602 IndexTuple ltup, rtup, newtup;
605 OffsetNumber leftoff, rightoff;
606 BlockNumber lbknum, rbknum;
607 BlockNumber bufblock;
608 GISTPageOpaque opaque;
610 InsertIndexResult res;
617 GISTENTRY tmpdentry, tmpentry;
619 isnull = (char *) palloc(r->rd_rel->relnatts);
620 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
622 p = (Page) BufferGetPage(buffer);
623 opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
627 * The root of the tree is the first block in the relation. If
628 * we're about to split the root, we need to do some hocus-pocus
629 * to enforce this guarantee.
632 if (BufferGetBlockNumber(buffer) == GISTP_ROOT) {
633 leftbuf = ReadBuffer(r, P_NEW);
634 GISTInitBuffer(leftbuf, opaque->flags);
635 lbknum = BufferGetBlockNumber(leftbuf);
636 left = (Page) BufferGetPage(leftbuf);
639 IncrBufferRefCount(buffer);
640 lbknum = BufferGetBlockNumber(buffer);
641 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
644 rightbuf = ReadBuffer(r, P_NEW);
645 GISTInitBuffer(rightbuf, opaque->flags);
646 rbknum = BufferGetBlockNumber(rightbuf);
647 right = (Page) BufferGetPage(rightbuf);
649 /* generate the item array */
650 maxoff = PageGetMaxOffsetNumber(p);
651 entryvec = (bytea *)palloc(VARHDRSZ + (maxoff + 2) * sizeof(GISTENTRY));
652 decompvec = (bool *)palloc(VARHDRSZ + (maxoff + 2) * sizeof(bool));
653 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) {
654 item_1 = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
655 gistdentryinit(giststate, &((GISTENTRY *)VARDATA(entryvec))[i],
656 (((char *) item_1) + sizeof(IndexTupleData)),
658 IndexTupleSize(item_1) - sizeof(IndexTupleData), FALSE);
659 if ((char *)(((GISTENTRY *)VARDATA(entryvec))[i].pred)
660 == (((char *) item_1) + sizeof(IndexTupleData)))
661 decompvec[i] = FALSE;
662 else decompvec[i] = TRUE;
665 /* add the new datum as the last entry */
666 gistdentryinit(giststate, &(((GISTENTRY *)VARDATA(entryvec))[maxoff+1]),
667 (((char *) itup) + sizeof(IndexTupleData)),
668 (Relation)NULL, (Page)NULL,
669 (OffsetNumber)0, tmpentry.bytes, FALSE);
670 if ((char *)(((GISTENTRY *)VARDATA(entryvec))[maxoff+1]).pred !=
671 (((char *) itup) + sizeof(IndexTupleData)))
672 decompvec[maxoff+1] = TRUE;
673 else decompvec[maxoff+1] = FALSE;
675 VARSIZE(entryvec) = (maxoff + 2) * sizeof(GISTENTRY) + VARHDRSZ;
677 /* now let the user-defined picksplit function set up the split vector */
678 (giststate->picksplitFn)(entryvec, &v);
680 /* compress ldatum and rdatum */
681 gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation)NULL,
682 (Page)NULL, (OffsetNumber)0,
683 ((GISTENTRY *)VARDATA(entryvec))[i].bytes, FALSE);
684 if (v.spl_ldatum != tmpentry.pred)
686 v.spl_ldatum = tmpentry.pred;
688 gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation)NULL,
689 (Page)NULL, (OffsetNumber)0,
690 ((GISTENTRY *)VARDATA(entryvec))[i].bytes, FALSE);
691 if (v.spl_rdatum != tmpentry.pred)
693 v.spl_rdatum = tmpentry.pred;
695 /* clean up the entry vector: its preds need to be deleted, too */
696 for (i = FirstOffsetNumber; i <= maxoff+1; i = OffsetNumberNext(i))
698 pfree(((GISTENTRY *)VARDATA(entryvec))[i].pred);
702 leftoff = rightoff = FirstOffsetNumber;
703 maxoff = PageGetMaxOffsetNumber(p);
704 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) {
705 itemid = PageGetItemId(p, i);
706 item = (IndexTuple) PageGetItem(p, itemid);
708 if (i == *(v.spl_left)) {
709 gistPageAddItem(giststate, r, left, (Item) item,
710 IndexTupleSize(item),
711 leftoff, LP_USED, &tmpdentry, &newtup);
712 leftoff = OffsetNumberNext(leftoff);
713 v.spl_left++; /* advance in left split vector */
715 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
716 pfree(tmpdentry.pred);
717 if ((IndexTuple)item != newtup)
721 gistPageAddItem(giststate, r, right, (Item) item,
722 IndexTupleSize(item),
723 rightoff, LP_USED, &tmpdentry, &newtup);
724 rightoff = OffsetNumberNext(rightoff);
725 v.spl_right++; /* advance in right split vector */
727 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
728 pfree(tmpdentry.pred);
734 /* build an InsertIndexResult for this insertion */
735 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
737 /* now insert the new index tuple */
738 if (*(v.spl_left) != FirstOffsetNumber) {
739 gistPageAddItem(giststate, r, left, (Item) itup,
740 IndexTupleSize(itup),
741 leftoff, LP_USED, &tmpdentry, &newtup);
742 leftoff = OffsetNumberNext(leftoff);
743 ItemPointerSet(&(res->pointerData), lbknum, leftoff);
745 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
746 pfree(tmpdentry.pred);
750 gistPageAddItem(giststate, r, right, (Item) itup,
751 IndexTupleSize(itup),
752 rightoff, LP_USED, &tmpdentry, &newtup);
753 rightoff = OffsetNumberNext(rightoff);
754 ItemPointerSet(&(res->pointerData), rbknum, rightoff);
756 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
757 pfree(tmpdentry.pred);
762 if ((bufblock = BufferGetBlockNumber(buffer)) != GISTP_ROOT) {
763 PageRestoreTempPage(left, p);
765 WriteBuffer(leftbuf);
766 WriteBuffer(rightbuf);
769 * Okay, the page is split. We have three things left to do:
771 * 1) Adjust any active scans on this index to cope with changes
772 * we introduced in its structure by splitting this page.
774 * 2) "Tighten" the bounding box of the pointer to the left
775 * page in the parent node in the tree, if any. Since we
776 * moved a bunch of stuff off the left page, we expect it
777 * to get smaller. This happens in the internal insertion
780 * 3) Insert a pointer to the right page in the parent. This
781 * may cause the parent to split. If it does, we need to
782 * repeat steps one and two for each split node in the tree.
785 /* adjust active scans */
786 gistadjscans(r, GISTOP_SPLIT, bufblock, FirstOffsetNumber);
790 ltup = (IndexTuple) index_formtuple(tupDesc,
791 (Datum *) &(v.spl_ldatum), isnull);
792 rtup = (IndexTuple) index_formtuple(tupDesc,
793 (Datum *) &(v.spl_rdatum), isnull);
796 /* set pointers to new child pages in the internal index tuples */
797 ItemPointerSet(&(ltup->t_tid), lbknum, 1);
798 ItemPointerSet(&(rtup->t_tid), rbknum, 1);
800 gistintinsert(r, stack, ltup, rtup, giststate);
809 ** After a split, we need to overwrite the old entry's key in the parent,
810 ** and install install an entry for the new key into the parent.
813 gistintinsert(Relation r,
815 IndexTuple ltup, /* new version of entry for old page */
816 IndexTuple rtup, /* entry for new page */
817 GISTSTATE *giststate)
819 ItemPointerData ltid;
821 if (stk == (GISTSTACK *) NULL) {
822 gistnewroot(giststate, r, ltup, rtup);
826 /* remove old left pointer, insert the 2 new entries */
827 ItemPointerSet(<id, stk->gs_blk, stk->gs_child);
828 gistdelete(r, (ItemPointer)<id);
829 gistentryinserttwo(r, stk, ltup, rtup, giststate);
834 ** Insert two entries onto one page, handling a split for either one!
837 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
838 IndexTuple rtup, GISTSTATE *giststate)
842 InsertIndexResult res;
846 b = ReadBuffer(r, stk->gs_blk);
847 p = BufferGetPage(b);
849 if (gistnospace(p, ltup)) {
850 res = gistSplit(r, b, stk->gs_parent, ltup, giststate);
851 WriteBuffer(b); /* don't forget to release buffer! - 01/31/94 */
853 gistdoinsert(r, rtup, giststate);
855 gistPageAddItem(giststate, r, p, (Item)ltup,
856 IndexTupleSize(ltup), InvalidOffsetNumber,
857 LP_USED, &tmpentry, &newtup);
859 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
860 tmpentry.bytes, giststate);
862 if (tmpentry.pred != (((char *) ltup) + sizeof(IndexTupleData)))
863 pfree(tmpentry.pred);
866 gistentryinsert(r, stk, rtup, giststate);
872 ** Insert an entry onto a page
874 static InsertIndexResult
875 gistentryinsert(Relation r, GISTSTACK *stk, IndexTuple tup,
876 GISTSTATE *giststate)
880 InsertIndexResult res;
885 b = ReadBuffer(r, stk->gs_blk);
886 p = BufferGetPage(b);
888 if (gistnospace(p, tup)) {
889 res = gistSplit(r, b, stk->gs_parent, tup, giststate);
890 WriteBuffer(b); /* don't forget to release buffer! - 01/31/94 */
894 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
895 off = gistPageAddItem(giststate, r, p, (Item) tup, IndexTupleSize(tup),
896 InvalidOffsetNumber, LP_USED, &tmpentry, &newtup);
898 ItemPointerSet(&(res->pointerData), stk->gs_blk, off);
899 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
900 tmpentry.bytes, giststate);
902 if (tmpentry.pred != (((char *) tup) + sizeof(IndexTupleData)))
903 pfree(tmpentry.pred);
912 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt, IndexTuple rt)
919 b = ReadBuffer(r, GISTP_ROOT);
920 GISTInitBuffer(b, 0);
921 p = BufferGetPage(b);
922 gistPageAddItem(giststate, r, p, (Item) lt, IndexTupleSize(lt),
924 LP_USED, &tmpentry, &newtup);
926 if (tmpentry.pred != (((char *) lt) + sizeof(IndexTupleData)))
927 pfree(tmpentry.pred);
930 gistPageAddItem(giststate, r, p, (Item) rt, IndexTupleSize(rt),
931 OffsetNumberNext(FirstOffsetNumber), LP_USED,
934 if (tmpentry.pred != (((char *) rt) + sizeof(IndexTupleData)))
935 pfree(tmpentry.pred);
942 GISTInitBuffer(Buffer b, uint32 f)
944 GISTPageOpaque opaque;
948 pageSize = BufferGetPageSize(b);
950 page = BufferGetPage(b);
951 memset(page, 0, (int) pageSize);
952 PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
954 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
960 ** find entry with lowest penalty
963 gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
964 GISTSTATE *giststate)
973 GISTENTRY entry, identry;
976 idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
977 id = ((char *) it) + sizeof(IndexTupleData);
978 maxoff = PageGetMaxOffsetNumber(p);
982 gistdentryinit(giststate,&identry,id,(Relation)NULL,(Page)NULL,
983 (OffsetNumber)0, idsize, FALSE);
985 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) {
986 datum = (char *) PageGetItem(p, PageGetItemId(p, i));
987 size = IndexTupleSize(datum) - sizeof(IndexTupleData);
988 datum += sizeof(IndexTupleData);
989 gistdentryinit(giststate,&entry,datum,r,p,i,size,FALSE);
990 (giststate->penaltyFn)(&entry, &identry, &usize);
991 if (which_grow < 0 || usize < which_grow) {
997 if (entry.pred != datum)
1000 if (identry.pred != id)
1001 pfree(identry.pred);
1007 gistnospace(Page p, IndexTuple it)
1009 return (PageGetFreeSpace(p) < IndexTupleSize(it));
1013 gistfreestack(GISTSTACK *s)
1017 while (s != (GISTSTACK *) NULL) {
1026 ** remove an entry from a page
1029 gistdelete(Relation r, ItemPointer tid)
1032 OffsetNumber offnum;
1036 /* must write-lock on delete */
1037 RelationSetLockForWrite(r);
1039 blkno = ItemPointerGetBlockNumber(tid);
1040 offnum = ItemPointerGetOffsetNumber(tid);
1042 /* adjust any scans that will be affected by this deletion */
1043 gistadjscans(r, GISTOP_DEL, blkno, offnum);
1045 /* delete the index tuple */
1046 buf = ReadBuffer(r, blkno);
1047 page = BufferGetPage(buf);
1049 PageIndexTupleDelete(page, offnum);
1053 /* XXX -- two-phase locking, don't release the write lock */
1057 initGISTstate(GISTSTATE *giststate, Relation index)
1059 RegProcedure consistent_proc, union_proc, compress_proc, decompress_proc;
1060 RegProcedure penalty_proc, picksplit_proc, equal_proc;
1064 IndexTupleForm itupform;
1066 consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
1067 union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
1068 compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
1069 decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
1070 penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
1071 picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
1072 equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1073 fmgr_info(consistent_proc, &user_fn, &pronargs);
1074 giststate->consistentFn = user_fn;
1075 fmgr_info(union_proc, &user_fn, &pronargs);
1076 giststate->unionFn = user_fn;
1077 fmgr_info(compress_proc, &user_fn, &pronargs);
1078 giststate->compressFn = user_fn;
1079 fmgr_info(decompress_proc, &user_fn, &pronargs);
1080 giststate->decompressFn = user_fn;
1081 fmgr_info(penalty_proc, &user_fn, &pronargs);
1082 giststate->penaltyFn = user_fn;
1083 fmgr_info(picksplit_proc, &user_fn, &pronargs);
1084 giststate->picksplitFn = user_fn;
1085 fmgr_info(equal_proc, &user_fn, &pronargs);
1086 giststate->equalFn = user_fn;
1088 /* see if key type is different from type of attribute being indexed */
1089 htup = SearchSysCacheTuple(INDEXRELID, ObjectIdGetDatum(index->rd_id),
1091 itupform = (IndexTupleForm)GETSTRUCT(htup);
1092 if (!HeapTupleIsValid(htup))
1093 elog(WARN, "initGISTstate: index %d not found", index->rd_id);
1094 giststate->haskeytype = itupform->indhaskeytype;
1095 if (giststate->haskeytype) {
1096 /* key type is different -- is it byval? */
1097 htup = SearchSysCacheTuple(ATTNUM,
1098 ObjectIdGetDatum(itupform->indexrelid),
1099 UInt16GetDatum(FirstOffsetNumber),
1101 if (!HeapTupleIsValid(htup)) {
1102 elog(WARN, "initGISTstate: no attribute tuple %d %d",
1103 itupform->indexrelid, FirstOffsetNumber);
1106 giststate->keytypbyval = (((AttributeTupleForm)htup)->attbyval);
1109 giststate->keytypbyval = FALSE;
1115 ** Given an IndexTuple to be inserted on a page, this routine replaces
1116 ** the key with another key, which may involve generating a new IndexTuple
1117 ** if the sizes don't match
1120 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1122 char * datum = (((char *) t) + sizeof(IndexTupleData));
1124 /* if new entry fits in index tuple, copy it in */
1125 if (entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData)) {
1126 memcpy(datum, entry.pred, entry.bytes);
1127 /* clear out old size */
1128 t->t_info &= 0xe000;
1129 /* or in new size */
1130 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1135 /* generate a new index tuple for the compressed entry */
1136 TupleDesc tupDesc = r->rd_att;
1141 isnull = (char *) palloc(r->rd_rel->relnatts);
1142 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
1143 isnull[blank] = ' ';
1144 newtup = (IndexTuple) index_formtuple(tupDesc,
1145 (Datum *)&(entry.pred),
1147 newtup->t_tid = t->t_tid;
1155 ** initialize a GiST entry with a decompressed version of pred
1158 gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1159 Page pg, OffsetNumber o, int b, bool l)
1162 gistentryinit(*e, pr, r, pg, o, b, l);
1163 if (giststate->haskeytype) {
1164 dep = (GISTENTRY *)((giststate->decompressFn)(e));
1165 gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1167 if (dep != e) pfree(dep);
1173 ** initialize a GiST entry with a compressed version of pred
1176 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1177 Page pg, OffsetNumber o, int b, bool l)
1180 gistentryinit(*e, pr, r, pg, o, b, l);
1181 if (giststate->haskeytype) {
1182 cep = (GISTENTRY *)((giststate->compressFn)(e));
1183 gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
1185 if (cep != e) pfree(cep);
1194 ** sloppy debugging support routine, requires recompilation with appropriate
1195 ** "out" method for the index keys. Could be fixed to find that info
1196 ** in the catalogs...
1199 _gistdump(Relation r)
1203 OffsetNumber offnum, maxoff;
1205 BlockNumber nblocks;
1208 BlockNumber itblkno;
1209 OffsetNumber itoffno;
1213 nblocks = RelationGetNumberOfBlocks(r);
1214 for (blkno = 0; blkno < nblocks; blkno++) {
1215 buf = ReadBuffer(r, blkno);
1216 page = BufferGetPage(buf);
1217 po = (GISTPageOpaque) PageGetSpecialPointer(page);
1218 maxoff = PageGetMaxOffsetNumber(page);
1219 printf("Page %d maxoff %d <%s>\n", blkno, maxoff,
1220 (po->flags & F_LEAF ? "LEAF" : "INTERNAL"));
1222 if (PageIsEmpty(page)) {
1227 for (offnum = FirstOffsetNumber;
1229 offnum = OffsetNumberNext(offnum)) {
1230 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
1231 itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1232 itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid));
1233 datum = ((char *) itup);
1234 datum += sizeof(IndexTupleData);
1235 /* get out function for type of key, and out it! */
1236 itkey = (char *) int_range_out((INTRANGE *)datum);
1237 /* itkey = " unable to print"; */
1238 printf("\t[%d] size %d heap <%d,%d> key:%s\n",
1239 offnum, IndexTupleSize(itup), itblkno, itoffno, itkey);
1247 char *text_range_out(TXTRANGE *r)
1250 char *lower, *upper;
1254 result = (char *)palloc(16 + VARSIZE(TRLOWER(r)) + VARSIZE(TRUPPER(r))
1257 lower = (char *)palloc(VARSIZE(TRLOWER(r)) + 1 - VARHDRSZ);
1258 memcpy(lower, VARDATA(TRLOWER(r)), VARSIZE(TRLOWER(r)) - VARHDRSZ);
1259 lower[VARSIZE(TRLOWER(r)) - VARHDRSZ] = '\0';
1260 upper = (char *)palloc(VARSIZE(TRUPPER(r)) + 1 - VARHDRSZ);
1261 memcpy(upper, VARDATA(TRUPPER(r)), VARSIZE(TRUPPER(r)) - VARHDRSZ);
1262 upper[VARSIZE(TRUPPER(r)) - VARHDRSZ] = '\0';
1264 sprintf(result, "[%s,%s): %d", lower, upper, r->flag);
1271 int_range_out(INTRANGE *r)
1277 result = (char *)palloc(80);
1278 sprintf(result, "[%d,%d): %d",r->lower, r->upper, r->flag);
1283 #endif /* defined GISTDEBUG */