[SQL] Designing a Forum

[hofan41]

Hey guys, I am trying to implement my own forum, and I am stuck on how to do this efficiently. Here is the schema that I have in mind, but feel free to change it if it isnt possible to do what I want:

[Table: Threads]
int threadID

[Table: Posts]
int threadID
int postID
date datePosted
text postText
bool isThread

Using as few queries as possible, I would like to be able to retrieve all of the most recent posts as well as their original threads they posted in (which would be the post with the same threadID that has isThread set to true). I have been thinking of a solution that only takes 2 queries:

1) Retrieve all of the most recent posts that are unique in threadID
2) Retrieve all of the posts that have the same threadID as the resulting set from step 1, but have isThread = true.

My problem is I have no idea how to do this. I have been looking at select distinct, but it seems it can only retrieve one column. Any ideas? =D

 

[piako]

first you need to design a global design where you have incorporated something like "thread title" and such

 

[mikeblas]

Using as few queries as possible, I would like to be able to retrieve all of the most recent posts as well as their original threads they posted in (which would be the post with the same threadID that has isThread set to true). I have been thinking of a solution that only takes 2 queries:

1) Retrieve all of the most recent posts that are unique in threadID

What is a unique post? What does that mean? What is a duplicate post?

Why does your model blur the difference between posts and threads? Why not model threads as a separate entity?

My problem is I have no idea how to do this. I have been looking at select distinct, but it seems it can only retrieve one column. Any ideas? =D

SELECT DISTINCT can use multiple columns. But I'm puzzled about why you think you need it. It's very expensive; it requires a sort or hash to deduplicate, and that's a blocking operation which can't be paralellized.

 

[piako]

Here's a simple idea. The problem you'll have isn't the situation with producing a accurate query. Your problem will be about if you want to involve some type of timestamping or locking. That would require you to write some type of DBMS. I don't know if most forums like phpbb or vbulletin use a DMBS? Usually there is some type of locking or batch update or timestamp which dictates how the computer applies data updates. But I can't see how that would be needed in a situation like this. I guess whoever hits submit first get the post in before the other person. You could also throw in some "group by" if you wanted.

 

[hofan41]

What is a unique post? What does that mean? What is a duplicate post?

Why does your model blur the difference between posts and threads? Why not model threads as a separate entity?

i meant the most recent posts with unique threadID's. what it means is if i want to retrieve the first page of a forum, i need to pull the most recent threads that were responded to. now if i just retrieved the most recent posts, some of those posts may be in the same thread. therefore, if i want to retrieve the 30 most recently updated threads, the posts i retrieve need to have unique thread id's.

my model blurs the difference between posts and threads because a post and thread are more or less the same thing in my opinion, its just that a thread is the very first post. think about it, a thread has a subject, text, and posted date. that's exactly the same thing as a post. that and it would be much more convenient to just have the same edit/creation code if thread/post entities were equivalent. it all just seems unnecessary to me when you could represent a thread using a boolean.

Here's a simple idea. The problem you'll have isn't the situation with producing a accurate query. Your problem will be about if you want to involve some type of timestamping or locking. That would require you to write some type of DBMS. I don't know if most forums like phpbb or vbulletin use a DMBS? Usually there is some type of locking or batch update or timestamp which dictates how the computer applies data updates. But I can't see how that would be needed in a situation like this. I guess whoever hits submit first get the post in before the other person. You could also throw in some "group by" if you wanted.

im not quite sure what you mean? locking has little to do with my problem, i took a look at the picture you provided and i know how i would view a thread, its retrieving a list of threads that have been most recently updated that's the problem. that last query in your picture attempts to solve it but its still possible to retrieve a whole page full of posts from the same thread.

 

[piako]

im not quite sure what you mean? locking has little to do with my problem, i took a look at the picture you provided and i know how i would view a thread, its retrieving a list of threads that have been most recently updated that's the problem. that last query in your picture attempts to solve it but its still possible to retrieve a whole page full of posts from the same thread.

