How should i perform tree traversal in given structure?

Question

Mission

I'm trying to find out the count of children in a set of tables illustrated below. The enviroment is LAMP but help in the right direction via other syntaxes are appreciated.

Table structure

users
-----
user_id  
parent_id


user_meta
---------
user_id
registration_date


user_levels
-----------
user_id
level

This basic structure is unlikely to change but could be extended.

Use case

select
  users.user_id
from
  users
inner join
  user_meta
  on users.user_id = user_meta.user_id
inner join
  user_levels
  on users.user_id = user_levels.user_id
where
  parent_id = *x*
  and
  registration_date > *certain date*
  and
  level < *certain level*

Conditions

• A user's descendant only counts as such if its level is lower than given *certain level*. If descendant's level is not lower, the node is a leaf but should be excluded from the count.
• Given *certain level* and *certain date* are the same for every query/set of queries.

I've tried using this in a loop but the amount of queries quickly escalades. This solution could probably be used and stored in a cron job but I'd prefer an as-real-time-as-it-gets-solution.

(PS: since this is my first question, feel free to edit and give hints on how to ask better questions)

Answer 1

It might be faster to pull all of the user records into local memory and run an algorithm there instead, depending on how many users you have. SQL isn't really suited for recursive tree traversal.

Answer 2

Hi,

There is a SQL99 feature witch is called "Common Table Expression" wich allow you to create recurcive functions and efficiently handle hierarchical data stored in relational database.

It looks like MySql does not (yet) implement it but you could see what can be done with this : http://msdn.microsoft.com/en-us/library/ms190766.aspx

Answer 3

With your current data model there isn't a more efficient way to do it than recursively querying the database. If you are able to change the way the data is stored to include more information you can use the Modified Preorder Tree Traversal (also refered to as the Nested set model). This model is discussed in an article on the MySQL website. There are also many examples on this website, just search for "Modified Pre-order Tree Traversal".