Loading...
Searching...
No Matches
nbtsort.c File Reference
#include "postgres.h"#include "access/nbtree.h"#include "access/parallel.h"#include "access/relscan.h"#include "access/table.h"#include "access/tableam.h"#include "access/xact.h"#include "catalog/index.h"#include "commands/progress.h"#include "executor/instrument.h"#include "miscadmin.h"#include "pgstat.h"#include "storage/bulk_write.h"#include "storage/condition_variable.h"#include "storage/proc.h"#include "tcop/tcopprot.h"#include "utils/rel.h"#include "utils/sortsupport.h"#include "utils/tuplesort.h"#include "utils/wait_event.h"
Include dependency graph for nbtsort.c:
Go to the source code of this file.
Data Structures | |
| struct | BTSpool |
| struct | BTShared |
| struct | BTLeader |
| struct | BTBuildState |
| struct | BTPageState |
| struct | BTWriteState |
Macros | |
| #define | PARALLEL_KEY_BTREE_SHARED UINT64CONST(0xA000000000000001) |
| #define | PARALLEL_KEY_TUPLESORT UINT64CONST(0xA000000000000002) |
| #define | PARALLEL_KEY_TUPLESORT_SPOOL2 UINT64CONST(0xA000000000000003) |
| #define | PARALLEL_KEY_QUERY_TEXT UINT64CONST(0xA000000000000004) |
| #define | PARALLEL_KEY_WAL_USAGE UINT64CONST(0xA000000000000005) |
| #define | PARALLEL_KEY_BUFFER_USAGE UINT64CONST(0xA000000000000006) |
| #define | ParallelTableScanFromBTShared(shared) (ParallelTableScanDesc) ((char *) (shared) + BUFFERALIGN(sizeof(BTShared))) |
Typedefs | |
| typedef struct BTSpool | BTSpool |
| typedef struct BTShared | BTShared |
| typedef struct BTLeader | BTLeader |
| typedef struct BTBuildState | BTBuildState |
| typedef struct BTPageState | BTPageState |
| typedef struct BTWriteState | BTWriteState |
Macro Definition Documentation
◆ PARALLEL_KEY_BTREE_SHARED
| #define PARALLEL_KEY_BTREE_SHARED UINT64CONST(0xA000000000000001) |
◆ PARALLEL_KEY_BUFFER_USAGE
| #define PARALLEL_KEY_BUFFER_USAGE UINT64CONST(0xA000000000000006) |
◆ PARALLEL_KEY_QUERY_TEXT
| #define PARALLEL_KEY_QUERY_TEXT UINT64CONST(0xA000000000000004) |
◆ PARALLEL_KEY_TUPLESORT
| #define PARALLEL_KEY_TUPLESORT UINT64CONST(0xA000000000000002) |
◆ PARALLEL_KEY_TUPLESORT_SPOOL2
| #define PARALLEL_KEY_TUPLESORT_SPOOL2 UINT64CONST(0xA000000000000003) |
◆ PARALLEL_KEY_WAL_USAGE
| #define PARALLEL_KEY_WAL_USAGE UINT64CONST(0xA000000000000005) |
◆ ParallelTableScanFromBTShared
| #define ParallelTableScanFromBTShared | ( | shared | ) | (ParallelTableScanDesc) ((char *) (shared) + BUFFERALIGN(sizeof(BTShared))) |
Definition at line 165 of file nbtsort.c.
171{
172 /* parallel context itself */
173 ParallelContext *pcxt;
174
175 /*
176 * nparticipanttuplesorts is the exact number of worker processes
177 * successfully launched, plus one leader process if it participates as a
178 * worker (only DISABLE_LEADER_PARTICIPATION builds avoid leader
179 * participating as a worker).
180 */
181 int nparticipanttuplesorts;
182
183 /*
184 * Leader process convenience pointers to shared state (leader avoids TOC
185 * lookups).
186 *
187 * btshared is the shared state for entire build. sharedsort is the
188 * shared, tuplesort-managed state passed to each process tuplesort.
189 * sharedsort2 is the corresponding btspool2 shared state, used only when
190 * building unique indexes. snapshot is the snapshot used by the scan iff
191 * an MVCC snapshot is required.
192 */
193 BTShared *btshared;
194 Sharedsort *sharedsort;
195 Sharedsort *sharedsort2;
196 Snapshot snapshot;
197 WalUsage *walusage;
198 BufferUsage *bufferusage;
199} BTLeader;
200
201/*
202 * Working state for btbuild and its callback.
203 *
204 * When parallel CREATE INDEX is used, there is a BTBuildState for each
205 * participant.
206 */
208{
214
215 /*
216 * spool2 is needed only when the index is a unique index. Dead tuples are
217 * put into spool2 instead of spool in order to avoid uniqueness check.
218 */
221
222 /*
223 * btleader is only present when a parallel index build is performed, and
224 * only in the leader process. (Actually, only the leader has a
225 * BTBuildState. Workers have their own spool and spool2, though.)
226 */
228} BTBuildState;
229
230/*
231 * Status record for a btree page being built. We have one of these
232 * for each active tree level.
233 */
235{
244} BTPageState;
245
246/*
247 * Overall status record for index writing phase.
248 */
250{
256} BTWriteState;
257
258
286 bool *brokenhotchain);
292
293
294/*
295 * btbuild() -- build a new btree index.
296 */
297IndexBuildResult *
299{
300 IndexBuildResult *result;
302 double reltuples;
303
304#ifdef BTREE_BUILD_STATS
306 ResetUsage();
307#endif /* BTREE_BUILD_STATS */
308
312 buildstate.heap = heap;
315 buildstate.indtuples = 0;
317
318 /*
319 * We expect to be called exactly once for any index relation. If that's
320 * not the case, big trouble's what we have.
321 */
325
327
328 /*
329 * Finish the build by (1) completing the sort of the spool file, (2)
330 * inserting the sorted tuples into btree pages and (3) building the upper
331 * levels. Finally, it may also be necessary to end use of parallelism.
332 */
339
341
342 result->heap_tuples = reltuples;
344
345#ifdef BTREE_BUILD_STATS
347 {
349 ResetUsage();
350 }
351#endif /* BTREE_BUILD_STATS */
352
353 return result;
354}
355
356/*
357 * Create and initialize one or two spool structures, and save them in caller's
358 * buildstate argument. May also fill-in fields within indexInfo used by index
359 * builds.
360 *
361 * Scans the heap, possibly in parallel, filling spools with IndexTuples. This
362 * routine encapsulates all aspects of managing parallelism. Caller need only
363 * call _bt_end_parallel() in parallel case after it is done with spool/spool2.
364 *
365 * Returns the total number of heap tuples scanned.
366 */
367static double
369 IndexInfo *indexInfo)
370{
373 double reltuples = 0;
374
375 /*
376 * We size the sort area as maintenance_work_mem rather than work_mem to
377 * speed index creation. This should be OK since a single backend can't
378 * run multiple index creations in parallel (see also: notes on
379 * parallelism and maintenance_work_mem below).
380 */
381 btspool->heap = heap;
385
386 /* Save as primary spool */
388
389 /* Report table scan phase started */
392
393 /* Attempt to launch parallel worker scan when required */
396 indexInfo->ii_ParallelWorkers);
397
398 /*
399 * If parallel build requested and at least one worker process was
400 * successfully launched, set up coordination state
401 */
403 {
406 coordinate->nParticipants =
407 buildstate->btleader->nparticipanttuplesorts;
409 }
410
411 /*
412 * Begin serial/leader tuplesort.
413 *
414 * In cases where parallelism is involved, the leader receives the same
415 * share of maintenance_work_mem as a serial sort (it is generally treated
416 * in the same way as a serial sort once we return). Parallel worker
417 * Tuplesortstates will have received only a fraction of
418 * maintenance_work_mem, though.
419 *
420 * We rely on the lifetime of the Leader Tuplesortstate almost not
421 * overlapping with any worker Tuplesortstate's lifetime. There may be
422 * some small overlap, but that's okay because we rely on leader
423 * Tuplesortstate only allocating a small, fixed amount of memory here.
424 * When its tuplesort_performsort() is called (by our caller), and
425 * significant amounts of memory are likely to be used, all workers must
426 * have already freed almost all memory held by their Tuplesortstates
427 * (they are about to go away completely, too). The overall effect is
428 * that maintenance_work_mem always represents an absolute high watermark
429 * on the amount of memory used by a CREATE INDEX operation, regardless of
430 * the use of parallelism or any other factor.
431 */
432 buildstate->spool->sortstate =
434 buildstate->nulls_not_distinct,
436 TUPLESORT_NONE);
437
438 /*
439 * If building a unique index, put dead tuples in a second spool to keep
440 * them out of the uniqueness check. We expect that the second spool (for
441 * dead tuples) won't get very full, so we give it only work_mem.
442 */
444 {
447
448 /* Initialize secondary spool */
449 btspool2->heap = heap;
452 /* Save as secondary spool */
454
456 {
457 /*
458 * Set up non-private state that is passed to
459 * tuplesort_begin_index_btree() about the basic high level
460 * coordination of a parallel sort.
461 */
464 coordinate2->nParticipants =
465 buildstate->btleader->nparticipanttuplesorts;
467 }
468
469 /*
470 * We expect that the second one (for dead tuples) won't get very
471 * full, so we give it only work_mem
472 */
473 buildstate->spool2->sortstate =
476 }
477
478 /* Fill spool using either serial or parallel heap scan */
482 NULL);
483 else
485 &indexInfo->ii_BrokenHotChain);
486
487 /*
488 * Set the progress target for the next phase. Reset the block number
489 * values set by table_index_build_scan
490 */
491 {
496 };
498 buildstate->indtuples,
499 0, 0
500 };
501
503 }
504
505 /* okay, all heap tuples are spooled */
507 {
508 /* spool2 turns out to be unnecessary */
511 }
512
513 return reltuples;
514}
515
516/*
517 * clean up a spool structure and its substructures.
518 */
519static void
521{
524}
525
526/*
527 * spool an index entry into the sort file.
528 */
529static void
530_bt_spool(BTSpool *btspool, const ItemPointerData *self, const Datum *values, const bool *isnull)
531{
534}
535
536/*
537 * given a spool loaded by successive calls to _bt_spool,
538 * create an entire btree.
539 */
540static void
542{
544
545#ifdef BTREE_BUILD_STATS
547 {
549 ResetUsage();
550 }
551#endif /* BTREE_BUILD_STATS */
552
553 /* Execute the sort */
558 {
562 }
563
567 /* _bt_mkscankey() won't set allequalimage without metapage */
569
570 /* reserve the metapage */
572
576}
577
578/*
579 * Per-tuple callback for table_index_build_scan
580 */
581static void
583 ItemPointer tid,
585 bool *isnull,
588{
590
591 /*
592 * insert the index tuple into the appropriate spool file for subsequent
593 * processing
594 */
597 else
598 {
599 /* dead tuples are put into spool2 */
602 }
603
604 buildstate->indtuples += 1;
605}
606
607/*
608 * allocate workspace for a new, clean btree page, not linked to any siblings.
609 */
612{
614 Page page;
615 BTPageOpaque opaque;
616
619
620 /* Zero the page and set up standard page header info */
622
623 /* Initialize BT opaque state */
624 opaque = BTPageGetOpaque(page);
626 opaque->btpo_level = level;
628 opaque->btpo_cycleid = 0;
629
630 /* Make the P_HIKEY line pointer appear allocated */
632
634}
635
636/*
637 * emit a completed btree page, and release the working storage.
638 */
639static void
641{
643 /* smgr_bulk_write took ownership of 'buf' */
644}
645
646/*
647 * allocate and initialize a new BTPageState. the returned structure
648 * is suitable for immediate use by _bt_buildadd.
649 */
652{
654
655 /* create initial page for level */
657
658 /* and assign it a page position */
660
662 /* initialize lastoff so first item goes into P_FIRSTKEY */
664 state->btps_lastextra = 0;
665 state->btps_level = level;
666 /* set "full" threshold based on level. See notes at head of file. */
667 if (level > 0)
669 else
671
672 /* no parent level, yet */
674
676}
677
678/*
679 * Slide the array of ItemIds from the page back one slot (from P_FIRSTKEY to
680 * P_HIKEY, overwriting P_HIKEY).
681 *
682 * _bt_blnewpage() makes the P_HIKEY line pointer appear allocated, but the
683 * rightmost page on its level is not supposed to get a high key. Now that
684 * it's clear that this page is a rightmost page, remove the unneeded empty
685 * P_HIKEY line pointer space.
686 */
687static void
689{
690 OffsetNumber off;
691 OffsetNumber maxoff;
693
698 {
700
703 }
705}
706
707/*
708 * Add an item to a page being built.
709 *
710 * This is very similar to nbtinsert.c's _bt_pgaddtup(), but this variant
711 * raises an error directly.
712 *
713 * Note that our nbtsort.c caller does not know yet if the page will be
714 * rightmost. Offset P_FIRSTKEY is always assumed to be the first data key by
715 * caller. Page that turns out to be the rightmost on its level is fixed by
716 * calling _bt_slideleft().
717 */
718static void
724{
726
728 {
729 trunctuple = *itup;
732 itup = &trunctuple;
734 }
735
738}
739
740/*----------
741 * Add an item to a disk page from the sort output (or add a posting list
742 * item formed from the sort output).
743 *
744 * We must be careful to observe the page layout conventions of nbtsearch.c:
745 * - rightmost pages start data items at P_HIKEY instead of at P_FIRSTKEY.
746 * - on non-leaf pages, the key portion of the first item need not be
747 * stored, we should store only the link.
748 *
749 * A leaf page being built looks like:
750 *
751 * +----------------+---------------------------------+
752 * | PageHeaderData | linp0 linp1 linp2 ... |
753 * +-----------+----+---------------------------------+
754 * | ... linpN | |
755 * +-----------+--------------------------------------+
756 * | ^ last |
757 * | |
758 * +-------------+------------------------------------+
759 * | | itemN ... |
760 * +-------------+------------------+-----------------+
761 * | ... item3 item2 item1 | "special space" |
762 * +--------------------------------+-----------------+
763 *
764 * Contrast this with the diagram in bufpage.h; note the mismatch
765 * between linps and items. This is because we reserve linp0 as a
766 * placeholder for the pointer to the "high key" item; when we have
767 * filled up the page, we will set linp0 to point to itemN and clear
768 * linpN. On the other hand, if we find this is the last (rightmost)
769 * page, we leave the items alone and slide the linp array over. If
770 * the high key is to be truncated, offset 1 is deleted, and we insert
771 * the truncated high key at offset 1.
772 *
773 * 'last' pointer indicates the last offset added to the page.
774 *
775 * 'truncextra' is the size of the posting list in itup, if any. This
776 * information is stashed for the next call here, when we may benefit
777 * from considering the impact of truncating away the posting list on
778 * the page before deciding to finish the page off. Posting lists are
779 * often relatively large, so it is worth going to the trouble of
780 * accounting for the saving from truncating away the posting list of
781 * the tuple that becomes the high key (that may be the only way to
782 * get close to target free space on the page). Note that this is
783 * only used for the soft fillfactor-wise limit, not the critical hard
784 * limit.
785 *----------
786 */
787static void
790{
792 Page npage;
799
800 /*
801 * This is a handy place to check for cancel interrupts during the btree
802 * load phase of index creation.
803 */
804 CHECK_FOR_INTERRUPTS();
805
812
816 /* Leaf case has slightly different rules due to suffix truncation */
818
819 /*
820 * Check whether the new item can fit on a btree page on current level at
821 * all.
822 *
823 * Every newly built index will treat heap TID as part of the keyspace,
824 * which imposes the requirement that new high keys must occasionally have
825 * a heap TID appended within _bt_truncate(). That may leave a new pivot
826 * tuple one or two MAXALIGN() quantums larger than the original
827 * firstright tuple it's derived from. v4 deals with the problem by
828 * decreasing the limit on the size of tuples inserted on the leaf level
829 * by the same small amount. Enforce the new v4+ limit on the leaf level,
830 * and the old limit on internal levels, since pivot tuples may need to
831 * make use of the reserved space. This should never fail on internal
832 * pages.
833 */
836 itup);
837
838 /*
839 * Check to see if current page will fit new item, with space left over to
840 * append a heap TID during suffix truncation when page is a leaf page.
841 *
842 * It is guaranteed that we can fit at least 2 non-pivot tuples plus a
843 * high key with heap TID when finishing off a leaf page, since we rely on
844 * _bt_check_third_page() rejecting oversized non-pivot tuples. On
845 * internal pages we can always fit 3 pivot tuples with larger internal
846 * page tuple limit (includes page high key).
847 *
848 * Most of the time, a page is only "full" in the sense that the soft
849 * fillfactor-wise limit has been exceeded. However, we must always leave
850 * at least two items plus a high key on each page before starting a new
851 * page. Disregard fillfactor and insert on "full" current page if we
852 * don't have the minimum number of items yet. (Note that we deliberately
853 * assume that suffix truncation neither enlarges nor shrinks new high key
854 * when applying soft limit, except when last tuple has a posting list.)
855 */
859 {
860 /*
861 * Finish off the page and write it out.
862 */
866 ItemId ii;
869
870 /* Create new page of same level */
873
874 /* and assign it a page position */
876
877 /*
878 * We copy the last item on the page into the new page, and then
879 * rearrange the old page so that the 'last item' becomes its high key
880 * rather than a true data item. There had better be at least two
881 * items on the page already, else the page would be empty of useful
882 * data.
883 */
888 !isleaf);
889
890 /*
891 * Move 'last' into the high key position on opage. _bt_blnewpage()
892 * allocated empty space for a line pointer when opage was first
893 * created, so this is a matter of rearranging already-allocated space
894 * on page, and initializing high key line pointer. (Actually, leaf
895 * pages must also swap oitup with a truncated version of oitup, which
896 * is sometimes larger than oitup, though never by more than the space
897 * needed to append a heap TID.)
898 */
900 *hii = *ii;
903
905 {
906 IndexTuple lastleft;
907 IndexTuple truncated;
908
909 /*
910 * Truncate away any unneeded attributes from high key on leaf
911 * level. This is only done at the leaf level because downlinks
912 * in internal pages are either negative infinity items, or get
913 * their contents from copying from one level down. See also:
914 * _bt_split().
915 *
916 * We don't try to bias our choice of split point to make it more
917 * likely that _bt_truncate() can truncate away more attributes,
918 * whereas the split point used within _bt_split() is chosen much
919 * more delicately. Even still, the lastleft and firstright
920 * tuples passed to _bt_truncate() here are at least not fully
921 * equal to each other when deduplication is used, unless there is
922 * a large group of duplicates (also, unique index builds usually
923 * have few or no spool2 duplicates). When the split point is
924 * between two unequal tuples, _bt_truncate() will avoid including
925 * a heap TID in the new high key, which is the most important
926 * benefit of suffix truncation.
927 *
928 * Overwrite the old item with new truncated high key directly.
929 * oitup is already located at the physical beginning of tuple
930 * space, so this should directly reuse the existing tuple space.
931 */
934
937 wstate->inskey);
940 pfree(truncated);
941
942 /* oitup should continue to point to the page's high key */
945 }
946
947 /*
948 * Link the old page into its parent, using its low key. If we don't
949 * have a parent, we have to create one; this adds a new btree level.
950 */
953
963
964 /*
965 * Save a copy of the high key from the old page. It is also the low
966 * key for the new page.
967 */
969
970 /*
971 * Set the sibling links for both pages.
972 */
973 {
976
980 }
981
982 /*
983 * Write out the old page. _bt_blwritepage takes ownership of the
984 * 'opage' buffer.
985 */
987
988 /*
989 * Reset last_off to point to new page
990 */
992 }
993
994 /*
995 * By here, either original page is still the current page, or a new page
996 * was created that became the current page. Either way, the current page
997 * definitely has space for new item.
998 *
999 * If the new item is the first for its page, it must also be the first
1000 * item on its entire level. On later same-level pages, a low key for a
1001 * page will be copied from the prior page in the code above. Generate a
1002 * minus infinity low key here instead.
1003 */
1005 {
1010 }
1011
1012 /*
1013 * Add the new item into the current page.
1014 */
1018
1022}
1023
1024/*
1025 * Finalize pending posting list tuple, and add it to the index. Final tuple
1026 * is based on saved base tuple, and saved list of heap TIDs.
1027 *
1028 * This is almost like _bt_dedup_finish_pending(), but it adds a new tuple
1029 * using _bt_buildadd().
1030 */
1031static void
1034{
1036
1039 else
1040 {
1043
1044 /* form a tuple with a posting list */
1046 dstate->htids,
1047 dstate->nhtids);
1048 /* Calculate posting list overhead */
1051
1054 }
1055
1056 dstate->nmaxitems = 0;
1057 dstate->nhtids = 0;
1058 dstate->nitems = 0;
1059 dstate->phystupsize = 0;
1060}
1061
1062/*
1063 * Finish writing out the completed btree.
1064 */
1065static void
1067{
1068 BTPageState *s;
1070 uint32 rootlevel = 0;
1072
1073 /*
1074 * Each iteration of this loop completes one more level of the tree.
1075 */
1077 {
1078 BlockNumber blkno;
1079 BTPageOpaque opaque;
1080
1081 blkno = s->btps_blkno;
1083
1084 /*
1085 * We have to link the last page on this level to somewhere.
1086 *
1087 * If we're at the top, it's the root, so attach it to the metapage.
1088 * Otherwise, add an entry for it to its parent using its low key.
1089 * This may cause the last page of the parent level to split, but
1090 * that's not a problem -- we haven't gotten to it yet.
1091 */
1093 {
1095 rootblkno = blkno;
1096 rootlevel = s->btps_level;
1097 }
1098 else
1099 {
1103 P_LEFTMOST(opaque));
1105 !P_LEFTMOST(opaque));
1110 }
1111
1112 /*
1113 * This is the rightmost page, so the ItemId array needs to be slid
1114 * back one slot. Then we can dump out the page.
1115 */
1119 }
1120
1121 /*
1122 * As the last step in the process, construct the metapage and make it
1123 * point to the new root (unless we had no data at all, in which case it's
1124 * set to point to "P_NONE"). This changes the index to the "valid" state
1125 * by filling in a valid magic number in the metapage.
1126 */
1129 wstate->inskey->allequalimage);
1131}
1132
1133/*
1134 * Read tuples in correct sort order from tuplesort, and load them into
1135 * btree leaves.
1136 */
1137static void
1139{
1142 IndexTuple itup,
1148 SortSupport sortKeys;
1150 bool deduplicate;
1151
1153
1156
1158 {
1159 /*
1160 * Another BTSpool for dead tuples exists. Now we have to merge
1161 * btspool and btspool2.
1162 */
1163
1164 /* the preparation of merge */
1167
1168 /* Prepare SortSupport data for each column */
1170
1172 {
1175 bool reverse;
1176
1179 sortKey->ssup_nulls_first =
1182 /* Abbreviation is not supported here */
1184
1186
1188
1190 }
1191
1192 for (;;)
1193 {
1196 {
1198 break;
1199 }
1201 {
1203
1205 {
1206 SortSupport entry;
1208 attrDatum2;
1210 isNull2;
1211
1212 entry = sortKeys + i - 1;
1215
1218 entry);
1220 {
1222 break;
1223 }
1225 break;
1226 }
1227
1228 /*
1229 * If key values are equal, we sort on ItemPointer. This is
1230 * required for btree indexes, since heap TID is treated as an
1231 * implicit last key attribute in order to ensure that all
1232 * keys in the index are physically unique.
1233 */
1235 {
1240 }
1241 }
1242 else
1244
1245 /* When we see first tuple, create first index page */
1248
1250 {
1253 }
1254 else
1255 {
1258 }
1259
1260 /* Report progress */
1262 ++tuples_done);
1263 }
1264 pfree(sortKeys);
1265 }
1266 else if (deduplicate)
1267 {
1268 /* merge is unnecessary, deduplicate into posting lists */
1270
1275 /* Metadata about base tuple of current pending posting list */
1278 dstate->basetupsize = 0;
1279 /* Metadata about current pending posting list TIDs */
1281 dstate->nhtids = 0;
1282 dstate->nitems = 0;
1285
1288 {
1289 /* When we see first tuple, create first index page */
1291 {
1293
1294 /*
1295 * Limit size of posting list tuples to 1/10 space we want to
1296 * leave behind on the page, plus space for final item's line
1297 * pointer. This is equal to the space that we'd like to
1298 * leave behind on each leaf page when fillfactor is 90,
1299 * allowing us to get close to fillfactor% space utilization
1300 * when there happen to be a great many duplicates. (This
1301 * makes higher leaf fillfactor settings ineffective when
1302 * building indexes that have many duplicates, but packing
1303 * leaf pages full with few very large tuples doesn't seem
1304 * like a useful goal.)
1305 */
1311
1312 /* start new pending posting list with itup copy */
1314 InvalidOffsetNumber);
1315 }
1317 itup) > keysz &&
1319 {
1320 /*
1321 * Tuple is equal to base tuple of pending posting list. Heap
1322 * TID from itup has been saved in state.
1323 */
1324 }
1325 else
1326 {
1327 /*
1328 * Tuple is not equal to pending posting list tuple, or
1329 * _bt_dedup_save_htid() opted to not merge current item into
1330 * pending posting list.
1331 */
1334
1335 /* start new pending posting list with itup copy */
1337 InvalidOffsetNumber);
1338 }
1339
1340 /* Report progress */
1342 ++tuples_done);
1343 }
1344
1346 {
1347 /*
1348 * Handle the last item (there must be a last item when the
1349 * tuplesort returned one or more tuples)
1350 */
1354 }
1355
1357 }
1358 else
1359 {
1360 /* merging and deduplication are both unnecessary */
1363 {
1364 /* When we see first tuple, create first index page */
1367
1369
1370 /* Report progress */
1372 ++tuples_done);
1373 }
1374 }
1375
1376 /* Close down final pages and write the metapage */
1379}
1380
1381/*
1382 * Create parallel context, and launch workers for leader.
1383 *
1384 * buildstate argument should be initialized (with the exception of the
1385 * tuplesort state in spools, which may later be created based on shared
1386 * state initially set up here).
1387 *
1388 * isconcurrent indicates if operation is CREATE INDEX CONCURRENTLY.
1389 *
1390 * request is the target number of parallel worker processes to launch.
1391 *
1392 * Sets buildstate's BTLeader, which caller must use to shut down parallel
1393 * mode by passing it to _bt_end_parallel() at the very end of its index
1394 * build. If not even a single worker process can be launched, this is
1395 * never set, and caller should proceed with a serial index build.
1396 */
1397static void
1399{
1400 ParallelContext *pcxt;
1401 int scantuplesortstates;
1402 Snapshot snapshot;
1405 BTShared *btshared;
1406 Sharedsort *sharedsort;
1407 Sharedsort *sharedsort2;
1410 WalUsage *walusage;
1411 BufferUsage *bufferusage;
1414
1415#ifdef DISABLE_LEADER_PARTICIPATION
1417#endif
1418
1419 /*
1420 * Enter parallel mode, and create context for parallel build of btree
1421 * index
1422 */
1423 EnterParallelMode();
1426 request);
1427
1429
1430 /*
1431 * Prepare for scan of the base relation. In a normal index build, we use
1432 * SnapshotAny because we must retrieve all tuples and do our own time
1433 * qual checks (because we have to index RECENTLY_DEAD tuples). In a
1434 * concurrent build, we take a regular MVCC snapshot and index whatever's
1435 * live according to that.
1436 */
1437 if (!isconcurrent)
1438 snapshot = SnapshotAny;
1439 else
1441
1442 /*
1443 * Estimate size for our own PARALLEL_KEY_BTREE_SHARED workspace, and
1444 * PARALLEL_KEY_TUPLESORT tuplesort workspace
1445 */
1450
1451 /*
1452 * Unique case requires a second spool, and so we may have to account for
1453 * another shared workspace for that -- PARALLEL_KEY_TUPLESORT_SPOOL2
1454 */
1457 else
1458 {
1461 }
1462
1463 /*
1464 * Estimate space for WalUsage and BufferUsage -- PARALLEL_KEY_WAL_USAGE
1465 * and PARALLEL_KEY_BUFFER_USAGE.
1466 *
1467 * If there are no extensions loaded that care, we could skip this. We
1468 * have no way of knowing whether anyone's looking at pgWalUsage or
1469 * pgBufferUsage, so do it unconditionally.
1470 */
1477
1478 /* Finally, estimate PARALLEL_KEY_QUERY_TEXT space */
1480 {
1484 }
1485 else
1487
1488 /* Everyone's had a chance to ask for space, so now create the DSM */
1489 InitializeParallelDSM(pcxt);
1490
1491 /* If no DSM segment was available, back out (do serial build) */
1493 {
1495 UnregisterSnapshot(snapshot);
1496 DestroyParallelContext(pcxt);
1497 ExitParallelMode();
1498 return;
1499 }
1500
1501 /* Store shared build state, for which we reserved space */
1503 /* Initialize immutable state */
1508 btshared->isconcurrent = isconcurrent;
1509 btshared->scantuplesortstates = scantuplesortstates;
1513 /* Initialize mutable state */
1514 btshared->nparticipantsdone = 0;
1515 btshared->reltuples = 0.0;
1517 btshared->indtuples = 0.0;
1520 ParallelTableScanFromBTShared(btshared),
1521 snapshot);
1522
1523 /*
1524 * Store shared tuplesort-private state, for which we reserved space.
1525 * Then, initialize opaque state using tuplesort routine.
1526 */
1528 tuplesort_initialize_shared(sharedsort, scantuplesortstates,
1529 pcxt->seg);
1530
1533
1534 /* Unique case requires a second spool, and associated shared state */
1536 sharedsort2 = NULL;
1537 else
1538 {
1539 /*
1540 * Store additional shared tuplesort-private state, for which we
1541 * reserved space. Then, initialize opaque state using tuplesort
1542 * routine.
1543 */
1545 tuplesort_initialize_shared(sharedsort2, scantuplesortstates,
1546 pcxt->seg);
1547
1549 }
1550
1551 /* Store query string for workers */
1553 {
1555
1559 }
1560
1561 /*
1562 * Allocate space for each worker's WalUsage and BufferUsage; no need to
1563 * initialize.
1564 */
1571
1572 /* Launch workers, saving status for leader/caller */
1573 LaunchParallelWorkers(pcxt);
1574 btleader->pcxt = pcxt;
1577 btleader->nparticipanttuplesorts++;
1578 btleader->btshared = btshared;
1579 btleader->sharedsort = sharedsort;
1580 btleader->sharedsort2 = sharedsort2;
1581 btleader->snapshot = snapshot;
1582 btleader->walusage = walusage;
1583 btleader->bufferusage = bufferusage;
1584
1585 /* If no workers were successfully launched, back out (do serial build) */
1587 {
1588 _bt_end_parallel(btleader);
1589 return;
1590 }
1591
1592 /* Save leader state now that it's clear build will be parallel */
1593 buildstate->btleader = btleader;
1594
1595 /* Join heap scan ourselves */
1598
1599 /*
1600 * Caller needs to wait for all launched workers when we return. Make
1601 * sure that the failure-to-start case will not hang forever.
1602 */
1603 WaitForParallelWorkersToAttach(pcxt);
1604}
1605
1606/*
1607 * Shut down workers, destroy parallel context, and end parallel mode.
1608 */
1609static void
1611{
1613
1614 /* Shutdown worker processes */
1616
1617 /*
1618 * Next, accumulate WAL usage. (This must wait for the workers to finish,
1619 * or we might get incomplete data.)
1620 */
1623
1624 /* Free last reference to MVCC snapshot, if one was used */
1628 ExitParallelMode();
1629}
1630
1631/*
1632 * Returns size of shared memory required to store state for a parallel
1633 * btree index build based on the snapshot its parallel scan will use.
1634 */
1637{
1638 /* c.f. shm_toc_allocate as to why BUFFERALIGN is used */
1640 table_parallelscan_estimate(heap, snapshot));
1641}
1642
1643/*
1644 * Within leader, wait for end of heap scan.
1645 *
1646 * When called, parallel heap scan started by _bt_begin_parallel() will
1647 * already be underway within worker processes (when leader participates
1648 * as a worker, we should end up here just as workers are finishing).
1649 *
1650 * Fills in fields needed for ambuild statistics, and lets caller set
1651 * field indicating that some worker encountered a broken HOT chain.
1652 *
1653 * Returns the total number of heap tuples scanned.
1654 */
1655static double
1657{
1659 int nparticipanttuplesorts;
1660 double reltuples;
1661
1662 nparticipanttuplesorts = buildstate->btleader->nparticipanttuplesorts;
1663 for (;;)
1664 {
1667 {
1670 *brokenhotchain = btshared->brokenhotchain;
1671 reltuples = btshared->reltuples;
1673 break;
1674 }
1676
1679 }
1680
1681 ConditionVariableCancelSleep();
1682
1683 return reltuples;
1684}
1685
1686/*
1687 * Within leader, participate as a parallel worker.
1688 */
1689static void
1691{
1696
1697 /* Allocate memory and initialize private spool */
1703
1704 /* Initialize second spool, if required */
1707 else
1708 {
1709 /* Allocate memory for worker's own private secondary spool */
1711
1712 /* Initialize worker's own secondary spool */
1716 }
1717
1718 /*
1719 * Might as well use reliable figure when doling out maintenance_work_mem
1720 * (when requested number of workers were not launched, this will be
1721 * somewhat higher than it is for other workers).
1722 */
1724
1725 /* Perform work common to all participants */
1729
1730#ifdef BTREE_BUILD_STATS
1732 {
1734 ResetUsage();
1735 }
1736#endif /* BTREE_BUILD_STATS */
1737}
1738
1739/*
1740 * Perform work within a launched parallel process.
1741 */
1742void
1744{
1748 BTShared *btshared;
1749 Sharedsort *sharedsort;
1750 Sharedsort *sharedsort2;
1751 Relation heapRel;
1752 Relation indexRel;
1755 WalUsage *walusage;
1756 BufferUsage *bufferusage;
1758
1759#ifdef BTREE_BUILD_STATS
1761 ResetUsage();
1762#endif /* BTREE_BUILD_STATS */
1763
1764 /*
1765 * The only possible status flag that can be set to the parallel worker is
1766 * PROC_IN_SAFE_IC.
1767 */
1770
1771 /* Set debug_query_string for individual workers first */
1774
1775 /* Report the query string from leader */
1777
1778 /* Look up nbtree shared state */
1780
1781 /* Open relations using lock modes known to be obtained by index.c */
1783 {
1786 }
1787 else
1788 {
1791 }
1792
1793 /* Track query ID */
1795
1796 /* Open relations within worker */
1799
1800 /* Initialize worker's own spool */
1802 btspool->heap = heapRel;
1803 btspool->index = indexRel;
1806
1807 /* Look up shared state private to tuplesort.c */
1809 tuplesort_attach_shared(sharedsort, seg);
1811 {
1813 sharedsort2 = NULL;
1814 }
1815 else
1816 {
1817 /* Allocate memory for worker's own private secondary spool */
1819
1820 /* Initialize worker's own secondary spool */
1824 /* Look up shared state private to tuplesort.c */
1826 tuplesort_attach_shared(sharedsort2, seg);
1827 }
1828
1829 /* Prepare to track buffer usage during parallel execution */
1830 InstrStartParallelQuery();
1831
1832 /* Perform sorting of spool, and possibly a spool2 */
1836
1837 /* Report WAL/buffer usage during parallel execution */
1841 &walusage[ParallelWorkerNumber]);
1842
1843#ifdef BTREE_BUILD_STATS
1845 {
1847 ResetUsage();
1848 }
1849#endif /* BTREE_BUILD_STATS */
1850
1853}
1854
1855/*
1856 * Perform a worker's portion of a parallel sort.
1857 *
1858 * This generates a tuplesort for passed btspool, and a second tuplesort
1859 * state if a second btspool is need (i.e. for unique index builds). All
1860 * other spool fields should already be set when this is called.
1861 *
1862 * sortmem is the amount of working memory to use within each worker,
1863 * expressed in KBs.
1864 *
1865 * When this returns, workers are done, and need only release resources.
1866 */
1867static void
1871{
1874 TableScanDesc scan;
1875 double reltuples;
1876 IndexInfo *indexInfo;
1877
1878 /* Initialize local tuplesort coordination state */
1881 coordinate->nParticipants = -1;
1882 coordinate->sharedsort = sharedsort;
1883
1884 /* Begin "partial" tuplesort */
1886 btspool->index,
1887 btspool->isunique,
1888 btspool->nulls_not_distinct,
1890 TUPLESORT_NONE);
1891
1892 /*
1893 * Just as with serial case, there may be a second spool. If so, a
1894 * second, dedicated spool2 partial tuplesort is required.
1895 */
1897 {
1899
1900 /*
1901 * We expect that the second one (for dead tuples) won't get very
1902 * full, so we give it only work_mem (unless sortmem is less for
1903 * worker). Worker processes are generally permitted to allocate
1904 * work_mem independently.
1905 */
1908 coordinate2->nParticipants = -1;
1909 coordinate2->sharedsort = sharedsort2;
1910 btspool2->sortstate =
1913 false);
1914 }
1915
1916 /* Fill in buildstate for _bt_build_callback() */
1923 buildstate.indtuples = 0;
1925
1926 /* Join parallel scan */
1930 ParallelTableScanFromBTShared(btshared));
1933 &buildstate, scan);
1934
1935 /* Execute this worker's part of the sort */
1941 {
1946 }
1947
1948 /*
1949 * Done. Record ambuild statistics, and whether we encountered a broken
1950 * HOT chain.
1951 */
1953 btshared->nparticipantsdone++;
1954 btshared->reltuples += reltuples;
1961
1962 /* Notify leader */
1964
1965 /* We can end tuplesorts immediately */
1969}
void WaitForParallelWorkersToFinish(ParallelContext *pcxt)
Definition parallel.c:805
ParallelContext * CreateParallelContext(const char *library_name, const char *function_name, int nworkers)
Definition parallel.c:175
void WaitForParallelWorkersToAttach(ParallelContext *pcxt)
Definition parallel.c:702
void pgstat_progress_update_param(int index, int64 val)
Definition backend_progress.c:49
void pgstat_progress_update_multi_param(int nparam, const int *index, const int64 *val)
Definition backend_progress.c:122
void pgstat_report_query_id(int64 query_id, bool force)
Definition backend_status.c:686
void pgstat_report_activity(BackendState state, const char *cmd_str)
Definition backend_status.c:572
bool PageIndexTupleOverwrite(Page page, OffsetNumber offnum, const void *newtup, Size newsize)
Definition bufpage.c:1404
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition bufpage.h:269
static void * PageGetItem(PageData *page, const ItemIdData *itemId)
Definition bufpage.h:379
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition bufpage.h:504
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition bufpage.h:397
BulkWriteState * smgr_bulk_start_rel(Relation rel, ForkNumber forknum)
Definition bulk_write.c:87
void smgr_bulk_write(BulkWriteState *bulkstate, BlockNumber blocknum, BulkWriteBuffer buf, bool page_std)
Definition bulk_write.c:323
BulkWriteBuffer smgr_bulk_get_buf(BulkWriteState *bulkstate)
Definition bulk_write.c:347
bool ConditionVariableCancelSleep(void)
Definition condition_variable.c:232
void ConditionVariableInit(ConditionVariable *cv)
Definition condition_variable.c:37
void ConditionVariableSleep(ConditionVariable *cv, uint32 wait_event_info)
Definition condition_variable.c:98
void ConditionVariableSignal(ConditionVariable *cv)
Definition condition_variable.c:261
void InstrAccumParallelQuery(BufferUsage *bufusage, WalUsage *walusage)
Definition instrument.c:219
void InstrEndParallelQuery(BufferUsage *bufusage, WalUsage *walusage)
Definition instrument.c:209
int32 ItemPointerCompare(const ItemPointerData *arg1, const ItemPointerData *arg2)
Definition itemptr.c:51
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition itup.h:131
bool _bt_dedup_save_htid(BTDedupState state, IndexTuple itup)
Definition nbtdedup.c:486
void _bt_dedup_start_pending(BTDedupState state, IndexTuple base, OffsetNumber baseoff)
Definition nbtdedup.c:435
IndexTuple _bt_form_posting(IndexTuple base, const ItemPointerData *htids, int nhtids)
Definition nbtdedup.c:864
void _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level, bool allequalimage)
Definition nbtpage.c:68
#define PROGRESS_BTREE_PHASE_PERFORMSORT_2
Definition nbtree.h:1148
static void BTreeTupleSetDownLink(IndexTuple pivot, BlockNumber blkno)
Definition nbtree.h:563
#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN
Definition nbtree.h:1146
#define PROGRESS_BTREE_PHASE_PERFORMSORT_1
Definition nbtree.h:1147
static uint32 BTreeTupleGetPostingOffset(IndexTuple posting)
Definition nbtree.h:530
static void BTreeTupleSetNAtts(IndexTuple itup, uint16 nkeyatts, bool heaptid)
Definition nbtree.h:596
static void _bt_blwritepage(BTWriteState *wstate, BulkWriteBuffer buf, BlockNumber blkno)
Definition nbtsort.c:641
static BTPageState * _bt_pagestate(BTWriteState *wstate, uint32 level)
Definition nbtsort.c:652
static void _bt_load(BTWriteState *wstate, BTSpool *btspool, BTSpool *btspool2)
Definition nbtsort.c:1139
static void _bt_parallel_scan_and_sort(BTSpool *btspool, BTSpool *btspool2, BTShared *btshared, Sharedsort *sharedsort, Sharedsort *sharedsort2, int sortmem, bool progress)
Definition nbtsort.c:1869
static Size _bt_parallel_estimate_shared(Relation heap, Snapshot snapshot)
Definition nbtsort.c:1637
static void _bt_sort_dedup_finish_pending(BTWriteState *wstate, BTPageState *state, BTDedupState dstate)
Definition nbtsort.c:1033
static double _bt_parallel_heapscan(BTBuildState *buildstate, bool *brokenhotchain)
Definition nbtsort.c:1657
IndexBuildResult * btbuild(Relation heap, Relation index, IndexInfo *indexInfo)
Definition nbtsort.c:299
static void _bt_begin_parallel(BTBuildState *buildstate, bool isconcurrent, int request)
Definition nbtsort.c:1399
static void _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup, Size truncextra)
Definition nbtsort.c:789
void _bt_parallel_build_main(dsm_segment *seg, shm_toc *toc)
Definition nbtsort.c:1744
static void _bt_build_callback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
Definition nbtsort.c:583
static double _bt_spools_heapscan(Relation heap, Relation index, BTBuildState *buildstate, IndexInfo *indexInfo)
Definition nbtsort.c:369
static void _bt_spool(BTSpool *btspool, const ItemPointerData *self, const Datum *values, const bool *isnull)
Definition nbtsort.c:531
static void _bt_uppershutdown(BTWriteState *wstate, BTPageState *state)
Definition nbtsort.c:1067
static BulkWriteBuffer _bt_blnewpage(BTWriteState *wstate, uint32 level)
Definition nbtsort.c:612
static void _bt_leader_participate_as_worker(BTBuildState *buildstate)
Definition nbtsort.c:1691
static void _bt_sortaddtup(Page page, Size itemsize, const IndexTupleData *itup, OffsetNumber itup_off, bool newfirstdataitem)
Definition nbtsort.c:720
void _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace, Page page, IndexTuple newtup)
Definition nbtutils.c:1119
IndexTuple _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
Definition nbtutils.c:693
int _bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright)
Definition nbtutils.c:912
static pairingheap_node * merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
Definition pairingheap.c:93
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition rel.h:533
void PrepareSortSupportFromIndexRel(Relation indexRel, bool reverse, SortSupport ssup)
Definition sortsupport.c:161
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition sortsupport.h:200
Definition nbtsort.c:209
Definition nbtree.h:877
Definition nbtsort.c:172
Definition nbtree.h:64
Definition nbtsort.c:236
Definition nbtree.h:796
Definition nbtsort.c:84
Definition nbtsort.c:251
Definition instrument.h:25
Definition bulk_write.c:62
Definition genam.h:39
Definition execnodes.h:174
Definition itup.h:36
Definition itemid.h:26
Definition itemptr.h:37
Definition c.h:1226
Definition parallel.h:34
Definition rel.h:56
Definition skey.h:65
Definition snapshot.h:139
Definition tuplesort.h:49
Definition sortsupport.h:61
Definition relscan.h:33
Definition tupdesc.h:149
Definition instrument.h:52
Definition dsm.c:67
Definition shm_toc.c:27
Definition regguts.h:323
TableScanDesc table_beginscan_parallel(Relation relation, ParallelTableScanDesc pscan)
Definition tableam.c:166
Size table_parallelscan_estimate(Relation rel, Snapshot snapshot)
Definition tableam.c:131
void table_parallelscan_initialize(Relation rel, ParallelTableScanDesc pscan, Snapshot snapshot)
Definition tableam.c:146
static double table_index_build_scan(Relation table_rel, Relation index_rel, IndexInfo *index_info, bool allow_sync, bool progress, IndexBuildCallback callback, void *callback_state, TableScanDesc scan)
Definition tableam.h:1765
void tuplesort_initialize_shared(Sharedsort *shared, int nWorkers, dsm_segment *seg)
Definition tuplesort.c:3210
void tuplesort_attach_shared(Sharedsort *shared, dsm_segment *seg)
Definition tuplesort.c:3233
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition tuplesortvariants.c:1063
Tuplesortstate * tuplesort_begin_index_btree(Relation heapRel, Relation indexRel, bool enforceUnique, bool uniqueNullsNotDistinct, int workMem, SortCoordinate coordinate, int sortopt)
Definition tuplesortvariants.c:360
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, const ItemPointerData *self, const Datum *values, const bool *isnull)
Definition tuplesortvariants.c:835
Typedef Documentation
◆ BTBuildState
| typedef struct BTBuildState BTBuildState |
◆ BTLeader
◆ BTPageState
| typedef struct BTPageState BTPageState |
◆ BTShared
◆ BTSpool
◆ BTWriteState
| typedef struct BTWriteState BTWriteState |
Function Documentation
◆ _bt_begin_parallel()
|
static |
Definition at line 1399 of file nbtsort.c.
1400{
1401 ParallelContext *pcxt;
1402 int scantuplesortstates;
1403 Snapshot snapshot;
1406 BTShared *btshared;
1407 Sharedsort *sharedsort;
1408 Sharedsort *sharedsort2;
1411 WalUsage *walusage;
1412 BufferUsage *bufferusage;
1415
1416#ifdef DISABLE_LEADER_PARTICIPATION
1418#endif
1419
1420 /*
1421 * Enter parallel mode, and create context for parallel build of btree
1422 * index
1423 */
1424 EnterParallelMode();
1427 request);
1428
1430
1431 /*
1432 * Prepare for scan of the base relation. In a normal index build, we use
1433 * SnapshotAny because we must retrieve all tuples and do our own time
1434 * qual checks (because we have to index RECENTLY_DEAD tuples). In a
1435 * concurrent build, we take a regular MVCC snapshot and index whatever's
1436 * live according to that.
1437 */
1438 if (!isconcurrent)
1439 snapshot = SnapshotAny;
1440 else
1442
1443 /*
1444 * Estimate size for our own PARALLEL_KEY_BTREE_SHARED workspace, and
1445 * PARALLEL_KEY_TUPLESORT tuplesort workspace
1446 */
1451
1452 /*
1453 * Unique case requires a second spool, and so we may have to account for
1454 * another shared workspace for that -- PARALLEL_KEY_TUPLESORT_SPOOL2
1455 */
1458 else
1459 {
1462 }
1463
1464 /*
1465 * Estimate space for WalUsage and BufferUsage -- PARALLEL_KEY_WAL_USAGE
1466 * and PARALLEL_KEY_BUFFER_USAGE.
1467 *
1468 * If there are no extensions loaded that care, we could skip this. We
1469 * have no way of knowing whether anyone's looking at pgWalUsage or
1470 * pgBufferUsage, so do it unconditionally.
1471 */
1478
1479 /* Finally, estimate PARALLEL_KEY_QUERY_TEXT space */
1481 {
1485 }
1486 else
1488
1489 /* Everyone's had a chance to ask for space, so now create the DSM */
1490 InitializeParallelDSM(pcxt);
1491
1492 /* If no DSM segment was available, back out (do serial build) */
1494 {
1496 UnregisterSnapshot(snapshot);
1497 DestroyParallelContext(pcxt);
1498 ExitParallelMode();
1499 return;
1500 }
1501
1502 /* Store shared build state, for which we reserved space */
1504 /* Initialize immutable state */
1509 btshared->isconcurrent = isconcurrent;
1510 btshared->scantuplesortstates = scantuplesortstates;
1514 /* Initialize mutable state */
1515 btshared->nparticipantsdone = 0;
1516 btshared->reltuples = 0.0;
1518 btshared->indtuples = 0.0;
1521 ParallelTableScanFromBTShared(btshared),
1522 snapshot);
1523
1524 /*
1525 * Store shared tuplesort-private state, for which we reserved space.
1526 * Then, initialize opaque state using tuplesort routine.
1527 */
1529 tuplesort_initialize_shared(sharedsort, scantuplesortstates,
1530 pcxt->seg);
1531
1534
1535 /* Unique case requires a second spool, and associated shared state */
1537 sharedsort2 = NULL;
1538 else
1539 {
1540 /*
1541 * Store additional shared tuplesort-private state, for which we
1542 * reserved space. Then, initialize opaque state using tuplesort
1543 * routine.
1544 */
1546 tuplesort_initialize_shared(sharedsort2, scantuplesortstates,
1547 pcxt->seg);
1548
1550 }
1551
1552 /* Store query string for workers */
1554 {
1556
1560 }
1561
1562 /*
1563 * Allocate space for each worker's WalUsage and BufferUsage; no need to
1564 * initialize.
1565 */
1572
1573 /* Launch workers, saving status for leader/caller */
1574 LaunchParallelWorkers(pcxt);
1575 btleader->pcxt = pcxt;
1578 btleader->nparticipanttuplesorts++;
1579 btleader->btshared = btshared;
1580 btleader->sharedsort = sharedsort;
1581 btleader->sharedsort2 = sharedsort2;
1582 btleader->snapshot = snapshot;
1583 btleader->walusage = walusage;
1584 btleader->bufferusage = bufferusage;
1585
1586 /* If no workers were successfully launched, back out (do serial build) */
1588 {
1589 _bt_end_parallel(btleader);
1590 return;
1591 }
1592
1593 /* Save leader state now that it's clear build will be parallel */
1594 buildstate->btleader = btleader;
1595
1596 /* Join heap scan ourselves */
1599
1600 /*
1601 * Caller needs to wait for all launched workers when we return. Make
1602 * sure that the failure-to-start case will not hang forever.
1603 */
1604 WaitForParallelWorkersToAttach(pcxt);
1605}
References _bt_end_parallel(), _bt_leader_participate_as_worker(), _bt_parallel_estimate_shared(), Assert, BTShared::brokenhotchain, BTLeader::btshared, BTLeader::bufferusage, ConditionVariableInit(), CreateParallelContext(), debug_query_string, DestroyParallelContext(), EnterParallelMode(), ParallelContext::estimator, ExitParallelMode(), fb(), GetTransactionSnapshot(), BTShared::havedead, BTShared::heaprelid, BTShared::indexrelid, BTShared::indtuples, InitializeParallelDSM(), BTShared::isconcurrent, IsMVCCSnapshot, BTShared::isunique, LaunchParallelWorkers(), mul_size(), BTShared::mutex, BTShared::nparticipantsdone, BTLeader::nparticipanttuplesorts, BTShared::nulls_not_distinct, ParallelContext::nworkers, ParallelContext::nworkers_launched, palloc0_object, PARALLEL_KEY_BTREE_SHARED, PARALLEL_KEY_BUFFER_USAGE, PARALLEL_KEY_QUERY_TEXT, PARALLEL_KEY_TUPLESORT, PARALLEL_KEY_TUPLESORT_SPOOL2, PARALLEL_KEY_WAL_USAGE, ParallelTableScanFromBTShared, BTLeader::pcxt, pgstat_get_my_query_id(), BTShared::queryid, RegisterSnapshot(), RelationGetRelid, BTShared::reltuples, BTShared::scantuplesortstates, ParallelContext::seg, BTLeader::sharedsort, BTLeader::sharedsort2, shm_toc_allocate(), shm_toc_estimate_chunk, shm_toc_estimate_keys, shm_toc_insert(), BTLeader::snapshot, SnapshotAny, SpinLockInit(), table_parallelscan_initialize(), ParallelContext::toc, tuplesort_estimate_shared(), tuplesort_initialize_shared(), UnregisterSnapshot(), WaitForParallelWorkersToAttach(), BTLeader::walusage, and BTShared::workersdonecv.
Referenced by _bt_spools_heapscan().
◆ _bt_blnewpage()
|
static |
Definition at line 612 of file nbtsort.c.
613{
615 Page page;
616 BTPageOpaque opaque;
617
620
621 /* Zero the page and set up standard page header info */
623
624 /* Initialize BT opaque state */
625 opaque = BTPageGetOpaque(page);
627 opaque->btpo_level = level;
629 opaque->btpo_cycleid = 0;
630
631 /* Make the P_HIKEY line pointer appear allocated */
633
635}
References _bt_pageinit(), BTP_LEAF, BTPageGetOpaque, BTPageOpaqueData::btpo_cycleid, BTPageOpaqueData::btpo_flags, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, buf, fb(), P_NONE, and smgr_bulk_get_buf().
Referenced by _bt_buildadd(), and _bt_pagestate().
◆ _bt_blwritepage()
|
static |
Definition at line 641 of file nbtsort.c.
642{
644 /* smgr_bulk_write took ownership of 'buf' */
645}
References buf, fb(), and smgr_bulk_write().
Referenced by _bt_buildadd(), and _bt_uppershutdown().
◆ _bt_build_callback()
|
static |
Definition at line 583 of file nbtsort.c.
589{
591
592 /*
593 * insert the index tuple into the appropriate spool file for subsequent
594 * processing
595 */
598 else
599 {
600 /* dead tuples are put into spool2 */
603 }
604
605 buildstate->indtuples += 1;
606}
References _bt_spool(), fb(), and values.
Referenced by _bt_parallel_scan_and_sort(), and _bt_spools_heapscan().
◆ _bt_buildadd()
|
static |
Definition at line 789 of file nbtsort.c.
791{
793 Page npage;
800
801 /*
802 * This is a handy place to check for cancel interrupts during the btree
803 * load phase of index creation.
804 */
805 CHECK_FOR_INTERRUPTS();
806
813
817 /* Leaf case has slightly different rules due to suffix truncation */
819
820 /*
821 * Check whether the new item can fit on a btree page on current level at
822 * all.
823 *
824 * Every newly built index will treat heap TID as part of the keyspace,
825 * which imposes the requirement that new high keys must occasionally have
826 * a heap TID appended within _bt_truncate(). That may leave a new pivot
827 * tuple one or two MAXALIGN() quantums larger than the original
828 * firstright tuple it's derived from. v4 deals with the problem by
829 * decreasing the limit on the size of tuples inserted on the leaf level
830 * by the same small amount. Enforce the new v4+ limit on the leaf level,
831 * and the old limit on internal levels, since pivot tuples may need to
832 * make use of the reserved space. This should never fail on internal
833 * pages.
834 */
837 itup);
838
839 /*
840 * Check to see if current page will fit new item, with space left over to
841 * append a heap TID during suffix truncation when page is a leaf page.
842 *
843 * It is guaranteed that we can fit at least 2 non-pivot tuples plus a
844 * high key with heap TID when finishing off a leaf page, since we rely on
845 * _bt_check_third_page() rejecting oversized non-pivot tuples. On
846 * internal pages we can always fit 3 pivot tuples with larger internal
847 * page tuple limit (includes page high key).
848 *
849 * Most of the time, a page is only "full" in the sense that the soft
850 * fillfactor-wise limit has been exceeded. However, we must always leave
851 * at least two items plus a high key on each page before starting a new
852 * page. Disregard fillfactor and insert on "full" current page if we
853 * don't have the minimum number of items yet. (Note that we deliberately
854 * assume that suffix truncation neither enlarges nor shrinks new high key
855 * when applying soft limit, except when last tuple has a posting list.)
856 */
860 {
861 /*
862 * Finish off the page and write it out.
863 */
867 ItemId ii;
870
871 /* Create new page of same level */
874
875 /* and assign it a page position */
877
878 /*
879 * We copy the last item on the page into the new page, and then
880 * rearrange the old page so that the 'last item' becomes its high key
881 * rather than a true data item. There had better be at least two
882 * items on the page already, else the page would be empty of useful
883 * data.
884 */
889 !isleaf);
890
891 /*
892 * Move 'last' into the high key position on opage. _bt_blnewpage()
893 * allocated empty space for a line pointer when opage was first
894 * created, so this is a matter of rearranging already-allocated space
895 * on page, and initializing high key line pointer. (Actually, leaf
896 * pages must also swap oitup with a truncated version of oitup, which
897 * is sometimes larger than oitup, though never by more than the space
898 * needed to append a heap TID.)
899 */
901 *hii = *ii;
904
906 {
907 IndexTuple lastleft;
908 IndexTuple truncated;
909
910 /*
911 * Truncate away any unneeded attributes from high key on leaf
912 * level. This is only done at the leaf level because downlinks
913 * in internal pages are either negative infinity items, or get
914 * their contents from copying from one level down. See also:
915 * _bt_split().
916 *
917 * We don't try to bias our choice of split point to make it more
918 * likely that _bt_truncate() can truncate away more attributes,
919 * whereas the split point used within _bt_split() is chosen much
920 * more delicately. Even still, the lastleft and firstright
921 * tuples passed to _bt_truncate() here are at least not fully
922 * equal to each other when deduplication is used, unless there is
923 * a large group of duplicates (also, unique index builds usually
924 * have few or no spool2 duplicates). When the split point is
925 * between two unequal tuples, _bt_truncate() will avoid including
926 * a heap TID in the new high key, which is the most important
927 * benefit of suffix truncation.
928 *
929 * Overwrite the old item with new truncated high key directly.
930 * oitup is already located at the physical beginning of tuple
931 * space, so this should directly reuse the existing tuple space.
932 */
935
938 wstate->inskey);
941 pfree(truncated);
942
943 /* oitup should continue to point to the page's high key */
946 }
947
948 /*
949 * Link the old page into its parent, using its low key. If we don't
950 * have a parent, we have to create one; this adds a new btree level.
951 */
954
964
965 /*
966 * Save a copy of the high key from the old page. It is also the low
967 * key for the new page.
968 */
970
971 /*
972 * Set the sibling links for both pages.
973 */
974 {
977
981 }
982
983 /*
984 * Write out the old page. _bt_blwritepage takes ownership of the
985 * 'opage' buffer.
986 */
988
989 /*
990 * Reset last_off to point to new page
991 */
993 }
994
995 /*
996 * By here, either original page is still the current page, or a new page
997 * was created that became the current page. Either way, the current page
998 * definitely has space for new item.
999 *
1000 * If the new item is the first for its page, it must also be the first
1001 * item on its entire level. On later same-level pages, a low key for a
1002 * page will be copied from the prior page in the code above. Generate a
1003 * minus infinity low key here instead.
1004 */
1006 {
1011 }
1012
1013 /*
1014 * Add the new item into the current page.
1015 */
1019
1023}
References _bt_blnewpage(), _bt_blwritepage(), _bt_buildadd(), _bt_check_third_page(), _bt_pagestate(), _bt_sortaddtup(), _bt_truncate(), Assert, BTMaxItemSize, BTPageGetOpaque, BTreeTupleGetNAtts, BTreeTupleSetDownLink(), BTreeTupleSetNAtts(), CHECK_FOR_INTERRUPTS, CopyIndexTuple(), elog, ERROR, fb(), IndexRelationGetNumberOfKeyAttributes, IndexTupleSize(), ItemIdGetLength, ItemIdSetUnused, MAXALIGN, OffsetNumberNext, OffsetNumberPrev, P_FIRSTKEY, P_HIKEY, P_LEFTMOST, P_NONE, PageGetFreeSpace(), PageGetItem(), PageGetItemId(), PageIndexTupleOverwrite(), palloc0_object, pfree(), and unlikely.
Referenced by _bt_buildadd(), _bt_load(), _bt_sort_dedup_finish_pending(), and _bt_uppershutdown().
◆ _bt_end_parallel()
Definition at line 1611 of file nbtsort.c.
1612{
1614
1615 /* Shutdown worker processes */
1617
1618 /*
1619 * Next, accumulate WAL usage. (This must wait for the workers to finish,
1620 * or we might get incomplete data.)
1621 */
1624
1625 /* Free last reference to MVCC snapshot, if one was used */
1629 ExitParallelMode();
1630}
References BTLeader::bufferusage, DestroyParallelContext(), ExitParallelMode(), i, InstrAccumParallelQuery(), IsMVCCSnapshot, ParallelContext::nworkers_launched, BTLeader::pcxt, BTLeader::snapshot, UnregisterSnapshot(), WaitForParallelWorkersToFinish(), and BTLeader::walusage.
Referenced by _bt_begin_parallel(), and btbuild().
◆ _bt_leader_participate_as_worker()
|
static |
Definition at line 1691 of file nbtsort.c.
1692{
1697
1698 /* Allocate memory and initialize private spool */
1704
1705 /* Initialize second spool, if required */
1708 else
1709 {
1710 /* Allocate memory for worker's own private secondary spool */
1712
1713 /* Initialize worker's own secondary spool */
1717 }
1718
1719 /*
1720 * Might as well use reliable figure when doling out maintenance_work_mem
1721 * (when requested number of workers were not launched, this will be
1722 * somewhat higher than it is for other workers).
1723 */
1725
1726 /* Perform work common to all participants */
1730
1731#ifdef BTREE_BUILD_STATS
1733 {
1735 ResetUsage();
1736 }
1737#endif /* BTREE_BUILD_STATS */
1738}
References _bt_parallel_scan_and_sort(), BTLeader::btshared, fb(), BTShared::isunique, log_btree_build_stats, maintenance_work_mem, BTLeader::nparticipanttuplesorts, palloc0_object, ResetUsage(), BTLeader::sharedsort, BTLeader::sharedsort2, and ShowUsage().
Referenced by _bt_begin_parallel().
◆ _bt_leafbuild()
Definition at line 542 of file nbtsort.c.
543{
545
546#ifdef BTREE_BUILD_STATS
548 {
550 ResetUsage();
551 }
552#endif /* BTREE_BUILD_STATS */
553
554 /* Execute the sort */
559 {
563 }
564
568 /* _bt_mkscankey() won't set allequalimage without metapage */
570
571 /* reserve the metapage */
573
577}
References _bt_allequalimage(), _bt_load(), _bt_mkscankey(), BTREE_METAPAGE, fb(), log_btree_build_stats, pgstat_progress_update_param(), PROGRESS_BTREE_PHASE_LEAF_LOAD, PROGRESS_BTREE_PHASE_PERFORMSORT_1, PROGRESS_BTREE_PHASE_PERFORMSORT_2, PROGRESS_CREATEIDX_SUBPHASE, ResetUsage(), ShowUsage(), and tuplesort_performsort().
Referenced by btbuild().
◆ _bt_load()
|
static |
Definition at line 1139 of file nbtsort.c.
1140{
1143 IndexTuple itup,
1149 SortSupport sortKeys;
1151 bool deduplicate;
1152
1154
1157
1159 {
1160 /*
1161 * Another BTSpool for dead tuples exists. Now we have to merge
1162 * btspool and btspool2.
1163 */
1164
1165 /* the preparation of merge */
1168
1169 /* Prepare SortSupport data for each column */
1171
1173 {
1176 bool reverse;
1177
1180 sortKey->ssup_nulls_first =
1183 /* Abbreviation is not supported here */
1185
1187
1189
1191 }
1192
1193 for (;;)
1194 {
1197 {
1199 break;
1200 }
1202 {
1204
1206 {
1207 SortSupport entry;
1209 attrDatum2;
1211 isNull2;
1212
1213 entry = sortKeys + i - 1;
1216
1219 entry);
1221 {
1223 break;
1224 }
1226 break;
1227 }
1228
1229 /*
1230 * If key values are equal, we sort on ItemPointer. This is
1231 * required for btree indexes, since heap TID is treated as an
1232 * implicit last key attribute in order to ensure that all
1233 * keys in the index are physically unique.
1234 */
1236 {
1241 }
1242 }
1243 else
1245
1246 /* When we see first tuple, create first index page */
1249
1251 {
1254 }
1255 else
1256 {
1259 }
1260
1261 /* Report progress */
1263 ++tuples_done);
1264 }
1265 pfree(sortKeys);
1266 }
1267 else if (deduplicate)
1268 {
1269 /* merge is unnecessary, deduplicate into posting lists */
1271
1276 /* Metadata about base tuple of current pending posting list */
1279 dstate->basetupsize = 0;
1280 /* Metadata about current pending posting list TIDs */
1282 dstate->nhtids = 0;
1283 dstate->nitems = 0;
1286
1289 {
1290 /* When we see first tuple, create first index page */
1292 {
1294
1295 /*
1296 * Limit size of posting list tuples to 1/10 space we want to
1297 * leave behind on the page, plus space for final item's line
1298 * pointer. This is equal to the space that we'd like to
1299 * leave behind on each leaf page when fillfactor is 90,
1300 * allowing us to get close to fillfactor% space utilization
1301 * when there happen to be a great many duplicates. (This
1302 * makes higher leaf fillfactor settings ineffective when
1303 * building indexes that have many duplicates, but packing
1304 * leaf pages full with few very large tuples doesn't seem
1305 * like a useful goal.)
1306 */
1312
1313 /* start new pending posting list with itup copy */
1315 InvalidOffsetNumber);
1316 }
1318 itup) > keysz &&
1320 {
1321 /*
1322 * Tuple is equal to base tuple of pending posting list. Heap
1323 * TID from itup has been saved in state.
1324 */
1325 }
1326 else
1327 {
1328 /*
1329 * Tuple is not equal to pending posting list tuple, or
1330 * _bt_dedup_save_htid() opted to not merge current item into
1331 * pending posting list.
1332 */
1335
1336 /* start new pending posting list with itup copy */
1338 InvalidOffsetNumber);
1339 }
1340
1341 /* Report progress */
1343 ++tuples_done);
1344 }
1345
1347 {
1348 /*
1349 * Handle the last item (there must be a last item when the
1350 * tuplesort returned one or more tuples)
1351 */
1355 }
1356
1358 }
1359 else
1360 {
1361 /* merging and deduplication are both unnecessary */
1364 {
1365 /* When we see first tuple, create first index page */
1368
1370
1371 /* Report progress */
1373 ++tuples_done);
1374 }
1375 }
1376
1377 /* Close down final pages and write the metapage */
1380}
References _bt_buildadd(), _bt_dedup_save_htid(), _bt_dedup_start_pending(), _bt_keep_natts_fast(), _bt_pagestate(), _bt_sort_dedup_finish_pending(), _bt_uppershutdown(), ApplySortComparator(), Assert, BTGetDeduplicateItems, BTMaxItemSize, compare(), CopyIndexTuple(), CurrentMemoryContext, fb(), i, index_getattr(), INDEX_SIZE_MASK, IndexRelationGetNumberOfKeyAttributes, InvalidOffsetNumber, ItemPointerCompare(), MAIN_FORKNUM, MAXALIGN_DOWN, merge(), palloc(), palloc0_array, palloc_object, pfree(), pgstat_progress_update_param(), PrepareSortSupportFromIndexRel(), PROGRESS_CREATEIDX_TUPLES_DONE, RelationGetDescr, SK_BT_DESC, SK_BT_NULLS_FIRST, smgr_bulk_finish(), smgr_bulk_start_rel(), IndexTupleData::t_tid, and tuplesort_getindextuple().
Referenced by _bt_leafbuild().
◆ _bt_pagestate()
|
static |
Definition at line 652 of file nbtsort.c.
653{
655
656 /* create initial page for level */
658
659 /* and assign it a page position */
661
663 /* initialize lastoff so first item goes into P_FIRSTKEY */
665 state->btps_lastextra = 0;
666 state->btps_level = level;
667 /* set "full" threshold based on level. See notes at head of file. */
668 if (level > 0)
670 else
672
673 /* no parent level, yet */
675
677}
References _bt_blnewpage(), BTGetTargetPageFreeSpace, BTREE_NONLEAF_FILLFACTOR, fb(), P_HIKEY, and palloc0_object.
Referenced by _bt_buildadd(), and _bt_load().
◆ _bt_parallel_build_main()
| void _bt_parallel_build_main | ( | dsm_segment * | seg, |
| shm_toc * | toc | ||
| ) |
Definition at line 1744 of file nbtsort.c.
1745{
1749 BTShared *btshared;
1750 Sharedsort *sharedsort;
1751 Sharedsort *sharedsort2;
1752 Relation heapRel;
1753 Relation indexRel;
1756 WalUsage *walusage;
1757 BufferUsage *bufferusage;
1759
1760#ifdef BTREE_BUILD_STATS
1762 ResetUsage();
1763#endif /* BTREE_BUILD_STATS */
1764
1765 /*
1766 * The only possible status flag that can be set to the parallel worker is
1767 * PROC_IN_SAFE_IC.
1768 */
1771
1772 /* Set debug_query_string for individual workers first */
1775
1776 /* Report the query string from leader */
1778
1779 /* Look up nbtree shared state */
1781
1782 /* Open relations using lock modes known to be obtained by index.c */
1784 {
1787 }
1788 else
1789 {
1792 }
1793
1794 /* Track query ID */
1796
1797 /* Open relations within worker */
1800
1801 /* Initialize worker's own spool */
1803 btspool->heap = heapRel;
1804 btspool->index = indexRel;
1807
1808 /* Look up shared state private to tuplesort.c */
1810 tuplesort_attach_shared(sharedsort, seg);
1812 {
1814 sharedsort2 = NULL;
1815 }
1816 else
1817 {
1818 /* Allocate memory for worker's own private secondary spool */
1820
1821 /* Initialize worker's own secondary spool */
1825 /* Look up shared state private to tuplesort.c */
1827 tuplesort_attach_shared(sharedsort2, seg);
1828 }
1829
1830 /* Prepare to track buffer usage during parallel execution */
1831 InstrStartParallelQuery();
1832
1833 /* Perform sorting of spool, and possibly a spool2 */
1837
1838 /* Report WAL/buffer usage during parallel execution */
1842 &walusage[ParallelWorkerNumber]);
1843
1844#ifdef BTREE_BUILD_STATS
1846 {
1848 ResetUsage();
1849 }
1850#endif /* BTREE_BUILD_STATS */
1851
1854}
References _bt_parallel_scan_and_sort(), AccessExclusiveLock, Assert, debug_query_string, fb(), BTShared::heaprelid, index_close(), index_open(), BTShared::indexrelid, InstrEndParallelQuery(), InstrStartParallelQuery(), BTShared::isconcurrent, BTShared::isunique, log_btree_build_stats, maintenance_work_mem, MyProc, BTShared::nulls_not_distinct, palloc0_object, PARALLEL_KEY_BTREE_SHARED, PARALLEL_KEY_BUFFER_USAGE, PARALLEL_KEY_QUERY_TEXT, PARALLEL_KEY_TUPLESORT, PARALLEL_KEY_TUPLESORT_SPOOL2, PARALLEL_KEY_WAL_USAGE, ParallelWorkerNumber, pgstat_report_activity(), pgstat_report_query_id(), PROC_IN_SAFE_IC, BTShared::queryid, ResetUsage(), RowExclusiveLock, BTShared::scantuplesortstates, ShareLock, ShareUpdateExclusiveLock, shm_toc_lookup(), ShowUsage(), STATE_RUNNING, PGPROC::statusFlags, table_close(), table_open(), and tuplesort_attach_shared().
◆ _bt_parallel_estimate_shared()
Definition at line 1637 of file nbtsort.c.
1638{
1639 /* c.f. shm_toc_allocate as to why BUFFERALIGN is used */
1641 table_parallelscan_estimate(heap, snapshot));
1642}
References add_size(), BUFFERALIGN, and table_parallelscan_estimate().
Referenced by _bt_begin_parallel().
◆ _bt_parallel_heapscan()
|
static |
Definition at line 1657 of file nbtsort.c.
1658{
1660 int nparticipanttuplesorts;
1661 double reltuples;
1662
1663 nparticipanttuplesorts = buildstate->btleader->nparticipanttuplesorts;
1664 for (;;)
1665 {
1668 {
1671 *brokenhotchain = btshared->brokenhotchain;
1672 reltuples = btshared->reltuples;
1674 break;
1675 }
1677
1680 }
1681
1682 ConditionVariableCancelSleep();
1683
1684 return reltuples;
1685}
References BTShared::brokenhotchain, ConditionVariableCancelSleep(), ConditionVariableSleep(), fb(), BTShared::havedead, BTShared::indtuples, BTShared::mutex, BTShared::nparticipantsdone, BTShared::reltuples, SpinLockAcquire(), SpinLockRelease(), and BTShared::workersdonecv.
Referenced by _bt_spools_heapscan().
◆ _bt_parallel_scan_and_sort()
|
static |
Definition at line 1869 of file nbtsort.c.
1872{
1875 TableScanDesc scan;
1876 double reltuples;
1877 IndexInfo *indexInfo;
1878
1879 /* Initialize local tuplesort coordination state */
1882 coordinate->nParticipants = -1;
1883 coordinate->sharedsort = sharedsort;
1884
1885 /* Begin "partial" tuplesort */
1887 btspool->index,
1888 btspool->isunique,
1889 btspool->nulls_not_distinct,
1891 TUPLESORT_NONE);
1892
1893 /*
1894 * Just as with serial case, there may be a second spool. If so, a
1895 * second, dedicated spool2 partial tuplesort is required.
1896 */
1898 {
1900
1901 /*
1902 * We expect that the second one (for dead tuples) won't get very
1903 * full, so we give it only work_mem (unless sortmem is less for
1904 * worker). Worker processes are generally permitted to allocate
1905 * work_mem independently.
1906 */
1909 coordinate2->nParticipants = -1;
1910 coordinate2->sharedsort = sharedsort2;
1911 btspool2->sortstate =
1914 false);
1915 }
1916
1917 /* Fill in buildstate for _bt_build_callback() */
1924 buildstate.indtuples = 0;
1926
1927 /* Join parallel scan */
1931 ParallelTableScanFromBTShared(btshared));
1934 &buildstate, scan);
1935
1936 /* Execute this worker's part of the sort */
1942 {
1947 }
1948
1949 /*
1950 * Done. Record ambuild statistics, and whether we encountered a broken
1951 * HOT chain.
1952 */
1954 btshared->nparticipantsdone++;
1955 btshared->reltuples += reltuples;
1962
1963 /* Notify leader */
1965
1966 /* We can end tuplesorts immediately */
1970}
References _bt_build_callback(), BTShared::brokenhotchain, BuildIndexInfo(), ConditionVariableSignal(), fb(), BTShared::havedead, IndexInfo::ii_BrokenHotChain, IndexInfo::ii_Concurrent, BTShared::indtuples, BTShared::isconcurrent, BTShared::isunique, Min, BTShared::mutex, BTShared::nparticipantsdone, BTShared::nulls_not_distinct, palloc0_object, ParallelTableScanFromBTShared, pgstat_progress_update_param(), progress, PROGRESS_BTREE_PHASE_PERFORMSORT_1, PROGRESS_BTREE_PHASE_PERFORMSORT_2, PROGRESS_CREATEIDX_SUBPHASE, BTShared::reltuples, SpinLockAcquire(), SpinLockRelease(), table_beginscan_parallel(), table_index_build_scan(), tuplesort_begin_index_btree(), tuplesort_end(), TUPLESORT_NONE, tuplesort_performsort(), work_mem, and BTShared::workersdonecv.
Referenced by _bt_leader_participate_as_worker(), and _bt_parallel_build_main().
◆ _bt_slideleft()
Definition at line 689 of file nbtsort.c.
References Assert, fb(), OffsetNumberNext, P_FIRSTKEY, P_HIKEY, PageGetItemId(), and PageGetMaxOffsetNumber().
Referenced by _bt_uppershutdown().
◆ _bt_sort_dedup_finish_pending()
|
static |
Definition at line 1033 of file nbtsort.c.
1035{
1037
1040 else
1041 {
1044
1045 /* form a tuple with a posting list */
1047 dstate->htids,
1048 dstate->nhtids);
1049 /* Calculate posting list overhead */
1052
1055 }
1056
1057 dstate->nmaxitems = 0;
1058 dstate->nhtids = 0;
1059 dstate->nitems = 0;
1060 dstate->phystupsize = 0;
1061}
References _bt_buildadd(), _bt_form_posting(), Assert, BTreeTupleGetPostingOffset(), fb(), IndexTupleSize(), and pfree().
Referenced by _bt_load().
◆ _bt_sortaddtup()
|
static |
Definition at line 720 of file nbtsort.c.
References BTreeTupleSetNAtts(), elog, ERROR, fb(), InvalidOffsetNumber, PageAddItem, and IndexTupleData::t_info.
Referenced by _bt_buildadd().
◆ _bt_spool()
|
static |
Definition at line 531 of file nbtsort.c.
References fb(), tuplesort_putindextuplevalues(), and values.
Referenced by _bt_build_callback().
◆ _bt_spooldestroy()
Definition at line 521 of file nbtsort.c.
References fb(), pfree(), and tuplesort_end().
Referenced by _bt_spools_heapscan(), and btbuild().
◆ _bt_spools_heapscan()
|
static |
Definition at line 369 of file nbtsort.c.
371{
374 double reltuples = 0;
375
376 /*
377 * We size the sort area as maintenance_work_mem rather than work_mem to
378 * speed index creation. This should be OK since a single backend can't
379 * run multiple index creations in parallel (see also: notes on
380 * parallelism and maintenance_work_mem below).
381 */
382 btspool->heap = heap;
386
387 /* Save as primary spool */
389
390 /* Report table scan phase started */
393
394 /* Attempt to launch parallel worker scan when required */
397 indexInfo->ii_ParallelWorkers);
398
399 /*
400 * If parallel build requested and at least one worker process was
401 * successfully launched, set up coordination state
402 */
404 {
407 coordinate->nParticipants =
408 buildstate->btleader->nparticipanttuplesorts;
410 }
411
412 /*
413 * Begin serial/leader tuplesort.
414 *
415 * In cases where parallelism is involved, the leader receives the same
416 * share of maintenance_work_mem as a serial sort (it is generally treated
417 * in the same way as a serial sort once we return). Parallel worker
418 * Tuplesortstates will have received only a fraction of
419 * maintenance_work_mem, though.
420 *
421 * We rely on the lifetime of the Leader Tuplesortstate almost not
422 * overlapping with any worker Tuplesortstate's lifetime. There may be
423 * some small overlap, but that's okay because we rely on leader
424 * Tuplesortstate only allocating a small, fixed amount of memory here.
425 * When its tuplesort_performsort() is called (by our caller), and
426 * significant amounts of memory are likely to be used, all workers must
427 * have already freed almost all memory held by their Tuplesortstates
428 * (they are about to go away completely, too). The overall effect is
429 * that maintenance_work_mem always represents an absolute high watermark
430 * on the amount of memory used by a CREATE INDEX operation, regardless of
431 * the use of parallelism or any other factor.
432 */
433 buildstate->spool->sortstate =
435 buildstate->nulls_not_distinct,
437 TUPLESORT_NONE);
438
439 /*
440 * If building a unique index, put dead tuples in a second spool to keep
441 * them out of the uniqueness check. We expect that the second spool (for
442 * dead tuples) won't get very full, so we give it only work_mem.
443 */
445 {
448
449 /* Initialize secondary spool */
450 btspool2->heap = heap;
453 /* Save as secondary spool */
455
457 {
458 /*
459 * Set up non-private state that is passed to
460 * tuplesort_begin_index_btree() about the basic high level
461 * coordination of a parallel sort.
462 */
465 coordinate2->nParticipants =
466 buildstate->btleader->nparticipanttuplesorts;
468 }
469
470 /*
471 * We expect that the second one (for dead tuples) won't get very
472 * full, so we give it only work_mem
473 */
474 buildstate->spool2->sortstate =
477 }
478
479 /* Fill spool using either serial or parallel heap scan */
483 NULL);
484 else
486 &indexInfo->ii_BrokenHotChain);
487
488 /*
489 * Set the progress target for the next phase. Reset the block number
490 * values set by table_index_build_scan
491 */
492 {
497 };
499 buildstate->indtuples,
500 0, 0
501 };
502
504 }
505
506 /* okay, all heap tuples are spooled */
508 {
509 /* spool2 turns out to be unnecessary */
512 }
513
514 return reltuples;
515}
References _bt_begin_parallel(), _bt_build_callback(), _bt_parallel_heapscan(), _bt_spooldestroy(), fb(), IndexInfo::ii_BrokenHotChain, IndexInfo::ii_Concurrent, IndexInfo::ii_NullsNotDistinct, IndexInfo::ii_ParallelWorkers, IndexInfo::ii_Unique, maintenance_work_mem, palloc0_object, pgstat_progress_update_multi_param(), pgstat_progress_update_param(), PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN, PROGRESS_CREATEIDX_SUBPHASE, PROGRESS_CREATEIDX_TUPLES_TOTAL, PROGRESS_SCAN_BLOCKS_DONE, PROGRESS_SCAN_BLOCKS_TOTAL, table_index_build_scan(), tuplesort_begin_index_btree(), TUPLESORT_NONE, and work_mem.
Referenced by btbuild().
◆ _bt_uppershutdown()
|
static |
Definition at line 1067 of file nbtsort.c.
1068{
1069 BTPageState *s;
1071 uint32 rootlevel = 0;
1073
1074 /*
1075 * Each iteration of this loop completes one more level of the tree.
1076 */
1078 {
1079 BlockNumber blkno;
1080 BTPageOpaque opaque;
1081
1082 blkno = s->btps_blkno;
1084
1085 /*
1086 * We have to link the last page on this level to somewhere.
1087 *
1088 * If we're at the top, it's the root, so attach it to the metapage.
1089 * Otherwise, add an entry for it to its parent using its low key.
1090 * This may cause the last page of the parent level to split, but
1091 * that's not a problem -- we haven't gotten to it yet.
1092 */
1094 {
1096 rootblkno = blkno;
1097 rootlevel = s->btps_level;
1098 }
1099 else
1100 {
1104 P_LEFTMOST(opaque));
1106 !P_LEFTMOST(opaque));
1111 }
1112
1113 /*
1114 * This is the rightmost page, so the ItemId array needs to be slid
1115 * back one slot. Then we can dump out the page.
1116 */
1120 }
1121
1122 /*
1123 * As the last step in the process, construct the metapage and make it
1124 * point to the new root (unless we had no data at all, in which case it's
1125 * set to point to "P_NONE"). This changes the index to the "valid" state
1126 * by filling in a valid magic number in the metapage.
1127 */
1130 wstate->inskey->allequalimage);
1132}
References _bt_blwritepage(), _bt_buildadd(), _bt_initmetapage(), _bt_slideleft(), Assert, BTP_ROOT, BTPageGetOpaque, BTPageOpaqueData::btpo_flags, BTPageState::btps_blkno, BTPageState::btps_buf, BTPageState::btps_level, BTPageState::btps_lowkey, BTPageState::btps_next, BTREE_METAPAGE, BTreeTupleGetNAtts, BTreeTupleSetDownLink(), fb(), IndexRelationGetNumberOfKeyAttributes, P_LEFTMOST, P_NONE, pfree(), and smgr_bulk_get_buf().
Referenced by _bt_load().
◆ btbuild()
| IndexBuildResult * btbuild | ( | Relation | heap, |
| Relation | index, | ||
| IndexInfo * | indexInfo | ||
| ) |
Definition at line 299 of file nbtsort.c.
300{
301 IndexBuildResult *result;
303 double reltuples;
304
305#ifdef BTREE_BUILD_STATS
307 ResetUsage();
308#endif /* BTREE_BUILD_STATS */
309
313 buildstate.heap = heap;
316 buildstate.indtuples = 0;
318
319 /*
320 * We expect to be called exactly once for any index relation. If that's
321 * not the case, big trouble's what we have.
322 */
326
328
329 /*
330 * Finish the build by (1) completing the sort of the spool file, (2)
331 * inserting the sorted tuples into btree pages and (3) building the upper
332 * levels. Finally, it may also be necessary to end use of parallelism.
333 */
340
342
343 result->heap_tuples = reltuples;
345
346#ifdef BTREE_BUILD_STATS
348 {
350 ResetUsage();
351 }
352#endif /* BTREE_BUILD_STATS */
353
354 return result;
355}
References _bt_end_parallel(), _bt_leafbuild(), _bt_spooldestroy(), _bt_spools_heapscan(), elog, ERROR, fb(), IndexBuildResult::heap_tuples, IndexInfo::ii_NullsNotDistinct, IndexInfo::ii_Unique, IndexBuildResult::index_tuples, log_btree_build_stats, palloc_object, RelationGetNumberOfBlocks, RelationGetRelationName, ResetUsage(), and ShowUsage().
Referenced by bthandler().
