Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2ffcb0c

Browse files
committed
Eliminate O(N^2) behavior in parallel restore with many blobs.
With hundreds of thousands of TOC entries, the repeated searches inreduce_dependencies() become the dominant cost. Get rid of that searchingby constructing reverse-dependency lists, which we can do in O(N) timeduring the fix_dependencies() preprocessing. I chose to store the reversedependencies as DumpId arrays for consistency with the forward-dependencyrepresentation, and keep the previously-transient tocsByDumpId[] arrayaround to locate actual TOC entry structs quickly from dump IDs.While this fixes the slow case reported by Vlad Arkhipov, there is stilla potential for O(N^2) behavior with sufficiently many tables:fix_dependencies itself, as well as mark_create_done andinhibit_data_for_failed_table, are doing repeated searches to deal withtable-to-table-data dependencies. Possibly this work could be extendedto deal with that, although the latter two functions are also used innon-parallel restore where we currently don't run fix_dependencies.Another TODO is that we fail to parallelize restore of multiple blobsat all. This appears to require changes in the archive format to fix.Back-patch to 9.0 where the problem was reported. 8.4 has potential issuesas well; but since it doesn't create a separate TOC entry for each blob,it's at much less risk of having enough TOC entries to cause real problems.
1 parent87eadd7 commit2ffcb0c

File tree

2 files changed

+76
-42
lines changed

2 files changed

+76
-42
lines changed

‎src/bin/pg_dump/pg_backup_archiver.c

Lines changed: 74 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -79,6 +79,10 @@ const char *progname;
7979

8080
staticconstchar*modulename=gettext_noop("archiver");
8181

82+
/* index array created by fix_dependencies -- only used in parallel restore */
83+
staticTocEntry**tocsByDumpId;/* index by dumpId - 1 */
84+
staticDumpIdmaxDumpId;/* length of above array */
85+
8286

