Rob Church and Timwi wrote (regarding frequency of edits that change categories):

...

Probably higher than that, to be honest, especially with all those Wikipedians running around, dealing with Special:Uncategorisedpages, and correcting stub templates and so forth.

Also don't forget about vandals just blanking a (categorised) page, plus the immediately following revert.

Okay, well, so that we have some quantified data and can think make a firm decision one way or the other about the suitability of a MyISAM table for category intersections, I'll take a random sample of edits (of some statistically significant size - doesn't take much) and see how many involve a category change and report back.

And, as always, anybody else got any ideas? If this can't work, I can't think of anything else beside a separate Lucene index (which will then not be real time and have to be updated every so often) as I don't think excluding large categories from an intersection search is an acceptable solution.

Thanks, Aerik