That's why I said you can use "group by" if you want.

 

[hofan41]

That's why I said you can use "group by" if you want.

the solution only works if the thread title is stored in thread. would you know of any solution if i wanted to keep thread title in the post via subject?

 

[piako]

the solution only works if the thread title is stored in thread. would you know of any solution if i wanted to keep thread title in the post via subject?

You could do that but you wouldn't have any type of post detail when showing most recent posts. You'd only have the thread title. Also that would mean your database isn't normalized. Just means it's less efficient.

 

[hofan41]

You could do that but you wouldn't have any type of post detail when showing most recent posts. You'd only have the thread title. Also that would mean your database isn't normalized. Just means it's less efficient.

hmm, i just ran what you suggested, and here are my results:

[Table: Threads]
threadID
threadTitle

[Table: Posts]
threadID
postID
text

SELECT * FROM Threads, Posts WHERE Posts.threadID = Threads.threadID GROUP BY Threads.threadTitle ORDER BY Posts.postID DESC

If you insert two threads, insert a post in each thread, and insert one more post in either, that last post is not returned by that query, even though it has the largest postID.

I think the GROUP BY prunes out the more recent post.

 

[piako]

Thread_ID and Post_ID would need to be some type of autonumber data type. If you're trying to store the data in only the posts table you wouldn't need a separate thread table.

 

[hofan41]

Thread_ID and Post_ID would need to be some type of autonumber data type. If you're trying to store the data in only the posts table you wouldn't need a separate thread table.

they are autonumber data type. and originally the only reason i needed the separate thread table was because i didnt want to keep track of threadID's myself.

 

[mikeblas]

i meant the most recent posts with unique threadID's.

Unique in what scope?

my model blurs the difference between posts and threads because a post and thread are more or less the same thing in my opinion, its just that a thread is the very first post. think about it, a thread has a subject, text, and posted date. that's exactly the same thing as a post. that and it would be much more convenient to just have the same edit/creation code if thread/post entities were equivalent. it all just seems unnecessary to me when you could represent a thread using a boolean.

They aren't the same; if they were, you wouldn't invent the word "thread" -- you'd call them all "posts". Using a boolean to store two different entities in the same table
denormalizes your model, and is exactly what's making you write more difficult, less efficient queries.

 

[hofan41]

Unique in what scope?

? scope? i have no idea what you're asking, but ill try again to explain what i'm saying:

before i retrieve the actual thread information by looking at all the posts with isThread = TRUE, i need to know which threads were most recently updated along with who updated it so I know the order in which to display them on a page. that is the purpose of step 1, with step 2 being to retrieve the actual thread information to display.

1) Retrieve all of the most recent posts that are unique in threadID
2) Retrieve all of the posts that have the same threadID as the resulting set from step 1, but have isThread = true.

say you have three posts in the table:

post #1: hello [10:00AM] Thread 1 isThread = TRUE
post #2: hello 2 [11:00AM] Thread 2 isThread = TRUE
post #3: hello 3 [11:30AM] Thread 1 isThread = FALSE

Then in order to do step 1, you want to retrieve post #3 and post #2 in that order, while leaving out post #1 because post #3 is the most recently updated post from Thread 1.

Then once you know that the threadID of #3 is followed by the threadID of #2, you would then retrieve the first post of those threads to display the threads.

I hope this explains it to you because I have no idea what you mean by scope.

They aren't the same; if they were, you wouldn't invent the word "thread" -- you'd call them all "posts". Using a boolean to store two different entities in the same table
denormalizes your model, and is exactly what's making you write more difficult, less efficient queries.

