Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I've received a dataset from an outside source which contains several bitmask fields as varchars. They come in length as low as 3 and as long as 21 values long. I need to be able to run SELECT queries based on these fields using AND or OR logic.

Using a calculated field, where I just convert the bits into an integer value, I can easily find rows that match an AND query, by using a simple WHERE rowvalue = requestvalue, but the OR logic would require using bitwise & in order to find matching records.

Given that I would need to work with several of these columns and select from hundreds of millions of records, I feel that there would be a huge performance hit when doing bitwise & operations to filter my SELECT results.

I came across this answer from searching and it looked like it may fit my needs, but I need some clarification on how it is implemented.

Is this as simple as creating a lookup table that has all possible search conditions?

Example for 3 bits using (a & b) (Edit: Wrong bitwise op)

001,001
001,011
001,101
001,111
010,010
010,011
010,110
011,011
011,111
etc

The author mentions that it's counter-intuitive initially, but I can't help but feel I'm interpreting the solution incorrectly, as this would give me a single lookup table with likely billions of rows.

Any clarifications on the answer I linked above or other suggestions that would preserve the existing database are appreciated.

Edit: A more concrete example using small data.

Four flags, HasHouse,HasCar,HasCat,HasDog, 0000 is has none, 1111 is has all.

Any number of flags, from all to none, can be flipped, and results must be filtered where selection matches all (Using exact value comparison) or at least 1 (Using bitwise &).

Adding a single calculated column for each bitmask is ok, but adding a column for each bit for more than 100 bits, coupled with how to insert/update the data is why I'm trying to find alternative solutions.

share|improve this question
6  
IMHO bitmasks are the devil and are from a time where every component of a system was so slow and expensive - compared to the labor involved with all the hacks and workarounds you have to use with them - that it made this approach seem attractive. If the dataset is a one-time import I would spend the one-time cost converting this to something that is actually manageable - e.g. 21 BIT/SPARSE columns. –  Aaron Bertrand Apr 1 '13 at 20:25
    
I agree that it shouldn't be stored as a bitmask, but I need to run under the assumption that I cannot change the data directly. If user JNK's solution is as simple and easy to implement as it sounds, I would like to use it with the data in place. Otherwise, I'll have to figure out another "workaround", such as just adding hundreds of columns that would be populated/updated with some tricky sql or preprocessing the updates before they hit the database. –  mindreave Apr 1 '13 at 23:28
add comment

1 Answer

I partially agree with Aaron's comment - in the most general case for storing 21 unrelated pieces of information, you'd probably use 21 bit columns. As a general solution, it may well be your best solution. If you had multiple bitmask-ed varchar columns, that would translate to a row with possibly over a hundred bit flags. FYI, 21 bits get stored as 3 bytes when you don't define them as NULLable, removing the necessity for space in the NULL bitmap. Since you have multiple bitmask columns, you'd end up with every 8 bits mashed into a byte.

What SQL Server ends up doing with your multi-column queries is eventually a bunch of bitmasking routines (yes! SQL Server uses bitmasks, so they the concept per se can't be all bad!) but for average use cases, it makes life easier for you.

If we had more information about what types of queries you run, we may be able to better advise, because ultimately the use cases dictate the design.

If you persist with the COMPUTED column, I would persist and index it if you haven't already. It helps some queries, such as

  1. exact matches

    WHERE computedInt = POWER(2, 6) -- bit position 7

  2. AND matching on 15th bit and OR matching on 2 other bits (10th and 7th)

    WHERE computedInt >= Power(2,14) AND computedInt < Power(2,15) AND computedInt & (Power(2,9) + Power(2,6)) > 0

But these are probably exotic samples and yet also real live in some cases. It's certainly not too much worse than 21 individual bit columns, for which yes your statements could be easier to write, but remember that SQL Server has mashed them for storage into 3 bytes and will be doing the bit-unmasking anyway! You would have thought if bit-masking were all bad (without exception) then SQL Server wouldn't be doing it, right?

EDIT

Re the scenario of

Four flags, HasHouse,HasCar,HasCat,HasDog, 0000 is has none, 1111 is has all.

it is more efficient and logically expedient to test all 4 bits at once and do a single integer based operation, e.g.

WHERE computedInt & (POWER(2,10)+POWER(2,5)+POWER(2,3)+POWER(2,1)) = 0 -- has none
WHERE computedInt & (POWER(2,10)+POWER(2,5)+POWER(2,3)+POWER(2,1)) > 0 -- has one or more

Hypothetically, if this were your most exercised query on the table, you might even group the four columns into another computed column and index it separately, making the bitmask unnecessary (just test the resultant int with =0 and >0). You might even go further and just precompute the answer... horses for courses.

share|improve this answer
    
As per your suggestion, I am planning on adding computed columns for each bitmask value for exact value comparisons where the flags are joined by AND, but when I need to consider OR is where the problems arise. I could use a bitwise '&' to do this, but because indexes won't apply in those cases, having a very large dataset increases the work done. In this case, it's not just one bitmask, but several, grouped by categories. I'll amend my question with a more concrete example. –  mindreave Apr 2 '13 at 0:21
    
Re: EDIT- It does seem more efficient to use the single indexed column when only considering small amounts. But extend this further, as I described in the original post. Instead of 1000s of records, there will be hundreds of millions. Instead of a single bitmask with 4 bits, there can be dozens, with between 3 and 21 bits. Calculating the columns for each bitmask would be a one time cost, but bitwise operations would be run on every row. Precomputing the answer seems like JNK's solution, linked above, which would let me use indexes, if I understood better. Perhaps I'm overthinking this? –  mindreave Apr 2 '13 at 1:48
    
My point is that you give a specific scenario, you get a specific solution. You give no scenarios or paint a broad picture, you get only broad solutions, of the most general form. That's how it works, and the only way I can think for it to work. I was not advocating to use the 4-bit solution for everything, rather getting you to consider targeted approaches for the most-used scenarios for your data. –  孔夫子 Apr 2 '13 at 1:52
    
You may also consider storing your data in EAV form, which means for every record of your 100s of millions, there could be up over a hundred attribute-values (records in a secondary table). The performance of such storage schemas aren't brilliant either but works for certain cases. –  孔夫子 Apr 2 '13 at 1:55
    
I'm sorry if I come off a bit frustrated. The main question was hoping to find clarification on JNK's solution. For your general solutions, I described doing very similar in the original post, though I called it a calculated field instead of a computed column. I'm trying to avoid the bitwise operations altogether because it is O(n) or worse, which may cause time issues as the database grows. I'm currently leaning towards this implementation anyway, hoping that the calculation time can be negligible or that SQL Server will intelligently do each unique comparison only once. –  mindreave Apr 2 '13 at 2:51
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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