[MDEV-3620] LP:890811 - Query in MySQL 5.0 uses index merge but MariaDB does a full table scan Created: 2011-11-15  Updated: 2015-02-02  Resolved: 2012-10-04

Status: Closed
Project: MariaDB Server
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Bug Priority: Minor
Reporter: Eric Bergen Assignee: Igor Babaev
Resolution: Won't Fix Votes: 0
Labels: Launchpad

Attachments: XML File LPexportBug890811.xml     File LPexportBug890811_fast_in_mysql_slow_in_mariadb.sql    

 Description   

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)

 Comments   
Comment by Eric Bergen [ 2011-11-15 ]

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

Comment by Eric Bergen [ 2011-11-15 ]

Create the t1, t2, and t3 tables.
LPexportBug890811_fast_in_mysql_slow_in_mariadb.sql

Comment by Philip Stoev (Inactive) [ 2011-11-16 ]

Re: Query in MySQL 5.0 uses index merge but MariaDB does a full table scan
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.

Comment by Philip Stoev (Inactive) [ 2011-11-16 ]

Re: Query in MySQL 5.0 uses index merge but MariaDB does a full table scan
Also repeatable with MyISAM. Repeatable regardless of the value of the table_elimination switch.

Comment by Igor Babaev [ 2011-11-19 ]

Re: Query in MySQL 5.0 uses index merge but MariaDB does a full table scan
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 builds an index merge scan over the indexes PRIMARY and c3 using the condition (t2.c2 = 182104825 OR t2.c3 = 182104825). Then the optimizer builds an index scan over the index c2 using the condition t3.c1 IS NOT NULL (here the equality t2.c1 = t3.c1 is applied). Mysql-5.1 always prefers index scans to index merge scans. So it discardx the index merge scan here though apparently it's much cheaper than the index scan. After this it chooses the full table scan of t2 as it's turns out to be cheaper than the index scan.

For the first query the optimizer just does not build any index scan to access t2 because due to a bug in its code the table t2 is considered as an inner table of an outer join even after the conversion of the left join to an inner join. This bug was fixed in the mariadb-5.1/5.2, but never in mysql-5.1.

Mariadb-5.3 resolves the problem of the fair choice between index merge scans and regular index scans
properly:

MariaDB [test]> 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 index

---------------------------------------------------------------------------------------------------------------+

MariaDB [test]> 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 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 index

---------------------------------------------------------------------------------------------------------------+

As a work-around for MariaDB 5.1/5.2 I could suggest the following variants of the above queries:

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+0 IS NOT NULL;

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+0 IS NOT NULL;

Then even for mariadb-5.2 (and mysql-5.1) we have:

MariaDB [test]> 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+0 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

---------------------------------------------------------------------------------------------------------------+

MariaDB [test]> 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+0 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

---------------------------------------------------------------------------------------------------------------+

Comment by Rasmus Johansson (Inactive) [ 2011-11-19 ]

Launchpad bug id: 890811

Generated at Thu Feb 08 06:49:58 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.