[Commits] Rev 4142: MDEV-5984: EITS: Incorrect filtered% value for single-table select with range access in file:///home/psergey/dev2/10.0/

Sergey Petrunya psergey at askmonty.org
Mon Mar 31 07:24:41 EEST 2014


At file:///home/psergey/dev2/10.0/

------------------------------------------------------------
revno: 4142
revision-id: psergey at askmonty.org-20140331042440-llucqhu68vcvua8d
parent: psergey at askmonty.org-20140331011658-30haw71pp9b2ceno
committer: Sergey Petrunya <psergey at askmonty.org>
branch nick: 10.0
timestamp: Mon 2014-03-31 08:24:40 +0400
message:
  MDEV-5984: EITS: Incorrect filtered% value for single-table select with range access
  - Fix records_in_column_ranges() to work correctly with range accesses over 
    multi-component keys:
    = First, take selectivity of range scans into account. Remember what columns 
      were used in the range scans.
    = Then, calculate selectivity produced by sargable predicates on columns. If 
      a column was used in a possible range access, assume its selectivity is already
      taken into account.
=== modified file 'mysql-test/r/selectivity_no_engine.result'
--- a/mysql-test/r/selectivity_no_engine.result	2014-03-27 20:32:53 +0000
+++ b/mysql-test/r/selectivity_no_engine.result	2014-03-31 04:24:40 +0000
@@ -118,6 +118,27 @@ id	select_type	table	type	possible_keys
 Note	1003	select `test`.`t1`.`col1` AS `col1` from `test`.`t1` where (`test`.`t1`.`col1` <= <cache>(-(1)))
 drop table t1, t2;
 # 
