Re: performance issue in remove_from_unowned_list()

On 3/13/19 1:12 PM, Robert Haas wrote:
> On Tue, Mar 12, 2019 at 6:54 PM Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>> Attached is a patch adopting the dlist approach - it seems to be working
>> quite fine, and is a bit cleaner than just slapping another pointer into
>> the SMgrRelationData struct. So I'd say this is the way to go.
>
> What about using a data structure that supports O(1) lookups for any element?
>
> The current efforts all seem to revolve around correctly guessing from
> which end of the list we are likely to delete stuff, but your research
> suggests that we don't always make such guesses particularly well.
> And it seems unnecessary.
>

Isn't the the doubly-linked list is doing exactly that?

AFAICS we already maintain a hash table of the smgr relations, and we
look them up in this table. We don't need to look them up in the list of
unowned relations - the whole problem is that with the current
single-linked list, we need to iterate the list anyway to update pointer
in the preceding entry.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services