When should you think about splitting up your database, you know, sharding it?

Hey everyone, I've been running into some serious scaling issues with a big relational database lately. Queries are taking ages during busy times. I'm thinking about sharding, but man, that seems like a huge project. What have you guys experienced with sharding? When did you finally decide to go for it, and what was the hardest part?