WL#3146 "less locking in auto_increment":

this is a cleanup patch for our current auto_increment handling:
new names for auto_increment variables in THD, new methods to manipulate them
(see sql_class.h), some move into handler::, causing less backup/restore
work when executing substatements. 
This makes the logic hopefully clearer, less work is is needed in
mysql_insert().
By cleaning up, using different variables for different purposes (instead
of one for 3 things...), we fix those bugs, which someone may want to fix
in 5.0 too:
BUG#20339 "stored procedure using LAST_INSERT_ID() does not replicate
statement-based"
BUG#20341 "stored function inserting into one auto_increment puts bad
data in slave"
BUG#19243 "wrong LAST_INSERT_ID() after ON DUPLICATE KEY UPDATE"
(now if a row is updated, LAST_INSERT_ID() will return its id)
and re-fixes:
BUG#6880 "LAST_INSERT_ID() value changes during multi-row INSERT"
(already fixed differently by Ramil in 4.1)
Test of documented behaviour of mysql_insert_id() (there was no test).
The behaviour changes introduced are:
- LAST_INSERT_ID() now returns "the first autogenerated auto_increment value
successfully inserted", instead of "the first autogenerated auto_increment
value if any row was successfully inserted", see auto_increment.test.
Same for mysql_insert_id(), see mysql_client_test.c.
- LAST_INSERT_ID() returns the id of the updated row if ON DUPLICATE KEY
UPDATE, see auto_increment.test. Same for mysql_insert_id(), see
mysql_client_test.c.
- LAST_INSERT_ID() does not change if no autogenerated value was successfully 
inserted (it used to then be 0), see auto_increment.test.
- if in INSERT SELECT no autogenerated value was successfully inserted,
mysql_insert_id() now returns the id of the last inserted row (it already
did this for INSERT VALUES), see mysql_client_test.c.
- if INSERT SELECT uses LAST_INSERT_ID(X), mysql_insert_id() now returns X
(it already did this for INSERT VALUES), see mysql_client_test.c.
- NDB now behaves like other engines wrt SET INSERT_ID: with INSERT IGNORE,
the id passed in SET INSERT_ID is re-used until a row succeeds; SET INSERT_ID
influences not only the first row now.

Additionally, when unlocking a table we check that the thread is not keeping
a next_insert_id (as the table is unlocked that id is potentially out-of-date);
forgetting about this next_insert_id is done in a new
handler::ha_release_auto_increment().

Finally we prepare for engines capable of reserving finite-length intervals
of auto_increment values: we store such intervals in THD. The next step
(to be done by the replication team in 5.1) is to read those intervals from
THD and actually store them in the statement-based binary log. NDB
will be a good engine to test that.


mysql-test/extra/binlog_tests/binlog.test:
  Testing that if INSERT_ID is set to a value too big for the
  column's type, the binlogged INSERT_ID is the truncated value
  (important if slave has a column of a "wider" numeric type).
  Testing binlogging of INSERT_ID with INSERT DELAYED, to be sure that 
  we binlog an INSERT_ID event only for the delayed rows which use one.
mysql-test/extra/rpl_tests/rpl_insert_id.test:
  Testcase for BUG#20339 "stored procedure using
  LAST_INSERT_ID() does not replicate statement-based".
  Testcase for BUG#20341 "stored function inserting into one
  auto_increment puts bad data in slave".
mysql-test/extra/rpl_tests/rpl_loaddata.test:
  Test that LOAD DATA INFILE sets a value for a future LAST_INSERT_ID().
mysql-test/r/auto_increment.result:
  behaviour change: when INSERT totally fails (not even succeeds
  partially and then rolls back), don't change last_insert_id().
  Behaviour change: LAST_INSERT_ID() is now the first successfully inserted,
  autogenerated, id.
  Behaviour change: if INSERT ON DUPLICATE KEY UPDATE, if the table has auto_increment
  and a row is updated, then LAST_INSERT_ID() returns the id of this row.
mysql-test/r/binlog_row_binlog.result:
  result update
mysql-test/r/binlog_stm_binlog.result:
  result update
mysql-test/r/insert.result:
  result update
mysql-test/r/rpl_insert_id.result:
  result update
mysql-test/r/rpl_loaddata.result:
  result update
mysql-test/r/rpl_ndb_auto_inc.result:
  ndb's behaviour is now like other engines wrt SET INSERT_ID
  in a multi-row INSERT:
  - with INSERT IGNORE: the id passed in SET INSERT_ID is re-used until
  a row succeeds.
  - generally, SET INSERT_ID sets the first value and other values are
  simply computed from this first value, instead of previously where
  the 2nd and subsequent values where not influenced by SET INSERT_ID;
  this good change is due to the removal of "thd->next_insert_id=0"
  from ha_ndbcluster.
mysql-test/t/auto_increment.test:
  A testcase of BUG#19243: if ON DUPLICATE KEY UPDATE updates a row,
  LAST_INSERT_ID() now returns the id of the row.
  Test of new behaviour of last_insert_id() when no autogenerated value was
  inserted, or when only some autogenerated value (not the first of them) was
  inserted.
mysql-test/t/insert.test:
  testing INSERT IGNORE re-using generated values
sql/ha_federated.cc:
  update for new variables.
sql/ha_ndbcluster.cc:
  handler::auto_increment_column_changed not needed, equivalent to
  (insert_id_for_cur_row > 0).
  thd->next_insert_id=0 not needed anymore; it was used to force
  handler::update_auto_increment() to call ha_ndbcluster::get_auto_increment()
  for each row of a multi-row INSERT, now this happens naturally
  because NDB says "I have reserved you *one* value" in get_auto_increment(),
  so handler::update_auto_increment() calls again for next row.
sql/handler.cc:
  More comments, use of new methods and variables. Hopes to be clearer
  than current code.
  thd->prev_insert_id not in THD anymore: it is managed locally by inserters
  (like mysql_insert()).
  THD::clear_next_insert_id is now equivalent to
  handler::next_insert_id > 0.
  get_auto_increment() reserves an interval of values from the engine,
  uses this interval for next rows of the statement, until interval
  is exhausted then it asks for another interval (of a bigger size
  than the first one; size doubles until reaching 65535 then it stays constant).
  If doing statement-based binlogging, intervals are remembered in a list
  for storage in the binlog.
  For "forced" insert_id values (SET INSERT_ID or replication slave),
  forced_auto_inc_intervals is non-empty and the handler takes its intervals
  from there, without calling get_auto_increment().
  ha_release_auto_increment() resets the handler's auto_increment variables;
  it calls release_auto_increment() which is handler-dependent and
  serves to return to the engine any unused tail of the last used
  interval.
  If ending a statement, next_insert_id>0 means that autoinc values have been
  generated or taken from the master's binlog (in a replication slave) so
  we clear those values read from binlog, so that next top- or sub-
  statement does not use them.
sql/handler.h:
  handler::auto_increment_changed can be replaced by
  (handler::insert_id_for_cur_row > 0).
  THD::next_insert_id moves into handler (more natural, and prepares
  for the day when we'll support a single statement inserting into
  two tables - "multi-table INSERT" like we have UPDATE - will this
  happen?).
  This move makes the backup/restore of THD::next_insert_id when entering
  a substatement unneeded, as each substatement has its own handler
  objects.
sql/item_func.cc:
  new names for variables.
  For the setting of what mysql_insert_id() will return to the client,
  LAST_INSERT_ID(X) used to simply pretend that the generated autoinc
  value for the current row was X, but this led to having no reliable
  way to know the really generated value, so we now have a bool:
  thd->arg_of_last_insert_id_function which enables us to know that
  LAST_INSERT_ID(X) was called (and then X can be found in
  thd->first_successful_insert_id_in_prev_stmt).
sql/log.cc:
  new variable names for insert_ids. Removing some unused variables in the slow
  log.
sql/log_event.cc:
  new variable names, comments. Preparing for when master's won't binlog
  LAST_INSERT_ID if it was 0.
sql/set_var.cc:
  new variable names.
  The last change repeats how Bar fixed BUG#20392
  "INSERT_ID session variable has weird value" in 5.0.
sql/sql_class.cc:
  new variables for insert_id. In THD::cleanup_after_query() we fix
  BUG#20339 "stored procedure using LAST_INSERT_ID() does not replicate
  statement-based" (will one want to fix it in 5.0?). Many comments
  about what stored functions do to auto_increment.
  In reset|restore_sub_statement_state(), we need to backup less
  auto_inc variables as some of them have moved to the handler;
  we backup/restore those which are about the current top- or sub-
  statement, *not* those about the statement-based binlog
  (which evolve as the top- and sub-statement execute).
  Because we split THD::last_insert_id into 
  THD::first_successful_insert_id_in_prev_stmt and
  THD::auto_inc_intervals_for_binlog (among others), we fix
  BUG#20341 "stored function inserting into one auto_increment
  puts bad data in slave": indeed we can afford to not backup/restore
  THD::auto_inc_intervals_for_binlog (which fixes the bug) while still
  backing up / restoring THD::first_successful_insert_id_in_prev_stmt
  (ensuring that the top-level LAST_INSERT_ID() is not affected by INSERTs
  done by sub-statements, as is desirable and tested in rpl_insert_id.test).
sql/sql_class.h:
  new variables and methods for auto_increment.
  Some THD members move into handler (those which are really about
  the table being inserted), some stay in THD (those which are
  about what a future LAST_INSERT_ID() should return, or about
  what should be stored into the statement-based binlog).
  THD::next_insert_id moves to handler::.
  THD::clear_next_insert_id removed (had become equivalent
  to next_insert_id > 0).
  THD::last_insert_id becomes four:
  THD::first_successful_insert_id_in_cur_stmt,
  THD::auto_inc_intervals_for_binlog,
  handler::insert_id_for_cur_row,
  THD::first_successful_insert_id_in_prev_stmt.
  THD::current_insert_id becomes:
  THD::first_successful_insert_id_in_prev_stmt_for_binlog
  THD::prev_insert_id is removed, handler can just use
  handler::insert_id_for_cur_row instead (which is more accurate:
  for the first row, prev_insert_id was set before get_auto_increment
  was called, so was 0, causing a call to
  get_auto_increment() for the 2nd row if the 1st row fails;
  here we don't need the call as insert_id_for_cur_row has
  the value of the first row).
  THD::last_insert_id_used becomes: stmt_depends_on_first_row_in_prev_stmt
  THD::insert_id_used is removed (equivalent to
  auto_inc_intervals_for_binlog non empty).
  The interval returned by get_auto_increment() and currently being
  consumed is handler::auto_inc_interval_for_cur_row.
  Comments to explain each of them.
  select_insert::last_insert_id becomes autoinc_value_of_last_inserted_row.
