Bug #58101 Optimizer picks wrong order of queries
Submitted: 10 Nov 2010 0:21 Modified: 11 Nov 2010 9:50
Reporter: Zbigniew Braniecki Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:5.1.38-community-log, 5.1.54-bzr OS:Linux
Assigned to: CPU Architecture:Any
Tags: join, Optimizer, queries
Triage: Triaged: D3 (Medium)

[10 Nov 2010 0:21] Zbigniew Braniecki
Description:
At Mozilla, we're using MySQL for storing our build system logs and we hit a very slow query. (https://bugzilla.mozilla.org/show_bug.cgi?id=608739)

How to repeat:
Download http://labs.braniecki.net/mysql/mysql-bug-608739.dump.bz2 and install.

Launch a query:

SELECT DISTINCT `mbdb_property`.`id`, `mbdb_property`.`name`,
`mbdb_property`.`source`, `mbdb_property`.`value` FROM `mbdb_property` INNER
JOIN `mbdb_build_properties` ON (`mbdb_property`.`id` =
`mbdb_build_properties`.`property_id`) WHERE (`mbdb_property`.`name` IN
('locale', 'tree', 'slavename') AND `mbdb_build_properties`.`build_id` >=
102540  AND `mbdb_build_properties`.`build_id` <= 102796 );

(generated by django)

Suggested fix:
Reversing the order of queries which I triggered by reordering the whole query and enforcing it by STRAIGHT_JOIN:

SELECT DISTINCT `mbdb_property`.`id`, `mbdb_property`.`name`,
`mbdb_property`.`source`, `mbdb_property`.`value` FROM `mbdb_build_properties`
STRAIGHT_JOIN `mbdb_property` ON
(`mbdb_property`.`id`=`mbdb_build_properties`.`property_id`) WHERE
(`mbdb_property`.`name` in ('locale', 'tree', 'slavename') and
`mbdb_build_properties`.`build_id` >= 102540 and
`mbdb_build_properties`.`build_id`<= 102796);

reduced the time the query took from 22 seconds to 0.05 sec.

Optimizer could be smart enough to do the same in such case :)
[10 Nov 2010 1:02] Miguel Solorzano
Which exactly server version are you using?. Thanks in advance.
[10 Nov 2010 1:20] Zbigniew Braniecki
server version is 5.1.38-community-log

uname -a:
Linux bm-l10n-db 2.6.18-194.11.1.el5 #1 SMP Tue Jul 27 05:44:43 EDT 2010 i686 i686 i386 GNU/Linux

If I remember correctly it's RHEL5.
[10 Nov 2010 11:05] Miguel Solorzano
Could you please try try server 5.5.7 rc and comment the result you will get. Thanks in advance.
[10 Nov 2010 12:21] Zbigniew Braniecki
Original query: 89 rows in set (0.69 sec)
Modified query: 89 rows in set (0.02 sec)

So it's definitely better (even the first query was like 3 sec, not 23 sec), but still slower by an order of magnitude (35x).

The explain extended on the first one:

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: mbdb_property
         type: range
possible_keys: PRIMARY,mbdb_property_name
          key: mbdb_property_name
      key_len: 62
          ref: NULL
         rows: 104
     filtered: 100.00
        Extra: Using where; Using temporary
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: mbdb_build_properties
         type: ref
possible_keys: build_id,property_id_refs_id_621d2a84
          key: property_id_refs_id_621d2a84
      key_len: 4
          ref: l10n_site.mbdb_property.id
         rows: 15
     filtered: 100.00
        Extra: Using where; Distinct
2 rows in set, 1 warning (0.00 sec)

On the latter:

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: mbdb_build_properties
         type: range
possible_keys: build_id,property_id_refs_id_621d2a84
          key: build_id
      key_len: 4
          ref: NULL
         rows: 3168
     filtered: 100.00
        Extra: Using where; Using index; Using temporary
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: mbdb_property
         type: eq_ref
possible_keys: PRIMARY,mbdb_property_name
          key: PRIMARY
      key_len: 4
          ref: l10n_site.mbdb_build_properties.property_id
         rows: 1
     filtered: 100.00
        Extra: Using where
2 rows in set, 1 warning (0.00 sec)
[11 Nov 2010 9:50] Valeriy Kravchuk
Verified on recent 5.1.54 from bzr using your test case.

This is the plan optimizer decided to use:

