Re: Bug #769: Slow vacuuming due to error in optimization

pgsql-bugs(at)postgresql(dot)org writes:
> I have found very long vacuuming times when vacuuming large tables in
> Postgres 7.2.1, running on i686 hardware under Redhat Linux 7.3.

How large is "large", and what FSM parameters are you using? Do you
know how many pages were getting passed into MultiRecordFreeSpace?

> To identify the source of the problem, I inserted some additional log
> statements into the source file backend/commands/vacuumlazy.c, and was
> able to track down the problem to the function that updates the free
> space map (i.e. the function lazy_update_fsm). This in turn calls the
> function MultiRecordFreeSpace() in storage/freespace/freespace.c.

The implementation of that function could stand to be improved, all
right; it's probably O(N^2) in the number of pages processed, if you
have a large enough FSM to let all the pages be stored.

> Looking further, I found a place where the
> comment and conditional logic did not seem to say the same thing, and
> hence looked suspicious.

No, they are the same. Perhaps it's more apparent if you apply De
Morgan's law to the condition:

if (avail >= fsmrel->threshold ||
page < minPage || page > maxPage)
fsm_record_free_space(fsmrel, page, avail);

becomes

if (! (avail < fsmrel->threshold &&
page >= minPage && page <= maxPage))
fsm_record_free_space(fsmrel, page, avail);

or even more verbosely,

if (avail < fsmrel->threshold &&
page >= minPage && page <= maxPage)
/* ignore page */;
else
fsm_record_free_space(fsmrel, page, avail);

which agrees with

> * One thing we can do is short-circuit the process entirely if a
> * page (a) has too little free space to be recorded, and (b) is
> * within the minPage..maxPage range --- then we deleted any old
> * entry above, and we aren't going to make a new one.

> Therefore I tried changing the logic to an AND, e.g.:

> if (avail >= fsmrel->threshold &&
> (page < minPage || page > maxPage))
> fsm_record_free_space(fsmrel, page, avail);

> This reduced my processing time in lazy_update_fsm() from about 2 minutes to nearly nothing, effectively solving my performance problem.

Unfortunately, you created a functionality problem: in this version
MultiRecordFreeSpace will fail to record any free space at all. As
the comment points out:

* ... in most cases, all the passed pages
* will in fact be in the minPage..maxPage range.

so the above condition always fails. Which indeed makes it quick,
but your tables will be bloating for lack of any FSM entries.

A more useful fix probably involves (a) requiring the input to be in
sorted order, and then (b) instead of using the general-purpose
subroutines, keeping track of where in the relation's free-space list
we are currently inserting, to save a fresh search for each insertion.
I had meant to do this but never got round to it.

regards, tom lane