MySQL Bugs: #49092: EXISTS clause optimization

Bug #49092	EXISTS clause optimization
Submitted:	25 Nov 2009 9:37	Modified:	25 Dec 2009 9:57
Reporter:	Christophe Fondacci	Email Updates:
Status:	No Feedback	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	5.0.26	OS:	Linux
Assigned to:		CPU Architecture:	Any
Tags:	EXISTS LIMIT OPTIMIZATION ROWS

Description:

I was very surprised that the EXISTS clause was fully executing its subquery. I would have expected it to stop after the first row returned by the subquery (like a limit 1 clause).

This would allow to use the EXISTS clause in much larger use cases, for example with large tables (see example below)

How to repeat:

Consider the following query :
select * from categories c 
where exists (
  select 1 from items where item_category_id=c.category_id
)

It *works* fine. Now let's say you have :
- an index on items.item_category_id column
- 30 rows in the categories table
- a billion lines in the items table

The optimizer will fully execute the "exists" subquery while it could stop after the first line found. It would be equivalent to a "limit 1" restriction in the subquery.

Currently the latter query would take several minutes to complete. It would have returned almost instantly if the exists subquery stops after the first row found. Having 1 row or millions in the subquery will not change the result of the exists clause...

Suggested fix:

I don't know if this suggestion face the restriction of not allowing subqueries to perform "limit" restrictions, but I would have expected the optimizer to stop the EXISTS evaluation after the first row found.

Thank you for the problem report. Please, check if you have this problem with a recent version, 5.0.88. If the problem is repeatable with 5.0.88, please, send CREATE TABLE statements for both tables and the results of EXPLAIN for the problematic query.

No feedback was provided for this bug for over a month, so it is
being suspended automatically. If you are able to provide the
information that was originally requested, please do so and change
the status of the bug back to "Open".