Theory and Practice of Multi-table Post Distribution
by D. Finnigan
21 Jul 08

This entire document is the exclusive intellectual property of, and is copyright 2008 by, D. Finnigan. All rights reserved. No portion of this document may be reproduced in any form without the express permission of D. Finnigan. Take note, however, that the ideas presented within this document are not protected and may be taken and implemented by anyone.

Introduction

In regards to large-scale forum systems, where the quick storage and retrieval of potentially one hundred million or more documents is crucial, such message system would most likely benefit from the implementation of multi-table post distribution, that is, the splitting of message posts across two or more tables and/or databases. The pros of such a system are less rows for the database to have to seek past to retrieve the requested messages; ease in backup as the tables are smaller; and ease in replication since these tables and/or databases can then be stored on multiple hard disk drives, and therefore, spread across an array of database servers, even if these servers are not already configured into any clustered or replicated environment. However, one of the cons of such a schema is its inherit complexity over the standard one-table model employed by most all common, off the shelf, forum products today. This document seeks to shed light on both the theory and practice of multi-table post distribution, hence the title, and in addition provide useful methods toward the creation and execution of such an arrangement.

Breaking it up: A look at three different potential methods

Now that we have decided that we do indeed wish to explore the option of multi-table post distribution, we have at least three logical options, which I will explain shortly, of how to split up the posts. Two of these three may seem convenient enough, but in fact they are not, as will be explained. The third option is, in my opinion, the best,

Option 1: Group By Post ID

This is the first potential option, and it is to simply group by post ID, for example, table1 would contain all posts 1 through 10 million and table2 would contain all posts numbering above 10 million. At first, this method seems completely logical and trouble-free: to prevent the original posts table from becoming too crowded, we simply redirect all new posts to a secondary table.

The problem: in storing posts, this method works. The problem is with viewing topics and the "imaginary table split". Imagine for a moment, a forum topic which up until page 200 contains all posts from the first posts table. Then, on page 201, posts above and below our 10 million-post table split appear. What would happen? Depending on how the forum software was written, the posts above the table split may not appear, or the page itself would have errors and refuse to display. Either result is undesirable. We cross this option off the list.

Option 2: Group By Forum ID

Now this option seems much better than the previous: we are simply grouping posts into tables based on their parent forum. If a board had 5 large forums and a few smaller ones, the 5 large forums could each have their own posting table and the smaller ones would all share a 6th table. There wouldn't be a problem with table-splits as in the previous option because everything is grouped together.

The problem: many forum systems offer a convenient "move topic" option, wherein the topic is logically moved from forum A to forum B by simply updating the values in the topic and its posts. However, by splitting the post tables by forum id, we are now forced to do a physical move, wherein the topic and its posts are selected and inserted into the new forum table, and then deleted from the old forum table. This requires a fair amount of work and overhead, and is thus undesirable unless you plan on rarely or never moving topics. We can confidently cross this option off the list.

Option 3: Group By Topic ID

This is the third option, and as you have read earlier, apparently the best option from the list. Unlike the first three options, grouping by topic id has the least amount of drawbacks. The method is simple: posts are grouped in to tables based on their topic id. Table 1 may contain topic IDs 1 through 5 million, and table 2 could store posts from topic IDs above 5 million. Using this method, we can further specify that having unique post IDs for all the tables is no longer necessary. That is, with the other two methods, the post id column, which is generally an auto increment value, would have to be updated across all other tables when a new post is inserted to prevent duplicate values. However, by instead grouping the post tables by topic ID, and then assigning each post its in-topic number (ie: the first post of a topic is 1, the second 2, etc), we can eliminate the ability to reference posts solely by their ID, and therefore we can build a potentially infinitely-scalable system by merely adding new tables as the amount of topics grows. With this system, a post would be referenced by its topic id and position in the topic, so the very first post of topic 10 would be referenced like so: 10_1; The 60th post of topic 780 would look like this: 780_60; and so on. In essence, the post ID is no longer a primary key to locate the row, but merely a number used to keep posts appearing in the correct order in their respective topics.

Setting up the Multi-Table Post Distribution

Let us now explore the implementation of this proposed system. First, let's take a look at the database tables for our forum system:

forums - this is the table which store the forum ID's in which all topics and posts are stored. Its schema is not needed for this example

topics - this is the table which stores the forum topics, It has the following columns: topic_id, forum_id, topic_table, topic_replies, topic_name. The topic_id is the primary key, the forum_id is a foreign key reference to the forums table, the topic_table is an integer which tells which table the topic's posts are in, topic_replies stores how many posts the topic has, and topic_name is an arbitrary name for the topic.

posts_1 - this is the first table for storing posts. It has the following columns: post_id, topic_id, post_number, forum_id, post_text. The post_id is the primary key, the topic_id is a foreign key reference to the topics table, the post_number starts at 1 and each successive reply to the topic increments by 1, the forum_id is a foreign key reference to the forums table, and the post_text stores the post message. A multi-column index is created called topic_post_num on the columns topic_id, post_number

posts_2 - this is the second table for storing posts. It has an identical schema to posts_1 table.

In order to keep numbers down to a small scale in this example, we will declare the topic split at 10. All posts belonging to a topic ID greater than 10 will go into the second posts table. Obviously, in a real-world use of this system, you would want the number to be several powers greater than a mere 10.

