[Commits] c5b7cc28b0c: MDEV-20129: Equality propagation for ORDER BY items do not work with expressions

Varun varunraiko1803 at gmail.com
Mon Jul 29 22:02:26 EEST 2019


revision-id: c5b7cc28b0cbc15c9bf44fe5a74e8ef363773133 (mariadb-10.4.4-255-gc5b7cc28b0c)
parent(s): ddce85907611e0533d6226de7f53e751cf173f6a
author: Varun Gupta
committer: Varun Gupta
timestamp: 2019-07-30 00:29:11 +0530
message:

MDEV-20129: Equality propagation for ORDER BY items do not work with expressions

Introduced a function equality_propagation_for_order_items, that would propagate
equalities to order by clause and will substitute them with the best field

---
 mysql-test/main/order_by.result | 110 ++++++++++++++++++++++++++++++++++++++++
 mysql-test/main/order_by.test   |  54 ++++++++++++++++++++
 sql/item.cc                     |  50 ++++++++++++++++++
 sql/item.h                      |  20 ++++++++
 sql/item_func.cc                |  11 ++++
 sql/item_func.h                 |   5 ++
 sql/sql_select.cc               |  23 +++------
 7 files changed, 258 insertions(+), 15 deletions(-)

diff --git a/mysql-test/main/order_by.result b/mysql-test/main/order_by.result
index b059cc686cd..54190d2f608 100644
--- a/mysql-test/main/order_by.result
+++ b/mysql-test/main/order_by.result
@@ -3436,3 +3436,113 @@ Note	1003	select `test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` A
 set histogram_size=@tmp_h, histogram_type=@tmp_ht, use_stat_tables=@tmp_u,
 optimizer_use_condition_selectivity=@tmp_o;
 drop table t1,t2,t3,t4;
+create table ten(a int);
+insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table one_k(a int);
+insert into one_k select A.a + B.a* 10 + C.a * 100 from ten A, ten B, ten C;
+create table t1(a int, b int);
+insert into t1 select A.a + B.a* 10, A.a + B.a* 10 from ten A, ten B;
+create table t2(a int, b int, key(a));
+insert into t2 select A.a + B.a* 10, A.a+B.a*10 from ten A, ten B;
+should have Using  Filesort only
+explain select * from t1,t2 where t1.a > 95  and t1.a=t2.a order by t2.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using where; Using filesort
+1	SIMPLE	t2	ref	a	a	5	test.t1.a	1	
+should have Using  Filesort only with expressions too
+explain select * from t1,t2 where t1.a > 95  and t1.a=t2.a order by t2.a+t1.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using where; Using filesort
+1	SIMPLE	t2	ref	a	a	5	test.t1.a	1	
+drop table t1,t2,ten,one_k;
+CREATE TABLE t1(a int, b int);
+CREATE TABLE t2(a int, b int, index i(a));
+INSERT INTO t1 VALUES (1,1), (2,2);
+INSERT INTO t2 VALUES (1,5), (1,6), (2,5), (2,6);
+INSERT INTO t2 VALUES (1,5), (1,6), (2,5), (2,6);
+INSERT INTO t2 VALUES (1,5), (1,6), (2,5), (2,6);
+CREATE VIEW v1 AS
+SELECT t1.a as c, t2.a as d FROM t1,t2 WHERE t1.a=t2.a;
+CREATE VIEW v2 AS
+SELECT t1.a+t2.a as c, abs(t2.a) as d FROM t1,t2 WHERE t1.a=t2.a;
+should have Using Filesort only
+explain SELECT c,d FROM v1 ORDER BY c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	2	Using where; Using filesort
+1	SIMPLE	t2	ref	i	i	5	test.t1.a	2	Using index
+SELECT c,d FROM v1 ORDER BY c;
+c	d
+1	1
+1	1
+1	1
+1	1
+1	1
+1	1
+2	2
+2	2
+2	2
+2	2
+2	2
+2	2
+views use Item_direct_view_ref, so this shows equalities are propagated
+should have Using Filesort only
+explain SELECT c,d FROM v1 ORDER BY d;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	2	Using where; Using filesort
+1	SIMPLE	t2	ref	i	i	5	test.t1.a	2	Using index
+SELECT c,d FROM v1 ORDER BY d;
+c	d
+1	1
+1	1
+1	1
+1	1
+1	1
+1	1
+2	2
+2	2
+2	2
+2	2
+2	2
+2	2
+views use Item_direct_view_ref that are expressions
+should have Using Filesort only
+explain SELECT c,d FROM v2 ORDER BY c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	2	Using where; Using filesort
+1	SIMPLE	t2	ref	i	i	5	test.t1.a	2	Using index
+SELECT c,d FROM v2 ORDER BY c;
+c	d
+2	1
+2	1
+2	1
+2	1
+2	1
+2	1
+4	2
+4	2
+4	2
+4	2
+4	2
+4	2
+views use Item_direct_view_ref that are expressions
+should have Using Filesort only
+explain SELECT c,d FROM v2 ORDER BY d;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	2	Using where; Using filesort
+1	SIMPLE	t2	ref	i	i	5	test.t1.a	2	Using index
+SELECT c,d FROM v2 ORDER BY d;
+c	d
+2	1
+2	1
+2	1
+2	1
+2	1
+2	1
+4	2
+4	2
+4	2
+4	2
+4	2
+4	2
+DROP VIEW v1,v2;
+DROP TABLE t1, t2;
diff --git a/mysql-test/main/order_by.test b/mysql-test/main/order_by.test
index 934c503302f..2f39bb88329 100644
--- a/mysql-test/main/order_by.test
+++ b/mysql-test/main/order_by.test
@@ -2276,3 +2276,57 @@ set histogram_size=@tmp_h, histogram_type=@tmp_ht, use_stat_tables=@tmp_u,
     optimizer_use_condition_selectivity=@tmp_o; 
 
 drop table t1,t2,t3,t4;