i suppose there is a good reason for separating the two, which is why phpBB distinguishes between the two, but i just dont like the idea of having a thread entity with meta-data such as (# of posts, first post, last post) stored into it, because that would involve even more complex maintenance queries.

also, if you aren't suggesting a thread entity with that meta data, the difficult, less efficient queries would still exist, because you'd still have to search through the post table for the most recent posts with unique threadID's.

 

[doh]

Try this for an idea. Beast is open source.

http://userscripts.devjavu.com/projects/userscripts/browser/trunk/db/schema.rb?rev=320

 

[mikeblas]

? scope? i have no idea what you're asking, but ill try again to explain what i'm saying:

What I'm asking is in what scope are thread IDs unique. Sounds like you want the newest post in each thread ID; "newest" can make them unique, but of course two posts can happen at the same time -- so I want to know how you decide which one to pick. You say "all of the most recent", so maybe you want some set (like, since last visit).

but i just dont like the idea of having a thread entity with meta-data such as (# of posts, first post, last post) stored into it, because that would involve even more complex maintenance queries.

The maintenance queries are not nearly as complex as doing SELECT DISTINCT, I think. You can also use triggers (if My SQL yet supports them) to handle the updates.

also, if you aren't suggesting a thread entity with that meta data, the difficult, less efficient queries would still exist, because you'd still have to search through the post table for the most recent posts with unique threadID's.

No. With multiple entities, you end up in better shape because you're not table scanning for IsThread = TRUE. You can create an index over IsThread, but it's pretty messy to do so; you can't enforce uniqueness over that column where it is true for only one PostID, and that starts the slide towards inefficient queries.

Your #1 query ends up being something like this, if your version of MySQL supports correlated subqueries:

select *
  from Posts P
 Where PostDate = (SELECT MAX(PostDate) FROM Posts WHERE P.TopicID = TopicID)

To implement this query, the database has to scan all the posts to find the max for each TopicID, then go back to the table to get the columns for at each row where the Max(PostDate) and TopicID have been found.

If you have a separate Topics entity, the query is trivial:

SELECT *
  FROM Topics

which is a scan over a much smaller index, without a self-referential implicit join to find the maximums.

While managing the Topics table opens a couple of questions, I don't think they're complicated or expensive at all. The queries can be done on the fly, too, with a simple index scan once you've got the separate entity. With a correct index, it doesn't get much faster than that.

Further, I think you're better off optimizing for retrieving posts and topic lists since that happens far more often than writing a new post, and the updates to the topic summary (if you choose to work it that way) execute less often than the read-only queries.

If you insist on the denormalization and tough queries, that's up to you. But I think you're far better off putting more thought into the data model at the beginning. When you want to extend your application, you'll end up paying the price later.

 

[generelz]

FWIW, I recently wrote a small bulletin board/forum and I second mike's advice. Due to the read many/write few nature of a forum, from my view it was much smarter and more manageable to model a thread as a separate entity in a separate table, with a one-to-many relationship to the posts the thread contains. The thread entity would contain the metadata you require for a quick summary, i.e. title, last post date, last post author, etc.

For example, this would be:

[Thread]
id (primary key)
title
last post time/date
last post author (potentially a reference to another table, users)

[Post]
id (primary key)
thread_id
title
post time/date
post author

Unfortunately here you are still duplicating data. Perhaps an even better solution would be:

[Thread]
id (primary key)
firstpost_id (references Post)
lastpost_id (references Post)

[Post]
id (primary key)
thread_id (references Thread, with index)
title
post time/date
post author

This way, when you want to summarize a thread, you simply need to join in the first and last post which is a very simple and optimized operation because of the index on the thread_id column. This would provide you with the original time the thread was created, the title, the author (joined from the first post), in addition to the last user to respond and last updated time. If you wanted to be able to summarize how many replies total were made, you could consider adding an index field to Post to retrieve that information quickly as well.

Furthermore you need to think about the future, as Mike mentioned. If this is the sort of thing that could have features added to it, it really is worth it to take a step back and evaluate your proposed design not only for suitability in the current use pattern but for suitability down the road when more features are added.

 

[hofan41]

No. With multiple entities, you end up in better shape because you're not table scanning for IsThread = TRUE.

you're right. thanks for the advice, everybody, having a thread metadata entity is the way to go.

 

[mikeblas]

Groovy. Let us know how it goes!

 

[piako]

you're right. thanks for the advice, everybody, having a thread metadata entity is the way to go.

yes it's called a index this makes the system more efficient because when you do a query or report you're not slowing everything down searching the possibly huge tables

 

[hofan41]

so here's an update, i used the following structure:

[Table: Category]
categoryID
...


[Table: Thread]
threadID
categoryID
firstpost
lastpost


[Table: Post]
postID
threadID
....


I was able to create forum display functionality in 2 queries, here they are:

1. SELECT * FROM Thread WHERE categoryID = ? ORDER BY lastpost DESC

My custom framework then populates an array of Thread objects containing the results. The php code then stores all of the firstpost/lastpost's into an array and loads it into query #2

2. SELECT SQL_CACHE * FROM Post WHERE postID IN ( ?, ?, ...) ORDER BY postID ASC

My custom framework then populates an array of Post objects, and now I am able to display both thread information as well as information on the last post in that particular thread.

I have a working prototype forum =). Let me know if you think query #2 could be optimized in any way, but aside from that I think I've got fairly efficient queries going on.

 

[mikeblas]

Why do you have two queries? Is one query executed to show the list of threads, then the other query is executed to show the list of posts in that thread, once the user clicks a thread to select it?

Why aren't you storing the ThreadID in the Post table?

 

[hofan41]

Why do you have two queries? Is one query executed to show the list of threads, then the other query is executed to show the list of posts in that thread, once the user clicks a thread to select it?

Why aren't you storing the ThreadID in the Post table?

whoops threadID is stored in the post table. forgot to put it in there. the first query is used to retrieve the most recent threadID's. then the second query is used to retrieve all the 'firstpost' and 'lastpost' posts to display the thread information. in retrospect i didnt read generelz post carefully enough it seems

This way, when you want to summarize a thread, you simply need to join in the first and last post which is a very simple and optimized operation because of the index on the thread_id column.

how would you join two items from the same table?

 

[generelz]

how would you join two items from the same table?

Just like you would join any two tables...

In this contrived example let's say a post can refer to itself, perhaps with a parent_id. Then we would join a post's parent by doing...

SELECT parent.title FROM post child LEFT JOIN post parent on parent.id = child.parent_id WHERE child.id = ?

This query for example would fetch the parent's title. You could also do:

SELECT parent.* FROM post child LEFT JOIN post parent on parent.id = child.parent_id WHERE child.id = ?

To get all the information for the parent row.

 

[hofan41]

thanks generelz. I'm away from my development machine atm so I can't run performance tests, but is there a (significant) performance difference between retrieving everything in one query as opposed to retrieving it in two? It seems because the JOIN's are based off of postID, just like my second query, the two methods appear to be largely equivalent. I've heard in some cases splitting a large query into two may even improve performance. Any insights?

 

[mikeblas]

Building the big IN list is time consuming for your PHP code. It's also very poor for the database, since it has no index over that ad-hoc list.

 

[hofan41]

Building the big IN list is time consuming for your PHP code. It's also very poor for the database, since it has no index over that ad-hoc list.

from what i've read PHP is exceedingly faster than asking the SQL server to do the work. also, creating the IN list is not as large as to slow down php either, as this IN list only retrieves one page's worth of threads at a time, say 30 threads a page..so 30 firstpost's and 30 lastpost's for a total of 60 posts in the IN list.

i would assume that since the IN list is off of postID it would be searching just as efficiently as if it were done in a join..they both use the same postID index dont they?

edit: I guess what I'm getting at is how exactly will a JOIN operation let the SQL server not have to search over an ad-hoc list anyways? It will still need to search through the posts table for all the postID's listed inside all the firstpost/lastpost fields in the threads it retrieves.

 

[mikeblas]

from what i've read PHP is exceedingly faster than asking the SQL server to do the work.

I'm sorry, but that's simply not correct. The database is far faster at manipulating data, particularly in a set-wise fashion, than PHP could ever hope to be.

also, creating the IN list is not as large as to slow down php either, as this IN list only retrieves one page's worth of threads at a time, say 30 threads a page..so 30 firstpost's and 30 lastpost's for a total of 60 posts in the IN list.

For each post, you'll be getting two numbers. You'll convert them to strings, then concatenate the strings to other strings with formatting. Maybe that ends up being four concats. So you'll do two conversions and four memcopies, plus four reallocations (which is an allocation plus a memcopy plus a free).

60 operations, then, is 60 conversions from integers to strings, 240 allocations, and 480 memcopies.

The database does no conversions and no reallocations. Plus, it has indexes to make the joins work well.

i would assume that since the IN list is off of postID it would be searching just as efficiently as if it were done in a join..they both use the same postID index dont they?

No, they don't. The IN list you provide isn't a table, and doesn't have an index.

edit: I guess what I'm getting at is how exactly will a JOIN operation let the SQL server not have to search over an ad-hoc list anyways? It will still need to search through the posts table for all the postID's listed inside all the firstpost/lastpost fields in the threads it retrieves.

You'll provide the threadID, won't you? Then, all the lookups are indexed.

 

[generelz]

You should listen to Mikeblas. He is correct. Doing a query with an IN list is going to be significantly slower than doing a JOIN. The performance of PHP here is inconsequential.

It seems you may lack some fundamental understanding of relational database theory (joins, indexes, how exactly different operations are carried out). You may want to take a step back and shore up that knowledge for a couple of days before proceeding.

You are talking about pagination. Do you know that most DBMS support a built-in way to limit the number of items returned, starting from a desired result? Doesn't that seem like a much more efficient way of paginating the posts for a thread?

 

[hofan41]

You should listen to Mikeblas. He is correct. Doing a query with an IN list is going to be significantly slower than doing a JOIN. The performance of PHP here is inconsequential.

It seems you may lack some fundamental understanding of relational database theory (joins, indexes, how exactly different operations are carried out). You may want to take a step back and shore up that knowledge for a couple of days before proceeding.

You are talking about pagination. Do you know that most DBMS support a built-in way to limit the number of items returned, starting from a desired result? Doesn't that seem like a much more efficient way of paginating the posts for a thread?

Yeah I am aware of the LIMIT statement in mysql. I think you have the issue here confused, I'm displaying a list of threads not a list of posts. I'm trying to retrieve the first and last post of every single thread. But yes I do plan on using the LIMIT statement to display the threads themselves.

I just can't wrap my head around how a query with an IN list of postID's is any different from doing a JOIN on the postID.

I think what mike was pointing out was that when you add in threadID on top of postID as an additional condition within the JOIN it will be possible for the DBMS to search faster. I'd agree with that.

Guess its time for me to get an intro to DBMS book.


edit:

SELECT * FROM thread LEFT JOIN (post AS firstpost, post AS lastpost) ON (thread.firstpost = firstpost.postID AND thread.lastpost = lastpost.postID) WHERE thread.categoryID = ? ORDER BY thread.lastpost DESC LIMIT 0, 30

That's the query as I see it now with joins. I am aware of mikeblas's suggestion of providing threadID on the join, but mysql only uses one index to search databases...wouldn't i want it to search using the postID instead of the threadID? Or would adding more conditions aka:

SELECT * FROM thread LEFT JOIN (post AS firstpost, post AS lastpost) ON (thread.firstpost = firstpost.postID AND firstpost.threadID = thread.threadID AND lastpost.threadID = thread.threadID AND thread.lastpost = lastpost.postID) WHERE thread.categoryID = ? ORDER BY thread.lastpost DESC LIMIT 0, 30

help?

 

[hofan41]

btw i wanna thank you guys for your help and advice and i appreciate it =)

 

