sqlity.net

Selecting the entire Database as XML String – 2

Sebastian — Wed, 01 Feb 2012 17:11:49 +0000

About two weeks ago I wrote about how to get the content of the entire database into an XML document. Today Daniel commented, that he would like the XML to be in a compacter format. In this post I am going to explain how to get there.

While WordPress™ conveniently ate the example XML Daniel tried to post, I will assume for this article that he was going for this format:

Instead of all column values being sub-nodes of their nodes they are now attributes of an empty node. Also the node between

and is now missing, as it was kind of superfluous. And while I was changing the code anyway, I went ahead and added the previously missing root node as .

So how did I get there?

First let us look at the missing root node, which turns out to be the simplest of all the changes. When you select rows for a table specifying the FOR XML PATH('NodeName') directive, every row is going to be represented as a node with the passed in name. Those nodes are just hanging together without an enclosing root node. To make the output a valid XML document you can just specify the ROOT clause next to the PATH clause like this:

  SELECT * 
    FROM dbo.Table
  FOR XML PATH('rowNodeName'),ROOT('rootNodeName'),TYPE

The TYPE directive tells SQL Server to return the XML as a value with the XML type. If you leave it out the XML gets returned as a string, which can create problems if you want to continue to work with it in T-SQL.

The next step was, to get rid of the node. When you specify an XML value in a select statement that is in turn using FOR XML PATH, that value is wrapped in a node with the value's column name. The generated SQL in my original solution looked like this:

SELECT * FROM(
SELECT '[dbo].[t1]' [@name],(SELECT * FROM dbo.t1 FOR XML PATH('row'),TYPE) data
UNION ALL
SELECT '[dbo].[t2]' [@name],(SELECT * FROM dbo.t2 FOR XML PATH('row'),TYPE) data
)X FOR XML PATH('table'),TYPE;

The data column in the UNION ALL query contains XML values, so the outer SELECT * ... FOR XML PATH('table') is going to wrap each one into a node like this:

1 1 2 1

1 2 4 2 2 4

To remove the additional node we can use the fact that SQL Sever will inline the value of a column that does not have a name. So we need to select the data column without specifying its name. To do that we will use a trick:

SELECT [@name],(SELECT data) FROM(
SELECT '[dbo].[t1]' [@name],(SELECT * FROM dbo.t1 FOR XML PATH('row'),TYPE) data
UNION ALL
SELECT '[dbo].[t2]' [@name],(SELECT * FROM dbo.t2 FOR XML PATH('row'),TYPE) data
)X FOR XML PATH('table'),TYPE;

By wrapping the data column in its own SELECT it loses its name property for the outer SELECT statement. The output it generates now looks like this:

The last thing we need to accomplish is to make the column values attributes of each node instead of sub-nodes. If you specify a column name with a leading "@" sign, FOR XML PATH will make that value an attribute with that name (without the "@"):

SELECT id AS [@id] FROM dbo.t1 FOR XML PATH('row'),TYPE;

The output of above statement looks like this:

So instead of a SELECT * FROM for each table, we need to list all columns in the format shown above. To get this specially formatted column list we are going to use XML concatenation one more time:

SELECT STUFF((SELECT ','+QUOTENAME(name)+' AS '+QUOTENAME('@'+name) 
                              FROM sys.columns c 
                             WHERE c.object_id = OBJECT_ID('dbo.t2')
                             ORDER BY column_id 
                            FOR XML PATH(''),TYPE).value('.','NVARCHAR(MAX)'),1,1,'');

This produces the desired list:

[id] AS [@id],[c1] AS [@c1],[c2] AS [@c2]

With that we have all the parts collected to create the new "compact" solution. The last step is to put it all together:

