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

Commit663fc32

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 parent9975c68 commit663fc32

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);
@@ -3743,7 +3745,12 @@ mark_work_done(ArchiveHandle *AH, TocEntry *ready_list,
37433745
/*
37443746
* Process the dependency information into a form useful for parallel restore.
37453747
*
3746-
* We set up depCount fields that are the number of as-yet-unprocessed
3748+
* This function takes care of fixing up some missing or badly designed
3749+
* dependencies, and then prepares subsidiary data structures that will be
3750+
* used in the main parallel-restore logic, including:
3751+
* 1. We build the tocsByDumpId[] index array.
3752+
* 2. We build the revDeps[] arrays of incoming dependency dumpIds.
3753+
* 3. We set up depCount fields that are the number of as-yet-unprocessed
37473754
* dependencies for each TOC entry.
37483755
*
37493756
* We also identify locking dependencies so that we can avoid trying to
@@ -3752,29 +3759,29 @@ mark_work_done(ArchiveHandle *AH, TocEntry *ready_list,
37523759
staticvoid
37533760
fix_dependencies(ArchiveHandle*AH)
37543761
{
3755-
TocEntry**tocsByDumpId;
37563762
TocEntry*te;
3757-
DumpIdmaxDumpId;
37583763
inti;
37593764

37603765
/*
3761-
*For some of the steps here, itis convenient to have an array that
3762-
*indexes the TOC entries by dumpID, rather than searching the TOC list
3763-
*repeatedly.Entries for dumpIDs not present in the TOC will be NULL.
3766+
*Itis convenient to have an array that indexes the TOC entries by dump
3767+
* ID, rather than searching the TOC list repeatedly. Entries for dump
3768+
* IDs not present in the TOC will be NULL.
37643769
*
37653770
* NOTE: because maxDumpId is just the highest dump ID defined in the
37663771
* archive, there might be dependencies for IDs > maxDumpId. All uses of
37673772
* this array must guard against out-of-range dependency numbers.
37683773
*
3769-
* Also, initialize the depCount fields, and make sure all the TOC items
3770-
* are marked as not being in any parallel-processing list.
3774+
* Also, initialize the depCount/revDeps/nRevDeps fields, and make sure
3775+
*the TOC itemsare marked as not being in any parallel-processing list.
37713776
*/
37723777
maxDumpId=AH->maxDumpId;
37733778
tocsByDumpId= (TocEntry**)calloc(maxDumpId,sizeof(TocEntry*));
37743779
for (te=AH->toc->next;te!=AH->toc;te=te->next)
37753780
{
37763781
tocsByDumpId[te->dumpId-1]=te;
37773782
te->depCount=te->nDeps;
3783+
te->revDeps=NULL;
3784+
te->nRevDeps=0;
37783785
te->par_prev=NULL;
37793786
te->par_next=NULL;
37803787
}
@@ -3792,6 +3799,9 @@ fix_dependencies(ArchiveHandle *AH)
37923799
* TABLE, if possible.However, if the dependency isn't in the archive
37933800
* then just assume it was a TABLE; this is to cover cases where the table
37943801
* was suppressed but we have the data and some dependent post-data items.
3802+
*
3803+
* XXX this is O(N^2) if there are a lot of tables. We ought to fix
3804+
* pg_dump to produce correctly-linked dependencies in the first place.
37953805
*/
37963806
for (te=AH->toc->next;te!=AH->toc;te=te->next)
37973807
{
@@ -3838,31 +3848,67 @@ fix_dependencies(ArchiveHandle *AH)
38383848
}
38393849

38403850
/*
3841-
* It is possible that the dependencies list items that are not in the
3842-
* archive at all.Subtract such items from the depCounts.
3851+
* At this point we start to build the revDeps reverse-dependency arrays,
3852+
* so all changes of dependencies must be complete.
3853+
*/
3854+
3855+
/*
3856+
* Count the incoming dependencies for each item. Also, it is possible
3857+
* that the dependencies list items that are not in the archive at
3858+
* all. Subtract such items from the depCounts.
38433859
*/
38443860
for (te=AH->toc->next;te!=AH->toc;te=te->next)
38453861
{
38463862
for (i=0;i<te->nDeps;i++)
38473863
{
38483864
DumpIddepid=te->dependencies[i];
38493865

3850-
if (depid>maxDumpId||tocsByDumpId[depid-1]==NULL)
3866+
if (depid <=maxDumpId&&tocsByDumpId[depid-1]!=NULL)
3867+
tocsByDumpId[depid-1]->nRevDeps++;
3868+
else
38513869
te->depCount--;
38523870
}
38533871
}
38543872

3873+
/*
3874+
* Allocate space for revDeps[] arrays, and reset nRevDeps so we can
3875+
* use it as a counter below.
3876+
*/
3877+
for (te=AH->toc->next;te!=AH->toc;te=te->next)
3878+
{
3879+
if (te->nRevDeps>0)
3880+
te->revDeps= (DumpId*)malloc(te->nRevDeps*sizeof(DumpId));
3881+
te->nRevDeps=0;
3882+
}
3883+
3884+
/*
3885+
* Build the revDeps[] arrays of incoming-dependency dumpIds. This
3886+
* had better agree with the loops above.
3887+
*/
3888+
for (te=AH->toc->next;te!=AH->toc;te=te->next)
3889+
{
3890+
for (i=0;i<te->nDeps;i++)
3891+
{
3892+
DumpIddepid=te->dependencies[i];
3893+
3894+
if (depid <=maxDumpId&&tocsByDumpId[depid-1]!=NULL)
3895+
{
3896+
TocEntry*otherte=tocsByDumpId[depid-1];
3897+
3898+
otherte->revDeps[otherte->nRevDeps++]=te->dumpId;
3899+
}
3900+
}
3901+
}
3902+
38553903
/*
38563904
* Lastly, work out the locking dependencies.
38573905
*/
38583906
for (te=AH->toc->next;te!=AH->toc;te=te->next)
38593907
{
38603908
te->lockDeps=NULL;
38613909
te->nLockDeps=0;
3862-
identify_locking_dependencies(te,tocsByDumpId,maxDumpId);
3910+
identify_locking_dependencies(te);
38633911
}
3864-
3865-
free(tocsByDumpId);
38663912
}
38673913