mysql> explain SELECT DISTINCT `mbdb_property`.`id`, `mbdb_property`.`name`, `mbdb_property`.`source`, `mbdb_property`.`value` FROM `mbdb_property` INNER JOIN `mbdb_build_properties` ON (`mbdb_property`.`id` = `mbdb_build_properties`.`property_id`) WHERE (`mbdb_property`.`name` IN ('locale', 'tree', 'slavename') AND `mbdb_build_properties`.`build_id` >= 102540  AND `mbdb_build_properties`.`build_id` <= 102796 );
+----+-------------+-----------------------+-------+---------------------------------------+------------------------------+---------+-----------------------+------+------------------------------+
| id | select_type | table                 | type  | possible_keys                         | key                          | key_len | ref                   | rows | Extra                        |
+----+-------------+-----------------------+-------+---------------------------------------+------------------------------+---------+-----------------------+------+------------------------------+
|  1 | SIMPLE      | mbdb_property         | range | PRIMARY,mbdb_property_name            | mbdb_property_name           | 62      | NULL                  |  104 | Using where; Using temporary |
|  1 | SIMPLE      | mbdb_build_properties | ref   | build_id,property_id_refs_id_621d2a84 | property_id_refs_id_621d2a84 | 4       | test.mbdb_property.id |   15 | Using where; Distinct        |
+----+-------------+-----------------------+-------+---------------------------------------+------------------------------+---------+-----------------------+------+------------------------------+
2 rows in set (0.00 sec)

While with this plan:

mysql> explain SELECT DISTINCT `mbdb_property`.`id`, `mbdb_property`.`name`,
    -> `mbdb_property`.`source`, `mbdb_property`.`value` FROM `mbdb_build_properties`
    -> STRAIGHT_JOIN `mbdb_property` ON
    -> (`mbdb_property`.`id`=`mbdb_build_properties`.`property_id`) WHERE
    -> (`mbdb_property`.`name` in ('locale', 'tree', 'slavename') and
    -> `mbdb_build_properties`.`build_id` >= 102540 and
    -> `mbdb_build_properties`.`build_id`<= 102796);
+----+-------------+-----------------------+--------+---------------------------------------+----------+---------+----------------------------------------+------+-------------------------------------------+
| id | select_type | table                 | type   | possible_keys                         | key      | key_len | ref                                    | rows | Extra                                     |
+----+-------------+-----------------------+--------+---------------------------------------+----------+---------+----------------------------------------+------+-------------------------------------------+
|  1 | SIMPLE      | mbdb_build_properties | range  | build_id,property_id_refs_id_621d2a84 | build_id | 4       | NULL                                   | 5568 | Using where; Using index; Using temporary |
|  1 | SIMPLE      | mbdb_property         | eq_ref | PRIMARY,mbdb_property_name            | PRIMARY  | 4       | test.mbdb_build_properties.property_id |    1 | Using where                               |
+----+-------------+-----------------------+--------+---------------------------------------+----------+---------+----------------------------------------+------+-------------------------------------------+
2 rows in set (0.00 sec)

query is executed notably faster (0.27 sec comparing to 37.40 sec in my case). ANALYZE TABLE does not help.
[7 Feb 2011 22:37] Stephen Jackson
This smells like http://bugs.mysql.com/bug.php?id=30423

To verify this, check the columns your suggested keys are on for lots of NULLS. Innodb maybe making bad stats due to this.

show indexes from each table and see if the cardinality is much higher for an index on one or other of the dbs. If its very low for an index that you would expect the optimizer to use, then issue "flush tables [table_name]", and then "show indexes from [tablename]" to see if the cardinality changes. If it goes much higher, then do your explain again. If it is this bug, then you should get same explain result on both servers if you do enough flush table statements...

Read the details of the bug in the link..
[7 Feb 2011 23:01] Stephen Jackson
Actually I just tested it for you, confirmed.

Repeated "flush tables mbdb_build_properties;" statements followed by "show indexes from mbdb_build_properties;" will show you how the cardinality is altering wildly.

This may be caused by the bug I referenced, but I cannot find NULL values in the indexed columns of your table. So basically you are falling victim to INNODB's random index cardinality algo. If you are running with the InnoDB plugin, I recommended tuning the innodb_stats_sample_pages up (http://dev.mysql.com/doc/refman/5.1/en/innodb-parameters.html#sysvar_innodb_stats_sample_p...) to get the optimizer to make a better decision ( he is presented with better index distribution stats) or, use an index hint on property_id_refs_id_621d2a84 index...

Hope this helps!

//Steve