New implementation for database tree parsing ( taxonomy / comment )

So some more background on this. Since the EOL taxonomy sprint, we've been discussing a lot about ways to denormalise taxonomy module's hierarchy storage so we don't need to do crazy recursive functions any more. There's the http://drupal.org/project/leftandright module by sdrycroft which implements nested sets, and we already have some materialised path in core with the menu system and comment's threading. Materialised path has storage issues with very deep taxonomies, not to mention multiple parents. Nested sets need to be rebuilt when something is inserted or moved within the tree.

However the nested sets keyed with rational numbers implementation allows for the light storage needs and fast retrieval of nested sets, without the terrible update woes - since there's always an available rational number you can use. This gives us the best of both approaches, and while the patch needs tidying up, it looks like not too much code weight either.

Suggested steps for this:
* Get the patch in line with core coding standards and using dbtng for query building.
* At the same time write tests for taxonomy_get_tree taxonomy_get_children/get_parents (we have some coverage, could use more).
* Convert taxonomy_get_tree() to use the new API, hopefully combined with multiple load so we only get the tree then load the objects into it.
* Looks at comments and other core hierarchies to see if they could benefit.

catch - if this is really the right solution, then we should move menu links to it too?

pwolanin: if it does everything which that paper promises, and especially if we can distill it into an easy to use API, then it'd be great to have everything using the same system. Menu is still pretty fresh though, so that seems like a consistency patch after it goes in to fix the monsters though.

Now *this* is interesting stuff! First time that I'll actually *like* reading a mathematical paper :)

Thanks drico & catch!

Subscribing.

pwolanin, wtf? When I wanted to add a very similar notation to the menu system, you ran screaming. See http://drupal.org/node/141866/revisions/159158/view .

The problem with this system (and any other similar) is that we need to understand what depth can we describe with floats as used by database systems supported by Drupal. That will be fun. The patch is full of whitespace errors as well. I would ask Mr. Tropashko (he answers emails :) ) as well what he thinks of Mr. Hazel's encoding.

Correct me if I'm wrong, but a path of 8.32.15.15.4.1.3.43.4 (an example from the Catalogue of Life classification) would give rise to values for the denominator and numerator of ~170M and ~1.5G respectively. This means that we'd be forced to use the float data type, rather than int, resulting in slower queries. I've investigated using the Tropashko encoding before, and found it resulted in much slower search queries compared to both regular nested sets, and materialised path tree encoding.

You do not need to build relatively simple SQL queries like this -- unless you want to make sure they are alterable which is not the case here IMO. count($parents->parent)>0 hardly needed just use $parents->parent is enough. Kindly please run coder module over your code it's a pain to read!

Edit: you are using normal maths operators instead of bcmath at places? Won't that be a problem?

This is looking better - some more code style issues though:

All comments should start with a capital letter and end with a full stop.

Is it worth putting the database table creation into system.install at this point? If so it needs to use schema API - can copy the way cache does it.

* @param $nv
*  numerator value of the term

Should be

* @param $nv
*   Numerator value of the term.

pflv nv, dv etc. - all of these need to be unabbreviated for both variable names and column names.

+    #top level insert
+    #we need in this case the vid in parents

We don't use C style comments, // is fine.

Did you do any benchmarking on tree selection yet, or just insert/update?

@chx, we need to use db_select() for everything here because $table is dynamic - that gets us pluggable/re-usable tree storage same as cache.inc

I think I mentioned already that using the SELECT query builder for these relatively simple queries is unnecessary and bloat. Rule of thumb: only use the select builder if any code, be that yours or someone else's needs to change the query. A static SELECT... query can be ran just fine through db_query.

