Need help with complex mysql pagination query logic

Question

Ok at this point, I am pretty confused on how to construct my pagination system in an efficient manner. The problem is that the system is not typical and does not go in regular intervals such as 10 per page. The problem is, messages can have replies and thus share the same reply_chunk_id (reply_id). I do not want messages to get cut off but it is seeming increasingly complex to do so.

My initial query to retrieve message is this and it retrieves messages as a grouping no matter where a reply is in the table, it will come out grouped with its corresponding messages with the same reply_chunk_id one after another in descending order based on timestamp

SELECT m.timestamp, m.user, m.message, g.grp_timestamp,m.reply_chunk_id
  FROM shoutbox AS m JOIN
       (SELECT reply_chunk_id, MIN(timestamp) AS grp_timestamp
          FROM shoutbox
         GROUP BY reply_chunk_id) AS g ON m.reply_chunk_id = g.reply_chunk_id
 WHERE m.topic_id = ? 
 ORDER BY g.grp_timestamp DESC, g.reply_chunk_id, m.timestamp DESC limit ?, ?

I was thinking that I would need another query to retrieve the limit parameters for this query since the pages do not go in regular intervals and thus need unique starting and ending points depending on what page you have selected. I was thinking of picking a limit say $limit of 10 just as an example, and then going to the nearest rounded number of messages over that. So for example, if you got to the 10th message and there were 2 more replies for that group, you would retrieve 12 messages.

The trouble I am having is with the logic of constructing this limit retrieving query. I would have to somehow start at the first message in that topic, count all replies for it, go to the second, count all replies until the rounded number is reached and then output it.

The real trouble comes when say you want to change the page, how would you transfer over the ending point of the previous page, or maybe you skip a page and go straight from 1-3rd page. The answer is you cannot so you would have to start from the first message for that topic each time, count all replies, move on and do the same for each message until you reach your rounded number, somehow indicate you have passed the first page, and move on until you get to the page messages you desire. I am really not sure how to do this, or if this is the best way so any help or advice whatsoever is really appreciated.

TABLE DESIGN

CREATE TABLE IF NOT EXISTS `shoutbox` (
  `id` int(5) NOT NULL AUTO_INCREMENT,
  `timestamp` int(11) NOT NULL,
  `user` varchar(25) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL 
         DEFAULT 'anonimous',
  `message` varchar(2000) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
  `topic_id` varchar(35) NOT NULL,
  `reply_chunk_id` varchar(35) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=7 ;

Answer 1

edit: got some time to test, new checked single query solution

SELECT timestamp, user, message, grp_timestamp,reply_chunk_id
FROM (
  SELECT totalresult.*,
    @page := IF(
        (
          @subcounter >= @perpage                    -- if we have more then @perpage
          AND
          reply_chunk_id != @old_chunk_id            -- AND we are on a reply_chunk border
        )
        OR
        (
          @subcounter >= @absolutemax                -- the upper maximum is reached
        )
        OR 
        (
          (@subcounter + grp_messagecount > @absolutemax) -- next replychunk would put us over the top
          AND 
          (grp_messagecount <= @absolutemax)              -- next replyhunk would fit in a single pagenumber
          AND
          (@subcounter >= @allowprematurebreak)           -- and we have enough items to qualify for a page
        ),
      @page + 1 + (@subcounter:=0),                 -- increment page and reset counter
      @page) as page,                               -- otherwise keep the same @page
    @subcounter := @subcounter + 1      as counter, -- increment counter
    @old_chunk_id := reply_chunk_id as reply_chunk  -- store previous reply chunk
  FROM (
    SELECT 
        m.timestamp, m.user, m.message, g.grp_timestamp,m.reply_chunk_id, g.grp_messagecount
    FROM shoutbox AS m
    JOIN (
          SELECT
            reply_chunk_id,
            MIN(timestamp) AS grp_timestamp,
            COUNT(*)       AS grp_messagecount
          FROM shoutbox
          GROUP BY reply_chunk_id
    ) AS g ON m.reply_chunk_id = g.reply_chunk_id
    WHERE m.topic_id = ? 
    ORDER BY g.grp_timestamp DESC, g.reply_chunk_id, m.timestamp DESC
  ) AS totalresult
  JOIN (
    SELECT
      @page                :=0,  -- the page number / counter
      @old_chunck_id       :=0,  -- placeholder for old reply_chunk so we can detect boundaries
      @subcounter          :=0,  -- counter for number of actual messages
      @perpage             :=10, -- preferred amount of messages per page
      @absolutemax         :=20, -- allow breaking in reply_chunk if absolutemax is reached
      @allowprematurebreak :=5   -- minimum of messages per page, used if we can let the 
                                 -- next chunk see whole on the next page
  ) AS void
) AS paginatedresult
WHERE page = <pagenumber>

I've added some settings as variables, for easy & somewhat more readable binding of parameters. About performace: benchmark it, chances are it does fine (certainly as it's restricted on the basis of topic). If it doesn't, your solution would to get the output of this inner subquery:

          SELECT
            reply_chunk_id,
            MIN(timestamp) AS grp_timestamp,
            COUNT(*)       AS grp_messagecount
          FROM shoutbox
          GROUP BY reply_chunk_id

And move the logic of determining where to break into some script logic which decides which reply_chunk_id's to query for.