{{ message }}
Repository navigation
Support Delete Range operation #577
Description
Re-partitioning a state store in a stream processor requires deleting a range of keys.
Consider a DB with key range from [1 - 1000]. Splitting this into two might result in two DBs, one with [1-500], and another with [501-1000].
This can be achieved with following steps
- Clone the DB to DB-1 and DB-2
- Delete ranges [501-1000] from DB-1 and ranges [1-500] from DB-2.
- DB-1 and DB-2 are the new partitions.
Step 2 can be a metadata only operation if we supported delete range that updates the manifest with deleted ranges.
A compaction can then do the actual deletion of keys.
Activity
criccomini commentedon May 12, 2025
I think @dmvk's split/merge work takes a different approach that doesn't require range deletions. IIRC, the idea was to clone DB to DB-1 with only SSTs containing range 0-500. Then clone DB to DB-2 with only SSTs containing range 501-1000. I think there was some logic to handle out-of-range keys that fall at the edge SSTs (the first and last).
[-]Support Delete Range operation.[/-][+]Support Delete Range operation[/+]criccomini commentedon Jul 24, 2025
Range deletion came up in the Discord today. I'm pasting some links and conversations here so we don't lose track:
Iceberg's deletion vector approach looks very appealing.
Discord discussion
https://github.com/cockroachdb/pebble/blob/master/docs/rocksdb.md#range-deletions I personally think Pebble's implementation is easier to understand and performs better. dmvk — 1/21/25, 6:23 AM Pebble still maintains a separate block with range_tombstones and only difference is on the read path right? Documents there don't seem to go too much into detailsI'm pretty comfortable with golang so I can also dig into the codebase
It feels like they take the same approach with separate metadata block 🤔
AsukaMilet — 1/21/25, 6:31 AM
If I remember correctly, Pebble should also maintain separate blocks, and I think their implementation based on mergeIter is easier to maintain and understand.
dmvk — 1/21/25, 6:37 AM
yeah, that's also my understanding of what the difference is
Rohan — 1/21/25, 9:34 AM
DeleteRange in rocks is pretty complicated. For this use case (which we have too) I was thinking we could just do a combination of:
make the existing support for compaction filters into a public api, and support some way to filter at the sst level (e.g. filter given the key range in an sst)
support manual compactions so you can just force the filter to run
That should be good enough since you don't actually care about the data being deleted semantically
support some way to filter at the sst level
this could also just be a one-time meta operation when initializing the clone that filtes out ssts when writing the first manifest
Rohan — 1/21/25, 9:44 AM
probably that plus filters is all you need, and you can skip the manual compaction. The bulk of the data will be removed when initializing the clone, and the rest can just be cleaned up as compaction chugs along.
criccomini — 1/21/25, 11:32 AM
I, too, would prefer to ignore range deletion for now. It seems like a lot of complexity for minimal gain. If we have compaction filtering, range scan, and transactions, I feel we can get pretty far.
this could also just be a one-time meta operation when initializing the clone that filters out ssts when writing the first manifest
Were you thinking that this would use the same interface as the compaction filter?
dmvk — 1/21/25, 11:59 AM
As long as we can make it as lightweight as metadata operation, I'm all in. I want to go the least painful to get to PoC for Flink.
Read Filters + Compaction Filters should in general do the trick, but might be complex to do right. I'm wondering whether we should rather build in first class support for database partitioning (split + merge operations during clone for example)
criccomini — 1/21/25, 12:18 PM
What would first class support look like to you? Supplying ranges when calling clone?
dmvk — 1/21/25, 12:53 PM
yeah, something along those lines, the cloned manifest would need to contain valid ranges
parent {
path: ...
valid_ranges [
a-b,
f-m
]
}
Rohan — 1/21/25, 4:05 PM
Were you thinking that this would use the same interface as the compaction filter?
I think it would need to be more specific than the compaction filter api since it should be able to filter based on the sorted-run metadata (e.g. the sst key ranges). What @dmvk suggested above seems reasonable
criccomini — 1/21/25, 4:12 PM
K.. this would need an RFC I think
flaneur233 — 1/21/25, 6:52 PM
i once went into an incident in production when our team used rocksdb's range deletion. if i remember correctly, our program triggered lots of range deletions, and it accumulated lots of range deletion markers (> 1million?), it exhausted ALL the CPU, as it requires to merge the range deletion markers for any read operation 😯...
we finally falled back to a vanilla delete within a for loop afterwards.
flaneur233 — 1/21/25, 7:01 PM
might off topic, i suppose deletion vector might also worth considering in the future, like: https://docs.google.com/document/d/1FtPI0TUzMrPAFfWX_CA9NL6m6O1uNSxlpDsR-7xpPL0/edit?tab=t.0#heading=h.f42to8zz3i0 it's pretty lightweight like a bloomfilter, and is widely adopted in iceberg, paimon with nice performance gain.
criccomini — 1/21/25, 7:29 PM
Dang this is neat!
This seems really reasonable… I think we can have a .deletions along side the .sst file and CAS it when we need to update…
Doing a deletion across SSTs atomically will be the interesting part…
This doc doesn’t seem to discuss that…
flaneur233 — 1/21/25, 7:39 PM
iceberg is also an OCC model with immutable data files, when update rows in multiple data files, it might generate several new data files in a CoW manner, and build a new metadata file with all the data files referenced (also a CoW) and fire a CAS operation to switch the root of metadata file (with a Snapshot Isolation guarantee). (it resembles a lot with Append-Only Btree imo 😯 )
before all the write operations, it read the latest version in the current metadata file. and when it COMMIT with CAS, it compares the latest version with the version when it started the txn, if there's conflict, it aborts the txn (at some cases it can has an retry automatically, like we were appending data files, and the data are not conflict with existed data file, it can safely retry this commit).
criccomini — 1/21/25, 7:52 PM
Ah was hoping to avoid the manifest.. but yea that makes sense…
Sounds expensive to consult manifest on writes.
flaneur233 — 1/21/25, 7:54 PM
this style may generate lots of snapshot/manifest data on frequent updates, at some workload, the manifest data may even become larger than the data files 😂
criccomini — 1/21/25, 7:54 PM
🤔
Yea..
dmvk — 1/22/25, 12:32 AM
Having separate deletion files might be super useful for compactions, it might enable us to get rid of data in higher levels faster.
Anyway, I really want to avoid doing full DeleteRange support now (still want to do it down the road though). I'll try to draft a proposal for sharding primitives and we can continue discussion there 👍
Vignesh — 4/5/25, 12:57 PM
I was thinking about this too, searched github issues and didn't find anything about this.
Discord search led me to this.
@dmvk mind opening a github issue with key insights from this thread? Several good ideas being discussed (deleted range in manifest, compaction filters, deletion vectors).
criccomini commentedon Jul 24, 2025
This definitely needs an RFC.
criccomini commentedon Aug 18, 2025
Assigning to @sujeetsawala
sujeetsawala commentedon Aug 18, 2025
Can you assign it to me?
criccomini commentedon Oct 6, 2025
Another good resource: https://www.shayon.dev/post/2025/277/an-mvcc-like-columnar-table-on-s3-with-constant-time-deletes/
criccomini commentedon Dec 16, 2025
After some more digging, I kind of feel like deletion vectors are for a different use case from range deletes. My reading from the Databricks docs is that they're a way to do point-based deletions in a parquet file without having to rewrite the whole thing. We don't really need this since we have tombstones and an LSM--we can just tombstone the key we want to delete and stuff it into the most recent L0.
I think it probably makes more sense to do something akin to what RocksDB did for their range deletions rather than trying to use deletion vectors for range deletes.
criccomini commentedon Feb 17, 2026
There is a good discussion on alternatives to range deletions on Discord. There are a few options:
LsmTreeSegmentsand drop unneeded segments.Barre commentedon Jun 29, 2026
While evaluating compaction filters for this use-case, it doesn't seem that they'd work for me.
A SlateDB compaction filter sees exactly one RowEntry at a time, plus a job-wide CompactionJobContext captured when the filter is created. It cannot consult other keys or other ranges from inside the callback.
In my use-case, to determine which keys I need to "range-delete", I must known that a (my project internal) tombstone exists for "a parent object id", and the key/value I want to remove carries zero liveness info. A per-key filter has nothing to decide on.