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
36 gistdoinsert(Relation r, IndexTuple itup,
37 GISTSTATE *GISTstate);
38 static InsertIndexResult
39 gistentryinsert(Relation r, GISTSTACK *stk,
41 GISTSTATE *giststate);
43 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
44 IndexTuple rtup, GISTSTATE *giststate);
46 gistAdjustKeys(Relation r, GISTSTACK *stk, BlockNumber blk,
47 char *datum, int att_size, GISTSTATE *giststate);
49 gistintinsert(Relation r, GISTSTACK *stk, IndexTuple ltup,
50 IndexTuple rtup, GISTSTATE *giststate);
51 static InsertIndexResult
52 gistSplit(Relation r, Buffer buffer,
53 GISTSTACK *stack, IndexTuple itup,
54 GISTSTATE *giststate);
56 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt,
58 static void GISTInitBuffer(Buffer b, uint32 f);
60 gistChooseSubtree(Relation r, IndexTuple itup, int level,
62 GISTSTACK **retstack, Buffer *leafbuf);
64 gistchoose(Relation r, Page p, IndexTuple it,
65 GISTSTATE *giststate);
66 static int gistnospace(Page p, IndexTuple it);
67 void gistdelete(Relation r, ItemPointer tid);
68 static IndexTuple gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t);
70 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr,
71 Relation r, Page pg, OffsetNumber o, int b, bool l);
72 static char *int_range_out(INTRANGE *r);
75 ** routine to build an index. Basically calls insert over and over
78 gistbuild(Relation heap,
95 InsertIndexResult res;
102 #ifndef OMIT_PARTIAL_INDEX
103 ExprContext *econtext;
104 TupleTable tupleTable;
105 TupleTableSlot *slot;
116 /* GiSTs only know how to do stupid locking now */
117 RelationSetLockForWrite(index);
119 setheapoverride(TRUE); /* so we can see the new pg_index tuple */
120 initGISTstate(&giststate, index);
121 setheapoverride(FALSE);
123 pred = predInfo->pred;
124 oldPred = predInfo->oldPred;
127 * We expect to be called exactly once for any index relation. If
128 * that's not the case, big trouble's what we have.
131 if (oldPred == NULL && (nb = RelationGetNumberOfBlocks(index)) != 0)
132 elog(WARN, "%.16s already contains data", &(index->rd_rel->relname.data[0]));
134 /* initialize the root page (if this is a new index) */
137 buffer = ReadBuffer(index, P_NEW);
138 GISTInitBuffer(buffer, F_LEAF);
142 /* init the tuple descriptors and get set for a heap scan */
143 hd = RelationGetTupleDescriptor(heap);
144 id = RelationGetTupleDescriptor(index);
145 d = (Datum *) palloc(natts * sizeof(*d));
146 nulls = (bool *) palloc(natts * sizeof(*nulls));
149 * If this is a predicate (partial) index, we will need to evaluate
150 * the predicate using ExecQual, which requires the current tuple to
151 * be in a slot of a TupleTable. In addition, ExecQual must have an
152 * ExprContext referring to that slot. Here, we initialize dummy
153 * TupleTable and ExprContext objects for this purpose. --Nels, Feb
156 #ifndef OMIT_PARTIAL_INDEX
157 if (pred != NULL || oldPred != NULL)
159 tupleTable = ExecCreateTupleTable(1);
160 slot = ExecAllocTableSlot(tupleTable);
161 econtext = makeNode(ExprContext);
162 FillDummyExprContext(econtext, slot, hd, buffer);
165 /* shut the compiler up */
171 #endif /* OMIT_PARTIAL_INDEX */
172 scan = heap_beginscan(heap, 0, NowTimeQual, 0, (ScanKey) NULL);
173 htup = heap_getnext(scan, 0, &buffer);
175 /* int the tuples as we insert them */
178 for (; HeapTupleIsValid(htup); htup = heap_getnext(scan, 0, &buffer))
184 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
185 * this tuple if it was already in the existing partial index
189 #ifndef OMIT_PARTIAL_INDEX
190 /* SetSlotContents(slot, htup); */
192 if (ExecQual((List *) oldPred, econtext) == true)
197 #endif /* OMIT_PARTIAL_INDEX */
201 * Skip this tuple if it doesn't satisfy the partial-index
206 #ifndef OMIT_PARTIAL_INDEX
207 /* SetSlotContents(slot, htup); */
209 if (ExecQual((List *) pred, econtext) == false)
211 #endif /* OMIT_PARTIAL_INDEX */
217 * For the current heap tuple, extract all the attributes we use
218 * in this index, and note which are null.
221 for (i = 1; i <= natts; i++)
227 * Offsets are from the start of the tuple, and are
228 * zero-based; indices are one-based. The next call returns i
229 * - 1. That's data hiding for you.
232 attoff = AttrNumberGetAttrOffset(i);
235 * d[attoff] = HeapTupleGetAttributeValue(htup, buffer,
237 d[attoff] = GetIndexValue(htup,
244 nulls[attoff] = (attnull ? 'n' : ' ');
247 /* immediately compress keys to normalize */
248 compvec = (bool *) palloc(sizeof(bool) * natts);
249 for (i = 0; i < natts; i++)
251 gistcentryinit(&giststate, &tmpcentry, (char *) d[i],
252 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
253 -1 /* size is currently bogus */ , TRUE);
254 if (d[i] != (Datum) tmpcentry.pred && !(giststate.keytypbyval))
258 d[i] = (Datum) tmpcentry.pred;
261 /* form an index tuple and point it at the heap tuple */
262 itup = index_formtuple(id, &d[0], nulls);
263 itup->t_tid = htup->t_ctid;
266 * Since we already have the index relation locked, we call
267 * gistdoinsert directly. Normal access method calls dispatch
268 * through gistinsert, which locks the relation for write. This
269 * is the right thing to do if you're inserting single tups, but
270 * not when you're initializing the whole index at once.
273 res = gistdoinsert(index, itup, &giststate);
274 for (i = 0; i < natts; i++)
275 if (compvec[i] == TRUE)
276 pfree((char *) d[i]);
282 /* okay, all heap tuples are indexed */
284 RelationUnsetLockForWrite(index);
286 if (pred != NULL || oldPred != NULL)
288 #ifndef OMIT_PARTIAL_INDEX
289 ExecDestroyTupleTable(tupleTable, true);
291 #endif /* OMIT_PARTIAL_INDEX */
295 * Since we just inted the tuples in the heap, we update its stats in
296 * pg_relation to guarantee that the planner takes advantage of the
297 * index we just created. UpdateStats() does a
298 * CommandinterIncrement(), which flushes changed entries from the
299 * system relcache. The act of constructing an index changes these
300 * heap and index tuples in the system catalogs, so they need to be
301 * flushed. We close them to guarantee that they will be.
304 hrelid = heap->rd_id;
305 irelid = index->rd_id;
309 UpdateStats(hrelid, nh, true);
310 UpdateStats(irelid, ni, false);
316 UpdateIndexPredicate(irelid, oldPred, pred);
325 * gistinsert -- wrapper for GiST tuple insertion.
327 * This is the public interface routine for tuple insertion in GiSTs.
328 * It doesn't do any work; just locks the relation and passes the buck.
331 gistinsert(Relation r, Datum *datum, char *nulls, ItemPointer ht_ctid, Relation heapRel)
333 InsertIndexResult res;
340 initGISTstate(&giststate, r);
342 /* immediately compress keys to normalize */
343 compvec = (bool *) palloc(sizeof(bool) * r->rd_att->natts);
344 for (i = 0; i < r->rd_att->natts; i++)
346 gistcentryinit(&giststate, &tmpentry, (char *) datum[i],
347 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
348 -1 /* size is currently bogus */ , TRUE);
349 if (datum[i] != (Datum) tmpentry.pred && !(giststate.keytypbyval))
353 datum[i] = (Datum) tmpentry.pred;
355 itup = index_formtuple(RelationGetTupleDescriptor(r), datum, nulls);
356 itup->t_tid = *ht_ctid;
358 RelationSetLockForWrite(r);
359 res = gistdoinsert(r, itup, &giststate);
360 for (i = 0; i < r->rd_att->natts; i++)
361 if (compvec[i] == TRUE)
362 pfree((char *) datum[i]);
366 /* XXX two-phase locking -- don't unlock the relation until EOT */
371 ** Take a compressed entry, and install it on a page. Since we now know
372 ** where the entry will live, we decompress it and recompress it using
373 ** that knowledge (some compression routines may want to fish around
374 ** on the page, for example, or do something special for leaf nodes.)
377 gistPageAddItem(GISTSTATE *giststate,
382 OffsetNumber offsetNumber,
388 IndexTuple itup = (IndexTuple) item;
391 * recompress the item given that we now know the exact page and
392 * offset for insertion
394 gistdentryinit(giststate, dentry,
395 (((char *) itup) + sizeof(IndexTupleData)),
396 (Relation) 0, (Page) 0, (OffsetNumber) InvalidOffsetNumber,
397 IndexTupleSize(itup) - sizeof(IndexTupleData), FALSE);
398 gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
399 offsetNumber, dentry->bytes, FALSE);
400 *newtup = gist_tuple_replacekey(r, *dentry, itup);
402 if (tmpcentry.pred != dentry->pred
403 && tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
404 pfree(tmpcentry.pred);
406 return (PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
407 offsetNumber, flags));
411 static InsertIndexResult
412 gistdoinsert(Relation r,
413 IndexTuple itup, /* itup contains compressed entry */
414 GISTSTATE *giststate)
417 InsertIndexResult res;
426 /* 3rd arg is ignored for now */
427 blk = gistChooseSubtree(r, itup, 0, giststate, &stack, &buffer);
428 page = (Page) BufferGetPage(buffer);
430 if (gistnospace(page, itup))
432 /* need to do a split */
433 res = gistSplit(r, buffer, stack, itup, giststate);
434 gistfreestack(stack);
435 WriteBuffer(buffer); /* don't forget to release buffer! */
439 if (PageIsEmpty(page))
440 off = FirstOffsetNumber;
442 off = OffsetNumberNext(PageGetMaxOffsetNumber(page));
444 /* add the item and write the buffer */
445 l = gistPageAddItem(giststate, r, page, (Item) itup, IndexTupleSize(itup),
446 off, LP_USED, &tmpdentry, &newtup);
449 /* now expand the page boundary in the parent to include the new child */
450 gistAdjustKeys(r, stack, blk, tmpdentry.pred, tmpdentry.bytes, giststate);
451 gistfreestack(stack);
456 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
457 pfree(tmpdentry.pred);
459 /* build and return an InsertIndexResult for this insertion */
460 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
461 ItemPointerSet(&(res->pointerData), blk, l);
468 gistChooseSubtree(Relation r, IndexTuple itup, /* itup has compressed
471 GISTSTATE *giststate,
472 GISTSTACK **retstack /* out */ ,
473 Buffer *leafbuf /* out */ )
479 GISTPageOpaque opaque;
483 buffer = InvalidBuffer;
484 stack = (GISTSTACK *) NULL;
488 /* let go of current buffer before getting next */
489 if (buffer != InvalidBuffer)
490 ReleaseBuffer(buffer);
492 /* get next buffer */
493 buffer = ReadBuffer(r, blk);
494 page = (Page) BufferGetPage(buffer);
496 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
497 if (!(opaque->flags & F_LEAF))
502 n = (GISTSTACK *) palloc(sizeof(GISTSTACK));
503 n->gs_parent = stack;
505 n->gs_child = gistchoose(r, page, itup, giststate);
508 iid = PageGetItemId(page, n->gs_child);
509 which = (IndexTuple) PageGetItem(page, iid);
510 blk = ItemPointerGetBlockNumber(&(which->t_tid));
512 } while (!(opaque->flags & F_LEAF));
522 gistAdjustKeys(Relation r,
525 char *datum, /* datum is uncompressed */
527 GISTSTATE *giststate)
541 if (stk == (GISTSTACK *) NULL)
544 b = ReadBuffer(r, stk->gs_blk);
545 p = BufferGetPage(b);
547 oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->gs_child));
548 tid = (IndexTuple) oldud;
549 size = IndexTupleSize((IndexTuple) oldud) - sizeof(IndexTupleData);
550 oldud += sizeof(IndexTupleData);
552 evec = (bytea *) palloc(2 * sizeof(GISTENTRY) + VARHDRSZ);
553 VARSIZE(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
555 /* insert decompressed oldud into entry vector */
556 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[0],
557 oldud, r, p, stk->gs_child,
559 ev0p = &((GISTENTRY *) VARDATA(evec))[0];
561 /* insert datum entry into entry vector */
562 gistentryinit(((GISTENTRY *) VARDATA(evec))[1], datum,
563 (Relation) NULL, (Page) NULL, (OffsetNumber) 0, att_size, FALSE);
564 ev1p = &((GISTENTRY *) VARDATA(evec))[1];
566 /* form union of decompressed entries */
567 datum = (char *) (giststate->unionFn) (evec, &datumsize);
569 /* did union leave decompressed version of oldud unchanged? */
570 (giststate->equalFn) (ev0p->pred, datum, &result);
573 TupleDesc td = RelationGetTupleDescriptor(r);
575 /* compress datum for storage on page */
576 gistcentryinit(giststate, ¢ry, datum, ev0p->rel, ev0p->page,
577 ev0p->offset, datumsize, FALSE);
578 if (td->attrs[0]->attlen >= 0)
580 memmove(oldud, centry.pred, att_size);
581 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
584 else if (VARSIZE(centry.pred) == VARSIZE(oldud))
586 memmove(oldud, centry.pred, VARSIZE(centry.pred));
587 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
594 * * new datum is not the same size as the old. * We have to
595 * delete the old entry and insert the new * one. Note that
596 * this may cause a split here!
599 ItemPointerData oldtid;
602 InsertIndexResult res;
604 /* delete old tuple */
605 ItemPointerSet(&oldtid, stk->gs_blk, stk->gs_child);
606 gistdelete(r, (ItemPointer) &oldtid);
608 /* generate and insert new tuple */
610 isnull = (char *) palloc(r->rd_rel->relnatts);
611 MemSet(isnull, ' ', r->rd_rel->relnatts);
612 newtup = (IndexTuple) index_formtuple(tupDesc,
613 (Datum *) ¢ry.pred, isnull);
615 /* set pointer in new tuple to point to current child */
616 ItemPointerSet(&oldtid, blk, 1);
617 newtup->t_tid = oldtid;
619 /* inserting the new entry also adjust keys above */
620 res = gistentryinsert(r, stk, newtup, giststate);
622 /* in stack, set info to point to new tuple */
623 stk->gs_blk = ItemPointerGetBlockNumber(&(res->pointerData));
624 stk->gs_child = ItemPointerGetOffsetNumber(&(res->pointerData));
630 if (centry.pred != datum)
641 * gistSplit -- split a page in the tree.
644 static InsertIndexResult
645 gistSplit(Relation r,
648 IndexTuple itup, /* contains compressed entry */
649 GISTSTATE *giststate)
663 OffsetNumber leftoff,
667 BlockNumber bufblock;
668 GISTPageOpaque opaque;
670 InsertIndexResult res;
680 isnull = (char *) palloc(r->rd_rel->relnatts);
681 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
683 p = (Page) BufferGetPage(buffer);
684 opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
688 * The root of the tree is the first block in the relation. If we're
689 * about to split the root, we need to do some hocus-pocus to enforce
693 if (BufferGetBlockNumber(buffer) == GISTP_ROOT)
695 leftbuf = ReadBuffer(r, P_NEW);
696 GISTInitBuffer(leftbuf, opaque->flags);
697 lbknum = BufferGetBlockNumber(leftbuf);
698 left = (Page) BufferGetPage(leftbuf);
703 IncrBufferRefCount(buffer);
704 lbknum = BufferGetBlockNumber(buffer);
705 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
708 rightbuf = ReadBuffer(r, P_NEW);
709 GISTInitBuffer(rightbuf, opaque->flags);
710 rbknum = BufferGetBlockNumber(rightbuf);
711 right = (Page) BufferGetPage(rightbuf);
713 /* generate the item array */
714 maxoff = PageGetMaxOffsetNumber(p);
715 entryvec = (bytea *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(GISTENTRY));
716 decompvec = (bool *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(bool));
717 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
719 item_1 = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
720 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(entryvec))[i],
721 (((char *) item_1) + sizeof(IndexTupleData)),
723 IndexTupleSize(item_1) - sizeof(IndexTupleData), FALSE);
724 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[i].pred)
725 == (((char *) item_1) + sizeof(IndexTupleData)))
726 decompvec[i] = FALSE;
731 /* add the new datum as the last entry */
732 gistdentryinit(giststate, &(((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]),
733 (((char *) itup) + sizeof(IndexTupleData)),
734 (Relation) NULL, (Page) NULL,
735 (OffsetNumber) 0, tmpentry.bytes, FALSE);
736 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]).pred !=
737 (((char *) itup) + sizeof(IndexTupleData)))
738 decompvec[maxoff + 1] = TRUE;
740 decompvec[maxoff + 1] = FALSE;
742 VARSIZE(entryvec) = (maxoff + 2) * sizeof(GISTENTRY) + VARHDRSZ;
744 /* now let the user-defined picksplit function set up the split vector */
745 (giststate->picksplitFn) (entryvec, &v);
747 /* compress ldatum and rdatum */
748 gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation) NULL,
749 (Page) NULL, (OffsetNumber) 0,
750 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
751 if (v.spl_ldatum != tmpentry.pred)
753 v.spl_ldatum = tmpentry.pred;
755 gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation) NULL,
756 (Page) NULL, (OffsetNumber) 0,
757 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
758 if (v.spl_rdatum != tmpentry.pred)
760 v.spl_rdatum = tmpentry.pred;
762 /* clean up the entry vector: its preds need to be deleted, too */
763 for (i = FirstOffsetNumber; i <= maxoff + 1; i = OffsetNumberNext(i))
765 pfree(((GISTENTRY *) VARDATA(entryvec))[i].pred);
769 leftoff = rightoff = FirstOffsetNumber;
770 maxoff = PageGetMaxOffsetNumber(p);
771 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
773 itemid = PageGetItemId(p, i);
774 item = (IndexTuple) PageGetItem(p, itemid);
776 if (i == *(v.spl_left))
778 gistPageAddItem(giststate, r, left, (Item) item,
779 IndexTupleSize(item),
780 leftoff, LP_USED, &tmpdentry, &newtup);
781 leftoff = OffsetNumberNext(leftoff);
782 v.spl_left++; /* advance in left split vector */
784 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
785 pfree(tmpdentry.pred);
786 if ((IndexTuple) item != newtup)
791 gistPageAddItem(giststate, r, right, (Item) item,
792 IndexTupleSize(item),
793 rightoff, LP_USED, &tmpdentry, &newtup);
794 rightoff = OffsetNumberNext(rightoff);
795 v.spl_right++; /* advance in right split vector */
797 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
798 pfree(tmpdentry.pred);
804 /* build an InsertIndexResult for this insertion */
805 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
807 /* now insert the new index tuple */
808 if (*(v.spl_left) != FirstOffsetNumber)
810 gistPageAddItem(giststate, r, left, (Item) itup,
811 IndexTupleSize(itup),
812 leftoff, LP_USED, &tmpdentry, &newtup);
813 leftoff = OffsetNumberNext(leftoff);
814 ItemPointerSet(&(res->pointerData), lbknum, leftoff);
816 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
817 pfree(tmpdentry.pred);
823 gistPageAddItem(giststate, r, right, (Item) itup,
824 IndexTupleSize(itup),
825 rightoff, LP_USED, &tmpdentry, &newtup);
826 rightoff = OffsetNumberNext(rightoff);
827 ItemPointerSet(&(res->pointerData), rbknum, rightoff);
829 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
830 pfree(tmpdentry.pred);
835 if ((bufblock = BufferGetBlockNumber(buffer)) != GISTP_ROOT)
837 PageRestoreTempPage(left, p);
839 WriteBuffer(leftbuf);
840 WriteBuffer(rightbuf);
843 * Okay, the page is split. We have three things left to do:
845 * 1) Adjust any active scans on this index to cope with changes we
846 * introduced in its structure by splitting this page.
848 * 2) "Tighten" the bounding box of the pointer to the left page in the
849 * parent node in the tree, if any. Since we moved a bunch of stuff
850 * off the left page, we expect it to get smaller. This happens in
851 * the internal insertion routine.
853 * 3) Insert a pointer to the right page in the parent. This may cause
854 * the parent to split. If it does, we need to repeat steps one and
855 * two for each split node in the tree.
858 /* adjust active scans */
859 gistadjscans(r, GISTOP_SPLIT, bufblock, FirstOffsetNumber);
863 ltup = (IndexTuple) index_formtuple(tupDesc,
864 (Datum *) &(v.spl_ldatum), isnull);
865 rtup = (IndexTuple) index_formtuple(tupDesc,
866 (Datum *) &(v.spl_rdatum), isnull);
869 /* set pointers to new child pages in the internal index tuples */
870 ItemPointerSet(&(ltup->t_tid), lbknum, 1);
871 ItemPointerSet(&(rtup->t_tid), rbknum, 1);
873 gistintinsert(r, stack, ltup, rtup, giststate);
882 ** After a split, we need to overwrite the old entry's key in the parent,
883 ** and install install an entry for the new key into the parent.
886 gistintinsert(Relation r,
888 IndexTuple ltup, /* new version of entry for old page */
889 IndexTuple rtup, /* entry for new page */
890 GISTSTATE *giststate)
892 ItemPointerData ltid;
894 if (stk == (GISTSTACK *) NULL)
896 gistnewroot(giststate, r, ltup, rtup);
900 /* remove old left pointer, insert the 2 new entries */
901 ItemPointerSet(<id, stk->gs_blk, stk->gs_child);
902 gistdelete(r, (ItemPointer) <id);
903 gistentryinserttwo(r, stk, ltup, rtup, giststate);
908 ** Insert two entries onto one page, handling a split for either one!
911 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
912 IndexTuple rtup, GISTSTATE *giststate)
916 InsertIndexResult res;
920 b = ReadBuffer(r, stk->gs_blk);
921 p = BufferGetPage(b);
923 if (gistnospace(p, ltup))
925 res = gistSplit(r, b, stk->gs_parent, ltup, giststate);
926 WriteBuffer(b); /* don't forget to release buffer! -
929 gistdoinsert(r, rtup, giststate);
933 gistPageAddItem(giststate, r, p, (Item) ltup,
934 IndexTupleSize(ltup), InvalidOffsetNumber,
935 LP_USED, &tmpentry, &newtup);
937 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
938 tmpentry.bytes, giststate);
940 if (tmpentry.pred != (((char *) ltup) + sizeof(IndexTupleData)))
941 pfree(tmpentry.pred);
944 gistentryinsert(r, stk, rtup, giststate);
950 ** Insert an entry onto a page
952 static InsertIndexResult
953 gistentryinsert(Relation r, GISTSTACK *stk, IndexTuple tup,
954 GISTSTATE *giststate)
958 InsertIndexResult res;
963 b = ReadBuffer(r, stk->gs_blk);
964 p = BufferGetPage(b);
966 if (gistnospace(p, tup))
968 res = gistSplit(r, b, stk->gs_parent, tup, giststate);
969 WriteBuffer(b); /* don't forget to release buffer! -
975 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
976 off = gistPageAddItem(giststate, r, p, (Item) tup, IndexTupleSize(tup),
977 InvalidOffsetNumber, LP_USED, &tmpentry, &newtup);
979 ItemPointerSet(&(res->pointerData), stk->gs_blk, off);
980 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
981 tmpentry.bytes, giststate);
983 if (tmpentry.pred != (((char *) tup) + sizeof(IndexTupleData)))
984 pfree(tmpentry.pred);
993 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt, IndexTuple rt)
1000 b = ReadBuffer(r, GISTP_ROOT);
1001 GISTInitBuffer(b, 0);
1002 p = BufferGetPage(b);
1003 gistPageAddItem(giststate, r, p, (Item) lt, IndexTupleSize(lt),
1005 LP_USED, &tmpentry, &newtup);
1007 if (tmpentry.pred != (((char *) lt) + sizeof(IndexTupleData)))
1008 pfree(tmpentry.pred);
1011 gistPageAddItem(giststate, r, p, (Item) rt, IndexTupleSize(rt),
1012 OffsetNumberNext(FirstOffsetNumber), LP_USED,
1013 &tmpentry, &newtup);
1015 if (tmpentry.pred != (((char *) rt) + sizeof(IndexTupleData)))
1016 pfree(tmpentry.pred);
1023 GISTInitBuffer(Buffer b, uint32 f)
1025 GISTPageOpaque opaque;
1029 pageSize = BufferGetPageSize(b);
1031 page = BufferGetPage(b);
1032 MemSet(page, 0, (int) pageSize);
1033 PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
1035 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1041 ** find entry with lowest penalty
1044 gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
1045 GISTSTATE *giststate)
1047 OffsetNumber maxoff;
1059 idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
1060 id = ((char *) it) + sizeof(IndexTupleData);
1061 maxoff = PageGetMaxOffsetNumber(p);
1065 gistdentryinit(giststate, &identry, id, (Relation) NULL, (Page) NULL,
1066 (OffsetNumber) 0, idsize, FALSE);
1068 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1070 datum = (char *) PageGetItem(p, PageGetItemId(p, i));
1071 size = IndexTupleSize(datum) - sizeof(IndexTupleData);
1072 datum += sizeof(IndexTupleData);
1073 gistdentryinit(giststate, &entry, datum, r, p, i, size, FALSE);
1074 (giststate->penaltyFn) (&entry, &identry, &usize);
1075 if (which_grow < 0 || usize < which_grow)
1079 if (which_grow == 0)
1082 if (entry.pred != datum)
1085 if (identry.pred != id)
1086 pfree(identry.pred);
1092 gistnospace(Page p, IndexTuple it)
1094 return (PageGetFreeSpace(p) < IndexTupleSize(it));
1098 gistfreestack(GISTSTACK *s)
1102 while (s != (GISTSTACK *) NULL)
1112 ** remove an entry from a page
1115 gistdelete(Relation r, ItemPointer tid)
1118 OffsetNumber offnum;
1122 /* must write-lock on delete */
1123 RelationSetLockForWrite(r);
1125 blkno = ItemPointerGetBlockNumber(tid);
1126 offnum = ItemPointerGetOffsetNumber(tid);
1128 /* adjust any scans that will be affected by this deletion */
1129 gistadjscans(r, GISTOP_DEL, blkno, offnum);
1131 /* delete the index tuple */
1132 buf = ReadBuffer(r, blkno);
1133 page = BufferGetPage(buf);
1135 PageIndexTupleDelete(page, offnum);
1139 /* XXX -- two-phase locking, don't release the write lock */
1143 initGISTstate(GISTSTATE *giststate, Relation index)
1145 RegProcedure consistent_proc,
1149 RegProcedure penalty_proc,
1155 IndexTupleForm itupform;
1157 consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
1158 union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
1159 compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
1160 decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
1161 penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
1162 picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
1163 equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1164 fmgr_info(consistent_proc, &user_fn, &pronargs);
1165 giststate->consistentFn = user_fn;
1166 fmgr_info(union_proc, &user_fn, &pronargs);
1167 giststate->unionFn = user_fn;
1168 fmgr_info(compress_proc, &user_fn, &pronargs);
1169 giststate->compressFn = user_fn;
1170 fmgr_info(decompress_proc, &user_fn, &pronargs);
1171 giststate->decompressFn = user_fn;
1172 fmgr_info(penalty_proc, &user_fn, &pronargs);
1173 giststate->penaltyFn = user_fn;
1174 fmgr_info(picksplit_proc, &user_fn, &pronargs);
1175 giststate->picksplitFn = user_fn;
1176 fmgr_info(equal_proc, &user_fn, &pronargs);
1177 giststate->equalFn = user_fn;
1179 /* see if key type is different from type of attribute being indexed */
1180 htup = SearchSysCacheTuple(INDEXRELID, ObjectIdGetDatum(index->rd_id),
1182 itupform = (IndexTupleForm) GETSTRUCT(htup);
1183 if (!HeapTupleIsValid(htup))
1184 elog(WARN, "initGISTstate: index %d not found", index->rd_id);
1185 giststate->haskeytype = itupform->indhaskeytype;
1186 if (giststate->haskeytype)
1188 /* key type is different -- is it byval? */
1189 htup = SearchSysCacheTuple(ATTNUM,
1190 ObjectIdGetDatum(itupform->indexrelid),
1191 UInt16GetDatum(FirstOffsetNumber),
1193 if (!HeapTupleIsValid(htup))
1195 elog(WARN, "initGISTstate: no attribute tuple %d %d",
1196 itupform->indexrelid, FirstOffsetNumber);
1199 giststate->keytypbyval = (((AttributeTupleForm) htup)->attbyval);
1202 giststate->keytypbyval = FALSE;
1208 ** Given an IndexTuple to be inserted on a page, this routine replaces
1209 ** the key with another key, which may involve generating a new IndexTuple
1210 ** if the sizes don't match
1213 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1215 char *datum = (((char *) t) + sizeof(IndexTupleData));
1217 /* if new entry fits in index tuple, copy it in */
1218 if (entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData))
1220 memcpy(datum, entry.pred, entry.bytes);
1221 /* clear out old size */
1222 t->t_info &= 0xe000;
1223 /* or in new size */
1224 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1230 /* generate a new index tuple for the compressed entry */
1231 TupleDesc tupDesc = r->rd_att;
1236 isnull = (char *) palloc(r->rd_rel->relnatts);
1237 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
1238 isnull[blank] = ' ';
1239 newtup = (IndexTuple) index_formtuple(tupDesc,
1240 (Datum *) &(entry.pred),
1242 newtup->t_tid = t->t_tid;
1250 ** initialize a GiST entry with a decompressed version of pred
1253 gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1254 Page pg, OffsetNumber o, int b, bool l)
1258 gistentryinit(*e, pr, r, pg, o, b, l);
1259 if (giststate->haskeytype)
1261 dep = (GISTENTRY *) ((giststate->decompressFn) (e));
1262 gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1271 ** initialize a GiST entry with a compressed version of pred
1274 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1275 Page pg, OffsetNumber o, int b, bool l)
1279 gistentryinit(*e, pr, r, pg, o, b, l);
1280 if (giststate->haskeytype)
1282 cep = (GISTENTRY *) ((giststate->compressFn) (e));
1283 gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
1295 ** sloppy debugging support routine, requires recompilation with appropriate
1296 ** "out" method for the index keys. Could be fixed to find that info
1297 ** in the catalogs...
1300 _gistdump(Relation r)
1304 OffsetNumber offnum,
1307 BlockNumber nblocks;
1310 BlockNumber itblkno;
1311 OffsetNumber itoffno;
1315 nblocks = RelationGetNumberOfBlocks(r);
1316 for (blkno = 0; blkno < nblocks; blkno++)
1318 buf = ReadBuffer(r, blkno);
1319 page = BufferGetPage(buf);
1320 po = (GISTPageOpaque) PageGetSpecialPointer(page);
1321 maxoff = PageGetMaxOffsetNumber(page);
1322 printf("Page %d maxoff %d <%s>\n", blkno, maxoff,
1323 (po->flags & F_LEAF ? "LEAF" : "INTERNAL"));
1325 if (PageIsEmpty(page))
1331 for (offnum = FirstOffsetNumber;
1333 offnum = OffsetNumberNext(offnum))
1335 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
1336 itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1337 itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid));
1338 datum = ((char *) itup);
1339 datum += sizeof(IndexTupleData);
1340 /* get out function for type of key, and out it! */
1341 itkey = (char *) int_range_out((INTRANGE *) datum);
1342 /* itkey = " unable to print"; */
1343 printf("\t[%d] size %d heap <%d,%d> key:%s\n",
1344 offnum, IndexTupleSize(itup), itblkno, itoffno, itkey);
1354 text_range_out(TXTRANGE *r)
1362 result = (char *) palloc(16 + VARSIZE(TRLOWER(r)) + VARSIZE(TRUPPER(r))
1365 lower = (char *) palloc(VARSIZE(TRLOWER(r)) + 1 - VARHDRSZ);
1366 memcpy(lower, VARDATA(TRLOWER(r)), VARSIZE(TRLOWER(r)) - VARHDRSZ);
1367 lower[VARSIZE(TRLOWER(r)) - VARHDRSZ] = '\0';
1368 upper = (char *) palloc(VARSIZE(TRUPPER(r)) + 1 - VARHDRSZ);
1369 memcpy(upper, VARDATA(TRUPPER(r)), VARSIZE(TRUPPER(r)) - VARHDRSZ);
1370 upper[VARSIZE(TRUPPER(r)) - VARHDRSZ] = '\0';
1372 sprintf(result, "[%s,%s): %d", lower, upper, r->flag);
1381 int_range_out(INTRANGE *r)
1387 result = (char *) palloc(80);
1388 sprintf(result, "[%d,%d): %d", r->lower, r->upper, r->flag);
1393 #endif /* defined GISTDEBUG */