Bug #71584 Optimizer executes statement inperformant
Submitted: 4 Feb 2014 11:15 Modified: 29 Jun 2015 15:34
Reporter: Martin Kirchner Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.6.15 and 5.6.16 OS:Linux (Debian 7.1)
Assigned to: CPU Architecture:Any

[4 Feb 2014 11:15] Martin Kirchner
Description:
The optimizer executes the inperformant subquery first which results in a total execution time of 34 minutes. If I change the query such that it uses two INNER JOINs instead of the subselects the result is returned in less than a second. The behaviour does not change for an 'optimizer_prune_level' of 0 and 1.
Strangely, on a another test system (not the one mentioned in 71171), a virtual machine with much less cpu power and RAM, the behaviour is vice versa: INNER JOIN takes about 50 minutes whereas the subselects return a result in less than 2 minutes. However the data in the tables is slightly different but not in dimensions.
You'll find the optimizer traces attached.

Original query (subselect):
---------------------------
SELECT EMAILSTORE.ISFORMEMAIL, EMAILSTORE.SENDDATE, EMAILSTORE.SUBJECT, EMAILSTORE.XFROM, EMAILSTORE.XTO, EMAILSTORE.HASATTACHMENTS, EMAILSTORE.GGUID 
FROM `svg`.EMAILSTORE0 AS EMAILSTORE 
WHERE 
	((EMAILSTORE.GGUID IN (SELECT rel.GUID1 FROM `svg`.TableRelation AS rel INNER JOIN `svg`.TODO0 AS TODOC7504C2A4C0C38BDBE403DA9CA19A0DF ON rel.GUID2 = TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID WHERE ((TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.KEYWORD LIKE '%antragsanforderung%' AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.WORKINGPERCENT = '100') AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID IN (SELECT TABLEGUID FROM `svg`.TODOORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ForeignEditPermission = 65535))))) AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISDELETED = 0 AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISTEMPLATE = 0))) 
	AND (EMAILSTORE.GGUID IN (SELECT TABLEGUID FROM `svg`.EMAILSTOREORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND EMAILSTORE.ForeignEditPermission = 65535))))) 
	AND (EMAILSTORE.ISDELETED = 0 AND EMAILSTORE.ISTEMPLATE = 0) 
ORDER BY EMAILSTORE.SENDDATE DESC, EMAILSTORE.GGUID ASC 
LIMIT 0, 100;

"Optimized" query (INNER JOIN):
-------------------------------
SELECT EMAILSTORE.ISFORMEMAIL, EMAILSTORE.SENDDATE, EMAILSTORE.SUBJECT, EMAILSTORE.XFROM, EMAILSTORE.XTO, EMAILSTORE.HASATTACHMENTS, EMAILSTORE.GGUID 
FROM `svg`.EMAILSTORE0 AS EMAILSTORE 
	INNER JOIN svg.tablerelation AS rel ON rel.GUID1 = EMAILSTORE.GGUID
	INNER JOIN svg.todo0 AS TODOC7504C2A4C0C38BDBE403DA9CA19A0DF ON rel.GUID2 = TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID
WHERE 
	(TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.KEYWORD LIKE '%antragsanforderung%' AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.WORKINGPERCENT = '100') 
	AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID IN (SELECT TABLEGUID FROM `svg`.TODOORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ForeignEditPermission = 65535)))) 
	AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISDELETED = 0 AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISTEMPLATE = 0)
	AND (EMAILSTORE.GGUID IN (SELECT TABLEGUID FROM `svg`.EMAILSTOREORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND EMAILSTORE.ForeignEditPermission = 65535)))) 
	AND (EMAILSTORE.ISDELETED = 0 AND EMAILSTORE.ISTEMPLATE = 0) 
ORDER BY EMAILSTORE.SENDDATE DESC, EMAILSTORE.GGUID ASC 
LIMIT 0, 100;

