Query in MySQL 5.0 uses index merge but MariaDB does a full table scan

[Eric Bergen]

The following query in MySQL 5.0.72sp1 correctly uses the index_merge optimization and executes in less than a second. On MariaDB it doesn't use the index_merge optimization and instead does a full scan of t3. The attached file fast_in_mysql_slow_in_mariadb.sql contains the tables to reproduce the bug. I've tested this in MariaDB 5.2.7 as well as 5.2.9. Uncommenting the index hint in mariadb gives the desired behavior.

SELECT
    *
FROM t1
LEFT JOIN t2 /* use index (primary, c3) */
    ON t2.c2 = t1.c2
LEFT JOIN t3
    ON t2.c1 = t3.c1
WHERE
      ((t2.c2 <=> 182104825 OR t2.c3 <=> 182104825)) AND
      (t3.c1 IS NOT NULL)

Explain output from MariaDB:
+----+-------------+-------+-------+---------------+---------+---------+-------------+-------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+---------+---------+-------------+-------+--------------------------+
| 1 | SIMPLE | t3 | index | PRIMARY | PRIMARY | 8 | NULL | 99879 | Using where; Using index |
| 1 | SIMPLE | t2 | ref | PRIMARY,c1,c3 | c1 | 9 | test2.t3.c1 | 1 | Using where |
| 1 | SIMPLE | t1 | ref | c2 | c2 | 9 | test2.t2.c2 | 1 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+-------------+-------+--------------------------+
3 rows in set (0.01 sec)

Desired explain output from MySQL:
+----+-------------+-------+-------------+---------------+------------+---------+-------------+------+--------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------------+---------------+------------+---------+-------------+------+--------------------------------------+
| 1 | SIMPLE | t2 | index_merge | PRIMARY,c1,c3 | PRIMARY,c3 | 8,8 | NULL | 2 | Using union(PRIMARY,c3); Using where |
| 1 | SIMPLE | t3 | eq_ref | PRIMARY | PRIMARY | 8 | test2.t2.c1 | 1 | Using where; Using index |
| 1 | SIMPLE | t1 | ref | c2 | c2 | 9 | test2.t2.c2 | 1 | Using where; Using index |
+----+-------------+-------+-------------+---------------+------------+---------+-------------+------+--------------------------------------+
3 rows in set (0.00 sec)

[Philip Stoev (pstoev-askmonty)]

Repeatable in maria-5.1 as described above. The default plan does not use index merge and takes 2.5 seconds. The USE INDEX plan uses index_merge and takes 0.01 seconds.

Not repeatable in mysql 5.1.58 . The default plan there uses index_merge and completes in 0.01 seconds.

[Philip Stoev (pstoev-askmonty)]

Also repeatable with MyISAM. Repeatable regardless of the value of the table_elimination switch.

[Igor Babaev (igorb-seattle)]

I investigated why for the reported query mysql-5.1 generated a fast plan with an index merge.

It also generated a fast plan for an equivalent query
SELECT * FROM t1 LEFT JOIN t2 ON t2.c2 = t1.c2, t3
    WHERE t2.c1 = t3.c1 AND (t2.c2 = 182104825 OR t2.c3 = 182104825)
                   AND t3.c1 IS NOT NULL;
that contained only one left join:

mysql> EXPLAIN
    -> SELECT * FROM t1 LEFT JOIN t2 ON t2.c2 = t1.c2, t3
    -> WHERE t2.c1 = t3.c1 AND (t2.c2 = 182104825 OR t2.c3 = 182104825)
    -> AND t3.c1 IS NOT NULL
    -> ;
+----+-------------+-------+-------------+---------------+------------+---------+------------+------+--------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------------+---------------+------------+---------+------------+------+--------------------------------------+
| 1 | SIMPLE | t2 | index_merge | PRIMARY,c1,c3 | PRIMARY,c3 | 8,8 | NULL | 2 | Using union(PRIMARY,c3); Using where |
| 1 | SIMPLE | t3 | eq_ref | PRIMARY | PRIMARY | 8 | test.t2.c1 | 1 | Using index |
| 1 | SIMPLE | t1 | ref | c2 | c2 | 9 | test.t2.c2 | 1 | Using where; Using index |
+----+-------------+-------+-------------+---------------+------------+---------+------------+------+--------------------------------------+

However further simplification of the query converting the remaining left join to to an inner join
SELECT * FROM t1 JOIN t2 ON t2.c2 = t1.c2, t3
    WHERE t2.c1 = t3.c1 AND (t2.c2 = 182104825 OR t2.c3 = 182104825)
                   AND t3.c1 IS NOT NULL;
brought me to a slow plan:

mysql> EXPLAIN
    -> SELECT * FROM t1 JOIN t2 ON t2.c2 = t1.c2, t3
    -> WHERE t2.c1 = t3.c1 AND (t2.c2 = 182104825 OR t2.c3 = 182104825)
    -> AND t3.c1 IS NOT NULL;
+----+-------------+-------+-------+---------------+---------+---------+------------+-------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+---------+---------+------------+-------+--------------------------+
| 1 | SIMPLE | t3 | index | PRIMARY | PRIMARY | 8 | NULL | 99879 | Using where; Using index |
| 1 | SIMPLE | t2 | ref | PRIMARY,c1,c3 | c1 | 9 | test.t3.c1 | 1 | Using where |
| 1 | SIMPLE | t1 | ref | c2 | c2 | 9 | test.t2.c2 | 1 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------------+-------+--------------------------+

The second query is equivalent to the first one because the condition t2.c1=t3.c1 effectively filters out
all null-complemented rows.

So basically we see the same problem for mysql-5.1 as for maridb-5.2/5.1.

When processing the second query and looking for possible accesses to the table t2 the optimizer first build...