Spreading Rows Into Hash Buckets With CHECKSUM and Modulo

Hash buckets sort rows into a fixed number of repeatable groups, so you can hand each group to a different worker. The same key always lands in the same bucket. That does not mean the buckets are equal in size, or equal in work.

Why you would use hash buckets

Picture a nightly job that has to touch every customer. One worker takes hours. So you start 16 workers, and worker 3 handles every customer in bucket 3. Nobody overlaps, and nobody has to ask who is doing what.

The usual recipe is CHECKSUM of the key, then modulo the number of buckets. It is one line of T-SQL. It also hides two traps, and we will walk into both on purpose.

Build the bucket column

First, a peek at CHECKSUM itself. For small integers it simply returns the number you gave it. Remember that, because it explains most of what follows.

SELECT value AS id, CHECKSUM(value) AS checksum_value
FROM GENERATE_SERIES(1, 5);

The bucket formula takes ABS of the checksum, so the result is never negative. But a checksum can be the smallest possible int, and ABS of that value does not fit in an int. Watch.

BEGIN TRY
    SELECT ABS(CONVERT(int, -2147483648)) AS plain_abs;
END TRY
BEGIN CATCH
    SELECT ERROR_NUMBER() AS error_number, ERROR_MESSAGE() AS error_message;
END CATCH;

SELECT ABS(CONVERT(bigint, -2147483648)) % 16 AS bigint_bucket;

Plain ABS fails with error 8115, an arithmetic overflow. Converting to bigint first works, and the bucket is 0. So the table uses bigint. The bucket is a persisted computed column, so the grouping travels with the row. Load customers 1 to 1000 into 16 buckets.

DROP TABLE IF EXISTS dbo.CustomerBucket;

CREATE TABLE dbo.CustomerBucket
(
    CustomerId int NOT NULL PRIMARY KEY,
    Bucket AS CONVERT(int, ABS(CONVERT(bigint, CHECKSUM(CustomerId))) % 16) PERSISTED
);

INSERT dbo.CustomerBucket (CustomerId)
SELECT value FROM GENERATE_SERIES(1, 1000);

SELECT Bucket, COUNT(*) AS customers
FROM dbo.CustomerBucket
GROUP BY Bucket
ORDER BY Bucket;

Looks perfect. Every bucket has 62 or 63 customers. This is the picture people take to the design review, and it is the reason the trap works.

Equal rows are not equal work

Now give each customer some work. Every customer has 10 orders, except customer 7, who has 3,000. Every bucket still has about 62 customers. Count the orders per bucket and see who stays late.

DROP TABLE IF EXISTS #Work;
CREATE TABLE #Work (CustomerId int NOT NULL PRIMARY KEY, Orders int NOT NULL);

INSERT #Work (CustomerId, Orders)
SELECT CustomerId, CASE WHEN CustomerId = 7 THEN 3000 ELSE 10 END
FROM dbo.CustomerBucket;

SELECT b.Bucket, COUNT(*) AS customers, SUM(w.Orders) AS orders
FROM dbo.CustomerBucket AS b
JOIN #Work AS w ON w.CustomerId = b.CustomerId
GROUP BY b.Bucket
ORDER BY b.Bucket;

Bucket 7 has 63 customers like its neighbors, but 3,620 orders against about 630. Worker 7 does almost six times the work, and the job ends when that worker ends. Balanced row counts told us nothing about this.

When your keys have a pattern

Now the second trap. Suppose your customer numbers are multiples of 16, which happens when a legacy system hands out ids in steps. CHECKSUM returns the number itself, and any multiple of 16 divided by 16 leaves remainder 0. Reload the table and count, with a join to a list of all 16 buckets so empty ones still show up.

TRUNCATE TABLE dbo.CustomerBucket;

INSERT dbo.CustomerBucket (CustomerId)
SELECT value * 16 FROM GENERATE_SERIES(1, 1000);

WITH Counts AS
(
    SELECT Bucket, COUNT(*) AS customers
    FROM dbo.CustomerBucket
    GROUP BY Bucket
)
SELECT n.value AS bucket, COALESCE(c.customers, 0) AS customers
FROM GENERATE_SERIES(0, 15) AS n
LEFT JOIN Counts AS c ON c.Bucket = n.value
ORDER BY n.value;

All 1,000 customers land in bucket 0. The other 15 workers sit idle. You paid for 16 workers and got one.

A cryptographic hash scrambles the pattern. Here SHA2_256 hashes the key as text, and I keep the first 8 bytes as a bigint. That number can be negative, so the modulo can be negative too. Adding 16 and taking modulo again puts it back in the 0 to 15 range.

SELECT m.bucket, COUNT(*) AS customers
FROM dbo.CustomerBucket AS cb
CROSS APPLY
(
    SELECT CONVERT(int, ((CONVERT(bigint, SUBSTRING(
        HASHBYTES('SHA2_256', CONVERT(varbinary(max), CONVERT(nvarchar(20), cb.CustomerId))),
        1, 8)) % 16) + 16) % 16) AS bucket
) AS m
GROUP BY m.bucket
ORDER BY m.bucket;

Same keys, and now every bucket gets customers, from 45 to 77. Not equal, but nobody sits idle. The catch is that you must always hash the same bytes, here the Unicode text of the number. Keep that rule in one place.

What to check before you add workers

A bucket is a grouping decision, not an identity. Many customers share one, so never use it as a key. Run the count against your real keys, not a tidy series. Then measure work per bucket, like orders or rows touched, not just customers.

Also make each worker safe to rerun, because a failed bucket will be retried. Finally, write down the bucket count. Change 16 to 32 and many customers move to a different worker.

DROP TABLE IF EXISTS dbo.CustomerBucket;
DROP TABLE IF EXISTS #Work;

Count your own keys first, and the workers will thank you.

A hash bucket is not a fair share of work, it is a repeatable grouping.

Published by Pinal Dave on SQLAuthority. More of my work at pinaldave.com.