[performance] DB caching for \Drupal\taxonomy\TermStorageController::loadTree()

Just for the record: I don't think we need an extra table for cached taxonomies. The plain cache table contains only a single entry on a default Drupal install, there is plenty of space, especially for cached itesm that won't change that often.

Looks good, some benchmakrs would indeed be helpful.

I created a vocabulary (page type, multiple hierarchy, related terms, no freetagging, multiple select, not required, 0 weight) and added a term, but "list terms" keeps showing "No terms available." and the terms aren't showing up as possible related terms or parent terms when I try to add another term.

If I then revert to HEAD the terms will show up. They are being inserted correctly but apparently the cache check isn't finding them.

patch in #11 didn't upload.

If this issue is indeed a duplicate of http://drupal.org/node/83057 , then it is not a feature request but a bug.

never mind about patch in #11. I notice a bit late that it's a duplicate post of #10.

Subscribing.

*Subscribing*

get in in dudes ^^

This needs a re-roll after the split patch went in.

Reroll. While this is an API change (an additional boolean $cache parameter in taxonomy_get_tree()), it doesn't break anything. So please don't make this patch wait for D7!

The changes in the admin area of the previous patch are no longer necessary, all of that is already fixed.

This is potentially a huge speed up for taxonomy browsers, and also for the Hierarchical Select module.

Forgot the patch...

The previous patch included a change to index.php. Use this one instead.

Better title.

Well this applies cleanly, the only implementation in core that's obvious is the forum inde and that works fine with a couple of levels of hierarchy. Not sure how to go about testing the performance implication to actually get this RTBC though.

The index improvements are now over at: http://drupal.org/node/164532

See RobRoy's tests in #7?

Well in that case it's has had reviews by various people, it's a big boost, and it's a small API change. The main boost within core would be forum_get_forums, which is a very slow query. Patch applies cleanly and doesn't throw up any errors etc.

If the API bit stops it getting into D6, it's a decision for Goba and Dries to make, so bumping to their queue.

I looked through the patch. Comments:

- having a specific cache_clear_all() before a generic one looked like interesting, but I see that the generic only clears cache_page and cache_block, so we need the specific clears still
- removing the array cast from taxonomy_del_term()s taxonomy_get_term() modifies the API for module_invoke_all('taxonomy', 'delete', 'term', $term) called later
- the caches seem to be very fine grained based on vid, parent tid, depth and max depth, which in combination could make up for a huge number of cached entries, which could easily clutter up the generic cache table (I know adding another cache table might be even more API change now)
- what testing is required still to clean up: "// Don't cache tree if empty, may be able to remove this after more testing."?

The benchmark looks impressive for sure, but there were changes in the code since then, so it should be rebenchmarked IMHO. Also I wonder what killes has to say about the current state of the code.

I am marking needs work because of the array cast API change. Others seem to need some discussion, but might not need code change.

I walked into this bug again today. I'll reroll with Gábor's comments taken into account.

Hi there,

could anybody give me a patch for Drupal 5.7? Or tell me which patch I can use?

Thank you!

Subscribing. The inability to reset the static cache in taxonomy_get_tree() makes it rather difficult for the drupal.org testing installation profile to create forums and containers via drupal_execute().

The static cache is also a problem for migration code that automatically creates terms and show a node edit form. If the pathauto module is active, its hook_taxonomy calls taxonomy_get_tree which caches the tree after the first term is added, and the rest doesn't show up in the node form. They do, however, get created.

Subscribing.

Add tag.

Subscribe.

I ran into this issue on D6, looking at the D7 code, this now uses drupal_static to declare the variables. So they can be cleared.

Should this ticket be put back to D6 where the issue persists?

This is still a performance issue in HEAD and that was the main part of the patch IMO - maybe open a separate issue for D6 but reference this one for the $reset param.

I have hacked a D6 taxonomy module to do some caching and cache clears. I may see if I can port this to D7.

Personally I don't think that taxonomy_get_tree can scale as a function, if you have a very large vocabulary it takes an age just to deserialise the data. My preferred approach would be to only allow something like and Iterator, or dom like functions (get parents, get children, get next sibling) for taxonomies and terms, but I think that is probably too much of an API change at this stage.

Thoughts anyone?

We can't change the API, at most tweaks. If there's something which helps some cases, that'd be great. We really need to work on pluggable systems, paging etc. in Drupal 8.

This patch might do it. From a look at the code places which edit terms call cache_clear_all(). The unit tests pass locally.

