Feature Proposal: Delete Event Support for ElasticGraph

[myronmarston]

Summary

This proposal outlines adding support for delete events to ElasticGraph, enabling applications to properly handle document deletions while maintaining ElasticGraph's core guarantee of safe out-of-order event processing. The feature will use a tombstoning approach with opt-in configuration to ensure backward compatibility and optimal performance.

Context

Current State

ElasticGraph currently supports only upsert events in its event stream specification:

{
  "op": "upsert",
  "id": "1",
  "type": "Widget",
  "version": 1,
  "record": { ... }
}

This schema was designed to also support delete events, but they are not currently supported:

{
  "op": "delete",
  "id": "1",
  "type": "Widget",
  "version": 2
}

The Challenge

Supporting delete events while maintaining ElasticGraph's core guarantee of safe out-of-order event processing presents significant challenges:

1. Version Ordering: ElasticGraph uses Elasticsearch's external versioning to handle duplicate and out-of-order events safely. When a document is deleted from Elasticsearch, the version information is lost, potentially allowing older upsert events to "resurrect" deleted documents.

2. Performance Impact: Any solution must not significantly degrade query performance for the majority of use cases that don't require delete support.

3. Data Integrity: The solution must handle edge cases like rollover indices and custom routing correctly.

The Version Ordering Problem Explained

To understand why delete events are challenging, consider how ElasticGraph currently handles out-of-order events with upserts:

Normal Order (Works Correctly)

Event 1: { "op": "upsert", "id": "widget-1", "version": 1, "record": { "name": "A" } }
Event 2: { "op": "upsert", "id": "widget-1", "version": 2, "record": { "name": "B" } }

ElasticGraph processes Event 1 first, storing Widget 1 with name "A". When Event 2 arrives, Elasticsearch's external versioning recognizes that version 2 is newer than version 1, so it updates the document to have name "B". ✅

Out-of-Order (Still Works Correctly)

Event 2: { "op": "upsert", "id": "widget-1", "version": 2, "record": { "name": "B" } }
Event 1: { "op": "upsert", "id": "widget-1", "version": 1, "record": { "name": "A" } }

ElasticGraph processes Event 2 first, storing Widget 1 with name "B". When Event 1 arrives later, Elasticsearch recognizes that version 1 is older than the current version 2, so it ignores the event. The document correctly remains with name "B". ✅

The Delete Problem - Normal Order

Event 1: { "op": "upsert", "id": "widget-1", "version": 1, "record": { "name": "A" } }
Event 2: { "op": "delete", "id": "widget-1", "version": 2 }
Event 3: { "op": "upsert", "id": "widget-1", "version": 3, "record": { "name": "C" } }

This should work as: create widget → delete widget → recreate widget. The final state should be a widget with name "C". ✅

The Delete Problem - Out-of-Order (Broken with a naive solution)

Event 2: { "op": "delete", "id": "widget-1", "version": 2 }
Event 1: { "op": "upsert", "id": "widget-1", "version": 1, "record": { "name": "A" } }

Naive approach:

1. ElasticGraph processes the delete event first, removing the document from Elasticsearch entirely
2. When the upsert event arrives, Elasticsearch has no record that widget-1 was ever deleted at version 2
3. The upsert event gets processed, creating a document with name "A"
4. Result: The widget incorrectly exists when it should be deleted ❌

Proposed Solution

Tombstoning Approach

We propose implementing delete support using a "tombstoning" approach:

1. When a delete event is processed, instead of removing the document from Elasticsearch, we:

   • Clear all document fields except id and version
   • Set a new __deleted: true field to mark the document as deleted
   • Preserve the version information to maintain proper event ordering

2. All queries automatically filter out deleted documents by adding __deleted: false to the query filter when needed

Query Performance Analysis

To determine the optimal approach for filtering deleted documents, we conducted extensive performance testing comparing different query patterns and field types. The analysis examined two key variables:

Query Patterns Tested

1. must queries: Explicitly include only non-deleted documents

   {
     "query": {
       "bool": {
         "must": {
           "term": {
             "__deleted": false
           }
         }
       }
     }
   }

