Home Uncategorized Dealing with very large bitmasks

    Dealing with very large bitmasks

    734
    8

    Continuing in my series of things you should probably not do in SQL Server but sometimes have to, I’m going to do a few posts on dealing with very large bitmasks.

    Let me first state my utter hatered of bitmasks in databases. I think they’re annoying, make the system difficult to understand, and whether or not they violate the First Normal Form (that’s up for discussion), using them is just a sign of bad design.

    But as I’ve said in other posts, I realize that short deadlines and tiny budgets are an issue at most shops, and sometimes we just need to shoehorn in a solution real quick (yeah, as if it’s not going to last for the next 5+ years?)

    In one case in the past, bitmasks were a very convenient solution to a problem I faced with an access control system. But alas, I only had 8 bytes available to me. Only enough for 64 values. And so that solution failed. And the company failed. And many, many tears were shed… If only I’d been able to figure out how to manipulate a bigger bitmask, I might have saved the little children…

    I won’t go into any more detail on that particular issue since there are still a few pending lawsuits, but suffice it to say that if that situation were happening today, I probably wouldn’t use a bitmask anyway. But you might need one — so here’s how you do it:

    First we’re going to modify the table of numbers that I’m always telling you that you absolutely must have in every single database.

    SELECT (a.number * 256 + b.number) AS Number,
    	CASE (a.number * 256 + b.number) % 8 
    		WHEN 0 THEN ((a.number * 256 + b.number) - 1) / 8
    		ELSE (a.number * 256 + b.number) / 8 
    		END + 1 AS Byte,
    	POWER(2, CASE (a.number * 256 + b.number) % 8 
    		WHEN 0 THEN 8
    		ELSE (a.number * 256 + b.number) % 8 
    		END-1) AS BitValue
    INTO BitmaskNumbers
    FROM
    	(
    		SELECT number
    		FROM master..spt_values
    		WHERE 
    			type = 'P'
    			AND number <= 255
    	) a (Number),
    	(
    		SELECT number
    		FROM master..spt_values
    		WHERE 
    			type = 'P'
    			AND number <= 255
    	) b (Number)
    WHERE 
    	(a.number * 256 + b.number) BETWEEN 1 AND 32767
    GO
    
    CREATE CLUSTERED INDEX IX_Byte ON BitmaskNumbers (Byte)
    GO
    

    This will produce a table with 32767 rows. Each row has a Number, which will represent a bit position in our bitmask, a Byte, which will help to parse the bitmask, and a BitValue, which is the value that the individual bits within each byte represent. Feel my 1960-esque skill!

    The brighter bulbs in my audience have now figured out that I’m going to show you how to handle a 4096-byte bitmask — capable of handling up to 32767 values. Not bad. But if you need more, just put more rows in the BitmaskNumbers table.

    So what do you want to do with bitmasks? Most of the queries I’ve seen involve access control And for those queries, you want to use a logical and and see if it evaluates to a number other than 0. That is, we want to see if both bitmasks we’re comparing have any of the same bits set.

    Using what little math knowledge I have managed to retain, I conjured up the following, which indicates which bit positions, based on the “number”, are filled in a bitmask. For instance:

    DECLARE@x VARBINARY(4096)
    SET @Bitmask = 0x1F0000000000000000000000000000000000000000000000000000000000000000000000123000000000000000000000000001
    
    SELECT Number
    FROM BitmaskNumbers
    WHERE (SUBSTRING(@Bitmask, Byte, 1) & BitValue) = BitValue
    	AND Byte <= DATALENGTH(@Bitmask)
    
    
    Number
    ----------
    1
    2
    3
    4
    5
    290
    293
    301
    302
    401
    

    Fun stuff, no?

    The Byte <= DATALENGTH(@x) allows SQL Server to utilize the clustered index on Byte, so that a full table scan doesn’t have to happen every single time. Small optimization. I couldn’t think of any others. If you can, drop me a line…

    Those of you who’ve read this far are probably yawning and wondering where the access control stuff is… Who cares about chunking up the bitmask into its bit positions? Well, it’s simply the first step. Bear with me.

    What we need to do is wrap this in a UDF. Then if we had two bitmasks, we could join the bit positions to eliminate those that aren’t in common…

    CREATE FUNCTION dbo.splitBitmask
    (
    	@Bitmask VARBINARY(4096)
    )
    RETURNS TABLE
    AS
    RETURN
    (
    	SELECT Number
    	FROM BitmaskNumbers
    	WHERE (SUBSTRING(@Bitmask, Byte, 1) & BitValue) = BitValue
    		AND Byte <= DATALENGTH(@Bitmask)
    )
    GO
    
    DECLARE @Bitmask1 VARBINARY(4096)
    SET @Bitmask1 = 0x1F0000000000000000000000000000000000000000000000000000000000000000000000123000000000000000000000000001
    
    DECLARE @Bitmask2 VARBINARY(4096)
    SET @Bitmask2 = 0x0E0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    
    SELECT x.Number
    FROM dbo.splitBitmask(@Bitmask1) x
    JOIN dbo.splitBitmask(@Bitmask2) y ON x.Number = y.Number
    GO
    
    
    Number
    ----------
    2
    3
    4
    

    We now know that these two bitmasks share bits 2, 3, and 4 in common. But for most access control situations, we don’t care what bits they share in common — just that they share some.

    CREATE FUNCTION dbo.HasAccess
    (
    	@Bitmask1 VARBINARY(4096),
    	@Bitmask2 VARBINARY(4096)
    )
    RETURNS BIT
    AS
    BEGIN
    	DECLARE @Result BIT
    
    	SELECT @Result = 
    		CASE COUNT(*)
    			WHEN 0 THEN 0
    			ELSE 1
    		END
    	FROM dbo.splitBitmask(@Bitmask1) x
    	JOIN dbo.splitBitmask(@Bitmask2) y ON x.Number = y.Number
    
    	RETURN (@Result)
    END
    GO
    
    DECLARE @Bitmask1 VARBINARY(4096)
    SET @Bitmask1 = 0x1F0000000000000000000000000000000000000000000000000000000000000000000000123000000000000000000000000001
    
    DECLARE @Bitmask2 VARBINARY(4096)
    SET @Bitmask2 = 0x0E0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    
    SELECT dbo.HasAccess(@Bitmask1, @Bitmask2) AS HasAccess
    GO
    
    
    HasAccess
    -------------
    1
    

    … And that is pretty much it for this installment. We can now determine whether or not two bitmasks have bits in common, and if necessary which bits they share.

    Future installments will cover how to manipulate large bitmasks in other ways — flip specific bits, perform a logical and that produces a bitmask instead of a result set, and perform a logical or that produces a bitmask. All very useful stuff if you need to work with these bitmasks. But now I just need to figure out how to do all of that stuff.

    So until next time…. Don’t use this technique.

    Previous articleValidate a URL from SQL Server
    Next articleCorrection on bitmask handling
    Adam Machanic helps companies get the most out of their SQL Server databases. He creates solid architectural foundations for high performance databases and is author of the award-winning SQL Server monitoring stored procedure, sp_WhoIsActive. Adam has contributed to numerous books on SQL Server development. A long-time Microsoft MVP for SQL Server, he speaks and trains at IT conferences across North America and Europe.

    8 COMMENTS

    1. I appreciate your binary examples.  One of the things that perplexes me as a previous application developer turned sql developer is that all of your examples would be better handled on the client side.  Some of your code…especially the use of a numbers table…is extremely innovative.  But, in a total solution I don’t see why I would use the database to handle any of them.  Don’t mean to be harsh…but i could see a carpenter build a nice space shuttle with wood… I just don’t see it getting far.

    2. Jason:
      As I mention several times in the post, I do not recommend actually using this technique, for several reasons.  That said, it is certainly not hard to think of scenarios where one might want to do these kinds of things in the database.  Think encapsulation.  If — for some very, very good reason — you need to use bitmasks in the database, but perhaps don’t need to expose the bitmasks to the application, you can and should do this work in the database in order to keep the application and database as loosely coupled as possible.
      I am all for handling tasks wherever they are best suited, but I’m an even bigger fan of highly modular designs.  So if I can keep the application ignorant of some hack I’ve worked up in the database, all the better…

    3. Just FYI Adam, I love this article.  I’ve been here hundreds of times so attribute a lot of traffic to me!

    4. Glad you enjoyed it. You know you can simply print it, frame it, and hang it on the wall, right? 🙂

    5. We do use large bitmasks in our database – and until now, we’ve handled them via SQL CLR, making all processing rather fast. However, with SQL Azure, CLR is no longer an option, at least for now. I tried re-implementing some of our bitmask user-defined functions in SQL basing myself on your wonderful articles and the bitmask reconstruction operation seems to be much slower than its SQL CLR counterpart. Do you think the bad performance is an intrinsic property of the bitmask reconstruction, or is there room for optimization?

    6. Hi David,
      It seems natural that a CLR approach would work much better–it’s a very CPU-heavy operation, and CLR functions almost always deliver higher performance in those cases. Is it so much slower that it’s unbearable?
      I originally wrote all of this stuff 7 or 8 years ago, so I’m not going to be able to give you a great answer about improvements without doing some testing. But taking a quick look at it, I’m thinking that yes, there is some room for optimization — perhaps by using some of the XQuery methods that were added in SQL Server 2005. Are those available in Azure? I’ve luckily managed to avoid having to use it, to date!
      –Adam

    7. The performance degradation is significant even for the binary mask creation. Consider the following:
      select Data, fnCreateBinaryMark(40) from SomeTable
      Which would create a binary mask of 40 bytes for each row of the table.
      For a table containing ~4000 rows, the SQL CLR version runs in less than a second while the purely SQL version takes 6 seconds.
      Since the binary mask creation is simply the concatenation if table variable values and  since the re-construction of the varbinary from a table already seems to be a costly operation, I have a feeling I would not be able to build performant bit operation functions, since it’s the mandatory final step.
      I do believe XQuery is available on Azure, but not sure how it can help – afaik, bit operations are not part of XPath/XQuery.

    8. Hi!
      This article was very useful to me. We have an old VB6 system with SQL server 2005 backend still in production. We are porting it to a SPA using AngularJS, but… it´s still in production! Clients are always asking for improvements!
      In addition, the system has a pre-diluvian era DB sync system, using custom batch files and FTP. This means that ANY change in DB structure must be reflected also in the sync system. A really nightmare!
      Recently a client asks about custom data access based on day by day basis spanning a year, or 365/366 days.
      The bitmask solution was perfect for me. I used a 368 bits (46 bytes) binary mask, setting bits on/off according access days.
      This means I had to put in the akward DB sync system ONLY one field, which make me very happy!!!
      Thanks for sharing!
      Alejandro.

    Comments are closed.