# SQL Puzzle 8

Published 27 November 2007 1:12 pm
/*

So I thought it was just about time for another puzzle but I was having great difficulty in coming up with a new challenge. Luckily Andras has posted a blog entry about how the

POWERSUM function has been removed from SQL Server.

http://www.simple-talk.com/community/blogs/andras/archive/2007/11/22/40021.aspx

This puzzle is a nice simple one and is to write a single select statement that will return the same results as POWERSUM when run on the supplied table variable. The input values will be between 0 and 127 but it would be nice to see solutions that will scale to beyond that. Andras has posted an explanation of what POWERSUM does but if it is still unclear exactly what it does (The output seems to be the reverse of what I expect it to be!) add a comment to the blog and I will add some clarification. Have fun!

Lionel

*/

SET NOCOUNT ON

DECLARE @Data TABLE

(

Col INT

)

INSERT INTO @Data(col)

SELECT 1

INSERT INTO @Data(col)

SELECT 1

INSERT INTO @Data(col)

SELECT 2

INSERT INTO @Data(col)

SELECT 98

INSERT INTO @Data(col)

SELECT 31

INSERT INTO @Data(col)

SELECT 32

INSERT INTO @Data(col)

SELECT 32

INSERT INTO @Data(col)

SELECT 63

INSERT INTO @Data(col)

SELECT 17

INSERT INTO @Data(col)

SELECT 100

INSERT INTO @Data(col)

SELECT 56

INSERT INTO @Data(col)

SELECT 24

INSERT INTO @Data(col)

SELECT 17

INSERT INTO @Data(col)

SELECT 2

INSERT INTO @Data(col)

SELECT 127

INSERT INTO @Data(col)

SELECT 76

INSERT INTO @Data(col)

SELECT 84

INSERT INTO @Data(col)

SELECT 99

INSERT INTO @Data(col)

SELECT 12

INSERT INTO @Data(col)

SELECT 103

SET NOCOUNT OFF

– This should return the same as

– SELECT POWERSUM(col) FROM @Data

– which is 0x0610028101000081001010009C000080

So I thought it was just about time for another puzzle but I was having great difficulty in coming up with a new challenge. Luckily Andras has posted a blog entry about how the

POWERSUM function has been removed from SQL Server.

http://www.simple-talk.com/community/blogs/andras/archive/2007/11/22/40021.aspx

This puzzle is a nice simple one and is to write a single select statement that will return the same results as POWERSUM when run on the supplied table variable. The input values will be between 0 and 127 but it would be nice to see solutions that will scale to beyond that. Andras has posted an explanation of what POWERSUM does but if it is still unclear exactly what it does (The output seems to be the reverse of what I expect it to be!) add a comment to the blog and I will add some clarification. Have fun!

Lionel

*/

SET NOCOUNT ON

DECLARE @Data TABLE

(

Col INT

)

INSERT INTO @Data(col)

SELECT 1

INSERT INTO @Data(col)

SELECT 1

INSERT INTO @Data(col)

SELECT 2

INSERT INTO @Data(col)

SELECT 98

INSERT INTO @Data(col)

SELECT 31

INSERT INTO @Data(col)

SELECT 32

INSERT INTO @Data(col)

SELECT 32

INSERT INTO @Data(col)

SELECT 63

INSERT INTO @Data(col)

SELECT 17

INSERT INTO @Data(col)

SELECT 100

INSERT INTO @Data(col)

SELECT 56

INSERT INTO @Data(col)

SELECT 24

INSERT INTO @Data(col)

SELECT 17

INSERT INTO @Data(col)

SELECT 2

INSERT INTO @Data(col)

SELECT 127

INSERT INTO @Data(col)

SELECT 76

INSERT INTO @Data(col)

SELECT 84

INSERT INTO @Data(col)

SELECT 99

INSERT INTO @Data(col)

SELECT 12

INSERT INTO @Data(col)

SELECT 103

SET NOCOUNT OFF

– This should return the same as

– SELECT POWERSUM(col) FROM @Data

