Why does MySQL explicit predicate locking disallow INSERT statements outside of the predicate lock

Assuming we have the following database tables:

create table department (
    id bigint not null, 
    budget bigint not null, 
    name varchar(255), 
    primary key (id)
) ENGINE=InnoDB

create table employee (
    id bigint not null, 
    name varchar(255), 
    salary bigint not null, 
    department_id bigint, primary key (id)
) ENGINE=InnoDB

alter table employee 
add constraint FK_department_id 
foreign key (department_id) 
references department (id)

And we have 2 departments:

insert into department (name, budget, id) 
values ('Hypersistence', 100000, 1)

insert into department (name, budget, id) 
values ('Bitsystem', 10000, 2)

And 3 employees in the first department:

insert into employee (department_id, name, salary, id) 
values (1, 'John Doe 0', 30000, 0)

insert into employee (department_id, name, salary, id) 
values (1, 'John Doe 1', 30000, 1)

insert into employee (department_id, name, salary, id) 
values (1, 'John Doe 2', 30000, 2)

Assuming we have two concurrent users: Alice and Bob.

First, Alice locks all the employee belonging to the 1st department and also gets the sum of salaries for that particular department:

SELECT * 
FROM employee 
WHERE department_id = 1 
FOR UPDATE

SELECT SUM(salary) 
FROM employee 
where department_id = 1

Now, in the meanwhile, it's expected that Bob cannot insert a new employee using the same department_id:

insert into employee (department_id, name, salary, id) 
values (1, `Carol`, 9000, 4)

com.mysql.jdbc.exceptions.jdbc4.MySQLTransactionRollbackException: 
    Lock wait timeout exceeded; try restarting transaction

So, the lock prevented Bob from issuing an insert against the same predicate.

However, the same exception is thrown even if Bob tries to insert an employee in a different department:

insert into employee (department_id, name, salary, id) 
values (2, `Dave`, 9000, 5)

com.mysql.jdbc.exceptions.jdbc4.MySQLTransactionRollbackException: 
    Lock wait timeout exceeded; try restarting transaction

This last insert statement is using the 2nd department_id, so this row should not overlap with the select statement for which we acquired a predicate lock.

Why does MySQL prevent the second insert which is not overlapping with the predicate lock acquired by the first transaction?

The same behavior can be observed on SQL Server as well.

Update

When changing the isolation level to READ_COMMITTED, the predicate lock does not prevent any of the two insert statements issued by Bob.

That could be explained if taking into consideration the following statements from this Percona blog post:

In REPEATABLE READ every lock acquired during a transaction is held for the duration of the transaction.

In READ COMMITTED the locks that did not match the scan are released after the STATEMENT completes.

However, it's still interesting to find out why the predicate locking works as it does on REPEATABLE READ.

Solution

The SELECT FOR UPDATE is locking between 1 and the next value in the employee table. Since there is no next-value, it is locking until the supremum pseudo-record. This can be seen in information_schema.innodb_locks:

mysql> select * from innodb_locks;
+----------------+-------------+-----------+-----------+-------------------+------------+------------+-----------+----------+------------------------+
| lock_id        | lock_trx_id | lock_mode | lock_type | lock_table        | lock_index | lock_space | lock_page | lock_rec | lock_data              |
+----------------+-------------+-----------+-----------+-------------------+------------+------------+-----------+----------+------------------------+
| 28275:1448:3:1 | 28275       | X         | RECORD    | `test`.`employee` | PRIMARY    |       1448 |         3 |        1 | supremum pseudo-record |
| 28273:1448:3:1 | 28273       | X         | RECORD    | `test`.`employee` | PRIMARY    |       1448 |         3 |        1 | supremum pseudo-record |
+----------------+-------------+-----------+-----------+-------------------+------------+------------+-----------+----------+------------------------+
2 rows in set, 1 warning (0.00 sec)

If you change the test-case slightly so there is a row in employees for dept-id=2, and then try and add an employee for dept-id=3, it will work. Example:

create table department (
    id bigint not null, 
    budget bigint not null, 
    name varchar(255), 
    primary key (id)
) ENGINE=InnoDB;

create table employee (
    id bigint not null, 
    name varchar(255), 
    salary bigint not null, 
    department_id bigint, primary key (id)
) ENGINE=InnoDB;


alter table employee 
add constraint FK_department_id 
foreign key (department_id) 
references department (id);


insert into department (name, budget, id) 
values ('Hypersistence', 100000, 1);

insert into department (name, budget, id) 
values ('Bitsystem', 10000, 2);

insert into department (name, budget, id) 
values ('XX', 10000, 3);


insert into employee (department_id, name, salary, id) 
values (1, 'John Doe 0', 30000, 0);

insert into employee (department_id, name, salary, id) 
values (1, 'John Doe 1', 30000, 1);

insert into employee (department_id, name, salary, id) 
values (2, 'John Doe 2', 30000, 2);


start transaction;

SELECT * 
FROM employee 
WHERE department_id = 1 
FOR UPDATE;


# new session

insert into employee (department_id, name, salary, id) 
values (3, 'Dave', 9000, 5)