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:
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…)
    @Input bigint
RETURNS bigint
    DECLARE @WorkValue bigint=@Input
    DECLARE @Result bigint=0;
    DECLARE @Counter int=0;
    WHILE @Counter<63
        SET @Result=@Result*2
        IF (@WorkValue&1)=1
            SET @Result=@Result+1
            SET @WorkValue=@WorkValue-1
        SET @WorkValue=@WorkValue/2
        SET @Counter=@Counter+1
    RETURN @Result
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.


  1. This post made my day. Thank you

  2. This comment has been removed by the author.

  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))

    1. @Avantix Quattro

      I have to ask... when is the last time you used negative BIGINTs as a Primary Key? There's no need for negative BIGINTs here.

  4. Wooow bits of pure database bewilderness

  5. Rick,
    This is totally awesome! This has all the great attributes of GUIDs except for being globally unique. It doe's have a hot spot once you get some size to the table, it's an almost evenly distributed pattern (which means a Fill Factor actually works to suppress fragmentation), and it's only half as wide as a GUID.

    Nicely done! I'm working on a way to do it with a Tally function inside an iTVF (inline Table Valued Function) to knock out the RBAR and the use of a scalar function but, like I said, this is a totally awesome idea! Thanks for posting it.

    Also, I'm not sure why this site is listing me as "Unknown" but it is. It also won't allow "Notify me". It throws "An error occurred while contacting the server."

    --Jeff Moden

  6. And I phat phingered it. I meant it DOESN'T have a hot spot once is gets some size to it.

    --Jeff Moden