Should I index a bit field in SQL Server?

Question

I remember reading at one point that indexing a field with low cardinality (a low number of distinct values) is not really worth doing. I admit I don't know enough about how indexes work to understand why that is.

So what if I have a table with 100 million rows in it, and I am selecting records where a bit field is 1? And let's say that at any point in time, there are only a handful of records where the bit field is 1 (as opposed to 0). Is it worth indexing that bit field or not? Why?

Of course I can just test it and check the execution plan, and I will do that, but I'm also curious about the theory behind it. When does cardinality matter and when does it not?

Answer 1

Consider what an index is in SQL - and index is really a chunk of memory pointing at other chunks of memory (i.e. pointers to rows). The index is broken into pages so that portions of the index can be loaded and unloaded from memory depending on usage.

When you ask for a set of rows, SQL uses the index to find the rows more quickly than table scanning (looking at every row).

SQL has clustered and non-clustered indexes. My understanding of clustered indexes is that they group similar index values into the same page. This way when you ask for all the rows matching an index value, SQL can return those rows from a clustered page of memory. This is why trying to cluster index a GUID column is a bad idea - you don't try to cluster random values.

When you index an integer column, SQL's index contains a set of rows for each index value. If you have a range of 1 to 10, then you would have 10 index pointers. Depending on how many rows there are this can be paged differently. If your query looks for the index matching "1" and then where Name contains "Fred" (assuming the Name column is not indexed), SQL gets the set of rows matching "1" very quickly, then table scans to find the rest.

So what SQL is really doing is trying to reduce the working set (number of rows) it has to iterate over.

When you index a bit field (or some narrow range), you only reduce the working set by the number of rows matching that value. If you have a small number of rows matching it would reduce your working set a lot. For a large number of rows with 50/50 distribution, it might buy you very little performance gain vs. keeping the index up to date.

The reason everyone says to test is because SQL contains a very clever and complex optimizer that may ignore an index if it decides table scanning is faster, or may use a sort, or may organize memory pages however it darn well likes.

Answer 2

If you are running SQL Server 2008 and above you can benefit from filtered indexes.

CREATE NONCLUSTERED INDEX RecordsWhereBitFieldIs_1
    ON Table1(BitField, LastName)
    WHERE BitField = 1 ;
GO

Answer 3

100-million records with only a few having the bit field set to 1? Yes, I would think indexing the bit field would definitely speed up querying the bit=1 records. You should get logarithmic search time from the index and then only touch the few pages with bit=1 records. Otherwise, you'd have to touch all pages of the 100-million record table.

Then again, I'm definitely not a database expert and could be missing something important.

Answer 4

Of course it worths, especially if you need to retrieve the data by that value. It would be similar to using a sparse matrix instead of using a normal matrix.

Now with SQL 2008 you can use partitioning functions, and you are able to filter the data that goes in an index. The disadvantage for earlier versions would be that the index would be made for all the data, but this can be optimized by storing the interesting values in a separate file group.

Answer 5

If your goal is to make querying for records where the bit field value equals '1' faster you might try an indexed view of your base table which only contains records where your bit field equals '1'. In enterprise edition if a query could make use of an indexed view instead of a specified table to improve query performance it will use the view. In theory this would increase the speed of select queries which only look for records with a bit field value of '1'.

http://www.microsoft.com/technet/prodtechnol/sql/2005/impprfiv.mspx

All this assumes you are Microsoft SQL Server 2005 Enterprise. The same might apply to 2008, I'm not familiar with that version.

Answer 6

As others have said, you'll want to measure this. I don't recall where I've read this, but a column needs to have very high cardinality (around 95%) in order for an index to be effective. Your best test for this would be to build the index and examine the execution plans for the 0 and 1 values of the BIT field. If you see an index seek operation in the execution plan then you know that your index will be used.

Your best course of action would be to test the with a basic SELECT * FROM table WHERE BitField = 1; query and slowly build out the functionality from there step by step until you have a realistic query for your application, examining the execution plan with every step to make sure that the index seek is still being utilized. Admittedly, there is no guarantee that this execution plan will be used in production, but there is a good chance that it will be.

Some information can be found on the sql-server-performance.com forums and in the referenced article

Answer 7

You can't index a bit field in SQL Server 2000, as was indicated in the Books Online at the time:

bit

Integer data type 1, 0, or NULL.

Remarks

Columns of type bit cannot have indexes on them.

Yes, if you have only a handful of rows, out of millions, an index will help. But if you want to do it in this case you need to make the column a tinyint.

Note: Enterprise Manager will not let you create an index on a bit column. If you wish you can still manually create an index on a bit column:

CREATE INDEX IX_Users_IsActiveUsername ON Users
(
   IsActive,
   Username
)

But SQL Server 2000 will not actually use such an index - running a query where the index would be a perfect candidate, e.g.:

SELECT TOP 1 Username 
FROM Users
WHERE IsActive = 0

SQL Server 2000 will do a table scan instead, acting as though the index doesn't even exist. If you change the column to a tinyint SQL Server 2000 will do an index seek. Also, the following non-covered query:

SELECT TOP 1 * 
FROM Users
WHERE IsActive = 0

It will perform an index seek, followed by a bookmark lookup.

---

SQL Server 2005 does have limited support for indexes on bit columns. For example:

SELECT TOP 1 Username 
FROM Users
WHERE IsActive = 0

will cause an index seek through the covering index. But the non-covered case:

SELECT TOP 1 * 
FROM Users
WHERE IsActive = 0

will not cause an index seek followed by a bookmark lookup, it will perform a table scan (or clustered index scan), rather than performing the index seek followed by a bookmark lookup.

Verified by experimentation and direct observation.