I insert all of my Web server hits into a MySQL database, and a few of the queries I run were really slow. Then I discovered that using FULLTEXT Searches, as opposed to LIKE or REGEXP, were far superior.
Cut the query time by 80%. Ouch.
If you use non-binary CHAR, VARCHAR, or TEXT columns, consider a FULLTEXT Index on those columns.