Skip to content

Commit b2735fc

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 parent de96cd5 commit b2735fc

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
int nPages = fraged_pages->num_pages;
27332734
int i;
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+
* the free space map!
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
bool fs_is_heap; /* are we using heap organization? */
8989
int num_free_pages; /* current # of entries */
90-
int max_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+
int max_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
static bool dummy_tid_reaped(ItemPointer itemptr, void *state);
120119
static void lazy_update_fsm(Relation onerel, LVRelStats *vacrelstats);
121120
static int vac_cmp_itemptr(const void *left, const void *right);
121+
static int vac_cmp_page_spaces(const void *left, const void *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
BlockNumber old_rel_pages = vacrelstats->rel_pages;
664663
BlockNumber new_rel_pages;
665-
BlockNumber *pages;
666-
Size *spaceavail;
664+
PageFreeSpaceInfo *pageSpaces;
667665
int n;
668666
int i,
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
BlockNumber page,
947943
Size avail)
948944
{
949-
BlockNumber *pages;
950-
Size *spaceavail;
945+
PageFreeSpaceInfo *pageSpaces;
951946
int n;
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-
BlockNumber R = pages[l];
995-
Size K = spaceavail[l];
988+
BlockNumber R = pageSpaces[l].blkno;
989+
Size K = pageSpaces[l].avail;
996990
int i; /* 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
static void
10861078
lazy_update_fsm(Relation onerel, LVRelStats *vacrelstats)
10871079
{
1080+
PageFreeSpaceInfo *pageSpaces = vacrelstats->free_pages;
1081+
int nPages = 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
return 0;
11281121
}
1122+
1123+
static int
1124+
vac_cmp_page_spaces(const void *left, const void *right)
1125+
{
1126+
PageFreeSpaceInfo *linfo = (PageFreeSpaceInfo *) left;
1127+
PageFreeSpaceInfo *rinfo = (PageFreeSpaceInfo *) right;
1128+
1129+
if (linfo->blkno < rinfo->blkno)
1130+
return -1;
1131+
else if (linfo->blkno > rinfo->blkno)
1132+
return 1;
1133+
return 0;
1134+
}

0 commit comments

Comments
 (0)