8387
staticArchiveHandle*_allocAH(constchar*FileSpec,constArchiveFormatfmt,
8488
constintcompression,ArchiveModemode);
@@ -134,9 +138,7 @@ static void fix_dependencies(ArchiveHandle *AH);
134138
staticboolhas_lock_conflicts(TocEntry*te1,TocEntry*te2);
135139
staticvoidrepoint_table_dependencies(ArchiveHandle*AH,
136140
DumpIdtableId,DumpIdtableDataId);
137-
staticvoididentify_locking_dependencies(TocEntry*te,
138-
TocEntry**tocsByDumpId,
139-
DumpIdmaxDumpId);
141+
staticvoididentify_locking_dependencies(TocEntry*te);
140142
staticvoidreduce_dependencies(ArchiveHandle*AH,TocEntry*te,
141143
TocEntry*ready_list);
142144
staticvoidmark_create_done(ArchiveHandle*AH,TocEntry*te);
@@ -3737,7 +3739,12 @@ mark_work_done(ArchiveHandle *AH, TocEntry *ready_list,
37373739
/*
37383740
* Process the dependency information into a form useful for parallel restore.
37393741
*
3740-
* We set up depCount fields that are the number of as-yet-unprocessed
3742+
* This function takes care of fixing up some missing or badly designed
3743+
* dependencies, and then prepares subsidiary data structures that will be
3744+
* used in the main parallel-restore logic, including:
3745+
* 1. We build the tocsByDumpId[] index array.
3746+
* 2. We build the revDeps[] arrays of incoming dependency dumpIds.
3747+
* 3. We set up depCount fields that are the number of as-yet-unprocessed
37413748
* dependencies for each TOC entry.
37423749
*
37433750
* We also identify locking dependencies so that we can avoid trying to
@@ -3746,29 +3753,29 @@ mark_work_done(ArchiveHandle *AH, TocEntry *ready_list,
37463753
staticvoid
37473754
fix_dependencies(ArchiveHandle*AH)
37483755
{
3749-
TocEntry**tocsByDumpId;
37503756
TocEntry*te;
3751-
DumpIdmaxDumpId;
37523757
inti;
37533758

37543759
/*
3755-
*For some of the steps here, itis convenient to have an array that
3756-
*indexes the TOC entries by dumpID, rather than searching the TOC list
3757-
*repeatedly.Entries for dumpIDs not present in the TOC will be NULL.
3760+
*Itis convenient to have an array that indexes the TOC entries by dump
3761+
* ID, rather than searching the TOC list repeatedly. Entries for dump
3762+
* IDs not present in the TOC will be NULL.
37583763
*
37593764
* NOTE: because maxDumpId is just the highest dump ID defined in the
37603765
* archive, there might be dependencies for IDs > maxDumpId. All uses of
37613766
* this array must guard against out-of-range dependency numbers.
37623767
*
3763-
* Also, initialize the depCount fields, and make sure all the TOC items
3764-
* are marked as not being in any parallel-processing list.
3768+
* Also, initialize the depCount/revDeps/nRevDeps fields, and make sure
3769+
*the TOC itemsare marked as not being in any parallel-processing list.
37653770
*/
37663771
maxDumpId=AH->maxDumpId;
37673772
tocsByDumpId= (TocEntry**)calloc(maxDumpId,sizeof(TocEntry*));
37683773
for (te=AH->toc->next;te!=AH->toc;te=te->next)
37693774
{
37703775
tocsByDumpId[te->dumpId-1]=te;
37713776
te->depCount=te->nDeps;
3777+
te->revDeps=NULL;
3778+
te->nRevDeps=0;
37723779
te->par_prev=NULL;
37733780
te->par_next=NULL;
37743781
}
@@ -3786,6 +3793,9 @@ fix_dependencies(ArchiveHandle *AH)
37863793
* TABLE, if possible.However, if the dependency isn't in the archive
37873794
* then just assume it was a TABLE; this is to cover cases where the table
37883795
* was suppressed but we have the data and some dependent post-data items.
3796+
*
3797+
* XXX this is O(N^2) if there are a lot of tables. We ought to fix
3798+
* pg_dump to produce correctly-linked dependencies in the first place.
37893799
*/
37903800
for (te=AH->toc->next;te!=AH->toc;te=te->next)
37913801
{
@@ -3832,31 +3842,67 @@ fix_dependencies(ArchiveHandle *AH)
38323842
}
38333843

38343844
/*
3835-
* It is possible that the dependencies list items that are not in the
3836-
* archive at all.Subtract such items from the depCounts.
3845+
* At this point we start to build the revDeps reverse-dependency arrays,
3846+
* so all changes of dependencies must be complete.
3847+
*/
3848+
3849+
/*
3850+
* Count the incoming dependencies for each item. Also, it is possible
3851+
* that the dependencies list items that are not in the archive at
3852+
* all. Subtract such items from the depCounts.
38373853
*/
38383854
for (te=AH->toc->next;te!=AH->toc;te=te->next)
38393855
{
38403856
for (i=0;i<te->nDeps;i++)
38413857
{
38423858
DumpIddepid=te->dependencies[i];
38433859

3844-
if (depid>maxDumpId||tocsByDumpId[depid-1]==NULL)
3860+
if (depid <=maxDumpId&&tocsByDumpId[depid-1]!=NULL)
3861+
tocsByDumpId[depid-1]->nRevDeps++;
3862+
else
38453863
te->depCount--;
38463864
}
38473865
}
38483866

3867+
/*
3868+
* Allocate space for revDeps[] arrays, and reset nRevDeps so we can
3869+
* use it as a counter below.
3870+
*/
3871+
for (te=AH->toc->next;te!=AH->toc;te=te->next)
3872+
{
3873+
if (te->nRevDeps>0)
3874+
te->revDeps= (DumpId*)malloc(te->nRevDeps*sizeof(DumpId));
3875+
te->nRevDeps=0;
3876+
}
3877+
3878+
/*
3879+
* Build the revDeps[] arrays of incoming-dependency dumpIds. This
3880+
* had better agree with the loops above.
3881+
*/
3882+
for (te=AH->toc->next;te!=AH->toc;te=te->next)
3883+
{
3884+
for (i=0;i<te->nDeps;i++)
3885+
{
3886+
DumpIddepid=te->dependencies[i];
3887+
3888+
if (depid <=maxDumpId&&tocsByDumpId[depid-1]!=NULL)
3889+
{
3890+
TocEntry*otherte=tocsByDumpId[depid-1];
3891+
3892+
otherte->revDeps[otherte->nRevDeps++]=te->dumpId;
3893+
}
3894+
}
3895+
}
3896+
38493897
/*
38503898
* Lastly, work out the locking dependencies.
38513899
*/
38523900
for (te=AH->toc->next;te!=AH->toc;te=te->next)
38533901
{
38543902
te->lockDeps=NULL;
38553903
te->nLockDeps=0;
3856-
identify_locking_dependencies(te,tocsByDumpId,maxDumpId);
3904+
identify_locking_dependencies(te);
38573905
}
3858-
3859-
free(tocsByDumpId);
38603906
}
38613907

