[Commits] 8f428279c31: MDEV-15777:Support Early NULLs filtering-like restrictions in the range optimizer

Varun varunraiko1803 at gmail.com
Wed Apr 18 16:56:47 EEST 2018


revision-id: 8f428279c31d9a36e6a2089d70dd7600f769ec57 (mariadb-10.3.0-765-g8f428279c31)
parent(s): 91245909a2f0c89444ecb5af587284f53b7196ee
author: Varun Gupta
committer: Varun Gupta
timestamp: 2018-04-18 19:26:12 +0530
message:

MDEV-15777:Support Early NULLs filtering-like restrictions in the range optimizer

Initial patch

---
 sql/mdev15864.sql | 29 ++++++++++++++++++
 sql/opt_range.cc  | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 sql/opt_range.h   |  3 ++
 sql/sql_select.cc | 13 ++++++--
 sql/sql_select.h  |  1 +
 5 files changed, 133 insertions(+), 3 deletions(-)

diff --git a/sql/mdev15864.sql b/sql/mdev15864.sql
new file mode 100644
index 00000000000..a7c4037950d
--- /dev/null
+++ b/sql/mdev15864.sql
@@ -0,0 +1,29 @@
+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 one_m(a int);
+insert into one_m select A.a + B.a* 1000  from one_k A, one_k B;
+delete from one_m where a=0 limit 1;
+
+create table t1 (
+  id int(10) unsigned NOT NULL AUTO_INCREMENT,
+  filler varchar(100),
+  subset_id int(11) DEFAULT NULL,
+  PRIMARY KEY (id),
+  KEY t1_subset_id (subset_id)
+);
+
+create table t1_subsets (
+  id int(10) unsigned NOT NULL AUTO_INCREMENT,
+  filler1 varchar(100),
+  filler2 varchar(100),
+  filler3 varchar(100),
+  PRIMARY KEY (id)
+);
+
+insert into t1 select a,a, NULL from one_m where a < 50*1000;
+insert into t1_subsets select a,a,a,a from one_m where a < 500*1000 limit 499000;
+analyze format=json select * from t1,t1_subsets where t1.subset_id IS NOT NULL and t1.subset_id= t1_subsets.id;
\ No newline at end of file
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index 38dbed92a22..a6d8dc8ea3f 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -1184,6 +1184,7 @@ SQL_SELECT *make_select(TABLE *head, table_map const_tables,
   select->const_tables=const_tables;
   select->head=head;
   select->cond= conds;
+  select->null_rejecting_conds= NULL;
 
   if (filesort && my_b_inited(&filesort->io_cache))
   {
@@ -2430,7 +2431,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
   {
     uchar buff[STACK_BUFF_ALLOC];
     MEM_ROOT alloc;
-    SEL_TREE *tree= NULL;
+    SEL_TREE *tree= NULL, *not_null_cond_tree= NULL;
     KEY_PART *key_parts;
     KEY *key_info;
     PARAM param;
@@ -2539,6 +2540,12 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
     TRP_GROUP_MIN_MAX *group_trp;
     double best_read_time= read_time;
 
+    if (null_rejecting_conds)
+    {
+      not_null_cond_tree= null_rejecting_conds->get_mm_tree(&param, 
+                                          &null_rejecting_conds);
+    }
+
     if (cond)
     {
       if ((tree= cond->get_mm_tree(&param, &cond)))
@@ -2557,6 +2564,13 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
           tree= NULL;
       }
     }
+    if (not_null_cond_tree)
+    {
+      if (!tree)
+        tree= not_null_cond_tree;
+      else
+        tree= tree_and(&param, tree, not_null_cond_tree);
+    }
 
     /*
       Try to construct a QUICK_GROUP_MIN_MAX_SELECT.
@@ -14647,6 +14661,80 @@ void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
   add_key_and_length(key_names, used_lengths, &first);
 }
 
+inline void add_cond(THD *thd, Item **e1, Item *e2)
+{
+  if (*e1)
+  {
+    if (!e2)
+      return;
+    Item *res;
+    if ((res= new (thd->mem_root) Item_cond_and(thd, *e1, e2)))
+    {
+      res->fix_fields(thd, 0);
+      res->update_used_tables();
+      *e1= res;
+    }
+  }
+  else
+    *e1= e2;
+}
+
+
+COND* make_null_rejecting_conds(THD *thd, TABLE *table,
+                        DYNAMIC_ARRAY *keyuse_array, key_map *const_keys)
+{
+  KEY *keyinfo, *keyinfo_keyuse;
+  KEY_PART_INFO *key_part;
+  COND *cond= NULL;
+  for (uint key=0; key< table->s->keys; key++)
+  {
+    keyinfo= table->key_info+key;
+    key_part= keyinfo->key_part;
+    /*
+      Only user degined key parts are required here because the extended
+      key parts we know would be from the primary key and all the key_parts
+      of the primary key are NOT NULL so no need to add such conditions
+    */
+    for (uint i=0; i < keyinfo->user_defined_key_parts; i++,key_part++)
+    {
+      for(uint j=0; j < keyuse_array->elements; j++)
+      {
+        KEYUSE* keyuse= (KEYUSE*)dynamic_array_ptr(keyuse_array, j);
+        if (keyuse->table == table && keyuse->key == key)
+        {
+          //generate equality
+          Field *field= key_part->field;
+          keyinfo_keyuse= keyuse->table->key_info+keyuse->key;
+          if (keyuse->val->const_item() 
+              || keyuse->func_type == Item_func::EQUAL_FUNC
+              || keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL
+              )
+            continue;
+          if (!field->eq(keyinfo_keyuse->key_part[keyuse->keypart].field))
+            continue;
+          /*
+            Add checks here to ensure that only fields that can be NOT NULL are added
+            that is dont include
+              1) keyparts defined as NOT NULL
+              2) keyparts belong to Primary Key (these will be handled in case 1)
+              3) equalities with <=> should not add NOT NULL for its fields[needs discussion]
+          */
+          if (field->flags & NOT_NULL_FLAG)
+            continue;
+          Item_field *field_item= new (thd->mem_root)Item_field(thd, key_part->field);
+          Item* not_null_item= new (thd->mem_root)Item_func_isnotnull(thd, field_item);
+          // adding the key to const keys as we have the condition as key.keypart IS NOT NULL
+          const_keys->set_bit(keyuse->key);
+          not_null_item->fix_fields(thd, 0);
+          not_null_item->update_used_tables();
+          add_cond(thd,&cond, not_null_item);
+        }
+      }
+    }
+  }
+  return cond;
+}
+
 
 #ifndef DBUG_OFF
 
