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

1 files changed, 10 insertions, 2 deletions

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;