Вячеслав Плиско

Не совсем понятна задача, PDO без всяких обёрток из коробки является DBAL. А вот обёртки учиться писать стоит, особенно с итерациями по увеличению функциональности, чтобы заранее продумывали точки входа и расширения. У меня такая обёртка обязательная при обучении джуниоров, профит огромный.

По поводу PDO и поддержки разных баз данных, то эта идея из коробки не работает, т.к. можно писать кастомный SQL, который может не поддерживаться всеми БД, поэтому нужен как минимум Query Builder.

Вам нужно почитать про джойны в доке мускула и вот неплохая вроде статья из поиска anton-pribora.ru/articles/mysql/mysql-join/
Ну и, соотвествтенно, подджойнить таблицу несколько раз используя алиасы.

Для кеширования в php, если система нераспределённая, то оптимальнее использовать акселераторы типа apc (apc_fetch,....) или шаренную память shmop.
Редисы и мемкешы нужны если доступ к кешу должны иметь несколько серверов, а так это не самый лучший вариант, так как это фактически отдельные сервера, пускай и очень быстрые, но с соотвественными летенси при обращении.

приложения с хранимыми процедурами поддерживать сложнее, т.к. логика размазана.
невозможно использовать нормальное кеширование и будут проблемы с маштабированием. лучший запрос — это тот, который не делается, а для этого нужен умный кэш.

очень советую погуглить по данной теме. но в честь праздника дам готовый ответ, но обещайте погуглить, очень полезна информация
SELECT pk, data
FROM test AS r1 JOIN
(SELECT (RAND() *
(SELECT MAX(pk)
FROM test)) AS id)
AS r2
WHERE r1.pk >= r2.id
ORDER BY r1.pk ASC
LIMIT 1;

тестировал на миллионе реальных записей, шустренько.

xdebug для профайлинга и pinba pinba.org/wiki/Main_Page

уберите MyISAM, она на уровне таблиц, а не записи.
проведите денормализацию, например жанр можно хранить в таблице с песней или засунуть в SET
почему вы используете inner join а не left join для присоединения таблиц?

у вас явно создаётся temporary table, отсюда вся нагрузка. можете поэксперементировать с view.