sql/sql_insert.cc:
  the "id" variable is not changed for each row now; it used to compensate for
  this contradiction:
  - thd->last_insert_id supposed job was to keep the id of the first row
  - but it was updated for every row
  - so mysql_insert() made sure to catch its first value and restore it at the end of stmt.
  Now THD keeps the first value in first_successful_insert_id_in_cur_stmt,
  and value of the row in insert_id_for_cur_row. So "id" only serves to fill
  mysql_insert_id(), as depending on some conditions, "id" must be different
  values.
  Prev_insert_id moves from THD to write_record().
  We now set LAST_INSERT_ID() in ON DUPLICATE KEY UPDATE too (BUG#19243).
  In an INSERT DELAYED, we still "reset auto-increment caching" but differently
  (by calling ha_release_auto_increment()).
sql/sql_load.cc:
  no need to fiddle with "id", THD maintains
  THD::first_successful_insert_id_in_cur_stmt by itself and correctly now.
  ha_release_auto_increment() is now (logically) called before we unlock
  the table.
sql/sql_parse.cc:
  update to new variable names.
  Assertion that reset_thd_for_next_command() is not called for every
  substatement of a routine (I'm not against it, but if we do this change,
  statement-based binlogging needs some adjustments).
sql/sql_select.cc:
  update for new variable names
sql/sql_table.cc:
  next_insert_id not needed in mysql_alter_table(), THD manages.
sql/sql_update.cc:
  update for new variable names.
  Even though this is UPDATE, an insert id can be generated (by
  LAST_INSERT_ID(X)) and should be recorded because mysql_insert_id() wants
  to know about it.
sql/structs.h:
  A class for "discrete" intervals (intervals of integer numbers with a certain
  increment between them): Discrete_interval, and a class for a list of such
  intervals: Discrete_intervals_list
tests/mysql_client_test.c:
  tests of behaviour of mysql_insert_id(): there were no such tests, while in
  our manual we document its behaviour. In comments you'll notice the behaviour
  changes introduced (there are 5).

17 files changed, 686 insertions, 329 deletions

diff --git a/sql/ha_federated.cc b/sql/ha_federated.cc
index 91111a433dc..e592102f53e 100644
--- a/sql/ha_federated.cc
+++ b/sql/ha_federated.cc
@@ -1710,14 +1710,15 @@ int ha_federated::write_row(byte *buf)
   This method ensures that last_insert_id() works properly. What it simply does
   is calls last_insert_id() on the foreign database immediately after insert
   (if the table has an auto_increment field) and sets the insert id via
-  thd->insert_id(ID) (as well as storing thd->prev_insert_id)
+  thd->insert_id(ID)).
 */
 void ha_federated::update_auto_increment(void)
 {
   THD *thd= current_thd;
   DBUG_ENTER("ha_federated::update_auto_increment");
 
-  thd->insert_id(mysql->last_used_con->insert_id);
+  thd->first_successful_insert_id_in_cur_stmt= 
+    mysql->last_used_con->insert_id;
   DBUG_PRINT("info",("last_insert_id %d", stats.auto_increment_value));
 
   DBUG_VOID_RETURN;
diff --git a/sql/ha_ndbcluster.cc b/sql/ha_ndbcluster.cc
index bbeea2ca1ba..d09907781e1 100644
--- a/sql/ha_ndbcluster.cc
+++ b/sql/ha_ndbcluster.cc
@@ -2473,9 +2473,7 @@ int ha_ndbcluster::write_row(byte *record)
 
       m_skip_auto_increment= FALSE;
       update_auto_increment();
-      /* Ensure that handler is always called for auto_increment values */
-      thd->next_insert_id= 0;
-      m_skip_auto_increment= !auto_increment_column_changed;
+      m_skip_auto_increment= (insert_id_for_cur_row == 0);
     }
   }
 
diff --git a/sql/handler.cc b/sql/handler.cc
index 0dfb31fba8c..51b95030929 100644
--- a/sql/handler.cc
+++ b/sql/handler.cc
@@ -1514,7 +1514,10 @@ int handler::read_first_row(byte * buf, uint primary_key)
 }
 
 /*
-  Generate the next auto-increment number based on increment and offset
+  Generate the next auto-increment number based on increment and offset:
+  computes the lowest number
+  - strictly greater than "nr"
+  - of the form: auto_increment_offset + N * auto_increment_increment
 
   In most cases increment= offset= 1, in which case we get:
   1,2,3,4,5,...
@@ -1523,8 +1526,10 @@ int handler::read_first_row(byte * buf, uint primary_key)
 */
 
 inline ulonglong
-next_insert_id(ulonglong nr,struct system_variables *variables)
+compute_next_insert_id(ulonglong nr,struct system_variables *variables)
 {
+  if (variables->auto_increment_increment == 1)
+    return (nr+1); // optimization of the formula below
   nr= (((nr+ variables->auto_increment_increment -
          variables->auto_increment_offset)) /
        (ulonglong) variables->auto_increment_increment);
@@ -1546,7 +1551,7 @@ next_insert_id(ulonglong nr,struct system_variables *variables)
 
   IMPLEMENTATION
 
-    Updates columns with type NEXT_NUMBER if:
+    Updates the record's Field of type NEXT_NUMBER if:
 
   - If column value is set to NULL (in which case
     auto_increment_field_not_null is 0)
@@ -1554,25 +1559,31 @@ next_insert_id(ulonglong nr,struct system_variables *variables)
     set. In the future we will only set NEXT_NUMBER fields if one sets them
     to NULL (or they are not included in the insert list).
 
+    In those cases, we check if the currently reserved interval still has
+    values we have not used. If yes, we pick the smallest one and use it.
+    Otherwise:
 
-  There are two different cases when the above is true:
+  - If a list of intervals has been provided to the statement via SET
+    INSERT_ID or via an Intvar_log_event (in a replication slave), we pick the
+    first unused interval from this list, consider it as reserved.
 
-  - thd->next_insert_id == 0  (This is the normal case)
-    In this case we set the set the column for the first row to the value
-    next_insert_id(get_auto_increment(column))) which is normally
-    max-used-column-value +1.
+  - Otherwise we set the column for the first row to the value
+    next_insert_id(get_auto_increment(column))) which is usually
+    max-used-column-value+1.
+    We call get_auto_increment() for the first row in a multi-row
+    statement. get_auto_increment() will tell us the interval of values it
+    reserved for us.
 
-    We call get_auto_increment() only for the first row in a multi-row
-    statement. For the following rows we generate new numbers based on the
-    last used number.
+  - In both cases, for the following rows we use those reserved values without
+    calling the handler again (we just progress in the interval, computing
+    each new value from the previous one). Until we have exhausted them, then
+    we either take the next provided interval or call get_auto_increment()
+    again to reserve a new interval.
 
-  - thd->next_insert_id != 0.  This happens when we have read an Intvar event
-    of type INSERT_ID_EVENT from the binary log or when one has used SET
-    INSERT_ID=#.
-
-    In this case we will set the column to the value of next_insert_id.
-    The next row will be given the id
-    next_insert_id(next_insert_id)
+  - In both cases, the reserved intervals are remembered in
+    thd->auto_inc_intervals_in_cur_stmt_for_binlog if statement-based
+    binlogging; the last reserved interval is remembered in
+    auto_inc_interval_for_cur_row.
 
     The idea is that generated auto_increment values are predictable and
     independent of the column values in the table.  This is needed to be
@@ -1583,7 +1594,13 @@ next_insert_id(ulonglong nr,struct system_variables *variables)
     inserts a column with a higher value than the last used one, we will
     start counting from the inserted value.
 
-    thd->next_insert_id is cleared after it's been used for a statement.
+    This function's "outputs" are: the table's auto_increment field is filled
+    with a value, thd->next_insert_id is filled with the value to use for the
+    next row, if a value was autogenerated for the current row it is stored in
+    thd->insert_id_for_cur_row, if get_auto_increment() was called
+    thd->auto_inc_interval_for_cur_row is modified, if that interval is not
+    present in thd->auto_inc_intervals_in_cur_stmt_for_binlog it is added to
+    this list.
 
    TODO
 
@@ -1600,7 +1617,8 @@ next_insert_id(ulonglong nr,struct system_variables *variables)
 
 bool handler::update_auto_increment()
 {
-  ulonglong nr;
+  ulonglong nr, nb_reserved_values;
+  bool append= FALSE;
   THD *thd= table->in_use;
   struct system_variables *variables= &thd->variables;
   bool auto_increment_field_not_null;
@@ -1608,10 +1626,10 @@ bool handler::update_auto_increment()
   DBUG_ENTER("handler::update_auto_increment");
 
   /*
-    We must save the previous value to be able to restore it if the
-    row was not inserted
+    next_insert_id is a "cursor" into the reserved interval, it may go greater
+    than the interval, but not smaller.
   */
-  thd->prev_insert_id= thd->next_insert_id;
+  DBUG_ASSERT(next_insert_id >= auto_inc_interval_for_cur_row.minimum());
   auto_increment_field_not_null= table->auto_increment_field_not_null;
   table->auto_increment_field_not_null= FALSE; // to reset for next row
 
@@ -1620,131 +1638,138 @@ bool handler::update_auto_increment()
       thd->variables.sql_mode & MODE_NO_AUTO_VALUE_ON_ZERO)
   {
     /*
-      The user did specify a value for the auto_inc column, we don't generate
-      a new value, write it down.
-    */
-    auto_increment_column_changed=0;
-
-    /*
       Update next_insert_id if we had already generated a value in this
       statement (case of INSERT VALUES(null),(3763),(null):
       the last NULL needs to insert 3764, not the value of the first NULL plus
       1).
     */
-    if (thd->clear_next_insert_id && nr >= thd->next_insert_id)
-    {
-      if (variables->auto_increment_increment != 1)
-        nr= next_insert_id(nr, variables);
-      else
-        nr++;
-      thd->next_insert_id= nr;
-      DBUG_PRINT("info",("next_insert_id: %lu", (ulong) nr));
-    }
+    if ((next_insert_id > 0) && (nr >= next_insert_id))
+      set_next_insert_id(compute_next_insert_id(nr, variables));
+    insert_id_for_cur_row= 0; // didn't generate anything
     DBUG_RETURN(0);
   }
