Always start with measurement. Until you know where any bottlenecks are, you don't know what to improve. "Without even having peeked at any performance data" you're unlikely to make the right call - or at least, I frequently find that I make incorrect guesses about where performance is hurting. Maybe you're better at guessing than me :) (Of course, it may well be in the database in your code...)
Measuring tools can be as simple as log statements to see how long different types of requests take, to full profilers, query analyzers etc. On the database side, you'll almost certainly want to use EXPLAIN to look at the query execution plans... but before that you'll want to know which queries are hurting you in the first place, and more than that, which requests to the web service itself are costly.