MySQL Bugs: #37721: ORDER BY when WHERE contains non-partitioned index column

Bug #37721	ORDER BY when WHERE contains non-partitioned index column
Submitted:	28 Jun 2008 18:57	Modified:	10 Nov 2008 16:18
Reporter:	duke hound
Status:	Closed
Category:	Server: Partition	Severity:	S3 (Non-critical)
Version:	5.1,6.0.4-alpha,6.0 BZR	OS:	Any (Linux, MS Windows xp pro 2002 sp3 AMD athlon 2600+ 2.13ghz 480 MB ram)
Assigned to:	Mattias Jonsson	Target Version:	5.1.31
Tags:	sort, non-partitioned index, where, order by
Triage:	Triaged: D2 (Serious) / R2 (Low) / E3 (Medium)

Description:
Before I reported this as a bug I wanted to check with the community.  
The original post was at forum,
http://forums.mysql.com/read.php?106,215325,215647#msg-215647 where it was confirmed as a
bug by a MySQL Software Engineer.

I am using windows xp sp2, v6.0.4-alpha

When one partitions a table and searches on an index not in the partition expression the
ORDER BY clause causes the server to not sort the result after retrieving the rows from
the partitioned table.  It does, however, sort the results on a per partition basis rather
than on a per partitioned table basis.

How to repeat:
[code]
CREATE DATABASE bug;
CREATE TABLE bug.t (t_a BIGINT,t_b BIGINT, PRIMARY KEY (t_a), INDEX (t_b) ) ENGINE =
InnoDB PARTITION BY HASH( MOD(t_a,2) ) PARTITIONS 2;
INSERT INTO bug.t VALUES (0,0),(1,0);
SELECT * FROM bug.t WHERE t_b=0 ORDER BY t_a DESC;

+-----+------+
| t_a | t_b  |
+-----+------+
|   0 |    0 |
|   1 |    0 |
+-----+------+

2 rows in set (0.00 sec)
[/code]

I expected:
[code]
+-----+------+
| t_a | t_b  |
+-----+------+
|   1 |    0 |
|   0 |    0 |
+-----+------+
2 rows in set (0.00 sec)
[/code]
This is more than just a switch from DESC to ASC as described in this bug post for ndb
tables:
http://bugs.mysql.com/bug.php?id=33061

To further show this distinction execute the following:
[Continuing with the above SQL statements]
[code]
INSERT IGNORE INTO bug.t VALUES (0,0),(1,0),(2,0),(3,0);
SELECT * FROM bug.t WHERE t_b=0 ORDER BY t_a DESC;

+-----+------+
| t_a | t_b  |
+-----+------+
|   2 |    0 |
|   0 |    0 |
|   3 |    0 |
|   1 |    0 |
+-----+------+
4 rows in set (0.00 sec)
[/code]
I expected:
[code]
+-----+------+
| t_a | t_b  |
+-----+------+
|   3 |    0 |
|   2 |    0 |
|   1 |    0 |
|   0 |    0 |
+-----+------+
4 rows in set (0.00 sec)
[/code]
Note: It does order by correctly on a per partition basis rather than on a whole table
basis.

This is more than just an issue with the DESC flag as seen by,
[code]
SELECT * FROM bug.t WHERE t_b=0 ORDER BY t_a;
+-----+------+
| t_a | t_b  |
+-----+------+
|   0 |    0 |
|   2 |    0 |
|   1 |    0 |
|   3 |    0 |
+-----+------+
4 rows in set (0.00 sec)

SELECT * FROM bug.t WHERE t_b=0 ORDER BY t_a ASC;
+-----+------+
| t_a | t_b  |
+-----+------+
|   0 |    0 |
|   2 |    0 |
|   1 |    0 |
|   3 |    0 |
+-----+------+
[/code]
I expected from both of the above:
[code]
+-----+------+
| t_a | t_b  |
+-----+------+
|   0 |    0 |
|   1 |    0 |
|   2 |    0 |
|   3 |    0 |
+-----+------+
[/code]

Note: I do not experience this issue if I remove the WHERE clause;

