List:Commits« Previous MessageNext Message »
From:pem Date:January 25 2006 2:11pm
Subject:bk commit into 5.0 tree (pem:1.2006) BUG#15737
View as plain text  
Below is the list of changes that have just been committed into a local
5.0 repository of pem. When pem 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.2006 06/01/25 15:11:49 pem@stripped +5 -0
  Fixed BUG#15737: Stored procedure optimizer bug with LEAVE
    Second version.
    The problem was that the optimizer didn't work correctly with forwards jumps
    to "no-op" hpop and cpop instructions.
    Don't generate "no-op" instructions (hpop 0 and cpop 0), it isn't actually
    necessary.

  sql/sql_yacc.yy
    1.450 06/01/25 15:11:45 pem@stripped +8 -9
    Don't generate "no-op" hpop and cpop instructions for LEAVE, it's not necessary.
    Just generate them when needed.

  sql/sp_head.h
    1.78 06/01/25 15:11:45 pem@stripped +22 -18
    Removed backpatch and opt_mark methods from sp_instr_hpop/cpop, since they're not needed
    any more.
    Added comments to optimizer methods in sp_instr.

  sql/sp_head.cc
    1.199 06/01/25 15:11:45 pem@stripped +9 -12
    Removed backpatch methods from sp_instr_hpop/cpop, since they're not needed any more.
    Added more documentation to sp_head::optimize()

  mysql-test/t/sp-code.test
    1.3 06/01/25 15:11:45 pem@stripped +143 -0
    New test case (BUG#15737)

  mysql-test/r/sp-code.result
    1.4 06/01/25 15:11:44 pem@stripped +139 -0
    Updated results for new test case (BUG#15737)

# 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:	pem
# Host:	pem.mysql.com
# Root:	/extern/mysql/work/bug15737/mysql-5.0

--- 1.449/sql/sql_yacc.yy	2006-01-24 18:15:09 +01:00
+++ 1.450/sql/sql_yacc.yy	2006-01-25 15:11:45 +01:00
@@ -2064,17 +2064,16 @@
 	    }
 	    else
 	    {
-	      uint ip= sp->instructions();
 	      sp_instr_jump *i;
-	      sp_instr_hpop *ih;
-	      sp_instr_cpop *ic;
+	      uint ip= sp->instructions();
+	      uint n;
 
-	      ih= new sp_instr_hpop(ip++, ctx, 0);
-	      sp->push_backpatch(ih, lab);
-	      sp->add_instr(ih);
-	      ic= new sp_instr_cpop(ip++, ctx, 0);
-	      sp->push_backpatch(ic, lab);
-	      sp->add_instr(ic);
+	      n= ctx->diff_handlers(lab->ctx);
+	      if (n)
+	        sp->add_instr(new sp_instr_hpop(ip++, ctx, n));
+	      n= ctx->diff_cursors(lab->ctx);
+	      if (n)
+	        sp->add_instr(new sp_instr_cpop(ip++, ctx, n));
 	      i= new sp_instr_jump(ip, ctx);
 	      sp->push_backpatch(i, lab);  /* Jumping forward */
               sp->add_instr(i);

--- 1.3/mysql-test/r/sp-code.result	2006-01-16 17:55:17 +01:00
+++ 1.4/mysql-test/r/sp-code.result	2006-01-25 15:11:44 +01:00
@@ -1,3 +1,5 @@
+drop procedure if exists empty;
+drop procedure if exists code_sample;
 create procedure empty()
 begin
 end;
@@ -60,3 +62,140 @@
 20	cpop 1
 21	stmt 0 "select t.name, t.idx from t2 t order ..."
 drop procedure code_sample;
+drop procedure if exists sudoku_solve;
+create procedure sudoku_solve(p_naive boolean, p_all boolean)
+deterministic
+modifies sql data
+begin
+drop temporary table if exists sudoku_work, sudoku_schedule;
+create temporary table sudoku_work
+(
+row smallint not null,
+col smallint not null,
+dig smallint not null,
+cnt smallint,
+key using btree (cnt),
+key using btree (row),
+key using btree (col),
+unique key using hash (row,col)
+);
+create temporary table sudoku_schedule
+(
+idx int not null auto_increment primary key,
+row smallint not null,
+col smallint not null
+);
+call sudoku_init();
+if p_naive then
+update sudoku_work set cnt = 0 where dig = 0;
+else
+call sudoku_count();
+end if;
+insert into sudoku_schedule (row,col)
+select row,col from sudoku_work where cnt is not null order by cnt desc;
+begin
+declare v_scounter bigint default 0;
+declare v_i smallint default 1;
+declare v_dig smallint;
+declare v_schedmax smallint;
+select count(*) into v_schedmax from sudoku_schedule;
+more: 
+loop
+begin
+declare v_tcounter bigint default 0;
+sched:
+while v_i <= v_schedmax do
+begin
+declare v_row, v_col smallint;
+select row,col into v_row,v_col from sudoku_schedule where v_i = idx;
+select dig into v_dig from sudoku_work
+where v_row = row and v_col = col;
+case v_dig
+when 0 then
+set v_dig = 1;
+update sudoku_work set dig = 1
+where v_row = row and v_col = col;
+when 9 then
+if v_i > 0 then
+update sudoku_work set dig = 0
+where v_row = row and v_col = col;
+set v_i = v_i - 1;
+iterate sched;
+else
+select v_scounter as 'Solutions';
+leave more;
+end if;
+else
+set v_dig = v_dig + 1;
+update sudoku_work set dig = v_dig
+where v_row = row and v_col = col;
+end case;
+set v_tcounter = v_tcounter + 1;
+if not sudoku_digit_ok(v_row, v_col, v_dig) then
+iterate sched;
+end if;
+set v_i = v_i + 1;
+end;
+end while sched;
+select dig from sudoku_work;
+select v_tcounter as 'Tests';
+set v_scounter = v_scounter + 1;
+if p_all and v_i > 0 then
+set v_i = v_i - 1;
+else
+leave more;
+end if;
+end;
+end loop more;
+end;
+drop temporary table sudoku_work, sudoku_schedule;
+end//
+show procedure code sudoku_solve;
+Pos	Instruction
+0	stmt 9 "drop temporary table if exists sudoku..."
+1	stmt 1 "create temporary table sudoku_work ( ..."
+2	stmt 1 "create temporary table sudoku_schedul..."
+3	stmt 95 "call sudoku_init("
+4	jump_if_not 7(8) p_naive@0
+5	stmt 4 "update sudoku_work set cnt = 0 where ..."
+6	jump 8
+7	stmt 95 "call sudoku_count("
+8	stmt 6 "insert into sudoku_schedule (row,col)..."
+9	set v_scounter@2 0
+10	set v_i@3 1
+11	set v_dig@4 NULL
+12	set v_schedmax@5 NULL
+13	stmt 0 "select count(*) into v_schedmax from ..."
+14	set v_tcounter@6 0
+15	jump_if_not 39(39) (v_i@3 <= v_schedmax@5)
+16	set v_row@7 NULL
+17	set v_col@8 NULL
+18	stmt 0 "select row,col into v_row,v_col from ..."
+19	stmt 0 "select dig into v_dig from sudoku_wor..."
+20	set_case_expr 0 v_dig@4
+21	jump_if_not 25(34) (case_expr@0 = 0)
+22	set v_dig@4 1
+23	stmt 4 "update sudoku_work set dig = 1 where ..."
+24	jump 34
+25	jump_if_not 32(34) (case_expr@0 = 9)
+26	jump_if_not 30(34) (v_i@3 > 0)
+27	stmt 4 "update sudoku_work set dig = 0 where ..."
+28	set v_i@3 (v_i@3 - 1)
+29	jump 15
+30	stmt 0 "select v_scounter as 'Solutions'"
+31	jump 45
+32	set v_dig@4 (v_dig@4 + 1)
+33	stmt 4 "update sudoku_work set dig = v_dig wh..."
+34	set v_tcounter@6 (v_tcounter@6 + 1)
+35	jump_if_not 37(37) not(`test`.`sudoku_digit_ok`(v_row@7,v_col@8,v_dig@4))
+36	jump 15
+37	set v_i@3 (v_i@3 + 1)
+38	jump 15
+39	stmt 0 "select dig from sudoku_work"
+40	stmt 0 "select v_tcounter as 'Tests'"
+41	set v_scounter@2 (v_scounter@2 + 1)
+42	jump_if_not 45(14) (p_all@1 and (v_i@3 > 0))
+43	set v_i@3 (v_i@3 - 1)
+44	jump 14
+45	stmt 9 "drop temporary table sudoku_work, sud..."
+drop procedure sudoku_solve;

--- 1.2/mysql-test/t/sp-code.test	2005-11-18 18:04:57 +01:00
+++ 1.3/mysql-test/t/sp-code.test	2006-01-25 15:11:45 +01:00
@@ -4,6 +4,11 @@
 
 -- source include/is_debug_build.inc
 
+--disable_warnings
+drop procedure if exists empty;
+drop procedure if exists code_sample;
+--enable_warnings
+
 create procedure empty()
 begin
 end;
@@ -47,3 +52,141 @@
 delimiter ;//
 show procedure code code_sample;
 drop procedure code_sample;
+
+
+#
+# BUG#15737: Stored procedure optimizer bug with LEAVE
+#
+# This is a much more extensive test case than is strictly needed,
+# but it was kept as is for two reasons:
+# - The bug occurs under some quite special circumstances, so it
+#   wasn't trivial to create a smaller test,
+# - There's some value in having another more complex code sample
+#   in this test file. This might catch future code generation bugs
+#   that doesn't not show in behaviour in any obvious way.
+
+--disable_warnings
+drop procedure if exists sudoku_solve;
+--enable_warnings
+
+delimiter //;
+create procedure sudoku_solve(p_naive boolean, p_all boolean)
+  deterministic
+  modifies sql data
+begin
+  drop temporary table if exists sudoku_work, sudoku_schedule;
+
+  create temporary table sudoku_work
+  (
+    row smallint not null,
+    col smallint not null,
+    dig smallint not null,
+    cnt smallint,
+    key using btree (cnt),
+    key using btree (row),
+    key using btree (col),
+    unique key using hash (row,col)
+  );
+
+  create temporary table sudoku_schedule
+  (
+    idx int not null auto_increment primary key,
+    row smallint not null,
+    col smallint not null
+  );
+
+  call sudoku_init();
+
+  if p_naive then
+    update sudoku_work set cnt = 0 where dig = 0;
+  else
+    call sudoku_count();
+  end if;
+  insert into sudoku_schedule (row,col)
+    select row,col from sudoku_work where cnt is not null order by cnt desc;
+
+  begin
+    declare v_scounter bigint default 0;
+    declare v_i smallint default 1;
+    declare v_dig smallint;
+    declare v_schedmax smallint;
+
+    select count(*) into v_schedmax from sudoku_schedule;
+
+   more: 
+    loop
+    begin
+      declare v_tcounter bigint default 0;
+
+     sched:
+      while v_i <= v_schedmax do
+      begin
+        declare v_row, v_col smallint;
+
+        select row,col into v_row,v_col from sudoku_schedule where v_i = idx;
+
+        select dig into v_dig from sudoku_work
+          where v_row = row and v_col = col;
+
+        case v_dig
+        when 0 then
+          set v_dig = 1;
+          update sudoku_work set dig = 1
+            where v_row = row and v_col = col;
+        when 9 then
+          if v_i > 0 then
+            update sudoku_work set dig = 0
+              where v_row = row and v_col = col;
+            set v_i = v_i - 1;
+            iterate sched;
+          else
+            select v_scounter as 'Solutions';
+            leave more;
+          end if;
+        else
+          set v_dig = v_dig + 1;
+          update sudoku_work set dig = v_dig
+            where v_row = row and v_col = col;
+        end case;
+
+        set v_tcounter = v_tcounter + 1;
+        if not sudoku_digit_ok(v_row, v_col, v_dig) then
+          iterate sched;
+        end if;
+        set v_i = v_i + 1;
+      end;
+      end while sched;
+
+      select dig from sudoku_work;
+      select v_tcounter as 'Tests';
+      set v_scounter = v_scounter + 1;
+
+      if p_all and v_i > 0 then
+        set v_i = v_i - 1;
+      else
+        leave more;
+      end if;
+    end;
+    end loop more;
+  end;
+
+  drop temporary table sudoku_work, sudoku_schedule;
+end//
+delimiter ;//
+
+# The interestings parts are where the code for the two "leave" are:
+# ...
+#|  26 | jump_if_not 30 (v_i@3 > 0)                                            |
+# ...
+#|  30 | stmt 0 "select v_scounter as 'Solutions'"                             |
+#|  31 | jump 45                                                               |
+# ...
+#|  42 | jump_if_not 45 (p_all@1 and (v_i@3 > 0))                              |
+#|  43 | set v_i@3 (v_i@3 - 1)                                                 |
+#|  44 | jump 14                                                               |
+#|  45 | stmt 9 "drop temporary table sudoku_work, sud..."                     |
+#+-----+-----------------------------------------------------------------------+
+# The bug appeared at position 42 (with the wrong destination).
+show procedure code sudoku_solve;
+
+drop procedure sudoku_solve;

--- 1.198/sql/sp_head.cc	2006-01-20 13:59:18 +01:00
+++ 1.199/sql/sp_head.cc	2006-01-25 15:11:45 +01:00
@@ -2011,6 +2011,15 @@
     1) Mark used instructions
        1.1) While doing this, shortcut jumps to jump instructions
     2) Compact the code, removing unused instructions
