Bug #18806829 OPENING INNODB TABLES WITH MANY FOREIGN KEY REFERENCES IS

SLOW/CRASHES SEMAPHORE

Problem:

There are 2 lakh tables - fk_000001, fk_000002 ... fk_200000.  All of them
are related to the same parent_table through a foreign key constraint.
When the parent_table is loaded into the dictionary cache, all the child table
will also be loaded.  This is taking lot of time.  Since this operation happens
when the dictionary latch is taken, the scenario leads to "long semaphore wait"
situation and the server gets killed.

Analysis:

A simple performance analysis showed that the slowness is because of the
dict_foreign_find() function.  It does a linear search on two linked list
table->foreign_list and table->referenced_list, looking for a particular
foreign key object based on foreign->id as the key.  This is called two
times for each foreign key object.

Solution:

Introduce a rb tree in table->foreign_rbt and table->referenced_rbt, which
are some sort of index on table->foreign_list and table->referenced_list
respectively, using foreign->id as the key.  These rbt structures will be
solely used by dict_foreign_find().  

rb#5599 approved by Vasil

4 files changed, 214 insertions, 39 deletions

diff --git a/storage/innobase/dict/dict0crea.c b/storage/innobase/dict/dict0crea.c
index eeebbe9bbd2..ac8a1eac03c 100644
--- a/storage/innobase/dict/dict0crea.c
+++ b/storage/innobase/dict/dict0crea.c
@@ -1,6 +1,6 @@
 /*****************************************************************************
 
-Copyright (c) 1996, 2013, Oracle and/or its affiliates. All Rights Reserved.
+Copyright (c) 1996, 2014, Oracle and/or its affiliates. All Rights Reserved.
 
 This program is free software; you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free Software
@@ -1441,6 +1441,8 @@ dict_create_add_foreign_to_dictionary(
 	ulint		i;
 	pars_info_t*	info;
 
+	ut_ad(mutex_own(&(dict_sys->mutex)));
+
 	if (foreign->id == NULL) {
 		/* Generate a new constraint id */
 		ulint	namelen	= strlen(table->name);
@@ -1519,6 +1521,37 @@ dict_create_add_foreign_to_dictionary(
 				      "END;\n"
 				      , table, foreign, trx);
 
+	if (error == DB_SUCCESS) {
+
+
+		if (foreign->foreign_table != NULL) {
+			ib_rbt_t*	rbt
+				= foreign->foreign_table->foreign_rbt;
+
+			if (rbt == NULL) {
+				rbt = dict_table_init_foreign_rbt(
+					foreign->foreign_table);
+			} else {
+				rbt_delete(rbt, foreign->id);
+			}
+
+			rbt_insert(rbt, foreign->id, &foreign);
+		}
+
+		if (foreign->referenced_table != NULL) {
+			ib_rbt_t* rbt
+				= foreign->referenced_table->referenced_rbt;
+
+			if (rbt == NULL) {
+				rbt = dict_table_init_referenced_rbt(
+					foreign->referenced_table);
+			} else {
+				rbt_delete(rbt, foreign->id);
+			}
+			rbt_insert(rbt, foreign->id, &foreign);
+		}
+	}
+
 	return(error);
 }
 
@@ -1543,6 +1576,7 @@ dict_create_add_foreigns_to_dictionary(
 	dict_foreign_t*	foreign;
 	ulint		number	= start_id + 1;
 	ulint		error;
+	DBUG_ENTER("dict_create_add_foreigns_to_dictionary");
 
 	ut_ad(mutex_own(&(dict_sys->mutex)));
 
@@ -1551,7 +1585,7 @@ dict_create_add_foreigns_to_dictionary(
 			"InnoDB: table SYS_FOREIGN not found"
 			" in internal data dictionary\n");
 
-		return(DB_ERROR);
+		DBUG_RETURN(DB_ERROR);
 	}
 
 	for (foreign = UT_LIST_GET_FIRST(table->foreign_list);
@@ -1563,9 +1597,9 @@ dict_create_add_foreigns_to_dictionary(
 
 		if (error != DB_SUCCESS) {
 
-			return(error);
+			DBUG_RETURN(error);
 		}
 	}
 
-	return(DB_SUCCESS);
+	DBUG_RETURN(DB_SUCCESS);
 }