-  if (!(nr= thd->next_insert_id))
+
+  if ((nr= next_insert_id) >= auto_inc_interval_for_cur_row.maximum())
   {
-    ulonglong nb_desired_values= 1, nb_reserved_values;
-#ifdef TO_BE_ENABLED_SOON
-    /*
-      Reserved intervals will be stored in "THD::auto_inc_intervals".
-      handler::estimation_rows_to_insert will be the argument passed by
-      handler::ha_start_bulk_insert().
-    */
-    uint estimation_known= test(estimation_rows_to_insert > 0);
-    uint nb_already_reserved_intervals= thd->auto_inc_intervals.nb_elements();
-    /*
-      If an estimation was given to the engine:
-      - use it.
-      - if we already reserved numbers, it means the estimation was
-        not accurate, then we'll reserve 2*AUTO_INC_DEFAULT_NB_VALUES the 2nd
-        time, twice that the 3rd time etc.
-      If no estimation was given, use those increasing defaults from the
-      start, starting from AUTO_INC_DEFAULT_NB_VALUES.
-      Don't go beyond a max to not reserve "way too much" (because reservation
-      means potentially losing unused values).
-    */
-    if (nb_already_reserved_intervals == 0 && estimation_known)
-      nb_desired_values= estimation_rows_to_insert;
-    else /* go with the increasing defaults */
+    /* next_insert_id is beyond what is reserved, so we reserve more. */
+    const Discrete_interval *forced=
+      thd->auto_inc_intervals_forced.get_next();
+    if (forced != NULL)
+    {
+      nr= forced->minimum();
+      nb_reserved_values= forced->values();
+    }
+    else
     {
-      /* avoid overflow in formula, with this if() */
-      if (nb_already_reserved_intervals <= AUTO_INC_DEFAULT_NB_MAX_BITS)
+      /*
+        handler::estimation_rows_to_insert was set by
+        handler::ha_start_bulk_insert(); if 0 it means "unknown".
+      */
+      uint nb_already_reserved_intervals=
+        thd->auto_inc_intervals_in_cur_stmt_for_binlog.nb_elements();
+      ulonglong nb_desired_values;
+      /*
+        If an estimation was given to the engine:
+        - use it.
+        - if we already reserved numbers, it means the estimation was
+        not accurate, then we'll reserve 2*AUTO_INC_DEFAULT_NB_ROWS the 2nd
+        time, twice that the 3rd time etc.
+        If no estimation was given, use those increasing defaults from the
+        start, starting from AUTO_INC_DEFAULT_NB_ROWS.
+        Don't go beyond a max to not reserve "way too much" (because
+        reservation means potentially losing unused values).
+      */
+      if (nb_already_reserved_intervals == 0 &&
+          (estimation_rows_to_insert > 0))
+        nb_desired_values= estimation_rows_to_insert;
+      else /* go with the increasing defaults */
       {
-        nb_desired_values= AUTO_INC_DEFAULT_NB_VALUES * 
-          (1 << nb_already_reserved_intervals);
-        set_if_smaller(nb_desired_values, AUTO_INC_DEFAULT_NB_MAX);
+        /* avoid overflow in formula, with this if() */
+        if (nb_already_reserved_intervals <= AUTO_INC_DEFAULT_NB_MAX_BITS)
+        {
+          nb_desired_values= AUTO_INC_DEFAULT_NB_ROWS * 
+            (1 << nb_already_reserved_intervals);
+          set_if_smaller(nb_desired_values, AUTO_INC_DEFAULT_NB_MAX);
+        }
+        else
+          nb_desired_values= AUTO_INC_DEFAULT_NB_MAX;
       }
-      else
-        nb_desired_values= AUTO_INC_DEFAULT_NB_MAX;
+      /* This call ignores all its parameters but nr, currently */
+      get_auto_increment(variables->auto_increment_offset,
+                         variables->auto_increment_increment,
+                         nb_desired_values, &nr,
+                         &nb_reserved_values);
+      if (nr == ~(ulonglong) 0)
+        result= 1;                                // Mark failure
+      
+      /*
+        That rounding below should not be needed when all engines actually
+        respect offset and increment in get_auto_increment(). But they don't
+        so we still do it. Wonder if for the not-first-in-index we should do
+        it. Hope that this rounding didn't push us out of the interval; even
+        if it did we cannot do anything about it (calling the engine again
+        will not help as we inserted no row).
+      */
+      nr= compute_next_insert_id(nr-1, variables);
+    }
+    
+    if (table->s->next_number_key_offset == 0)
+    {
+      /* We must defer the appending until "nr" has been possibly truncated */
+      append= TRUE;
+    }
+    else
+    {
+      /*
+        For such auto_increment there is no notion of interval, just a
+        singleton. The interval is not even stored in
+        thd->auto_inc_interval_for_cur_row, so we are sure to call the engine
+        for next row.
+      */
+      DBUG_PRINT("info",("auto_increment: special not-first-in-index"));
     }
-#endif
-    /* This call ignores all its parameters but nr, currently */
-    get_auto_increment(variables->auto_increment_offset,
-                       variables->auto_increment_increment,
-                       nb_desired_values, &nr,
-                       &nb_reserved_values);
-    if (nr == ~(ulonglong) 0)
-      result= 1;                                // Mark failure
-
-    /*
-      That should not be needed when engines actually use offset and increment
-      above.
-    */
-    if (variables->auto_increment_increment != 1)
-      nr= next_insert_id(nr-1, variables);
-    /*
-      Update next row based on the found value. This way we don't have to
-      call the handler for every generated auto-increment value on a
-      multi-row statement
-    */
-    thd->next_insert_id= nr;
   }
 
   DBUG_PRINT("info",("auto_increment: %lu", (ulong) nr));
 
-  /* Mark that we should clear next_insert_id before next stmt */
-  thd->clear_next_insert_id= 1;
-
-  if (!table->next_number_field->store((longlong) nr, TRUE))
-    thd->insert_id((ulonglong) nr);
-  else
-    thd->insert_id(table->next_number_field->val_int());
-
-  /*
-    We can't set next_insert_id if the auto-increment key is not the
-    first key part, as there is no guarantee that the first parts will be in
-    sequence
-  */
-  if (!table->s->next_number_key_offset)
+  if (unlikely(table->next_number_field->store((longlong) nr, TRUE)))
   {
     /*
-      Set next insert id to point to next auto-increment value to be able to
-      handle multi-row statements
-      This works even if auto_increment_increment > 1
+      field refused this value (overflow) and truncated it, use the result of
+      the truncation (which is going to be inserted).
+      That will shift the left bound of the reserved interval, we don't
+      bother shifting the right bound (anyway any other value from this
+      interval will cause a duplicate key).
     */
-    thd->next_insert_id= next_insert_id(nr, variables);
+    nr= table->next_number_field->val_int();
+  }
+  if (append)
+  {
+    auto_inc_interval_for_cur_row.replace(nr, nb_reserved_values,
+                                          variables->auto_increment_increment);
+    /* Row-based replication does not need to store intervals in binlog */
+    if (!thd->current_stmt_binlog_row_based)
+      result= result ||
+        thd->auto_inc_intervals_in_cur_stmt_for_binlog.append(auto_inc_interval_for_cur_row.minimum(),
+                                                              auto_inc_interval_for_cur_row.values(),
+                                                              variables->auto_increment_increment);
   }
-  else
-    thd->next_insert_id= 0;
-
-  /* Mark that we generated a new value */
-  auto_increment_column_changed=1;
-  DBUG_RETURN(result);
-}
-
-/*
-  restore_auto_increment
 
-  In case of error on write, we restore the last used next_insert_id value
-  because the previous value was not used.
-*/
+  /*
+    Record this autogenerated value. If the caller then
+    succeeds to insert this value, it will call
+    record_first_successful_insert_id_in_cur_stmt()
+    which will set first_successful_insert_id_in_cur_stmt if it's not
+    already set.
+  */
+  insert_id_for_cur_row= nr;
+  /*
+    Set next insert id to point to next auto-increment value to be able to
+    handle multi-row statements.
+  */
+  set_next_insert_id(compute_next_insert_id(nr, variables));
 
-void handler::restore_auto_increment()
-{
-  THD *thd= table->in_use;
-  if (thd->next_insert_id)
-    thd->next_insert_id= thd->prev_insert_id;
+  DBUG_RETURN(result);
 }
 
 
@@ -1840,6 +1865,23 @@ void handler::get_auto_increment(ulonglong offset, ulonglong increment,
 }
 
 
+void handler::ha_release_auto_increment()
+{
+  release_auto_increment();
+  insert_id_for_cur_row= 0;
+  auto_inc_interval_for_cur_row.replace(0, 0, 0);
+  if (next_insert_id > 0)
+  {
+    next_insert_id= 0;
+    /*
+      this statement used forced auto_increment values if there were some,
+      wipe them away for other statements.
+    */
+    table->in_use->auto_inc_intervals_forced.empty();
+  }
+}
+
+
 void handler::print_keydup_error(uint key_nr, const char *msg)
 {
   /* Write the duplicated key in the error message */
@@ -3369,10 +3411,13 @@ namespace
 int handler::ha_external_lock(THD *thd, int lock_type)
 {
   DBUG_ENTER("handler::ha_external_lock");
-  int error;
-  if (unlikely(error= external_lock(thd, lock_type)))
-    DBUG_RETURN(error);
-  DBUG_RETURN(0);
+  /*
+    Whether this is lock or unlock, this should be true, and is to verify that
+    if get_auto_increment() was called (thus may have reserved intervals or
+    taken a table lock), ha_release_auto_increment() was too.
+  */
+  DBUG_ASSERT(next_insert_id == 0);
+  DBUG_RETURN(external_lock(thd, lock_type));
 }
 
 
diff --git a/sql/handler.h b/sql/handler.h
index 94f4519a2e7..d1ed6669037 100644
--- a/sql/handler.h
+++ b/sql/handler.h
@@ -906,16 +906,37 @@ public:
   uint ref_length;
   FT_INFO *ft_handler;
   enum {NONE=0, INDEX, RND} inited;
-  bool  auto_increment_column_changed;
   bool implicit_emptied;                /* Can be !=0 only if HEAP */
   const COND *pushed_cond;
+  /*
+    next_insert_id is the next value which should be inserted into the
+    auto_increment column: in a inserting-multi-row statement (like INSERT
+    SELECT), for the first row where the autoinc value is not specified by the
+    statement, get_auto_increment() called and asked to generate a value,
+    next_insert_id is set to the next value, then for all other rows
+    next_insert_id is used (and increased each time) without calling
+    get_auto_increment().
+  */
+  ulonglong next_insert_id;
+  /*
+    insert id for the current row (*autogenerated*; if not
+    autogenerated, it's 0).
+    At first successful insertion, this variable is stored into
+    THD::first_successful_insert_id_in_cur_stmt.
+  */
+  ulonglong insert_id_for_cur_row;
+  /*
+    Interval returned by get_auto_increment() and being consumed by the
+    inserter.
+  */
+  Discrete_interval auto_inc_interval_for_cur_row;
 
   handler(const handlerton *ht_arg, TABLE_SHARE *share_arg)
     :table_share(share_arg), estimation_rows_to_insert(0), ht(ht_arg),
     ref(0), key_used_on_scan(MAX_KEY), active_index(MAX_KEY),
     ref_length(sizeof(my_off_t)),
     ft_handler(0), inited(NONE), implicit_emptied(0),
-    pushed_cond(NULL)
+    pushed_cond(NULL), next_insert_id(0), insert_id_for_cur_row(0)
     {}
   virtual ~handler(void)
   {
@@ -1227,9 +1248,30 @@ public:
                                   ulonglong nb_desired_values,
                                   ulonglong *first_value,
                                   ulonglong *nb_reserved_values);
+private:
   virtual void release_auto_increment() { return; };
-  virtual void restore_auto_increment();
-
+public:
+  void ha_release_auto_increment();
+  void set_next_insert_id(ulonglong id)
+  {
+    DBUG_PRINT("info",("auto_increment: next value %lu", (ulong)id));
+    next_insert_id= id;
+  }
+  void restore_auto_increment(ulonglong prev_insert_id)
+  {
+    /*
+      Insertion of a row failed, re-use the lastly generated auto_increment
+      id, for the next row. This is achieved by resetting next_insert_id to
+      what it was before the failed insertion (that old value is provided by
+      the caller). If that value was 0, it was the first row of the INSERT;
+      then if insert_id_for_cur_row contains 0 it means no id was generated
+      for this first row, so no id was generated since the INSERT started, so
+      we should set next_insert_id to 0; if insert_id_for_cur_row is not 0, it
+      is the generated id of the first and failed row, so we use it.
+    */
+    next_insert_id= (prev_insert_id > 0) ? prev_insert_id :
+      insert_id_for_cur_row;
+  }
   /*
     Reset the auto-increment counter to the given value, i.e. the next row
     inserted will get the given value. This is called e.g. after TRUNCATE
diff --git a/sql/item_func.cc b/sql/item_func.cc
index 8139ba81777..b24f61d9011 100644
--- a/sql/item_func.cc
+++ b/sql/item_func.cc
@@ -3283,12 +3283,20 @@ longlong Item_func_last_insert_id::val_int()
   if (arg_count)
   {
     longlong value= args[0]->val_int();
-    thd->insert_id(value);
     null_value= args[0]->null_value;
-    return value;                       // Avoid side effect of insert_id()
+    /*
+      LAST_INSERT_ID(X) must affect the client's mysql_insert_id() as
+      documented in the manual. We don't want to touch
+      first_successful_insert_id_in_cur_stmt because it would make
+      LAST_INSERT_ID(X) take precedence over an generated auto_increment
+      value for this row.
+    */
+    thd->arg_of_last_insert_id_function= TRUE;
+    thd->first_successful_insert_id_in_prev_stmt= value;
+    return value;
   }
   thd->lex->uncacheable(UNCACHEABLE_SIDEEFFECT);
