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

On 09/15/2015 12:02 PM, Jan Wieck wrote:
> On 09/15/2015 11:54 AM, Tom Lane wrote:
>> Jan Wieck <jan@wi3ck.info> writes:
>>> Would it be appropriate to use (Un)RegisterXactCallback() in case of
>>> detecting excessive sequential scanning of that cache and remove all
>>> invalid entries from it at that time?
>
>> Another idea is that it's not the size of the cache that's the problem,
>> it's the cost of finding the entries that need to be invalidated.
>> So we could also consider adding list links that chain only the entries
>> that are currently marked valid.  If the list gets too long, we could mark
>> them all invalid and thereby reset the list to nil.  This doesn't do
>> anything for the cache's space consumption, but that wasn't what you were
>> worried about anyway was it?
>
> That sounds like a workable solution to this edge case. I'll see how
> that works.

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.

This code does pass the regression tests with CLOBBER_CACHE_ALWAYS, does
have the desired performance impact on restore of hundreds of thousands
of foreign key constraints and does not show any negative impact on bulk
loading of data with foreign keys.


Regards, Jan

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