+
+  This is the main mark and move loop; it relies on the following methods
+  in sp_instr and its subclasses:
+
+  opt_mark()           Mark instruction as reachable (will recurse for jumps)
+  opt_shortcut_jump()  Shortcut jumps to the final destination;
+                       used by opt_mark().
+  opt_move()           Update moved instruction
+  set_destination()    Set the new destination (jump instructions only)
 */
 
 void sp_head::optimize()
@@ -2703,12 +2712,6 @@
   str->qs_append(m_count);
 }
 
-void
-sp_instr_hpop::backpatch(uint dest, sp_pcontext *dst_ctx)
-{
-  m_count= m_ctx->diff_handlers(dst_ctx);
-}
-
 
 /*
   sp_instr_hreturn class functions
@@ -2828,12 +2831,6 @@
     return;
   str->qs_append(STRING_WITH_LEN("cpop "));
   str->qs_append(m_count);
-}
-
-void
-sp_instr_cpop::backpatch(uint dest, sp_pcontext *dst_ctx)
-{
-  m_count= m_ctx->diff_cursors(dst_ctx);
 }
 
 

--- 1.77/sql/sp_head.h	2006-01-19 16:13:00 +01:00
+++ 1.78/sql/sp_head.h	2006-01-25 15:11:45 +01:00
@@ -461,17 +461,34 @@
   virtual void backpatch(uint dest, sp_pcontext *dst_ctx)
   {}
 
+  /*
+    Mark this instruction as reachable during optimization and return the
+    index to the next instruction. Jump instruction will mark their
+    destination too recursively.
+  */
   virtual uint opt_mark(sp_head *sp)
   {
     marked= 1;
     return m_ip+1;
   }
 