chx: we can't/shouldn't do db_query('SELECT * FROM {' . $table . '}...' so have to use the query builder here as a matter of good practice, even if it's unnecessary otherwise.

Oh I missed that! Fine then. Next question, why are we using db_and() when they are ANDed by default together anyways?

I think this approach is over-complicated and unnecessary. The "crazy recursive functions" can be avoided by walking up the taxonomy tree when you save a node's terms. The term_node table would get an additional column like "steps." Terms directly applied to a node would have a value of zero in this column. As we recurse up the tree, the number of "steps" increases. We end up with a row mapping every term associated with the node, no matter how far up the tree, to the node.

We then index (tid, steps). It becomes a fast query to find items linked to a tid with any recursive depth limit.

The only tricky part is when you modify a term's parent(s). You have to clear the non-zero steps for the term and insert the updated parents.

@David, while that might help with taxonomy/term/%/$depth pages, it doesn't help at all for rendering the entire taxononomy tree, which is currently done for all non-autocomplete term selection (both node/add and term administration), and has a very wide range of uses cases and implementations in contrib.

@catch If the problem is having so many terms that it becomes slow to build a "select" element offering the whole tree and the question is "How can we build the tree faster?", we're asking the wrong question. If building the tree is slow, then we're putting way too many elements in the select element. We should find a different, better interface for selecting the terms.

(But I'm not saying this work won't see use elsewhere.)

David, yes for the form widgets I'm in favour of getting something along the lines of hierarchical select module or chx's menu chooser patch into core - ideally to replace taxonomy, book and menu select lists. These have both performance and usability issues as they stand now, and the usability ones hit long, long before the queries start getting expensive.

That still leaves http://api.drupal.org/api/function/forum_get_forums/7 which uses taxonomy_get_tree to load the actual hierarchy rather than just calculating term/node associations. Now for forum.module we could do something specific - use materialised path, cache the tree etc. - since there's no multiple parents and likely to be < 1000 discussion forums and limited depth - but that still leaves us with a crappy API for getting trees and branches of trees even if we work around it for all the places it's actually used in core. comment.module's threading desperately needs a revamp too, and it looks like this approach could also be applicable there.

Now it might turn out that this solution won't scale up as much as it needs to but if it does, then we potentially fix a lot of related issues in one go.

@catch Forums needs to have its own denormalized implementation for topic management. Even a perfectly optimized taxonomy system wouldn't fix the scalability issues in the forum module.

@catch - does the approach here support multiple parents?

If not, is it feasible to consider different implementations of materialized path? Assuming we used a 255 varchar column (rather than individual int column), stored numbers as hex, and had 32 bit ints as IDs (i.e. max of 8 chars), plus used a separator character, we could be guaranteed to handle a depth of 28. MySQl 5.0+ and Postgres support longer varchar columns, and of course SQLite is its own beast in terms of this.

I'm not sure what the performance of indexed varchar columns looks like in terms of matching and sorting, but at least all the algorithms involved are immediately understandable.

@pwolanin - as far as I know it does - it'll treat each instance of the term as a different entity.

@pwoloanin: Official limits on VARCHAR column length are deceptive. Many relational databases only store the first X bytes in the main row record and store the rest elsewhere, which is little better than TEXT. Indexes have their own limits, independent of VARCHAR ones.

subscribing

subscribing

Please tell me this isn't seriously being considered for core.

I guess what needs to be asked is, what issues is this trying to fix with Drupal's current taxonomy? I wrote the leftandright (nested set) module as Drupal is unable to handle large taxonomies efficiently (or at all), this patch doesn't fix that issue.

I've attempted to load a large (2M terms) tree into a database using the algorithm that this patch is using, only to find that it results in denominator and numerator values of ~10^15. This results in having to use bigint columns (or in the case of the patch, varchar), which in turn results in having to use a high level of precision for the float_value column. Comparing varchar columns against each other is never going to be as fast as comparing int columns. If we can't handle large taxonomies using this patch, then what is the point in using it at all.

It's pretty efficient...

Really? I doubt that one very much, in fact, looking at the table layout, I'd say it's far from being efficient.

Assuming the purpose of this patch is to improve the speed at which taxonomies can be loaded into Drupal, then it's a large trade off against the speed at which taxonomies can be edited/added.

Drupal's current taxonomy system works for the vast majority of users, why is it necessary to complicate it, and slow it down, for what appears to be zero gain. What needs looking at, instead of the tree storage algorithm, is how taxonomy is being used, and whether or not we can work without methods like drupal_get_tree.

subscribe.
Nice idea. So this is still nested sets instead of nested intervals?
I don't know if what I'm going to say can also apply to nested sets. but nested intervals are also used to represent hierarchy.
The way to pick those rational numbers doesn't look optimal. The size grows pretty fast. I don't know if there is other ways to pick rational numbers. maybe nested intervals with Farey Fractions? with that, 1M records produce numerator/denominator below 30k, at least the data used in the article.
I could work on this for GSoC... if Farey fractions could work...

Good to see people doing nested set work. Recently came across this concept when reading MySQL book. varchar columns seems to not be the way to go. I haven't had a chance to review this patch, but I am putting it on my radar.

I believe that this technique will allow the taxonomy landing pages to pull in all nodes with child tags of that term efficiently.

tagging.

This won't get into Drupal 7, we need to seriously revisit this in Drupal 8 to get it properly sorted out though.

Consider this as well for hierarchical taxonomy handling:
http://drupal.org/project/lineage
I believe it is the best solution for large hierarchical taxo handling.

Ran across this in checking to see what issues are already open about the taxonomy API.

Re: #43. Um. I'm not sure lineage is the best solution for anything other than building taxonomy views more simply. It stores strings in database fields, regexes them to render, and loops over big arrays to sort an render hierarchical taxonomy lists. The storage method may be faster for large, complicated hierarchies, but the module itself, while useful for views plugins, contains redundancies and probably isn't that performant.

Crossposting #1207326: Refactor taxonomy hierarchy API for performance, consistency, and convenience.

We should look at entity_tree as the basis for a new (performant) tree API be used across menu_links, book, taxonomy, comment, etc

Or at this https://www.drupal.org/project/tree

@ivanjaros - we already use a variant on materialized path for menu links since Drupal 6.

Thank you for creating this issue to improve Drupal.

We are working to decide if this task is still relevant to a currently supported version of Drupal. There hasn't been any discussion here for over 8 years which suggests that this has either been implemented or is no longer relevant. Your thoughts on this will allow a decision to be made.

Since we need more information to move forward with this issue, the status is now Postponed (maintainer needs more info). If we don't receive additional information to help with the issue, it may be closed after three months.

Thanks!

This is still overall a scalability issue in Drupal core, and there are some contrib approaches these days like https://www.drupal.org/project/entity_hierarchy which uses nested sets.

Moving back to 'active' but converting to a plan.