Subject: Re: performance issue in remove_from_unowned_list()
To: Robert Haas <robertmhaas@gmail.com>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>,
 Postgres hackers <pgsql-hackers@lists.postgresql.org>
References: <20190310200923.GA4108@alvherre.pgsql>
 <7c599eff-8125-091c-61ef-90e02aa57486@2ndquadrant.com>
 <CA+TgmobHscKHVBLfZ0k43hXoq6vP8R5CB6i686jCZQtW7ASoaw@mail.gmail.com>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <319fd982-2d28-5879-a8bb-75d1067e8980@2ndquadrant.com>
Date: Wed, 13 Mar 2019 14:47:26 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.5.1
MIME-Version: 1.0
In-Reply-To: 
 <CA+TgmobHscKHVBLfZ0k43hXoq6vP8R5CB6i686jCZQtW7ASoaw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 3/13/19 1:12 PM, Robert Haas wrote:
> On Tue, Mar 12, 2019 at 6:54 PM Tomas Vondra
> <tomas.vondra@2ndquadrant.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