Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references. - Mailing list pgsql-hackers

From Jan Wieck
Subject Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references.
Date
Msg-id 5605582E.1010209@wi3ck.info
Whole thread Raw
In response to Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references.  (Tom Lane <tgl@sss.pgh.pa.us>)
Responses Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references.  (Tom Lane <tgl@sss.pgh.pa.us>)
List pgsql-hackers
On 09/18/2015 10:47 AM, Tom Lane wrote:
> Jan Wieck <jan@wi3ck.info> writes:
>> Attached is a complete rework of the fix from scratch, based on Tom's
>> suggestion.
>
>> The code now maintains a double linked list as suggested, but only uses
>> it to mark all currently valid entries as invalid when hashvalue == 0.
>> If a specific entry is invalidated it performs a hash lookup for maximum
>> efficiency in that case.
>
> That does not work; you're ignoring the possibility of hashvalue
> collisions, and for that matter not considering that the hash value
> is not equal to the hash key.  I don't think your code is invalidating
> the right entry at all during a foreign key constraint update, and
> it certainly cannot do the right thing if there's a hash value collision.
>
> Attached is something closer to what I was envisioning; can you do
> performance testing on it?

Sorry for the delay.

Yes, that patch also has the desired performance for restoring a schema 
with hundreds of thousands of foreign key constraints.


Regards, Jan

-- 
Jan Wieck
Senior Software Engineer
http://slony.info



pgsql-hackers by date:

Previous
From: Teodor Sigaev
Date:
Subject: Re: WIP: Rework access method interface
Next
From: Tom Lane
Date:
Subject: Re: cluster_name and update_process_title documentation