O próprio Heroku fornece apenas suporte direto para o PostgreSQL. Muitas aplicações (especialmente as do Rails) podem ser migradas do MySQL para o PostgreSQL com poucos problemas.
Para situações em que você não pode migrar facilmente, você pode usar um complemento Heroku de terceiros .