Click here to Skip to main content
Click here to Skip to main content

Optimising hierarchical SQL structures (an ASP approach)

, 15 Oct 2001
Rate this:
Please Sign up or sign in to vote.
An article on how to improve SQL hierarchies
<!-- Download Links -->

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:

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:

'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

About the Author

Ciprian Miclaus

United States United States
No Biography provided

Comments and Discussions

 
GeneralSimple Improvement PinmemberTom Welch16-Oct-01 9:02 
GeneralRe: Simple Improvement PinmemberCiprian Miclaus17-Oct-01 0:06 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.140721.1 | Last Updated 16 Oct 2001
Article Copyright 2001 by Ciprian Miclaus
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid