First, the configs then the mods.
* Machine is a Dell CS24-SC, with dual Xeon L5420 (2.5GHZ quads) and 24GB of DDR2 667 RAM and a single 500GB 7200RPM drive.
* Software is Ubuntu 13.04 64-bit with MariaDB on MyISAM tables.
The MyISAM part is important, because the single biggest speed improvement came from using a feature that was only available on MyISAM with my version of MariaDB (5.5) -- and that's FULLTEXT indexes. As was mentioned before several queries were missing some indexes and fixing those helped speed, but with a small modification to the PHP and adding the fulltext indexes we (me & KDad) have gotten some massive speed improvements.
When I was originally voluntold to help fix the performance of our indexer, the kind of tweaks were down to adjusting buffer caches and going to InnoDB -- inconsequential things that were really just masking the underlying performance problems. Our searches return in well under a second, even for complete gibberish queries like "flobbleywop" (a good hit like "oakenfold" is about 0.75 seconds). These results are
with a backfill running as well with 3.4 million releases and 58 active groups, and at this point we are limited by IO on the HDD.
Now, the downside. These modifications only work if you're able to use FULLTEXT indexes, which for most versions of MariaDB is only MyISAM. The good news is that its fast enough it doesn't really matter.
What to change:* Convert your tables to MyISAM
* Run the following SQL to add the missing indexes I identified so far
CREATE INDEX ix_releases_searchname ON releases (searchname);
CREATE INDEX ix_partrepair_attempts ON partrepair (attempts);
CREATE INDEX ix_binaryblacklist_groupname ON binaryblacklist (groupname);
CREATE INDEX ix_binaryblacklist_status ON binaryblacklist (status);
CREATE INDEX ix_releases_groupid ON releases (groupid);
CREATE INDEX ix_groups_id ON groups (id);
CREATE INDEX ix_category_parentid ON category (parentID);
CREATE INDEX ix_category_id ON category (id);
CREATE INDEX ix_movieinfo_title ON movieinfo (title);
CREATE FULLTEXT INDEX ix_releases_searchname_ft ON releases (searchname);
* Open releases.php in a text editor and follow this pattern:
Search for "and releases.searchname like". This will get you to the right area. The code comes in blocks of 3 and is repeated all down this file (srsly guys wtf). You can't just copy+paste my code below because the variable names will be overwritten, you have to modify your code to look the same for every instance.
if ($intwordcount == 0 && (strpos($word, "^") === 0))
$searchnamesql = sprintf(" and releases.searchname like %s", $db->escapeString(substr($word, 1)."%"));
elseif (substr($word, 0, 2) == '--')
$searcnamehsql = sprintf(" and not match(releases.searchname) against (%s)", $db->escapeString(substr($word, 2)));
else
$searchnamesql = sprintf(" and match(releases.searchname) against (%s)", $db->escapeString($word));
What I did was change the "and releases.searchname like %s" to "and match(releases.searchname) against (%s)" and then removed the "%". & ."%" parts from the escapeString call. You have to modify the second and third line of each block, and there's about 8. The "match/against" code is specific to full text indexes and is the reason for the speed.
I'm open to any questions or critiques

Feel free to try it on your own. I realize the indexes I added may be redundant in some cases, and I'll eventually get around to tuning those once the DB size becomes important again.
edit: thank you to everyone who's tried this and provided feedback!