– which is 0x0610028101000081001010009C000080

Well, just to start the ball rolling, here is my simple approach.

I couldn’t bring myself to use COALECE to initialise the bitmap so I’ve added a second select. You’ll just have to imagine the horrible COALESCE code.

This approach will scale to any size of bitmap just by changing the size of @Bitmap.

This approach might need some refinement to do exactly what powersum does!

DECLARE @bitmap VARBINARY(16)

SELECT @bitmap = 0×0000000000000000000000000000000000000000000000000000000000000000000000000000

SELECT @bitmap = CONVERT(VARBINARY,STUFF(@bitmap, ( col / 8 ) + 1, 1,CAST(CAST(COALESCE(SUBSTRING(@Bitmap, ( col / 8 ) + 1, 1), 0×00) AS integer)| POWER(2, col % 8) AS VARBINARY(1))))

FROM @data

SELECT @bitmap,

Powersum(col)

FROM @data

Very nice Phil but how about doing it in a single select statement next time

I should add that it is definitely possible to do it in one select statement

Not sure it qualifies as a “single select statement”, but here’s a solution I put together using some recursive CTEs:

http://ewbi.blogs.com/develops/2007/11/sql-server-powe.html

Thanks for the interesting challenge!

SELECT Cast(Sum(DISTINCT Power(2,col)) as varbinary)

FROM @Data

Should do it, however the number of bytes returned is different because of the default cast to varbinary.

Marien. Unfortunately, you get a …

Msg 232, Level 16, State 3, Line 51

Arithmetic overflow error for type int, value = 316912650057057350000000000000.000000.

This is because Power(2, col) only works when col is between 0 and 30. Since I said that col is between 0 and 127 that doesn’t quite work

How about this one:

DECLARE @x VARBINARY( MAX )

SET @x = 0x;

WITH Werte( ByteWert, Position )

AS

(

SELECT DISTINCT

col % 8,

col / 8

FROM @Data

UNION ALL

SELECT NULL, 1 WHERE 1 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 2 WHERE 2 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 3 WHERE 3 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 4 WHERE 4 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 5 WHERE 5 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 6 WHERE 6 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 7 WHERE 7 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 8 WHERE 8 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 9 WHERE 9 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 10 WHERE 10 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 11 WHERE 11 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 12 WHERE 12 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 13 WHERE 13 < ( SELECT MAX( Col / 8 ) FROM @Data ) UNION ALL

SELECT NULL, 14 WHERE 14 < ( SELECT MAX( Col / 8 ) FROM @Data )

)

SELECT

@x = @x + CAST( ISNULL( SUM( POWER( 2, ByteWert ) ), 0×00 ) AS VARBINARY( 1 ) )

FROM Werte

GROUP BY Position

ORDER BY Position

PRINT @x

You can easy scale beyond 127.

now, you wouldn’t by any chance be giving us a puzzle that can only be solved in SQL Server 2005/7 would you now? . Michael’s solution is great, awesome, but it has sixteen select statements to my reckoning

Good fun

;

WITH PowerSumList AS (

SELECT

Col

FROM

@Data

GROUP BY

Col

)

, RdxValues AS (

SELECT

Col

, Power(2,Col%8) as rdx

, Col/8 AS Pos

FROM

PowerSumList

)

, PowerSumParts AS (

SELECT

row_number()OVER(ORDER BY Pos)-1 PosByRow

, Pos

, CAST(SUM(rdx)AS Varbinary(1)) AS vb

FROM

RdxValues

GROUP BY

Pos

)

, PowerSum(PosByRow, pos, vb) AS (

SELECT

PowerSumParts.PosByRow

, PowerSumParts.pos

, CAST(PowerSumParts.vb AS varbinary)

FROM

PowerSumParts

WHERE

posbyrow = 0

UNION ALL

SELECT

PowerSumParts.PosByRow

, PowerSumParts.pos

, CAST(PowerSum.vb

+ CAST(REPLICATE(CHAR(0),PowerSumParts.pos – PowerSumParts_Prev.pos-1) as varbinary)

+ PowerSumParts.vb AS varbinary)

FROM

PowerSumParts

INNER JOIN

PowerSum

ON PowerSumParts.posbyrow = PowerSum.posbyrow+1

INNER JOIN

PowerSumParts AS PowerSumParts_Prev

ON PowerSumParts_Prev.posbyrow = PowerSum.posbyrow

)

