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

8 files changed, 334 insertions, 43 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);
 }
diff --git a/storage/innobase/include/dict0dict.h b/storage/innobase/include/dict0dict.h
index deabbfcbe92..254d4e149ca 100644
--- a/storage/innobase/include/dict0dict.h
+++ b/storage/innobase/include/dict0dict.h
@@ -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
@@ -39,6 +39,7 @@ Created 1/8/1996 Heikki Tuuri
 #include "ut0rnd.h"
 #include "ut0byte.h"
 #include "trx0types.h"
+#include "ut0rbt.h"
 
 #ifndef UNIV_HOTBACKUP
 # include "sync0sync.h"
@@ -1331,6 +1332,42 @@ dict_set_corrupted_by_space(
 /*========================*/
 	ulint		space_id);	/*!< in: space ID */
 
+/**********************************************************************//**
+Compares the given foreign key identifier (the key in rb-tree) and the
+foreign key identifier in the given fk object (value in rb-tree).
+@return	negative, 0, or positive if foreign_id is smaller, equal,
+or greater than foreign_obj->id, respectively. */
+UNIV_INLINE
+int
+dict_foreign_rbt_cmp(
+/*=================*/
+	const void*	foreign_id,	/*!< in: the foreign key identifier
+					which is used as a key in rb-tree.  */
+	const void*	foreign_obj);	/*!< in: the foreign object itself
+					which is used as value in rb-tree. */
+
+/**********************************************************************//**
+Allocate the table->foreign_rbt, which stores all the foreign objects
+that is available in table->foreign_list.
+@return the allocated rbt object */
+UNIV_INLINE
+ib_rbt_t*
+dict_table_init_foreign_rbt(
+/*========================*/
+	dict_table_t*	table);	/*!< in: the table object whose
+				table->foreign_rbt will be initialized */
+
+/**********************************************************************//**
+Allocate the table->referened_rbt, which stores all the foreign objects
+that is available in table->referenced_list.
+@return the allocated rbt object */
+UNIV_INLINE
+ib_rbt_t*
+dict_table_init_referenced_rbt(
+/*===========================*/
+	dict_table_t*	table);	/*!< in: the table object whose
+				table->referenced_rbt will be initialized */
+
 #ifndef UNIV_NONINL
 #include "dict0dict.ic"
 #endif
diff --git a/storage/innobase/include/dict0dict.ic b/storage/innobase/include/dict0dict.ic
index 9b0c9e5c001..a63e1d16427 100644
--- a/storage/innobase/include/dict0dict.ic
+++ b/storage/innobase/include/dict0dict.ic
@@ -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
@@ -945,3 +945,62 @@ dict_index_is_corrupted(
 }
 
 #endif /* !UNIV_HOTBACKUP */
