Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * gist.c
4 : : * interface routines for the postgres GiST index access method.
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/gist/gist.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : #include "postgres.h"
16 : :
17 : : #include "access/gist_private.h"
18 : : #include "access/gistscan.h"
19 : : #include "access/xloginsert.h"
20 : : #include "catalog/pg_collation.h"
21 : : #include "commands/vacuum.h"
22 : : #include "miscadmin.h"
23 : : #include "nodes/execnodes.h"
24 : : #include "storage/predicate.h"
25 : : #include "utils/fmgrprotos.h"
26 : : #include "utils/index_selfuncs.h"
27 : : #include "utils/memutils.h"
28 : : #include "utils/rel.h"
29 : :
30 : : /* non-export function prototypes */
31 : : static void gistfixsplit(GISTInsertState *state, GISTSTATE *giststate);
32 : : static bool gistinserttuple(GISTInsertState *state, GISTInsertStack *stack,
33 : : GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum);
34 : : static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
35 : : GISTSTATE *giststate,
36 : : IndexTuple *tuples, int ntup, OffsetNumber oldoffnum,
37 : : Buffer leftchild, Buffer rightchild,
38 : : bool unlockbuf, bool unlockleftchild);
39 : : static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
40 : : GISTSTATE *giststate, List *splitinfo, bool unlockbuf);
41 : : static void gistprunepage(Relation rel, Page page, Buffer buffer,
42 : : Relation heapRel);
43 : :
44 : :
45 : : #define ROTATEDIST(d) do { \
46 : : SplitPageLayout *tmp = (SplitPageLayout *) palloc0(sizeof(SplitPageLayout)); \
47 : : tmp->block.blkno = InvalidBlockNumber; \
48 : : tmp->buffer = InvalidBuffer; \
49 : : tmp->next = (d); \
50 : : (d)=tmp; \
51 : : } while(0)
52 : :
53 : :
54 : : /*
55 : : * GiST handler function: return IndexAmRoutine with access method parameters
56 : : * and callbacks.
57 : : */
58 : : Datum
3520 tgl@sss.pgh.pa.us 59 :CBC 7434 : gisthandler(PG_FUNCTION_ARGS)
60 : : {
61 : 7434 : IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
62 : :
63 : 7434 : amroutine->amstrategies = 0;
3418 teodor@sigaev.ru 64 : 7434 : amroutine->amsupport = GISTNProcs;
1986 akorotkov@postgresql 65 : 7434 : amroutine->amoptsprocnum = GIST_OPTIONS_PROC;
3520 tgl@sss.pgh.pa.us 66 : 7434 : amroutine->amcanorder = false;
67 : 7434 : amroutine->amcanorderbyop = true;
191 peter@eisentraut.org 68 : 7434 : amroutine->amcanhash = false;
183 69 : 7434 : amroutine->amconsistentequality = false;
70 : 7434 : amroutine->amconsistentordering = false;
3520 tgl@sss.pgh.pa.us 71 : 7434 : amroutine->amcanbackward = false;
72 : 7434 : amroutine->amcanunique = false;
73 : 7434 : amroutine->amcanmulticol = true;
74 : 7434 : amroutine->amoptionalkey = true;
75 : 7434 : amroutine->amsearcharray = false;
76 : 7434 : amroutine->amsearchnulls = true;
77 : 7434 : amroutine->amstorage = true;
78 : 7434 : amroutine->amclusterable = true;
2720 teodor@sigaev.ru 79 : 7434 : amroutine->ampredlocks = true;
3125 rhaas@postgresql.org 80 : 7434 : amroutine->amcanparallel = false;
638 tomas.vondra@postgre 81 : 7434 : amroutine->amcanbuildparallel = false;
2372 akorotkov@postgresql 82 : 7434 : amroutine->amcaninclude = true;
2061 akapila@postgresql.o 83 : 7434 : amroutine->amusemaintenanceworkmem = false;
901 tomas.vondra@postgre 84 : 7434 : amroutine->amsummarizing = false;
2061 akapila@postgresql.o 85 : 7434 : amroutine->amparallelvacuumoptions =
86 : : VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP;
3520 tgl@sss.pgh.pa.us 87 : 7434 : amroutine->amkeytype = InvalidOid;
88 : :
89 : 7434 : amroutine->ambuild = gistbuild;
90 : 7434 : amroutine->ambuildempty = gistbuildempty;
91 : 7434 : amroutine->aminsert = gistinsert;
651 tomas.vondra@postgre 92 : 7434 : amroutine->aminsertcleanup = NULL;
3520 tgl@sss.pgh.pa.us 93 : 7434 : amroutine->ambulkdelete = gistbulkdelete;
94 : 7434 : amroutine->amvacuumcleanup = gistvacuumcleanup;
95 : 7434 : amroutine->amcanreturn = gistcanreturn;
96 : 7434 : amroutine->amcostestimate = gistcostestimate;
361 peter@eisentraut.org 97 : 7434 : amroutine->amgettreeheight = NULL;
3520 tgl@sss.pgh.pa.us 98 : 7434 : amroutine->amoptions = gistoptions;
3311 99 : 7434 : amroutine->amproperty = gistproperty;
2349 alvherre@alvh.no-ip. 100 : 7434 : amroutine->ambuildphasename = NULL;
3520 tgl@sss.pgh.pa.us 101 : 7434 : amroutine->amvalidate = gistvalidate;
1862 102 : 7434 : amroutine->amadjustmembers = gistadjustmembers;
3520 103 : 7434 : amroutine->ambeginscan = gistbeginscan;
104 : 7434 : amroutine->amrescan = gistrescan;
105 : 7434 : amroutine->amgettuple = gistgettuple;
106 : 7434 : amroutine->amgetbitmap = gistgetbitmap;
107 : 7434 : amroutine->amendscan = gistendscan;
108 : 7434 : amroutine->ammarkpos = NULL;
109 : 7434 : amroutine->amrestrpos = NULL;
3147 rhaas@postgresql.org 110 : 7434 : amroutine->amestimateparallelscan = NULL;
111 : 7434 : amroutine->aminitparallelscan = NULL;
112 : 7434 : amroutine->amparallelrescan = NULL;
216 peter@eisentraut.org 113 : 7434 : amroutine->amtranslatestrategy = NULL;
215 114 : 7434 : amroutine->amtranslatecmptype = gisttranslatecmptype;
115 : :
3520 tgl@sss.pgh.pa.us 116 : 7434 : PG_RETURN_POINTER(amroutine);
117 : : }
118 : :
119 : : /*
120 : : * Create and return a temporary memory context for use by GiST. We
121 : : * _always_ invoke user-provided methods in a temporary memory
122 : : * context, so that memory leaks in those functions cannot cause
123 : : * problems. Also, we use some additional temporary contexts in the
124 : : * GiST code itself, to avoid the need to do some awkward manual
125 : : * memory management.
126 : : */
127 : : MemoryContext
7289 bruce@momjian.us 128 : 4759 : createTempGistContext(void)
129 : : {
130 : 4759 : return AllocSetContextCreate(CurrentMemoryContext,
131 : : "GiST temporary context",
132 : : ALLOCSET_DEFAULT_SIZES);
133 : : }
134 : :
135 : : /*
136 : : * gistbuildempty() -- build an empty gist index in the initialization fork
137 : : */
138 : : void
3520 tgl@sss.pgh.pa.us 139 : 5 : gistbuildempty(Relation index)
140 : : {
141 : : Buffer buffer;
142 : :
143 : : /* Initialize the root page */
745 tmunro@postgresql.or 144 : 5 : buffer = ExtendBufferedRel(BMR_REL(index), INIT_FORKNUM, NULL,
145 : : EB_SKIP_EXTENSION_LOCK | EB_LOCK_FIRST);
146 : :
147 : : /* Initialize and xlog buffer */
4590 heikki.linnakangas@i 148 : 5 : START_CRIT_SECTION();
149 : 5 : GISTInitBuffer(buffer, F_LEAF);
150 : 5 : MarkBufferDirty(buffer);
4294 151 : 5 : log_newpage_buffer(buffer, true);
4590 152 [ - + ]: 5 : END_CRIT_SECTION();
153 : :
154 : : /* Unlock and release the buffer */
155 : 5 : UnlockReleaseBuffer(buffer);
5365 rhaas@postgresql.org 156 : 5 : }
157 : :
158 : : /*
159 : : * gistinsert -- wrapper for GiST tuple insertion.
160 : : *
161 : : * This is the public interface routine for tuple insertion in GiSTs.
162 : : * It doesn't do any work; just locks the relation and passes the buck.
163 : : */
164 : : bool
3520 tgl@sss.pgh.pa.us 165 : 152205 : gistinsert(Relation r, Datum *values, bool *isnull,
166 : : ItemPointer ht_ctid, Relation heapRel,
167 : : IndexUniqueCheck checkUnique,
168 : : bool indexUnchanged,
169 : : IndexInfo *indexInfo)
170 : : {
3131 171 : 152205 : GISTSTATE *giststate = (GISTSTATE *) indexInfo->ii_AmCache;
172 : : IndexTuple itup;
173 : : MemoryContext oldCxt;
174 : :
175 : : /* Initialize GISTSTATE cache if first call in this statement */
176 [ + + ]: 152205 : if (giststate == NULL)
177 : : {
178 : 930 : oldCxt = MemoryContextSwitchTo(indexInfo->ii_Context);
179 : 930 : giststate = initGISTstate(r);
180 : 930 : giststate->tempCxt = createTempGistContext();
282 peter@eisentraut.org 181 : 930 : indexInfo->ii_AmCache = giststate;
3131 tgl@sss.pgh.pa.us 182 : 930 : MemoryContextSwitchTo(oldCxt);
183 : : }
184 : :
5090 185 : 152205 : oldCxt = MemoryContextSwitchTo(giststate->tempCxt);
186 : :
303 michael@paquier.xyz 187 : 152205 : itup = gistFormTuple(giststate, r, values, isnull, true);
10226 bruce@momjian.us 188 : 152204 : itup->t_tid = *ht_ctid;
189 : :
2348 heikki.linnakangas@i 190 : 152204 : gistdoinsert(r, itup, 0, giststate, heapRel, false);
191 : :
192 : : /* cleanup */
5090 tgl@sss.pgh.pa.us 193 : 152198 : MemoryContextSwitchTo(oldCxt);
3131 194 : 152198 : MemoryContextReset(giststate->tempCxt);
195 : :
3520 196 : 152198 : return false;
197 : : }
198 : :
199 : :
200 : : /*
201 : : * Place tuples from 'itup' to 'buffer'. If 'oldoffnum' is valid, the tuple
202 : : * at that offset is atomically removed along with inserting the new tuples.
203 : : * This is used to replace a tuple with a new one.
204 : : *
205 : : * If 'leftchildbuf' is valid, we're inserting the downlink for the page
206 : : * to the right of 'leftchildbuf', or updating the downlink for 'leftchildbuf'.
207 : : * F_FOLLOW_RIGHT flag on 'leftchildbuf' is cleared and NSN is set.
208 : : *
209 : : * If 'markfollowright' is true and the page is split, the left child is
210 : : * marked with F_FOLLOW_RIGHT flag. That is the normal case. During buffered
211 : : * index build, however, there is no concurrent access and the page splitting
212 : : * is done in a slightly simpler fashion, and false is passed.
213 : : *
214 : : * If there is not enough room on the page, it is split. All the split
215 : : * pages are kept pinned and locked and returned in *splitinfo, the caller
216 : : * is responsible for inserting the downlinks for them. However, if
217 : : * 'buffer' is the root page and it needs to be split, gistplacetopage()
218 : : * performs the split as one atomic operation, and *splitinfo is set to NIL.
219 : : * In that case, we continue to hold the root page locked, and the child
220 : : * pages are released; note that new tuple(s) are *not* on the root page
221 : : * but in one of the new child pages.
222 : : *
223 : : * If 'newblkno' is not NULL, returns the block number of page the first
224 : : * new/updated tuple was inserted to. Usually it's the given page, but could
225 : : * be its right sibling if the page was split.
226 : : *
227 : : * Returns 'true' if the page was split, 'false' otherwise.
228 : : */
229 : : bool
5112 heikki.linnakangas@i 230 : 816253 : gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
231 : : Buffer buffer,
232 : : IndexTuple *itup, int ntup, OffsetNumber oldoffnum,
233 : : BlockNumber *newblkno,
234 : : Buffer leftchildbuf,
235 : : List **splitinfo,
236 : : bool markfollowright,
237 : : Relation heapRel,
238 : : bool is_build)
239 : : {
4769 240 : 816253 : BlockNumber blkno = BufferGetBlockNumber(buffer);
3426 kgrittn@postgresql.o 241 : 816253 : Page page = BufferGetPage(buffer);
5371 heikki.linnakangas@i 242 : 816253 : bool is_leaf = (GistPageIsLeaf(page)) ? true : false;
243 : : XLogRecPtr recptr;
244 : : bool is_split;
245 : :
246 : : /*
247 : : * Refuse to modify a page that's incompletely split. This should not
248 : : * happen because we finish any incomplete splits while we walk down the
249 : : * tree. However, it's remotely possible that another concurrent inserter
250 : : * splits a parent page, and errors out before completing the split. We
251 : : * will just throw an error in that case, and leave any split we had in
252 : : * progress unfinished too. The next insert that comes along will clean up
253 : : * the mess.
254 : : */
255 [ - + ]: 816253 : if (GistFollowRight(page))
5371 heikki.linnakangas@i 256 [ # # ]:UBC 0 : elog(ERROR, "concurrent GiST page split was incomplete");
257 : :
258 : : /* should never try to insert to a deleted page */
1690 heikki.linnakangas@i 259 [ - + ]:CBC 816253 : Assert(!GistPageIsDeleted(page));
260 : :
5371 261 : 816253 : *splitinfo = NIL;
262 : :
263 : : /*
264 : : * if isupdate, remove old key: This node's key has been modified, either
265 : : * because a child split occurred or because we needed to adjust our key
266 : : * for an insert in a child node. Therefore, remove the old version of
267 : : * this node's key.
268 : : *
269 : : * for WAL replay, in the non-split case we handle this by setting up a
270 : : * one-element todelete array; in the split case, it's handled implicitly
271 : : * because the tuple vector passed to gistSplit won't include this tuple.
272 : : */
5112 273 : 816253 : is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
274 : :
275 : : /*
276 : : * If leaf page is full, try at first to delete dead tuples. And then
277 : : * check again.
278 : : */
3650 teodor@sigaev.ru 279 [ + + + + : 816253 : if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
- + ]
280 : : {
2377 heikki.linnakangas@i 281 :UBC 0 : gistprunepage(rel, page, buffer, heapRel);
3650 teodor@sigaev.ru 282 : 0 : is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
283 : : }
284 : :
5371 heikki.linnakangas@i 285 [ + + ]:CBC 816253 : if (is_split)
286 : : {
287 : : /* no space for insertion */
288 : : IndexTuple *itvec;
289 : : int tlen;
613 rhaas@postgresql.org 290 : 12495 : SplitPageLayout *dist = NULL,
291 : : *ptr;
5371 heikki.linnakangas@i 292 : 12495 : BlockNumber oldrlink = InvalidBlockNumber;
4822 293 : 12495 : GistNSN oldnsn = 0;
294 : : SplitPageLayout rootpg;
295 : : bool is_rootsplit;
296 : : int npage;
297 : :
5371 298 : 12495 : is_rootsplit = (blkno == GIST_ROOT_BLKNO);
299 : :
300 : : /*
301 : : * Form index tuples vector to split. If we're replacing an old tuple,
302 : : * remove the old version from the vector.
303 : : */
304 : 12495 : itvec = gistextractpage(page, &tlen);
305 [ + + + - : 12495 : if (OffsetNumberIsValid(oldoffnum))
+ + ]
306 : : {
307 : : /* on inner page we should remove old tuple */
308 : 2650 : int pos = oldoffnum - FirstOffsetNumber;
309 : :
6912 bruce@momjian.us 310 : 2650 : tlen--;
311 [ + + ]: 2650 : if (pos != tlen)
312 : 1704 : memmove(itvec + pos, itvec + pos + 1, sizeof(IndexTuple) * (tlen - pos));
313 : : }
5371 heikki.linnakangas@i 314 : 12495 : itvec = gistjoinvector(itvec, &tlen, itup, ntup);
5112 315 : 12495 : dist = gistSplit(rel, page, itvec, tlen, giststate);
316 : :
317 : : /*
318 : : * Check that split didn't produce too many pages.
319 : : */
4174 320 : 12495 : npage = 0;
321 [ + + ]: 37502 : for (ptr = dist; ptr; ptr = ptr->next)
322 : 25007 : npage++;
323 : : /* in a root split, we'll add one more page to the list below */
324 [ + + ]: 12495 : if (is_rootsplit)
325 : 175 : npage++;
326 [ - + ]: 12495 : if (npage > GIST_MAX_SPLIT_PAGES)
4174 heikki.linnakangas@i 327 [ # # ]:UBC 0 : elog(ERROR, "GiST page split into too many halves (%d, maximum %d)",
328 : : npage, GIST_MAX_SPLIT_PAGES);
329 : :
330 : : /*
331 : : * Set up pages to work with. Allocate new buffers for all but the
332 : : * leftmost page. The original page becomes the new leftmost page, and
333 : : * is just replaced with the new contents.
334 : : *
335 : : * For a root-split, allocate new buffers for all child pages, the
336 : : * original page is overwritten with new root page containing
337 : : * downlinks to the new child pages.
338 : : */
5371 heikki.linnakangas@i 339 :CBC 12495 : ptr = dist;
340 [ + + ]: 12495 : if (!is_rootsplit)
341 : : {
342 : : /* save old rightlink and NSN */
343 : 12320 : oldrlink = GistPageGetOpaque(page)->rightlink;
4615 344 : 12320 : oldnsn = GistPageGetNSN(page);
345 : :
5371 346 : 12320 : dist->buffer = buffer;
347 : 12320 : dist->block.blkno = BufferGetBlockNumber(buffer);
3426 kgrittn@postgresql.o 348 : 12320 : dist->page = PageGetTempPageCopySpecial(BufferGetPage(buffer));
349 : :
350 : : /* clean all flags except F_LEAF */
7059 teodor@sigaev.ru 351 : 12320 : GistPageGetOpaque(dist->page)->flags = (is_leaf) ? F_LEAF : 0;
352 : :
5371 heikki.linnakangas@i 353 : 12320 : ptr = ptr->next;
354 : : }
355 [ + + ]: 25182 : for (; ptr; ptr = ptr->next)
356 : : {
357 : : /* Allocate new page */
889 andres@anarazel.de 358 : 12687 : ptr->buffer = gistNewBuffer(rel, heapRel);
5371 heikki.linnakangas@i 359 : 12687 : GISTInitBuffer(ptr->buffer, (is_leaf) ? F_LEAF : 0);
3426 kgrittn@postgresql.o 360 : 12687 : ptr->page = BufferGetPage(ptr->buffer);
5371 heikki.linnakangas@i 361 : 12687 : ptr->block.blkno = BufferGetBlockNumber(ptr->buffer);
2720 teodor@sigaev.ru 362 : 12687 : PredicateLockPageSplit(rel,
363 : : BufferGetBlockNumber(buffer),
364 : : BufferGetBlockNumber(ptr->buffer));
365 : : }
366 : :
367 : : /*
368 : : * Now that we know which blocks the new pages go to, set up downlink
369 : : * tuples to point to them.
370 : : */
6912 bruce@momjian.us 371 [ + + ]: 37502 : for (ptr = dist; ptr; ptr = ptr->next)
372 : : {
5371 heikki.linnakangas@i 373 : 25007 : ItemPointerSetBlockNumber(&(ptr->itup->t_tid), ptr->block.blkno);
374 : 25007 : GistTupleSetValid(ptr->itup);
375 : : }
376 : :
377 : : /*
378 : : * If this is a root split, we construct the new root page with the
379 : : * downlinks here directly, instead of requiring the caller to insert
380 : : * them. Add the new root page to the list along with the child pages.
381 : : */
382 [ + + ]: 12495 : if (is_rootsplit)
383 : : {
384 : : IndexTuple *downlinks;
5263 bruce@momjian.us 385 : 175 : int ndownlinks = 0;
386 : : int i;
387 : :
5371 heikki.linnakangas@i 388 : 175 : rootpg.buffer = buffer;
3426 kgrittn@postgresql.o 389 : 175 : rootpg.page = PageGetTempPageCopySpecial(BufferGetPage(rootpg.buffer));
5371 heikki.linnakangas@i 390 : 175 : GistPageGetOpaque(rootpg.page)->flags = 0;
391 : :
392 : : /* Prepare a vector of all the downlinks */
393 [ + + ]: 528 : for (ptr = dist; ptr; ptr = ptr->next)
394 : 353 : ndownlinks++;
395 : 175 : downlinks = palloc(sizeof(IndexTuple) * ndownlinks);
396 [ + + ]: 528 : for (i = 0, ptr = dist; ptr; ptr = ptr->next)
397 : 353 : downlinks[i++] = ptr->itup;
398 : :
399 : 175 : rootpg.block.blkno = GIST_ROOT_BLKNO;
400 : 175 : rootpg.block.num = ndownlinks;
401 : 175 : rootpg.list = gistfillitupvec(downlinks, ndownlinks,
402 : : &(rootpg.lenlist));
403 : 175 : rootpg.itup = NULL;
404 : :
405 : 175 : rootpg.next = dist;
406 : 175 : dist = &rootpg;
407 : : }
408 : : else
409 : : {
410 : : /* Prepare split-info to be returned to caller */
411 [ + + ]: 36974 : for (ptr = dist; ptr; ptr = ptr->next)
412 : : {
413 : 24654 : GISTPageSplitInfo *si = palloc(sizeof(GISTPageSplitInfo));
414 : :
415 : 24654 : si->buf = ptr->buffer;
416 : 24654 : si->downlink = ptr->itup;
417 : 24654 : *splitinfo = lappend(*splitinfo, si);
418 : : }
419 : : }
420 : :
421 : : /*
422 : : * Fill all pages. All the pages are new, ie. freshly allocated empty
423 : : * pages, or a temporary copy of the old page.
424 : : */
425 [ + + ]: 37677 : for (ptr = dist; ptr; ptr = ptr->next)
426 : : {
5263 bruce@momjian.us 427 : 25182 : char *data = (char *) (ptr->list);
428 : :
1109 drowley@postgresql.o 429 [ + + ]: 886946 : for (int i = 0; i < ptr->block.num; i++)
430 : : {
4769 heikki.linnakangas@i 431 : 861764 : IndexTuple thistup = (IndexTuple) data;
432 : :
433 [ - + ]: 861764 : if (PageAddItem(ptr->page, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
5112 heikki.linnakangas@i 434 [ # # ]:UBC 0 : elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(rel));
435 : :
436 : : /*
437 : : * If this is the first inserted/updated tuple, let the caller
438 : : * know which page it landed on.
439 : : */
4769 heikki.linnakangas@i 440 [ + + + + ]:CBC 861764 : if (newblkno && ItemPointerEquals(&thistup->t_tid, &(*itup)->t_tid))
441 : 387 : *newblkno = ptr->block.blkno;
442 : :
443 : 861764 : data += IndexTupleSize(thistup);
444 : : }
445 : :
446 : : /* Set up rightlinks */
5371 447 [ + + + + ]: 25182 : if (ptr->next && ptr->block.blkno != GIST_ROOT_BLKNO)
448 : 25024 : GistPageGetOpaque(ptr->page)->rightlink =
449 : 12512 : ptr->next->block.blkno;
450 : : else
451 : 12670 : GistPageGetOpaque(ptr->page)->rightlink = oldrlink;
452 : :
453 : : /*
454 : : * Mark the all but the right-most page with the follow-right
455 : : * flag. It will be cleared as soon as the downlink is inserted
456 : : * into the parent, but this ensures that if we error out before
457 : : * that, the index is still consistent. (in buffering build mode,
458 : : * any error will abort the index build anyway, so this is not
459 : : * needed.)
460 : : */
5112 461 [ + + + + : 25182 : if (ptr->next && !is_rootsplit && markfollowright)
+ + ]
5371 462 : 11950 : GistMarkFollowRight(ptr->page);
463 : : else
464 : 13232 : GistClearFollowRight(ptr->page);
465 : :
466 : : /*
467 : : * Copy the NSN of the original page to all pages. The
468 : : * F_FOLLOW_RIGHT flags ensure that scans will follow the
469 : : * rightlinks until the downlinks are inserted.
470 : : */
4615 471 : 25182 : GistPageSetNSN(ptr->page, oldnsn);
472 : : }
473 : :
474 : : /*
475 : : * gistXLogSplit() needs to WAL log a lot of pages, prepare WAL
476 : : * insertion for that. NB: The number of pages and data segments
477 : : * specified here must match the calculations in gistXLogSplit()!
478 : : */
2348 479 [ + + + + : 12495 : if (!is_build && RelationNeedsWAL(rel))
+ + + - +
- ]
3943 480 : 1741 : XLogEnsureRecordSpace(npage, 1 + npage * 2);
481 : :
7059 teodor@sigaev.ru 482 : 12495 : START_CRIT_SECTION();
483 : :
484 : : /*
485 : : * Must mark buffers dirty before XLogInsert, even though we'll still
486 : : * be changing their opaque fields below.
487 : : */
6912 bruce@momjian.us 488 [ + + ]: 37677 : for (ptr = dist; ptr; ptr = ptr->next)
7099 tgl@sss.pgh.pa.us 489 : 25182 : MarkBufferDirty(ptr->buffer);
5371 heikki.linnakangas@i 490 [ + + ]: 12495 : if (BufferIsValid(leftchildbuf))
491 : 2566 : MarkBufferDirty(leftchildbuf);
492 : :
493 : : /*
494 : : * The first page in the chain was a temporary working copy meant to
495 : : * replace the old page. Copy it over the old page.
496 : : */
3426 kgrittn@postgresql.o 497 : 12495 : PageRestoreTempPage(dist->page, BufferGetPage(dist->buffer));
498 : 12495 : dist->page = BufferGetPage(dist->buffer);
499 : :
500 : : /*
501 : : * Write the WAL record.
502 : : *
503 : : * If we're building a new index, however, we don't WAL-log changes
504 : : * yet. The LSN-NSN interlock between parent and child requires that
505 : : * LSNs never move backwards, so set the LSNs to a value that's
506 : : * smaller than any real or fake unlogged LSN that might be generated
507 : : * later. (There can't be any concurrent scans during index build, so
508 : : * we don't need to be able to detect concurrent splits yet.)
509 : : */
2348 heikki.linnakangas@i 510 [ + + ]: 12495 : if (is_build)
511 : 10751 : recptr = GistBuildLSN;
512 : : else
513 : : {
514 [ + + + + : 1744 : if (RelationNeedsWAL(rel))
+ - + - ]
515 : 1741 : recptr = gistXLogSplit(is_leaf,
516 : : dist, oldrlink, oldnsn, leftchildbuf,
517 : : markfollowright);
518 : : else
519 : 3 : recptr = gistGetFakeLSN(rel);
520 : : }
521 : :
6912 bruce@momjian.us 522 [ + + ]: 37677 : for (ptr = dist; ptr; ptr = ptr->next)
5371 heikki.linnakangas@i 523 : 25182 : PageSetLSN(ptr->page, recptr);
524 : :
525 : : /*
526 : : * Return the new child buffers to the caller.
527 : : *
528 : : * If this was a root split, we've already inserted the downlink
529 : : * pointers, in the form of a new root page. Therefore we can release
530 : : * all the new buffers, and keep just the root page locked.
531 : : */
532 [ + + ]: 12495 : if (is_rootsplit)
533 : : {
534 [ + + ]: 528 : for (ptr = dist->next; ptr; ptr = ptr->next)
535 : 353 : UnlockReleaseBuffer(ptr->buffer);
536 : : }
537 : : }
538 : : else
539 : : {
540 : : /*
541 : : * Enough space. We always get here if ntup==0.
542 : : */
7059 teodor@sigaev.ru 543 : 803758 : START_CRIT_SECTION();
544 : :
545 : : /*
546 : : * Delete old tuple if any, then insert new tuple(s) if any. If
547 : : * possible, use the fast path of PageIndexTupleOverwrite.
548 : : */
5371 heikki.linnakangas@i 549 [ + + + - : 803758 : if (OffsetNumberIsValid(oldoffnum))
+ + ]
550 : : {
3284 tgl@sss.pgh.pa.us 551 [ + + ]: 368517 : if (ntup == 1)
552 : : {
553 : : /* One-for-one replacement, so use PageIndexTupleOverwrite */
554 [ - + ]: 358772 : if (!PageIndexTupleOverwrite(page, oldoffnum, (Item) *itup,
555 : : IndexTupleSize(*itup)))
3284 tgl@sss.pgh.pa.us 556 [ # # ]:UBC 0 : elog(ERROR, "failed to add item to index page in \"%s\"",
557 : : RelationGetRelationName(rel));
558 : : }
559 : : else
560 : : {
561 : : /* Delete old, then append new tuple(s) to page */
3284 tgl@sss.pgh.pa.us 562 :CBC 9745 : PageIndexTupleDelete(page, oldoffnum);
563 : 9745 : gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
564 : : }
565 : : }
566 : : else
567 : : {
568 : : /* Just append new tuples at the end of the page */
569 : 435241 : gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
570 : : }
571 : :
5371 heikki.linnakangas@i 572 : 803758 : MarkBufferDirty(buffer);
573 : :
574 [ + + ]: 803758 : if (BufferIsValid(leftchildbuf))
575 : 9384 : MarkBufferDirty(leftchildbuf);
576 : :
2348 577 [ + + ]: 803758 : if (is_build)
578 : 556427 : recptr = GistBuildLSN;
579 : : else
580 : : {
581 [ + + + + : 247331 : if (RelationNeedsWAL(rel))
+ - + - ]
7289 bruce@momjian.us 582 : 247292 : {
2348 heikki.linnakangas@i 583 : 247292 : OffsetNumber ndeloffs = 0,
584 : : deloffs[1];
585 : :
586 [ + + + - : 247292 : if (OffsetNumberIsValid(oldoffnum))
+ + ]
587 : : {
588 : 96865 : deloffs[0] = oldoffnum;
589 : 96865 : ndeloffs = 1;
590 : : }
591 : :
592 : 247292 : recptr = gistXLogUpdate(buffer,
593 : : deloffs, ndeloffs, itup, ntup,
594 : : leftchildbuf);
595 : : }
596 : : else
597 : 39 : recptr = gistGetFakeLSN(rel);
598 : : }
599 : 803758 : PageSetLSN(page, recptr);
600 : :
4769 601 [ + + ]: 803758 : if (newblkno)
602 : 52185 : *newblkno = blkno;
603 : : }
604 : :
605 : : /*
606 : : * If we inserted the downlink for a child page, set NSN and clear
607 : : * F_FOLLOW_RIGHT flag on the left child, so that concurrent scans know to
608 : : * follow the rightlink if and only if they looked at the parent page
609 : : * before we inserted the downlink.
610 : : *
611 : : * Note that we do this *after* writing the WAL record. That means that
612 : : * the possible full page image in the WAL record does not include these
613 : : * changes, and they must be replayed even if the page is restored from
614 : : * the full page image. There's a chicken-and-egg problem: if we updated
615 : : * the child pages first, we wouldn't know the recptr of the WAL record
616 : : * we're about to write.
617 : : */
5371 618 [ + + ]: 816253 : if (BufferIsValid(leftchildbuf))
619 : : {
3426 kgrittn@postgresql.o 620 : 11950 : Page leftpg = BufferGetPage(leftchildbuf);
621 : :
4615 heikki.linnakangas@i 622 : 11950 : GistPageSetNSN(leftpg, recptr);
5371 623 : 11950 : GistClearFollowRight(leftpg);
624 : :
625 : 11950 : PageSetLSN(leftpg, recptr);
626 : : }
627 : :
628 [ - + ]: 816253 : END_CRIT_SECTION();
629 : :
630 : 816253 : return is_split;
631 : : }
632 : :
633 : : /*
634 : : * Workhorse routine for doing insertion into a GiST index. Note that
635 : : * this routine assumes it is invoked in a short-lived memory context,
636 : : * so it does not bother releasing palloc'd allocations.
637 : : */
638 : : void
2451 akorotkov@postgresql 639 : 427363 : gistdoinsert(Relation r, IndexTuple itup, Size freespace,
640 : : GISTSTATE *giststate, Relation heapRel, bool is_build)
641 : : {
642 : : ItemId iid;
643 : : IndexTuple idxtuple;
644 : : GISTInsertStack firststack;
645 : : GISTInsertStack *stack;
646 : : GISTInsertState state;
5371 heikki.linnakangas@i 647 : 427363 : bool xlocked = false;
648 : :
649 : 427363 : memset(&state, 0, sizeof(GISTInsertState));
650 : 427363 : state.freespace = freespace;
651 : 427363 : state.r = r;
2451 akorotkov@postgresql 652 : 427363 : state.heapRel = heapRel;
2348 heikki.linnakangas@i 653 : 427363 : state.is_build = is_build;
654 : :
655 : : /* Start from the root */
5371 656 : 427363 : firststack.blkno = GIST_ROOT_BLKNO;
4822 657 : 427363 : firststack.lsn = 0;
2307 658 : 427363 : firststack.retry_from_parent = false;
5371 659 : 427363 : firststack.parent = NULL;
5167 660 : 427363 : firststack.downlinkoffnum = InvalidOffsetNumber;
5371 661 : 427363 : state.stack = stack = &firststack;
662 : :
663 : : /*
664 : : * Walk down along the path of smallest penalty, updating the parent
665 : : * pointers with the key we're inserting as we go. If we crash in the
666 : : * middle, the tree is consistent, although the possible parent updates
667 : : * were a waste.
668 : : */
669 : : for (;;)
670 : : {
671 : : /*
672 : : * If we split an internal page while descending the tree, we have to
673 : : * retry at the parent. (Normally, the LSN-NSN interlock below would
674 : : * also catch this and cause us to retry. But LSNs are not updated
675 : : * during index build.)
676 : : */
2307 677 [ + + ]: 986933 : while (stack->retry_from_parent)
678 : : {
679 [ - + ]: 145 : if (xlocked)
2307 heikki.linnakangas@i 680 :UBC 0 : LockBuffer(stack->buffer, GIST_UNLOCK);
2307 heikki.linnakangas@i 681 :CBC 145 : xlocked = false;
682 : 145 : ReleaseBuffer(stack->buffer);
683 : 145 : state.stack = stack = stack->parent;
684 : : }
685 : :
5371 686 [ + + ]: 986788 : if (XLogRecPtrIsInvalid(stack->lsn))
687 : 986713 : stack->buffer = ReadBuffer(state.r, stack->blkno);
688 : :
689 : : /*
690 : : * Be optimistic and grab shared lock first. Swap it for an exclusive
691 : : * lock later if we need to update the page.
692 : : */
693 [ + - ]: 986788 : if (!xlocked)
694 : : {
695 : 986788 : LockBuffer(stack->buffer, GIST_SHARE);
696 : 986788 : gistcheckpage(state.r, stack->buffer);
697 : : }
698 : :
8 peter@eisentraut.org 699 :GNC 986788 : stack->page = BufferGetPage(stack->buffer);
2797 alvherre@alvh.no-ip. 700 :CBC 986788 : stack->lsn = xlocked ?
701 [ - + ]: 986788 : PageGetLSN(stack->page) : BufferGetLSNAtomic(stack->buffer);
5371 heikki.linnakangas@i 702 [ + + + + : 986788 : Assert(!RelationNeedsWAL(state.r) || !XLogRecPtrIsInvalid(stack->lsn));
+ + + + -
+ ]
703 : :
704 : : /*
705 : : * If this page was split but the downlink was never inserted to the
706 : : * parent because the inserting backend crashed before doing that, fix
707 : : * that now.
708 : : */
709 [ - + ]: 986788 : if (GistFollowRight(stack->page))
710 : : {
5371 heikki.linnakangas@i 711 [ # # ]:UBC 0 : if (!xlocked)
712 : : {
713 : 0 : LockBuffer(stack->buffer, GIST_UNLOCK);
714 : 0 : LockBuffer(stack->buffer, GIST_EXCLUSIVE);
715 : 0 : xlocked = true;
716 : : /* someone might've completed the split when we unlocked */
717 [ # # ]: 0 : if (!GistFollowRight(stack->page))
718 : 0 : continue;
719 : : }
720 : 0 : gistfixsplit(&state, giststate);
721 : :
722 : 0 : UnlockReleaseBuffer(stack->buffer);
723 : 0 : xlocked = false;
724 : 0 : state.stack = stack = stack->parent;
725 : 0 : continue;
726 : : }
727 : :
2236 heikki.linnakangas@i 728 [ + + + - ]:CBC 1546152 : if ((stack->blkno != GIST_ROOT_BLKNO &&
729 : 559364 : stack->parent->lsn < GistPageGetNSN(stack->page)) ||
730 [ - + ]: 986788 : GistPageIsDeleted(stack->page))
731 : : {
732 : : /*
733 : : * Concurrent split or page deletion detected. There's no
734 : : * guarantee that the downlink for this page is consistent with
735 : : * the tuple we're inserting anymore, so go back to parent and
736 : : * rechoose the best child.
737 : : */
5371 heikki.linnakangas@i 738 :UBC 0 : UnlockReleaseBuffer(stack->buffer);
739 : 0 : xlocked = false;
740 : 0 : state.stack = stack = stack->parent;
7376 teodor@sigaev.ru 741 : 0 : continue;
742 : : }
743 : :
5371 heikki.linnakangas@i 744 [ + + ]:CBC 986788 : if (!GistPageIsLeaf(stack->page))
745 : : {
746 : : /*
747 : : * This is an internal page so continue to walk down the tree.
748 : : * Find the child node that has the minimum insertion penalty.
749 : : */
750 : : BlockNumber childblkno;
751 : : IndexTuple newtup;
752 : : GISTInsertStack *item;
753 : : OffsetNumber downlinkoffnum;
754 : :
5167 755 : 559425 : downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
756 : 559425 : iid = PageGetItemId(stack->page, downlinkoffnum);
5371 757 : 559425 : idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
758 : 559425 : childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
759 : :
760 : : /*
761 : : * Check that it's not a leftover invalid tuple from pre-9.1
762 : : */
763 [ - + ]: 559425 : if (GistTupleIsInvalid(idxtuple))
5371 heikki.linnakangas@i 764 [ # # ]:UBC 0 : ereport(ERROR,
765 : : (errmsg("index \"%s\" contains an inner tuple marked as invalid",
766 : : RelationGetRelationName(r)),
767 : : errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
768 : : errhint("Please REINDEX it.")));
769 : :
770 : : /*
771 : : * Check that the key representing the target child node is
772 : : * consistent with the key we're inserting. Update it if it's not.
773 : : */
5371 heikki.linnakangas@i 774 :CBC 559425 : newtup = gistgetadjusted(state.r, idxtuple, itup, giststate);
775 [ + + ]: 559425 : if (newtup)
776 : : {
777 : : /*
778 : : * Swap shared lock for an exclusive one. Beware, the page may
779 : : * change while we unlock/lock the page...
780 : : */
781 [ + - ]: 324374 : if (!xlocked)
782 : : {
783 : 324374 : LockBuffer(stack->buffer, GIST_UNLOCK);
784 : 324374 : LockBuffer(stack->buffer, GIST_EXCLUSIVE);
785 : 324374 : xlocked = true;
8 peter@eisentraut.org 786 :GNC 324374 : stack->page = BufferGetPage(stack->buffer);
787 : :
4635 alvherre@alvh.no-ip. 788 [ - + ]:CBC 324374 : if (PageGetLSN(stack->page) != stack->lsn)
789 : : {
790 : : /* the page was changed while we unlocked it, retry */
5371 heikki.linnakangas@i 791 :UBC 0 : continue;
792 : : }
793 : : }
794 : :
795 : : /*
796 : : * Update the tuple.
797 : : *
798 : : * We still hold the lock after gistinserttuple(), but it
799 : : * might have to split the page to make the updated tuple fit.
800 : : * In that case the updated tuple might migrate to the other
801 : : * half of the split, so we have to go back to the parent and
802 : : * descend back to the half that's a better fit for the new
803 : : * tuple.
804 : : */
4866 heikki.linnakangas@i 805 [ + + ]:CBC 324374 : if (gistinserttuple(&state, stack, giststate, newtup,
806 : : downlinkoffnum))
807 : : {
808 : : /*
809 : : * If this was a root split, the root page continues to be
810 : : * the parent and the updated tuple went to one of the
811 : : * child pages, so we just need to retry from the root
812 : : * page.
813 : : */
5354 814 [ + - ]: 75 : if (stack->blkno != GIST_ROOT_BLKNO)
815 : : {
816 : 75 : UnlockReleaseBuffer(stack->buffer);
817 : 75 : xlocked = false;
818 : 75 : state.stack = stack = stack->parent;
819 : : }
5371 820 : 75 : continue;
821 : : }
822 : : }
823 : 559350 : LockBuffer(stack->buffer, GIST_UNLOCK);
824 : 559350 : xlocked = false;
825 : :
826 : : /* descend to the chosen child */
827 : 559350 : item = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
828 : 559350 : item->blkno = childblkno;
829 : 559350 : item->parent = stack;
5167 830 : 559350 : item->downlinkoffnum = downlinkoffnum;
5371 831 : 559350 : state.stack = stack = item;
832 : : }
833 : : else
834 : : {
835 : : /*
836 : : * Leaf page. Insert the new key. We've already updated all the
837 : : * parents on the way down, but we might have to split the page if
838 : : * it doesn't fit. gistinserttuple() will take care of that.
839 : : */
840 : :
841 : : /*
842 : : * Swap shared lock for an exclusive one. Be careful, the page may
843 : : * change while we unlock/lock the page...
844 : : */
845 [ + - ]: 427363 : if (!xlocked)
846 : : {
847 : 427363 : LockBuffer(stack->buffer, GIST_UNLOCK);
848 : 427363 : LockBuffer(stack->buffer, GIST_EXCLUSIVE);
849 : 427363 : xlocked = true;
8 peter@eisentraut.org 850 :GNC 427363 : stack->page = BufferGetPage(stack->buffer);
5371 heikki.linnakangas@i 851 :CBC 427363 : stack->lsn = PageGetLSN(stack->page);
852 : :
853 [ + + ]: 427363 : if (stack->blkno == GIST_ROOT_BLKNO)
854 : : {
855 : : /*
856 : : * the only page that can become inner instead of leaf is
857 : : * the root page, so for root we should recheck it
858 : : */
859 [ - + ]: 19371 : if (!GistPageIsLeaf(stack->page))
860 : : {
861 : : /*
862 : : * very rare situation: during unlock/lock index with
863 : : * number of pages = 1 was increased
864 : : */
5371 heikki.linnakangas@i 865 :UBC 0 : LockBuffer(stack->buffer, GIST_UNLOCK);
866 : 0 : xlocked = false;
867 : 0 : continue;
868 : : }
869 : :
870 : : /*
871 : : * we don't need to check root split, because checking
872 : : * leaf/inner is enough to recognize split for root
873 : : */
874 : : }
2236 heikki.linnakangas@i 875 [ + - + - ]:CBC 815984 : else if ((GistFollowRight(stack->page) ||
1690 876 : 407992 : stack->parent->lsn < GistPageGetNSN(stack->page)) ||
2236 877 [ - + ]: 407992 : GistPageIsDeleted(stack->page))
878 : : {
879 : : /*
880 : : * The page was split or deleted while we momentarily
881 : : * unlocked the page. Go back to parent.
882 : : */
5371 heikki.linnakangas@i 883 :UBC 0 : UnlockReleaseBuffer(stack->buffer);
884 : 0 : xlocked = false;
885 : 0 : state.stack = stack = stack->parent;
886 : 0 : continue;
887 : : }
888 : : }
889 : :
890 : : /* now state.stack->(page, buffer and blkno) points to leaf page */
891 : :
4866 heikki.linnakangas@i 892 :CBC 427363 : gistinserttuple(&state, stack, giststate, itup,
893 : : InvalidOffsetNumber);
5371 894 : 427357 : LockBuffer(stack->buffer, GIST_UNLOCK);
895 : :
896 : : /* Release any pins we might still hold before exiting */
897 [ + + ]: 1413838 : for (; stack; stack = stack->parent)
898 : 986481 : ReleaseBuffer(stack->buffer);
7389 teodor@sigaev.ru 899 : 427357 : break;
900 : : }
901 : : }
7376 902 : 427357 : }
903 : :
904 : : /*
905 : : * Traverse the tree to find path from root page to specified "child" block.
906 : : *
907 : : * returns a new insertion stack, starting from the parent of "child", up
908 : : * to the root. *downlinkoffnum is set to the offset of the downlink in the
909 : : * direct parent of child.
910 : : *
911 : : * To prevent deadlocks, this should lock only one page at a time.
912 : : */
913 : : static GISTInsertStack *
5167 heikki.linnakangas@i 914 :UBC 0 : gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
915 : : {
916 : : Page page;
917 : : Buffer buffer;
918 : : OffsetNumber i,
919 : : maxoff;
920 : : ItemId iid;
921 : : IndexTuple idxtuple;
922 : : List *fifo;
923 : : GISTInsertStack *top,
924 : : *ptr;
925 : : BlockNumber blkno;
926 : :
927 : 0 : top = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
7376 teodor@sigaev.ru 928 : 0 : top->blkno = GIST_ROOT_BLKNO;
5167 heikki.linnakangas@i 929 : 0 : top->downlinkoffnum = InvalidOffsetNumber;
930 : :
931 : 0 : fifo = list_make1(top);
932 [ # # ]: 0 : while (fifo != NIL)
933 : : {
934 : : /* Get next page to visit */
935 : 0 : top = linitial(fifo);
936 : 0 : fifo = list_delete_first(fifo);
937 : :
7100 tgl@sss.pgh.pa.us 938 : 0 : buffer = ReadBuffer(r, top->blkno);
939 : 0 : LockBuffer(buffer, GIST_SHARE);
7244 940 : 0 : gistcheckpage(r, buffer);
8 peter@eisentraut.org 941 :UNC 0 : page = BufferGetPage(buffer);
942 : :
7289 bruce@momjian.us 943 [ # # ]:UBC 0 : if (GistPageIsLeaf(page))
944 : : {
945 : : /*
946 : : * Because we scan the index top-down, all the rest of the pages
947 : : * in the queue must be leaf pages as well.
948 : : */
7099 tgl@sss.pgh.pa.us 949 : 0 : UnlockReleaseBuffer(buffer);
5167 heikki.linnakangas@i 950 : 0 : break;
951 : : }
952 : :
953 : : /* currently, internal pages are never deleted */
2236 954 [ # # ]: 0 : Assert(!GistPageIsDeleted(page));
955 : :
2797 alvherre@alvh.no-ip. 956 : 0 : top->lsn = BufferGetLSNAtomic(buffer);
957 : :
958 : : /*
959 : : * If F_FOLLOW_RIGHT is set, the page to the right doesn't have a
960 : : * downlink. This should not normally happen..
961 : : */
5371 heikki.linnakangas@i 962 [ # # ]: 0 : if (GistFollowRight(page))
963 [ # # ]: 0 : elog(ERROR, "concurrent GiST page split was incomplete");
964 : :
4615 965 [ # # # # ]: 0 : if (top->parent && top->parent->lsn < GistPageGetNSN(page) &&
7289 bruce@momjian.us 966 [ # # ]: 0 : GistPageGetOpaque(page)->rightlink != InvalidBlockNumber /* sanity check */ )
967 : : {
968 : : /*
969 : : * Page was split while we looked elsewhere. We didn't see the
970 : : * downlink to the right page when we scanned the parent, so add
971 : : * it to the queue now.
972 : : *
973 : : * Put the right page ahead of the queue, so that we visit it
974 : : * next. That's important, because if this is the lowest internal
975 : : * level, just above leaves, we might already have queued up some
976 : : * leaf pages, and we assume that there can't be any non-leaf
977 : : * pages behind leaf pages.
978 : : */
979 : 0 : ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
7376 teodor@sigaev.ru 980 : 0 : ptr->blkno = GistPageGetOpaque(page)->rightlink;
5167 heikki.linnakangas@i 981 : 0 : ptr->downlinkoffnum = InvalidOffsetNumber;
982 : 0 : ptr->parent = top->parent;
983 : :
984 : 0 : fifo = lcons(ptr, fifo);
985 : : }
986 : :
7376 teodor@sigaev.ru 987 : 0 : maxoff = PageGetMaxOffsetNumber(page);
988 : :
7289 bruce@momjian.us 989 [ # # ]: 0 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
990 : : {
7376 teodor@sigaev.ru 991 : 0 : iid = PageGetItemId(page, i);
992 : 0 : idxtuple = (IndexTuple) PageGetItem(page, iid);
993 : 0 : blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
7289 bruce@momjian.us 994 [ # # ]: 0 : if (blkno == child)
995 : : {
996 : : /* Found it! */
7099 tgl@sss.pgh.pa.us 997 : 0 : UnlockReleaseBuffer(buffer);
5167 heikki.linnakangas@i 998 : 0 : *downlinkoffnum = i;
7376 teodor@sigaev.ru 999 : 0 : return top;
1000 : : }
1001 : : else
1002 : : {
1003 : : /* Append this child to the list of pages to visit later */
7289 bruce@momjian.us 1004 : 0 : ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
7376 teodor@sigaev.ru 1005 : 0 : ptr->blkno = blkno;
5167 heikki.linnakangas@i 1006 : 0 : ptr->downlinkoffnum = i;
7376 teodor@sigaev.ru 1007 : 0 : ptr->parent = top;
1008 : :
5167 heikki.linnakangas@i 1009 : 0 : fifo = lappend(fifo, ptr);
1010 : : }
1011 : : }
1012 : :
7099 tgl@sss.pgh.pa.us 1013 : 0 : UnlockReleaseBuffer(buffer);
1014 : : }
1015 : :
5167 heikki.linnakangas@i 1016 [ # # ]: 0 : elog(ERROR, "failed to re-find parent of a page in index \"%s\", block %u",
1017 : : RelationGetRelationName(r), child);
1018 : : return NULL; /* keep compiler quiet */
1019 : : }
1020 : :
1021 : : /*
1022 : : * Updates the stack so that child->parent is the correct parent of the
1023 : : * child. child->parent must be exclusively locked on entry, and will
1024 : : * remain so at exit, but it might not be the same page anymore.
1025 : : */
1026 : : static void
711 heikki.linnakangas@i 1027 :CBC 11950 : gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
1028 : : {
7289 bruce@momjian.us 1029 : 11950 : GISTInsertStack *parent = child->parent;
1030 : : ItemId iid;
1031 : : IndexTuple idxtuple;
1032 : : OffsetNumber maxoff;
1033 : : GISTInsertStack *ptr;
1034 : :
7244 tgl@sss.pgh.pa.us 1035 : 11950 : gistcheckpage(r, parent->buffer);
8 peter@eisentraut.org 1036 :GNC 11950 : parent->page = BufferGetPage(parent->buffer);
711 heikki.linnakangas@i 1037 :CBC 11950 : maxoff = PageGetMaxOffsetNumber(parent->page);
1038 : :
1039 : : /* Check if the downlink is still where it was before */
1040 [ + - + - ]: 11950 : if (child->downlinkoffnum != InvalidOffsetNumber && child->downlinkoffnum <= maxoff)
1041 : : {
1042 : 11950 : iid = PageGetItemId(parent->page, child->downlinkoffnum);
1043 : 11950 : idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
1044 [ + - ]: 11950 : if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
1045 : 11950 : return; /* still there */
1046 : : }
1047 : :
1048 : : /*
1049 : : * The page has changed since we looked. During normal operation, every
1050 : : * update of a page changes its LSN, so the LSN we memorized should have
1051 : : * changed too.
1052 : : *
1053 : : * During index build, however, we don't WAL-log the changes until we have
1054 : : * built the index, so the LSN doesn't change. There is no concurrent
1055 : : * activity during index build, but we might have changed the parent
1056 : : * ourselves.
1057 : : *
1058 : : * We will also get here if child->downlinkoffnum is invalid. That happens
1059 : : * if 'parent' had been updated by an earlier call to this function on its
1060 : : * grandchild, which had to move right.
1061 : : */
155 heikki.linnakangas@i 1062 [ # # # # :LBC (8) : Assert(parent->lsn != PageGetLSN(parent->page) || is_build ||
# # ]
1063 : : child->downlinkoffnum == InvalidOffsetNumber);
1064 : :
1065 : : /*
1066 : : * Scan the page to re-find the downlink. If the page was split, it might
1067 : : * have moved to a different page, so follow the right links until we find
1068 : : * it.
1069 : : */
1070 : : while (true)
711 1071 : (4) : {
1072 : : OffsetNumber i;
1073 : :
1074 : (12) : maxoff = PageGetMaxOffsetNumber(parent->page);
1075 [ # # ]: (60) : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1076 : : {
1077 : (56) : iid = PageGetItemId(parent->page, i);
1078 : (56) : idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
1079 [ # # ]: (56) : if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
1080 : : {
1081 : : /* yes!!, found */
1082 : (8) : child->downlinkoffnum = i;
1083 : (8) : return;
1084 : : }
1085 : : }
1086 : :
1087 : (4) : parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
1088 : (4) : parent->downlinkoffnum = InvalidOffsetNumber;
1089 : (4) : UnlockReleaseBuffer(parent->buffer);
1090 [ # # ]: (4) : if (parent->blkno == InvalidBlockNumber)
1091 : : {
1092 : : /*
1093 : : * End of chain and still didn't find parent. It's a very-very
1094 : : * rare situation when the root was split.
1095 : : */
711 heikki.linnakangas@i 1096 :UBC 0 : break;
1097 : : }
711 heikki.linnakangas@i 1098 :LBC (4) : parent->buffer = ReadBuffer(r, parent->blkno);
1099 : (4) : LockBuffer(parent->buffer, GIST_EXCLUSIVE);
1100 : (4) : gistcheckpage(r, parent->buffer);
8 peter@eisentraut.org 1101 :UNC 0 : parent->page = BufferGetPage(parent->buffer);
1102 : : }
1103 : :
1104 : : /*
1105 : : * awful!!, we need search tree to find parent ... , but before we should
1106 : : * release all old parent
1107 : : */
1108 : :
711 heikki.linnakangas@i 1109 :UBC 0 : ptr = child->parent->parent; /* child->parent already released above */
1110 [ # # ]: 0 : while (ptr)
1111 : : {
1112 : 0 : ReleaseBuffer(ptr->buffer);
1113 : 0 : ptr = ptr->parent;
1114 : : }
1115 : :
1116 : : /* ok, find new path */
1117 : 0 : ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
1118 : :
1119 : : /* read all buffers as expected by caller */
1120 : : /* note we don't lock them or gistcheckpage them here! */
1121 [ # # ]: 0 : while (ptr)
1122 : : {
1123 : 0 : ptr->buffer = ReadBuffer(r, ptr->blkno);
8 peter@eisentraut.org 1124 :UNC 0 : ptr->page = BufferGetPage(ptr->buffer);
711 heikki.linnakangas@i 1125 :UBC 0 : ptr = ptr->parent;
1126 : : }
1127 : :
1128 : : /* install new chain of parents to stack */
1129 : 0 : child->parent = parent;
1130 : :
1131 : : /* make recursive call to normal processing */
1132 : 0 : LockBuffer(child->parent->buffer, GIST_EXCLUSIVE);
1133 : 0 : gistFindCorrectParent(r, child, is_build);
1134 : : }
1135 : :
1136 : : /*
1137 : : * Form a downlink pointer for the page in 'buf'.
1138 : : */
1139 : : static IndexTuple
5371 1140 : 0 : gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate,
1141 : : GISTInsertStack *stack, bool is_build)
1142 : : {
3426 kgrittn@postgresql.o 1143 : 0 : Page page = BufferGetPage(buf);
1144 : : OffsetNumber maxoff;
1145 : : OffsetNumber offset;
5263 bruce@momjian.us 1146 : 0 : IndexTuple downlink = NULL;
1147 : :
5371 heikki.linnakangas@i 1148 : 0 : maxoff = PageGetMaxOffsetNumber(page);
1149 [ # # ]: 0 : for (offset = FirstOffsetNumber; offset <= maxoff; offset = OffsetNumberNext(offset))
1150 : : {
1151 : : IndexTuple ituple = (IndexTuple)
841 tgl@sss.pgh.pa.us 1152 : 0 : PageGetItem(page, PageGetItemId(page, offset));
1153 : :
5371 heikki.linnakangas@i 1154 [ # # ]: 0 : if (downlink == NULL)
1155 : 0 : downlink = CopyIndexTuple(ituple);
1156 : : else
1157 : : {
1158 : : IndexTuple newdownlink;
1159 : :
1160 : 0 : newdownlink = gistgetadjusted(rel, downlink, ituple,
1161 : : giststate);
1162 [ # # ]: 0 : if (newdownlink)
1163 : 0 : downlink = newdownlink;
1164 : : }
1165 : : }
1166 : :
1167 : : /*
1168 : : * If the page is completely empty, we can't form a meaningful downlink
1169 : : * for it. But we have to insert a downlink for the page. Any key will do,
1170 : : * as long as its consistent with the downlink of parent page, so that we
1171 : : * can legally insert it to the parent. A minimal one that matches as few
1172 : : * scans as possible would be best, to keep scans from doing useless work,
1173 : : * but we don't know how to construct that. So we just use the downlink of
1174 : : * the original page that was split - that's as far from optimal as it can
1175 : : * get but will do..
1176 : : */
1177 [ # # ]: 0 : if (!downlink)
1178 : : {
1179 : : ItemId iid;
1180 : :
1181 : 0 : LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE);
711 1182 : 0 : gistFindCorrectParent(rel, stack, is_build);
5167 1183 : 0 : iid = PageGetItemId(stack->parent->page, stack->downlinkoffnum);
5371 1184 : 0 : downlink = (IndexTuple) PageGetItem(stack->parent->page, iid);
1185 : 0 : downlink = CopyIndexTuple(downlink);
1186 : 0 : LockBuffer(stack->parent->buffer, GIST_UNLOCK);
1187 : : }
1188 : :
1189 : 0 : ItemPointerSetBlockNumber(&(downlink->t_tid), BufferGetBlockNumber(buf));
1190 : 0 : GistTupleSetValid(downlink);
1191 : :
1192 : 0 : return downlink;
1193 : : }
1194 : :
1195 : :
1196 : : /*
1197 : : * Complete the incomplete split of state->stack->page.
1198 : : */
1199 : : static void
1200 : 0 : gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
1201 : : {
1202 : 0 : GISTInsertStack *stack = state->stack;
1203 : : Buffer buf;
1204 : : Page page;
1205 : 0 : List *splitinfo = NIL;
1206 : :
1737 peter@eisentraut.org 1207 [ # # ]: 0 : ereport(LOG,
1208 : : (errmsg("fixing incomplete split in index \"%s\", block %u",
1209 : : RelationGetRelationName(state->r), stack->blkno)));
1210 : :
5371 heikki.linnakangas@i 1211 [ # # ]: 0 : Assert(GistFollowRight(stack->page));
5167 1212 [ # # # # : 0 : Assert(OffsetNumberIsValid(stack->downlinkoffnum));
# # ]
1213 : :
5371 1214 : 0 : buf = stack->buffer;
1215 : :
1216 : : /*
1217 : : * Read the chain of split pages, following the rightlinks. Construct a
1218 : : * downlink tuple for each page.
1219 : : */
1220 : : for (;;)
1221 : 0 : {
1222 : 0 : GISTPageSplitInfo *si = palloc(sizeof(GISTPageSplitInfo));
1223 : : IndexTuple downlink;
1224 : :
3426 kgrittn@postgresql.o 1225 : 0 : page = BufferGetPage(buf);
1226 : :
1227 : : /* Form the new downlink tuples to insert to parent */
711 heikki.linnakangas@i 1228 : 0 : downlink = gistformdownlink(state->r, buf, giststate, stack, state->is_build);
1229 : :
5371 1230 : 0 : si->buf = buf;
1231 : 0 : si->downlink = downlink;
1232 : :
1233 : 0 : splitinfo = lappend(splitinfo, si);
1234 : :
1235 [ # # ]: 0 : if (GistFollowRight(page))
1236 : : {
1237 : : /* lock next page */
1238 : 0 : buf = ReadBuffer(state->r, GistPageGetOpaque(page)->rightlink);
1239 : 0 : LockBuffer(buf, GIST_EXCLUSIVE);
1240 : : }
1241 : : else
1242 : 0 : break;
1243 : : }
1244 : :
1245 : : /* Insert the downlinks */
4866 1246 : 0 : gistfinishsplit(state, stack, giststate, splitinfo, false);
5371 1247 : 0 : }
1248 : :
1249 : : /*
1250 : : * Insert or replace a tuple in stack->buffer. If 'oldoffnum' is valid, the
1251 : : * tuple at 'oldoffnum' is replaced, otherwise the tuple is inserted as new.
1252 : : * 'stack' represents the path from the root to the page being updated.
1253 : : *
1254 : : * The caller must hold an exclusive lock on stack->buffer. The lock is still
1255 : : * held on return, but the page might not contain the inserted tuple if the
1256 : : * page was split. The function returns true if the page was split, false
1257 : : * otherwise.
1258 : : */
1259 : : static bool
4866 heikki.linnakangas@i 1260 :CBC 751737 : gistinserttuple(GISTInsertState *state, GISTInsertStack *stack,
1261 : : GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum)
1262 : : {
1263 : 751737 : return gistinserttuples(state, stack, giststate, &tuple, 1, oldoffnum,
1264 : : InvalidBuffer, InvalidBuffer, false, false);
1265 : : }
1266 : :
1267 : : /* ----------------
1268 : : * An extended workhorse version of gistinserttuple(). This version allows
1269 : : * inserting multiple tuples, or replacing a single tuple with multiple tuples.
1270 : : * This is used to recursively update the downlinks in the parent when a page
1271 : : * is split.
1272 : : *
1273 : : * If leftchild and rightchild are valid, we're inserting/replacing the
1274 : : * downlink for rightchild, and leftchild is its left sibling. We clear the
1275 : : * F_FOLLOW_RIGHT flag and update NSN on leftchild, atomically with the
1276 : : * insertion of the downlink.
1277 : : *
1278 : : * To avoid holding locks for longer than necessary, when recursing up the
1279 : : * tree to update the parents, the locking is a bit peculiar here. On entry,
1280 : : * the caller must hold an exclusive lock on stack->buffer, as well as
1281 : : * leftchild and rightchild if given. On return:
1282 : : *
1283 : : * - Lock on stack->buffer is released, if 'unlockbuf' is true. The page is
1284 : : * always kept pinned, however.
1285 : : * - Lock on 'leftchild' is released, if 'unlockleftchild' is true. The page
1286 : : * is kept pinned.
1287 : : * - Lock and pin on 'rightchild' are always released.
1288 : : *
1289 : : * Returns 'true' if the page had to be split. Note that if the page was
1290 : : * split, the inserted/updated tuples might've been inserted to a right
1291 : : * sibling of stack->buffer instead of stack->buffer itself.
1292 : : */
1293 : : static bool
5371 1294 : 763687 : gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
1295 : : GISTSTATE *giststate,
1296 : : IndexTuple *tuples, int ntup, OffsetNumber oldoffnum,
1297 : : Buffer leftchild, Buffer rightchild,
1298 : : bool unlockbuf, bool unlockleftchild)
1299 : : {
1300 : : List *splitinfo;
1301 : : bool is_split;
1302 : :
1303 : : /*
1304 : : * Check for any rw conflicts (in serializable isolation level) just
1305 : : * before we intend to modify the page
1306 : : */
2048 tmunro@postgresql.or 1307 : 763687 : CheckForSerializableConflictIn(state->r, NULL, BufferGetBlockNumber(stack->buffer));
1308 : :
1309 : : /* Insert the tuple(s) to the page, splitting the page if necessary */
5112 heikki.linnakangas@i 1310 : 763681 : is_split = gistplacetopage(state->r, state->freespace, giststate,
1311 : : stack->buffer,
1312 : : tuples, ntup,
1313 : : oldoffnum, NULL,
1314 : : leftchild,
1315 : : &splitinfo,
1316 : : true,
1317 : : state->heapRel,
2348 1318 : 763681 : state->is_build);
1319 : :
1320 : : /*
1321 : : * Before recursing up in case the page was split, release locks on the
1322 : : * child pages. We don't need to keep them locked when updating the
1323 : : * parent.
1324 : : */
4866 1325 [ + + ]: 763681 : if (BufferIsValid(rightchild))
1326 : 11950 : UnlockReleaseBuffer(rightchild);
1327 [ + + + + ]: 763681 : if (BufferIsValid(leftchild) && unlockleftchild)
1328 : 2509 : LockBuffer(leftchild, GIST_UNLOCK);
1329 : :
1330 : : /*
1331 : : * If we had to split, insert/update the downlinks in the parent. If the
1332 : : * caller requested us to release the lock on stack->buffer, tell
1333 : : * gistfinishsplit() to do that as soon as it's safe to do so. If we
1334 : : * didn't have to split, release it ourselves.
1335 : : */
5371 1336 [ + + ]: 763681 : if (splitinfo)
4866 1337 : 11936 : gistfinishsplit(state, stack, giststate, splitinfo, unlockbuf);
1338 [ + + ]: 751745 : else if (unlockbuf)
1339 : 9427 : LockBuffer(stack->buffer, GIST_UNLOCK);
1340 : :
5371 1341 : 763681 : return is_split;
1342 : : }
1343 : :
1344 : : /*
1345 : : * Finish an incomplete split by inserting/updating the downlinks in parent
1346 : : * page. 'splitinfo' contains all the child pages involved in the split,
1347 : : * from left-to-right.
1348 : : *
1349 : : * On entry, the caller must hold a lock on stack->buffer and all the child
1350 : : * pages in 'splitinfo'. If 'unlockbuf' is true, the lock on stack->buffer is
1351 : : * released on return. The child pages are always unlocked and unpinned.
1352 : : */
1353 : : static void
1354 : 11936 : gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
1355 : : GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
1356 : : {
1357 : : GISTPageSplitInfo *right;
1358 : : GISTPageSplitInfo *left;
1359 : : IndexTuple tuples[2];
1360 : :
1361 : : /* A split always contains at least two halves */
1362 [ - + ]: 11936 : Assert(list_length(splitinfo) >= 2);
1363 : :
1364 : : /*
1365 : : * We need to insert downlinks for each new page, and update the downlink
1366 : : * for the original (leftmost) page in the split. Begin at the rightmost
1367 : : * page, inserting one downlink at a time until there's only two pages
1368 : : * left. Finally insert the downlink for the last new page and update the
1369 : : * downlink for the original page as one operation.
1370 : : */
1371 : 11936 : LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE);
1372 : :
1373 : : /*
1374 : : * Insert downlinks for the siblings from right to left, until there are
1375 : : * only two siblings left.
1376 : : */
2243 tgl@sss.pgh.pa.us 1377 [ + + ]: 11950 : for (int pos = list_length(splitinfo) - 1; pos > 1; pos--)
1378 : : {
1379 : 14 : right = (GISTPageSplitInfo *) list_nth(splitinfo, pos);
1380 : 14 : left = (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1);
1381 : :
711 heikki.linnakangas@i 1382 : 14 : gistFindCorrectParent(state->r, stack, state->is_build);
5371 1383 [ - + ]: 14 : if (gistinserttuples(state, stack->parent, giststate,
1384 : : &right->downlink, 1,
1385 : : InvalidOffsetNumber,
1386 : : left->buf, right->buf, false, false))
1387 : : {
1388 : : /*
1389 : : * If the parent page was split, the existing downlink might have
1390 : : * moved.
1391 : : */
2094 heikki.linnakangas@i 1392 :LBC (3) : stack->downlinkoffnum = InvalidOffsetNumber;
1393 : : }
1394 : : /* gistinserttuples() released the lock on right->buf. */
1395 : : }
1396 : :
2243 tgl@sss.pgh.pa.us 1397 :CBC 11936 : right = (GISTPageSplitInfo *) lsecond(splitinfo);
1398 : 11936 : left = (GISTPageSplitInfo *) linitial(splitinfo);
1399 : :
1400 : : /*
1401 : : * Finally insert downlink for the remaining right page and update the
1402 : : * downlink for the original page to not contain the tuples that were
1403 : : * moved to the new pages.
1404 : : */
5371 heikki.linnakangas@i 1405 : 11936 : tuples[0] = left->downlink;
1406 : 11936 : tuples[1] = right->downlink;
711 1407 : 11936 : gistFindCorrectParent(state->r, stack, state->is_build);
1408 : 11936 : (void) gistinserttuples(state, stack->parent, giststate,
1409 : : tuples, 2,
1410 : 11936 : stack->downlinkoffnum,
1411 : : left->buf, right->buf,
1412 : : true, /* Unlock parent */
1413 : : unlockbuf /* Unlock stack->buffer if caller
1414 : : * wants that */
1415 : : );
1416 : :
1417 : : /*
1418 : : * The downlink might have moved when we updated it. Even if the page
1419 : : * wasn't split, because gistinserttuples() implements updating the old
1420 : : * tuple by removing and re-inserting it!
1421 : : */
1422 : 11936 : stack->downlinkoffnum = InvalidOffsetNumber;
1423 : :
5371 1424 [ - + ]: 11936 : Assert(left->buf == stack->buffer);
1425 : :
1426 : : /*
1427 : : * If we split the page because we had to adjust the downlink on an
1428 : : * internal page, while descending the tree for inserting a new tuple,
1429 : : * then this might no longer be the correct page for the new tuple. The
1430 : : * downlink to this page might not cover the new tuple anymore, it might
1431 : : * need to go to the newly-created right sibling instead. Tell the caller
1432 : : * to walk back up the stack, to re-check at the parent which page to
1433 : : * insert to.
1434 : : *
1435 : : * Normally, the LSN-NSN interlock during the tree descend would also
1436 : : * detect that a concurrent split happened (by ourselves), and cause us to
1437 : : * retry at the parent. But that mechanism doesn't work during index
1438 : : * build, because we don't do WAL-logging, and don't update LSNs, during
1439 : : * index build.
1440 : : */
2307 1441 : 11936 : stack->retry_from_parent = true;
7383 teodor@sigaev.ru 1442 : 11936 : }
1443 : :
1444 : : /*
1445 : : * gistSplit -- split a page in the tree and fill struct
1446 : : * used for XLOG and real writes buffers. Function is recursive, ie
1447 : : * it will split page until keys will fit in every page.
1448 : : */
1449 : : SplitPageLayout *
10603 scrappy@hub.org 1450 : 13233 : gistSplit(Relation r,
1451 : : Page page,
1452 : : IndexTuple *itup, /* contains compressed entry */
1453 : : int len,
1454 : : GISTSTATE *giststate)
1455 : : {
1456 : : IndexTuple *lvectup,
1457 : : *rvectup;
1458 : : GistSplitVector v;
1459 : : int i;
613 rhaas@postgresql.org 1460 : 13233 : SplitPageLayout *res = NULL;
1461 : :
1462 : : /* this should never recurse very deeply, but better safe than sorry */
3991 heikki.linnakangas@i 1463 : 13233 : check_stack_depth();
1464 : :
1465 : : /* there's no point in splitting an empty page */
1466 [ - + ]: 13233 : Assert(len > 0);
1467 : :
1468 : : /*
1469 : : * If a single tuple doesn't fit on a page, no amount of splitting will
1470 : : * help.
1471 : : */
1472 [ - + ]: 13233 : if (len == 1)
3991 heikki.linnakangas@i 1473 [ # # ]:UBC 0 : ereport(ERROR,
1474 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1475 : : errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
1476 : : IndexTupleSize(itup[0]), GiSTPageSize,
1477 : : RelationGetRelationName(r))));
1478 : :
2372 akorotkov@postgresql 1479 :CBC 13233 : memset(v.spl_lisnull, true,
1480 : 13233 : sizeof(bool) * giststate->nonLeafTupdesc->natts);
1481 : 13233 : memset(v.spl_risnull, true,
1482 : 13233 : sizeof(bool) * giststate->nonLeafTupdesc->natts);
4591 tgl@sss.pgh.pa.us 1483 : 13233 : gistSplitByKey(r, page, itup, len, giststate, &v, 0);
1484 : :
1485 : : /* form left and right vector */
7059 teodor@sigaev.ru 1486 : 13233 : lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
1487 : 13233 : rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
1488 : :
7010 1489 [ + + ]: 573260 : for (i = 0; i < v.splitVector.spl_nleft; i++)
1490 : 560027 : lvectup[i] = itup[v.splitVector.spl_left[i] - 1];
1491 : :
1492 [ + + ]: 638880 : for (i = 0; i < v.splitVector.spl_nright; i++)
1493 : 625647 : rvectup[i] = itup[v.splitVector.spl_right[i] - 1];
1494 : :
1495 : : /* finalize splitting (may need another split) */
1496 [ + + ]: 13233 : if (!gistfitpage(rvectup, v.splitVector.spl_nright))
1497 : : {
1498 : 344 : res = gistSplit(r, page, rvectup, v.splitVector.spl_nright, giststate);
1499 : : }
1500 : : else
1501 : : {
7059 1502 : 12889 : ROTATEDIST(res);
7010 1503 : 12889 : res->block.num = v.splitVector.spl_nright;
6912 bruce@momjian.us 1504 : 12889 : res->list = gistfillitupvec(rvectup, v.splitVector.spl_nright, &(res->lenlist));
5371 heikki.linnakangas@i 1505 : 12889 : res->itup = gistFormTuple(giststate, r, v.spl_rattr, v.spl_risnull, false);
1506 : : }
1507 : :
7010 teodor@sigaev.ru 1508 [ + + ]: 13233 : if (!gistfitpage(lvectup, v.splitVector.spl_nleft))
1509 : : {
1510 : : SplitPageLayout *resptr,
1511 : : *subres;
1512 : :
1513 : 212 : resptr = subres = gistSplit(r, page, lvectup, v.splitVector.spl_nleft, giststate);
1514 : :
1515 : : /* install on list's tail */
6912 bruce@momjian.us 1516 [ + + ]: 545 : while (resptr->next)
7059 teodor@sigaev.ru 1517 : 333 : resptr = resptr->next;
1518 : :
1519 : 212 : resptr->next = res;
1520 : 212 : res = subres;
1521 : : }
1522 : : else
1523 : : {
1524 : 13021 : ROTATEDIST(res);
7010 1525 : 13021 : res->block.num = v.splitVector.spl_nleft;
6912 bruce@momjian.us 1526 : 13021 : res->list = gistfillitupvec(lvectup, v.splitVector.spl_nleft, &(res->lenlist));
5371 heikki.linnakangas@i 1527 : 13021 : res->itup = gistFormTuple(giststate, r, v.spl_lattr, v.spl_lisnull, false);
1528 : : }
1529 : :
7059 teodor@sigaev.ru 1530 : 13233 : return res;
1531 : : }
1532 : :
1533 : : /*
1534 : : * Create a GISTSTATE and fill it with information about the index
1535 : : */
1536 : : GISTSTATE *
5090 tgl@sss.pgh.pa.us 1537 : 4563 : initGISTstate(Relation index)
1538 : : {
1539 : : GISTSTATE *giststate;
1540 : : MemoryContext scanCxt;
1541 : : MemoryContext oldCxt;
1542 : : int i;
1543 : :
1544 : : /* safety check to protect fixed-size arrays in GISTSTATE */
8782 1545 [ - + ]: 4563 : if (index->rd_att->natts > INDEX_MAX_KEYS)
8083 tgl@sss.pgh.pa.us 1546 [ # # ]:UBC 0 : elog(ERROR, "numberOfAttributes %d > %d",
1547 : : index->rd_att->natts, INDEX_MAX_KEYS);
1548 : :
1549 : : /* Create the memory context that will hold the GISTSTATE */
5090 tgl@sss.pgh.pa.us 1550 :CBC 4563 : scanCxt = AllocSetContextCreate(CurrentMemoryContext,
1551 : : "GiST scan context",
1552 : : ALLOCSET_DEFAULT_SIZES);
1553 : 4563 : oldCxt = MemoryContextSwitchTo(scanCxt);
1554 : :
1555 : : /* Create and fill in the GISTSTATE */
1556 : 4563 : giststate = (GISTSTATE *) palloc(sizeof(GISTSTATE));
1557 : :
1558 : 4563 : giststate->scanCxt = scanCxt;
2999 1559 : 4563 : giststate->tempCxt = scanCxt; /* caller must change this if needed */
2372 akorotkov@postgresql 1560 : 4563 : giststate->leafTupdesc = index->rd_att;
1561 : :
1562 : : /*
1563 : : * The truncated tupdesc for non-leaf index tuples, which doesn't contain
1564 : : * the INCLUDE attributes.
1565 : : *
1566 : : * It is used to form tuples during tuple adjustment and page split.
1567 : : * B-tree creates shortened tuple descriptor for every truncated tuple,
1568 : : * because it is doing this less often: it does not have to form truncated
1569 : : * tuples during page split. Also, B-tree is not adjusting tuples on
1570 : : * internal pages the way GiST does.
1571 : : */
260 drowley@postgresql.o 1572 : 9126 : giststate->nonLeafTupdesc = CreateTupleDescTruncatedCopy(index->rd_att,
1573 : 4563 : IndexRelationGetNumberOfKeyAttributes(index));
1574 : :
2372 akorotkov@postgresql 1575 [ + + ]: 12058 : for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(index); i++)
1576 : : {
8736 tgl@sss.pgh.pa.us 1577 : 7495 : fmgr_info_copy(&(giststate->consistentFn[i]),
7417 neilc@samurai.com 1578 : 7495 : index_getprocinfo(index, i + 1, GIST_CONSISTENT_PROC),
1579 : : scanCxt);
8736 tgl@sss.pgh.pa.us 1580 : 7495 : fmgr_info_copy(&(giststate->unionFn[i]),
8717 bruce@momjian.us 1581 : 7495 : index_getprocinfo(index, i + 1, GIST_UNION_PROC),
1582 : : scanCxt);
1583 : :
1584 : : /* opclasses are not required to provide a Compress method */
2909 tgl@sss.pgh.pa.us 1585 [ + + ]: 7495 : if (OidIsValid(index_getprocid(index, i + 1, GIST_COMPRESS_PROC)))
1586 : 2695 : fmgr_info_copy(&(giststate->compressFn[i]),
1587 : 2695 : index_getprocinfo(index, i + 1, GIST_COMPRESS_PROC),
1588 : : scanCxt);
1589 : : else
1590 : 4800 : giststate->compressFn[i].fn_oid = InvalidOid;
1591 : :
1592 : : /* opclasses are not required to provide a Decompress method */
1593 [ + + ]: 7495 : if (OidIsValid(index_getprocid(index, i + 1, GIST_DECOMPRESS_PROC)))
1594 : 811 : fmgr_info_copy(&(giststate->decompressFn[i]),
1595 : 811 : index_getprocinfo(index, i + 1, GIST_DECOMPRESS_PROC),
1596 : : scanCxt);
1597 : : else
1598 : 6684 : giststate->decompressFn[i].fn_oid = InvalidOid;
1599 : :
8736 1600 : 7495 : fmgr_info_copy(&(giststate->penaltyFn[i]),
8717 bruce@momjian.us 1601 : 7495 : index_getprocinfo(index, i + 1, GIST_PENALTY_PROC),
1602 : : scanCxt);
8736 tgl@sss.pgh.pa.us 1603 : 7495 : fmgr_info_copy(&(giststate->picksplitFn[i]),
7417 neilc@samurai.com 1604 : 7495 : index_getprocinfo(index, i + 1, GIST_PICKSPLIT_PROC),
1605 : : scanCxt);
8736 tgl@sss.pgh.pa.us 1606 : 7495 : fmgr_info_copy(&(giststate->equalFn[i]),
8717 bruce@momjian.us 1607 : 7495 : index_getprocinfo(index, i + 1, GIST_EQUAL_PROC),
1608 : : scanCxt);
1609 : :
1610 : : /* opclasses are not required to provide a Distance method */
5391 tgl@sss.pgh.pa.us 1611 [ + + ]: 7495 : if (OidIsValid(index_getprocid(index, i + 1, GIST_DISTANCE_PROC)))
1612 : 957 : fmgr_info_copy(&(giststate->distanceFn[i]),
2999 1613 : 957 : index_getprocinfo(index, i + 1, GIST_DISTANCE_PROC),
1614 : : scanCxt);
1615 : : else
5391 1616 : 6538 : giststate->distanceFn[i].fn_oid = InvalidOid;
1617 : :
1618 : : /* opclasses are not required to provide a Fetch method */
3817 heikki.linnakangas@i 1619 [ + + ]: 7495 : if (OidIsValid(index_getprocid(index, i + 1, GIST_FETCH_PROC)))
1620 : 689 : fmgr_info_copy(&(giststate->fetchFn[i]),
3759 bruce@momjian.us 1621 : 689 : index_getprocinfo(index, i + 1, GIST_FETCH_PROC),
1622 : : scanCxt);
1623 : : else
3817 heikki.linnakangas@i 1624 : 6806 : giststate->fetchFn[i].fn_oid = InvalidOid;
1625 : :
1626 : : /*
1627 : : * If the index column has a specified collation, we should honor that
1628 : : * while doing comparisons. However, we may have a collatable storage
1629 : : * type for a noncollatable indexed data type. If there's no index
1630 : : * collation then specify default collation in case the support
1631 : : * functions need collation. This is harmless if the support
1632 : : * functions don't care about collation, so we just do it
1633 : : * unconditionally. (We could alternatively call get_typcollation,
1634 : : * but that seems like expensive overkill --- there aren't going to be
1635 : : * any cases where a GiST storage type has a nondefault collation.)
1636 : : */
5251 tgl@sss.pgh.pa.us 1637 [ + + ]: 7495 : if (OidIsValid(index->rd_indcollation[i]))
1638 : 97 : giststate->supportCollation[i] = index->rd_indcollation[i];
1639 : : else
1640 : 7398 : giststate->supportCollation[i] = DEFAULT_COLLATION_OID;
1641 : : }
1642 : :
1643 : : /* No opclass information for INCLUDE attributes */
2372 akorotkov@postgresql 1644 [ + + ]: 4814 : for (; i < index->rd_att->natts; i++)
1645 : : {
1646 : 251 : giststate->consistentFn[i].fn_oid = InvalidOid;
1647 : 251 : giststate->unionFn[i].fn_oid = InvalidOid;
1648 : 251 : giststate->compressFn[i].fn_oid = InvalidOid;
1649 : 251 : giststate->decompressFn[i].fn_oid = InvalidOid;
1650 : 251 : giststate->penaltyFn[i].fn_oid = InvalidOid;
1651 : 251 : giststate->picksplitFn[i].fn_oid = InvalidOid;
1652 : 251 : giststate->equalFn[i].fn_oid = InvalidOid;
1653 : 251 : giststate->distanceFn[i].fn_oid = InvalidOid;
1654 : 251 : giststate->fetchFn[i].fn_oid = InvalidOid;
1655 : 251 : giststate->supportCollation[i] = InvalidOid;
1656 : : }
1657 : :
5090 tgl@sss.pgh.pa.us 1658 : 4563 : MemoryContextSwitchTo(oldCxt);
1659 : :
1660 : 4563 : return giststate;
1661 : : }
1662 : :
1663 : : void
8717 bruce@momjian.us 1664 : 3501 : freeGISTstate(GISTSTATE *giststate)
1665 : : {
1666 : : /* It's sufficient to delete the scanCxt */
5090 tgl@sss.pgh.pa.us 1667 : 3501 : MemoryContextDelete(giststate->scanCxt);
10603 scrappy@hub.org 1668 : 3501 : }
1669 : :
1670 : : /*
1671 : : * gistprunepage() -- try to remove LP_DEAD items from the given page.
1672 : : * Function assumes that buffer is exclusively locked.
1673 : : */
1674 : : static void
2377 heikki.linnakangas@i 1675 :UBC 0 : gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
1676 : : {
1677 : : OffsetNumber deletable[MaxIndexTuplesPerPage];
3376 rhaas@postgresql.org 1678 : 0 : int ndeletable = 0;
1679 : : OffsetNumber offnum,
1680 : : maxoff;
1681 : :
3650 teodor@sigaev.ru 1682 [ # # ]: 0 : Assert(GistPageIsLeaf(page));
1683 : :
1684 : : /*
1685 : : * Scan over all items to see which ones need to be deleted according to
1686 : : * LP_DEAD flags.
1687 : : */
1688 : 0 : maxoff = PageGetMaxOffsetNumber(page);
1689 : 0 : for (offnum = FirstOffsetNumber;
1690 [ # # ]: 0 : offnum <= maxoff;
1691 : 0 : offnum = OffsetNumberNext(offnum))
1692 : : {
1693 : 0 : ItemId itemId = PageGetItemId(page, offnum);
1694 : :
1695 [ # # ]: 0 : if (ItemIdIsDead(itemId))
1696 : 0 : deletable[ndeletable++] = offnum;
1697 : : }
1698 : :
1699 [ # # ]: 0 : if (ndeletable > 0)
1700 : : {
1024 pg@bowt.ie 1701 : 0 : TransactionId snapshotConflictHorizon = InvalidTransactionId;
1702 : :
1684 1703 [ # # # # : 0 : if (XLogStandbyInfoActive() && RelationNeedsWAL(rel))
# # # # #
# ]
1704 : : snapshotConflictHorizon =
1705 : 0 : index_compute_xid_horizon_for_tuples(rel, heapRel, buffer,
1706 : : deletable, ndeletable);
1707 : :
3650 teodor@sigaev.ru 1708 : 0 : START_CRIT_SECTION();
1709 : :
1710 : 0 : PageIndexMultiDelete(page, deletable, ndeletable);
1711 : :
1712 : : /*
1713 : : * Mark the page as not containing any LP_DEAD items. This is not
1714 : : * certainly true (there might be some that have recently been marked,
1715 : : * but weren't included in our target-item list), but it will almost
1716 : : * always be true and it doesn't seem worth an additional page scan to
1717 : : * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
1718 : : */
1719 : 0 : GistClearPageHasGarbage(page);
1720 : :
1721 : 0 : MarkBufferDirty(buffer);
1722 : :
1723 : : /* XLOG stuff */
1724 [ # # # # : 0 : if (RelationNeedsWAL(rel))
# # # # ]
1725 : 0 : {
1726 : : XLogRecPtr recptr;
1727 : :
2451 akorotkov@postgresql 1728 : 0 : recptr = gistXLogDelete(buffer,
1729 : : deletable, ndeletable,
1730 : : snapshotConflictHorizon,
1731 : : heapRel);
1732 : :
3650 teodor@sigaev.ru 1733 : 0 : PageSetLSN(page, recptr);
1734 : : }
1735 : : else
1736 : 0 : PageSetLSN(page, gistGetFakeLSN(rel));
1737 : :
1738 [ # # ]: 0 : END_CRIT_SECTION();
1739 : : }
1740 : :
1741 : : /*
1742 : : * Note: if we didn't find any LP_DEAD items, then the page's
1743 : : * F_HAS_GARBAGE hint bit is falsely set. We do not bother expending a
1744 : : * separate write to clear it, however. We will clear it when we split
1745 : : * the page.
1746 : : */
1747 : 0 : }
|