I have changed the title for clarity. I think the other issues raised in this ticket originally have been split out.

 function taxonomy_get_tree($vid, $parent = 0, $max_depth = NULL, $depth = -1) {
   $children = &drupal_static(__FUNCTION__, array());
   $parents = &drupal_static(__FUNCTION__ . 'parents', array());
   $terms = &drupal_static(__FUNCTION__ . 'terms', array());

   $depth++;
 
+  // If the function is being called with default arguments see if a
+  // cached copy exsists.
+  if ($parent == 0 && $max_depth == NULL && $depth == -1) {
+    if ($cached_tree = cache_get('taxonomy_get_tree_' . $vid)) {
+      return $cached_tree;
+    }
+  }  
   // We cache trees, so it's not CPU-intensive to call get_tree() on a term
   // and its children, too.
   if (!isset($children[$vid]))

$depth is never -1, because it was incremented three lines above. (BTW, unrelated to this issue, but wouldn't it be more intuitive to set the default value to 0, remove the $depth++, and then instead pass $depth + 1 in the recursive function call?).

You should return $cached_tree->data instead of the entire cache object, but ...

Instead of returning early, why not move the cache_get() into the if (!isset($children[$vid])) { block and then always fetch the cached value, even if $max_depth != NULL and $parent != 0. Then just put the cached value into $children[$vid][0] and let the rest of the function do its magic.

    cache_set('taxonomy_get_tree_' . $vid,$tree);

Missing space after comma.
I suggest using colon as separator before $vid in the cache cid. This pattern is used elsewhere in core.

I'm not sure why you removed the new cache_clear_all('taxonomy_get_tree_' . $vid, ...) calls? cache_clear_all() without arguments only clears cache_page and cache_block.

Thanks for the review, I'll try to get round to fixing. Most of the comments make sense, the only one that I would question is:
Instead of returning early, why not move the cache_get() into the if (!isset($children[$vid])) { block and then always fetch the cached value, even if $max_depth != NULL and $parent != 0. Then just put the cached value into $children[$vid][0] and let the rest of the function do its magic.
This would create a lot of cache keys for vocabs with a deep hierarchy. Many of these cache keys would only be set when taxonomy_get_tree calls itself. So would not give a performance gain.
Where as you get the biggest performance hit when querying the root of a vocabulary. So there would be a bigger cache for very little benefit most of the time.

Ideally you could set a flag to determine weather you are on a recursive call or calling the function from elsewhere and only cache on the non hierarchical calls. But this may require an API change so I went with the simpler option.

Ideally you could set a flag to determine weather you are on a recursive call or calling the function from elsewhere and only cache on the non hierarchical calls.

You can use $depth for that. However, on second thought I don't think my initial thought about always using the cache can be implemented as easy as described, but something can be done:

WRT to $max_depth you could get the cached copy of the whole tree and the prune it in PHP code without hitting the database.

Using the cached copy of the whole tree for $parent != 0 is a bit tougher, because there is no easy way to find the appropriate subtree in the array unless you also save the $parents array to the cache. With this you can find the path of parent tids on the way from the specified $parent to the root and then use that to descend down through the cached tree. I don't know how this will perform.

#42: taxonomy_get_tree_cache.patch queued for re-testing.

Code seems fine, but it really seems to be a solution looking for a problem.

Would anyone care to comment why this is important? =)

With very large taxonomies, taxonomy_get_tree can become a bottleneck on quite a few pages. I think some of the other changes in D7 improve this, by not calling it so much.

It may be worth testing a D7 install with a 100,000 term vocabulary, to see how it performs.

Subscribing.

setting to "needs work" since the concerns expressed in #45 haven't been addressed.

+1 subscribing

now that taxonomy_get_tree() memory issues is done, is there a genrall feeling as to whether this is needed any more.

#42: taxonomy_get_tree_cache.patch queued for re-testing.

#42: taxonomy_get_tree_cache.patch queued for re-testing.

Moving this to D8.

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

taxonomy.tree.patch queued for re-testing.

So far this seems to be working for me:

function taxonomy_get_tree_with_reset($vid, $parent = 0, $depth = -1, $max_depth = NULL, $reset = FALSE) {
  static $children, $parents, $terms;

  if ($reset) {
    unset($children[$vid]);
    unset($parents[$vid]);
    unset($terms[$vid]);
  }


  $depth++;

  // We cache trees, so it's not CPU-intensive to call get_tree() on a term
  // and its children, too.
  if (!isset($children[$vid])) {
    $children[$vid] = array();

    $result = db_query(db_rewrite_sql('SELECT t.tid, t.*, parent FROM {term_data} t INNER JOIN {term_hierarchy} h ON t.tid = h.tid WHERE t.vid = %d ORDER BY weight, name', 't', 'tid'), $vid);
    while ($term = db_fetch_object($result)) {
      $children[$vid][$term->parent][] = $term->tid;
      $parents[$vid][$term->tid][] = $term->parent;
      $terms[$vid][$term->tid] = $term;
    }
  }

  $max_depth = (is_null($max_depth)) ? count($children[$vid]) : $max_depth;
  $tree = array();
  if ($max_depth > $depth && !empty($children[$vid][$parent])) {
    foreach ($children[$vid][$parent] as $child) {
      $term = drupal_clone($terms[$vid][$child]);
      $term->depth = $depth;
      // The "parent" attribute is not useful, as it would show one parent only.
      unset($term->parent);
      $term->parents = $parents[$vid][$child];
      $tree[] = $term;
      if (!empty($children[$vid][$child])) {
        $tree = array_merge($tree, taxonomy_get_tree_with_reset($vid, $child, $depth, $max_depth));
      }
    }
  }

  return $tree;
}

There isn't a current patch in this issue.

BTW - I'm not (yet) familiar with patching - so if someone could create a patch that would be great.

When I've created a patch for a project I'm working on I'll come back to this and create a patch if needed.

Regarding #64, check out:
http://drupal.org/patch
http://drupal.org/patch/create

It's not too complicated, I promise. :)

This is a tricky one.
Suppose we need to store only tree structure because whole entities are entity cache territory.
otoh any static cache affect "statability" of the controller/service...

So maybe better to abstract "tree-handling" into separate service?
We already have one after https://www.drupal.org/node/2226481
This should allow contib to implement a site-specific handling and caching?

PS: I know that @amateescu have a Tree module ported for d8 so glad to get his opinion on that

My opinion is that I will just do it in contrib and we can see later about moving it to core :)