Fix an O(N^2) problem in foreign key references.

kgrittn · kgrittn · commit 7d0712890d1e · 2015-09-11T13:20:30.000-05:00
Commit 45ba424 improved 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 would grow very big and every ALTER TABLE command was causing an InvalidateConstraintCacheCallBack(), which uses a sequential hash table scan. This could cause a severe performance regression in restoring a schema dump (including during pg_upgrade). 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 fixes the regression without noticeable harm to the bulk update use case. Jan Wieck Backpatch to 9.3 where the performance regression was introduced.
diff --git a/src/backend/utils/adt/ri_triggers.c b/src/backend/utils/adt/ri_triggers.c
@@ -182,6 +182,7 @@ typedef struct RI_CompareHashEntry
  * ----------
  */
 static HTAB *ri_constraint_cache = NULL;
+static long  ri_constraint_cache_seq_count = 0;
 static HTAB *ri_query_cache = NULL;
 static HTAB *ri_compare_cache = NULL;
 
@@ -214,6 +215,7 @@ static bool ri_KeysEqual(Relation rel, HeapTuple oldtup, HeapTuple newtup,
 static bool ri_AttributesEqual(Oid eq_opr, Oid typeid,
 				   Datum oldvalue, Datum newvalue);
 
+static void ri_InitConstraintCache(void);
 static void ri_InitHashTables(void);
 static void InvalidateConstraintCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);
 static SPIPlanPtr ri_FetchPreparedPlan(RI_QueryKey *key);
@@ -2932,6 +2934,20 @@ InvalidateConstraintCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)
 
 	Assert(ri_constraint_cache != NULL);
 
+	/*
+	 * Prevent an O(N^2) problem when creating large amounts of foreign
+	 * key constraints with ALTER TABLE, like it happens at the end of
+	 * a pg_dump with hundred-thousands of tables having references.
+	 */
+	ri_constraint_cache_seq_count += hash_get_num_entries(ri_constraint_cache);
+	if (ri_constraint_cache_seq_count > 1000000)
+	{
+		hash_destroy(ri_constraint_cache);
+		ri_InitConstraintCache();
+		ri_constraint_cache_seq_count = 0;
+		return;
+	}
+
 	hash_seq_init(&status, ri_constraint_cache);
 	while ((hentry = (RI_ConstraintInfo *) hash_seq_search(&status)) != NULL)
 	{
@@ -3327,13 +3343,15 @@ ri_NullCheck(HeapTuple tup,
 
 
 /* ----------
- * ri_InitHashTables -
+ * ri_InitConstraintCache
  *
- *	Initialize our internal hash tables.
+ * Initialize ri_constraint_cache when new or being rebuilt.
+ *
+ * This needs to be done from two places, so split it out to prevent drift.
  * ----------
  */
 static void
-ri_InitHashTables(void)
+ri_InitConstraintCache(void)
 {
 	HASHCTL		ctl;
 
@@ -3344,6 +3362,20 @@ ri_InitHashTables(void)
 	ri_constraint_cache = hash_create("RI constraint cache",
 									  RI_INIT_CONSTRAINTHASHSIZE,
 									  &ctl, HASH_ELEM | HASH_FUNCTION);
+}
+
+/* ----------
+ * ri_InitHashTables -
+ *
+ *	Initialize our internal hash tables.
+ * ----------
+ */
+static void
+ri_InitHashTables(void)
+{
+	HASHCTL		ctl;
+
+	ri_InitConstraintCache();
 
 	/* Arrange to flush cache on pg_constraint changes */
 	CacheRegisterSyscacheCallback(CONSTROID,
