Modelling Conversations, Branches and Edits

A chat history looks like a list until the first time a user edits a message or asks for a different answer. Then it is a tree, and a schema that assumed a list has to destroy history to represent it. Model it as a tree from the start and every operation — edit, regenerate, branch, switch — is an insert, and nothing is ever overwritten.

Why it is a tree

Three ordinary product features are all the same operation, and none of them fits a list.

• Edit and resubmit. The user changes their third message and sends it again. The original third message and everything after it still exist — the user may want to go back — so the edit is a second child of the second message, not a replacement of the third.
• Regenerate. The user asks for another answer to the same question. That is a second child of the same user message. The interface shows “2 / 3” with arrows, which is a sibling navigator over a tree node.
• Several models at once. One question, four replies, and the user continues from whichever they prefer. Four children of one node, three of which become dead branches.

A list schema handles all three by deleting: the edit overwrites, the regenerate replaces, the alternatives are discarded. Users notice. “Where did my other answer go” is the bug report, and it is unfixable without changing the schema.

Three schemas

Flat list with a sequence number

CREATE TABLE messages (
  id              bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  conversation_id uuid NOT NULL,
  seq             int  NOT NULL,
  role            text NOT NULL,
  content         text NOT NULL,
  UNIQUE (conversation_id, seq)
);

One index scan renders a conversation, and it is the right schema when the product genuinely has no branching — a support transcript, a log of a completed run. It cannot represent an edit without destroying the original, and no amount of application code fixes that.

Parent pointer

CREATE TABLE messages (
  id              bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  conversation_id uuid   NOT NULL,
  parent_id       bigint REFERENCES messages(id),   -- NULL at the root
  role            text   NOT NULL,
  content         text   NOT NULL,
  created_at      timestamptz NOT NULL DEFAULT now()
);
CREATE INDEX messages_parent_idx ON messages (parent_id, created_at);

Correct, minimal, and every write is an insert. The cost is reading: rendering the current thread means walking from the leaf to the root, which is a recursive CTE and one index lookup per message. At forty messages that is forty round trips inside one query — fine, but it is the query you run on every page load.

Parent pointer plus materialised ancestor path

CREATE TABLE messages (
  id              bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  conversation_id uuid   NOT NULL,
  parent_id       bigint REFERENCES messages(id),
  path            bigint[] NOT NULL,     -- ancestors, root first, ending in id
  depth           int    NOT NULL,
  role            text   NOT NULL,
  content         text   NOT NULL,
  model           text,                  -- which model produced an assistant turn
  input_tokens    int,
  output_tokens   int,
  created_at      timestamptz NOT NULL DEFAULT now()
);

CREATE TABLE conversations (
  id           uuid PRIMARY KEY,
  tenant_id    uuid NOT NULL,
  user_id      uuid NOT NULL,
  title        text,
  head_id      bigint REFERENCES messages(id),   -- the currently displayed leaf
  created_at   timestamptz NOT NULL DEFAULT now(),
  updated_at   timestamptz NOT NULL DEFAULT now()
);

CREATE INDEX messages_conv_idx   ON messages (conversation_id, created_at);
CREATE INDEX messages_parent_idx ON messages (parent_id, created_at);

The path column holds every ancestor id, root first, ending with the row’s own id. It is written once at insert as parent.path || new_id and never updated, because a message is never re-parented. That immutability is what makes a materialised path safe here when it is a maintenance problem in most hierarchies.

The ancestor path, and what it buys

Rendering the current thread stops being a traversal and becomes a single indexed lookup:

-- With the parent-pointer schema: recursive, one lookup per message.
WITH RECURSIVE thread AS (
  SELECT * FROM messages WHERE id = $head
  UNION ALL
  SELECT m.* FROM messages m JOIN thread t ON m.id = t.parent_id
)
SELECT * FROM thread ORDER BY id;

-- With the path: one index scan, no recursion, at any depth.
SELECT m.*
FROM messages m
WHERE m.id = ANY((SELECT path FROM messages WHERE id = $head))
ORDER BY m.depth;

The insert that maintains it, in one statement:

INSERT INTO messages (conversation_id, parent_id, path, depth, role, content)
SELECT $conv, p.id, p.path || currval(pg_get_serial_sequence('messages','id')),
       p.depth + 1, $role, $content
FROM messages p WHERE p.id = $parent;

-- Cleaner, and what to use in practice: two statements in one
-- transaction, avoiding the sequence dance.
WITH new_row AS (
  INSERT INTO messages (conversation_id, parent_id, path, depth, role, content)
  SELECT $conv, p.id, ARRAY[]::bigint[], p.depth + 1, $role, $content
  FROM messages p WHERE p.id = $parent
  RETURNING id, parent_id
)
UPDATE messages m
SET path = (SELECT p.path FROM messages p WHERE p.id = n.parent_id) || m.id
FROM new_row n WHERE m.id = n.id
RETURNING m.id, m.path;

The cost is one extra column of a few hundred bytes on a deep thread, and one small update per insert. The benefit is that every read path in the product becomes a single index scan, at any depth, forever.

The five queries

