Ben Sampson has a tutorial posted to his site for the Laravel users out there sharing some tips about speeding up your database queries when using relationships between models.
Adding indexes to your database tables is a great way to get some extra performance out of your application, especially if you have a large amount of data in your tables. They should be used sparingly and only on identified slow queries, as they have implications of their own such as increased table size and increased RAM usage. But those potential drawbacks are well worth it when you can get a query down from a 3 seconds 15 milliseconds with 5 minutes of work. The effects are particularly noticeable on polymorphic / many to many polymorphic relationships.
He then includes the code required to create the indexes on your tables (either a single column or a compound index involving more than one column) in your migrations. He also provides code examples showing how to use foreign keys to improve one-to-one/one-to-many relationships. More examples include optimizations for many-to-many relationships and polymorphic relationships.