Debian Codegraph @

src/backend/access/nbtree/nbtree.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * nbtree.c
4 * Implementation of Lehman and Yao's btree management algorithm for
5 * Postgres.
6 *
7 * NOTES
8 * This file contains only the public interface routines.
9 *
10 *
11 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
12 * Portions Copyright (c) 1994, Regents of the University of California
13 *
14 * IDENTIFICATION
15 * src/backend/access/nbtree/nbtree.c
16 *
17 *-------------------------------------------------------------------------
18 */
19 #include "postgres.h"
20
21 #include "access/nbtree.h"
22 #include "access/relscan.h"
23 #include "access/stratnum.h"
24 #include "commands/progress.h"
25 #include "commands/vacuum.h"
26 #include "nodes/execnodes.h"
27 #include "pgstat.h"
28 #include "storage/bulk_write.h"
29 #include "storage/condition_variable.h"
30 #include "storage/indexfsm.h"
31 #include "storage/ipc.h"
32 #include "storage/lmgr.h"
33 #include "storage/read_stream.h"
34 #include "utils/datum.h"
35 #include "utils/fmgrprotos.h"
36 #include "utils/index_selfuncs.h"
37 #include "utils/memutils.h"
38
39
40 /*
41 * BTPARALLEL_NOT_INITIALIZED indicates that the scan has not started.
42 *
43 * BTPARALLEL_NEED_PRIMSCAN indicates that some process must now seize the
44 * scan to advance it via another call to _bt_first.
45 *
46 * BTPARALLEL_ADVANCING indicates that some process is advancing the scan to
47 * a new page; others must wait.
48 *
49 * BTPARALLEL_IDLE indicates that no backend is currently advancing the scan
50 * to a new page; some process can start doing that.
51 *
52 * BTPARALLEL_DONE indicates that the scan is complete (including error exit).
53 */
54 typedef enum
55 {
56 BTPARALLEL_NOT_INITIALIZED,
57 BTPARALLEL_NEED_PRIMSCAN,
58 BTPARALLEL_ADVANCING,
59 BTPARALLEL_IDLE,
60 BTPARALLEL_DONE,
61 } BTPS_State;
62
63 /*
64 * BTParallelScanDescData contains btree specific shared information required
65 * for parallel scan.
66 */
67 typedef struct BTParallelScanDescData
68 {
69 BlockNumber btps_nextScanPage; /* next page to be scanned */
70 BlockNumber btps_lastCurrPage; /* page whose sibling link was copied into
71 * btps_nextScanPage */
72 BTPS_State btps_pageStatus; /* indicates whether next page is
73 * available for scan. see above for
74 * possible states of parallel scan. */
75 LWLock btps_lock; /* protects shared parallel state */
76 ConditionVariable btps_cv; /* used to synchronize parallel scan */
77
78 /*
79 * btps_arrElems is used when scans need to schedule another primitive
80 * index scan with one or more SAOP arrays. Holds BTArrayKeyInfo.cur_elem
81 * offsets for each = scan key associated with a ScalarArrayOp array.
82 */
83 int btps_arrElems[FLEXIBLE_ARRAY_MEMBER];
84
85 /*
86 * Additional space (at the end of the struct) is used when scans need to
87 * schedule another primitive index scan with one or more skip arrays.
88 * Holds a flattened datum representation for each = scan key associated
89 * with a skip array.
90 */
91 } BTParallelScanDescData;
92
93 typedef struct BTParallelScanDescData *BTParallelScanDesc;
94
95
96 static void _bt_parallel_serialize_arrays(Relation rel, BTParallelScanDesc btscan,
97 BTScanOpaque so);
98 static void _bt_parallel_restore_arrays(Relation rel, BTParallelScanDesc btscan,
99 BTScanOpaque so);
100 static void btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
101 IndexBulkDeleteCallback callback, void *callback_state,
102 BTCycleId cycleid);
103 static BlockNumber btvacuumpage(BTVacState *vstate, Buffer buf);
104 static BTVacuumPosting btreevacuumposting(BTVacState *vstate,
105 IndexTuple posting,
106 OffsetNumber updatedoffset,
107 int *nremaining);
108
109
110 /*
111 * Btree handler function: return IndexAmRoutine with access method parameters
112 * and callbacks.
113 */
114 Datum
115 bthandler(PG_FUNCTION_ARGS)
116 {
117 IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
118
119 amroutine->amstrategies = BTMaxStrategyNumber;
120 amroutine->amsupport = BTNProcs;
121 amroutine->amoptsprocnum = BTOPTIONS_PROC;
122 amroutine->amcanorder = true;
123 amroutine->amcanorderbyop = false;
124 amroutine->amcanhash = false;
125 amroutine->amconsistentequality = true;
126 amroutine->amconsistentordering = true;
127 amroutine->amcanbackward = true;
128 amroutine->amcanunique = true;
129 amroutine->amcanmulticol = true;
130 amroutine->amoptionalkey = true;
131 amroutine->amsearcharray = true;
132 amroutine->amsearchnulls = true;
133 amroutine->amstorage = false;
134 amroutine->amclusterable = true;
135 amroutine->ampredlocks = true;
136 amroutine->amcanparallel = true;
137 amroutine->amcanbuildparallel = true;
138 amroutine->amcaninclude = true;
139 amroutine->amusemaintenanceworkmem = false;
140 amroutine->amsummarizing = false;
141 amroutine->amparallelvacuumoptions =
142 VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP;
143 amroutine->amkeytype = InvalidOid;
144
145 amroutine->ambuild = btbuild;
146 amroutine->ambuildempty = btbuildempty;
147 amroutine->aminsert = btinsert;
148 amroutine->aminsertcleanup = NULL;
149 amroutine->ambulkdelete = btbulkdelete;
150 amroutine->amvacuumcleanup = btvacuumcleanup;
151 amroutine->amcanreturn = btcanreturn;
152 amroutine->amcostestimate = btcostestimate;
153 amroutine->amgettreeheight = btgettreeheight;
154 amroutine->amoptions = btoptions;
155 amroutine->amproperty = btproperty;
156 amroutine->ambuildphasename = btbuildphasename;
157 amroutine->amvalidate = btvalidate;
158 amroutine->amadjustmembers = btadjustmembers;
159 amroutine->ambeginscan = btbeginscan;
160 amroutine->amrescan = btrescan;
161 amroutine->amgettuple = btgettuple;
162 amroutine->amgetbitmap = btgetbitmap;
163 amroutine->amendscan = btendscan;
164 amroutine->ammarkpos = btmarkpos;
165 amroutine->amrestrpos = btrestrpos;
166 amroutine->amestimateparallelscan = btestimateparallelscan;
167 amroutine->aminitparallelscan = btinitparallelscan;
168 amroutine->amparallelrescan = btparallelrescan;
169 amroutine->amtranslatestrategy = bttranslatestrategy;
170 amroutine->amtranslatecmptype = bttranslatecmptype;
171
172 PG_RETURN_POINTER(amroutine);
173 }
174
175 /*
176 * btbuildempty() -- build an empty btree index in the initialization fork
177 */
178 void
179 btbuildempty(Relation index)
180 {
181 bool allequalimage = _bt_allequalimage(index, false);
182 BulkWriteState *bulkstate;
183 BulkWriteBuffer metabuf;
184
185 bulkstate = smgr_bulk_start_rel(index, INIT_FORKNUM);
186
187 /* Construct metapage. */
188 metabuf = smgr_bulk_get_buf(bulkstate);
189 _bt_initmetapage((Page) metabuf, P_NONE, 0, allequalimage);
190 smgr_bulk_write(bulkstate, BTREE_METAPAGE, metabuf, true);
191
192 smgr_bulk_finish(bulkstate);
193 }
194
195 /*
196 * btinsert() -- insert an index tuple into a btree.
197 *
198 * Descend the tree recursively, find the appropriate location for our
199 * new tuple, and put it there.
200 */
201 bool
202 btinsert(Relation rel, Datum *values, bool *isnull,
203 ItemPointer ht_ctid, Relation heapRel,
204 IndexUniqueCheck checkUnique,
205 bool indexUnchanged,
206 IndexInfo *indexInfo)
207 {
208 bool result;
209 IndexTuple itup;
210
211 /* generate an index tuple */
212 itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
213 itup->t_tid = *ht_ctid;
214
215 result = _bt_doinsert(rel, itup, checkUnique, indexUnchanged, heapRel);
216
217 pfree(itup);
218
219 return result;
220 }
221
222 /*
223 * btgettuple() -- Get the next tuple in the scan.
224 */
225 bool
226 btgettuple(IndexScanDesc scan, ScanDirection dir)
227 {
228 BTScanOpaque so = (BTScanOpaque) scan->opaque;
229 bool res;
230
231 Assert(scan->heapRelation != NULL);
232
233 /* btree indexes are never lossy */
234 scan->xs_recheck = false;
235
236 /* Each loop iteration performs another primitive index scan */
237 do
238 {
239 /*
240 * If we've already initialized this scan, we can just advance it in
241 * the appropriate direction. If we haven't done so yet, we call
242 * _bt_first() to get the first item in the scan.
243 */
244 if (!BTScanPosIsValid(so->currPos))
245 res = _bt_first(scan, dir);
246 else
247 {
248 /*
249 * Check to see if we should kill the previously-fetched tuple.
250 */
251 if (scan->kill_prior_tuple)
252 {
253 /*
254 * Yes, remember it for later. (We'll deal with all such
255 * tuples at once right before leaving the index page.) The
256 * test for numKilled overrun is not just paranoia: if the
257 * caller reverses direction in the indexscan then the same
258 * item might get entered multiple times. It's not worth
259 * trying to optimize that, so we don't detect it, but instead
260 * just forget any excess entries.
261 */
262 if (so->killedItems == NULL)
263 so->killedItems = (int *)
264 palloc(MaxTIDsPerBTreePage * sizeof(int));
265 if (so->numKilled < MaxTIDsPerBTreePage)
266 so->killedItems[so->numKilled++] = so->currPos.itemIndex;
267 }
268
269 /*
270 * Now continue the scan.
271 */
272 res = _bt_next(scan, dir);
273 }
274
275 /* If we have a tuple, return it ... */
276 if (res)
277 break;
278 /* ... otherwise see if we need another primitive index scan */
279 } while (so->numArrayKeys && _bt_start_prim_scan(scan, dir));
280
281 return res;
282 }
283
284 /*
285 * btgetbitmap() -- gets all matching tuples, and adds them to a bitmap
286 */
287 int64
288 btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
289 {
290 BTScanOpaque so = (BTScanOpaque) scan->opaque;
291 int64 ntids = 0;
292 ItemPointer heapTid;
293
294 Assert(scan->heapRelation == NULL);
295
296 /* Each loop iteration performs another primitive index scan */
297 do
298 {
299 /* Fetch the first page & tuple */
300 if (_bt_first(scan, ForwardScanDirection))
301 {
302 /* Save tuple ID, and continue scanning */
303 heapTid = &scan->xs_heaptid;
304 tbm_add_tuples(tbm, heapTid, 1, false);
305 ntids++;
306
307 for (;;)
308 {
309 /*
310 * Advance to next tuple within page. This is the same as the
311 * easy case in _bt_next().
312 */
313 if (++so->currPos.itemIndex > so->currPos.lastItem)
314 {
315 /* let _bt_next do the heavy lifting */
316 if (!_bt_next(scan, ForwardScanDirection))
317 break;
318 }
319
320 /* Save tuple ID, and continue scanning */
321 heapTid = &so->currPos.items[so->currPos.itemIndex].heapTid;
322 tbm_add_tuples(tbm, heapTid, 1, false);
323 ntids++;
324 }
325 }
326 /* Now see if we need another primitive index scan */
327 } while (so->numArrayKeys && _bt_start_prim_scan(scan, ForwardScanDirection));
328
329 return ntids;
330 }
331
332 /*
333 * btbeginscan() -- start a scan on a btree index
334 */
335 IndexScanDesc
336 btbeginscan(Relation rel, int nkeys, int norderbys)
337 {
338 IndexScanDesc scan;
339 BTScanOpaque so;
340
341 /* no order by operators allowed */
342 Assert(norderbys == 0);
343
344 /* get the scan */
345 scan = RelationGetIndexScan(rel, nkeys, norderbys);
346
347 /* allocate private workspace */
348 so = (BTScanOpaque) palloc(sizeof(BTScanOpaqueData));
349 BTScanPosInvalidate(so->currPos);
350 BTScanPosInvalidate(so->markPos);
351 if (scan->numberOfKeys > 0)
352 so->keyData = (ScanKey) palloc(scan->numberOfKeys * sizeof(ScanKeyData));
353 else
354 so->keyData = NULL;
355
356 so->skipScan = false;
357 so->needPrimScan = false;
358 so->scanBehind = false;
359 so->oppositeDirCheck = false;
360 so->arrayKeys = NULL;
361 so->orderProcs = NULL;
362 so->arrayContext = NULL;
363
364 so->killedItems = NULL; /* until needed */
365 so->numKilled = 0;
366
367 /*
368 * We don't know yet whether the scan will be index-only, so we do not
369 * allocate the tuple workspace arrays until btrescan. However, we set up
370 * scan->xs_itupdesc whether we'll need it or not, since that's so cheap.
371 */
372 so->currTuples = so->markTuples = NULL;
373
374 scan->xs_itupdesc = RelationGetDescr(rel);
375
376 scan->opaque = so;
377
378 return scan;
379 }
380
381 /*
382 * btrescan() -- rescan an index relation
383 */
384 void
385 btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
386 ScanKey orderbys, int norderbys)
387 {
388 BTScanOpaque so = (BTScanOpaque) scan->opaque;
389
390 /* we aren't holding any read locks, but gotta drop the pins */
391 if (BTScanPosIsValid(so->currPos))
392 {
393 /* Before leaving current page, deal with any killed items */
394 if (so->numKilled > 0)
395 _bt_killitems(scan);
396 BTScanPosUnpinIfPinned(so->currPos);
397 BTScanPosInvalidate(so->currPos);
398 }
399
400 /*
401 * We prefer to eagerly drop leaf page pins before btgettuple returns.
402 * This avoids making VACUUM wait to acquire a cleanup lock on the page.
403 *
404 * We cannot safely drop leaf page pins during index-only scans due to a
405 * race condition involving VACUUM setting pages all-visible in the VM.
406 * It's also unsafe for plain index scans that use a non-MVCC snapshot.
407 *
408 * When we drop pins eagerly, the mechanism that marks so->killedItems[]
409 * index tuples LP_DEAD has to deal with concurrent TID recycling races.
410 * The scheme used to detect unsafe TID recycling won't work when scanning
411 * unlogged relations (since it involves saving an affected page's LSN).
412 * Opt out of eager pin dropping during unlogged relation scans for now
413 * (this is preferable to opting out of kill_prior_tuple LP_DEAD setting).
414 *
415 * Also opt out of dropping leaf page pins eagerly during bitmap scans.
416 * Pins cannot be held for more than an instant during bitmap scans either
417 * way, so we might as well avoid wasting cycles on acquiring page LSNs.
418 *
419 * See nbtree/README section on making concurrent TID recycling safe.
420 *
421 * Note: so->dropPin should never change across rescans.
422 */
423 so->dropPin = (!scan->xs_want_itup &&
424 IsMVCCSnapshot(scan->xs_snapshot) &&
425 RelationNeedsWAL(scan->indexRelation) &&
426 scan->heapRelation != NULL);
427
428 so->markItemIndex = -1;
429 so->needPrimScan = false;
430 so->scanBehind = false;
431 so->oppositeDirCheck = false;
432 BTScanPosUnpinIfPinned(so->markPos);
433 BTScanPosInvalidate(so->markPos);
434
435 /*
436 * Allocate tuple workspace arrays, if needed for an index-only scan and
437 * not already done in a previous rescan call. To save on palloc
438 * overhead, both workspaces are allocated as one palloc block; only this
439 * function and btendscan know that.
440 *
441 * NOTE: this data structure also makes it safe to return data from a
442 * "name" column, even though btree name_ops uses an underlying storage
443 * datatype of cstring. The risk there is that "name" is supposed to be
444 * padded to NAMEDATALEN, but the actual index tuple is probably shorter.
445 * However, since we only return data out of tuples sitting in the
446 * currTuples array, a fetch of NAMEDATALEN bytes can at worst pull some
447 * data out of the markTuples array --- running off the end of memory for
448 * a SIGSEGV is not possible. Yeah, this is ugly as sin, but it beats
449 * adding special-case treatment for name_ops elsewhere.
450 */
451 if (scan->xs_want_itup && so->currTuples == NULL)
452 {
453 so->currTuples = (char *) palloc(BLCKSZ * 2);
454 so->markTuples = so->currTuples + BLCKSZ;
455 }
456
457 /*
458 * Reset the scan keys
459 */
460 if (scankey && scan->numberOfKeys > 0)
461 memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
462 so->numberOfKeys = 0; /* until _bt_preprocess_keys sets it */
463 so->numArrayKeys = 0; /* ditto */
464 }
465
466 /*
467 * btendscan() -- close down a scan
468 */
469 void
470 btendscan(IndexScanDesc scan)
471 {
472 BTScanOpaque so = (BTScanOpaque) scan->opaque;
473
474 /* we aren't holding any read locks, but gotta drop the pins */
475 if (BTScanPosIsValid(so->currPos))
476 {
477 /* Before leaving current page, deal with any killed items */
478 if (so->numKilled > 0)
479 _bt_killitems(scan);
480 BTScanPosUnpinIfPinned(so->currPos);
481 }
482
483 so->markItemIndex = -1;
484 BTScanPosUnpinIfPinned(so->markPos);
485
486 /* No need to invalidate positions, the RAM is about to be freed. */
487
488 /* Release storage */
489 if (so->keyData != NULL)
490 pfree(so->keyData);
491 /* so->arrayKeys and so->orderProcs are in arrayContext */
492 if (so->arrayContext != NULL)
493 MemoryContextDelete(so->arrayContext);
494 if (so->killedItems != NULL)
495 pfree(so->killedItems);
496 if (so->currTuples != NULL)
497 pfree(so->currTuples);
498 /* so->markTuples should not be pfree'd, see btrescan */
499 pfree(so);
500 }
501
502 /*
503 * btmarkpos() -- save current scan position
504 */
505 void
506 btmarkpos(IndexScanDesc scan)
507 {
508 BTScanOpaque so = (BTScanOpaque) scan->opaque;
509
510 /* There may be an old mark with a pin (but no lock). */
511 BTScanPosUnpinIfPinned(so->markPos);
512
513 /*
514 * Just record the current itemIndex. If we later step to next page
515 * before releasing the marked position, _bt_steppage makes a full copy of
516 * the currPos struct in markPos. If (as often happens) the mark is moved
517 * before we leave the page, we don't have to do that work.
518 */
519 if (BTScanPosIsValid(so->currPos))
520 so->markItemIndex = so->currPos.itemIndex;
521 else
522 {
523 BTScanPosInvalidate(so->markPos);
524 so->markItemIndex = -1;
525 }
526 }
527
528 /*
529 * btrestrpos() -- restore scan to last saved position
530 */
531 void
532 btrestrpos(IndexScanDesc scan)
533 {
534 BTScanOpaque so = (BTScanOpaque) scan->opaque;
535
536 if (so->markItemIndex >= 0)
537 {
538 /*
539 * The scan has never moved to a new page since the last mark. Just
540 * restore the itemIndex.
541 *
542 * NB: In this case we can't count on anything in so->markPos to be
543 * accurate.
544 */
545 so->currPos.itemIndex = so->markItemIndex;
546 }
547 else
548 {
549 /*
550 * The scan moved to a new page after last mark or restore, and we are
551 * now restoring to the marked page. We aren't holding any read
552 * locks, but if we're still holding the pin for the current position,
553 * we must drop it.
554 */
555 if (BTScanPosIsValid(so->currPos))
556 {
557 /* Before leaving current page, deal with any killed items */
558 if (so->numKilled > 0)
559 _bt_killitems(scan);
560 BTScanPosUnpinIfPinned(so->currPos);
561 }
562
563 if (BTScanPosIsValid(so->markPos))
564 {
565 /* bump pin on mark buffer for assignment to current buffer */
566 if (BTScanPosIsPinned(so->markPos))
567 IncrBufferRefCount(so->markPos.buf);
568 memcpy(&so->currPos, &so->markPos,
569 offsetof(BTScanPosData, items[1]) +
570 so->markPos.lastItem * sizeof(BTScanPosItem));
571 if (so->currTuples)
572 memcpy(so->currTuples, so->markTuples,
573 so->markPos.nextTupleOffset);
574 /* Reset the scan's array keys (see _bt_steppage for why) */
575 if (so->numArrayKeys)
576 {
577 _bt_start_array_keys(scan, so->currPos.dir);
578 so->needPrimScan = false;
579 }
580 }
581 else
582 BTScanPosInvalidate(so->currPos);
583 }
584 }
585
586 /*
587 * btestimateparallelscan -- estimate storage for BTParallelScanDescData
588 */
589 Size
590 btestimateparallelscan(Relation rel, int nkeys, int norderbys)
591 {
592 int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
593 Size estnbtreeshared,
594 genericattrspace;
595
596 /*
597 * Pessimistically assume that every input scan key will be output with
598 * its own SAOP array
599 */
600 estnbtreeshared = offsetof(BTParallelScanDescData, btps_arrElems) +
601 sizeof(int) * nkeys;
602
603 /* Single column indexes cannot possibly use a skip array */
604 if (nkeyatts == 1)
605 return estnbtreeshared;
606
607 /*
608 * Pessimistically assume that all attributes prior to the least
609 * significant attribute require a skip array (and an associated key)
610 */
611 genericattrspace = datumEstimateSpace((Datum) 0, false, true,
612 sizeof(Datum));
613 for (int attnum = 1; attnum < nkeyatts; attnum++)
614 {
615 CompactAttribute *attr;
616
617 /*
618 * We make the conservative assumption that every index column will
619 * also require a skip array.
620 *
621 * Every skip array must have space to store its scan key's sk_flags.
622 * We also need space for each skip array's unused btps_arrElems slot
623 * (we need to be able to subscript btps_arrElems using a simple
624 * so->arrayKeys[]-wise offset for any subsequent SAOP arrays).
625 */
626 estnbtreeshared = add_size(estnbtreeshared, sizeof(int) * 2);
627
628 /* Consider space required to store a datum of opclass input type */
629 attr = TupleDescCompactAttr(rel->rd_att, attnum - 1);
630 if (attr->attbyval)
631 {
632 /* This index attribute stores pass-by-value datums */
633 Size estfixed = datumEstimateSpace((Datum) 0, false,
634 true, attr->attlen);
635
636 estnbtreeshared = add_size(estnbtreeshared, estfixed);
637 continue;
638 }
639
640 /*
641 * This index attribute stores pass-by-reference datums.
642 *
643 * Assume that serializing this array will use just as much space as a
644 * pass-by-value datum, in addition to space for the largest possible
645 * whole index tuple (this is not just a per-datum portion of the
646 * largest possible tuple because that'd be almost as large anyway).
647 *
648 * This is quite conservative, but it's not clear how we could do much
649 * better. The executor requires an up-front storage request size
650 * that reliably covers the scan's high watermark memory usage. We
651 * can't be sure of the real high watermark until the scan is over.
652 */
653 estnbtreeshared = add_size(estnbtreeshared, genericattrspace);
654 estnbtreeshared = add_size(estnbtreeshared, BTMaxItemSize);
655 }
656
657 return estnbtreeshared;
658 }
659
660 /*
661 * _bt_parallel_serialize_arrays() -- Serialize parallel array state.
662 *
663 * Caller must have exclusively locked btscan->btps_lock when called.
664 */
665 static void
666 _bt_parallel_serialize_arrays(Relation rel, BTParallelScanDesc btscan,
667 BTScanOpaque so)
668 {
669 char *datumshared;
670
671 /* Space for serialized datums begins immediately after btps_arrElems[] */
672 datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
673 for (int i = 0; i < so->numArrayKeys; i++)
674 {
675 BTArrayKeyInfo *array = &so->arrayKeys[i];
676 ScanKey skey = &so->keyData[array->scan_key];
677
678 if (array->num_elems != -1)
679 {
680 /* Save SAOP array's cur_elem (no need to copy key/datum) */
681 Assert(!(skey->sk_flags & SK_BT_SKIP));
682 btscan->btps_arrElems[i] = array->cur_elem;
683 continue;
684 }
685
686 /* Save all mutable state associated with skip array's key */
687 Assert(skey->sk_flags & SK_BT_SKIP);
688 memcpy(datumshared, &skey->sk_flags, sizeof(int));
689 datumshared += sizeof(int);
690
691 if (skey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))
692 {
693 /* No sk_argument datum to serialize */
694 Assert(skey->sk_argument == 0);
695 continue;
696 }
697
698 datumSerialize(skey->sk_argument, (skey->sk_flags & SK_ISNULL) != 0,
699 array->attbyval, array->attlen, &datumshared);
700 }
701 }
702
703 /*
704 * _bt_parallel_restore_arrays() -- Restore serialized parallel array state.
705 *
706 * Caller must have exclusively locked btscan->btps_lock when called.
707 */
708 static void
709 _bt_parallel_restore_arrays(Relation rel, BTParallelScanDesc btscan,
710 BTScanOpaque so)
711 {
712 char *datumshared;
713
714 /* Space for serialized datums begins immediately after btps_arrElems[] */
715 datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
716 for (int i = 0; i < so->numArrayKeys; i++)
717 {
718 BTArrayKeyInfo *array = &so->arrayKeys[i];
719 ScanKey skey = &so->keyData[array->scan_key];
720 bool isnull;
721
722 if (array->num_elems != -1)
723 {
724 /* Restore SAOP array using its saved cur_elem */
725 Assert(!(skey->sk_flags & SK_BT_SKIP));
726 array->cur_elem = btscan->btps_arrElems[i];
727 skey->sk_argument = array->elem_values[array->cur_elem];
728 continue;
729 }
730
731 /* Restore skip array by restoring its key directly */
732 if (!array->attbyval && skey->sk_argument)
733 pfree(DatumGetPointer(skey->sk_argument));
734 skey->sk_argument = (Datum) 0;
735 memcpy(&skey->sk_flags, datumshared, sizeof(int));
736 datumshared += sizeof(int);
737
738 Assert(skey->sk_flags & SK_BT_SKIP);
739
740 if (skey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))
741 {
742 /* No sk_argument datum to restore */
743 continue;
744 }
745
746 skey->sk_argument = datumRestore(&datumshared, &isnull);
747 if (isnull)
748 {
749 Assert(skey->sk_argument == 0);
750 Assert(skey->sk_flags & SK_SEARCHNULL);
751 Assert(skey->sk_flags & SK_ISNULL);
752 }
753 }
754 }
755
756 /*
757 * btinitparallelscan -- initialize BTParallelScanDesc for parallel btree scan
758 */
759 void
760 btinitparallelscan(void *target)
761 {
762 BTParallelScanDesc bt_target = (BTParallelScanDesc) target;
763
764 LWLockInitialize(&bt_target->btps_lock,
765 LWTRANCHE_PARALLEL_BTREE_SCAN);
766 bt_target->btps_nextScanPage = InvalidBlockNumber;
767 bt_target->btps_lastCurrPage = InvalidBlockNumber;
768 bt_target->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
769 ConditionVariableInit(&bt_target->btps_cv);
770 }
771
772 /*
773 * btparallelrescan() -- reset parallel scan
774 */
775 void
776 btparallelrescan(IndexScanDesc scan)
777 {
778 BTParallelScanDesc btscan;
779 ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
780
781 Assert(parallel_scan);
782
783 btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
784 parallel_scan->ps_offset_am);
785
786 /*
787 * In theory, we don't need to acquire the LWLock here, because there
788 * shouldn't be any other workers running at this point, but we do so for
789 * consistency.
790 */
791 LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
792 btscan->btps_nextScanPage = InvalidBlockNumber;
793 btscan->btps_lastCurrPage = InvalidBlockNumber;
794 btscan->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
795 LWLockRelease(&btscan->btps_lock);
796 }
797
798 /*
799 * _bt_parallel_seize() -- Begin the process of advancing the scan to a new
800 * page. Other scans must wait until we call _bt_parallel_release()
801 * or _bt_parallel_done().
802 *
803 * The return value is true if we successfully seized the scan and false
804 * if we did not. The latter case occurs when no pages remain, or when
805 * another primitive index scan is scheduled that caller's backend cannot
806 * start just yet (only backends that call from _bt_first are capable of
807 * starting primitive index scans, which they indicate by passing first=true).
808 *
809 * If the return value is true, *next_scan_page returns the next page of the
810 * scan, and *last_curr_page returns the page that *next_scan_page came from.
811 * An invalid *next_scan_page means the scan hasn't yet started, or that
812 * caller needs to start the next primitive index scan (if it's the latter
813 * case we'll set so.needPrimScan).
814 *
815 * Callers should ignore the value of *next_scan_page and *last_curr_page if
816 * the return value is false.
817 */
818 bool
819 _bt_parallel_seize(IndexScanDesc scan, BlockNumber *next_scan_page,
820 BlockNumber *last_curr_page, bool first)
821 {
822 Relation rel = scan->indexRelation;
823 BTScanOpaque so = (BTScanOpaque) scan->opaque;
824 bool exit_loop = false,
825 status = true,
826 endscan = false;
827 ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
828 BTParallelScanDesc btscan;
829
830 *next_scan_page = InvalidBlockNumber;
831 *last_curr_page = InvalidBlockNumber;
832
833 /*
834 * Reset so->currPos, and initialize moreLeft/moreRight such that the next
835 * call to _bt_readnextpage treats this backend similarly to a serial
836 * backend that steps from *last_curr_page to *next_scan_page (unless this
837 * backend's so->currPos is initialized by _bt_readfirstpage before then).
838 */
839 BTScanPosInvalidate(so->currPos);
840 so->currPos.moreLeft = so->currPos.moreRight = true;
841
842 if (first)
843 {
844 /*
845 * Initialize array related state when called from _bt_first, assuming
846 * that this will be the first primitive index scan for the scan
847 */
848 so->needPrimScan = false;
849 so->scanBehind = false;
850 so->oppositeDirCheck = false;
851 }
852 else
853 {
854 /*
855 * Don't attempt to seize the scan when it requires another primitive
856 * index scan, since caller's backend cannot start it right now
857 */
858 if (so->needPrimScan)
859 return false;
860 }
861
862 btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
863 parallel_scan->ps_offset_am);
864
865 while (1)
866 {
867 LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
868
869 if (btscan->btps_pageStatus == BTPARALLEL_DONE)
870 {
871 /* We're done with this parallel index scan */
872 status = false;
873 }
874 else if (btscan->btps_pageStatus == BTPARALLEL_IDLE &&
875 btscan->btps_nextScanPage == P_NONE)
876 {
877 /* End this parallel index scan */
878 status = false;
879 endscan = true;
880 }
881 else if (btscan->btps_pageStatus == BTPARALLEL_NEED_PRIMSCAN)
882 {
883 Assert(so->numArrayKeys);
884
885 if (first)
886 {
887 /* Can start scheduled primitive scan right away, so do so */
888 btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
889
890 /* Restore scan's array keys from serialized values */
891 _bt_parallel_restore_arrays(rel, btscan, so);
892 exit_loop = true;
893 }
894 else
895 {
896 /*
897 * Don't attempt to seize the scan when it requires another
898 * primitive index scan, since caller's backend cannot start
899 * it right now
900 */
901 status = false;
902 }
903
904 /*
905 * Either way, update backend local state to indicate that a
906 * pending primitive scan is required
907 */
908 so->needPrimScan = true;
909 so->scanBehind = false;
910 so->oppositeDirCheck = false;
911 }
912 else if (btscan->btps_pageStatus != BTPARALLEL_ADVANCING)
913 {
914 /*
915 * We have successfully seized control of the scan for the purpose
916 * of advancing it to a new page!
917 */
918 btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
919 Assert(btscan->btps_nextScanPage != P_NONE);
920 *next_scan_page = btscan->btps_nextScanPage;
921 *last_curr_page = btscan->btps_lastCurrPage;
922 exit_loop = true;
923 }
924 LWLockRelease(&btscan->btps_lock);
925 if (exit_loop || !status)
926 break;
927 ConditionVariableSleep(&btscan->btps_cv, WAIT_EVENT_BTREE_PAGE);
928 }
929 ConditionVariableCancelSleep();
930
931 /* When the scan has reached the rightmost (or leftmost) page, end it */
932 if (endscan)
933 _bt_parallel_done(scan);
934
935 return status;
936 }
937
938 /*
939 * _bt_parallel_release() -- Complete the process of advancing the scan to a
940 * new page. We now have the new value btps_nextScanPage; another backend
941 * can now begin advancing the scan.
942 *
943 * Callers whose scan uses array keys must save their curr_page argument so
944 * that it can be passed to _bt_parallel_primscan_schedule, should caller
945 * determine that another primitive index scan is required.
946 *
947 * If caller's next_scan_page is P_NONE, the scan has reached the index's
948 * rightmost/leftmost page. This is treated as reaching the end of the scan
949 * within _bt_parallel_seize.
950 *
951 * Note: unlike the serial case, parallel scans don't need to remember both
952 * sibling links. next_scan_page is whichever link is next given the scan's
953 * direction. That's all we'll ever need, since the direction of a parallel
954 * scan can never change.
955 */
956 void
957 _bt_parallel_release(IndexScanDesc scan, BlockNumber next_scan_page,
958 BlockNumber curr_page)
959 {
960 ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
961 BTParallelScanDesc btscan;
962
963 Assert(BlockNumberIsValid(next_scan_page));
964
965 btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
966 parallel_scan->ps_offset_am);
967
968 LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
969 btscan->btps_nextScanPage = next_scan_page;
970 btscan->btps_lastCurrPage = curr_page;
971 btscan->btps_pageStatus = BTPARALLEL_IDLE;
972 LWLockRelease(&btscan->btps_lock);
973 ConditionVariableSignal(&btscan->btps_cv);
974 }
975
976 /*
977 * _bt_parallel_done() -- Mark the parallel scan as complete.
978 *
979 * When there are no pages left to scan, this function should be called to
980 * notify other workers. Otherwise, they might wait forever for the scan to
981 * advance to the next page.
982 */
983 void
984 _bt_parallel_done(IndexScanDesc scan)
985 {
986 BTScanOpaque so = (BTScanOpaque) scan->opaque;
987 ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
988 BTParallelScanDesc btscan;
989 bool status_changed = false;
990
991 Assert(!BTScanPosIsValid(so->currPos));
992
993 /* Do nothing, for non-parallel scans */
994 if (parallel_scan == NULL)
995 return;
996
997 /*
998 * Should not mark parallel scan done when there's still a pending
999 * primitive index scan
1000 */
1001 if (so->needPrimScan)
1002 return;
1003
1004 btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
1005 parallel_scan->ps_offset_am);
1006
1007 /*
1008 * Mark the parallel scan as done, unless some other process did so
1009 * already
1010 */
1011 LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
1012 Assert(btscan->btps_pageStatus != BTPARALLEL_NEED_PRIMSCAN);
1013 if (btscan->btps_pageStatus != BTPARALLEL_DONE)
1014 {
1015 btscan->btps_pageStatus = BTPARALLEL_DONE;
1016 status_changed = true;
1017 }
1018 LWLockRelease(&btscan->btps_lock);
1019
1020 /* wake up all the workers associated with this parallel scan */
1021 if (status_changed)
1022 ConditionVariableBroadcast(&btscan->btps_cv);
1023 }
1024
1025 /*
1026 * _bt_parallel_primscan_schedule() -- Schedule another primitive index scan.
1027 *
1028 * Caller passes the curr_page most recently passed to _bt_parallel_release
1029 * by its backend. Caller successfully schedules the next primitive index scan
1030 * if the shared parallel state hasn't been seized since caller's backend last
1031 * advanced the scan.
1032 */
1033 void
1034 _bt_parallel_primscan_schedule(IndexScanDesc scan, BlockNumber curr_page)
1035 {
1036 Relation rel = scan->indexRelation;
1037 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1038 ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
1039 BTParallelScanDesc btscan;
1040
1041 Assert(so->numArrayKeys);
1042
1043 btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
1044 parallel_scan->ps_offset_am);
1045
1046 LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
1047 if (btscan->btps_lastCurrPage == curr_page &&
1048 btscan->btps_pageStatus == BTPARALLEL_IDLE)
1049 {
1050 btscan->btps_nextScanPage = InvalidBlockNumber;
1051 btscan->btps_lastCurrPage = InvalidBlockNumber;
1052 btscan->btps_pageStatus = BTPARALLEL_NEED_PRIMSCAN;
1053
1054 /* Serialize scan's current array keys */
1055 _bt_parallel_serialize_arrays(rel, btscan, so);
1056 }
1057 LWLockRelease(&btscan->btps_lock);
1058 }
1059
1060 /*
1061 * Bulk deletion of all index entries pointing to a set of heap tuples.
1062 * The set of target tuples is specified via a callback routine that tells
1063 * whether any given heap tuple (identified by ItemPointer) is being deleted.
1064 *
1065 * Result: a palloc'd struct containing statistical info for VACUUM displays.
1066 */
1067 IndexBulkDeleteResult *
1068 btbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
1069 IndexBulkDeleteCallback callback, void *callback_state)
1070 {
1071 Relation rel = info->index;
1072 BTCycleId cycleid;
1073
1074 /* allocate stats if first time through, else re-use existing struct */
1075 if (stats == NULL)
1076 stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
1077
1078 /* Establish the vacuum cycle ID to use for this scan */
1079 /* The ENSURE stuff ensures we clean up shared memory on failure */
1080 PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel));
1081 {
1082 cycleid = _bt_start_vacuum(rel);
1083
1084 btvacuumscan(info, stats, callback, callback_state, cycleid);
1085 }
1086 PG_END_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel));
1087 _bt_end_vacuum(rel);
1088
1089 return stats;
1090 }
1091
1092 /*
1093 * Post-VACUUM cleanup.
1094 *
1095 * Result: a palloc'd struct containing statistical info for VACUUM displays.
1096 */
1097 IndexBulkDeleteResult *
1098 btvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
1099 {
1100 BlockNumber num_delpages;
1101
1102 /* No-op in ANALYZE ONLY mode */
1103 if (info->analyze_only)
1104 return stats;
1105
1106 /*
1107 * If btbulkdelete was called, we need not do anything (we just maintain
1108 * the information used within _bt_vacuum_needs_cleanup() by calling
1109 * _bt_set_cleanup_info() below).
1110 *
1111 * If btbulkdelete was _not_ called, then we have a choice to make: we
1112 * must decide whether or not a btvacuumscan() call is needed now (i.e.
1113 * whether the ongoing VACUUM operation can entirely avoid a physical scan
1114 * of the index). A call to _bt_vacuum_needs_cleanup() decides it for us
1115 * now.
1116 */
1117 if (stats == NULL)
1118 {
1119 /* Check if VACUUM operation can entirely avoid btvacuumscan() call */
1120 if (!_bt_vacuum_needs_cleanup(info->index))
1121 return NULL;
1122
1123 /*
1124 * Since we aren't going to actually delete any leaf items, there's no
1125 * need to go through all the vacuum-cycle-ID pushups here.
1126 *
1127 * Posting list tuples are a source of inaccuracy for cleanup-only
1128 * scans. btvacuumscan() will assume that the number of index tuples
1129 * from each page can be used as num_index_tuples, even though
1130 * num_index_tuples is supposed to represent the number of TIDs in the
1131 * index. This naive approach can underestimate the number of tuples
1132 * in the index significantly.
1133 *
1134 * We handle the problem by making num_index_tuples an estimate in
1135 * cleanup-only case.
1136 */
1137 stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
1138 btvacuumscan(info, stats, NULL, NULL, 0);
1139 stats->estimated_count = true;
1140 }
1141
1142 /*
1143 * Maintain num_delpages value in metapage for _bt_vacuum_needs_cleanup().
1144 *
1145 * num_delpages is the number of deleted pages now in the index that were
1146 * not safe to place in the FSM to be recycled just yet. num_delpages is
1147 * greater than 0 only when _bt_pagedel() actually deleted pages during
1148 * our call to btvacuumscan(). Even then, _bt_pendingfsm_finalize() must
1149 * have failed to place any newly deleted pages in the FSM just moments
1150 * ago. (Actually, there are edge cases where recycling of the current
1151 * VACUUM's newly deleted pages does not even become safe by the time the
1152 * next VACUUM comes around. See nbtree/README.)
1153 */
1154 Assert(stats->pages_deleted >= stats->pages_free);
1155 num_delpages = stats->pages_deleted - stats->pages_free;
1156 _bt_set_cleanup_info(info->index, num_delpages);
1157
1158 /*
1159 * It's quite possible for us to be fooled by concurrent page splits into
1160 * double-counting some index tuples, so disbelieve any total that exceeds
1161 * the underlying heap's count ... if we know that accurately. Otherwise
1162 * this might just make matters worse.
1163 */
1164 if (!info->estimated_count)
1165 {
1166 if (stats->num_index_tuples > info->num_heap_tuples)
1167 stats->num_index_tuples = info->num_heap_tuples;
1168 }
1169
1170 return stats;
1171 }
1172
1173 /*
1174 * btvacuumscan --- scan the index for VACUUMing purposes
1175 *
1176 * This combines the functions of looking for leaf tuples that are deletable
1177 * according to the vacuum callback, looking for empty pages that can be
1178 * deleted, and looking for old deleted pages that can be recycled. Both
1179 * btbulkdelete and btvacuumcleanup invoke this (the latter only if no
1180 * btbulkdelete call occurred and _bt_vacuum_needs_cleanup returned true).
1181 *
1182 * The caller is responsible for initially allocating/zeroing a stats struct
1183 * and for obtaining a vacuum cycle ID if necessary.
1184 */
1185 static void
1186 btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
1187 IndexBulkDeleteCallback callback, void *callback_state,
1188 BTCycleId cycleid)
1189 {
1190 Relation rel = info->index;
1191 BTVacState vstate;
1192 BlockNumber num_pages;
1193 bool needLock;
1194 BlockRangeReadStreamPrivate p;
1195 ReadStream *stream = NULL;
1196
1197 /*
1198 * Reset fields that track information about the entire index now. This
1199 * avoids double-counting in the case where a single VACUUM command
1200 * requires multiple scans of the index.
1201 *
1202 * Avoid resetting the tuples_removed and pages_newly_deleted fields here,
1203 * since they track information about the VACUUM command, and so must last
1204 * across each call to btvacuumscan().
1205 *
1206 * (Note that pages_free is treated as state about the whole index, not
1207 * the current VACUUM. This is appropriate because RecordFreeIndexPage()
1208 * calls are idempotent, and get repeated for the same deleted pages in
1209 * some scenarios. The point for us is to track the number of recyclable
1210 * pages in the index at the end of the VACUUM command.)
1211 */
1212 stats->num_pages = 0;
1213 stats->num_index_tuples = 0;
1214 stats->pages_deleted = 0;
1215 stats->pages_free = 0;
1216
1217 /* Set up info to pass down to btvacuumpage */
1218 vstate.info = info;
1219 vstate.stats = stats;
1220 vstate.callback = callback;
1221 vstate.callback_state = callback_state;
1222 vstate.cycleid = cycleid;
1223
1224 /* Create a temporary memory context to run _bt_pagedel in */
1225 vstate.pagedelcontext = AllocSetContextCreate(CurrentMemoryContext,
1226 "_bt_pagedel",
1227 ALLOCSET_DEFAULT_SIZES);
1228
1229 /* Initialize vstate fields used by _bt_pendingfsm_finalize */
1230 vstate.bufsize = 0;
1231 vstate.maxbufsize = 0;
1232 vstate.pendingpages = NULL;
1233 vstate.npendingpages = 0;
1234 /* Consider applying _bt_pendingfsm_finalize optimization */
1235 _bt_pendingfsm_init(rel, &vstate, (callback == NULL));
1236
1237 /*
1238 * The outer loop iterates over all index pages except the metapage, in
1239 * physical order (we hope the kernel will cooperate in providing
1240 * read-ahead for speed). It is critical that we visit all leaf pages,
1241 * including ones added after we start the scan, else we might fail to
1242 * delete some deletable tuples. Hence, we must repeatedly check the
1243 * relation length. We must acquire the relation-extension lock while
1244 * doing so to avoid a race condition: if someone else is extending the
1245 * relation, there is a window where bufmgr/smgr have created a new
1246 * all-zero page but it hasn't yet been write-locked by _bt_getbuf(). If
1247 * we manage to scan such a page here, we'll improperly assume it can be
1248 * recycled. Taking the lock synchronizes things enough to prevent a
1249 * problem: either num_pages won't include the new page, or _bt_getbuf
1250 * already has write lock on the buffer and it will be fully initialized
1251 * before we can examine it. Also, we need not worry if a page is added
1252 * immediately after we look; the page splitting code already has
1253 * write-lock on the left page before it adds a right page, so we must
1254 * already have processed any tuples due to be moved into such a page.
1255 *
1256 * XXX: Now that new pages are locked with RBM_ZERO_AND_LOCK, I don't
1257 * think the use of the extension lock is still required.
1258 *
1259 * We can skip locking for new or temp relations, however, since no one
1260 * else could be accessing them.
1261 */
1262 needLock = !RELATION_IS_LOCAL(rel);
1263
1264 p.current_blocknum = BTREE_METAPAGE + 1;
1265
1266 /*
1267 * It is safe to use batchmode as block_range_read_stream_cb takes no
1268 * locks.
1269 */
1270 stream = read_stream_begin_relation(READ_STREAM_MAINTENANCE |
1271 READ_STREAM_FULL |
1272 READ_STREAM_USE_BATCHING,
1273 info->strategy,
1274 rel,
1275 MAIN_FORKNUM,
1276 block_range_read_stream_cb,
1277 &p,
1278 0);
1279 for (;;)
1280 {
1281 /* Get the current relation length */
1282 if (needLock)
1283 LockRelationForExtension(rel, ExclusiveLock);
1284 num_pages = RelationGetNumberOfBlocks(rel);
1285 if (needLock)
1286 UnlockRelationForExtension(rel, ExclusiveLock);
1287
1288 if (info->report_progress)
1289 pgstat_progress_update_param(PROGRESS_SCAN_BLOCKS_TOTAL,
1290 num_pages);
1291
1292 /* Quit if we've scanned the whole relation */
1293 if (p.current_blocknum >= num_pages)
1294 break;
1295
1296 p.last_exclusive = num_pages;
1297
1298 /* Iterate over pages, then loop back to recheck relation length */
1299 while (true)
1300 {
1301 BlockNumber current_block;
1302 Buffer buf;
1303
1304 /* call vacuum_delay_point while not holding any buffer lock */
1305 vacuum_delay_point(false);
1306
1307 buf = read_stream_next_buffer(stream, NULL);
1308
1309 if (!BufferIsValid(buf))
1310 break;
1311
1312 current_block = btvacuumpage(&vstate, buf);
1313
1314 if (info->report_progress)
1315 pgstat_progress_update_param(PROGRESS_SCAN_BLOCKS_DONE,
1316 current_block);
1317 }
1318
1319 /*
1320 * We have to reset the read stream to use it again. After returning
1321 * InvalidBuffer, the read stream API won't invoke our callback again
1322 * until the stream has been reset.
1323 */
1324 read_stream_reset(stream);
1325 }
1326
1327 read_stream_end(stream);
1328
1329 /* Set statistics num_pages field to final size of index */
1330 stats->num_pages = num_pages;
1331
1332 MemoryContextDelete(vstate.pagedelcontext);
1333
1334 /*
1335 * If there were any calls to _bt_pagedel() during scan of the index then
1336 * see if any of the resulting pages can be placed in the FSM now. When
1337 * it's not safe we'll have to leave it up to a future VACUUM operation.
1338 *
1339 * Finally, if we placed any pages in the FSM (either just now or during
1340 * the scan), forcibly update the upper-level FSM pages to ensure that
1341 * searchers can find them.
1342 */
1343 _bt_pendingfsm_finalize(rel, &vstate);
1344 if (stats->pages_free > 0)
1345 IndexFreeSpaceMapVacuum(rel);
1346 }
1347
1348 /*
1349 * btvacuumpage --- VACUUM one page
1350 *
1351 * This processes a single page for btvacuumscan(). In some cases we must
1352 * backtrack to re-examine and VACUUM pages that were on buf's page during
1353 * a previous call here. This is how we handle page splits (that happened
1354 * after our cycleid was acquired) whose right half page happened to reuse
1355 * a block that we might have processed at some point before it was
1356 * recycled (i.e. before the page split).
1357 *
1358 * Returns BlockNumber of a scanned page (not backtracked).
1359 */
1360 static BlockNumber
1361 btvacuumpage(BTVacState *vstate, Buffer buf)
1362 {
1363 IndexVacuumInfo *info = vstate->info;
1364 IndexBulkDeleteResult *stats = vstate->stats;
1365 IndexBulkDeleteCallback callback = vstate->callback;
1366 void *callback_state = vstate->callback_state;
1367 Relation rel = info->index;
1368 Relation heaprel = info->heaprel;
1369 bool attempt_pagedel;
1370 BlockNumber blkno,
1371 backtrack_to;
1372 BlockNumber scanblkno = BufferGetBlockNumber(buf);
1373 Page page;
1374 BTPageOpaque opaque;
1375
1376 blkno = scanblkno;
1377
1378 backtrack:
1379
1380 attempt_pagedel = false;
1381 backtrack_to = P_NONE;
1382
1383 _bt_lockbuf(rel, buf, BT_READ);
1384 page = BufferGetPage(buf);
1385 opaque = NULL;
1386 if (!PageIsNew(page))
1387 {
1388 _bt_checkpage(rel, buf);
1389 opaque = BTPageGetOpaque(page);
1390 }
1391
1392 Assert(blkno <= scanblkno);
1393 if (blkno != scanblkno)
1394 {
1395 /*
1396 * We're backtracking.
1397 *
1398 * We followed a right link to a sibling leaf page (a page that
1399 * happens to be from a block located before scanblkno). The only
1400 * case we want to do anything with is a live leaf page having the
1401 * current vacuum cycle ID.
1402 *
1403 * The page had better be in a state that's consistent with what we
1404 * expect. Check for conditions that imply corruption in passing. It
1405 * can't be half-dead because only an interrupted VACUUM process can
1406 * leave pages in that state, so we'd definitely have dealt with it
1407 * back when the page was the scanblkno page (half-dead pages are
1408 * always marked fully deleted by _bt_pagedel(), barring corruption).
1409 */
1410 if (!opaque || !P_ISLEAF(opaque) || P_ISHALFDEAD(opaque))
1411 {
1412 Assert(false);
1413 ereport(LOG,
1414 (errcode(ERRCODE_INDEX_CORRUPTED),
1415 errmsg_internal("right sibling %u of scanblkno %u unexpectedly in an inconsistent state in index \"%s\"",
1416 blkno, scanblkno, RelationGetRelationName(rel))));
1417 _bt_relbuf(rel, buf);
1418 return scanblkno;
1419 }
1420
1421 /*
1422 * We may have already processed the page in an earlier call, when the
1423 * page was scanblkno. This happens when the leaf page split occurred
1424 * after the scan began, but before the right sibling page became the
1425 * scanblkno.
1426 *
1427 * Page may also have been deleted by current btvacuumpage() call,
1428 * since _bt_pagedel() sometimes deletes the right sibling page of
1429 * scanblkno in passing (it does so after we decided where to
1430 * backtrack to). We don't need to process this page as a deleted
1431 * page a second time now (in fact, it would be wrong to count it as a
1432 * deleted page in the bulk delete statistics a second time).
1433 */
1434 if (opaque->btpo_cycleid != vstate->cycleid || P_ISDELETED(opaque))
1435 {
1436 /* Done with current scanblkno (and all lower split pages) */
1437 _bt_relbuf(rel, buf);
1438 return scanblkno;
1439 }
1440 }
1441
1442 if (!opaque || BTPageIsRecyclable(page, heaprel))
1443 {
1444 /* Okay to recycle this page (which could be leaf or internal) */
1445 RecordFreeIndexPage(rel, blkno);
1446 stats->pages_deleted++;
1447 stats->pages_free++;
1448 }
1449 else if (P_ISDELETED(opaque))
1450 {
1451 /*
1452 * Already deleted page (which could be leaf or internal). Can't
1453 * recycle yet.
1454 */
1455 stats->pages_deleted++;
1456 }
1457 else if (P_ISHALFDEAD(opaque))
1458 {
1459 /* Half-dead leaf page (from interrupted VACUUM) -- finish deleting */
1460 attempt_pagedel = true;
1461
1462 /*
1463 * _bt_pagedel() will increment both pages_newly_deleted and
1464 * pages_deleted stats in all cases (barring corruption)
1465 */
1466 }
1467 else if (P_ISLEAF(opaque))
1468 {
1469 OffsetNumber deletable[MaxIndexTuplesPerPage];
1470 int ndeletable;
1471 BTVacuumPosting updatable[MaxIndexTuplesPerPage];
1472 int nupdatable;
1473 OffsetNumber offnum,
1474 minoff,
1475 maxoff;
1476 int nhtidsdead,
1477 nhtidslive;
1478
1479 /*
1480 * Trade in the initial read lock for a full cleanup lock on this
1481 * page. We must get such a lock on every leaf page over the course
1482 * of the vacuum scan, whether or not it actually contains any
1483 * deletable tuples --- see nbtree/README.
1484 */
1485 _bt_upgradelockbufcleanup(rel, buf);
1486
1487 /*
1488 * Check whether we need to backtrack to earlier pages. What we are
1489 * concerned about is a page split that happened since we started the
1490 * vacuum scan. If the split moved tuples on the right half of the
1491 * split (i.e. the tuples that sort high) to a block that we already
1492 * passed over, then we might have missed the tuples. We need to
1493 * backtrack now. (Must do this before possibly clearing btpo_cycleid
1494 * or deleting scanblkno page below!)
1495 */
1496 if (vstate->cycleid != 0 &&
1497 opaque->btpo_cycleid == vstate->cycleid &&
1498 !(opaque->btpo_flags & BTP_SPLIT_END) &&
1499 !P_RIGHTMOST(opaque) &&
1500 opaque->btpo_next < scanblkno)
1501 backtrack_to = opaque->btpo_next;
1502
1503 ndeletable = 0;
1504 nupdatable = 0;
1505 minoff = P_FIRSTDATAKEY(opaque);
1506 maxoff = PageGetMaxOffsetNumber(page);
1507 nhtidsdead = 0;
1508 nhtidslive = 0;
1509 if (callback)
1510 {
1511 /* btbulkdelete callback tells us what to delete (or update) */
1512 for (offnum = minoff;
1513 offnum <= maxoff;
1514 offnum = OffsetNumberNext(offnum))
1515 {
1516 IndexTuple itup;
1517
1518 itup = (IndexTuple) PageGetItem(page,
1519 PageGetItemId(page, offnum));
1520
1521 Assert(!BTreeTupleIsPivot(itup));
1522 if (!BTreeTupleIsPosting(itup))
1523 {
1524 /* Regular tuple, standard table TID representation */
1525 if (callback(&itup->t_tid, callback_state))
1526 {
1527 deletable[ndeletable++] = offnum;
1528 nhtidsdead++;
1529 }
1530 else
1531 nhtidslive++;
1532 }
1533 else
1534 {
1535 BTVacuumPosting vacposting;
1536 int nremaining;
1537
1538 /* Posting list tuple */
1539 vacposting = btreevacuumposting(vstate, itup, offnum,
1540 &nremaining);
1541 if (vacposting == NULL)
1542 {
1543 /*
1544 * All table TIDs from the posting tuple remain, so no
1545 * delete or update required
1546 */
1547 Assert(nremaining == BTreeTupleGetNPosting(itup));
1548 }
1549 else if (nremaining > 0)
1550 {
1551
1552 /*
1553 * Store metadata about posting list tuple in
1554 * updatable array for entire page. Existing tuple
1555 * will be updated during the later call to
1556 * _bt_delitems_vacuum().
1557 */
1558 Assert(nremaining < BTreeTupleGetNPosting(itup));
1559 updatable[nupdatable++] = vacposting;
1560 nhtidsdead += BTreeTupleGetNPosting(itup) - nremaining;
1561 }
1562 else
1563 {
1564 /*
1565 * All table TIDs from the posting list must be
1566 * deleted. We'll delete the index tuple completely
1567 * (no update required).
1568 */
1569 Assert(nremaining == 0);
1570 deletable[ndeletable++] = offnum;
1571 nhtidsdead += BTreeTupleGetNPosting(itup);
1572 pfree(vacposting);
1573 }
1574
1575 nhtidslive += nremaining;
1576 }
1577 }
1578 }
1579
1580 /*
1581 * Apply any needed deletes or updates. We issue just one
1582 * _bt_delitems_vacuum() call per page, so as to minimize WAL traffic.
1583 */
1584 if (ndeletable > 0 || nupdatable > 0)
1585 {
1586 Assert(nhtidsdead >= ndeletable + nupdatable);
1587 _bt_delitems_vacuum(rel, buf, deletable, ndeletable, updatable,
1588 nupdatable);
1589
1590 stats->tuples_removed += nhtidsdead;
1591 /* must recompute maxoff */
1592 maxoff = PageGetMaxOffsetNumber(page);
1593
1594 /* can't leak memory here */
1595 for (int i = 0; i < nupdatable; i++)
1596 pfree(updatable[i]);
1597 }
1598 else
1599 {
1600 /*
1601 * If the leaf page has been split during this vacuum cycle, it
1602 * seems worth expending a write to clear btpo_cycleid even if we
1603 * don't have any deletions to do. (If we do, _bt_delitems_vacuum
1604 * takes care of this.) This ensures we won't process the page
1605 * again.
1606 *
1607 * We treat this like a hint-bit update because there's no need to
1608 * WAL-log it.
1609 */
1610 Assert(nhtidsdead == 0);
1611 if (vstate->cycleid != 0 &&
1612 opaque->btpo_cycleid == vstate->cycleid)
1613 {
1614 opaque->btpo_cycleid = 0;
1615 MarkBufferDirtyHint(buf, true);
1616 }
1617 }
1618
1619 /*
1620 * If the leaf page is now empty, try to delete it; else count the
1621 * live tuples (live table TIDs in posting lists are counted as
1622 * separate live tuples). We don't delete when backtracking, though,
1623 * since that would require teaching _bt_pagedel() about backtracking
1624 * (doesn't seem worth adding more complexity to deal with that).
1625 *
1626 * We don't count the number of live TIDs during cleanup-only calls to
1627 * btvacuumscan (i.e. when callback is not set). We count the number
1628 * of index tuples directly instead. This avoids the expense of
1629 * directly examining all of the tuples on each page. VACUUM will
1630 * treat num_index_tuples as an estimate in cleanup-only case, so it
1631 * doesn't matter that this underestimates num_index_tuples
1632 * significantly in some cases.
1633 */
1634 if (minoff > maxoff)
1635 attempt_pagedel = (blkno == scanblkno);
1636 else if (callback)
1637 stats->num_index_tuples += nhtidslive;
1638 else
1639 stats->num_index_tuples += maxoff - minoff + 1;
1640
1641 Assert(!attempt_pagedel || nhtidslive == 0);
1642 }
1643
1644 if (attempt_pagedel)
1645 {
1646 MemoryContext oldcontext;
1647
1648 /* Run pagedel in a temp context to avoid memory leakage */
1649 MemoryContextReset(vstate->pagedelcontext);
1650 oldcontext = MemoryContextSwitchTo(vstate->pagedelcontext);
1651
1652 /*
1653 * _bt_pagedel maintains the bulk delete stats on our behalf;
1654 * pages_newly_deleted and pages_deleted are likely to be incremented
1655 * during call
1656 */
1657 Assert(blkno == scanblkno);
1658 _bt_pagedel(rel, buf, vstate);
1659
1660 MemoryContextSwitchTo(oldcontext);
1661 /* pagedel released buffer, so we shouldn't */
1662 }
1663 else
1664 _bt_relbuf(rel, buf);
1665
1666 if (backtrack_to != P_NONE)
1667 {
1668 blkno = backtrack_to;
1669
1670 /* check for vacuum delay while not holding any buffer lock */
1671 vacuum_delay_point(false);
1672
1673 /*
1674 * We can't use _bt_getbuf() here because it always applies
1675 * _bt_checkpage(), which will barf on an all-zero page. We want to
1676 * recycle all-zero pages, not fail. Also, we want to use a
1677 * nondefault buffer access strategy.
1678 */
1679 buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL,
1680 info->strategy);
1681 goto backtrack;
1682 }
1683
1684 return scanblkno;
1685 }
1686
1687 /*
1688 * btreevacuumposting --- determine TIDs still needed in posting list
1689 *
1690 * Returns metadata describing how to build replacement tuple without the TIDs
1691 * that VACUUM needs to delete. Returned value is NULL in the common case
1692 * where no changes are needed to caller's posting list tuple (we avoid
1693 * allocating memory here as an optimization).
1694 *
1695 * The number of TIDs that should remain in the posting list tuple is set for
1696 * caller in *nremaining.
1697 */
1698 static BTVacuumPosting
1699 btreevacuumposting(BTVacState *vstate, IndexTuple posting,
1700 OffsetNumber updatedoffset, int *nremaining)
1701 {
1702 int live = 0;
1703 int nitem = BTreeTupleGetNPosting(posting);
1704 ItemPointer items = BTreeTupleGetPosting(posting);
1705 BTVacuumPosting vacposting = NULL;
1706
1707 for (int i = 0; i < nitem; i++)
1708 {
1709 if (!vstate->callback(items + i, vstate->callback_state))
1710 {
1711 /* Live table TID */
1712 live++;
1713 }
1714 else if (vacposting == NULL)
1715 {
1716 /*
1717 * First dead table TID encountered.
1718 *
1719 * It's now clear that we need to delete one or more dead table
1720 * TIDs, so start maintaining metadata describing how to update
1721 * existing posting list tuple.
1722 */
1723 vacposting = palloc(offsetof(BTVacuumPostingData, deletetids) +
1724 nitem * sizeof(uint16));
1725
1726 vacposting->itup = posting;
1727 vacposting->updatedoffset = updatedoffset;
1728 vacposting->ndeletedtids = 0;
1729 vacposting->deletetids[vacposting->ndeletedtids++] = i;
1730 }
1731 else
1732 {
1733 /* Second or subsequent dead table TID */
1734 vacposting->deletetids[vacposting->ndeletedtids++] = i;
1735 }
1736 }
1737
1738 *nremaining = live;
1739 return vacposting;
1740 }
1741
1742 /*
1743 * btcanreturn() -- Check whether btree indexes support index-only scans.
1744 *
1745 * btrees always do, so this is trivial.
1746 */
1747 bool
1748 btcanreturn(Relation index, int attno)
1749 {
1750 return true;
1751 }
1752
1753 /*
1754 * btgettreeheight() -- Compute tree height for use by btcostestimate().
1755 */
1756 int
1757 btgettreeheight(Relation rel)
1758 {
1759 return _bt_getrootheight(rel);
1760 }
1761
1762 CompareType
1763 bttranslatestrategy(StrategyNumber strategy, Oid opfamily)
1764 {
1765 switch (strategy)
1766 {
1767 case BTLessStrategyNumber:
1768 return COMPARE_LT;
1769 case BTLessEqualStrategyNumber:
1770 return COMPARE_LE;
1771 case BTEqualStrategyNumber:
1772 return COMPARE_EQ;
1773 case BTGreaterEqualStrategyNumber:
1774 return COMPARE_GE;
1775 case BTGreaterStrategyNumber:
1776 return COMPARE_GT;
1777 default:
1778 return COMPARE_INVALID;
1779 }
1780 }
1781
1782 StrategyNumber
1783 bttranslatecmptype(CompareType cmptype, Oid opfamily)
1784 {
1785 switch (cmptype)
1786 {
1787 case COMPARE_LT:
1788 return BTLessStrategyNumber;
1789 case COMPARE_LE:
1790 return BTLessEqualStrategyNumber;
1791 case COMPARE_EQ:
1792 return BTEqualStrategyNumber;
1793 case COMPARE_GE:
1794 return BTGreaterEqualStrategyNumber;
1795 case COMPARE_GT:
1796 return BTGreaterStrategyNumber;
1797 default:
1798 return InvalidStrategy;
1799 }
1800 }