Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * spgvacuum.c
4 : : * vacuum for SP-GiST
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/spgist/spgvacuum.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : :
16 : : #include "postgres.h"
17 : :
18 : : #include "access/genam.h"
19 : : #include "access/spgist_private.h"
20 : : #include "access/spgxlog.h"
21 : : #include "access/transam.h"
22 : : #include "access/xloginsert.h"
23 : : #include "commands/vacuum.h"
24 : : #include "miscadmin.h"
25 : : #include "storage/bufmgr.h"
26 : : #include "storage/indexfsm.h"
27 : : #include "storage/lmgr.h"
28 : : #include "utils/snapmgr.h"
29 : :
30 : :
31 : : /* Entry in pending-list of TIDs we need to revisit */
32 : : typedef struct spgVacPendingItem
33 : : {
34 : : ItemPointerData tid; /* redirection target to visit */
35 : : bool done; /* have we dealt with this? */
36 : : struct spgVacPendingItem *next; /* list link */
37 : : } spgVacPendingItem;
38 : :
39 : : /* Local state for vacuum operations */
40 : : typedef struct spgBulkDeleteState
41 : : {
42 : : /* Parameters passed in to spgvacuumscan */
43 : : IndexVacuumInfo *info;
44 : : IndexBulkDeleteResult *stats;
45 : : IndexBulkDeleteCallback callback;
46 : : void *callback_state;
47 : :
48 : : /* Additional working state */
49 : : SpGistState spgstate; /* for SPGiST operations that need one */
50 : : spgVacPendingItem *pendingList; /* TIDs we need to (re)visit */
51 : : TransactionId myXmin; /* for detecting newly-added redirects */
52 : : BlockNumber lastFilledBlock; /* last non-deletable block */
53 : : } spgBulkDeleteState;
54 : :
55 : :
56 : : /*
57 : : * Add TID to pendingList, but only if not already present.
58 : : *
59 : : * Note that new items are always appended at the end of the list; this
60 : : * ensures that scans of the list don't miss items added during the scan.
61 : : */
62 : : static void
4416 tgl@sss.pgh.pa.us 63 :CBC 51879 : spgAddPendingTID(spgBulkDeleteState *bds, ItemPointer tid)
64 : : {
65 : : spgVacPendingItem *pitem;
66 : : spgVacPendingItem **listLink;
67 : :
68 : : /* search the list for pre-existing entry */
69 : 51879 : listLink = &bds->pendingList;
70 [ + + ]: 4582908 : while (*listLink != NULL)
71 : : {
72 : 4548059 : pitem = *listLink;
73 [ + + ]: 4548059 : if (ItemPointerEquals(tid, &pitem->tid))
74 : 17030 : return; /* already in list, do nothing */
75 : 4531029 : listLink = &pitem->next;
76 : : }
77 : : /* not there, so append new entry */
78 : 34849 : pitem = (spgVacPendingItem *) palloc(sizeof(spgVacPendingItem));
79 : 34849 : pitem->tid = *tid;
80 : 34849 : pitem->done = false;
81 : 34849 : pitem->next = NULL;
82 : 34849 : *listLink = pitem;
83 : : }
84 : :
85 : : /*
86 : : * Clear pendingList
87 : : */
88 : : static void
89 : 263 : spgClearPendingList(spgBulkDeleteState *bds)
90 : : {
91 : : spgVacPendingItem *pitem;
92 : : spgVacPendingItem *nitem;
93 : :
94 [ + + ]: 35112 : for (pitem = bds->pendingList; pitem != NULL; pitem = nitem)
95 : : {
96 : 34849 : nitem = pitem->next;
97 : : /* All items in list should have been dealt with */
98 [ - + ]: 34849 : Assert(pitem->done);
99 : 34849 : pfree(pitem);
100 : : }
101 : 263 : bds->pendingList = NULL;
102 : 263 : }
103 : :
104 : : /*
105 : : * Vacuum a regular (non-root) leaf page
106 : : *
107 : : * We must delete tuples that are targeted for deletion by the VACUUM,
108 : : * but not move any tuples that are referenced by outside links; we assume
109 : : * those are the ones that are heads of chains.
110 : : *
111 : : * If we find a REDIRECT that was made by a concurrently-running transaction,
112 : : * we must add its target TID to pendingList. (We don't try to visit the
113 : : * target immediately, first because we don't want VACUUM locking more than
114 : : * one buffer at a time, and second because the duplicate-filtering logic
115 : : * in spgAddPendingTID is useful to ensure we can't get caught in an infinite
116 : : * loop in the face of continuous concurrent insertions.)
117 : : *
118 : : * If forPending is true, we are examining the page as a consequence of
119 : : * chasing a redirect link, not as part of the normal sequential scan.
120 : : * We still vacuum the page normally, but we don't increment the stats
121 : : * about live tuples; else we'd double-count those tuples, since the page
122 : : * has been or will be visited in the sequential scan as well.
123 : : */
124 : : static void
125 : 19842 : vacuumLeafPage(spgBulkDeleteState *bds, Relation index, Buffer buffer,
126 : : bool forPending)
127 : : {
2916 kgrittn@postgresql.o 128 : 19842 : Page page = BufferGetPage(buffer);
129 : : spgxlogVacuumLeaf xlrec;
130 : : OffsetNumber toDead[MaxIndexTuplesPerPage];
131 : : OffsetNumber toPlaceholder[MaxIndexTuplesPerPage];
132 : : OffsetNumber moveSrc[MaxIndexTuplesPerPage];
133 : : OffsetNumber moveDest[MaxIndexTuplesPerPage];
134 : : OffsetNumber chainSrc[MaxIndexTuplesPerPage];
135 : : OffsetNumber chainDest[MaxIndexTuplesPerPage];
136 : : OffsetNumber predecessor[MaxIndexTuplesPerPage + 1];
137 : : bool deletable[MaxIndexTuplesPerPage + 1];
138 : : int nDeletable;
139 : : OffsetNumber i,
4502 tgl@sss.pgh.pa.us 140 : 19842 : max = PageGetMaxOffsetNumber(page);
141 : :
142 : 19842 : memset(predecessor, 0, sizeof(predecessor));
143 : 19842 : memset(deletable, 0, sizeof(deletable));
144 : 19842 : nDeletable = 0;
145 : :
146 : : /* Scan page, identify tuples to delete, accumulate stats */
147 [ + + ]: 3142016 : for (i = FirstOffsetNumber; i <= max; i++)
148 : : {
149 : : SpGistLeafTuple lt;
150 : :
151 : 3122174 : lt = (SpGistLeafTuple) PageGetItem(page,
152 : : PageGetItemId(page, i));
153 [ + + ]: 3122174 : if (lt->tupstate == SPGIST_LIVE)
154 : : {
155 [ - + ]: 2975881 : Assert(ItemPointerIsValid(<->heapPtr));
156 : :
157 [ + + ]: 2975881 : if (bds->callback(<->heapPtr, bds->callback_state))
158 : : {
159 : 48020 : bds->stats->tuples_removed += 1;
160 : 48020 : deletable[i] = true;
161 : 48020 : nDeletable++;
162 : : }
163 : : else
164 : : {
4416 165 [ + + ]: 2927861 : if (!forPending)
166 : 306905 : bds->stats->num_index_tuples += 1;
167 : : }
168 : :
169 : : /* Form predecessor map, too */
1105 170 [ + + ]: 2975881 : if (SGLT_GET_NEXTOFFSET(lt) != InvalidOffsetNumber)
171 : : {
172 : : /* paranoia about corrupted chain links */
173 [ + - ]: 2950484 : if (SGLT_GET_NEXTOFFSET(lt) < FirstOffsetNumber ||
174 [ + - ]: 2950484 : SGLT_GET_NEXTOFFSET(lt) > max ||
175 [ - + ]: 2950484 : predecessor[SGLT_GET_NEXTOFFSET(lt)] != InvalidOffsetNumber)
4502 tgl@sss.pgh.pa.us 176 [ # # ]:UBC 0 : elog(ERROR, "inconsistent tuple chain links in page %u of index \"%s\"",
177 : : BufferGetBlockNumber(buffer),
178 : : RelationGetRelationName(index));
1105 tgl@sss.pgh.pa.us 179 :CBC 2950484 : predecessor[SGLT_GET_NEXTOFFSET(lt)] = i;
180 : : }
181 : : }
4416 182 [ + + ]: 146293 : else if (lt->tupstate == SPGIST_REDIRECT)
183 : : {
184 : 17818 : SpGistDeadTuple dt = (SpGistDeadTuple) lt;
185 : :
1105 186 [ - + ]: 17818 : Assert(SGLT_GET_NEXTOFFSET(dt) == InvalidOffsetNumber);
4416 187 [ - + ]: 17818 : Assert(ItemPointerIsValid(&dt->pointer));
188 : :
189 : : /*
190 : : * Add target TID to pending list if the redirection could have
191 : : * happened since VACUUM started.
192 : : *
193 : : * Note: we could make a tighter test by seeing if the xid is
194 : : * "running" according to the active snapshot; but snapmgr.c
195 : : * doesn't currently export a suitable API, and it's not entirely
196 : : * clear that a tighter test is worth the cycles anyway.
197 : : */
198 [ + + ]: 17818 : if (TransactionIdFollowsOrEquals(dt->xid, bds->myXmin))
199 : 17293 : spgAddPendingTID(bds, &dt->pointer);
200 : : }
201 : : else
202 : : {
1105 203 [ - + ]: 128475 : Assert(SGLT_GET_NEXTOFFSET(lt) == InvalidOffsetNumber);
204 : : }
205 : : }
206 : :
4502 207 [ + + ]: 19842 : if (nDeletable == 0)
208 : 19393 : return; /* nothing more to do */
209 : :
210 : : /*----------
211 : : * Figure out exactly what we have to do. We do this separately from
212 : : * actually modifying the page, mainly so that we have a representation
213 : : * that can be dumped into WAL and then the replay code can do exactly
214 : : * the same thing. The output of this step consists of six arrays
215 : : * describing four kinds of operations, to be performed in this order:
216 : : *
217 : : * toDead[]: tuple numbers to be replaced with DEAD tuples
218 : : * toPlaceholder[]: tuple numbers to be replaced with PLACEHOLDER tuples
219 : : * moveSrc[]: tuple numbers that need to be relocated to another offset
220 : : * (replacing the tuple there) and then replaced with PLACEHOLDER tuples
221 : : * moveDest[]: new locations for moveSrc tuples
222 : : * chainSrc[]: tuple numbers whose chain links (nextOffset) need updates
223 : : * chainDest[]: new values of nextOffset for chainSrc members
224 : : *
225 : : * It's easiest to figure out what we have to do by processing tuple
226 : : * chains, so we iterate over all the tuples (not just the deletable
227 : : * ones!) to identify chain heads, then chase down each chain and make
228 : : * work item entries for deletable tuples within the chain.
229 : : *----------
230 : : */
231 : 449 : xlrec.nDead = xlrec.nPlaceholder = xlrec.nMove = xlrec.nChain = 0;
232 : :
233 [ + + ]: 99338 : for (i = FirstOffsetNumber; i <= max; i++)
234 : : {
235 : : SpGistLeafTuple head;
236 : : bool interveningDeletable;
237 : : OffsetNumber prevLive;
238 : : OffsetNumber j;
239 : :
240 : 98889 : head = (SpGistLeafTuple) PageGetItem(page,
241 : : PageGetItemId(page, i));
242 [ + + ]: 98889 : if (head->tupstate != SPGIST_LIVE)
243 : 30922 : continue; /* can't be a chain member */
244 [ + + ]: 67967 : if (predecessor[i] != 0)
245 : 67499 : continue; /* not a chain head */
246 : :
247 : : /* initialize ... */
248 : 468 : interveningDeletable = false;
249 [ + + ]: 468 : prevLive = deletable[i] ? InvalidOffsetNumber : i;
250 : :
251 : : /* scan down the chain ... */
1105 252 : 468 : j = SGLT_GET_NEXTOFFSET(head);
4502 253 [ + + ]: 67967 : while (j != InvalidOffsetNumber)
254 : : {
255 : : SpGistLeafTuple lt;
256 : :
257 : 67499 : lt = (SpGistLeafTuple) PageGetItem(page,
258 : : PageGetItemId(page, j));
259 [ - + ]: 67499 : if (lt->tupstate != SPGIST_LIVE)
260 : : {
261 : : /* all tuples in chain should be live */
4502 tgl@sss.pgh.pa.us 262 [ # # ]:UBC 0 : elog(ERROR, "unexpected SPGiST tuple state: %d",
263 : : lt->tupstate);
264 : : }
265 : :
4502 tgl@sss.pgh.pa.us 266 [ + + ]:CBC 67499 : if (deletable[j])
267 : : {
268 : : /* This tuple should be replaced by a placeholder */
269 : 47583 : toPlaceholder[xlrec.nPlaceholder] = j;
270 : 47583 : xlrec.nPlaceholder++;
271 : : /* previous live tuple's chain link will need an update */
272 : 47583 : interveningDeletable = true;
273 : : }
274 [ + + ]: 19916 : else if (prevLive == InvalidOffsetNumber)
275 : : {
276 : : /*
277 : : * This is the first live tuple in the chain. It has to move
278 : : * to the head position.
279 : : */
280 : 437 : moveSrc[xlrec.nMove] = j;
281 : 437 : moveDest[xlrec.nMove] = i;
282 : 437 : xlrec.nMove++;
283 : : /* Chain updates will be applied after the move */
284 : 437 : prevLive = i;
285 : 437 : interveningDeletable = false;
286 : : }
287 : : else
288 : : {
289 : : /*
290 : : * Second or later live tuple. Arrange to re-chain it to the
291 : : * previous live one, if there was a gap.
292 : : */
293 [ + + ]: 19479 : if (interveningDeletable)
294 : : {
295 : 14620 : chainSrc[xlrec.nChain] = prevLive;
296 : 14620 : chainDest[xlrec.nChain] = j;
297 : 14620 : xlrec.nChain++;
298 : : }
299 : 19479 : prevLive = j;
300 : 19479 : interveningDeletable = false;
301 : : }
302 : :
1105 303 : 67499 : j = SGLT_GET_NEXTOFFSET(lt);
304 : : }
305 : :
4502 306 [ - + ]: 468 : if (prevLive == InvalidOffsetNumber)
307 : : {
308 : : /* The chain is entirely removable, so we need a DEAD tuple */
4502 tgl@sss.pgh.pa.us 309 :UBC 0 : toDead[xlrec.nDead] = i;
310 : 0 : xlrec.nDead++;
311 : : }
4502 tgl@sss.pgh.pa.us 312 [ + + ]:CBC 468 : else if (interveningDeletable)
313 : : {
314 : : /* One or more deletions at end of chain, so close it off */
315 : 454 : chainSrc[xlrec.nChain] = prevLive;
316 : 454 : chainDest[xlrec.nChain] = InvalidOffsetNumber;
317 : 454 : xlrec.nChain++;
318 : : }
319 : : }
320 : :
321 : : /* sanity check ... */
322 [ - + ]: 449 : if (nDeletable != xlrec.nDead + xlrec.nPlaceholder + xlrec.nMove)
4502 tgl@sss.pgh.pa.us 323 [ # # ]:UBC 0 : elog(ERROR, "inconsistent counts of deletable tuples");
324 : :
325 : : /* Do the updates */
4502 tgl@sss.pgh.pa.us 326 :CBC 449 : START_CRIT_SECTION();
327 : :
328 : 449 : spgPageIndexMultiDelete(&bds->spgstate, page,
329 : 449 : toDead, xlrec.nDead,
330 : : SPGIST_DEAD, SPGIST_DEAD,
331 : : InvalidBlockNumber, InvalidOffsetNumber);
332 : :
333 : 449 : spgPageIndexMultiDelete(&bds->spgstate, page,
334 : 449 : toPlaceholder, xlrec.nPlaceholder,
335 : : SPGIST_PLACEHOLDER, SPGIST_PLACEHOLDER,
336 : : InvalidBlockNumber, InvalidOffsetNumber);
337 : :
338 : : /*
339 : : * We implement the move step by swapping the line pointers of the source
340 : : * and target tuples, then replacing the newly-source tuples with
341 : : * placeholders. This is perhaps unduly friendly with the page data
342 : : * representation, but it's fast and doesn't risk page overflow when a
343 : : * tuple to be relocated is large.
344 : : */
345 [ + + ]: 886 : for (i = 0; i < xlrec.nMove; i++)
346 : : {
347 : 437 : ItemId idSrc = PageGetItemId(page, moveSrc[i]);
348 : 437 : ItemId idDest = PageGetItemId(page, moveDest[i]);
349 : : ItemIdData tmp;
350 : :
351 : 437 : tmp = *idSrc;
352 : 437 : *idSrc = *idDest;
353 : 437 : *idDest = tmp;
354 : : }
355 : :
356 : 449 : spgPageIndexMultiDelete(&bds->spgstate, page,
357 : 449 : moveSrc, xlrec.nMove,
358 : : SPGIST_PLACEHOLDER, SPGIST_PLACEHOLDER,
359 : : InvalidBlockNumber, InvalidOffsetNumber);
360 : :
361 [ + + ]: 15523 : for (i = 0; i < xlrec.nChain; i++)
362 : : {
363 : : SpGistLeafTuple lt;
364 : :
365 : 15074 : lt = (SpGistLeafTuple) PageGetItem(page,
366 : 15074 : PageGetItemId(page, chainSrc[i]));
367 [ - + ]: 15074 : Assert(lt->tupstate == SPGIST_LIVE);
1105 368 : 15074 : SGLT_SET_NEXTOFFSET(lt, chainDest[i]);
369 : : }
370 : :
4502 371 : 449 : MarkBufferDirty(buffer);
372 : :
373 [ + - + + : 449 : if (RelationNeedsWAL(index))
+ - + - ]
374 : : {
375 : : XLogRecPtr recptr;
376 : :
3433 heikki.linnakangas@i 377 : 449 : XLogBeginInsert();
378 : :
379 : 449 : STORE_STATE(&bds->spgstate, xlrec.stateSrc);
380 : :
381 : 449 : XLogRegisterData((char *) &xlrec, SizeOfSpgxlogVacuumLeaf);
382 : : /* sizeof(xlrec) should be a multiple of sizeof(OffsetNumber) */
383 : 449 : XLogRegisterData((char *) toDead, sizeof(OffsetNumber) * xlrec.nDead);
384 : 449 : XLogRegisterData((char *) toPlaceholder, sizeof(OffsetNumber) * xlrec.nPlaceholder);
385 : 449 : XLogRegisterData((char *) moveSrc, sizeof(OffsetNumber) * xlrec.nMove);
386 : 449 : XLogRegisterData((char *) moveDest, sizeof(OffsetNumber) * xlrec.nMove);
387 : 449 : XLogRegisterData((char *) chainSrc, sizeof(OffsetNumber) * xlrec.nChain);
388 : 449 : XLogRegisterData((char *) chainDest, sizeof(OffsetNumber) * xlrec.nChain);
389 : :
390 : 449 : XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);
391 : :
392 : 449 : recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_VACUUM_LEAF);
393 : :
4502 tgl@sss.pgh.pa.us 394 : 449 : PageSetLSN(page, recptr);
395 : : }
396 : :
397 [ - + ]: 449 : END_CRIT_SECTION();
398 : : }
399 : :
400 : : /*
401 : : * Vacuum a root page when it is also a leaf
402 : : *
403 : : * On the root, we just delete any dead leaf tuples; no fancy business
404 : : */
405 : : static void
406 : 16 : vacuumLeafRoot(spgBulkDeleteState *bds, Relation index, Buffer buffer)
407 : : {
2916 kgrittn@postgresql.o 408 : 16 : Page page = BufferGetPage(buffer);
409 : : spgxlogVacuumRoot xlrec;
410 : : OffsetNumber toDelete[MaxIndexTuplesPerPage];
411 : : OffsetNumber i,
4502 tgl@sss.pgh.pa.us 412 : 16 : max = PageGetMaxOffsetNumber(page);
413 : :
414 : 16 : xlrec.nDelete = 0;
415 : :
416 : : /* Scan page, identify tuples to delete, accumulate stats */
417 [ + + ]: 82 : for (i = FirstOffsetNumber; i <= max; i++)
418 : : {
419 : : SpGistLeafTuple lt;
420 : :
421 : 66 : lt = (SpGistLeafTuple) PageGetItem(page,
422 : : PageGetItemId(page, i));
423 [ + - ]: 66 : if (lt->tupstate == SPGIST_LIVE)
424 : : {
425 [ - + ]: 66 : Assert(ItemPointerIsValid(<->heapPtr));
426 : :
427 [ - + ]: 66 : if (bds->callback(<->heapPtr, bds->callback_state))
428 : : {
4502 tgl@sss.pgh.pa.us 429 :UBC 0 : bds->stats->tuples_removed += 1;
430 : 0 : toDelete[xlrec.nDelete] = i;
431 : 0 : xlrec.nDelete++;
432 : : }
433 : : else
434 : : {
4502 tgl@sss.pgh.pa.us 435 :CBC 66 : bds->stats->num_index_tuples += 1;
436 : : }
437 : : }
438 : : else
439 : : {
440 : : /* all tuples on root should be live */
4502 tgl@sss.pgh.pa.us 441 [ # # ]:UBC 0 : elog(ERROR, "unexpected SPGiST tuple state: %d",
442 : : lt->tupstate);
443 : : }
444 : : }
445 : :
4502 tgl@sss.pgh.pa.us 446 [ + - ]:CBC 16 : if (xlrec.nDelete == 0)
447 : 16 : return; /* nothing more to do */
448 : :
449 : : /* Do the update */
4502 tgl@sss.pgh.pa.us 450 :UBC 0 : START_CRIT_SECTION();
451 : :
452 : : /* The tuple numbers are in order, so we can use PageIndexMultiDelete */
453 : 0 : PageIndexMultiDelete(page, toDelete, xlrec.nDelete);
454 : :
455 : 0 : MarkBufferDirty(buffer);
456 : :
457 [ # # # # : 0 : if (RelationNeedsWAL(index))
# # # # ]
458 : : {
459 : : XLogRecPtr recptr;
460 : :
3433 heikki.linnakangas@i 461 : 0 : XLogBeginInsert();
462 : :
463 : : /* Prepare WAL record */
464 : 0 : STORE_STATE(&bds->spgstate, xlrec.stateSrc);
465 : :
466 : 0 : XLogRegisterData((char *) &xlrec, SizeOfSpgxlogVacuumRoot);
467 : : /* sizeof(xlrec) should be a multiple of sizeof(OffsetNumber) */
468 : 0 : XLogRegisterData((char *) toDelete,
469 : 0 : sizeof(OffsetNumber) * xlrec.nDelete);
470 : :
471 : 0 : XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);
472 : :
473 : 0 : recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_VACUUM_ROOT);
474 : :
4502 tgl@sss.pgh.pa.us 475 : 0 : PageSetLSN(page, recptr);
476 : : }
477 : :
478 [ # # ]: 0 : END_CRIT_SECTION();
479 : : }
480 : :
481 : : /*
482 : : * Clean up redirect and placeholder tuples on the given page
483 : : *
484 : : * Redirect tuples can be marked placeholder once they're old enough.
485 : : * Placeholder tuples can be removed if it won't change the offsets of
486 : : * non-placeholder ones.
487 : : *
488 : : * Unlike the routines above, this works on both leaf and inner pages.
489 : : */
490 : : static void
379 andres@anarazel.de 491 :CBC 19937 : vacuumRedirectAndPlaceholder(Relation index, Relation heaprel, Buffer buffer)
492 : : {
2916 kgrittn@postgresql.o 493 : 19937 : Page page = BufferGetPage(buffer);
4502 tgl@sss.pgh.pa.us 494 : 19937 : SpGistPageOpaque opaque = SpGistPageGetOpaque(page);
495 : : OffsetNumber i,
496 : 19937 : max = PageGetMaxOffsetNumber(page),
497 : 19937 : firstPlaceholder = InvalidOffsetNumber;
498 : 19937 : bool hasNonPlaceholder = false;
499 : 19937 : bool hasUpdate = false;
500 : : OffsetNumber itemToPlaceholder[MaxIndexTuplesPerPage];
501 : : OffsetNumber itemnos[MaxIndexTuplesPerPage];
502 : : spgxlogVacuumRedirect xlrec;
503 : : GlobalVisState *vistest;
504 : :
378 andres@anarazel.de 505 [ - + - - : 19937 : xlrec.isCatalogRel = RelationIsAccessibleInLogicalDecoding(heaprel);
- - - - -
- - - - -
- - - - -
- ]
4502 tgl@sss.pgh.pa.us 506 : 19937 : xlrec.nToPlaceholder = 0;
514 pg@bowt.ie 507 : 19937 : xlrec.snapshotConflictHorizon = InvalidTransactionId;
508 : :
377 509 : 19937 : vistest = GlobalVisTestFor(heaprel);
510 : :
4502 tgl@sss.pgh.pa.us 511 : 19937 : START_CRIT_SECTION();
512 : :
513 : : /*
514 : : * Scan backwards to convert old redirection tuples to placeholder tuples,
515 : : * and identify location of last non-placeholder tuple while at it.
516 : : */
517 : 19937 : for (i = max;
518 [ + + ]: 2794675 : i >= FirstOffsetNumber &&
4326 bruce@momjian.us 519 [ + + + + ]: 2777179 : (opaque->nRedirection > 0 || !hasNonPlaceholder);
4502 tgl@sss.pgh.pa.us 520 : 2774738 : i--)
521 : : {
522 : : SpGistDeadTuple dt;
523 : :
524 : 2774738 : dt = (SpGistDeadTuple) PageGetItem(page, PageGetItemId(page, i));
525 : :
526 [ + + + + ]: 2792559 : if (dt->tupstate == SPGIST_REDIRECT &&
1341 andres@anarazel.de 527 : 17821 : GlobalVisTestIsRemovableXid(vistest, dt->xid))
528 : : {
4502 tgl@sss.pgh.pa.us 529 : 368 : dt->tupstate = SPGIST_PLACEHOLDER;
530 [ - + ]: 368 : Assert(opaque->nRedirection > 0);
531 : 368 : opaque->nRedirection--;
532 : 368 : opaque->nPlaceholder++;
533 : :
534 : : /* remember newest XID among the removed redirects */
514 pg@bowt.ie 535 [ + + - + ]: 667 : if (!TransactionIdIsValid(xlrec.snapshotConflictHorizon) ||
536 : 299 : TransactionIdPrecedes(xlrec.snapshotConflictHorizon, dt->xid))
537 : 69 : xlrec.snapshotConflictHorizon = dt->xid;
538 : :
4502 tgl@sss.pgh.pa.us 539 : 368 : ItemPointerSetInvalid(&dt->pointer);
540 : :
541 : 368 : itemToPlaceholder[xlrec.nToPlaceholder] = i;
542 : 368 : xlrec.nToPlaceholder++;
543 : :
544 : 368 : hasUpdate = true;
545 : : }
546 : :
547 [ + + ]: 2774738 : if (dt->tupstate == SPGIST_PLACEHOLDER)
548 : : {
549 [ + + ]: 104504 : if (!hasNonPlaceholder)
550 : 99662 : firstPlaceholder = i;
551 : : }
552 : : else
553 : : {
554 : 2670234 : hasNonPlaceholder = true;
555 : : }
556 : : }
557 : :
558 : : /*
559 : : * Any placeholder tuples at the end of page can safely be removed. We
560 : : * can't remove ones before the last non-placeholder, though, because we
561 : : * can't alter the offset numbers of non-placeholder tuples.
562 : : */
563 [ + + ]: 19937 : if (firstPlaceholder != InvalidOffsetNumber)
564 : : {
565 : : /*
566 : : * We do not store this array to rdata because it's easy to recreate.
567 : : */
568 [ + + ]: 101241 : for (i = firstPlaceholder; i <= max; i++)
569 : 99662 : itemnos[i - firstPlaceholder] = i;
570 : :
571 : 1579 : i = max - firstPlaceholder + 1;
572 [ - + ]: 1579 : Assert(opaque->nPlaceholder >= i);
573 : 1579 : opaque->nPlaceholder -= i;
574 : :
575 : : /* The array is surely sorted, so can use PageIndexMultiDelete */
576 : 1579 : PageIndexMultiDelete(page, itemnos, i);
577 : :
578 : 1579 : hasUpdate = true;
579 : : }
580 : :
581 : 19937 : xlrec.firstPlaceholder = firstPlaceholder;
582 : :
583 [ + + ]: 19937 : if (hasUpdate)
584 : 1585 : MarkBufferDirty(buffer);
585 : :
586 [ + + + - : 19937 : if (hasUpdate && RelationNeedsWAL(index))
+ + + - +
- ]
587 : : {
588 : : XLogRecPtr recptr;
589 : :
3433 heikki.linnakangas@i 590 : 1585 : XLogBeginInsert();
591 : :
592 : 1585 : XLogRegisterData((char *) &xlrec, SizeOfSpgxlogVacuumRedirect);
593 : 1585 : XLogRegisterData((char *) itemToPlaceholder,
594 : 1585 : sizeof(OffsetNumber) * xlrec.nToPlaceholder);
595 : :
596 : 1585 : XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);
597 : :
598 : 1585 : recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_VACUUM_REDIRECT);
599 : :
4502 tgl@sss.pgh.pa.us 600 : 1585 : PageSetLSN(page, recptr);
601 : : }
602 : :
603 [ - + ]: 19937 : END_CRIT_SECTION();
604 : 19937 : }
605 : :
606 : : /*
607 : : * Process one page during a bulkdelete scan
608 : : */
609 : : static void
610 : 2725 : spgvacuumpage(spgBulkDeleteState *bds, BlockNumber blkno)
611 : : {
612 : 2725 : Relation index = bds->info->index;
613 : : Buffer buffer;
614 : : Page page;
615 : :
616 : : /* call vacuum_delay_point while not holding any buffer lock */
617 : 2725 : vacuum_delay_point();
618 : :
619 : 2725 : buffer = ReadBufferExtended(index, MAIN_FORKNUM, blkno,
620 : 2725 : RBM_NORMAL, bds->info->strategy);
621 : 2725 : LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
2916 kgrittn@postgresql.o 622 : 2725 : page = (Page) BufferGetPage(buffer);
623 : :
4502 tgl@sss.pgh.pa.us 624 [ + + ]: 2725 : if (PageIsNew(page))
625 : : {
626 : : /*
627 : : * We found an all-zero page, which could happen if the database
628 : : * crashed just after extending the file. Recycle it.
629 : : */
630 : : }
3184 heikki.linnakangas@i 631 [ + + ]: 2716 : else if (PageIsEmpty(page))
632 : : {
633 : : /* nothing to do */
634 : : }
4502 tgl@sss.pgh.pa.us 635 [ + + ]: 2660 : else if (SpGistPageIsLeaf(page))
636 : : {
4417 637 [ + + + + ]: 2565 : if (SpGistBlockIsRoot(blkno))
638 : : {
4502 639 : 16 : vacuumLeafRoot(bds, index, buffer);
640 : : /* no need for vacuumRedirectAndPlaceholder */
641 : : }
642 : : else
643 : : {
4416 644 : 2549 : vacuumLeafPage(bds, index, buffer, false);
379 andres@anarazel.de 645 : 2549 : vacuumRedirectAndPlaceholder(index, bds->info->heaprel, buffer);
646 : : }
647 : : }
648 : : else
649 : : {
650 : : /* inner page */
651 : 95 : vacuumRedirectAndPlaceholder(index, bds->info->heaprel, buffer);
652 : : }
653 : :
654 : : /*
655 : : * The root pages must never be deleted, nor marked as available in FSM,
656 : : * because we don't want them ever returned by a search for a place to put
657 : : * a new tuple. Otherwise, check for empty page, and make sure the FSM
658 : : * knows about it.
659 : : */
4417 tgl@sss.pgh.pa.us 660 [ + + + + ]: 2725 : if (!SpGistBlockIsRoot(blkno))
661 : : {
3184 heikki.linnakangas@i 662 [ + + + + ]: 2637 : if (PageIsNew(page) || PageIsEmpty(page))
663 : : {
4502 tgl@sss.pgh.pa.us 664 : 36 : RecordFreeIndexPage(index, blkno);
665 : 36 : bds->stats->pages_deleted++;
666 : : }
667 : : else
668 : : {
3184 heikki.linnakangas@i 669 : 2601 : SpGistSetLastUsedPage(index, buffer);
4502 tgl@sss.pgh.pa.us 670 : 2601 : bds->lastFilledBlock = blkno;
671 : : }
672 : : }
673 : :
674 : 2725 : UnlockReleaseBuffer(buffer);
675 : 2725 : }
676 : :
677 : : /*
678 : : * Process the pending-TID list between pages of the main scan
679 : : */
680 : : static void
4416 681 : 263 : spgprocesspending(spgBulkDeleteState *bds)
682 : : {
683 : 263 : Relation index = bds->info->index;
684 : : spgVacPendingItem *pitem;
685 : : spgVacPendingItem *nitem;
686 : : BlockNumber blkno;
687 : : Buffer buffer;
688 : : Page page;
689 : :
690 [ + + ]: 35112 : for (pitem = bds->pendingList; pitem != NULL; pitem = pitem->next)
691 : : {
692 [ + + ]: 34849 : if (pitem->done)
693 : 17293 : continue; /* ignore already-done items */
694 : :
695 : : /* call vacuum_delay_point while not holding any buffer lock */
696 : 17556 : vacuum_delay_point();
697 : :
698 : : /* examine the referenced page */
699 : 17556 : blkno = ItemPointerGetBlockNumber(&pitem->tid);
700 : 17556 : buffer = ReadBufferExtended(index, MAIN_FORKNUM, blkno,
701 : 17556 : RBM_NORMAL, bds->info->strategy);
702 : 17556 : LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
2916 kgrittn@postgresql.o 703 : 17556 : page = (Page) BufferGetPage(buffer);
704 : :
4416 tgl@sss.pgh.pa.us 705 [ + - + - ]: 17556 : if (PageIsNew(page) || SpGistPageIsDeleted(page))
706 : : {
707 : : /* Probably shouldn't happen, but ignore it */
708 : : }
709 [ + + ]: 17556 : else if (SpGistPageIsLeaf(page))
710 : : {
711 [ + - - + ]: 17293 : if (SpGistBlockIsRoot(blkno))
712 : : {
713 : : /* this should definitely not happen */
4416 tgl@sss.pgh.pa.us 714 [ # # ]:UBC 0 : elog(ERROR, "redirection leads to root page of index \"%s\"",
715 : : RelationGetRelationName(index));
716 : : }
717 : :
718 : : /* deal with any deletable tuples */
4416 tgl@sss.pgh.pa.us 719 :CBC 17293 : vacuumLeafPage(bds, index, buffer, true);
720 : : /* might as well do this while we are here */
379 andres@anarazel.de 721 : 17293 : vacuumRedirectAndPlaceholder(index, bds->info->heaprel, buffer);
722 : :
4416 tgl@sss.pgh.pa.us 723 : 17293 : SpGistSetLastUsedPage(index, buffer);
724 : :
725 : : /*
726 : : * We can mark as done not only this item, but any later ones
727 : : * pointing at the same page, since we vacuumed the whole page.
728 : : */
729 : 17293 : pitem->done = true;
730 [ + + ]: 1516456 : for (nitem = pitem->next; nitem != NULL; nitem = nitem->next)
731 : : {
732 [ + + ]: 1499163 : if (ItemPointerGetBlockNumber(&nitem->tid) == blkno)
733 : 263 : nitem->done = true;
734 : : }
735 : : }
736 : : else
737 : : {
738 : : /*
739 : : * On an inner page, visit the referenced inner tuple and add all
740 : : * its downlinks to the pending list. We might have pending items
741 : : * for more than one inner tuple on the same page (in fact this is
742 : : * pretty likely given the way space allocation works), so get
743 : : * them all while we are here.
744 : : */
745 [ + + ]: 35112 : for (nitem = pitem; nitem != NULL; nitem = nitem->next)
746 : : {
747 [ - + ]: 34849 : if (nitem->done)
4416 tgl@sss.pgh.pa.us 748 :UBC 0 : continue;
4416 tgl@sss.pgh.pa.us 749 [ + + ]:CBC 34849 : if (ItemPointerGetBlockNumber(&nitem->tid) == blkno)
750 : : {
751 : : OffsetNumber offset;
752 : : SpGistInnerTuple innerTuple;
753 : :
754 : 17293 : offset = ItemPointerGetOffsetNumber(&nitem->tid);
755 : 17293 : innerTuple = (SpGistInnerTuple) PageGetItem(page,
756 : : PageGetItemId(page, offset));
757 [ + - ]: 17293 : if (innerTuple->tupstate == SPGIST_LIVE)
758 : : {
759 : : SpGistNodeTuple node;
760 : : int i;
761 : :
762 [ + + ]: 86465 : SGITITERATE(innerTuple, i, node)
763 : : {
764 [ + + ]: 69172 : if (ItemPointerIsValid(&node->t_tid))
765 : 34586 : spgAddPendingTID(bds, &node->t_tid);
766 : : }
767 : : }
4416 tgl@sss.pgh.pa.us 768 [ # # ]:UBC 0 : else if (innerTuple->tupstate == SPGIST_REDIRECT)
769 : : {
770 : : /* transfer attention to redirect point */
771 : 0 : spgAddPendingTID(bds,
772 : : &((SpGistDeadTuple) innerTuple)->pointer);
773 : : }
774 : : else
775 [ # # ]: 0 : elog(ERROR, "unexpected SPGiST tuple state: %d",
776 : : innerTuple->tupstate);
777 : :
4416 tgl@sss.pgh.pa.us 778 :CBC 17293 : nitem->done = true;
779 : : }
780 : : }
781 : : }
782 : :
783 : 17556 : UnlockReleaseBuffer(buffer);
784 : : }
785 : :
786 : 263 : spgClearPendingList(bds);
787 : 263 : }
788 : :
789 : : /*
790 : : * Perform a bulkdelete scan
791 : : */
792 : : static void
4502 793 : 44 : spgvacuumscan(spgBulkDeleteState *bds)
794 : : {
795 : 44 : Relation index = bds->info->index;
796 : : bool needLock;
797 : : BlockNumber num_pages,
798 : : blkno;
799 : :
800 : : /* Finish setting up spgBulkDeleteState */
801 : 44 : initSpGistState(&bds->spgstate, index);
4416 802 : 44 : bds->pendingList = NULL;
803 : 44 : bds->myXmin = GetActiveSnapshot()->xmin;
4417 804 : 44 : bds->lastFilledBlock = SPGIST_LAST_FIXED_BLKNO;
805 : :
806 : : /*
807 : : * Reset counts that will be incremented during the scan; needed in case
808 : : * of multiple scans during a single VACUUM command
809 : : */
4502 810 : 44 : bds->stats->estimated_count = false;
811 : 44 : bds->stats->num_index_tuples = 0;
812 : 44 : bds->stats->pages_deleted = 0;
813 : :
814 : : /* We can skip locking for new or temp relations */
815 [ + - + - ]: 44 : needLock = !RELATION_IS_LOCAL(index);
816 : :
817 : : /*
818 : : * The outer loop iterates over all index pages except the metapage, in
819 : : * physical order (we hope the kernel will cooperate in providing
820 : : * read-ahead for speed). It is critical that we visit all leaf pages,
821 : : * including ones added after we start the scan, else we might fail to
822 : : * delete some deletable tuples. See more extensive comments about this
823 : : * in btvacuumscan().
824 : : */
4417 825 : 44 : blkno = SPGIST_METAPAGE_BLKNO + 1;
826 : : for (;;)
827 : : {
828 : : /* Get the current relation length */
4502 829 [ + - ]: 88 : if (needLock)
830 : 88 : LockRelationForExtension(index, ExclusiveLock);
831 : 88 : num_pages = RelationGetNumberOfBlocks(index);
832 [ + - ]: 88 : if (needLock)
833 : 88 : UnlockRelationForExtension(index, ExclusiveLock);
834 : :
835 : : /* Quit if we've scanned the whole relation */
836 [ + + ]: 88 : if (blkno >= num_pages)
837 : 44 : break;
838 : : /* Iterate over pages, then loop back to recheck length */
839 [ + + ]: 2769 : for (; blkno < num_pages; blkno++)
840 : : {
841 : 2725 : spgvacuumpage(bds, blkno);
842 : : /* empty the pending-list after each page */
4416 843 [ + + ]: 2725 : if (bds->pendingList != NULL)
844 : 263 : spgprocesspending(bds);
845 : : }
846 : : }
847 : :
848 : : /* Propagate local lastUsedPages cache to metablock */
4502 849 : 44 : SpGistUpdateMetaPage(index);
850 : :
851 : : /*
852 : : * If we found any empty pages (and recorded them in the FSM), then
853 : : * forcibly update the upper-level FSM pages to ensure that searchers can
854 : : * find them. It's possible that the pages were also found during
855 : : * previous scans and so this is a waste of time, but it's cheap enough
856 : : * relative to scanning the index that it shouldn't matter much, and
857 : : * making sure that free pages are available sooner not later seems
858 : : * worthwhile.
859 : : *
860 : : * Note that if no empty pages exist, we don't bother vacuuming the FSM at
861 : : * all.
862 : : */
2207 863 [ + + ]: 44 : if (bds->stats->pages_deleted > 0)
864 : 29 : IndexFreeSpaceMapVacuum(index);
865 : :
866 : : /*
867 : : * Truncate index if possible
868 : : *
869 : : * XXX disabled because it's unsafe due to possible concurrent inserts.
870 : : * We'd have to rescan the pages to make sure they're still empty, and it
871 : : * doesn't seem worth it. Note that btree doesn't do this either.
872 : : *
873 : : * Another reason not to truncate is that it could invalidate the cached
874 : : * pages-with-freespace pointers in the metapage and other backends'
875 : : * relation caches, that is leave them pointing to nonexistent pages.
876 : : * Adding RelationGetNumberOfBlocks calls to protect the places that use
877 : : * those pointers would be unduly expensive.
878 : : */
879 : : #ifdef NOT_USED
880 : : if (num_pages > bds->lastFilledBlock + 1)
881 : : {
882 : : BlockNumber lastBlock = num_pages - 1;
883 : :
884 : : num_pages = bds->lastFilledBlock + 1;
885 : : RelationTruncate(index, num_pages);
886 : : bds->stats->pages_removed += lastBlock - bds->lastFilledBlock;
887 : : bds->stats->pages_deleted -= lastBlock - bds->lastFilledBlock;
888 : : }
889 : : #endif
890 : :
891 : : /* Report final stats */
4502 892 : 44 : bds->stats->num_pages = num_pages;
1144 pg@bowt.ie 893 : 44 : bds->stats->pages_newly_deleted = bds->stats->pages_deleted;
4502 tgl@sss.pgh.pa.us 894 : 44 : bds->stats->pages_free = bds->stats->pages_deleted;
895 : 44 : }
896 : :
897 : : /*
898 : : * Bulk deletion of all index entries pointing to a set of heap tuples.
899 : : * The set of target tuples is specified via a callback routine that tells
900 : : * whether any given heap tuple (identified by ItemPointer) is being deleted.
901 : : *
902 : : * Result: a palloc'd struct containing statistical info for VACUUM displays.
903 : : */
904 : : IndexBulkDeleteResult *
3010 905 : 6 : spgbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
906 : : IndexBulkDeleteCallback callback, void *callback_state)
907 : : {
908 : : spgBulkDeleteState bds;
909 : :
910 : : /* allocate stats if first time through, else re-use existing struct */
4502 911 [ + - ]: 6 : if (stats == NULL)
912 : 6 : stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
913 : 6 : bds.info = info;
914 : 6 : bds.stats = stats;
915 : 6 : bds.callback = callback;
916 : 6 : bds.callback_state = callback_state;
917 : :
918 : 6 : spgvacuumscan(&bds);
919 : :
3010 920 : 6 : return stats;
921 : : }
922 : :
923 : : /* Dummy callback to delete no tuples during spgvacuumcleanup */
924 : : static bool
4502 925 : 2907980 : dummy_callback(ItemPointer itemptr, void *state)
926 : : {
927 : 2907980 : return false;
928 : : }
929 : :
930 : : /*
931 : : * Post-VACUUM cleanup.
932 : : *
933 : : * Result: a palloc'd struct containing statistical info for VACUUM displays.
934 : : */
935 : : IndexBulkDeleteResult *
3010 936 : 62 : spgvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
937 : : {
938 : : spgBulkDeleteState bds;
939 : :
940 : : /* No-op in ANALYZE ONLY mode */
4502 941 [ + + ]: 62 : if (info->analyze_only)
3010 942 : 18 : return stats;
943 : :
944 : : /*
945 : : * We don't need to scan the index if there was a preceding bulkdelete
946 : : * pass. Otherwise, make a pass that won't delete any live tuples, but
947 : : * might still accomplish useful stuff with redirect/placeholder cleanup
948 : : * and/or FSM housekeeping, and in any case will provide stats.
949 : : */
4502 950 [ + + ]: 44 : if (stats == NULL)
951 : : {
952 : 38 : stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
953 : 38 : bds.info = info;
954 : 38 : bds.stats = stats;
955 : 38 : bds.callback = dummy_callback;
956 : 38 : bds.callback_state = NULL;
957 : :
958 : 38 : spgvacuumscan(&bds);
959 : : }
960 : :
961 : : /*
962 : : * It's quite possible for us to be fooled by concurrent tuple moves into
963 : : * double-counting some index tuples, so disbelieve any total that exceeds
964 : : * the underlying heap's count ... if we know that accurately. Otherwise
965 : : * this might just make matters worse.
966 : : */
967 [ + - ]: 44 : if (!info->estimated_count)
968 : : {
969 [ - + ]: 44 : if (stats->num_index_tuples > info->num_heap_tuples)
4502 tgl@sss.pgh.pa.us 970 :UBC 0 : stats->num_index_tuples = info->num_heap_tuples;
971 : : }
972 : :
3010 tgl@sss.pgh.pa.us 973 :CBC 44 : return stats;
974 : : }
|
