Optimization: Performing DETACH-DELETE on a large-scale graph will consume a very long time

[Mrhs121]

Description

I created a graph locally with 10 million vertices and 50 million edges. When I was executing MATCH (n:User) where n.id <9999999 DETACH DELETE n, I waited for at least an hour but it still didn't finish. There are 9,999,999 vertices that meet the condition n.id <9999999, and the number of edges associated with them is 9,999,999 *5.

[Mrhs121]

As shown in the following figure, every time I increase the data volume by 10 times, the deletion time also increases by 10 times accordingly. Therefore, it can be calculated that when I need to delete 10 million nodes, it will take an extremely long time.

[adsharma]

Most of the time is in the detach delete op:

lbug> profile MATCH (n:User) where n.id <9999999 DETACH DELETE n;
┌────────────────────────────────┐
│┌──────────────────────────────┐│
││        Physical Plan         ││
│└──────────────────────────────┘│
└────────────────────────────────┘
┌────────────────────────────────┐
│           PROFILE[7]           │
│   --------------------------   │
│   --------------------------   │
│       NumOutputTuples: 0       │
│   --------------------------   │
│    ExecutionTime: 0.000000     │
└───────────────┬────────────────┘
┌───────────────┴────────────────┐
│      RESULT_COLLECTOR[6]       │
│   --------------------------   │
│         Expressions:           │
│   --------------------------   │
│       NumOutputTuples: 0       │
│   --------------------------   │
│   ExecutionTime: 108.263000    │
└───────────────┬────────────────┘
┌───────────────┴────────────────┐
│           DELETE[5]            │
│   --------------------------   │
│   Type: Detach Delete Nodes    │
│             From: n            │
│   --------------------------   │
│       NumOutputTuples: 0       │
│   --------------------------   │
│   ExecutionTime: 3291.835000   │
└───────────────┬────────────────┘
┌───────────────┴────────────────┐
│           FLATTEN[4]           │
│   --------------------------   │
│   --------------------------   │
│    NumOutputTuples: 100000     │
│   --------------------------   │
│    ExecutionTime: 1.467000     │
└───────────────┬────────────────┘
┌───────────────┴────────────────┐
│     TABLE_FUNCTION_CALL[3]     │
│   --------------------------   │
│     Function: READ_FTABLE      │
│       Expressions: n._ID       │
│              n.id              │
│   --------------------------   │
│      NumOutputTuples: 49       │
│   --------------------------   │
│    ExecutionTime: 0.759000     │
└───────────────┬────────────────┘
┌───────────────┴────────────────┐
│      RESULT_COLLECTOR[2]       │
│   --------------------------   │
│       Expressions: n._ID       │
│              n.id              │
│   --------------------------   │
│    NumOutputTuples: 100000     │
│   --------------------------   │
│    ExecutionTime: 2.197000     │
└───────────────┬────────────────┘
┌───────────────┴────────────────┐
│           FILTER[1]            │
│   --------------------------   │
│        LESS_THAN(n.id)         │
│   --------------------------   │
│    NumOutputTuples: 100000     │
│   --------------------------   │
│    ExecutionTime: 0.151000     │
└───────────────┬────────────────┘
┌───────────────┴────────────────┐
│       SCAN_NODE_TABLE[0]       │
│   --------------------------   │
│          Tables: User          │
│            Alias: n            │
│        Properties: n.id        │
│   --------------------------   │
│    NumOutputTuples: 100000     │
│   --------------------------   │
│    ExecutionTime: 0.878000     │
└────────────────────────────────┘

Also see explain <query>.

[adsharma]

Potential bulk delete optimization strategy for delete_executor.cpp

1. Current Implementation Analysis:
   • detachDeleteForCSSRels (lines 352-390) is the core function doing the actual work
   • It scans through relationships one batch at a time
   • For each batch, it iterates through relationships and deletes them one-by-one
   • Each iteration involves:
     • Setting up selection vectors
     • Reading relOffset
     • Deleting from both tableData and reverseTableData
2. Key Bottlenecks:
   • Sequential per-relationship processing: The inner loop (line 370) processes relationships one at a time with scalar operations
   • State management overhead: Constantly setting/getting selection vectors for each rel (line 371)
   • Two separate delete calls: One for forward and one for reverse table data
   • No batching for local table deletes: Each local table delete is called separately
3. Optimization opportunities:
   • Batch processing: Process multiple relationships in a batch instead of one-by-one
   • Vectorized operations: Use bulk delete operations on tableData instead of per-rel
   • Reduce state changes: Minimize the number of selection vector modifications
   • Parallel processing: Consider parallelizing work across multiple batches (if transaction allows)
   • Prefetching: Prefetch next batch data while processing current batch
   • Bulk local table operations: Group local table deletes together

[adsharma]

@Mrhs121 could you test the PR above? It was 6x faster for me for 100k deletes. The batch size is hard coded right now. Please let me know if a different batch size works better for you.

To compile: check out the PR and run make shell

[Mrhs121]

Thank you very much. I tested it locally and found that this pr effectively accelerated the performance of delete. By the way, we are currently considering embedding bugdb as a graph database in the new system. If there is an opportunity, we will also actively participate in opensource contributions.

[adsharma]

@Mrhs121 that'll be great. If you want to pursue the PR further, this could help:

--- a/src/processor/processor_task.cpp
+++ b/src/processor/processor_task.cpp
@@ -29,6 +29,10 @@ void ProcessorTask::run() {
     auto resultSet =
         sink->getResultSet(storage::MemoryManager::Get(*executionContext->clientContext));
     taskRoot->ptrCast<Sink>()->execute(resultSet.get(), executionContext);
+    // It's not super clear why this conditional is needed. Without it, issue.2589 fails
+    if (taskRoot->getOperatorType() == PhysicalOperatorType::RESULT_COLLECTOR) {
+        taskRoot->finalize(executionContext);
+    }
 }

The finalize() call is necessary to flush the last batch which could be smaller than BATCH_SIZE. However, adding the call breaks other tests as noted in the comment.

Perhaps its possible to use some other mechanism to handle the last batch that doesn't break tests.

A second optimization I was thinking was morsel driven parallelism. Multiple threads execute the delete in parallel. But it's complex because of potential dependencies. We'll need a dependency analysis pass that proves that it's parallelizable and then do it.