Yesterday I demonstrated a set based technique allowing you to build a Hex string from a comma separated value list. The list would allow you to select items from 1 to 63, and build a hex string, representing all of the selections. If you were to represent the data in a binary form a string of number 1, 2, 3, 4, would be represented as the number 15 (1+2+4=8) decimal, 1111 binary, or 0x0A Hexidecimal. We are limited to 63 choices because we generate the Hex value by converting a BIGINT into a Varbinary. A BIGINT, because it is singed, can only have 63 usable bit positions, thus the limitation.
I wanted the ability to store any number of values in a single varbinay value. Because you can concatenate varbinary values, I came up with the idea that I could break the selection down into segments, convert that segment into an Integer, and then into a varbinary value. I chose to make work in ranges of 30, so I could do an INT for each segment.
The following figure shows how I break up the large sequence of numbers into binary values. I only need an Int 32 to store on block of data. Since this is a bit mask, I can calculate each block separately, and then concatenate the results as if I computed each one independently.
1 2 3 4 5 6
123456789012345678901234567890123456789012345678901234567890
| Block 1 | BLOCK 2 |
So,
I start with converting the delimited list of selections into a table using the CTE “List”. See the editorial last Wednesday for more info if it doesn’t make sense.
Next, I need to break up the work I am going to do into the blocks demonstrated above. I need to find the range of each block, identify the numbers falling within that range, and calculate the binary integer for each of the bits within that range. So, the binary integer patter repeats for each block. 1 and 31 have the same integer 1. 2 and 32 have 2. 3 and 33 have 4. F and 24 have 8, continuing by power of 2 until the block ends at 30.
First I use a CTE I call Blocks. Blocks uses my Sequence table to figure out where each block starts and ends, and the order these blocks (My code calls the order Place), should be concatenated.
Output would look like
MinValue MaxValue Place
1 30 1
31 60 2
61 90 3
I don’t know what choices will be passed in for saving. So, I am going to calculate a sequence for numbers. Again I use the Sequence table in a CTE called HexNumbers. It starts at 1 (the lowest selected value that we can convert, and the max number of selections) I end up with a table that starts at 1, has the Places value, and an integer with the power of 2 from 1 to 30 for each place, aligned with the value sent by the user.
Next I use a CTE to join the possible options to the selections made by the user, resulting in a place and the binary number for that binary place represented by the user selection.
The CTE BlockListTotals groups all the BlockDetail data into a single record per place.
The CTE BlockTotals takes the results from BlockListTotals, and adds the missing places with the value 0, because there were no selections in that black. I now have a series of blocks with an integer containing the sum of all the integers representing the binary bit that would be turned on with the users selection per block. I can now select all the places in reverse order, convert the integer to VarBinary, concatenate the result into a single variable for each place. I have now calculated on hex representation of a large set of selections. You can extent the number of places to allow for a much large bitmask. There does appear to be a performance hit as you increase the size. I had to tune this query a lot to get it under a second. Originally it was 10 seconds.
Give it a spin and see what you think. Clearly, the other half of this brain teaser is still outstanding. How do you get the data out of this bitmask back into a table of selections, or a delimited list of selections?
Cheers,
Ben
TSQL
DECLARE @PowerOfTwo FLOAT = 2
DECLARE @Selections VARCHAR(4000) = '1, 2, 13, 14, 15, 16, 17, 20, 32, 64, 98, 246, 248, 249'
DECLARE @MaxSelection INT = 256
DECLARE @HexValue VARBINARY(256) = 0x
DECLARE @Pages INT = 256/30 + 1
;WITH List
as
(
SELECT Item
,1 AS IsItem
FROM dbo.Split(@Selections, ', ')
)
,Blocks
AS
(
SELECT Number * 30 - 29 as MinValue
,Number * 30 AS MaxValue
,Number as Place
FROM Sequence
WHERE Number BETWEEN 1 AND @Pages
)
--SELECT * FROM Blocks
,HexNumbers
AS
(
SELECT
CONVERT(VARCHAR(10), s.Number) as Item
,s.Number - h.MinValue + 1 AS HexBit
,h.Place
,IntValue = POWER(@PowerOfTwo, CONVERT(FLOAT, s.Number - h.MinValue))
FROM Sequence s
JOIN Blocks h ON s.Number BETWEEN h.MinValue and h.MaxValue
WHERE s.Number <= @MaxSelection
)
--SELECT * FROM HexNumbers
,BlockDetail
AS
(
SELECT
h.Place
,h.IntValue
FROM HexNumbers h
JOIN List L on h.Item = l.Item
)
--SELECT * FROM BlockDetail
,BlockListTotals
AS
(
SELECT
h.Place ,SUM(h.IntValue) as IntPlaceTotal
FROM BlockDetail h
GROUP BY h.Place
)-- SELECT * FROM BlockListTotals
,BlockTotals
AS
(
SELECT Place, IntPlaceTotal
FROM BlockListTotals UNION ALL
SELECT b.place, 0
FROM Blocks b
LEFT JOIN BlockListTotals blt on b.Place = blt.place
WHERE blt.place IS NULL
)
--SELECT * FROM BlockTotals
--ORDER BY Place
SELECT @HexValue += CONVERT(VARBINARY(8), Convert(int, IntPlaceTotal))
FROM BlockTotals
ORDER BY Place DESC
SELECT @HexValue as HexBitMask