Make WordPress Core

Opened 17 years ago

Closed 16 years ago

#3985 closed defect (bug) (fixed)

_get_cat_children is very inefficient

Reported by: ryan's profile ryan Owned by:
Milestone: 2.2 Priority: high
Severity: major Version: 2.1.2
Component: Administration Keywords: 2nd-opnion category optimization hit-list
Focuses: Cc:


_get_cat_children is slow and stupid. Doing DB queries to get the children of each cat is faster than using _get_cat_children.

One proposal is to store an array that contains the hierarchy. array(parent => child, child => grandchild). Categories that have no children would not be present in the array. The drawback is that this would require keeping the array in sync with category changes. Any other suggestions to make creating the hierarchy more efficient while minimizing DB queries?

Attachments (1)

3985.diff (2.0 KB) - added by ryan 17 years ago.
First cut at caching category children

Download all attachments as: .zip

Change History (21)

#1 @ryan
17 years ago

See also #3614

#2 @JeremyVisser
17 years ago

Please forgive my ignorance, as your PHP skills would be way better than mine, but when I do hierachies in arrays, I generally use matrixes (matrices?):

    parent => array(
        child => array(
            grandchild => 'value'

Is this what you meant, or is your method better performance-wise? Or should I just stay away from Trac? ;)

#3 @ryan
17 years ago

Acutally, we should probably do it with left and right pointers.

parent => (root, child), child => (parent, grandchild)

#4 @charleshooper
17 years ago

  • Cc charleshooper added

I agree.

If we use the hierarchy method mentioned above we would recursively have to search through the array whereas with the left and right pointer-method it wouldn't matter how "deep" the array in question was, the search is simple.

I have some free time tonight, I'd love to get some work done on this.

#5 @charleshooper
17 years ago

  • Keywords 2nd-opnion added
  • Owner changed from anonymous to charleshooper
  • Status changed from new to assigned

Just clarifying some things here -- feel free to correct me if I'm wrong in these

  • Syncing the array should be done only when categories are created, edited, or deleted
  • A "sanity check" should be done upon access to the Manage Categories page. This is how it's done for plugins anyways, so I'm just trying to keep our methods consistent.

On second thought, perhaps instead of a sanity check this could be a good time to rebuild the array completely from the database.

I would also like this array to be storable using Wordpress' built-in caching functions.

#6 @charleshooper
17 years ago

For quickly and efficiently building the array I recommend we add a table to the schema: wp_cat_hierarchy

wp_cat_hierarchy would consist of 2 columns: parent_id and child_id. There would be a unique key on the pair. This would allow us to quickly and efficiently build our hierarchy array.

#7 @foolswisdom
17 years ago

  • Milestone changed from 2.2 to 2.3

#8 @ryan
17 years ago

  • Keywords hit-list added
  • Milestone changed from 2.3 to 2.2

Actually, I'd like to try to get this into 2.2. WP sucks with a large number of categories because of this bug.

#9 @ryan
17 years ago

For 2.2, I think an array approach would suffice. I'd rather not muck with new tables right now.

#10 @foolswisdom
17 years ago

  • Priority changed from low to high
  • Severity changed from normal to major

#11 @charleshooper
17 years ago

  • Owner charleshooper deleted
  • Status changed from assigned to new

17 years ago

First cut at caching category children

#12 @ryan
17 years ago

Patch creates array of categories and their children and sticks it in the options DB. Array is consulted to avoid descending through _get_cat_children() when there are no children. Next pass will remove the recursion.

#13 @ryan
17 years ago

(In [5178]) Cache category hierarchy to make cat listing faster. Phase 1. see #3985

#14 @ryan
17 years ago

That change avoids walking the category list for cats that have no children. With a categories table containing 3100 cats arranged in a flat hierarchy, time need to list categories went from minutes to seconds. Next I need to eliminate recursion altogether to sped up listing for those who use lots of hierarchy.

#15 @ryan
17 years ago

(In [5179]) Category listing speedups. see #3985

#16 @yskin
17 years ago

What about replace


in clean_category_cache() to

update_option('category_children', ""); 

clean_category_cache() will be called when publishing or editing posts. Category_children option will be deleted and added very often.

An empty string can work well, because _get_category_hierarchy() use is_array() to check category_children option. If it is not an array, it will be identified as invalid cache.

#17 @rob1n
16 years ago

Or change it to update_option('category_children', array());

So it gets serialized and returns a blank array, so it's a valid cache.

#18 @ryan
16 years ago

(In [5295]) Fix variable collission in _get_cat_children. see #3985

#19 @ryan
16 years ago

(In [5296]) Fix variable collission in _get_cat_children. For 2.2. see #3985

#20 @ryan
16 years ago

  • Resolution set to fixed
  • Status changed from new to closed

Let's call this good enough for now.

Note: See TracTickets for help on using tickets.