MySQL - Simple update is very slow We are having trouble with simple updates on a single table taking a long time. The table contains ~5 Million rows.

Here is the table:

CREATE TABLE Documents (
    GeneratedKey varchar(32) NOT NULL,
    SourceId int(11) NOT NULL,
    Uri longtext,
    ModifiedDateUtc datetime NOT NULL,
    OperationId varchar(36) DEFAULT NULL,
    RowModifiedDateUtc datetime NOT NULL,
    ParentKey varchar(32) NOT NULL,
    PRIMARY KEY (SourceId, GeneratedKey),
    KEY IX_RowModifiedDateUtc (RowModifiedDateUtc),
    KEY IX_ParentKey (ParentKey),
    KEY IX_OperationId (OperationId(36))
) ENGINE=InnoDB DEFAULT CHARSET=utf8;


Here is the update query:

UPDATE Documents
SET OperationId = 'xxxx'
WHERE SourceId = 12345
AND ParentKey = '0965b3983ceb0e8e41ab47b53e37d0f3';


This query updates ~80k rows and takes around 60 seconds to complete, and the more rows updated the longer it takes which results in timeouts. The index IX_ParentKey cardinality is ~830k. Note that a select with the same WHERE clause returns very quickly (&lt; 1s).

Query profiling:

starting                0.000072
checking permissions    0.000006
Opening tables          0.000019
init                    0.000023
System lock             0.000266
updating                50.415424
end                     0.000039
query end               0.024398
closing tables          0.000037
freeing items           0.000051
cleaning up             0.000022


When switching to MyISAM, the query took only 2 seconds. What could be slowing down the updates, I assume the index needs to be rebuilt? Is there any way we can optimize this?
There are many possible explanations:


UUIDs have terrible performance on large tables.
What was the value of innodb_buffer_pool_size?  It should be about 70% of available RAM.  Poor caching, especially due to UUIDs could ba a problem.
That UPDATE needs INDEX(SourceId, ParentKey) (in either order).
Why prefix the index on OperationId when it is already that length?
Don't use utf8 on hex strings.
Packing UUIDs into BINARY(16) would shrink the table, thereby providing more speed.
Updating 80K rows at once takes a lot of effort, especially when planning for a possible ROLLBACK.  This may partially explain why InnoDB seems to be slower than MyISAM.  Will you often update that many rows?  Sound like a design flaw.