OTOH, looking for images on Commons in "GFDL" and "Buildings in Berlin" took ~2min. Might be the giant GFDL category, or the toolserver, or both. I'll try to fiddle with it some more utilising cat_pages/cat_files.
Hah! By using small categories first, then restricting possible page_ids in the query for the larger categories, I got it down to 3 sec!
Testing "Buildings in Berlin" and "PD Old" (to avoid false timings from cache) : < 0.6 sec.
This way, adding more intersections with small categories (where currently "small" is < 20.000 pages) will actually make the query run faster.
I think I'm onto something here. Then again, I thought that before :-)
Magnus