-- 1. Render the current thread. One index scan.
SELECT m.id, m.role, m.content, m.model
FROM messages m
WHERE m.id = ANY((SELECT path FROM messages WHERE id = $head))
ORDER BY m.depth;

-- 2. Siblings of a message, for the "2 / 3" branch switcher.
SELECT id, created_at, model,
       row_number() OVER (ORDER BY created_at) AS variant
FROM messages
WHERE parent_id = (SELECT parent_id FROM messages WHERE id = $msg)
ORDER BY created_at;

-- 3. Switch branch. One update; nothing is deleted, ever.
UPDATE conversations SET head_id = $new_leaf, updated_at = now()
WHERE id = $conv;

-- 4. Token cost of the context this thread will send — the number
--    that decides when to compact.
SELECT sum(coalesce(input_tokens, 0) + coalesce(output_tokens, 0)) AS thread_tokens
FROM messages
WHERE id = ANY((SELECT path FROM messages WHERE id = $head));

-- 5. Orphaned branches: everything in the conversation that is not
--    on the current path. What a "clean up" feature would delete.
SELECT m.id, m.created_at, length(m.content) AS chars
FROM messages m
WHERE m.conversation_id = $conv
  AND NOT (m.id = ANY((SELECT path FROM messages WHERE id = $head)))
ORDER BY m.created_at;

Query 4 is the one that repays the schema fastest. The prompt you send is the current path, not the conversation, so the token count that matters is a sum over the path — and with a list schema you would be summing over messages that are not being sent. Getting this wrong makes your token budget calculations quietly pessimistic and your compaction fire too early.

Several models answering one question

When one question is sent to several models, the four replies are four children of the same user message, and the interface wants to group them. A turn identifier does that without changing the tree:

ALTER TABLE messages ADD COLUMN turn_id uuid;
CREATE INDEX messages_turn_idx ON messages (conversation_id, turn_id);

-- All replies in one turn, side by side.
SELECT id, model, content, output_tokens
FROM messages
WHERE turn_id = $turn
ORDER BY model;

turn_id is nullable and older rows leave it NULL, which readers should treat as “this reply stands alone”. That is the migration-friendly shape: a new column that is null for history and meaningful going forward, with no backfill required and no change to how existing conversations render.

Continuing from one of the four is just setting head_id to that message. The other three remain as branches — still visible, still costed, still there if the user changes their mind. Nothing was deleted to make the choice.

Keeping it from growing forever

A tree that never deletes grows without bound, and long conversations with heavy regeneration accumulate large amounts of text nobody will read again. Three bounded mechanisms, in the order to apply them.

1. Summarise the head of the path, do not delete it. When a thread’s token count crosses a threshold, insert a summary message as a child of the last message being summarised, and send the prompt from that point forward. The summarised messages stay in the table for display and audit; they simply stop being sent. This is context compression expressed as a schema operation.
2. Prune abandoned branches on a schedule. Query 5 above finds them. A branch not on the current path and older than ninety days is almost certainly dead; delete it in batches, and expect the storage not to come back until vacuum — the mechanics are in deletion that reaches the vector index.
3. Move attachments out of the row. An image or a PDF sent with a message is measured in megabytes; stored inline as a data URI it makes listing a conversation expensive even though nothing displays it. Separate table, keyed by message id and conversation id, with the bytes in object storage and the row holding only the reference. Denormalising the conversation id onto that table means deleting a conversation’s attachments does not require joining through messages.

What not to do: rewriting path arrays to compact them, or re-parenting messages to collapse a chain. Both make the path mutable, which removes the property the whole design rests on. If a thread is too long, summarise it forward; do not rewrite its history.

A final detail that only appears once two clients are open on the same conversation, which for a product with a web app and a mobile app is immediately. conversations.head_id is shared mutable state: two tabs each sending a message from the same leaf produce two branches, and whichever update lands second wins the head. That is not corruption — the tree is fine, both messages exist — but the first tab silently loses its place.

-- Make the head move conditionally, so a client that was looking at
-- a stale head is told rather than overwriting.
UPDATE conversations
SET head_id = $new_leaf, updated_at = now()
WHERE id = $conv AND head_id = $expected_head
RETURNING head_id;
-- Zero rows returned means somebody else moved it. Refetch the
-- thread and show the user both branches rather than guessing.

Ordering has the same shape of problem. Sorting siblings by created_at is ambiguous when two rows share a timestamp, which at microsecond resolution is rare but not impossible, and is common if you write several replies in one transaction with now() rather than clock_timestamp() — the former returns the transaction start time and is identical for every row in it. Sort by (created_at, id), and use clock_timestamp() where the real order within a transaction matters. The generated identity column is monotonic and free, so it costs nothing to make the tiebreak explicit and it removes a class of bug where the branch switcher shows variants in a different order on each load.

None of this is exotic, and that is rather the point. A conversation tree is an ordinary hierarchy with two unusual properties — it is append-only, and one path through it is privileged — and both of those make it easier to model than a general tree, not harder. The schema above is four columns more than the list version everybody writes first, and it is the difference between a product where the user can change their mind and one where they cannot.