diff --git a/storage/innobase/dict/dict0dict.c b/storage/innobase/dict/dict0dict.c
index 546794be26c..4ed0051b77a 100644
--- a/storage/innobase/dict/dict0dict.c
+++ b/storage/innobase/dict/dict0dict.c
@@ -1,6 +1,6 @@
 /*****************************************************************************
 
-Copyright (c) 1996, 2013, Oracle and/or its affiliates. All Rights Reserved.
+Copyright (c) 1996, 2014, Oracle and/or its affiliates. All Rights Reserved.
 
 This program is free software; you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free Software
@@ -26,6 +26,7 @@ Created 1/8/1996 Heikki Tuuri
 #include <my_sys.h>
 
 #include "dict0dict.h"
+#include "ut0rbt.h"
 
 #ifdef UNIV_NONINL
 #include "dict0dict.ic"
@@ -191,6 +192,7 @@ UNIV_INTERN FILE*	dict_foreign_err_file		= NULL;
 /* mutex protecting the foreign and unique error buffers */
 UNIV_INTERN mutex_t	dict_foreign_err_mutex;
 #endif /* !UNIV_HOTBACKUP */
+
 /******************************************************************//**
 Makes all characters in a NUL-terminated UTF-8 string lower case. */
 UNIV_INTERN
@@ -1103,6 +1105,10 @@ dict_table_rename_in_cache(
 
 		UT_LIST_INIT(table->referenced_list);
 
+		if (table->referenced_rbt != NULL) {
+			rbt_clear(table->referenced_rbt);
+		}
+
 		return(TRUE);
 	}
 
