Well, there are several problems with this analysis when you go very large (>10000 machines): - For many applications, it's easiest to put the state of the obj

Well, there are several problems with this analysis when you go very large (>10000 machines): - For many applications, it's easiest to put the state of the object in the primary key, and thus point reads will fail when something gets deleted. This has other problems though with hotspotting and compaction during deletes. The deleted table doesn't really solve this either. - For storage systems, GC is critical functionality to implement. Most systems whether they want to believe it or not are glorified storage systems. Garbage collection is hard to do at scale, and I've never seen it implemented as SQL statements rather than code. Especially for GDPR etc. - For large scale distributed systems, foreign key constraints are rare if impossible to implement with reasonable latency, so they don't exist either way. I haven't worked on a system in >15 years that had fk constraints. - For large scale restores where you need to undelete trillions of rows, keeping the rows basically pre-assigns the distribution of writes. When you have to re-create the rows, you tend to get intense hotspotting and failures along the way as you attempt to load balance on the keyspace of the writes. A deleted records table is good for smaller (<10000 machine) systems when latency between nodes can be kept within the same campus. It can really improve performance of your GC if reading by column isn't fast compared to reading by table.