I set a replication master -> slave.
I create a simple table with NO Primary Key
I populate data (a few thousands rows)

Then, I switch binlog format to ROW
I update rows on the master (it takes a few seconds to execute)

=> On slave, it takes a very long time to apply changes (on my original table with 200'000 rows, I skipped the query (with SQL_SLAVE_SKIP_COUNTER) after 20 minutes still in "Reading event from the relay log" state...).

If I create a primary key, changes are applied instantly on slave.

Here is a test case to reproduce the problem :

MASTER
--------

mydb=# CREATE TABLE `nptest` (
-> `id` int(11) NOT NULL DEFAULT '0',
-> `tmp` tinyint(4) DEFAULT NULL
-> );
Query OK, 0 rows affected (0.07 sec)

mydb=# INSERT INTO nptest (id) SELECT id FROM othertable;
Query OK, 192743 rows affected (1.83 sec)
Records: 192743 Duplicates: 0 Warnings: 0

mydb=# SET binlog_format = ROW;
Query OK, 0 rows affected (0.00 sec)

mydb=# UPDATE nptest SET tmp = 1;
Query OK, 192743 rows affected (3.76 sec)
Rows matched: 192743 Changed: 192743 Warnings: 0

SLAVE
--------

(none)=# SHOW PROCESSLIST\G

*************************** 23. row ***************************
Id: 627527
User: system user
Host:
db: NULL
Command: Connect
Time: 103
State: Reading event from the relay log
Info: NULL
Progress: 0.000