Background to avoid the X-Y problem: I'm building a database migration system that needs to resolve foreign key constraints (see here for full background). I need to determine what order I can execute create table/modify table operations so as to not violate any foreign key constraints. A topological sort is a natural starting place, except that a database can have circular constraints that a typical topological sorting algorithm can't handle.

There are some questions along those lines already here, and the most common suggestion I see here is to simply remove foreign key constraints and add them separately afterwards. That is not the solution I'm looking for, because doing so results in twice as many table alteration operations, which is especially important to avoid for large tables. As much as possible I would like to minimize the total number of CREATE/ALTER commands needed to migrate the database, which requires being smart about it.

Obviously though, in the case of circular foreign key constraints, the only option is to add the foreign keys separately. As a result the general approach I'm looking for is a two part approach: identify circular constraints and "break" them by flagging the foreign key constraints to be added afterward, perform a standard topological sort on the remaining operations, update the database in topological order, and finally apply any outstanding constraints that were reserved for later. I've found plenty of examples of topological sort algorithms, and references to algorithms that can help identify edges to be "broken" to enable a standard topological sort algorithm, but no actual algorithms for the latter.

Any direction would be appreciated, both for my specific problem and the general problem.

1 Month later: Update

A few weeks in, and I've learned that I do indeed need to solve this problem. I went with the general suggestion of just migrating with the foreign key checks off, especially given suggestions that it will improve overall performance. We've now been using this internally for a few weeks.

Unfortunately, it isn't a bullet-proof solution. It turns out that there are edge cases where MySQL will throw a 1215 error even with foreign key checks off. I've always had a plan to add in a MySQL linter on the table definitions, and that will prevent this edge case from being encountered. They primarily happen as a result of adjusting the structure to fix items that were caused by developers not being careful enough when initially creating the tables. Regardless, I now know that there are cases where order matters even when transaction checks are off. While we are implementing institutional fixes on our end to avoid those cases, I want this to be a general purpose tool for others. Others may run into these same edge cases, which means I need to implement a proper topological sorting, and I can't do that without identifying and breaking cycles. To be clear, in this case breaking cycles means simply flagging foreign key constraints to be added after everything else. It doesn't have to be smart. It just has to identify when the addition of an add foreign key operation to the migration plan will result in a cycle, and defer that add operation until after everything else.

  • 2
    The fact you need more ALTER TABLE operations for disabling and enabling the FK contraints does not necessarily mean the resulting program is noteable slower than a solution which avoids these. And "breaking cycles" does not have unique solution, in a loop, it does not matter where you break a cycle, for a relational model it might matter. For a real world model, however, it is IMHO better to make a sensible decision about this, if your model has, say less than 500 tables and maybe 10 to 20 cycles, you can make this decision manually far quicker than trying to invent something "smart". – Doc Brown Oct 13 '17 at 14:37
  • 2
    I'd want to profile migrating data with constraints on vs constraints off followed by adding them. You might find that the latter is faster than the former. – Caleth Oct 13 '17 at 14:43
  • 1
    You only need the constraints whilst data is being changed. If you have exclusive access during the migration then the data can't be changing – Caleth Oct 13 '17 at 14:53
  • 1
    @ConorMancone: my point is, you need to identify these 10 FK constraints once. I assume this is not a process you need to repeat several times. Thus it will probably much easier to do this manually, for example by using a printout of the ER model, than by implementing some sophisticated "cycle breaker algorithm", including some input interface for this algorithm to feed it with the schema information. – Doc Brown Oct 13 '17 at 15:00
  • 1
    What is the largest expected size of database, in terms of data? Are we talking less than a million rows or are we talking potentially many millions of rows? Volumetrics dictate solution approaches. We migrated a 14 million row database for Y2K and started out with constraints enabled. Dropped that idea the first day. Completely impossible. Used too much of everything and ran for too slow to ever finish before crashing the system. – DocSalvager Oct 19 '17 at 21:22

What you are asking for is essentially the the so-called Feedback arc set problem, so finding the minimum necessary edges to be removed from the graph induced by the FK constraints is NP hard. There are effcient algorithms mentioned in that Wikipedia article, which don't guarantee to find the minimum number of edges, but might be enough for your case.

