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
37 gistdoinsert(Relation r, IndexTuple itup,
38 GISTSTATE *GISTstate);
39 static InsertIndexResult
40 gistentryinsert(Relation r, GISTSTACK *stk,
42 GISTSTATE *giststate);
44 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
45 IndexTuple rtup, GISTSTATE *giststate);
47 gistAdjustKeys(Relation r, GISTSTACK *stk, BlockNumber blk,
48 char *datum, int att_size, GISTSTATE *giststate);
50 gistintinsert(Relation r, GISTSTACK *stk, IndexTuple ltup,
51 IndexTuple rtup, GISTSTATE *giststate);
52 static InsertIndexResult
53 gistSplit(Relation r, Buffer buffer,
54 GISTSTACK *stack, IndexTuple itup,
55 GISTSTATE *giststate);
57 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt,
59 static void GISTInitBuffer(Buffer b, uint32 f);
61 gistChooseSubtree(Relation r, IndexTuple itup, int level,
63 GISTSTACK **retstack, Buffer *leafbuf);
65 gistchoose(Relation r, Page p, IndexTuple it,
66 GISTSTATE *giststate);
67 static int gistnospace(Page p, IndexTuple it);
68 void gistdelete(Relation r, ItemPointer tid);
69 static IndexTuple gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t);
71 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr,
72 Relation r, Page pg, OffsetNumber o, int b, bool l);
73 static char *int_range_out(INTRANGE *r);
76 ** routine to build an index. Basically calls insert over and over
79 gistbuild(Relation heap,
96 InsertIndexResult res;
103 #ifndef OMIT_PARTIAL_INDEX
104 ExprContext *econtext;
105 TupleTable tupleTable;
106 TupleTableSlot *slot;
117 /* GiSTs only know how to do stupid locking now */
118 RelationSetLockForWrite(index);
120 setheapoverride(TRUE); /* so we can see the new pg_index tuple */
121 initGISTstate(&giststate, index);
122 setheapoverride(FALSE);
124 pred = predInfo->pred;
125 oldPred = predInfo->oldPred;
128 * We expect to be called exactly once for any index relation. If
129 * that's not the case, big trouble's what we have.
132 if (oldPred == NULL && (nb = RelationGetNumberOfBlocks(index)) != 0)
133 elog(ERROR, "%s already contains data", index->rd_rel->relname.data);
135 /* initialize the root page (if this is a new index) */
138 buffer = ReadBuffer(index, P_NEW);
139 GISTInitBuffer(buffer, F_LEAF);
143 /* init the tuple descriptors and get set for a heap scan */
144 hd = RelationGetTupleDescriptor(heap);
145 id = RelationGetTupleDescriptor(index);
146 d = (Datum *) palloc(natts * sizeof(*d));
147 nulls = (bool *) palloc(natts * sizeof(*nulls));
150 * If this is a predicate (partial) index, we will need to evaluate
151 * the predicate using ExecQual, which requires the current tuple to
152 * be in a slot of a TupleTable. In addition, ExecQual must have an
153 * ExprContext referring to that slot. Here, we initialize dummy
154 * TupleTable and ExprContext objects for this purpose. --Nels, Feb
157 #ifndef OMIT_PARTIAL_INDEX
158 if (pred != NULL || oldPred != NULL)
160 tupleTable = ExecCreateTupleTable(1);
161 slot = ExecAllocTableSlot(tupleTable);
162 econtext = makeNode(ExprContext);
163 FillDummyExprContext(econtext, slot, hd, buffer);
166 /* shut the compiler up */
172 #endif /* OMIT_PARTIAL_INDEX */
173 scan = heap_beginscan(heap, 0, false, 0, (ScanKey) NULL);
174 htup = heap_getnext(scan, 0, &buffer);
176 /* int the tuples as we insert them */
179 for (; HeapTupleIsValid(htup); htup = heap_getnext(scan, 0, &buffer))
185 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
186 * this tuple if it was already in the existing partial index
190 #ifndef OMIT_PARTIAL_INDEX
191 /* SetSlotContents(slot, htup); */
193 if (ExecQual((List *) oldPred, econtext) == true)
198 #endif /* OMIT_PARTIAL_INDEX */
202 * Skip this tuple if it doesn't satisfy the partial-index
207 #ifndef OMIT_PARTIAL_INDEX
208 /* SetSlotContents(slot, htup); */
210 if (ExecQual((List *) pred, econtext) == false)
212 #endif /* OMIT_PARTIAL_INDEX */
218 * For the current heap tuple, extract all the attributes we use
219 * in this index, and note which are null.
222 for (i = 1; i <= natts; i++)
228 * Offsets are from the start of the tuple, and are
229 * zero-based; indices are one-based. The next call returns i
230 * - 1. That's data hiding for you.
233 attoff = AttrNumberGetAttrOffset(i);
236 * d[attoff] = HeapTupleGetAttributeValue(htup, buffer,
238 d[attoff] = GetIndexValue(htup,
245 nulls[attoff] = (attnull ? 'n' : ' ');
248 /* immediately compress keys to normalize */
249 compvec = (bool *) palloc(sizeof(bool) * natts);
250 for (i = 0; i < natts; i++)
252 gistcentryinit(&giststate, &tmpcentry, (char *) d[i],
253 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
254 -1 /* size is currently bogus */ , TRUE);
255 if (d[i] != (Datum) tmpcentry.pred && !(giststate.keytypbyval))
259 d[i] = (Datum) tmpcentry.pred;
262 /* form an index tuple and point it at the heap tuple */
263 itup = index_formtuple(id, &d[0], nulls);
264 itup->t_tid = htup->t_ctid;
267 * Since we already have the index relation locked, we call
268 * gistdoinsert directly. Normal access method calls dispatch
269 * through gistinsert, which locks the relation for write. This
270 * is the right thing to do if you're inserting single tups, but
271 * not when you're initializing the whole index at once.
274 res = gistdoinsert(index, itup, &giststate);
275 for (i = 0; i < natts; i++)
276 if (compvec[i] == TRUE)
277 pfree((char *) d[i]);
283 /* okay, all heap tuples are indexed */
285 RelationUnsetLockForWrite(index);
287 if (pred != NULL || oldPred != NULL)
289 #ifndef OMIT_PARTIAL_INDEX
290 ExecDestroyTupleTable(tupleTable, true);
292 #endif /* OMIT_PARTIAL_INDEX */
296 * Since we just inted the tuples in the heap, we update its stats in
297 * pg_relation to guarantee that the planner takes advantage of the
298 * index we just created. UpdateStats() does a
299 * CommandinterIncrement(), which flushes changed entries from the
300 * system relcache. The act of constructing an index changes these
301 * heap and index tuples in the system catalogs, so they need to be
302 * flushed. We close them to guarantee that they will be.
305 hrelid = heap->rd_id;
306 irelid = index->rd_id;
310 UpdateStats(hrelid, nh, true);
311 UpdateStats(irelid, ni, false);
317 UpdateIndexPredicate(irelid, oldPred, pred);
326 * gistinsert -- wrapper for GiST tuple insertion.
328 * This is the public interface routine for tuple insertion in GiSTs.
329 * It doesn't do any work; just locks the relation and passes the buck.
332 gistinsert(Relation r, Datum *datum, char *nulls, ItemPointer ht_ctid, Relation heapRel)
334 InsertIndexResult res;
341 initGISTstate(&giststate, r);
343 /* immediately compress keys to normalize */
344 compvec = (bool *) palloc(sizeof(bool) * r->rd_att->natts);
345 for (i = 0; i < r->rd_att->natts; i++)
347 gistcentryinit(&giststate, &tmpentry, (char *) datum[i],
348 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
349 -1 /* size is currently bogus */ , TRUE);
350 if (datum[i] != (Datum) tmpentry.pred && !(giststate.keytypbyval))
354 datum[i] = (Datum) tmpentry.pred;
356 itup = index_formtuple(RelationGetTupleDescriptor(r), datum, nulls);
357 itup->t_tid = *ht_ctid;
359 RelationSetLockForWrite(r);
360 res = gistdoinsert(r, itup, &giststate);
361 for (i = 0; i < r->rd_att->natts; i++)
362 if (compvec[i] == TRUE)
363 pfree((char *) datum[i]);
367 /* XXX two-phase locking -- don't unlock the relation until EOT */
372 ** Take a compressed entry, and install it on a page. Since we now know
373 ** where the entry will live, we decompress it and recompress it using
374 ** that knowledge (some compression routines may want to fish around
375 ** on the page, for example, or do something special for leaf nodes.)
378 gistPageAddItem(GISTSTATE *giststate,
383 OffsetNumber offsetNumber,
389 IndexTuple itup = (IndexTuple) item;
392 * recompress the item given that we now know the exact page and
393 * offset for insertion
395 gistdentryinit(giststate, dentry,
396 (((char *) itup) + sizeof(IndexTupleData)),
397 (Relation) 0, (Page) 0, (OffsetNumber) InvalidOffsetNumber,
398 IndexTupleSize(itup) - sizeof(IndexTupleData), FALSE);
399 gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
400 offsetNumber, dentry->bytes, FALSE);
401 *newtup = gist_tuple_replacekey(r, *dentry, itup);
403 if (tmpcentry.pred != dentry->pred
404 && tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
405 pfree(tmpcentry.pred);
407 return (PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
408 offsetNumber, flags));
412 static InsertIndexResult
413 gistdoinsert(Relation r,
414 IndexTuple itup, /* itup contains compressed entry */
415 GISTSTATE *giststate)
418 InsertIndexResult res;
427 /* 3rd arg is ignored for now */
428 blk = gistChooseSubtree(r, itup, 0, giststate, &stack, &buffer);
429 page = (Page) BufferGetPage(buffer);
431 if (gistnospace(page, itup))
433 /* need to do a split */
434 res = gistSplit(r, buffer, stack, itup, giststate);
435 gistfreestack(stack);
436 WriteBuffer(buffer); /* don't forget to release buffer! */
440 if (PageIsEmpty(page))
441 off = FirstOffsetNumber;
443 off = OffsetNumberNext(PageGetMaxOffsetNumber(page));
445 /* add the item and write the buffer */
446 l = gistPageAddItem(giststate, r, page, (Item) itup, IndexTupleSize(itup),
447 off, LP_USED, &tmpdentry, &newtup);
450 /* now expand the page boundary in the parent to include the new child */
451 gistAdjustKeys(r, stack, blk, tmpdentry.pred, tmpdentry.bytes, giststate);
452 gistfreestack(stack);
457 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
458 pfree(tmpdentry.pred);
460 /* build and return an InsertIndexResult for this insertion */
461 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
462 ItemPointerSet(&(res->pointerData), blk, l);
469 gistChooseSubtree(Relation r, IndexTuple itup, /* itup has compressed
472 GISTSTATE *giststate,
473 GISTSTACK **retstack /* out */ ,
474 Buffer *leafbuf /* out */ )
480 GISTPageOpaque opaque;
484 buffer = InvalidBuffer;
485 stack = (GISTSTACK *) NULL;
489 /* let go of current buffer before getting next */
490 if (buffer != InvalidBuffer)
491 ReleaseBuffer(buffer);
493 /* get next buffer */
494 buffer = ReadBuffer(r, blk);
495 page = (Page) BufferGetPage(buffer);
497 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
498 if (!(opaque->flags & F_LEAF))
503 n = (GISTSTACK *) palloc(sizeof(GISTSTACK));
504 n->gs_parent = stack;
506 n->gs_child = gistchoose(r, page, itup, giststate);
509 iid = PageGetItemId(page, n->gs_child);
510 which = (IndexTuple) PageGetItem(page, iid);
511 blk = ItemPointerGetBlockNumber(&(which->t_tid));
513 } while (!(opaque->flags & F_LEAF));
523 gistAdjustKeys(Relation r,
526 char *datum, /* datum is uncompressed */
528 GISTSTATE *giststate)
542 if (stk == (GISTSTACK *) NULL)
545 b = ReadBuffer(r, stk->gs_blk);
546 p = BufferGetPage(b);
548 oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->gs_child));
549 tid = (IndexTuple) oldud;
550 size = IndexTupleSize((IndexTuple) oldud) - sizeof(IndexTupleData);
551 oldud += sizeof(IndexTupleData);
553 evec = (bytea *) palloc(2 * sizeof(GISTENTRY) + VARHDRSZ);
554 VARSIZE(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
556 /* insert decompressed oldud into entry vector */
557 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[0],
558 oldud, r, p, stk->gs_child,
560 ev0p = &((GISTENTRY *) VARDATA(evec))[0];
562 /* insert datum entry into entry vector */
563 gistentryinit(((GISTENTRY *) VARDATA(evec))[1], datum,
564 (Relation) NULL, (Page) NULL, (OffsetNumber) 0, att_size, FALSE);
565 ev1p = &((GISTENTRY *) VARDATA(evec))[1];
567 /* form union of decompressed entries */
568 datum = (*fmgr_faddr(&giststate->unionFn)) (evec, &datumsize);
570 /* did union leave decompressed version of oldud unchanged? */
571 (*fmgr_faddr(&giststate->equalFn)) (ev0p->pred, datum, &result);
574 TupleDesc td = RelationGetTupleDescriptor(r);
576 /* compress datum for storage on page */
577 gistcentryinit(giststate, ¢ry, datum, ev0p->rel, ev0p->page,
578 ev0p->offset, datumsize, FALSE);
579 if (td->attrs[0]->attlen >= 0)
581 memmove(oldud, centry.pred, att_size);
582 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
585 else if (VARSIZE(centry.pred) == VARSIZE(oldud))
587 memmove(oldud, centry.pred, VARSIZE(centry.pred));
588 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
595 * * new datum is not the same size as the old. * We have to
596 * delete the old entry and insert the new * one. Note that
597 * this may cause a split here!
600 ItemPointerData oldtid;
603 InsertIndexResult res;
605 /* delete old tuple */
606 ItemPointerSet(&oldtid, stk->gs_blk, stk->gs_child);
607 gistdelete(r, (ItemPointer) &oldtid);
609 /* generate and insert new tuple */
611 isnull = (char *) palloc(r->rd_rel->relnatts);
612 MemSet(isnull, ' ', r->rd_rel->relnatts);
613 newtup = (IndexTuple) index_formtuple(tupDesc,
614 (Datum *) ¢ry.pred, isnull);
616 /* set pointer in new tuple to point to current child */
617 ItemPointerSet(&oldtid, blk, 1);
618 newtup->t_tid = oldtid;
620 /* inserting the new entry also adjust keys above */
621 res = gistentryinsert(r, stk, newtup, giststate);
623 /* in stack, set info to point to new tuple */
624 stk->gs_blk = ItemPointerGetBlockNumber(&(res->pointerData));
625 stk->gs_child = ItemPointerGetOffsetNumber(&(res->pointerData));
631 if (centry.pred != datum)
640 * gistSplit -- split a page in the tree.
643 static InsertIndexResult
644 gistSplit(Relation r,
647 IndexTuple itup, /* contains compressed entry */
648 GISTSTATE *giststate)
662 OffsetNumber leftoff,
666 BlockNumber bufblock;
667 GISTPageOpaque opaque;
669 InsertIndexResult res;
679 isnull = (char *) palloc(r->rd_rel->relnatts);
680 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
682 p = (Page) BufferGetPage(buffer);
683 opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
687 * The root of the tree is the first block in the relation. If we're
688 * about to split the root, we need to do some hocus-pocus to enforce
692 if (BufferGetBlockNumber(buffer) == GISTP_ROOT)
694 leftbuf = ReadBuffer(r, P_NEW);
695 GISTInitBuffer(leftbuf, opaque->flags);
696 lbknum = BufferGetBlockNumber(leftbuf);
697 left = (Page) BufferGetPage(leftbuf);
702 IncrBufferRefCount(buffer);
703 lbknum = BufferGetBlockNumber(buffer);
704 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
707 rightbuf = ReadBuffer(r, P_NEW);
708 GISTInitBuffer(rightbuf, opaque->flags);
709 rbknum = BufferGetBlockNumber(rightbuf);
710 right = (Page) BufferGetPage(rightbuf);
712 /* generate the item array */
713 maxoff = PageGetMaxOffsetNumber(p);
714 entryvec = (bytea *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(GISTENTRY));
715 decompvec = (bool *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(bool));
716 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
718 item_1 = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
719 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(entryvec))[i],
720 (((char *) item_1) + sizeof(IndexTupleData)),
722 IndexTupleSize(item_1) - sizeof(IndexTupleData), FALSE);
723 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[i].pred)
724 == (((char *) item_1) + sizeof(IndexTupleData)))
725 decompvec[i] = FALSE;
730 /* add the new datum as the last entry */
731 gistdentryinit(giststate, &(((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]),
732 (((char *) itup) + sizeof(IndexTupleData)),
733 (Relation) NULL, (Page) NULL,
734 (OffsetNumber) 0, tmpentry.bytes, FALSE);
735 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]).pred !=
736 (((char *) itup) + sizeof(IndexTupleData)))
737 decompvec[maxoff + 1] = TRUE;
739 decompvec[maxoff + 1] = FALSE;
741 VARSIZE(entryvec) = (maxoff + 2) * sizeof(GISTENTRY) + VARHDRSZ;
743 /* now let the user-defined picksplit function set up the split vector */
744 (*fmgr_faddr(&giststate->picksplitFn)) (entryvec, &v);
746 /* compress ldatum and rdatum */
747 gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation) NULL,
748 (Page) NULL, (OffsetNumber) 0,
749 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
750 if (v.spl_ldatum != tmpentry.pred)
752 v.spl_ldatum = tmpentry.pred;
754 gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation) NULL,
755 (Page) NULL, (OffsetNumber) 0,
756 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
757 if (v.spl_rdatum != tmpentry.pred)
759 v.spl_rdatum = tmpentry.pred;
761 /* clean up the entry vector: its preds need to be deleted, too */
762 for (i = FirstOffsetNumber; i <= maxoff + 1; i = OffsetNumberNext(i))
764 pfree(((GISTENTRY *) VARDATA(entryvec))[i].pred);
768 leftoff = rightoff = FirstOffsetNumber;
769 maxoff = PageGetMaxOffsetNumber(p);
770 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
772 itemid = PageGetItemId(p, i);
773 item = (IndexTuple) PageGetItem(p, itemid);
775 if (i == *(v.spl_left))
777 gistPageAddItem(giststate, r, left, (Item) item,
778 IndexTupleSize(item),
779 leftoff, LP_USED, &tmpdentry, &newtup);
780 leftoff = OffsetNumberNext(leftoff);
781 v.spl_left++; /* advance in left split vector */
783 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
784 pfree(tmpdentry.pred);
785 if ((IndexTuple) item != newtup)
790 gistPageAddItem(giststate, r, right, (Item) item,
791 IndexTupleSize(item),
792 rightoff, LP_USED, &tmpdentry, &newtup);
793 rightoff = OffsetNumberNext(rightoff);
794 v.spl_right++; /* advance in right split vector */
796 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
797 pfree(tmpdentry.pred);
803 /* build an InsertIndexResult for this insertion */
804 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
806 /* now insert the new index tuple */
807 if (*(v.spl_left) != FirstOffsetNumber)
809 gistPageAddItem(giststate, r, left, (Item) itup,
810 IndexTupleSize(itup),
811 leftoff, LP_USED, &tmpdentry, &newtup);
812 leftoff = OffsetNumberNext(leftoff);
813 ItemPointerSet(&(res->pointerData), lbknum, leftoff);
815 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
816 pfree(tmpdentry.pred);
822 gistPageAddItem(giststate, r, right, (Item) itup,
823 IndexTupleSize(itup),
824 rightoff, LP_USED, &tmpdentry, &newtup);
825 rightoff = OffsetNumberNext(rightoff);
826 ItemPointerSet(&(res->pointerData), rbknum, rightoff);
828 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
829 pfree(tmpdentry.pred);
834 if ((bufblock = BufferGetBlockNumber(buffer)) != GISTP_ROOT)
835 PageRestoreTempPage(left, p);
836 WriteBuffer(leftbuf);
837 WriteBuffer(rightbuf);
840 * Okay, the page is split. We have three things left to do:
842 * 1) Adjust any active scans on this index to cope with changes we
843 * introduced in its structure by splitting this page.
845 * 2) "Tighten" the bounding box of the pointer to the left page in the
846 * parent node in the tree, if any. Since we moved a bunch of stuff
847 * off the left page, we expect it to get smaller. This happens in
848 * the internal insertion routine.
850 * 3) Insert a pointer to the right page in the parent. This may cause
851 * the parent to split. If it does, we need to repeat steps one and
852 * two for each split node in the tree.
855 /* adjust active scans */
856 gistadjscans(r, GISTOP_SPLIT, bufblock, FirstOffsetNumber);
860 ltup = (IndexTuple) index_formtuple(tupDesc,
861 (Datum *) &(v.spl_ldatum), isnull);
862 rtup = (IndexTuple) index_formtuple(tupDesc,
863 (Datum *) &(v.spl_rdatum), isnull);
866 /* set pointers to new child pages in the internal index tuples */
867 ItemPointerSet(&(ltup->t_tid), lbknum, 1);
868 ItemPointerSet(&(rtup->t_tid), rbknum, 1);
870 gistintinsert(r, stack, ltup, rtup, giststate);
879 ** After a split, we need to overwrite the old entry's key in the parent,
880 ** and install install an entry for the new key into the parent.
883 gistintinsert(Relation r,
885 IndexTuple ltup, /* new version of entry for old page */
886 IndexTuple rtup, /* entry for new page */
887 GISTSTATE *giststate)
889 ItemPointerData ltid;
891 if (stk == (GISTSTACK *) NULL)
893 gistnewroot(giststate, r, ltup, rtup);
897 /* remove old left pointer, insert the 2 new entries */
898 ItemPointerSet(<id, stk->gs_blk, stk->gs_child);
899 gistdelete(r, (ItemPointer) <id);
900 gistentryinserttwo(r, stk, ltup, rtup, giststate);
905 ** Insert two entries onto one page, handling a split for either one!
908 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
909 IndexTuple rtup, GISTSTATE *giststate)
913 InsertIndexResult res;
917 b = ReadBuffer(r, stk->gs_blk);
918 p = BufferGetPage(b);
920 if (gistnospace(p, ltup))
922 res = gistSplit(r, b, stk->gs_parent, ltup, giststate);
923 WriteBuffer(b); /* don't forget to release buffer! -
926 gistdoinsert(r, rtup, giststate);
930 gistPageAddItem(giststate, r, p, (Item) ltup,
931 IndexTupleSize(ltup), InvalidOffsetNumber,
932 LP_USED, &tmpentry, &newtup);
934 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
935 tmpentry.bytes, giststate);
937 if (tmpentry.pred != (((char *) ltup) + sizeof(IndexTupleData)))
938 pfree(tmpentry.pred);
941 gistentryinsert(r, stk, rtup, giststate);
947 ** Insert an entry onto a page
949 static InsertIndexResult
950 gistentryinsert(Relation r, GISTSTACK *stk, IndexTuple tup,
951 GISTSTATE *giststate)
955 InsertIndexResult res;
960 b = ReadBuffer(r, stk->gs_blk);
961 p = BufferGetPage(b);
963 if (gistnospace(p, tup))
965 res = gistSplit(r, b, stk->gs_parent, tup, giststate);
966 WriteBuffer(b); /* don't forget to release buffer! -
972 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
973 off = gistPageAddItem(giststate, r, p, (Item) tup, IndexTupleSize(tup),
974 InvalidOffsetNumber, LP_USED, &tmpentry, &newtup);
976 ItemPointerSet(&(res->pointerData), stk->gs_blk, off);
977 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
978 tmpentry.bytes, giststate);
980 if (tmpentry.pred != (((char *) tup) + sizeof(IndexTupleData)))
981 pfree(tmpentry.pred);
990 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt, IndexTuple rt)
997 b = ReadBuffer(r, GISTP_ROOT);
998 GISTInitBuffer(b, 0);
999 p = BufferGetPage(b);
1000 gistPageAddItem(giststate, r, p, (Item) lt, IndexTupleSize(lt),
1002 LP_USED, &tmpentry, &newtup);
1004 if (tmpentry.pred != (((char *) lt) + sizeof(IndexTupleData)))
1005 pfree(tmpentry.pred);
1008 gistPageAddItem(giststate, r, p, (Item) rt, IndexTupleSize(rt),
1009 OffsetNumberNext(FirstOffsetNumber), LP_USED,
1010 &tmpentry, &newtup);
1012 if (tmpentry.pred != (((char *) rt) + sizeof(IndexTupleData)))
1013 pfree(tmpentry.pred);
1020 GISTInitBuffer(Buffer b, uint32 f)
1022 GISTPageOpaque opaque;
1026 pageSize = BufferGetPageSize(b);
1028 page = BufferGetPage(b);
1029 MemSet(page, 0, (int) pageSize);
1030 PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
1032 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1038 ** find entry with lowest penalty
1041 gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
1042 GISTSTATE *giststate)
1044 OffsetNumber maxoff;
1056 idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
1057 id = ((char *) it) + sizeof(IndexTupleData);
1058 maxoff = PageGetMaxOffsetNumber(p);
1062 gistdentryinit(giststate, &identry, id, (Relation) NULL, (Page) NULL,
1063 (OffsetNumber) 0, idsize, FALSE);
1065 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1067 datum = (char *) PageGetItem(p, PageGetItemId(p, i));
1068 size = IndexTupleSize(datum) - sizeof(IndexTupleData);
1069 datum += sizeof(IndexTupleData);
1070 gistdentryinit(giststate, &entry, datum, r, p, i, size, FALSE);
1071 (*fmgr_faddr(&giststate->penaltyFn)) (&entry, &identry, &usize);
1072 if (which_grow < 0 || usize < which_grow)
1076 if (which_grow == 0)
1079 if (entry.pred != datum)
1082 if (identry.pred != id)
1083 pfree(identry.pred);
1089 gistnospace(Page p, IndexTuple it)
1091 return (PageGetFreeSpace(p) < IndexTupleSize(it));
1095 gistfreestack(GISTSTACK *s)
1099 while (s != (GISTSTACK *) NULL)
1109 ** remove an entry from a page
1112 gistdelete(Relation r, ItemPointer tid)
1115 OffsetNumber offnum;
1119 /* must write-lock on delete */
1120 RelationSetLockForWrite(r);
1122 blkno = ItemPointerGetBlockNumber(tid);
1123 offnum = ItemPointerGetOffsetNumber(tid);
1125 /* adjust any scans that will be affected by this deletion */
1126 gistadjscans(r, GISTOP_DEL, blkno, offnum);
1128 /* delete the index tuple */
1129 buf = ReadBuffer(r, blkno);
1130 page = BufferGetPage(buf);
1132 PageIndexTupleDelete(page, offnum);
1136 /* XXX -- two-phase locking, don't release the write lock */
1140 initGISTstate(GISTSTATE *giststate, Relation index)
1142 RegProcedure consistent_proc,
1146 RegProcedure penalty_proc,
1150 IndexTupleForm itupform;
1152 consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
1153 union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
1154 compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
1155 decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
1156 penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
1157 picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
1158 equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1159 fmgr_info(consistent_proc, &giststate->consistentFn);
1160 fmgr_info(union_proc, &giststate->unionFn);
1161 fmgr_info(compress_proc, &giststate->compressFn);
1162 fmgr_info(decompress_proc, &giststate->decompressFn);
1163 fmgr_info(penalty_proc, &giststate->penaltyFn);
1164 fmgr_info(picksplit_proc, &giststate->picksplitFn);
1165 fmgr_info(equal_proc, &giststate->equalFn);
1167 /* see if key type is different from type of attribute being indexed */
1168 htup = SearchSysCacheTuple(INDEXRELID, ObjectIdGetDatum(index->rd_id),
1170 itupform = (IndexTupleForm) GETSTRUCT(htup);
1171 if (!HeapTupleIsValid(htup))
1172 elog(ERROR, "initGISTstate: index %d not found", index->rd_id);
1173 giststate->haskeytype = itupform->indhaskeytype;
1174 if (giststate->haskeytype)
1176 /* key type is different -- is it byval? */
1177 htup = SearchSysCacheTuple(ATTNUM,
1178 ObjectIdGetDatum(itupform->indexrelid),
1179 UInt16GetDatum(FirstOffsetNumber),
1181 if (!HeapTupleIsValid(htup))
1183 elog(ERROR, "initGISTstate: no attribute tuple %d %d",
1184 itupform->indexrelid, FirstOffsetNumber);
1187 giststate->keytypbyval = (((AttributeTupleForm) htup)->attbyval);
1190 giststate->keytypbyval = FALSE;
1196 ** Given an IndexTuple to be inserted on a page, this routine replaces
1197 ** the key with another key, which may involve generating a new IndexTuple
1198 ** if the sizes don't match
1201 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1203 char *datum = (((char *) t) + sizeof(IndexTupleData));
1205 /* if new entry fits in index tuple, copy it in */
1206 if (entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData))
1208 memcpy(datum, entry.pred, entry.bytes);
1209 /* clear out old size */
1210 t->t_info &= 0xe000;
1211 /* or in new size */
1212 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1218 /* generate a new index tuple for the compressed entry */
1219 TupleDesc tupDesc = r->rd_att;
1224 isnull = (char *) palloc(r->rd_rel->relnatts);
1225 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
1226 isnull[blank] = ' ';
1227 newtup = (IndexTuple) index_formtuple(tupDesc,
1228 (Datum *) &(entry.pred),
1230 newtup->t_tid = t->t_tid;
1238 ** initialize a GiST entry with a decompressed version of pred
1241 gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1242 Page pg, OffsetNumber o, int b, bool l)
1246 gistentryinit(*e, pr, r, pg, o, b, l);
1247 if (giststate->haskeytype)
1249 dep = (GISTENTRY *) ((*fmgr_faddr(&giststate->decompressFn)) (e));
1250 gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1259 ** initialize a GiST entry with a compressed version of pred
1262 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1263 Page pg, OffsetNumber o, int b, bool l)
1267 gistentryinit(*e, pr, r, pg, o, b, l);
1268 if (giststate->haskeytype)
1270 cep = (GISTENTRY *) ((*fmgr_faddr(&giststate->compressFn)) (e));
1271 gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
1283 ** sloppy debugging support routine, requires recompilation with appropriate
1284 ** "out" method for the index keys. Could be fixed to find that info
1285 ** in the catalogs...
1288 _gistdump(Relation r)
1292 OffsetNumber offnum,
1295 BlockNumber nblocks;
1298 BlockNumber itblkno;
1299 OffsetNumber itoffno;
1303 nblocks = RelationGetNumberOfBlocks(r);
1304 for (blkno = 0; blkno < nblocks; blkno++)
1306 buf = ReadBuffer(r, blkno);
1307 page = BufferGetPage(buf);
1308 po = (GISTPageOpaque) PageGetSpecialPointer(page);
1309 maxoff = PageGetMaxOffsetNumber(page);
1310 printf("Page %d maxoff %d <%s>\n", blkno, maxoff,
1311 (po->flags & F_LEAF ? "LEAF" : "INTERNAL"));
1313 if (PageIsEmpty(page))
1319 for (offnum = FirstOffsetNumber;
1321 offnum = OffsetNumberNext(offnum))
1323 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
1324 itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1325 itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid));
1326 datum = ((char *) itup);
1327 datum += sizeof(IndexTupleData);
1328 /* get out function for type of key, and out it! */
1329 itkey = (char *) int_range_out((INTRANGE *) datum);
1330 /* itkey = " unable to print"; */
1331 printf("\t[%d] size %d heap <%d,%d> key:%s\n",
1332 offnum, IndexTupleSize(itup), itblkno, itoffno, itkey);
1342 text_range_out(TXTRANGE *r)
1350 result = (char *) palloc(NAMEDATALEN + VARSIZE(TRLOWER(r)) + VARSIZE(TRUPPER(r))
1353 lower = (char *) palloc(VARSIZE(TRLOWER(r)) + 1 - VARHDRSZ);
1354 memcpy(lower, VARDATA(TRLOWER(r)), VARSIZE(TRLOWER(r)) - VARHDRSZ);
1355 lower[VARSIZE(TRLOWER(r)) - VARHDRSZ] = '\0';
1356 upper = (char *) palloc(VARSIZE(TRUPPER(r)) + 1 - VARHDRSZ);
1357 memcpy(upper, VARDATA(TRUPPER(r)), VARSIZE(TRUPPER(r)) - VARHDRSZ);
1358 upper[VARSIZE(TRUPPER(r)) - VARHDRSZ] = '\0';
1360 sprintf(result, "[%s,%s): %d", lower, upper, r->flag);
1369 int_range_out(INTRANGE *r)
1375 result = (char *) palloc(80);
1376 sprintf(result, "[%d,%d): %d", r->lower, r->upper, r->flag);
1381 #endif /* defined GISTDEBUG */