{"id":769,"date":"2010-01-07T00:00:00","date_gmt":"2010-01-07T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/13-things-you-should-know-about-statistics-and-the-query-optimizer\/"},"modified":"2021-09-29T16:22:02","modified_gmt":"2021-09-29T16:22:02","slug":"13-things-you-should-know-about-statistics-and-the-query-optimizer","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/13-things-you-should-know-about-statistics-and-the-query-optimizer\/","title":{"rendered":"13 Things You Should Know About Statistics and the Query Optimizer"},"content":{"rendered":"
\n

You don’t you think thirteen is a good number? Well, here in Brazil we’ve a famous soccer player and coach called Mario Zagalo<\/a> who really likes it. This obviously has nothing at all to do with Query Optimizer, so let’s get started with the good stuff.<\/p>\n

When we are talking about query plans and optimization, there are some things that you really should know. The SQL Query Optimizer employs many techniques to create a optimal execution plan, and today I’ll present some terminology and features used.<\/p>\n

\n

1 – Selectivity<\/h2>\n

We can define selectivity as:<\/p>\n

The degree to which one value can be differentiated within a wider group of similar values<\/em>.<\/p>\n

For instance, when Mario Zagalo was a coach of Brazilian soccer team, one of his hardest jobs was select the players for each match. Brazil is a huge country and, as you probably know, we have a lot of very good players. So, the selectivity of good players in Brazil is very low, because there are a lot of them. If I ask to you to select just players who would make good attackers, you would probably return to me with a lot of guys, and returning with many players lowers the selectivity.<\/p>\n

In database terms, suppose we have a table called Internationally_Renown_Players<\/em> with a column called Country<\/em>. If we write:<\/p>\n

SELECT * FROM Internationally_Renown_Players WHERE Country= 'Brazil'<\/pre>\n
\u00a0… then we can say that this query is not very selective, because many rows will be returned (Update<\/strong>: Sadly, this didn’t help us in the 2010 World Cup). However, if we write:<\/p>\n
SELECT * FROM Internationally_Renown_Players WHERE Location = 'Tuvalu'\r\n<\/pre>\n
… then this query will be very selective, because it will return very few rows (I know if they have a soccer team, but they have yet to really make a name for themselves.)<\/p>\n
Another good (and broader interest) example would be to have a table called Customers, with columns for Gender and, say, Passport_Number. The selectivity of the Gender column is very low because we can’t do much filtering with just the F<\/em> or M<\/em> values, and so many rows will be returned by any query using it. by contrast, a query filtering with the Passport_Number column will always return just one row, and so the selectivity of that column is very high.<\/p>\n
Why You Should Know This<\/h4>\n
\u00a0<\/strong>The Query Optimizer use Selectivity information to create the execution plans, and \u00a0can decide on an optimal execution plan based on the selectivity of a given column. It is also clearly good practice is create your indexes on the columns with a highest selectivity level. That means it is better to create a index on a Name<\/em> column than a Gender column. It is also better create a composite index<\/a> in a order to make use of the most selective column first, and thus increase the chances that the SQL Server will actually use<\/em> that index.<\/p>\n
\n
2. Density<\/h2>\n
The term “density<\/em>” comes from physics, and is calculated by the dividing the mass of a substance by the volume it occupies, as represented mathematically below.<\/p>\n
\"909-13things_clip_image002.jpg\"<\/p>\n
Where D = Density, M = Mass and V = Volume.<\/p>\n
The explanation can be stretched, as is the case with “Geographic Density<\/em>” (something we’ve become used to hearing and understanding); For example, the geographic density of Brazil is calculated by dividing the number of habitants (or the ‘mass’) by the size of the geographic area (the ‘volume’, which is 187,000,000 people divided by 8,514,215.3 km2, which gives us 21.96 habitants per km2. In SQL Server, we can interpret this as:<\/p>\n
The more dense a column is, more rows that column returns for a given query. <\/em><\/p>\n
Take note that is exactly the opposite<\/em> of selectivity, for which a higher value means less<\/em> rows. To calculate the density of a column, you can run the following query:<\/p>\n
SELECT (1.0 \/ COUNT(DISTINCT <ColumnName>)) FROM <TableName> <\/pre>\n
… The\u00a0larger a number that query returns, the more ‘dense’ your column is, and the more duplications it contains. With this number, the QO can determine two important facts about the frequency of data of a column, and to explain this better, let’s create an example table.<\/p>\n
CREATE TABLE Test(Col1 INT)\r\nGO\r\nDECLARE @i INT\r\n\u00a0\u00a0\u00a0\u00a0SET @I = 0\r\nWHILE @i < 5000\r\n\u00a0\u00a0\u00a0\u00a0BEGIN\r\n\u00a0\u00a0\u00a0\u00a0INSERT INTO Test VALUES(@i)\r\n\u00a0\u00a0\u00a0\u00a0INSERT INTO Test VALUES(@i)\r\n\u00a0\u00a0\u00a0\u00a0INSERT INTO Test VALUES(@i)\r\n\u00a0\u00a0\u00a0\u00a0INSERT INTO Test VALUES(@i)\r\n\u00a0\u00a0\u00a0\u00a0INSERT INTO Test VALUES(@i)\r\n\u00a0\u00a0\u00a0\u00a0SET @i = @i + 1\r\n\u00a0\u00a0\u00a0\u00a0END\r\nGO\r\nCREATE STATISTICS Stat ON Test(Col1)\r\nGO\u00a0\u00a0<\/pre>\n
As you can see, we have a table with 25,000 rows, and each value is duplicated across five rows; so the density is calculated as 1.0 \/ 5000 = 0.0002. \u00a0The first question we can answer that that information is: “How many unique values do we have in the column ‘Col1’?” Just<\/em> using the density information we can make the following, 1.0 \/ 0.0002 = 5000. The second question is: “What is the average number of duplication per value in the ‘Col1’ column?” Using the density information we can calculate: 0.0002 * 25000 = 5 (Which is exactly the average of duplicated values in this case).<\/p>\n
Why You Should Know This<\/strong><\/h4>\n
Using the table created above, let’s see where the SQL Server uses that information in practice. Take the following query:<\/p>\n
DECLARE @I INT\r\nSET @I = 999999\r\nSELECT * \r\n\u00a0\u00a0\u00a0\u00a0FROM Test\r\n\u00a0\u00a0\u00a0\u00a0WHERE Col1 = @I<\/pre>\n
\"909-13things_clip_image002_0000.jpg\"<\/p>\n
The SQL Server will use the information about the average density to estimate how many rows will be returned (in this case, 5 rows). We will see more about why<\/em> the SQL uses the density information in the section 7.<\/p>\n
Another example:<\/p>\n
SELECT COUNT(*) FROM Test\r\n\u00a0\u00a0\u00a0\u00a0GROUP BY Col1<\/pre>\n
\"909-13things_clip_image004.jpg\"<\/p>\n
\"909-13things_clip_image006.jpg\"<\/p>\n
In the first step, the Table Scan operator estimates that 25000 rows will be returned, and then after the Hash Mach Operator applies the Group By, only 5000<\/em> rows will be returned. In that case, SQL Server uses the information about how many unique rows are in the column.<\/p>\n
The density information used to give the QO an impression of how many duplicated rows exist in a column, which allows it to chose the optimal operator or join algorithm in an execution plan. In certain cases, the QO also uses density information to guess how many rows will be returned by a query – look at section 5 for more details.\u00a0<\/p>\n
\n
3. Cardinality<\/h2>\n
This is used to measure the number of rows which satisfy one condition. For instance, imagine one table with 500 rows, and a query with “WHERE NAME = ‘Joao'”<\/em> – the Optimizer goes to the statistics and reads from the histogram that ‘Joao’ represents 5% of the table, so the cardinality is (5% x 500) = 25. In the execution plan, we can think of the cardinality as the “estimated number of rows” displayed in the tool tips of each operator. I probably don’t need to spell it out, but a bad estimation of cardinality can easily result in an inefficient plan.<\/p>\n
Why you should know that<\/h4>\n
In my opinion, the cardinality of a column is one of the most important pieces of information to the creation of an efficient execution plan. To create an execution plan, we really need to know (or at least be able to make a decent estimate about) how many rows will be returned to each operator. \u00a0For example, a join query which returns a lot of rows would be better processed with a hash join; But if the QO doesn’t know about the cardinality, it can mistakenly chose to use a Loop Join or, even worst, chose to order the key columns to make use of a merge join!<\/p>\n
\n
4. SARG<\/h2>\n
SARGs (Search Arguments) are the conditions of your query; The value you include in WHERE = “…”<\/em> is the value passed to the search. With that information, the Optimizer will estimate how many rows will be returned and what is the best way(plan) to read this data. In the other words, based on the SARG, the QO analyses the selectivity, density and cardinality to get the best possible execution plan.<\/p>\n
Why you should know that<\/h4>\n
Queries with good SARGs are used to filter returned data, as when less data is selected, fewer pages will need to be read, and that will manifest itself as a huge performance gain.<\/p>\n
\n
\n
Interlude<\/h2>\n
Many SQL Server books and Query Processor references uses these four core terms described \u00a0above (Selectivity, Density, Cardinality and SARG) to explain the behavior of a query plan, so hopefully this knowledge will make things a little clearer for you in the future.<\/p>\n<\/div>\n
\n
5. Foldable Expressions<\/h2>\n
Early on in the optimization phase, the QO tries to change your query to evaluate an expression, and then change that expression to a constant. A constant is a literal value like such as ‘1’, ‘Peter’, ‘10.50’, ‘20090101’, etc. This method is known as Constant Folding.<\/p>\n
A simple example of Constant Folding is the expression “<column> = 1+1″<\/em>; early in the optimization process, the QO would change that expression to “<column> = 2<\/em>“, and then use the value ‘2’ as a SARG<\/strong>. Another interesting example is that the QO would change “<column> = REPLACE(‘123xxx’, ‘xxx’, ‘456’)”<\/em> to simply “<column> = ‘123456’”<\/em>.<\/p>\n
Why You Should Know This<\/h4>\n
It is good to know where the QO can do this, because that can make our queries a little easier to write. It is also worth bearing in mind that an exception is made for large object types. If the output type of the folding process is a large object type (text, image, nvarchar(max), varchar(max), or varbinary(max)), then SQL Server does not<\/em> fold the expression.<\/p>\n
\n
6. Non-foldable Expressions<\/h2>\n
An expression is considered non-foldable when the SQL Server cannot evaluate the expression, which causes a bad estimation of cardinality and a bad execution plan. We will see some examples in the next section (7) of when the use of some expressions blocks the use of statistics for a column.<\/p>\n
Why You Should Know This<\/h4>\n
Well basically, you should know to avoid the use of these constructions in your query, as they’ll just make life more difficult. To avoid this, instead of using, say ABS(-1000),<\/em> you could use (-1000 * -1)<\/em>, or pass the expression to a variable and then use that variable in your query, as in:<\/p>\n
SELECT * FROM Tab1\r\nWHERE Col1 < ABS(-78150)\r\n\r\n-- Use a variable with the recompile clause, to force the QO read the value of @Var\r\nDECLARE @Var INT\r\nSET @Var = ABS(-1000)\r\n\r\nSELECT * FROM CONVE002\r\nWHERE ID_Pessoa < @Var\r\nOPTION(RECOMPILE))<\/pre>\n
\n
7. What Happens When the Query Optimizer Can’t Estimate the Cardinality of a SARG?<\/h2>\n
The cardinality, density and selectivity of a value or a column are the heart of the matter, and the QO will always try to use these pieces of information to get an execution plan. When possible during the optimization stage, the QO tries to simplify your search arguments into constants. We’ve already covered this section 5, and we know that:<\/p>\n