2. must_not queries: Exclude deleted documents

   {
     "query": {
       "bool": {
         "must_not": {
           "term": {
             "__deleted": true
           }
         }
       }
     }
   }

Field Types and Query Operators

• Boolean field with term queries: Direct boolean value matching
• Existence-based queries with exists operator: Checking for field presence/absence

Performance Results

We did a benchmark which revealed significant performance differences based on the query pattern and result set size:

Filter Pattern	Query Type	Result Set Size	Average (ms)	P99 (ms)
must_not	term	few	7,229	11,454
must	term	few	26	101
must_not	term	many	37	85
must	term	many	37	75
must_not	exists	few	7,620	13,596
must	exists	few	27	85
must_not	exists	many	37	116
must	exists	many	26	54

Key Findings

1. Dramatic Performance Difference with Small Result Sets: When queries return few results, must_not queries perform approximately 250x worse than must queries (7,229ms vs 26ms average).

2. Similar Performance with Large Result Sets: When queries return many results, both approaches perform similarly (~37ms average).

3. Field Type Impact: Boolean vs existence-based queries showed minimal performance differences within the same query pattern.
   early all documents in the index (common case), this intersection becomes expensive.

Decision: Use must Queries

Based on these results, we will use must queries with __deleted: false to ensure optimal performance across all scenarios, particularly for queries that return small result sets.

Opt-in Configuration

Delete support will be opt-in at the index level to ensure backward compatibility:

t.index "widgets", number_of_shards: 10 do |index|
  index.support_deletes! # New configuration option
  index.rollover :yearly, "created_at"
  index.route_with "workspace_id"
end

Smart Query Filtering

To minimize performance impact, we'll use intelligent query filtering:

• When filtering is needed: If a query doesn't require the presence of any specific fields, we add the __deleted: false filter
• When filtering is unnecessary: If a query already requires specific fields that would exclude deleted documents (which have all fields cleared), we skip the additional filter

This approach ensures optimal performance while maintaining correctness.

Required Fields for Delete Events

For indices using rollover or custom routing, delete events must include the necessary routing information:

Rollover indices - must include the rollover key:

{
  "op": "delete",
  "id": "1",
  "type": "Widget",
  "version": 2,
  "record": {
    "createdAt": "2023-03-30T00:30:00Z"
  }
}

Custom routing - must include the routing key:

{
  "op": "delete",
  "id": "1",
  "type": "Widget",
  "version": 2,
  "record": {
    "workspaceId": "ABCD1234"
  }
}

Validation and Error Handling

• JSON schema validation will enforce required fields for delete events
• A new <ObjectTypeName>Deletion type will be generated for validation
• Clear error messages will guide users when required fields are missing
• Attempting to enable delete support on existing indices will be prevented with helpful error messages

Implementation Details

Schema Changes

For indices with delete support enabled:

1. Elasticsearch Mapping: Include a __deleted boolean field in the index mapping
2. GraphQL Schema: Generate deletion validation types (e.g., WidgetDeletion)
3. Event Processing: Add __deleted: false to all non-delete events during indexing

Query Modification

The query engine will be enhanced to:

1. Analyze incoming queries to determine if the __deleted: false filter is needed
2. Automatically inject the filter when required
3. Optimize queries that already exclude deleted documents naturally

Performance Considerations

Based on our benchmarking analysis:

• Optimal Query Pattern: Using must queries with __deleted: false provides the best performance across all scenarios
• Minimal Impact on Large Result Sets: For queries returning many results, the performance impact is negligible
• Smart Filtering: Only applying the filter when necessary further reduces performance impact

Migration Path

For New Indices

Simply add index.support_deletes! to the schema definition before indexing any documents.

Safety Measures

• Delete support cannot be enabled on indices that already contain documents
• The admin tooling will validate schema changes and prevent unsafe migrations
• Clear documentation will guide users through the migration process

Why Delete Support Must Be Enabled Before Indexing Data

The requirement that support_deletes! be enabled only on empty indices is critical for data consistency. Here's why:

The Problem: Our tombstoning approach relies on every document having a __deleted: false field to distinguish between:

