Bug #25673 spatial index corruption, error 126 incorrect key file for table
Submitted: 17 Jan 2007 9:27 Modified: 15 Mar 2007 2:46
Reporter: Shane Bester (Platinum Quality Contributor) Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: MyISAM storage engine Severity:S1 (Critical)
Version:5.0.34,5.0.36-BK,5.1.15-BK OS: *
Assigned to: Ingo Strüwing CPU Architecture:Any
Tags: bfsm_2007_02_01, corruption, myisam, spatial

[17 Jan 2007 9:27] Shane Bester
Description:
when doing SELECT/INSERT/UPDATE/DELETE from a MyISAM table containing a SPATIAL index in a few concurrent threads, index file becomes corrupted quickly.

here's the output from running the testcase for ~5 minutes:

sbester@linux:~> ./testcase 
running initializations
completed spawning new database worker threads
query failed 'UPDATE `t1` set `spatial_point`=GeomFromText('POINT(143 59)') where  `c1` like 'f%'' : 126 (Incorrect key file for table '.\test\t1.MYI'; try to repair it)
query failed 'INSERT IGNORE INTO `t1` SET `c2` = 'e', `c1` = 'z', `c3` = 'i', `spatial_point` = GeomFromText('POINT(112 158)')' : 126 (Incorrect key file for table '.\test\t1.MYI'; try to repair it)
query failed 'UPDATE `t1` set `spatial_point`=GeomFromText('POINT(203 16)') where  `c1` like 'm%'' : 126 (Incorrect key file for table '.\test\t1.MYI'; try to repair it)
query failed 'UPDATE `t1` set `spatial_point`=GeomFromText('POINT(108 84)') where  `c1` like 'm%'' : 126 (Incorrect key file for table '.\test\t1.MYI'; try to repair it)

mysql> check table t1 extended;
+---------+-------+----------+-----------------------------------------------------------------+
| Table   | Op    | Msg_type | Msg_text                                                        |
+---------+-------+----------+-----------------------------------------------------------------+
| test.t1 | check | warning  | Table is marked as crashed                                      |
| test.t1 | check | warning  | Auto-increment value: 7934 is smaller than max used value: 7935 |
| test.t1 | check | error    | Key 5 doesn't point at same records that key 1                  |
| test.t1 | check | error    | Corrupt                                                         |
+---------+-------+----------+-----------------------------------------------------------------+
4 rows in set (0.01 sec)

How to repeat:
build and run testcase.c, after changing host, port, user, password at the top of the file.

if corruptions don't happen within ~30 minutes, then increase NUMTHREADS slightly in testcase.c. Normally takes < 5 minutes at 5 threads.

Suggested fix:
don't let indexes get corrupted.
[17 Jan 2007 9:29] Shane Bester
see top of file for build instructions, host, user, port, etc

Attachment: testcase.c (text/plain), 5.75 KiB.

[17 Jan 2007 12:20] Shane Bester
suse 9.3 using todays 5.0BK test:

mysql> check table t1 extended;
+---------+-------+----------+----------------------------+
| Table   | Op    | Msg_type | Msg_text                   |
+---------+-------+----------+----------------------------+
| test.t1 | check | warning  | Table is marked as crashed |
| test.t1 | check | error    | Found 4072 keys of 4073    |
| test.t1 | check | error    | Corrupt                    |
+---------+-------+----------+----------------------------+
3 rows in set (0.00 sec)

mysql> select version();
+--------------+
| version()    |
+--------------+
| 5.0.36-debug |
+--------------+
1 row in set (0.00 sec)
[30 Jan 2007 8:57] Stefan Gläßer
Hallo,

ich kann den Bug leider bestätigen. Ich lade täglich SQL-Files in eine Tabelle meiner Datenbank. Die SQL-Files enthalten entweder "Delete from table" oder "Insert into table ... on duplicate key update ..." Statements.

+----------------------+-------+----------+-------------------------------+
| Table                | Op    | Msg_type | Msg_text                      |
+----------------------+-------+----------+-------------------------------+
| buecher.shopProducts | check | warning  | Table is marked as crashed    |
| buecher.shopProducts | check | error    | Found 2142063 keys of 2142075 |
| buecher.shopProducts | check | error    | Corrupt                       |
+----------------------+-------+----------+-------------------------------+

+---------------------+
| version()           |
+---------------------+
| 5.0.32-Debian_3-log |
+---------------------+

Linux version 2.6.8-12-amd64-k8-smp (buildd@bester) (gcc version 3.4.4 20050314 (prerelease) (Debian 3.4.3-13sarge1)) #1 SMP Thu Dec 7 18:44:52 UTC 2006
[22 Feb 2007 18:28] Ingo Strüwing
While the problem does not seem to be deterministic, it is still _not_ related to concurrency.

I repeated the problem several times on
blade08        (Dual Xeon    3.0GHz) ~  5 min
sol10-amd64-a  (Dual Opteron 1.8GHz) ~ 10 min
quadita2       (Quad Itanium 1.3GHz) ~ 15 min
Other machines needed much longer or failed to repeat at all.
The above times were quite constant over several runs, so this seemed to make a concurrency problem somewhat unlikely.

After the above I disabled the key cache with --key_buffer_size=0. Unfortunately it made no difference. My patch for Bug#17332 does not help.

