MySQL Bugs: #63320: innodb_stats_method=nulls

Bug #63320	innodb_stats_method=nulls_ignored work incorrectly
Submitted:	19 Nov 2011 0:33	Modified:	6 Jan 2012 7:50
Reporter:	Oleg Tsarev	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S2 (Serious)
Version:	5.1.59, 5.5.17	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
InnoDB collects statistics incorrectly when you setup option innodb_stats_method to nulls_ignored

How to repeat:
Get patch from attachment. Appliable both for 5.1.59 and 5.5.17

Test-cases

Attachment: stats_null.patch (text/x-patch), 5.19 KiB.

Logging: ./mysql-test-run  --force percona_stats_null_innodb percona_stats_null_myisam
111119  2:30:35 [Note] Plugin 'FEDERATED' is disabled.
MySQL Version 5.1.59
Checking supported features...
 - skipping ndbcluster
 - SSL connections supported
 - binaries are debug compiled
Collecting tests...
vardir: /storage/dev/percona/innodb_stats/debug/mysql-test/var
Removing old var directory...
Creating var directory '/storage/dev/percona/innodb_stats/debug/mysql-test/var'...
Installing system database...
Using server port 41724

==============================================================================

TEST                                      RESULT   TIME (ms)
------------------------------------------------------------

worker[1]  - 'localhost:13000' was not free
worker[1]  - 'localhost:13010' was not free
worker[1]  - 'localhost:13020' was not free
worker[1] Using MTR_BUILD_THREAD 303, with reserved ports 13030..13039
main.percona_stats_null_myisam           [ pass ]  10888
main.percona_stats_null_innodb           [ fail ]
        Test ended at 2011-11-19 02:31:06

CURRENT_TEST: main.percona_stats_null_innodb
--- /storage/dev/percona/innodb_stats/debug/mysql-test/r/percona_stats_null_innodb.result	2011-11-19 03:27:06.375140046 +0300
+++ /storage/dev/percona/innodb_stats/debug/mysql-test/r/percona_stats_null_innodb.reject	2011-11-19 03:31:06.433990538 +0300
@@ -15,4 +15,17 @@
 ANALYZE TABLE t;
 Table	Op	Msg_type	Msg_text
 test.t	analyze	status	OK
+Failed with '--innodb_stats_on_metadata=0 --innodb_stats_method=nulls_ignored --default-storage-engine=InnoDB'
+SELECT count(*) FROM t WHERE id IS NULL;
+count(*)
+94425
+SELECT count(*) FROM t WHERE id IS NOT NULL;
+count(*)
+5664
+SHOW INDEXES FROM t;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t	1	t	1	id	A	100494	NULL	NULL	YES	BTREE	
+
+We are expected cardinality approximately equal to not null count, but this is false
+
 DROP TABLE t;

mysqltest: Result length mismatch

 - saving '/storage/dev/percona/innodb_stats/debug/mysql-test/var/log/main.percona_stats_null_innodb/' to '/storage/dev/percona/innodb_stats/debug/mysql-test/var/log/main.percona_stats_null_innodb/'

Retrying test main.percona_stats_null_innodb, attempt(2/3)...

main.percona_stats_null_innodb           [ retry-fail ]
        Test ended at 2011-11-19 02:31:25

CURRENT_TEST: main.percona_stats_null_innodb
--- /storage/dev/percona/innodb_stats/debug/mysql-test/r/percona_stats_null_innodb.result	2011-11-19 03:27:06.375140046 +0300
+++ /storage/dev/percona/innodb_stats/debug/mysql-test/r/percona_stats_null_innodb.reject	2011-11-19 03:31:25.488010708 +0300
@@ -15,4 +15,17 @@
 ANALYZE TABLE t;
 Table	Op	Msg_type	Msg_text
 test.t	analyze	status	OK
+Failed with '--innodb_stats_on_metadata=0 --innodb_stats_method=nulls_ignored --default-storage-engine=InnoDB'
+SELECT count(*) FROM t WHERE id IS NULL;
+count(*)
+94425
+SELECT count(*) FROM t WHERE id IS NOT NULL;
+count(*)
+5664
+SHOW INDEXES FROM t;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t	1	t	1	id	A	100558	NULL	NULL	YES	BTREE	
+
+We are expected cardinality approximately equal to not null count, but this is false
+
 DROP TABLE t;

