Generate sequential guid

If you work with Sql Server and create a new table you often think about using the right primary key. In Sql Server, if you are using artificially primary keys you normally use an int key or and uniqueidentifier key. For performance reasons an int key (used with identity insert) is better, but you can not generate this key in the business logic. A uniqueidentifier can be generated in the business logic. But if you have a table with millions of enties and a uniqueidentifier primary key and you have lot of inserts in this table, then you could become a performance problem because after every insert the clusted index on the primary key has to be reordered. If you use newid() to generate the keys for the primary key, the generated key is not sequential and your inserts become slow. So since Sql server 2005 there is a possibility to generate sequential guids. With the newsequntialid() function the sql server generates sequential ids.

CREATE TABLE SequentialIdTable (PK uniqueidentifier primary key DEFAULT NEWSEQUENTIALID())

But if you try invoke the NEWSEQUENTIALID() function in the sql server management studio, you get the following error.

The newsequentialid() built-in function can only be used in a DEFAULT expression for a column of type 
'uniqueidentifier' in a CREATE TABLE or ALTER TABLE statement.

So if you want to generate the sequential guid in your business logic, you need to implement the sequential guid by yourself. So you need the following expression to generate the sequential guid at the sql server:

select cast(newid() AS BINARY(10) + CAST(getdate() AS BINARY(6)) AS UNIQUEIDENTIFIER)

This expression takes a new guid generated by the newid() function and takes the first 10 bytes and adds the 6 bytes from a datetime generated with getdate() to it. The cast to binary allows it to concenate the part of the guid with the datetime. So now we always get a new guid that is bigger than the guid generated before. This works because sql server orders guids in a very special way. If you want to know how, there is the blog that describes it. So at the database we now can generate a sequential guid and use it as default value in a tablecolumn or in stored procedure or function. But if we want to generate a sequential guid in the business logic we need the following class.

public class SequentialGuidGenerator
{
    public Guid CreateSequentialGuid(Guid guid, DateTime targetDateTime)
    {
       // the datetime datatype on sql server contains 8 bytes 
       // the first 4 bytes store the days since 1900
       // the second 4 bytes store the milliseconds since 00:00 of the actual day
       // diveded by 3.3333333 because milliseconds get rounded
       // the value for the DateTime '2.1.1900 00:00:00.002' in hex
       // 7 6 5 4 3 2 1 0
       // 0x 00 00 00 01 00 00 00 01 
       var baseDateTime = new DateTime(1900, 1, 1);
       var ticksSince0001 = baseDateTime.Ticks;
       var ticksSince1900 = targetDateTime.Ticks - ticksSince0001;
       // convert ticks (nanoseconds) since 1900 into days
       var daysSince1900 = ticksSince1900 / 10000 / 1000 / 3600 / 24;
       // milliseconds today
       var millisecondsToday = targetDateTime.Hour * 60 * 60 * 1000 +
          targetDateTime.Minute * 60 * 1000 +
          targetDateTime.Second * 1000 +
          targetDateTime.Millisecond;
       // divide milliseconds by 3.3333333 because milliseconds get rounded
       double milliseconds = millisecondsToday / 3.333333;
       // shift days four bytes to the left
       var daysValue = daysSince1900 << 32;
       // add milliseconds of the current day to the days value
        daysValue += Convert.ToInt64(Math.Round(milliseconds, 0));
       // generate new guid
       //Guid guid = System.Guid.NewGuid();
       //Guid guid = System.Guid.Empty;
       // convert guid to byte array
       byte[] guidArray = guid.ToByteArray();
       // convert daysValue to byte array
       byte[] daysValueArray = BitConverter.GetBytes(daysValue);
       // override last 8 bytes of guid array with daysValue array
       foreach (int item in Enumerable.Range(0, 7))
       {
           guidArray[15 - item] = daysValueArray[item];
       }
       // generate guid from overriden guidArray
       Guid resultGuid = new Guid(guidArray);
       return resultGuid;
   }
}

As you see in the comments of the CreateSequentialGuid method first i calculate the base time i need. Sql server datetime type starts at 01-01-1900 and the .net DateTime type starts at 01-01-0001 so i had to bring both to the same base time. Then i had to shift the day value 4 bytes to the left and add the milliseconds (divided by 3.33333) to the value. The last step is to add the generated bytes to the correct position in the Guid. The following tests show how the generated Guids look like.

[TestMethod]
public void CreateSequentialGuidTrue()
{
  var sequentialGuidGenerator = new SequentialGuidGenerator();
  var guid = sequentialGuidGenerator.CreateSequentialGuid(System.Guid.Empty,
  new DateTime(1900, 1, 1));
  Assert.AreEqual("00000000-0000-0000-0000-000000000000", guid.ToString());

  guid = sequentialGuidGenerator.CreateSequentialGuid(System.Guid.Empty, new
  DateTime(1900, 1, 2));
  Assert.AreEqual("00000000-0000-0000-0000-000100000000", guid.ToString());

  guid = sequentialGuidGenerator.CreateSequentialGuid(System.Guid.Empty, new
  DateTime(1900, 1, 4, 0, 0, 0, 4));
  Assert.AreEqual("00000000-0000-0000-0000-000300000001", guid.ToString());

  guid = sequentialGuidGenerator.CreateSequentialGuid(System.Guid.Empty, new
  DateTime(1900, 1, 3, 0, 0, 0, 9));
  Assert.AreEqual("00000000-0000-0000-0000-000200000003", guid.ToString());
}

So if you generate sequential guids this way you can gernerate the guid at the database and in the business logic, and you avoid big perfomance problems if you have multible inserts into tables with millions of rows and a uniqueidentifier primary key column.

Advertisements


If you have a note or a question please write a comment.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s