MySQL Bugs: #12232: Bad statistics lead to bad execution plan

Bug #12232	Bad statistics lead to bad execution plan
Submitted:	27 Jul 2005 22:34	Modified:	29 Sep 2005 18:08
Reporter:	Kolbe Kegel	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: MyISAM storage engine	Severity:	S2 (Serious)
Version:	4.1, 5.0	OS:	Linux (Linux)
Assigned to:	Sergey Petrunya	CPU Architecture:	Any

Description:
The optimizer chooses a bad query execution plan based on incorrect statistics.

How to repeat:
Load attached SQL dump "bad_statistics.dump"

If you execute the following query on both 4.0.24 and 4.1.13 you can see the difference:

EXPLAIN SELECT count(*) FROM transactions t FORCE INDEX (transactions$id1), statuses s WHERE t.trans_type = 6 AND t.id = 478004 AND t.tbl = 1 AND t.id1 = s.status_id AND s.type_id = 3 \G

As you can see, the transactions$id1 index looks much more attractive in 4.1.13, reporting "rows: 5" compared to "rows: 19679" in 4.0.24.

If you then execute the following in both versions, you will see that the transactions$id$tbl index reports the same statistic in both versions:

EXPLAIN SELECT count(*) FROM transactions t FORCE INDEX (transactions$id$tbl), statuses s WHERE t.trans_type = 6 AND t.id = 478004 AND t.tbl = 1 AND t.id1 = s.status_id AND s.type_id = 3 \G

In both cases, the statistics for this index show "rows: 10". So, in 4.1.13, the optimizer sees a value of 5 for transactions$id1 and a value of 10 for $transactions$id$tbl, and it picks the former. 

This SELECT is significantly 

MySQL 5.0.9 exhibits the erroneous behavior as well.

Suggested fix:
Repair statistics so that the optimizer can make the correct decision.

This is not a bug. The way how 4.1 calculate statistics deffers in 4.1 and 4.0: in 4.1 all null values in the last component of an index is considered as
inequal.
However the case reveals that the new method of collecting statistics is not adequate anymore after addition an optimization that that rejects keys with
null values. This problem will be resolved in near future.

Hi!  I have more information from the customer on this bug which I would
like to log here.

There are now three test cases, all of which are probably caused by the
same limitation in the server.  All three are fast in MySQL 4.0, slow in
MySQL 4.1.  Two are slow in MySQL 5.0; the third runs fast in 5.0
despite having the "bad" EXPLAIN plan, perhaps due to index merge or
some other optimization which is working around the bad plan.

#1 - still slow. It runs in 2 seconds but that's because it's a stipped
down table and query. When forcing the index it takes 0.00 seconds

See private comment for dump file #1 location.

Query is: SELECT count(*) FROM transactions t, statuses s WHERE t.trans_type = 6 AND t.id = 478004 AND t.tbl = 1 AND t.id1 = s.status_id AND s.type_id = 3;

4.0 choses an index on id (scans 3 rows); 4.1 choses index on id1 (scans
570,000 rows)

#2 - This one is "fixed" in 5.0 though the explain is wrong.  Maybe the
index merge optimization is making it work?  It is still very slow in
4.1.

See private comment for dump file #2 location.

SELECT incidents.i_id FROM queues, incidents WHERE
(incidents.queue_id = queues.id) AND (incidents.queue_id in
(45,46,47,48,89)) AND (incidents.assgn_acct_id IS NULL) AND
(incidents.status_type = 1);

#3 - still slow

See private comment for dump file #3 location.

1)Load the dump
2) run explain:
explain select count(*) from incidents incidents JOIN threads
threads ON incidents.i_id=threads.id JOIN accounts accounts ON
threads.acct_id¬counts.acct_id WHERE (incidents.updated >= '2005-08-31
00:00:00' AND incidents.updated < '2005-09-02 00:00:00');
3) Notice it doesn't use the index on 'updated'
4) Run query, notice it's slow.
5) Run query again with 'use index' notice it runs 34x faster:
select count(*) from incidents use index (incidents$updated) JOIN
threads threads ON incidents.i_id=threads.id JOIN accounts accounts ON
threads.acct_id¬counts.acct_id WHERE (incidents.updated >= '2005-08-31
00:00:00' AND incidents.updated < '2005-09-02 00:00:00');

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/internals/29880

Got feedback on the patch from Igor.

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/internals/29964

Note for the docs team: 

Added myisam_stats_method global/session variable and server startup option.
The option controls which method is used to collect index statistics for 
MyISAM tables.
Currently there are two possible values: 

nulls_inequal 
    This is the default. Index statistics collection code will treat NULLs
    as different (see example below). This method is also used by previous
    releases of MySQL 4.1/5.0.

nulls_equal
    NULLs will be treated as equal when collecting index statistics. This
    method is used in MySQL 4.0.

The reason for adding this option is that one method may be advantageous in
one case and the other method may be advantageous in another.
Now one can use the server option to globally switch back to 4.0 behavior.

One can also temporary set global/session option and run ANALYZE TABLE to
get statistics recollected with other method.  

(
to make it clear: I wanted to say that statistics collection method is
currently not remembered in the table and every time statistics gets
recollected it will be collected using current myisam_stats_method_setting.
It is also ok to access/use a table with statistics collected with method X
while current statistics collection method is Y. The query optimizer
currently is not aware of different statistics collection method, it's ok
since the values produced by different methods have similar meaning.
)

myisamchk has got a new --stats_method parameter with the same meaning.

I've started 4.1 with --myisam_stats_method=nulls_equal and run 3 test cases provided above by Tim Smith. The queries run fast.

Here are my results:

case | 4.0-bk    |   4.1-bk    |   4.1-nulls-equal (commited patch)
 #1  | 0.00 sec  |  1.55 sec   | 0.00 sec
 #2  | 0.01 sec  |  0.98 sec   | 0.00 sec
 #3  | 1.35 sec  | 48.22 sec  | 1.77 sec

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/internals/30067

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/internals/30125

Fix pushed into 4.1.15 tree

Note for the docs team:
Some considerations on which method one should use
===================================

Table engines collect statistics. They provide the optimizer with 
  
  AVG(#records with the same key prefix value)  (1)

value. Lets denote a set of table records with the same key prefix value 
as "value group", and the above number as "value group size".
(btw SHOW INDEX displays #records_in_table/(value group size) )

MySQL uses "value group size" to get an estimates of 
 A) how many records it will have to read for one "ref" access
 B) how many records a partial join "(...) JOIN tbl ON tbl.key = expr"
    will have.

When one performs join with '<=>' operator, NULL is not different from any
other possible value and so should be treated as identical (i.e. NULL<=>NULL
just as 1<=>1).

For join performed with '=' operator, the NULL value is special as "a = b"
is not true when a or b is NULL. In particular, when doing a 'ref' access
on "tbl.key = expr":
 * MySQL will not access table tbl if the current value of expr is NULL
 * Partial join result mentioned above in B) will not contain records such
   that tbl.key IS NULL.

Basically we don't care how many NULLs are in table tbl here, and should 
use the average size of non-NULL value group as (1). MySQL currently doesn't
allow one to collect/use this value though.

If you use MyISAM, you've got two other options:

1. myisam_stats_method=nulls_equal:
Count all NULL values as identical (i.e. as one "value group").
If the number of records with tbl.key IS NULL is much higher then average
number of records such that tbl.key = <some other value>, use of this method
may make the optimizer not to use index on tbl.key for "ref" access.

So if you have "good if not NULLs" indexes with small value groups that also 
contain lots of NULLs, don't use this method.

2. myisam_stats_method=nulls_inequal:
Count all NULL values as different (i.e. as N "value groups" of size 1).

Use of this method may cause the optimizer be too optimistic about the index.
If the index has big non-NULL value groups, counting NULLs as groups of size
1 will make statistics look as if value groups were smaller, and the
optimizer will choose to use "ref" access on the index when other methods
are better.

So if you have "bad without NULLs" indexes that also contain lots of NULLs,
don't use this method.

Note: For non-MyISAM table currently there is only one method to collect
statistics. Usually it is closer to nulls_equal method.

Sergey,

ANALYZE TABLE won't help as presumably statistics for many tables will already be up to date. Same for OPTIMIZE TABLE. CHECK TABLE works though. Would it be accurate to say that it is necessary to run CHECK TABLE to ensure that the statistics are updated using the value of myisam_stats_method?

> ANALYZE TABLE won't help as presumably statistics for many tables will already
> be up to date. Same for OPTIMIZE TABLE. CHECK TABLE works though. Would it be
> accurate to say that it is necessary to run CHECK TABLE to ensure that the
> statistics are updated using the value of myisam_stats_method?
Yes, I didn't explicitly mention it (assumed it was obvious from all other notes), but 
one needs to get table statistics regenerated. This can be done by either running 
CHECK TABLE / myisamchk, or table getting statistics out of date date  (e.g. insert a
record and delete it back) and then running ANALYZE TABLE.

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/internals/30289

I've pushed a changeset that replaces "inequal" with "unequal".

Noted in:
- 4.1.15, 5.0.14 changelogs
- entry in system variable list
- "MyISAM Index Statistics Collection" section in optimizer chapter