Per user encryption doesn't work in real systems. These have been implemented for several decades and no one uses them because they have pathologically terrible scalability and performance. The simple act of requiring encryption of individual user data forces the use of extremely suboptimal data structures relative to what would be used in the non-encrypted case.

A single AES encryption block is 16 bytes; internal storage of records is managed in terms of individual bits if you don't encrypt them. You also can't compress data encrypted in this way, which is table stakes for databases. The encryption key schedule alone for a single record will be much larger than the typical record! Requiring a per-user encryption key has the unfortunate effect of bloating database storage and memory requirements by at least 10x, while massively reducing computational throughput.

The design of delete-efficient database kernels is an interesting unsolved problem in computer science. No one knows how to do it. People that think there are trivial solutions have not studied the problem adequately. It hasn't been a priority to solve this problem, but its reputation for being theoretically difficult is well-deserved.