Small patch to fix an O(N^2) problem in foreign keys - Mailing list pgsql-hackers

From Jan Wieck
Subject Small patch to fix an O(N^2) problem in foreign keys
Date
Msg-id 55E8CCE9.8020007@wi3ck.info
Whole thread Raw
Responses Re: Small patch to fix an O(N^2) problem in foreign keys
List pgsql-hackers
Attached is a small patch and a script to reproduce the issue.

The problem is a cache introduced in commit 45ba4247 that improves
foreign key lookups during bulk updates when the FK value does not
change. When restoring a schema dump from a database with many (say
100,000) foreign keys, this cache is growing very big and every ALTER
TABLE command is causing a InvalidateConstraintCacheCallBack(), which
does a sequential hash table scan.

The patch uses a heuristic method of detecting when the hash table
should be destroyed and recreated. InvalidateConstraintCacheCallBack()
adds the current size of the hash table to a counter. When that sum
reaches 1,000,000, the hash table is flushed. This improves the schema
restore of a database with 100,000 foreign keys by factor 3.

According to my tests the patch does not interfere with the bulk
updates, the original feature was supposed to improve.


Regards, Jan

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

Attachment

pgsql-hackers by date:

Previous
From: Corey Huinker
Date:
Subject: Re: [POC] FETCH limited by bytes.
Next
From: Tatsuo Ishii
Date:
Subject: Re: BRIN INDEX value