-  return thd->last_insert_id_used ? thd->current_insert_id : thd->insert_id();
+  return thd->read_first_successful_insert_id_in_prev_stmt();
 }
 
 /* This function is just used to test speed of different functions */
diff --git a/sql/log.cc b/sql/log.cc
index ec73400ea3c..c5f5743c51a 100644
--- a/sql/log.cc
+++ b/sql/log.cc
@@ -430,16 +430,23 @@ bool Log_to_csv_event_handler::
     table->field[6]->set_notnull();
   }
 
-  if (thd->last_insert_id_used)
+  if (thd->stmt_depends_on_first_successful_insert_id_in_prev_stmt)
   {
-    table->field[7]->store((longlong) thd->current_insert_id, TRUE);
+    table->field[7]->store((longlong)
+                           thd->first_successful_insert_id_in_prev_stmt_for_binlog, TRUE);
     table->field[7]->set_notnull();
   }
 
-  /* set value if we do an insert on autoincrement column */
-  if (thd->insert_id_used)
+  /*
+    Set value if we do an insert on autoincrement column. Note that for
+    some engines (those for which get_auto_increment() does not leave a
+    table lock until the statement ends), this is just the first value and
+    the next ones used may not be contiguous to it.
+  */
+  if (thd->auto_inc_intervals_in_cur_stmt_for_binlog.nb_elements() > 0)
   {
-    table->field[8]->store((longlong) thd->last_insert_id, TRUE);
+    table->field[8]->store((longlong)
+                           thd->auto_inc_intervals_in_cur_stmt_for_binlog.minimum(), TRUE);
     table->field[8]->set_notnull();
   }
 
