Category Operation (Adjacency vs. Modified Preorder)

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Category Operation (Adjacency vs. Modified Preorder)

Christopher Johnson-3
Had anyone ever considered using a modified pre-order tree to store the post
categories in? I realize it would mean rewriting several large swaths of
code in addition to a tool to convert adjacency<->tree.

With all the posts and plugins I've seen relating to filtering and/or
excluding posts by category ... it would seem that a modifed preorder tree
would not only simpify queries but would be more "read" efficient. Had this
ever come up?


_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Jeff Minard
Christopher Johnson wrote:
> Had anyone ever considered using a modified pre-order tree to store the
> post categories in?

Excuse the simpleton, but what in hay-diddly is that? Some links and/or
examples would be helpful.

Jeff
_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

RE: Category Operation (Adjacency vs. Modified Preorder)

Christopher Johnson-3
In reply to this post by Christopher Johnson-3
> > Had anyone ever considered using a modified pre-order tree to store the
> > post categories in?
>
>Excuse the simpleton, but what in hay-diddly is that? Some links and/or
>examples would be helpful.

A modified preorder tree is a method of storing hierarchal data in a
database. This article provides a much better explanation than I'm capable
of ... http://www.sitepoint.com/article/hierarchical-data-database

The method requires a little more work during inserts and updates but allows
for much faster and much more flexible queries. An example ... with this
method you could extract an entire sub tree from the categories table with
only 1 query and no sub-selects (2 joins). No recursive post processing is
needed either. When retrieving posts by category, multiple sub tree's could
be excluded or included with a single query (2 joins). The path to a
category, a list of siblings, a list of children, all can be retreived with
single query, but not at the same time of course.

The multiple inclusion/exclusion of hierarchies feature is what really calls
to me. Granted, doing inclusion "and" exclusion at the same time would
require a couple queries without sub-selects.

If anyone is interested and/or thinks this might be a good addition, I've
got some prototypes I could share.


_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Mark Jaquith
On Feb 10, 2006, at 8:33 AM, Christopher Johnson wrote:

> The method requires a little more work during inserts and updates  
> but allows for much faster and much more flexible queries. An  
> example ... with this method you could extract an entire sub tree  
> from the categories table with only 1 query and no sub-selects (2  
> joins). No recursive post processing is needed either. When  
> retrieving posts by category, multiple sub tree's could be excluded  
> or included with a single query (2 joins). The path to a category,  
> a list of siblings, a list of children, all can be retreived with  
> single query, but not at the same time of course.

It certainly sounds nice.  One thing I noticed about that article is  
that the old "parent style" can be kept, and run in tandem.  Sounds  
to me like we could update the WordPress code to use the transversal  
style, but plugins that directly query the table looking for parent  
relationships wouldn't be left in the dark.

--
Mark Jaquith
http://txfx.net/


_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Christopher Johnson-3
> It certainly sounds nice.  One thing I noticed about that article is  that
> the old "parent style" can be kept, and run in tandem.  Sounds  to me like
> we could update the WordPress code to use the transversal  style, but
> plugins that directly query the table looking for parent  relationships
> wouldn't be left in the dark.

By leaving and maintaining the original parent refs you also gain a little
protection from the left and right indexs getting screwed up by a failed
update. If anything ever goes wrong, you can just reindex using the parent
refs. My only concern is that there are plugins out there that modfiy the
table directly, thereby bypassing the new indexing. Other than that, the
change would basicly be seamless. I've started by writing a conversion tool
and replacing the wp_..._category functions in categories.php
_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Christopher Johnson-3
In reply to this post by Mark Jaquith
One thing I'm not sure about is if I should bother pre-sorting the table.
Upon converting to the new indexing, should siblings be sorted by name and
then during inserts and moves choosing appropriate insertion points. Again,
this means more effort during inserts and updates but further simplifies
reads by not requiring recursive processing to sort a tree after a query.
_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

RE: Category Operation (Adjacency vs. Modified Preorder)

Denis de Bernardy
In reply to this post by Christopher Johnson-3
sql tree preordering works nice, but imho implementing them without
transactions and triggers is really asking for trouble.

D.

_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Christopher Johnson-3
> sql tree preordering works nice, but imho implementing them without
> transactions and triggers is really asking for trouble.