+/**********************************************************************//**
+Compares the given foreign key identifier (the key in rb-tree) and the
+foreign key identifier in the given fk object (value in rb-tree).
+@return	negative, 0, or positive if foreign_id is smaller, equal,
+or greater than foreign_obj->id, respectively. */
+UNIV_INLINE
+int
+dict_foreign_rbt_cmp(
+/*=================*/
+	const void*	foreign_id,	/*!< in: the foreign key identifier
+					which is used as a key in rb-tree.  */
+	const void*	foreign_obj)	/*!< in: the foreign object itself
+					which is used as value in rb-tree. */
+{
+	return(ut_strcmp((const char*) foreign_id,
+			 (*(dict_foreign_t**) foreign_obj)->id));
+}
+
+/**********************************************************************//**
+Allocate the table->foreign_rbt, which stores all the foreign objects
+that is available in table->foreign_list.  The caller must hold the
+dict_sys->mutex.
+@return the allocated rbt object */
+UNIV_INLINE
+ib_rbt_t*
+dict_table_init_foreign_rbt(
+/*========================*/
+	dict_table_t*	table) /*!< in: the table object whose
+				table->foreign_rbt will be initialized */
+{
+	ut_a(table->foreign_rbt == NULL);
+	ut_ad(mutex_own(&(dict_sys->mutex)));
+
+	table->foreign_rbt = rbt_create(sizeof(dict_foreign_t*),
+					dict_foreign_rbt_cmp);
+	ut_a(table->foreign_rbt != NULL);
+	return(table->foreign_rbt);
+}
+
+/**********************************************************************//**
+Allocate the table->referened_rbt, which stores all the foreign objects
+that is available in table->referenced_list.  The caller must hold the
+dict_sys->mutex.
+@return the allocated rbt object */
+UNIV_INLINE
+ib_rbt_t*
+dict_table_init_referenced_rbt(
+/*===========================*/
+	dict_table_t*	table) /*!< in: the table object whose
+				table->referenced_rbt will be initialized */
+{
+	ut_a(table->referenced_rbt == NULL);
+	ut_ad(mutex_own(&(dict_sys->mutex)));
+
+	table->referenced_rbt = rbt_create(sizeof(dict_foreign_t*),
+					   dict_foreign_rbt_cmp);
+	ut_a(table->referenced_rbt != NULL);
+	return(table->referenced_rbt);
+}
diff --git a/storage/innobase/include/dict0load.h b/storage/innobase/include/dict0load.h
index bdc6a2b995c..772f36de850 100644
--- a/storage/innobase/include/dict0load.h
+++ b/storage/innobase/include/dict0load.h
@@ -32,6 +32,7 @@ Created 4/24/1996 Heikki Tuuri
 #include "ut0byte.h"
 #include "mem0mem.h"
 #include "btr0types.h"
+#include "ut0rbt.h"
 
 /** enum that defines all 6 system table IDs */
 enum dict_system_table_id {
@@ -329,6 +330,17 @@ dict_process_sys_foreign_col_rec(
 	const char**	ref_col_name,	/*!< out: referenced column name
 					in referenced table */
 	ulint*		pos);		/*!< out: column position */
+/********************************************************************//**
+Check if dict_table_t::foreign_rbt and dict_table::foreign_list
+contains the same set of foreign key objects; and check if
+dict_table_t::referenced_rbt and dict_table::referenced_list contains
+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 */
+
 #ifndef UNIV_NONINL
 #include "dict0load.ic"
 #endif
diff --git a/storage/innobase/include/dict0mem.h b/storage/innobase/include/dict0mem.h
index 0ee5721d34b..a58bb914be2 100644
--- a/storage/innobase/include/dict0mem.h
+++ b/storage/innobase/include/dict0mem.h
@@ -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
@@ -43,6 +43,7 @@ Created 1/8/1996 Heikki Tuuri
 #include "ut0byte.h"
 #include "hash0hash.h"
 #include "trx0types.h"
+#include "ut0rbt.h"
 
 /** Type flags of an index: OR'ing of the flags is allowed to define a
 combination of types */
@@ -506,7 +507,6 @@ a foreign key constraint is enforced, therefore RESTRICT just means no flag */
 #define DICT_FOREIGN_ON_UPDATE_NO_ACTION 32	/*!< ON UPDATE NO ACTION */
 /* @} */
 
-
 /** Data structure for a database table.  Most fields will be
 initialized to 0, NULL or FALSE in dict_mem_table_create(). */
 struct dict_table_struct{
@@ -558,6 +558,14 @@ struct dict_table_struct{
 	UT_LIST_BASE_NODE_T(dict_foreign_t)
 			referenced_list;/*!< list of foreign key constraints
 				which refer to this table */
+
+	ib_rbt_t*	foreign_rbt;	/*!< a rb-tree of all foreign keys
+					listed in foreign_list, sorted by
+					foreign->id */
+	ib_rbt_t*	referenced_rbt;	/*!< a rb-tree of all foreign keys
+					listed in referenced_list, sorted by
+					foreign->id */
+
 	UT_LIST_NODE_T(dict_table_t)
 			table_LRU; /*!< node of the LRU list of tables */
 	ulint		n_mysql_handles_opened;