[MDEV-38] NOT EXISTS to IN (part of exists2in transformation for 10.0) Created: 2012-01-04  Updated: 2013-02-26  Resolved: 2013-02-26

Status: Closed
Project: MariaDB Server
Component/s: None
Fix Version/s: 10.0.2

Type: Task Priority: Major
Reporter: Rasmus Johansson (Inactive) Assignee: Oleksandr Byelkin
Resolution: Fixed Votes: 0
Labels: None

Issue Links:
Blocks
is blocked by MDEV-159 Exists2In: Assertion `!table || (!tab... Closed
is blocked by MDEV-160 Exists2In: Crash in in hp_movelink wi... Closed
PartOf
includes MDEV-3903 Exists2In: Server crashes in Item_con... Closed
includes MDEV-3904 Exists2In: Assertion `in_subs->has_st... Closed
Relates
relates to MDEV-245 Exists2In: Wrong result (extra rows) ... Closed
relates to MDEV-403 Exists2In: Wrong result (missing rows... Closed
relates to MDEV-404 Exists2In: Wrong result (extra rows) ... Closed
relates to MDEV-3906 Exists2In: Server crashes in Dependen... Closed
relates to MDEV-243 Exists2In: Wrong result (extra or mis... Closed
Sub-Tasks:
Key
 Summary
 Type
 Status
 Assignee
MDEV-3879 Exists2In: Wrong result (extra row) a... Technical task Closed Oleksandr Byelkin  
MDEV-3880 Exists2In: Wrong result (missing rows... Technical task Closed Oleksandr Byelkin  
MDEV-3881 Endless loop for query with EXISTS pr... Technical task Closed Oleksandr Byelkin  
MDEV-3894 Server crashes in Item_field::Item_fi... Technical task Closed Oleksandr Byelkin  

 Description   

Transform queries like:

... WHERE EXISTS (SELECT 1 FROM inner_table WHERE inner_table.field = 
2*outer_table.field AND maybe_something_else)...

and

... WHERE NOT EXISTS (SELECT 1 FROM inner_table WHERE inner_table.field = 
2*outer_table.field AND maybe_something_else)...

into

... WHERE 2*outer_table.field IN (SELECT inner_table.field FROM inner_table 
WHERE 1 = 1 AND maybe_something_else)..
 

... WHERE NOT( 2*outer_table.field IS NOT NULL AND NOT 2*outer_table.field IN 
(SELECT 
inner_table.field FROM inner_table WHERE inner_table.field IS NOT NULL AND 
maybe_something_else)...

To allow optimizations made for IN/ALL/ANY subqueries.

Conversion is possible only if:
1)real NULL is not important (top element of WHERE/ON AND/OR list, i.e. NULL
equal to FALSE)
2a)subquery has dependences in the WHERE clause and they are equalities and in is not "NOT EXISTS" (this kind of queries could be converted to semijoin)
OR
2b)subquery has the only dependences (after bringing them out subquery become independent) in the WHERE clause and they are equalities (could be materialized)
3)the subquery is simple (has no aggregate function, GROUp BY, ORDER BY, LIMIT
HAVING and so on)

For NOT EXISTS conversion the subquery should be marked that its left part can't
be NULL.

Note: Number of equalities could be limited by already allocated space for select list for current implementation.

 Comments   
Comment by Oleksandr Byelkin [ 2012-02-08 ]

I checked that current implementation uses full match (that is what we wanted).

Comment by Oleksandr Byelkin [ 2012-02-23 ]

Added multi-item support. Waiting for test results.

Comment by Oleksandr Byelkin [ 2012-10-15 ]

Start after review work...

Comment by Oleksandr Byelkin [ 2012-10-22 ]

Problem with view test could be problem of unset flag due to absence of real execution of the query (no result after reading constant tables).

Comment by Oleksandr Byelkin [ 2012-11-12 ]

Move to 10.0

Comment by Sergei Petrunia [ 2012-11-27 ]

It seems, it is easy to support EXISTS->IN conversion anywhere (not only on top level of WHERE or under NOT). EXISTS's NULLs handling policy is easier than that of IN, so we'll just need to introduce/use NULL-oblivious-IN. Details in the email. need to discuss it.,

Comment by Sergei Petrunia [ 2012-11-27 ]

DBT-3 has EXISTS subqueries. In Q4 and Q22 - optimization is applicable, in Q21 optimization not applicable (non-equality correlated conditions).

I don't expect these queries to benefit from this optimization (they all seem to be better served by IN-to-EXISTS strategy), though. We'll also need to check for regressions, just in case.

Comment by Oleksandr Byelkin [ 2013-02-26 ]

pushed to 10.0-base

Generated at Thu Feb 08 06:25:50 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.