+
+create table ten(a int);
+insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table one_k(a int);
+insert into one_k select A.a + B.a* 10 + C.a * 100 from ten A, ten B, ten C;
+create table t1(a int, b int);
+insert into t1 select A.a + B.a* 10, A.a + B.a* 10 from ten A, ten B;
+create table t2(a int, b int, key(a));
+insert into t2 select A.a + B.a* 10, A.a+B.a*10 from ten A, ten B;
+
+--echo should have Using  Filesort only
+explain select * from t1,t2 where t1.a > 95  and t1.a=t2.a order by t2.a;
+
+--echo should have Using  Filesort only with expressions too
+explain select * from t1,t2 where t1.a > 95  and t1.a=t2.a order by t2.a+t1.b;
+drop table t1,t2,ten,one_k;
+
+CREATE TABLE t1(a int, b int);
+CREATE TABLE t2(a int, b int, index i(a));
+INSERT INTO t1 VALUES (1,1), (2,2);
+INSERT INTO t2 VALUES (1,5), (1,6), (2,5), (2,6);
+INSERT INTO t2 VALUES (1,5), (1,6), (2,5), (2,6);
+INSERT INTO t2 VALUES (1,5), (1,6), (2,5), (2,6);
+CREATE VIEW v1 AS
+  SELECT t1.a as c, t2.a as d FROM t1,t2 WHERE t1.a=t2.a;
+
+CREATE VIEW v2 AS
+  SELECT t1.a+t2.a as c, abs(t2.a) as d FROM t1,t2 WHERE t1.a=t2.a;
+
+
+--echo should have Using Filesort only
+let $query= SELECT c,d FROM v1 ORDER BY c;
+eval explain $query;
+eval $query;
+
+--echo views use Item_direct_view_ref, so this shows equalities are propagated
+--echo should have Using Filesort only
+let $query= SELECT c,d FROM v1 ORDER BY d;
+eval explain $query;
+eval $query;
+
+--echo views use Item_direct_view_ref that are expressions
+--echo should have Using Filesort only
+let $query= SELECT c,d FROM v2 ORDER BY c;
+eval explain $query;
+eval $query;
+
+--echo views use Item_direct_view_ref that are expressions
+--echo should have Using Filesort only
+let $query= SELECT c,d FROM v2 ORDER BY d;
+eval explain $query;
+eval $query;
+DROP VIEW v1,v2;
+DROP TABLE t1, t2;
diff --git a/sql/item.cc b/sql/item.cc
index 42bcb216935..53220453cd9 100644
--- a/sql/item.cc
+++ b/sql/item.cc
@@ -6096,6 +6096,23 @@ Item *Item_field::propagate_equal_fields(THD *thd,
 }
 
 
