9 ms·
DELETEs Are Difficult
- yen223 2y agoA big asterisk that should be added to the article is that all that applies to Postgres. Other databases have their own deletion mechanisms (and deletion quirks) It's a very good article otherwise.
- jandrewrogers 2y agoDELETE 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.
- redox99 2y agoI think garbage collection memory management can be thought of a delete optimized database.
- tybit 2y agoRuntimes with garbage collectors typically optimize for allocation, not deletion.
- mike_hearn 2y agoGenerational GC optimizes for both. They assume that most objects die young, so choose to relocate live objects and just mark the entire region that was evacuated as empty. So this is a very efficient way to delete data.
- SgtBastard 2y agoOnly if you profoundly misunderstand what GC is.
- actionfromafar 2y agoI have long day-dreamed of what a “use it (soon) or loose it” runtime would mean. Allocated blocks would just expire after a set time.
- okasaki 2y agoSo kind of like browsers work now with the tab unloading and Android killing apps? Personally I find it really obnoxious and disruptive.
- sitkack 2y agoYou would prefer something a little more persistent?
- dotancohen 2y agoI would prefer a 48 hour day, so that I could get everything done that needs to be done. Or maybe a 72 hour day, so I'd have time for things that I'd just enjoy.
- okasaki 2y agoI prefer to do my own app lifecycle management.
- mpweiher 2y agoYes...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_progress 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 https://dl.acm.org/doi/10.1145/985692.985779
- akira2501 2y ago> 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.
- throwaway984393 2y ago[dead]
- brightball 2y agoYep, 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.
- epistasis 2y agoThere 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.
- mike_hearn 2y agoWhat 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.
- selecsosi 2y ago+1 This was our strategy at TempoIQ for our ts storage engine (built on top of rocks). 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
- latency-guy2 2y agoWell 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.
- mike_hearn 2y agoThe 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.
- kccqzy 2y agoIt'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.
- toast0 2y ago> 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.
- hinkley 2y agoIf 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.
- Svip 2y ago> Unlike DELETEs, UPDATEs don’t trigger cascaded actions - they only involve triggers that are explicitly defined. 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.
- arcanemachiner 2y ago> Though, personally, I would never use ON UPDATE CASCADE, as it seems kind of funky. As a relative noob in the world of database administration, I'm glad to hear that someone else feels this way.
- pepelotas 2y agoIt does if your key is an auto increment or random unique identifier. But if you had a key that is also data, say a "Genre" colum, it starts to make sense that you'd want to cascade updates
- rrr_oh_man 2y ago> Though, personally, I would never use ON UPDATE CASCADE, as it seems kind of funky. Why?
- Svip 2y agoPersonally, I like to be explicit and in control. In the application layer, I may be far away (at least mentally speaking) from the constraints in the database, and if I update/delete something, I don't want it to "magically" cascade through the database. For those reasons, I always prefer RESTRICT, both for ON DELETE and ON UPDATE. This forces me to clean up before I make the actual change I'm interested in, and anyone reading the code later, can uncover that behaviour quickly. 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.)
- burntcaramel 2y agoIf 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.”
- konha 2y agoYes. GDPR allows for delays when complying with deletion requests. You should ideally document it and factor the delay into any deadlines you might be bound to. 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.
- lucianbr 2y agoIf vacuum runs at least once per day, seems pretty GDPR compliant to me. Even if it runs once every two or three days. 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.
- dataflow 2y agoEven 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.
- Polizeiposaune 2y ago> Because filesystems don't guarantee they will overwrite or wipe any particular disk blocks. 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.
- physicsguy 2y agoThey are difficult but it shouldn’t be underestimated the cost of trying to keep consistency with the alternatives either. 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.
- xg15 2y ago> For example, deleting 1 million rows in a single transaction is a textbook case of what not to do. Instead, splitting the operation into smaller batches, such as deleting 10,000 rows across 100 iterations, is far more effective. 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)
- sureglymop 2y agoAnd a follow up question: would the current best way to handle this be to "mark records as deletable" and then do the batched deletion operations when convenient?
- rawgabbit 2y agoCreate a column called MarkedForDeletion. Create a job that starts in the off hours to detect how many locks are present on the table, if low then delete X records. Else wait for Y minutes. Put this in a loop. If error detected, breakout of the loop.
- Nican 2y agoTransactional consistency / ACID guarantees. 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.
- tremon 2y ago> none of the data should be available 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.
- cannibalXxx 2y agothis content reminds me of this post where we can get an idea of how to build complex and efficient queries. https://chat-to.dev/post?id=724 https://chat-to.dev/post?id=724
- redman25 2y agoOne solution for performance degradation with soft deletes is to partition the table by some field like `created` monthly. Queries will need to include `created` in the query is the main downside.
- kccqzy 2y agoI've only heard of this trick being employed on OLAP scenarios. Is this kind of partitioning also advisable for OLTP workloads?
- joelshep 2y agoDepends on the workload. In the past, I've worked on several workflow-based systems that performed lots of OLTP operations to drive live workflows forward, but once a workflow was done the operational data became a lot less interesting. So there it made sense to (say) partition the operational data and table by month, and roll off partitions after 3-6 months.
- pmarreck 2y agoMy only recommendation would be, no matter which strategy you go with, cover it with tests to make sure the right information stays and the right information gets physically (or marked) deleted, and that data marked for deletion is invisible to the UI except via admin access. But, indeed, proper deletion is surprisingly difficult, especially when you consider cascades on a complex table containing many defined foreign-key relationships.
- tonymet 2y agoWhy do DBs perform Delete operations online? Wouldn’t it be better to soft-delete (at the table-space level ) and then run scheduled task to clean up the table spaces? 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.
- junto 2y agoReminds 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.com/sqlcat/archive/2009/05/21/fast-ordered-delete.aspx 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-some-rows-from-a-really-big-table/ https://www.brentozar.com/archive/2018/04/how-to-delete-just...
- aurareturn 2y agoDELETE FROM films; I'm surprised databases makes it so easy to just delete an entire table. I think the command should be DELETE FROM films YES-I-KNOW-WHAT-I-AM-DOING;
- jsemrau 2y agoMySQL has this as default as far as I recall. But then I never delete, I just set "deleted" to yes.
- physicsguy 2y agoThat just wouldn’t fly where you have business customers, many insist on data deletion at the end of contracts. In practice though partitioning or using seperate databases can be a better strategy for dealing with that as otherwise dealing with backups are challenging.
- kijin 2y agoIt might depend on the version, but last time I checked, DELETEing an entire table was much slower than TRUNCATE TABLE.
- eddd-ddde 2y agoI'm pretty sure that only applies to Postgres.
- magicalhippo 2y agoSybase SQLAnywhere as well, and not unlikely MSSQL too given its shared ancestry. 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.
- evanelias 2y agoYou're probably thinking of the --safe-updates option [1] for the `mysql` CLI, also available as the memorable alias --i-am-a-dummy. This requires UPDATE and DELETE to have either a WHERE clause or a LIMIT clause. Under the hood, the command-line client option just manipulates the sql_safe_updates session variable [2] to enforce the UPDATE and DELETE requirement, as well as a couple other unrelated variables to prevent overly-huge SELECTs. 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-updates 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-variables.html#sysvar_sql_safe_updates https://dev.mysql.com/doc/refman/8.4/en/server-system-variab...
- orionblastar 2y agoMost databases I used have a Status column we could mark as active, inactive, or deleted. That way, you can see what records were marked as deleted and change them back in case of accidental deletion. 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.
- alexanderscott 2y agothis is a “soft delete”. as the author notes, depending on the nature of the data being stored a soft delete does not meet the requirements of many data privacy laws and compliance regulations (like GDPR’s right to erasure).
- isbvhodnvemrwvn 2y agoAnd in postgres soft delete is more expensive than a regular delete because it's effectively an insert and update, while delete is just an update.
- kijin 2y agoThere are different kinds of soft delete. 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.
- arielcostas 2y agoI do something similar, but instead keep a "date_deleted" column null by default, and the "active" column as a boolean. 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.
- Terr_ 2y agoFor 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.
- buildingcrash7 2y ago>software was first made the stakeholders/product-org 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.
- tempodox 2y agoThat depends on the context. In some cases you're not allowed to physically delete because you need to provide an audit trail for 10 years or so. You could move those rows into separate audit tables instead. However, that requirement should not come as a surprise.
- BlueTemplar 2y agoBut, 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».