Whence Deferrable Constraints

From Zanecorpwiki

While coding the Kibbles Tagging Module (TODO: link), which includes support for categorization, and specifically while implementing support for re-arranging categories, I'd come up with the following approach:

1. Javascript widget supports drag and drop of categories according to rules
2. as categories are moved, each move is recorded (specifically, the item moved, the emnew parent/em, and the emprevious sibling/em, which tells us the location)ref group=notesIt would be possible determine position from a single touch point, but we would then have to break out two cases: when there is a previous sibling, and when the item is the first element under a parent (or the root). To avoid the special casing, we record both bits of information./ref
3. the record of movements is then played back to the service call, which updates the data model

The category table looks like this:ref group=notesThe table and other examples have been somewhat simplified to remove fields that are not important to the story./ref

pre

CREATE TABLE dogfood.category (

id INT, parent INT, name VARCHAR(64) NOT NULL, ordering INT NOT NULL, PRIMARY KEY (id), CONSTRAINT unique_order UNIQUE (parent, ordering), FOREIGN KEY (parent) REFERENCES category (id)

);

/pre

The important thing to note is that an elements position is determined by parent+ordering. The first pass at the move code implemented the following algorithm:

1. start transaction
2. remove the moved element from original position; shift all elements with same original parent as the moved element down
3. make room for moved element in new position; shift all elements occurring after the emprevious sibling/em under the emnew parent/em up
4. insert moved element in new position; update its parent and ordering
5. commit

The key calls where:

UPDATE dogfood.category SET ordering=ordering-1 WHERE parent=lt;old parentgt; AND orderinglt;old positiongt;;
UPDATE dogfood.category SET ordering=ordering+1 WHERE parent=lt;new parentgt; AND ordering=lt;new positiongt;;
UPDATE dogfood.category SET parent=lt;new parentgt;, ordering=lt;new positiongt; WHERE id=lt;category IDgt;;

Didn't work. After a little debugging, I realized that my implicit assumption that constraints were not checked until after a transaction was committedref group=notesFrom a user/functional standpoint, I am even more convinced that deferring constraint checks--at least by default--is the right way to go. From an implementation perspective, I understand that this is hard and that overall speed considerations, etc. may make the current behavior the best compromise./ref was no good. Constraints were being checked within the transaction, and as items were being shifted around categories to occupy the same position, even if just temporarily.

My first fix was to try and move the category to be moved out of the way (by setting ordering to -1), then shift everything to it's place. I thought that if maybe constraints were checked within a transaction, maybe they wouldn't be checked within a statement. I.e., even though the shift statements might cause two rows to temporarily occupy the same space while the statement was executing, by the time the statement was done, it would be fine.

This appeared to work at first. I did rather extensive testing, no problem. However, when I excitedly called my wife to see what I'd done, it immediately broke. I'm guessing that I was just lucky in the order that the row updates were being done at first, and that nothing was bumping into each other. During the demo, my luck ran out.

Back to the drawing board.

I researched deferrable constraints. Luckily, that's the exact phrase; both SQL and Postgres support the idea. Unluckily, at the end of the discussion of deferrable constraints, the Postgres documentation notes that they are not supported in the general case.ref group=notesIn fact, no free database does. It's on the Postgres TODO list and MySQL has no support or plans at all as far as I can tell./ref

My first thought was to try and disable constraint checking. This can be done for triggers (and possibly some constraints) but testing revealed it could not be done for unique constraints. Dropping and re-adading the constraint for every move was out of the question. It would be worse than moving each category individually.

I was beginning to get nervous. I was behind and a complete re-write of the algorithm would add even more time. Turning off constraint checking is simply not an option. It would be fastest both for me and for the application, but could lead to shifting garbage.ref group=notesWithout constraints, one can easily end up with garbage data. The DB then becomes useless because what it says makes no sense. No matter how fast you move the garbage around, it's still garbage and you end up doing no useful work./ref However, I was looking at potentially long running times since without any other recourse, the best option would be to move each effected category individually. This would lead to a theoretical running time of O(n) rather than O(1), and could practically add many seconds, or even minutes user requests.

Punchline: postgres does support deferrable constraint checks in one case: the foreign key constraint. This gave me a hole to squeeze through:

1. start transaction
2. move the item to be moved out of the way by setting ordering to -1
3. shift all elements with same original parent as the moved element down emand change the parent at the same time/em
4. change the parent of the shifted elements back to the proper parent
5. shift all elements occurring after the emprevious sibling/em under the emnew parent/em up emand change the parent at the same time/em
6. change the parent of the shifted elements back to the proper parent
7. insert moved element in new position; update its parent and ordering
8. commit

The key calls where:

UPDATE dogfood.category SET ordering=-1 WHERE id=lt;category IDgt;;
UPDATE dogfood.category SET ordering=ordering-1, parent=-1 WHERE parent=lt;old parentgt; AND orderinglt;old positiongt;;
UPDATE dogfood.category SET parent=lt;original parentgt; WHERE parent=-1;
UPDATE dogfood.category SET ordering=ordering+1, parent=-1 WHERE parent=lt;new parentgt; AND ordering=lt;new positiongt;;
UPDATE dogfood.category SET parent=lt;original parentgt; WHERE parent=-1;
UPDATE dogfood.category SET parent=lt;new parentgt;, ordering=lt;new positiongt; WHERE id=lt;category IDgt;;

Because the parent can be invalid within the transaction of the context, I could use the fake parent ID to move the shifting categories someplace where they would not conflict with the unique parent/ordering constraint. Then once everyone had been moved and was properly ordered, they could be popped back to the correct parent. To make this happen, the constraint declaration in the table was modified as well:

FOREIGN KEY (parent) REFERENCES category (id) DEFERRABLE INITIALLY DEFERRED

Which says that the constraint is deferrable (to the end of a transaction) and should be deferred by default (initially deferred).

A little more debugging to fix the code, and viola, that worked. I shudder to think what would have happened had postgres not had some implementation for deferrable constraints. It would be do-able, but much less elegant. As it is, the basic approach was maintained, just needed to add a few steps to work around limitations in the postgres SQL implementation.

I really look forward to the day that all constraints are deferrable. Still, Postgres managed to have just enough to allow me to get what was most important--constant number of database per calls while maintaining proper integrity. This is now my best example as to why developers should prefer Postgres to MySQL. If I'd been using MySQLref group=notesThat's MySQL with a DB engine that supported constraint checking. MySQL's default behavior of silently ignoring constraints is absolutely baffling. See previous note on shifting garbage./ref the only viable option would be to move each effected category individually, which was discussed before and would lead to potentially unacceptable running times.

Notes

references group=notes /