Bug #73386 for ranges, innodb doubles estimates, or caps estimates to half the table

• Submitted: 25 Jul 2014 8:57
• Reporter: Shane Bester (Platinum Quality Contributor)
• Status: Verified
• Category: MySQL Server: InnoDB storage engine
• Severity: S3 (Non-critical)
• Version: 5.6.21, 5.7.5
• OS: Any
• CPU Architecture: Any

[25 Jul 2014 8:57] Shane Bester

Description:
Reported by HarrisonF.

The code in btr_estimate_n_rows_in_range may cap the n_rows to half the table, 
or double the number.  This seems to be a rather arbitrary way to implement the algorithm.

Notice the testcase outputs indicated by <------

How to repeat:
drop table if exists t;
create table t (a serial) engine=innodb;
insert t values (),(),(),(),(),(),();
insert t select null from t,t a,t b,t c,t d,t e limit 100000;
optimize table t;analyze table t;

select count(*), min(a), max(a) from t;
explain select count(*) from t where a < 10;   -- estimate 
select count(*) from t where a < 10;           -- actual

explain select count(*) from t where a < 100;  -- estimate 
select count(*) from t where a < 100;          -- actual

explain select count(*) from t where a < 1000;  -- estimate 
select count(*) from t where a < 1000;          -- actual

explain select count(*) from t where a < 10000; -- estimate <------
select count(*) from t where a < 10000;         -- actual

explain select count(*) from t where a < 20000; -- estimate <------
select count(*) from t where a < 20000;         -- actual

explain select count(*) from t where a < 40000; -- estimate <------
select count(*) from t where a < 40000;         -- actual

explain select count(*) from t where a < 200000;-- estimate <-------
select count(*) from t where a < 200000;        -- actual

Suggested fix:
improve the algorithm so that arbitrary capping/doubling is not needed.

[25 Jul 2014 9:00] MySQL Verification Team

output from 5.7.5

Attachment: bug73386_5.7.5_output.txt (text/plain), 9.50 KiB.

[24 Aug 2015 13:45] Andrii Nikitin

Posted by developer:
 
Just for reference: I was able to reproduce as well in 5.1.63 , 5.5.25 , 5.5.45

[24 Aug 2015 13:58] Andrii Nikitin

Very similar (Most probably duplicate) bug #78192

[26 Jun 2020 11:25] MySQL Verification Team

https://bugs.mysql.com/bug.php?id=99998
https://bugs.mysql.com/bug.php?id=99997

[26 Jun 2020 12:24] MySQL Verification Team

This bug is the original of the following duplicate:

https://bugs.mysql.com/bug.php?id=99997