How to repeat:
See optimizer traces.
[4 Feb 2014 11:16] Martin Kirchner
Optimizer trace on LIVE - SubSelect - executed in 34 minutes

Attachment: live_trace_20140121_SubSelect_34min.txt (text/plain), 299.09 KiB.

[4 Feb 2014 11:16] Martin Kirchner
Optimizer trace on LIVE - INNER JOIN - executed in 0,5s

Attachment: live_trace_20140203_InnerJoin_0s.txt (text/plain), 18.97 KiB.

[4 Feb 2014 11:16] Martin Kirchner
Optimizer trace on TEST vm - INNER JOIN - executed in 50min

Attachment: testvm_trace_20140204_innerjoin_50min.txt (text/plain), 268.50 KiB.

[4 Feb 2014 11:17] Martin Kirchner
Optimizer trace on TEST vm - SubSelect - executed in 1.5 minutes

Attachment: testvm_trace_20140204_subselect_1,5min.txt (text/plain), 247.04 KiB.

[4 Feb 2014 14:08] Sinisa Milivojevic
Hi,

This is a problem that was started with the introduction of nested queries in 4.1. The type of nested queries you use are considered DEPENDENT nested query and those have not been optimized at all. Finally, since 5.5.15 some types of those queries were optimized, but not all. We have an entire chapter in our manual, chapter 8.2.1.14. , which describes the set of conditions that nested query has to satisfy in order to get optimized. Please, read it carefully.

A work on this problem is continuing one and cases like your queries will be dealt with in future.
[4 Feb 2014 14:40] Martin Kirchner
Well, it might be that not all subselects can be optimized, however that does not explain the differences between the servers.
[4 Feb 2014 16:20] Sinisa Milivojevic
Differences in optimizer paths can be quite different on different servers. Causes of the differences can be:

* different server versions
* different settings
* different data

Third factor is absolutely the most frequent cause of the speed differences.

If you find out that all three different factors are totally identical on both LIVE and TEST servers, then this would deserve further investigations.
[5 Feb 2014 13:39] Øystein Grøvlen
Hi Martin,

Thanks for the optimizer traces.  One of the traces, "Optimizer trace on LIVE - INNER JOIN", seems to be truncated so I was not able to determine what happens in that case.  It would also be nice if you could provide the output of EXPLAIN FORMAT=JSON for the queries.  It is a bit cumbersome to reconstruct the final plan from the trace.

For the subquery variant, the only difference I can see is which index is used for TableRelation (IDX_GUID1296 vs IX_MDX_V5_1).  I do not have the definition of those indexes, but I would not think that should make such a big difference.

Looking at the trace, I suspect that there is a bug wrt cost of the semi-join strategy called DuplicateWeedout.  Hence, I will investigate this a bit further.

I am not convinced that your two queries are equivalent, but it is a bit hard to know without knowing which columns of the tables are unique.

Another issue that makes optimization of the query bit more complex is the or expressions.  I would not rule out that the performance would be better if you handled rows with "ForeignEditPermission = 65535" in a separate query.  (You could always use UNION to merge the results).  In that query the test on ForeignEditPermission could be put in the outer query.  If the subquery is without references to tables of the outer query, other execution plans could be used.
[6 Feb 2014 10:37] Øystein Grøvlen
Uploaded optimizer trace shows that cost calculations will not be correct for joins that involves duplicate weedout semi-join.

Setting this bug report to verified.
[6 Feb 2014 14:48] Martin Kirchner
I'm going crazy. That is weird indeed.
Today I executed the INNER JOIN query on live again - incredibly slow, about 75 min., subselect also slow - 75 min, too. Unfortunately the optimizer trace was not yet enabled.
The same result on a similar, replicated system.
Then I restarted the live system: INNER JOIN runs in about 46s, subselect takes its time.
On the slow test virtual machine is the result as it was, however there is basically no data changed.
I don't understand it.

Anyway, thanks a lot for looking into it.

I will attach the truncated optimizer trace as well as the execution plans.

