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

Recursive tables in SQL Server

, 26 Jan 2006
Rate this:
Please Sign up or sign in to vote.
Fast recursion in DB.

Introduction

I've tried to create here a good architecture for custom role-based authorization. I did not want to create tables for each hierarchy (operations, tasks, roles, role/groups) - because such a design would also need tables for references, such as: rolegroup2role, role2role, task2role, operation2role, etc...

So I decided to use the following structure...

Sample Image

But then I faced a problem: there is no support for recursion in MS SQL 2000. So I decided to create a stored procedure, which would then, for a given permission item, find all items that are to be related.

And so came the second problem: my architecture also allowed circular references, and also even assigning roles to a given task (even if this would not be allowed, but such a possibility is still there) - but this one did not make me upset.

I had to come up with a proper stopping expression for my stored procedure. Until a row was added in the last recursive cycle, the code had to call itelf again-and again...

To cite from a forum: "Google is your friend". I tried to find similar solutions... Everything I found there was either code for MS SQL 2005 or MySQL. They have quiet good extensions for recursion, but I still had to use MS SQL 2000. So I followed the idea behind these algorithms:

  • create the first level of data
  • then calculate the second level of data and merge them together...

So my first code

The idea behind this code was:

  • create a simple JOIN
  • then remove duplicates

It worked on the same principle as the suggested recursive model I found (somewhere) on the www. The difference is that I'm using temporary tables.

The real problem was that I was inserting multiple data with one SQL expression, so even if one of the rows was violating primary keys or unique constraints, none of the rows were added... Does anyone have a good suggestion on how to deal with this problem on MS SQL 2000 when using table variables?

Because of the problem mentioned in the previous paragraph, I had to remove duplicates using another way...

Ratings: This code was rather slow. To remove duplicates, I had to find them, then create a list of primary key values which were not needed. For this, I had to use the NOT IN operator, which also resulted in poor performance.

So I rated this code as unusable because of performance issues. Then what to do?

Again I tried other ways to deal with the problem (removing duplicates). But again: limitations of SQL and the limitation of the TABLE variable did not allow me to create a unique index which would be able to ignore duplicate keys on insertion.

So my second code

The idea: If removing duplicates takes too long then avoid adding duplicates.

With a simple change in the code, the results were amazing:

  • By using the NOT IN operator on a smaller set, the data performance increased about 50-100 times.
  • I did not have to use the SELECT COUNT (distinct ID) - note: this function is quiet fast (see later).

Ratings: Again, performance is still not acceptable (8 sec for the SP to run).

So my third code

The idea: We allow duplicates (but they're limited), we do not use the NOT IN operator.

Changes:

  • by using the NOT IN operator performance increased
  • created a distinct SELECT on the final result-set

Ratings: Comparing it to the second code, the performance increased about 10-20 times.

So my fourth code

The idea: We allow duplicates (but they're limited), we do not use the NOT IN operator, we remove the limited duplicate items in each cycle.

Changes:

  • by using the NOT IN operator, performance increased
  • we use two TABLE variables
  • in each cycle, we add new items to the existing collection, then insert into the other table only the distinct data

Ratings: Comparing it to the third code, the performance increased again about 10-20 times. But we still have to use three INSERTs an two DELETE operations for a cycle.

So my fifth code

The idea: We allow duplicates (but they're limited), we do not use the NOT IN operator, we remove the limited duplicate items in each cycle.

Changes - compared to code #4:

  • we do only three operations in a cycle: INSERT - DELETE - INSERT
  • we use two TABLE variables
  • in each cycle (odd/even), the other table contains the full results

Ratings: Comparing it to the fourth code, the performance increased about five times. For the given test data-set, it took 350ms for completing the query.

About the performance tests

I've created 1000 permission items and 10000 relations between them (a randomly created dataset).

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

Share

About the Author

balazs_hideghety
Web Developer
Slovakia Slovakia
Since 1999 I work in IT. Worked 2-3 yrs with Borland Builder C++. Since .NET appeared, I program in C#, ASP.NET.
 
You may know the current technologies, but still there's a lot of experience to gain. IT's evolving all the time.
 
From 2006 I'm a MCP. Now I'm focusing on technologies like: NHibernate, NSpring...

Comments and Discussions

 
GeneralFantastic! Pinmembermaqdk31-May-07 4:22 
Generalwith ignore_dup_key option (duplicates) PinmemberGearbox805-May-06 16:13 
GeneralHierarchies in SQL PinmemberRichardHowells30-Jan-06 22:49 
GeneralRe: Hierarchies in SQL Pinmemberbalazs_hideghety19-Sep-06 3:12 
GeneralAvoiding duplicates in SQL Server 2000 Pinmemberpmoldovan30-Jan-06 21:48 
GeneralRe: Avoiding duplicates in SQL Server 2000 Pinmemberbalazs_hideghety31-Jan-06 0:12 
GeneralRe: Avoiding duplicates in SQL Server 2000 Pinmemberpmoldovan31-Jan-06 0:35 
GeneralRe: Avoiding duplicates in SQL Server 2000 Pinmemberbalazs_hideghety1-Feb-06 0:22 
GeneralPlease RATE this article! Pinmemberbalazs_hideghety27-Jan-06 5:08 
RATE THE CONTENT!
 
DON'T GIVE POOR RATING FOR ANY PROJECT:
- IF IT'S AIN'T THE SOLUTION YOU WERE LOOKING FOR

 
C#, ASPX, SQL
GeneralRe: Please RATE this article! PinmemberM_Rizwan30-Jan-06 21:51 
GeneralRe: Please RATE this article! PinmemberThatsAlok15-Nov-11 21:30 

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 | Terms of Use | Mobile
Web01 | 2.8.141220.1 | Last Updated 26 Jan 2006
Article Copyright 2006 by balazs_hideghety
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid