Monday, October 3, 2011

Bit reversion

This might seem to be something you never need in SQL Server, but maybe you do and just never knew, so hear me out:
The problem started with a typical scenario for logging tables and even more with some OLTP tables that are heavily inserted: You have an identity column as your primary key (because GUIDs are taking too much time, or you just want bigints or whatever…) and due to the latch contention on the last index page you just can’t get more inserts than 10.000 a second. (OK, that might be enough for almost everyone… But maybe you are not almost everyone?) So what to do? The idea is called “Reverse index”… (Some other DB systems have those out of the box, SQL doesn’t… Doesn’t matter, we can build one…) the basic idea behind it is that you do a binary flip of the increasing number. How does this help? Well, look at the values you get: (tinyint as a sample…)
Identity value Binary Reverse New value
1 00000001 10000000 128
2 00000010 01000000 64
3 00000011 11000000 172
4 00000100 00100000 32
5 00000101 10100000 160
6 00000110 01100000 96
You see how the values keep jumping? Now there is no latch contention anymore on the PK index…
OK, now how do you accomplish this?
First you need to get rid of the identity. Leave the PK without default value, or build your default with what comes next.
Second we need to get a new unique number. Let us all bow before SQL Server Denali, because it comes bearing gifts for us… The magic word is called SEQUENCE. and it is simple:
CREATE SEQUENCE <SomeSequenceName> START WITH 1 INCREMENT BY 1
Now you get the next value calling:
SET @Variable= NEXT VALUE FOR <SomeSequenceName>
Now all you need to do is the inversion… And here is how that is done: (The code works for Bigint…)
CREATE FUNCTION BitReverse
(
    @Input bigint
)
RETURNS bigint
AS
BEGIN
    DECLARE @WorkValue bigint=@Input
    DECLARE @Result bigint=0;
    DECLARE @Counter int=0;
    WHILE @Counter<63
    BEGIN
        SET @Result=@Result*2
        IF (@WorkValue&1)=1
        BEGIN
            SET @Result=@Result+1
            SET @WorkValue=@WorkValue-1
        END
        SET @WorkValue=@WorkValue/2
        SET @Counter=@Counter+1
    END
   
    RETURN @Result
   
END
And now you can glue this together… If you want a default value it might be easiest to get rid of the input Parameter for the BitReverse and query the sequence in the function itself, but this is up to you.

6 comments:

  1. This post made my day. Thank you

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Take care, the function works only for positive numbers, must to be altered to include a sign bit. Test:
    declare @bi bigint = -1
    declare @re bigint = dbo.bitreverse(@bi)
    select @bi, cast(@bi as varbinary(max)), @re, cast(@re as varbinary(max))
    set @bi = dbo.bitreverse(@re)
    select @bi, cast(@bi as varbinary(max)), @re, cast(@re as varbinary(max))

    ReplyDelete
  4. Thanks for providing this informative information you may also refer.
    http://www.s4techno.com/blog/2016/07/27/introduction-to-sql/

    ReplyDelete