Posting messages to the System

Now that we have defined the database tables, and our forum system is in place, it is time to test out how it will work. Right now, the forum is completely empty: there are no posts and no topics.

A user decides to post the first-ever topic, ID 1. He does so, and a new topic is inserted into the topics table with the following data:
topic_id - 1
forum_id - 1
topic_table - 1
topic_replies - 0
topic_name - First Ever Topic

As you can see, the topic was designated to use the first posting table, posts_1. This was done by analyzing the maximum topic Id, since there were none for this first topic, the value was 1. The first posting table will be used.

After the user's new topic is inserted, the post is also inserted with the following data, into posts_1:
post_id - 1
topic_id - 1
post_number - 1
forum_id - 1
post_text - foo bar, test 1,2,3

All the integers are set to 1. If a user were to reply to this topic, another row would be inserted, which would look like this:
post_id - 2
topic_id - 1
post_number - 2
forum_id - 1
post_text - this is the first reply

Also, the topic_replies field in the topics table would be incremented by 1. As you can see, replies to this single topic increment the post_id and post_number field.
Let's say that more time has passed and there are now 10 topics in total, with a handful of replies each. Let's take a look at one of these posts:
post_id - 45
topic_id - 10
post_number - 6
forum_id - 1
post_text - this is the 6th reply to the topic

Here we are looking at post number 6 within topic id 10. We can also tell by looking at the post_id that the forum has at least 45 posts in total.

Now, here is where the split happens! A new user signs up and immediately decides to start a new topic, this one happening to be topic id 11.

Our forum system, which know the split is after 10, takes note and appropriately records the change to make sure all replies to it go to posts_2 table. Here is what is entered in the topics table:
topic_id - 11
forum_id - 1
topic_table - 2
topic_replies - 0
topic_name - Hi, I'm new here!

Notice how the topic_table field is set to a 2 instead of one. That means that all replies to this topic will be found in posts_2 table.

After the user's new topic is inserted, the post is also inserted with the following data, into posts_2:
post_id - 1
topic_id - 11
post_number - 1
forum_id - 1
post_text - this sure is a great place!

Since the posts_2 table was empty, the post_id starts at 1. Remember too that the first posts table also contains a post id of 1. This does not matter, because these two posts should never cross paths! Furthermore, with the topicID_postID format, the first post for this topic will be assigned the value 11_1, and there will be no conflicts.

More replies to the first 10 topics will all go the first posts table, while all replies to topic 11 and all subsequent topics will be directed to the second posts table.

Retrieving Messages from the System

Since typically a post will be posted just once and then read many times, it is important to have a method of retrieval which is quick and efficient.

For displaying messages we will use the URL and our multi-column index that we created earlier on the posts tables.

Let's say that the URL for topic id 10 is this: http://forum.com/topic.php?t=10

We then run an SQL query to get topic 10's data:

SELECT * FROM topics WHERE topic_id = 10

Now we set all the fields from the returned row in to an array. Since we know from the examples above that topic ID 10's posts are in the posts_1 table, we can go directly to that. Normally, you would look at the topic_table field and see if it was a 1 or a 2.

For this particular forum system, we will show just 5 posts on a page, so we run this query to get the posts for page 1:

SELECT * FROM posts_1 WHERE topic_id = 10 AND post_number <= 5

The database optimizer should choose the multi-column "topic_post_num" index that we had created earlier, and thus the first 5 posts should be quickly returned.

Now the user clicks the link to go to page 2, which has posts 6 through 10. The URL then looks like this: http://forum.com/topic.php?t=10&start=6
The following query is run:

SELECT * FROM posts_1 WHERE topic_id = 10 AND post_number BETWEEN 6 AND 10

The database optimizer should choose the multi-column "topic_post_num" index that we had created earlier, and thus the second 5 posts should be quickly returned. The formula for this query is this: 

SELECT * FROM posts_N WHERE topic id = X AND post_number BETWEEN Y AND [(Y-1)+Z]

N = topic post table
X = topic ID
Y = the starting value as given by URL
Z = the number of posts per page

As long as value Y is incrementing by value Z for each page, then this query formula should accurately return the correct posts in the correct number for each page.

Retrieving a Single Message from the System

There are some cases where it is preferable to return a single post from among millions, for example: to edit that post, quote it, or delete it. In any case, the following URL would be used: 
http://forum.com/post.php?t=10&num=6

Although this URL looks similar to the one used in the previous example, this time the query is slightly adjusted:

SELECT * from posts_1 WHERE topic_id = 10 AND post_num = 6

The decision to query posts_1 table was made by looking at the topic ID and noting that it is equal or less than 10. This query will return the contents of the 6th post in topic 10, after which the user may carry out some operation such as quoting, editing, or deleting. he database optimizer should choose the multi-column "topic_post_num" index that we had created earlier in order to speed up the process.

Searching for posts using Fulltext

Generally it is considered a drawback if there is no convenient mechanism for searching the posts made within the forums. Normally, this process is straight-froward when only one post table is involved, but when more than one are involved, the task becomes more complex. Simply put, all the tables must be queries for matches to the search terms and then these results must be joined together and sorted.