MySQL Bugs: #16168: execute the same queries, however the results are different

Bug #16168	execute the same queries, however the results are different
Submitted:	3 Jan 2006 22:59	Modified:	4 Jul 2006 8:53
Reporter:	Allen Weng	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0.17/5.0.19 BK/4.1.17 BK	OS:	Any (all)
Assigned to:	Sergey Petrunya	CPU Architecture:	Any

Description:
create 2 tables, same sturcture, compund keys, one with 102 rows and one with 23 rows

(these 23 rows are in the 102 rows also)

execute the following same queries, however the results are different

the 102-rows-table will return the empty result set, and the 23-rows-table will have the correct result. (1 row) 

I will attach the sql file to create tables then.

How to repeat:
create these 2 tables, excute the sql query and see the result

Suggested fix:
something wrong with the optimized query as compound keys existed in a table with certain amount of rows?

create tables and insert data

Attachment: 16168.sql (application/octet-stream, text), 14.77 KiB.

forget the query...  

SELECT * FROM TABLENAME
WHERE ((((pk4 =0) AND (pk1 =2621) AND (pk2 =2635)))
OR ((pk4 =1) AND (((pk1 IN ( 7, 2, 1 ))) OR (pk1 =522)) AND ((pk2 IN ( 0, 2635 ))))
)
AND (pk3 >=1000000)

Thank you for the bug report.

mysql> show tables;
+---------------+
| Tables_in_db8 |
+---------------+
| table102_1    |
| table23_1     |
+---------------+
2 rows in set (0.00 sec)

mysql> SELECT * FROM table102_1
    -> WHERE ((((pk4 =0) AND (pk1 =2621) AND (pk2 =2635)))
    -> OR ((pk4 =1) AND (((pk1 IN ( 7, 2, 1 ))) OR (pk1 =522)) AND ((pk2 IN ( 0, 2635
    -> ))))
    -> )
    -> AND (pk3 >=1000000)\G
Empty set (0.02 sec)

mysql> SELECT * FROM table23_1
    -> WHERE ((((pk4 =0) AND (pk1 =2621) AND (pk2 =2635)))
    -> OR ((pk4 =1) AND (((pk1 IN ( 7, 2, 1 ))) OR (pk1 =522)) AND ((pk2 IN ( 0, 2635
    -> ))))
    -> )
    -> AND (pk3 >=1000000)\G
*************************** 1. row ***************************
            pk1: 2621
            pk2: 2635
            pk3: 1000015
            pk4: 0
           col5: 1
           col6: 0
           col7: 1
           col8: 1
           col9: 1
          col10: 0
          col11: 1
          col12: 0
          col13: 1
          col14: 0
          col15: 0
          col16: 2
transactiondate: 2005-12-28 13:18:08
1 row in set (0.01 sec)

mysql> alter table table102_1 engine=MyISAM;
Query OK, 102 rows affected (0.04 sec)
Records: 102  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM table102_1
    -> WHERE ((((pk4 =0) AND (pk1 =2621) AND (pk2 =2635)))
    -> OR ((pk4 =1) AND (((pk1 IN ( 7, 2, 1 ))) OR (pk1 =522)) AND ((pk2 IN ( 0, 2635
    -> ))))
    -> )
    -> AND (pk3 >=1000000)\G
Empty set (0.00 sec)

mysql> alter table table102_1 drop primary key;
Query OK, 102 rows affected (0.03 sec)
Records: 102  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM table102_1
    -> WHERE ((((pk4 =0) AND (pk1 =2621) AND (pk2 =2635)))
    -> OR ((pk4 =1) AND (((pk1 IN ( 7, 2, 1 ))) OR (pk1 =522)) AND ((pk2 IN ( 0, 2635
    -> ))))
    -> )
    -> AND (pk3 >=1000000)\G
*************************** 1. row ***************************
            pk1: 2621
            pk2: 2635
            pk3: 1000015
            pk4: 0
           col5: 1
           col6: 0
           col7: 1
           col8: 1
           col9: 1
          col10: 0
          col11: 1
          col12: 0
          col13: 1
          col14: 0
          col15: 0
          col16: 2
transactiondate: 2005-12-28 13:18:08
1 row in set (0.00 sec)

mysql> select version();
+--------------+
| version()    |
+--------------+
| 5.0.19-debug |
+--------------+
1 row in set (0.00 sec)

mysql> 

060104  8:53:42 [Note] libexec/mysqld: ready for connections.
Version: '5.0.19-debug'  socket: '/tmp/mysql.sock'  port: 3306  Source distribution
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79c80, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79d50, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79dc0, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79968, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79c80, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79d50, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79dc0, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79968, 5 should be 8
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79f98, 1 should be 4
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79fd0, 1 should be 4
060104  8:54:35 [Warning] Wrong use count: 2 (should be 1) for tree at 0x8e79c80
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e7a008, 1 should be 4
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e7a040, 1 should be 4
060104  8:54:35 [Warning] Wrong use count: 2 (should be 1) for tree at 0x8e79d50
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79dc0, 0 should be 3
060104  8:54:35 [Note] Use_count: Wrong count for key at 0x8e79ad8, 0 should be 3

