Bug #1262 LEFT JOIN of a table with an INNER JOIN returns cartesian product

• Submitted: 12 Sep 2003 8:10
• Modified: 21 Oct 2003 9:50
• Reporter: Aleksander Adamowski
• Status: Not a Bug
• Category: MySQL Server: InnoDB storage engine
• Severity: S2 (Serious)
• Version: 4.0.11a
• OS: Linux (Mandrake Linux 9.1)
• CPU Architecture: Any

[12 Sep 2003 8:10] Aleksander Adamowski

Description:
I have 3 tables that form a canonical n:m relation. The tables are named:

   * groups
   * groups_has_permissions
   * permissions

They specify groups of users and assiciate permissions with those groups.

Suppose that I want to list all groups that don't have a specific permission (identified by permission's name attribute).

I have to:

1) Create a list of group-permission associations with the spefified permission name:

SELECT *
FROM permissions 
INNER JOIN groups_has_permissions ON (groups_has_permissions.idpermissions = permissions.idpermissions AND permissions.name = 'manage_users')

2) Since "NOT IN" isn't implemented in MySQL, I have to use a "LEFT JOIN" with a "IS NULL" check as a workaroun (documented here: http://www.mysql.com/doc/en/ANSI_diff_Subqueries.html).

So:

  a) The LEFT JOIN:
SELECT *
FROM groups
LEFT JOIN
(permissions INNER JOIN groups_has_permissions ON 
  (groups_has_permissions.idpermissions = permissions.idpermissions AND 
  permissions.name = 'manage_users')
)
ON groups_has_permissions.idgroups = groups.idgroups

it returns a cartesian product, not expected LEF JOIN. There's no sense in proceeding further, but let's try:

  b) The IS NULL check:

SELECT *
FROM groups
LEFT JOIN
(permissions INNER JOIN groups_has_permissions ON 
  (groups_has_permissions.idpermissions = permissions.idpermissions AND 
   permissions.name = 'manage_users')
)
ON groups_has_permissions.idgroups = groups.idgroups
WHERE permissions.idpermissions IS NULL

This gives an error:

ERROR 1146: Table 'left_joins.Impossible WHERE noticed after reading const tables' doesn't exist

How to repeat:
I'll attach a testcase mysqldump and all discuseed queries.

Suggested fix:
Inspect behaviour of LEFT JOINS of tables with other JOINS

[12 Sep 2003 8:12] Aleksander Adamowski

I've experienced this bug on MySQL 4.0.11a as well as MySQL 4.0.14.

[12 Sep 2003 8:12] Aleksander Adamowski

mysqldump of test database, including test data

Attachment: left_joins.sql (application/octet-stream, text), 2.10 KiB.

[12 Sep 2003 8:13] Aleksander Adamowski

PNG image showing ERD of testcase

Attachment: testcase.png (image/png, text), 8.99 KiB.

[12 Sep 2003 8:13] Aleksander Adamowski

DBDesigner4 file with the ERD

Attachment: testcase.xml (text/xml), 23.25 KiB.

[12 Sep 2003 8:14] Aleksander Adamowski

The first step in developing a query - INNER JOIN. It works fine.

Attachment: 01_INNER_JOIN.sql (application/octet-stream, text), 245 bytes.

[12 Sep 2003 8:15] Aleksander Adamowski

The second step - LEFT JOIN of groups with the previous INNER JOIN. Triggers this bug.

Attachment: 02_LEFT_JOIN_to_INNER_JOIN.sql (application/octet-stream, text), 319 bytes.

[12 Sep 2003 8:16] Aleksander Adamowski

The third step - IS NULL check. Triggers "Impossible WHERE" error message

Attachment: 03_LEFT_JOIN_to_INNER_JOIN_with_IS_NULL_condition.sql (application/octet-stream, text), 359 bytes.

[12 Sep 2003 8:17] Aleksander Adamowski

LEFT JOIN of 2 ordinary tables to show that this works fine - it shows groups with no permission as expected

Attachment: 04_LEFT_JOIN_to_groups_has_permissions_with_IS_NULL_condition.sql (application/octet-stream, text), 238 bytes.

[22 Sep 2003 3:20] MySQL Verification Team

You said:

I'll attach a testcase mysqldump and all discuseed queries.

Please could you send it at:

ftp://support.mysql.com/pub/mysql/secret

with a name file identifying this bug report.

Thanks in advance.

[1 Oct 2003 5:18] Aleksander Adamowski

Done.

[21 Oct 2003 9:50] Dean Ellis

The central cause for this is that MySQL currently ignores parentheses in the FROM clause.  (This is to be changed in version 5.)  Your query is thus interpreted as:

SELECT *
FROM
 groups
 LEFT JOIN permissions
 INNER JOIN groups_has_permissions
  ON groups_has_permissions.idpermissions = permissions.idpermissions
  AND permissions.name = 'manage_users'
 ON groups_has_permissions.idgroups = groups.idgroups

Which will, as you have seen, result in a cartesian product.

You may wish to rewrite your query as:

SELECT g.idgroups
FROM
 permissions AS p
 LEFT JOIN groups_has_permissions AS gp
  ON p.idpermissions = gp.idpermissions
 RIGHT JOIN groups AS g
  ON g.idgroups = gp.idgroups
WHERE
 p.name = 'manage_users'
 AND gp.idgroups IS NULL