Re: Speedup of relation deletes during recovery

On Sat, Jun 16, 2018 at 3:28 AM, Andres Freund <andres@anarazel.de> wrote:
> Hi,
>
> On 2018-06-15 10:45:04 -0700, Andres Freund wrote:
>> > +
>> > +   srels = palloc(sizeof(SMgrRelation) * ndelrels);
>> >     for (i = 0; i < ndelrels; i++)
>> > -   {
>> > -           SMgrRelation srel = smgropen(delrels[i], InvalidBackendId);
>> > +           srels[i] = smgropen(delrels[i], InvalidBackendId);
>> >
>> > -           smgrdounlink(srel, false);
>> > -           smgrclose(srel);
>> > -   }
>> > +   smgrdounlinkall(srels, ndelrels, false);
>> > +
>> > +   for (i = 0; i < ndelrels; i++)
>> > +           smgrclose(srels[i]);
>> > +   pfree(srels);
>
> Hm. This will probably cause another complexity issue. If we just
> smgropen() the relation will be unowned. Which means smgrclose() will
> call remove_from_unowned_list(), which is O(open-relations). Which means
> this change afaict creates a new O(ndrels^2) behaviour?
>
> It seems like the easiest fix for that would be to have a local
> SMgrRelationData in that loop, that we assign the relations to?  That's
> a bit hacky, but afaict should work?

The easier (but tricky) fix for that is to call smgrclose() for
each SMgrRelation in the reverse order. That is, we should do

   for (i = ndelrels - 1; i >= 0; i--)
           smgrclose(srels[i]);

instead of

   for (i = 0; i < ndelrels; i++)
           smgrclose(srels[i]);

Since add_to_unowned_list() always adds the entry into the head of
the list, each SMgrRelation entry is added into the "unowned" list in
descending order of its identifier, i.e., SMgrRelation entry with larger
identifier should be placed ahead of one with smaller identifier.
So if we calls remove_from_unowed_list() in descending order of
SMgrRelation entry's identifier, the performance of
remove_from_unowned_list()'s search should O(1). IOW, we can
immediately find the SMgrRelation entry to remove, at the head of
the list.

Regards,

-- 
Fujii Masao