Missing numbers in a series

Question

Missing numbers in a series

Viewing 15 posts - 31 through 45 (of 61 total)

You must be logged in to reply to this topic. Login to reply

Jeff Moden SSC Guru Points: 1004363 More actions · Answer 1

Paul White NZ (5/4/2010)
Jeff Moden (5/4/2010)
Absolutely. You know me... I never turn down knowledge. Thanks, Paul.
Hey Jeff and Mr Coffee - I'm not saying a SQLCLR solution won't suck (it might do!) but since there is interest, I'll have a go later. Just a bit busy with QotD at the moment 😀
My objective would be to get close to Jeff's rocket code performance here, I don't think there's much chance of a win...but hey I am awesome so anything's possible :laugh:

On no... I wasn't being a smart guy on my response, Paul. I'd really be interested in seeing what a CLR could do with this one way or the other because it would be another "data point" for the ol' calcium knob to ponder.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 2

Jeff Moden (5/4/2010)
On no... I wasn't being a smart guy on my response, Paul. I'd really be interested in seeing what a CLR could do with this one way or the other because it would be another "data point" for the ol' calcium knob to ponder.

I was hedging my bets - don't tell anyone 😉

Going to be tomorrow now, but definitely going to give this a go.

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Jeff Moden SSC Guru Points: 1004363 More actions · Answer 3

Jeff Moden (5/4/2010)

Hey guys.... just ignore this post... I was testing our Injection Blocker for anything that contains code.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 4

Jeff Moden (5/4/2010)
I'd really be interested in seeing what a CLR could do with this one way or the other because it would be another "data point" for the ol' calcium knob to ponder.

Ok, so I coded a quick 'n' dirty CLR aggregate, tested it out with Jeff's sample data, and could not believe the difference between 2005 (9.0.4285) and 2008 (10.0.2766) - same machine, different instance, same configuration.

I'm just going to post the results of my runs without code at this stage because I want to understand this more first. Ten-run minimum, maximum, average, and standard deviation elapsed times in milliseconds:

2005

method minimum maximum average std_dev

CLR 1676 1746 1701 26

Jeff 1353 1490 1397 50

2008

method minimum maximum average std_dev

CLR 2030 2203 2096 59

Jeff 1996 2156 2065 63

Weird huh?

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Jeff Moden SSC Guru Points: 1004363 More actions · Answer 5

Paul White NZ (5/5/2010)
Weird huh?

Heh... it's not a fault... it's a feature. Gives folks more time to take a sip of Scotch whilst waiting for their code to run.

Thanks for doing the testing, Paul. Like I said, another datapoint for the ol' calcium knob.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 6

Jeff Moden (5/5/2010)
Heh... it's not a fault... it's a feature. Gives folks more time to take a sip of Scotch whilst waiting for their code to run.

Yes, that must be it 🙂

Thanks for doing the testing, Paul. Like I said, another datapoint for the ol' calcium knob.

No worries. Now, I have to say that your code solution is extremely beautiful, and a solution I had not even considered. The merge join is fantastically efficient - it even manages to avoid the many-to-many trap! Very, very nice.

Just for fun I (predictably) tweaked it to use APPLY with EXISTS (same plan):

SELECT GapStart = Lo.MyID + 1,

GapEnd = Hi.MyID - 1

FROM dbo.MyTest Hi

CROSS

APPLY (

SELECT MyID = ISNULL(MAX(Lo.MyID), 0) + 1

FROM dbo.MyTest Lo

WHERE Lo.MyID < Hi.MyID

) Lo

WHERE NOT EXISTS

(

SELECT NotIn.MyID + 1

FROM dbo.MyTest NotIn

WHERE NotIn.MyID + 1 = Hi.MyID

);

What impressed me about the SQLCLR solution (even though it came second!) is that it managed to get close at all. The overhead of passing it nearly two million rows made this a tough ask. Happily, the SQLCLR solution out-performs all the other gap solutions I know of - just not your code! Moden strikes again!

Paul

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Jeff Moden SSC Guru Points: 1004363 More actions · Answer 7

Paul White NZ (5/5/2010)
What impressed me about the SQLCLR solution (even though it came second!) is that it managed to get close at all. The overhead of passing it nearly two million rows made this a tough ask. Happily, the SQLCLR solution out-performs all the other gap solutions I know of - just not your code! Moden strikes again!

