MySQL Bugs: #12144: 4.1 has wrong estimate of number of rows; explain & max_join

Bug #12144	4.1 has wrong estimate of number of rows; explain & max_join_size wrong
Submitted:	25 Jul 2005 0:37	Modified:	6 Aug 2005 23:40
Reporter:	Timothy Smith	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	4.1	OS:	Any (all)
Assigned to:	Igor Babaev	CPU Architecture:	Any

Description:
In MySQL 4.0, EXPLAIN shows 22214 * 8 * 140 = 25 million rows need to be scanned.  And a max_join_size of 10 million will trigger, disallowing the query.

In MySQL 4.1, EXPLAIN shows 22214 * 1 * 1 = 22 thousand rows need to be scanned.

When running the actual query on MySQL 4.1, it is clear that it's scanning much more than 22 thousand rows (based on SHOW STATUS output).

How to repeat:
Try the following on MySQL 4.1.14 and MySQL 4.0.26.  Load the file attached to this issue:

gzip -cd bad_explain.sql.gz | mysql test

Now, try the explain (notice difference in 'rows' between 4.0 and 4.1):

mysql -Ee 'explain SELECT SQL_CALC_FOUND_ROWS orgs.org_id, count(DISTINCT contacts.c_id), count(DISTINCT sa_opportunities.op_id) FROM orgs orgs LEFT JOIN contacts contacts ON orgs.org_id=contacts.org_id LEFT JOIN sa_opportunities sa_opportunities ON contacts.c_id=sa_opportunities.c_id GROUP BY orgs.org_id ORDER BY NULL LIMIT 0,1000' test

Now, on 4.1 verify that the Handler_read_next is reading much more than 22000 rows:

mysql -sse 'flush status'
mysql -sse 'show status like "handler_read%"'

mysql -sse 'SELECT SQL_CALC_FOUND_ROWS orgs.org_id, count(DISTINCT contacts.c_id), count(DISTINCT sa_opportunities.op_id) FROM orgs orgs LEFT JOIN contacts contacts ON orgs.org_id=contacts.org_id LEFT JOIN sa_opportunities sa_opportunities ON contacts.c_id=sa_opportunities.c_id GROUP BY orgs.org_id ORDER BY NULL LIMIT 0,1000' test &

mysql -sse 'show processlist'

mysql -sse 'show status like "handler_read%"'
mysql -sse 'show status like "handler_read%"'

mysqladmin kill <ID>

My test results:

12:30 ~/m/41/m$ mysql -e 'flush status';
12:31 ~/m/41/m$ mysql -sse 'SELECT SQL_CALC_FOUND_ROWS orgs.org_id, count(DISTINCT contacts.c_id), count(DISTINCT sa_opportunities.op_id) FROM orgs orgs LEFT JOIN contacts contacts ON orgs.org_id=contacts.org_id LEFT JOIN sa_opportunities sa_opportunities ON contacts.c_id=sa_opportunities.c_id GROUP BY orgs.org_id ORDER BY NULL LIMIT 0,10' test &
[2] 47802
12:31 ~/m/41/m$ mysql -sse 'show status like "handler_read%"'
Handler_read_first      1
Handler_read_key        7176
Handler_read_next       2672199
Handler_read_prev       0
Handler_read_rnd        0
Handler_read_rnd_next   0
12:31 ~/m/41/m$ mysql -sse 'show status like "handler_read%"'
Handler_read_first      1
Handler_read_key        8982
Handler_read_next       6760956
Handler_read_prev       0
Handler_read_rnd        0
Handler_read_rnd_next   0
12:31 ~/m/41/m$ mysql -sse 'show status like "handler_read%"'
Handler_read_first      1
Handler_read_key        12902
Handler_read_next       21398233
Handler_read_prev       0
Handler_read_rnd        0
Handler_read_rnd_next   0
12:32 ~/m/41/m$ mysql -sse 'show processlist'
28      root    localhost       test    Query   90      Sending data    SELECT SQL_CALC_FOUND_ROWS orgs.org_id, count(DISTINCT contacts.c_id), count(DISTINCT sa_opportuniti
32      root    localhost       NULL    Query   0       NULL    show processlist
12:32 ~/m/41/m$ mysqladmin kill 28      
12:32 ~/m/41/m$ ERROR 1053 (08S01) at line 1: Server shutdown in progress

[2]  - exit 1     mysql -sse  test
12:33 ~/m/41/m$ mysql -sse 'select version();'
4.1.14-debug-log

Suggested fix:

The main problem is that max_join_size doesn't catch this problem query.  This causes real trouble for the customer.

The best fix would be that MySQL 4.1 could actually do the query and only look at 22,000 rows.  If that's not possible, then EXPLAIN and max_join_size should match the way the query will truly be performed.

Hmmm, trouble uploading the file to the bug report.

Please see the file as uploaded to the FTP site:

ftp://ftp.mysql.com/pub/mysql/upload/bug12144.sql.gz

Thanks!

Timothy

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/27687

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/27697

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/27702

The SELECT query
  SELECT SQL_CALC_FOUND_ROWS orgs.org_id
    FROM orgs orgs LEFT JOIN contacts contacts ON orgs.org_id=contacts.org_id
                   LEFT JOIN sa_opportunities sa_opportunities
                             ON contacts.c_id=sa_opportunities.c_id
    GROUP BY orgs.org_id
    ORDER BY NULL LIMIT 0,1000;
was slow by the following reasons.

The first left join yielded 5127 rows:
mysql> SELECT count(*) FROM orgs LEFT JOIN contacts ON orgs.org_id=contacts.org_id
    ->   WHERE contacts.c_id IS NULL;
+----------+
| count(*) |
+----------+
|     5127 |
+----------+

Thus the table sa_opportunities was accessed 5127 times with key=NULL.
The table sa_opportunities had 21296 rows with c_id=NULL 
mysql> SELECT count(*) FROM sa_opportunities WHERE c_id IS NULL;
+----------+
| count(*) |
+----------+
|    21296 |
+----------+

So there were 5127*21296 calls of handler read_next.

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/27752

This patch is in 3 changesets.

ChangeSet
  1.2347 05/07/28 13:31:15 igor@rurik.mysql.com +3 -0
  sql_select.cc:
    Fixed bug #12144.
    Added an optimization that avoids key access with null keys for the 'ref'
    method when used in outer joins. The regilar optimization with adding
    IS NOT NULL expressions is not applied for outer join on expressions as
    the predicates of these expressions are not pushed down in 4.1.
  null_key.result, null_key.test:
    Added a test case for bug #12144.

ChangeSet
  1.2357 05/07/28 16:04:47 igor@rurik.mysql.com +2 -0
  null_key.test, null_key.result:
    Modified the test case for patch of the bug #12144
    to display status of Handler_read_next before and
    after the tested query.

ChangeSet
  1.2358 05/07/28 17:53:51 igor@rurik.mysql.com +2 -0
  null_key.test, null_key.result:
    Made the test case for bug #12144 independent on other tests.

The fix will appear in 4.1.14 and 5.0.11

Documented in 4.1.14 and 5.0.11 changelogs:

<listitem><para>
 Added an optimization that avoids key access with <literal>NULL</literal> keys for the <literal>ref</literal> method when used in outer joins. (Bug #12144)
</para></listitem>