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

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?

regards, tom lane