1 /*-------------------------------------------------------------------------
4 * interface routines for the postgres GiST index access method.
9 * $Header: /cvsroot/pgsql/src/backend/access/gist/gist.c,v 1.74 2001/05/14 21:53:16 momjian 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"
26 #include "access/xlogutils.h"
32 /* non-export function prototypes */
33 static void gistdoinsert(Relation r,
35 InsertIndexResult *res,
36 GISTSTATE *GISTstate);
37 static int gistlayerinsert(Relation r, BlockNumber blkno,
40 InsertIndexResult *res,
41 GISTSTATE *giststate);
42 static OffsetNumber gistwritebuffer(Relation r,
47 GISTSTATE *giststate);
48 static int gistnospace(Page page,
49 IndexTuple *itvec, int len);
50 static IndexTuple *gistreadbuffer(Relation r,
51 Buffer buffer, int *len);
52 static IndexTuple *gistjoinvector(
53 IndexTuple *itvec, int *len,
54 IndexTuple *additvec, int addlen);
55 static IndexTuple gistunion(Relation r, IndexTuple *itvec,
56 int len, GISTSTATE *giststate);
57 static IndexTuple gistgetadjusted(Relation r,
60 GISTSTATE *giststate);
61 static IndexTuple *gistSplit(Relation r,
66 InsertIndexResult *res);
67 static void gistnewroot(GISTSTATE *giststate, Relation r,
68 IndexTuple *itup, int len);
69 static void GISTInitBuffer(Buffer b, uint32 f);
70 static OffsetNumber gistchoose(Relation r, Page p,
72 GISTSTATE *giststate);
73 static IndexTuple gist_tuple_replacekey(Relation r,
74 GISTENTRY entry, IndexTuple t);
75 static void gistcentryinit(GISTSTATE *giststate,
76 GISTENTRY *e, char *pr,
78 OffsetNumber o, int b, bool l);
82 static void gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff);
87 * routine to build an index. Basically calls insert over and over
90 gistbuild(PG_FUNCTION_ARGS)
92 Relation heap = (Relation) PG_GETARG_POINTER(0);
93 Relation index = (Relation) PG_GETARG_POINTER(1);
94 IndexInfo *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
95 Node *oldPred = (Node *) PG_GETARG_POINTER(3);
98 IndexStrategy istrat = (IndexStrategy) PG_GETARG_POINTER(4);
106 Datum attdata[INDEX_MAX_KEYS];
107 char nulls[INDEX_MAX_KEYS];
110 Node *pred = indexInfo->ii_Predicate;
112 #ifndef OMIT_PARTIAL_INDEX
113 TupleTable tupleTable;
114 TupleTableSlot *slot;
117 ExprContext *econtext;
120 Buffer buffer = InvalidBuffer;
124 /* no locking is needed */
126 initGISTstate(&giststate, index);
129 * We expect to be called exactly once for any index relation. If
130 * that's not the case, big trouble's what we have.
132 if (oldPred == NULL && RelationGetNumberOfBlocks(index) != 0)
133 elog(ERROR, "%s already contains data", RelationGetRelationName(index));
135 /* initialize the root page (if this is a new index) */
138 buffer = ReadBuffer(index, P_NEW);
139 GISTInitBuffer(buffer, F_LEAF);
143 /* get tuple descriptors for heap and index relations */
144 htupdesc = RelationGetDescr(heap);
145 itupdesc = RelationGetDescr(index);
148 * If this is a predicate (partial) index, we will need to evaluate
149 * the predicate using ExecQual, which requires the current tuple to
150 * be in a slot of a TupleTable. In addition, ExecQual must have an
151 * ExprContext referring to that slot. Here, we initialize dummy
152 * TupleTable and ExprContext objects for this purpose. --Nels, Feb 92
154 * We construct the ExprContext anyway since we need a per-tuple
155 * temporary memory context for function evaluation -- tgl July 00
157 #ifndef OMIT_PARTIAL_INDEX
158 if (pred != NULL || oldPred != NULL)
160 tupleTable = ExecCreateTupleTable(1);
161 slot = ExecAllocTableSlot(tupleTable);
162 ExecSetSlotDescriptor(slot, htupdesc, false);
169 econtext = MakeExprContext(slot, TransactionCommandContext);
171 econtext = MakeExprContext(NULL, TransactionCommandContext);
172 #endif /* OMIT_PARTIAL_INDEX */
174 /* build the index */
175 nhtups = nitups = 0.0;
177 compvec = (bool *) palloc(sizeof(bool) * indexInfo->ii_NumIndexAttrs);
179 /* start a heap scan */
180 hscan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);
182 while (HeapTupleIsValid(htup = heap_getnext(hscan, 0)))
184 MemoryContextReset(econtext->ecxt_per_tuple_memory);
188 #ifndef OMIT_PARTIAL_INDEX
191 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
192 * this tuple if it was already in the existing partial index
197 if (ExecQual((List *) oldPred, econtext, false))
205 * Skip this tuple if it doesn't satisfy the partial-index
211 if (!ExecQual((List *) pred, econtext, false))
214 #endif /* OMIT_PARTIAL_INDEX */
219 * For the current heap tuple, extract all the attributes we use
220 * in this index, and note which are null.
222 FormIndexDatum(indexInfo,
225 econtext->ecxt_per_tuple_memory,
229 /* immediately compress keys to normalize */
230 for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
232 gistcentryinit(&giststate, &tmpcentry, (char *) attdata[i],
233 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
234 -1 /* size is currently bogus */ , TRUE);
235 if (attdata[i] != (Datum) tmpcentry.pred &&
236 !(giststate.keytypbyval))
240 attdata[i] = (Datum) tmpcentry.pred;
243 /* form an index tuple and point it at the heap tuple */
244 itup = index_formtuple(itupdesc, attdata, nulls);
245 itup->t_tid = htup->t_self;
248 * Since we already have the index relation locked, we call
249 * gistdoinsert directly. Normal access method calls dispatch
250 * through gistinsert, which locks the relation for write. This
251 * is the right thing to do if you're inserting single tups, but
252 * not when you're initializing the whole index at once.
255 gistdoinsert(index, itup, NULL, &giststate);
257 for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
259 pfree(DatumGetPointer(attdata[i]));
264 /* okay, all heap tuples are indexed */
269 #ifndef OMIT_PARTIAL_INDEX
270 if (pred != NULL || oldPred != NULL)
271 ExecDropTupleTable(tupleTable, true);
272 #endif /* OMIT_PARTIAL_INDEX */
273 FreeExprContext(econtext);
276 * Since we just counted the tuples in the heap, we update its stats
277 * in pg_class to guarantee that the planner takes advantage of the
278 * index we just created. But, only update statistics during normal
279 * index definitions, not for indices on system catalogs created
280 * during bootstrap processing. We must close the relations before
281 * updating statistics to guarantee that the relcache entries are
282 * flushed when we increment the command counter in UpdateStats(). But
283 * we do not release any locks on the relations; those will be held
284 * until end of transaction.
286 if (IsNormalProcessingMode())
288 Oid hrelid = RelationGetRelid(heap);
289 Oid irelid = RelationGetRelid(index);
291 heap_close(heap, NoLock);
293 UpdateStats(hrelid, nhtups);
294 UpdateStats(irelid, nitups);
297 if (nitups == nhtups)
299 UpdateIndexPredicate(irelid, oldPred, pred);
304 gist_dumptree(index, 0, GISTP_ROOT, 0);
311 * gistinsert -- wrapper for GiST tuple insertion.
313 * This is the public interface routine for tuple insertion in GiSTs.
314 * It doesn't do any work; just locks the relation and passes the buck.
317 gistinsert(PG_FUNCTION_ARGS)
319 Relation r = (Relation) PG_GETARG_POINTER(0);
320 Datum *datum = (Datum *) PG_GETARG_POINTER(1);
321 char *nulls = (char *) PG_GETARG_POINTER(2);
322 ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3);
325 Relation heapRel = (Relation) PG_GETARG_POINTER(4);
328 InsertIndexResult res;
335 initGISTstate(&giststate, r);
337 /* immediately compress keys to normalize */
338 compvec = (bool *) palloc(sizeof(bool) * r->rd_att->natts);
339 for (i = 0; i < r->rd_att->natts; i++)
341 gistcentryinit(&giststate, &tmpentry, (char *) datum[i],
342 (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
343 -1 /* size is currently bogus */ , TRUE);
344 if (datum[i] != (Datum) tmpentry.pred && !(giststate.keytypbyval))
348 datum[i] = (Datum) tmpentry.pred;
350 itup = index_formtuple(RelationGetDescr(r), datum, nulls);
351 itup->t_tid = *ht_ctid;
354 * Notes in ExecUtils:ExecOpenIndices()
356 * RelationSetLockForWrite(r);
359 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
360 gistdoinsert(r, itup, &res, &giststate);
361 for (i = 0; i < r->rd_att->natts; i++)
362 if (compvec[i] == TRUE)
363 pfree((char *) datum[i]);
367 PG_RETURN_POINTER(res);
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;
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, tmpcentry, itup);
402 retval = PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
403 offsetNumber, flags);
404 if (retval == InvalidOffsetNumber)
405 elog(ERROR, "gist: failed to add index item to %s",
406 RelationGetRelationName(r));
408 if (tmpcentry.pred && tmpcentry.pred != dentry->pred
409 && tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
410 pfree(tmpcentry.pred);
415 gistdoinsert(Relation r,
417 InsertIndexResult *res,
418 GISTSTATE *giststate)
425 instup = (IndexTuple *) palloc(sizeof(IndexTuple));
426 instup[0] = (IndexTuple) palloc(IndexTupleSize(itup));
427 memcpy(instup[0], itup, IndexTupleSize(itup));
429 ret = gistlayerinsert(r, GISTP_ROOT, &instup, &len, res, giststate);
431 gistnewroot(giststate, r, instup, len);
433 for (i = 0; i < len; i++)
439 gistlayerinsert(Relation r, BlockNumber blkno,
440 IndexTuple **itup, /* in - out, has compressed entry */
441 int *len, /* in - out */
442 InsertIndexResult *res, /* out */
443 GISTSTATE *giststate)
449 GISTPageOpaque opaque;
451 buffer = ReadBuffer(r, blkno);
452 page = (Page) BufferGetPage(buffer);
453 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
455 if (!(opaque->flags & F_LEAF))
457 /* internal page, so we must walk on tree */
458 /* len IS equial 1 */
461 ItemPointerData oldtid;
464 child = gistchoose(r, page, *(*itup), giststate);
465 iid = PageGetItemId(page, child);
466 oldtup = (IndexTuple) PageGetItem(page, iid);
467 nblkno = ItemPointerGetBlockNumber(&(oldtup->t_tid));
470 * After this call: 1. if child page was splited, then itup
471 * contains keys for each page 2. if child page wasn't splited,
472 * then itup contains additional for adjustement of current key
474 ret = gistlayerinsert(r, nblkno, itup, len, res, giststate);
476 /* nothing inserted in child */
477 if (!(ret & INSERTED))
479 ReleaseBuffer(buffer);
483 /* child does not splited */
484 if (!(ret & SPLITED))
486 IndexTuple newtup = gistgetadjusted(r, oldtup, (*itup)[0], giststate);
490 /* not need to update key */
491 ReleaseBuffer(buffer);
495 pfree((*itup)[0]); /* !!! */
499 /* key is modified, so old version must be deleted */
500 ItemPointerSet(&oldtid, blkno, child);
501 DirectFunctionCall2(gistdelete,
503 PointerGetDatum(&oldtid));
508 if (gistnospace(page, (*itup), *len))
510 /* no space for insertion */
515 itvec = gistreadbuffer(r, buffer, &tlen);
516 itvec = gistjoinvector(itvec, &tlen, (*itup), *len);
518 (*itup) = gistSplit(r, buffer, itvec, &tlen, giststate,
519 (opaque->flags & F_LEAF) ? res : NULL); /* res only for
520 * inserting in leaf */
521 ReleaseBuffer(buffer);
523 *len = tlen; /* now tlen >= 2 */
531 off = (PageIsEmpty(page)) ?
534 OffsetNumberNext(PageGetMaxOffsetNumber(page));
535 l = gistwritebuffer(r, page, (*itup), *len, off, giststate);
539 * set res if insert into leaf page, in this case, len = 1 always
541 if (res && (opaque->flags & F_LEAF))
542 ItemPointerSet(&((*res)->pointerData), blkno, l);
545 { /* previos insert ret & SPLITED != 0 */
549 * child was splited, so we must form union for insertion in
552 IndexTuple newtup = gistunion(r, (*itup), *len, giststate);
554 for (i = 0; i < *len; i++)
565 * Write itup vector to page, has no control of free space
568 gistwritebuffer(Relation r, Page page, IndexTuple *itup,
569 int len, OffsetNumber off, GISTSTATE *giststate)
571 OffsetNumber l = InvalidOffsetNumber;
576 for (i = 0; i < len; i++)
578 l = gistPageAddItem(giststate, r, page,
579 (Item) itup[i], IndexTupleSize(itup[i]),
580 off, LP_USED, &tmpdentry, &newtup);
581 off = OffsetNumberNext(off);
582 if (tmpdentry.pred != (((char *) itup[i]) + sizeof(IndexTupleData)) && tmpdentry.pred)
583 pfree(tmpdentry.pred);
584 if (itup[i] != newtup)
591 * Check space for itup vector on page
594 gistnospace(Page page, IndexTuple *itvec, int len)
599 for (i = 0; i < len; i++)
600 size += IndexTupleSize(itvec[i]) + 4; /* ??? */
602 return (PageGetFreeSpace(page) < size);
606 * Read buffer into itup vector
609 gistreadbuffer(Relation r, Buffer buffer, int *len /* out */ )
614 Page p = (Page) BufferGetPage(buffer);
617 maxoff = PageGetMaxOffsetNumber(p);
618 itvec = palloc(sizeof(IndexTuple) * maxoff);
619 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
620 itvec[(*len)++] = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
626 * join two vectors into one
629 gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
631 itvec = (IndexTuple *) repalloc((void *) itvec, sizeof(IndexTuple) * ((*len) + addlen));
632 memmove(&itvec[*len], additvec, sizeof(IndexTuple) * addlen);
638 * return union of itup vector
641 gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
651 evec = (bytea *) palloc(len * sizeof(GISTENTRY) + VARHDRSZ);
652 VARATT_SIZEP(evec) = len * sizeof(GISTENTRY) + VARHDRSZ;
654 for (i = 0; i < len; i++)
655 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[i],
656 (char *) itvec[i] + sizeof(IndexTupleData),
657 (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
658 IndexTupleSize((IndexTuple) itvec[i]) - sizeof(IndexTupleData), FALSE);
661 DatumGetPointer(FunctionCall2(&giststate->unionFn,
662 PointerGetDatum(evec),
663 PointerGetDatum(&datumsize)));
665 for (i = 0; i < len; i++)
666 if (((GISTENTRY *) VARDATA(evec))[i].pred &&
667 ((GISTENTRY *) VARDATA(evec))[i].pred !=
668 ((char *) (itvec[i]) + sizeof(IndexTupleData)))
669 pfree(((GISTENTRY *) VARDATA(evec))[i].pred);
673 gistcentryinit(giststate, ¢ry, datum,
674 (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
677 isnull = (centry.pred) ? ' ' : 'n';
678 newtup = (IndexTuple) index_formtuple(r->rd_att, (Datum *) ¢ry.pred, &isnull);
679 if (centry.pred != datum)
686 * Forms union of oldtup and addtup, if union == oldtup then return NULL
689 gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
699 IndexTuple newtup = NULL;
701 evec = (bytea *) palloc(2 * sizeof(GISTENTRY) + VARHDRSZ);
702 VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
704 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[0],
705 (char *) oldtup + sizeof(IndexTupleData), (Relation) NULL,
706 (Page) NULL, (OffsetNumber) 0,
707 IndexTupleSize((IndexTuple) oldtup) - sizeof(IndexTupleData), FALSE);
708 ev0p = &((GISTENTRY *) VARDATA(evec))[0];
710 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[1],
711 (char *) addtup + sizeof(IndexTupleData), (Relation) NULL,
712 (Page) NULL, (OffsetNumber) 0,
713 IndexTupleSize((IndexTuple) addtup) - sizeof(IndexTupleData), FALSE);
714 ev1p = &((GISTENTRY *) VARDATA(evec))[1];
717 DatumGetPointer(FunctionCall2(&giststate->unionFn,
718 PointerGetDatum(evec),
719 PointerGetDatum(&datumsize)));
721 if (!(ev0p->pred && ev1p->pred))
722 result = (ev0p->pred == NULL && ev1p->pred == NULL);
725 FunctionCall3(&giststate->equalFn,
726 PointerGetDatum(ev0p->pred),
727 PointerGetDatum(datum),
728 PointerGetDatum(&result));
733 /* not need to update key */
738 gistcentryinit(giststate, ¢ry, datum, ev0p->rel, ev0p->page,
739 ev0p->offset, datumsize, FALSE);
741 isnull = (centry.pred) ? ' ' : 'n';
742 newtup = (IndexTuple) index_formtuple(r->rd_att, (Datum *) ¢ry.pred, &isnull);
743 newtup->t_tid = oldtup->t_tid;
744 if (centry.pred != datum)
749 ev0p->pred != (char *) oldtup + sizeof(IndexTupleData))
752 ev1p->pred != (char *) addtup + sizeof(IndexTupleData))
760 * gistSplit -- split a page in the tree.
763 gistSplit(Relation r,
765 IndexTuple *itup, /* contains compressed entry */
767 GISTSTATE *giststate,
768 InsertIndexResult *res)
775 OffsetNumber *spl_left,
784 GISTPageOpaque opaque;
793 p = (Page) BufferGetPage(buffer);
794 opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
798 * The root of the tree is the first block in the relation. If we're
799 * about to split the root, we need to do some hocus-pocus to enforce
803 if (BufferGetBlockNumber(buffer) == GISTP_ROOT)
805 leftbuf = ReadBuffer(r, P_NEW);
806 GISTInitBuffer(leftbuf, opaque->flags);
807 lbknum = BufferGetBlockNumber(leftbuf);
808 left = (Page) BufferGetPage(leftbuf);
813 IncrBufferRefCount(buffer);
814 lbknum = BufferGetBlockNumber(buffer);
815 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
818 rightbuf = ReadBuffer(r, P_NEW);
819 GISTInitBuffer(rightbuf, opaque->flags);
820 rbknum = BufferGetBlockNumber(rightbuf);
821 right = (Page) BufferGetPage(rightbuf);
823 /* generate the item array */
824 entryvec = (bytea *) palloc(VARHDRSZ + (*len + 1) * sizeof(GISTENTRY));
825 decompvec = (bool *) palloc(VARHDRSZ + (*len + 1) * sizeof(bool));
826 VARATT_SIZEP(entryvec) = (*len + 1) * sizeof(GISTENTRY) + VARHDRSZ;
827 for (i = 1; i <= *len; i++)
829 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(entryvec))[i],
830 (((char *) itup[i - 1]) + sizeof(IndexTupleData)),
832 IndexTupleSize(itup[i - 1]) - sizeof(IndexTupleData), FALSE);
833 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[i].pred)
834 == (((char *) itup[i - 1]) + sizeof(IndexTupleData)))
835 decompvec[i] = FALSE;
840 /* now let the user-defined picksplit function set up the split vector */
841 FunctionCall2(&giststate->picksplitFn,
842 PointerGetDatum(entryvec),
843 PointerGetDatum(&v));
845 /* clean up the entry vector: its preds need to be deleted, too */
846 for (i = 1; i <= *len; i++)
847 if (decompvec[i] && ((GISTENTRY *) VARDATA(entryvec))[i].pred)
848 pfree(((GISTENTRY *) VARDATA(entryvec))[i].pred);
852 spl_left = v.spl_left;
853 spl_right = v.spl_right;
855 /* form left and right vector */
856 lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nleft);
857 rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nright);
858 leftoff = rightoff = 0;
859 for (i = 1; i <= *len; i++)
861 if (i == *(spl_left) || (i == *len && *(spl_left) != FirstOffsetNumber))
863 lvectup[leftoff++] = itup[i - 1];
868 rvectup[rightoff++] = itup[i - 1];
873 /* write on disk (may be need another split) */
874 if (gistnospace(right, rvectup, v.spl_nright))
877 newtup = gistSplit(r, rightbuf, rvectup, &nlen, giststate,
878 (res && rvectup[nlen - 1] == itup[*len - 1]) ? res : NULL);
879 ReleaseBuffer(rightbuf);
885 l = gistwritebuffer(r, right, rvectup, v.spl_nright, FirstOffsetNumber, giststate);
886 WriteBuffer(rightbuf);
889 ItemPointerSet(&((*res)->pointerData), rbknum, l);
890 gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation) NULL,
891 (Page) NULL, (OffsetNumber) 0,
893 if (v.spl_rdatum != tmpentry.pred)
895 v.spl_rdatum = tmpentry.pred;
898 newtup = (IndexTuple *) palloc(sizeof(IndexTuple) * 1);
899 isnull = (v.spl_rdatum) ? ' ' : 'n';
900 newtup[0] = (IndexTuple) index_formtuple(r->rd_att, (Datum *) &(v.spl_rdatum), &isnull);
901 ItemPointerSet(&(newtup[0]->t_tid), rbknum, 1);
904 if (gistnospace(left, lvectup, v.spl_nleft))
906 int llen = v.spl_nleft;
909 lntup = gistSplit(r, leftbuf, lvectup, &llen, giststate,
910 (res && lvectup[llen - 1] == itup[*len - 1]) ? res : NULL);
911 ReleaseBuffer(leftbuf);
913 newtup = gistjoinvector(newtup, &nlen, lntup, llen);
920 l = gistwritebuffer(r, left, lvectup, v.spl_nleft, FirstOffsetNumber, giststate);
921 if (BufferGetBlockNumber(buffer) != GISTP_ROOT)
922 PageRestoreTempPage(left, p);
924 WriteBuffer(leftbuf);
927 ItemPointerSet(&((*res)->pointerData), lbknum, l);
928 gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation) NULL,
929 (Page) NULL, (OffsetNumber) 0,
931 if (v.spl_ldatum != tmpentry.pred)
933 v.spl_ldatum = tmpentry.pred;
936 newtup = (IndexTuple *) repalloc((void *) newtup, sizeof(IndexTuple) * nlen);
937 isnull = (v.spl_ldatum) ? ' ' : 'n';
938 newtup[nlen - 1] = (IndexTuple) index_formtuple(r->rd_att, (Datum *) &(v.spl_ldatum), &isnull);
939 ItemPointerSet(&(newtup[nlen - 1]->t_tid), lbknum, 1);
943 /* adjust active scans */
944 gistadjscans(r, GISTOP_SPLIT, BufferGetBlockNumber(buffer), FirstOffsetNumber);
957 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple *itup, int len)
962 b = ReadBuffer(r, GISTP_ROOT);
963 GISTInitBuffer(b, 0);
964 p = BufferGetPage(b);
966 gistwritebuffer(r, p, itup, len, FirstOffsetNumber, giststate);
971 GISTInitBuffer(Buffer b, uint32 f)
973 GISTPageOpaque opaque;
977 pageSize = BufferGetPageSize(b);
979 page = BufferGetPage(b);
980 MemSet(page, 0, (int) pageSize);
981 PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
983 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
989 ** find entry with lowest penalty
992 gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
993 GISTSTATE *giststate)
1007 idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
1008 id = ((char *) it) + sizeof(IndexTupleData);
1009 maxoff = PageGetMaxOffsetNumber(p);
1013 gistdentryinit(giststate, &identry, id, (Relation) NULL, (Page) NULL,
1014 (OffsetNumber) 0, idsize, FALSE);
1016 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1018 datum = (char *) PageGetItem(p, PageGetItemId(p, i));
1019 size = IndexTupleSize(datum) - sizeof(IndexTupleData);
1020 datum += sizeof(IndexTupleData);
1021 gistdentryinit(giststate, &entry, datum, r, p, i, size, FALSE);
1022 FunctionCall3(&giststate->penaltyFn,
1023 PointerGetDatum(&entry),
1024 PointerGetDatum(&identry),
1025 PointerGetDatum(&usize));
1026 if (which_grow < 0 || usize < which_grow)
1030 if (which_grow == 0)
1033 if (entry.pred && entry.pred != datum)
1036 if (identry.pred && identry.pred != id)
1037 pfree(identry.pred);
1043 gistfreestack(GISTSTACK *s)
1047 while (s != (GISTSTACK *) NULL)
1057 ** remove an entry from a page
1060 gistdelete(PG_FUNCTION_ARGS)
1062 Relation r = (Relation) PG_GETARG_POINTER(0);
1063 ItemPointer tid = (ItemPointer) PG_GETARG_POINTER(1);
1065 OffsetNumber offnum;
1070 * Notes in ExecUtils:ExecOpenIndices() Also note that only vacuum
1071 * deletes index tuples now...
1073 * RelationSetLockForWrite(r);
1076 blkno = ItemPointerGetBlockNumber(tid);
1077 offnum = ItemPointerGetOffsetNumber(tid);
1079 /* adjust any scans that will be affected by this deletion */
1080 gistadjscans(r, GISTOP_DEL, blkno, offnum);
1082 /* delete the index tuple */
1083 buf = ReadBuffer(r, blkno);
1084 page = BufferGetPage(buf);
1086 PageIndexTupleDelete(page, offnum);
1094 initGISTstate(GISTSTATE *giststate, Relation index)
1096 RegProcedure consistent_proc,
1100 RegProcedure penalty_proc,
1104 Form_pg_index itupform;
1107 consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
1108 union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
1109 compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
1110 decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
1111 penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
1112 picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
1113 equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1114 fmgr_info(consistent_proc, &giststate->consistentFn);
1115 fmgr_info(union_proc, &giststate->unionFn);
1116 fmgr_info(compress_proc, &giststate->compressFn);
1117 fmgr_info(decompress_proc, &giststate->decompressFn);
1118 fmgr_info(penalty_proc, &giststate->penaltyFn);
1119 fmgr_info(picksplit_proc, &giststate->picksplitFn);
1120 fmgr_info(equal_proc, &giststate->equalFn);
1122 /* see if key type is different from type of attribute being indexed */
1123 htup = SearchSysCache(INDEXRELID,
1124 ObjectIdGetDatum(RelationGetRelid(index)),
1126 if (!HeapTupleIsValid(htup))
1127 elog(ERROR, "initGISTstate: index %u not found",
1128 RelationGetRelid(index));
1129 itupform = (Form_pg_index) GETSTRUCT(htup);
1130 indexrelid = itupform->indexrelid;
1131 ReleaseSysCache(htup);
1133 if (giststate->haskeytype)
1135 /* key type is different -- is it byval? */
1136 htup = SearchSysCache(ATTNUM,
1137 ObjectIdGetDatum(indexrelid),
1138 UInt16GetDatum(FirstOffsetNumber),
1140 if (!HeapTupleIsValid(htup))
1141 elog(ERROR, "initGISTstate: no attribute tuple %u %d",
1142 indexrelid, FirstOffsetNumber);
1143 giststate->keytypbyval = (((Form_pg_attribute) htup)->attbyval);
1144 ReleaseSysCache(htup);
1147 giststate->keytypbyval = FALSE;
1152 ** Given an IndexTuple to be inserted on a page, this routine replaces
1153 ** the key with another key, which may involve generating a new IndexTuple
1154 ** if the sizes don't match
1157 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1159 char *datum = (((char *) t) + sizeof(IndexTupleData));
1161 /* if new entry fits in index tuple, copy it in */
1162 if ((Size) entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData) || (Size) entry.bytes == 0)
1164 memcpy(datum, entry.pred, entry.bytes);
1165 /* clear out old size */
1166 t->t_info &= ~INDEX_SIZE_MASK;
1167 /* or in new size */
1168 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1174 /* generate a new index tuple for the compressed entry */
1175 TupleDesc tupDesc = r->rd_att;
1179 isnull = (entry.pred) ? ' ' : 'n';
1180 newtup = (IndexTuple) index_formtuple(tupDesc,
1181 (Datum *) &(entry.pred),
1183 newtup->t_tid = t->t_tid;
1190 ** initialize a GiST entry with a decompressed version of pred
1193 gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1194 Page pg, OffsetNumber o, int b, bool l)
1198 gistentryinit(*e, pr, r, pg, o, b, l);
1199 if (giststate->haskeytype)
1202 DatumGetPointer(FunctionCall1(&giststate->decompressFn,
1203 PointerGetDatum(e)));
1204 gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1213 ** initialize a GiST entry with a compressed version of pred
1216 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1217 Page pg, OffsetNumber o, int b, bool l)
1221 gistentryinit(*e, pr, r, pg, o, b, l);
1222 if (giststate->haskeytype)
1225 DatumGetPointer(FunctionCall1(&giststate->compressFn,
1226 PointerGetDatum(e)));
1227 gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
1236 gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff)
1240 GISTPageOpaque opaque;
1248 pred = (char *) palloc(sizeof(char) * level + 1);
1249 MemSet(pred, '\t', level);
1252 buffer = ReadBuffer(r, blk);
1253 page = (Page) BufferGetPage(buffer);
1254 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1256 maxoff = PageGetMaxOffsetNumber(page);
1258 elog(NOTICE, "%sPage: %d %s blk: %d maxoff: %d free: %d", pred, coff, (opaque->flags & F_LEAF) ? "LEAF" : "INTE", (int) blk, (int) maxoff, PageGetFreeSpace(page));
1260 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1262 iid = PageGetItemId(page, i);
1263 which = (IndexTuple) PageGetItem(page, iid);
1264 cblk = ItemPointerGetBlockNumber(&(which->t_tid));
1266 elog(NOTICE, "%s Tuple. blk: %d size: %d", pred, (int) cblk, IndexTupleSize(which));
1269 if (!(opaque->flags & F_LEAF))
1270 gist_dumptree(r, level + 1, cblk, i);
1272 ReleaseBuffer(buffer);
1276 #endif /* defined GISTDEBUG */
1279 gist_redo(XLogRecPtr lsn, XLogRecord *record)
1281 elog(STOP, "gist_redo: unimplemented");
1285 gist_undo(XLogRecPtr lsn, XLogRecord *record)
1287 elog(STOP, "gist_undo: unimplemented");
1291 gist_desc(char *buf, uint8 xl_info, char *rec)