When does a database table get large enough that an index is beneficial?

Question

Hypothetically, in a SQL Server database, if I have a table with two int fields (say a many-to-many relation) that participates in joins between two other tables, at what approximate size does the table become large enough where the performance benefit of indexes on the two int fields overcomes the overhead imposed by said indexes?

Are there differences in architecture between different versions of SQL Server that would substantially change this answer?

Update: Quassnoi gets the selected answer for his detailed insight into query execution plans. For me, I think the most important point is that the SQL Server Optimizer will optimize out the index if necessary, so there is really no penalty for having an index on every foreign key (other than the inserting overhead), and I won't have to think about adding an index later when the table reaches some (undetermined) size.

Answer 1

I believe as soon as you start doing joins on those int fields your table is big enough. If the table is small enough that it wouldn't benefit from an index then the overhead wouldn't be significant enough that you would want to opt out.

When I think about the overhead due to an index I usually consider how often the table index will be changing--through inserts, deletes and updates to indexed columns.

Answer 2

The index will nearly always increase the performance of the query, at the cost of extra memory and performance cost for insert/deletion (since it needs to maintain the index at that point). Profiling will be the only definite way to tell whether or not the index, in your particular case, is beneficial.

In general, you're trading memory for speed when you create an index (other than the additional cost of insertion). If you're doing many queries (selects or updates) relative to the number of inserted/deleted rows, indexes will pretty much always increase your performance.

Answer 3

it depends on the selectivity of your data, if your data is not selective enough then the index might not even be used since the cost would be too expensive. If you have only 2 values in the table and these values are evenly distributed then you will get a scan not a seek

I still believe every table should have a Primary Key, if you have that then you also have an index already

Answer 4

The penalty for insertion will be negligible until long after the benefit of the indexes will appear. The optimizer is smart enough to ignore the indexes anyway until that point clicks in. So just index the table from the start.

Answer 5

Another thing to think about is the concept of coding performance-- sometimes having an index can streamline the mental overhead of thinking about how to manage the relationship between different pieces of data. sometimes it can complicate it...

Answer 6

For the queries involving small portions of the table rows, indexes are always beneficial, be there 100 rows or 1,000,000.

See this entry in my blog for examples with plans and performance details:

• Indexing tiny tables

The queries like this:

SELECT  *
FROM    table1 t1
JOIN    table2 t2
ON      t2.col = t1.col

will most probably use HASH JOIN. A hash table for the smaller table will be built, and the rows from the larger table will be used to probe the hash table.

To do this, no index is needed.

However, this query:

SELECT  *
FROM    table1 t1
JOIN    table2 t2
ON      t2.col = t1.col
WHERE   t1.othercol = @value

will use NESTED LOOPS: the rows from the outer table (table1) will be searched using an index on table1.othercol, and the rows from the inner table (table2) will be searched using an index on table2.col.

If you don't have an index on col1, a HASH JOIN will be used which requires scanning all rows from both tables and some more resources to built a hash table.

Indexes are also useful for the queries like this:

SELECT  t2.col
FROM    table1 t1
JOIN    table2 t2
ON      t2.col = t1.col

, in which case the engine doesn't need to read table2 itself at all: eveything you need for this query can be found in the index, which can be much smaller than the table itself and more efficient to read.

And, of course, if you need your data sorted and have indexes on both table1.col and table2.col, then the following query:

SELECT  *
FROM    table1 t1
JOIN    table2 t2
ON      t2.col = t1.col
ORDER BY
        t2.col

will probably use MERGE JOIN method, which is super fast if both input rowset are sorted, and its output is also sorted, which means that ORDER BY comes free.

Note that even if you don't have an index, an optimizer may choose to Eager Spool your small table, which means building a temporary index for the duration of the query and dropped the index after the query finishes.

If the query is small, it will be very fast, but again, an index won't hurt (for SELECT queries I mean). If the optimizer won't need it, it just will not be used.

Note, though, that creating an index may affect DML performance, but it's other story.

Answer 7

Regardless of size, there is always a performance benefit to using an index when doing a lookup.

Regarding overhead, the question becomes: what overhead do you mean, and how do you relate it to the value of a lookup? The two are separate values, after all.

There are two forms of overhead for an index: space (which is usually negligible, depending on how the index is structured), and re-index on insert (the server must recalculate an index after every insert).

As I mentioned, the space issue probably isn't that big a deal. But re-indexing is. Fortunately, you need to be doing lots of near-continuous inserting before that form of overhead becomes a problem.

So bottom line: You're almost always better off having an index. Start from that position and wait until re-indexing becomes a bottleneck. Then you can look into alternatives.

Answer 8

A very useful link: "The Tipping Point Query Answers" http://www.sqlskills.com/BLOGS/KIMBERLY/post/The-Tipping-Point-Query-Answers.aspx

Answer 9

The best thing is to let the server itself figure it out. You create index in the columns where it makes sense(Im sure there's entire chapters if not books on how to do this the best way), and let the SQL server figure out when/how to use the index.

In many cases, when optimizing, you'd need to read the docs of your particular DBMS to learn more how it uses indexes, and relate that to the queries the application you're optimizing uses. Then you can fine tune the index usage.