Matthew T. O'Connor wrote:
> Phil Endecott wrote:
>> > Could it be that there is some code in autovacuum that is O(n^2) in
>> > the number of tables?
>>
>> Browsing the code using webcvs, I have found this:
>>
>> for (j = 0; j < PQntuples(res); j++)
>> {
>> tbl_elem = DLGetHead(dbs->table_list);
>> while (tbl_elem != NULL)
>> {
>> Have I correctly understood what is going on here?
> Indeed you have. I have head a few similar reports but perhaps none as
> bad as yours. One person put a small sleep value so that it doesn't
> spin so tight. You could also just up the sleep delay so that it
> doesn't do this work quite so often. No other quick suggestions.
I do wonder why autovacuum is keeping its table list in memory rather
than in the database.
But given that it is keeping it in memory, I think the real fix is to
sort that list (or keep it ordered when building or updating it). It is
trivial to also get the query results ordered, and they can then be
compared in O(n) time.
I notice various other places where there seem to be nested loops, e.g.
in the update_table_list function. I'm not sure if they can be fixed by
similar means.
--Phil.