Yeah, that's the downside of basicly going from one tree index (cat_parent)
to three( left, right, parent). There are three index's that can get fouled
up with a bad write operation.

I suppose performing an index check after every insert/update might be a bit
excessive .. or would it?
_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Robert Deaton
In reply to this post by Denis de Bernardy
On 2/11/06, Denis de Bernardy <[hidden email]> wrote:
> sql tree preordering works nice, but imho implementing them without
> transactions and triggers is really asking for trouble.
>

Another perfect reason for dropping everything < 4.1 (As I mentioned
in the other thread about ideas for 2.next. At least with 4.1, we'd
have transactions, maybe not stored procedures or triggers, but
transactions at the very least.

--
--Robert Deaton
http://somethingunpredictable.com

_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

RE: Category Operation (Adjacency vs. Modified Preorder)

Denis de Bernardy
In reply to this post by Christopher Johnson-3
> > sql tree preordering works nice, but imho implementing them without
> > transactions and triggers is really asking for trouble.
>
> I suppose performing an index check after every insert/update
> might be a bit excessive .. or would it?

Technically, you can live with a corrupt tree, but you cannot trust any math
to make assumptions on its contents.

Assume the following if this is not immediate to you:

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
INSERT INTO tree (lft, rgt, title) values (6, 7, 'Strawberry');

Now, imagine a user who is a little nervous with the save button and a
server than terminates php scripts without executing them until the end on
multi-clicks.

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
-- user clicks the save button again

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
-- one more time

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
INSERT INTO tree (lft, rgt, title) values (6, 7, 'Strawberry');

note that the sql tree remains useful when you traverse the data. when it
comes to the underlying math, however:

descendants != (right - left - 1) / 2

D.

_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

David Chait
Well, without some real atomic operation, uncancellable by the user, lots of
problems could occur throughout the entire system... ;)

Some ideas for this one:
- spawn the thing that does the update in another script, so user can't muck
it up.
- have the update script use some kind of lock file, in order to try to keep
atomicity of its operations.
..etc.

Just me, randomly writing without thinking... :)
-d

----- Original Message -----
From: "Denis de Bernardy" <[hidden email]>
To: <[hidden email]>
Sent: Saturday, February 11, 2006 12:03 PM
Subject: RE: [wp-hackers] Category Operation (Adjacency vs. Modified
Preorder)


> > sql tree preordering works nice, but imho implementing them without
> > transactions and triggers is really asking for trouble.
>
> I suppose performing an index check after every insert/update
> might be a bit excessive .. or would it?

Technically, you can live with a corrupt tree, but you cannot trust any math
to make assumptions on its contents.

_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Evan Broder
I'm not sure that I see the sense in using modified preorder for WP
categories.

It seems that the only thing we gain is the ability to count the number
of children any given node has. However, it becomes significantly more
difficult to loop through, say, the top level categories.

It's quite probable that I just haven't completely wrapped by head
around the modified preorder, but it seems like it causes more problems
that it solves. For example, there's the whole easy corruptibility, but
it also complicates any attempts to change the order categories are
sorted in and stuff like that.

Like I said, I probably just still miss the inner beauty of the modified
preorder, but it seems like we'd be better off sticking to the adjacent
method.

- Evan
_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers
Reply | Threaded
Open this post in threaded view
|

Re: Category Operation (Adjacency vs. Modified Preorder)

Christopher Johnson-3
> I'm not sure that I see the sense in using modified preorder for WP
> categories.
> It seems that the only thing we gain is the ability to count the number of
> children any given node has.

The real draw that I see is the ability to create easily readable subtrees.
You'ld have a dummy root node at the top of the tree and then a handful of
subtrees as children. One for youre main blog entries, one for an aside,
etc. You could include or exclude whole trees with single queries.

> However, it becomes significantly more
> difficult to loop through, say, the top level categories.

That's where the addition of a "level" field comes in. If your dummy root
node is at level 0, just query all the children of root with level = 1. I
think that's what you were looking for

I do admit this is a feature that does really need transactions to be safely
viable.
_______________________________________________
wp-hackers mailing list
[hidden email]
http://lists.automattic.com/mailman/listinfo/wp-hackers