You can use row based encryption and store the encrypted encryption key alongside each row. You use a master key to decrypt the row encryption key and then decrypt the row each time you need to access it. This is the standard way of implementing it.
You can instead switch to a password-based key derivation function for the row encryption key if you want the row to be encrypted by a user provided password
This has been tried many times. The performance is so poor as to be unusable for most applications. The technical reasons are well-understood.
The issue is that, at a minimum, you have added 32 bytes to a row just for the key. That is extremely expensive and in many cases will be a large percentage of the entire row; many years ago PostgreSQL went to heroic efforts to reduce 2 bytes per row for performance reasons. It also limits you to row storage, which means query performance will be poor.
That aside, you overlooked the fact that you'll have to compute a key schedule for each row. None of the setup costs of the encryption can be amortized, which makes processing a row extremely expensive computationally.
There is no obvious solution that actually works. This has been studied and implemented extensively. The reason no one does it isn't because no one has thought of it before.
You’re not wrong about the downsides. However you’re wrong about the costs being prohibitive on general. I’ve personally worked on quite a few applications that do this and the additional cost has never been an issue.
Obviously context matters and there are some applications where the cost does not outweigh the benefit
I think you and the GP are probably talking about different scale orders of magnitude.
Very likely!
But I think there must also be constraints other than scale. The profit margins must also be razor thin.