From books online:
Indexing small tables may not be optimal because it can take the query optimizer longer to traverse the index searching for data than to perform a simple table scan. Therefore, indexes on small tables might never be used, but must still be maintained as data in the table changes.
I was having a debate with a co-worker the other day and we were talking about a small table (heap) that had absolutely no indexes. There are 35k rows in just over 1,000 pages.
My co-worker was of the opinion that this was a "small" table. This is a 90+% read lookup table (heap), and I was able to show that after creating a clustered index and a single non-clustered composite index of three key columns and a few included columns that I could now cover the query, and reduced the 1048 logical reads of a table scan to a 2 logical read index seek.
So this specific example aside, and given that mileage will vary, my question is are there general rules of thumb for what is the threshold for a "small" table?
I started thinking in terms of storage internals, that if a table is sized so it fits in under 8 pages (a single extent) that SQL Server would effectively read the entire table during a normal disk read, then there would be absolutely no benefit from indexes. It seems like once we cross the 8 page threshold, adding at least one non-clustered index should prove beneficial. I know now we're venturing into a bit of the theoretical realm, but I'm curious what are the technical boundaries for when we can expect to see benefits.
For the purposes of this (theoretical) discussion lets leave out the "tipping point" and assume any non-clustered indexes we may create are covering, and that queries are not predicated on the clustering key. There may be other assumptions necessary for a debate, so please feel free to add.