mysqltest: Result length mismatch

 - saving '/storage/dev/percona/innodb_stats/debug/mysql-test/var/log/main.percona_stats_null_innodb/' to '/storage/dev/percona/innodb_stats/debug/mysql-test/var/log/main.percona_stats_null_innodb/'

Test main.percona_stats_null_innodb has failed 2 times, no more retries!

------------------------------------------------------------
The servers were restarted 1 times
Spent 10.888 of 50 seconds executing testcases

Completed: Failed 1/2 tests, 50.00% were successful.

Failing test(s): main.percona_stats_null_innodb

The log files in var/log may give you some hint of what went wrong.

If you want to report this error, please read first the documentation
at http://dev.mysql.com/doc/mysql/en/mysql-test-suite.html

mysql-test-run: *** ERROR: there were failing test cases

Logging: /storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0/mysql-test/mysql-test-run.pl  --force percona_stats_null_innodb percona_stats_null_myisam
MySQL Version 5.5.17
Too long tmpdir path '/storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0-release/mysql-test/var/tmp'  creating a shorter one...
 - using tmpdir: '/tmp/fFfX0kXdr7'

Checking supported features...
 - skipping ndbcluster
 - skipping SSL, mysqld not compiled with SSL
Collecting tests...
vardir: /storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0-release/mysql-test/var
Checking leftover processes...
Removing old var directory...
Creating var directory '/storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0-release/mysql-test/var'...
Installing system database...
Using server port 57933

==============================================================================

TEST                                      RESULT   TIME (ms) or COMMENT
--------------------------------------------------------------------------

worker[1]  - 'localhost:13000' was not free
worker[1]  - 'localhost:13010' was not free
worker[1]  - 'localhost:13020' was not free
worker[1] Using MTR_BUILD_THREAD 303, with reserved ports 13030..13039
main.percona_stats_null_myisam           [ pass ]  11522
main.percona_stats_null_innodb           [ fail ]
        Test ended at 2011-11-19 02:37:04

CURRENT_TEST: main.percona_stats_null_innodb
--- /storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0/mysql-test/r/percona_stats_null_innodb.result	2011-11-19 03:16:08.862872476 +0300
+++ /storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0/mysql-test/r/percona_stats_null_innodb.reject	2011-11-19 03:37:03.947136726 +0300
@@ -15,4 +15,17 @@
 ANALYZE TABLE t;
 Table	Op	Msg_type	Msg_text
 test.t	analyze	status	OK
+Failed with '--innodb_stats_on_metadata=0 --innodb_stats_method=nulls_ignored --default-storage-engine=InnoDB'
+SELECT count(*) FROM t WHERE id IS NULL;
+count(*)
+94425
+SELECT count(*) FROM t WHERE id IS NOT NULL;
+count(*)
+5664
+SHOW INDEXES FROM t;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment	Index_comment
+t	1	t	1	id	A	100494	NULL	NULL	YES	BTREE		
+
+We are expected cardinality approximately equal to not null count, but this is false
+
 DROP TABLE t;

mysqltest: Result length mismatch

 - saving '/storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0-release/mysql-test/var/log/main.percona_stats_null_innodb/' to '/storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0-release/mysql-test/var/log/main.percona_stats_null_innodb/'

Retrying test main.percona_stats_null_innodb, attempt(2/3)...

main.percona_stats_null_innodb           [ retry-fail ]
        Test ended at 2011-11-19 02:37:19

CURRENT_TEST: main.percona_stats_null_innodb
--- /storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0/mysql-test/r/percona_stats_null_innodb.result	2011-11-19 03:16:08.862872476 +0300
+++ /storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0/mysql-test/r/percona_stats_null_innodb.reject	2011-11-19 03:37:19.579974140 +0300
@@ -15,4 +15,17 @@
 ANALYZE TABLE t;
 Table	Op	Msg_type	Msg_text
 test.t	analyze	status	OK