SELECT vb AS PowerSum

FROM

PowerSum

WHERE

PosByRow = (SELECT MAX(PosByRow) FROM PowerSum)

glenfitch: I have a solution that works in SQL 2000 and 2005. In order to make it scale beyond 127 you have to cut and past a bit of code. It is totally possible to produce a solution the works on 2000.

To everyone else for further challenge try creating a solution that works on SQL 2000 and doesn’t use a variable .

Lionel

SQL Server 2000 and a little cut-and-paste. Okay. I’ve updated my solution here:

http://ewbi.blogs.com/develops/2007/11/sql-server-powe.html

No CTEs this time. Thanks again for the interesting challenge!

I think Eric has it sorted. The only criticism I have is that he has eighteen select statements in it. With a little bit of tweaking, I reckon that this is the solution. Eric v3

select

cast(

left(

char(sum(distinct case when col/8=0 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=1 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=2 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=3 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=4 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=5 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=6 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=7 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=8 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=9 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=10 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=11 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=12 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=13 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=14 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=15 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=16 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=17 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=18 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=19 then power(2, Col%8) else 0 end))

+ char(sum(distinct case when col/8=20 then power(2, Col%8) else 0 end))

,max(col/8)+1)as varbinary),

Powersum(col) from @data

–powersum is there just to check that the answers are the same, by the way

Oops, you’re right. I did the first line and copied for the remainder without thinking to pull the select for a case. Thanks!

Eric W. Bachtal: Very nice idea full marks for a solution that works on 2000

Now Robyn’s solution is starting to look very similar to mine I will leave it a little longer and then I will post my solution up unless people think I should do it now.

Lionel

Well I guess it is time to post up my solution. As you can see it is very similar to Robyn’s but with a little bit of a twist so I could cut down on the number of sums. Hope you guys found this fun and sorry for the strange formatting. I was trying to sop it wrapping .

– This basically trims of the trailing 00s

SELECT COALESCE(CONVERT(VARBINARY,

SUBSTRING(result, 1,

LEN(RTRIM(REPLACE(result, CHAR(0) , ‘ ‘))))), 0x)

FROM

(

– This is what calculates the powersum

SELECT CONVERT(VARBINARY, REVERSE(

CONVERT(VARBINARY(7),

SUM(DISTINCT (

CASE

WHEN col < 168 AND col >= 112

THEN CONVERT(BIGINT, POWER(2.0, col – 112))

ELSE 0

END)

))

+

CONVERT(VARBINARY(7),

SUM(DISTINCT (

CASE

WHEN col < 112 AND col >= 56

THEN CONVERT(BIGINT, POWER(2.0, col – 56))

ELSE 0

END)

))

+

CONVERT(VARBINARY(7),

SUM(DISTINCT (

CASE

WHEN col < 56

THEN CONVERT(BIGINT, POWER(2.0, col))

ELSE 0

END)

))

)) AS result

FROM @data

) PowerSum

Hmm. Two select statements there, Lionel. Eric v3 wins, I think.

Well I don’t really need the outer select but I didn’t really mean you couldn’t use derived tables.

SELECT COALESCE(CONVERT(VARBINARY, LEFT(REVERSE(

CONVERT(VARBINARY(7),

SUM(DISTINCT (

CASE

WHEN col < 168 AND col >= 112

THEN CONVERT(BIGINT, POWER(2.0, col – 112))

ELSE 0

END)

))

+

CONVERT(VARBINARY(7),

SUM(DISTINCT (

CASE

WHEN col < 112 AND col >= 56

THEN CONVERT(BIGINT, POWER(2.0, col – 56))

ELSE 0

END)

))

+

CONVERT(VARBINARY(7),

SUM(DISTINCT (

CASE

WHEN col < 56

THEN CONVERT(BIGINT, POWER(2.0, col))

ELSE 0

END)

))

), (MAX(col) / 8)+1)),0x) AS result

