Sql-server – Slow delete with varbinary(max) column

I have two tables that temporarily hold uploaded data from a web application before it gets processed. This is running on an Azure SQL Database.

UploadFile

Id uniqueidentifier
CustomerId uniqueidentifier
FileName nvarchar(MAX) NULL
UploadDate datetime
UploadedBy nvarchar(MAX) NULL

UploadFileChunk

Id uniqueidentifier
Data varbinary(MAX) NULL
UploadFileId uniqueidentifier
[Index] int

UploadFile has a foreign key with cascade delete to UploadFileChunk. UploadFileChunk has a non-clustered index on UploadFileId. I have been uploading chunks of 1MB each.

Inserting and reading this data is working really well, but deleting a record from UploadFile after its data has been processed is really slow. On an S0 10 DTU testing Azure environment, it took 38 minutes to delete 12 records with ~500 child chunks collectively (just an example – it also performs poorly on our higher powered production environment and a fast local machine.)

How do I make it fast?

There is an index on UploadFileChunk.FileUploadId. Here's the execution plan.

I ran the following query (from Finding Blocking Queries in SQL Azure) several times while the slow delete was mid-execution and it didn't return any results:

SELECT TOP 10
    r.session_id,
    r.plan_handle,
    r.sql_handle,
    r.request_id,
    r.start_time,
    r.status,
    r.command,
    r.database_id,
    r.user_id,
    r.wait_type,
    r.wait_time,
    r.last_wait_type,
    r.wait_resource,
    r.total_elapsed_time,
    r.cpu_time,
    r.transaction_isolation_level,
    r.row_count,
    st.text
FROM sys.dm_exec_requests r
CROSS APPLY sys.dm_exec_sql_text(r.sql_handle) AS st
WHERE
    r.blocking_session_id = 0
    AND r.session_id IN 
    (
        SELECT DISTINCT (blocking_session_id) FROM sys.dm_exec_requests)
GROUP BY
    r.session_id,
    r.plan_handle,
    r.sql_handle,
    r.request_id,
    r.start_time,
    r.status,
    r.command,
    r.database_id,
    r.user_id,
    r.wait_type,
    r.wait_time,
    r.last_wait_type,
    r.wait_resource,
    r.total_elapsed_time,
    r.cpu_time,
    r.transaction_isolation_level,
    r.row_count,
    st.text
ORDER BY
    r.total_elapsed_time DESC;

Truncating might be faster [than deleting] but these two tables contain data for multiple files and I must be able to delete one at a time. The nvarchar(max) columns could probably be something else, this is just what Entity Framework generated based on our domain classes. Do you think that would help with this problem?

I confirmed that deleting records directly from FileUploadChunks is just as slow. On my extra slow example (S0 10 DTU) it's around 1 second per row deleted.