38623908
/*
@@ -3890,13 +3936,9 @@ repoint_table_dependencies(ArchiveHandle *AH,
38903936
* Identify which objects we'll need exclusive lock on in order to restore
38913937
* the given TOC entry (*other* than the one identified by the TOC entry
38923938
* itself). Record their dump IDs in the entry's lockDeps[] array.
3893-
* tocsByDumpId[] is a convenience array (of size maxDumpId) to avoid
3894-
* searching the TOC for each dependency.
38953939
*/
38963940
staticvoid
3897-
identify_locking_dependencies(TocEntry*te,
3898-
TocEntry**tocsByDumpId,
3899-
DumpIdmaxDumpId)
3941+
identify_locking_dependencies(TocEntry*te)
39003942
{
39013943
DumpId*lockids;
39023944
intnlockids;
@@ -3950,31 +3992,21 @@ identify_locking_dependencies(TocEntry *te,
39503992
staticvoid
39513993
reduce_dependencies(ArchiveHandle*AH,TocEntry*te,TocEntry*ready_list)
39523994
{
3953-
DumpIdtarget=te->dumpId;
39543995
inti;
39553996

3956-
ahlog(AH,2,"reducing dependencies for %d\n",target);
3997+
ahlog(AH,2,"reducing dependencies for %d\n",te->dumpId);
39573998

3958-
/*
3959-
* We must examine all entries, not only the ones after the target item,
3960-
* because if the user used a -L switch then the original dependency-
3961-
* respecting order has been destroyed by SortTocFromFile.
3962-
*/
3963-
for (te=AH->toc->next;te!=AH->toc;te=te->next)
3999+
for (i=0;i<te->nRevDeps;i++)
39644000
{
3965-
for (i=0;i<te->nDeps;i++)
4001+
TocEntry*otherte=tocsByDumpId[te->revDeps[i]-1];
4002+
4003+
otherte->depCount--;
4004+
if (otherte->depCount==0&&otherte->par_prev!=NULL)
39664005
{
3967-
if (te->dependencies[i]==target)
3968-
{
3969-
te->depCount--;
3970-
if (te->depCount==0&&te->par_prev!=NULL)
3971-
{
3972-
/* It must be in the pending list, so remove it ... */
3973-
par_list_remove(te);
3974-
/* ... and add to ready_list */
3975-
par_list_append(ready_list,te);
3976-
}
3977-
}
4006+
/* It must be in the pending list, so remove it ... */
4007+
par_list_remove(otherte);
4008+
/* ... and add to ready_list */
4009+
par_list_append(ready_list,otherte);
39784010
}
39794011
}
39804012
}

‎src/bin/pg_dump/pg_backup_archiver.h

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -321,6 +321,8 @@ typedef struct _tocEntry
321321
struct_tocEntry*par_next;/* these are NULL if not in either list */
322322
boolcreated;/* set for DATA member if TABLE was created */
323323
intdepCount;/* number of dependencies not yet restored */
324+
DumpId*revDeps;/* dumpIds of objects depending on this one */
325+
intnRevDeps;/* number of such dependencies */
324326
DumpId*lockDeps;/* dumpIds of objects this one needs lock on */
325327
intnLockDeps;/* number of such dependencies */
326328
}TocEntry;

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp