This first patch prepared for the task MDEV-13369:

"Optimization for equi-joins of derived tables with GROUP BY"
should be considered rather as a 'proof of concept'.

The task itself is targeted at an optimization that employs re-writing
equi-joins with grouping derived tables / views into lateral
derived tables. Here's an example of such transformation:
  select t1.a,t.max,t.min
  from t1 [left] join
       (select a, max(t2.b) max, min(t2.b) min from t2
       group by t2.a) as t
       on t1.a=t.a;
=>
  select t1.a,tl.max,tl.min
  from t1 [left] join
       lateral (select a, max(t2.b) max, min(t2.b) min from t2
                where  t1.a=t2.a) as t
       on 1=1;
The transformation pushes the equi-join condition t1.a=t.a into the
derived table making it dependent on table t1. It means that for
every row from t1 a new derived table must be filled out. However
the size of any of these derived tables is just a fraction of the
original derived table t. One could say that transformation 'splits'
the rows used for the GROUP BY operation into separate groups
performing aggregation for a group only in the case when there is
a match for the current row of t1.
Apparently the transformation may produce a query with a better
performance only in the case when
 - the GROUP BY list refers only to fields returned by the derived table
 - there is an index I on one of the tables T used in FROM list of
   the specification of the derived table whose prefix covers the
   the fields from the proper beginning of the GROUP BY list or
   fields that are equal to those fields.
Whether the result of the re-writing can be executed faster depends
on many factors:
  - the size of the original derived table
  - the size of the table T
  - whether the index I is clustering for table T
  - whether the index I fully covers the GROUP BY list.

This patch only tries to improve the chosen execution plan using
this transformation. It tries to do it only when the chosen
plan reaches the derived table by a key whose prefix covers
all the fields of the derived table produced by the fields of
the table T from the GROUP BY list.
The code of the patch does not evaluates the cost of the improved
plan. If certain conditions are met the transformation is applied.

1 files changed, 438 insertions, 0 deletions

diff --git a/mysql-test/r/derived_cond_pushdown.result b/mysql-test/r/derived_cond_pushdown.result
index 5b07b0488e0..51fc63371e8 100644
--- a/mysql-test/r/derived_cond_pushdown.result
+++ b/mysql-test/r/derived_cond_pushdown.result
@@ -8782,3 +8782,441 @@ EXPLAIN
 }
 DROP VIEW v2;
 DROP TABLE t1,t2;
+#
+# MDEV-13369: Optimization for equi-joins of grouping derived tables 
+#             (Splitting derived tables / views with GROUP BY)
+#
+create table t1 (a int);
+insert into t1 values
+(8), (5), (1), (2), (9), (7), (2), (7);
+create table t2 (a int, b int, index idx(a));
+insert into t2 values
+(7,10), (1,20), (2,23), (7,18), (1,30),
+(4,71), (3,15), (7,82), (8,12), (4,15),
+(11,33), (10,42), (4,53), (10,17), (2,90);
+set statement optimizer_switch='split_grouping_derived=off' for select t1.a,t.max,t.min
+from t1 join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+a	max	min
+8	12	12
+1	30	20
+2	90	23
+7	82	10
+2	90	23
+7	82	10
+select t1.a,t.max,t.min
+from t1 join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+a	max	min
+8	12	12
+1	30	20
+2	90	23
+7	82	10
+2	90	23
+7	82	10
+explain extended select t1.a,t.max,t.min
+from t1 join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	8	100.00	Using where
+1	PRIMARY	<derived2>	ref	key0	key0	5	test.t1.a	2	100.00	
+2	LATERAL DERIVED	t2	ref	idx	idx	5	test.t1.a	2	100.00	
+Warnings:
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,`t`.`max` AS `max`,`t`.`min` AS `min` from `test`.`t1` join (/* select#2 */ select `test`.`t2`.`a` AS `a`,max(`test`.`t2`.`b`) AS `max`,min(`test`.`t2`.`b`) AS `min` from `test`.`t2` where `test`.`t2`.`a` = `test`.`t1`.`a` group by `test`.`t2`.`a`) `t` where `t`.`a` = `test`.`t1`.`a`
+explain format=json select t1.a,t.max,t.min
+from t1 join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+EXPLAIN
+{
+  "query_block": {
+    "select_id": 1,
+    "table": {
+      "table_name": "t1",
+      "access_type": "ALL",
+      "rows": 8,
+      "filtered": 100,
+      "attached_condition": "t1.a is not null"
+    },
+    "table": {
+      "table_name": "<derived2>",
+      "access_type": "ref",
+      "possible_keys": ["key0"],
+      "key": "key0",
+      "key_length": "5",
+      "used_key_parts": ["a"],
+      "ref": ["test.t1.a"],
+      "rows": 2,
+      "filtered": 100,
+      "materialized": {
+        "query_block": {
+          "select_id": 2,
+          "outer_ref_condition": "t1.a is not null",
+          "table": {
+            "table_name": "t2",
+            "access_type": "ref",
+            "possible_keys": ["idx"],
+            "key": "idx",
+            "key_length": "5",
+            "used_key_parts": ["a"],
+            "ref": ["test.t1.a"],
+            "rows": 2,
+            "filtered": 100
+          }
+        }
+      }
+    }
+  }
+}
+set statement optimizer_switch='split_grouping_derived=off' for select t1.a,t.max,t.min
+from t1 left join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+a	max	min
+8	12	12
+5	NULL	NULL
+1	30	20
+2	90	23
+9	NULL	NULL
+7	82	10
+2	90	23
+7	82	10
+select t1.a,t.max,t.min
+from t1 left join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+a	max	min
+8	12	12
+5	NULL	NULL
+1	30	20
+2	90	23
+9	NULL	NULL
+7	82	10
+2	90	23
+7	82	10
+explain extended select t1.a,t.max,t.min
+from t1 left join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	8	100.00	
+1	PRIMARY	<derived2>	ref	key0	key0	5	test.t1.a	2	100.00	Using where
+2	LATERAL DERIVED	t2	ref	idx	idx	5	test.t1.a	2	100.00	
+Warnings:
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,`t`.`max` AS `max`,`t`.`min` AS `min` from `test`.`t1` left join (/* select#2 */ select `test`.`t2`.`a` AS `a`,max(`test`.`t2`.`b`) AS `max`,min(`test`.`t2`.`b`) AS `min` from `test`.`t2` where `test`.`t2`.`a` = `test`.`t1`.`a` group by `test`.`t2`.`a`) `t` on(`t`.`a` = `test`.`t1`.`a` and `test`.`t1`.`a` is not null) where 1
+explain format=json select t1.a,t.max,t.min
+from t1 left join
+(select a, max(t2.b) max, min(t2.b) min from t2 group by t2.a) t
+on t1.a=t.a;
+EXPLAIN
+{
+  "query_block": {
+    "select_id": 1,
+    "const_condition": "1",
+    "table": {
+      "table_name": "t1",
+      "access_type": "ALL",
+      "rows": 8,
+      "filtered": 100
+    },
+    "table": {
+      "table_name": "<derived2>",
+      "access_type": "ref",
+      "possible_keys": ["key0"],
+      "key": "key0",
+      "key_length": "5",
+      "used_key_parts": ["a"],
+      "ref": ["test.t1.a"],
+      "rows": 2,
+      "filtered": 100,
+      "attached_condition": "trigcond(trigcond(t1.a is not null))",
+      "materialized": {
+        "query_block": {
+          "select_id": 2,
+          "outer_ref_condition": "t1.a is not null",
+          "table": {
+            "table_name": "t2",
+            "access_type": "ref",
+            "possible_keys": ["idx"],
+            "key": "idx",
+            "key_length": "5",
+            "used_key_parts": ["a"],
+            "ref": ["test.t1.a"],
+            "rows": 2,
+            "filtered": 100
+          }
+        }
+      }
+    }
+  }
+}
+create table t3 (a int, c varchar(16));
+insert into t3 values
+(8,'aa'), (5,'cc'), (1,'bb'), (2,'aa'), (9,'cc'),
+(7,'aa'), (2,'aa'), (7,'bb');
+create table t4 (a int, b int, c varchar(16), index idx(a,c));
+insert into t4 values
+(7,10,'cc'), (1,20,'aa'), (2,23,'bb'), (7,18,'cc'), (1,30,'bb'),
+(4,71,'xx'), (3,15,'aa'), (7,82,'bb'), (8,12,'dd'), (4,15,'aa'),
+(11,33,'yy'), (10,42,'zz'), (4,53,'xx'), (10,17,'yy'), (7,12,'bb'),
+(8,20,'dd'), (7,32,'bb'), (1,50,'aa'), (3,40,'bb'), (3,77,'aa');
+set statement optimizer_switch='split_grouping_derived=off' for select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by a,c) t
+on t3.a=t.a and t3.c=t.c;
+a	c	max	min
+1	bb	30	30
+7	bb	82	12
+select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by a,c) t
+on t3.a=t.a and t3.c=t.c;
+a	c	max	min
+1	bb	30	30
+7	bb	82	12
+explain extended select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by a,c) t
+on t3.a=t.a and t3.c=t.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	8	100.00	Using where
+1	PRIMARY	<derived2>	ref	key0	key0	24	test.t3.a,test.t3.c	2	100.00	
+2	LATERAL DERIVED	t4	ref	idx	idx	24	test.t3.a,test.t3.c	2	100.00	
+Warnings:
+Note	1003	/* select#1 */ select `test`.`t3`.`a` AS `a`,`test`.`t3`.`c` AS `c`,`t`.`max` AS `max`,`t`.`min` AS `min` from `test`.`t3` join (/* select#2 */ select `test`.`t4`.`a` AS `a`,`test`.`t4`.`c` AS `c`,max(`test`.`t4`.`b`) AS `max`,min(`test`.`t4`.`b`) AS `min` from `test`.`t4` where `test`.`t4`.`a` = `test`.`t3`.`a` and `test`.`t4`.`c` = `test`.`t3`.`c` group by `test`.`t4`.`a`,`test`.`t4`.`c`) `t` where `t`.`a` = `test`.`t3`.`a` and `t`.`c` = `test`.`t3`.`c`
+explain format=json select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by a,c) t
+on t3.a=t.a and t3.c=t.c;
+EXPLAIN
+{
+  "query_block": {
+    "select_id": 1,
+    "table": {
+      "table_name": "t3",
+      "access_type": "ALL",
+      "rows": 8,
+      "filtered": 100,
+      "attached_condition": "t3.a is not null and t3.c is not null"
+    },
+    "table": {
+      "table_name": "<derived2>",
+      "access_type": "ref",
+      "possible_keys": ["key0"],
+      "key": "key0",
+      "key_length": "24",
+      "used_key_parts": ["a", "c"],
+      "ref": ["test.t3.a", "test.t3.c"],
+      "rows": 2,
+      "filtered": 100,
+      "materialized": {
+        "query_block": {
+          "select_id": 2,
+          "outer_ref_condition": "t3.a is not null and t3.c is not null",
+          "table": {
+            "table_name": "t4",
+            "access_type": "ref",
+            "possible_keys": ["idx"],
+            "key": "idx",
+            "key_length": "24",
+            "used_key_parts": ["a", "c"],
+            "ref": ["test.t3.a", "test.t3.c"],
+            "rows": 2,
+            "filtered": 100
+          }
+        }
+      }
+    }
+  }
+}
+set statement optimizer_switch='split_grouping_derived=off' for select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by c,a) t
+on t3.a=t.a and t3.c=t.c;
+a	c	max	min
+1	bb	30	30
+7	bb	82	12
+select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by c,a) t
+on t3.a=t.a and t3.c=t.c;
+a	c	max	min
+1	bb	30	30
+7	bb	82	12
+explain extended select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by c,a) t
+on t3.a=t.a and t3.c=t.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	8	100.00	Using where
+1	PRIMARY	<derived2>	ref	key0	key0	24	test.t3.a,test.t3.c	2	100.00	
+2	LATERAL DERIVED	t4	ref	idx	idx	24	test.t3.a,test.t3.c	2	100.00	
+Warnings:
+Note	1003	/* select#1 */ select `test`.`t3`.`a` AS `a`,`test`.`t3`.`c` AS `c`,`t`.`max` AS `max`,`t`.`min` AS `min` from `test`.`t3` join (/* select#2 */ select `test`.`t4`.`a` AS `a`,`test`.`t4`.`c` AS `c`,max(`test`.`t4`.`b`) AS `max`,min(`test`.`t4`.`b`) AS `min` from `test`.`t4` where `test`.`t4`.`c` = `test`.`t3`.`c` and `test`.`t4`.`a` = `test`.`t3`.`a` group by `test`.`t4`.`c`,`test`.`t4`.`a`) `t` where `t`.`a` = `test`.`t3`.`a` and `t`.`c` = `test`.`t3`.`c`
+explain format=json select t3.a,t3.c,t.max,t.min
+from t3 join
+(select a, c, max(b) max, min(b) min from t4 group by c,a) t
+on t3.a=t.a and t3.c=t.c;
+EXPLAIN
+{
+  "query_block": {
+    "select_id": 1,
+    "table": {
+      "table_name": "t3",
+      "access_type": "ALL",
+      "rows": 8,
+      "filtered": 100,
+      "attached_condition": "t3.a is not null and t3.c is not null"
+    },
+    "table": {
+      "table_name": "<derived2>",
+      "access_type": "ref",
+      "possible_keys": ["key0"],
+      "key": "key0",
+      "key_length": "24",
+      "used_key_parts": ["a", "c"],
+      "ref": ["test.t3.a", "test.t3.c"],
+      "rows": 2,
+      "filtered": 100,
+      "materialized": {
+        "query_block": {
+          "select_id": 2,
+          "outer_ref_condition": "t3.a is not null and t3.c is not null",
+          "table": {
+            "table_name": "t4",
+            "access_type": "ref",
+            "possible_keys": ["idx"],
+            "key": "idx",
+            "key_length": "24",
+            "used_key_parts": ["a", "c"],
+            "ref": ["test.t3.a", "test.t3.c"],
+            "rows": 2,
+            "filtered": 100
+          }
+        }
+      }
+    }
+  }
+}
+drop index idx on t2;
+create index idx on t2(b);
+create index idx on t3(a);
+create index idx2 on t4(c);
+insert into t3 select * from t3;
+insert into t3 select * from t3;
+insert into t4 select * from t4;
+set statement optimizer_switch='split_grouping_derived=off' for select t2.a,t2.b,t3.c,t.max,t.min
+from t2, t3, (select c, max(b) max, min(b) min from t4 group by c) t
+where t2.b > 50 and t2.a=t3.a and t3.c=t.c;
+a	b	c	max	min
+7	82	aa	77	15
+7	82	bb	82	12
+7	82	aa	77	15
+7	82	bb	82	12
+7	82	aa	77	15
+7	82	bb	82	12
+7	82	aa	77	15
+7	82	bb	82	12
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+select t2.a,t2.b,t3.c,t.max,t.min
+from t2, t3, (select c, max(b) max, min(b) min from t4 group by c) t
+where t2.b > 50 and t2.a=t3.a and t3.c=t.c;
+a	b	c	max	min
+7	82	aa	77	15
+7	82	bb	82	12
+7	82	aa	77	15
+7	82	bb	82	12
+7	82	aa	77	15
+7	82	bb	82	12
+7	82	aa	77	15
+7	82	bb	82	12
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+2	90	aa	77	15
+explain extended select t2.a,t2.b,t3.c,t.max,t.min
+from t2, t3, (select c, max(b) max, min(b) min from t4 group by c) t
+where t2.b > 50 and t2.a=t3.a and t3.c=t.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	PRIMARY	t2	range	idx	idx	5	NULL	5	100.00	Using index condition; Using where
+1	PRIMARY	t3	ref	idx	idx	5	test.t2.a	3	100.00	Using where
+1	PRIMARY	<derived2>	ref	key0	key0	19	test.t3.c	4	100.00	
+2	LATERAL DERIVED	t4	ref	idx2	idx2	19	test.t3.c	5	100.00	
+Warnings:
+Note	1003	/* select#1 */ select `test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t3`.`c` AS `c`,`t`.`max` AS `max`,`t`.`min` AS `min` from `test`.`t2` join `test`.`t3` join (/* select#2 */ select `test`.`t4`.`c` AS `c`,max(`test`.`t4`.`b`) AS `max`,min(`test`.`t4`.`b`) AS `min` from `test`.`t4` where `test`.`t4`.`c` = `test`.`t3`.`c` group by `test`.`t4`.`c`) `t` where `test`.`t3`.`a` = `test`.`t2`.`a` and `t`.`c` = `test`.`t3`.`c` and `test`.`t2`.`b` > 50
+explain format=json select t2.a,t2.b,t3.c,t.max,t.min
+from t2, t3, (select c, max(b) max, min(b) min from t4 group by c) t
+where t2.b > 50 and t2.a=t3.a and t3.c=t.c;
+EXPLAIN
+{
+  "query_block": {
+    "select_id": 1,
+    "table": {
+      "table_name": "t2",
+      "access_type": "range",
+      "possible_keys": ["idx"],
+      "key": "idx",
+      "key_length": "5",
+      "used_key_parts": ["b"],
+      "rows": 5,
+      "filtered": 100,
+      "index_condition": "t2.b > 50",
+      "attached_condition": "t2.a is not null"
+    },
+    "table": {
+      "table_name": "t3",
+      "access_type": "ref",
+      "possible_keys": ["idx"],
+      "key": "idx",
+      "key_length": "5",
+      "used_key_parts": ["a"],
+      "ref": ["test.t2.a"],
+      "rows": 3,
+      "filtered": 100,
+      "attached_condition": "t3.c is not null"
+    },
+    "table": {
+      "table_name": "<derived2>",
+      "access_type": "ref",
+      "possible_keys": ["key0"],
+      "key": "key0",
+      "key_length": "19",
+      "used_key_parts": ["c"],
+      "ref": ["test.t3.c"],
+      "rows": 4,
+      "filtered": 100,
+      "materialized": {
+        "query_block": {
+          "select_id": 2,
+          "outer_ref_condition": "t3.c is not null",
+          "table": {
+            "table_name": "t4",
+            "access_type": "ref",
+            "possible_keys": ["idx2"],
+            "key": "idx2",
+            "key_length": "19",
+            "used_key_parts": ["c"],
+            "ref": ["test.t3.c"],
+            "rows": 5,
+            "filtered": 100
+          }
+        }
+      }
+    }
+  }
+}
+drop table t1,t2,t3,t4;