bk commit into 5.0 tree (igor:1.1894) BUG#10561

[igor]

Below is the list of changes that have just been committed into a local
5.0 repository of igor. When igor does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html

ChangeSet
  1.1894 05/05/21 06:11:44 igor@stripped +4 -0
  range.result, range.test:
    Added test cases for optimization request #10561.
  opt_range.cc, sql_select.cc:
    Fixed bug #10561: an optimization request to allow
    range analysis for NOT IN and NOT BETWEEN.

  mysql-test/r/range.result
    1.35 05/05/21 06:08:03 igor@stripped +76 -0
    Added test cases for optimization request #10561.

  mysql-test/t/range.test
    1.28 05/05/21 06:07:37 igor@stripped +40 -0
    Added test cases for optimization request #10561.

  sql/opt_range.cc
    1.160 05/05/21 06:06:56 igor@stripped +111 -35
    Fixed bug #10561: an optimization request to allow
    range analysis for NOT IN and NOT BETWEEN.

  sql/sql_select.cc
    1.322 05/05/21 06:06:14 igor@stripped +11 -0
    Fixed bug #10561: an optimization request to allow
    range analysis for NOT IN and NOT BETWEEN.

# This is a BitKeeper patch.  What follows are the unified diffs for the
# set of deltas contained in the patch.  The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User:	igor
# Host:	rurik.mysql.com
# Root:	/home/igor/dev/mysql-5.0-0

--- 1.159/sql/opt_range.cc	Thu May 19 14:52:16 2005
+++ 1.160/sql/opt_range.cc	Sat May 21 06:06:56 2005
@@ -3307,6 +3307,38 @@
 
 
 /*
+  Build a SEL_TREE for <> predicate
+ 
+  SYNOPSIS
+    get_ne_mm_tree()
+      param       PARAM from SQL_SELECT::test_quick_select
+      cond_func   item for the predicate
+      field       field in the predicate
+      value       constant in the predicate
+      cmp_type    compare type for the field
+
+  RETURN 
+    Pointer to tree built tree
+*/
+
+static SEL_TREE *get_ne_mm_tree(PARAM *param, Item_func *cond_func, 
+                                Field *field, Item *value,
+                                Item_result cmp_type)
+{
+  SEL_TREE *tree= 0;
+  tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
+		       value, cmp_type);
+  if (tree)
+  {
+    tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
+					    Item_func::GT_FUNC,
+					    value, cmp_type));
+  }
+  return tree;
+}
+   
+
+/*
   Build a SEL_TREE for a simple predicate
  
   SYNOPSIS
@@ -3316,55 +3348,85 @@
       field       field in the predicate
       value       constant in the predicate
       cmp_type    compare type for the field
+      inv         TRUE <> NOT cond_func is considered
 
   RETURN 
-    Pointer to thre built tree
+    Pointer to tree built tree
 */
 
 static SEL_TREE *get_func_mm_tree(PARAM *param, Item_func *cond_func, 
                                   Field *field, Item *value,
-                                  Item_result cmp_type)
+                                  Item_result cmp_type, bool inv)
 {
   SEL_TREE *tree= 0;
   DBUG_ENTER("get_func_mm_tree");
 
   switch (cond_func->functype()) {
+
   case Item_func::NE_FUNC:
-    tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
-		       value, cmp_type);
-    if (tree)
-    {
-      tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
-					      Item_func::GT_FUNC,
-					      value, cmp_type));
-    }
+    tree= get_ne_mm_tree(param, cond_func, field, value, cmp_type);
     break;
+
   case Item_func::BETWEEN:
-    tree= get_mm_parts(param, cond_func, field, Item_func::GE_FUNC,
-		       cond_func->arguments()[1],cmp_type);
-    if (tree)
-    {
-      tree= tree_and(param, tree, get_mm_parts(param, cond_func, field,
-					       Item_func::LE_FUNC,
-					       cond_func->arguments()[2],
-                                               cmp_type));
+    if (inv)
+    {
+      tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
+		         cond_func->arguments()[1],cmp_type);
+      if (tree)
+      {
+        tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
+					        Item_func::GT_FUNC,
+					        cond_func->arguments()[2],
+                                                cmp_type));
+      }
+    }
+    else
+    {
+      tree= get_mm_parts(param, cond_func, field, Item_func::GE_FUNC,
+		         cond_func->arguments()[1],cmp_type);
+      if (tree)
+      {
+        tree= tree_and(param, tree, get_mm_parts(param, cond_func, field,
+					         Item_func::LE_FUNC,
+					         cond_func->arguments()[2],
+                                                 cmp_type));
+      }
     }
     break;