Then I added --skip-concurrent-insert to be sure that concurrent inserts are disabled (they are disabled implicitly for tables with rtree indexes anyway). It didn't help either. This means that I disabled everything that could lead to concurrency within MyISAM, as far as I know.

Finally I reduced the number of test threads to 1. Again the corruptions appeared, even within about the same times.

So I conclude that this is not a concurrency problem. This should improve the chance to locate the bug.
[24 Feb 2007 10:17] Shane Bester
Ingo, I have a 4MB testcase:

>mysql -uroot test <..\client_release\bug25673.sql
ERROR 126 (HY000) at line 69203: Incorrect key file for table '.\test\t1.MYI'; try to repair it

I expect to be able to get it down to a few kb, and will upload what I have later today.
[24 Feb 2007 11:34] Shane Bester
and here's the promised testcase. simply import using command line client

Attachment: bug25673.zip (application/zip, text), 207.97 KiB.

[25 Feb 2007 5:05] Shane Bester
a final version of testcase, 538 lines long!!!

Attachment: bug25673_reduced.sql (application/octet-stream, text), 54.33 KiB.

[25 Feb 2007 5:53] Shane Bester
same testcase as bug25673_reduced.sql except multirow insert and less indexes are used.

Attachment: bug25673_tiny.sql (application/octet-stream, text), 34.54 KiB.

[1 Mar 2007 20:26] Ingo Strüwing
This is a bug in the rtree index code. According to Guttman's algorithm, page underflow is handled by storing the page in a list for later re-insertion. The keys from the stored pages have to be inserted into the remaining pages of the same level of the tree. Hence the level number is stored in the re-insertion list together with the page.

In the MySQL RTree implementation the level counts from zero at the root page, increasing numbers for levels down the tree.

If during re-insertion of the keys the tree height grows, all level numbers become invalid. The remaining keys will be inserted at the wrong level.

The problem exists since version 5.0.x.
[2 Mar 2007 20:08] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/21058

ChangeSet@1.2417, 2007-03-02 21:07:44+01:00, istruewing@chilla.local +5 -0
  Bug#25673 - spatial index corruption, error 126
              incorrect key file for table
  
  In certain cases it could happen that deleting a row could
  corrupt an RTREE index.
  
  According to Guttman's algorithm, page underflow is handled
  by storing the page in a list for later re-insertion. The
  keys from the stored pages have to be inserted into the
  remaining pages of the same level of the tree. Hence the
  level number is stored in the re-insertion list together
  with the page.
  
  In the MySQL RTree implementation the level counts from zero
  at the root page, increasing numbers for levels down the tree.
  
  If during re-insertion of the keys the tree height grows, all
  level numbers become invalid. The remaining keys will be
  inserted at the wrong level.
  
  The fix is to increment the level numbers stored in the
  reinsert list after a split of the root block during reinsertion.
[2 Mar 2007 21:47] Ingo Strüwing
Some comments on rtree index structures and algorithmns.

Attachment: rtree-indexes.txt (text/plain), 6.42 KiB.

[5 Mar 2007 12:38] Sergey Vojtovich
I vote for push.
[8 Mar 2007 8:55] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/21465

ChangeSet@1.2607, 2007-03-08 09:54:37+01:00, istruewing@chilla.local +5 -0
  Bug#25673 - spatial index corruption, error 126
            incorrect key file for table
  
  In certain cases it could happen that deleting a row could
  corrupt an RTREE index.
  
  According to Guttman's algorithm, page underflow is handled
  by storing the page in a list for later re-insertion. The
  keys from the stored pages have to be inserted into the
  remaining pages of the same level of the tree. Hence the
  level number is stored in the re-insertion list together
  with the page.
  
  In the MySQL RTree implementation the level counts from zero
  at the root page, increasing numbers for levels down the tree.
  
  If during re-insertion of the keys the tree height grows, all
  level numbers become invalid. The remaining keys will be
  inserted at the wrong level.
  
  The fix is to increment the level numbers stored in the
  reinsert list after a split of the root block during reinsertion.
[8 Mar 2007 11:09] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/21474

ChangeSet@1.2418, 2007-03-08 12:08:59+01:00, istruewing@chilla.local +1 -0
  Bug#25673 - spatial index corruption, error 126 incorrect key file for table
  After merge fix
[8 Mar 2007 18:22] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/21533

ChangeSet@1.2608, 2007-03-08 19:22:43+01:00, istruewing@chilla.local +1 -0
  Bug#25673 - spatial index corruption, error 126 incorrect key file for table
  After backport fix.
  Added forgotten DBUG_RETURNs, which was detected in 5.1 only.
[9 Mar 2007 17:40] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/21622

ChangeSet@1.2609, 2007-03-09 16:19:42+01:00, istruewing@chilla.local +1 -0
  Bug#25673 - spatial index corruption, error 126 incorrect key file for table
  Fixed a compiler warning, deteced by pushbuild only.
[10 Mar 2007 17:38] Ingo Strüwing
Queued to 5.1-engines, 5.0-engines, and 4.1-engines.
[14 Mar 2007 8:53] Sergey Vojtovich
Fixed in 4.1.23, 5.0.38, 5.1.17.
[15 Mar 2007 2:46] Paul Dubois
Noted in 4.1.23, 5.0.38, 5.1.17 changelogs.

n certain cases it could happen that deleting a row corrupted an
RTREE index. This affected indexes on spatial columns.