MySQL Lists are EOL. Please join:

List:Commits« Previous MessageNext Message »
From:marc.alff Date:August 22 2007 5:05pm
Subject:bk commit into 5.0 tree (malff:1.2491) BUG#30237
View as plain text  
Below is the list of changes that have just been committed into a local
5.0 repository of marcsql. When marcsql 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@stripped, 2007-08-22 11:05:35-06:00, malff@weblab.(none) +4 -0
  Bug#30237 (Performance regression in boolean expressions)
  
  This is a performance bug, related to the parsing or 'OR' and 'AND' boolean
  expressions.
  
  Let N be the number of expressions involved in a OR (respectively AND).
  
  When N=1
  
  For example, "select 1" involve only 1 term: there is no OR operator.
  
  In 4.0 and 4.1, parsing expressions not involving OR had no overhead.
  In 5.0, parsing adds some overhead, with Select->expr_list.
  
  With this patch, the overhead introduced in 5.0 has been removed,
  so that performances for N=1 should be identical to the 4.0 performances,
  which are optimal (there is no code executed at all)
  
  The overhead in 5.0 was in fact affecting significantly some operations.
  For example, loading 1 Million rows into a table with INSERTs,
  for a table that has 100 columns, leads to parsing 100 Millions of
  expressions, which means that the overhead related to Select->expr_list
  is executed 100 Million times ...
  
  Considering that N=1 is by far the most probable expression,
  this case should be optimal.
  
  When N=2
  
  For example, "select a OR b" involves 2 terms in the OR operator.
  
  In 4.0 and 4.1, parsing expressions involving 2 terms created 1 Item_cond_or
  node, which is the expected result.
  In 5.0, parsing these expression also produced 1 node, but with some extra
  overhead related to Select->expr_list : creating 1 list in Select->expr_list
  and another in Item_cond::list is inefficient.
  
  With this patch, the overhead introduced in 5.0 has been removed
  so that performances for N=2 should be identical to the 4.0 performances.
  Note that the memory allocation uses the new (thd->mem_root) syntax
  directly.
  The cost of "is_cond_or" is estimated to be neglectable: the real problem
  of the performance degradation comes from unneeded memory allocations.
  
  When N>=3
  
  For example, "select a OR b OR c ...", which involves 3 or more terms.
  
  In 4.0 and 4.1, the parser had no significant cost overhead, but produced
  an Item tree which is difficult to evaluate / optimize during runtime.
  In 5.0, the parser produces a better Item tree, using the Item_cond
  constructor that accepts a list of children directly, but at an extra cost
  related to Select->expr_list.
  
  With this patch, the code is implemented to take the best of the two
  implementations:
  - there is no overhead with Select->expr_list
  - the Item tree generated is optimized and flattened.
  
  This is achieved by adding children nodes into the Item tree directly,
  with Item_cond::add(), which avoids the need for temporary lists and memory
  allocation
  
  Note that this patch also provide an extra optimization, that the previous
  code in 5.0 did not provide: expressions are flattened in the Item tree,
  based on what the expression already parsed is, and not based on the order
  in which rules are reduced.
  
  For example : "(a OR b) OR c", "a OR (b OR c)" would both be represented
  with 2 Item_cond_or nodes before this patch, and with 1 node only with this
  patch. The logic used is based on the mathematical properties of the OR
  operator (it's associative), and produces a simpler tree.

  mysql-test/r/parser_precedence.result@stripped, 2007-08-22 11:05:33-06:00, malff@weblab.(none) +356 -0
    Added test cases to cover boolean operator precedence
    

  mysql-test/r/parser_precedence.result@stripped, 2007-08-22 11:05:33-06:00, malff@weblab.(none) +0 -0

  mysql-test/t/parser_precedence.test@stripped, 2007-08-22 11:05:33-06:00, malff@weblab.(none) +93 -0
    Added test cases to cover boolean operator precedence
    

  mysql-test/t/parser_precedence.test@stripped, 2007-08-22 11:05:33-06:00, malff@weblab.(none) +0 -0

  sql/item_cmpfunc.h@stripped, 2007-08-22 11:05:33-06:00, malff@weblab.(none) +18 -0
    Improved performances for parsing boolean expressions

  sql/sql_yacc.yy@stripped, 2007-08-22 11:05:33-06:00, malff@weblab.(none) +97 -43
    Improved performances for parsing boolean expressions

diff -Nrup a/mysql-test/r/parser_precedence.result b/mysql-test/r/parser_precedence.result
--- /dev/null	Wed Dec 31 16:00:00 196900
+++ b/mysql-test/r/parser_precedence.result	2007-08-22 11:05:33 -06:00
@@ -0,0 +1,356 @@
+drop table if exists t1_30237_bool;
+create table t1_30237_bool(A boolean, B boolean, C boolean);
+insert into t1_30237_bool values
+(FALSE, FALSE, FALSE),
+(FALSE, FALSE, NULL),
+(FALSE, FALSE, TRUE),
+(FALSE, NULL, FALSE),
+(FALSE, NULL, NULL),
+(FALSE, NULL, TRUE),
+(FALSE, TRUE, FALSE),
+(FALSE, TRUE, NULL),
+(FALSE, TRUE, TRUE),
+(NULL, FALSE, FALSE),
+(NULL, FALSE, NULL),
+(NULL, FALSE, TRUE),
+(NULL, NULL, FALSE),
+(NULL, NULL, NULL),
+(NULL, NULL, TRUE),
+(NULL, TRUE, FALSE),
+(NULL, TRUE, NULL),
+(NULL, TRUE, TRUE),
+(TRUE, FALSE, FALSE),
+(TRUE, FALSE, NULL),
+(TRUE, FALSE, TRUE),
+(TRUE, NULL, FALSE),
+(TRUE, NULL, NULL),
+(TRUE, NULL, TRUE),
+(TRUE, TRUE, FALSE),
+(TRUE, TRUE, NULL),
+(TRUE, TRUE, TRUE) ;
+Testing OR, XOR, AND
+select A, B, A OR B, A XOR B, A AND B
+from t1_30237_bool where C is null order by A, B;
+A	B	A OR B	A XOR B	A AND B
+NULL	NULL	NULL	NULL	NULL
+NULL	0	NULL	NULL	0
+NULL	1	1	NULL	NULL
+0	NULL	NULL	NULL	0
+0	0	0	0	0
+0	1	1	1	0
+1	NULL	1	NULL	NULL
+1	0	1	1	0
+1	1	1	0	1
+Testing that OR is associative 
+select A, B, C, (A OR B) OR C, A OR (B OR C), A OR B OR C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A OR B) OR C	A OR (B OR C)	A OR B OR C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	NULL	NULL	NULL
+NULL	NULL	1	1	1	1
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	NULL	NULL	NULL
+NULL	0	1	1	1	1
+NULL	1	NULL	1	1	1
+NULL	1	0	1	1	1
+NULL	1	1	1	1	1
+0	NULL	NULL	NULL	NULL	NULL
+0	NULL	0	NULL	NULL	NULL
+0	NULL	1	1	1	1
+0	0	NULL	NULL	NULL	NULL
+0	0	0	0	0	0
+0	0	1	1	1	1
+0	1	NULL	1	1	1
+0	1	0	1	1	1
+0	1	1	1	1	1
+1	NULL	NULL	1	1	1
+1	NULL	0	1	1	1
+1	NULL	1	1	1	1
+1	0	NULL	1	1	1
+1	0	0	1	1	1
+1	0	1	1	1	1
+1	1	NULL	1	1	1
+1	1	0	1	1	1
+1	1	1	1	1	1
+select count(*) from t1_30237_bool
+where ((A OR B) OR C) != (A OR (B OR C));
+count(*)
+0
+Testing that XOR is associative 
+select A, B, C, (A XOR B) XOR C, A XOR (B XOR C), A XOR B XOR C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A XOR B) XOR C	A XOR (B XOR C)	A XOR B XOR C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	NULL	NULL	NULL
+NULL	NULL	1	NULL	NULL	NULL
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	NULL	NULL	NULL
+NULL	0	1	NULL	NULL	NULL
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	NULL	NULL	NULL
+NULL	1	1	NULL	NULL	NULL
+0	NULL	NULL	NULL	NULL	NULL
+0	NULL	0	NULL	NULL	NULL
+0	NULL	1	NULL	NULL	NULL
+0	0	NULL	NULL	NULL	NULL
+0	0	0	0	0	0
+0	0	1	1	1	1
+0	1	NULL	NULL	NULL	NULL
+0	1	0	1	1	1
+0	1	1	0	0	0
+1	NULL	NULL	NULL	NULL	NULL
+1	NULL	0	NULL	NULL	NULL
+1	NULL	1	NULL	NULL	NULL
+1	0	NULL	NULL	NULL	NULL
+1	0	0	1	1	1
+1	0	1	0	0	0
+1	1	NULL	NULL	NULL	NULL
+1	1	0	0	0	0
+1	1	1	1	1	1
+select count(*) from t1_30237_bool
+where ((A XOR B) XOR C) != (A XOR (B XOR C));
+count(*)
+0
+Testing that AND is associative 
+select A, B, C, (A AND B) AND C, A AND (B AND C), A AND B AND C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A AND B) AND C	A AND (B AND C)	A AND B AND C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	0	0	0
+NULL	NULL	1	NULL	NULL	NULL
+NULL	0	NULL	0	0	0
+NULL	0	0	0	0	0
+NULL	0	1	0	0	0
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	0	0	0
+NULL	1	1	NULL	NULL	NULL
+0	NULL	NULL	0	0	0
+0	NULL	0	0	0	0
+0	NULL	1	0	0	0
+0	0	NULL	0	0	0
+0	0	0	0	0	0
+0	0	1	0	0	0
+0	1	NULL	0	0	0
+0	1	0	0	0	0
+0	1	1	0	0	0
+1	NULL	NULL	NULL	NULL	NULL
+1	NULL	0	0	0	0
+1	NULL	1	NULL	NULL	NULL
+1	0	NULL	0	0	0
+1	0	0	0	0	0
+1	0	1	0	0	0
+1	1	NULL	NULL	NULL	NULL
+1	1	0	0	0	0
+1	1	1	1	1	1
+select count(*) from t1_30237_bool
+where ((A AND B) AND C) != (A AND (B AND C));
+count(*)
+0
+Testing that AND has precedence over OR
+select A, B, C, (A OR B) AND C, A OR (B AND C), A OR B AND C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A OR B) AND C	A OR (B AND C)	A OR B AND C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	0	NULL	NULL
+NULL	NULL	1	NULL	NULL	NULL
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	0	NULL	NULL
+NULL	0	1	NULL	NULL	NULL
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	0	NULL	NULL
+NULL	1	1	1	1	1
+0	NULL	NULL	NULL	NULL	NULL
+0	NULL	0	0	0	0
+0	NULL	1	NULL	NULL	NULL
+0	0	NULL	0	0	0
+0	0	0	0	0	0
+0	0	1	0	0	0
+0	1	NULL	NULL	NULL	NULL
+0	1	0	0	0	0
+0	1	1	1	1	1
+1	NULL	NULL	NULL	1	1
+1	NULL	0	0	1	1
+1	NULL	1	1	1	1
+1	0	NULL	NULL	1	1
+1	0	0	0	1	1
+1	0	1	1	1	1
+1	1	NULL	NULL	1	1
+1	1	0	0	1	1
+1	1	1	1	1	1
+select count(*) from t1_30237_bool
+where (A OR (B AND C)) != (A OR B AND C);
+count(*)
+0
+select A, B, C, (A AND B) OR C, A AND (B OR C), A AND B OR C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A AND B) OR C	A AND (B OR C)	A AND B OR C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	NULL	NULL	NULL
+NULL	NULL	1	1	NULL	1
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	0	0	0
+NULL	0	1	1	NULL	1
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	NULL	NULL	NULL
+NULL	1	1	1	NULL	1
+0	NULL	NULL	NULL	0	NULL
+0	NULL	0	0	0	0
+0	NULL	1	1	0	1
+0	0	NULL	NULL	0	NULL
+0	0	0	0	0	0
+0	0	1	1	0	1
+0	1	NULL	NULL	0	NULL
+0	1	0	0	0	0
+0	1	1	1	0	1
+1	NULL	NULL	NULL	NULL	NULL
+1	NULL	0	NULL	NULL	NULL
+1	NULL	1	1	1	1
+1	0	NULL	NULL	NULL	NULL
+1	0	0	0	0	0
+1	0	1	1	1	1
+1	1	NULL	1	1	1
+1	1	0	1	1	1
+1	1	1	1	1	1
+select count(*) from t1_30237_bool
+where ((A AND B) OR C) != (A AND B OR C);
+count(*)
+0
+Testing that AND has precedence over XOR
+select A, B, C, (A XOR B) AND C, A XOR (B AND C), A XOR B AND C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A XOR B) AND C	A XOR (B AND C)	A XOR B AND C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	0	NULL	NULL
+NULL	NULL	1	NULL	NULL	NULL
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	0	NULL	NULL
+NULL	0	1	NULL	NULL	NULL
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	0	NULL	NULL
+NULL	1	1	NULL	NULL	NULL
+0	NULL	NULL	NULL	NULL	NULL
+0	NULL	0	0	0	0
+0	NULL	1	NULL	NULL	NULL
+0	0	NULL	0	0	0
+0	0	0	0	0	0
+0	0	1	0	0	0
+0	1	NULL	NULL	NULL	NULL
+0	1	0	0	0	0
+0	1	1	1	1	1
+1	NULL	NULL	NULL	NULL	NULL
+1	NULL	0	0	1	1
+1	NULL	1	NULL	NULL	NULL
+1	0	NULL	NULL	1	1
+1	0	0	0	1	1
+1	0	1	1	1	1
+1	1	NULL	0	NULL	NULL
+1	1	0	0	1	1
+1	1	1	0	0	0
+select count(*) from t1_30237_bool
+where (A XOR (B AND C)) != (A XOR B AND C);
+count(*)
+0
+select A, B, C, (A AND B) XOR C, A AND (B XOR C), A AND B XOR C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A AND B) XOR C	A AND (B XOR C)	A AND B XOR C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	NULL	NULL	NULL
+NULL	NULL	1	NULL	NULL	NULL
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	0	0	0
+NULL	0	1	1	NULL	1
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	NULL	NULL	NULL
+NULL	1	1	NULL	0	NULL
+0	NULL	NULL	NULL	0	NULL
+0	NULL	0	0	0	0
+0	NULL	1	1	0	1
+0	0	NULL	NULL	0	NULL
+0	0	0	0	0	0
+0	0	1	1	0	1
+0	1	NULL	NULL	0	NULL
+0	1	0	0	0	0
+0	1	1	1	0	1
+1	NULL	NULL	NULL	NULL	NULL
+1	NULL	0	NULL	NULL	NULL
+1	NULL	1	NULL	NULL	NULL
+1	0	NULL	NULL	NULL	NULL
+1	0	0	0	0	0
+1	0	1	1	1	1
+1	1	NULL	NULL	NULL	NULL
+1	1	0	1	1	1
+1	1	1	0	0	0
+select count(*) from t1_30237_bool
+where ((A AND B) XOR C) != (A AND B XOR C);
+count(*)
+0
+Testing that XOR has precedence over OR
+select A, B, C, (A XOR B) OR C, A XOR (B OR C), A XOR B OR C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A XOR B) OR C	A XOR (B OR C)	A XOR B OR C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	NULL	NULL	NULL
+NULL	NULL	1	1	NULL	1
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	NULL	NULL	NULL
+NULL	0	1	1	NULL	1
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	NULL	NULL	NULL
+NULL	1	1	1	NULL	1
+0	NULL	NULL	NULL	NULL	NULL
+0	NULL	0	NULL	NULL	NULL
+0	NULL	1	1	1	1
+0	0	NULL	NULL	NULL	NULL
+0	0	0	0	0	0
+0	0	1	1	1	1
+0	1	NULL	1	1	1
+0	1	0	1	1	1
+0	1	1	1	1	1
+1	NULL	NULL	NULL	NULL	NULL
+1	NULL	0	NULL	NULL	NULL
+1	NULL	1	1	0	1
+1	0	NULL	1	NULL	1
+1	0	0	1	1	1
+1	0	1	1	0	1
+1	1	NULL	NULL	0	NULL
+1	1	0	0	0	0
+1	1	1	1	0	1
+select count(*) from t1_30237_bool
+where ((A XOR B) OR C) != (A XOR B OR C);
+count(*)
+0
+select A, B, C, (A OR B) XOR C, A OR (B XOR C), A OR B XOR C
+from t1_30237_bool order by A, B, C;
+A	B	C	(A OR B) XOR C	A OR (B XOR C)	A OR B XOR C
+NULL	NULL	NULL	NULL	NULL	NULL
+NULL	NULL	0	NULL	NULL	NULL
+NULL	NULL	1	NULL	NULL	NULL
+NULL	0	NULL	NULL	NULL	NULL
+NULL	0	0	NULL	NULL	NULL
+NULL	0	1	NULL	1	1
+NULL	1	NULL	NULL	NULL	NULL
+NULL	1	0	1	1	1
+NULL	1	1	0	NULL	NULL
+0	NULL	NULL	NULL	NULL	NULL
+0	NULL	0	NULL	NULL	NULL
+0	NULL	1	NULL	NULL	NULL
+0	0	NULL	NULL	NULL	NULL
+0	0	0	0	0	0
+0	0	1	1	1	1
+0	1	NULL	NULL	NULL	NULL
+0	1	0	1	1	1
+0	1	1	0	0	0
+1	NULL	NULL	NULL	1	1
+1	NULL	0	1	1	1
+1	NULL	1	0	1	1
+1	0	NULL	NULL	1	1
+1	0	0	1	1	1
+1	0	1	0	1	1
+1	1	NULL	NULL	1	1
+1	1	0	1	1	1
+1	1	1	0	1	1
+select count(*) from t1_30237_bool
+where (A OR (B XOR C)) != (A OR B XOR C);
+count(*)
+0
+drop table t1_30237_bool;
diff -Nrup a/mysql-test/t/parser_precedence.test b/mysql-test/t/parser_precedence.test
--- /dev/null	Wed Dec 31 16:00:00 196900
+++ b/mysql-test/t/parser_precedence.test	2007-08-22 11:05:33 -06:00
@@ -0,0 +1,93 @@
+
+--disable_warnings
+drop table if exists t1_30237_bool;
+--enable_warnings
+
+create table t1_30237_bool(A boolean, B boolean, C boolean);
+
+insert into t1_30237_bool values
+(FALSE, FALSE, FALSE),
+(FALSE, FALSE, NULL),
+(FALSE, FALSE, TRUE),
+(FALSE, NULL, FALSE),
+(FALSE, NULL, NULL),
+(FALSE, NULL, TRUE),
+(FALSE, TRUE, FALSE),
+(FALSE, TRUE, NULL),
+(FALSE, TRUE, TRUE),
+(NULL, FALSE, FALSE),
+(NULL, FALSE, NULL),
+(NULL, FALSE, TRUE),
+(NULL, NULL, FALSE),
+(NULL, NULL, NULL),
+(NULL, NULL, TRUE),
+(NULL, TRUE, FALSE),
+(NULL, TRUE, NULL),
+(NULL, TRUE, TRUE),
+(TRUE, FALSE, FALSE),
+(TRUE, FALSE, NULL),
+(TRUE, FALSE, TRUE),
+(TRUE, NULL, FALSE),
+(TRUE, NULL, NULL),
+(TRUE, NULL, TRUE),
+(TRUE, TRUE, FALSE),
+(TRUE, TRUE, NULL),
+(TRUE, TRUE, TRUE) ;
+
+--echo Testing OR, XOR, AND
+select A, B, A OR B, A XOR B, A AND B
+  from t1_30237_bool where C is null order by A, B;
+
+--echo Testing that OR is associative 
+select A, B, C, (A OR B) OR C, A OR (B OR C), A OR B OR C
+ from t1_30237_bool order by A, B, C;
+
+select count(*) from t1_30237_bool
+  where ((A OR B) OR C) != (A OR (B OR C));
+
+--echo Testing that XOR is associative 
+select A, B, C, (A XOR B) XOR C, A XOR (B XOR C), A XOR B XOR C
+  from t1_30237_bool order by A, B, C;
+
+select count(*) from t1_30237_bool
+  where ((A XOR B) XOR C) != (A XOR (B XOR C));
+
+--echo Testing that AND is associative 
+select A, B, C, (A AND B) AND C, A AND (B AND C), A AND B AND C
+  from t1_30237_bool order by A, B, C;
+
+select count(*) from t1_30237_bool
+  where ((A AND B) AND C) != (A AND (B AND C));
+
+--echo Testing that AND has precedence over OR
+select A, B, C, (A OR B) AND C, A OR (B AND C), A OR B AND C
+  from t1_30237_bool order by A, B, C;
+select count(*) from t1_30237_bool
+  where (A OR (B AND C)) != (A OR B AND C);
+select A, B, C, (A AND B) OR C, A AND (B OR C), A AND B OR C
+  from t1_30237_bool order by A, B, C;
+select count(*) from t1_30237_bool
+  where ((A AND B) OR C) != (A AND B OR C);
+
+--echo Testing that AND has precedence over XOR
+select A, B, C, (A XOR B) AND C, A XOR (B AND C), A XOR B AND C
+  from t1_30237_bool order by A, B, C;
+select count(*) from t1_30237_bool
+  where (A XOR (B AND C)) != (A XOR B AND C);
+select A, B, C, (A AND B) XOR C, A AND (B XOR C), A AND B XOR C
+  from t1_30237_bool order by A, B, C;
+select count(*) from t1_30237_bool
+  where ((A AND B) XOR C) != (A AND B XOR C);
+
+--echo Testing that XOR has precedence over OR
+select A, B, C, (A XOR B) OR C, A XOR (B OR C), A XOR B OR C
+  from t1_30237_bool order by A, B, C;
+select count(*) from t1_30237_bool
+  where ((A XOR B) OR C) != (A XOR B OR C);
+select A, B, C, (A OR B) XOR C, A OR (B XOR C), A OR B XOR C
+  from t1_30237_bool order by A, B, C;
+select count(*) from t1_30237_bool
+  where (A OR (B XOR C)) != (A OR B XOR C);
+
+drop table t1_30237_bool;
+
diff -Nrup a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h
--- a/sql/item_cmpfunc.h	2007-07-15 11:49:58 -06:00
+++ b/sql/item_cmpfunc.h	2007-08-22 11:05:33 -06:00
@@ -1361,6 +1361,7 @@ public:
   Item_cond(List<Item> &nlist)
     :Item_bool_func(), list(nlist), abort_on_null(0) {}
   bool add(Item *item) { return list.push_back(item); }
