Wednesday, October 5, 2011

The day Sequences saved the world

In my last post I brought up the idea of reverse indexes and how those could save you from latch contentions.Well, after another day of hard work it turns out that the new Sequence feature in SQL Denali really is a kind of universal life saver for high load OLTP applications… I don’t know how many sequences we did already to get rid of latch contention and last page inserts, but I can tell you, it were quite a few…

There are two things I have to add though regarding my last post:

First… If you run sequences in really high load environments you have to use the CACHE feature. In the case of a server crash this might leave you with gaps in your sequence, but if you don’t use the Cache you will get locking issues on the sequence once you hit somewhere around 10.000 Fetch next statements per second.

And second… While my T-SQL bit reverser works perfectly fine it is sort of CPU intensive… Our 80-core server burnt about 1% CPU per 1000 rows inserted, with more than half of that going into the bit reverser. I did a lot of tests following this finding, and it almost hurts me to say that, but in this one case SQL CLR really is the best solution you can have… Using the CLR function instead of the T-SQL function we are almost down to nothing for the bit reverse.

Oh, and here is the code of the CLR function: (If anyone wants the compiled DLL or the complete solution please ping me and I’ll mail it to you.)

public static Int64 Reverse(Int64 inVal)
    ulong Result = 0;
    ulong Input = (ulong)inVal;
    int i;
    for (i = 0; i < 63; i++) // 64 bits...
        Result <<= 1; // Shift result by one digit
        if ((Input & 1) == 1) // If lowest bit of input is 1 add one to result
        Input >>= 1; // Now shift the input so that the next bit is lowest
    return (Int64) Result;


  1. Excellent blog post Rick, you beat me to it. I have just posted a blog entry that adds more data to support your test.

    You should see a pingback from my blog very soon

    1. Dr Osato herbal medicine cures herpes within two weeks. I just tested negative for Genital herpes after using Dr Osato herbal meds for two weeks! To place an order and get yours today visit his website or email him at OSATOHERBALCURE@GMAIL.COM or WhatsApp +2347051705853.

  2. Actually Rick... How about this way to generate the sequence (if we assume you are a BIGINT):

    @@SPID * 10000000000 + [Next Sequence Number]

  3. Nice idea Thomas, but I see two drawbacks:
    1) You loose IDs (as you can't predict a SPID), and this could also lead to duplicates if you are not extra carefull.
    2) SPIDs tend to group together, especially if your app uses connection pooling...

  4. RSince you are adding a sequence and a large offset, it will not result in duplicates. The sequence is already unique, and offsetting it by 10B will only make it "non unique" if you have more than 10B inserts per SPID (unlikely?)

    The grouping together is exactly the idea of the SPID trick. To avoid page latch, you have to "split the key space". Bit flipping achieves this - but so does the SPID splitting. For SPID splitting, each 10B range will have its own little "subspace" that where inserts are linear (which is OK; because PAGELATCH only happens at concurrency, which you wont have per SPID, only per server).

    The SPID grouping should give you less fragmentation, but more importantly, less page splits (but it does require the assumption that you can "pre-partition the space" - your bitflip doesnt require that.

  5. 10B inserts are not that unlikely... Two years ago someone told me that we would never need more than int16... now we are at int64 already...

    The point behind grouping is that if I have two SPIDs reused (e.g. 52 and 53) by two heavy load servers I get a grouping around those two spids, while every other "subspace" might be less congested.
    You are still right that this will give you good segmentation at less CPU cost, but when you need the best possible segmentation I still think I am a little ahead ;-)

  6. Good point on the SPID grouping consuming part of the "key space" faster than others.

    Another options to consume the space evenly would be to use scheduler_id (since that is guaranteed to be approximately equal)

    Would be interesting to see how these methods measure up against each other on CPU and page splitting

  7. Instead if looping, how does this attempts stand up? I know it's only 32-bit.

    unsigned int v; // 32-bit word to reverse bit order

    // swap odd and even bits
    v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
    // swap consecutive pairs
    v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
    // swap nibbles ...
    v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
    // swap bytes
    v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
    // swap 2-byte long pairs
    v = ( v >> 16 ) | ( v << 16);

  8. Thanks for that input Unknown... Took me a while to wrap my head around it, but it is a really cool one. Recoded in Assembler it takes a little over 100 CPU cycles, which is another improvement over what I had. And it works with 64bit just as it does with 32...
    I think I will stresstest that and post it, if it should stand up.

  9. Thank you sir. Can you please send me the complete code (CLR) for key generation using bit reversal.


  10. it’s ok to show some appreciation and say ‘great post’
    Asp .NET developer

  11. I GOT CURED FROM HERPES VIRUS I was diagnosed of HERPES virus and i have tried all I can to get cured but all to no avail,,until I saw a post in a health forum about a herbalist man who prepare herbal medications to cure all kind of diseases including #HERPES virus,at first I doubted if it was real but decided to give it a try,when I contacted this herbalist via his email and he prepared a #HERPES herbal cure and sent it to me via DHL delivery company service, when I received this herbal medicine, he gave me step by direction on how to apply it,after applying the way I was instructed,I was totally cured of this deadly disease called HERPES, all thanks to Dr OGODO Email this great herbal doctor via his email
    You can also WhatsApp him on +2349044680467
    {5} HPV
    {6} ALS
    Only DR OGODO Can Help You I Love You Father.
    You can check his website on his Facebook page.

  12. My health was horrible before I decided to try the Protocol Of taking Dr. Omola pure herbal mixture. I felt there was no hope for my health and I was to try the Protocol, thinking it wouldn’t work because I have visited so many hospital but same result. However, I was convinced by a Instagram friend to try the herbal medicine because I wanted to get rid of Herpes virus. The herbal mixture that was given to me was really quick and easy to take, within 2 week I was fully cured from Herpes. The herbal medicine really work and I will like to share this great doctor contact with you all email him or WhatsApp +2348118116254 you won't regret it, I promise.

  13. Thanks to Dr Aire for curing me of HPV2, Indeed you are great, your herbal medicine its real and 100% satisfactory, am glad to have patronized you. Once again thanks to you for the good work you have done in my life. i will advised anyone out here living with herpes should please contact him to get the herbal cure for herpes its 100% guarantee and work, with no side effects. I recommend his service for you kindly contact him to get your cure as well. On his email: Whatsapp: +2347036740271 

  14. Dr Osato herbal medicine cures herpes within two weeks. I just tested negative for Genital herpes after using Dr Osato herbal meds for two weeks! To place an order and get yours today visit his website or email him at OSATOHERBALCURE@GMAIL.COM or WhatsApp +2347051705853.

  15. Good day everyone, it's hard to believe that herbal medicine can cure herpes, I never believe that this will work, I have to spend a lot of money getting drugs from the hospital to keep me and my son healthy, it got to a point that I was waiting for death to come because I was broke, one day I hard about this great man called Dr. Abolo who is well know for Herpes, HIV, and cancer cure, I decided to email him I didn't believe him that much, I just wanted to give him a try, he replied to my mail and Needed some Information about me, then I sent them to him, he prepared herbal medicine and he gave my details to the Courier Office. they told me that in 4-6 days I will receive the package and after receiving it, I took the medicine as prescribed by him at the end of two weeks, he told me to go to the hospital for a check-up, and I went, surprisingly after the test the doctor confirm me Herpes simplex virus-negative, and my son and I thought it was a joke, I went to another hospital and was also negative, thank you for saving our life's, I promise I will always testify of your good works. if you are a herpes simplex virus patient, contact him and I am sure you will get cured, contact him on his Email@ or contact him on his whatSApp number +234744725611
    . HERPES
    . HIV/AIDS
    . CANCER

  16. I am here to give my testimony
    about Dr babaiba who helped me.. i want to inform the public how i was cured from (HERPES SIMPLEX VIRUS) by salami, i visited different hospital but they gave me list of drugs like Famvir, Zovirax, and Valtrex which is very expensive to treat the symptoms and never cured me. I was browsing through the Internet searching for remedy on HERPES and i saw comment of people talking about how Dr babaiba cured them. when i contacted him he gave me hope and send a Herbal medicine to me that i took for just 2 weeks and it seriously worked for me, my HERPES result came out negative. I am so happy as i am sharing this testimony. My advice to you all who thinks that there is no cure for herpes that is Not true just contact him and get cure from Dr babaiba healing herbal cure of all kinds of sickness you may have like
    . he also cure my friend from cervical #cancer Email: ( or call or WHATAPP +2348140046509 I am forever greaful ...

  17. I got Diagnosed with Herpes, I have be dealing with Herpes for the past 4 years. On till I got review online about natural cure people testifies how DR. Ehimare cure them with his herbal treatment. And I order the treatment, after taking it for 21 days I totally got cured with DR. Ehimare treatment. I'm recommending you diagnosis with herpes should get this treatment and be cured of it you can contact his email address via; drehimare3@gmail. com or you can also call or whatsapp +1 (267) 691-1087Dr. Ehimare also cure the following virus and many more... 1} Cancer 2} Diabetes 3} Hepatitis 4} fibroid 5} herpes 6} Lupus

  18. Greetings to everyone reading this testimony,am here to
    testify of a great man who was able to cure me permanently from herpes
    Disease just with his herbal medicine,i have been herpes Positive for 5
    years before i came across Dr voodoo Email on the internet on how he has
    been using his herbal medicine to treat and cure patients from different
    virus, so i contacted him and i explain to him concerning my problem, i
    followed up with the instructions he gave me and he urge me to have faith
    in his words that he was going to restore my health back, after some couple
    of days Dr voodoo sent me some medicine which he gave me prescription on
    how to take for 2 weeks, to make the long story short, I have been
    confirmed Negative from my recent test in the hospital, just within 2 weeks
    Dr voodoo was able to make me healthy and see reasons to live again, though
    science says there is no cure, i believe God has sent this great man to
    save people, you can all contact him for his medicine, he has presently
    been treating diseases like,CANCER,BLOOD DISEASE,DIABETES,HIV,TYPHOID, and
    many others, you can contact this man on
    add him on whatsApp +2348140120719, God Bless you sir!