I believe I have a solution for this, but I'm going to allow others to reply before I post a spoiler

When your user changes data in the database,
You want to update the counts in any case.
So you write a small function
That updates this junction
To keep the master counts right any way(s).

- © 2009 httpwebwitch enterprises

In case the limerick is not clear - just a small function to update the total count any time any changes are made to an "item" is all that's needed. I have a similar system in place: we track inventory, and the three states are in stock, pending, and sold. Cust. orders an item, it gets moved to pending; stock is untouched, but what displays publicly is stock minus pending. When the item is shipped, pending and stock are decremented by quantity, sold is incremented by quantity. These are, similar your system, stored in the products "master" stock, pending, and sold fields for quick access and low overhead, rather than futzing about with the inventory tables.

Iambic pentameter is supposed to have accents on alternating syllables, so this isn't quite IP. But it's got ten syllables per line so please don't flame me. I'm not Shakespeare.

moving from one node into another
affects the nodes above it in this way
if the nodes share a common ancestor,
common node's count of children doesn't change.

put ancestry of nodes in two arrays
remove any nodes they have in common
these are nodes that will not be affected
what you're left with are the ones that will change

in each element of the "from" array,
decrement the count of it by just one
in each element of the "to" array,
increment its count likewise by just one

what you end up with is a nice function
that gladly accepts two parameters
the first is the node the item's leaving
the second is node it's going to

if you are adding a brand new item
you leave that first parameter as null
it decrements no nodes because it has
no nodes to decrement so it gives up

the added item goes into a node
which shares no common ancestry with null
its ancestors are all incremented
by 1up all the way up to the root

if you are deleting an old item
leave the second parameter as null
just as before there is no ancestry
and so all its ancestors subtract one.

in this way you can update your treenodes
and keep the item counts denormalized
it's quite efficient for the database
and flexible enough to handle change

[edited by: httpwebwitch at 8:31 pm (utc) on Sep. 1, 2009]

In other words:

function recalculate_itemcounts($from,$to){
$fromarr = get_ancestry($from); // returns an array
$toarr = get_ancestry($to); // returns an array
$f = array_diff($fromarr,$toarr);
$t = array_diff($toarr,$fromarr);
foreach($f as $v){
$query = "UPDATE categories SET itemcount = itemcount - 1 WHERE categoryid = ".$v;
mysql_query($query);
}
foreach($t as $v){
$query = "UPDATE categories SET itemcount = itemcount + 1 WHERE categoryid = ".$v;
mysql_query($query);
}
}

What if the user changes the values by more than 1? (Or is that not possible . . . . )

oh, like if you add a whole bunch of items at once?

if they're all added/deleted/moved to/from the same categories, then I suppose you increment or decrement by n, instead of by 1.

I'd be inclined to just run the function multiple times (*ducks to avoid projectiles from the DBA*)

Right, I was thinking in terms of inventory per my previous example, if someone buys two widgets, etc. Easy change.

function recalculate_itemcounts($from,$to,$quantity){

As a programmer, you found that recursing through the entire database to count items was too costly, especially since it's done on every page view

Why don't you do that after the inventory has been modified? It's easy to write, and may be easier than updating everything one by one.

correct Dabrowski, the function described above as the solution is run after inventory is modified. It reads and writes only the records that will be changed by the operation, so it doesn't need to iterate recursively through the entire tree.

I see.

Well, IMO, if the database is so huge you can't do a recursion on a page view basis, the server must be pretty well equipped. It couldn't take more than a couple of seconds to do a recursion which would be acceptable if it was done only when an item was changed.

In fact, you are already doing a recursive lookup to get your ancestry tree.

...or you could add an index for your items based on item and category id's.

Then if you perform your recursion on the index it should execute instantly.

Using this method I got a database containing over 1,000,000 rows to search in less than 2 seconds, on a machine with a very low spec that I just use for messing around on.