+Failed with '--innodb_stats_on_metadata=0 --innodb_stats_method=nulls_ignored --default-storage-engine=InnoDB'
+SELECT count(*) FROM t WHERE id IS NULL;
+count(*)
+94425
+SELECT count(*) FROM t WHERE id IS NOT NULL;
+count(*)
+5664
+SHOW INDEXES FROM t;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment	Index_comment
+t	1	t	1	id	A	100515	NULL	NULL	YES	BTREE		
+
+We are expected cardinality approximately equal to not null count, but this is false
+
 DROP TABLE t;

mysqltest: Result length mismatch

 - saving '/storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0-release/mysql-test/var/log/main.percona_stats_null_innodb/' to '/storage/dev/percona/innodb_stats_5.5/Percona-Server-5.5.17-rel21.0-release/mysql-test/var/log/main.percona_stats_null_innodb/'

Test main.percona_stats_null_innodb has failed 2 times, no more retries!

--------------------------------------------------------------------------
The servers were restarted 1 times
Spent 11.522 of 51 seconds executing testcases

Completed: Failed 1/2 tests, 50.00% were successful.

Failing test(s): main.percona_stats_null_innodb

The log files in var/log may give you some hint of what went wrong.

If you want to report this error, please read first the documentation
at http://dev.mysql.com/doc/mysql/en/mysql-test-suite.html

mysql-test-run: *** ERROR: there were failing test cases

Are you sure that this is the same for 'upstream InnoDB' and PerconaServer InnoDb/ExtraDB (it seeems you sue the latter)?

I read in http://www.percona.com/doc/percona-server/5.5/diagnostics/innodb_stats.html

"Beginning in release 5.1.56 ... a variable with the same and functionality was implemented in the upstream InnoDB."

I understand this like the functionality is basically the same but the exact coding implementation is not necessarily.  What would then mean that one may have a bug not affecting the other (and vice versa).

Peter
(not a MySQL person).

Peter,

Implementation is different, but declared functionality works incorrectly.

Please look into my patch with test-cases. MyISAM and InnoDB has identical behavior for nulls_equal and nulls_unequal, and different behavior for nulls_ignored.

What does it mean? One of it has bug.

I checked this tests on Percona-Server 5.1/5.5 implementations (before replacement). All workds as I expected without fails.

Latest 5.1 and 5.5 has test fails for nulls_ignored InnoDB.
I have come to the conclusion.

Best regards, Oleg

* I have come to the conclusion - this is bug/

Verified on Windows XP:

mysql> set global innodb_stats_method=nulls_ignored;
Query OK, 0 rows affected (0.00 sec)

mysql> analyze table t;
+--------+---------+----------+----------+
| Table  | Op      | Msg_type | Msg_text |
+--------+---------+----------+----------+
| test.t | analyze | status   | OK       |
+--------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> show indexes from t;
+-------+------------+----------+--------------+-------------+-----------+------
-------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardi
nality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+-------------+-----------+------
-------+----------+--------+------+------------+---------+---------------+
| t     |          1 | t$id     |            1 | id          | A         |
100536 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+-------------+-----------+------
-------+----------+--------+------+------------+---------+---------------+
1 row in set (0.02 sec)

mysql> SELECT count(*) FROM t WHERE id IS NOT NULL;
+----------+
| count(*) |
+----------+
|     2286 |
+----------+
1 row in set (0.01 sec)

mysql> SELECT count(*) FROM t WHERE id IS NULL;
+----------+
| count(*) |
+----------+
|    97714 |
+----------+
1 row in set (0.13 sec)

Forgot this:

mysql> SELECT count(distinct id) from t;
+--------------------+
| count(distinct id) |
+--------------------+
|                  6 |
+--------------------+
1 row in set (0.05 sec)

This is not a bug. The difference comes from InnoDB's estimation on the limited pages it has sampled. In this case, the distinct value of all 100,000 value is only 6. The InnoDB sampling could not accurately estimate this value when it samples some rows in only 8 pages in this case.

MyISAM does a full scan, so it has accurate value.

So let's go through this example step by step. The cardinality comes from a "record_per_key" value calculated (both for MyISAM and InnoDB), which estimates the number of records per distinct key:

The table has 100089 records, 5664 are not null, 94425 are nulls (most are nulls), distinct value is 6. So the record per key should be 5664/6 = 944 (as we ignore all the null values). This is what MyISAM got.

For InnoDB, we do estimation from sampling, we sample only 8 pages (the index has 82 leaf pages), so it will approximately times 10 on values got from this 8 pages sampling.

