Bug #84107 Severe slowdown on partitioned table with simple ORDER BY ASC change to DESC
Submitted: 8 Dec 2016 11:15 Modified: 19 Dec 2016 2:49
Reporter: Atsushi Nakagawa Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Partitions Severity:S3 (Non-critical)
Version:5.7.16 OS:Any
Assigned to: CPU Architecture:Any

[8 Dec 2016 11:15] Atsushi Nakagawa
Description:
We have noticed that a seemingly simple query takes order of magnitudes more time to complete when an ORDER BY condition is changed from ASC to DESC.  Comparing 'explain' for both queries show identical plans.

A minimal test case is included under "How to repeat".  Here are few things I noticed while creating the minimal test case:

* The table must be partitioned to reproduce. (The number of partitions may not matter.)
* A third column ('z' below) is required and must be included in the SELECT statement.
* The query needn't result in any rows for the slow down to occur.
* A PRIMARY KEY wasn't required to reproduce so was removed.
* Data types were originally bigint and datetime but were all changed to 'int' for simplicity.  NOT NULL conditions were also removed.

Execution plan for both the ASC and DESC queries are:

+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-----------------------+
| id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | test  | p0         | range | x             | x    | 8       | NULL |    1 |   100.00 | Using index condition |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-----------------------+

How to repeat:
DROP TABLE test;
CREATE TABLE test
( x int
, y int
, z int
, KEY (x, y)
) ENGINE=InnoDB PARTITION BY HASH (x) PARTITIONS 8;

insert into test select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999), FLOOR(RAND() * 9999) from dual;

# The following should be run multiple times to create LOTS of rows
# (With my setup, the problem is pronounced enough to notice after 1mil rows:  0.04 sec vs 0.00 sec)
insert into test select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999), FLOOR(RAND() * 9999) from test;
insert into test select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999), FLOOR(RAND() * 9999) from test;
insert into test select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999), FLOOR(RAND() * 9999) from test;
insert into test select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999), FLOOR(RAND() * 9999) from test;
insert into test select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999), FLOOR(RAND() * 9999) from test;

# This returns near instantaneously
select z from test where x = 90000 and y >= 50000 and y < 60000 order by y ASC;

# This takes significantly more time to complete
select z from test where x = 90000 and y >= 50000 and y < 60000 order by y DESC;

# These return near instantaneously
select z from test where x = 90000 and y >= 50000 and y < 60000 order by y+0 DESC;
select z from test where x = 90000 and y >= 50000 and y < 60000 order by -y ASC;
select z from test where x = 90000 and y >= 50000 and y < 60000 order by y DESC, z;
select x, y from test where x = 90000 and y >= 50000 and y < 60000 order by y DESC;
[8 Dec 2016 17:36] Miguel Solorzano
Please read: https://bugs.mysql.com/bug.php?id=13375. Thanks.
[9 Dec 2016 16:28] Sinisa Milivojevic
Hi,

First of all, ORDER-ing by expressions like y+0 or -y is totally different beast and it is THOROUGHLY described in our manual. Now, regarding the results between ASC and DESC.

I have done some minor changes in your script and got different results. 

Here is the script:

DROP TABLE IF EXISTS test_part_asc;
CREATE TABLE test_part_asc ( x int, y int, z int, KEY (x, y)) ENGINE=InnoDB PARTITION BY HASH (x) PARTITIONS 8;

insert into test_part_asc select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999),FLOOR(RAND() * 9999) from dual;

insert into test_part_asc select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999),FLOOR(RAND() * 9999) from test_part_asc;
insert into test_part_asc select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999),FLOOR(RAND() * 9999) from test_part_asc;
insert into test_part_asc select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999),FLOOR(RAND() * 9999) from test_part_asc;
insert into test_part_asc select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999),FLOOR(RAND() * 9999) from test_part_asc;
insert into test_part_asc select FLOOR(RAND() * 9999), FLOOR(RAND() * 9999),FLOOR(RAND() * 9999) from test_part_asc;

select z from test_part_asc where x = 90000 and y >= 50000 and y < 60000 order by y ASC;

select z from test_part_asc where x = 90000 and y >= 50000 and y < 60000 order by y DESC;

explain extended select z from test_part_asc where x = 90000 and y >= 50000 and y < 60000 order by y ASC;

explain extended select z from test_part_asc where x = 90000 and y >= 50000 and y < 60000 order by y DESC;

DROP TABLE IF EXISTS test_part_asc;

Results are different. Both of SELECTs are instantaneous, each take 0.00 seconds, and both return zero results. EXPLAINs return the same execution plan for both cases:

id      select_type     table   partitions      type    possible_keys   key     key_len ref     rows    filtered        Extra
1       SIMPLE  test_part_asc   p0      range   x       x       10      NULL    1       100.00  Using index condition
id      select_type     table   partitions      type    possible_keys   key     key_len ref     rows    filtered        Extra
1       SIMPLE  test_part_asc   p0      range   x       x       10      NULL    1       100.00  Using index condition

Hence, I did not repeat your results. So, check everything and let us have a proper test case that will return the results as you experienced them.
[12 Dec 2016 14:36] Sinisa Milivojevic
Your original "How to repeat" chapter has only this note:

"# The following should be run multiple times to create LOTS of rows"

I ran it 5 times. Now , you come with more precise instructions, while we already have run your test case. I hope you do understand that we can  not generate hundreds of millions of rows. There, the only problem in speed could be due to more reading or less cacheing of data on disk.
[12 Dec 2016 15:03] Sinisa Milivojevic
Hi,

We did some further investigation and came to the conclusion of why do you experience such a large difference in speed on huge data.

All InnoDB indices are strictly ascending. Hence, when sorting in ascending order, reading of indices is much faster then when descending ordering is demanded. There are plans to make it possible to have descending indices also. Those plans are elaborated in the WorkLog #1074. It is planned for the future, most probably in some of 8.* versions.

Thank you for your report.
[14 Dec 2016 14:10] Sinisa Milivojevic
Hi,

The last response that I  provided to you was fully sanctioned by the developer that is a leader of the development team that covers only this area of functionality. So much about the expertise ....
[16 Dec 2016 18:20] Sinisa Milivojevic
Hi!

You seem to have big problems with filing a bug related to your problems. You fail to provide sufficient information for any deduction or for any decent reproducible test case. 

You now come with the information that previous versions did not have that problem. I do not see the info on the speed of 5.6.23 anywhere in your posts. Can you provide info on the various speeds of ASC and DESC in 5.6 and 5.7 GA versions. Do note that 5.7.3 is not a GA version.

You are also totally missing the point.  The results of the four extra queries are only muddying the waters and hinder any diagnosis. Nobody needs such supporting information, although it did not confuse us at all, as we just ignored it.

The answer that you got on 12 Dec 15:03 was provided by the top developer who deals with optimizing queries with ASC and DESC ordering and was NOT provided by me.  

Regarding differences between 5.6 and 5.7, yes there are some regressions in the optimizer, but as I wrote to you, those will not be dealt with in 5.7. Regression is, very likely, caused by the fix of the bug #70001. After index pushdown is implemented for partitioned tables as well, then it could not be used any more for ordering in the desired directive. Hence, the regression, which will be fixed as I explained before.
[21 Dec 2016 10:50] Shane Bester
This looks like a duplicate of
http://bugs.mysql.com/bug.php?id=83470 ?