Bug #37721 ORDER BY when WHERE contains non-partitioned index column
Submitted: 28 Jun 2008 16:57 Modified: 10 Nov 2008 15:18
Reporter: duke hound Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Partitions 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 CPU Architecture:Any
Tags: non-partitioned index, order by, sort, where
Triage: Triaged: D2 (Serious) / R2 (Low) / E3 (Medium)

[28 Jun 2008 16:57] duke hound
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).
[28 Jun 2008 17:40] Sveta Smirnova
Thank you for the report.

Verified as described. Bug is not repeatable if use MyISAM storage engine.
[5 Aug 2008 14:54] Konstantin Osipov
Setting risk/effort, and the right lead, since the bug seems to be in the optimizer.
[16 Sep 2008 13:02] Joe Grasse
Same thing happens with the range partition type. Also, curious if this will be fixed before the GA of 5.1?
[30 Sep 2008 12:16] Mattias Jonsson
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.
[3 Oct 2008 18:26] 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/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.
[3 Oct 2008 18:30] Mattias Jonsson
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
[10 Oct 2008 17:06] Mattias Jonsson
New proposed patch, incl. comments, the commit mail got lost...

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

[30 Oct 2008 8:12] Mattias Jonsson
Pushed into 6.0-bugteam and 5.1-bugteam
[10 Nov 2008 10:54] Bugs System
Pushed into 6.0.8-alpha  (revid:mattias.jonsson@sun.com-20081010100101-cahpb979obu0pr2y) (version source revid:mattias.jonsson@sun.com-20081029223410-bm7llueahyz96nj0) (pib:5)
[10 Nov 2008 11:37] Bugs System
Pushed into 5.1.30  (revid:mattias.jonsson@sun.com-20081010100101-cahpb979obu0pr2y) (version source revid:mattias.jonsson@sun.com-20081029220141-coyup0ey28z66pxn) (pib:5)
[10 Nov 2008 15:18] Jon Stephens
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.
[10 Nov 2008 15:20] Jon Stephens
5.1 fix will appear in 5.1.31 per mail from Joro. Adjusted changelog entry accordingly.
[19 Jan 2009 11:26] Bugs System
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)
[19 Jan 2009 13:04] Bugs System
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)
[19 Jan 2009 16:10] Bugs System
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)