24 Feb 2003 amars   » (Journeyer)

MySQL woes...

For while, actually for as long as i've been working with MySQL, i've been trying to figure out the best way to handle heirarchal relationships between rows. I have three goals, to fetch all children resulting from a single node, count all children from a single node and have them in their respective order.

This simplest, most obvious choice is to have a column to store a node id and a column to store the id of the node's parent. The problem with this method, with regards to MySQL, is to achieve my three goals, one would have to recursively traverse the database via sql call in a recursive function. While it's easy to, say, fetch the immediate children of any given node, it's not good when i want to fetch everything and have it in order.

My most recent attempt is as follows...

Two tables, one with the nodes and the other to handle the relationships. the node table isn't important... just know that there is a unique node id that corresponds to a node in that table. The other table, i call the signature table or more appropriately the relationship table. In the relationship table i have a unique relationship id, for the sake of being able to update/delete it from the command line, a node id, a node signature and a depth. node id is obvious, a node signature consists of the nodes id appended to it's parents signature, separated with ':' (example: :1:2:3:4:) and the depth, calculated upon entry into the database is how deep the node is in it's particular thread.

With such a method, i am able to achieve my first and second goal easily with the use of LIKE. The problem arises when i try to order the results from MySQL. First off, since the signature is text, ORDER BY orders the results alphabetically, which puts 10 before 9, so i can't do a straight ORDER BY signature. The solution is to break it up by parts and order by each part successively. But that requires prior knowledge of how deep the thread goes so you can construct a string of parameters to pass to ORDER BY, which is where the depth comes in.

So theoretically, upon proper depth calculation upon entry, i can achieve my goal in two SELECT statements, first the one to determien the length and the other to select with successive ORDER BY parameters. The next problem therein is the fact, again, that ORDER BY orders alphabetically, so 10 still comes before 9. The solution to that is to type cast it to decimal, which is only supported in 4.x, so i can't use that. The next option is to convert between bases. Since substring_index returns text, it can be seen as outputting a number of base 36 (0-9a-z), which mysql supports.

But that doesn't work either... for some reason MySQL isn't sorting beyong the first parameter... it seems to be ignoring the rest.

So, i'm at a loss. I was hoping i could do this without having to sort it via PHP. If someone knows about this type of thing, i'd be interested in some pointers in the right direction. This kind of stuff pops up all the time, most notably in comment systems. Right now my best option is to use my signature method to fetch all children and sort it with PHP. Sample query is below.

select substring_index(substring_index(signature,':',5),':',-1) as 'e',
substring_index(substring_index(signature,':',4),':',-1) as 'd',
substring_index(substring_index(signature,':',3),':',-1) as 'c',
substring_index(substring_index(signature,':',2),':',-1) as 'b',
signature_id,ticket_id,signature,depth from tickets_signature
order by conv(substring_index(substring_index(signature,':',2),':',-1),36,10) asc,
conv(substring_index(substring_index(signature,':',3),':',-1), 36,10) asc,
conv(substring_index(substring_index(signature,':',4),':',-1),36,10) asc,
conv(substring_index(substring_index(signature,':',5),':',-1) ,36,10) asc;

And resulting output...

+------+------+------+------+--------------+-----------+--------------+-------+
| e    | d    | c    | b    | signature_id | ticket_id | signature    | depth |
+------+------+------+------+--------------+-----------+--------------+-------+
|      |      |      | 1    |            1 |         1 | :1:          |     0 |
|      |      |      | 2    |            2 |         2 | :2:          |     0 |
|      |      |      | 3    |            3 |         3 | :3:          |     0 |
|      |      |      | 4    |            4 |         4 | :4:          |     0 |
|      |      | 14   | 4    |           14 |        14 | :4:14:       |     1 |
|      | 15   | 14   | 4    |           15 |        15 | :4:14:15:    |     2 |
|      | 16   | 14   | 4    |           16 |        16 | :4:14:16:    |     2 |
| 17   | 16   | 14   | 4    |           17 |        17 | :4:14:16:17: |     3 |
| 18   | 16   | 14   | 4    |           18 |        18 | :4:14:16:18: |     3 |
|      |      |      | 5    |            5 |         5 | :5:          |     0 |
|      |      |      | 6    |            6 |         6 | :6:          |     0 |
|      |      |      | 7    |            7 |         7 | :7:          |     0 |
|      |      | 10   | 7    |           10 |        10 | :7:10:       |     1 |
|      | 13   | 10   | 7    |           13 |        13 | :7:10:13:    |     2 |
|      |      | 11   | 7    |           11 |        11 | :7:11:       |     1 |
|      | 12   | 11   | 7    |           12 |        12 | :7:11:12:    |     2 |
|      |      | 8    | 7    |            8 |         8 | :7:8:        |     1 |
|      | 9    | 8    | 7    |            9 |         9 | :7:8:9:      |     2 |
+------+------+------+------+--------------+-----------+--------------+-------+

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!