So from this 8 pages sampling, we get:

gdb) p n_not_null[0]
$44 = 944

(gdb) p n_diff[1]
$45 = 8420

It got an estimation of 944 not null value, and 8420 diffs (the diffs include null values, null considered as different, this is same as in MyISAM). So it extrapolates to the whole index and got:

(gdb) p index->stat_n_non_null_key_vals[0]
$48 = 9677

(gdb) p index->stat_n_diff_key_vals[j] 
$49 = 86307

(gdb) p records
$53 = 94268

so it estimates 9677 non-null values, and 86307 different key (with nulls). It estimates the table has 94268 records.

So with this value, the estimated distinct value is 86307 - (94268 - 9677) = 1716. 

And with 9677 non-null value, the record per key is 9677/1716 = 5. so this is very different from 944 got from the MyISAM. 

However, the whole calculation is correct. Here is the comparison of estimation and reality:

                InnoDB estimation from sampling   reality
Records in table     94268                           10089
Null Value           84591                           94425
non-Null value        9677                            5664
number of distinct    1716                               6

So we can see the null/non-null value and records in table are in the ballpark. However, the distinct value is vastly off, partly due to NULL value are considered as different in the process, so any small difference in null value can be exaggerated, and affect the distinct value calculation.

However, the whole calculation, estimation process is correct. The combination of large amount of NULL values and small distinct value cause this estimation deviation. The only way to improve on this is to increase srv_stats_sample_pages and also maybe in our code to allow more records sampled.

Jimmy,

1) +Failed with '--innodb_stats_on_metadata=0 --innodb_stats_method=nulls_ignored --default-storage-engine=InnoDB --innodb_stats_sample_pages=20000'
+SELECT count(*) FROM t WHERE id IS NULL;
+count(*)
+94425
+SELECT count(*) FROM t WHERE id IS NOT NULL;
+count(*)
+5664
+SHOW INDEXES FROM t;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t	1	t	1	id	A	100093	NULL	NULL	YES	BTREE	
+
+We are expected cardinality approximately equal to not null count, but this is false
+

I setup --innodb_stats_sample_pages=20000 - and receive error again.
With 20000 InnoDB will check ALL pages in index.
But result incorrect again.

I check different values of innodb_stats_sample_pages - 1, 10, 100, 150, 200, 2000, 20000 - and every time I receive incorrect statistics.

2) So, in my test-case just a single column INT type in table.

This is mean, statistics with "nulls_equal" should be near the statistics with nulls_ignored. But nulls_equal provide correct statistics on every value of innodb_stats_sample_pages, and nulls_ignored - always incorrect.

Jimmy,

1) +Failed with '--innodb_stats_on_metadata=0 --innodb_stats_method=nulls_ignored --default-storage-engine=InnoDB --innodb_stats_sample_pages=20000'
+SELECT count(*) FROM t WHERE id IS NULL;
+count(*)
+94425
+SELECT count(*) FROM t WHERE id IS NOT NULL;
+count(*)
+5664
+SHOW INDEXES FROM t;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t	1	t	1	id	A	100093	NULL	NULL	YES	BTREE	
+
+We are expected cardinality approximately equal to not null count, but this is false
+

I setup --innodb_stats_sample_pages=20000 - and receive error again.
With 20000 InnoDB will check ALL pages in index.
But result incorrect again.

I check different values of innodb_stats_sample_pages - 1, 10, 100, 150, 200, 2000, 20000 - and every time I receive incorrect statistics.

2) So, in my test-case just a single column INT type in table.

This is mean, statistics with "nulls_equal" should be near the statistics with nulls_ignored. But nulls_equal provide correct statistics on every value of innodb_stats_sample_pages, and nulls_ignored - always incorrect.

Test case for bug 63320 on current upstream (incorrect nulls_ignored on big number of nulls)

Attachment: bug63320.patch (text/x-patch), 8.08 KiB.

* InnoDB statistic calculation

InnoDB get innodb_stats_sample_pages pages for statistics calculation.
On every page InnoDB calculates the number of different keys (diff_stats)
Then InnoDB approximates the result to total records number.

* Percona innodb_stats_method algorithm

Percona has option "innodb_stats_method" before 5.1.56 version.
It works in this way:

