1 /*-------------------------------------------------------------------------
4 * interface routines for the postgres GiST index access method.
9 * $Header: /cvsroot/pgsql/src/backend/access/gist/gist.c,v 1.63 2000/10/21 15:43:09 vadim Exp $
11 *-------------------------------------------------------------------------
16 #include "access/genam.h"
17 #include "access/gist.h"
18 #include "access/gistscan.h"
19 #include "access/heapam.h"
20 #include "catalog/index.h"
21 #include "catalog/pg_index.h"
22 #include "executor/executor.h"
23 #include "miscadmin.h"
24 #include "utils/syscache.h"
27 #include "access/xlogutils.h"
28 void gist_redo(XLogRecPtr lsn, XLogRecord *record);
29 void gist_undo(XLogRecPtr lsn, XLogRecord *record);
30 void gist_desc(char *buf, uint8 xl_info, char* rec);
33 /* non-export function prototypes */
34 static InsertIndexResult gistdoinsert(Relation r, IndexTuple itup,
35 GISTSTATE *GISTstate);
36 static InsertIndexResult gistentryinsert(Relation r, GISTSTACK *stk,
38 GISTSTATE *giststate);
39 static void gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
40 IndexTuple rtup, GISTSTATE *giststate);
41 static void gistAdjustKeys(Relation r, GISTSTACK *stk, BlockNumber blk,
42 char *datum, int att_size, GISTSTATE *giststate);
43 static void gistintinsert(Relation r, GISTSTACK *stk, IndexTuple ltup,
44 IndexTuple rtup, GISTSTATE *giststate);
45 static InsertIndexResult gistSplit(Relation r, Buffer buffer,
46 GISTSTACK *stack, IndexTuple itup,
47 GISTSTATE *giststate);
48 static void gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt,
50 static void GISTInitBuffer(Buffer b, uint32 f);
51 static BlockNumber gistChooseSubtree(Relation r, IndexTuple itup, int level,
53 GISTSTACK **retstack, Buffer *leafbuf);
54 static OffsetNumber gistchoose(Relation r, Page p, IndexTuple it,
55 GISTSTATE *giststate);
56 static int gistnospace(Page p, IndexTuple it);
57 static IndexTuple gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t);
58 static void gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr,
59 Relation r, Page pg, OffsetNumber o, int b, bool l);
62 static char *int_range_out(INTRANGE *r);
67 ** routine to build an index. Basically calls insert over and over
70 gistbuild(PG_FUNCTION_ARGS)
72 Relation heap = (Relation) PG_GETARG_POINTER(0);
73 Relation index = (Relation) PG_GETARG_POINTER(1);
74 IndexInfo *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
75 Node *oldPred = (Node *) PG_GETARG_POINTER(3);
77 IndexStrategy istrat = (IndexStrategy) PG_GETARG_POINTER(4);
84 Datum attdata[INDEX_MAX_KEYS];
85 char nulls[INDEX_MAX_KEYS];
88 Node *pred = indexInfo->ii_Predicate;
89 #ifndef OMIT_PARTIAL_INDEX
90 TupleTable tupleTable;
93 ExprContext *econtext;
94 InsertIndexResult res = NULL;
97 Buffer buffer = InvalidBuffer;
101 /* no locking is needed */
103 initGISTstate(&giststate, index);
106 * We expect to be called exactly once for any index relation. If
107 * that's not the case, big trouble's what we have.
109 if (oldPred == NULL && RelationGetNumberOfBlocks(index) != 0)
110 elog(ERROR, "%s already contains data", RelationGetRelationName(index));
112 /* initialize the root page (if this is a new index) */
115 buffer = ReadBuffer(index, P_NEW);
116 GISTInitBuffer(buffer, F_LEAF);
120 /* get tuple descriptors for heap and index relations */
121 htupdesc = RelationGetDescr(heap);
122 itupdesc = RelationGetDescr(index);
125 * If this is a predicate (partial) index, we will need to evaluate
126 * the predicate using ExecQual, which requires the current tuple to
127 * be in a slot of a TupleTable. In addition, ExecQual must have an
128 * ExprContext referring to that slot. Here, we initialize dummy
129 * TupleTable and ExprContext objects for this purpose. --Nels, Feb 92
131 * We construct the ExprContext anyway since we need a per-tuple
132 * temporary memory context for function evaluation -- tgl July 00
134 #ifndef OMIT_PARTIAL_INDEX
135 if (pred != NULL || oldPred != NULL)
137 tupleTable = ExecCreateTupleTable(1);
138 slot = ExecAllocTableSlot(tupleTable);
139 ExecSetSlotDescriptor(slot, htupdesc);
146 econtext = MakeExprContext(slot, TransactionCommandContext);
148 econtext = MakeExprContext(NULL, TransactionCommandContext);
149 #endif /* OMIT_PARTIAL_INDEX */
151 /* build the index */
154 compvec = (bool *) palloc(sizeof(bool) * indexInfo->ii_NumIndexAttrs);
156 /* start a heap scan */
157 hscan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);
159 while (HeapTupleIsValid(htup = heap_getnext(hscan, 0)))
161 MemoryContextReset(econtext->ecxt_per_tuple_memory);
165 #ifndef OMIT_PARTIAL_INDEX
167 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
168 * this tuple if it was already in the existing partial index
173 if (ExecQual((List *) oldPred, econtext, false))
181 * Skip this tuple if it doesn't satisfy the partial-index
187 if (!ExecQual((List *) pred, econtext, false))
190 #endif /* OMIT_PARTIAL_INDEX */
195 * For the current heap tuple, extract all the attributes we use
196 * in this index, and note which are null.
198 FormIndexDatum(indexInfo,
201 econtext->ecxt_per_tuple_memory,
205 /* immediately compress keys to normalize */
206 for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
208 gistcentryinit(&giststate, &tmpcentry, (char *) attdata[i],
209 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
210 -1 /* size is currently bogus */ , TRUE);
211 if (attdata[i] != (Datum) tmpcentry.pred &&
212 !(giststate.keytypbyval))
216 attdata[i] = (Datum) tmpcentry.pred;
219 /* form an index tuple and point it at the heap tuple */
220 itup = index_formtuple(itupdesc, attdata, nulls);
221 itup->t_tid = htup->t_self;
224 * Since we already have the index relation locked, we call
225 * gistdoinsert directly. Normal access method calls dispatch
226 * through gistinsert, which locks the relation for write. This
227 * is the right thing to do if you're inserting single tups, but
228 * not when you're initializing the whole index at once.
231 res = gistdoinsert(index, itup, &giststate);
233 for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
235 pfree(DatumGetPointer(attdata[i]));
241 /* okay, all heap tuples are indexed */
246 #ifndef OMIT_PARTIAL_INDEX
247 if (pred != NULL || oldPred != NULL)
249 ExecDropTupleTable(tupleTable, true);
251 #endif /* OMIT_PARTIAL_INDEX */
252 FreeExprContext(econtext);
255 * Since we just counted the tuples in the heap, we update its stats
256 * in pg_class to guarantee that the planner takes advantage of the
257 * index we just created. But, only update statistics during normal
258 * index definitions, not for indices on system catalogs created
259 * during bootstrap processing. We must close the relations before
260 * updating statistics to guarantee that the relcache entries are
261 * flushed when we increment the command counter in UpdateStats(). But
262 * we do not release any locks on the relations; those will be held
263 * until end of transaction.
265 if (IsNormalProcessingMode())
267 Oid hrelid = RelationGetRelid(heap);
268 Oid irelid = RelationGetRelid(index);
269 bool inplace = IsReindexProcessing();
271 heap_close(heap, NoLock);
273 UpdateStats(hrelid, nhtups, inplace);
274 UpdateStats(irelid, nitups, inplace);
275 if (oldPred != NULL && !inplace)
277 if (nitups == nhtups)
279 UpdateIndexPredicate(irelid, oldPred, pred);
287 * gistinsert -- wrapper for GiST tuple insertion.
289 * This is the public interface routine for tuple insertion in GiSTs.
290 * It doesn't do any work; just locks the relation and passes the buck.
293 gistinsert(PG_FUNCTION_ARGS)
295 Relation r = (Relation) PG_GETARG_POINTER(0);
296 Datum *datum = (Datum *) PG_GETARG_POINTER(1);
297 char *nulls = (char *) PG_GETARG_POINTER(2);
298 ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3);
300 Relation heapRel = (Relation) PG_GETARG_POINTER(4);
302 InsertIndexResult res;
309 initGISTstate(&giststate, r);
311 /* immediately compress keys to normalize */
312 compvec = (bool *) palloc(sizeof(bool) * r->rd_att->natts);
313 for (i = 0; i < r->rd_att->natts; i++)
315 gistcentryinit(&giststate, &tmpentry, (char *) datum[i],
316 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
317 -1 /* size is currently bogus */ , TRUE);
318 if (datum[i] != (Datum) tmpentry.pred && !(giststate.keytypbyval))
322 datum[i] = (Datum) tmpentry.pred;
324 itup = index_formtuple(RelationGetDescr(r), datum, nulls);
325 itup->t_tid = *ht_ctid;
328 * Notes in ExecUtils:ExecOpenIndices()
330 * RelationSetLockForWrite(r);
333 res = gistdoinsert(r, itup, &giststate);
334 for (i = 0; i < r->rd_att->natts; i++)
335 if (compvec[i] == TRUE)
336 pfree((char *) datum[i]);
340 PG_RETURN_POINTER(res);
344 ** Take a compressed entry, and install it on a page. Since we now know
345 ** where the entry will live, we decompress it and recompress it using
346 ** that knowledge (some compression routines may want to fish around
347 ** on the page, for example, or do something special for leaf nodes.)
350 gistPageAddItem(GISTSTATE *giststate,
355 OffsetNumber offsetNumber,
361 IndexTuple itup = (IndexTuple) item;
364 * recompress the item given that we now know the exact page and
365 * offset for insertion
367 gistdentryinit(giststate, dentry,
368 (((char *) itup) + sizeof(IndexTupleData)),
369 (Relation) 0, (Page) 0, (OffsetNumber) InvalidOffsetNumber,
370 IndexTupleSize(itup) - sizeof(IndexTupleData), FALSE);
371 gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
372 offsetNumber, dentry->bytes, FALSE);
373 *newtup = gist_tuple_replacekey(r, *dentry, itup);
375 if (tmpcentry.pred != dentry->pred
376 && tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
377 pfree(tmpcentry.pred);
379 return (PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
380 offsetNumber, flags));
384 static InsertIndexResult
385 gistdoinsert(Relation r,
386 IndexTuple itup, /* itup contains compressed entry */
387 GISTSTATE *giststate)
390 InsertIndexResult res;
399 /* 3rd arg is ignored for now */
400 blk = gistChooseSubtree(r, itup, 0, giststate, &stack, &buffer);
401 page = (Page) BufferGetPage(buffer);
403 if (gistnospace(page, itup))
405 /* need to do a split */
406 res = gistSplit(r, buffer, stack, itup, giststate);
407 gistfreestack(stack);
408 WriteBuffer(buffer); /* don't forget to release buffer! */
412 if (PageIsEmpty(page))
413 off = FirstOffsetNumber;
415 off = OffsetNumberNext(PageGetMaxOffsetNumber(page));
417 /* add the item and write the buffer */
418 l = gistPageAddItem(giststate, r, page, (Item) itup, IndexTupleSize(itup),
419 off, LP_USED, &tmpdentry, &newtup);
422 /* now expand the page boundary in the parent to include the new child */
423 gistAdjustKeys(r, stack, blk, tmpdentry.pred, tmpdentry.bytes, giststate);
424 gistfreestack(stack);
429 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
430 pfree(tmpdentry.pred);
432 /* build and return an InsertIndexResult for this insertion */
433 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
434 ItemPointerSet(&(res->pointerData), blk, l);
441 gistChooseSubtree(Relation r, IndexTuple itup, /* itup has compressed
444 GISTSTATE *giststate,
445 GISTSTACK **retstack /* out */ ,
446 Buffer *leafbuf /* out */ )
452 GISTPageOpaque opaque;
456 buffer = InvalidBuffer;
457 stack = (GISTSTACK *) NULL;
461 /* let go of current buffer before getting next */
462 if (buffer != InvalidBuffer)
463 ReleaseBuffer(buffer);
465 /* get next buffer */
466 buffer = ReadBuffer(r, blk);
467 page = (Page) BufferGetPage(buffer);
469 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
470 if (!(opaque->flags & F_LEAF))
475 n = (GISTSTACK *) palloc(sizeof(GISTSTACK));
476 n->gs_parent = stack;
478 n->gs_child = gistchoose(r, page, itup, giststate);
481 iid = PageGetItemId(page, n->gs_child);
482 which = (IndexTuple) PageGetItem(page, iid);
483 blk = ItemPointerGetBlockNumber(&(which->t_tid));
485 } while (!(opaque->flags & F_LEAF));
495 gistAdjustKeys(Relation r,
498 char *datum, /* datum is uncompressed */
500 GISTSTATE *giststate)
514 if (stk == (GISTSTACK *) NULL)
517 b = ReadBuffer(r, stk->gs_blk);
518 p = BufferGetPage(b);
520 oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->gs_child));
521 tid = (IndexTuple) oldud;
522 size = IndexTupleSize((IndexTuple) oldud) - sizeof(IndexTupleData);
523 oldud += sizeof(IndexTupleData);
525 evec = (bytea *) palloc(2 * sizeof(GISTENTRY) + VARHDRSZ);
526 VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
528 /* insert decompressed oldud into entry vector */
529 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[0],
530 oldud, r, p, stk->gs_child,
532 ev0p = &((GISTENTRY *) VARDATA(evec))[0];
534 /* insert datum entry into entry vector */
535 gistentryinit(((GISTENTRY *) VARDATA(evec))[1], datum,
536 (Relation) NULL, (Page) NULL, (OffsetNumber) 0, att_size, FALSE);
537 ev1p = &((GISTENTRY *) VARDATA(evec))[1];
539 /* form union of decompressed entries */
541 DatumGetPointer(FunctionCall2(&giststate->unionFn,
542 PointerGetDatum(evec),
543 PointerGetDatum(&datumsize)));
545 /* did union leave decompressed version of oldud unchanged? */
546 FunctionCall3(&giststate->equalFn,
547 PointerGetDatum(ev0p->pred),
548 PointerGetDatum(datum),
549 PointerGetDatum(&result));
552 TupleDesc td = RelationGetDescr(r);
554 /* compress datum for storage on page */
555 gistcentryinit(giststate, ¢ry, datum, ev0p->rel, ev0p->page,
556 ev0p->offset, datumsize, FALSE);
557 if (td->attrs[0]->attlen >= 0)
559 memmove(oldud, centry.pred, att_size);
560 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
563 else if (VARSIZE(centry.pred) == VARSIZE(oldud))
565 memmove(oldud, centry.pred, VARSIZE(centry.pred));
566 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
573 * * new datum is not the same size as the old. * We have to
574 * delete the old entry and insert the new * one. Note that
575 * this may cause a split here!
578 ItemPointerData oldtid;
581 InsertIndexResult res;
583 /* delete old tuple */
584 ItemPointerSet(&oldtid, stk->gs_blk, stk->gs_child);
585 DirectFunctionCall2(gistdelete,
587 PointerGetDatum(&oldtid));
589 /* generate and insert new tuple */
591 isnull = (char *) palloc(r->rd_rel->relnatts);
592 MemSet(isnull, ' ', r->rd_rel->relnatts);
593 newtup = (IndexTuple) index_formtuple(tupDesc,
594 (Datum *) ¢ry.pred, isnull);
596 /* set pointer in new tuple to point to current child */
597 ItemPointerSet(&oldtid, blk, 1);
598 newtup->t_tid = oldtid;
600 /* inserting the new entry also adjust keys above */
601 res = gistentryinsert(r, stk, newtup, giststate);
603 /* in stack, set info to point to new tuple */
604 stk->gs_blk = ItemPointerGetBlockNumber(&(res->pointerData));
605 stk->gs_child = ItemPointerGetOffsetNumber(&(res->pointerData));
611 if (centry.pred != datum)
620 * gistSplit -- split a page in the tree.
623 static InsertIndexResult
624 gistSplit(Relation r,
627 IndexTuple itup, /* contains compressed entry */
628 GISTSTATE *giststate)
642 OffsetNumber leftoff,
646 BlockNumber bufblock;
647 GISTPageOpaque opaque;
649 InsertIndexResult res;
659 isnull = (char *) palloc(r->rd_rel->relnatts);
660 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
662 p = (Page) BufferGetPage(buffer);
663 opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
667 * The root of the tree is the first block in the relation. If we're
668 * about to split the root, we need to do some hocus-pocus to enforce
672 if (BufferGetBlockNumber(buffer) == GISTP_ROOT)
674 leftbuf = ReadBuffer(r, P_NEW);
675 GISTInitBuffer(leftbuf, opaque->flags);
676 lbknum = BufferGetBlockNumber(leftbuf);
677 left = (Page) BufferGetPage(leftbuf);
682 IncrBufferRefCount(buffer);
683 lbknum = BufferGetBlockNumber(buffer);
684 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
687 rightbuf = ReadBuffer(r, P_NEW);
688 GISTInitBuffer(rightbuf, opaque->flags);
689 rbknum = BufferGetBlockNumber(rightbuf);
690 right = (Page) BufferGetPage(rightbuf);
692 /* generate the item array */
693 maxoff = PageGetMaxOffsetNumber(p);
694 entryvec = (bytea *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(GISTENTRY));
695 decompvec = (bool *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(bool));
696 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
698 item_1 = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
699 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(entryvec))[i],
700 (((char *) item_1) + sizeof(IndexTupleData)),
702 IndexTupleSize(item_1) - sizeof(IndexTupleData), FALSE);
703 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[i].pred)
704 == (((char *) item_1) + sizeof(IndexTupleData)))
705 decompvec[i] = FALSE;
710 /* add the new datum as the last entry */
711 gistdentryinit(giststate, &(((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]),
712 (((char *) itup) + sizeof(IndexTupleData)),
713 (Relation) NULL, (Page) NULL,
714 (OffsetNumber) 0, tmpentry.bytes, FALSE);
715 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]).pred !=
716 (((char *) itup) + sizeof(IndexTupleData)))
717 decompvec[maxoff + 1] = TRUE;
719 decompvec[maxoff + 1] = FALSE;
721 VARATT_SIZEP(entryvec) = (maxoff + 2) * sizeof(GISTENTRY) + VARHDRSZ;
723 /* now let the user-defined picksplit function set up the split vector */
724 FunctionCall2(&giststate->picksplitFn,
725 PointerGetDatum(entryvec),
726 PointerGetDatum(&v));
728 /* compress ldatum and rdatum */
729 gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation) NULL,
730 (Page) NULL, (OffsetNumber) 0,
731 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
732 if (v.spl_ldatum != tmpentry.pred)
734 v.spl_ldatum = tmpentry.pred;
736 gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation) NULL,
737 (Page) NULL, (OffsetNumber) 0,
738 ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
739 if (v.spl_rdatum != tmpentry.pred)
741 v.spl_rdatum = tmpentry.pred;
743 /* clean up the entry vector: its preds need to be deleted, too */
744 for (i = FirstOffsetNumber; i <= maxoff + 1; i = OffsetNumberNext(i))
746 pfree(((GISTENTRY *) VARDATA(entryvec))[i].pred);
750 leftoff = rightoff = FirstOffsetNumber;
751 maxoff = PageGetMaxOffsetNumber(p);
752 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
754 itemid = PageGetItemId(p, i);
755 item = (IndexTuple) PageGetItem(p, itemid);
757 if (i == *(v.spl_left))
759 gistPageAddItem(giststate, r, left, (Item) item,
760 IndexTupleSize(item),
761 leftoff, LP_USED, &tmpdentry, &newtup);
762 leftoff = OffsetNumberNext(leftoff);
763 v.spl_left++; /* advance in left split vector */
765 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
766 pfree(tmpdentry.pred);
767 if ((IndexTuple) item != newtup)
772 gistPageAddItem(giststate, r, right, (Item) item,
773 IndexTupleSize(item),
774 rightoff, LP_USED, &tmpdentry, &newtup);
775 rightoff = OffsetNumberNext(rightoff);
776 v.spl_right++; /* advance in right split vector */
778 if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
779 pfree(tmpdentry.pred);
785 /* build an InsertIndexResult for this insertion */
786 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
788 /* now insert the new index tuple */
789 if (*(v.spl_left) != FirstOffsetNumber)
791 gistPageAddItem(giststate, r, left, (Item) itup,
792 IndexTupleSize(itup),
793 leftoff, LP_USED, &tmpdentry, &newtup);
794 leftoff = OffsetNumberNext(leftoff);
795 ItemPointerSet(&(res->pointerData), lbknum, leftoff);
797 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
798 pfree(tmpdentry.pred);
804 gistPageAddItem(giststate, r, right, (Item) itup,
805 IndexTupleSize(itup),
806 rightoff, LP_USED, &tmpdentry, &newtup);
807 rightoff = OffsetNumberNext(rightoff);
808 ItemPointerSet(&(res->pointerData), rbknum, rightoff);
810 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
811 pfree(tmpdentry.pred);
816 if ((bufblock = BufferGetBlockNumber(buffer)) != GISTP_ROOT)
817 PageRestoreTempPage(left, p);
818 WriteBuffer(leftbuf);
819 WriteBuffer(rightbuf);
822 * Okay, the page is split. We have three things left to do:
824 * 1) Adjust any active scans on this index to cope with changes we
825 * introduced in its structure by splitting this page.
827 * 2) "Tighten" the bounding box of the pointer to the left page in the
828 * parent node in the tree, if any. Since we moved a bunch of stuff
829 * off the left page, we expect it to get smaller. This happens in
830 * the internal insertion routine.
832 * 3) Insert a pointer to the right page in the parent. This may cause
833 * the parent to split. If it does, we need to repeat steps one and
834 * two for each split node in the tree.
837 /* adjust active scans */
838 gistadjscans(r, GISTOP_SPLIT, bufblock, FirstOffsetNumber);
842 ltup = (IndexTuple) index_formtuple(tupDesc,
843 (Datum *) &(v.spl_ldatum), isnull);
844 rtup = (IndexTuple) index_formtuple(tupDesc,
845 (Datum *) &(v.spl_rdatum), isnull);
848 /* set pointers to new child pages in the internal index tuples */
849 ItemPointerSet(&(ltup->t_tid), lbknum, 1);
850 ItemPointerSet(&(rtup->t_tid), rbknum, 1);
852 gistintinsert(r, stack, ltup, rtup, giststate);
861 ** After a split, we need to overwrite the old entry's key in the parent,
862 ** and install install an entry for the new key into the parent.
865 gistintinsert(Relation r,
867 IndexTuple ltup, /* new version of entry for old page */
868 IndexTuple rtup, /* entry for new page */
869 GISTSTATE *giststate)
871 ItemPointerData ltid;
873 if (stk == (GISTSTACK *) NULL)
875 gistnewroot(giststate, r, ltup, rtup);
879 /* remove old left pointer, insert the 2 new entries */
880 ItemPointerSet(<id, stk->gs_blk, stk->gs_child);
881 DirectFunctionCall2(gistdelete,
883 PointerGetDatum(<id));
884 gistentryinserttwo(r, stk, ltup, rtup, giststate);
889 ** Insert two entries onto one page, handling a split for either one!
892 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
893 IndexTuple rtup, GISTSTATE *giststate)
897 InsertIndexResult res;
901 b = ReadBuffer(r, stk->gs_blk);
902 p = BufferGetPage(b);
904 if (gistnospace(p, ltup))
906 res = gistSplit(r, b, stk->gs_parent, ltup, giststate);
907 WriteBuffer(b); /* don't forget to release buffer! -
910 gistdoinsert(r, rtup, giststate);
914 gistPageAddItem(giststate, r, p, (Item) ltup,
915 IndexTupleSize(ltup), InvalidOffsetNumber,
916 LP_USED, &tmpentry, &newtup);
918 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
919 tmpentry.bytes, giststate);
921 if (tmpentry.pred != (((char *) ltup) + sizeof(IndexTupleData)))
922 pfree(tmpentry.pred);
925 gistentryinsert(r, stk, rtup, giststate);
931 ** Insert an entry onto a page
933 static InsertIndexResult
934 gistentryinsert(Relation r, GISTSTACK *stk, IndexTuple tup,
935 GISTSTATE *giststate)
939 InsertIndexResult res;
944 b = ReadBuffer(r, stk->gs_blk);
945 p = BufferGetPage(b);
947 if (gistnospace(p, tup))
949 res = gistSplit(r, b, stk->gs_parent, tup, giststate);
950 WriteBuffer(b); /* don't forget to release buffer! -
956 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
957 off = gistPageAddItem(giststate, r, p, (Item) tup, IndexTupleSize(tup),
958 InvalidOffsetNumber, LP_USED, &tmpentry, &newtup);
960 ItemPointerSet(&(res->pointerData), stk->gs_blk, off);
961 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
962 tmpentry.bytes, giststate);
964 if (tmpentry.pred != (((char *) tup) + sizeof(IndexTupleData)))
965 pfree(tmpentry.pred);
974 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt, IndexTuple rt)
981 b = ReadBuffer(r, GISTP_ROOT);
982 GISTInitBuffer(b, 0);
983 p = BufferGetPage(b);
984 gistPageAddItem(giststate, r, p, (Item) lt, IndexTupleSize(lt),
986 LP_USED, &tmpentry, &newtup);
988 if (tmpentry.pred != (((char *) lt) + sizeof(IndexTupleData)))
989 pfree(tmpentry.pred);
992 gistPageAddItem(giststate, r, p, (Item) rt, IndexTupleSize(rt),
993 OffsetNumberNext(FirstOffsetNumber), LP_USED,
996 if (tmpentry.pred != (((char *) rt) + sizeof(IndexTupleData)))
997 pfree(tmpentry.pred);
1004 GISTInitBuffer(Buffer b, uint32 f)
1006 GISTPageOpaque opaque;
1010 pageSize = BufferGetPageSize(b);
1012 page = BufferGetPage(b);
1013 MemSet(page, 0, (int) pageSize);
1014 PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
1016 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1022 ** find entry with lowest penalty
1025 gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
1026 GISTSTATE *giststate)
1028 OffsetNumber maxoff;
1040 idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
1041 id = ((char *) it) + sizeof(IndexTupleData);
1042 maxoff = PageGetMaxOffsetNumber(p);
1046 gistdentryinit(giststate, &identry, id, (Relation) NULL, (Page) NULL,
1047 (OffsetNumber) 0, idsize, FALSE);
1049 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1051 datum = (char *) PageGetItem(p, PageGetItemId(p, i));
1052 size = IndexTupleSize(datum) - sizeof(IndexTupleData);
1053 datum += sizeof(IndexTupleData);
1054 gistdentryinit(giststate, &entry, datum, r, p, i, size, FALSE);
1055 FunctionCall3(&giststate->penaltyFn,
1056 PointerGetDatum(&entry),
1057 PointerGetDatum(&identry),
1058 PointerGetDatum(&usize));
1059 if (which_grow < 0 || usize < which_grow)
1063 if (which_grow == 0)
1066 if (entry.pred != datum)
1069 if (identry.pred != id)
1070 pfree(identry.pred);
1076 gistnospace(Page p, IndexTuple it)
1078 return PageGetFreeSpace(p) < IndexTupleSize(it);
1082 gistfreestack(GISTSTACK *s)
1086 while (s != (GISTSTACK *) NULL)
1096 ** remove an entry from a page
1099 gistdelete(PG_FUNCTION_ARGS)
1101 Relation r = (Relation) PG_GETARG_POINTER(0);
1102 ItemPointer tid = (ItemPointer) PG_GETARG_POINTER(1);
1104 OffsetNumber offnum;
1109 * Notes in ExecUtils:ExecOpenIndices() Also note that only vacuum
1110 * deletes index tuples now...
1112 * RelationSetLockForWrite(r);
1115 blkno = ItemPointerGetBlockNumber(tid);
1116 offnum = ItemPointerGetOffsetNumber(tid);
1118 /* adjust any scans that will be affected by this deletion */
1119 gistadjscans(r, GISTOP_DEL, blkno, offnum);
1121 /* delete the index tuple */
1122 buf = ReadBuffer(r, blkno);
1123 page = BufferGetPage(buf);
1125 PageIndexTupleDelete(page, offnum);
1133 initGISTstate(GISTSTATE *giststate, Relation index)
1135 RegProcedure consistent_proc,
1139 RegProcedure penalty_proc,
1143 Form_pg_index itupform;
1145 consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
1146 union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
1147 compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
1148 decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
1149 penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
1150 picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
1151 equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1152 fmgr_info(consistent_proc, &giststate->consistentFn);
1153 fmgr_info(union_proc, &giststate->unionFn);
1154 fmgr_info(compress_proc, &giststate->compressFn);
1155 fmgr_info(decompress_proc, &giststate->decompressFn);
1156 fmgr_info(penalty_proc, &giststate->penaltyFn);
1157 fmgr_info(picksplit_proc, &giststate->picksplitFn);
1158 fmgr_info(equal_proc, &giststate->equalFn);
1160 /* see if key type is different from type of attribute being indexed */
1161 htup = SearchSysCacheTuple(INDEXRELID,
1162 ObjectIdGetDatum(RelationGetRelid(index)),
1164 itupform = (Form_pg_index) GETSTRUCT(htup);
1165 if (!HeapTupleIsValid(htup))
1166 elog(ERROR, "initGISTstate: index %u not found",
1167 RelationGetRelid(index));
1168 giststate->haskeytype = itupform->indhaskeytype;
1169 if (giststate->haskeytype)
1171 /* key type is different -- is it byval? */
1172 htup = SearchSysCacheTuple(ATTNUM,
1173 ObjectIdGetDatum(itupform->indexrelid),
1174 UInt16GetDatum(FirstOffsetNumber),
1176 if (!HeapTupleIsValid(htup))
1178 elog(ERROR, "initGISTstate: no attribute tuple %u %d",
1179 itupform->indexrelid, FirstOffsetNumber);
1182 giststate->keytypbyval = (((Form_pg_attribute) htup)->attbyval);
1185 giststate->keytypbyval = FALSE;
1191 ** Given an IndexTuple to be inserted on a page, this routine replaces
1192 ** the key with another key, which may involve generating a new IndexTuple
1193 ** if the sizes don't match
1196 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1198 char *datum = (((char *) t) + sizeof(IndexTupleData));
1200 /* if new entry fits in index tuple, copy it in */
1201 if ((Size) entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData))
1203 memcpy(datum, entry.pred, entry.bytes);
1204 /* clear out old size */
1205 t->t_info &= 0xe000;
1206 /* or in new size */
1207 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1213 /* generate a new index tuple for the compressed entry */
1214 TupleDesc tupDesc = r->rd_att;
1219 isnull = (char *) palloc(r->rd_rel->relnatts);
1220 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
1221 isnull[blank] = ' ';
1222 newtup = (IndexTuple) index_formtuple(tupDesc,
1223 (Datum *) &(entry.pred),
1225 newtup->t_tid = t->t_tid;
1233 ** initialize a GiST entry with a decompressed version of pred
1236 gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1237 Page pg, OffsetNumber o, int b, bool l)
1241 gistentryinit(*e, pr, r, pg, o, b, l);
1242 if (giststate->haskeytype)
1245 DatumGetPointer(FunctionCall1(&giststate->decompressFn,
1246 PointerGetDatum(e)));
1247 gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1256 ** initialize a GiST entry with a compressed version of pred
1259 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1260 Page pg, OffsetNumber o, int b, bool l)
1264 gistentryinit(*e, pr, r, pg, o, b, l);
1265 if (giststate->haskeytype)
1268 DatumGetPointer(FunctionCall1(&giststate->compressFn,
1269 PointerGetDatum(e)));
1270 gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
1282 ** sloppy debugging support routine, requires recompilation with appropriate
1283 ** "out" method for the index keys. Could be fixed to find that info
1284 ** in the catalogs...
1287 _gistdump(Relation r)
1291 OffsetNumber offnum,
1294 BlockNumber nblocks;
1297 BlockNumber itblkno;
1298 OffsetNumber itoffno;
1302 nblocks = RelationGetNumberOfBlocks(r);
1303 for (blkno = 0; blkno < nblocks; blkno++)
1305 buf = ReadBuffer(r, blkno);
1306 page = BufferGetPage(buf);
1307 po = (GISTPageOpaque) PageGetSpecialPointer(page);
1308 maxoff = PageGetMaxOffsetNumber(page);
1309 printf("Page %d maxoff %d <%s>\n", blkno, maxoff,
1310 (po->flags & F_LEAF ? "LEAF" : "INTERNAL"));
1312 if (PageIsEmpty(page))
1318 for (offnum = FirstOffsetNumber;
1320 offnum = OffsetNumberNext(offnum))
1322 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
1323 itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1324 itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid));
1325 datum = ((char *) itup);
1326 datum += sizeof(IndexTupleData);
1327 /* get out function for type of key, and out it! */
1328 itkey = (char *) int_range_out((INTRANGE *) datum);
1329 /* itkey = " unable to print"; */
1330 printf("\t[%d] size %d heap <%d,%d> key:%s\n",
1331 offnum, IndexTupleSize(itup), itblkno, itoffno, itkey);
1340 int_range_out(INTRANGE *r)
1346 result = (char *) palloc(80);
1347 snprintf(result, 80, "[%d,%d): %d", r->lower, r->upper, r->flag);
1352 #endif /* defined GISTDEBUG */
1356 gist_redo(XLogRecPtr lsn, XLogRecord *record)
1358 elog(STOP, "gist_redo: unimplemented");
1362 gist_undo(XLogRecPtr lsn, XLogRecord *record)
1364 elog(STOP, "gist_undo: unimplemented");
1368 gist_desc(char *buf, uint8 xl_info, char* rec)