FROM @data

well, here is a tidied version of my attempt. Two Selects I grant you but neat eh?

DECLARE @bitmap varbinary(60)

SELECT

@bitmap= cast (STUFF(

coalesce(@bitmap,replicate(char(0),60)),

( col / 8 ) + 1,

1,

cast(ascii(SUBSTRING(

coalesce(@bitmap,replicate(char(0),60)),

(col / 8 ) + 1,

1))

| POWER(2, col % 8)as varbinary(1)))as varbinary)

FROM @data

SELECT cast(left(@bitmap,max(col/8)+1) as varbinary),

Powersum(col)

FROM @data

I freely concede that Phil’s solution is more elegant than mine, and mine only works in SQL Server 2005. I like Phil’s STUFF technology.

DECLARE @bitmap VARBINARY (16)

SELECT @bitmap = ISNULL (@bitmap + byte, byte)

FROM (SELECT byteseq

, CONVERT (BINARY (1), CONVERT (TINYINT, 0) | CONVERT (TINYINT, int1)) byte

FROM (SELECT (bitnum / 8) + 1 byteseq

, SUM (POWER (2, bitpos) * val) int1

FROM (SELECT grid.bitnum

, grid.bitnum % 8 bitpos

, ISNULL (SIGN (bits.col), grid.val) val

FROM (SELECT ROW_NUMBER () OVER (ORDER BY val) – 1 bitnum

, zeros.val

FROM (SELECT TOP 128 CONVERT (INT, 0) val

FROM syscolumns) zeros) grid

LEFT JOIN (SELECT DISTINCT col

FROM @data) bits ON grid.bitnum = bits.col) allbits

GROUP BY (bitnum / 8) + 1) bytes) map

ORDER BY byteseq

SELECT @bitmap

Thanks, Lee. Until I discovered Lionel’s puzzle, I had know idea that one could use STUFF this way, for setting bit patterns in VARBINARYs. TSQL for writing graphics anyone?

Can someone please enlighten me on the “Bit 56 Boundary” ? In my usage of bitmaps I have always stopped at bit 56, due to inconsistent results for bits greater than 56. I’m comforted to see Lionel has accommodated this behavior, but could someone elaborate on the intricacies surrounding the “Bit 56 Boundary” ?

Well the problem is this case is that I am trying to put the bit field into an integer. The biginteger is stored in twos complement form.

http://en.wikipedia.org/wiki/Two's_complement

This means that the top bit controls if the number is negative (it is a bit subtle what exactly is going on but wikepedia explains it). I am using the SUM function in my solution to combine the bit fields. The problem happens when I set the top bit of the bigint. This sets the number to be negative and since the number is stored in twos complement form adding negative numbers does not just combine the bits like it does with positive numbers. This means that I can not use the top bit.

So then that explains why I can only used 63 bits of the integer but why then have I limited it to 56 bits. Well you notice that after the sum I am converting the big integers into VARBINARY(7). The full length of a big integer is 8 bytes but as I have explained already I can not use the top bit. Since the convert function need a whole number of bytes the next smallest number of bytes that I can get from the bigint is 7. Since we have 8 bits in a byte 8*7 = 56 bits which means we can only use 56 bits of the bigint.

I hope that explains what is going on but just post another comment if you want me to clarify anything as I am notoriously bad at explaining things :/

Lionel

Well, I can’t add to the SQL side of it (I was away on holidays, but I still wouldn’t have dreamed up Eric v3)… but personally I figure this is a perfect case for the use of the CLR to create a SQL Server Aggregate… That way if you miss the undocumented and obscure function, you can replace it with a much simpler call (rather than messing up your select statement with 18 or more lines of SQL)…

For those who are interested, here is my first pass at creating a CLR version:

(Please see the Microsoft Documentation on creating a Database Project in Visual Studio, deploying, turning on CLR etc):