In our application use case the two queries are equivalent.

With regard to the subselects with the ...orel-tables: These tables contain the permissions on records in the corresponding ...0-table, the integers that are compared to the OID column are users and groups. The permission system is quite complex, generic and not easily changeable. What I learned from optimizing queries in the past is that it is actually never a good idea to start a query's evaluation in the ...orel-table. Is there a way to give the optimizer a hint to evaluate the subselect on the emailstoreorel-table at last?
I tried to replace the OR in the subselect with an UNION, however I am waiting more than 10 minutes for the result, probably it will be around 75 min. again:
SELECT EMAILSTORE.ISFORMEMAIL, EMAILSTORE.SENDDATE, EMAILSTORE.SUBJECT, EMAILSTORE.XFROM, EMAILSTORE.XTO, EMAILSTORE.HASATTACHMENTS, EMAILSTORE.GGUID 
FROM `svg`.EMAILSTORE0 AS EMAILSTORE 
WHERE 
	((EMAILSTORE.GGUID IN (SELECT rel.GUID1 FROM `svg`.TableRelation AS rel INNER JOIN `svg`.TODO0 AS TODOC7504C2A4C0C38BDBE403DA9CA19A0DF ON rel.GUID2 = TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID WHERE ((TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.KEYWORD LIKE '%antragsanforderung%' AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.WORKINGPERCENT = '100') AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID IN (SELECT TABLEGUID FROM `svg`.TODOORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ForeignEditPermission = 65535))))) AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISDELETED = 0 AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISTEMPLATE = 0))) 
	AND (EMAILSTORE.GGUID IN (SELECT TABLEGUID FROM `svg`.EMAILSTOREORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0))))) 
	AND (EMAILSTORE.ISDELETED = 0 AND EMAILSTORE.ISTEMPLATE = 0) 
UNION
SELECT EMAILSTORE.ISFORMEMAIL, EMAILSTORE.SENDDATE, EMAILSTORE.SUBJECT, EMAILSTORE.XFROM, EMAILSTORE.XTO, EMAILSTORE.HASATTACHMENTS, EMAILSTORE.GGUID 
FROM `svg`.EMAILSTORE0 AS EMAILSTORE 
WHERE 
	((EMAILSTORE.GGUID IN (SELECT rel.GUID1 FROM `svg`.TableRelation AS rel INNER JOIN `svg`.TODO0 AS TODOC7504C2A4C0C38BDBE403DA9CA19A0DF ON rel.GUID2 = TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID WHERE ((TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.KEYWORD LIKE '%antragsanforderung%' AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.WORKINGPERCENT = '100') AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID IN (SELECT TABLEGUID FROM `svg`.TODOORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ForeignEditPermission = 65535))))) AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISDELETED = 0 AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISTEMPLATE = 0))) 
	AND (EMAILSTORE.GGUID IN (SELECT TABLEGUID FROM `svg`.EMAILSTOREORel WHERE EIMRight >= 64 AND OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9))))
	AND EMAILSTORE.ForeignEditPermission = 65535
	AND (EMAILSTORE.ISDELETED = 0 AND EMAILSTORE.ISTEMPLATE = 0)
ORDER BY SENDDATE DESC, GGUID ASC LIMIT 0, 100;

Thanks again for helping. Let me know if I can provide further information.
[6 Feb 2014 14:49] Martin Kirchner
Execution plan of the subselect

Attachment: live_execution_plan_subselect_20140204_after_restart.txt (text/plain), 17.62 KiB.

[6 Feb 2014 14:50] Martin Kirchner
Execution plan or the INNER JOIN (on live)

Attachment: live_execution_plan_innerJoin_20140204_after_restart.txt (text/plain), 16.24 KiB.

[6 Feb 2014 14:50] Martin Kirchner
Trace of subselect on live

Attachment: live_trace_subselect_20140206_after_restart.txt (text/plain), 302.43 KiB.

