DELETE is expensive at a deep fundamental level that we don’t think about much in computer science because we are more worried about losing data. The article is about Postgres but it generalizes. We don’t actually have any computer science for DELETE optimized databases. I’ve idly looked into delete-optimization in databases as thought experiments, since there isn’t much in the way of literature on it, and it is far more difficult than I think many people intuit. The article is partly a manifestation of this reality.

I think the nature of DELETE is one of the more interesting open problems in computer science. It is one of those things that, when we require precision, turns out to be very difficult to define.

Yes...but it goes even deeper.

For example, in physics, the paradox of Maxwells Demon is resolved when you consider the cost of deleting data:

"In 1982, Charles Bennett showed that, however well prepared, eventually the demon will run out of information storage space and must begin to erase the information it has previously gathered.[8][12] Erasing information is a thermodynamically irreversible process that increases the entropy of a system."

https://en.wikipedia.org/wiki/Maxwell's_demon#Recent_progres...

It is also difficult for humans to delete information. In my humble and only a little facetious opinion this is one of the main drivers for ever new "To Do" apps: the existing app gets full because deleting is too hard, so we start fresh with a new app. The app isn't the point, the starting fresh is.

The underlying reason there being that the cost of maintaining small (to do) notes can be greater than the value of the note, which is one of the reasons we still use little scraps of paper and other mechanisms that will effectively auto-delete.

Understanding the micronote lifecycle: improving mobile support for informal note taking

https://dl.acm.org/doi/10.1145/985692.985779

What about LSM trees? Something like RocksDB is very efficient at deleting. A delete operation is a tiny write (a tombstone) and then the actual deletion is done via compaction in the background with entire tablets being freed at once when the live data is evacuated. It's actually most efficient when deleting large ranges - when just replacing data it's not so efficient due to the write amplification.

That said, I agree with you in general. An under-used technique is to simply encrypt everything and then use a key store that is guaranteed capable of deleting data. This makes it easy to comply with legal deletion requests even across backups, though of course, you need to manage the keys very carefully and ensure that they are also backed up.

There was a common thread through all of my algorithms and data structures class: Hash maps, b-trees, etc. are all beautiful structures until you add a delete operation and have to start dealing with all those little holes... Removing data complicates everything.

> We don’t actually have any computer science for DELETE optimized databases.

Depending on how much deleting and when, there might be engineering if not science for this.

If everything is deleted on a schedule, partitioned databases and dropping whole partitions as they expire is a well worn path. Soft delete and compaction also works pretty well if most, but not all things will be deleted. A generational garbage collection kind of thing.

As others said, fixed sized records are easier to manage deletion/replacement with, too.

It's absolutely true that we don't think about it much. When I was first taught balanced binary trees, deletion wasn't even a topic that needed to be learned. Same thing later when I was taught balanced binary trees. Then again in hash tables. It's an operation that's overlooked in CS education.

> We don’t actually have any computer science for DELETE optimized databases.

There is actually a fair amount if you consider databases with fixed length records. Which used to be the dominant form.

I think garbage collection memory management can be thought of a delete optimized database.

If someone dumped that project in my lap and said fix it (and it I was more used to low level programming), I’d probably start be refreshing myself on the last 10+ years of GC advances since I stopped reading SIGPLAN. Particularly multithreaded sweep. Because essentially you want to decouple delete from free so you can not do 100% of the bookkeeping work in the middle of time sensitive operations. But not fall as far behind as Postgres can with its vacuuming albatross.

In a way, deletion is a form of eventual consistency. The user loses access to the data but the system still knows about it for a while.

Just off the top of my head, I would think for LSM systems, you would resort to snapshotting as the edit history became much larger than the retained row count, and as you delete old snapshots (two GC roots) you could compare the old and the new and drop everything that didn’t survive. You only have to finish well before the next snapshot interval, and if you maintain a queue you only have to process them on average as fast as the snapshot interval.

And for BTree systems you can amortize the deletes across every insert, the way some realtime systems clean up a few free pointers on every allocation.

Yep, it’s tough. One of the more unexpectedly complicated aspects of GDPR compliance is the strain that full deletes put on a system.

You have to break it into small batches across the cascade of associated data.

[dead]