Comment by vvern

Some time ago I worked on cockroachdb and I was working on implementing planning for complex online schema changes.

We really wanted a model that could convincingly handle and reasonably schedule arbitrary combinations of schema change statements that are valid in Postgres. Unlike mysql postgres offers transactional schema changes. Unlike Postgres, cockroach strives to implement online schema changes in a protocol inspired by f1 [0]. Also, you want to make sure you can safely roll back (until you’ve reached the point where you know it can’t fail, then only metadata updates are allowed).

The model we came up with was to decompose all things that can possibly change into “elements” [1] and each element had a schedule of state transitions that move the element through a sequence of states from public to absent or vice versa [2]. Each state transitions has operations [3].

Anyway, you end up wanting to define rules that say that certain element states have to be entered before other if the elements are related in some way. Or perhaps some transitions should happen at the same time. To express these rules I created a little datalog-like framework I called rel [4]. This lets you embed in go a rules engine that then you can add indexes to so that you can have sufficiently efficient implementation and know that all your lookups are indexed statically. You write the rules in Go [5]. To be honest it could be more ergonomic.

The rules are written in Go but for testing and visibility they produce a datomic-inspired format [6]. There’s a lot of rules now!

The internal implementation isn’t too far off from the search implementation presented here [7]. Here’s unify [8]. The thing has some indexes and index selection for acceleration. It also has inverted indexes for set containment queries.

It was fun to make a little embedded logic language and to have had a reason to!