NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commit7d07128

committed

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

Commit45ba424 improved foreign key lookups during bulk updateswhen the FK value does not change. When restoring a schema dumpfrom a database with many (say 100,000) foreign keys, this cachewould grow very big and every ALTER TABLE command was causing anInvalidateConstraintCacheCallBack(), which uses a sequential hashtable scan. This could cause a severe performance regression inrestoring a schema dump (including during pg_upgrade).The patch uses a heuristic method of detecting when the hash tableshould be destroyed and recreated.InvalidateConstraintCacheCallBack() adds the current size of thehash table to a counter. When that sum reaches 1,000,000, the hashtable is flushed. This fixes the regression without noticeableharm to the bulk update use case.Jan WieckBackpatch to 9.3 where the performance regression was introduced.

1 parent907f3a9 commit7d07128Copy full SHA for 7d07128

File tree

1 file changed

+35

-3

lines changed

src/backend/utils/adt
- ri_triggers.c

1 file changed

+35

-3

lines changed

`‎src/backend/utils/adt/ri_triggers.c`

Lines changed: 35 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -182,6 +182,7 @@ typedef struct RI_CompareHashEntry`
`182`	`182`	`* ----------`
`183`	`183`	`*/`
`184`	`184`	`staticHTAB*ri_constraint_cache=NULL;`
	`185`	`+staticlongri_constraint_cache_seq_count=0;`
`185`	`186`	`staticHTAB*ri_query_cache=NULL;`
`186`	`187`	`staticHTAB*ri_compare_cache=NULL;`
`187`	`188`
`@@ -214,6 +215,7 @@ static bool ri_KeysEqual(Relation rel, HeapTuple oldtup, HeapTuple newtup,`
`214`	`215`	`staticboolri_AttributesEqual(Oideq_opr,Oidtypeid,`
`215`	`216`	`Datumoldvalue,Datumnewvalue);`
`216`	`217`
	`218`	`+staticvoidri_InitConstraintCache(void);`
`217`	`219`	`staticvoidri_InitHashTables(void);`
`218`	`220`	`staticvoidInvalidateConstraintCacheCallBack(Datumarg,intcacheid,uint32hashvalue);`
`219`	`221`	`staticSPIPlanPtrri_FetchPreparedPlan(RI_QueryKey*key);`
`@@ -2932,6 +2934,20 @@ InvalidateConstraintCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)`
`2932`	`2934`
`2933`	`2935`	`Assert(ri_constraint_cache!=NULL);`
`2934`	`2936`
	`2937`	`+/*`
	`2938`	`+ * Prevent an O(N^2) problem when creating large amounts of foreign`
	`2939`	`+ * key constraints with ALTER TABLE, like it happens at the end of`
	`2940`	`+ * a pg_dump with hundred-thousands of tables having references.`
	`2941`	`+ */`
	`2942`	`+ri_constraint_cache_seq_count+=hash_get_num_entries(ri_constraint_cache);`
	`2943`	`+if (ri_constraint_cache_seq_count>1000000)`
	`2944`	`+{`
	`2945`	`+hash_destroy(ri_constraint_cache);`
	`2946`	`+ri_InitConstraintCache();`
	`2947`	`+ri_constraint_cache_seq_count=0;`
	`2948`	`+return;`
	`2949`	`+}`
	`2950`	`+`
`2935`	`2951`	`hash_seq_init(&status,ri_constraint_cache);`
`2936`	`2952`	`while ((hentry= (RI_ConstraintInfo*)hash_seq_search(&status))!=NULL)`
`2937`	`2953`	`{`
`@@ -3327,13 +3343,15 @@ ri_NullCheck(HeapTuple tup,`
`3327`	`3343`
`3328`	`3344`
`3329`	`3345`	`/* ----------`
`3330`		`- *ri_InitHashTables -`
	`3346`	`+ *ri_InitConstraintCache`
`3331`	`3347`	`*`
`3332`		`- *Initialize our internal hash tables.`
	`3348`	`+ * Initialize ri_constraint_cache when new or being rebuilt.`
	`3349`	`+ *`
	`3350`	`+ * This needs to be done from two places, so split it out to prevent drift.`
`3333`	`3351`	`* ----------`
`3334`	`3352`	`*/`
`3335`	`3353`	`staticvoid`
`3336`		`-ri_InitHashTables(void)`
	`3354`	`+ri_InitConstraintCache(void)`
`3337`	`3355`	`{`
`3338`	`3356`	`HASHCTLctl;`
`3339`	`3357`
`@@ -3344,6 +3362,20 @@ ri_InitHashTables(void)`
`3344`	`3362`	`ri_constraint_cache=hash_create("RI constraint cache",`
`3345`	`3363`	`RI_INIT_CONSTRAINTHASHSIZE,`
`3346`	`3364`	`&ctl,HASH_ELEM \|HASH_FUNCTION);`
	`3365`	`+}`
	`3366`	`+`
	`3367`	`+/* ----------`
	`3368`	`+ * ri_InitHashTables -`
	`3369`	`+ *`
	`3370`	`+ *Initialize our internal hash tables.`
	`3371`	`+ * ----------`
	`3372`	`+ */`
	`3373`	`+staticvoid`
	`3374`	`+ri_InitHashTables(void)`
	`3375`	`+{`
	`3376`	`+HASHCTLctl;`
	`3377`	`+`
	`3378`	`+ri_InitConstraintCache();`
`3347`	`3379`
`3348`	`3380`	`/* Arrange to flush cache on pg_constraint changes */`
`3349`	`3381`	`CacheRegisterSyscacheCallback(CONSTROID,`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit7d07128

File tree

1 file changed

1 file changed

`‎src/backend/utils/adt/ri_triggers.c`

0 commit comments