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 12:06	Modified:	3 Sep 2019 13:11
Reporter:	Alejandro Cusumano	Email Updates:
Status:	Closed	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:		CPU Architecture:	Any
Tags:	delete, Optimizer, subquery

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;

Hello Alejandro. Quite a lot of development has happened in MySQL since this bug was filed. We have improved subqueries, and now one can do EXPLAIN on DELETE, and there's also an optimizer tracing feature to understand the optimizer's decision.
Is the performance problem of DELETE still occurring with a recent version (MySQL 8.0)? If not, then we can close this report.

Hello!

The default plan is still significantly suboptimal.

Summary, running on MySQL 8.0.15:

> DELETE FROM carts WHERE id not IN (SELECT cart_id FROM line_items);

Hangs - stopped at 60 seconds ("preparing" state).

> DELETE carts.* FROM carts LEFT JOIN line_items ON carts.id = line_items.cart_id WHERE line_items.cart_id IS NULL;

Runs in subsecond time (plan attached in separate, hidden, comment.

First, the slow and fast queries are not equivalent:
a) DELETE FROM carts WHERE id not IN (SELECT cart_id FROM line_items);
b) DELETE carts.* FROM carts LEFT JOIN line_items ON carts.id = line_items.cart_id WHERE line_items.cart_id IS NULL;
Say carts.id is 3, and line_items contains no row with cart_id=3 but has at least one row where cart_id is NULL.
With a), the result of IN is the SQL value UNKNOWN, the result of NOT IN is also UNKNOWN, the WHERE is not TRUE, and finally the row with carts.id=3 is *not* deleted.
With b), the LEFT JOIN finds no match, so the row with cart_id=3 is complemented with NULLs, the WHERE is TRUE, and the row with carts.id=3 is deleted.

Should the row be deleted or not? What is your preferred behaviour here: (a) or (b)?

Second, I wonder if it's NULL values which explain the speed difference.
Can you do another test (*not on your production data, this is a DELETE!*):
time the execution of:
 DELETE FROM carts WHERE not exists (SELECT 1 FROM line_items where cart_id=carts.id);
(note: this deletes the row with carts.id=3, like (b)). And please provide its EXPLAIN too.

And I'd also need to know: is the SELECT, equivalent to (a), fast or slow? I mean this one:
SELECT id FROM carts WHERE id not IN (SELECT cart_id FROM line_items);
and also I'd need EXPLAIN for this. Thanks.

NOT IN is slow because, taking my example of an earlier post (say carts.id is 3, and line_items contains no row with cart_id=3 but has at least one row where cart_id is NULL): we look for value 3 in line_items - no match, then we have to look for NULL in line_items too (if there is a NULL, we'll return UNKNOWN for IN; if there is no NULL, we'll return FALSE for IN; that makes a real difference for NOT IN's result value).
I read that NOT IN is not what you really want, so maybe that makes the discussion moot. Still, some comments on timings:

DELETE FROM carts2 WHERE NOT EXISTS (SELECT 1 FROM line_items WHERE cart_id = carts2.id); -- (c), faster (5/6 seconds)

-> thanks to NOT EXISTS, doesn't have to check for NULLs, so is fast

SELECT * FROM carts2 WHERE id NOT IN (SELECT cart_id FROM line_items); -- (a/SELECT), fast (8/9 seconds)

-> NOT IN, so should be slow, but uses an optimization called "subquery materialization", which stores only distinct values of line_items.cart_id into a tmp table, with an index on it, and then looks things up; it needs to look NULL up, as always for NOT IN, but after looking it up once it keeps a cache of if NULL is there or not, so all next lookups of NULL are not done and served by the cache instead.

DELETE FROM carts2 WHERE id NOT IN (SELECT cart_id FROM line_items); -- (a/original), hangs

-> Slow because NOT IN _without_ subquery materialization

DELETE carts2.* FROM carts2 LEFT JOIN line_items ON carts2.id = line_items.cart_id WHERE line_items.cart_id IS NULL; -- (b), faster (5/6 seconds)

-> Fast, equivalent to NOT EXISTS.

-> To speed up the DELETE NOT IN query, you can try to make it use subquery materialization; that feature is currently disabled for single-table DELETE syntax but enabled for multi-table syntax; so you could try changing DELETE to the multi-table syntax, like (on test data):
DELETE carts2.* FROM carts2 WHERE id NOT IN (SELECT cart_id FROM line_items);
I'd be interested in knowing the plan and time for that. If EXPLAIN shows "SUBQUERY" instead of "DEPENDENT SUBQUERY" then it is using subquery materialization.

Thanks. The last DELETE above is using subquery materialization. It takes 16 secs, while the equivalent SELECT takes 8 seconds; that makes sense, as DELETE also has to delete rows, not only retrieve them (deletes writes to disk, at some point).
I think we have our conclusion now:
- NOT EXISTS, or a LEFT JOIN, are the fastest, because they don't have to handle NULL checking
- NOT EXISTS or a LEFT JOIN are the way to delete the intended rows, and NOT IN isn't, if I read you correctly
- NOT IN is necessarily slower as it has to handle NULL checking; subquery materialization makes it acceptably slower; without it, the query becomes very slow. andI don't think we can do much to make it faster
- However, what we can do is making single-table DELETE support subquery materialization (we'll think about putting this on our development plan).

That said, I propose that I close this bug report. Is that ok?

That makes sense.

Many thanks for the time spent and the thorough explanations; they're very helpful (in addition to being a good general reference).

You guys are welcome.
Closing the bug now.

Fixed in MySQL 8.0.21 as part of WL#6057. 

See same for docs info.

Closed.

Precision on the comment above: in version 8.0.21, a single-table DELETE will try to use the same optimizations as the multi-table DELETE already did: subquery materialization, or semijoin, for NOT EXISTS, and for NOT IN if nullability allows.