Deleting from table with millions of records

I don't think it is possible to delete without locking. That said, I don't think locking the record you want to delete is a problem. What would be a problem is locking other rows.

I found some information on that subject here: http://dev.mysql.com/doc/refman/5.0/en/innodb-locks-set.html

What I would suggest, is to try and do a million single row deletes. I think that if you do all those in a single transaction, performance should not hurt too much. so you would get something like:

START TRANSACTION;

DELETE FROM tab WHERE id = 1;
..
..
DELETE FROM tab WHERE id = x;

COMMIT;

You can generate the required statments by doing something like

SELECT CONCAT('DELETE FROM tab WHERE id = ', id)
FROM   tab
WHERE  <some intricate condition that selects the set you want to delete>

So the advantage over this method instead of doing:

DELETE FROM tab 
WHERE  <some intricate condition that selects the set you want to delete>

is that in the first approach you only ever lock the record you're deleting, whereas in the second approach you could run the risk of locking other records that happen to be in the same range as the rows you are deleteing.

If it fits your application, then you could limit the number of rows to delete, and setup a cronjob for repeating the deletion. E.g.:

DELETE FROM tab WHERE .. LIMIT 1000

I found this to be good compromise in a similar scenario.