SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 Site Related Forums
 Article Discussion
 Article: Bit-Masks
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

AskSQLTeam
Ask SQLTeam Question

USA
0 Posts

Posted - 08/09/2000 :  10:44:43  Show Profile  Visit AskSQLTeam's Homepage  Reply with Quote
chris writes "I am having difficultly finding information on bit masks. Can you help me understand advantages and how to create using VID6.0? SQL Server 7.0/Win98" Bitmasks are interesting. Here's the scoop.

Article Link.

jfuex
Starting Member

USA
29 Posts

Posted - 06/20/2002 :  17:34:22  Show Profile  Reply with Quote
It was asked in the original question and not addressed in the answer why you would want to use a bitmask. They are very useful for storing a series of related boolean values in a single field. Most frequently I use them for security related functionalty. For example, say that you have a user security table in which you want to store the user name, password and which of 32 pre-defined rights that user has. You could implement this as 2 varchar fields and 32 bit fields, but you could simplify this model by representing all of the permissions in an integer field. An integer field is essentially a binary value consisting of 32 bits. If you logically assign a specific permission to each bit position, you can store any combination of 32 distinct permission values in a single field.

Example:
Bit 1 = Read Permission
Bit 2 = Write Permissin
Bit 3 = Admin Permission.

To give a person read and write, but not admin permission you would set the permission (integer) value by OR'ing (|) all the rights you are interesting in combining as follows:
SET @USER_RIGHTS = 2 OR 4 {2 = 2^1 and 2 = 2^2)


To query to see if a user has admin rights you can do a bitwise comparison such as
IF (@USER_RIGHTS & 8 = 8) .... (8 = 2^3)

It makes your code a lot easier to readif you use some sort of constant to represent each of the bit/right assignments

PERMISSION_READ = 2 '00000000000000000000000000000010
PERMISSION_WRITE = 4 '00000000000000000000000000000100
PERMISSION_ADMIN = 8 '00000000000000000000000000001000

SET @USER_RIGHTS = PERMISSION_READ OR PERMISSION_ADMIN

An added bonus is that boolean operations are in the computer's native language and thus are pretty much one of the fastest operations around in just about any environment.

Go to Top of Page

tymberwyld
Starting Member

4 Posts

Posted - 10/11/2004 :  15:30:07  Show Profile  Reply with Quote
Ok, you mentioned using an "Int" DataType field (lets assume this is SQL Server). I've tried doing this, and maybe I don't understand enough, but I cannot store 32bits into an Int Column.

Lets say I have an Enum and the values are 1 - 23. Lets also assume that each value is represented by 1 bit (Booleans). Using your example, I should be able to do something like this:
Set @USER_RIGHTS = Power(2,32) -- Set the 32nd Bit

I get Arithmetic Overflow Errors doing this. What am I doing wrong and how to I get this working??
Go to Top of Page

robvolk
Most Valuable Yak

USA
15688 Posts

Posted - 10/11/2004 :  22:18:13  Show Profile  Visit robvolk's Homepage  Reply with Quote
The 32nd bit of a 32 bit word is for flagging negative/positive values. You can set it by negating the numeric value:

SET myIntColumn = -myIntColumn

Also, because the upper limit of an int is 2^31 - 1, you cannot raise 2 to any power greater than 30. You can get around this with:

SET myIntColumn=Power(2, 30) - 1 + Power(2, 30)