38683914
/*
@@ -3896,13 +3942,9 @@ repoint_table_dependencies(ArchiveHandle *AH,
38963942
* Identify which objects we'll need exclusive lock on in order to restore
38973943
* the given TOC entry (*other* than the one identified by the TOC entry
38983944
* itself). Record their dump IDs in the entry's lockDeps[] array.
3899-
* tocsByDumpId[] is a convenience array (of size maxDumpId) to avoid
3900-
* searching the TOC for each dependency.
39013945
*/
39023946
staticvoid
3903-
identify_locking_dependencies(TocEntry*te,
3904-
TocEntry**tocsByDumpId,
3905-
DumpIdmaxDumpId)
3947+
identify_locking_dependencies(TocEntry*te)
39063948
{
39073949
DumpId*lockids;
39083950
intnlockids;
@@ -3956,31 +3998,21 @@ identify_locking_dependencies(TocEntry *te,
39563998
staticvoid
39573999
reduce_dependencies(ArchiveHandle*AH,TocEntry*te,TocEntry*ready_list)
39584000
{
3959-
DumpIdtarget=te->dumpId;
39604001
inti;
39614002

3962-
ahlog(AH,2,"reducing dependencies for %d\n",target);
4003+
ahlog(AH,2,"reducing dependencies for %d\n",te->dumpId);
39634004

3964-
/*
3965-
* We must examine all entries, not only the ones after the target item,
3966-
* because if the user used a -L switch then the original dependency-
3967-
* respecting order has been destroyed by SortTocFromFile.
3968-
*/
3969-
for (te=AH->toc->next;te!=AH->toc;te=te->next)
4005+
for (i=0;i<te->nRevDeps;i++)
39704006
{
3971-
for (i=0;i<te->nDeps;i++)
4007+
TocEntry*otherte=tocsByDumpId[te->revDeps[i]-1];
4008+
4009+
otherte->depCount--;
4010+
if (otherte->depCount==0&&otherte->par_prev!=NULL)
39724011
{
3973-
if (te->dependencies[i]==target)
3974-
{
3975-
te->depCount--;
3976-
if (te->depCount==0&&te->par_prev!=NULL)
3977-
{
3978-
/* It must be in the pending list, so remove it ... */
3979-
par_list_remove(te);
3980-
/* ... and add to ready_list */
3981-
par_list_append(ready_list,te);
3982-
}
3983-
}
4012+
/* It must be in the pending list, so remove it ... */
4013+
par_list_remove(otherte);
4014+
/* ... and add to ready_list */
4015+
par_list_append(ready_list,otherte);
39844016
}
39854017
}
39864018
}

‎src/bin/pg_dump/pg_backup_archiver.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -326,6 +326,8 @@ typedef struct _tocEntry
326326
struct_tocEntry*par_next;/* these are NULL if not in either list */
327327
boolcreated;/* set for DATA member if TABLE was created */
328328
intdepCount;/* number of dependencies not yet restored */
329+
DumpId*revDeps;/* dumpIds of objects depending on this one */
330+
intnRevDeps;/* number of such dependencies */
329331
DumpId*lockDeps;/* dumpIds of objects this one needs lock on */
330332
intnLockDeps;/* number of such dependencies */
331333
}TocEntry;

0 commit comments

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