diff --git a/sql/opt_range.h b/sql/opt_range.h
index bd85a12d4a1..54f113c710d 100644
--- a/sql/opt_range.h
+++ b/sql/opt_range.h
@@ -1636,6 +1636,7 @@ class SQL_SELECT :public Sql_alloc {
   /* See PARAM::possible_keys */
   key_map possible_keys;
   bool	free_cond; /* Currently not used and always FALSE */
+  COND *null_rejecting_conds;
 
   SQL_SELECT();
   ~SQL_SELECT();
@@ -1728,6 +1729,8 @@ bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item **cond);
 bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond);
 #endif
 void store_key_image_to_rec(Field *field, uchar *ptr, uint len);
+COND* make_null_rejecting_conds(THD *thd, TABLE *table,
+                          DYNAMIC_ARRAY *keyuse_array, key_map *const_keys);
 
 extern String null_string;
 
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 796ea569e64..7abad3ffed9 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -4242,6 +4242,7 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
   SARGABLE_PARAM *sargables= 0;
   List_iterator<TABLE_LIST> ti(tables_list);
   TABLE_LIST *tables;
+  COND* null_rejecting_conds= NULL;
   DBUG_ENTER("make_join_statistics");
 
   table_count=join->table_count;
@@ -4783,6 +4784,9 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
     add_group_and_distinct_keys(join, s);
 
     s->table->cond_selectivity= 1.0;
+
+//    null_rejecting_conds= make_null_rejecting_conds(join->thd, s->table,
+//                                           keyuse_array, &s->const_keys);
     
     /*
       Perform range analysis if there are keys it could use (1). 
@@ -4812,6 +4816,8 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
 			    1, &error);
         if (!select)
           goto error;
+
+//        select->null_rejecting_conds= null_rejecting_conds;
         records= get_quick_record_count(join->thd, select, s->table,
 				        &s->const_keys, join->row_limit);
         /* Range analyzer could modify the condition. */
@@ -4824,6 +4830,7 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
         s->needed_reg=select->needed_reg;
         select->quick=0;
         impossible_range= records == 0 && s->table->reginfo.impossible_range;
+        select->null_rejecting_conds= NULL;
       }
       if (!impossible_range)
       {
@@ -4832,7 +4839,7 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
                                                *s->on_expr_ref ?
                                                s->on_expr_ref : &join->conds);
         if (s->table->reginfo.impossible_range)
-	{
+	      {
           impossible_range= TRUE;
           records= 0;
         }
@@ -4867,7 +4874,8 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
     }
 
   }
-
+  if (null_rejecting_conds)
+    delete null_rejecting_conds;
   if (pull_out_semijoin_tables(join))
     DBUG_RETURN(TRUE);
 
@@ -5796,6 +5804,7 @@ add_keyuse(DYNAMIC_ARRAY *keyuse_array, KEY_FIELD *key_field,
   keyuse.cond_guard= key_field->cond_guard;
   keyuse.sj_pred_no= key_field->sj_pred_no;
   keyuse.validity_ref= 0;
+  keyuse.func_type= key_field->cond->functype();
   return (insert_dynamic(keyuse_array,(uchar*) &keyuse));
 }
 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index f8911fbba01..7d2977e187f 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -78,6 +78,7 @@ typedef struct keyuse_t {
     Otherwise it points to the enabling flag for this keyuse (true <=> enabled)
   */
   bool *validity_ref;
+  Item_func::Functype func_type;
 
   bool is_for_hash_join() { return is_hash_join_key_no(key); }
 } KEYUSE;


More information about the commits mailing list