Bug #1932 Cartesian product within subgroups using outer joins optimizes poorly
Submitted: 24 Nov 2003 7:44 Modified: 24 Nov 2003 16:08
Reporter: Kevin Grittner Email Updates:
Status: Duplicate Impact on me:
Category:MySQL Server Severity:S2 (Serious)
Version:4.1 alpha OS:Any (all)
Assigned to: CPU Architecture:Any

[24 Nov 2003 7:44] Kevin Grittner
The following query runs in about a second in another popular database product, but failed to complete in 20 minutes, against an identical schema and dataset in MySQL.  It pretty much pegged the server while running, and I don't know how long it would have run or if it even would have completed successfully.

I was able to work around the problem with this specific query by splitting it into two queries.  That's probably how it should have been written in the first place; but, the query is a well-formed query with unambiguous semantics, so this may point out a more general optimizer problem which merits investigation.

How to repeat:
    R."name" AS "tableName",
    A1."name" AS "attributeName",
    A2."name" AS "columnName",
    UT."name" AS "typeName"
  FROM "Relation" R 
  LEFT OUTER JOIN "KeyAttr" KA JOIN "Attribute" A1 ON (KA."attribute" = A1."id") ON 
       R."id" = KA."relation" AND 
       R."id" = A1."relation" 
  LEFT OUTER JOIN "UserType" UT JOIN "Attribute" A2 ON (UT."id" = A2."userType") ON 
       R."id" = A2."relation" AND 
       UT."id" = A2."userType" AND 
       UT."name" IN ('DateT', 'TimeT', 'TimestampT') 
  ORDER BY "tableName", "columnName", "orderingNo"

Suggested fix:
The optimizer seems to have a weakness here which should be fixed.
[24 Nov 2003 16:08] Dean Ellis
The query is, essentially, attempting to perform nested joins, which MySQL does not currently support.  The performance issues were likely due to the cartesian products resulting from the way MySQL actually parses the query.  Chances are that had you let the query complete you would have found the results to be useless.

Support for nested joins is planned for the future.

Thank you.