Wednesday, July 13, 2005
You can't break just some of the rules.
I found out some weird stuff today at work. I've always been told that you have to have good selectivity for an index to be useful, particularly if it's a non-clustered index. So you wouldn't imagine that an index on a bit field would particularly improve performance. Yet today I saw a query that went from two plus minutes go to a one second query by adding a non-clustered index on a bit field.
This really perturbed me. Why would adding an index to a field with terrible selectivity improve the speed by exponential factors?
Before the answer a little bit of history. The database structure we are working with is a legacy structure that was designed and created before my time with the company. This structure breaks every single rule and principle of relational design I've ever learned. It is in all honesty one of the freakiest database systems I've ever seen. Unfortunately there is a lot of code written on top of the structure and very little political support for rebuilding it.
Just to give you a taste of the pain, the system is designed so that we maintain logically separate databases in the same physical database and they are differentiated by a prefix.
Next the main table for each database is this massively wide table with all kinds of interdependencies between columns. In order to make fulltext searching work better, someone had the bright idea that we should denormalize the list structure, and instead of storing lists in a separate table, we should store them inside this table in a single column in a semi-colon space delimited list. To add to that, we should also then make another column in the same table that contains the id's of all of the list items, and build a comma delimited list for the ids. Of course those two columns should be dependend not only on each other, but on several separate tables, and if you want to verify the integrity of any of this data, you have to pull it out of the database and run through it with a program. No referential integrity here.
Ok, so that was a mouthful, and to be honest it is just the tip of the iceburg when it comes to all of the problems present within this database. Now, let's get down to the original problem mentioned at the beginning. Why does an index on a bit column speed up queries?
Well the problem lies in the fact that this superwide table has a lot of variable length columns. So if I want to do a query like select count(*) from table where bitfield = 1. The server not only has to do a table scan, but it has all kinds of trouble actually moving through the records.
It turns out that creating a non-clustered index on that bitfield essentially creates a structure outside of the table that represents a fixed width layout of all the records for the table with just that field. So for the server to move through the records, it can now do so simply by incrementing a pointer.
We theorized that we would see the same performance if we were to extract just the bit column into a separate table and run the same queries. Our theory exactly matched reality. So ultimately the solution to the problem is to move the data into a fixed field structure that the server can more readily deal with.
As my boss said when we finally figured out the solution. When it comes to this system we are dealing with, you can't just break some of the rules. You have to break all of them, and when you break enough of them, you wind up back where you should have been to begin with.
Comments: Post a Comment