Find packages starting with a string with apt or aptitude

Searching for packages with apt-cache or aptitude is quite easy, but what if we want to find a package name starting with a specific string?

With apt-cache:

$ apt-cache search mysql | grep '^mysql'
mysql-cluster-client - MySQL database client (metapackage)
mysql-mmm-agent - Multi-Master Replication Manager for MySQL - agent daemon
mysql-mmm-common - Multi-Master Replication Manager for MySQL - common files
mysql-mmm-monitor - Multi-Master Replication Manager for MySQL - monitoring daemon
mysql-mmm-tools - Multi-Master Replication Manager for MySQL - tools

With aptitude:

$ aptitude search ^mysql
p   mysql-admin  - GUI tool for intuitive MySQL administration
p   mysql-client  - MySQL database client (metapackage)                              
v   mysql-client-4.1  - 
p   mysql-client-5.1  - MySQL database client binaries
i A mysql-client-core-5.1  - MySQL database core client binaries
[...]