There might be a few more inputs, but these are the main ones. The first step which often is decisive for the performance of the query is to estimate how many rows the query might deliver back based on the inputs above. It is not only estimated how many rows the query would deliver. In order to decide for the correct join method in e.g. a table join, one also needs to estimate how many rows would be delivered by each execution step and query branch accessing each of the tables involved in the join. This is done in the so called Cardinality Estimation (referred to as CE from now), which this article is about. The estimated number of rows will be the base for the next step of query optimization assuming that the estimated number of rows is correct. This means the choice of picking a certain index or the choice of a join order or join type is majorly impacted by the first step of estimating the cardinality of a query.<\/p>\n
If that estimation is plain wrong, one can\u2019t expect that the subsequent steps of query optimization will be able to derive an efficient plan, unless the query itself leans to a particular index like querying exactly one row by specifying the Primary Key or hardly any indexes are available to be used.<\/p>\n
In order to estimate the number of rows returned, CE requires the statistics over indexes and columns of tables as a reliable source of information to figure out how often a certain value of a parameter value, submitted with the query, is present. Hence if there are no statistics or plain wrong or stale statistics, the best CE logic will hardly be able to predict the right values of returning rows for a query.<\/p>\n
The role CE is playing in the process to generate a good query plan is important. One hardly can expect a great Query Execution Plan as a result when the CE would estimates would be completely off workload which required SQL Server code fixes circled around issues in Cardinality Estimation.<\/p>\n
What changed in SQL Server 2014?<\/b><\/p>\n
At a very high level, the CE process in SQL Server 2012 was the same through all prior releases back to SQL Server 7.0 (the release before SQL 2000). In recent years we tried to put a lot of fixes or QFEs in regards to query optimization (including cardinality estimation) under trace flag in order not to cause a general regression over all those releases due to changed behavior by the fix.<\/p>\n
With the release of SQL Server 2014, there were several good reasons to overhaul what was basically the CE as introduced 15 years ago. Our goals in SQL Server Development certainly were to avoid issues we so far experienced over the past 15 years and which were not fixable without a major redesign. However to state it pretty clearly as well, it was NOT a goal to avoid any regressions compared to the existing CE. The new SQL Server 2014 CE is NOT integrated following the principals of QFEs. This means our expectation is that the new SQL Server 2014 CE will create better plans for many queries, especially complex queries, but will also result in worse plans for some queries than the old CE resulted in. To define what we mean by better or worse plans, better plans have lower query latency and\/or less pages read and worse plans have higher query latency and\/or more pages read.<\/p>\n
Knowing that the CE has changed and purposefully was not overcautiously re-architected to avoid regressions, you need to prepare a little more carefully for a SQL Server 2014 upgrade if you will utilize the new Cardinality Estimator. Based on our experience so far, you need to know first:<\/p>\n
- \n
- As of January 2014, feedback about the new CE is very good, showing only a small number of cases where query performance showed regressions compared to the old CE<\/li>\n
- Whether the overall picture with the new CE is positive or negative is dependent on the nature of the queries the workload is generating and the distribution of the data<\/li>\n
- Even with ISV applications it is not always easy to tell whether certain ISV application benefit from the new CE or not. Reason is that a lot of ISV applications are highly customizable and therefore can produce very different workload when used by different customers. \u00a0<\/li>\n<\/ul>\n
Activation\/De-Activation of the new CE<\/b><\/p>\n
As delivered, SQL Server 2014 decides if the new Cardinality Estimator will be utilized for a specific database based simply on the compatibility level of that database within the SQL Server 2014 instance. In case the compatibility level of a specific database is set to \u2018SQL Server 2014 (120)\u2019 as shown below, the new CE is going to be used.<\/p>\n
![\"](\"https:\/\/www.microsoft.com\/en-us\/sql-server\/blog\/wp-content\/uploads\/2018\/03\/CE.png\")
<\/a><\/p>\nIf the Compatibility level of a specific database is set to a lower value, like \u2018SQL Server 2012 (110)\u2019, the old CE is going to be used for the specific database.<\/p>\n
As with other releases of SQL Server, upgrading your SQL Server instances in place or attaching existing databases from earlier releases of SQL Server will not result in a change of the compatibility level of a database. Hence by purely upgrading a SQL Server instance or attaching a database from SQL Server 2012 or earlier releases will not activate the new CE. One would need to change the compatibility level of such a database manually to \u2018SQL Server 2014 (120)\u2019 to activate the new CE. However toggling between the compatibility levels of 110 and 120 in case of SQL Server 2014 does have some other impact beyond the change of CE algorithms. E.g. the parallel insert functionality of SELECT INTO would be disabled by staying on the old compatibility levels as well.<\/p>\n
Another alternative to enable\/disable the different CE algorithms is the usage of a trace flag. Even with the compatibility level of a database set to \u2018SQL Server 2014 (120)\u2019, the trace flag would enforce the usage of the old CE. In opposite to the compatibility level which is applied to a specific database, the trace flag, if used as startup trace flag, would affect the usage of the CE SQL Server instance wide. This behavior might not be desired when many different databases are run in one instance. However, for situations where one runs one user database per SQL instance or consolidates several databases of a type of application under one SQL server instance, it indeed might make sense to use the trace flag approach. In order to force the old CE algorithms, trace flag 9481 can be used as startup trace flag.<\/p>\n
Why can query plans change with the new CE?<\/b><\/span><\/p>\n
Calculate combined density of filters differently<\/b><\/p>\n
In this section we refer quite a bit to index or column statistics and the specific data that is captured in those. For folks less familiar with how index or column statistics are structured and what is contained in those, it would be advisable to read the Microsoft TechNet article, \u201cStatistics Used by the Query Optimizer in Microsoft SQL Server 2008<\/a>\u201d before continuing.<\/p>\n
One of the most significant changes in the new CE is the way how the CE calculates the selectivity of a combination of filters submitted with a query. In the old CE, the assumption was that the selectivity of the filters was independent, assuming any combination of values stored in the different columns the filters are applied to, would have the same probability of occurring. However very often reality is that combinations of values of different columns are not as independent. We can find masses of cases where values in different column within one table are not independent of each other. Think about a car brand like Toyota, Volkswagen, Ford, Mercedes, etc being represented in one column and the type like Corolla, Jetta, Focus or E-Class being represented in another column of the table. It immediately becomes clear that certain combinations can\u2019t happen since Volkswagen is not producing a car named \u2018Corolla\u2019.<\/p>\n
Let\u2019s see at what the differences really are in the calculation of selectivity.<\/p>\n
Let\u2019s assume the following indexes against a table like this:<\/p>\n
\n\n
\n \n index_name<\/b><\/p>\n<\/td>\n
\n index_description<\/b><\/p>\n<\/td>\n
\n index_keys<\/b><\/p>\n<\/td>\n<\/tr>\n
\n \n FILCA~0<\/p>\n<\/td>\n
\n clustered, unique, primary key located on PRIMARY<\/p>\n<\/td>\n
\n RCLNT, GL_SIRID<\/p>\n<\/td>\n<\/tr>\n
\n \n FILCA~1<\/p>\n<\/td>\n
\n nonclustered located on PRIMARY<\/p>\n<\/td>\n
\n RCOMP, RACCT, RYEAR, RVERS, RLDNR<\/p>\n<\/td>\n<\/tr>\n
\n \n FILCA~2<\/p>\n<\/td>\n
\n nonclustered, unique located on PRIMARY<\/p>\n<\/td>\n
\n DOCNR, DOCCT, RLDNR, RYEAR, RCOMP, ROBUKRS, DOCLN, RCLNT<\/p>\n<\/td>\n<\/tr>\n
\n \n FILCA~3<\/p>\n<\/td>\n
\n nonclustered located on PRIMARY<\/p>\n<\/td>\n
\n REFDOCNR, REFRYEAR, REFDOCCT, RCOMP, ROBUKRS, RLDNR, RCLNT, REFDOCLN<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\u00a0<\/p>\n
The query issued against the table looks like:<\/p>\n
SELECT<\/span><\/p>\n
\u00a0 *<\/span><\/p>\n
FROM<\/span><\/p>\n
\u00a0 “FILCA”<\/span><\/p>\n
WHERE<\/span><\/p>\n
\u00a0 “RCLNT” = ‘001’<\/span> AND “RLDNR” = ’10’<\/span> AND “RRCTY” = ‘0’<\/span> AND “RVERS” = ‘001’<\/span> AND “RCOMP” = ‘ABXYZ’<\/span><\/span><\/p>\n
\u00a0 AND “RACCT” = ‘1212121212’<\/span> AND “RMVCT” = ”<\/span> AND “RYEAR” = ‘1997’<\/span> AND “RLEVL” = ‘0’<\/span> AND “DOCTY” = ”<\/span><\/p>\n
\u00a0 AND “POPER” BETWEEN ‘001’<\/span> AND ‘006’<\/span> AND “DOCCT” = ‘A’<\/span><\/span><\/p>\n
SQL Server\u2019s query optimizer using the old CE would choose the first non-clustered index (FILCA~1) to access the table. This means there would be five filters which could be applied since all the five columns of the ~1 index are specified in the query.<\/p>\n
In the single column statistics the densities of each single column look like:<\/p>\n
\n\n
\n \n Column Name<\/p>\n<\/td>\n
\n Density<\/p>\n<\/td>\n<\/tr>\n
\n \n RAACT<\/p>\n<\/td>\n
\n 0.125<\/p>\n<\/td>\n<\/tr>\n
\n \n RVERS<\/p>\n<\/td>\n
\n 0.3333<\/p>\n<\/td>\n<\/tr>\n
\n \n RCOMP<\/p>\n<\/td>\n
\n 0.5<\/p>\n<\/td>\n<\/tr>\n
\n \n RLDNR<\/p>\n<\/td>\n
\n 0.5<\/p>\n<\/td>\n<\/tr>\n
\n \n RYEAR<\/p>\n<\/td>\n
\n 1<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Treating the selectivity\/density of each filter\/column independently, the question of the overall density would be:<\/p>\n
0.125 * 0.3333 * 0.5 * 0.5 * 1 = 0.0104<\/p>\n
A value which is confirmed when we look at the combined densities displayed in the statistics of index FILCA~1:<\/p>\n
\n\n
\n \n All density<\/p>\n<\/td>\n
\n Average Length<\/p>\n<\/td>\n
\n Columns<\/p>\n<\/td>\n<\/tr>\n
\n \n 0.5<\/p>\n<\/td>\n
\n 11.14286<\/p>\n<\/td>\n
\n RCOMP<\/p>\n<\/td>\n<\/tr>\n
\n \n 0.0625<\/p>\n<\/td>\n
\n 31.14286<\/p>\n<\/td>\n
\n RCOMP, RACCT<\/p>\n<\/td>\n<\/tr>\n
\n \n 0.0625<\/p>\n<\/td>\n
\n 39.14286<\/p>\n<\/td>\n
\n RCOMP, RACCT, RYEAR<\/p>\n<\/td>\n<\/tr>\n
\n \n 0.02083333<\/p>\n<\/td>\n
\n 45.14286<\/p>\n<\/td>\n
\n RCOMP, RACCT, RYEAR, RVERS<\/p>\n<\/td>\n<\/tr>\n
\n \n 0.01041667<\/b><\/span><\/p>\n<\/td>\n
\n 49.14286<\/b><\/span><\/p>\n<\/td>\n
\n RCOMP, RACCT, RYEAR, RVERS, RLDNR<\/b><\/span><\/p>\n<\/td>\n<\/tr>\n
\n \n 0.01041667<\/p>\n<\/td>\n
\n 55.14286<\/p>\n<\/td>\n
\n RCOMP, RACCT, RYEAR, RVERS, RLDNR, RCLNT<\/p>\n<\/td>\n<\/tr>\n
\n \n 3.60E-05<\/p>\n<\/td>\n
\n 89.14285<\/p>\n<\/td>\n
\n RCOMP, RACCT, RYEAR, RVERS, RLDNR, RCLNT, GL_SIRID<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Assuming an even distribution over the values of the columns, we can assume density values as those displayed above. Be aware that CE using parameter sniffing would use the particular density value for a submitted value if the data distribution is uneven. But for simplicity reasons we assume an even distribution. \u00a0Having a very small number of rows in our table of only 27776 rows, the estimated number of rows basically was calculated out of:<\/p>\n
# of rows \/ (1\/combined density) which would be:\u00a0\u00a0 27776\/(1\/0.01041667) = 289.33<\/p>\n
This means CE would expect to get 289 rows back using this index FILCA~1<\/p>\n
Looking at the query it becomes clear that using the non-clustered index, not all columns could be filtered that were specified in the where clause. After reading the 289 entries of the non-clustered index, the real data rows would be read and the additional column filters applied then.<\/p>\n
Now to the change with the new CE, where we assume that the combination of the different column values are not as independent. The assumption is that certain combinations of values are not coming up at all, whereas others are showing up more frequently. Besides the example with car brands and their car types, other examples of such dependencies between columns are found in all business processes and therefore in the underlying data in database tables. For example, materials or goods that are produced or stored in certain locations and warehouses only would have such a data dependencies. Or, employees associated with a certain profit center or organization would also have such a data dependencies. This means the reality is that the values in different columns are sometimes related to each other. In order to reflect that in the calculation of the possible selectivity\/density, we apply a new formula with a so called \u2018exponential back-off\u2019. The logic would work like:<\/p>\n
- \n
- Sort the filters according to their density where the smallest density value is first. Since the density is expressed in a range between 0.xxxx and 1 the smaller values means lower density, better selectivity or more different values.<\/li>\n
- We also would use the first four most selective filters only to calculate the combined density. Looking at the formula we use, it becomes clear why 5th<\/sup>and more density values will not make big impact anymore. In our cases the order would look like:\n
- \n
- 0.125, 0.3333, 0.5, 0.5 in single column density values of the filters which can be applied to the non-clustered index FILCA~1.<\/li>\n<\/ul>\n<\/li>\n
- The calculation formula now would d1 * d2^(1\/2) * d3^(1\/4) * d4^(1\/8)<\/li>\n<\/ul>\n