List each message from table A with it's earliest response in table B, chronologically

I have three tables: conversations, user_messages and system_messages. Their basic structure (irrelevant columns removed for brevity) is:

create table conversations(id int generated by default as identity primary key);

create table user_messages(
   id int generated by default as identity primary key
  ,conversation_id int references conversations(id)
  ,content text
  ,created_at timestamp);

create table system_messages(
   id int generated by default as identity primary key
  ,conversation_id int references conversations(id)
  ,content text
  ,created_at timestamp);

I am trying to generate an export of "system said X" and "user responded with Y" rows for a given conversation. The issue I'm having is finding a way to ensure that the "user responded with Y" message corresponds to the chronologically next message in the conversation, following the system message. So output would look something like:

system_said	user_said
Hi!	Hello
How's it going?	I'm alright, you?
I'm good!	Nice.

Approach 1: This works, but with a poor and inefficient query, using a sub-query that references outer values.

SELECT
    content AS system_said, (
        SELECT content
        FROM user_messages
        WHERE conversation_id = sm.conversation_id AND created_at > sm.created_at
        ORDER BY created_at
        LIMIT 1
    ) AS user_said
FROM system_messages sm
WHERE sm.conversation_id = ?

Approach 2: This is where I'm stuck. I'm trying to rewrite the above more efficiently using a proper join, but I can't force the join to give me the chronologically next message, so I'm getting mixed up pairs like:

system_said user_said

Hi! Nice.

How's it going? Hello

I'm good! I'm alright, you?

Here's the query:
```
SELECT
    DISTINCT ON (sm) sm.id AS message,
    sm.content AS system_said,
    um.content AS user_said
FROM system_messages sm
JOIN (
    SELECT conversation_id, created_at, content
    FROM user_messages
    ORDER BY created_at
) um ON um.conversation_id = sm.conversation_id AND um.created_at > sm.created_at
ORDER BY sm
WHERE c.id = ?
```
(I found I had to add in DISTINCT ON () otherwise I got duplicate rows.)

system_said	user_said
Hi!	Nice.
How's it going?	Hello
I'm good!	I'm alright, you?

What's the best way to approach this?

[ EDIT ]

Clarification: messages always alternate from system message to user message to system message and so on. There would never be two messages chronologically adjacent from the same source.

Solution

Your idea with distinct on sounds good, but there are a few things you could improve:

You don't need the subquery, you can join directly.
Distinct on(sm) checks the entire record FROM system_messages sm. Since it has a primary key, distinct on(sm.id) is sufficient.
The order by you use with distinct on could use more than just the unique column. If you want the soonest response, add its timestamp: order by sm.id,um.created_at.

In a demo at db<>fiddle with 20k conversations and 200k messages in them, this takes 40ms:

SELECT
    DISTINCT ON (sm.id) sm.id AS message,
    sm.content AS system_said,
    um.content AS user_said
FROM system_messages sm
JOIN user_messages um 
   ON um.conversation_id = sm.conversation_id 
  AND um.created_at > sm.created_at
  AND sm.conversation_id = 1
ORDER BY sm.id,um.created_at;

You can also add covering indexes to speed things up with index-only scans, which reduces the exec time below 1ms:

create index on user_messages(conversation_id,created_at)
   include(content,id);
create index on system_messages(conversation_id,created_at)
   include(content,id);

With those in place, it looks like your initial idea wins performance wise, whether you push down the correlated scalar subquery down to be cross joined with, as a lateral suqbuery doing the exact same thing, or not: _{demo2 at db<>fiddle}

SELECT sm.content AS system_said,
       um.content AS user_said
FROM system_messages sm
CROSS JOIN LATERAL (
    SELECT content
    FROM   user_messages um
    WHERE um.conversation_id = sm.conversation_id 
      AND um.created_at > sm.created_at
    ORDER BY um.created_at
    LIMIT 1 ) um
WHERE sm.conversation_id = 999
ORDER BY sm.created_at;