Note: I do not experience this issue if I remove the INDEX (t_b) and retain the where
clause;
[code]
ALTER TABLE bug.t DROP INDEX t_b;
SELECT * FROM bug.t WHERE t_b=0 ORDER BY t_a;
+-----+------+
| t_a | t_b  |
+-----+------+
|   0 |    0 |
|   1 |    0 |
|   2 |    0 |
|   3 |    0 |
+-----+------+
4 rows in set (0.00 sec)
[/code]
I expected the above result.
[code]
SELECT * FROM bug.t WHERE t_b=0 ORDER BY t_a DESC;
+-----+------+
| t_a | t_b  |
+-----+------+
|   3 |    0 |
|   2 |    0 |
|   1 |    0 |
|   0 |    0 |
+-----+------+
4 rows in set (0.00 sec)
[/code]
I expected the above result.

Note: I have not tested with other partition types other than HASH

Suggested fix:
When one partitions a table and searches on an index not in the partition expression, that
ORDER BY searches work on the entire table, rather than on a per partition basis. (in
effect merging the query results of the individual partitions).

Thank you for the report.

Verified as described. Bug is not repeatable if use MyISAM storage engine.

Setting risk/effort, and the right lead, since the bug seems to be in the optimizer.

Same thing happens with the range partition type. Also, curious if this will be fixed
before the GA of 5.1?

This is probably due to key_rec_cmp does only sort for the given index, but for clustered
primary key it should also on second level (if key for given index is equal) sort by
primary key.

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

2751 Mattias Jonsson	2008-10-03
      Bug#37721: ORDER BY when WHERE contains non-partitioned
      index column
      
      There was actually two problems
      1) when clustered pk, order by non pk index should also
      compare with pk as last resort to differ keys from each
      other
      2) bug in the index search handling in ha_partition (was
      found when extending the test case
      
      Solution to 1 was to include the pk in key compare if
      clustered pk and search on other index.
      
      2 was just a faulty compare of key_length.

I also fixed the following bug in the patch (faulty key_length compare):
CREATE TABLE t1 (
a INT,
b INT,
PRIMARY KEY (a),
INDEX (b))
ENGINE InnoDB
PARTITION BY HASH(a)
PARTITIONS 3;
INSERT INTO t1 VALUES (0,0),(4,0),(2,0);
SELECT a FROM t1 WHERE b = 0 ORDER BY a ASC;
a
0
4
2

New proposed patch, incl. comments, the commit mail got lost...

Attachment: b37721.patch.tar.gz (application/x-gzip, text), 4.91 KiB.

Pushed into 6.0-bugteam and 5.1-bugteam

Pushed into 6.0.8-alpha  (revid:mattias.jonsson@sun.com-20081010100101-cahpb979obu0pr2y)
(version source revid:mattias.jonsson@sun.com-20081029223410-bm7llueahyz96nj0) (pib:5)

Pushed into 5.1.30  (revid:mattias.jonsson@sun.com-20081010100101-cahpb979obu0pr2y)
(version source revid:mattias.jonsson@sun.com-20081029220141-coyup0ey28z66pxn) (pib:5)

Documented bugfix in the 5.1.30 and 6.0.8 changelogs as follows:

        When executing an ORDER BY query on a partitioned InnoDB table using an
        index that was not in the partition expression, the results were sorted
        on a per-partition basis rather than for the table as a whole.

5.1 fix will appear in 5.1.31 per mail from Joro. Adjusted changelog entry accordingly.

Pushed into 5.1.31-ndb-6.2.17 (revid:tomas.ulin@sun.com-20090119095303-uwwvxiibtr38djii)
(version source revid:tomas.ulin@sun.com-20090108105244-8opp3i85jw0uj5ib) (merge vers:
5.1.31-ndb-6.2.17) (pib:6)

Pushed into 5.1.31-ndb-6.3.21 (revid:tomas.ulin@sun.com-20090119104956-guxz190n2kh31fxl)
(version source revid:tomas.ulin@sun.com-20090119104956-guxz190n2kh31fxl) (merge vers:
5.1.31-ndb-6.3.21) (pib:6)

Pushed into 5.1.31-ndb-6.4.1 (revid:tomas.ulin@sun.com-20090119144033-4aylstx5czzz88i5)
(version source revid:tomas.ulin@sun.com-20090119144033-4aylstx5czzz88i5) (merge vers:
5.1.31-ndb-6.4.1) (pib:6)