Adding foreign keys constraint on databases used
OK - following my comment, here is what I would do.

Before shutting down the server or individual database.


Create backup table scripts for each table you need to enforce foreign keys on and their parent(s). Call them my_table_bak (or similar).
Run these CREATE TABLE my_table_bak(1..n) scripts on the database (don't definitively delete anything).
(removed during edit)
Prepare an SQL script file (salvage.sql? :-))

Now, the question is are you removing orphan records (i.e. child records that have no corresponding record in the parent table)? Or are you deleting barren parents (i.e. parents with no child records)? Below will do both.

INSERT INTO parent_bak 
SELECT * FROM parent 
WHERE parent.primary_key NOT IN 
(
    SELECT child.foreign_key 
    FROM child
); -- backup barren parents

INSERT INTO child_bak 
SELECT * FROM child 
WHERE child.foreign_key 
NOT IN 
(
    SELECT parent.primary_key 
    FROM parent
); -- backup orphan records

DELETE FROM parent 
WHERE parent.primary_key 
NOT IN 
(
    SELECT child.foreign_key 
    FROM child
); -- remove invalid records from your original tables.

DELETE FROM child 
WHERE child.foreign_key NOT IN 
(
    SELECT parent.primary_key 
    FROM parent
); -- remove invalid records from your original tables.


Add your FOREIGN KEY constraints.
Stop all clients connecting to the server or database (so updates can't occur while running the copy into _bak tables (invalid data) and the deletes.
Run:

mysql -h host -u username -ppassword yourdb &lt; salvage.sql


...for each of your servers. For your 20 databases, you could write a script for all 20 and run that.




The time this will take will depend on the size of your databases and the number of tables. Warning - there may be typos in this post - I didn't run the scripts on a server, but you should get the idea.

Test on at least one database before running on your live server.

[EDIT] Forgot - add your FOREIGN KEY constraints at the end of salvage.sql also.