11

I have a table in a SQL Server database with a clustered index on the primary key. The table has 1 million rows. If I delete 10K rows from table, do index get restructured during deletion operation is performed ?

The deletion operation is part of stored procedure. At a time, more than one client can be executing the stored procedure, however each individual run will delete it's own set of rows (uniquely identified by primary key). I'm getting blocking on Key lock (of type U) when multiple clients executes the procedure. The blocker lock belongs to a row from the same table and it is not part of any of the concurrently running transaction. There should not be any blocking as each run is trying to delete it's own set of rows. Lock escalation is not happening as it is turned off.

I suspect, deletion operation must be causing index to re-balance and hence during restructuring process it can take key lock on any row of the table.

I would really appreciate any opinion on this.

7
  • Nice question and nice guess. Yes, when you delete record , index is rebuild. During rebuild process table is lock and other user won't be able to access that table.stackoverflow.com/questions/6309614/…
    – KumarHarsh
    Apr 19, 2018 at 6:23
  • 4
    NO, delete of rows on clustered index does not causes index rebuild. Can you also post the query used to delete the data. The U lock comes when query is trying to find data which will be deleted and finally exclusively locks the rows to delete it.
    – Shanky
    Apr 19, 2018 at 6:38
  • 3
    When delete happens it creates a "hole" or you can say space as the data was removed from clustered index. This may create low page density and can be considered as a fragmentation. When insert happens on CI it will fill records on right side and due to this the space may never be filled. But SQL Server is not automatically going to remove this space. You have to rebuild index or reorganize to fill this space. There is NO rebalancing as such
    – Shanky
    Apr 19, 2018 at 8:11
  • 1
    @jayesh I don't see how the order of nodes in a tree has to do with rebalancing. A B-tree can be unbalanced (either because of inserts or deletes). The node order doesn't change in these cases. It's just an unbalanced tree. Apr 19, 2018 at 10:16
  • 1
    @jayesh I think you may benefit from reading some of the MSSQL docs, as I think the terminology you're using is confusing both you and some of us. Apr 19, 2018 at 14:35

1 Answer 1

5

To answer the question in the title, whether the B-tree rebalanced during a delete, the answer appears to be no, at least in the following minimal test case.

The following demo runs commands that are best left for a test environment.

--create table and fill it
DROP TABLE IF EXISTS bunchesofints
CREATE TABLE bunchesofints (
thisisanint INT PRIMARY KEY CLUSTERED,
junkrow CHAR(1000) NOT NULL
)

INSERT dbo.bunchesofints
SELECT TOP 5000
ROW_NUMBER() OVER(ORDER BY(SELECT NULL)) AS thisisanint,
REPLICATE('a',1000) AS junkrow
FROM sys.all_objects a1
CROSS JOIN sys.all_objects a2


--with this query we can see all the non-leaf pages of the b-tree, plus the IAM
SELECT allocated_page_page_id, page_type_desc, page_level, is_allocated, next_page_page_id, previous_page_page_id
FROM sys.dm_db_database_page_allocations(DB_ID(),OBJECT_ID('dbo.bunchesofints'),NULL,NULL,'DETAILED')
WHERE page_type != 1
GO

--Ok, let's delete most of the rows
;WITH CTE AS (
    SELECT TOP (4500) *
    FROM dbo.bunchesofints
    ORDER BY thisisanint DESC
)

DELETE 
FROM CTE
GO

--Hmm, still have 3 non-leaf index pages
SELECT allocated_page_page_id, page_type_desc, page_level, is_allocated, next_page_page_id, previous_page_page_id
FROM sys.dm_db_database_page_allocations(DB_ID(),OBJECT_ID('dbo.bunchesofints'),NULL,NULL,'DETAILED')
WHERE page_type != 1



--So, where are the rows?
--please note the assumption that your test database has a single file.
DECLARE @firstindexpage INT, @lastindexpage INT, @db INT = DB_ID()
SELECT @firstindexpage = MIN(previous_page_page_id), @lastindexpage = MAX(next_page_page_id)
FROM sys.dm_db_database_page_allocations(DB_ID(),OBJECT_ID('dbo.bunchesofints'),NULL,NULL,'DETAILED')
WHERE page_type = 2 AND page_level = 1

DBCC PAGE(@db,1,@firstindexpage,3) WITH TABLERESULTS
DBCC PAGE(@db,1,@lastindexpage,3) WITH TABLERESULTS

This demo shows that a delete can produce a very unbalanced b-tree, with practically all data on one side.

1
  • thanks for the clear and concise explanation and demo code. I'll try this out. I'll accept this answer. I'm still trying to figure out why delete on disjoint set of rows causes blocking on table with clustered index.
    – jayesh
    Apr 20, 2018 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.