MySQL Bugs: #4446: Server Crashes on DELETE which should cascade very deep

Bug #4446	Server Crashes on DELETE which should cascade very deep
Submitted:	8 Jul 2004 0:19	Modified:	16 Jul 2004 10:17
Reporter:	Thomas Kleffel	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S2 (Serious)
Version:	4.0	OS:	Linux (gentoo-linux i386)
Assigned to:	Marko Mäkelä	CPU Architecture:	Any

Description:
I have a table (InnoDB) with a primary key (ID) and a foreign key (pID) which references to itself's primary key. This table is used to represent a tree in the database. To enforece consitency I added a foreign key constraint in the following manner:

ALTER TABLE tree ADD FOREIGN KEY (pID) REFERENCES tree(pID) ON DELETE CASCADE ON UPDATE CASCADE

Due to a bug in my software I created a veeeeery deep (about 7000 nodes) tree. So the table looks like this:

   ID | pID | name
------+-----+-----
   0  |   0 | root
   1  |   0 | node1
   2  |   1 | node2
   3  |   2 | node3
[...]
   3  |   2 | node3
7000  |6999 | node7000

Now I executed a 
DELETE FROM tree WHERE ID=1
and expected the whole tree to be gone.

Instead - boooom - the server crashed. This is what appeard in my log:

Number of processes running now: 1
mysqld process hanging, pid 32323 - killed
040707 23:50:06  mysqld restarted
040707 23:50:06  InnoDB: Database was not shut down normally!
InnoDB: Starting crash recovery.
InnoDB: Reading tablespace information from the .ibd files...
InnoDB: Restoring possible half-written data pages from the doublewrite
InnoDB: buffer...
040707 23:50:06  InnoDB: Starting log scan based on checkpoint at
InnoDB: log sequence number 0 563903299.
InnoDB: Doing recovery: scanned up to log sequence number 0 563903299
040707 23:50:06  InnoDB: Flushing modified pages from the buffer pool...
040707 23:50:06  InnoDB: Started; log sequence number 0 563903299
/usr/local/mysql/bin/mysqld: ready for connections.
Version: '4.1.2-alpha-max'  socket: '/tmp/mysql.sock'  port: 3306

This problem does not appear if I work with trees as deep as 20 or 30 nodes.

How to repeat:
As the table which causes the server to crash is too big (about 7000 lines) to include it here I will be more than happy to send it to you. Just contact me at  

thomas(dot)kleffel(at)maintech(dot)de

Just updated to 4.1.3-max, happens there as well.

changed Version field to 4.1.3-beta-max

I could repeat the crash with a tree structure that is 75 levels deep. It looks like InnoDB is calling itself recursively:

row_upd_del_mark_clust_rec
row_upd_clust_step
row_upd
row_upd_step
row_update_cascade_for_mysql
row_ins_foreign_check_on_constraint
row_ins_check_foreign_constraint
row_upd_check_references_constraints
...

Marko,

can you add some check to row0ins.c that would restrict the depth of the recursion to 50, for example?

Regards,

Heikki

What should InnoDB do when that artificial limit is exceeded? Abort the transaction?

I have another idea: set up a queue or stack data structure that holds those referenced key values that have not been processed yet. That should consume much less memory than the many stack frames currently needed for one recursion step.

Marko,

maybe it should treat the constraint as RESTRICT then? In practice that leads to the rollback to the SQL statement. We could also print a warning to the .err log.

InnoDB already considers self-referential ON UPDATE CASCADE's as RESTRICT.

Regards,

Heikki

Fix committed to 4.0 tree, waiting for approval. At most 49 levels of cascaded UPDATE or DELETE will be tolerated. The limit could probably be made much higher by not allocating table_name_buf[1000] from the stack, in row_ins_foreign_check_on_constraint().

Each level of recursion consumes almost 4 kilobytes of stack space on x86. Removing table_name_buf[1000] from the stack reduces the consumption to less than 3000 bytes. After some discussion, Heikki and I decided to limit the recursion depth to 15 levels in order to avoid stack overflow on builds with small stack size. I'm submitting a new patch.

Thank you for your bug report. This issue has been committed to our
source repository of that product and will be incorporated into the
next release.

If necessary, you can access the source repository and build the latest
available version, including the bugfix, yourself. More information 
about accessing the source trees is available at
    http://www.mysql.com/doc/en/Installing_source_tree.html

Additional info:

Fix pushed to the 4.0 tree, will appear in 4.1 after some time.