Created
October 27, 2025 00:13
-
-
Save wlib/1be72993eab627ebff80d22ea916e36a to your computer and use it in GitHub Desktop.
Revisions
-
wlib created this gist
Oct 27, 2025 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,180 @@ create schema if not exists omdb; -- Record types have a 1:1 table to store each record in. create table if not exists omdb.types ( id text primary key, -- Table of all (checkpoint) snapshots of records for this type. snapshots text unique not null, -- Fully materialized table of latest records for this type. latest text unique not null, created_at timestamptz not null default now() ); -- Every record has a type. create table if not exists omdb.records ( id uuid primary key, "type" text not null references omdb.types(id), created_at timestamptz not null default now() ); -- All records of a given type. create index if not exists omdb_records_by_type on omdb.records("type"); -- Operations have predicates which must be true to apply the operation. -- An operation mutates one record specifially by applying a named operation -- with certain parameters on a set of affected fields of the record specified -- by the path. -- Operations may or may not commute with other operations. -- The predicates specify logical dependencies for an operation. -- Conflicts happen when other operations break a proposed operation's -- predicates. create table if not exists omdb.operations ( id bigserial primary key, predicates jsonb not null, record uuid not null references omdb.records(id), "path" jsonb not null, operation text not null, parameters jsonb not null ); -- All operations applied to a record on all branches. create index if not exists omdb_operations_by_record on omdb.operations(record); -- Commits are topologically ordered by logical time. create table if not exists omdb.commits ( id bigserial primary key, logical_time bigint not null, ts timestamptz not null default now() ); -- All commits at a topological depth (logical time). create index if not exists omdb_commits_by_logical_time on omdb.commits(logical_time); -- Commits form a DAG. create table if not exists omdb.commit_to_commit ( parent bigint not null references omdb.commits(id), child bigint not null references omdb.commits(id), primary key (parent, child) ); -- All children of a parent commit. create index if not exists omdb_commit_to_commit_by_parent on omdb.commit_to_commit(parent); -- All parents of a child commit. create index if not exists omdb_commit_to_commit_by_child on omdb.commit_to_commit(child); -- Commits contain operations. create table if not exists omdb.operation_to_commit ( operation bigint not null references omdb.operations(id) primary key, "commit" bigint not null references omdb.commits(id) ); -- All operations in a commit. create index if not exists omdb_operation_to_commit_by_commit on omdb.operation_to_commit("commit"); -- Frontiers are antichains of commits -- (no commit is an ancestor or descendant of another) -- where the commits do no conflict with each other. -- Walking the full DAG of commits and applying the operations -- constructs a consistent full state at each commit. -- A frontier view is equivalent to a merged view of those commits. -- Named frontiers. create table if not exists omdb.frontiers ( id text primary key ); -- Frontier name and commit pairs. create table if not exists omdb.frontier_commits ( frontier text not null references omdb.frontiers(id), "commit" bigint not null references omdb.commits(id), primary key (frontier, "commit") ); -- All commits at a named frontier. create index if not exists omdb_frontier_commits_by_frontier on omdb.frontier_commits(frontier); -- Only the operations operating on a given record, grouped by commit, -- by that record. create table if not exists omdb.record_wise_operations ( record uuid not null references omdb.records(id), "commit" bigint not null references omdb.commits(id), operation bigint not null references omdb.operations(id), primary key (record, "commit", operation) ); -- By record at all commits. create index if not exists omdb_record_wise_operations_by_record on omdb.record_wise_operations(record); -- By record at a specific commit. create index if not exists omdb_record_wise_operations_by_record_commit on omdb.record_wise_operations(record, "commit"); -- A DAG of those commits. create table if not exists omdb.record_wise_operations_edges ( record uuid not null references omdb.records(id), parent bigint not null references omdb.commits(id), child bigint not null references omdb.commits(id), primary key (record, parent, child) ); -- Child commits on a record by record and parent commit on that record. create index if not exists omdb_record_wise_operations_edges_by_record_parent on omdb.record_wise_operations_edges(record, parent); -- Parent commits on a record by record and child commit on that record. create index if not exists omdb_record_wise_operations_edges_by_record_child on omdb.record_wise_operations_edges(record, child); -- The utility of that is to only have to walk the specific commits and -- operations that mutate a given record to only construct that specific record. -- This can be even more efficient if we have periodic snapshots and start from -- the latest one. -- We can even record coalesced operations to skip redundancy and apply -- the coalescing recursively. -- The idea is to walk each record from the root directly with the operations -- which apply to it and record the coalesced operations from commit to commit -- if it is at most half of the sum of operation sizes. -- This is done recursively to form a sort of skip graph and once the operations -- reach a size where a record snapshot is at most half of the operations size, -- we have formed a way to construct the record at any commit along the way in -- logarithmic instead of linear time. -- Coalesced operations form a quotient DAG. create table if not exists omdb.coalesced_operations ( record uuid not null references omdb.records(id), parent bigint not null references omdb.commits(id), child bigint not null references omdb.commits(id), operation bigint not null references omdb.operations(id), primary key (record, parent, child) ); -- Operations from a parent commit to a child commit by record and parent. create index if not exists omdb_coalesced_operations_by_record_parent on omdb.coalesced_operations(record, parent); -- Operations to a child commit from a parent commit by record and child. create index if not exists omdb_coalesced_operations_by_record_child on omdb.coalesced_operations(record, child); -- Nearest snapshots (antichain) per record and commit. create table if not exists omdb.commit_snapshot_ancestors ( record uuid not null references omdb.records(id), "commit" bigint not null references omdb.commits(id), "snapshot" bigint not null references omdb.commits(id), primary key (record, "commit", "snapshot") ); -- Nearest snapshots per record and commit. create index if not exists omdb_commit_snapshot_ancestors_by_commit on omdb.commit_snapshot_ancestors(record, "commit"); -- Descendant commits per record and snapshot, up to the next snapshots. create index if not exists omdb_commit_snapshot_ancestors_by_snapshot on omdb.commit_snapshot_ancestors(record, "snapshot"); -- Record snapshots form a sort of quotient DAG. create table if not exists omdb.snapshot_to_snapshot ( record uuid not null references omdb.records(id), parent bigint not null references omdb.commits(id), child bigint not null references omdb.commits(id), primary key (record, parent, child) ); -- Child snapshots by record and parent. create index if not exists omdb_snapshot_to_snapshot_by_record_parent on omdb.snapshot_to_snapshot(record, parent); -- Parent snapshots by record and child. create index if not exists omdb_snapshot_to_snapshot_by_record_child on omdb.snapshot_to_snapshot(record, child);