[6 Feb 2014 14:50] Martin Kirchner
Trace of inner join on live

Attachment: live_trace_inner_join_20140206_after_restart.txt (text/plain), 267.07 KiB.

[6 Feb 2014 14:54] Martin Kirchner
Execution plan or the INNER JOIN (on test vm)

Attachment: testvm_execution_plan_innerjoin_20140206.txt (text/plain), 9.93 KiB.

[6 Feb 2014 14:54] Martin Kirchner
Execution plan of the subselect (on test vm)

Attachment: testvm_execution_plan_subselect_20140206.txt (text/plain), 11.88 KiB.

[6 Feb 2014 15:05] Sinisa Milivojevic
Thank you Martin for your data.

Couple of other info that might be useful and required. 

I suppose that you are using InnoDB tables and that you have not changed defaults for any of the --innodb-stats-* settings.

When you get such slow results, can you try running ANALYZE on all tables involved and try the queries again ???

Also, please try using UNION ALL with JOIN queries ...
[7 Feb 2014 12:54] Martin Kirchner
I did not change any of the --innodb-stats-* settings.
UNION ALL does not help because of duplicates.

But I might have found a solution that runs in acceptable time on the live system (and its two replicated siblings) as well as on the test vm. I tried to replace the subselect with an EXISTS.
EXISTS for subselect in todoorel --> slow
EXISTS for subselect in emailstoreorel --> fast 
EXISTS for subselect in emailstoreorel and todoorel --> slower as any of the other tries before
EXISTS for subselect in tablerelation/todo0 --> fast

I'll attach the execution plan and optimizer trace for the latter.

SELECT EMAILSTORE.ISFORMEMAIL, EMAILSTORE.SENDDATE, EMAILSTORE.SUBJECT, EMAILSTORE.XFROM, EMAILSTORE.XTO, EMAILSTORE.HASATTACHMENTS, EMAILSTORE.GGUID 
FROM `svg`.EMAILSTORE0 AS EMAILSTORE 
WHERE 
	((EXISTS (SELECT rel.GUID1 FROM `svg`.TableRelation AS rel INNER JOIN `svg`.TODO0 AS TODOC7504C2A4C0C38BDBE403DA9CA19A0DF ON rel.GUID2 = TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID WHERE EMAILSTORE.GGUID = rel.GUID1 AND ((TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.KEYWORD LIKE '%antragsanforderung%' AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.WORKINGPERCENT = '100') AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.GGUID IN (SELECT TABLEGUID FROM `svg`.TODOORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ForeignEditPermission = 65535))))) AND (TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISDELETED = 0 AND TODOC7504C2A4C0C38BDBE403DA9CA19A0DF.ISTEMPLATE = 0))) 
	AND (EMAILSTORE.GGUID IN (SELECT TABLEGUID FROM `svg`.EMAILSTOREORel WHERE EIMRight >= 64 AND (OID IN (1014, -426, -396, -98, -305, -50, -215, -8, -100, -366, -88, -90, -279, -319, -314, -270, -99, -428, -92, -431, -317, -427, -430, -320, -95, -101, 0) OR (OID IN (4328, -314, -215, -159, -216, 4389, 4390, 4392, 4093, 4399, 4109, 4355, 4114, 4115, 1032, 1033, 1034, 3055, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 3756, 3755, 4456, 4443, 4189, 3519, 3406, 3944, 3407, 3945, 3946, 3947, 3936, 3937, 3938, 3939, 3940, 3941, 3942, 3943, 4527, 4226, 3453, 3454, 3935, 3934, 1016, 3096, 1017, 1018, 4332, 1019, 1020, 1021, 1022, 1023, 3089, 1008, 1009, 3091, 1010, 3090, 3093, 1012, 1013, 3094, 1015, 1001, 1000, 1003, 1002, 1005, 1004, 1007, 1006, 997, 996, 999, 3616, 3613, 3855, 3615, 3852, 3609, 3850, 3608, 3848, 3610, 3849, 3846, 3847, 3607, 3844, 3606, 3845, 3842, 3843, 3840, 3841, 4550, 4400, 4401, 4402, 4403, 4464, 4404, 4465, 4461, 4460, 4463, 4462, 4457, 4459, 4458, 3600, 3596, 3597, 3598, 3599, 3592, 3593, 3594, 3595, 3588, 3589, 3590, 3591, -93, -101, -8, -99, -50, -95, -100, -98, -92, -161, -380, -217, -148, -307, -90, -323, -321, -110, -150, -103, -109, -107, -149, -218, -324, -88, -415, -319, -320, -305, -317, -427, -357, -270, -279, -428, -105, -366, -91, -102, -365, -306, -313, -311, -308, -309, -9) AND EMAILSTORE.ForeignEditPermission = 65535))))) 
	AND (EMAILSTORE.ISDELETED = 0 AND EMAILSTORE.ISTEMPLATE = 0) 
ORDER BY EMAILSTORE.SENDDATE DESC, EMAILSTORE.GGUID ASC LIMIT 0, 100;
[7 Feb 2014 12:55] Martin Kirchner
Execution plan of EXISTS in tablerelation (on live)

Attachment: live_execution_plan_exists_tablerelation_20140207.txt (text/plain), 19.39 KiB.

[7 Feb 2014 12:57] Martin Kirchner
Optimizer trace on LIVE - exists tablerelation - executed in 3,5s

Attachment: live_trace_exists_tablerelation_20140207_after_restart2.zip (application/x-zip-compressed, text), 72.53 KiB.

[7 Feb 2014 13:30] Øystein Grøvlen
Hi Martin,

As Sinisa indicates, it is probably variation in statistics that cause different plans to happen.  If statistics change on restart, you are probably still using so-called transient statistics for your tables.  If you switch to persistent InnoDB statistics (new in 5.6), the statistics should be stable across restarts.

Another statistics issue that may hit you, is a new 5.6 variable eq_range_index_dive_limit.  For IN lists with many elements, it determines whether the optimization should be based on general statistics or determines through index look-ups.  By default, for all IN lists with more than 10 elements the general statistics would be used.  To get the 5.5 behavior where optimizer will do index look-ups and get estimates for each given value, you can set eq_range_index_dive_limit to 0.  This will give more accurate estimates, but query optimization will also be more costly.  Especially, when the distribution of column values are skewed, skipping index dives may give wrong estimates. 

Looking at the chosen plans, it seems the main reason why queries takes very long is that MySQL for some reason chooses to do a table scan of TODO0 instead of a PRIMARY key look-up.  You could try to use a hint like '... TODO0 FORCE INDEX(PRIMARY)', to see if that could give a more optimal plan.  

In general, it is normally best to start the join with the table that has the predicate with highest selectivity. Since I do not know the database, it is a bit hard to say, but maybe starting with TODO0 could be an idea (depending on the selectivity of the predicate on TODO0.KEYWORD).  Using the JOIN variant of the query you could use STRAIGHT_JOIN instead of INNER JOIN to try out different join orders. E.g., "TODO0 STRAIGHT_JOIN EMAILSTORE0" will tell the optimizer to only consider plans where TODO0 is processed before EMAILSTORE0.

Finally, my idea about using UNION was to avoid the OR expressions and references to so-called outer tables.  I think something like the below should be equivalent, but no guarantees (neither with respect to correctness nor performance).  The main point is to be able to pull the reference to ForeignEditPermission out of the sub-query.