+  bool add_at_head(Item *item) { return list.push_front(item); }
   void add_at_head(List<Item> *nlist) { list.prepand(nlist); }
   bool fix_fields(THD *, Item **ref);
 
@@ -1554,6 +1555,15 @@ public:
   Item *neg_transformer(THD *thd);
 };
 
+inline bool is_cond_and(Item *item)
+{
+  if (item->type() != Item::COND_ITEM)
+    return FALSE;
+
+  Item_cond *cond_item= (Item_cond*) item;
+  return (cond_item->functype() == Item_func::COND_AND_FUNC);
+}
+
 class Item_cond_or :public Item_cond
 {
 public:
@@ -1575,6 +1585,14 @@ public:
   Item *neg_transformer(THD *thd);
 };
 
+inline bool is_cond_or(Item *item)
+{
+  if (item->type() != Item::COND_ITEM)
+    return FALSE;
+
+  Item_cond *cond_item= (Item_cond*) item;
+  return (cond_item->functype() == Item_func::COND_OR_FUNC);
+}
 
 /*
   XOR is Item_cond, not an Item_int_func because we could like to
diff -Nrup a/sql/sql_yacc.yy b/sql/sql_yacc.yy
--- a/sql/sql_yacc.yy	2007-07-23 16:23:33 -06:00
+++ b/sql/sql_yacc.yy	2007-08-22 11:05:33 -06:00
@@ -458,10 +458,10 @@ bool my_yyoverflow(short **a, YYSTYPE **
 
 %pure_parser					/* We have threads */
 /*
-  Currently there is 251 shift/reduce conflict. We should not introduce
-  new conflicts any more.
+  Currently there are 245 shift/reduce conflicts.
+  We should not introduce new conflicts any more.
 */
