What does "Create Statistics" do in SQL Server 2005?

Cost Based Query Optimisation is a technique that uses histograms and row counts to heuristically estimate the cost of executing a query plan. When you submit a query to SQL Server, it evaluates it and generates a series of Query Plans for which it uses heuristics to estimate the costs. It then selects the cheapest query plan.

Statistics are used by the query optimiser to calculate the cost of the query plans. If the statistics are missing or out of date it does not have correct data to estimate the plan. In this case it can generate query plans that are moderately or highly sub-optimal.

SQL Server will (under most circumstances) generate statistics on most tables and indexes automatically but you can supplement these or force refreshes. The query tuning wizard has presumably found some missing statistics or identified joins within the query that statistics should be added for.

Statistics are used by the optimizer to determine whether to use a specific index for your query. Without statistics, the optimizer doesn't have a way to know about how many of your rows will match a given condition, causing it to have to optimize for the "many rows" case, which could be less-than-optimal.

In a nutshell, it prepares your database to work effectively. By having prepared statistics, your database knows (before it needs to figure out an execution plan) what is likely to be its most efficient route.