SELECT ...
FROM EMAILSTORE0 AS EMAILSTORE
WHERE ((EMAILSTORE.GGUID IN 
        (SELECT rel.GUID1 
	 FROM TableRelation AS rel INNER JOIN TODO0 ON rel.GUID2 = TODO0.GGUID 
         WHERE ((TODO0.KEYWORD LIKE '%antragsanforderung%'
                 AND TODO0.WORKINGPERCENT = '100') 
                AND (TODO0.GGUID IN 
                     (SELECT TABLEGUID FROM TODOORel 
                      WHERE EIMRight >= 64 AND OID IN (<SetA>))))
           AND (TODO0.ISDELETED = 0 AND TODO0.ISTEMPLATE = 0)))
       AND (EMAILSTORE.GGUID IN 
            (SELECT TABLEGUID FROM EMAILSTOREORel 
             WHERE EIMRight >= 64 AND OID IN (<SetA>))))
  AND (EMAILSTORE.ISDELETED = 0 AND EMAILSTORE.ISTEMPLATE = 0)
UNION ALL
SELECT ...
FROM EMAILSTORE0 AS EMAILSTORE
WHERE ((EMAILSTORE.GGUID IN 
        (SELECT rel.GUID1 
	 FROM TableRelation AS rel INNER JOIN TODO0 ON rel.GUID2 = TODO0.GGUID 
         WHERE ((TODO0.KEYWORD LIKE '%antragsanforderung%'
                 AND TODO0.WORKINGPERCENT = '100') 
                AND (TODO0.GGUID IN 
                     (SELECT TABLEGUID FROM TODOORel 
                      WHERE EIMRight >= 64 AND OID IN (<SetB>))))
           AND (TODO0.ISDELETED = 0 AND TODO0.ISTEMPLATE = 0)))
       AND (EMAILSTORE.GGUID IN 
            (SELECT TABLEGUID FROM EMAILSTOREORel 
             WHERE EIMRight >= 64 AND OID IN (<SetB>))))
  AND (EMAILSTORE.ISDELETED = 0 AND EMAILSTORE.ISTEMPLATE = 0)
  AND EMAILSTORE.ForeignEditPermission = 65535
ORDER BY EMAILSTORE.SENDDATE DESC, EMAILSTORE.GGUID ASC
LIMIT 0, 100;
[7 Feb 2014 14:42] Øystein Grøvlen
Hi Martin,
Thanks for sharing your experiments.  Replacing IN with EXISTS is a good idea.  Since the semijoin optimization in MySQL 5.6 only works for IN, not for EXISTS, you will work around the cost calculation bug that way.  However, I suspect there is potential for even further performance improvements once we fix the bug.

We have an idea of how to fix this bug. If we send you a patch, would it be possible for you to try it out? (Requires that you build MySQL from source).  Alternatively, if you provide us with data to reproduce this problem, we could test it out ourselves.
[7 Feb 2014 15:40] Martin Kirchner
Hi Øystein,
thanks for your commitment! I'd be more than happy to try out the patch. I've never built MySQL from source, however the steps in the documentation do not sound too complex.
As it is a customer's system I'll have to seek their approval on Monday but I assume that should be possible.

Changing eq_range_index_dive_limit to 0 did not help, however the index hint on TODO0 seems to be perform a miracle. The result is returned within 1s - on all machines! Now I have to check if it's generally a good idea to use this kind of hint for all types of this subselect (the user can define it quite generically in the GUI).
Thanks again.

Nonetheless I'd be happy to try your patch.
Enjoy your weekend.
[10 Feb 2014 14:00] Martin Kirchner
I have a go to try your patch. Please let me know where I can get it.
Kind regards,
Martin
[11 Feb 2014 17:23] Sinisa Milivojevic
Mr. Kirchner,

This patch is being worked upon with great priority. After a work on patch is finished, then it needs to be tested and to get all approvals necessary. We shall do our best to make the process as fast as possible, but at this moment we can not tell you exactly when will the patch be available for you. You shall be hearing from us soon.
[28 Mar 2014 7:16] Martin Kirchner
Could you please provide a status update?
Thank you in advance.
[29 Jun 2015 15:34] Paul Dubois
Noted in 5.6.26, 5.7.8, 5.8.0 changelogs.

When choosing join order, the optimizer could incorrectly calculate
the cost of a table scan and choose a table scan over a more
efficient eq_ref join.