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

101–110 of 121 posts

Re: DELETEs Are Difficult

#101

Post by MetaWhirledPeas »

mpweiher wrote: post #27
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…

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…

> The app isn't the point, the starting fresh is.

This is the crux of what made Google Inbox so good. The UX encouraged "deleting" and starting fresh. This was made possible not just through the controls, but also through the promise that undelete would be possible. People want to start fresh, but they also don't want to lose anything; that's the conundrum.

Re: DELETEs Are Difficult

#102

Post by teitoklien »

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.

you can already do it, with Apple’s native Shortcuts app and Reminders app. You can set an automation to delete all reminders after a fixed time has passed with the ‘Remove Reminders’ action

Otherwise you can just use cronjobs with a small python snippet to parse and decide what reminders tagged with which labels to delete after X,Y,Z many days and hit the APIs of most major todo apps like todoist, asana, etc to just delete those tasks. Heck works with your local markdown based todo lists too.

Re: DELETEs Are Difficult

#104

Post by junto »

Reminds me of this old post about deleting large amounts of data efficiently at MySpace. Page has now gone but was archived.

https://web.archive.org/web/20090525233504/http://blogs.msdn...

Brent Ozar talked about this back in 2008 in reference to working with large tables in MSSQL Server:

https://www.brentozar.com/archive/2018/04/how-to-delete-just...

Re: DELETEs Are Difficult

#105

Post by __turbobrew__ »

dataflow wrote: post #50
burntcaramel wrote: post #18

If data isn’t actually removed until vacuuming, then are systems that perform SQL DELETES actually GDPR compliant? Because technically the private data is still there on disk and could be recovered. “Until the autovacuum process or a manual VACUUM operation reclaims the space, the “deleted” data remains.”

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.

With our current understanding of physics you cannot destroy information outside of maybe throwing something in a black hole — and even then you may still be able to get the information back from hawking radiation after many eons — so the question is how much should we scramble information before it is considered “deleted”?

Re: DELETEs Are Difficult

#106

Post by latency-guy2 »

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…

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 entry for new INSERT/UPDATE operations, but these suck when you want to do batched INSERT/UPDATE on a range since they're scattered all about in a table, and you lose ordering + monotonic properties.

Re: DELETEs Are Difficult

#107

Post by toast0 »

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…

> 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.

Re: DELETEs Are Difficult

#108

Post by BlueTemplar »

Terr_ wrote: post #6

For many of the most painful deletion questions, the root problem is that when the software was first made the stakeholders/product-org didn't think about use-cases for deleting things. At best, they assume a "do not show" property can be placed onto things, which falls apart when you get to legal issues that compel actual removal.

But, just like this article using «physically deleted», when in practice it's not the case (the bits are just freed to be overwritten some unknown amounts of time later), does legal compliance just completely ignores this fact of actual physical deletion ??*

(AFAIK it takes several passes of overwriting bits with random bits on magneto-mechanical storage to not be able to retrieve any significant fragments of the original data, and things are even worse on transistor storage, which casually makes copies of the data for wear leveling reasons.)

*With the exception of state secrets of course, where we know that storage is mechanically destroyed «with extreme prejudice».

Re: DELETEs Are Difficult

#109

Post by hinkley »

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…

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.

Re: DELETEs Are Difficult

#110

Post by wenc »

lukevp wrote: post #72
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…

Every day I’d have more and more state accumulation on my machine - open apps, unsaved changes, open tabs. I’ve tried many methods for preventing this from happening over the years, but the only and most effective solution I’ve been using for the last year - a script I wrote that just quits every browser tab and every open app (leaving unsaved apps still running) every evening. I wake up and the machine is new and fr…

> Every day I’d have more and more state accumulation on my machine - open apps, unsaved changes, open tabs.

I resonate with your comment.

I grew up during a time when PC state was ephemeral (DOS days). Unsaved changes essentially meant lost data. Open apps were gone once the computer was shut down (and the computer was shut down daily - a 250W power supply had an expensive power draw; in contrast a Mac Mini only sips 1W when sleeping). This helped me develop a habit of keeping only necessary things open, bookmarking what I want to keep, and of habitually pressing Ctrl+S to save data. I never keep any tabs open (my browser loses all tabs upon close anyway), and my inbox is zero.

The cost I pay for this is context recovery -- every day, I have to essentially set everything up again. I do write notes or leave comments in code to remind myself where I left off, but I essentially started fresh. But there is an upside to this: I start each day from an uncluttered slate, which leads to clarity in my head. When context is ephemeral, I'm more likely to not be beholden to an existing state.

This actually helps me increase the quality of my writing and my code. It's akin to the heuristic of "throwing away your first draft and rewriting" to achieve higher quality. Write your code once, delete it, and write it again from scratch. The next version takes a quarter of the time to write but can be twice the quality because you've prototyped it in your head but you are not bound to your crufty first attempt. There was an HN discussion on this a while ago:

https://grantslatton.com/software-pathfinding

If you save state, you can resume more quickly, which is great if you're on a roll, but it's also an accumulation of more clutter that blocks certain more creative thoughts.

Post reply on HN