Best way to add Foreign Key to massive table? Say I have 4 tables: arrival (~100 million rows), departure (~100 million rows), airport (~30 million rows), airplane (small).

arrival and departure each have 2 ForeignKeys: one to airport, one to airplane.

Currently, to figure out which planes are at an airport at a certain time, I have to do a massive join between arrival, departure, and airport. So, I'd like to add a (possibly NULL) ForeignKey to the departure table that points to the arrival of the same airplane that's departing.

Given that these tables are so big, it seems like a bad idea to do this all as a single transaction. So, what's the best way to go about it?
First of all, depending not just on the number of rows but also on the total size of your table (based on the average row size) , it may not be excessive to create a new Foreign Key. Especially if scheduled properly.  

However, it may well be too heavy a change.  In that case, you could consider creating an Intersection Table like:

CREATE TABLE FlightPair
(
     departurekey INT REFERENCES arrival NULL,
     arrivalkey INT REFERENCES departure NULL
)


This would allow you to incrementally batch the insert of rows into the intersection table a bit at a time, thus keeping the update transactions quite small.  Perhaps insert one day at a time, 10,000 rows at a time, or some other batching method.  Each batch should be a transaction that begins before the insert/update and commits when finished.

That means that the updating of the batches of your choice would be many small transactions instead of one big one.  That would limit the resources needed and, in many cases, would run faster that one big update.

Perhaps having a date included would help to filter the results more effectively.  NULL keys are probably needed for the periods that are incomplete.

What indexes do you currently have?  SQL performance issues often depend on having the indexes properly defined. The columns in the intersection table likewise need to have indexes, as do the departure and arrival tables.