@@ -729,7 +736,6 @@ bool LOGGER::slow_log_print(THD *thd, const char *query, uint query_length,
   Security_context *sctx= thd->security_ctx;
   uint message_buff_len= 0, user_host_len= 0;
   longlong query_time= 0, lock_time= 0;
-  longlong last_insert_id= 0, insert_id= 0;
 
   /*
     Print the message to the buffer if we have slow log enabled
@@ -764,13 +770,6 @@ bool LOGGER::slow_log_print(THD *thd, const char *query, uint query_length,
       lock_time= (longlong) (thd->time_after_lock - query_start_arg);
     }
 
-    if (thd->last_insert_id_used)
-      last_insert_id= (longlong) thd->current_insert_id;
-
-    /* set value if we do an insert on autoincrement column */
-    if (thd->insert_id_used)
-      insert_id= (longlong) thd->last_insert_id;
-
     if (!query)
     {
       is_command= TRUE;
@@ -1922,18 +1921,22 @@ bool MYSQL_QUERY_LOG::write(THD *thd, time_t current_time,
         tmp_errno= errno;
       strmov(db,thd->db);
     }
-    if (thd->last_insert_id_used)
+    if (thd->stmt_depends_on_first_successful_insert_id_in_prev_stmt)
     {
       end=strmov(end, ",last_insert_id=");
-      end=longlong10_to_str((longlong) thd->current_insert_id, end, -10);
+      end=longlong10_to_str((longlong)
+                            thd->first_successful_insert_id_in_prev_stmt_for_binlog,
+                            end, -10);
     }
     // Save value if we do an insert.
-    if (thd->insert_id_used)
+    if (thd->auto_inc_intervals_in_cur_stmt_for_binlog.nb_elements() > 0)
     {
       if (!(specialflag & SPECIAL_SHORT_LOG_FORMAT))
       {
         end=strmov(end,",insert_id=");
-        end=longlong10_to_str((longlong) thd->last_insert_id, end, -10);
+        end=longlong10_to_str((longlong)
+                              thd->auto_inc_intervals_in_cur_stmt_for_binlog.minimum(),
+                              end, -10);
       }
     }
 
@@ -3354,21 +3357,24 @@ bool MYSQL_BIN_LOG::write(Log_event *event_info)
     {
       if (!thd->current_stmt_binlog_row_based)
       {
-        if (thd->last_insert_id_used)
+        if (thd->stmt_depends_on_first_successful_insert_id_in_prev_stmt)
         {
           Intvar_log_event e(thd,(uchar) LAST_INSERT_ID_EVENT,
-                             thd->current_insert_id);
+                             thd->first_successful_insert_id_in_prev_stmt_for_binlog);
           if (e.write(file))
             goto err;
         }
-        if (thd->insert_id_used)
+        if (thd->auto_inc_intervals_in_cur_stmt_for_binlog.nb_elements() > 0)
         {
+          DBUG_PRINT("info",("number of auto_inc intervals: %lu",
+                             thd->auto_inc_intervals_in_cur_stmt_for_binlog.nb_elements()));
           /*
             If the auto_increment was second in a table's index (possible with
             MyISAM or BDB) (table->next_number_key_offset != 0), such event is
             in fact not necessary. We could avoid logging it.
           */
-          Intvar_log_event e(thd,(uchar) INSERT_ID_EVENT,thd->last_insert_id);
+          Intvar_log_event e(thd,(uchar) INSERT_ID_EVENT,
+                             thd->auto_inc_intervals_in_cur_stmt_for_binlog.minimum());
           if (e.write(file))
             goto err;
         }
diff --git a/sql/log_event.cc b/sql/log_event.cc
index 36805e0043d..2ecf0b1844f 100644
--- a/sql/log_event.cc
+++ b/sql/log_event.cc
@@ -1921,6 +1921,16 @@ end:
   thd->query_length= thd->db_length =0;
   VOID(pthread_mutex_unlock(&LOCK_thread_count));
   close_thread_tables(thd);      
+  /*
+    As a disk space optimization, future masters will not log an event for
+    LAST_INSERT_ID() if that function returned 0 (and thus they will be able
+    to replace the THD::stmt_depends_on_first_successful_insert_id_in_prev_stmt
+    variable by (THD->first_successful_insert_id_in_prev_stmt > 0) ; with the
+    resetting below we are ready to support that.
+  */
+  thd->first_successful_insert_id_in_prev_stmt_for_binlog= 0;
+  thd->first_successful_insert_id_in_prev_stmt= 0;
+  thd->stmt_depends_on_first_successful_insert_id_in_prev_stmt= 0;
   free_root(thd->mem_root,MYF(MY_KEEP_PREALLOC));
   /*
     If there was an error we stop. Otherwise we increment positions. Note that
@@ -3399,11 +3409,11 @@ int Intvar_log_event::exec_event(struct st_relay_log_info* rli)
 {
   switch (type) {
   case LAST_INSERT_ID_EVENT:
-    thd->last_insert_id_used = 1;
-    thd->last_insert_id = val;
+    thd->stmt_depends_on_first_successful_insert_id_in_prev_stmt= 1;
+    thd->first_successful_insert_id_in_prev_stmt= val;
     break;
   case INSERT_ID_EVENT:
-    thd->next_insert_id = val;
+    thd->force_one_auto_inc_interval(val);
     break;
   }
   rli->inc_event_relay_log_pos();
diff --git a/sql/set_var.cc b/sql/set_var.cc
index b0ecc7eccef..8616f0c5e60 100644
--- a/sql/set_var.cc
+++ b/sql/set_var.cc
@@ -2794,7 +2794,8 @@ byte *sys_var_timestamp::value_ptr(THD *thd, enum_var_type type,
 
 bool sys_var_last_insert_id::update(THD *thd, set_var *var)
 {
-  thd->insert_id(var->save_result.ulonglong_value);
+  thd->first_successful_insert_id_in_prev_stmt= 
+    var->save_result.ulonglong_value;
   return 0;
 }
 
@@ -2802,14 +2803,19 @@ bool sys_var_last_insert_id::update(THD *thd, set_var *var)
 byte *sys_var_last_insert_id::value_ptr(THD *thd, enum_var_type type,
 					LEX_STRING *base)
 {
-  thd->sys_var_tmp.long_value= (long) thd->insert_id();
-  return (byte*) &thd->last_insert_id;
+  /*
+    this tmp var makes it robust againt change of type of 
+    read_first_successful_insert_id_in_prev_stmt().
+  */
+  thd->sys_var_tmp.ulonglong_value= 
+    thd->read_first_successful_insert_id_in_prev_stmt();
+  return (byte*) &thd->sys_var_tmp.ulonglong_value;
 }
 
 
 bool sys_var_insert_id::update(THD *thd, set_var *var)
 {
-  thd->next_insert_id= var->save_result.ulonglong_value;
+  thd->force_one_auto_inc_interval(var->save_result.ulonglong_value);
   return 0;
 }
 
@@ -2817,7 +2823,9 @@ bool sys_var_insert_id::update(THD *thd, set_var *var)
 byte *sys_var_insert_id::value_ptr(THD *thd, enum_var_type type,
 				   LEX_STRING *base)
 {
-  return (byte*) &thd->current_insert_id;
+  thd->sys_var_tmp.ulonglong_value= 
+    thd->auto_inc_intervals_forced.minimum();
+  return (byte*) &thd->sys_var_tmp.ulonglong_value;
 }
 
 
diff --git a/sql/sql_class.cc b/sql/sql_class.cc
index c8c8ff16199..2d2f27256ba 100644
--- a/sql/sql_class.cc
+++ b/sql/sql_class.cc
@@ -208,8 +208,12 @@ THD::THD()
 #endif /*HAVE_ROW_BASED_REPLICATION*/
    global_read_lock(0), is_fatal_error(0),
    rand_used(0), time_zone_used(0),
-   last_insert_id_used(0), insert_id_used(0), clear_next_insert_id(0),
+   arg_of_last_insert_id_function(FALSE),
+   first_successful_insert_id_in_prev_stmt(0),
+   first_successful_insert_id_in_prev_stmt_for_binlog(0),
+   first_successful_insert_id_in_cur_stmt(0),
    in_lock_tables(0), bootstrap(0), derived_tables_processing(FALSE),
+   stmt_depends_on_first_successful_insert_id_in_prev_stmt(FALSE),
    spcont(NULL)
 {
   stmt_arena= this;
@@ -224,7 +228,6 @@ THD::THD()
   killed= NOT_KILLED;
   db_length= col_access=0;
   query_error= tmp_table_used= 0;
-  next_insert_id=last_insert_id=0;
   hash_clear(&handler_tables_hash);
   tmp_table=0;
   used_tables=0;
@@ -628,11 +631,26 @@ bool THD::store_globals()
 
 void THD::cleanup_after_query()
 {
-  if (clear_next_insert_id)
+  /*
+    If in stored function or trigger, where statement-based binlogging logs
+    only the caller, the insert_id/last_insert_id stored in binlog must
+    describe their first values inside the routine or caller (the values when
+    they were first set). Otherwise (e.g. stored procedure) it must describe
+    their values for the current substatement.
+  */
+  if (!prelocked_mode)
+  {
+    stmt_depends_on_first_successful_insert_id_in_prev_stmt= 0;
+    auto_inc_intervals_in_cur_stmt_for_binlog.empty();
+  }
+  if (first_successful_insert_id_in_cur_stmt > 0)
   {
-    clear_next_insert_id= 0;
-    next_insert_id= 0;
+    /* set what LAST_INSERT_ID() will return */
+    first_successful_insert_id_in_prev_stmt= 
+      first_successful_insert_id_in_cur_stmt;
+    first_successful_insert_id_in_cur_stmt= 0;
   }
+  arg_of_last_insert_id_function= 0;
   /* Free Items that were created during this execution */
   free_items();
   /* Reset where. */
@@ -2139,18 +2157,16 @@ void THD::reset_sub_statement_state(Sub_statement_state *backup,
   backup->in_sub_stmt=     in_sub_stmt;
   backup->no_send_ok=      net.no_send_ok;
   backup->enable_slow_log= enable_slow_log;
-  backup->last_insert_id=  last_insert_id;
-  backup->next_insert_id=  next_insert_id;
-  backup->current_insert_id=  current_insert_id;
-  backup->insert_id_used=  insert_id_used;
-  backup->last_insert_id_used=  last_insert_id_used;
-  backup->clear_next_insert_id= clear_next_insert_id;
   backup->limit_found_rows= limit_found_rows;
   backup->examined_row_count= examined_row_count;
   backup->sent_row_count=   sent_row_count;
   backup->cuted_fields=     cuted_fields;
   backup->client_capabilities= client_capabilities;
   backup->savepoints= transaction.savepoints;
+  backup->first_successful_insert_id_in_prev_stmt= 
+    first_successful_insert_id_in_prev_stmt;
+  backup->first_successful_insert_id_in_cur_stmt= 
+    first_successful_insert_id_in_cur_stmt;
 
   if ((!lex->requires_prelocking() || is_update_query(lex->sql_command)) &&
       !current_stmt_binlog_row_based)
@@ -2160,12 +2176,11 @@ void THD::reset_sub_statement_state(Sub_statement_state *backup,
   /* Disable result sets */
   client_capabilities &= ~CLIENT_MULTI_RESULTS;
   in_sub_stmt|= new_state;
-  next_insert_id= 0;
-  insert_id_used= 0;
   examined_row_count= 0;
   sent_row_count= 0;
   cuted_fields= 0;
   transaction.savepoints= 0;
+  first_successful_insert_id_in_cur_stmt= 0;
 
   /* Surpress OK packets in case if we will execute statements */
   net.no_send_ok= TRUE;
@@ -2193,12 +2208,10 @@ void THD::restore_sub_statement_state(Sub_statement_state *backup)
   in_sub_stmt=      backup->in_sub_stmt;
   net.no_send_ok=   backup->no_send_ok;
   enable_slow_log=  backup->enable_slow_log;
-  last_insert_id=   backup->last_insert_id;
-  next_insert_id=   backup->next_insert_id;
-  current_insert_id= backup->current_insert_id;
-  insert_id_used=   backup->insert_id_used;
-  last_insert_id_used= backup->last_insert_id_used;
-  clear_next_insert_id= backup->clear_next_insert_id;
+  first_successful_insert_id_in_prev_stmt= 
+    backup->first_successful_insert_id_in_prev_stmt;
+  first_successful_insert_id_in_cur_stmt= 
+    backup->first_successful_insert_id_in_cur_stmt;
   limit_found_rows= backup->limit_found_rows;
   sent_row_count=   backup->sent_row_count;
   client_capabilities= backup->client_capabilities;
@@ -2779,4 +2792,26 @@ int THD::binlog_query(THD::enum_binlog_query_type qtype,
   DBUG_RETURN(0);
 }
 
+bool Discrete_intervals_list::append(ulonglong start, ulonglong val,
+                                 ulonglong incr)
+{
+  DBUG_ENTER("Discrete_intervals_list::append");
+  /* first, see if this can be merged with previous */
+  if ((head == NULL) || tail->merge_if_contiguous(start, val, incr))
+  {
+    /* it cannot, so need to add a new interval */
+    Discrete_interval *new_interval= new Discrete_interval(start, val, incr);
+    if (unlikely(new_interval == NULL)) // out of memory
+      DBUG_RETURN(1);
+    DBUG_PRINT("info",("adding new auto_increment interval"));
+    if (head == NULL)
+      head= current= new_interval;
+    else
+      tail->next= new_interval;
+    tail= new_interval;
+    elements++;
+  }
+  DBUG_RETURN(0);
+}
+
 #endif /* !defined(MYSQL_CLIENT) */
diff --git a/sql/sql_class.h b/sql/sql_class.h
index 5222e75f309..ee18ddec225 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -770,12 +770,14 @@ class Sub_statement_state
 {
 public:
   ulonglong options;
-  ulonglong last_insert_id, next_insert_id, current_insert_id;
+  ulonglong first_successful_insert_id_in_prev_stmt;
+  ulonglong first_successful_insert_id_in_cur_stmt, insert_id_for_cur_row;
+  Discrete_interval auto_inc_interval_for_cur_row;
   ulonglong limit_found_rows;
   ha_rows    cuted_fields, sent_row_count, examined_row_count;
   ulong client_capabilities;
   uint in_sub_stmt;
-  bool enable_slow_log, insert_id_used, clear_next_insert_id;
+  bool enable_slow_log;
   bool last_insert_id_used;
   my_bool no_send_ok;
   SAVEPOINT *savepoints;
@@ -1071,24 +1073,136 @@ public:
     Note: in the parser, stmt_arena == thd, even for PS/SP.
   */
   Query_arena *stmt_arena;
+  /* Tells if LAST_INSERT_ID(#) was called for the current statement */
+  bool arg_of_last_insert_id_function;
   /*
-    next_insert_id is set on SET INSERT_ID= #. This is used as the next
-    generated auto_increment value in handler.cc
+    ALL OVER THIS FILE, "insert_id" means "*automatically generated* value for
+    insertion into an auto_increment column".
   */
-  ulonglong  next_insert_id;
-  /* Remember last next_insert_id to reset it if something went wrong */
-  ulonglong  prev_insert_id;
   /*
-    The insert_id used for the last statement or set by SET LAST_INSERT_ID=#
-    or SELECT LAST_INSERT_ID(#).  Used for binary log and returned by
-    LAST_INSERT_ID()
+    This is the first autogenerated insert id which was *successfully*
+    inserted by the previous statement (exactly, if the previous statement
+    didn't successfully insert an autogenerated insert id, then it's the one
+    of the statement before, etc).
+    It can also be set by SET LAST_INSERT_ID=# or SELECT LAST_INSERT_ID(#).
+    It is returned by LAST_INSERT_ID().
   */
-  ulonglong  last_insert_id;
+  ulonglong  first_successful_insert_id_in_prev_stmt;
   /*
-    Set to the first value that LAST_INSERT_ID() returned for the last
-    statement.  When this is set, last_insert_id_used is set to true.
+    Variant of the above, used for storing in statement-based binlog. The
+    difference is that the one above can change as the execution of a stored
+    function progresses, while the one below is set once and then does not
+    change (which is the value which statement-based binlog needs).
   */
-  ulonglong  current_insert_id;
+  ulonglong  first_successful_insert_id_in_prev_stmt_for_binlog;
+  /*
+    This is the first autogenerated insert id which was *successfully*
+    inserted by the current statement. It is maintained only to set
+    first_successful_insert_id_in_prev_stmt when statement ends.
+  */
+  ulonglong  first_successful_insert_id_in_cur_stmt;
+  /*
+    We follow this logic:
+    - when stmt starts, first_successful_insert_id_in_prev_stmt contains the
+    first insert id successfully inserted by the previous stmt.
+    - as stmt makes progress, handler::insert_id_for_cur_row changes; every
+    time get_auto_increment() is called, auto_inc_intervals_for_binlog is
+    augmented with the reserved interval (if statement-based binlogging).
+    - at first successful insertion of an autogenerated value,
+    first_successful_insert_id_in_cur_stmt is set to
+    handler::insert_id_for_cur_row.
+    - when stmt goes to binlog, auto_inc_intervals_for_binlog is
+    binlogged if non-empty.
+    - when stmt ends, first_successful_insert_id_in_prev_stmt is set to
+    first_successful_insert_id_in_cur_stmt.
+  */
+  /*
+    stmt_depends_on_first_successful_insert_id_in_prev_stmt is set when
+    LAST_INSERT_ID() is used by a statement.
+    If it is set, first_successful_insert_id_in_prev_stmt_for_binlog will be
+    stored in the statement-based binlog.
+    This variable is CUMULATIVE along the execution of a stored function or
+    trigger: if one substatement sets it to 1 it will stay 1 until the
+    function/trigger ends, thus making sure that
+    first_successful_insert_id_in_prev_stmt_for_binlog does not change anymore
+    and is propagated to the caller for binlogging.
+  */
+  bool       stmt_depends_on_first_successful_insert_id_in_prev_stmt;
+  /*
+    List of auto_increment intervals reserved by the thread so far, for
+    storage in the statement-based binlog.
+    Note that its minimum is not first_successful_insert_id_in_cur_stmt:
+    assuming a table with an autoinc column, and this happens:
+    INSERT INTO ... VALUES(3);
+    SET INSERT_ID=3; INSERT IGNORE ... VALUES (NULL);
+    then the latter INSERT will insert no rows
+    (first_successful_insert_id_in_cur_stmt == 0), but storing "INSERT_ID=3"
+    in the binlog is still needed; the list's minimum will contain 3.
+  */
+  Discrete_intervals_list auto_inc_intervals_in_cur_stmt_for_binlog;
+  /* Used by replication and SET INSERT_ID */
+  Discrete_intervals_list auto_inc_intervals_forced;
+  /*
+    There is BUG#19630 where statement-based replication of stored
+    functions/triggers with two auto_increment columns breaks.
+    We however ensure that it works when there is 0 or 1 auto_increment
+    column; our rules are
+    a) on master, while executing a top statement involving substatements,
+    first top- or sub- statement to generate auto_increment values wins the
+    exclusive right to write them to binlog (so the losers won't write their
+    values to binlog).
+    b) on slave, while replicating a top statement involving substatements,
+    first top- or sub- statement to need to read auto_increment values from
+    the master's binlog wins the exclusive right to read them (so the losers
+    won't read their values from binlog but instead generate on their own).
+    a) implies that we mustn't backup/restore
+    auto_inc_intervals_in_cur_stmt_for_binlog.
+    b) implies that we mustn't backup/restore auto_inc_intervals_forced.
+
+    If there are more than 1 auto_increment columns, then intervals for
+    different columns may mix into the
+    auto_inc_intervals_in_cur_stmt_for_binlog list, which is logically wrong,
+    but there is no point in preventing this mixing by preventing intervals
+    from the secondly inserted column to come into the list, as such
+    prevention would be wrong too.
+    What will happen in the case of
+    INSERT INTO t1 (auto_inc) VALUES(NULL);
+    where t1 has a trigger which inserts into an auto_inc column of t2, is
+    that in binlog we'll store the interval of t1 and the interval of t2 (when
+    we store intervals, soon), then in slave, t1 will use both intervals, t2
+    will use none; if t1 inserts the same number of rows as on master,
+    normally the 2nd interval will not be used by t1, which is fine. t2's
+    values will be wrong if t2's internal auto_increment counter is different
+    from what it was on master (which is likely). In 5.1, in mixed binlogging
+    mode, row-based binlogging is used for such cases where two
+    auto_increment columns are inserted.
+  */
+  inline void record_first_successful_insert_id_in_cur_stmt(ulonglong id)
+  {
+    if (first_successful_insert_id_in_cur_stmt == 0)
+      first_successful_insert_id_in_cur_stmt= id;
+  }
+  inline ulonglong read_first_successful_insert_id_in_prev_stmt(void)
+  {
+    if (!stmt_depends_on_first_successful_insert_id_in_prev_stmt)
+    {
+      /* It's the first time we read it */
+      first_successful_insert_id_in_prev_stmt_for_binlog=
+        first_successful_insert_id_in_prev_stmt;
+      stmt_depends_on_first_successful_insert_id_in_prev_stmt= 1;
+    }
+    return first_successful_insert_id_in_prev_stmt;
+  }
+  /*
+    Used by Intvar_log_event::exec_event() and by "SET INSERT_ID=#"
+    (mysqlbinlog). We'll soon add a variant which can take many intervals in
+    argument.
+  */
+  inline void force_one_auto_inc_interval(ulonglong next_id)
+  {
+    auto_inc_intervals_forced.append(next_id, ULONGLONG_MAX, 0);
+  }
+
   ulonglong  limit_found_rows;
   ulonglong  options;           /* Bitmap of states */
   longlong   row_count_func;	/* For the ROW_COUNT() function */
@@ -1157,7 +1271,6 @@ public:
   bool       last_cuted_field;
   bool	     no_errors, password, is_fatal_error;
   bool	     query_start_used, rand_used, time_zone_used;
-  bool	     last_insert_id_used,insert_id_used, clear_next_insert_id;
   bool	     in_lock_tables;
   bool       query_error, bootstrap, cleanup_done;
   bool	     tmp_table_used;
@@ -1185,9 +1298,10 @@ public:
   /* Used by the sys_var class to store temporary values */
   union
   {
-    my_bool my_bool_value;
-    long    long_value;
-    ulong   ulong_value;
+    my_bool   my_bool_value;
+    long      long_value;
+    ulong     ulong_value;
+    ulonglong ulonglong_value;
   } sys_var_tmp;
   
   struct {
@@ -1288,20 +1402,6 @@ public:
   inline void	end_time()    { time(&start_time); }
   inline void	set_time(time_t t) { time_after_lock=start_time=user_time=t; }
   inline void	lock_time()   { time(&time_after_lock); }
-  inline void	insert_id(ulonglong id_arg)
-  {
-    last_insert_id= id_arg;
-    insert_id_used=1;
-  }
-  inline ulonglong insert_id(void)
-  {
-    if (!last_insert_id_used)
-    {
-      last_insert_id_used=1;
-      current_insert_id=last_insert_id;
-    }
-    return last_insert_id;
-  }
   inline ulonglong found_rows(void)
   {
     return limit_found_rows;
@@ -1589,7 +1689,7 @@ class select_insert :public select_result_interceptor {
   TABLE_LIST *table_list;
   TABLE *table;
   List<Item> *fields;
-  ulonglong last_insert_id;
+  ulonglong autoinc_value_of_last_inserted_row; // autogenerated or not
   COPY_INFO info;
   bool insert_into_view;
 
diff --git a/sql/sql_insert.cc b/sql/sql_insert.cc
index 7b017ad7317..c279148ab5a 100644
--- a/sql/sql_insert.cc
+++ b/sql/sql_insert.cc
@@ -411,7 +411,6 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
   table->next_number_field=table->found_next_number_field;
 
   error=0;
-  id=0;
   thd->proc_info="update";
   if (duplic != DUP_ERROR || ignore)
     table->file->extra(HA_EXTRA_IGNORE_DUP_KEY);
@@ -517,16 +516,6 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
     else
 #endif
       error=write_record(thd, table ,&info);
-    /*
-      If auto_increment values are used, save the first one
-       for LAST_INSERT_ID() and for the update log.
-       We can't use insert_id() as we don't want to touch the
-       last_insert_id_used flag.
-    */
-    if (! id && thd->insert_id_used)
-    {						// Get auto increment value
-      id= thd->last_insert_id;
-    }
     if (error)
       break;
     thd->row_count++;
@@ -534,6 +523,7 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
 
   free_underlaid_joins(thd, &thd->lex->select_lex);
   joins_freed= TRUE;
+  table->file->ha_release_auto_increment();
 
   /*
     Now all rows are inserted.  Time to update logs and sends response to
@@ -544,7 +534,6 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
   {
     if (!error)
     {
-      id=0;					// No auto_increment id
       info.copied=values_list.elements;
       end_delayed_insert(thd);
     }
@@ -558,11 +547,6 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
       table->file->print_error(my_errno,MYF(0));
       error=1;
     }
-    if (id && values_list.elements != 1)
-      thd->insert_id(id);			// For update log
-    else if (table->next_number_field && info.copied)
-      id=table->next_number_field->val_int();	// Return auto_increment value
-
     transactional_table= table->file->has_transactions();
 
     if ((changed= (info.copied || info.deleted || info.updated)))
@@ -611,18 +595,27 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
     }
   }
   thd->proc_info="end";
+  /*
+    We'll report to the client this id:
+    - if the table contains an autoincrement column and we successfully
+    inserted an autogenerated value, the autogenerated value.
+    - if the table contains no autoincrement column and LAST_INSERT_ID(X) was
+    called, X.
+    - if the table contains an autoincrement column, and some rows were
+    inserted, the id of the last "inserted" row (if IGNORE, that value may not
+    have been really inserted but ignored).
+  */
+  id= (thd->first_successful_insert_id_in_cur_stmt > 0) ?
+    thd->first_successful_insert_id_in_cur_stmt :
+    (thd->arg_of_last_insert_id_function ?
+     thd->first_successful_insert_id_in_prev_stmt :
+     ((table->next_number_field && info.copied) ?
+     table->next_number_field->val_int() : 0));
   table->next_number_field=0;
   thd->count_cuted_fields= CHECK_FIELD_IGNORE;
-  thd->next_insert_id=0;			// Reset this if wrongly used
   if (duplic != DUP_ERROR || ignore)
     table->file->extra(HA_EXTRA_NO_IGNORE_DUP_KEY);
 
-  /* Reset value of LAST_INSERT_ID if no rows where inserted */
-  if (!info.copied && thd->insert_id_used)
-  {
-    thd->insert_id(0);
-    id=0;
-  }
   if (error)
     goto abort;
   if (values_list.elements == 1 && (!(thd->options & OPTION_WARNINGS) ||
@@ -644,8 +637,6 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
     thd->row_count_func= info.copied+info.deleted+info.updated;
     ::send_ok(thd, (ulong) thd->row_count_func, id, buff);
   }
-  if (table != NULL)
-    table->file->release_auto_increment();
   thd->abort_on_warning= 0;
   DBUG_RETURN(FALSE);
 
@@ -655,7 +646,7 @@ abort:
     end_delayed_insert(thd);
 #endif
   if (table != NULL)
-    table->file->release_auto_increment();
+    table->file->ha_release_auto_increment();
   if (!joins_freed)
     free_underlaid_joins(thd, &thd->lex->select_lex);
   thd->abort_on_warning= 0;
@@ -964,6 +955,8 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
   int error, trg_error= 0;
   char *key=0;
   MY_BITMAP *save_read_set, *save_write_set;
+  ulonglong prev_insert_id= table->file->next_insert_id;
+  ulonglong insert_id_for_cur_row= 0;
   DBUG_ENTER("write_record");
 
   info->records++;
@@ -976,9 +969,19 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
     while ((error=table->file->ha_write_row(table->record[0])))
     {
       uint key_nr;
+      /*
+        If we do more than one iteration of this loop, from the second one the
+        row will have an explicit value in the autoinc field, which was set at
+        the first call of handler::update_auto_increment(). So we must save
+        the autogenerated value to avoid thd->insert_id_for_cur_row to become
+        0.
+      */
+      if (table->file->insert_id_for_cur_row > 0)
+        insert_id_for_cur_row= table->file->insert_id_for_cur_row;
+      else
+        table->file->insert_id_for_cur_row= insert_id_for_cur_row;
       if (error != HA_WRITE_SKIP)
 	goto err;
-      table->file->restore_auto_increment(); // it's too early here! BUG#20188
       if ((int) (key_nr = table->file->get_dup_key(error)) < 0)
       {
 	error=HA_WRITE_SKIP;			/* Database can't find key */
@@ -994,7 +997,7 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
       if (info->handle_duplicates == DUP_REPLACE &&
           table->next_number_field &&
           key_nr == table->s->next_number_index &&
-	  table->file->auto_increment_column_changed)
+	  (insert_id_for_cur_row > 0))
 	goto err;
       if (table->file->ha_table_flags() & HA_DUPLICATE_POS)
       {
@@ -1053,12 +1056,6 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
         if (res == VIEW_CHECK_ERROR)
           goto before_trg_err;
 
-        if (thd->clear_next_insert_id)
-        {
-          /* Reset auto-increment cacheing if we do an update */
-          thd->clear_next_insert_id= 0;
-          thd->next_insert_id= 0;
-        }
         if ((error=table->file->ha_update_row(table->record[1],
                                               table->record[0])))
 	{
@@ -1067,7 +1064,14 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
           goto err;
 	}
         info->updated++;
-
+        /*
+          If ON DUP KEY UPDATE updates a row instead of inserting one, and
+          there is an auto_increment column, then SELECT LAST_INSERT_ID()
+          returns the id of the updated row:
+        */
+        if (table->next_number_field)
+          thd->record_first_successful_insert_id_in_cur_stmt(table->next_number_field->val_int());
+        
         trg_error= (table->triggers &&
                     table->triggers->process_triggers(thd, TRG_EVENT_UPDATE,
                                                       TRG_ACTION_AFTER, TRUE));
@@ -1096,16 +1100,11 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
              table->timestamp_field_type == TIMESTAMP_AUTO_SET_ON_BOTH) &&
             (!table->triggers || !table->triggers->has_delete_triggers()))
         {
-          if (thd->clear_next_insert_id)
-          {
-            /* Reset auto-increment cacheing if we do an update */
-            thd->clear_next_insert_id= 0;
-            thd->next_insert_id= 0;
-          }
           if ((error=table->file->ha_update_row(table->record[1],
 					        table->record[0])))
             goto err;
           info->deleted++;
+          thd->record_first_successful_insert_id_in_cur_stmt(table->file->insert_id_for_cur_row);
           /*
             Since we pretend that we have done insert we should call
             its after triggers.
@@ -1134,6 +1133,7 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
         }
       }
     }
+    thd->record_first_successful_insert_id_in_cur_stmt(table->file->insert_id_for_cur_row);
     /*
       Restore column maps if they where replaced during an duplicate key
       problem.
@@ -1147,12 +1147,13 @@ int write_record(THD *thd, TABLE *table,COPY_INFO *info)
     if (!info->ignore ||
 	(error != HA_ERR_FOUND_DUPP_KEY && error != HA_ERR_FOUND_DUPP_UNIQUE))
       goto err;
-    table->file->restore_auto_increment();
+    table->file->restore_auto_increment(prev_insert_id);
     goto ok_or_after_trg_err;
   }
 
 after_trg_n_copied_inc:
   info->copied++;
+  thd->record_first_successful_insert_id_in_cur_stmt(table->file->insert_id_for_cur_row);
   trg_error= (table->triggers &&
               table->triggers->process_triggers(thd, TRG_EVENT_INSERT,
                                                 TRG_ACTION_AFTER, TRUE));
@@ -1172,6 +1173,7 @@ err:
   table->file->print_error(error,MYF(0));
 
 before_trg_err:
+  table->file->restore_auto_increment(prev_insert_id);
   if (key)
     my_safe_afree(key, table->s->max_unique_length, MAX_KEY_LENGTH);
   table->column_bitmaps_set(save_read_set, save_write_set);
@@ -1234,8 +1236,9 @@ public:
   char *record;
   enum_duplicates dup;
   time_t start_time;
-  bool query_start_used,last_insert_id_used,insert_id_used, ignore, log_query;
-  ulonglong last_insert_id;
+  bool query_start_used, ignore, log_query;
+  bool stmt_depends_on_first_successful_insert_id_in_prev_stmt;
+  ulonglong first_successful_insert_id_in_prev_stmt;
   timestamp_auto_set_type timestamp_field_type;
 
   delayed_row(enum_duplicates dup_arg, bool ignore_arg, bool log_query_arg)
@@ -1639,9 +1642,16 @@ static int write_delayed(THD *thd,TABLE *table,enum_duplicates duplic,
   di->set_query(query, query_length);
   row->start_time=		thd->start_time;
   row->query_start_used=	thd->query_start_used;
-  row->last_insert_id_used=	thd->last_insert_id_used;
-  row->insert_id_used=		thd->insert_id_used;
-  row->last_insert_id=		thd->last_insert_id;
+  /*
+    those are for the binlog: LAST_INSERT_ID() has been evaluated at this
+    time, so record does not need it, but statement-based binlogging of the
+    INSERT will need when the row is actually inserted.
+    As for SET INSERT_ID, DELAYED does not honour it (BUG#20830).
+  */
+  row->stmt_depends_on_first_successful_insert_id_in_prev_stmt=
+    thd->stmt_depends_on_first_successful_insert_id_in_prev_stmt;
+  row->first_successful_insert_id_in_prev_stmt=
+    thd->first_successful_insert_id_in_prev_stmt;
   row->timestamp_field_type=    table->timestamp_field_type;
 
   di->rows.push_back(row);
@@ -1895,6 +1905,7 @@ pthread_handler_t handle_delayed_insert(void *arg)
       MYSQL_LOCK *lock=thd->lock;
       thd->lock=0;
       pthread_mutex_unlock(&di->mutex);
+      di->table->file->ha_release_auto_increment();
       mysql_unlock_tables(thd, lock);
       di->group_count=0;
       pthread_mutex_lock(&di->mutex);
@@ -2007,13 +2018,6 @@ bool delayed_insert::handle_inserts(void)
     table->file->extra(HA_EXTRA_WRITE_CACHE);
   pthread_mutex_lock(&mutex);
 
-  /* Reset auto-increment cacheing */
-  if (thd.clear_next_insert_id)
-  {
-    thd.next_insert_id= 0;
-    thd.clear_next_insert_id= 0;
-  }
-
   while ((row=rows.get()))
   {
     stacked_inserts--;
@@ -2022,9 +2026,12 @@ bool delayed_insert::handle_inserts(void)
 
     thd.start_time=row->start_time;
     thd.query_start_used=row->query_start_used;
-    thd.last_insert_id=row->last_insert_id;
-    thd.last_insert_id_used=row->last_insert_id_used;
-    thd.insert_id_used=row->insert_id_used;
+    /* for the binlog, forget auto_increment ids generated by previous rows */
+    thd.auto_inc_intervals_in_cur_stmt_for_binlog.empty();
+    thd.first_successful_insert_id_in_prev_stmt= 
+      row->first_successful_insert_id_in_prev_stmt;
+    thd.stmt_depends_on_first_successful_insert_id_in_prev_stmt= 
+      row->stmt_depends_on_first_successful_insert_id_in_prev_stmt;
     table->timestamp_field_type= row->timestamp_field_type;
 
     info.ignore= row->ignore;
@@ -2187,7 +2194,7 @@ select_insert::select_insert(TABLE_LIST *table_list_par, TABLE *table_par,
                              enum_duplicates duplic,
                              bool ignore_check_option_errors)
   :table_list(table_list_par), table(table_par), fields(fields_par),
-   last_insert_id(0),
+   autoinc_value_of_last_inserted_row(0),
    insert_into_view(table_list_par && table_list_par->view != 0)
 {
   bzero((char*) &info,sizeof(info));
@@ -2396,15 +2403,20 @@ bool select_insert::send_data(List<Item> &values)
     if (table->next_number_field)
     {
       /*
+        If no value has been autogenerated so far, we need to remember the
+        value we just saw, we may need to send it to client in the end.
+      */
+      if (thd->first_successful_insert_id_in_cur_stmt == 0) // optimization
+        autoinc_value_of_last_inserted_row= 
+          table->next_number_field->val_int();
+      /*
         Clear auto-increment field for the next record, if triggers are used
         we will clear it twice, but this should be cheap.
       */
       table->next_number_field->reset();
-      if (!last_insert_id && thd->insert_id_used)
-        last_insert_id= thd->insert_id();
     }
   }
-  table->file->release_auto_increment();
+  table->file->ha_release_auto_increment();
   DBUG_RETURN(error);
 }
 
@@ -2466,8 +2478,6 @@ void select_insert::send_error(uint errcode,const char *err)
   {
     if (!table->file->has_transactions())
     {
-      if (last_insert_id)
-        thd->insert_id(last_insert_id);		// For binary log
       if (mysql_bin_log.is_open())
       {
         thd->binlog_query(THD::ROW_QUERY_TYPE, thd->query, thd->query_length,
@@ -2487,6 +2497,7 @@ void select_insert::send_error(uint errcode,const char *err)
 bool select_insert::send_eof()
 {
   int error,error2;
+  ulonglong id;
   DBUG_ENTER("select_insert::send_eof");
 
   error= (!thd->prelocked_mode) ? table->file->ha_end_bulk_insert():0;
@@ -2512,8 +2523,6 @@ bool select_insert::send_eof()
       thd->options|= OPTION_STATUS_NO_TRANS_UPDATE;
    }
 
-  if (last_insert_id)
-    thd->insert_id(last_insert_id);		// For binary log
   /*
     Write to binlog before commiting transaction.  No statement will
     be written by the binlog_query() below in RBR mode.  All the
@@ -2543,7 +2552,13 @@ bool select_insert::send_eof()
     sprintf(buff, ER(ER_INSERT_INFO), (ulong) info.records,
 	    (ulong) (info.deleted+info.updated), (ulong) thd->cuted_fields);
   thd->row_count_func= info.copied+info.deleted+info.updated;
-  ::send_ok(thd, (ulong) thd->row_count_func, last_insert_id, buff);
+
+  id= (thd->first_successful_insert_id_in_cur_stmt > 0) ?
+    thd->first_successful_insert_id_in_cur_stmt :
+    (thd->arg_of_last_insert_id_function ?
+     thd->first_successful_insert_id_in_prev_stmt :
+     (info.copied ? autoinc_value_of_last_inserted_row : 0));
+  ::send_ok(thd, (ulong) thd->row_count_func, id, buff);
   DBUG_RETURN(0);
 }
 
diff --git a/sql/sql_load.cc b/sql/sql_load.cc
index f8debbedc62..215ea303f0a 100644
--- a/sql/sql_load.cc
+++ b/sql/sql_load.cc
@@ -497,13 +497,12 @@ bool mysql_load(THD *thd,sql_exchange *ex,TABLE_LIST *table_list,
     error=ha_autocommit_or_rollback(thd,error);
 
 err:
+  table->file->ha_release_auto_increment();
   if (thd->lock)
   {
     mysql_unlock_tables(thd, thd->lock);
     thd->lock=0;
   }
-  if (table != NULL)
-    table->file->release_auto_increment();
   thd->abort_on_warning= 0;
   DBUG_RETURN(error);
 }
@@ -639,14 +638,6 @@ read_fixed_length(THD *thd, COPY_INFO &info, TABLE_LIST *table_list,
     thd->no_trans_update= no_trans_update;
    
     /*
-      If auto_increment values are used, save the first one
-       for LAST_INSERT_ID() and for the binary/update log.
-       We can't use insert_id() as we don't want to touch the
-       last_insert_id_used flag.
-    */
-    if (!id && thd->insert_id_used)
-      id= thd->last_insert_id;
-    /*
       We don't need to reset auto-increment field since we are restoring
       its default value at the beginning of each loop iteration.
     */
@@ -662,8 +653,6 @@ read_fixed_length(THD *thd, COPY_INFO &info, TABLE_LIST *table_list,
     thd->row_count++;
 continue_loop:;
   }
-  if (id && !read_info.error)
-    thd->insert_id(id);			// For binary/update log
   DBUG_RETURN(test(read_info.error));
 }
 
@@ -807,14 +796,6 @@ read_sep_field(THD *thd, COPY_INFO &info, TABLE_LIST *table_list,
     if (write_record(thd, table, &info))
       DBUG_RETURN(1);
     /*
-      If auto_increment values are used, save the first one
-       for LAST_INSERT_ID() and for the binary/update log.
-       We can't use insert_id() as we don't want to touch the
-       last_insert_id_used flag.
-    */
-    if (!id && thd->insert_id_used)
-      id= thd->last_insert_id;
-    /*
       We don't need to reset auto-increment field since we are restoring
       its default value at the beginning of each loop iteration.
     */
@@ -833,8 +814,6 @@ read_sep_field(THD *thd, COPY_INFO &info, TABLE_LIST *table_list,
     thd->row_count++;
 continue_loop:;
   }
-  if (id && !read_info.error)
-    thd->insert_id(id);			// For binary/update log
   DBUG_RETURN(test(read_info.error));
 }
 
diff --git a/sql/sql_parse.cc b/sql/sql_parse.cc
index 232df095816..5d108000286 100644
--- a/sql/sql_parse.cc
+++ b/sql/sql_parse.cc
@@ -3348,8 +3348,9 @@ end_with_restore_list:
     res= mysql_insert(thd, all_tables, lex->field_list, lex->many_values,
 		      lex->update_list, lex->value_list,
                       lex->duplicates, lex->ignore);
+    /* do not show last insert ID if VIEW does not have auto_inc */
     if (first_table->view && !first_table->contain_auto_increment)
-      thd->last_insert_id= 0; // do not show last insert ID if VIEW have not it
+      thd->first_successful_insert_id_in_cur_stmt= 0;
     break;
   }
   case SQLCOM_REPLACE_SELECT:
@@ -3401,9 +3402,9 @@ end_with_restore_list:
       /* revert changes for SP */
       select_lex->table_list.first= (byte*) first_table;
     }
-
+    /* do not show last insert ID if VIEW does not have auto_inc */
     if (first_table->view && !first_table->contain_auto_increment)
-      thd->last_insert_id= 0; // do not show last insert ID if VIEW have not it
+      thd->first_successful_insert_id_in_cur_stmt= 0;
     break;
   }
   case SQLCOM_TRUNCATE:
@@ -5807,6 +5808,7 @@ mysql_init_query(THD *thd, uchar *buf, uint length)
  DESCRIPTION
    This needs to be called before execution of every statement
    (prepared or conventional).
+   It is not called by substatements of routines.
 
  TODO
    Make it a method of THD and align its name with the rest of
@@ -5817,9 +5819,12 @@ mysql_init_query(THD *thd, uchar *buf, uint length)
 void mysql_reset_thd_for_next_command(THD *thd)
 {
   DBUG_ENTER("mysql_reset_thd_for_next_command");
+  DBUG_ASSERT(!thd->spcont); /* not for substatements of routines */
   thd->free_list= 0;
   thd->select_number= 1;
-  thd->last_insert_id_used= thd->query_start_used= thd->insert_id_used=0;
+  thd->auto_inc_intervals_in_cur_stmt_for_binlog.empty();
+  thd->stmt_depends_on_first_successful_insert_id_in_prev_stmt= 
+    thd->query_start_used= 0;
   thd->is_fatal_error= thd->time_zone_used= 0;
   thd->server_status&= ~ (SERVER_MORE_RESULTS_EXISTS | 
                           SERVER_QUERY_NO_INDEX_USED |
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 127409a01bf..57969479448 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -7895,7 +7895,7 @@ remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value)
       Field *field=((Item_field*) args[0])->field;
       if (field->flags & AUTO_INCREMENT_FLAG && !field->table->maybe_null &&
 	  (thd->options & OPTION_AUTO_IS_NULL) &&
-	  thd->insert_id())
+	  (thd->first_successful_insert_id_in_prev_stmt > 0))
       {
 #ifdef HAVE_QUERY_CACHE
 	query_cache_abort(&thd->net);
@@ -7903,7 +7903,7 @@ remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value)
 	COND *new_cond;
 	if ((new_cond= new Item_func_eq(args[0],
 					new Item_int("last_insert_id()",
-						     thd->insert_id(),
+                                                     thd->read_first_successful_insert_id_in_prev_stmt(),
 						     21))))
 	{
 	  cond=new_cond;
@@ -7914,7 +7914,11 @@ remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value)
           */
 	  cond->fix_fields(thd, &cond);
 	}
-	thd->insert_id(0);		// Clear for next request
+        /*
+          IS NULL should be mapped to LAST_INSERT_ID only for first row, so
+          clear for next row
+        */
+	thd->first_successful_insert_id_in_prev_stmt= 0;
       }
       /* fix to replace 'NULL' dates with '0' (shreeve@uci.edu) */
       else if (((field->type() == FIELD_TYPE_DATE) ||
diff --git a/sql/sql_table.cc b/sql/sql_table.cc
index 7d8631e3236..4a33231cc19 100644
--- a/sql/sql_table.cc
+++ b/sql/sql_table.cc
@@ -4953,7 +4953,6 @@ bool mysql_alter_table(THD *thd,char *new_db, char *new_name,
   char path[FN_REFLEN];
   char reg_path[FN_REFLEN+1];
   ha_rows copied,deleted;
-  ulonglong next_insert_id;
   uint db_create_options, used_fields;
   handlerton *old_db_type, *new_db_type;
   HA_CREATE_INFO *create_info;
@@ -5773,7 +5772,6 @@ bool mysql_alter_table(THD *thd,char *new_db, char *new_name,
   thd->count_cuted_fields= CHECK_FIELD_WARN;	// calc cuted fields
   thd->cuted_fields=0L;
   thd->proc_info="copy to tmp table";
-  next_insert_id=thd->next_insert_id;		// Remember for logging
   copied=deleted=0;
   if (new_table && !(new_table->file->ha_table_flags() & HA_NO_COPY_ON_ALTER))
   {
@@ -5784,7 +5782,6 @@ bool mysql_alter_table(THD *thd,char *new_db, char *new_name,
 				   handle_duplicates, ignore,
 				   order_num, order, &copied, &deleted);
   }
-  thd->last_insert_id=next_insert_id;		// Needed for correct log
   thd->count_cuted_fields= CHECK_FIELD_IGNORE;
 
   /* If we did not need to copy, we might still need to add/drop indexes. */
@@ -6214,6 +6211,7 @@ copy_data_between_tables(TABLE *from,TABLE *to,
   ha_rows examined_rows;
   bool auto_increment_field_copied= 0;
   ulong save_sql_mode;
+  ulonglong prev_insert_id;
   DBUG_ENTER("copy_data_between_tables");
 
   /*
@@ -6320,6 +6318,7 @@ copy_data_between_tables(TABLE *from,TABLE *to,
     {
       copy_ptr->do_copy(copy_ptr);
     }
+    prev_insert_id= to->file->next_insert_id;
     if ((error=to->file->ha_write_row((byte*) to->record[0])))
     {
       if ((!ignore &&
@@ -6345,7 +6344,7 @@ copy_data_between_tables(TABLE *from,TABLE *to,
 	to->file->print_error(error,MYF(0));
 	break;
       }
-      to->file->restore_auto_increment();
+      to->file->restore_auto_increment(prev_insert_id);
       delete_count++;
     }
     else
@@ -6379,6 +6378,7 @@ copy_data_between_tables(TABLE *from,TABLE *to,
   free_io_cache(from);
   *copied= found_count;
   *deleted=delete_count;
+  to->file->ha_release_auto_increment();
   if (to->file->ha_external_lock(thd,F_UNLCK))
     error=1;
   DBUG_RETURN(error > 0 ? -1 : 0);
diff --git a/sql/sql_update.cc b/sql/sql_update.cc
index da529cc0070..495c71c42f9 100644
--- a/sql/sql_update.cc
+++ b/sql/sql_update.cc
@@ -135,7 +135,8 @@ int mysql_update(THD *thd,
   SQL_SELECT	*select;
   READ_RECORD	info;
   SELECT_LEX    *select_lex= &thd->lex->select_lex;
-  bool need_reopen;
+  bool          need_reopen;
+  ulonglong     id;
   DBUG_ENTER("mysql_update");
 
   for ( ; ; )
@@ -675,6 +676,10 @@ int mysql_update(THD *thd,
     thd->lock=0;
   }
 
+  /* If LAST_INSERT_ID(X) was used, report X */
+  id= thd->arg_of_last_insert_id_function ?
+    thd->first_successful_insert_id_in_prev_stmt : 0;
+
   if (error < 0)
   {
     char buff[STRING_BUFFER_USUAL_SIZE];
@@ -682,8 +687,7 @@ int mysql_update(THD *thd,
 	    (ulong) thd->cuted_fields);
     thd->row_count_func=
       (thd->client_capabilities & CLIENT_FOUND_ROWS) ? found : updated;
-    send_ok(thd, (ulong) thd->row_count_func,
-	    thd->insert_id_used ? thd->insert_id() : 0L,buff);
+    send_ok(thd, (ulong) thd->row_count_func, id, buff);
     DBUG_PRINT("info",("%d records updated",updated));
   }
   thd->count_cuted_fields= CHECK_FIELD_IGNORE;		/* calc cuted fields */
@@ -1632,6 +1636,7 @@ err2:
 bool multi_update::send_eof()
 {
   char buff[STRING_BUFFER_USUAL_SIZE];
+  ulonglong id;
   thd->proc_info="updating reference tables";
 
   /* Does updates for the last n - 1 tables, returns 0 if ok */
@@ -1684,12 +1689,12 @@ bool multi_update::send_eof()
     return TRUE;
   }
 
-
+  id= thd->arg_of_last_insert_id_function ?
+    thd->first_successful_insert_id_in_prev_stmt : 0;
   sprintf(buff, ER(ER_UPDATE_INFO), (ulong) found, (ulong) updated,
 	  (ulong) thd->cuted_fields);
   thd->row_count_func=
     (thd->client_capabilities & CLIENT_FOUND_ROWS) ? found : updated;
-  ::send_ok(thd, (ulong) thd->row_count_func,
-	    thd->insert_id_used ? thd->insert_id() : 0L,buff);
+  ::send_ok(thd, (ulong) thd->row_count_func, id, buff);
   return FALSE;
 }
diff --git a/sql/structs.h b/sql/structs.h
index 38bb441fc03..83ae6cac032 100644
--- a/sql/structs.h
+++ b/sql/structs.h
@@ -250,3 +250,99 @@ typedef struct  user_conn {
 #define STATUS_UPDATED		16	/* Record is updated by formula */
 #define STATUS_NULL_ROW		32	/* table->null_row is set */
 #define STATUS_DELETED		64
+
+/*
+  Such interval is "discrete": it is the set of
+  { auto_inc_interval_min + k * increment,
+    0 <= k <= (auto_inc_interval_values-1) }
+  Where "increment" is maintained separately by the user of this class (and is
+  currently only thd->variables.auto_increment_increment).
+  It mustn't derive from Sql_alloc, because SET INSERT_ID needs to
+  allocate memory which must stay allocated for use by the next statement.
+*/
+class Discrete_interval {
+private:
+  ulonglong interval_min;
+  ulonglong interval_values;
+  ulonglong  interval_max;    // excluded bound. Redundant.
+public:
+  Discrete_interval *next;    // used when linked into Discrete_intervals_list
+  void replace(ulonglong start, ulonglong val, ulonglong incr)
+  {
+    interval_min=    start;
+    interval_values= val;
+    interval_max=    (val == ULONGLONG_MAX) ? val : start + val * incr;
+  }
+  Discrete_interval(ulonglong start, ulonglong val, ulonglong incr) :
+    next(NULL) { replace(start, val, incr); };
+  Discrete_interval() : next(NULL) { replace(0, 0, 0); };
+  ulonglong minimum() const { return interval_min;    };
+  ulonglong values()  const { return interval_values; };
+  ulonglong maximum() const { return interval_max;    };
+  /*
+    If appending [3,5] to [1,2], we merge both in [1,5] (they should have the
+    same increment for that, user of the class has to ensure that). That is
+    just a space optimization. Returns 0 if merge succeeded.
+  */
+  bool merge_if_contiguous(ulonglong start, ulonglong val, ulonglong incr)
+  {
+    if (interval_max == start)
+    {
+      if (val == ULONGLONG_MAX)
+      {
+        interval_values=   interval_max= val;
+      }
+      else
+      {
+        interval_values+=  val;
+        interval_max=      start + val * incr;
+      }
+      return 0;
+    }
+    return 1;
+  };
+};
+
+/* List of Discrete_interval objects */
+class Discrete_intervals_list {
+private:
+  Discrete_interval        *head;
+  Discrete_interval        *tail;
+  /*
+    When many intervals are provided at the beginning of the execution of a
+    statement (in a replication slave or SET INSERT_ID), "current" points to
+    the interval being consumed by the thread now (so "current" goes from
+    "head" to "tail" then to NULL).
+  */
+  Discrete_interval        *current;
+  uint                  elements; // number of elements
+public:
+  Discrete_intervals_list() : head(NULL), current(NULL), elements(0) {};
+  void empty_no_free()
+  {
+    head= current= NULL;
+    elements= 0;
+  }
+  void empty()
+  {
+    for (Discrete_interval *i= head; i;)
+    {
+      Discrete_interval *next= i->next;
+      delete i;
+      i= next;
+    }
+    empty_no_free();
+  }
+  const Discrete_interval* get_next()
+  {
+    Discrete_interval *tmp= current;
+    if (current != NULL)
+      current= current->next;
+    return tmp;
+  }
+  ~Discrete_intervals_list() { empty(); };
+  bool append(ulonglong start, ulonglong val, ulonglong incr);
+  ulonglong minimum()     const { return (head ? head->minimum() : 0); };
+  ulonglong maximum()     const { return (head ? tail->maximum() : 0); };
+  uint      nb_elements() const { return elements; }
+};