Perhaps you should look into using tombstone tables.
Here is what I mean: Suppose you had this table
CREATE TABLE mytable
(
id INT NOT NULL AUTO_INCREMENT,
... other columns ....
PRIMARY KEY (id),
... other indexes ...
);
Now, create a table with the IDs that are marked for deletion
CREATE TABLE mytable_deleted
(
id INT NOT NULL,
PRIMARY KEY (id)
);
So instead of doing
DELETE FROM mytable WHERE MOD(id,100) = 0;
You would add the ids to mytable_deleted
INSERT IGNORE INTO mytable_deleted
SELECT id FROM mytable WHERE MOD(id,100) = 0;
From here, you simply have to add the mytable_delete to all queries
To see all rows
SELECT * FROM mytable;
To see non-deleted rows
SELECT * FROM mytable A LEFT JOIN mytable_deleted B USING (id) WHERE B.id IS NULL;
To see deleted rows
SELECT * FROM mytable A LEFT JOIN mytable_deleted B USING (id) WHERE B.id IS NOT NULL;
or
SELECT * FROM mytable A INNER JOIN mytable_deleted B USING (id);
To perform the actual deletion
DELETE A.* FROM mytable A INNER JOIN mytable_deleted B USING (id);
TRUNCATE TABLE mytable_deleted;
CAVEAT
This will means that lots of SELECT queries must incorporate the tombstone table.
I have discussed this before : Tombstone Table vs Deleted Flag in database syncronization & soft-delete scenarios. You should read the accepted answer from Leigh Riffel instead of mine for a more honest critique as to which method is better in your case.