+Item *Item_field::equality_propagation_for_order_items(THD *thd,
+                                                      const Context &ctx,
+                                                      COND_EQUAL *arg)
+{
+  Item *item= propagate_equal_fields(thd, ctx, arg);
+
+  DBUG_ASSERT(item);
+  Item_equal *item_eq;
+  if ((item_eq= item->get_item_equal()))
+  {
+    Item *first= item_eq->get_first(NO_PARTICULAR_TAB, NULL);
+    return first;
+  }
+  return item;
+}
+
+
 /**
   Replace an Item_field for an equal Item_field that evaluated earlier
   (if any).
@@ -7110,6 +7127,18 @@ Item* Item::propagate_equal_fields_and_change_item_tree(THD *thd,
 }
 
 
+Item* Item::equality_propagation_and_change_item_tree(THD *thd,
+                                                      const Context &ctx,
+                                                      COND_EQUAL *cond,
+                                                      Item **place)
+{
+  Item *item= equality_propagation_for_order_items(thd, ctx, cond);
+  if (item && item != this)
+    thd->change_item_tree(place, item);
+  return item;
+}
+
+
 void Item_field::update_null_value() 
 { 
   /* 
@@ -9003,6 +9032,17 @@ Item *Item_direct_view_ref::propagate_equal_fields(THD *thd,
 }
 
 
+Item *Item_direct_view_ref::equality_propagation_for_order_items(THD *thd,
+                                                            const Context &ctx,
+                                                            COND_EQUAL *arg)
+{
+  Item *item= real_item();
+  Item *res= item->equality_propagation_for_order_items(thd, ctx, arg);
+  set_item_equal(res->get_item_equal());
+  return res;
+}
+
+
 Item *Item_ref::propagate_equal_fields(THD *thd, const Context &ctx,
                                        COND_EQUAL *cond)
 {
@@ -9016,6 +9056,16 @@ Item *Item_ref::propagate_equal_fields(THD *thd, const Context &ctx,
 }
 
 
+Item *Item_ref::equality_propagation_for_order_items(THD *thd,
+                                                     const Context &ctx,
+                                                     COND_EQUAL *arg)
+{
+  Item *item= real_item();
+  Item *res= item->equality_propagation_for_order_items(thd, ctx, arg);
+  return res;
+}
+
+
 /**
   Replace an Item_direct_view_ref for an equal Item_field evaluated earlier
   (if any).
diff --git a/sql/item.h b/sql/item.h
index 14c29fe4e6a..b6ca0d81ad0 100644
--- a/sql/item.h
+++ b/sql/item.h
@@ -2022,10 +2022,26 @@ class Item: public Value_source,
     return this;
   };
 
+  /*
+    This function would propagate the equalities to the order item and
+    return the first item of the Item_equal if the field
+    has participated in an equality
+  */
+
+  virtual Item* equality_propagation_for_order_items(THD*, const Context &, COND_EQUAL *)
+  {
+    return this;
+  };
+
+
   Item* propagate_equal_fields_and_change_item_tree(THD *thd,
                                                     const Context &ctx,
                                                     COND_EQUAL *cond,
                                                     Item **place);
+  Item* equality_propagation_and_change_item_tree(THD *thd,
+                                                  const Context &ctx,
+                                                  COND_EQUAL *cond,
+                                                  Item **place);
 
   /* arg points to REPLACE_EQUAL_FIELD_ARG object */
   virtual Item *replace_equal_field(THD *thd, uchar *arg) { return this; }
@@ -2448,6 +2464,7 @@ class Item_args
   }
   bool transform_args(THD *thd, Item_transformer transformer, uchar *arg);
   void propagate_equal_fields(THD *, const Item::Context &, COND_EQUAL *);