+
   case Item_func::IN_FUNC:
   {
     Item_func_in *func=(Item_func_in*) cond_func;
-    tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
-                       func->arguments()[1], cmp_type);
-    if (tree)
-    {
-      Item **arg, **end;
-      for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
-           arg < end ; arg++)
-      {
-        tree=  tree_or(param, tree, get_mm_parts(param, cond_func, field, 
-                                                 Item_func::EQ_FUNC,
-                                                 *arg,
-                                                 cmp_type));
+
+    if (inv)
+    {
+      tree= get_ne_mm_tree(param, cond_func, field,
+                           func->arguments()[1], cmp_type);
+      if (tree)
+      {
+        Item **arg, **end;
+        for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
+             arg < end ; arg++)
+        {
+          tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 
+                                                      *arg, cmp_type));
+        }
+      }
+    }
+    else
+    {    
+      tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
+                         func->arguments()[1], cmp_type);
+      if (tree)
+      {
+        Item **arg, **end;
+        for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
+             arg < end ; arg++)
+        {
+          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field, 
+                                                  Item_func::EQ_FUNC,
+                                                  *arg, cmp_type));
+        }
       }
     }
     break;
@@ -3396,6 +3458,7 @@
   SEL_TREE *tree=0;
   SEL_TREE *ftree= 0;
   Item_field *field_item= 0;
+  bool inv= FALSE;
   Item *value;
   DBUG_ENTER("get_mm_tree");
 
@@ -3457,15 +3520,28 @@
   }
 
   Item_func *cond_func= (Item_func*) cond;
-  if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
-    DBUG_RETURN(0);				// Can't be calculated
+  if (cond_func->functype() == Item_func::NOT_FUNC)
+  {
+    Item *arg= cond_func->arguments()[0];
+    if (arg->type() == Item::FUNC_ITEM)
+    {
+      cond_func= (Item_func*) arg;
+      if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
+        DBUG_RETURN(0);
+      inv= TRUE;	
+    }
+    else
+      DBUG_RETURN(0);
+  }    
+  else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
+      DBUG_RETURN(0);			       
 
   param->cond= cond;
 
   switch (cond_func->functype()) {
   case Item_func::BETWEEN:
     if (cond_func->arguments()[0]->type() != Item::FIELD_ITEM)
-      DBUG_RETURN(0);
+        DBUG_RETURN(0);
     field_item= (Item_field*) (cond_func->arguments()[0]);
     value= NULL;
     break;
@@ -3536,7 +3612,7 @@
   Field *field= field_item->field;
   Item_result cmp_type= field->cmp_type();
   if (!((ref_tables | field->table->map) & param_comp))
-    ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type);
+    ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
   Item_equal *item_equal= field_item->item_equal;
   if (item_equal)
   {
@@ -3549,7 +3625,7 @@
         continue;
       if (!((ref_tables | f->table->map) & param_comp))
       {
-        tree= get_func_mm_tree(param, cond_func, f, value, cmp_type);
+        tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv);
         ftree= !ftree ? tree : tree_and(param, ftree, tree);
       }
     }

--- 1.321/sql/sql_select.cc	Fri May 20 06:16:21 2005
+++ 1.322/sql/sql_select.cc	Sat May 21 06:06:14 2005
@@ -2822,6 +2822,17 @@
   if (cond->type() != Item::FUNC_ITEM)
     return;
   Item_func *cond_func= (Item_func*) cond;