[generelz]

Yeah I am aware of the LIMIT statement in mysql. I think you have the issue here confused, I'm displaying a list of threads not a list of posts. I'm trying to retrieve the first and last post of every single thread. But yes I do plan on using the LIMIT statement to display the threads themselves.

Ok, then in my mind there is really only one way of going about this that will provide a performant query, and that is to join the first post and last post.

I just can't wrap my head around how a query with an IN list of postID's is any different from doing a JOIN on the postID.

Mike can probably explain this better than I can, however the jist of the matter is that it is a lot more work for the database to build a query plan and optimize around an IN list rather than a simple join. With a simple join all the DBMS has to do is read from an index which is a very inexpensive operation, especially when that index is on a primary key field.

I think what mike was pointing out was that when you add in threadID on top of postID as an additional condition within the JOIN it will be possible for the DBMS to search faster. I'd agree with that.

The way the database *should* optimize this is by picking the index which gives the most limiting results first - so let's compare the primary key index to the threadID index.

Since primary keys are guaranteed to be unique, this index will always return exactly one row.

Since threadIDs are not unique, this index will return any number of rows.

Hence, the DBMS should always use the primary key index.

Unfortunately, what will end up happening is if you specify the extra qualifiers (firstpost.threadID = thread.id, lastpost.threadID = thread.id) is the DBMS will end up doing extra work by verifying these conditionals to be true because you wrote a bad query.

