14

Part of my workload uses a CLR function that implements the spooky hash algorithm to compare rows to see if any column values have changed. The CLR function takes a binary string as an input, so I need a fast way to convert rows to a binary string. I expect to hash around 10 billion rows during the full workload so I'd like this code to be as fast as possible.

I have about 300 tables with different schemas. For the purposes of this question please assume a simple table structure of 32 nullable INT columns. I've provided sample data as well as a way to benchmark results at the bottom of this question.

Rows must be converted to the same binary string if all column values are the same. Rows must be converted to different binary strings if any column value is different. For example, code as simple as the following will not work:

CAST(COL1 AS BINARY(4)) + CAST(COL2 AS BINARY(4)) + ..

It does not handle NULLs correctly. If COL1 is NULL for row 1 and COL2 is NULL for row 2 then both rows will be converted to a NULL string. I believe that correct handling of NULLs is the hardest part of converting the entire row correctly. All allowed values for the INT columns are possible.

To preempt some questions:

  • If it matters, a significant majority of the time (90%+) the columns won't be NULL.
  • I have to use the CLR.
  • I have to hash this many rows. I cannot persist the hashes.
  • I believe that I cannot use batch mode for the conversion due to the presence of the CLR function.

What is the fastest way to convert 32 nullable INT columns to a BINARY(X) or VARBINARY(X) string?

Sample data and code as promised:

-- create sample data
DROP TABLE IF EXISTS dbo.TABLE_OF_32_INTS;

CREATE TABLE dbo.TABLE_OF_32_INTS (
    COL1 INT NULL,
    COL2 INT NULL,
    COL3 INT NULL,
    COL4 INT NULL,
    COL5 INT NULL,
    COL6 INT NULL,
    COL7 INT NULL,
    COL8 INT NULL,
    COL9 INT NULL,
    COL10 INT NULL,
    COL11 INT NULL,
    COL12 INT NULL,
    COL13 INT NULL,
    COL14 INT NULL,
    COL15 INT NULL,
    COL16 INT NULL,
    COL17 INT NULL,
    COL18 INT NULL,
    COL19 INT NULL,
    COL20 INT NULL,
    COL21 INT NULL,
    COL22 INT NULL,
    COL23 INT NULL,
    COL24 INT NULL,
    COL25 INT NULL,
    COL26 INT NULL,
    COL27 INT NULL,
    COL28 INT NULL,
    COL29 INT NULL,
    COL30 INT NULL,
    COL31 INT NULL,
    COL32 INT NULL
);