DECLARE @cmd NVARCHAR(MAX) ;
SET @cmd = 'SELECT [@name],(SELECT data) FROM('
    + STUFF(
(SELECT ' UNION ALL SELECT ''' + QUOTENAME(OBJECT_SCHEMA_NAME(object_id))
        + '.' + QUOTENAME(t.name) + ''' [@name],' + '(SELECT '+c.ColList+' FROM '
        + QUOTENAME(OBJECT_SCHEMA_NAME(object_id)) + '.' + QUOTENAME(t.name)
        + ' FOR XML PATH(''row''),TYPE) data'
 FROM   sys.tables t
 CROSS APPLY (SELECT STUFF((SELECT ','+QUOTENAME(name)+' AS '+QUOTENAME('@'+name) 
                              FROM sys.columns c 
                             WHERE c.object_id = t.object_id
                             ORDER BY column_id 
                            FOR XML PATH(''),TYPE).value('.','NVARCHAR(MAX)'),1,1,'')
             )c(ColList)
    FOR     XML PATH('') ,
                TYPE).value('.', 'NVARCHAR(MAX)'), 1, 11, '')
    + ')X FOR XML PATH(''table''),ROOT(''tables''),TYPE;' ;

EXEC(@cmd) ;

This produces the desired output that was shown all the way at the beginning of this article. The size of the resulting XML document for my example database went from about 1.4 MB for the original solution to now about 0.5 MB – a significant improvement.

The Performance Impact of Forwarded Records on Table Scans

Sebastian — Tue, 31 Jan 2012 16:00:18 +0000

Forwarded records are a mechanism that SQL Server employs to reduce the amount of maintenance work for indexes on a table without a clustered index. During an update of a record in a table that does not have a clustered index, an increase in size might prevent the record to fit on its current page. If that happens, a forwarding pointer is created in the current page and the record is moved to a new location.

It is well known that such forwarded records will cause each RID-Lookup operation that encounters one to have to read a second page. If you are doing a filtered index scan followed by an RID-Lookup this can potentially double the amount of work necessary to retrieve all rows.

What is less well known is the fact, that such forwarded records can significantly impact the performance of a simple table scan as well. In this article I will show you why this happens.

Terminology

To explain the way SQL Server handles forwarded records during a table scan, I am first going to rehash some storage basics.

SQL Server knows two ways to organize the data in a table on disk. One is the Clustered Index and the other one the Heap. In a Clustered Index data is organized in a B+Tree structure allowing for fast access based on the Clustered Index Key. In a Heap on the other hand the data is not sorted or linked in any way. Any new row is inserted into the table in any free space big enough to hold the row.

In both cases the smallest unit of storage and access is a Page. Every piece of data SQL Server needs to store on disk is organized in blocks called pages. Each page is exactly 8192 Bytes in size. The only exception to this rule are the log files. Log data is stored in a structure called virtual log file and those are not part of today's discussion.

Indexes created on a Heap use a physical address to point from the index record to the underlying data record. This address consists of the file number, the number of the page that contains the record within that file and the slot number inside that page.

Forwarded Records

When a record with variable length data type columns is updated, its size might increase. If the page it is stored in is filled already, the updated record might need to be moved to a new page. If that happens, all pointers in any index on that table addressing the moved row now point to the wrong (old) place. There are two ways to handle this situation: Update all indexes with the new location or put a special record in the old place that "forwards" to the new location.

Going through all existing indexes can be extensively resource intensive. For that reason SQL Server is using the second option to put a forwarding record in the old place.

Such a forwarding record links to the new physical address of the actual data. The new record also contains a pointer back to the forwarding record. This back-pointer allows the forwarding record to get updated in case the data record has to move again or in case it gets deleted which causes the forwarding record to be deleted as well. Updating the forwarding records in cases of repeated data record moves prevents long forwarding chains. Instead there is always only at max on hop.

In the case of an RID-Lookup SQL Server has to follow those forwarding records to get to the actual data record. This causes an additional (logical) page read for each forwarding record encountered.

During a table scan on the other hand each page will be read anyway so SQL Server could just ignore all forwarding records. That however could cause reading inconsistencies. Rows that are updated after the scan started and before it finishes could be missed entirely by the scan, if the record gets moved to a page that was scanned already. For that reason SQL Server follows each forwarding record immediately. This not only causes an additional read right there, is also turns the sequential read of all pages in allocation order into a succession of random reads, hurting performance potentially even more.

Demonstration

To demonstrate this behavior let us set up two tables dbo.ForwardSmall and dbo.NoForwardSmall as well as a Procedure dbo.ChangeRow to help with the creation of forwarded records:

IF OBJECT_ID('dbo.ForwardSmall') IS NOT NULL DROP TABLE dbo.ForwardSmall;
CREATE TABLE dbo.ForwardSmall(Id INT ,F VARCHAR(8000))
GO
IF OBJECT_ID('dbo.NoForwardSmall') IS NOT NULL DROP TABLE dbo.NoForwardSmall;
CREATE TABLE dbo.NoForwardSmall(Id INT ,F VARCHAR(8000))
GO

IF OBJECT_ID('dbo.ChangeRow') IS NOT NULL DROP PROCEDURE dbo.ChangeRow;
GO
CREATE PROCEDURE dbo.ChangeRow
@Id INT,
@Size INT
AS
BEGIN
  SET NOCOUNT ON;
  MERGE dbo.ForwardSmall fs
  USING (SELECT @Id,REPLICATE('X',@Size)) x(Id,F)
  ON fs.Id = x.Id
  WHEN MATCHED THEN
    UPDATE SET fs.F = x.F
  WHEN NOT MATCHED THEN
    INSERT (Id,F)VALUES(x.Id,x.F);
END
GO

The procedure will take an Id parameter as well as a size parameter. It uses to merge command to either insert or update the record with the given Id value. The F column will be valued with a string of length @Size.

The following script will create 16 rows in the table dbo.ForwardSmall and then update those records to create forwarded records.

EXEC dbo.ChangeRow 11,900;
EXEC dbo.ChangeRow 12,900;
EXEC dbo.ChangeRow 13,900;
EXEC dbo.ChangeRow 14,900;
EXEC dbo.ChangeRow 15,900;
EXEC dbo.ChangeRow 16,900;
EXEC dbo.ChangeRow 17,900;
EXEC dbo.ChangeRow 18,900;

EXEC dbo.ChangeRow 21,900;
EXEC dbo.ChangeRow 22,900;
EXEC dbo.ChangeRow 23,900;
EXEC dbo.ChangeRow 24,900;
EXEC dbo.ChangeRow 25,900;
EXEC dbo.ChangeRow 26,900;
EXEC dbo.ChangeRow 27,900;
EXEC dbo.ChangeRow 28,900;
--------------------------
EXEC dbo.ChangeRow 27,0;
EXEC dbo.ChangeRow 28,0;
EXEC dbo.ChangeRow 18,1800;
EXEC dbo.ChangeRow 28,900;
EXEC dbo.ChangeRow 18,900;

EXEC dbo.ChangeRow 26,0;
EXEC dbo.ChangeRow 17,1800;
EXEC dbo.ChangeRow 27,900;
EXEC dbo.ChangeRow 17,900;

EXEC dbo.ChangeRow 25,0;
EXEC dbo.ChangeRow 16,1800;
EXEC dbo.ChangeRow 26,900;
EXEC dbo.ChangeRow 16,900;

EXEC dbo.ChangeRow 24,0;
EXEC dbo.ChangeRow 15,1800;
EXEC dbo.ChangeRow 25,900;
EXEC dbo.ChangeRow 15,900;


EXEC dbo.ChangeRow 23,0;
EXEC dbo.ChangeRow 14,1800;
EXEC dbo.ChangeRow 24,900;
EXEC dbo.ChangeRow 14,900;

EXEC dbo.ChangeRow 22,0;
EXEC dbo.ChangeRow 13,1800;
EXEC dbo.ChangeRow 23,900;
EXEC dbo.ChangeRow 13,900;

EXEC dbo.ChangeRow 21,0;
EXEC dbo.ChangeRow 12,1800;
EXEC dbo.ChangeRow 22,1499;
EXEC dbo.ChangeRow 12,780;

EXEC dbo.ChangeRow 11,910;

EXEC dbo.ChangeRow 22,900;
EXEC dbo.ChangeRow 21,910;

Each record starts out with ~950 bytes, so the 16 records will fit into two pages. From there the records are updated in a way so that each of them ends up on the other page with a forwarding record in its old place.

Now lets put the exact same data into the dbo.NoForwardSmall table:

INSERT INTO dbo.NoForwardSmall
SELECT * FROM dbo.ForwardSmall;

This again requires two pages, but this time no forwarded records are created.

To confirm, we can use the following query using the sys.dm_db_index_physical_stats DMF:

SELECT OBJECT_SCHEMA_NAME(object_id)+'.'+OBJECT_NAME(object_id) Tbl,index_type_desc,alloc_unit_type_desc,page_count,record_count,forwarded_record_count
FROM sys.dm_db_index_physical_stats(DB_ID(),NULL,NULL,NULL,'detailed') ps
WHERE object_id IN (OBJECT_ID('dbo.ForwardSmall'),OBJECT_ID('dbo.NoForwardSmall'));

This query returns the number of pages, the total number of records and the number of forwarded records for each table:

Tbl	index_type_desc	alloc_unit_type_desc	page_count	record_count	forwarded_record_count
dbo.ForwardSmall	HEAP	IN_ROW_DATA	2	32	16
dbo.NoForwardSmall	HEAP	IN_ROW_DATA	2	16	0

Now let us look at what happens during a table scan:

SET STATISTICS IO ON;
SELECT * FROM dbo.NoForwardSmall;
GO
SELECT * FROM dbo.ForwardSmall;
SET STATISTICS IO OFF;

This produces the following output:

(16 row(s) affected)
Table 'NoForwardSmall'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(16 row(s) affected)
Table 'ForwardSmall'. Scan count 1, logical reads 18, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Scanning the dbo.NoForwardSmall table caused 2 logical reads - one for each page of the table. Scanning the dbo.ForwardSmall table however caused 18 logical reads. That is almost ten times more. Each of the 16 records caused an additional page read.

Conclusion

This article showed that SQL Server follows each forwarding record it encounters right away. This not only happens in the case of an RID-Lookup but also in the case of a table scan. These additional reads can present a significant performance impact. If you have a decently sized table with variable length columns and with regular update activity, add this behavior to the list of reasons why the table really should have a clustered index.

2012-02-08: Index Internals – February 2012 Philadelphia SQL Server Users Group Meeting

Sebastian — Sun, 29 Jan 2012 01:37:19 +0000

On 2/8 I am going repeat my talk about Index Internals at the Philadelphia SQL Server Users Group Meeting.
Signup here to attend: http://pssug20120208.eventbrite.com/

Title	Index Internals - How SQL Server stores and accesses data
When	02/08/2012 at 17:30
Where	Philadelphia SQL Server Users Group Meeting DeVry University Rm 121 1140 Virginia Dr Fort Washington, PA

How to rollback in procedures

Sebastian — Mon, 23 Jan 2012 15:00:39 +0000

Transaction Management

The question where in the call stack a transaction should be managed, is similar to the one where errors should be handled. There are several strong reasons to push the transaction management as high up the stack as possible. The most obvious reason is the lack of support for nested transactions in SQL Server.

SQL Server does allow to nest BEGIN TRANSACTION ... COMMIT blocks within each other. However, only the outermost layer actually opens and closes a transaction. In the inner layers SQL Server just maintains a counter; only the outermost COMMIT has any effect on the data.

With that structure in place, SQL Server has no way to do a partial rollback, so if a rollback is requested, everything is rolled back to the beginning of the outer most transaction.

If you have code, that does some data changes followed by a procedure call followed by other data changes, all within a transaction, and the procedure decides to execute a rollback, the rest of the data changes after the procedure call will execute outside of any transaction. Among other catastrophies this can cause inconsistencies in your data and it will prevent another rollback later.

SQL Server realizes this to be a mayor issue. It raises an error anytime the transaction count before and after the execution of a procedure do not match. You can try this out with this code snippet:

IF OBJECT_ID('dbo.DoRollback') IS NOT NULL DROP PROCEDURE dbo.DoRollback;
GO
CREATE PROCEDURE dbo.DoRollback
AS
BEGIN
  BEGIN TRAN
  ROLLBACK;
  RETURN 0;
END;
GO

RAISERROR('Calling dbo.DoRollback outside of transaction',0,1)WITH NOWAIT;
EXEC dbo.DoRollback; -- No Error

GO

RAISERROR('Calling dbo.DoRollback inside of transaction',0,1)WITH NOWAIT;
BEGIN TRAN;
EXEC dbo.DoRollback; -- Error

Executing the procedure after starting a transaction causes an error like this:

Transaction count after EXECUTE indicates a mismatching number of BEGIN and COMMIT statements. Previous count = 1, current count = 0.

That error however does not prevent execution of additional code. The following example demonstrates that by calling the above procedure within another procedure:

IF OBJECT_ID('dbo.CallDoRollback') IS NOT NULL DROP PROCEDURE dbo.CallDoRollback;
GO
CREATE PROCEDURE dbo.CallDoRollback
AS
BEGIN
  BEGIN TRAN;
  EXEC dbo.DoRollback;
  RAISERROR('--Inside dbo.CallDoRollback after calling dbo.DoRollback',0,1)WITH NOWAIT;
  IF(@@TRANCOUNT>0)ROLLBACK;
  RETURN 0;
END;
GO

RAISERROR('Calling dbo.CallDoRollback',0,1)WITH NOWAIT;
EXEC dbo.CallDoRollback;

So the conclusion here is, that a stored procedure should never execute a rollback. Instead it should raise an error to signal to the outer layer that a situation occurred that requires some mediation like a rollback.

Partial Rollbacks

Every once in while you need to code a procedure that needs to undo its own actions independent of the circumstances it was called in. That can be achieved with a partial rollback.

While SQL Server does not support nested transactions, it allows you to set a save-point within an open transaction. After setting a safe-point you can then rollback all changes that occurred after it. The DoCorrectRollback procedure demonstrates how you can use that functionality in your procedures.

IF OBJECT_ID('dbo.DoCorrectRollback') IS NOT NULL DROP PROCEDURE dbo.DoCorrectRollback;
GO
CREATE PROCEDURE dbo.DoCorrectRollback
AS
BEGIN
  DECLARE @ErrorStatus INT; SET @ErrorStatus = 0;
  DECLARE @TranName VARCHAR(32);SET @TranName = REPLACE((CAST(NEWID() AS VARCHAR(36))),'-','');

  BEGIN TRAN;
  RAISERROR('Setting savepoint: %s',0,1,@TranName)WITH NOWAIT;
  SAVE TRAN @TranName;
 
  BEGIN TRY
    EXEC dbo.DoError;
  END TRY
  BEGIN CATCH
    DECLARE @msg NVARCHAR(MAX);SET @msg = ERROR_MESSAGE();
    RAISERROR('Caught this error: %s',0,1,@msg)WITH NOWAIT;
    SET @ErrorStatus = -1
  END CATCH;

  IF(@ErrorStatus != 0)
  BEGIN
    RAISERROR('Rolling back to savepoint: %s',0,1,@TranName)WITH NOWAIT;
    ROLLBACK TRANSACTION @TranName;
  END;
  
  COMMIT;
  
  RETURN 0;
END;
GO

RAISERROR('Calling dbo.DoCorrectRollback outside of transaction',0,1)WITH NOWAIT;
EXEC dbo.DoCorrectRollback;

GO

RAISERROR('Calling dbo.DoCorrectRollback inside of transaction',0,1)WITH NOWAIT;
BEGIN TRAN
  EXEC dbo.DoCorrectRollback;
COMMIT;
GO

The procedure first executes a BEGIN TRANSACTION to make sure that there is an active transaction. (Remember, this does not have any effect inside a preexisting transaction.) Next, the procedure sets a save-point. A save-point requires a unique name that can be up to 32 characters long. The procedure uses the NEWID() function to get this name. NEWID() returns 36 characters of which 4 are a '-', so by removing them we end up with the required 32 characters.

After this transaction setup section the actual code is executed inside a TRY...CATCH block. If an error is thrown, the error handling code causes a ROLLBACK to be executed. The ROLLBACK TRANSACTION statement takes the save-point name as parameter, which causes the rollback to undo only actions that happened after the save-point was set - the beginning of the procedure in our case.

This ROLLBACK to the previously set save-point does not change the open transaction counter at all, so before the procedure returns it needs to execute a commit to bring the transaction counter back to the state it was in at the beginning of the procedure. This step has to be taken independently of the ROLLBACK being executed or not. It should therefore be the last statement of the procedure.

This allows the procedure to be called inside and outside of a transaction without causing adverse effects by executing a rollback.

Limitations

SQL Server allows to set several save-points within one active transaction as long as they have unique names. If a name is reused the existing save-point is moved to the current position and no error is thrown, so be sure to use unique names as shown in the example.

Another limitation is, that save-points cannot be used in distributed transactions spanning more than one SQL Server instance. If you try to set a save-point in a distributed transaction an error is thrown.

Lastly, the example given does not notify the outer layers about the existence of a problem. This should certainly be part of the design of your procedures. There are several ways to achieve this, for example by raising an error after the rollback step that contains the reason for the rollback.

2012-01-24: Index Internals – January 2012 SJ SQL Server Meeting

Sebastian — Sun, 22 Jan 2012 21:01:59 +0000

On 1/24 I am going to talk about Index Internals at the SJ SQL Server Meeting.
Signup here to attend: http://sjpssug20120124.eventbrite.com/

Title	Index Internals - How SQL Server stores and accesses data
When	01/24/2012 at 17:30
Where	SJ SQL Server Meeting Haddon Heights Public Library 608 Station Ave Haddon Heights, NJ 08035

Presentation Materials – Index Internals

Sebastian — Sun, 22 Jan 2012 20:46:16 +0000

Abstract

In this session we will examine one of SQL Servers' most fundamental yet most important functions - how does SQL Server store data on disk and how does it find it again when executing a query. Using a combination of demos, lecture and discussions we will begin with the structure of the data on disk by delving into the world of HoBTs and Extends, RIDs and Keys and especially Pages. From there we will tackle topics concerning the retrieval of data such as Index levels, Index Scans and Seeks and Lookups.

Downloads

Other Resources

Selecting the entire Database as XML String

Sebastian — Fri, 13 Jan 2012 17:09:15 +0000

I just ran into this question on StackOverflow: Dump data into single XML file from MS SQL Server 2008 R2. In there Daniel is looking for a solution to export his database as an XML file.

I thought that request was an excellent way to practice my XML skills so I spend a little time to come up with a solution.

For testing purposes I first created a few tables in an empty database:


DECLARE @cmd NVARCHAR(MAX) ;
SET @cmd = ( SELECT 'CREATE TABLE T' + CAST(n AS NVARCHAR(MAX))
                    + '(id INT IDENTITY(1,1)'
                    + (SELECT   ',c' + CAST(c.n AS NVARCHAR(MAX))
                                + ' INT DEFAULT ' + CAST(c.n AS NVARCHAR(MAX))
                                + '*' + CAST(t.n AS NVARCHAR(MAX))
                       FROM     dbo.GetNums(( t.n - 1 ) % 10 + 1) c
             FOR    XML PATH('') ,
                        TYPE).value('.', 'NVARCHAR(MAX)') + ');INSERT INTO T'
                    + CAST(n AS NVARCHAR(MAX)) + ' DEFAULT VALUES;'
             FROM   dbo.GetNums (3000) t
FOR XML PATH('') ,
        TYPE).value('.', 'NVARCHAR(MAX)') ;

EXEC(@cmd) ;

This snippet uses Itzik's GetNums function to generate 3000 CREATE TABLE and INSERT statements.

With the table in place I was able to come up with this solution to the original question:

DECLARE @cmd NVARCHAR(MAX) ;
SET @cmd = 'SELECT * FROM('
    + STUFF(
(SELECT ' UNION ALL SELECT ''' + QUOTENAME(OBJECT_SCHEMA_NAME(object_id))
        + '.' + QUOTENAME(name) + ''' [@name],' + '(SELECT * FROM '
        + QUOTENAME(OBJECT_SCHEMA_NAME(object_id)) + '.' + QUOTENAME(name)
        + ' FOR XML PATH(''row''),TYPE) data'
 FROM   sys.tables
    FOR     XML PATH('') ,
                TYPE).value('.', 'NVARCHAR(MAX)'), 1, 11, '')
    + ')X FOR XML PATH(''table''),TYPE;' ;

EXEC(@cmd) ;

The script builds a single statement. For each table it selects the table name in a column with the name [@name] and the content of that table as XML (using a sub-select) in a column with the name data. All these SELECTs are "UNION ALL"ed together and formated into the final XML document with an additional outer SELECT FOR XML.

If you are only after some of the tables, you can add a where clause in row 8 of the above snippet.

The resulting XML has this format:

For each table there is a

tag that has a name attribut with the table name. It contains a tag that in turn contains one tag for every row in the table.

The only thing missing to make this valid XML is a root tag, but that should be easy to add.

Index Misconceptions [TSQL Tuesday #026 - Second Chances]

Sebastian — Tue, 10 Jan 2012 05:00:11 +0000

T-SQL Tuesday #26 is hosted by David Howard (blog|twitter). This month’s topic is “Second Chances”.

Index Misconceptions

The topic this month is "Second Chances" which means that we can write about anything, we would have liked to write about before but didn't get to. Well, not really anything, but any of the 25 previos T-SQL Tuesday topics. I picked two topics: Indexes by Michael Swart and Misconceptions in SQL Server by Sankar Reddy.

Misconception: SQL Server Indexes are binary trees

I keep running into articles that claim that SQL Server internally uses a binary tree to build it's indexes. That however is incorrect and I would like to use this opportunity to clear things up a little.

SQL Server stores its tables (to be exact: table partitions) in a format that is called a HoBT. HoBT stands for "Heap or B-Tree". A Heap is used for tables without a clustered index. A B-Tree is used for all clustered and nonclustered indexes. If you lock up the word B-Tree on Wikipedia, the first sentence states: "Not to be confused with Binary tree."

The B in B-Tree is often said to stand fo "Balanced". However, when Rudolf Bayer and Ed McCreight at Boeing invented the B-Tree in 1971, they did not specify the meaning of the B at all. Speculations include Balanced, Bushy, Bayer and Boeing (see again Wikipedia).

SQL Server is not using a plain B-Tree but instead a variation called a B+Tree. The main difference to a B-Tree is, that in a B+Tree the actual data is only stored in the leaf nodes with all other nodes containing only key values. In B-Trees the data is distributed over all levels.

So, let's take a look under the covers to see the structure for ourselves. First lets create a table to play with:

CREATE TABLE dbo.IdxTst1
    (
      Id INT IDENTITY(1, 1) ,
      V1 CHAR(795) ,
      F1 CHAR(7254) ,
      CONSTRAINT PK_IdxTst1 PRIMARY KEY CLUSTERED( Id, V1 )
    ) ;

The table has a 4 byte (INT) identity column and two fixed length CHAR columns. The Clustered Index key contains the Id and the 795 byte, a total of 799 bytes. The full row contains an additional 7254 bytes for a total row data size of 8053 bytes. Each row when stored contains some meta information and for this table this additional information is 7 bytes per row, which brings us to a total of 8060 bytes for each row. This is the maximum number of bytes that one row is allowed to take (we are excluding LOB data from this exercise). This row size will make sure that there is always only one row per page.

To look at the structure of the table we are going to use the sys.dm_db_index_physical_stats dmf:

SELECT index_type_desc,Alloc_unit_type_desc,index_depth,index_level,page_count,record_count,avg_record_size_in_bytes 
  FROM sys.dm_db_index_physical_stats(DB_ID(),OBJECT_ID('dbo.IdxTst1'),NULL,NULL,'DETAILED');

This query returns one row for every level of every B+Tree for the dbo.IdxTst1 table. As the table is not partitioned and contains only one index (the clustered index), the query in our case returns only information about this one index.

After inserting one row into the table the query returns the following result set:

index_type_desc	Alloc_unit_type_desc	index_depth	index_level	page_count	record_count	avg_record_size_in_bytes
CLUSTERED INDEX	IN_ROW_DATA	1	0	1	1	8060

The B+Tree has so far only one level (index_level = 0), contains 1 node (page_count = 1) and 1 record within that node. The record has the expected size of 8060 bytes.

To insert a second row SQL Server needs to create a new page (node), as each page can hold only one row. With now two data pages we also need a new root page that links to the data pages:

index_type_desc	Alloc_unit_type_desc	index_depth	index_level	page_count	record_count	avg_record_size_in_bytes
CLUSTERED INDEX	IN_ROW_DATA	2	0	2	2	8060
CLUSTERED INDEX	IN_ROW_DATA	2	1	1	2	806

As expected, the B+Tree has now two levels: Index_level 0 with 2 pages holding one row of 8060 bytes each, and index_level 1 for the root page which holds two records of 806 bytes each – one for each level 0 page. The 806 bytes contain the 799 byte key value plus the pointer to the data page for this key value.

With a key storage size of 806 a page can hold 10 different values, so lets insert an other 8 rows to check:

index_type_desc	Alloc_unit_type_desc	index_depth	index_level	page_count	record_count	avg_record_size_in_bytes
CLUSTERED INDEX	IN_ROW_DATA	2	0	10	10	8060
CLUSTERED INDEX	IN_ROW_DATA	2	1	1	10	806

And one more to force an additional page on index_level 1:

index_type_desc	Alloc_unit_type_desc	index_depth	index_level	page_count	record_count	avg_record_size_in_bytes
CLUSTERED INDEX	IN_ROW_DATA	3	0	11	11	8060
CLUSTERED INDEX	IN_ROW_DATA	3	1	2	11	806
CLUSTERED INDEX	IN_ROW_DATA	3	2	1	2	806

As predicted, we now have two pages on index_level 1 and a new root page on index_level 2. All the data (11 rows) is still stored in index_level 0 in 11 separate pages. All intermediate (and root) pages contain only key values (806 bytes).

The root page can hold 10 entries and each index_level 1 page can also hold 10 entries. That should allow us to insert an additional 89 rows into this table without requiring a fourth index level. So let's try it:

index_type_desc	Alloc_unit_type_desc	index_depth	index_level	page_count	record_count	avg_record_size_in_bytes
CLUSTERED INDEX	IN_ROW_DATA	4	0	100	100	8060
CLUSTERED INDEX	IN_ROW_DATA	4	1	24	100	806
CLUSTERED INDEX	IN_ROW_DATA	4	2	5	24	806
CLUSTERED INDEX	IN_ROW_DATA	4	3	1	5	806

What happened here? We have the expected 100 data rows and the corresponding 100 index_level 0 pages but instead of only 10 index_level 1 and one root page we have now 30 non leaf level pages spread over three levels.

The reason for this is that SQL Server, every time it requires a new page to insert a row, takes the page that should have contained the new row and splits its contents in half, leaving one half in the old page and moving the other half into the new page. After that it inserts the new row into the new page. This algorithm is used for all index pages, no matter of their index_level and independent of the value of the new row. (For leaf level pages SQL Server does not split the existing page if the position of the new row is the end of the table. It instead just adds a new empty page to the table and inserts the row in there. The example in this article hides this behavior as there is always only one row per data page.) That algorithm leaves most of the intermediate index pages with only 5 rows, so after only 55 rows a new index level is required.

To reclaim that space lost space we need to rebuild the index:

ALTER INDEX PK_IdxTst1 ON dbo.IdxTst1 REBUILD;

Now the table structure looks as expected:

index_type_desc	Alloc_unit_type_desc	index_depth	index_level	page_count	record_count	avg_record_size_in_bytes
CLUSTERED INDEX	IN_ROW_DATA	3	0	100	100	8060
CLUSTERED INDEX	IN_ROW_DATA	3	1	10	100	806
CLUSTERED INDEX	IN_ROW_DATA	3	2	1	10	806

The FILLFACTOR of the index does not matter in this case as non data pages in an index are always completely filled during an index rebuild operation (unless PAD_INDEX = ON is also specified).

Conclusion

We did see that SQL Server uses a physical tree implementation that allows for more than two child nodes per tree node. We also confirmed that SQL Server stores only the key values in the non-leaf nodes. That are the two main characteristics of a B+Tree. It also clearly rules out the binary search tree format.

We also ran into a situation where most of the non-leaf levels of the index where only half filled. This is one of the disadvantages that come with the use of B+Trees. Usually this is however not a big issue, as the number of non leaf pages is usually small compared to the total number of pages. You might however want to keep an eye out for this behavior, especially if you ar dealing with overly wide keys, as we did in this example.

If you rather store you data as compact as possible you can do so by executing an index rebuild.

Additional Information

For further information about index internals with some nice graphics check out Michael Swart's Guts Of An Clustered Index, his contribution to his own SQL Saturday #10.

T-SQL Tuesday #25 – SQL Server Tips & Tricks

Sebastian — Tue, 13 Dec 2011 16:39:22 +0000

T-SQL Tuesday #25 is hosted by Allen White (blog). This month’s topic is “SQL Server Tips and Tricks”.

Transaction Log Reuse Wait

One question that keeps coming up in forums, at user group meetings and on twitter is: Why is my transaction log growing out of bounds?

To adhere to the ACID properties, SQL Server records all changes to the database first into the transaction log file. A transaction can only be committed after that write succeeds. The changes to the data itself actually get applied only to the data pages in the buffer pool. If and when they get written to the disk is influenced by several factors that are independent of the transaction itself. The records in the transaction log allow SQL Server to redo a change after a crash for example that prevented the data page changes to be written to disk.

That means in theory, that after the transaction is committed and after the data pages are preserved on disk, there is no need for SQL Server to hold on to the transaction log data anymore. That's why the transaction log usually does not grow unbounded, because SQL Server can reuse the parts of the file(s) that are not needed anymore.

In practice however, there can be several reasons, why such a reuse is not possible. The most common one is the requirement for log backups. If you have your database set to recovery mode FULL, SQL Server does not reuse any part of the log file until it is backed up with a transaction log backup. There are several other reasons why SQL Server might have to wait before it can reuse the transaction log, ranging from long running open transactions to transactional replication.

If you are in a situation that requires you to find out why the transaction log file keeps growing and growing, this simple query can give you the answer:

SELECT name,log_reuse_wait_desc FROM sys.databases;

The log_reuse_wait_desc column contains the reason why the SQL Server currently can't reuse the log file of that database. Explanations for each of the values you can find in BOL under Factors That Can Delay Log Truncation.

SQL Test available

Sebastian — Wed, 07 Dec 2011 19:59:37 +0000

Exciting news!

Red Gate is now shipping SQL Test, a graphical UI for tSQLt.

tSQLt is a Database Unit Testing Framework for SQL Server that was developed by Dennis and me.
SQL Test integrates with SSMS and allows you to create, edit and run your tSQLt tests right where you do all your T-SQL development work anyway. That makes the whole workflow of testing a lot simpler and easier to follow:

Testcases executing in SQL Test

Also check out Grant Fritchey's new video here: http://youtu.be/1w9X-WzcFz0

Give it a try now:

Download SQL Test Now!