postgres.git / summary / log / commit / refs

commit    5ddc72887a012f6a8b85707ef27d85c274faf53d
Author:   Kevin Grittner <kgrittn@postgresql.org>
Date:     Fri Sep 11 18:06:51 2015 +0000
First released in: 9.6.0, 9.3.10, 9.4.5, 9.5.0

    Fix an O(N^2) problem in foreign key references.
    
    Commit 45ba424f 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.


 src/backend/utils/adt/ri_triggers.c | 38 ++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/adt/ri_triggers.c b/src/backend/utils/adt/ri_triggers.c
index 61edde9c5d3..0469522a567 100644
--- a/src/backend/utils/adt/ri_triggers.c
+++ b/src/backend/utils/adt/ri_triggers.c
@@ -183,6 +183,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;
 
@@ -215,6 +216,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);
@@ -2945,6 +2947,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)
 	{
@@ -3364,13 +3380,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;
 
@@ -3380,6 +3398,20 @@ ri_InitHashTables(void)
 	ri_constraint_cache = hash_create("RI constraint cache",
 									  RI_INIT_CONSTRAINTHASHSIZE,
 									  &ctl, HASH_ELEM | HASH_BLOBS);
+}
+
+/* ----------
+ * 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,


[parent: aa65de042f58]