-%expect 251
+%expect 245
 
 %token  END_OF_INPUT
 
@@ -1011,7 +1011,8 @@ bool my_yyoverflow(short **a, YYSTYPE **
 /* A dummy token to force the priority of table_ref production in a join. */
 %left   TABLE_REF_PRIORITY
 %left   SET_VAR
-%left	OR_OR_SYM OR_SYM OR2_SYM XOR
+%left	OR_OR_SYM OR_SYM OR2_SYM
+%left	XOR
 %left	AND_SYM AND_AND_SYM
 %left	BETWEEN_SYM CASE_SYM WHEN_SYM THEN_SYM ELSE
 %left	EQ EQUAL_SYM GE GT_SYM LE LT NE IS LIKE REGEXP IN_SYM
@@ -1024,6 +1025,7 @@ bool my_yyoverflow(short **a, YYSTYPE **
 %left	NEG '~'
 %right	NOT_SYM NOT2_SYM
 %right	BINARY COLLATE_SYM
+%left   INTERVAL_SYM
 
 %type <lex_str>
         IDENT IDENT_QUOTED TEXT_STRING DECIMAL_NUM FLOAT_NUM NUM LONG_NUM HEX_NUM
@@ -1066,7 +1068,8 @@ bool my_yyoverflow(short **a, YYSTYPE **
 %type <item>
 	literal text_literal insert_ident order_ident
 	simple_ident select_item2 expr opt_expr opt_else sum_expr in_sum_expr
-	variable variable_aux bool_term bool_factor bool_test bool_pri 
+	variable variable_aux bool_factor
+        bool_test bool_pri
 	predicate bit_expr bit_term bit_factor value_expr term factor
 	table_wild simple_expr udf_expr
 	expr_or_default set_expr_or_default interval_expr
@@ -4464,53 +4467,103 @@ optional_braces:
 	| '(' ')' {};
 
 /* all possible expressions */
-expr:	
-	  bool_term { Select->expr_list.push_front(new List<Item>); }
-          bool_or_expr
+expr:
+          bool_factor
+        | expr or expr %prec OR_SYM
           {
-            List<Item> *list= Select->expr_list.pop();
-            if (list->elements)
+            /*
+              Design notes:
+              Do not use a manually maintained stack like thd->lex->xxx_list,
+              but use the internal bison stack ($$, $1 and $3) instead.
+              Using the bison stack is:
+              - more robust to changes in the grammar,
+              - guaranteed to be in sync with the parser state,
+              - better for performances (no memory allocation).
+            */
+            Item_cond_or *item1;
+            Item_cond_or *item3;
+            if (is_cond_or($1))
             {
-              list->push_front($1);
-              $$= new Item_cond_or(*list);
-              /* optimize construction of logical OR to reduce
-                 amount of objects for complex expressions */
+              item1= (Item_cond_or*) $1;
+              if (is_cond_or($3))
+              {
+                item3= (Item_cond_or*) $3;
+                /*
+                  (X1 OR X2) OR (Y1 OR Y2) ==> OR (X1, X2, Y1, Y2)
+                */
+                item3->add_at_head(item1->argument_list());
+                $$ = $3;
+              }
+              else
+              {
+                /*
+                  (X1 OR X2) OR Y ==> OR (X1, X2, Y)
+                */
+                item1->add($3);
+                $$ = $1;
+              }
+            }
+            else if (is_cond_or($3))
+            {
+              item3= (Item_cond_or*) $3;
+              /*
+                X OR (Y1 OR Y2) ==> OR (X, Y1, Y2)
+              */
+              item3->add_at_head($1);
+              $$ = $3;
             }
             else
-              $$= $1;
-            delete list;
+            {
+              /* X OR Y */
+              $$ = new (YYTHD->mem_root) Item_cond_or($1, $3);
+            }
           }
-	;
-
-bool_or_expr:
-	/* empty */
-        | bool_or_expr or bool_term
-          { Select->expr_list.head()->push_back($3); }
-        ;
-
-bool_term:
-	bool_term XOR bool_term { $$= new Item_cond_xor($1,$3); }
-	| bool_factor { Select->expr_list.push_front(new List<Item>); }
-          bool_and_expr
+        | expr XOR expr %prec XOR
+          {
+            /* XOR is a proprietary extension */
+            $$ = new (YYTHD->mem_root) Item_cond_xor($1, $3);
+          }
+        | expr and expr %prec AND_SYM
           {
-            List<Item> *list= Select->expr_list.pop();
-            if (list->elements)
+            /* See comments in rule expr: expr or expr */
+            Item_cond_and *item1;
+            Item_cond_and *item3;
+            if (is_cond_and($1))
             {
-              list->push_front($1);
-              $$= new Item_cond_and(*list);
-              /* optimize construction of logical AND to reduce
-                 amount of objects for complex expressions */
+              item1= (Item_cond_and*) $1;
+              if (is_cond_and($3))
+              {
+                item3= (Item_cond_and*) $3;
+                /*
+                  (X1 AND X2) AND (Y1 AND Y2) ==> AND (X1, X2, Y1, Y2)
+                */
+                item3->add_at_head(item1->argument_list());
+                $$ = $3;
+              }
+              else
+              {
+                /*
+                  (X1 AND X2) AND Y ==> AND (X1, X2, Y)
+                */
+                item1->add($3);
+                $$ = $1;
+              }
+            }
+            else if (is_cond_and($3))
+            {
+              item3= (Item_cond_and*) $3;
+              /*
+                X AND (Y1 AND Y2) ==> AND (X, Y1, Y2)
+              */
+              item3->add_at_head($1);
+              $$ = $3;
             }
             else
-              $$= $1;
-            delete list;
+            {
+              /* X AND Y */
+              $$ = new (YYTHD->mem_root) Item_cond_and($1, $3);
+            }
           }
-	;
-
-bool_and_expr:
-	/* empty */
-        | bool_and_expr and bool_factor
-          { Select->expr_list.head()->push_back($3); }
         ;
 
 bool_factor:
@@ -4648,7 +4701,8 @@ all_or_any: ALL     { $$ = 1; }
         ;
 
 interval_expr:
-         INTERVAL_SYM expr { $$=$2; }
+          INTERVAL_SYM expr %prec INTERVAL_SYM
+          { $$=$2; }
         ;
 
 simple_expr:
Thread
bk commit into 5.0 tree (malff:1.2491) BUG#30237marc.alff22 Aug