State Machines in SQL

State machines are a powerful tool for modeling complex systems. They can be used to model everything from simple workflows to complex business processes. In this post, we’ll explore how to implement a state machine in SQL.

The basic idea behind a state machine is that an object can exist in one of a finite number of states, and transitions between states are triggered by events. For example, a simple state machine might model the lifecycle of a blog post, with states like “draft”, “published”, and “archived”. Transitions between states might be triggered by events like “publish” or “archive”.

The naive approach to implementing a state machine in SQL is to use a column in a table to represent the current state of an object. For example, you might have a state column in a blog_post table that stores the current state of a blog post. You could then write queries that update the state column to transition the blog post between states.

UPDATE blog_post
SET state = 'published'
WHERE id = 123;

However, this approach has a number of drawbacks. For one, it’s difficult to enforce constraints on the state transitions. For example, you might want to prevent a blog post from being published if it’s in the “archived” state. With the naive approach, you would have to write application-level code to enforce these constraints, which can be error-prone and difficult to maintain. A limited number of states and transitions can be enforced with a CHECK constraint or through using enums, but this quickly becomes unwieldy as the state machine grows in complexity. States cannot be updated on the fly, and you would have to update the application code to add new states or transitions.

Furthermore, keeping a history of state transitions is difficult with the naive approach. You might want to be able to answer questions like “when was this blog post published?” or “how many times has this blog post been archived?“. With the naive approach, you would have to write additional application-level code to keep track of this information. Please, no database triggers.

A better approach is to model the state machine explicitly in the database. You can do this by creating a separate table to represent the states and transitions of the state machine. For example, you might have a state table that stores the possible states of a blog post, and a transition table that stores the possible transitions between states.

CREATE TABLE state (
  id SERIAL PRIMARY KEY,
  name TEXT NOT NULL
);

CREATE TABLE transition (
  id SERIAL PRIMARY KEY,
  from_state INTEGER REFERENCES state(id),
  to_state INTEGER REFERENCES state(id),
  event TEXT NOT NULL
);

CREATE TABLE state_change (
  id SERIAL PRIMARY KEY,
  post_id INTEGER REFERENCES blog_post(id),
  from_state INTEGER REFERENCES state(id),
  to_state INTEGER REFERENCES state(id),
  transition_id INTEGER REFERENCES transition(id),
  created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

You may be asking why we keep the from_state and to_state columns in the state_changes table while we already have the transition_id column. I’ve found that it’s useful to provide an escape hatch here for overriding the transition logic. For example, you might want to allow an admin user to manually transition a blog post between states, even if the transition is not allowed by the state machine. The transition_id column is therefore for contextualising the transition, especially in cases where multiple transitions are possible between two states.

Most commonly, you’ll want to get the current state of an object from the database. You can do this by selecting the most recent state change for the object from the state_changes table using PostgreSQL’s DISTINCT ON clause.

SELECT DISTINCT ON (post_id) to_state
FROM state_changes
WHERE post_id = 123
ORDER BY post_id, created_at DESC;

This operation is so common that you might want to encapsulate it in a view or a stored procedure. This means you can easily join the state_changes table with other tables to get the current state of an object.

CREATE VIEW current_state AS
SELECT DISTINCT ON (post_id) post_id, to_state
FROM state_change
ORDER BY post_id, created_at DESC;

SELECT blog_post.*,
  transition.event,
  state.name AS state
FROM blog_post
JOIN current_state ON blog_post.id = current_state.post_id
JOIN state ON current_state.to_state = state.id
JOIN transition ON current_state.transition_id = transition.id;

This returns the current state of each blog post, along with the event that triggered the transition and the name of the state. You can use this information to build powerful queries that answer questions about the state of your objects while retaining full context of the transitions. States can be updated on the fly by adding new rows to the state and transition tables, and multiple state machines can be modelled by adding a machine_id column to the state table. This allows you to model complex systems with multiple state machines which are configurable by the user, without having to change the application code.