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

Commitb2735fc

Browse files
committed
Performance improvement for MultiRecordFreeSpace on large relations ---
avoid O(N^2) behavior. Problem noted and fixed by Stephen Marshall <smarshall@wsicorp.com>,with some help from Tom Lane.
1 parentde96cd5 commitb2735fc

File tree

5 files changed

+181
-147
lines changed

5 files changed

+181
-147
lines changed

‎src/backend/commands/vacuum.c

Lines changed: 19 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@
1313
*
1414
*
1515
* IDENTIFICATION
16-
* $Header: /cvsroot/pgsql/src/backend/commands/vacuum.c,v 1.237 2002/09/04 20:31:16 momjian Exp $
16+
* $Header: /cvsroot/pgsql/src/backend/commands/vacuum.c,v 1.238 2002/09/20 19:56:01 tgl Exp $
1717
*
1818
*-------------------------------------------------------------------------
1919
*/
@@ -1321,9 +1321,10 @@ scan_heap(VRelStats *vacrelstats, Relation onerel,
13211321
pfree(vtlinks);
13221322
}
13231323

1324-
elog(elevel,"Pages %u: Changed %u, reaped %u, Empty %u, New %u; \
1325-
Tup %.0f: Vac %.0f, Keep/VTL %.0f/%u, UnUsed %.0f, MinLen %lu, MaxLen %lu; \
1326-
Re-using: Free/Avail. Space %.0f/%.0f; EndEmpty/Avail. Pages %u/%u.\n\t%s",
1324+
elog(elevel,"Pages %u: Changed %u, reaped %u, Empty %u, New %u; "
1325+
"Tup %.0f: Vac %.0f, Keep/VTL %.0f/%u, UnUsed %.0f, MinLen %lu, "
1326+
"MaxLen %lu; Re-using: Free/Avail. Space %.0f/%.0f; "
1327+
"EndEmpty/Avail. Pages %u/%u.\n\t%s",
13271328
nblocks,changed_pages,vacuum_pages->num_pages,empty_pages,
13281329
new_pages,num_tuples,tups_vacuumed,
13291330
nkeep,vacrelstats->num_vtlinks,
@@ -2597,8 +2598,8 @@ scan_index(Relation indrel, double num_tuples)
25972598
{
25982599
if (stats->num_index_tuples>num_tuples||
25992600
!vac_is_partial_index(indrel))
2600-
elog(WARNING,"Index %s: NUMBER OF INDEX' TUPLES (%.0f) IS NOT THE SAME AS HEAP' (%.0f).\
2601-
\n\tRecreate the index.",
2601+
elog(WARNING,"Index %s: NUMBER OF INDEX' TUPLES (%.0f) IS NOT THE SAME AS HEAP' (%.0f)."
2602+
"\n\tRecreate the index.",
26022603
RelationGetRelationName(indrel),
26032604
stats->num_index_tuples,num_tuples);
26042605
}
@@ -2651,8 +2652,8 @@ vacuum_index(VacPageList vacpagelist, Relation indrel,
26512652
{
26522653
if (stats->num_index_tuples>num_tuples+keep_tuples||
26532654
!vac_is_partial_index(indrel))
2654-
elog(WARNING,"Index %s: NUMBER OF INDEX' TUPLES (%.0f) IS NOT THE SAME AS HEAP' (%.0f).\
2655-
\n\tRecreate the index.",
2655+
elog(WARNING,"Index %s: NUMBER OF INDEX' TUPLES (%.0f) IS NOT THE SAME AS HEAP' (%.0f)."
2656+
"\n\tRecreate the index.",
26562657
RelationGetRelationName(indrel),
26572658
stats->num_index_tuples,num_tuples);
26582659
}
@@ -2731,35 +2732,32 @@ vac_update_fsm(Relation onerel, VacPageList fraged_pages,
27312732
{
27322733
intnPages=fraged_pages->num_pages;
27332734
inti;
2734-
BlockNumber*pages;
2735-
Size*spaceAvail;
2735+
PageFreeSpaceInfo*pageSpaces;
27362736

27372737
/* +1 to avoid palloc(0) */
2738-
pages= (BlockNumber*)palloc((nPages+1)*sizeof(BlockNumber));
2739-
spaceAvail= (Size*)palloc((nPages+1)*sizeof(Size));
2738+
pageSpaces= (PageFreeSpaceInfo*)
2739+
palloc((nPages+1)*sizeof(PageFreeSpaceInfo));
27402740

27412741
for (i=0;i<nPages;i++)
27422742
{
2743-
pages[i]=fraged_pages->pagedesc[i]->blkno;
2744-
spaceAvail[i]=fraged_pages->pagedesc[i]->free;
2743+
pageSpaces[i].blkno=fraged_pages->pagedesc[i]->blkno;
2744+
pageSpaces[i].avail=fraged_pages->pagedesc[i]->free;
27452745

27462746
/*
27472747
* fraged_pages may contain entries for pages that we later
27482748
* decided to truncate from the relation; don't enter them into
2749-
* the map!
2749+
* thefree spacemap!
27502750
*/
2751-
if (pages[i] >=rel_pages)
2751+
if (pageSpaces[i].blkno >=rel_pages)
27522752
{
27532753
nPages=i;
27542754
break;
27552755
}
27562756
}
27572757

2758-
MultiRecordFreeSpace(&onerel->rd_node,
2759-
0,MaxBlockNumber,
2760-
nPages,pages,spaceAvail);
2761-
pfree(pages);
2762-
pfree(spaceAvail);
2758+
MultiRecordFreeSpace(&onerel->rd_node,0,nPages,pageSpaces);
2759+
2760+
pfree(pageSpaces);
27632761
}
27642762

27652763
/* Copy a VacPage structure */

‎src/backend/commands/vacuumlazy.c

Lines changed: 53 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@
3131
*
3232
*
3333
* IDENTIFICATION
34-
* $Header: /cvsroot/pgsql/src/backend/commands/vacuumlazy.c,v 1.19 2002/09/04 20:31:17 momjian Exp $
34+
* $Header: /cvsroot/pgsql/src/backend/commands/vacuumlazy.c,v 1.20 2002/09/20 19:56:01 tgl Exp $
3535
*
3636
*-------------------------------------------------------------------------
3737
*/
@@ -87,9 +87,8 @@ typedef struct LVRelStats
8787
/* We use a simple array until it fills up, then convert to heap */
8888
boolfs_is_heap;/* are we using heap organization? */
8989
intnum_free_pages;/* current # of entries */
90-
intmax_free_pages;/* # slots allocated in arrays */
91-
BlockNumber*free_pages;/* array or heap of block numbers */
92-
Size*free_spaceavail;/* array or heap of available space */
90+
intmax_free_pages;/* # slots allocated in array */
91+
PageFreeSpaceInfo*free_pages;/* array or heap of blkno/avail */
9392
}LVRelStats;
9493

9594

@@ -119,6 +118,7 @@ static bool lazy_tid_reaped(ItemPointer itemptr, void *state);
119118
staticbooldummy_tid_reaped(ItemPointeritemptr,void*state);
120119
staticvoidlazy_update_fsm(Relationonerel,LVRelStats*vacrelstats);
121120
staticintvac_cmp_itemptr(constvoid*left,constvoid*right);
121+
staticintvac_cmp_page_spaces(constvoid*left,constvoid*right);
122122

123123

124124
/*
@@ -432,8 +432,7 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
432432
lazy_scan_index(Irel[i],vacrelstats);
433433
}
434434

435-
elog(elevel,"Pages %u: Changed %u, Empty %u; \
436-
Tup %.0f: Vac %.0f, Keep %.0f, UnUsed %.0f.\n\tTotal %s",
435+
elog(elevel,"Pages %u: Changed %u, Empty %u; Tup %.0f: Vac %.0f, Keep %.0f, UnUsed %.0f.\n\tTotal %s",
437436
nblocks,changed_pages,empty_pages,
438437
num_tuples,tups_vacuumed,nkeep,nunused,
439438
vac_show_rusage(&ru0));
@@ -662,8 +661,7 @@ lazy_truncate_heap(Relation onerel, LVRelStats *vacrelstats)
662661
{
663662
BlockNumberold_rel_pages=vacrelstats->rel_pages;
664663
BlockNumbernew_rel_pages;
665-
BlockNumber*pages;
666-
Size*spaceavail;
664+
PageFreeSpaceInfo*pageSpaces;
667665
intn;
668666
inti,
669667
j;
@@ -736,20 +734,20 @@ lazy_truncate_heap(Relation onerel, LVRelStats *vacrelstats)
736734
* Drop free-space info for removed blocks; these must not get entered
737735
* into the FSM!
738736
*/
739-
pages=vacrelstats->free_pages;
740-
spaceavail=vacrelstats->free_spaceavail;
737+
pageSpaces=vacrelstats->free_pages;
741738
n=vacrelstats->num_free_pages;
742739
j=0;
743740
for (i=0;i<n;i++)
744741
{
745-
if (pages[i]<new_rel_pages)
742+
if (pageSpaces[i].blkno<new_rel_pages)
746743
{
747-
pages[j]=pages[i];
748-
spaceavail[j]=spaceavail[i];
744+
pageSpaces[j]=pageSpaces[i];
749745
j++;
750746
}
751747
}
752748
vacrelstats->num_free_pages=j;
749+
/* We destroyed the heap ordering, so mark array unordered */
750+
vacrelstats->fs_is_heap= false;
753751

754752
/*
755753
* We keep the exclusive lock until commit (perhaps not necessary)?
@@ -913,10 +911,8 @@ lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks)
913911
vacrelstats->fs_is_heap= false;
914912
vacrelstats->num_free_pages=0;
915913
vacrelstats->max_free_pages=maxpages;
916-
vacrelstats->free_pages= (BlockNumber*)
917-
palloc(maxpages*sizeof(BlockNumber));
918-
vacrelstats->free_spaceavail= (Size*)
919-
palloc(maxpages*sizeof(Size));
914+
vacrelstats->free_pages= (PageFreeSpaceInfo*)
915+
palloc(maxpages*sizeof(PageFreeSpaceInfo));
920916
}
921917

922918
/*
@@ -946,32 +942,30 @@ lazy_record_free_space(LVRelStats *vacrelstats,
946942
BlockNumberpage,
947943
Sizeavail)
948944
{
949-
BlockNumber*pages;
950-
Size*spaceavail;
945+
PageFreeSpaceInfo*pageSpaces;
951946
intn;
952947

953948
/* Ignore pages with little free space */
954949
if (avail<PAGE_SPACE_THRESHOLD)
955950
return;
956951

957952
/* Copy pointers to local variables for notational simplicity */
958-
pages=vacrelstats->free_pages;
959-
spaceavail=vacrelstats->free_spaceavail;
953+
pageSpaces=vacrelstats->free_pages;
960954
n=vacrelstats->max_free_pages;
961955

962956
/* If we haven't filled the array yet, just keep adding entries */
963957
if (vacrelstats->num_free_pages<n)
964958
{
965-
pages[vacrelstats->num_free_pages]=page;
966-
spaceavail[vacrelstats->num_free_pages]=avail;
959+
pageSpaces[vacrelstats->num_free_pages].blkno=page;
960+
pageSpaces[vacrelstats->num_free_pages].avail=avail;
967961
vacrelstats->num_free_pages++;
968962
return;
969963
}
970964

971965
/*----------
972966
* The rest of this routine works with "heap" organization of the
973967
* free space arrays, wherein we maintain the heap property
974-
*spaceavail[(j-1) div 2] <=spaceavail[j] for 0 < j < n.
968+
*avail[(j-1) div 2] <=avail[j] for 0 < j < n.
975969
* In particular, the zero'th element always has the smallest available
976970
* space and can be discarded to make room for a new page with more space.
977971
* See Knuth's discussion of heap-based priority queues, sec 5.2.3;
@@ -991,8 +985,8 @@ lazy_record_free_space(LVRelStats *vacrelstats,
991985

992986
while (--l >=0)
993987
{
994-
BlockNumberR=pages[l];
995-
SizeK=spaceavail[l];
988+
BlockNumberR=pageSpaces[l].blkno;
989+
SizeK=pageSpaces[l].avail;
996990
inti;/* i is where the "hole" is */
997991

998992
i=l;
@@ -1002,23 +996,22 @@ lazy_record_free_space(LVRelStats *vacrelstats,
1002996

1003997
if (j >=n)
1004998
break;
1005-
if (j+1<n&&spaceavail[j]>spaceavail[j+1])
999+
if (j+1<n&&pageSpaces[j].avail>pageSpaces[j+1].avail)
10061000
j++;
1007-
if (K <=spaceavail[j])
1001+
if (K <=pageSpaces[j].avail)
10081002
break;
1009-
pages[i]=pages[j];
1010-
spaceavail[i]=spaceavail[j];
1003+
pageSpaces[i]=pageSpaces[j];
10111004
i=j;
10121005
}
1013-
pages[i]=R;
1014-
spaceavail[i]=K;
1006+
pageSpaces[i].blkno=R;
1007+
pageSpaces[i].avail=K;
10151008
}
10161009

10171010
vacrelstats->fs_is_heap= true;
10181011
}
10191012

10201013
/* If new page has more than zero'th entry, insert it into heap */
1021-
if (avail>spaceavail[0])
1014+
if (avail>pageSpaces[0].avail)
10221015
{
10231016
/*
10241017
* Notionally, we replace the zero'th entry with the new data, and
@@ -1034,16 +1027,15 @@ lazy_record_free_space(LVRelStats *vacrelstats,
10341027

10351028
if (j >=n)
10361029
break;
1037-
if (j+1<n&&spaceavail[j]>spaceavail[j+1])
1030+
if (j+1<n&&pageSpaces[j].avail>pageSpaces[j+1].avail)
10381031
j++;
1039-
if (avail <=spaceavail[j])
1032+
if (avail <=pageSpaces[j].avail)
10401033
break;
1041-
pages[i]=pages[j];
1042-
spaceavail[i]=spaceavail[j];
1034+
pageSpaces[i]=pageSpaces[j];
10431035
i=j;
10441036
}
1045-
pages[i]=page;
1046-
spaceavail[i]=avail;
1037+
pageSpaces[i].blkno=page;
1038+
pageSpaces[i].avail=avail;
10471039
}
10481040
}
10491041

@@ -1085,16 +1077,17 @@ dummy_tid_reaped(ItemPointer itemptr, void *state)
10851077
staticvoid
10861078
lazy_update_fsm(Relationonerel,LVRelStats*vacrelstats)
10871079
{
1080+
PageFreeSpaceInfo*pageSpaces=vacrelstats->free_pages;
1081+
intnPages=vacrelstats->num_free_pages;
1082+
10881083
/*
1089-
* Since MultiRecordFreeSpace doesn't currently impose any
1090-
* restrictions on the ordering of the input, we can just pass it the
1091-
* arrays as-is, whether they are in heap or linear order.
1084+
* Sort data into order, as required by MultiRecordFreeSpace.
10921085
*/
1093-
MultiRecordFreeSpace(&onerel->rd_node,
1094-
0,MaxBlockNumber,
1095-
vacrelstats->num_free_pages,
1096-
vacrelstats->free_pages,
1097-
vacrelstats->free_spaceavail);
1086+
if (nPages>1)
1087+
qsort(pageSpaces,nPages,sizeof(PageFreeSpaceInfo),
1088+
vac_cmp_page_spaces);
1089+
1090+
MultiRecordFreeSpace(&onerel->rd_node,0,nPages,pageSpaces);
10981091
}
10991092

11001093
/*
@@ -1126,3 +1119,16 @@ vac_cmp_itemptr(const void *left, const void *right)
11261119

11271120
return0;
11281121
}
1122+
1123+
staticint
1124+
vac_cmp_page_spaces(constvoid*left,constvoid*right)
1125+
{
1126+
PageFreeSpaceInfo*linfo= (PageFreeSpaceInfo*)left;
1127+
PageFreeSpaceInfo*rinfo= (PageFreeSpaceInfo*)right;
1128+
1129+
if (linfo->blkno<rinfo->blkno)
1130+
return-1;
1131+
elseif (linfo->blkno>rinfo->blkno)
1132+
return1;
1133+
return0;
1134+
}

0 commit comments

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