INSERT INTO dbo.TABLE_OF_32_INTS WITH (TABLOCK)
SELECT 0, 123, 12345, 1234567, 123456789
, 0, 123, 12345, 1234567, 123456789
, 0, 123, 12345, 1234567, 123456789
, 0, 123, 12345, 1234567, 123456789
, 0, 123, 12345, 1234567, 123456789
, 0, 123, 12345, 1234567, 123456789
, NULL, -876545321
FROM
(
    SELECT TOP (1000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) q
OPTION (MAXDOP 1);


GO


-- procedure to test performance
CREATE OR ALTER PROCEDURE #p AS 
BEGIN

SET NOCOUNT ON;

DECLARE
@counter INT = 0,
@dummy VARBINARY(8000);

WHILE @counter < 10
BEGIN
    SELECT @dummy = -- this code is clearly incomplete as it does not handle NULLs
        CAST(COL1 AS BINARY(4)) + 
        CAST(COL2 AS BINARY(4)) + 
        CAST(COL3 AS BINARY(4)) + 
        CAST(COL4 AS BINARY(4)) + 
        CAST(COL5 AS BINARY(4)) + 
        CAST(COL6 AS BINARY(4)) + 
        CAST(COL7 AS BINARY(4)) + 
        CAST(COL8 AS BINARY(4)) + 
        CAST(COL9 AS BINARY(4)) + 
        CAST(COL10 AS BINARY(4)) + 
        CAST(COL11 AS BINARY(4)) + 
        CAST(COL12 AS BINARY(4)) + 
        CAST(COL13 AS BINARY(4)) + 
        CAST(COL14 AS BINARY(4)) + 
        CAST(COL15 AS BINARY(4)) + 
        CAST(COL16 AS BINARY(4)) + 
        CAST(COL17 AS BINARY(4)) + 
        CAST(COL18 AS BINARY(4)) + 
        CAST(COL19 AS BINARY(4)) + 
        CAST(COL20 AS BINARY(4)) + 
        CAST(COL21 AS BINARY(4)) + 
        CAST(COL22 AS BINARY(4)) + 
        CAST(COL23 AS BINARY(4)) + 
        CAST(COL24 AS BINARY(4)) + 
        CAST(COL25 AS BINARY(4)) + 
        CAST(COL26 AS BINARY(4)) + 
        CAST(COL27 AS BINARY(4)) + 
        CAST(COL28 AS BINARY(4)) + 
        CAST(COL29 AS BINARY(4)) + 
        CAST(COL30 AS BINARY(4)) + 
        CAST(COL31 AS BINARY(4)) + 
        CAST(COL32 AS BINARY(4))
    FROM dbo.TABLE_OF_32_INTS
    OPTION (MAXDOP 1);

    SET @counter = @counter + 1;
END;

SELECT cpu_time
FROM sys.dm_exec_requests
WHERE session_id = @@SPID;

END;

GO

-- run procedure
EXEC #p;

(I will still be using the spooky hash on this binary result. The workload uses hash joins and the hashed value is used for one of the hash builds. I don't want a long binary value in the hash build because it requires too much memory.)

6

What about using BINARY(5) and converting NULLs to something out of range for INTs:

SELECT @dummy =
    ISNULL(CAST(COL1  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL2  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL3  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL4  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL5  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL6  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL7  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL8  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL9  AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL10 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL11 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL12 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL13 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL14 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL15 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL16 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL17 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL18 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL19 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL20 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL21 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL22 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL23 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL24 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL25 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL26 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL27 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL28 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL29 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL30 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL31 AS BINARY(5)), 0x0100000000) + 
    ISNULL(CAST(COL32 AS BINARY(5)), 0x0100000000)
FROM dbo.TABLE_OF_32_INTS
OPTION (MAXDOP 1);
11
+250

On my machine (SQL Server 2017) the following C# SQLCLR function runs about 30% faster than the binary(5) idea, 35% faster than CONCAT_WS, and in half the time of the self-answer.

It requires UNSAFE permission and uses pointers. The implementation is very specifically tied to the test data.

For testing purposes, the easiest way to get this unsafe assembly working is to set the database to TRUSTWORTHY and disable the clr strict security configuration option if necessary.

Compiled code

For convenience the CREATE ASSEMBLY compiled bits are at https://gist.github.com/SQLKiwi/72d01b661c74485900e7ebcfdc63ab8e

T-SQL Function Stub

CREATE FUNCTION dbo.NullableIntsToBinary
(
    @Col01 int, @Col02 int, @Col03 int, @Col04 int, @Col05 int, @Col06 int, @Col07 int, @Col08 int, 
    @Col09 int, @Col10 int, @Col11 int, @Col12 int, @Col13 int, @Col14 int, @Col15 int, @Col16 int, 
    @Col17 int, @Col18 int, @Col19 int, @Col20 int, @Col21 int, @Col22 int, @Col23 int, @Col24 int, 
    @Col25 int, @Col26 int, @Col27 int, @Col28 int, @Col29 int, @Col30 int, @Col31 int, @Col32 int
)
RETURNS binary(132) 
WITH EXECUTE AS CALLER
AS EXTERNAL NAME Obbish.UserDefinedFunctions.NullableIntsToBinary;

Source code

The C# source is at https://gist.github.com/SQLKiwi/64f320fe7fd802a68a3a644aa8b8af9f

If you compile this for yourself, you must use a Class Library (.dll) as the target project type and check the Allow Unsafe Code build option.

Combined solution

Since you ultimately want to compute the SpookyHash of the binary data returned above, you can call SpookyHash within the CLR function and return the 16-byte hash.

An example implementation based on a table with a mixture of column data types is at https://gist.github.com/SQLKiwi/6f82582a4ad1920c372fac118ec82460. This includes an unsafe inlined version of the Spooky Hash algorithm derived from Jon Hanna's SpookilySharp and the original public domain C source code by Bob Jenkins.

7

An INT column has four bytes of allowed values which exactly matches the size of a BINARY(4). In other words, every possible value of a BINARY(4) is matched to a possible value of an INT column. So unless there's a value that isn't allowed in the INT column, there is no safe replacement for a NULL. Whether or not a column is NULL has to be encoded separately. It simply cannot fit within a BINARY(4).

One way to do this is with a NULL bitmap. Consider the following code:

CAST(       
    CASE WHEN COL1 IS NOT NULL THEN 0 ELSE 1 END | 
    CASE WHEN COL2 IS NOT NULL THEN 0 ELSE 2 END | 
    CASE WHEN COL3 IS NOT NULL THEN 0 ELSE 4 END | 
    CASE WHEN COL4 IS NOT NULL THEN 0 ELSE 8 END | 
    CASE WHEN COL5 IS NOT NULL THEN 0 ELSE 16 END | 
    CASE WHEN COL6 IS NOT NULL THEN 0 ELSE 32 END | 
    CASE WHEN COL7 IS NOT NULL THEN 0 ELSE 64 END | 
    CASE WHEN COL8 IS NOT NULL THEN 0 ELSE 128 END
AS BINARY(1))

Whether or not eight columns are NULL fits in a single byte. These expressions can be compared between rows to check that all of the same columns are NULL or not NULL. With that additional information it then becomes safe to replace a NULL column value with anything that isn't NULL. I found CAST(ISNULL(COL1, 0) AS BINARY(4)) to be the fastest, although other variations such as ISNULL(CAST(COL1 AS VARBINARY(4)), 0x) are possible.

It's hard to prove anything definitely, but I found the following details to be the fastest:

  • Using 0 for NOT NULL in the bitmap since I know most column values won't be NULL
  • Using bitwise or instead of addition for the bitmap
  • Checking if the column value is NULL as opposed to the converted binary value

On my machine the benchmark takes about 27.5 CPU seconds. Unfortunately, the NULL bitmap step takes about one third of that time. It would be nice if there was a faster way to do this.

Here's the full solution:

SELECT
    CAST(ISNULL(COL1, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL2, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL3, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL4, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL5, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL6, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL7, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL8, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL9, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL10, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL11, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL12, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL13, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL14, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL15, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL16, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL17, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL18, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL19, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL20, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL21, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL22, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL23, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL24, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL25, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL26, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL27, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL28, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL29, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL30, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL31, 0) AS BINARY(4)) + 
    CAST(ISNULL(COL32, 0) AS BINARY(4)) + 
    CAST(       
        CASE WHEN COL1 IS NOT NULL THEN 0 ELSE 1 END | 
        CASE WHEN COL2 IS NOT NULL THEN 0 ELSE 2 END | 
        CASE WHEN COL3 IS NOT NULL THEN 0 ELSE 4 END | 
        CASE WHEN COL4 IS NOT NULL THEN 0 ELSE 8 END | 
        CASE WHEN COL5 IS NOT NULL THEN 0 ELSE 16 END | 
        CASE WHEN COL6 IS NOT NULL THEN 0 ELSE 32 END | 
        CASE WHEN COL7 IS NOT NULL THEN 0 ELSE 64 END | 
        CASE WHEN COL8 IS NOT NULL THEN 0 ELSE 128 END
    AS BINARY(1)) + 
    CAST(   
        CASE WHEN COL9  IS NOT NULL THEN 0 ELSE 1 END | 
        CASE WHEN COL10 IS NOT NULL THEN 0 ELSE 2 END | 
        CASE WHEN COL11 IS NOT NULL THEN 0 ELSE 4 END | 
        CASE WHEN COL12 IS NOT NULL THEN 0 ELSE 8 END | 
        CASE WHEN COL13 IS NOT NULL THEN 0 ELSE 16 END | 
        CASE WHEN COL14 IS NOT NULL THEN 0 ELSE 32 END | 
        CASE WHEN COL15 IS NOT NULL THEN 0 ELSE 64 END | 
        CASE WHEN COL16 IS NOT NULL THEN 0 ELSE 128 END
    AS BINARY(1)) + 
    CAST(   
        CASE WHEN COL17 IS NOT NULL THEN 0 ELSE 1 END | 
        CASE WHEN COL18 IS NOT NULL THEN 0 ELSE 2 END | 
        CASE WHEN COL19 IS NOT NULL THEN 0 ELSE 4 END | 
        CASE WHEN COL20 IS NOT NULL THEN 0 ELSE 8 END | 
        CASE WHEN COL21 IS NOT NULL THEN 0 ELSE 16 END | 
        CASE WHEN COL22 IS NOT NULL THEN 0 ELSE 32 END | 
        CASE WHEN COL23 IS NOT NULL THEN 0 ELSE 64 END | 
        CASE WHEN COL24 IS NOT NULL THEN 0 ELSE 128 END
    AS BINARY(1)) + 
    CAST(   
        CASE WHEN COL25 IS NOT NULL THEN 0 ELSE 1 END | 
        CASE WHEN COL26 IS NOT NULL THEN 0 ELSE 2 END | 
        CASE WHEN COL27 IS NOT NULL THEN 0 ELSE 4 END | 
        CASE WHEN COL28 IS NOT NULL THEN 0 ELSE 8 END | 
        CASE WHEN COL29 IS NOT NULL THEN 0 ELSE 16 END | 
        CASE WHEN COL30 IS NOT NULL THEN 0 ELSE 32 END | 
        CASE WHEN COL31 IS NOT NULL THEN 0 ELSE 64 END | 
        CASE WHEN COL32 IS NOT NULL THEN 0 ELSE 128 END
    AS BINARY(1))
FROM dbo.TABLE_OF_32_INTS
OPTION (MAXDOP 1);
5

In my tests concat_ws was a bit faster (18 seconds) than your null bitmap solution (26 seconds). There will be more data to shuffle around so you might see some performance degradation elsewhere and if you want to mix this up with character columns you have to choose the delimiter wisely.

select @dummy = cast(concat_ws('|',
         isnull(cast(T.COL1  as varchar(11)), ''),
         isnull(cast(T.COL2  as varchar(11)), ''),
         isnull(cast(T.COL3  as varchar(11)), ''),
         isnull(cast(T.COL4  as varchar(11)), ''),
         isnull(cast(T.COL5  as varchar(11)), ''),
         isnull(cast(T.COL6  as varchar(11)), ''),
         isnull(cast(T.COL7  as varchar(11)), ''),
         isnull(cast(T.COL8  as varchar(11)), ''),
         isnull(cast(T.COL9  as varchar(11)), ''),
         isnull(cast(T.COL10 as varchar(11)), ''),
         isnull(cast(T.COL11 as varchar(11)), ''),
         isnull(cast(T.COL12 as varchar(11)), ''),
         isnull(cast(T.COL13 as varchar(11)), ''),
         isnull(cast(T.COL14 as varchar(11)), ''),
         isnull(cast(T.COL15 as varchar(11)), ''),
         isnull(cast(T.COL16 as varchar(11)), ''),
         isnull(cast(T.COL17 as varchar(11)), ''),
         isnull(cast(T.COL18 as varchar(11)), ''),
         isnull(cast(T.COL19 as varchar(11)), ''),
         isnull(cast(T.COL20 as varchar(11)), ''),
         isnull(cast(T.COL21 as varchar(11)), ''),
         isnull(cast(T.COL22 as varchar(11)), ''),
         isnull(cast(T.COL23 as varchar(11)), ''),
         isnull(cast(T.COL24 as varchar(11)), ''),
         isnull(cast(T.COL25 as varchar(11)), ''),
         isnull(cast(T.COL26 as varchar(11)), ''),
         isnull(cast(T.COL27 as varchar(11)), ''),
         isnull(cast(T.COL28 as varchar(11)), ''),
         isnull(cast(T.COL29 as varchar(11)), ''),
         isnull(cast(T.COL30 as varchar(11)), ''),
         isnull(cast(T.COL31 as varchar(11)), ''),
         isnull(cast(T.COL32 as varchar(11)), ''))
       as varbinary(8000))
from dbo.TABLE_OF_32_INTS as T
option (maxdop 1)
  • 2
    Thanks for this. It's faster for me too, but it does have a disadvantage in that it generates a longer binary string (191 characters vs 132 for the sample data). We'll definitely consider it though. – Joe Obbish May 9 at 14:45
-1

If you can ensure ahead-of-time that you don't store some particular int, like -2,147,483,648 then you can do something like:

 SELECT @dummy = 
        coalesce(CAST(COL1 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL2 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL3 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL4 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL5 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL6 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL7 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL8 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL9 AS BINARY(4)),  0x80000000) + 
        coalesce(CAST(COL10 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL11 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL12 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL13 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL14 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL15 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL16 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL17 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL18 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL19 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL20 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL21 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL22 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL23 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL24 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL25 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL26 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL27 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL28 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL29 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL30 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL31 AS BINARY(4)), 0x80000000) + 
        coalesce(CAST(COL32 AS BINARY(4)), 0x80000000) 
    FROM dbo.TABLE_OF_32_INTS
  • Thank you for the answer. All allowed values for the INT columns are possible. – Joe Obbish May 8 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.