| blob | ccf824bbdb20a4c179a324154f84a0acccc8c9b3 |
1 /*
2 * brin.c
3 * Implementation of BRIN indexes for Postgres
4 *
5 * See src/backend/access/brin/README for details.
6 *
7 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
9 *
10 * IDENTIFICATION
11 * src/backend/access/brin/brin.c
12 *
13 * TODO
14 * * ScalarArrayOpExpr (amsearcharray -> SK_SEARCHARRAY)
15 */
46 /* Magic numbers for parallel state sharing */
47 #define PARALLEL_KEY_BRIN_SHARED UINT64CONST(0xB000000000000001)
48 #define PARALLEL_KEY_TUPLESORT UINT64CONST(0xB000000000000002)
49 #define PARALLEL_KEY_QUERY_TEXT UINT64CONST(0xB000000000000003)
50 #define PARALLEL_KEY_WAL_USAGE UINT64CONST(0xB000000000000004)
51 #define PARALLEL_KEY_BUFFER_USAGE UINT64CONST(0xB000000000000005)
53 /*
54 * Status for index builds performed in parallel. This is allocated in a
55 * dynamic shared memory segment.
56 */
58 {
59 /*
60 * These fields are not modified during the build. They primarily exist
61 * for the benefit of worker processes that need to create state
62 * corresponding to that used by the leader.
63 */
64 Oid heaprelid;
65 Oid indexrelid;
67 BlockNumber pagesPerRange;
70 /* Query ID, for report in worker processes */
71 uint64 queryid;
73 /*
74 * workersdonecv is used to monitor the progress of workers. All parallel
75 * participants must indicate that they are done before leader can use
76 * results built by the workers (and before leader can write the data into
77 * the index).
78 */
79 ConditionVariable workersdonecv;
81 /*
82 * mutex protects all fields before heapdesc.
83 *
84 * These fields contain status information of interest to BRIN index
85 * builds that must work just the same when an index is built in parallel.
86 */
87 slock_t mutex;
89 /*
90 * Mutable state that is maintained by workers, and reported back to
91 * leader at end of the scans.
92 *
93 * nparticipantsdone is number of worker processes finished.
94 *
95 * reltuples is the total number of input heap tuples.
96 *
97 * indtuples is the total number of tuples that made it into the index.
98 */
103 /*
104 * ParallelTableScanDescData data follows. Can't directly embed here, as
105 * implementations of the parallel table scan desc interface might need
106 * stronger alignment.
107 */
110 /*
111 * Return pointer to a BrinShared's parallel table scan.
112 *
113 * c.f. shm_toc_allocate as to why BUFFERALIGN is used, rather than just
114 * MAXALIGN.
115 */
116 #define ParallelTableScanFromBrinShared(shared) \
117 (ParallelTableScanDesc) ((char *) (shared) + BUFFERALIGN(sizeof(BrinShared)))
119 /*
120 * Status for leader in parallel index build.
121 */
123 {
124 /* parallel context itself */
127 /*
128 * nparticipanttuplesorts is the exact number of worker processes
129 * successfully launched, plus one leader process if it participates as a
130 * worker (only DISABLE_LEADER_PARTICIPATION builds avoid leader
131 * participating as a worker).
132 */
135 /*
136 * Leader process convenience pointers to shared state (leader avoids TOC
137 * lookups).
138 *
139 * brinshared is the shared state for entire build. sharedsort is the
140 * shared, tuplesort-managed state passed to each process tuplesort.
141 * snapshot is the snapshot used by the scan iff an MVCC snapshot is
142 * required.
143 */
146 Snapshot snapshot;
151 /*
152 * We use a BrinBuildState during initial construction of a BRIN index.
153 * The running state is kept in a BrinMemTuple.
154 */
156 {
157 Relation bs_irel;
160 Buffer bs_currentInsertBuf;
161 BlockNumber bs_pagesPerRange;
162 BlockNumber bs_currRangeStart;
163 BlockNumber bs_maxRangeStart;
169 Size bs_emptyTupleLen;
170 MemoryContext bs_context;
172 /*
173 * bs_leader is only present when a parallel index build is performed, and
174 * only in the leader process. (Actually, only the leader process has a
175 * BrinBuildState.)
176 */
180 /*
181 * The sortstate is used by workers (including the leader). It has to be
182 * part of the build state, because that's the only thing passed to the
183 * build callback etc.
184 */
188 /*
189 * We use a BrinInsertState to capture running state spanning multiple
190 * brininsert invocations, within the same command.
191 */
193 {
196 BlockNumber bis_pages_per_range;
199 /*
200 * Struct used as "opaque" during index scans
201 */
203 {
204 BlockNumber bo_pagesPerRange;
209 #define BRIN_ALL_BLOCKRANGES InvalidBlockNumber
213 BlockNumber pagesPerRange,
214 BlockNumber tablePages);
230 /* parallel index builds */
245 /*
246 * BRIN handler function: return IndexAmRoutine with access method parameters
247 * and callbacks.
248 */
249 Datum
251 {
274 VACUUM_OPTION_PARALLEL_CLEANUP;
305 }
307 /*
308 * Initialize a BrinInsertState to maintain state to be used across multiple
309 * tuple inserts, within the same command.
310 */
313 {
315 MemoryContext oldcxt;
326 }
328 /*
329 * A tuple in the heap is being inserted. To keep a brin index up to date,
330 * we need to obtain the relevant index tuple and compare its stored values
331 * with those of the new tuple. If the tuple values are not consistent with
332 * the summary tuple, we need to update the index tuple.
333 *
334 * If autosummarization is enabled, check if we need to summarize the previous
335 * page range.
336 *
337 * If the range is not currently summarized (i.e. the revmap returns NULL for
338 * it), there's nothing to do for this tuple.
339 */
340 bool
343 IndexUniqueCheck checkUnique,
346 {
347 BlockNumber pagesPerRange;
348 BlockNumber origHeapBlk;
349 BlockNumber heapBlk;
358 /*
359 * If first time through in this statement, initialize the insert state
360 * that we keep for all the inserts in the command.
361 */
369 /*
370 * origHeapBlk is the block number where the insertion occurred. heapBlk
371 * is the first block in the corresponding page range.
372 */
377 {
379 OffsetNumber off;
385 /*
386 * If auto-summarization is enabled and we just inserted the first
387 * tuple into the first block of a new non-first page range, request a
388 * summarization run of the previous range.
389 */
394 {
398 lastPageTuple =
402 {
407 lastPageRange);
413 lastPageRange)));
414 }
415 else
417 }
422 /* if range is unsummarized, there's nothing to do */
426 /* First time through in this brininsert call? */
428 {
431 ALLOCSET_DEFAULT_SIZES);
433 }
440 {
441 /*
442 * The tuple is consistent with the new values, so there's nothing
443 * to do.
444 */
446 }
447 else
448 {
451 Size origsz;
453 Size newsz;
457 /*
458 * Make a copy of the old tuple, so that we can compare it after
459 * re-acquiring the lock.
460 */
464 /*
465 * Before releasing the lock, check if we can attempt a same-page
466 * update. Another process could insert a tuple concurrently in
467 * the same page though, so downstream we must be prepared to cope
468 * if this turns out to not be possible after all.
469 */
474 /*
475 * Try to update the tuple. If this doesn't work for whatever
476 * reason, we need to restart from the top; the revmap might be
477 * pointing at a different tuple for this block now, so we need to
478 * recompute to ensure both our new heap tuple and the other
479 * inserter's are covered by the combined tuple. It might be that
480 * we don't need to update at all.
481 */
484 samepage))
485 {
486 /* no luck; start over */
489 }
490 }
492 /* success! */
494 }
503 }
505 /*
506 * Callback to clean up the BrinInsertState once all tuple inserts are done.
507 */
508 void
510 {
513 /* bail out if cache not initialized */
517 /*
518 * Clean up the revmap. Note that the brinDesc has already been cleaned up
519 * as part of its own memory context.
520 */
524 }
526 /*
527 * Initialize state for a BRIN index scan.
528 *
529 * We read the metapage here to determine the pages-per-range number that this
530 * index was built with. Note that since this cannot be changed while we're
531 * holding lock on index, it's not necessary to recompute it during brinrescan.
532 */
533 IndexScanDesc
535 {
536 IndexScanDesc scan;
547 }
549 /*
550 * Execute the index scan.
551 *
552 * This works by reading index TIDs from the revmap, and obtaining the index
553 * tuples pointed to by them; the summary values in the index tuples are
554 * compared to the scan keys. We return into the TID bitmap all the pages in
555 * ranges corresponding to index tuples that match the scan keys.
556 *
557 * If a TID from the revmap is read as InvalidTID, we know that range is
558 * unsummarized. Pages in those ranges need to be returned regardless of scan
559 * keys.
560 */
561 int64
563 {
567 Oid heapOid;
568 Relation heapRel;
570 BlockNumber nblocks;
571 BlockNumber heapBlk;
574 MemoryContext oldcxt;
575 MemoryContext perRangeCxt;
584 Size len;
591 /*
592 * We need to know the size of the table so that we know how long to
593 * iterate on the revmap.
594 */
600 /*
601 * Make room for the consistent support procedures of indexed columns. We
602 * don't look them up here; we do that lazily the first time we see a scan
603 * key reference each of them. We rely on zeroing fn_oid to InvalidOid.
604 */
607 /*
608 * Make room for per-attribute lists of scan keys that we'll pass to the
609 * consistent support procedure. We don't know which attributes have scan
610 * keys, so we allocate space for all attributes. That may use more memory
611 * but it's probably cheaper than determining which attributes are used.
612 *
613 * We keep null and regular keys separate, so that we can pass just the
614 * regular keys to the consistent function easily.
615 *
616 * To reduce the allocation overhead, we allocate one big chunk and then
617 * carve it into smaller arrays ourselves. All the pieces have exactly the
618 * same lifetime, so that's OK.
619 *
620 * XXX The widest index can have 32 attributes, so the amount of wasted
621 * memory is negligible. We could invent a more compact approach (with
622 * just space for used attributes) but that would make the matching more
623 * complex so it's not a good trade-off.
624 */
625 len =
649 {
655 }
659 /* zero the number of keys */
663 /* Preprocess the scan keys - split them into per-attribute arrays. */
665 {
669 /*
670 * The collation of the scan key must match the collation used in the
671 * index column (but only if the search is not IS NULL/ IS NOT NULL).
672 * Otherwise we shouldn't be using this index ...
673 */
679 /*
680 * First time we see this index attribute, so init as needed.
681 *
682 * This is a bit of an overkill - we don't know how many scan keys are
683 * there for this attribute, so we simply allocate the largest number
684 * possible (as if all keys were for this attribute). This may waste a
685 * bit of memory, but we only expect small number of scan keys in
686 * general, so this should be negligible, and repeated repalloc calls
687 * are not free either.
688 */
690 {
693 /* First time we see this attribute, so no key/null keys. */
698 BRIN_PROCNUM_CONSISTENT);
700 CurrentMemoryContext);
701 }
703 /* Add key to the proper per-attribute array. */
705 {
708 }
709 else
710 {
713 }
714 }
716 /* allocate an initial in-memory tuple, out of the per-range memcxt */
719 /*
720 * Setup and use a per-range memory context, which is reset every time we
721 * loop below. This avoids having to free the tuples within the loop.
722 */
725 ALLOCSET_DEFAULT_SIZES);
728 /*
729 * Now scan the revmap. We start by querying for heap page 0,
730 * incrementing by the number of pages per range; this gives us a full
731 * view of the table.
732 */
734 {
738 OffsetNumber off;
739 Size size;
748 {
752 }
754 /*
755 * For page ranges with no indexed tuple, we must return the whole
756 * range; otherwise, compare it to the scan keys.
757 */
759 {
761 }
762 else
763 {
766 {
767 /*
768 * Placeholder tuples are always returned, regardless of the
769 * values stored in them.
770 */
772 }
773 else
774 {
777 /*
778 * Compare scan keys with summary values stored for the range.
779 * If scan keys are matched, the page range must be added to
780 * the bitmap. We initially assume the range needs to be
781 * added; in particular this serves the case where there are
782 * no keys.
783 */
786 {
788 Datum add;
789 Oid collation;
791 /*
792 * skip attributes without any scan keys (both regular and
793 * IS [NOT] NULL)
794 */
800 /*
801 * If the BRIN tuple indicates that this range is empty,
802 * we can skip it: there's nothing to match. We don't
803 * need to examine the next columns.
804 */
806 {
809 }
811 /*
812 * First check if there are any IS [NOT] NULL scan keys,
813 * and if we're violating them. In that case we can
814 * terminate early, without invoking the support function.
815 *
816 * As there may be more keys, we can only determine
817 * mismatch within this loop.
818 */
822 {
823 /*
824 * If any of the IS [NOT] NULL keys failed, the page
825 * range as a whole can't pass. So terminate the loop.
826 */
829 }
831 /*
832 * So either there are no IS [NOT] NULL keys, or all
833 * passed. If there are no regular scan keys, we're done -
834 * the page range matches. If there are regular keys, but
835 * the page range is marked as 'all nulls' it can't
836 * possibly pass (we're assuming the operators are
837 * strict).
838 */
840 /* No regular scan keys - page range as a whole passes. */
847 /* If it is all nulls, it cannot possibly be consistent. */
849 {
852 }
854 /*
855 * Collation from the first key (has to be the same for
856 * all keys for the same attribute).
857 */
860 /*
861 * Check whether the scan key is consistent with the page
862 * range values; if so, have the pages in the range added
863 * to the output bitmap.
864 *
865 * The opclass may or may not support processing of
866 * multiple scan keys. We can determine that based on the
867 * number of arguments - functions with extra parameter
868 * (number of scan keys) do support this, otherwise we
869 * have to simply pass the scan keys one by one.
870 */
872 {
873 /* Check all keys at once */
875 collation,
881 }
882 else
883 {
884 /*
885 * Check keys one by one
886 *
887 * When there are multiple scan keys, failure to meet
888 * the criteria for a single one of them is enough to
889 * discard the range as a whole, so break out of the
890 * loop as soon as a false return value is obtained.
891 */
895 {
904 }
905 }
907 /*
908 * If we found a scan key eliminating the range, no need
909 * to check additional ones.
910 */
913 }
914 }
915 }
917 /* add the pages in the range to the output bitmap, if needed */
919 {
920 BlockNumber pageno;
924 pageno++)
925 {
928 totalpages++;
930 }
931 }
932 }
940 /*
941 * XXX We have an approximation of the number of *pages* that our scan
942 * returns, but we don't have a precise idea of the number of heap tuples
943 * involved.
944 */
946 }
948 /*
949 * Re-initialize state for a BRIN index scan
950 */
951 void
954 {
955 /*
956 * Other index AMs preprocess the scan keys at this point, or sometime
957 * early during the scan; this lets them optimize by removing redundant
958 * keys, or doing early returns when they are impossible to satisfy; see
959 * _bt_preprocess_keys for an example. Something like that could be added
960 * here someday, too.
961 */
965 }
967 /*
968 * Close down a BRIN index scan
969 */
970 void
972 {
978 }
980 /*
981 * Per-heap-tuple callback for table_index_build_scan.
982 *
983 * Note we don't worry about the page range at the end of the table here; it is
984 * present in the build state struct after we're called the last time, but not
985 * inserted into the index. Caller must ensure to do so, if appropriate.
986 */
987 static void
989 ItemPointer tid,
994 {
996 BlockNumber thisblock;
1000 /*
1001 * If we're in a block that belongs to a future range, summarize what
1002 * we've got and start afresh. Note the scan might have skipped many
1003 * pages, if they were devoid of live tuples; make sure to insert index
1004 * tuples for those too.
1005 */
1007 {
1014 /* create the index tuple and insert it */
1017 /* set state to correspond to the next range */
1020 /* re-initialize state for it */
1022 }
1024 /* Accumulate the current tuple into the running state */
1027 }
1029 /*
1030 * Per-heap-tuple callback for table_index_build_scan with parallelism.
1031 *
1032 * A version of the callback used by parallel index builds. The main difference
1033 * is that instead of writing the BRIN tuples into the index, we write them
1034 * into a shared tuplesort, and leave the insertion up to the leader (which may
1035 * reorder them a bit etc.). The callback also does not generate empty ranges,
1036 * those will be added by the leader when merging results from workers.
1037 */
1038 static void
1040 ItemPointer tid,
1045 {
1047 BlockNumber thisblock;
1051 /*
1052 * If we're in a block that belongs to a different range, summarize what
1053 * we've got and start afresh. Note the scan might have skipped many
1054 * pages, if they were devoid of live tuples; we do not create empty BRIN
1055 * ranges here - the leader is responsible for filling them in.
1056 *
1057 * Unlike serial builds, parallel index builds allow synchronized seqscans
1058 * (because that's what parallel scans do). This means the block may wrap
1059 * around to the beginning of the relation, so the condition needs to
1060 * check for both future and past ranges.
1061 */
1064 {
1071 /* create the index tuple and write it into the tuplesort */
1074 /*
1075 * Set state to correspond to the next range (for this block).
1076 *
1077 * This skips ranges that are either empty (and so we don't get any
1078 * tuples to summarize), or processed by other workers. We can't
1079 * differentiate those cases here easily, so we leave it up to the
1080 * leader to fill empty ranges where needed.
1081 */
1082 state->bs_currRangeStart
1085 /* re-initialize state for it */
1087 }
1089 /* Accumulate the current tuple into the running state */
1092 }
1094 /*
1095 * brinbuild() -- build a new BRIN index.
1096 */
1097 IndexBuildResult *
1099 {
1105 Buffer meta;
1106 BlockNumber pagesPerRange;
1108 /*
1109 * We expect to be called exactly once for any index relation.
1110 */
1115 /*
1116 * Critical section not required, because on error the creation of the
1117 * whole relation will be rolled back.
1118 */
1125 BRIN_CURRENT_VERSION);
1129 {
1130 xl_brin_createidx xlrec;
1131 XLogRecPtr recptr;
1132 Page page;
1145 }
1149 /*
1150 * Initialize our state, including the deformed tuple state.
1151 */
1156 /*
1157 * Attempt to launch parallel worker scan when required
1158 *
1159 * XXX plan_create_index_workers makes the number of workers dependent on
1160 * maintenance_work_mem, requiring 32MB for each worker. That makes sense
1161 * for btree, but not for BRIN, which can do with much less memory. So
1162 * maybe make that somehow less strict, optionally?
1163 */
1168 /*
1169 * If parallel build requested and at least one worker process was
1170 * successfully launched, set up coordination state, wait for workers to
1171 * complete. Then read all tuples from the shared tuplesort and insert
1172 * them into the index.
1173 *
1174 * In serial mode, simply scan the table and build the index one index
1175 * tuple at a time.
1176 */
1178 {
1179 SortCoordinate coordinate;
1187 /*
1188 * Begin leader tuplesort.
1189 *
1190 * In cases where parallelism is involved, the leader receives the
1191 * same share of maintenance_work_mem as a serial sort (it is
1192 * generally treated in the same way as a serial sort once we return).
1193 * Parallel worker Tuplesortstates will have received only a fraction
1194 * of maintenance_work_mem, though.
1195 *
1196 * We rely on the lifetime of the Leader Tuplesortstate almost not
1197 * overlapping with any worker Tuplesortstate's lifetime. There may
1198 * be some small overlap, but that's okay because we rely on leader
1199 * Tuplesortstate only allocating a small, fixed amount of memory
1200 * here. When its tuplesort_performsort() is called (by our caller),
1201 * and significant amounts of memory are likely to be used, all
1202 * workers must have already freed almost all memory held by their
1203 * Tuplesortstates (they are about to go away completely, too). The
1204 * overall effect is that maintenance_work_mem always represents an
1205 * absolute high watermark on the amount of memory used by a CREATE
1206 * INDEX operation, regardless of the use of parallelism or any other
1207 * factor.
1208 */
1211 TUPLESORT_NONE);
1213 /* scan the relation and merge per-worker results */
1217 }
1219 {
1220 /*
1221 * Now scan the relation. No syncscan allowed here because we want
1222 * the heap blocks in physical order (we want to produce the ranges
1223 * starting from block 0, and the callback also relies on this to not
1224 * generate summary for the same range twice).
1225 */
1229 /*
1230 * process the final batch
1231 *
1232 * XXX Note this does not update state->bs_currRangeStart, i.e. it
1233 * stays set to the last range added to the index. This is OK, because
1234 * that's what brin_fill_empty_ranges expects.
1235 */
1238 /*
1239 * Backfill the final ranges with empty data.
1240 *
1241 * This saves us from doing what amounts to full table scans when the
1242 * index with a predicate like WHERE (nonnull_column IS NULL), or
1243 * other very selective predicates.
1244 */
1248 }
1250 /* release resources */
1255 /*
1256 * Return statistics
1257 */
1264 }
1266 void
1268 {
1269 Buffer metabuf;
1271 /* An empty BRIN index has a metapage only. */
1275 /* Initialize and xlog metabuffer. */
1278 BRIN_CURRENT_VERSION);
1284 }
1286 /*
1287 * brinbulkdelete
1288 * Since there are no per-heap-tuple index tuples in BRIN indexes,
1289 * there's not a lot we can do here.
1290 *
1291 * XXX we could mark item tuples as "dirty" (when a minimum or maximum heap
1292 * tuple is deleted), meaning the need to re-run summarization on the affected
1293 * range. Would need to add an extra flag in brintuples for that.
1294 */
1295 IndexBulkDeleteResult *
1298 {
1299 /* allocate stats if first time through, else re-use existing struct */
1304 }
1306 /*
1307 * This routine is in charge of "vacuuming" a BRIN index: we just summarize
1308 * ranges that are currently unsummarized.
1309 */
1310 IndexBulkDeleteResult *
1312 {
1313 Relation heapRel;
1315 /* No-op in ANALYZE ONLY mode */
1322 /* rest of stats is initialized by zeroing */
1325 AccessShareLock);
1335 }
1337 /*
1338 * reloptions processor for BRIN indexes
1339 */
1340 bytea *
1342 {
1346 };
1349 RELOPT_KIND_BRIN,
1352 }
1354 /*
1355 * SQL-callable function to scan through an index and summarize all ranges
1356 * that are not currently summarized.
1357 */
1358 Datum
1360 {
1364 relation,
1366 }
1368 /*
1369 * SQL-callable function to summarize the indicated page range, if not already
1370 * summarized. If the second argument is BRIN_ALL_BLOCKRANGES, all
1371 * unsummarized ranges are summarized.
1372 */
1373 Datum
1375 {
1378 BlockNumber heapBlk;
1379 Oid heapoid;
1380 Relation indexRel;
1381 Relation heapRel;
1382 Oid save_userid;
1400 /*
1401 * We must lock table before index to avoid deadlocks. However, if the
1402 * passed indexoid isn't an index then IndexGetRelation() will fail.
1403 * Rather than emitting a not-very-helpful error message, postpone
1404 * complaining, expecting that the is-it-an-index test below will fail.
1405 */
1408 {
1411 /*
1412 * Autovacuum calls us. For its benefit, switch to the table owner's
1413 * userid, so that any index functions are run as that user. Also
1414 * lock down security-restricted operations and arrange to make GUC
1415 * variable changes local to this command. This is harmless, albeit
1416 * unnecessary, when called from SQL, because we fail shortly if the
1417 * user does not own the index.
1418 */
1424 }
1425 else
1426 {
1428 /* Set these just to suppress "uninitialized variable" warnings */
1432 }
1436 /* Must be a BRIN index */
1444 /* User must own the index (comparable to privileges needed for VACUUM) */
1449 /*
1450 * Since we did the IndexGetRelation call above without any lock, it's
1451 * barely possible that a race against an index drop/recreation could have
1452 * netted us the wrong table. Recheck.
1453 */
1460 /* see gin_clean_pending_list() */
1463 else
1469 /* Roll back any GUC changes executed by index functions */
1472 /* Restore userid and security context */
1479 }
1481 /*
1482 * SQL-callable interface to mark a range as no longer summarized
1483 */
1484 Datum
1486 {
1489 BlockNumber heapBlk;
1490 Oid heapoid;
1491 Relation heapRel;
1492 Relation indexRel;
1508 /*
1509 * We must lock table before index to avoid deadlocks. However, if the
1510 * passed indexoid isn't an index then IndexGetRelation() will fail.
1511 * Rather than emitting a not-very-helpful error message, postpone
1512 * complaining, expecting that the is-it-an-index test below will fail.
1513 *
1514 * Unlike brin_summarize_range(), autovacuum never calls this. Hence, we
1515 * don't switch userid.
1516 */
1520 else
1525 /* Must be a BRIN index */
1533 /* User must own the index (comparable to privileges needed for VACUUM) */
1538 /*
1539 * Since we did the IndexGetRelation call above without any lock, it's
1540 * barely possible that a race against an index drop/recreation could have
1541 * netted us the wrong table. Recheck.
1542 */
1549 /* see gin_clean_pending_list() */
1551 {
1552 /* the revmap does the hard work */
1553 do
1554 {
1556 }
1558 }
1559 else
1569 }
1571 /*
1572 * Build a BrinDesc used to create or scan a BRIN index
1573 */
1574 BrinDesc *
1576 {
1579 TupleDesc tupdesc;
1583 MemoryContext cxt;
1584 MemoryContext oldcxt;
1588 ALLOCSET_SMALL_SIZES);
1592 /*
1593 * Obtain BrinOpcInfo for each indexed column. While at it, accumulate
1594 * the number of columns stored, since the number is opclass-defined.
1595 */
1598 {
1607 }
1609 /* Allocate our result struct and fill it in */
1627 }
1629 void
1631 {
1632 /* make sure the tupdesc is still valid */
1634 /* no need for retail pfree */
1636 }
1638 /*
1639 * Fetch index's statistical data into *stats
1640 */
1641 void
1643 {
1644 Buffer metabuffer;
1645 Page metapage;
1657 }
1659 /*
1660 * Initialize a BrinBuildState appropriate to create tuples on the given index.
1661 */
1665 {
1687 /* Remember the memory context to use for an empty tuple, if needed. */
1692 /*
1693 * Calculate the start of the last page range. Page numbers are 0-based,
1694 * so to calculate the index we need to subtract one. The integer division
1695 * gives us the index of the page range.
1696 */
1700 /* Now calculate the start of the next range. */
1704 }
1706 /*
1707 * Release resources associated with a BrinBuildState.
1708 */
1709 static void
1711 {
1712 /*
1713 * Release the last index buffer used. We might as well ensure that
1714 * whatever free space remains in that page is available in FSM, too.
1715 */
1717 {
1718 Page page;
1719 Size freespace;
1720 BlockNumber blk;
1728 }
1733 }
1735 /*
1736 * On the given BRIN index, summarize the heap page range that corresponds
1737 * to the heap block number given.
1738 *
1739 * This routine can run in parallel with insertions into the heap. To avoid
1740 * missing those values from the summary tuple, we first insert a placeholder
1741 * index tuple into the index, then execute the heap scan; transactions
1742 * concurrent with the scan update the placeholder tuple. After the scan, we
1743 * union the placeholder tuple with the one computed by this routine. The
1744 * update of the index value happens in a loop, so that if somebody updates
1745 * the placeholder tuple after we read it, we detect the case and try again.
1746 * This ensures that the concurrently inserted tuples are not lost.
1747 *
1748 * A further corner case is this routine being asked to summarize the partial
1749 * range at the end of the table. heapNumBlocks is the (possibly outdated)
1750 * table size; if we notice that the requested range lies beyond that size,
1751 * we re-compute the table size after inserting the placeholder tuple, to
1752 * avoid missing pages that were appended recently.
1753 */
1754 static void
1757 {
1758 Buffer phbuf;
1760 Size phsz;
1761 OffsetNumber offset;
1762 BlockNumber scanNumBlks;
1764 /*
1765 * Insert the placeholder tuple
1766 */
1773 /*
1774 * Compute range end. We hold ShareUpdateExclusive lock on table, so it
1775 * cannot shrink concurrently (but it can grow).
1776 */
1779 {
1780 /*
1781 * If we're asked to scan what we believe to be the final range on the
1782 * table (i.e. a range that might be partial) we need to recompute our
1783 * idea of what the latest page is after inserting the placeholder
1784 * tuple. Anyone that grows the table later will update the
1785 * placeholder tuple, so it doesn't matter that we won't scan these
1786 * pages ourselves. Careful: the table might have been extended
1787 * beyond the current range, so clamp our result.
1788 *
1789 * Fortunately, this should occur infrequently.
1790 */
1793 }
1794 else
1795 {
1796 /* Easy case: range is known to be complete */
1798 }
1800 /*
1801 * Execute the partial heap scan covering the heap blocks in the specified
1802 * page range, summarizing the heap tuples in it. This scan stops just
1803 * short of brinbuildCallback creating the new index entry.
1804 *
1805 * Note that it is critical we use the "any visible" mode of
1806 * table_index_build_range_scan here: otherwise, we would miss tuples
1807 * inserted by transactions that are still in progress, among other corner
1808 * cases.
1809 */
1815 /*
1816 * Now we update the values obtained by the scan with the placeholder
1817 * tuple. We do this in a loop which only terminates if we're able to
1818 * update the placeholder tuple successfully; if we are not, this means
1819 * somebody else modified the placeholder tuple after we read it.
1820 */
1822 {
1824 Size newsize;
1830 /*
1831 * Update the summary tuple and try to update.
1832 */
1836 didupdate =
1843 /* If the update succeeded, we're done. */
1847 /*
1848 * If the update didn't work, it might be because somebody updated the
1849 * placeholder tuple concurrently. Extract the new version, union it
1850 * with the values we have from the scan, and start over. (There are
1851 * other reasons for the update to fail, but it's simple to treat them
1852 * the same.)
1853 */
1856 /* the placeholder tuple must exist */
1862 /* merge it into the tuple from the heap scan */
1864 }
1867 }
1869 /*
1870 * Summarize page ranges that are not already summarized. If pageRange is
1871 * BRIN_ALL_BLOCKRANGES then the whole table is scanned; otherwise, only the
1872 * page range containing the given heap page number is scanned.
1873 * If include_partial is true, then the partial range at the end of the table
1874 * is summarized, otherwise not.
1875 *
1876 * For each new index tuple inserted, *numSummarized (if not NULL) is
1877 * incremented; for each existing tuple, *numExisting (if not NULL) is
1878 * incremented.
1879 */
1880 static void
1883 {
1887 BlockNumber heapNumBlocks;
1888 BlockNumber pagesPerRange;
1889 Buffer buf;
1890 BlockNumber startBlk;
1894 /* determine range of pages to process */
1898 else
1899 {
1902 }
1904 {
1905 /* Nothing to do if start point is beyond end of table */
1908 }
1910 /*
1911 * Scan the revmap to find unsummarized items.
1912 */
1915 {
1917 OffsetNumber off;
1919 /*
1920 * Unless requested to summarize even a partial range, go away now if
1921 * we think the next range is partial. Caller would pass true when it
1922 * is typically run once bulk data loading is done
1923 * (brin_summarize_new_values), and false when it is typically the
1924 * result of arbitrarily-scheduled maintenance command (vacuuming).
1925 */
1933 BUFFER_LOCK_SHARE);
1935 {
1936 /* no revmap entry for this heap range. Summarize it. */
1938 {
1939 /* first time through */
1942 pagesPerRange,
1943 InvalidBlockNumber);
1945 }
1948 /* and re-initialize state for the next range */
1953 }
1954 else
1955 {
1959 }
1960 }
1965 /* free resources */
1968 {
1971 }
1972 }
1974 /*
1975 * Given a deformed tuple in the build state, convert it into the on-disk
1976 * format and insert it into the index, making the revmap point to it.
1977 */
1978 static void
1980 {
1982 Size size;
1992 }
1994 /*
1995 * Given a deformed tuple in the build state, convert it into the on-disk
1996 * format and write it to a (shared) tuplesort (the leader will insert it
1997 * into the index later).
1998 */
1999 static void
2001 {
2003 Size size;
2005 /* don't insert empty tuples in parallel build */
2012 /* write the BRIN tuple to the tuplesort */
2018 }
2020 /*
2021 * Given two deformed tuples, adjust the first one so that it's consistent
2022 * with the summary values in both.
2023 */
2024 static void
2026 {
2029 MemoryContext cxt;
2030 MemoryContext oldcxt;
2032 /* Use our own memory context to avoid retail pfree */
2035 ALLOCSET_DEFAULT_SIZES);
2040 /*
2041 * Check if the ranges are empty.
2042 *
2043 * If at least one of them is empty, we don't need to call per-key union
2044 * functions at all. If "b" is empty, we just use "a" as the result (it
2045 * might be empty fine, but that's fine). If "a" is empty but "b" is not,
2046 * we use "b" as the result (but we have to copy the data into "a" first).
2047 *
2048 * Only when both ranges are non-empty, we actually do the per-key merge.
2049 */
2051 /* If "b" is empty - ignore it and just use "a" (even if it's empty etc.). */
2053 {
2054 /* skip the per-key merge */
2057 }
2059 /*
2060 * Now we know "b" is not empty. If "a" is empty, then "b" is the result.
2061 * But we need to copy the data from "b" to "a" first, because that's how
2062 * we pass result out.
2063 *
2064 * We have to copy all the global/per-key flags etc. too.
2065 */
2067 {
2069 {
2078 /* If "b" has no data, we're done. */
2087 }
2089 /* "a" started empty, but "b" was not empty, so remember that */
2092 /* skip the per-key merge */
2095 }
2097 /* Now we know neither range is empty. */
2099 {
2106 {
2107 /* Does the "b" summary represent any NULL values? */
2110 /* Adjust "hasnulls". */
2114 /* If there are no values in B, there's nothing left to do. */
2118 /*
2119 * Adjust "allnulls". If A doesn't have values, just copy the
2120 * values from B into A, and we're done. We cannot run the
2121 * operators in this case, because values in A might contain
2122 * garbage. Note we already established that B contains values.
2123 *
2124 * Also adjust "hasnulls" in order not to forget the summary
2125 * represents NULL values. This is not redundant with the earlier
2126 * update, because that only happens when allnulls=false.
2127 */
2129 {
2142 }
2143 }
2146 BRIN_PROCNUM_UNION);
2152 }
2155 }
2157 /*
2158 * brin_vacuum_scan
2159 * Do a complete scan of the index during VACUUM.
2160 *
2161 * This routine scans the complete index looking for uncataloged index pages,
2162 * i.e. those that might have been lost due to a crash after index extension
2163 * and such.
2164 */
2165 static void
2167 {
2168 BlockNumber nblocks;
2169 BlockNumber blkno;
2171 /*
2172 * Scan the index in physical order, and clean up any possible mess in
2173 * each page.
2174 */
2177 {
2178 Buffer buf;
2188 }
2190 /*
2191 * Update all upper pages in the index's FSM, as well. This ensures not
2192 * only that we propagate leaf-page FSM updates made by brin_page_cleanup,
2193 * but also that any pre-existing damage or out-of-dateness is repaired.
2194 */
2196 }
2198 static bool
2201 {
2204 /* If the range starts empty, we're certainly going to modify it. */
2207 /*
2208 * Compare the key values of the new tuple to the stored index values; our
2209 * deformed tuple will get updated if the new tuple doesn't fit the
2210 * original range (note this means we can't break out of the loop early).
2211 * Make a note of whether this happens, so that we know to insert the
2212 * modified tuple later.
2213 */
2215 {
2216 Datum result;
2223 /*
2224 * Does the range have actual NULL values? Either of the flags can be
2225 * set, but we ignore the state before adding first row.
2226 *
2227 * We have to remember this, because we'll modify the flags and we
2228 * need to know if the range started as empty.
2229 */
2233 /*
2234 * If the value we're adding is NULL, handle it locally. Otherwise
2235 * call the BRIN_PROCNUM_ADDVALUE procedure.
2236 */
2238 {
2239 /*
2240 * If the new value is null, we record that we saw it if it's the
2241 * first one; otherwise, there's nothing to do.
2242 */
2244 {
2247 }
2250 }
2253 BRIN_PROCNUM_ADDVALUE);
2260 /* if that returned true, we need to insert the updated tuple */
2263 /*
2264 * If the range was had actual NULL values (i.e. did not start empty),
2265 * make sure we don't forget about the NULL values. Either the
2266 * allnulls flag is still set to true, or (if the opclass cleared it)
2267 * we need to set hasnulls=true.
2268 *
2269 * XXX This can only happen when the opclass modified the tuple, so
2270 * the modified flag should be set.
2271 */
2273 {
2276 }
2277 }
2279 /*
2280 * After updating summaries for all the keys, mark it as not empty.
2281 *
2282 * If we're actually changing the flag value (i.e. tuple started as
2283 * empty), we should have modified the tuple. So we should not see empty
2284 * range that was not modified.
2285 */
2290 }
2292 static bool
2294 {
2297 /*
2298 * First check if there are any IS [NOT] NULL scan keys, and if we're
2299 * violating them.
2300 */
2302 {
2307 /* Handle only IS NULL/IS NOT NULL tests */
2312 {
2313 /* IS NULL scan key, but range has no NULLs */
2316 }
2318 {
2319 /*
2320 * For IS NOT NULL, we can only skip ranges that are known to have
2321 * only nulls.
2322 */
2325 }
2326 else
2327 {
2328 /*
2329 * Neither IS NULL nor IS NOT NULL was used; assume all indexable
2330 * operators are strict and thus return false with NULL value in
2331 * the scan key.
2332 */
2334 }
2335 }
2338 }
2340 /*
2341 * Create parallel context, and launch workers for leader.
2342 *
2343 * buildstate argument should be initialized (with the exception of the
2344 * tuplesort states, which may later be created based on shared
2345 * state initially set up here).
2346 *
2347 * isconcurrent indicates if operation is CREATE INDEX CONCURRENTLY.
2348 *
2349 * request is the target number of parallel worker processes to launch.
2350 *
2351 * Sets buildstate's BrinLeader, which caller must use to shut down parallel
2352 * mode by passing it to _brin_end_parallel() at the very end of its index
2353 * build. If not even a single worker process can be launched, this is
2354 * never set, and caller should proceed with a serial index build.
2355 */
2356 static void
2359 {
2362 Snapshot snapshot;
2363 Size estbrinshared;
2364 Size estsort;
2373 #ifdef DISABLE_LEADER_PARTICIPATION
2375 #endif
2377 /*
2378 * Enter parallel mode, and create context for parallel build of brin
2379 * index
2380 */
2384 request);
2388 /*
2389 * Prepare for scan of the base relation. In a normal index build, we use
2390 * SnapshotAny because we must retrieve all tuples and do our own time
2391 * qual checks (because we have to index RECENTLY_DEAD tuples). In a
2392 * concurrent build, we take a regular MVCC snapshot and index whatever's
2393 * live according to that.
2394 */
2397 else
2400 /*
2401 * Estimate size for our own PARALLEL_KEY_BRIN_SHARED workspace.
2402 */
2410 /*
2411 * Estimate space for WalUsage and BufferUsage -- PARALLEL_KEY_WAL_USAGE
2412 * and PARALLEL_KEY_BUFFER_USAGE.
2413 *
2414 * If there are no extensions loaded that care, we could skip this. We
2415 * have no way of knowing whether anyone's looking at pgWalUsage or
2416 * pgBufferUsage, so do it unconditionally.
2417 */
2425 /* Finally, estimate PARALLEL_KEY_QUERY_TEXT space */
2427 {
2431 }
2432 else
2435 /* Everyone's had a chance to ask for space, so now create the DSM */
2438 /* If no DSM segment was available, back out (do serial build) */
2440 {
2446 }
2448 /* Store shared build state, for which we reserved space */
2450 /* Initialize immutable state */
2460 /* Initialize mutable state */
2467 snapshot);
2469 /*
2470 * Store shared tuplesort-private state, for which we reserved space.
2471 * Then, initialize opaque state using tuplesort routine.
2472 */
2477 /*
2478 * Store shared tuplesort-private state, for which we reserved space.
2479 * Then, initialize opaque state using tuplesort routine.
2480 */
2484 /* Store query string for workers */
2486 {
2492 }
2494 /*
2495 * Allocate space for each worker's WalUsage and BufferUsage; no need to
2496 * initialize.
2497 */
2505 /* Launch workers, saving status for leader/caller */
2517 /* If no workers were successfully launched, back out (do serial build) */
2519 {
2522 }
2524 /* Save leader state now that it's clear build will be parallel */
2527 /* Join heap scan ourselves */
2531 /*
2532 * Caller needs to wait for all launched workers when we return. Make
2533 * sure that the failure-to-start case will not hang forever.
2534 */
2536 }
2538 /*
2539 * Shut down workers, destroy parallel context, and end parallel mode.
2540 */
2541 static void
2543 {
2546 /* Shutdown worker processes */
2549 /*
2550 * Next, accumulate WAL usage. (This must wait for the workers to finish,
2551 * or we might get incomplete data.)
2552 */
2556 /* Free last reference to MVCC snapshot, if one was used */
2561 }
2563 /*
2564 * Within leader, wait for end of heap scan.
2565 *
2566 * When called, parallel heap scan started by _brin_begin_parallel() will
2567 * already be underway within worker processes (when leader participates
2568 * as a worker, we should end up here just as workers are finishing).
2569 *
2570 * Returns the total number of heap tuples scanned.
2571 */
2572 static double
2574 {
2580 {
2583 {
2584 /* copy the data into leader state */
2590 }
2594 WAIT_EVENT_PARALLEL_CREATE_INDEX_SCAN);
2595 }
2600 }
2602 /*
2603 * Within leader, wait for end of heap scan and merge per-worker results.
2604 *
2605 * After waiting for all workers to finish, merge the per-worker results into
2606 * the complete index. The results from each worker are sorted by block number
2607 * (start of the page range). While combining the per-worker results we merge
2608 * summaries for the same page range, and also fill-in empty summaries for
2609 * ranges without any tuples.
2610 *
2611 * Returns the total number of heap tuples scanned.
2612 */
2613 static double
2615 {
2618 Size tuplen;
2620 MemoryContext rangeCxt,
2621 oldCxt;
2624 /* wait for workers to scan table and produce partial results */
2627 /* do the actual sort in the leader */
2630 /*
2631 * Initialize BrinMemTuple we'll use to union summaries from workers (in
2632 * case they happened to produce parts of the same page range).
2633 */
2636 /*
2637 * Create a memory context we'll reset to combine results for a single
2638 * page range (received from the workers). We don't expect huge number of
2639 * overlaps under regular circumstances, because for large tables the
2640 * chunk size is likely larger than the BRIN page range), but it can
2641 * happen, and the union functions may do all kinds of stuff. So we better
2642 * reset the context once in a while.
2643 */
2646 ALLOCSET_DEFAULT_SIZES);
2649 /*
2650 * Read the BRIN tuples from the shared tuplesort, sorted by block number.
2651 * That probably gives us an index that is cheaper to scan, thanks to
2652 * mostly getting data from the same index page as before.
2653 */
2655 {
2656 /* Ranges should be multiples of pages_per_range for the index. */
2659 /*
2660 * Do we need to union summaries for the same page range?
2661 *
2662 * If this is the first brin tuple we read, then just deform it into
2663 * the memtuple, and continue with the next one from tuplesort. We
2664 * however may need to insert empty summaries into the index.
2665 *
2666 * If it's the same block as the last we saw, we simply union the brin
2667 * tuple into it, and we're done - we don't even need to insert empty
2668 * ranges, because that was done earlier when we saw the first brin
2669 * tuple (for this range).
2670 *
2671 * Finally, if it's not the first brin tuple, and it's not the same
2672 * page range, we need to do the insert and then deform the tuple into
2673 * the memtuple. Then we'll insert empty ranges before the new brin
2674 * tuple, if needed.
2675 */
2677 {
2678 /* First brin tuples, just deform into memtuple. */
2681 /* continue to insert empty pages before thisblock */
2682 }
2684 {
2685 /*
2686 * Not the first brin tuple, but same page range as the previous
2687 * one, so we can merge it into the memtuple.
2688 */
2691 }
2692 else
2693 {
2695 Size len;
2697 /*
2698 * We got brin tuple for a different page range, so form a brin
2699 * tuple from the memtuple, insert it, and re-init the memtuple
2700 * from the new brin tuple.
2701 */
2708 /*
2709 * Reset the per-output-range context. This frees all the memory
2710 * possibly allocated by the union functions, and also the BRIN
2711 * tuple we just formed and inserted.
2712 */
2717 /* continue to insert empty pages before thisblock */
2718 }
2720 /* Fill empty ranges for all ranges missing in the tuplesort. */
2724 }
2728 /* Fill the BRIN tuple for the last page range with data. */
2730 {
2732 Size len;
2741 }
2743 /* Fill empty ranges at the end, for all ranges missing in the tuplesort. */
2746 /*
2747 * Switch back to the original memory context, and destroy the one we
2748 * created to isolate the union_tuple calls.
2749 */
2754 }
2756 /*
2757 * Returns size of shared memory required to store state for a parallel
2758 * brin index build based on the snapshot its parallel scan will use.
2759 */
2760 static Size
2762 {
2763 /* c.f. shm_toc_allocate as to why BUFFERALIGN is used */
2766 }
2768 /*
2769 * Within leader, participate as a parallel worker.
2770 */
2771 static void
2773 {
2777 /*
2778 * Might as well use reliable figure when doling out maintenance_work_mem
2779 * (when requested number of workers were not launched, this will be
2780 * somewhat higher than it is for other workers).
2781 */
2784 /* Perform work common to all participants */
2787 }
2789 /*
2790 * Perform a worker's portion of a parallel sort.
2791 *
2792 * This generates a tuplesort for the worker portion of the table.
2793 *
2794 * sortmem is the amount of working memory to use within each worker,
2795 * expressed in KBs.
2796 *
2797 * When this returns, workers are done, and need only release resources.
2798 */
2799 static void
2804 {
2805 SortCoordinate coordinate;
2806 TableScanDesc scan;
2810 /* Initialize local tuplesort coordination state */
2816 /* Begin "partial" tuplesort */
2818 TUPLESORT_NONE);
2820 /* Join parallel scan */
2830 /* insert the last item */
2833 /* sort the BRIN ranges built by this worker */
2838 /*
2839 * Done. Record ambuild statistics.
2840 */
2847 /* Notify leader */
2851 }
2853 /*
2854 * Perform work within a launched parallel process.
2855 */
2856 void
2858 {
2863 Relation heapRel;
2864 Relation indexRel;
2865 LOCKMODE heapLockmode;
2866 LOCKMODE indexLockmode;
2871 /*
2872 * The only possible status flag that can be set to the parallel worker is
2873 * PROC_IN_SAFE_IC.
2874 */
2878 /* Set debug_query_string for individual workers first */
2882 /* Report the query string from leader */
2885 /* Look up brin shared state */
2888 /* Open relations using lock modes known to be obtained by index.c */
2890 {
2893 }
2894 else
2895 {
2898 }
2900 /* Track query ID */
2903 /* Open relations within worker */
2909 InvalidBlockNumber);
2911 /* Look up shared state private to tuplesort.c */
2915 /* Prepare to track buffer usage during parallel execution */
2918 /*
2919 * Might as well use reliable figure when doling out maintenance_work_mem
2920 * (when requested number of workers were not launched, this will be
2921 * somewhat higher than it is for other workers).
2922 */
2928 /* Report WAL/buffer usage during parallel execution */
2936 }
2938 /*
2939 * brin_build_empty_tuple
2940 * Maybe initialize a BRIN tuple representing empty range.
2941 *
2942 * Returns a BRIN tuple representing an empty page range starting at the
2943 * specified block number. The empty tuple is initialized only once, when it's
2944 * needed for the first time, stored in the memory context bs_context to ensure
2945 * proper life span, and reused on following calls. All empty tuples are
2946 * exactly the same except for the bt_blkno field, which is set to the value
2947 * in blkno parameter.
2948 */
2949 static void
2951 {
2952 /* First time an empty tuple is requested? If yes, initialize it. */
2954 {
2955 MemoryContext oldcxt;
2958 /* Allocate the tuple in context for the whole index build. */
2965 }
2966 else
2967 {
2968 /* If we already have an empty tuple, just update the block. */
2970 }
2971 }
2973 /*
2974 * brin_fill_empty_ranges
2975 * Add BRIN index tuples representing empty page ranges.
2976 *
2977 * prevRange/nextRange determine for which page ranges to add empty summaries.
2978 * Both boundaries are exclusive, i.e. only ranges starting at blkno for which
2979 * (prevRange < blkno < nextRange) will be added to the index.
2980 *
2981 * If prevRange is InvalidBlockNumber, this means there was no previous page
2982 * range (i.e. the first empty range to add is for blkno=0).
2983 *
2984 * The empty tuple is built only once, and then reused for all future calls.
2985 */
2986 static void
2989 {
2990 BlockNumber blkno;
2992 /*
2993 * If we already summarized some ranges, we need to start with the next
2994 * one. Otherwise start from the first range of the table.
2995 */
2998 /* Generate empty ranges until we hit the next non-empty range. */
3000 {
3001 /* Did we already build the empty tuple? If not, do it now. */
3008 /* try next page range */
3010 }
3011 }