Implementing State Machines in PostgreSQL

Another interesting idea is to implement applications in SQLite3 (all local). IIRC libgda (GNOME GDA) uses SQLite3 to drive LDAP and other protocols.

This will get much easier to do now with the new "pointer passing interface" in SQLite3 3.20.0 (http://sqlite.org/bindptr.html).

I'm not recommend this, nor against this. Just observing that it's a legitimate design pattern.

> If ever you decide you want to migrate away from Postgres, you'll need to rewrite all the business logic into some other out of process language.

Of you follow this rule you'll never be able to use the most powerful features of postgres.

> If ever you want to scale this, such that you want to calculate states in batches, you'd want to have the business logic somewhere else...

Not due I'm totally on board with the premise here, but the need to calculate state outside the database is a generally valid one and so it might be a good idea to write the core of the transition function in JavaScript and implement the postgres functions in PLv8.

Given the problem in the article, an accumulating snapshot table is simply the best solution for the reasons I laid out. If your actual system has different requirements in terms of storage and analysis (which apparently it does), I would be happy to hear about those and come up with an updated recommendation.

Along those same lines I'm not insisting you can't have a transaction table. If you need to record more information, like an IP address or user_id with each transition, then it would require a transaction table (although the article mentions none of this).

Honestly, the storage concerns I bring up (that is the schema) are really far less of a concern than the basic idea of storing your transitions in the database. Put simply, you are storing the wrong information. Instead of storing the actual state, you are storing a series of inputs that allows you to derive the state. This is a HUGE mistake. What if you add a new state? Say, [in_transit]. Every one of those 1 billion rows that are already in there will no longer be able to be processed correctly because they won't have the correct order of events.

This entire thing could be one table that stores the [order_id] [state] [timestamp] [is_current], with a stored procedure to update it that takes an "order_id" and "event_name". Instead, you have created a house of cards.

If you are bound to an existing database schema then there isn't much you can do (depending on how bound you are of course). That's a totally valid reason to choose your current path. I'm not naive to business requirements. Often, systems end up being far from theoretically perfect due to legacy {insert component of stack here}. I get it.

So ruling out a snapshot table (I think you have made clear this is not an option), your best choice would then be a transaction table where your [state] is a Type 2 Slowly Changing Dimension (SCD2) with an indicator field for the current state. I want to be clear here: you should be storing your state, NOT the events (arguments) that can be used to derive your state. I cannot express this enough. Your problem is not unique. You simply cannot be naive enough to think you are the first person to want store the state history of an FSM in a database. This is literally data warehousing 101. The novelty of your solution stems from the fact that you are (dangerously) misunderstanding the problem. If, for some reason, you need to store what [event_name] caused the transition to the [state], just add a field. Simple.

As for invariants. Let's use an example: say you add a "package" event that transitions to an [in_transit] state between [awaiting_shipment] and [shipped] (note here we may also then want to change "ship" to "deliver"). This simple and totally reasonable change would make every order with an event queue: "create", "pay", "ship" result in [error]. If you just stored the [state], then a [shipped] order will remain [shipped] regardless of what series of events brought it there - which would be correct. There would be no need to go back and change historical data - nor would you want to. How would that even be done? Manufacture shipping information and timestamps? There are no invariants in this process (again, I want to reiterate that this is a solved problem). True FSMs (if this is actually modeled as one) only care about the current state anyway and maybe the previous state (see SCD3). What I mean is, future actions are determined using the current state. If the current state becomes [error] for 1 billion orders, that's a problem. A huge problem.

"Absolute correctness" is an interesting term... and I agree that I am probably coming off a bit aggressive in my comments. Look, I'm not trying to be a bully here, and I DO think that the FSM you have created is interesting, unique, and a cool example of how user-defined aggregates can be used. The problem with it is, unfortunately, an extremely common one. If I had a nickle for every time a programmer jumped into the world of databases and came up with a "new" solution to a "never-before-seen" problem... I'd be a wealthy man. Relational databases have been around for a long time and are one of THE MOST studied and written about pieces of infrastructure/software in existence (they're interesting for so many reasons!). What this means is that it's EXTREMELY unlikely you have found a problem that hasn't already been "solved" (of course there can be wiggle room) in a theoretically correct manner. It's almost always just an individual not recognizing (or breaking down) the problem efficiently.

And that's what I am seeing here: a problem that is present and handled in LOTS of databases (I've personally done this dozens of times), but is being approached from a less-than-perfect (albeit unique) angle. I can't say that I'm "absolutely correct"... I don't have the full grasp of your domain and business requirements. I don't know precisely the degree of constraint your schema is imposing. I don't know how well communication between teams and management of your stack is handled (yes, these can be important - you did mention you had problems in these areas). Maybe yours really is the best solution - though I remain unconvinced. But I can say, that given what I know about the problem, the entity relational model, database design, and data warehousing that your solution is simply not sound. It's difficult to put that nicely. I don't mean that your wrong (apparently this is working for you). It's not black and white. Just that if one of my clients came to me with similar requirements, I would follow "the book", because this has already been written.

Here's what I'd do (SCD6):

    Order [OrderId] ... [additional data]

    OrderStateHistory [OrderStateId] [OrderId] [TransitionTimestamp] [PreviousStateName] [EventName] [StateName] [IsCurrent] ... [additional data] 

And if you want a transitions table for your FSM to enforce explicit constraints (I don't recommend this, but it's MUCH better than hiding this data in a function/trigger):

    OrderTransition [CurrentStateName] [EventName] [NextStateName]
    

You can figure out the keying/substitutions. Then use a simple stored procedure:

order_state_history_tr @current_state_name, @event_name -- note this the PK of OrderTransition

to facilitate transitions. This stores BOTH the transitions and the state.

If you ever decide you want to migrate away from Postgres, it's because there's another platform that supports significant functionality that Postgres doesn't. Changing out the data tier is not a decision made on a whim.

If there is significant functionality we want to take advantage of in this new platform, then that means that we have to refactor anyway to use this, because by definition we either don't do it today, or we do it with an insufficient workaround in Postgres.

The migration necessitates large refactoring by its very justification.