You are already guaranteed by your data model that by choosing posts which match thread.firstPostId and thread.lastPostId that they will also have the correct threadId. If this is not the case then there is an error in your business logic.

Guess its time for me to get an intro to DBMS book.

Might not be a bad idea

 

[hofan41]

With a simple join all the DBMS has to do is read from an index which is a very inexpensive operation, especially when that index is on a primary key field.

Is there any reason why the DBMS can't read from an index to process an IN list query on a primary key field? Why does it need to "do" more? lol sorry if I seem to be pestering =D

i mean, concept-wise the two seem the same. say you are the JOIN operation, here would be your line of thought according to what you just said:

"I am JOIN'ing two tables based on postID. So I have gathered all the postID's I need to look for in table B. I am now looking for all the posts in table B that have matching postID's"

say I am the IN list query operation

"Look for all the posts in table B that have matching postID's to the following list."

Maybe DBMS's just simply implements the two operations differently, but can you see why I would have this sort of confusion? The two operations seem very similar to me.

 

[mikeblas]

Mike can probably explain this better than I can, however the jist of the matter is that it is a lot more work for the database to build a query plan and optimize around an IN list rather than a simple join. With a simple join all the DBMS has to do is read from an index which is a very inexpensive operation, especially when that index is on a primary key field.

Right, essentially.

The database has a few ways to implement IN. It might decide to read each row, comparing it with a list of values in your IN. Or, it might create a constant table and stuff it full of those values, then join against that table and the key column. I've never seen a DBMS that makes a constant table have an index and ordering, and all the goodness that comes with it. As a result, you end up doing an in-memory table scan over that guy and rewind it each iteration of the join loop.

The cost of building the query string in your client application is real, and shouldn't be dismissed. In addition, the query string you show the server will differ reach time the numbers change, and the server probably won't parameterize the query. That is, it'll compile the query again and again each time it is executed and that leaves you with a pretty big expense that you wouldn't pay with the other methods we've suggested here.

 

[hofan41]

The database has a few ways to implement IN. It might decide to read each row, comparing it with a list of values in your IN. Or, it might create a constant table and stuff it full of those values, then join against that table and the key column. I've never seen a DBMS that makes a constant table have an index and ordering, and all the goodness that comes with it. As a result, you end up doing an in-memory table scan over that guy and rewind it each iteration of the join loop.

that answered all my questions. thanks!