Click here to Skip to main content
15,867,453 members
Articles / Web Development / IIS
Article

Optimising hierarchical SQL structures (an ASP approach)

Rate me:
Please Sign up or sign in to vote.
5.00/5 (3 votes)
15 Oct 20014 min read 103.7K   663   44   13
An article on how to improve SQL hierarchies

Introduction

The fancy title of this article could be rephrased like: How to write an ASP forum or How to improve your ASP bulletin board. I bet the title would be more commercially attractive. However this is more like a SQL optimisation, and the ASP forum example just a practical instance. However our article is not highly theoretical but instead problem solving oriented as we will see.

The problem

Imagine a newsgroup, where people publish problems, and others reply. Obviously you need to format the messages so that all the messages related to the same topic are displayed together. This is done hierarchically, so the first message appears first in the hierarchy, underlining it should be read first. A forum or a message board works exactly the same. So let's see how can we express that through SQL structures like tables, fields, relations etc.

A naive approach

Take a look at the following picture (Fig 1) showing how a naive table for a simple forum, or web based message board could be expressed in SQL structures.

Fig 1

From, Subject, Text and Date fields are self explanatory. The hierarchy is given by the primary key, Id, which identifies uniquely the topic and by the foreign key, Id_parent, which engage in a relationship as shown in the picture. In short, a topic with Id=X will have as replies all topics with Id_parent=X. Pretty straightforward. Why is it naive?

Let's take a look at how we will display this hierarchical structure... First we will SELECT all the topics that have no parents, the upper level, and then for each topic we will SELECT all the topics that has this topic as parent, and then for each sub-topic we will SELECT ..., and then for each... and so on. Not very easy is it? If you played with cursors before, you would know some improvements can be made, but still we will have a tedious task, lot of processing and maybe a database server congestion on a busy server. It's definitely not a scalable solution. Forget about it...

A smarter statistic approach

In terms of performance and scalability, the best software solutions are not general solutions but targeted solutions. To target our solution, let's analyse the problem. In a forum solution, users will write and read from the database. Statistically, write will represent 1-20% while read will represent the rest. So, instead of putting the burden on read, like in the previous solution, we would like to make the read process as fast as possible and move the burden from read to write, which is by far less used than read. Ideally, we would want a single SELECT to be enough, while the write procedure might become more complex with several SELECTs and INSERT. Take a look at the next picture (Fig 2.)

Fig 2

We added to fields: DisplayOrder and DisplayDepth. Well the idea is simple. DisplayOrder and DisplayDepth will allow us to SELECT items in the exact order of display as shown in Fig 3.

Fig 3

As you can see, DisplayOrder simply keeps the order of display of the items, while the DisplayDepth keeps the hierarchy depth, that will help us display the hierarchy. So, now we can simply:

SQL
SELECT * from Topics ORDER BY DisplayOrder

and then with a cursor intend the display according to DisplayDepth. Yes, you guessed right, DisplayOrder and DisplayDepth are computed at write-time. So at write time, knowing the Id_parent=X (the parent of the current topic to be inserted), what happens is:

SQL
'find the parent
SELECT DisplayOrder as Y, DisplayDepth as Z FROM Topics WHERE id=X

'insert the new topic and update DisplayOrder and DisplayDepth
UPDATE Replies SET DisplayOrder=DisplayOrder+1 WHERE DisplayOrder>Y
INSERT INTO Topics (...,DisplayOrder, DisplayDepth, Id_parent, ...) VALUES (...,Y+1, Z+1, X,...)

In plain English: We identify the DisplayOrder of the parent. The new reply topic will have DisplayOrder equal to parent's DisplayOrder + 1. But first we must ensure no other item has this DisplayOrder, so we simply add 1 to all the items that should be displayed after the item to be inserted. For a more detailed understanding of what happens here study the demo example attached to this article and then try to write your own.

Conclusion

There are many improvements one can make when dealing with a backend database server, improvements that will dramatically affect the scalability of your application. If you would implement both solutions, the naive one and the smarter statistical one, you would see the difference. It definitely worth considering such an improvement. An ASP implementation is offered in the demo example. I used this technique myself in my website to allow people to give hierarchical feedback to my articles.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralProblems Pin
bikedude21-Mar-02 15:19
bikedude21-Mar-02 15:19 
GeneralTest Pin
14-Mar-02 4:35
suss14-Mar-02 4:35 
GeneralRe: Test Pin
14-Mar-02 4:37
suss14-Mar-02 4:37 
GeneralThird party components Pin
26-Feb-02 4:04
suss26-Feb-02 4:04 
GeneralRe: Third party components Pin
Anonymous1-May-05 6:43
Anonymous1-May-05 6:43 
GeneralMove a record is a problem Pin
12-Feb-02 4:20
suss12-Feb-02 4:20 
GeneralRe: Move a record is a problem Pin
Karthikeyan Ganesan8-Feb-06 21:39
Karthikeyan Ganesan8-Feb-06 21:39 
GeneralUsefull field could be added Pin
26-Dec-01 11:27
suss26-Dec-01 11:27 
GeneralRetrieve a group with displaydepth = x Pin
25-Oct-01 17:18
suss25-Oct-01 17:18 
GeneralSimple Improvement Pin
Tom Welch16-Oct-01 9:02
Tom Welch16-Oct-01 9:02 
GeneralRe: Simple Improvement Pin
17-Oct-01 0:06
suss17-Oct-01 0:06 
GeneralConfusing Pin
Tom Welch16-Oct-01 7:17
Tom Welch16-Oct-01 7:17 
GeneralRe: Confusing Pin
16-Oct-01 23:56
suss16-Oct-01 23:56 
You're absolutely right. My mistake.
Indeed, for clarity reasons, it should be Reply_to_topic1.2 because it's the second reply to Topic1.
And UPDATE Replies should be read UPDATE Topics indeed, I worked with an example having a table Replies and I modified it later to be Topics, coz I thought Topics sounds better and suggests more. But it seems I forgot to replace Replies with Topics in that SQL query.
Thanks a lot, I will correct that asap.
Ciprian Miclaus
www.ciprian-miclaus.com

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.