Bug #35794 Very bad query optimization on DELETE with subquery
Submitted: 3 Apr 2008 12:06 Modified: 16 Jun 2008 19:08
Reporter: Alejandro Cusumano Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.0.45, 5.0, 5.1, 6.0 BK OS:Any
Assigned to:
Tags: delete, Optimizer, subquery
Triage: Triaged: D3 (Medium)

[3 Apr 2008 12:06] Alejandro Cusumano
Description:
The optimization plan for a very common type of query took an undefined time on my machine.

How to repeat:
Suppose you have these two tables:

TABLE T1: id (PK) - 150K records
TABLE T2: id, t1_id (indexed, not RKed) - 80K records - about 1.5K distinct `t1_id`.

We want to delete the orphan records in T1.
This is very easily accomplished:

DELETE FROM T1 WHERE id NOT IN (SELECT t1_id FROM T2);

(this is shorter version of the NOT EXISTS variant).

This took an undefined amount of time (stopped after 10 minutes).

The SELECT counterpart it's working appropriately, taking a few seconds.

If I create a temporary table:

TEMP_T2_T1_IDS(heap): t1_id PK - FROM SELECT DISTINCT t2.t1_id

DELETE FROM T1 WHERE id NOT IN (SELECT t1_id FROM TEMP_T2_T1_IDS);

This runs fine (in a few seconds.)

Suggested fix:
Since I can't EXPLAIN delete[s], it's hard to guess.
[3 Apr 2008 13:37] Valerii Kravchuk
Please, send the exact version used, 5.0.x. Send the results of

EXPLAIN SELECT * FROM T1 WHERE id NOT IN (SELECT t1_id FROM T2);

Try also

DELETE FROM T1 WHERE id NOT IN (select t1_id FROM (SELECT t1_id FROM T2) a);

Maybe it runs faster... MySQL 6.0.x also worth a try.
[4 Apr 2008 13:29] Alejandro Cusumano
Hello,

1. the server version is 5.0.45

2. As I wrote, this is the EXPLAINed SELECT:

explain select * from carts where id not in (select cart_id from line_items);

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	carts	ALL	<null>	<null>	<null>	<null>	7836	Using where
2	DEPENDENT SUBQUERY	line_items	index_subquery	line_items_cart_id_index	line_items_cart_id_index	35  	func	14	Using index

If I put line_items.cart_ids in this table:

table li_cart_ids (id integer primary key) engine=heap;
(then fill it with the DISTINCTed ids)

and run:

delete from carts where id not in (select id from li_cart_ids);

the deletion happens very quickly; while this is obvious, it shows that the bare DELETE is choosing an extremely slow plan (that is, without using indexes).

Saverio
[4 Apr 2008 19:45] Sveta Smirnova
Thank you for the feedback.

As Valeriy said this probably fixed in version 6.0. But, please, provide output of SHOW CREATE TABLE T1; AND SHOW CREATE TABLE T2; to we can check.
[7 Apr 2008 8:36] Alejandro Cusumano
So, here they are!:

+------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table      | Create Table                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
+------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| line_items | CREATE TABLE `line_items` (
  `id` int(11) NOT NULL auto_increment,
  `type` varchar(255) default NULL,
  `created_on` datetime default NULL,
  `order_id` int(11) default NULL,
  `booking_id` int(11) default NULL,
  `cart_id` int(11) default NULL,
  `templock_id` int(11) default NULL,
  `position` int(11) default NULL,
  `price` float NOT NULL default '0',
  `quantity` int(11) NOT NULL default '0',
  `total` float default NULL,
  `account_id` int(11) default NULL,
  `ticket_price_id` int(11) default NULL,
  `note` varchar(255) default '',
  `product_id` int(11) default NULL,
  `group_size` int(11) default '1',
  `print_batch_id` int(11) default NULL,
  `print_count` int(11) default '0',
  `discount` float default '0',
  `ticket_allocation_id` int(11) default NULL,
  `deleteable` tinyint(1) default '1',
  PRIMARY KEY  (`id`),
  KEY `line_items_order_id_index` (`order_id`,`position`),
  KEY `line_items_cart_id_index` (`cart_id`,`position`),
  KEY `index_line_items_on_ticket_allocation_id` (`ticket_allocation_id`)
) ENGINE=InnoDB AUTO_INCREMENT=512831 DEFAULT CHARSET=utf8 | 
+------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

+-------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| carts | CREATE TABLE `carts` (
  `id` int(11) NOT NULL auto_increment,
  `created_at` datetime default NULL,
  `customer_id` int(11) default NULL,
  `max_tickets_per_event` int(11) default NULL,
  `remote_host` varchar(255) default NULL,
  `amends_order_id` int(11) default NULL,
  `order_type` varchar(40) default NULL,
  `referrer_id` int(11) default NULL,
  `deleteable` tinyint(1) default '1',
  `account_id` int(11) default NULL,
  PRIMARY KEY  (`id`),
  KEY `index_carts_on_account_id` (`account_id`)
) ENGINE=InnoDB AUTO_INCREMENT=168922 DEFAULT CHARSET=utf8 | 
+-------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
[19 May 2008 18:58] Sveta Smirnova
Thank you for the feedback.

I can not repeat described behavior with test data. Please try with current veriosn 5.0.51b and if problem still exists provide dump of tables.
[29 May 2008 10:55] Alejandro Cusumano
[Thread not abandoned!]
[31 May 2008 12:53] Sveta Smirnova
Sorry, but I don't understand what you wanted to say in last comment.
[14 Jun 2008 14:45] Alejandro Cusumano
Minimal databaset for reproducing the bug.

Attachment: minimal_bug_dump.sql.bz2 (application/x-bzip, text), 331.38 KiB.

[14 Jun 2008 14:55] Alejandro Cusumano
Attached the minimal dataset (databaset!) for redproducing the bug.

I just reproduced it on the following mysql server:

--> mysql  Ver 14.12 Distrib 5.0.51a, for debian-linux-gnu (i486) using readline 5.2

The query executed is:

--> delete from carts where id not in (select cart_id from line_items);

I can reproduce the bug _every_ time.

----------------------------------------------------------------------------

A very important question is (hopefully this is the appropriate place, as the general bug reporting FAQ doesn't explain it):

- Suppose I have a query which triggers an intermittent bug in the query optimizer.
- I connect to the server, and discover that for this specific connection, I am able to reproduce the bug every time I run the query.

Is there some way to produce an *extremely* detailed log of what's happening?
If so, I would be able to exploit that very fortunate event of being able to reproduce the bug every time given undefined circustances.

Note: this question regards a _different_ bug in the query optimizer, again found in the latest version of mysql 5.

Saverio
[14 Jun 2008 14:56] Alejandro Cusumano
[Thread not abandoned!] = I didn't take action in the thread for a long time, but I still plan to answer.
[14 Jun 2008 15:06] Alejandro Cusumano
The following query (suggested by v.kravchuk) causes undefined running time too:

--> delete from carts where id not in (select cart_id from (select cart_id from line_items) sub);
[16 Jun 2008 19:08] Sveta Smirnova
Thank you for the feedback.

Verified as described.

Workaround: delete from carts left join line_items on(carts.id=line_items.cart_id) where line_items.cart_id is null;