Delete single row from large MySql table results in "lock timeout"

Question

I'm running MySql 5.0.22 and have a really unwieldy table containing approximately 5 million rows.

Some, but not all rows are referenced by a foreign key to another table.

All attempts to cull the unreferenced rows have failed so far, resulting in lock-timeouts every time.

Copying the rows I want to an alternate table also failed with lock-timeout.

Suspiciously, even a statement that should finish instantaneously like the one below will also fail with "lock timeout":

DELETE FROM mytable WHERE uid_pk = 1 LIMIT 1;

...it's at this point that I've run out of ideas.

Edit: For what it's worth, I've been working through this on my dev system, so only I am actually using the database at this moment so there shouldn't be any locking going on outside of the SQL I'm running.

Any MySql gurus out there have suggestions on how to tame this rogue table?

Edit #2: As requested, the table structure:

CREATE TABLE `tunknowncustomer` (
  `UID_PK` int(11) NOT NULL auto_increment,
  `UNKNOWNCUSTOMERGUID` varchar(36) NOT NULL,
  `CREATIONDATE` datetime NOT NULL,
  `EMAIL` varchar(100) default NULL,
  `CUSTOMERUID` int(11) default NULL,
  PRIMARY KEY  (`UID_PK`),
  KEY `IUNKNOWCUST_CUID` (`CUSTOMERUID`),
  KEY `IUNKNOWCUST_UCGUID` (`UNKNOWNCUSTOMERGUID`),
  CONSTRAINT `tunknowncustomer_ibfk_1` FOREIGN KEY (`CUSTOMERUID`) REFERENCES `tcustomer` (`UID_PK`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8$$

Note, attempting to drop the FK also times out.

Answer 1

I had the same problem with an innodb table. optimize table corrected it.