When using statement-based replication, AUTO_INCREMENT columns in tables on the slave must match the same columns on the master; that is, AUTO_INCREMENT columns must be replicated to AUTO_INCREMENT columns.

This is a known issue which is fixed in MySQL 5.5. (Bug #12669186)

Prior to MySQL 5.1.12, a stored procedure that uses LAST_INSERT_ID() does not replicate properly using statement-based binary logging.

Prior to MySQL 5.1.12, when a stored routine or trigger caused an INSERT into an AUTO_INCREMENT column, the generated AUTO_INCREMENT value was not written into the binary log, so a different value could in some cases be inserted on the slave.

An insert into an AUTO_INCREMENT column caused by a stored routine or trigger running on a master that uses MySQL 5.0.60 or earlier does not replicate correctly to a slave running MySQL 5.1.12 through 5.1.23 (inclusive). (Bug #33029)

A statement invoking a trigger or function that causes an update to an AUTO_INCREMENT column is not replicated correctly using statement-based replication. Beginning with MySQL 5.1.40, such statements are marked as unsafe. (Bug #45677)

The AUTO_INCREMENT table option was not replicated correctly prior to MySQL 5.1.31. (Bug #41986)

An INSERT into a table that has a composite primary key that includes an AUTO_INCREMENT column that is not the first column of this composite key is not safe for statement-based logging or replication. Beginning with MySQL 5.1.64, such statements are marked as unsafe. (Bug #11754117, Bug #45670)

This issue does not affect tables using the InnoDB storage engine, since an InnoDB table with an AUTO_INCREMENT column requires at least one key where the auto-increment column is the only or leftmost column.

Adding an AUTO_INCREMENT column to a table with ALTER TABLE might not produce the same ordering of the rows on the slave and the master. This occurs because the order in which the rows are numbered depends on the specific storage engine used for the table and the order in which the rows were inserted. If it is important to have the same order on the master and slave, the rows must be ordered before assigning an AUTO_INCREMENT number. Assuming that you want to add an AUTO_INCREMENT column to a table t1 that has columns col1 and col2, the following statements produce a new table t2 identical to t1 but with an AUTO_INCREMENT column:

CREATE TABLE t2 LIKE t1;
ALTER TABLE t2 ADD id INT AUTO_INCREMENT PRIMARY KEY;
INSERT INTO t2 SELECT * FROM t1 ORDER BY col1, col2;

The instructions just given are subject to the limitations of CREATE TABLE ... LIKE: Foreign key definitions are ignored, as are the DATA DIRECTORY and INDEX DIRECTORY table options. If a table definition includes any of those characteristics, create t2 using a CREATE TABLE statement that is identical to the one used to create t1, but with the addition of the AUTO_INCREMENT column.

Regardless of the method used to create and populate the copy having the AUTO_INCREMENT column, the final step is to drop the original table and then rename the copy:

DROP t1;
ALTER TABLE t2 RENAME t1;

See also Section C.5.7.1, “Problems with ALTER TABLE”.