DELETEs Are Difficult
notso.boringsql.com
notso.boringsql.com
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.
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
I have an endless reminders app and todo list. I wonder if something similar (items expire automatically unless you flag them as permanent or something) would help keep a clearer list. Sometimes ephemerality is best!
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.
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.
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.
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.
Alas, it doesn't.
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.
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.
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.
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.
Very efficient and effective at managing tons of data ingestion (and deletion) at scale.
Not an easy out of the box tech to build on top of though when you have to build all the analytics/management pieces that something like PG gets you so I get the lack of public examples
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.
There is actually a fair amount if you consider databases with fixed length records. Which used to be the dominant form.
Personally I find it really obnoxious and disruptive.
Or maybe a 72 hour day, so I'd have time for things that I'd just enjoy.
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.
You have to break it into small batches across the cascade of associated data.
Why do I as a user have to do that? Why can't the database implement batching internally and automatically transform my 1-million-rows query into an appropriate list of batched queries?
(Edit: Thanks a lot for the answers, that makes more sense - in particular the point that this would also lock one million rows at once)
Before you execute the query, you should be able to query any of the data, and after you execute the query, none of the data should be available. The mechanisms to make a transactional database is tricky.
Some databases, like CockroachDB, provides some built-in TTL capabilities.
But also- if you are having to delete huge ranges of data and do not care about consistency, you are probably looking at an analytical workload, and there would be better databases suited for that, like Clickhouse.
As written, that's not required. The data should not be retrieveable by query, but ACID only specifies what happens at the client-server boundary, not what happens at the server-storage boundary (Durability prescribes that the server must persist the data, but not how to persist it). A database that implements DELETEs by only tombstoning the row and doesn't discard the data until the next re-index or vacuum operation would still be ACID-compliant.
By manually batching the deletes, you are telling the database that the whole operation does not need to be atomic and other operations can see partial updates of it as they run. The database wouldn't be able to do that for every large delete without breaking its guarantees.
DELETE FROM t WHERE … BATCH 100
If DELETE is so special, make special ways to manage it. Don’t offload what is your competence onto a clueless user, it’s recipe for disaster. Replace DELETE with anything and it’s still true.
ALTER DATABASE d SET UNBATCHED DELETE LIMIT 500000
If you've gone to the effort of batching things, you are still writing out those records, you are just giving the db a chance to delete them from the log.
I'd like to save my ssds that heartache and instead allow the database to just delete.
In MSSQL in some extreme circumstances, we've partitioned our tables specifically so we can use the 'TRUNCATE TABLE' command as delete is just too expensive.
That operation can wipe gbs in seconds.
One simple way in Oracle is to take a table lock, copy the data you want to preserve out to a temporary table, truncate the target table, copy the data back in.
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.
That said, I agree it would be nice to have a DELETE BATCH option to make it even easier.
[1]: https://learn.microsoft.com/en-us/sql/t-sql/statements/delet...
In that case I'd fire off a job and tell the user, yeah sure the delete is successful. But check the logs to be sure.
No message (other than an INFO log message) when the operation completes successfully, but failures are handled and notified properly.
DELETE FROM films;
DELETE FROM films YES-I-KNOW-WHAT-I-AM-DOING;If you really want to just delete everything, just do WHERE 1=1.
(You could always set autocommit=false, which forces you to explicitly commit or rollback every action, but that has its own baggage)
At which point we could just say all SQL should have a WHERE clause.
It's not enabled by default out of the box, but some companies do override their configuration to enable it for new sessions, iirc Facebook did this.
[1] https://dev.mysql.com/doc/refman/8.4/en/mysql-tips.html#safe...
[2] https://dev.mysql.com/doc/refman/8.4/en/server-system-variab...
Delete with WHERE is sufficiently slow in MSSQL we have to do batched deletes, but I can't recall offhand if that holds for whole table deletion as well.
That's not entirely true. ON UPDATE CASCADE is a thing for foreign keys, at least in PostgreSQL (which this article is talking about), meaning that the foreign row referencing the row gets updated. Though, personally, I would never use ON UPDATE CASCADE, as it seems kind of funky.
For this to work with soft-deletes, wouldn't you have to include the soft-delete column in a compound foreign key? That sounds funky indeed.
In one case, we had a table of invoices and a table of goods items, and each goods item should point to an invoice.
If one wants to use the natural key, invoice number, and have a foreign key to ensure the goods items can't point to an invoice that doesn't exist, then ON UPDATE CASCADE was needed in case the user had to change the invoice number (due to mistyping it or similar).
Of course, if one does not use a natural key then this isn't such an issue.
Another case was where we've had to merge databases after two companies merged. If they had overlapping primary key ranges, then the easiest was to switch to ON UPDATE CASCADE and then renumber the existing rows before inserting the other rows.
We'd change back after the merge though.
Yeah, that's why you shouldn't use natural keys as primary ones.
But yea, these days I never use natural keys.
As a relative noob in the world of database administration, I'm glad to hear that someone else feels this way.
Why?
That being said, I can see the arguments for ON DELETE CASCADE, particularly in a codebase, where there is a lot of functionality in the database itself (in the formed of stored procedures, and what have you), since you are always mentally closer to the action. But ON UPDATE CASCADE feels weird, because why are you updating the primary key (which is usually what foreign keys references) of your rows? That feels like something that needs a good explanation.
Though, I do recognise, you need to jump through a lot of hoops to modify your primary key values with ON UPDATE RESTRICT, because you basically need to cover all your bases in a large convoluted common table expression (depending on the number of foreign keys, of course), when an ON UPDATE CASCADE would do that for you. But I'd also rather be blocked from updating primary row values entirely, since it feels like the wrong thing to do. (Yes, I know that foreign keys doesn't have to reference other primary keys, and there may be niche cases for this, but personally, I'd just avoid it altogether.)
This is the big reason I don't like triggers either. I would use them in only one case: if the database didn't support an auto-incrementing "identity" type, I might use a trigger to simulate that. But just as often I would prefer a stored procedure that got the new ID from a sequence, and then did the insert, especially if there were other things I needed a stored procedure to deal with.
The first case I was thinking about was a merger of two accounts. Second case would be a db-wide update of one or more keys for some reason. That’s why I tend to leave it ON UPDATE CASCADE.
Although both of these cases are more diffuse muscle memory than rational foresight.
(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».
Practically all building, physical and software is made for a purpose first, the process is mainly an obstacle that needs to be minimized. A piece of software is trying to solve a problem just like a door is. It's driven by economics where the recipients don't want to pay any more than they need to and someone is always willing to undercut you by cutting corners.
Other databases have their own deletion mechanisms (and deletion quirks)
It's a very good article otherwise.
I sometimes think that people ask the wrong question on this sort of thing - rather than thinking “what technical solution should I come up with” you should be thinking “what is the business requirement here, and what consistency guarantees are needed?”
In many cases you want to soft delete anyway and mark rows as stale rather than deleting them wholesale. Cascade deletes need to be very carefully thought about, as while they’re very handy they can be quite destructive if the relationships are not mapped out.
Personally having spent some time now in the microservices hole, I miss all the power SQL databases give you for this sort of thing. I think everyone should spend some time reading and digesting ‘Designing Data Intensive Applications’ and evaluating the trade offs in detail.
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...
But, indeed, proper deletion is surprisingly difficult, especially when you consider cascades on a complex table containing many defined foreign-key relationships.
Similar to git. When you “delete” files they are just removed from the tree. It isn’t until later that all refs and reflog references have expired , and gc is run, that the objects are actually removed.
Keep record retention with the Date_Modified column so you can use SQL delete to remove those deleted records that are older than a year or so.
That way, I kill two birds in one stone by having a dedicated column for last deletion (instead of updating a record that is supposedly deleted) and the status just as a boolean instead of some enum, or integer or string.
I've had cases where the rows in question absolutely could not be hard deleted, because of legacy foreign key relations. But the PII in those rows had to go. So we did a kind of "firm delete" by setting all columns (except the PK and a few necessary flags) to their default values and/or null.
Some filesystems have a richer interface to the underlying storage device, allowing them to invoke commands such as ATA TRIM or SCSI UNMAP - either incrementally as blocks are freed, or on demand - which request that the underlying storage device forget the block contents.
So the necessary interfaces exist and are widely available, and even if imperfect they improve the situation.
No, that's not a guarantee of data erasure. Not just because it's just a request that the device can disregard, but also because filesystems play tricks (like storing small bits of data inline, or logging data in various places, etc.) and they don't clear all those blocks just because you wanted to clear a couple bytes.
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”?
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."
GDPR supervisory authorities disagree on what to do about data in backups. France has said you don't have to delete data from backups. The Danish authorities have said that you have to delete from backups where it is technically possible. The UK (which still has GDPR) has said that you must put the data "beyond use" which most have taken to mean that you have to make sure that if you ever restore data from the backup you will omit the data that is supposed to be forgotten.
I don't know what other supervisor authorities have said--those three are just the ones that tend to show up when searching on this topic. I would not be surprised if there are at least a dozen other different opinions from the rest.
You’d need to make sure the process is somewhat predictable, like running the vacuum on a set schedule so you know for sure what maximum amount of time a deletion request will take.
Now if your database runs vacuum once every 6 months, yeah, DELETE might not actually be a delete. But is it really a GDPR issue? What's really going on in this system?
I don't think any EU agency is going to fine your company if the data you say you deleted survived 6 or even 60 hours after deletion, if that is the end of it.