avocadia

# Some notes on my Threading model

In the last post I mentioned a threading model, and how I had forgotten how it worked. And having more recently discovered that others have also developed the same model and even given it a name, but that I have forgotten where I read about it.

With some small hope that someone will recognise it and remind me what it is called, I present

A Threading model

Posit the following set of nodes

A graph depicting a set of nodes in a hierarchical tree structure

The nodes are stored in the following tables:

nodes

id	parent_id	title
1	NULL	A Post
2	1	First!
3	2	Lame!
4	2	re: First!
5	1	re: A Post
6	1	re: A Post_2
7	6	re: A Post_3

threads

root_id	node_id
1	2
2	3
1	3
2	4
1	4
1	5
1	6
6	7
1	7

root_id is the id of a node, node_id is the id of any descendants.

For example, Node 3 (Lame!) is a descendant of nodes 2 (First!) and 1 (A Post), so two records appear, one with root_id 1 and another with root_id 2.

To select the descendants of a root node:

select n.*
from nodes n, threads t
where n.id = t.node_id
and t.root_id = @root_id

If we were then to add an 8th node, and make it a child of node 3, the nodes table would become

id	parent_id	title
1	NULL	A Post
2	1	First!
3	2	Lame!
4	2	re: First!
5	1	re: A Post
6	1	re: A Post_2
7	6	re: A Post_3
8	3	re: Lame!

and the threads table would become:

root_id	node_id
1	2
2	3
1	3
2	4
1	4
1	5
1	6
6	7
1	7
3	8
2	8
1	8

the query for updating the threading table being:

insert into threads (root_id, node_id)
select @parent_id, @node_id
union
select root_id, @node_id
from threads
where node_id = @parent_id

The reason I came up with this system¹ was because I didn’t like having to recursively call back to the database for every node to see if it had any child nodes. I was working in a bubble and I’m not sure that I would have found information on Nested Sets If I had searched. Even if I had, I’ve always had a problem with the idea that an INSERT requires followup UPDATEs to the same table, with potential locking problems, &c.

A slight variant that would probably make Database Normalisers cry

I actually used to use a slightly different model back when I wasn’t using ActiveRecord to abstract away queries. ActiveRecord insists that I use foreign keys – even if in the (MySQL) database they aren’t actual formally declared as such. When I originally designed this model, I didn’t worry so much about it and did this:

root_id	parent_node_id
1	2
1	6

and

select distinct n.* 
from nodes n, threads t
where (n.parent_id = t.parent_node_id
and t.root_id = 2)
union
select * from nodes where parent_id = 2

Again, if I added an eigth node as a child of Node 3, the new threads table would be:

root_id	parent_node_id
1	2
1	6
2	3
1	3

and the query to perform that update would be

insert into threads(root_id, parent_node_id)
select root_id, @parent_id
from threads t, nodes n
where t.parent_node_id = n.parent_id
and n.id = @parent_id

I have never done any performance testing on either of these two models, versus Nested Set or even each other. I don’t really need to, I’m not getting enough traffic to need any optimisation on that level. OTOH, I’m not getting enough traffic to warrant coming up with this boondoggle just to avoid multiple database hits to display a comment thread. But it was there.

¹ Independently came up with. I know that it’s been developed elsewhere and long before I thought of it.

avocadia

# Some notes on my Threading model

A Threading model

nodes

threads

A slight variant that would probably make Database Normalisers cry

Meta

Feeds

Links