+  void equality_propagation_for_order_items(THD *, const Item::Context &, COND_EQUAL *);
   bool excl_dep_on_table(table_map tab_map)
   {
     for (uint i= 0; i < arg_count; i++)
@@ -3392,6 +3409,7 @@ class Item_field :public Item_ident,
   void set_item_equal(Item_equal *item_eq) { item_equal= item_eq; }
   Item_equal *find_item_equal(COND_EQUAL *cond_equal);
   Item* propagate_equal_fields(THD *, const Context &, COND_EQUAL *);
+  Item* equality_propagation_for_order_items(THD *, const Context &, COND_EQUAL *);
   Item *replace_equal_field(THD *thd, uchar *arg);
   uint32 max_display_length() const { return field->max_display_length(); }
   Item_field *field_for_view_update() { return this; }
@@ -5120,6 +5138,7 @@ class Item_ref :public Item_ident,
   Field *create_tmp_field_ex(MEM_ROOT *root, TABLE *table, Tmp_field_src *src,
                              const Tmp_field_param *param);
   Item* propagate_equal_fields(THD *, const Context &, COND_EQUAL *);
+  Item* equality_propagation_for_order_items(THD *, const Context &, COND_EQUAL *);
   table_map used_tables() const;		
   void update_used_tables(); 
   COND *build_equal_items(THD *thd, COND_EQUAL *inherited,
@@ -5554,6 +5573,7 @@ class Item_direct_view_ref :public Item_direct_ref
   void set_item_equal(Item_equal *item_eq) { item_equal= item_eq; }
   Item_equal *find_item_equal(COND_EQUAL *cond_equal);
   Item* propagate_equal_fields(THD *, const Context &, COND_EQUAL *);
+  Item* equality_propagation_for_order_items(THD *, const Context &, COND_EQUAL *);
   Item *replace_equal_field(THD *thd, uchar *arg);
   table_map used_tables() const;
   void update_used_tables();
diff --git a/sql/item_func.cc b/sql/item_func.cc
index 03abe4f26fb..cdf710d9be0 100644
--- a/sql/item_func.cc
+++ b/sql/item_func.cc
@@ -561,6 +561,17 @@ void Item_args::propagate_equal_fields(THD *thd,
 }
 
 
+void Item_args::equality_propagation_for_order_items(THD *thd,
+                                                    const Item::Context &ctx,
+                                                    COND_EQUAL *cond)
+{
+  uint i;
+  for (i= 0; i < arg_count; i++)
+    args[i]->equality_propagation_and_change_item_tree(thd, ctx, cond,
+                                                        &args[i]);
+}
+
+
 /**
   See comments in Item_cond::split_sum_func()
 */
diff --git a/sql/item_func.h b/sql/item_func.h
index 00ed688e9e3..4e15fe2fd7e 100644
--- a/sql/item_func.h
+++ b/sql/item_func.h
@@ -326,6 +326,11 @@ class Item_func :public Item_func_or_sum,
     Item_args::propagate_equal_fields(thd, Context_identity(), cond);
     return this;
   }
+  Item* equality_propagation_for_order_items(THD *thd, const Context &ctx, COND_EQUAL *cond)
+  {
+    Item_args::equality_propagation_for_order_items(thd, Context_identity(), cond);
+    return this;
+  }
 
   bool has_rand_bit()
   {
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 8163f5b4cf0..39ca47991eb 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -13987,7 +13987,6 @@ remove_const(JOIN *join,ORDER *first_order, COND *cond,
           */
           if (optimizer_flag(join->thd, OPTIMIZER_SWITCH_ORDERBY_EQ_PROP) &&
               first_is_base_table && !first_is_in_sjm_nest &&
-              order->item[0]->real_item()->type() == Item::FIELD_ITEM &&
               join->cond_equal)
           {
             table_map first_table_bit=
@@ -14003,20 +14002,14 @@ remove_const(JOIN *join,ORDER *first_order, COND *cond,
               multiple equality the item belongs to and set item->item_equal
               accordingly.
             */
-            Item *res= item->propagate_equal_fields(join->thd,
-                                                    Value_source::
-                                                    Context_identity(),
-                                                    join->cond_equal);
-            Item_equal *item_eq;
-            if ((item_eq= res->get_item_equal()))
-            {
-              Item *first= item_eq->get_first(NO_PARTICULAR_TAB, NULL);
-              if (first->const_item() || first->used_tables() ==
-                                         first_table_bit)
-              {
-                can_subst_to_first_table= true;
-              }
-            }
+            Item *res= item->equality_propagation_for_order_items(join->thd,
+                                                                  Value_source::
+                                                                  Context_identity(),
+                                                                  join->cond_equal);
+            res->update_used_tables();
+            Item *real_item= res->real_item();
+            if (real_item->const_item() || real_item->used_tables() == first_table_bit)
+              can_subst_to_first_table= TRUE;
           }
 
           if (!can_subst_to_first_table)


More information about the commits mailing list