+  /*
+    Short-cut jumps to jumps during optimization. This is used by the
+    jump instructions' opt_mark() methods. 'start' is the starting point,
+    used to prevent the mark sweep from looping for ever. Return the
+    end destination.
+  */
   virtual uint opt_shortcut_jump(sp_head *sp, sp_instr *start)
   {
     return m_ip;
   }
 
+  /*
+    Inform the instruction that it has been moved during optimization.
+    Most instructions will simply update its index, but jump instructions
+    must also take care of their destination pointers. Forward jumps get
+    pushed to the backpatch list 'ibp'.
+  */
   virtual void opt_move(uint dst, List<sp_instr> *ibp)
   {
     m_ip= dst;
@@ -696,6 +713,9 @@
       m_dest= dest;
   }
 
+  /*
+    Update the destination; used by the optimizer.
+  */
   virtual void set_destination(uint old_dest, uint new_dest)
   {
     if (m_dest == old_dest)
@@ -739,6 +759,7 @@
 
   virtual uint opt_mark(sp_head *sp);
 
+  /* Override sp_instr_jump's shortcut; we stop here */
   virtual uint opt_shortcut_jump(sp_head *sp, sp_instr *start)
   {
     return m_ip;
@@ -822,6 +843,7 @@
 
   virtual uint opt_mark(sp_head *sp);
 
+  /* Override sp_instr_jump's shortcut; we stop here. */
   virtual uint opt_shortcut_jump(sp_head *sp, sp_instr *start)
   {
     return m_ip;
@@ -859,15 +881,6 @@
 
   virtual void print(String *str);
 
-  virtual void backpatch(uint dest, sp_pcontext *dst_ctx);
-
-  virtual uint opt_mark(sp_head *sp)
-  {
-    if (m_count)
-      marked= 1;
-    return m_ip+1;
-  }
-
 private:
 
   uint m_count;
@@ -952,15 +965,6 @@
   virtual int execute(THD *thd, uint *nextp);
 
   virtual void print(String *str);
-
-  virtual void backpatch(uint dest, sp_pcontext *dst_ctx);
-
-  virtual uint opt_mark(sp_head *sp)
-  {
-    if (m_count)
-      marked= 1;
-    return m_ip+1;
-  }
 
 private:
 
Thread
bk commit into 5.0 tree (pem:1.2006) BUG#15737pem25 Jan