[wp-hackers] Restructuring Category Hierarchy

[Otto]

Took me a while to figure out just what the hell you were talking
about, but I get it now. You're basically talking about hierarchy in
the categories. And you're right, that is a more efficient way to do a
tree model. Selection of a whole branch basically becomes a simple
query. You get the left and right values of the category you want,
then select everything with left/right values between those two
values. Voila, you have all the children. The cost is that inserting a
category into the hierarchy requires an insert and 2 updates, while
deleting takes a delete and 3 updates. Not a huge deal, really.

The one thing that does concern me on that dev.mysql page is that they
talk about inserts and deletes, but they don't talk about rearranging
the hierarchy. A rearrangement is basically a delete followed by an
insert to another location, so you're looking at least 7 queries to do
it in the most obvious way. That seems really high.


On 5/4/07, Jamie Talbot <wphackers at jamietalbot.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> As part of the taxonomy improvements that are due for 2.3, wp_categories and wp_post2cat are likely
> to be removed or significantly altered, no matter what schema we end up going for (the current
> proposal is at trac ticket #4189[1]).  Our current category schema is more optimised for inserts
> than selects.  For subcategories for example, we either have to cache the entire category table into
> a complex array, or recursively retrieve data.
>
> A better model, more suited to WordPress ideals, is the other way round, where we take a _slight_
> hit on inserts, so that we can instead select whole subsets of data very quickly.  This can be
> achieved by using the Nested Set Model, described on MySQL's website[2].  That page has lots of
> optimised queries for common usage which model our needs very well.  The vast majority are 4.0
> compatible, with a few less common examples requiring 4.1.  Given that there is going to be a
> sizeable structural shift anyway, I'd like to see us move to this new model, which should offer big
> speed improvements.  API for categories will already have to change to fit the new schema, so we
> should change it all in one go.
>
> The changes basically boil down to replacing the single 'parent' column with two 'left' and 'right'
> ('lft', 'rght') columns.  For tagging, these columns aren't so useful, but they are for
> post-category and link-category, and I can imagine other taxonomies that would also be made
> possible, like linked-list.
>
> I raised this on the ticket above, but there haven't been any responses to it there, so I'm
> wondering what the hackers think?  If we miss this opportunity for change, it will be a long time
> before we have another chance.
>
> Cheers,
>
> Jamie.
>
> [1] http://trac.wordpress.org/ticket/4189
> [2] http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
>
> - --
> http://jamietalbot.com
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.5 (MingW32)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFGO7G0rovxfShShFARArPnAJ47mPO39GiUnYSTI2Ncqdy2XO512QCeJJvn
> 4LmBd8vrNwYBAO5kYIF8phY=
> =CM27
> -----END PGP SIGNATURE-----
> _______________________________________________
> wp-hackers mailing list
> wp-hackers at lists.automattic.com
> http://lists.automattic.com/mailman/listinfo/wp-hackers
>