MySQL Bugs: #40384: Gap in auto_increment sequence when inserts fire a trigger

Bug #40384	Gap in auto_increment sequence when inserts fire a trigger
Submitted:	29 Oct 2008 7:42	Modified:	4 Nov 2019 15:09
Reporter:	Øystein Grøvlen	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: DML	Severity:	S3 (Non-critical)
Version:	5.1, main-6.0, revision 2866 and greater	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	regresssion

Description:
I have an after insert trigger on a table with auto_increment key.  This trigger inserts row into another table.  If I execute an insert statements inserting multiple rows, there will be gaps in the auto_increment statement between consecutive statements.

When the test case mentioned in this report is run on later 6.0 revisions, I see the following output for the last query:

SELECT * FROM t2;
id      data
1       Normal Insert1
2       Normal Insert2
3       Normal Insert3
4       Normal Insert4
8       Normal Insert5
9       Normal Insert6
10      Normal Insert7
11      Normal Insert8

On earlier revisions, ids will be 1 through 8. 

How to repeat:
Execute the following test case:

--source include/have_innodb.inc

# Create database
CREATE DATABASE IF NOT EXISTS ptr_ob1;
USE ptr_ob1;

--echo **** Creating tables ****

CREATE TABLE t2(
  id INT NOT NULL AUTO_INCREMENT PRIMARY KEY, 
  data CHAR(50)
) ENGINE = innodb;

CREATE TABLE t3(
 name VARCHAR(30) NOT NULL 
) ENGINE = innodb; 

--echo **** Creating Triggers ****

delimiter ||;
CREATE TRIGGER trg2 AFTER INSERT ON t2 FOR EACH ROW
BEGIN
 INSERT INTO t3 VALUES('trigger fired for AFTER INSERT');
END;||
delimiter ;||

INSERT INTO t2 VALUES
(NULL, 'Normal Insert1'),(NULL, 'Normal Insert2'),
(NULL, 'Normal Insert3'),(NULL, 'Normal Insert4');

SELECT * FROM t2;
SELECT * FROM t3;

INSERT INTO t2 VALUES
(NULL, 'Normal Insert5'),(NULL, 'Normal Insert6'),
(NULL, 'Normal Insert7'),(NULL, 'Normal Insert8');

SELECT * FROM t2;

Thank you for the report.

Verified as described. Version 5.1 is affected and version 5.0 is not.

Probably has workaround: use single-row INSERT statements.

I'm unsure about "on earlier revisions, ids will be 1 through 8."
I took the latest 6.0-main tree, ran the testcase and the result was:
+SELECT * FROM t2;
+id     data
+1      Normal Insert1
+2      Normal Insert2
+3      Normal Insert3
+4      Normal Insert4
+8      Normal Insert5
+9      Normal Insert6
+10     Normal Insert7
+11     Normal Insert8

Then I undid the changes of the fix for BUG#31612
(what is called revision 2866 which is actually revision guilhem@mysql.com-20081006140659-0ktkpe0glfgs6am2)
and then I got:
+SELECT * FROM t2;
+id     data
+1      Normal Insert1
+2      Normal Insert2
+3      Normal Insert3
+4      Normal Insert4
+6      Normal Insert5
+7      Normal Insert6
+8      Normal Insert7
+9      Normal Insert8

See, there is a gap at 5 (1,2,3,4,6, etc).
That is, the gap existed before my patch (already a bug, as there's no reason for this gap, test is single-threaded without rollbacks); and my patch probably amplified this gap. It may be that by fixing the pre-patch bug, the post-patch bug would go away too.

So, here's what happens (this explains the 1,2,3,4,8,9,10,11, and probably also the 1,2,3,4,6,7,8,9 of before-the-fix-for-bug-31612).
handler::update_auto_increment(), in 5.1 since WL#3146 (2006), is capable of asking engines to reserve an interval of auto_increment values of a certain width (this was made to avoid going to the engine for every row: we ask the engine for a bunch of values, less round-trips). It determines the width by following this logic:
- if the number of rows to insert is known and is N, ask the engine for N values
- if it's not known, ask the engine for 1 value; if later in the same INSERT we have used this value and find out that we need one more value, ask for 1*2 more values; if later we have used those 2 more and find out that we need yet one more value, ask for 2*2 values, etc, in total, it means ask for 2^(number of already reserved intervals).
Here, the number of rows to insert could be known (it's 4), but, because triggers are involved, it's not (see comment in handler::update_auto_increment() 
"Note that in prelocked mode no estimation is given."); this is a fact of prelocking. So the method follows the "*2" heuristic above. Which means that the first multi-row INSERT does:
- first row, asks for one value (1) (this bumps InnoDB's next-auto-inc counter to 2)
- second row, reserved interval is exhausted (it was only one value and was entirely used by first row), ask for 2 values (2,3) (this bumps InnoDB's next-auto-inc counter to 4)
- third row, reserved interval has one value free (3), use it
- fourth row, reserved interval is exhauster, ask for 2*2=4 values (4,5,6,7) (this bumps InnoDB's next-auto-inc counter to 8)
- end of INSERT: InnoDB's release_auto_increment() is called, but this is an empty method; if InnoDB wanted, it could define it and reclaim unused values; but it does not, so InnoDB's next-auto-inc counter stays at 8
- Second INSERT starts: InnoDB's next-auto-inc counter is 8 so 8 is inserted.

Before my patch, the gap would not be so big (only 1) because there was another effect: the "*2" heuristic was fooled by the number of reserved intervals which was always 1 during the first INSERT though it is successively 1, then 2, then 3 (3 reserved intervals at end of INSERT). So the heuristic reserved always intervals of max width 2, and that's why the gap was smaller. But it was a bug, not a good thing, the patch intentionally fixed this. Here it causes a problem, but there are other cases (large INSERTs) where reserving 1 then 2 values again and again (1-2-2-2-2-2-etc) would be less efficient than reserving 1-2-4-8-16-etc values).

So I'm not sure anything can be done for this. It's a case where:
- the server does not pass enough info (due to the presence of trigger) for handler::update_auto_increment() to allocate the exact number of values
- so it has to use a heuristic, which is bound to have some unused values and so some gaps

Later, engines may want to implement release_auto_increment() to reclaim unused values.

An improvement which could be done in the server:
when using triggers, ha_start_bulk_insert() could pass a proper number instead of just 0 (which means "unknown number of rows to insert").

Even if there was an improvement of the estimation for triggers, the estimation would still be "unknown" for INSERT SELECT.
Another change to consider: instead of growing by powers of 2, grow by powers of a smaller number A (1<A<2). The average number of lost values for a number of rows to insert by the statement is roughly
lost = rows_in_statement * (A - 1) / 2
(with a max at rows_in_statement * (A - 1) and a min at 0).
So with A=1.5, 'lost' would be 25% of rows_in_statement on average, which sounds acceptable.
Note that max width is already limited to 64k.
Before the patch we accidentally had a max width of 2, which made a gap of 1 or 0. The problems with reverting to that behaviour (having a max width of 2) are:
- it would make lots of round-trips to the engine (defeating the idea of reservation)
- it would make very large INSERTs use a very large number of intervals, and so generate a very large Insert_id_list_event (see WL#3404).

Another workaround: use partitioning. (after the fix for bug#33479, this does not happen in a partitioned table :)

If not release_auto_increment is implemented in the engine, then the server should only allocate one auto_increment at a time to prevent gaps.

It is probably easy to verify if any auto_increment has been allocated by another thread, and if not, then it is OK to go back to the lowest used auto_increment value. See the code for ha_partition::release_auto_increment. Maybe move this code in to a default auto_increment handling in the server?

Posted by developer:
 
this bug was fixed by the fix for
    Bug #12752572 61579: REPLICATION FAILURE WHILE
    INNODB_AUTOINC_LOCK_MODE=1 AND USING TRIGGER
in May 2012.