Your first step could be (and possibly *should* be - although I can't quite tell from your description where the bottleneck lies) optimising the database, and your queries. DB & query optimistion is a fine art, and I suggest consulting the documentation for your specific database. Most have fairly lengthy sections on optimisation (and how to view / interpret query plans, etc).

9000 'things' isn't really a hell of a lot for most half-decent DB systems (even if the 'things' span multiple tables, requiring joins). I've run plenty of systems with many more, and (after optimising) had few issues with performance.

Besides that, I'd also look at whether your hardware is up to the mark - that's a fairly easy thing to guague, just install some good performance statistics software.

Application changes would be my last port of call. But even then, I'd first look at individual modules, and think about profiling them, and possibly optimising code if possible (although I wouldn't spend a whole lot of time on this, unless there's something really obvious). Also, I'd look at CPAN and see if there's something already there that's been properly optimised for what I'm trying to do (maybe even as a replacement for another CPAN module I'm already using.)

Finally, I'd begin to consider the type of architectural changes you're talking about. Although these types of changes may be the most sure-fire way of improving performance (because they're completely customised to your specific problems), they're also the most likely to introduce other problems.