1) Function, which compares two tuples (used by diff_stats) is now sensitive to innodb_stats_method.
On nulls_unequal and nulls_ignored it considers two NULLs as different values.
On nulls_equal it consider two NULLs as equal.

2) Instead of getting random pages, XtraDB gets random pages, where first column of key is not null

As result, Percona's algorithm works in situation, when KEY is just single column.
When key has more than one column, algorithm can work incorrectly (I didn't check this).

* Upstream innodb_stats_method algorithm

InnoDB statistics bug related to innodb_stats_method=nulls_ignored
http://bugs.mysql.com/bug.php?id=30423

Starting from 5.1.56 upstream MySQL has similar option for innodb (innodb_stats_method).
Algorithm different from Percona

1) function for compare two tuples changes as in Percona algorithm

2) instread of Percona, upstream implementation get random pages, and calculates on every page diff_stats (as before, but don't forget about changes in compare function), and also calculate not_null_stats count (number of not-null keys)

As result, this algorithm free from Percona's limiation to one column

* Test-case for the problem.

1) I get table with 100 thousands of rows, where 100 not-null values, every value repeat 20 times (1, 2, 3, 4, and 5 value). All other rows (key in it) is NULLs. Key is single column
2) I run ANALYZE TABLE and ask for Cardinality (SHOW INDEXES FROM table) for every value of innodb_stats_method/myisam_stats_method variables, for InnoDB/MyISAM, and for different values (1, 100, 1000) of innodb_sample_pages.

MyISAM works always fine.
XtraDB old implementation (before 5.1.56) works always fine.
Upstream implementation works always incorrectly for nulls_ignored. Cardinality too big.

Jimmy,

Please also note, MyISAM works as Percona implementation.
MyISAM skips all null values, and calculate diff_stats on not_nulls values. After that, rec_per_key = records / diff_stats.

You code (not_null_count) / (diff_count - null_count) works perfectly with small amount of NULLs, but most of mysql users changing *_stats_method parameter when amount of null values is significant.

Percona implementation was before 5.1.56 and 5.5.9.

Best regards, Oleg

Oleg, a few points here:

1) Increase "innodb_stats_sample_pages" will not help.

a) it will be capped by index->stat_index_size.

b) it still does random dive to the leaf page, so some pages can be repeatedly sampled, and thus make results skewed as well.

2) In terms of unique value calculation, InnoDB does exactly the same as MyISAM does, please check update_key_parts() in myisam/mi_check.c:

/*
#(unique_tuples not counting tuples with NULLs) =
#(unique_tuples counting tuples with NULLs as different) -
#(tuples with NULLs)
*/
BTW, MyISAM scans whole index, so it has accurate results. That is key of
difference.

3) Percona skips first column of key is not null, this more likes a tailor solution if not a hack. It can be easily broken by adding a key column whose first column is not NULL. This is not a good solution since it can't be extended to multiple columns as most indexes are.

4) The essence of the problem is that sampling provides inaccurate results
on a skewed dataset. Please note, we would need a solution that works
universally, does not restrict to single columns. I think we can enhance the
InnoDB sampling code, that allow users to get accurate statistics with full
table scan. Such operation can also be done at check table time, create index
time etc. I have a separate bug to do this enhancement. And prototype shows
it provides exactly accurate result as MyISAM does. I will provide you the patch once it is reviewed.

Thanks
Jimmy

We expand the innodb_stats_transient_sample_pages (or
innodb_stats_sample_pages) to allow value 0, which used to indicate a full
index scan for stats generation. And with the new implementation (for Bug
13565145), we got identical result as in MyISAM:

mysql> show indexes from t;
+-------+------------+----------+--------------+-------------+-----------+----
---------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation |
Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment
|
+-------+------------+----------+--------------+-------------+-----------+----
---------+----------+--------+------+------------+---------+---------------+
| t     |          1 | t$id     |            1 | id          | A         |
     106 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+-------------+-----------+----
---------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

record per key value in this case is 944. This also shows our original
calculation method is correct. And this can be expanded to multiple columns
without any problem.

In addition, if innodb_stats_transient_sample_pages / innodb_stats_sample_pages specified by user is larger than the whole index size, then it will also covert to a index scan, rather than doing repetitively random dive.