miguel@hegel:~/dbs/4.1> libexec/mysqld
060104  8:55:52  InnoDB: Started; log sequence number 0 44089
libexec/mysqld: ready for connections.
Version: '4.1.17-debug-log'  socket: '/tmp/mysql.sock'  port: 3306  Source distribution
060104  8:56:26 [Note] Use_count: Wrong count for key at 8ca9328, 5 should be 8
060104  8:56:26 [Note] Use_count: Wrong count for key at 8ca9398, 5 should be 8
060104  8:56:26 [Note] Use_count: Wrong count for key at 8ca9408, 5 should be 8
060104  8:56:26 [Note] Use_count: Wrong count for key at 8ca8d58, 5 should be 8

mysql> SELECT * FROM table102_1
    -> WHERE ((((pk4 =0) AND (pk1 =2621) AND (pk2 =2635)))
    -> OR ((pk4 =1) AND (((pk1 IN ( 7, 2, 1 ))) OR (pk1 =522)) AND ((pk2 IN ( 0, 2635
    -> ))))
    -> )
    -> AND (pk3 >=1000000)\G
Empty set (0.01 sec)

mysql> alter table table102_1 drop primary key;
Query OK, 102 rows affected (0.03 sec)
Records: 102  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM table102_1
    -> WHERE ((((pk4 =0) AND (pk1 =2621) AND (pk2 =2635)))
    -> OR ((pk4 =1) AND (((pk1 IN ( 7, 2, 1 ))) OR (pk1 =522)) AND ((pk2 IN ( 0, 2635
    -> ))))
    -> )
    -> AND (pk3 >=1000000)\G
*************************** 1. row ***************************
            pk1: 2621
            pk2: 2635
            pk3: 1000015
            pk4: 0
           col5: 1
           col6: 0
           col7: 1
           col8: 1
           col9: 1
          col10: 0
          col11: 1
          col12: 0
          col13: 1
          col14: 0
          col15: 0
          col16: 2
transactiondate: 2005-12-28 13:18:08
1 row in set (0.00 sec)

mysql> select version();
+------------------+
| version()        |
+------------------+
| 4.1.17-debug-log |
+------------------+
1 row in set (0.00 sec)

mysql>

See bug: http://bugs.mysql.com/bug.php?id=16249

The cause of the problem lies within the range optimizer.
The generated list of ranges doesn't cover all intervals that will satisfy the table condition.

The generated list of ranges is:
1/0   /1000000/1 <= X <= 1/0
1/2635/1000000/1 <= X <= 1/2635

2/0   /1000000/1 <= X <= 2/0
2/2635/1000000/1 <= X <= 2/2635

7/0   /1000000/1 <= X <= 7/0
7/2635/1000000/1 <= X <= 7/2635

522/0  /1000000/1 <= X <= 522/0
522/2635/1000000/1 <= X <= 522/2635

This interval is missing:
2621/2635/1000000/1 <= X <= 2621/2635

The interval is lost during the last "AND" operation.

SEL_ARG-graph representation for condition
cond1 = 
  (pk1=2621 AND              pk2=2635         AND pk4=0) OR 
  (pk1 IN (7, 2, 1, 552) AND pk2 IN (0, 2635) AND pk4=1)

is correct (not counting the SEL_ARG::use_count fields, didnt check those).

The interval is lost during calculation of SEL_ARG-graph representation of 

  cond1 AND (pk3 >=1000000)

SEL-ARG representation of cond1 can be viewed as

  cond1= 
    cond1_1 OR 
    ...
    cond1_8 OR 
    (pk1,pk2,pk4)= (2621,2635,0)

Calculation of "cond1 AND (pk3 >=1000000)" proceeds as follows:

for each disjunct C_i in cond1
{
  C_i = a-representation-of( C_i AND (pk3 >=1000000) )
}

The problem is that instead of calculating

   ((pk1,pk2,pk4)=(2621,2635,0)) AND (pk3 >=1000000)

We really try to calculate 

   ((pk1,pk2,pk4)=(2621,2635,0))  AND (pk3 >=1000000 AND somecond(pk4) )

and lose an interval. The cause seems to be that at some earlier step we think that SEL_ARG(pk3 >=1000000) is not going to be shared and change it. Then at the last step we assume that it has not been changed.

*Perhaps* this is caused by incorrect SEL_ARG reference counting.

The SEL_ARG graph SG1 generated for this part of the WHERE clause:

  (pk1=2621 AND pk2=2635 AND pk4=0) OR 
  (pk1 IN (7, 2, 1) OR pk1=522) AND pk2 IN (0, 2635) AND pk4=1

is incorrect in two ways:
 1. There are 3 identical RB-trees that represent "pk2=0 OR pk2=2635" (those are "copies" of one "original" tree(*)) In those trees, the root SEL_ARG has elements==1. 

 2. SEL_ARG representing "pk4=1" has use_count==5 instead of 8.

#2 seems to be a consequence of #1. 

If one manually "fixes" SG1 right after it is produced, the query result will be correct. So the bug will probably be fixed if we make fix construction of SG1.

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/8531

The fix has been pushed to 4.1.21 and 5.0.24 trees.

Notes for the changelog:
The bug showed up on a certain kind of complicated WHERE clauses that include conditions on multi-part keys with #keyparts>2.
The bug effects were wrong query results and "[Note] Use_count: Wrong count for key at..." messages in server stderr.

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 bug fix. More information about accessing the source trees is available at

    http://www.mysql.com/doc/en/Installing_source_tree.html

Documented bugfix in 4.1.21 and 5.0.24 changelogs.

5.0.x fix went to 5.0.25 instead.