MySQL Bugs: #35794: Very bad query optimization on DELETE with subquery

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

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.

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.

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

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.

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 | 
+-------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

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.

[Thread not abandoned!]

Sorry, but I don't understand what you wanted to say in last comment.

Minimal databaset for reproducing the bug.

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

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

[Thread not abandoned!] = I didn't take action in the thread for a long time, but I still
plan to answer.

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);

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;