@@ -1113,6 +1119,10 @@ dict_table_rename_in_cache(
 	foreign = UT_LIST_GET_FIRST(table->foreign_list);
 
 	while (foreign != NULL) {
+
+		/* The id will be changed.  So remove old one */
+		rbt_delete(foreign->foreign_table->foreign_rbt, foreign->id);
+
 		if (ut_strlen(foreign->foreign_table_name)
 		    < ut_strlen(table->name)) {
 			/* Allocate a longer name buffer;
@@ -1260,6 +1270,9 @@ dict_table_rename_in_cache(
 			mem_free(old_id);
 		}
 
+		rbt_insert(foreign->foreign_table->foreign_rbt,
+			   foreign->id, &foreign);
+
 		foreign = UT_LIST_GET_NEXT(foreign_list, foreign);
 	}
 
@@ -2480,22 +2493,40 @@ dict_foreign_remove_from_cache(
 /*===========================*/
 	dict_foreign_t*	foreign)	/*!< in, own: foreign constraint */
 {
+	DBUG_ENTER("dict_foreign_remove_from_cache");
+
 	ut_ad(mutex_own(&(dict_sys->mutex)));
 	ut_a(foreign);
 
 	if (foreign->referenced_table) {
+		ib_rbt_t*	rbt;
+
 		UT_LIST_REMOVE(referenced_list,
 			       foreign->referenced_table->referenced_list,
 			       foreign);
+
+		rbt = foreign->referenced_table->referenced_rbt;
+		if (rbt != NULL) {
+			rbt_delete(rbt, foreign->id);
+		}
 	}
 
 	if (foreign->foreign_table) {
+		ib_rbt_t*	rbt;
+
 		UT_LIST_REMOVE(foreign_list,
 			       foreign->foreign_table->foreign_list,
 			       foreign);
+		rbt = foreign->foreign_table->foreign_rbt;
+
+		if (rbt != NULL) {
+			rbt_delete(rbt, foreign->id);
+		}
 	}
 
 	dict_foreign_free(foreign);
+
+	DBUG_VOID_RETURN;
 }
 
 /**********************************************************************//**
@@ -2509,33 +2540,36 @@ dict_foreign_find(
 	dict_table_t*	table,	/*!< in: table object */
 	const char*	id)	/*!< in: foreign constraint id */
 {
-	dict_foreign_t*	foreign;
-
-	ut_ad(mutex_own(&(dict_sys->mutex)));
-
-	foreign = UT_LIST_GET_FIRST(table->foreign_list);
+	const ib_rbt_node_t*	node;
 
-	while (foreign) {
-		if (ut_strcmp(id, foreign->id) == 0) {
+	DBUG_ENTER("dict_foreign_find");
 
-			return(foreign);
+	ut_ad(mutex_own(&(dict_sys->mutex)));
+	ut_ad(dict_table_check_foreign_keys(table));
+
+	if (table->foreign_rbt != NULL) {
+		ut_a(UT_LIST_GET_LEN(table->foreign_list)
+		     == rbt_size(table->foreign_rbt));
+		node = rbt_lookup(table->foreign_rbt, id);
+		if (node != NULL) {
+			DBUG_RETURN(*(dict_foreign_t**) node->value);
 		}
-
-		foreign = UT_LIST_GET_NEXT(foreign_list, foreign);
+	} else {
+		ut_a(UT_LIST_GET_LEN(table->foreign_list) == 0);
 	}
 
-	foreign = UT_LIST_GET_FIRST(table->referenced_list);
-
-	while (foreign) {
-		if (ut_strcmp(id, foreign->id) == 0) {
-
-			return(foreign);
+	if (table->referenced_rbt != NULL) {
+		ut_a(UT_LIST_GET_LEN(table->referenced_list)
+		     == rbt_size(table->referenced_rbt));
+		node = rbt_lookup(table->referenced_rbt, id);
+		if (node != NULL) {
+			DBUG_RETURN(*(dict_foreign_t**) node->value);
 		}
-
-		foreign = UT_LIST_GET_NEXT(referenced_list, foreign);
+	} else {
+		ut_a(UT_LIST_GET_LEN(table->referenced_list) == 0);
 	}
 
-	return(NULL);
+	DBUG_RETURN(NULL);
 }
 
 /*********************************************************************//**
@@ -2773,6 +2807,8 @@ dict_foreign_add_to_cache(
 	ibool		added_to_referenced_list= FALSE;
 	FILE*		ef			= dict_foreign_err_file;
 
+	DBUG_ENTER("dict_foreign_add_to_cache");
+
 	ut_ad(mutex_own(&(dict_sys->mutex)));
 
 	for_table = dict_table_check_if_in_cache_low(
@@ -2782,7 +2818,14 @@ dict_foreign_add_to_cache(
 		foreign->referenced_table_name_lookup);
 	ut_a(for_table || ref_table);
 
+	if (ref_table != NULL && ref_table->referenced_rbt == NULL) {
+		dict_table_init_referenced_rbt(ref_table);
+	}
+
 	if (for_table) {
+		if (for_table->foreign_rbt == NULL) {
+			dict_table_init_foreign_rbt(for_table);
+		}
 		for_in_cache = dict_foreign_find(for_table, foreign->id);
 	}
 
@@ -2819,18 +2862,22 @@ dict_foreign_add_to_cache(
 				mem_heap_free(foreign->heap);
 			}
 
-			return(DB_CANNOT_ADD_CONSTRAINT);
+			DBUG_RETURN(DB_CANNOT_ADD_CONSTRAINT);
 		}
 
 		for_in_cache->referenced_table = ref_table;
 		for_in_cache->referenced_index = index;
+
 		UT_LIST_ADD_LAST(referenced_list,
-				 ref_table->referenced_list,
-				 for_in_cache);
+				 ref_table->referenced_list, for_in_cache);
 		added_to_referenced_list = TRUE;
+
+		rbt_insert(ref_table->referenced_rbt,
+			   for_in_cache->id, &for_in_cache);
 	}
 
 	if (for_in_cache->foreign_table == NULL && for_table) {
+
 		index = dict_foreign_find_index(
 			for_table,
 			for_in_cache->foreign_col_names,
@@ -2859,22 +2906,28 @@ dict_foreign_add_to_cache(
 						referenced_list,
 						ref_table->referenced_list,
 						for_in_cache);
+					rbt_delete(ref_table->referenced_rbt,
+						   for_in_cache->id);
 				}
 
 				mem_heap_free(foreign->heap);
 			}
 
-			return(DB_CANNOT_ADD_CONSTRAINT);
+			DBUG_RETURN(DB_CANNOT_ADD_CONSTRAINT);
 		}
 
 		for_in_cache->foreign_table = for_table;
 		for_in_cache->foreign_index = index;
+
 		UT_LIST_ADD_LAST(foreign_list,
 				 for_table->foreign_list,
 				 for_in_cache);
+
+		rbt_insert(for_table->foreign_rbt, for_in_cache->id,
+			   &for_in_cache);
 	}
 
-	return(DB_SUCCESS);
+	DBUG_RETURN(DB_SUCCESS);
 }
 
 #endif /* !UNIV_HOTBACKUP */
diff --git a/storage/innobase/dict/dict0load.c b/storage/innobase/dict/dict0load.c
index 9ddc4b28cae..4d012c5cf50 100644
--- a/storage/innobase/dict/dict0load.c
+++ b/storage/innobase/dict/dict0load.c
@@ -1759,6 +1759,8 @@ dict_load_table(
 	const char*	err_msg;
 	mtr_t		mtr;
 
+	DBUG_ENTER("dict_load_table");
+
 	ut_ad(mutex_own(&(dict_sys->mutex)));
 
 	heap = mem_heap_create(32000);
@@ -1792,7 +1794,7 @@ err_exit:
 		mtr_commit(&mtr);
 		mem_heap_free(heap);
 
-		return(NULL);
+		DBUG_RETURN(NULL);
 	}
 
 	field = rec_get_nth_field_old(rec, 0, &len);
@@ -1954,8 +1956,8 @@ err_exit:
 #endif /* 0 */
 func_exit:
 	mem_heap_free(heap);
-
-	return(table);
+	ut_ad(table == NULL || dict_table_check_foreign_keys(table));
+	DBUG_RETURN(table);
 }
 
 /***********************************************************************//**
@@ -2180,6 +2182,8 @@ dict_load_foreign(
 	dict_table_t*	for_table;
 	dict_table_t*	ref_table;
 
+	DBUG_ENTER("dict_load_foreign");
+
 	ut_ad(mutex_own(&(dict_sys->mutex)));
 
 	heap2 = mem_heap_create(1000);
@@ -2212,7 +2216,7 @@ dict_load_foreign(
 		mtr_commit(&mtr);
 		mem_heap_free(heap2);
 
-		return(DB_ERROR);
+		DBUG_RETURN(DB_ERROR);
 	}
 
 	field = rec_get_nth_field_old(rec, 0, &len);
@@ -2228,7 +2232,7 @@ dict_load_foreign(
 		mtr_commit(&mtr);
 		mem_heap_free(heap2);
 
-		return(DB_ERROR);
+		DBUG_RETURN(DB_ERROR);
 	}
 
 	/* Read the table names and the number of columns associated
@@ -2325,7 +2329,7 @@ dict_load_foreign(
 	a new foreign key constraint but loading one from the data
 	dictionary. */
 
-	return(dict_foreign_add_to_cache(foreign, check_charsets, ignore_err));
+	DBUG_RETURN(dict_foreign_add_to_cache(foreign, check_charsets, ignore_err));
 }
 
 /***********************************************************************//**
@@ -2360,6 +2364,8 @@ dict_load_foreigns(
 	ulint		err;
 	mtr_t		mtr;
 
+	DBUG_ENTER("dict_load_foreigns");
+
 	ut_ad(mutex_own(&(dict_sys->mutex)));
 
 	sys_foreign = dict_table_get_low("SYS_FOREIGN", DICT_ERR_IGNORE_NONE);
@@ -2371,7 +2377,7 @@ dict_load_foreigns(
 			"InnoDB: Error: no foreign key system tables"
 			" in the database\n");
 
-		return(DB_ERROR);
+		DBUG_RETURN(DB_ERROR);
 	}
 
 	ut_a(!dict_table_is_comp(sys_foreign));
@@ -2451,7 +2457,7 @@ loop:
 	if (err != DB_SUCCESS) {
 		btr_pcur_close(&pcur);
 
-		return(err);
+		DBUG_RETURN(err);
 	}
 
 	mtr_start(&mtr);
@@ -2480,5 +2486,74 @@ load_next_index:
 		goto start_load;
 	}
 
-	return(DB_SUCCESS);
+	DBUG_RETURN(DB_SUCCESS);
+}
+
+/********************************************************************//**
+Check if dict_table_t::foreign_rbt and dict_table::foreign_list
+contain the same set of foreign key objects; and check if
+dict_table_t::referenced_rbt and dict_table::referenced_list contain
+the same set of foreign key objects.
+@return	TRUE if correct, FALSE otherwise. */
+ibool
+dict_table_check_foreign_keys(
+/*==========================*/
+	const dict_table_t* table)	/* in: table object to check */
+{
+	dict_foreign_t*		foreign;
+	const ib_rbt_node_t*	node;
+
+	ut_ad(mutex_own(&(dict_sys->mutex)));
+
+	if (table->foreign_rbt == NULL) {
+
+		if (UT_LIST_GET_LEN(table->foreign_list) > 0) {
+			return(FALSE);
+		}
+
+	} else {
+
+		if (UT_LIST_GET_LEN(table->foreign_list)
+		    != rbt_size(table->foreign_rbt)) {
+			return(FALSE);
+		}
+
+		foreign = UT_LIST_GET_FIRST(table->foreign_list);
+
+		while (foreign != NULL) {
+
+			node = rbt_lookup(table->foreign_rbt, foreign->id);
+			if (node == NULL) {
+				return(FALSE);
+			}
+			foreign = UT_LIST_GET_NEXT(foreign_list, foreign);
+		}
+	}
+
+	if (table->referenced_rbt == NULL ) {
+
+		if (UT_LIST_GET_LEN(table->referenced_list) > 0) {
+			return(FALSE);
+		}
+
+	} else {
+
+		if (UT_LIST_GET_LEN(table->referenced_list)
+		    != rbt_size(table->referenced_rbt)) {
+			return(FALSE);
+		}
+
+		foreign = UT_LIST_GET_FIRST(table->referenced_list);
+
+		while (foreign != NULL) {
+
+			node = rbt_lookup(table->referenced_rbt, foreign->id);
+			if (node == NULL) {
+				return(FALSE);
+			}
+			foreign = UT_LIST_GET_NEXT(referenced_list, foreign);
+		}
+	}
+
+	return(TRUE);
 }
diff --git a/storage/innobase/dict/dict0mem.c b/storage/innobase/dict/dict0mem.c
index 5be5c1b5543..cea7a253ba0 100644
--- a/storage/innobase/dict/dict0mem.c
+++ b/storage/innobase/dict/dict0mem.c
@@ -66,6 +66,7 @@ dict_mem_table_create(
 {
 	dict_table_t*	table;
 	mem_heap_t*	heap;
+	DBUG_ENTER("dict_mem_table_create");
 
 	ut_ad(name);
 	ut_a(!(flags & (~0 << DICT_TF2_BITS)));
@@ -98,8 +99,11 @@ dict_mem_table_create(
 	table->n_waiting_or_granted_auto_inc_locks = 0;
 #endif /* !UNIV_HOTBACKUP */
 
+	table->foreign_rbt = NULL;
+	table->referenced_rbt = NULL;
+
 	ut_d(table->magic_n = DICT_TABLE_MAGIC_N);
-	return(table);
+	DBUG_RETURN(table);
 }
 
 /****************************************************************//**
@@ -117,6 +121,15 @@ dict_mem_table_free(
 #ifndef UNIV_HOTBACKUP
 	mutex_free(&(table->autoinc_mutex));
 #endif /* UNIV_HOTBACKUP */
+
+	if (table->foreign_rbt != NULL) {
+		rbt_free(table->foreign_rbt);
+	}
+
+	if (table->referenced_rbt != NULL) {
+		rbt_free(table->referenced_rbt);
+	}
+
 	ut_free(table->name);
 	mem_heap_free(table->heap);
 }