However, from a practical point of view, unless you want to use your migration tool for hundreds of arbitrary data models, I would consider to go a simpler route (maybe as a first step). You can still create a generic migration tool which gets the "foreign keys for deferred migration" (or in terms of a digraph: the edges to be removed to break the cycles) as input. Then, one can take a diagram of a real data model, identify the cycles manually and decide manually about the foreign keys to pick for breaking the cycles. Such a tool can be used in production, even when it does not do anything automatic.

Later, if you then still think you really need that, you could implement an auto-detection algorithm for the FKs, using the reference from above.

  • Not that you need it, but I'm going to start up a bounty for this answer: it is exactly the information I needed to get this done. I had an idea in mind, and this confirms it as the best course of action. While I have to verify this, I believe that the cost of breaking edges (i.e. deferring FK creation to later) is very minimal. With FK checks off, I think the performance hit of two alters will be small. As a result, the trick is not to do this smarter, but rather to do this dumber-er. – Conor Mancone Nov 25 '17 at 16:46
  • If I limit the "tree" depth to one level and break any edges that create a dependency with a dependency, then I can easily ensure that there are no cycles. It will get the job done with a minimal performance hit, and this way I don't have to venture into an NP-hard problem set. Nothing good ever comes out of that. I may go ahead and implement the manual step in the future anyway: especially if the performance hit becomes a problem for very large databases. I may roll in J_H's answer and come up with some different and selectable migration options. Gonna start with automatic though. – Conor Mancone Nov 25 '17 at 16:50

Why is this even needed? If constraint validation is deferred until commit, the ordering of DML operations will not matter.

  • Due to above comments, I've been beta testing this for a while with unordered alters and checks off. Turns out this isn't a complete answer though. There are a small number of edge cases where MySQL will throw a 1215 error even when FK checks are off. – Conor Mancone Nov 25 '17 at 12:11
  • Isn't that a bug, then? – James Youngman Dec 27 '17 at 9:47
  • In MySQL? I doubt it. For details, the example we encountered is that if you try to add a FK constraint to a column which does not match, MySQL will throw a 1215 with FK checks off. As a real-world example, one of our developers added a table and forgot to add a FK check to the parent table. They also had a slightly difference between the parent and child table: the parent table had a signed integer for the id and the child table had an unsigned integer for the id column for the FK relationship. They missed the difference because they forgot to add the FK too. – Conor Mancone Dec 27 '17 at 13:34
  • Fixing it was therefore a two step process: change the parent table to have an unsigned id (which is our standard anyway), and add the FK to the child table. However, even with FK checks off, MySQL would refuse to add the FK until the column definitions of child and parent table match. While this is an uncommon edge case (and also caused by developer error), it is also obviously a real-world edge case, and a case in which ordering matters even when FK checks are off. Moreover, I can see cases where the same problem might be encountered even without developer mistakes. – Conor Mancone Dec 27 '17 at 13:36
  • @ConorMancone That edge case about a different data type on the reference column is orthogonal to your goals. It's a good thing that the database engine wouldn't allow creation, because any foreign key index between different datatypes would need (poor performing) implicit casting, or in the case of int vs uint there is no obvious coercion so fail. The checks are for actual data values, not for metadata issues like type-mismatch. Sure a different tool to ensure type consistency is useful, however deferring FK creation until after tables, but before data is migrated is perfectly cromulent. – Davos May 10 at 13:12

The backend optimizer has several access paths available to it, and a model for how many seconds each path will add to elapsed query time. It searches a graph looking for plans with estimated cost lower than the current best estimate.

As I read your paragraphs, it sounds like an analogous situation to me. The comments point out that there's more than one way to deal with table FOO. We might create empty FOO1, adjust FOO1's constraints and indexes, (slowly) insert into FOO1, and drop FOO followed by rename of FOO1. Different "equivalent" approaches might win for small or big tables.

If your code knows the row counts and has a model for operation completion times, it could explore many alternatives, including ones in the comments, and defend its final course of action based on operation time comparisons.

If a given migration will include both change in constraints and change (increase) in number of rows, disable FK / insert / enable FK may turn out to be winning.

  • That's a great idea in general that I hadn't considered. I don't have time for it right now though: will probably leave it for a big v2.0 update. – Conor Mancone Nov 25 '17 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.