Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

DELETEs Are Difficult

notso.boringsql.com

Post reply on HN
Print view View original

111–120 of 121 posts

Re: DELETEs Are Difficult

#111

Post by mpweiher »

loa_in_ wrote: post #62
mpweiher wrote: post #27

Earlier quoted context omitted.

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 increase…

Just add a __delete all__ button.

Yeah, that should work.

Alas, it doesn't.

Re: DELETEs Are Difficult

#112

Post by mycall »

marcosdumay wrote: post #80
magicalhippo wrote: post #76

Earlier quoted context omitted.

Learned that lesson a bit too late for that. But yea, these days I never use natural keys.

I really hate that the educational literature says it's an option. Yet everybody knows it's something you should never do, no exceptions.

Maintaining old databases is one reason to use natural keys. There are a lot of them in the wild.

Re: DELETEs Are Difficult

#113

Post by dataflow »

__turbobrew__ wrote: post #105
dataflow wrote: post #50

Earlier quoted context omitted.

Even vacuuming wouldn't actually destroy the data right? Because filesystems don't guarantee they will overwrite or wipe any particular disk blocks. And even if they did, SSDs still wouldn't promise that the blocks aren't remapped instead of being wiped & reused.

Yea the only way to be sure that data is gone is through mechanical destruction (shredding) of the drives. Sometimes you can write something to a SSD and then not be able to delete it due to a hardware fault, but the data can still be read. I wonder if a GDPR nation has made a ruling on the extent of data erasure? Surely you cannot expect a company to shred a SSD every time someone asks for their data to be deleted.…

> I wonder if a GDPR nation has made a ruling on the extent of data erasure?

My understanding (based on a couple random conversations, take it with a grain of salt) is that at least some entities are taking the sheer difficulty of true compliance with the letter of the law to imply that softer deletion methods have to be reasonably acceptable, and their stance is basically "if you disagree, well, take us to court and we'll figure it out."

Re: DELETEs Are Difficult

#114

Post by jandrewrogers »

mike_hearn wrote: post #84
jandrewrogers wrote: post #13

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…

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 ag…

Encryption that allows precise deletion of records in databases is quite famously pathological for performance and cost. Databases that work this way have existed for many decades and almost no one uses them because the performance is unacceptably terrible.

The reason may not be obvious. At the limit, database data structures and algorithms are a collection of data compression algorithms, though we typically don’t think of databases this way. Using encryption in front of that compression renders it worthless, and most database performance is predicated on the ability to use compressive representations of the data. Encrypting the data forces the most naive and inefficient data structures imaginable.

Re: DELETEs Are Difficult

#115

Post by immibis »

mattashii wrote: post #77
immibis wrote: post #71

Earlier quoted context omitted.

So why does it need to be copied into the WAL log until vacuum runs? And vacuum is not expected or required to be atomic, since it deletes data that was necessarily unreferenced anyway, so it also shouldn't need to copy the old data into WAL files.

Many DBMSs with index-oriented storage (MySQL, Oracle, MSSQL) use undo logging for a transaction's MVCC, so that for deletion the old version is put into the undo log of that transaction and referred to as an old version of the record (or page, or ...), immediately cleaning up space on the page for new data while the transaction is still goin on. This is great for short transactions and record updates, as a page only…

The space isn't immediately cleaned up because of Postgres's version-based MVCC. It should only need to record that it marked the row as deleted, and the vacuum shouldn't need to record anything because it isn't atomic.

Re: DELETEs Are Difficult

#116

Post by mike_hearn »

jandrewrogers wrote: post #114
mike_hearn wrote: post #84

Earlier quoted context omitted.

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 ag…

Encryption that allows precise deletion of records in databases is quite famously pathological for performance and cost. Databases that work this way have existed for many decades and almost no one uses them because the performance is unacceptably terrible. The reason may not be obvious. At the limit, database data structures and algorithms are a collection of data compression algorithms, though we typically don’t th…

Yes, encrypted databases aren't that useful for fine grained data especially if you get into academic computable encryption schemes.

For document DBs where you're storing files like big JSON structures, PDFs, or for archival data, etc it can work out. Though mostly it's not worth it because key management is too hard.

Re: DELETEs Are Difficult

#117

Post by mike_hearn »

latency-guy2 wrote: post #106
mike_hearn wrote: post #84

Earlier quoted context omitted.

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 ag…

Well tombstoning is fundamentally punting the operation, the data is still there taking up space and computation if the flagged entry does not get removed from varying levels of query plans. I agree that it meets the requirements for batched DELETE, and that's likely as best as we can make it. But I wonder if there was a better way. I know there are research DBs out there that experimented with reusing the tombstone…

The way tombstones work in a sorted KV store like RocksDB is that queries walk up the levels, and the moment a tomb stone is hit the walk stops because it's known the keys are deleted. Then when the levels are compacted the live data is evacuated into a new tablet, so it's like generational GC. The cost scales with live data, not how much data there is in total. The problem of course is you pay that cost over and over again.

Re: DELETEs Are Difficult

#118

Post by mattashii »

immibis wrote: post #115
mattashii wrote: post #77

Earlier quoted context omitted.

Many DBMSs with index-oriented storage (MySQL, Oracle, MSSQL) use undo logging for a transaction's MVCC, so that for deletion the old version is put into the undo log of that transaction and referred to as an old version of the record (or page, or ...), immediately cleaning up space on the page for new data while the transaction is still goin on. This is great for short transactions and record updates, as a page only…

The space isn't immediately cleaned up because of Postgres's version-based MVCC. It should only need to record that it marked the row as deleted, and the vacuum shouldn't need to record anything because it isn't atomic.

Yes, but that's in PostgreSQL, not in MSSQL or the other systems I described (and which the gps seemed to refer to)

Re: DELETEs Are Difficult

#119

Post by marcosdumay »

mycall wrote: post #112
marcosdumay wrote: post #80

Earlier quoted context omitted.

I really hate that the educational literature says it's an option. Yet everybody knows it's something you should never do, no exceptions.

Maintaining old databases is one reason to use natural keys. There are a lot of them in the wild.

It's not a valid reason for adding more of them. It's only a reason to be stuck inheriting some.

Re: DELETEs Are Difficult

#120

Post by perryizgr8 »

hnbear wrote: post #93
mpweiher wrote: post #27

Earlier quoted context omitted.

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 increase…

I like the idea of a todo list that comes with a built in auto-delete. You either do your to dos, or it auto-deletes them for you. No worry about it getting full, but also some pressure to actually get them done or they'll be wiped. And if you're happy they're wiped, then you probably didn't need to do it at all. I wonder if there's something like that already.

This was a pretty nice feature for me in the now defunct arc browser. It simply deletes tabs that you don't interact with for 12 hours. If its important I'll open it again!
Post reply on HN