Bug #14400 Query joins wrong rows from table which is subject of "concurrent insert"
Submitted: 27 Oct 2005 16:15 Modified: 22 Sep 2006 15:27
Reporter: Alexander Keremidarski Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: MyISAM storage engine Severity:S2 (Serious)
Version:3.23, 4.0, 4.1, 5.0 OS:Any (any)
Assigned to: Ingo Strüwing

[27 Oct 2005 16:15] Alexander Keremidarski
Description:
When there is INSERT and SELECT running in parallel and "concurrent insert" is possible SELECT may join wrong rows.

The query is:
SELECT t1.x AS x1, t2.x AS x2  
FROM t1, t2 
WHERE t1.x = t2.x;

Under the conditions described above the result of the query contains rows for which 
t1.x != t2.x

The easiest way to demonstrate this is with:
SELECT t1.x AS x1, t2.x AS x2  
FROM t1, t2 
WHERE t1.x = t2.x
HAVING t1.x != t2.x;

It is obvious that this query should result in Empty set regardless of the data!
However:

 SELECT t1.x AS x1, t2.x AS x2  FROM t1, t2 WHERE t1.x = t2.x HAVING t1.x != t2.x;
+------------+------------+
| x1         | x2         |
+------------+------------+
| test051846 | test051887 |
| test055122 | test055757 |
| test056859 | test057202 |

...

| test098695 | test098809 |
| test099165 | test099408 |
| test099669 | test099800 |
+------------+------------+
40 rows in set (5.89 sec)

Note that HAVING clause is only to simplify the test case! 

The same can be observed with comparing the values in result of:

SELECT t1.x AS x1, t2.x AS x2  FROM t1, t2 WHERE t1.x = t2.x;

All false matches happen with values where first 7 characters are the same. I couldn't observe any case with difference before 8th character.

The bug only happens with Optimized MyISAM tables and never if there are deleted rows which is strong indication that Concurrent insert is involved.

The tables are as simple as:

CREATE TABLE `t1` (
  `x` varchar(250) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

CREATE TABLE `t2` (
  `x` varchar(250) NOT NULL,
  PRIMARY KEY  (`x`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

Character set does not seem to be relevant. Same with utf8 

How to repeat:
Download the testcase.sql.bz2 and import it.

It will create the tables and will INSERT into t1 with values from 'test000001' to 'test099999'
( I wasn't able to reproduce the bug with less rows in t1! )

Run INSERT INTO t2 in a loop. I am using this one line bash script:

$ while true; do mysql test -e "INSERT IGNORE INTO t2 VALUES(CONCAT('test', LPAD(ROUND(RAND()*100000), 6, 0)))"; done

While the insert loop is running try:
SELECT t1.x AS x1, t2.x AS x2  
FROM t1, t2 
WHERE t1.x = t2.x
HAVING t1.x != t2.x;

Observe the wrong non-empty result.
[27 Oct 2005 16:16] Alexander Keremidarski
mysqldump generated script

Attachment: testcase.sql.bz2 (application/x-bzip, text), 96.05 KiB.

[2 Jun 2006 16:20] Ingo Strüwing
My test script

Attachment: bug14400-1.sh (application/x-sh, text), 5.31 KiB.

[7 Jun 2006 11:11] 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/7348
[7 Jun 2006 12:33] Ingo Strüwing
My final test script. It can repeat the problem now.

Attachment: bug14400-1.sh (application/x-sh, text), 8.09 KiB.

[7 Jun 2006 14:05] 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/7356
[28 Jun 2006 16:56] 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/8424
[6 Jul 2006 13:50] Ingo Strüwing
Pushed to mysql-5.1-engines.
[6 Jul 2006 16:23] Ingo Strüwing
Pushed to mysql-5.0-engines.
[8 Jul 2006 19:44] Ingo Strüwing
It was possible that fetching a record by an exact key value 
  (including the record pointer) could return a record with a 
  different key value. This happened only if a concurrent insert 
  added a record with the searched key value after the fetching 
  statement locked the table for read.
  
  The search succeded on the key value, but the record was
  rejected as it was past the file length that was remembered
  at start of the fetching statement. With other words it was 
  rejected as being a concurrently inserted record.
  
  The action to recover from this problem was to fetch the 
  record that is pointed at by the next key of the index. 
  This was repeated until a record below the file length was 
  found.
  
  I do now avoid this loop if an exact match was searched. 
  If this match is beyond the file length, it is now treated 
  as "key not found". There cannot be another key with the 
  same record pointer.

Pushed to 5.1.12 and 5.0.24 and 4.1.21 and 4.0.28.
[11 Jul 2006 9:18] MC Brown
Documented in the 4.0, 4.1, 5.0 and 5.1 changelogs:

Using <literal>SELECT</literal> and a table join while running a concurrent <literal>INSERT</literal> operation would join incorrect rows. (Bug #14400)
[13 Jul 2006 3:31] Paul Dubois
5.0.x fix went to 5.0.25 instead.
[10 Aug 2006 19:54] Michael Widenius
Unfortunately the last patch did not fix the problem correctly
Have now pushed a patch (+ test case) in 4.0 that will fix this.
(Fix will be merged to 4.1, 5.0 and 5.1 shortly)
[29 Aug 2006 18:45] 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/11021

ChangeSet@1.2183, 2006-08-29 20:45:04+02:00, istruewing@chilla.local +3 -0
  Bug#14400 - Query joins wrong rows from table which is
              subject of "concurrent insert"
  Better fix by Monty: "The previous bug fix didn't work
  when using partial keys."
[7 Sep 2006 13:39] 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/11544

ChangeSet@1.2184, 2006-09-07 15:39:31+02:00, istruewing@chilla.local +3 -0
  Bug#14400 - Query joins wrong rows from table which is subject of
              "concurrent insert"
  Additional fix for full keys and test case.
[14 Sep 2006 14:17] 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/11945

ChangeSet@1.2546, 2006-09-14 16:17:14+02:00, istruewing@chilla.local +1 -0
  Bug#14400 - Query joins wrong rows from table which is subject of
              "concurrent insert"
  After merge fix.
[21 Sep 2006 7:52] Ingo Strüwing
Pushed the final set of fixes to 5.1.12.
[21 Sep 2006 17:09] Ingo Strüwing
Pushed the final set of fixes to 5.0.26.
[22 Sep 2006 12:34] Ingo Strüwing
Pushed the final set of fixes to 4.1.22.
[22 Sep 2006 15:23] 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/12411

ChangeSet@1.2195, 2006-09-22 17:23:25+02:00, istruewing@chilla.local +1 -0
  Bug#14400 - Query joins wrong rows from table which is subject of
              "concurrent insert"
  After merge fix.
[22 Sep 2006 15:25] Ingo Strüwing
Pushed the final set of fixes to 4.0.28.
[22 Sep 2006 15:27] Ingo Strüwing
I think no further documentation is required as the later fixes fix possible problems which were not mentioned in the bug report.