+# MDEV-5984: EITS: Incorrect filtered% value for single-table select with range access
+# 
+create table t1(a int);
+insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t2 (a int, b int, col1 varchar(64), col2 varchar(64), key(a,b));
+insert into t2 select A.a+10*B.a, C.a+10*D.a, 'filler-data1', 'filler-data2' from t1 A, t1 B, t1 C, t1 D;
+set histogram_size=100;
+set optimizer_use_condition_selectivity=4;
+set use_stat_tables='preferably';
+analyze table t2 persistent for all;
+Table	Op	Msg_type	Msg_text
+test.t2	analyze	status	Engine-independent statistics collected
+test.t2	analyze	status	Table is already up to date
+# This must show filtered=100%:
+explain extended select * from t2 where a in (1,2,3) and b in (1,2,3);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t2	range	a	a	10	NULL	9	100.00	Using index condition
+Warnings:
+Note	1003	select `test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`col1` AS `col1`,`test`.`t2`.`col2` AS `col2` from `test`.`t2` where ((`test`.`t2`.`a` in (1,2,3)) and (`test`.`t2`.`b` in (1,2,3)))
+drop table t2, t1;
+# 
 # End of the test file
 # 
 set use_stat_tables= @save_use_stat_tables;

=== modified file 'mysql-test/t/selectivity_no_engine.test'
--- a/mysql-test/t/selectivity_no_engine.test	2014-03-27 09:08:00 +0000
+++ b/mysql-test/t/selectivity_no_engine.test	2014-03-31 04:24:40 +0000
@@ -84,7 +84,23 @@ explain extended select * from t1 where
 explain extended select * from t1 where col1<=-1;
 drop table t1, t2;
 
+--echo # 
+--echo # MDEV-5984: EITS: Incorrect filtered% value for single-table select with range access
+--echo # 
+create table t1(a int);
+insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+
+create table t2 (a int, b int, col1 varchar(64), col2 varchar(64), key(a,b));
+insert into t2 select A.a+10*B.a, C.a+10*D.a, 'filler-data1', 'filler-data2' from t1 A, t1 B, t1 C, t1 D;
+
+set histogram_size=100;
+set optimizer_use_condition_selectivity=4;
+set use_stat_tables='preferably';
+analyze table t2 persistent for all;
+--echo # This must show filtered=100%:
+explain extended select * from t2 where a in (1,2,3) and b in (1,2,3);
 
+drop table t2, t1;
 --echo # 
 --echo # End of the test file
 --echo # 

=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc	2014-03-31 01:16:58 +0000
+++ b/sql/opt_range.cc	2014-03-31 04:24:40 +0000
@@ -3390,6 +3390,13 @@ double records_in_column_ranges(PARAM *p
     on the rows of 'table' in the processed query.
     The calculated selectivity is assigned to the field table->cond_selectivity.
     
+    Selectivity is calculated as a product of selectivities imposed by:
+
+    1. possible range accesses. (if multiple range accesses refer to the 
+       same column, we make adjustments for that)
+    2. Sargable conditions on fields for which we have distribution data
+    3. Sampling a few disk pages and checking the condition.
+
   NOTE
     Currently the selectivities of range conditions over different columns are
     considered independent. 
@@ -3415,14 +3422,89 @@ bool calculate_cond_selectivity_for_tabl
   if (table->pos_in_table_list->schema_table)
     DBUG_RETURN(FALSE);
   
+  MY_BITMAP handled_columns;
+  my_bitmap_map* buf;
+  if (!(buf= (my_bitmap_map*)thd->alloc(table->s->column_bitmap_size)))
+    DBUG_RETURN(TRUE);
+  my_bitmap_init(&handled_columns, buf, table->s->fields, FALSE);
+
+  /*
+    First, take into account possible range accesses. 
+    range access estimates are the most precise, we prefer them to any other
+    estimate sources.
+  */
+
+  for (keynr= 0;  keynr < table->s->keys; keynr++)
+  {
+    if (table->quick_keys.is_set(keynr))
+      set_if_bigger(max_quick_key_parts, table->quick_key_parts[keynr]);
+  }
+
+  /* 
+    Walk through all keys, keys where range access uses more keyparts go first
+  */
+  for (uint quick_key_parts= max_quick_key_parts;
+       quick_key_parts; quick_key_parts--)
+  {
+    for (keynr= 0;  keynr < table->s->keys; keynr++)
+    {
+      if (table->quick_keys.is_set(keynr) &&
+          table->quick_key_parts[keynr] == quick_key_parts)
+      {
+        uint i;
+        uint used_key_parts= table->quick_key_parts[keynr];
+        double quick_cond_selectivity= table->quick_rows[keynr] / 
+	                               table_records;
+        KEY *key_info= table->key_info + keynr;
+        KEY_PART_INFO* key_part= key_info->key_part;
+        /*
+          Suppose, there are range conditions on two keys
+            KEY1 (col1, col2)
+            KEY2 (col3, col2)
+          
+          we don't want to count selectivity of condition on col2 twice.
+          
+          First, find the longest key prefix that's made of columns whose
+          selectivity wasn't already accounted for.
+        */
+        for (i= 0; i < used_key_parts; i++, key_part++)
+        {
+          if (bitmap_is_set(&handled_columns, key_part->fieldnr-1))
+	    break; 
+          bitmap_set_bit(&handled_columns, key_part->fieldnr-1);
+        }
+        if (i)
+        {
+          /* 
+            There is at least 1-column prefix of columns whose selectivity has
+            not yet been accounted for.
+          */
+          table->cond_selectivity*= quick_cond_selectivity;
+          if (i != used_key_parts)
+	  {
+            /*
+              Range access got us estimate for #used_key_parts.
+              We need estimate for #(i-1) key parts.
+            */
+            double f1= key_info->actual_rec_per_key(i-1);
+            double f2= key_info->actual_rec_per_key(i);
+            table->cond_selectivity*= f1 / f2;
+          }
+        }
+      }
+    }
+  }
+   
+  /* 
+    Second step: calculate the selectivity of the range conditions not 
+    supported by any index
+  */
+  bitmap_subtract(used_fields, &handled_columns);
+  /* no need to do: my_bitmap_free(&handled_columns); */
+
   if (thd->variables.optimizer_use_condition_selectivity > 2 &&
       !bitmap_is_clear_all(used_fields))
   {
-    /* 
-      Calculate the selectivity of the range conditions not supported
-      by any index
-    */
-
     PARAM param;
     MEM_ROOT alloc;
     SEL_TREE *tree;
@@ -3509,66 +3591,6 @@ bool calculate_cond_selectivity_for_tabl
 
   bitmap_clear_all(used_fields);
 
-  for (keynr= 0;  keynr < table->s->keys; keynr++)
-  {
-    if (table->quick_keys.is_set(keynr))
-      set_if_bigger(max_quick_key_parts, table->quick_key_parts[keynr]);
-  }
-
-  /* 
-    Walk through all keys, keys where range access uses more keyparts go first
-  */
-  for (uint quick_key_parts= max_quick_key_parts;
-       quick_key_parts; quick_key_parts--)
-  {
-    for (keynr= 0;  keynr < table->s->keys; keynr++)
-    {
-      if (table->quick_keys.is_set(keynr) &&
-          table->quick_key_parts[keynr] == quick_key_parts)
-      {
-        uint i;
-        uint used_key_parts= table->quick_key_parts[keynr];
-        double quick_cond_selectivity= table->quick_rows[keynr] / 
-	                               table_records;
-        KEY *key_info= table->key_info + keynr;
-        KEY_PART_INFO* key_part= key_info->key_part;
-        /*
-          Suppose, there are range conditions on two keys
-            KEY1 (col1, col2)
-            KEY2 (col3, col2)
-          
-          we don't want to count selectivity of condition on col2 twice.
-          
-          First, find the longest key prefix that's made of columns whose
-          selectivity wasn't already accounted for.
-        */
-        for (i= 0; i < used_key_parts; i++, key_part++)
-        {
-          if (bitmap_is_set(used_fields, key_part->fieldnr-1))
-	    break; 
-          bitmap_set_bit(used_fields, key_part->fieldnr-1);
-        }
-        if (i)
-        {
-          /* 
-            There is at least 1-column prefix of columns whose selectivity is
-            not yet accounted for
-          */
-          table->cond_selectivity*= quick_cond_selectivity;
-          if (i != used_key_parts)
-	  {
-            /*
-              Range access got us estimate for #used_key_parts.
-              We need estimate for #(i-1) key parts.
-            */
-            double f1= key_info->actual_rec_per_key(i-1);
-            double f2= key_info->actual_rec_per_key(i);
-            table->cond_selectivity*= f1 / f2;
-          }
-        }
-      } 
-    }
-  }
 
   /* Check if we can improve selectivity estimates by using sampling */
   ulong check_rows=



More information about the commits mailing list