+  if (cond_func->functype() == Item_func::NOT_FUNC)
+  {
+    Item *item= cond_func->arguments()[0];
+    if (item->type() == Item::FUNC_ITEM &&
+        ((Item_func *) item)->select_optimize() == Item_func::OPTIMIZE_KEY)
+    {
+      add_key_fields(key_fields,and_level,item,usable_tables);
+      return;
+    }
+    return;
+  }
   switch (cond_func->select_optimize()) {
   case Item_func::OPTIMIZE_NONE:
     break;

--- 1.34/mysql-test/r/range.result	Fri May 13 02:08:03 2005
+++ 1.35/mysql-test/r/range.result	Sat May 21 06:08:03 2005
@@ -584,3 +584,79 @@
 count(*)
 4
 drop table t1;
+CREATE TABLE t1 (
+id int(11) NOT NULL auto_increment,
+status varchar(20),
+PRIMARY KEY  (id),
+KEY (status)
+);
+INSERT INTO t1 VALUES
+(1,'B'), (2,'B'), (3,'B'), (4,'B'), (5,'B'), (6,'B'),
+(7,'B'), (8,'B'), (9,'B'), (10,'B'), (11,'B'), (12,'B'),
+(13,'B'), (14,'B'), (15,'B'), (16,'B'), (17,'B'), (18,'B'),
+(19,'B'), (20,'B'), (21,'B'), (22,'B'), (23,'B'), (24,'B'), 
+(25,'A'), (26,'A'), (27,'A'), (28,'A'), (29,'A'), (30,'A'),
+(31,'A'), (32,'A'), (33,'A'), (34,'A'), (35,'A'), (36,'A'),
+(37,'A'), (38,'A'), (39,'A'), (40,'A'), (41,'A'), (42,'A'),
+(43,'A'), (44,'A'), (45,'A'), (46,'A'), (47,'A'), (48,'A'),
+(49,'A'), (50,'A'), (51,'A'), (52,'A'), (53,'C'), (54,'C'),
+(55,'C'), (56,'C'), (57,'C'), (58,'C'), (59,'C'), (60,'C');
+EXPLAIN SELECT * FROM t1 WHERE status <> 'A' AND status <> 'B';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	status	status	23	NULL	11	Using where
+EXPLAIN SELECT * FROM t1 WHERE status NOT IN ('A','B');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	status	status	23	NULL	11	Using where
+SELECT * FROM t1 WHERE status <> 'A' AND status <> 'B';
+id	status
+53	C
+54	C
+55	C
+56	C
+57	C
+58	C
+59	C
+60	C
+SELECT * FROM t1 WHERE status NOT IN ('A','B');
+id	status
+53	C
+54	C
+55	C
+56	C
+57	C
+58	C
+59	C
+60	C
+EXPLAIN SELECT status FROM t1 WHERE status <> 'A' AND status <> 'B';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	status	status	23	NULL	11	Using where; Using index
+EXPLAIN SELECT status FROM t1 WHERE status NOT IN ('A','B');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	status	status	23	NULL	11	Using where; Using index
+EXPLAIN SELECT * FROM t1 WHERE status NOT BETWEEN 'A' AND 'B';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	status	status	23	NULL	10	Using where
+EXPLAIN SELECT * FROM t1 WHERE status < 'A' OR status > 'B';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	status	status	23	NULL	10	Using where
+SELECT * FROM t1 WHERE status NOT BETWEEN 'A' AND 'B';
+id	status
+53	C
+54	C
+55	C
+56	C
+57	C
+58	C
+59	C
+60	C
+SELECT * FROM t1 WHERE status < 'A' OR status > 'B';
+id	status
+53	C
+54	C
+55	C
+56	C
+57	C
+58	C
+59	C
+60	C
+DROP TABLE t1;

--- 1.27/mysql-test/t/range.test	Wed May 18 11:06:31 2005
+++ 1.28/mysql-test/t/range.test	Sat May 21 06:07:37 2005
@@ -455,3 +455,43 @@
 SELECT count(*) FROM t1 WHERE CLIENT='000' AND (ARG1 != ' 2' OR ARG1 != ' 1');
 drop table t1;
 
+#
+# Test for optimization request #10561: to use keys for
+# NOT IN (c1,...,cn) and NOT BETWEEN c1 AND c2
+#
+
+CREATE TABLE t1 (
+  id int(11) NOT NULL auto_increment,
+  status varchar(20),
+  PRIMARY KEY  (id),
+  KEY (status)
+);
+
+INSERT INTO t1 VALUES
+(1,'B'), (2,'B'), (3,'B'), (4,'B'), (5,'B'), (6,'B'),
+(7,'B'), (8,'B'), (9,'B'), (10,'B'), (11,'B'), (12,'B'),
+(13,'B'), (14,'B'), (15,'B'), (16,'B'), (17,'B'), (18,'B'),
+(19,'B'), (20,'B'), (21,'B'), (22,'B'), (23,'B'), (24,'B'), 
+(25,'A'), (26,'A'), (27,'A'), (28,'A'), (29,'A'), (30,'A'),
+(31,'A'), (32,'A'), (33,'A'), (34,'A'), (35,'A'), (36,'A'),
+(37,'A'), (38,'A'), (39,'A'), (40,'A'), (41,'A'), (42,'A'),
+(43,'A'), (44,'A'), (45,'A'), (46,'A'), (47,'A'), (48,'A'),
+(49,'A'), (50,'A'), (51,'A'), (52,'A'), (53,'C'), (54,'C'),
+(55,'C'), (56,'C'), (57,'C'), (58,'C'), (59,'C'), (60,'C');
+
+EXPLAIN SELECT * FROM t1 WHERE status <> 'A' AND status <> 'B';
+EXPLAIN SELECT * FROM t1 WHERE status NOT IN ('A','B');
+
+SELECT * FROM t1 WHERE status <> 'A' AND status <> 'B';
+SELECT * FROM t1 WHERE status NOT IN ('A','B');
+
+EXPLAIN SELECT status FROM t1 WHERE status <> 'A' AND status <> 'B';
+EXPLAIN SELECT status FROM t1 WHERE status NOT IN ('A','B');
+
+EXPLAIN SELECT * FROM t1 WHERE status NOT BETWEEN 'A' AND 'B';
+EXPLAIN SELECT * FROM t1 WHERE status < 'A' OR status > 'B';
+
+SELECT * FROM t1 WHERE status NOT BETWEEN 'A' AND 'B';
+SELECT * FROM t1 WHERE status < 'A' OR status > 'B';
+
+DROP TABLE t1;