Bug #113303 Explain plan takes forever when there are more joins
Submitted: 1 Dec 2023 7:29 Modified: 1 Dec 2023 7:44
Reporter: Yunus Shaikh Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:8.0.35 OS:Any
Assigned to: CPU Architecture:Any
Tags: Explain plan, regression

[1 Dec 2023 7:29] Yunus Shaikh
Description:
Explain plan takes forever from version 8.0.16 and above. Works well till 8.0.15.

How to repeat:
Step1 - 
Install world database.

Run the below explain query -

explain select * from country a where a.Population > 1000
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Buenos Aires')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'La')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Córdoba')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Rosario')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Lomas')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Quilmes')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Almirante')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'La')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Mar')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'San')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Lanús')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Merlo')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'General')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Salta')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Moreno')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Santa')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Avellaneda')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Tres')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Morón')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Florencio')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'San')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Tigre')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Malvinas')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Vicente')
    -> and exists (select 'x' from city b where a.Code = b.CountryCode and b.Name = 'Berazategui');

This explain works without any problem on 8.0.15 but takes forever when we run it on 8.0.16.

If we reduce couple of exists statements, it works fine. 

Also another fix is if we disable optimizer switch semijoin to off,
it works well too.

set optimizer_switch="semijoin=off";

Explain plan works well after setting semijoin to OFF in new versions as well.
[1 Dec 2023 7:44] MySQL Verification Team
Hello Yunus Shaikh,

Thank you for the report and feedback.
Verified as described.

regards,
Umesh
[4 Dec 2023 6:36] Aristotle Po
Hi Team,

I would like to add that it is not just generation of the EXPLAIN PLAN that took forever but even the execution of the query itself behaves the same.

Also, I would to add for the workaround is that we can use the optimizer hint NO_SEMIJOIN to achieve same goal. Example :

SELECT /*+ NO_SEMIJOIN(@subq1) NO_SEMIJOIN(@subq2) [...] NO_SEMIJOIN(@subq25) */
      *
  FROM country a WHERE a.Population > 1000
 AND EXISTS (SELECT /*+ QB_NAME(subq1) */ 'x' FROM city b WHERE a.Code = b.CountryCode AND b.Name = 'Buenos Aires')
 [...]
 AND EXISTS (SELECT /*+ QB_NAME(subq25) */ 'x' FROM city b WHERE a.Code = b.CountryCode AND b.Name = 'Berazategui')
;
[5 Dec 2023 4:54] MAKOTO FUKUMOTO
We are encountering the same problem.
It occurs even if it is not an EXPLAIN, and the SQL execution does not finish even if it was rewritten as a JOIN.

select 
    count(*) 
from 
    country a 
    inner join city b on a.Code = b.CountryCode and b.Name = 'Buenos Aires'
    inner join city c on a.Code = c.CountryCode and c.Name = 'La'
    inner join city d on a.Code = d.CountryCode and d.Name = 'Córdoba'
    inner join city e on a.Code = e.CountryCode and e.Name = 'Rosario'
    inner join city f on a.Code = f.CountryCode and f.Name = 'Lomas'
    inner join city g on a.Code = g.CountryCode and g.Name = 'Quilmes'
    inner join city h on a.Code = h.CountryCode and h.Name = 'Almirante'
    inner join city i on a.Code = i.CountryCode and i.Name = 'Mar'
    inner join city j on a.Code = j.CountryCode and j.Name = 'San'
    inner join city k on a.Code = k.CountryCode and k.Name = 'Lanús'
    inner join city l on a.Code = l.CountryCode and l.Name = 'Merlo'
    inner join city m on a.Code = m.CountryCode and m.Name = 'General'
    inner join city n on a.Code = n.CountryCode and n.Name = 'Salta'
    inner join city o on a.Code = o.CountryCode and o.Name = 'Moreno'
    inner join city p on a.Code = p.CountryCode and p.Name = 'Santa'
    inner join city q on a.Code = q.CountryCode and q.Name = 'Avellaneda'
    inner join city r on a.Code = r.CountryCode and r.Name = 'Tres'
    inner join city s on a.Code = s.CountryCode and s.Name = 'Morón'
    inner join city t on a.Code = t.CountryCode and t.Name = 'Florencio'
    inner join city u on a.Code = u.CountryCode and u.Name = 'San'
    inner join city v on a.Code = v.CountryCode and v.Name = 'Tigre'
    inner join city w on a.Code = w.CountryCode and w.Name = 'Malvinas'
    inner join city x on a.Code = x.CountryCode and x.Name = 'Vicente'
    inner join city y on a.Code = y.CountryCode and y.Name = 'Berazategui';

I hope this bug will be fixed soon, because turning semijoin off slows down the execution time of this SQL.