I leave the bitwise math equivalent of that to you (I sure can't figure it out) Don't forget that you can do bitwise operations using binary or varbinary values too (as the article demonstrates), as long as one of the arguments is an int, smallint, or tinyint. You can then convert the binary value to an int, or just store is as binary.

I'd suggest that if you had more than 32 settings you want to store, use a regular binary value instead. You can do bitwise operations on up to 4 bytes of it at a time, and if you need to work with more than 4 bytes you can use SUBSTRING() to extract the extra bytes you need:

DECLARE @flags binary(8)
set @flags=0xFFEEDDCCBBAA9900
select substring(@flags, 1, 4) & 16384
select substring(@flags, 5, 4) & 4096


Keep in mind that SQL Server is not designed for efficient bitwise handling, and unless you need to save many dozen or hundreds of settings (especially if you have to query them regularly) you are most likely better off storing them in individual bit columns. In SQL Server 2000 bit columns can be indexed. Additionally, you can create calculated columns that do the bitwise operations needed to mask out a setting, making it easier to read and query, and these can also be indexed in SQL Server 2000.
Go to Top of Page

tymberwyld
Starting Member

4 Posts

Posted - 10/11/2004 :  22:41:48  Show Profile  Reply with Quote
What I ended up doing (after further reading and understand) is making a Column called "SecurityAccess" with a DataType of BigInt. At this point in time I only need 23 values (or Bits) but I figured to go with the 64-Bit handling of a BigInt. Please let me know if there is a better way, I'll look into VarBinary DataTypes.

However, this made the Querying of what I need faster than ever! I was impressed! For instance, if I need all the Managers in the App:

Select * From Users Where SecurityAccess & Power(2, 4) > 0

There it is, short and sweet!
Go to Top of Page

robvolk
Most Valuable Yak

USA
15688 Posts

Posted - 10/11/2004 :  22:44:42  Show Profile  Visit robvolk's Homepage  Reply with Quote
Take a shot at creating a calculated column and indexing it, you may see an even bigger improvement.
Go to Top of Page

tymberwyld
Starting Member

4 Posts

Posted - 10/11/2004 :  22:48:21  Show Profile  Reply with Quote
Would you happen to have a sample Script? I'm not too familiar with Calculated Columns...and I'm not sure what it would be calculating. I don't have a Bit Column for each setting because the Settings can grow / shrink over the course of the App's lifetime...so I didn't want to "hard-code" Columns or have to Create / Delete Columns everytime a setting was Added / Deleted. In the begining I thought about Child Tables to store the info, but that would be insane to maintain because I need this info in 3 different tables.
Go to Top of Page

robvolk
Most Valuable Yak

USA
15688 Posts

Posted - 10/11/2004 :  22:59:47  Show Profile  Visit robvolk's Homepage  Reply with Quote
ALTER TABLE Users ADD Level4 AS SIGN(SecurityAccess & 16) -- gives a 1 or 0 if 4th bit is set
CREATE INDEX idx_Users_Level4 ON Users(Level4) -- index column
SELECT * FROM Users WHERE Level4=1 -- regular query

Forgot to mention that using this method to index the computed column lets the query optimizer choose an index seek instead of a table scan, which can greatly improve the query performance.

Even if you indexed the SecurityAccess column, since you were originally doing a bitwise operation in the WHERE clause:

WHERE SecurityAccess & Power(2, 4) > 0

That index can't be used, because the bitwise expression is to the left of the greater-than operator. Nor could this expression be written in a different way. This is known as a non-SARGable expression (SARG = search argument). A SARGable expression places a column value alone on the left side of a comparison operator:

WHERE Level4=1

The optimizer can then look for an index on that column and use it to evaluate the query.
Go to Top of Page

coolerbob
Aged Yak Warrior

United Kingdom
841 Posts

Posted - 09/17/2006 :  20:21:00  Show Profile  Reply with Quote
I've put a little something together. Just paste it into Visual Studio.NET
Any comments anyone?




Module sqlteam_version
'Introduction:
'In T-SQL, bitwise operations are generally not the fastest way to get results. That's because
'you are working with indexes -like phonebooks. When you literally use a phonebook you don't use
'bitwise comparisons. You use the alphabet. Bitwise comparison are fine for a microchip but not
'much good for an index. So the challenge is to translate the bitmask into something than the query
'optimizer can use.
'That is what's done here. The mask is turned into a set of SQL OR statements.
'So "1010" (which is 10 in the enumeration) becomes "WHERE FilterEnum=10 OR FilterEnum=11
'OR FilterEnum=10 OR FilterEnum=14 OR FilterEnum=15".
'That will mean that all Filter SProcs will use dynamic SQL.
'This example uses 16 bits. But you will probably use 64 or more in the real world.
'If this approach seems to combersome or it turns out to be too slow, then individual bit
'columns would be the only remaining solution.
'In such a case we would not need a Bit Mask column as well.
'The benefit of one bit mask column is that only one index has to be searched.
'We also still need to decide between having a normal SQL column that all the relevant SProcs update
'or a calculated column that calls a deterministic function. Either will slow down updates and creates.
'Side Point: If your deterministic function needs to use the current date, pick it up from a single-
'record table that has its date value updated every x seconds by a SQL Task on a Schedule.
'If the calculated column with an index on it is not significantly slower (for filters and updates)
'than a normal column, then we will stick with that.

'0 0000000000000000 0 All
'1 0000000000000001 2^0 CurrentEmployee
'2 0000000000000010 2^1 Manager
'3 0000000000000011 2^1+2^0 CurrentEmployee,Manager
'4 0000000000000100 2^2 HomeWorker
'5 0000000000000101 2^2+2^0 HomeWorker,CurrentEmployee
'6 0000000000000110 2^2+2^1 HomeWorker,Manager
'7 0000000000000111 2^2+2^1+2^0 HomeWorker,CurrentEmployee,Manager
'8 0000000000001000 2^3 SpecialNeedsEmployee
'9 0000000000001001 2^3+2^0 SpecialNeedsEmployee,CurrentEmployee
'10 0000000000001010 2^3+2^1 SpecialNeedsEmployee,Manager
'11 0000000000001011 2^3+2^1+2^0 SpecialNeedsEmployee,CurrentEmployee,Manager
'12 0000000000001100 2^3+2^2 SpecialNeedsEmployee,HomeWorker
'13 0000000000001101 2^3+2^2+2^0 SpecialNeedsEmployee,HomeWorker,CurrentEmployee
'14 0000000000001110 2^3+2^2+2^1 SpecialNeedsEmployee,HomeWorker,Manager
'15 0000000000001111 2^3+2^2+2^1+2^0 SpecialNeedsEmployee,HomeWorker,CurrentEmployee,Manager

'If you can't remember your maths from school:
'http://techsupt.winbatch.com/webcgi/webbatch.exe?techsupt/tsleft.web+Tutorials+Boolean~Math~and~Boolean~Algebra~Refresher.txt

'On the filter screen, a case statement will check for one of the combinations in this enumeration by starting from the bottom up.
'It will then pass an enum val to the function.
Public Enum FilterCombination
All
CurrentEmployee
Manager
CurrentEmployee_Manager
HomeWorker
HomeWorker_CurrentEmployee '5
HomeWorker_Manager
HomeWorker_CurrentEmployee_Manager
SpecialNeedsEmployee_CurrentEmployee
SpecialNeedsEmployee_Manager
SpecialNeedsEmployee_CurrentEmployee_Manager '10
SpecialNeedsEmployee_HomeWorker
SpecialNeedsEmployee_HomeWorker_CurrentEmployee
SpecialNeedsEmployee_HomeWorker_Manager
SpecialNeedsEmployee_HomeWorker_CurrentEmployee_Manager
End Enum

Private Function GetSQLForBitmask(ByVal andSelection As FilterCombination, ByVal notSelection As FilterCombination) As String
Dim sAnd As String = ""
Dim sNot As String = ""

Select Case andSelection 'These result in a T-SQL OR
Case 1
sAnd = "(FilterEnum=1 OR FilterEnum=3 OR FilterEnum=5 OR FilterEnum=7 OR FilterEnum=9 OR FilterEnum=11 OR FilterEnum=13 OR FilterEnum=15)"
Case 2
sAnd = "(FilterEnum=2 OR FilterEnum=3 OR FilterEnum=6 OR FilterEnum=7 OR FilterEnum=10 OR FilterEnum=11 OR FilterEnum=14 OR FilterEnum=15)"
Case 3
sAnd = "(FilterEnum=3 OR FilterEnum=7 OR FilterEnum=11 OR FilterEnum=15)"
Case 4
sAnd = "(FilterEnum=4 OR FilterEnum=5 OR FilterEnum=6 OR FilterEnum=12 OR FilterEnum=13 OR FilterEnum=14 OR FilterEnum=15)"
Case 5
sAnd = "(FilterEnum=5 OR FilterEnum=7 OR FilterEnum=13 OR FilterEnum=15)"
Case 6
sAnd = "(FilterEnum=6 OR FilterEnum=7 OR FilterEnum=14 OR FilterEnum=15)"
Case 7
sAnd = "(FilterEnum=7 OR FilterEnum=15)"
Case 8
sAnd = "(FilterEnum=8 OR FilterEnum=9 OR FilterEnum=10 OR FilterEnum=11 OR FilterEnum=12 OR FilterEnum=13 OR FilterEnum=14 OR FilterEnum=15)"
Case 9
sAnd = "(FilterEnum=9 OR FilterEnum=11 OR FilterEnum=13 OR FilterEnum=15)"
Case 10
sAnd = "(FilterEnum=10 OR FilterEnum=11 OR FilterEnum=14 OR FilterEnum=15)"
Case 11
sAnd = "(FilterEnum=11 OR FilterEnum=15)"
Case 12
sAnd = "(FilterEnum=12 OR FilterEnum=12 OR FilterEnum=14 OR FilterEnum=15)"
Case 13
sAnd = "(FilterEnum=13 OR FilterEnum=15)"
Case 14
sAnd = "(FilterEnum=14 OR FilterEnum=15)"
Case 15
sAnd = "(FilterEnum=15)"
End Select

Select Case notSelection 'These result in a T-SQL AND
Case 1
sNot = "(FilterEnum<>1 AND FilterEnum<>3 AND FilterEnum<>5 AND FilterEnum<>7 AND FilterEnum<>9 AND FilterEnum<>11 AND FilterEnum<>13 AND FilterEnum<>15)"
Case 2
sNot = "(FilterEnum<>2 AND FilterEnum<>3 AND FilterEnum<>6 AND FilterEnum<>7 AND FilterEnum<>10 AND FilterEnum<>11 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 3
sNot = "(FilterEnum<>3 AND FilterEnum<>7 AND FilterEnum<>11 AND FilterEnum<>15)"
Case 4
sNot = "(FilterEnum<>4 AND FilterEnum<>5 AND FilterEnum<>6 AND FilterEnum<>12 AND FilterEnum<>13 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 5
sNot = "(FilterEnum<>5 AND FilterEnum<>7 AND FilterEnum<>13 AND FilterEnum<>15)"
Case 6
sNot = "(FilterEnum<>6 AND FilterEnum<>7 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 7
sNot = "(FilterEnum<>7 AND FilterEnum<>15)"
Case 8
sNot = "(FilterEnum<>8 AND FilterEnum<>9 AND FilterEnum<>10 AND FilterEnum<>11 AND FilterEnum<>12 AND FilterEnum<>13 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 9
sNot = "(FilterEnum<>9 AND FilterEnum<>11 AND FilterEnum<>13 AND FilterEnum<>15)"
Case 10
sNot = "(FilterEnum<>10 AND FilterEnum<>11 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 11
sNot = "(FilterEnum<>11 AND FilterEnum<>15)"
Case 12
sNot = "(FilterEnum<>12 AND FilterEnum<>12 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 13
sNot = "(FilterEnum<>13 AND FilterEnum<>15)"
Case 14
sNot = "(FilterEnum<>14 AND FilterEnum<>15)"
Case 15
sNot = "(FilterEnum<>15)"
End Select

If sAnd.Length > 0 Then
If sNot.Length > 0 Then
Return String.Concat(sAnd, " AND ", sNot)
Else
Return sAnd
End If
Else
Return sNot
End If
End Function

Sub Main()
'test
'Normally you would base what parameters you pass in to the function on what the user
'specified on your screen...
Debug.WriteLine(GetSQLForBitmask(FilterCombination.SpecialNeedsEmployee_Manager, FilterCombination.All))
'Required result: (FilterEnum=9 OR FilterEnum=11 OR FilterEnum=13 OR FilterEnum=15)
End Sub

End Module

Edited by - coolerbob on 09/18/2006 03:39:14
Go to Top of Page

coolerbob
Aged Yak Warrior

United Kingdom
841 Posts

Posted - 05/17/2007 :  12:24:42  Show Profile  Reply with Quote
If I have an int column as I decribed in my previous post, and I want to unset (set to zero/off) one of the bits, how do I do that?
Setting it on is easy.
update MyTable
set MyCol=MyCol| 2

In the above example, this is the result if 8 was in the MyCol: 1000 OR 0010 = 1010 (8 or 2 = 10)

But if I wanted to switch one bit off, e.g. turn 1010 back into 1000, how do you do that?
I can test wether bit #1 is on or not because (using MyCol & 2):
1101 AND 0010 = 0000
1111 AND 0010 = 0010

But how do I in SQL turn a bit off if it's on? How do I turn 10 into 8, 6 into 4, 14 into 12, 15 into 13, 11 into 9, etc...
It looks like you just subtract two if the Bitwise AND operation is non-zero.
Is that right?
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 05/17/2007 :  13:11:25  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
if you have

0110

and you want to "unset" the second bit (from the right), you just AND it with:

1101

which gives you:

0100



- Jeff
http://weblogs.sqlteam.com/JeffS
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 05/17/2007 :  13:12:28  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
Let me add: I have no idea why anyone would store data as bits in an INT like this in T-SQL. Why would you want to do this?

- Jeff
http://weblogs.sqlteam.com/JeffS
Go to Top of Page

spirit1
Cybernetic Yak Master

Slovenia
11751 Posts

Posted - 05/17/2007 :  14:04:40  Show Profile  Visit spirit1's Homepage  Reply with Quote
flags maybe?

_______________________________________________
Causing trouble since 1980
blog: http://weblogs.sqlteam.com/mladenp
Go to Top of Page

Kristen
Test

United Kingdom
22431 Posts

Posted - 05/17/2007 :  14:06:35  Show Profile  Reply with Quote
I've had situations where I wanted bit-fields of "properties" that I wanted to match on.

Dunno if it was efficient or not, but that's how we did it!

Kristen
Go to Top of Page

coolerbob
Aged Yak Warrior

United Kingdom
841 Posts

Posted - 05/18/2007 :  04:22:34  Show Profile  Reply with Quote
quote:
Originally posted by jsmith8858

Let me add: I have no idea why anyone would store data as bits in an INT like this in T-SQL. Why would you want to do this?

- Jeff
http://weblogs.sqlteam.com/JeffS




Performance boost. Currently I have to do some joins and where clauses to establish this information. Picking up on column from one table is a whole lot faster.

I'm now at the performance tuning part of this particular project. The old database before I arrived was badly de-normalized. I came in and made a normalized one and converted the denormalized data from the old db into the new. They've been running on the new db for owver a year now and all is well. Now we are adding some denormalized bits to add performance gains - while of course leaving the normalized original source data in place.

Edited by - coolerbob on 05/18/2007 04:32:50
Go to Top of Page

coolerbob
Aged Yak Warrior

United Kingdom
841 Posts

Posted - 05/18/2007 :  04:27:57  Show Profile  Reply with Quote
quote:
Originally posted by jsmith8858

if you have

0110

and you want to "unset" the second bit (from the right), you just AND it with:

1101

which gives you:

0100



- Jeff
http://weblogs.sqlteam.com/JeffS





Thanks!

update MyTable
set MyCol=MyCol & 14

I was being a little thick there...

Edited by - coolerbob on 05/18/2007 04:28:28
Go to Top of Page

coolerbob
Aged Yak Warrior

United Kingdom
841 Posts

Posted - 08/10/2007 :  08:23:14  Show Profile  Reply with Quote
Some of you may have a use for grey codes too.
You can read more about that here:
http://en.wikipedia.org/wiki/Grey_code
Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.3 seconds. Powered By: Snitz Forums 2000