Help with recursive SELECT

Question

Here's the situation. I have two tables:

• users (registered users of the website),
• messages (personal messages they sent between each other)

The messages table has these columns (just the important ones):

• id,
• sender (id of user who sent the message),
• receiver id of user to whom the message was sent),
• reply_to (id of a message to which this message is reply to, can be NULL)

What I need to do is construct a SELECT query that will select a complete conversation between 2 users. I.e. if user A replies to message sent from user B and the user B replies back to the message, I would like to get three rows like this:

• message03: reply to the message02
• message02: reply to the message01
• message01 from user A to user B

I'm sure that it is possible to construct such a SELECT query based on the reply_to field but I have never done something like it before so I need a little help.

The SELECT query should be for MySQL database.

Answer 1

Actually you're incorrect: with ANSI SQL this isn't possible. Certain databases with vendor extensions (eg Oracle's CONNECT BY) may be able to do what you want but not plain old SQL.

My advice? Change your data so enable an easier solution.

In this case, give each message a conversation_id. If the user posts a new message, give that a new (currently unused) value. If they reply, keep the conversation_id of the message being replied to.

Then querying the data becomes trivial.

Answer 2

This is the adjacency list model.

MySQL has no native way to query it, but you can use a certain hack: create a function like this:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    messages
                WHERE   reply_to = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, reply_to
                INTO    _id, _parent
                FROM    messages
                WHERE   id = _parent;
        END LOOP;
END

and use it in a query:

SELECT  CONCAT(REPEAT('    ', level - 1), CAST(hi.id AS CHAR)) AS treeitem, parent, level
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, messages
        WHERE   @id IS NOT NULL
        ) ho
JOIN    messages hi
ON      hi.id = ho.id

See this article in my blog for more detailed explanations on how it works:

• Hierarchical queries in MySQL

Only the children of the original message (whose id should be used to initialize @start_with) will be selected.

This query additionally can be filtered for the values of sender_id and receiver_id to make sure only the messages between the users are selected.

Answer 3

I would suggest adding a conversation_id field to the messages table. Each new non-reply message would have a generated conversation_id, and then each reply based on that message would use the same id. Then your query would be simple:

select * from messages where conversation_id = ? order by id asc

Answer 4

I use a technique I found in Joe Celko's SQL for Smarties book - chapter 29 on the nested set model for trees. Maintaining the data is a little ugly (insert, update, delete), but selects are very fast. The code in the book is very thorough and well explained. There is also some info on how to convert the data you have into this new model.

Answer 5

Using something like:

SELECT *
FROM [Messages] 
WHERE 
    (
        [Sender] = @Sender 
            AND [Reciever] = @Reciever
    ) OR (
        [Sender] = @Reciever 
            AND [Reciever] = @Sender)

Will get you an entire conversation history. As far as the reply_to field, I wouldn't use that because:

A) It will make it very complex to retrieve the first message of a conversation.

B) You can use other filters such as date or limit the history length to prevent a full output of every conversation the users have had.

Instead, I would add something along the lines of a ConversationId instead that would increment if there was no messages sent between users for a pre-specified length of time.

In specific answer to your question though, the following query will work, provided you can allow selection of the first message in a conversation:

SELECT * 
FROM [Messages] 
WHERE 
    (
        (
            [Sender] = @Sender 
                AND [Reciever] = @Reciever
        ) OR (
            [Sender] = @Reciever 
                AND [Reciever] = @Sender)
    )
    AND id >= @FirstMessageId
    AND id < 
        (
            SELECT TOP 1 [id] 
            FROM [Messages] 
            WHERE [id] > @FirstMessageId
                AND [reply_to] IS NULL
                AND  
                    (       
                        (
                            [Sender] = @Sender 
                                AND [Reciever] = @Reciever
                        ) OR (
                            [Sender] = @Reciever 
                                AND [Reciever] = @Sender
                        )
                    )
    )