Sql-server – Bitmask Flags with Lookup Tables Clarification

database-designindexsql serversql-server-2008

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)

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.

Best 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

exact matches

WHERE computedInt = POWER(2, 6) -- bit position 7
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.

Related Solutions

Sql-server – Do I need separate indexes for each type of query, or will one multi-column index work

You are right in that your example query would not use that index.

The query planner will consider using an index if:

all the fields contained in it are referenced in the query
some of the fields starting from the beginning are referenced

It will not be able to make use of indexes that start with a field not used by the query.

So for your example:

SELECT [id], [name], [customerId], [dateCreated]
   FROM Representatives WHERE customerId=1 
   ORDER BY dateCreated

it would consider indexes such as:

[customerId]
[customerId], [dateCreated]
[customerId], [dateCreated], [name]

but not:

[name], [customerId], [dateCreated]

If it found both [customerId] and [customerId], [dateCreated], [name] its decision to prefer one over the other would depend on the index stats which depend on estimates of the balance of data in the fields. If [customerId], [dateCreated] were defined it should prefer that over the other two unless you give a specific index hint to the contrary.

It is not uncommon to see one index defined for every field in my experience either, though this is rarely optimal as the extra management needed to update the indexes on insert/update, and the extra space needed to store them, is wasted when half of them may never get used - but unless your DB sees write-heavy loads the performance is not going to stink badly even with the excess indexes.

Specific indexes for frequent queries that would otherwise be slow due to table or index scanning is generally a good idea, though don't overdo it as you could be exchanging one performance issue for another. If you do define [customerId], [dateCreated] as an index, for example, remember that the query planner will be able to use that for queries that would use an index on just [customerId] if present. While using just [customerId] would be slightly more efficient than using the compound index this may be mitigated by ending up having two indexes competing for space in RAM instead of one (though if your entire normal working set fits easily into RAM this extra memory competition may not be an issue).

Sql-server – Methods for finding new Trace Flags in SQL Server

There's nothing you can do to find the list except ask or pick them up from posts/slide decks/etc. The list only exists in the code, in a header file where the valid trace flag numbers are mapped to names in a big enum in the C++ code, and then the names are used in the rest of the code.

As Aaron said, you can enable any trace flag number, and if it doesn't do anything, or you don't exercise the functionality that the trace flag is relevant to, you won't notice any difference in behavior.

DBCC TRACEON doesn't check anything - as there's no run-time list of which numbers are valid or not - it just enables that trace flag number in a bitmap of what flags are set for that connection/globally.

The problem with having a validity check is that would expose which trace flags are valid, allowing them to be discovered. This way the 'valid list' is effectively obfuscated, which is what the SQL team wants.

Regarding Kin's suggestion in a comment that SQL Server should have select * from sys.available_trace_flags - Yes and no. There are many trace flags that are highly detrimental to performance and are only necessary for debugging problems under guidance from Product Support, but SQL Server could list the 'safe' flags.

Best Answer

Related Solutions

Sql-server – Do I need separate indexes for each type of query, or will one multi-column index work

Sql-server – Methods for finding new Trace Flags in SQL Server

Related Question