Help with threaded forum / SQL

GameMusic

I'm trying to make a PHP / MySQL message board that supports both topic layouts (like this one) and tree layouts (like Slashdot, WWWBoard). The topic part was easy, but the tree could be much tougher. The most direct approach would be a recursive function that retrieves replies to a post and then repeats this for each reply, but on a large forum this could turn into a TON of SQL statements.

What would be the most efficient way to do a tree forum in SQL? Are there any examples/tutorials out there? Is there some SQL syntax that might mimic the recursive behavior of the function I described?

tha_mink

Yeah...look up join syntax in the mysql manual. That is the real power of the relational database.

tha_mink

GameMusic

I have a very rudimentary knowledge of JOINs, but I don't understand how they would solve this. I need to take a post ID (since it should be possible to click on any post and see replies to it) and find not only replies to it, but replies to them and so on for an arbitrary number of levels, preferably in a single statement.

For example, if I'm looking at a post with id 1, then this:

SELECT DISTINCT t1.* FROM boardposts t1 LEFT JOIN boardposts t2 ON t2.replyTo = 1 WHERE t1.replyTo = t2.id OR t1.replyTo = 1 OR t1.id = 1

retrieves the post and replies for 2 levels, but not 3 or more.

I did a ton of searching on Google and found http://www.faqchest.com/prgm/php-l/php-02/php-0201/php-020105/php02010315_21785.html which is a response to someone else who had exactly the same issue. The PHP-based fix described there will work for a single thread, but not individual replies. Is anyone here familiar with the tree/graph building method that this person mentioned?

TalonFinsky

Just a guess, but would it be easier to have a table with an individual id for each top level post, and for each of those, have it create a table where each reply has it's own unique id? You would then just use simple loops to list all the replies to each topic in tree order.

Just a thought, as I haven't put much time into database design for a web forum.

leatherback

Hi
--Don't get excited: I have no easy answer --
I am trying (Or more: Thinking about) tackling the same problem. I am thinking along the line of:
(And do not look at the actual coding: THere are many errors in it. Look at the idea behind the code. I think it should work, after putting in the final details. I can't work on this for the next few days, but will continue looking at it this weekend. So if you want, we can work on it together then?

Use a parentID and thread ID per message

For a complete tree: Select all "thread starters:
- Select * from messages where parentID = 0

Query all unique parent ID's per Thread ID (this gives you an idea of the number of levels needed)
- $levels = mysql_query("Select * from messages where parentID = $row[id] ParentID unique");

Loop, using mysql_num_rows($levels) as a number for the relooping
$x=1
while ( $x <= $levels)
{something, $x ++}

Query individual responces to a message at a certain level

select * frome messages where ParentID = $x and $ThreadID = $row[ID]

Let me know how you solve it, if you have an other (Better!) idea? (Although I am confident this should be able to run properly..

Pests

Okay, here is my code. It does everything except link the topics and it does not seperate the topics from eachother, usualy a <hr> does this, but mine doesnt. Feel free to use it.

<?php

$myhost = "localhost";
$dbname = "***";
$fuser = "***";
$fpass = "***";
$fname = "pf_topic";
$db = mysql_connect($myhost,$fuser,$fpass);
mysql_select_db($dbname,$db);

function DisplayThread($num)
{

GLOBAL $db, $fname;

$result = mysql_query("SELECT * FROM $fname WHERE parent_id = $num ORDER BY date",$db);

if (mysql_num_rows($result))
{




while($myrow = mysql_fetch_array($result))
{

$data .= "<ul><li>".$myrow[topic]."-by ".$myrow[poster]." on ".$myrow[date]." at Remote Host";
$data .= DisplayThread($myrow[id]);
$data .= "</li></ul>";

}



}

return $data;

}


echo DisplayThread(0);
?>

Table pf_topic struct:
id
parent_id
topic
date

What it does is find all posts with the same parent_id as $num. Kinda hard for ME to explain, you figure it out.

leatherback

Hi,

Yeah Pests, that looks very nice, and would work to get just all the replies to a specific message. But that part is not too hard to come up with. (the thing you are doing is exactly the same as the last statement in the rough idea I posted last night.)

You would not however get a recursive tree structure. You would have to program this SQL query for each level of the tree (Since you need to get the parent_id for each level you want to find the childs of. )

The whole idea was to avoid having to build a thousand queries for larger trees..

Or am I missing something?

Pests

Yes you would make a recursive tree structure. Since the function calls itself with the new id inside of the function, then the function will look for replys to that, ect. Here:

    $data .= "<ul><li>".$myrow[topic]."-by ".$myrow[poster]." on ".$myrow[date]." at Remote Host";
    $data .= DisplayThread($myrow[id]); //GETS REPLYS!!!!
    $data .= "</li></ul>";

Note the comment i added.
It will get every reply to every message. http://www.flatface.net/~pests/junk/f.php is an example of this exact code in work. THIS DOES NOT WORK RIGHT NOW! Flatface's mysql is down atm, should be up friday, but when it is, it should work.

leatherback

Aaahh!

Yes! Overlooked the nested function! (Was it the short night?)
Excelent solution. I'll try it as soon as I get home at a decent time!

Thanks!

GameMusic

Nice, but it runs into a problem - it has to run a query for every post, and if you're dealing with a large thread...

Still, it ran fairly quickly when I tried it on my test forum, which currently has 35 posts. I would probably make a maximum number of replies to show per thread somewhere around 50-100, so the slowdown might not be too bad, but I want to prevent the server from being bogged down.

Here are a few ideas:

At the cost of increasing the amount of space used to store each post, I could include a "replied to" flag with each one. If it's 1, then DisplayThread is called for that post. This would reduce the number of queries by however many "end" posts there are. (Even better, I could make this flag a date - so each post would have a field showing when it was replied to.)
I'm not that familiar with MySQL optimization, so tell me if this wouldn't work well. Use this query:

SELECT DISTINCT t1.* FROM boardposts t1 LEFT JOIN boardposts t2 ON t2.replyTo = 1 WHERE t1.replyTo = t2.id OR t1.replyTo = 1 OR t1.id = 1

To get the post and first 2 levels of replies, then run it again for each reply on the 2nd level. (The PHP involved in organizing the thread would be more complex, but it is possible to do it this way.)

In order for this to be an effective optimization in all situations, this more complex query would have to be no slower than making 3 individual queries, and I'm not sure if that's the case.

This tutorial - http://reguly.net/alvaro/cic/php/PHP-MySQL-threads.html - uses a recursive method as well, but it suggests opening a permanent connection to the database. I haven't tested yet how much of an impact this might have on speed.

Pests

I know it could be better, but i only worked on it for 10 min. And anyways, i think it shows a good example of how to do some small thread recursion.

Also, the link you pointed out seems to be doing the same thing i am. Only thing that is different is the mysql_pconnect. What it does is open up a persistant connection to the mysql database, and if its called again, it will try to use an exsisting one. Now, that one should have 3 pages (view all the threads, replying/posting, display message). Now, mysql_pconnect helps there since its between pages, but since mine is only one page, it doesnt do much good. mysql_pconnect doesnt colse until its timed out, even if you call mysql_close, thats how it helps up speed between pages. But if i were to continue to use that code, i would definitly change it to mysql_pconnect.