[Serializable]

[Microsoft.SqlServer.Server.SqlUserDefinedAggregate(Format.UserDefined,IsInvariantToOrder=true,IsInvariantToDuplicates = true, IsInvariantToNulls = true, IsNullIfEmpty = true, MaxByteSize=8000)]

public class CLRPowersum : IBinarySerialize

{

private byte[] dBytes;

public CLRPowersum()

{

Init();

}

public void Init()

{

dBytes = new byte[1];

}

public void Accumulate(SqlInt32 value)

{

Int32 idx = value.Value >> 3;

byte bit = (byte) (0×1 << (value.Value & 0×07));

if (dBytes.Length <= idx)

{

byte[] tmp = dBytes;

dBytes = new byte[idx+1];

tmp.CopyTo(dBytes, 0);

}

dBytes[idx] |= bit;

}

public void Merge(CLRPowersum value)
{

{

if (dBytes.Length < value.dBytes.Length)

{

byte[] tmp = dBytes;

dBytes = new byte[value.dBytes.Length];

tmp.CopyTo(dBytes, 0);

}

for (int i = 0; i

dBytes[i] |= value.dBytes[i];

}

}

public SqlBinary Terminate()

{

return new SqlBinary(dBytes);

}

void IBinarySerialize.Read(System.IO.BinaryReader r)

{

Int32 len = r.ReadInt32();

dBytes = r.ReadBytes(len);

}

void IBinarySerialize.Write(System.IO.BinaryWriter w)

{

w.Write(dBytes.Length);

w.Write(dBytes);

}

Then the SQL becomes:

SELECT dbo.CLRPowersum(col)

I know which one I would use… (ok, so I’m answering the question of how to replace the missing function, rather than the one asked, but hey, I figured it was sort of on-topic… and SQL2008 has CLR integration… previous versions have… Powersum!).

Lionel, thank you for taking the time to respond to my rather elementary question. Your answer was very clear and understandable.

PingBack from http://rolldice.wordpress.com/2010/01/24/fun-with-sql-games-painting-puzzles/

PingBack from http://360.unlockiphone30.net/post/207214/

PingBack from http://427.eumreborn.com/post/128560/

PingBack from http://380.eumreborn.com/post/127610/

PingBack from http://5.computeronlinebingo.com/post/30109/

PingBack from http://10.luna-atra.net/post/100213/

PingBack from http://75.unlockiphone30.net/post/201509/

PingBack from http://491.codebluehacks.org/post/89823/

PingBack from http://117.animejin.com/post/12344/

PingBack from http://416.dlmreza.net/post/138334/

PingBack from http://468.unlockiphone30.net/post/209372/

PingBack from http://405.unlockiphone30.net/post/208103/

PingBack from http://208.cmanager.org/post/94167/

PingBack from http://111.zapstreaming.com/post/172226/

PingBack from http://274.tgrconversions.com/post/65494/

PingBack from http://165.cmanager.org/post/93314/

PingBack from http://369.rkwrh.com/post/57386/

PingBack from http://434.zapstreaming.com/post/178694/

PingBack from http://259.renters.ws/post/235198/

PingBack from http://364.jeepsunlimted.com/post/157285/

PingBack from http://496.unlockiphone30.net/post/209929/

PingBack from http://24.luna-atra.net/post/100483/

PingBack from http://58.defutbolazo.com/post/191178/

PingBack from http://471.luna-atra.net/post/109426/

PingBack from http://363.an74.com/post/217266/

PingBack from http://347.codebluehacks.org/

PingBack from http://485.defutbolazo.com/post/199720/

PingBack from http://456.1fh.org/post/149138/

PingBack from http://453.mfbattle.com/post/79069/

PingBack from http://157.dlmreza.net/post/133153/

PingBack from http://227.eumreborn.com/post/124545/

PingBack from http://276.tgrconversions.com/post/65534/

PingBack from http://9.binggreen.com/post/20185/

PingBack from http://262.jeepsunlimted.com/post/155251/