• Documents that exist and are not deleted
• Documents that have been tombstoned (deleted) with __deleted: true

What Happens with Existing Data: If we enabled delete support on an index that already contains documents:

1. Existing documents would lack the __deleted field entirely
2. New documents (after enabling delete support) would have __deleted: false
3. Queries would filter for __deleted: false, which would exclude all existing documents!

Example Scenario:

# Before enabling delete support
Document A: { "id": "1", "name": "Widget A" }
Document B: { "id": "2", "name": "Widget B" }

# After enabling delete support
Document C: { "id": "3", "name": "Widget C", "__deleted": false }

# Query: Find all non-deleted widgets
# Filter: __deleted: false
# Result: Only Document C returned (Documents A & B are missing!)

The Solution: By requiring delete support to be enabled before any data is indexed:

• All documents consistently have the __deleted: false field from the start
• Queries work correctly across all documents
• No existing data is accidentally hidden or lost

Enforcement: The admin tooling will compare the current Elasticsearch mapping against the desired schema. If the mapping lacks the __deleted field but the schema configuration includes support_deletes!, it will throw a clear error explaining that delete support cannot be added to indices with existing data.

Migration Path for Existing Indices: If users need delete support on existing indices, they would need to:

1. Create a new index with support_deletes! enabled
2. Reindex all existing data (which would automatically add __deleted: false)
3. Switch over to the new index
4. This ensures data consistency but requires a deliberate migration process

Benefits

1. Maintains Core Guarantees: Preserves ElasticGraph's safety guarantees around out-of-order event processing
2. Backward Compatible: Existing applications continue to work unchanged
3. Performance Optimized: Minimal impact on query performance through intelligent filtering and optimal query patterns
4. Flexible: Supports complex index configurations (rollover, custom routing)
5. Developer Friendly: Clear validation and error messages guide proper usage

Alternatives Considered

Elasticsearch's index.gc_deletes Setting

We investigated using Elasticsearch's built-in deleted document version retention, but this approach:

• Doesn't survive node restarts (confirmed by Elastic team)
• Has unclear performance implications for long retention periods
• Lacks guarantees about backup/restore behavior

External Version Tracking

Maintaining deleted document versions in a separate datastore was considered but rejected due to:

• Complexity of maintaining consistency across systems
• Challenges with backup/restore scenarios
• Risk of state divergence between systems

No Delete Support

Forcing applications to handle deletions themselves was considered but rejected because:

• Delete support is a common framework-level concern
• It pushes complexity to every application
• ElasticGraph can provide optimal query patterns directly in the framework. Individual applications are unlikely to implement the same optimization.

[jwils]

I'm a fan of this approach and generally the design looks good to me. Few small questions.

Does the size of the field key have any noticeable impact on the document sizes? Since every document needs this new field is there any noticeable size difference between something like _del and _deleted. I'd imagine compression / storage optimization may make the difference here neglectable, but something to consider.

I'm also curious if you know why must_not performs so poorly with a small number of deleted documents? It's not clear to me what features would make that query difficult.

[myronmarston]

Does the size of the field key have any noticeable impact on the document sizes? Since every document needs this new field is there any noticeable size difference between something like _del and _deleted. I'd imagine compression / storage optimization may make the difference here neglectable, but something to consider.

Good question. I asked Chat GPT about this and here's what it said:

✅ Bottom line:

• If _source is disabled, field name length makes no difference.
• If _source is enabled, the theoretical raw savings per doc = difference in field name length × number of fields × number of docs, but compression makes that almost negligible.
• Even at tens of billions of docs, you’re unlikely to see more than single-digit GB savings unless your documents are extremely small.

👉 If your real concern is storage bloat at 10B+ docs, you’ll get orders of magnitude better savings from:

• Disabling _source (if you don’t need to retrieve full docs).
• Using source filtering (_source excludes).
• Using index templates with doc_values: false or index: false
  where appropriate.
• Adjusting compression settings (best_compression).