I have to admit, I was also very surprised by the CLR for this. As you said, it had to get to almost 2 million rows which I didn't really believe it would be any good at at all. Massive datapoint for the calcium knob. 😀

What's really funny about both your code and mine is that I'd swear there's an aggregated triangular join in it but it just never materializes that way (I believe that's what you meant by the "many-to-many trap?).

I have to admit that the basis of the code wasn't my original idea. I saw it on some forum somewhere around 8-10 years ago. It was a bit slower than the current slightly tweeked version but it was a really good find.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 8

Jeff Moden (5/5/2010)
I was also very surprised by the CLR for this. As you said, it had to get to almost 2 million rows which I didn't really believe it would be any good at at all.

Generally, you'd be right - using a SQLCLR stored procedure (or function) and the 'context connection' to retrieve two million rows would be a disaster. Luckily the transfer interface to the input of a SQLCLR aggregate is much faster. If I hadn't had that trick up my sleeve, I would not have even attempted a SQLCLR solution.

What's really funny about both your code and mine is that I'd swear there's an aggregated triangular join in it but it just never materializes that way (I believe that's what you meant by the "many-to-many trap?).

Doesn't this remind you of the 'triangular join' I surprised you with a few weeks back? The one with the computed column CASE expression on the NULLs? I don't recall the exact details...:(

A triangular join can be fast in very precise circumstances - typically where an aggregate or TOP expression with ORDER BY can seek directly to the first or last row of a supporting index. This is obviously cheating, since it doesn't touch all the intermediate rows, but still.

It's not bullet-proof by any means: in this problem, for large numbers of gaps, performance might still drop off as the number of seeks increases - and especially if the QO decides on a hash or merge instead of the loop.

The 'many-to-many' trap I mentioned refers to the mode that the Merge Join runs in. Merge is extremely efficient when doing a one-to-many match, but a many-to-many join needs a tempdb worktable to rewind the outer input as necessary. If you hover over a Merge Join iterator on a graphical plan, it will show you which mode it is running in (also STATISTICS IO will show that a worktable was used). Most of the merge-based solutions I tried wound up doing a many-to-many match (unnecessarily - but the QO has reasoning limits!)

Merge is great for some problems: it starts reading from both inputs simultaneously (a Hash Join has to read its build input completely to create the hash table before matching rows from the probe input can begin). Merge will also stop reading from its inner input as soon as all the rows from the outer input have been matched - not important for this problem, but it sure can be.

I have to admit that the basis of the code wasn't my original idea. I saw it on some forum somewhere around 8-10 years ago. It was a bit slower than the current slightly tweeked version but it was a really good find.

Absolutely it was. And don't get over modest here - it is code to be proud of, for sure.

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Garadin One Orange Chip Points: 29613 More actions · Answer 9

It's threads like this that remind me on a regular basis how much I still need to learn about SQL Server :hehe:.

Seth Phelabaum

Consistency is only a virtue if you're not a screwup. 😉

Links: How to Post Sample Data[/url] :: Running Totals[/url] :: Tally Table[/url] :: Cross Tabs/Pivots[/url] :: String Concatenation[/url]

Jeff Moden SSC Guru Points: 1004363 More actions · Answer 10

@ Paul,

Yep... I remember the "other" triangular join. You made it to be very fast but it still ended up doing the same number of reads. This one seems to avoid that for some reason.

@ Seth,

I agree... now all we have to do is get Paul to post his SQLCLR aggregate code and we'll be all set. 😛

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 11

Ok, here's the quick 'n' dirty CLR aggregate:

CREATE ASSEMBLY Aggregates

AUTHORIZATION dbo

FROM 0x4D5A90000300000004000000FFFF0000B800000000000000400000000000000000000000000000000000000000000000000000000000000000000000800000000E1FBA0E00B409CD21B8014CCD21546869732070726F6772616D2063616E6E6F742062652072756E20696E20444F53206D6F64652E0D0D0A2400000000000000504500004C010300E73DE34B0000000000000000E00002210B010800001000000020000000000000BE2D00000020000000400000000040000020000000100000040000000000000004000000000000000080000000100000000000000300408500001000001000000000100000100000000000001000000000000000000000006C2D00004F000000004000004003000000000000000000000000000000000000006000000C00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000080000000000000000000000082000004800000000000000000000002E74657874000000C40D0000002000000010000000100000000000000000000000000000200000602E7273726300000040030000004000000010000000200000000000000000000000000000400000402E72656C6F6300000C00000000600000001000000030000000000000000000000000000040000042000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000A02D000000000000480000000200050068220000040B000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005602166A7D010000040216731200000A7D020000042AC60F01281300000A2D2702257B01000004176A587D0100000402257B020000040F01281400000A281500000A7D020000042AE20F017B01000004166A312C02257B010000040F017B01000004587D0100000402257B020000040F017B02000004281500000A7D020000042A0000001B3002003B00000001000011027B01000004166A3129027B02000004027B01000004281600000A281700000A281800000A281900000A0ADE0C26FE1A26FE1A7E1A00000A2A062A00011C000000000A00232D00031B00000100000A00233000031C0000016603027B010000046F1B00000A03027B020000046F1C00000A2A6602036F1D00000A7D0100000402036F1E00000A7D020000042A6602176A7D06000004022000080000731F00000A7D050000042A0000033003006A0000000000000003027B06000004176A582E56027B05000004027B060000046F2000000A26027B050000041F2D6F2100000A26027B05000004036F2000000A26027B050000041F3B6F2100000A2602037D0600000403027B060000042F0B7201000070732200000A7A02037D060000042A66027B050000040F01280A0000068C050000016F2300000A262A46027B050000046F2400000A281900000A2A7A03027B060000046F1B00000A03027B050000046F2400000A6F2500000A2A7A02036F1D00000A7D0600000402036F2600000A732700000A7D050000042A42534A4201000100000000000C00000076322E302E35303732370000000005006C000000C8030000237E0000340400007404000023537472696E677300000000A80800004000000023555300E8080000100000002347554944000000F80800000C02000023426C6F620000000000000002000001571F02020900000000FA013300160000010000001E00000003000000060000000C000000080000000200000027000000020000000C0000000100000002000000010000000200000000000A00010000000000060035002E000A0066004B0006007D002E000A00A3008E000A00BF008E000600DD00D3000600F000D3000600230117010600B501A3010600F301D40106000702A30106002002A30106003B02A30106005602A30106006F02A30106008802A3010600A702A3010600C402A3010600FB02DB0206001B03DB02060044032E000A005A034B000A007B034B0006008203D40106009803D4010600EB032E00060001042E00060017042E00060050042E00060060042E00000000000100000000000100010009211000190000000500010001000921100020000000050003000700010077000A00010085000D0051800201320051800D013200010031013B00010035010A0050200000000086008900110001006620000000008600AE00150001009820000000008600B9001B000200D420000000008600C90021000300382100000000E601EA0026000300522100000000E601FD002C0004006C210000000086008900110005008821000000008600AE003F000500FE21000000008600B900440006001822000000008600C900210007002A2200000000E101400126000700492200000000E10172012C00080000000100A30300000100CA03000001002904000001002B04000001004304000001005A04000001002904000001002B0402000900030009001100EA0026001100FD002C004900CE014A005100CE014F005900CE014A006100CE014A006900CE014A007100CE014A007900CE014A008100CE014A008900CE014A009100CE014A009900CE015400A100CE011100A900CE011100B100CE015900C100CE01E1001900CE0154002100A903E7002100B403EB001900BE03F0001900D803F9001900E403F000D100F303FF002900D80305012900FC030B013100EA003F003100EA00140139002D041A0139003704EB004100CE01540041004904A10141004904A701E900CE014A0041004904AD01F100F303B3013100EA004A0039006704B3014100CE014A0003000C0035000300100038002E004300D5012E004B00B7012E007300ED012E003300B7012E003B00BD012E005300B7012E002300B7012E005B00B7012E006300D5012E006B00E401430083005F00630083001E010F010300160003000300180005000480000001000000C30E5B4E00000000000039030000020000000000000000000000010025000000000002000000000000000000000001003F00000000000000003C4D6F64756C653E00416767726567617465732E646C6C004D595F4156470047617073006D73636F726C69620053797374656D0056616C7565547970650053797374656D2E44617461004D6963726F736F66742E53716C5365727665722E536572766572004942696E61727953657269616C697A6500636F756E7400446563696D616C0073756D00496E69740053797374656D2E446174612E53716C54797065730053716C446563696D616C00416363756D756C617465004D657267650053716C537472696E67005465726D696E6174650053797374656D2E494F0042696E6172795772697465720057726974650042696E61727952656164657200526561640052414E47455F43484152005445524D5F434841520053797374656D2E5465787400537472696E674275696C646572005F7362005F6C61737456616C7565004D6963726F736F66742E53716C5365727665722E5365727665722E4942696E61727953657269616C697A652E5772697465004D6963726F736F66742E53716C5365727665722E5365727665722E4942696E61727953657269616C697A652E526561640053797374656D2E5265666C656374696F6E00417373656D626C7956657273696F6E417474726962757465002E63746F720053797374656D2E52756E74696D652E496E7465726F70536572766963657300436F6D56697369626C6541747472696275746500417373656D626C7943756C7475726541747472696275746500417373656D626C7954726164656D61726B41747472696275746500417373656D626C79436F7079726967687441747472696275746500417373656D626C7950726F6475637441747472696275746500417373656D626C79436F6D70616E7941747472696275746500417373656D626C79436F6E66696775726174696F6E41747472696275746500417373656D626C794465736372697074696F6E41747472696275746500417373656D626C795469746C654174747269627574650053797374656D2E52756E74696D652E436F6D70696C6572536572766963657300436F6D70696C6174696F6E52656C61786174696F6E734174747269627574650052756E74696D65436F6D7061746962696C69747941747472696275746500416767726567617465730053657269616C697A61626C654174747269627574650053716C55736572446566696E656441676772656761746541747472696275746500466F726D6174005374727563744C61796F7574417474726962757465004C61796F75744B696E6400506172616D006765745F49734E756C6C006765745F56616C7565006F705F4164646974696F6E005061727469616C526573756C74006F705F496D706C696369740044697669646500436F6E7665727400546F537472696E67004E756C6C0044697669646542795A65726F457863657074696F6E004F766572666C6F77457863657074696F6E007700720052656164496E7436340052656164446563696D616C0056616C756500417070656E6400457863657074696F6E0047726F7570004F626A6563740052656164537472696E67000000003D560061006C007500650020007200650063006500690076006500640020006F007500740020006F0066002000730065007100750065006E006300650000000011AFE3AD4912449AD996D7DC3CB70B0008B77A5C561934E08902060A0306110D03200001052001011111052001011108042000111505200101121905200101121D020603022D00023B0003061221042001010A05200101110C042001010E0420010102042001010805200101115D8080010002000000060054080B4D61784279746553697A65401F00005402174973496E76617269616E74546F4475706C696361746573005402124973496E76617269616E74546F4E756C6C73015402124973496E76617269616E74546F4F726465720154020D49734E756C6C4966456D70747901540E044E616D65064D595F41564705200101116503200002042000110D080002110D110D110D050001110D0A0500010E110D05000111150E03061115040701111505200101110D0320000A8081010002000000060054080B4D61784279746553697A65401F00005402174973496E76617269616E74546F4475706C696361746573015402124973496E76617269616E74546F4E756C6C73015402124973496E76617269616E74546F4F726465720054020D49734E756C6C4966456D70747901540E044E616D65074761705F41474705200112210A05200112210305200112211C0320000E05010000000017010012436F7079726967687420C2A920203230313000000E01000953696D706C6555444100000801000800000000001E01000100540216577261704E6F6E457863657074696F6E5468726F777301942D00000000000000000000AE2D0000002000000000000000000000000000000000000000000000A02D0000000000000000000000005F436F72446C6C4D61696E006D73636F7265652E646C6C0000000000FF2500204000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100100000001800008000000000000000000000000000000100010000003000008000000000000000000000000000000100000000004800000058400000E80200000000000000000000E80234000000560053005F00560045005200530049004F004E005F0049004E0046004F0000000000BD04EFFE00000100000001005B4EC30E000001005B4EC30E3F000000000000000400000002000000000000000000000000000000440000000100560061007200460069006C00650049006E0066006F00000000002400040000005400720061006E0073006C006100740069006F006E00000000000000B00448020000010053007400720069006E006700460069006C00650049006E0066006F0000002402000001003000300030003000300034006200300000003C000A000100460069006C0065004400650073006300720069007000740069006F006E0000000000530069006D0070006C006500550044004100000040000F000100460069006C006500560065007200730069006F006E000000000031002E0030002E0033003700370039002E00320030003000350039000000000040000F00010049006E007400650072006E0061006C004E0061006D006500000041006700670072006500670061007400650073002E0064006C006C00000000004800120001004C006500670061006C0043006F007000790072006900670068007400000043006F0070007900720069006700680074002000A900200020003200300031003000000048000F0001004F0072006900670069006E0061006C00460069006C0065006E0061006D006500000041006700670072006500670061007400650073002E0064006C006C000000000034000A000100500072006F0064007500630074004E0061006D00650000000000530069006D0070006C006500550044004100000044000F000100500072006F006400750063007400560065007200730069006F006E00000031002E0030002E0033003700370039002E00320030003000350039000000000048000F00010041007300730065006D0062006C0079002000560065007200730069006F006E00000031002E0030002E0033003700370039002E003200300030003500390000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000C000000C03D000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

WITH PERMISSION_SET = SAFE;

GO

CREATE AGGREGATE dbo.Gap_AGG

(

@Value BIGINT

)

RETURNS NVARCHAR(4000)

EXTERNAL NAME Aggregates.Gaps;

Example usage: (add string splitting code if required)

SELECT dbo.Gap_AGG(MyID)

FROM dbo.MyTest;

Sample output:

1-10000001;11000000-82011000000001;82011000401999-82011000402001;82011000403999-82011000404001;82011000405999-82011000406001;82011000407999-82011000408001;82011000409999-82011000410001;82011000411999-82011000412001;82011000413999-82011000414001;82011000415999-82011000416001;82011000417999-82011000418001;82011000419999-82011000420001;82011000421999-82011000422001;82011000423999-82011000424001;82011000425999-82011000426001;82011000427999-82011000428001;82011000429999-82011000430001;82011000431999-82011000432001;82011000433999-82011000434001;82011000435999-82011000436001;82011000437999-82011000438001;82011000439999-82011000440001;82011000441999-82011000442001;82011000443999-82011000444001;82011000445999-82011000446001;82011000447999-82011000448001;82011000449999-82011000450001;82011000451999-82011000452001;82011000453999-82011000454001;82011000455999-82011000456001;82011000457999-82011000458001;82011000459999-82011000460001;82011000461999-82011000462001;82011000463999-82011000464001;82011000465999-82011000466001;82011000467999-82011000468001;82011000469999-82011000470001;82011000471999-82011000472001;82011000473999-82011000474001;82011000475999-82011000476001;82011000477999-82011000478001;82011000479999-82011000480001;82011000481999-82011000482001;82011000483999-82011000484001;82011000485999-82011000486001;82011000487999-82011000488001;82011000489999-82011000490001;82011000491999-82011000492001;82011000493999-82011000494001;82011000495999-82011000496001;82011000497999-82011000498001;82011000499999-82011000500001;82011000600000-82011000700001;

C# source code:

using System;

using System.IO;

using System.Text;

using System.Data.SqlTypes;

using Microsoft.SqlServer.Server;

[Serializable]

[SqlUserDefinedAggregate

(

Format.UserDefined,

MaxByteSize = 8000, // Change to -1 in SQL Server 2008 to return NVARCHAR(MAX)

IsInvariantToDuplicates = true,

IsInvariantToNulls = true,

IsInvariantToOrder = false,

IsNullIfEmpty = true,

Name = "Gap_AGG"

)

]

public struct Gaps : IBinarySerialize

{

// Constants

private const char RANGE_CHAR = '-';

private const char TERM_CHAR = ';';

// Fields

private StringBuilder _sb;

private long _lastValue;

// Called by SQL Server at the start of a new aggregation

public void Init()

{

// Start of the range is 1 (arbitrarily)

_lastValue = 1L;

// A string builder holds the aggregated output

_sb = new StringBuilder(2048);

}

// Called by SQL Server to add a new value to the aggregate

public void Accumulate(long Value)

{

// If the current value is not the last value seen + 1

// the current value represents the end of a gap

if ((Value != this._lastValue + 1))

{

// Add a gap to the output

// Format GapStart1-GapEnd1;GapStart2-GapEnd2;...

this._sb.Append(this._lastValue);

this._sb.Append(RANGE_CHAR);

this._sb.Append(Value);

this._sb.Append(TERM_CHAR);

this._lastValue = Value;

// Check for out-of-sequence

if (Value < this._lastValue)

{

throw new Exception("Value received out of sequence");

}

// The current value becomes the last value

this._lastValue = Value;

}

// Called by SQL Server to merge partial aggregations

public void Merge(Gaps Group)

{

// Add the output from the partial aggregate

// to this aggregate

this._sb.Append(Group.Terminate());

}

// Called by SQL Server when all values have been aggregated

// Returns the result of the aggregate

public SqlString Terminate()

{

return this._sb.ToString();

}

// Interface used by SQL Server to serialize and

// de-serialize the state of the aggregate

#region IBinarySerialize Members

// Called to write the state of the aggregate to SQL Server-provided storage

void IBinarySerialize.Write(BinaryWriter w)

{

// Save the last value and the

// current aggregate result

w.Write(this._lastValue);

w.Write(this._sb.ToString());

}

// Call to read the state of the aggregate from SQL Server-provided storage

void IBinarySerialize.Read(BinaryReader r)

{

// Read internal state

this._lastValue = r.ReadInt64();

this._sb = new StringBuilder(r.ReadString());

}

#endregion

}

Paul

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Paul White SSC Guru Points: 150467 More actions · Answer 12

Jeff Moden (5/6/2010)
Yep... I remember the "other" triangular join. You made it to be very fast but it still ended up doing the same number of reads. This one seems to avoid that for some reason.

The optimiser contains a rule to transform a MAX or MIN to a single-row index seek plus TOP operator:

Look at it this way. Say we have an index on a column 'n' that contains the numbers 1...999 and the query is SELECT MAX(n) WHERE n < 500.

You could seek to find all the rows < 500 and perform the MAX on those 499 rows - that would be a 'true' triangular join, touching N-1 rows for each iteration.

The optimisation is to seek the index (backward in this case) to find the first index entry before the position where the value 500 would be.

Physically, this results in a single binary search down the upper levels of the index B+ tree to find the page that would contain (the first value before) 500, followed by a single binary search on that single index page to find the first index key < 500. Very fast, and very efficient.

Paul

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Jeff Moden SSC Guru Points: 1004363 More actions · Answer 13

Paul White NZ (5/6/2010)
Ok, here's the quick 'n' dirty CLR aggregate:

Ooooohhhhh mmmmyyyyy ggggooooodddd... someone that actually knows what "//" is for.

Very well done Mr. White.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1004363 More actions · Answer 14

Paul White NZ (5/6/2010)
Jeff Moden (5/6/2010)
Yep... I remember the "other" triangular join. You made it to be very fast but it still ended up doing the same number of reads. This one seems to avoid that for some reason.
The optimiser contains a rule to transform a MAX or MIN to a single-row index seek plus TOP operator:
Look at it this way. Say we have an index on a column 'n' that contains the numbers 1...999 and the query is SELECT MAX(n) WHERE n < 500.
You could seek to find all the rows < 500 and perform the MAX on those 499 rows - that would be a 'true' triangular join, touching N-1 rows for each iteration.
The optimisation is to seek the index (backward in this case) to find the first index entry before the position where the value 500 would be.
Physically, this results in a single binary search down the upper levels of the index B+ tree to find the page that would contain (the first value before) 500, followed by a single binary search on that single index page to find the first index key < 500. Very fast, and very efficient.
Paul

I'm not sure where you found the time to study that but, like Seth said, I learn something new every day. I didn't know why it worked well... I just knew it did. Thanks for the education, Paul.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 15

Jeff Moden (5/6/2010)
Paul White NZ (5/6/2010)
Ok, here's the quick 'n' dirty CLR aggregate:
Ooooohhhhh mmmmyyyyy ggggooooodddd... someone that actually knows what "//" is for.
Very well done Mr. White.

Thanks - but it was rushed - I normally use /// with the self-documenting tags like <summary> etc.

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi