Software As A Service One Database Or Many

I am creating a software as a service product and I am going back and forth on a database design issue.

Should I create a separate database for each new customer, or create one big database and store all customers and do the standard relational database design idea.

The clear choice for me is create a new database for each new customer, but the only problem is rolling out schema updates and bug fixes. If I have 5000 customers and then 5000 databases, how to manage creating a new table, editing a column name or data type, editing a stored procedure, or creating a new trigger on 5000 separate customer databases?

So, there are many benefits for making a new database for each customer that I can think of:

With separate databases, customer’s data are each separate entities, it is the whole encapsulation/modular design idea. It is impossible to get data out of a different customer databases. With one large database a query that forgets to include the WHERE clause selecting a customer_id can cause havoc.

With one large database all customers are located in one, actually maybe a few, files. So many of the selects, inserts, deletes will scan all customers data, when all they ever need or care about is their own data. Even with indexes, inserts and deletes become slower with one large database as the size of the database increases.

What happens if you have one large database with 100,000 customers and say a table with 30 million records? Then you need to spilt the database across multiple servers, a cluster, because one machine inst cutting it. With a single database design, cluttering becomes a headache. With multiple databases, no problem, just setup a new server and start adding new databases.

Also, last thing is database integrity. With one large database if you database gets corrupt or accidentally deleted, or modified in a way which causes unwanted results all your customers are screwed. With multiple databases problems only effect the one single customer, again each customer is a separate entity.

The only problem of course with multiple databases, and the root of my question; how do I manage database schema maintenance? How do I effectively roll out changes to each customer database schema?