So we have the option to make __deleted vs __del make no difference whatsoever by excluding it from _source. Or we can leave it in and compression makes it negligible (particularly when it's alongside tons of other fields which are stored in _source and are not abbreviated).

I hadn't consciously thought about disabling the field from _source but I think that probably makes sense here--we don't need to ever retrieve __deleted from _source. That said, excluding it from _source means that when an ElasticGraph user queries the cluster directly (e.g. in kibana) for troubleshooting, the __deleted value will not show up in _source. I think that's likely to cause confusion: when an engineer direct queries the index they are unlikely to remember to filter out __deleted documents, and if they get back a _source that doesn't indicate which documents are deleted it could be very confusing and lead to wasted time and effort. In fact, I suspect that the wasted time and effort from that confusion would likely outpace any cost savings from excluding __deleted from _source--so my leaning is now to leave it in _source after all.

Another data point here: in a very early internal release of ElasticGraph, we required a numeric value to be assigned to every enum value in the schema so that we could just store the numeric value rather than the string value for enums (similar to how they work with Protobufs). However, we later learned about global ordinals and realized it wasn't likely to make a difference--and it caused some problems (it made sorting on an enum field wonky!). So we ripped it out.

With that experience in mind, I think I've landed on keeping the field named __deleted and keeping it in _source (but let me know if you disagree!).

I'm also curious if you know why must_not performs so poorly with a small number of deleted documents? It's not clear to me what features would make that query difficult.

In general, we've observed that must_not is less performant than must which makes a certain amount of sense when you think about the inverted index used by Elasticsearch/OpenSearch internally. It keeps a mapping from a term to the document ids containing that term which allows for very fast lookups on a "must": {"term": {"someField": "someValue"}} query--it's just a direct lookup in the map! In contrast, for a "must_not": {"term": {"someField": "someValue"}}, there is no mapping of someValue to the ids of documents that don't have that value. I'm sure there are clever techniques it can use but it shouldn't be surprising that it's slower.

[nicolewoch]

Great write-up!

Two questions:

1. On clearing all fields other than id and version - some examples come to mind about other fields users might want to retain. For instance, if using a field as the routing key or rollover key. Wouldn't clearing these result in potential duplicate documents since these keys are supposed to be immutable (and may be enforced as "not null" in the json schema)? Maybe we could make an exception for not clearing said fields, or at least make it configurable in the index as to which fields don't get cleared, in case the schema includes other non-nullable fields.

2. I think the intent is to never expose the __deleted field in GraphQL/Apollo, right? If not, I think the name could result in some lint errors since the Apollo convention is to always use camelcase.

[myronmarston]

For instance, if using a field as the routing key or rollover key. Wouldn't clearing these result in potential duplicate documents since these keys are supposed to be immutable (and may be enforced as "not null" in the json schema)?

The routing and rollover fields must be immutable on the published events (that is, the publishing system cannot publish event Widget:123@v1 with routing key A and later publish event Widget:123@v2 with routing key B -- as you pointed out, this would lead to duplicate documents). On the payload we store in Elasticsearch/OpenSearch, we don't need to retain them. The rollover key is used to determine which index we write to and the routing key is passed as a ?routing=abc query parameter, and so long as these are included in every event, we are able to target the right document and avoid duplicates. The values of these fields need not be on the document payload itself for it to work properly.

So while we could retain these fields on the indexed document payloads, we don't have to for things to work correctly, so long as we still require them on the delete events themselves (which we will, as per the "Required Fields for Delete Events" section in the proposal above).

As much as possible, I'd like the fact that we do tombstoning to be an implementation detail that is completely hidden to publishers and clients (although it will be visible to clients who query OpenSearch/Elasticsearch directly, of course).

some examples come to mind about other fields users might want to retain

Are there other fields you can think of beyond the routing/rollover fields to consider keeping?

at least make it configurable in the index as to which fields don't get cleared

Given my goal of making delete events appear to completely delete the document (while only retaining a tombstone as an implementation detail so we can maintain safe out-of-order processing), I think it would be odd to allow users to configure specific fields to retain for a delete event. If a user wants to implement a sort of "partial delete" (where some fields are cleared, and others are retained), they are free to implement that themselves as a normal update event, with no framework support required. In fact, users are still free to implement their own version of soft deletes if what we're providing doesn't meet their needs. (And of course, I'm very happy to extend what we provide in future versions based on user feedback as well.)

I think the intent is to never expose the __deleted field in GraphQL/Apollo, right? If not, I think the name could result in some lint errors since the Apollo convention is to always use camelcase.

Correct. As I mentioned above, I'd like our delete support to appear to clients to actually delete documents even though hidden tombstones will be retained. With that in mind, I don't think exposing a __deleted field in the GraphQL schema makes sense. It's also worth noting that we can't even expose a field named __deleted in the GraphQL schema; the GraphQL spec forbids fields prefixed with double-underscores. But that's actually one of the reasons I've chosen that field name--it's guaranteed to not conflict with a user-defined field, since users can't name a GraphQL field with that name!

[nicolewoch]

Thanks for the detailed answers!

The routing and rollover fields must be immutable on the published events (that is, the publishing system cannot publish event Widget:123@v1 with routing key A and later publish event Widget:123@v2 with routing key B -- as you pointed out, this would lead to duplicate documents). On the payload we store in Elasticsearch/OpenSearch, we don't need to retain them. The rollover key is used to determine which index we write to and the routing key is passed as a ?routing=abc query parameter, and so long as these are included in every event, we are able to target the right document and avoid duplicates. The values of these fields need not be on the document payload itself for it to work properly.

So while we could retain these fields on the indexed document payloads, we don't have to for things to work correctly, so long as we still require them on the delete events themselves (which we will, as per the "Required Fields for Delete Events" section in the proposal above).

As much as possible, I'd like the fact that we do tombstoning to be an implementation detail that is completely hidden to publishers and clients (although it will be visible to clients who query OpenSearch/Elasticsearch directly, of course).

Ah I see. So if the schema had fields tagged with json_schema(nullable: false), the publisher could still set these fields and the EG delete impl would still clear them before indexing the document, right?

Are there other fields you can think of beyond the routing/rollover fields to consider keeping?

In our schema we use a pair of fields as an alternate compound Apollo key, so these fields are required to be set by the publisher even when tombstoning a document. However, I think this would fall under the case described above since they're still nullable on the document itself.

I know this is not recommended, but what about if a schema has defined other non-nullable fields besides id? Not just in json_schema but on the document itself. Would they not be able to use the delete feature?

Correct. As I mentioned above, I'd like our delete support to appear to clients to actually delete documents even though hidden tombstones will be retained. With that in mind, I don't think exposing a __deleted field in the GraphQL schema makes sense. It's also worth noting that we can't even expose a field named __deleted in the GraphQL schema; the GraphQL spec forbids fields prefixed with double-underscores. But that's actually one of the reasons I've chosen that field name--it's guaranteed to not conflict with a user-defined field, since users can't name a GraphQL field with that name!

Makes sense!

[myronmarston]

Ah I see. So if the schema had fields tagged with json_schema(nullable: false), the publisher could still set these fields and the EG delete impl would still clear them before indexing the document, right?

nullable: false only determines the nullability of fields within upsert events. According to the publicly visible semantics of a delete event, the document is being deleted, so it doesn't make sense to require non-null values for any fields but the ones required to ingest the delete event: id, version, and the routing key (if routing_with has been configured) and the rollover field (if rollover has been configured).

In our schema we use a pair of fields as an alternate compound Apollo key, so these fields are required to be set by the publisher even when tombstoning a document.

I might be missing something...but I don't see why a pair of fields used in an Apollo entity key will need to be set when tombstoning a document. When a delete event is ingested, for all intents and purposes, the document has been deleted. It will not be returnable from GraphQL (due to an implicit filter on __deleted, rather than the document actually being gone from the index...). From a GraphQL point of view, a document which has been deleted will behave the same as one which has never existed at all. Apollo is purely a GraphQL concern, and documents which aren't available to return from GraphQL (either due to never existing, or from being "deleted" as a tombstone) are equally invisible to Apollo.

I know this is not recommended, but what about if a schema has defined other non-nullable fields besides id? Not just in json_schema but on the document itself. Would they not be able to use the delete feature?

ElasticGraph has no concept of non-nullability on the document itself. Even if we wanted to offer such a feature, I don't think it's possible to implement unless we say that new fields can never be added to an existing index. Consider, for example, what happens when a new field is added to an existing index which already has documents. The field will be null on all previously indexed documents. (Actually, it'll be omitted from the payloads of such documents entirely, but our GraphQL API will return null for it).

Calling f.json_schema nullable: false only impacts the JSOM Schema. It prevents a publisher publishing events at that JSON schema version from passing null as the value for the field. It has no impact on the nullability of the field in the index.

Someone who uses f.json_schema nullable: false on some fields should be able to use the delete feature just fine.

Another way to think about this: a delete event is the equivalent of SQL like:

DELETE
FROM index_for(event.timestamp_field_value)
WHERE id = event.id
  AND version < event.version
  AND routing_key = event.routing_field_value

To support that we need to require the id, version and the rollover/routing values...and nothing else, regardless of the non-nullability of any fields in the JSON schema for upsert events.

[nicolewoch]

nullable: false only determines the nullability of fields within upsert events. According to the publicly visible semantics of a delete event, the document is being deleted, so it doesn't make sense to require non-null values for any fields but the ones required to ingest the delete event: id, version, and the routing key (if routing_with has been configured) and the rollover field (if rollover has been configured).

I might be missing something...but I don't see why a pair of fields used in an Apollo entity key will need to be set when tombstoning a document. When a delete event is ingested, for all intents and purposes, the document has been deleted. It will not be returnable from GraphQL (due to an implicit filter on __deleted, rather than the document actually being gone from the index...). From a GraphQL point of view, a document which has been deleted will behave the same as one which has never existed at all. Apollo is purely a GraphQL concern, and documents which aren't available to return from GraphQL (either due to never existing, or from being "deleted" as a tombstone) are equally invisible to Apollo.
``nullable: falseonly determines the nullability of fields withinupsert` events`

I think this was the piece I was missing to bring it together. I misunderstood JSON schema validation will enforce required fields for delete events and didn't realize that custom json nullability requirements in the schema could selectively only be applied to upsert events. It seems all good then!

Yeah, my comment above is not very relevant in hindsight - it's referencing our EG instance's bespoke implementation of tombstoning which relies on a custom deleted flag similar to what's described here. However, it's not really comparable because it still relies on upsert events rather than a new delete event type, and our deleted flag is also exposed in GraphQL (although it probably shouldn't be in hindsight), which is why the alternate key fields are retained. But I think these concerns aren't relevant with delete being a new event type which doesn't have to adhere to the same rules as upsert.

I know this is not recommended, but what about if a schema has defined other non-nullable fields besides id? Not just in json_schema but on the document itself. Would they not be able to use the delete feature?

ElasticGraph has no concept of non-nullability on the document itself. Even if we wanted to offer such a feature, I don't think it's possible to implement unless we say that new fields can never be added to an existing index. Consider, for example, what happens when a new field is added to an existing index which already has documents. The field will be null on all previously indexed documents. (Actually, it'll be omitted from the payloads of such documents entirely, but our GraphQL API will return null for it).

Calling f.json_schema nullable: false only impacts the JSOM Schema. It prevents a publisher publishing events at that JSON schema version from passing null as the value for the field. It has no impact on the nullability of the field in the index.

Someone who uses f.json_schema nullable: false on some fields should be able to use the delete feature just fine.

Another way to think about this: a delete event is the equivalent of SQL like:

DELETE
FROM index_for(event.timestamp_field_value)
WHERE id = event.id
  AND version < event.version
  AND routing_key = event.routing_field_value

To support that we need to require the id, version and the rollover/routing values...and nothing else, regardless of the non-nullability of any fields in the JSON schema for upsert events.

My bad, I got this mixed up with GraphQL type modifiers that can be added in the EG schema (e.g. ID!). And since the docs won't show up in GraphQL after being deleted, it shouldn't matter if there are ! fields. 👍