Click here to monitor SSC

Software Engineer - Red Gate Software

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

58 Responses to “SQL Puzzle 8”

  1. Phil Factor says:

    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

  2. Lionel says:

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

  3. Lionel says:

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

  4. Eric W. Bachtal says:

    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!

  5. Marien says:

    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.

  6. Lionel says:

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

  7. Michael.Kriegner says:

    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.

  8. glenfitch says:

    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

  9. Joshua says:

    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)

  10. Lionel says:

    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

  11. Eric W. Bachtal says:

    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!

  12. Robyn Page says:

    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

  13. Eric W. Bachtal says:

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

  14. Lionel says:

    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

  15. Lionel says:

    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

  16. Phil Factor says:

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

  17. Lionel says:

    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

  18. Phil Factor says:

    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

  19. Lee says:

    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

  20. Phil Factor says:

    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?

  21. duhnbr says:

    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” ?

  22. Lionel says:

    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

  23. puzsol says:

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

  24. duhnbr says:

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

Leave a Reply