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

On 09/18/2015 10:47 AM, Tom Lane wrote:
> Jan Wieck <jan(at)wi3ck(dot)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